Filling a screen with rectangles - a brain teaser | Together C & C++ | Page 1

woeful dove Jul 7, 2023, 4:58 AM

#

Hey kids, here's something to bake your noodle.

I have a full screen - say 800x480 at 16-bit color.

Therein, I have a 32kB window. This window allows me the memory to create up to a 128x128 bitmap at 16-bit color. Or 64x256. Or any rectangular region with that same area or less.

Creating rectangles using all available area is the ideal choice, but less area also works.

For a given screen, there are already rectangles of various sizes populating it at various locations, of various sizes, any area and potentially overlapping each other (but uncommon to do that). These rectangles must be filled around and otherwise untouched.

The goal is to fill the entire screen with as few rectangles as possible, each up to 32kB (128x128) in area.
I've come up with some code in the comments

naive glacierBOT Jul 7, 2023, 4:58 AM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

bright prawn Jul 7, 2023, 7:50 AM

#

The first idea is to look through the pixels, left to right, top to bottom, until you find a hole. Then fill that pixel with a rectangle. Then expand the rectangle to the right until you hit a wall or the 128 limit. Then expand it down until you hit a wall, the 128 limit or both side walls fall away.

#

Proving that this is optimal is too difficult for me.

#

Hmm, it's not, I can think of a case where it fails.

#

Maybe there is a smarter way than looping through all pixels to get the holes as well.

tribal locust Jul 7, 2023, 9:04 AM

#

my gut tells me that doing this with the minimum number of rectangles is gonna be np hard ^^

woeful dove Jul 7, 2023, 1:56 PM

#

yeah

#

the solution is most likely a variant of the tiling algorithm https://www.geeksforgeeks.org/tiling-problem-using-divide-and-conquer-algorithm/

GeeksforGeeks

Tiling Problem using Divide and Conquer algorithm - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

#

however, in that demonstration the filled rects are on a grid. They are not on a grid in my problem

tribal locust Jul 7, 2023, 1:58 PM

#

to be clear, if it's just about finding rectangles that fill the space, your problem can ofc be solved, and it's not too hard. it's just finding the optimal solution that is very hard.

woeful dove Jul 7, 2023, 1:58 PM

#

i could subdivide the grid smaller and smaller until all the rects fit, but then i have another problem of expanding all the little rects into larger composite rects

#

sure @tribal locust - and i might settle on a less optimal solution for now that i can improve later

#

it's still early for me and my brain isn't firing on all cylinders rn

tribal locust Jul 7, 2023, 1:59 PM

#

i think you'll have to tbh, unless the number of rectangles is small enough for simple brute force search to be viable

#

there are probably algorithms that can give you a solution that's guaranteed to be not further away from the optimal than some bound or smth

#

but i'm just guessing ^^

woeful dove Jul 7, 2023, 2:00 PM

#

the number of filled rects is small. this is for screens whose max res is probably 800x480 or so

tribal locust Jul 7, 2023, 2:00 PM

#

how many rects are you talking about?

woeful dove Jul 7, 2023, 2:00 PM

#

so you really don't have that many rects. Not 100s. You're dealing in 10s of rects at most

#

often less in a lot of cases

#

i'd say maybe 25 max

tribal locust Jul 7, 2023, 2:01 PM

#

well, 10 might already be borderline for brute-force search given the shier number of possibilities. depends on how much time you have ^^

woeful dove Jul 7, 2023, 2:01 PM

#

fair enough

#

that wouldn't work then

#

tends to be exponential complexity with brute force methods

tribal locust Jul 7, 2023, 2:01 PM

#

yeah

#

that's the problem ^^

#

2^10 might be doable

#

2^25… dunno

#

possible still, sure, depends on how much time you have

woeful dove Jul 7, 2023, 2:02 PM

#

maybe if i describe the problem at a high level. maybe this algo isn't the right approach. bear with me

#

i have a number of control widgets on a display screen

#

I have a 32kB transfer buffer to move bitmap data to a display. that means i go through my dirty rects and subdivide them into 32kb regions top to bottom and draw the controls therein as many times as needed to fill those regions. does that make sense so far?

tribal locust Jul 7, 2023, 2:03 PM

#

i see

#

that explains the weird thing with the buffer ^^

woeful dove Jul 7, 2023, 2:04 PM

#

problem is some controls are slow to draw, so when i do a full screen refresh, it's drawing 800px wide, and very short, so at it passes over controls, they need to be drawn multiple times

#

i'm trying to improve that

#

by 800px wide and very short, i mean like the 32kb region is 800px wide, and i don't know, 16px tall or something

tribal locust Jul 7, 2023, 2:05 PM

#

that is a really weird display connection you have there xD

woeful dove Jul 7, 2023, 2:05 PM

#

it's due to using DMA on IoT over a slow bus

tribal locust Jul 7, 2023, 2:06 PM

#

and there's no memory on the side where the display is so that you could do double buffering?

woeful dove Jul 7, 2023, 2:06 PM

#

there is, and everything is effectively double buffered due to this 32kB "bitmap" being drawn to and then sent

#

so you have like this

#

controls -> draw surface bitmap (32kB) -> sent to screen via DMA

tribal locust Jul 7, 2023, 2:07 PM

#

but if it's double buffered then you can build up the new image from thes 32 KiB chunks and then swap buffers only once that is done?

woeful dove Jul 7, 2023, 2:07 PM

#

that's what i do

tribal locust Jul 7, 2023, 2:07 PM

#

i see

woeful dove Jul 7, 2023, 2:07 PM

#

and i actually have two buffers. i send one while writing to the other

#

they are 32kB each. but that's an implementation detail

#

it shouldn't affect the algo i need

tribal locust Jul 7, 2023, 2:07 PM

#

yeah i see

#

so it's effectively pipelined using the DMA engine to transfer while the CPU fills the next buffer

woeful dove Jul 7, 2023, 2:08 PM

#

yes

tribal locust Jul 7, 2023, 2:08 PM

#

k

#

and you only update certain parts of the screen?

woeful dove Jul 7, 2023, 2:08 PM

#

not all cases. some displays don't do DMA. in that case i give it 1 64kB buffer

#

yes, only dirty portions

#

but i'm using a full dirty screen as a baseline for this algo

#

i'll adjust the algo to do this for each dirty rect

tribal locust Jul 7, 2023, 2:09 PM

#

800×480 you say with 16-bit color?

woeful dove Jul 7, 2023, 2:09 PM

#

yep

#

that's not the only one

#

240x135 is actually what i'm testing on rn

#

i need a general algo

#

and one display is 128x64 monochrome 😛

#

for that one this doesn't matter

tribal locust Jul 7, 2023, 2:10 PM

#

ok so really, this is about packing a given set of dirty rects into a series of 32 KiB buffers to be sent

woeful dove Jul 7, 2023, 2:10 PM

#

no. the dirty rects are most often bigger than 32kb

#

so i subdivide THEM

tribal locust Jul 7, 2023, 2:10 PM

#

oh

woeful dove Jul 7, 2023, 2:10 PM

#

think of each dirty rect as it's own "screen" i will apply this algo to

tribal locust Jul 7, 2023, 2:11 PM

#

so it would seem that you'd basically want to only cut them in half at the max size right?

woeful dove Jul 7, 2023, 2:11 PM

#

yes

#

buffer size also is configurable, just FYI. 32KB is just what I'm using

tribal locust Jul 7, 2023, 2:11 PM

#

because cutting these up in 2d would require all sorts of weird memory movement

#

ok, i initially understood the problem as packing in 2d…

woeful dove Jul 7, 2023, 2:11 PM

#

i can only send rectangular regions

#

so weird regions require subdivision and multiple sends

tribal locust Jul 7, 2023, 2:12 PM

#

yeah but you're really just dealing with linear regions of memory

#

the fact that they contain 2d image data is kinda not relevant?

woeful dove Jul 7, 2023, 2:12 PM

#

keep in mind, there are controls on the screen i want to fill around, so i can refresh the control itself with as few redraws as possible

#

basically the controls don't get touched at first. those rectangles need to be left alone.

#

that way, i can devote the entire 32KB to drawing the control itself, reducing the number of times i need to draw it

tribal locust Jul 7, 2023, 2:13 PM

#

the way i understand it right now is that you get from somewhere a list of buffers that need to be sent. these buffers are of various sizes. and you need to pack them into 32 KiB chunks.

woeful dove Jul 7, 2023, 2:14 PM

#

yes

#

but i don't have a good list of buffers as such

#

i have less than optimal list i need work from

#

subdividing those using this algo

#

right now i subdivide naively top to bottom along the width of the entire dirty rect or "screen"

tribal locust Jul 7, 2023, 2:15 PM

#

i kinda doubt that the overhead of doing much optimization there before sending will really outperfom just sending them tbh

woeful dove Jul 7, 2023, 2:15 PM

#

the bus is very slow, dot

#

i'm dealing with a 240MHz processor over a 40MHz bus with a lot of transactional overhead (7 transactions per send)

#

and that's the best case

tribal locust Jul 7, 2023, 2:16 PM

#

i think i'd look at some examples to assess how much really can be gained here. take some example screen update, brute force compute the optimal subdivision, and see how much transfer that really would save…

woeful dove Jul 7, 2023, 2:16 PM

#

you can actually see the full screen draw

#

i totally plan to

#

but first i need something to compare. and i'm struggling with it

tribal locust Jul 7, 2023, 2:17 PM

#

i'm not exactly following

woeful dove Jul 7, 2023, 2:17 PM

#

i just need to come up with a brute force way of doing it which amounts to consuming lots more caffiene

#

i'm brain broke at the moment, but i wanted to follow up so people didn't think i abandoned this post

tribal locust Jul 7, 2023, 2:18 PM

#

k^^

woeful dove Jul 7, 2023, 2:19 PM

#

it's no fun waiting for my brain. mornings. meh. i'm not really all there until noon hits, but i can go into the night.

tribal locust Jul 7, 2023, 2:19 PM

#

do you have an example of what exactly these input rectangles look like?

#

and what exaclty you'd like the output to be?

woeful dove Jul 7, 2023, 2:19 PM

#

sort of. here's what I'm testing with. i don't have appropriate outputs yet. I'd have to fire up paint and spend a significant amount of time with it

#

// this is basically main() in normal C++
void setup() {
    lcd.initialize();
    lcd.rotation(3);
    draw::filled_rectangle(lcd,lcd.bounds(),color_t::black);
    int ctl_count = rand()%5;
    for(int i = 0;i<ctl_count;++i) {
        srect16 r(
            spoint16(rand()%lcd.dimensions().width,rand()%lcd.dimensions().height),
            spoint16(rand()%lcd.dimensions().width,rand()%lcd.dimensions().height));
        r.normalize_inplace();
        draw::rectangle(lcd,r,color_t::red);
        control_rects.push_back(r);
    }
    // make_fill_rects();
}

#

This is what I'm testing with.

#

i'll snap the output rn

#

ignore the artifacts around the corners of the rects. that's just LCD refresh being caught on cam

#

those are my untouchable rects on a 240x134 screen

tribal locust Jul 7, 2023, 2:23 PM

#

ah ok, so you want to send everything that's not inside those rectangles?

woeful dove Jul 7, 2023, 2:23 PM

#

yes

tribal locust Jul 7, 2023, 2:23 PM

#

ok

woeful dove Jul 7, 2023, 2:24 PM

#

it's just like the tiling algo i linked to except the existing rects aren't on a grid

#

btw, is that code i posted readable? i'm just curious because i made that graphics lib

tribal locust Jul 7, 2023, 2:26 PM

#

upon first glance, i'm not sure what srect and spoint are exactly, or what normalize_inplace does

woeful dove Jul 7, 2023, 2:27 PM

#

fair enough. spoint16 represents an x,y struct of int16s. srect16 has two points that place a rectangle on a 2d plane

#

i have docs for all of it. i just wanted to draw a bead on how understandable it is at first blush

tribal locust Jul 7, 2023, 2:28 PM

#

ok so the s is for struct

woeful dove Jul 7, 2023, 2:28 PM

#

s is for signed

#

i have rect16 and point16 etc

tribal locust Jul 7, 2023, 2:28 PM

#

i'm not sure i understand what a signed rectangle is supposed to be ^^

woeful dove Jul 7, 2023, 2:29 PM

#

hah, imagine drawing a rectangle that intersects the screen but is not entirely on it. like up off the top left corner

tribal locust Jul 7, 2023, 2:29 PM

#

i'm guessing a rectangle with signed coordinates

woeful dove Jul 7, 2023, 2:29 PM

#

yes

tribal locust Jul 7, 2023, 2:29 PM

#

and an unsigned rectangle?

#

would wrap around the screen or smth?

woeful dove Jul 7, 2023, 2:30 PM

#

unsigned rects have unsigned points uint16_t are usually for lower level drawing, like directly to the driver and not through draw:: ... there signed doesn't make sense, and everything is cropped to the draw surface

tribal locust Jul 7, 2023, 2:30 PM

#

k^^

woeful dove Jul 7, 2023, 2:30 PM

#

in my user interface library that sits on top of this everything is signed. this gfx lib is kind of lower level than i usually go

#

lcd.bounds() actually returns an unsigned rect, because the lcd screen is obv unsigned. it can never have neg coordinates

#

draw:: takes either one

tribal locust Jul 7, 2023, 2:34 PM

#

ok anyways so regarding your problem, i think one approach would be a kd-tree subdivision of the screen based on the edges of the rectangles. you can then use heuristics to decide how to split and optimize for various aspects like keeping uninterrupted 32 KiB runs or smth.

woeful dove Jul 7, 2023, 2:34 PM

#

interesting. I've only ever used kd trees for nearest color matching

#

that's the problem with being self taught i guess.

#

holes in my knowledge big enough to drive a truck through XD

tribal locust Jul 7, 2023, 2:35 PM

#

kd-tree is a very simple idea

woeful dove Jul 7, 2023, 2:35 PM

#

yeah, it helps find relative distances, no?

tribal locust Jul 7, 2023, 2:35 PM

#

you recursively split space along either x or y

#

at each level, you decide where to place the split based on some criterion

woeful dove Jul 7, 2023, 2:36 PM

#

edges of the existing untouchable rects in this case, i'd think

tribal locust Jul 7, 2023, 2:36 PM

#

yes, you'd have those edges be your candidates for splits for examples

woeful dove Jul 7, 2023, 2:37 PM

#

now I'm wondering if I couldn't just subdivide horiz, around those filled rects, and then again vertically, and then subdivide any results > 32KB and that won't be relatively efficient?

tribal locust Jul 7, 2023, 2:37 PM

#

after each split, you sort your rectangles into either entirely in one half or the other half

#

the problem is that you will have rectangles that get split

woeful dove Jul 7, 2023, 2:37 PM

#

oh yeah, i see

tribal locust Jul 7, 2023, 2:37 PM

#

because the edge of one rect cuts through another

woeful dove Jul 7, 2023, 2:37 PM

#

brain broke. heh

tribal locust Jul 7, 2023, 2:38 PM

#

in that case, you split the rectangle into two smaller ones

#

each entirely in one half of the split

#

and then you just keep doing that

#

at the end, you'll have subdivided space into just non-overlapping rectangles

woeful dove Jul 7, 2023, 2:38 PM

#

i think this might be what LVGL does. I looked at their code for this, and there's so much supporting code (in C no less) that I got lost, but i saw it sorts rects

tribal locust Jul 7, 2023, 2:39 PM

#

tribal locust at the end, you'll have subdivided space into just non-overlapping rectangles

at least assuming that your input rects don't overlap

woeful dove Jul 7, 2023, 2:39 PM

#

your input rectangles might - the untouchable ones

#

especially since alpha-blending is a thing. controls can be semi-transparent

tribal locust Jul 7, 2023, 2:39 PM

#

well, even that should be fine, or at least can be accounted for i guess

woeful dove Jul 7, 2023, 2:39 PM

#

yeah

tribal locust Jul 7, 2023, 2:40 PM

#

you can just subdivide until you have a region that is either entirely dirty or entirely clean

woeful dove Jul 7, 2023, 2:40 PM

#

yeah

#

i'll take a crack at this and see how far i get. thanks!

tribal locust Jul 7, 2023, 2:42 PM

#

np^^

naive glacierBOT Jul 7, 2023, 2:47 PM

#

@woeful dove Has your question been resolved? If so, run !solved :)

woeful dove Jul 7, 2023, 2:48 PM

#

(for readers other than the bot) no it hasn't, but it's getting closer. I need to try this first and see how far i get. i'm still looking for input at the moment. it's getting there..

tribal locust Jul 7, 2023, 2:50 PM

#

the placement of your controls is static i assume?

#

because then you can even just determine the best way to cut this up at compile time and generate code so that the only thing you do at runtime is just copying the data into buffers based on those predetermined regions…

woeful dove Jul 7, 2023, 3:02 PM

#

it's static ish. Every time a control moves the whole process will happen again for two dirty rects (the previous control position and the new one)

#

for the purpose of this algo it's static

tribal locust Jul 7, 2023, 3:03 PM

#

k

woeful dove Jul 7, 2023, 3:03 PM

#

oh it's not that static. it's not compile time static

tribal locust Jul 7, 2023, 3:03 PM

#

yeah i got it

woeful dove Jul 7, 2023, 3:03 PM

#

it in theory could be in many situations, but unfortunately i need to be able to handle when they are not 😦

tribal locust Jul 7, 2023, 3:04 PM

#

i would probably still do this in two parts, one where you figure out how to pack which regions, and one where you just copy the regions into buffers.

#

the first one then only needs to run whenever controls move

woeful dove Jul 7, 2023, 3:04 PM

#

oh definitely

#

ah i see what you mean

#

yeah i could do that.

tribal locust Jul 7, 2023, 3:05 PM

#

like, you have a function that just builds you a list of what regions to copy into which buffers
and a second function that just runs through such a list and perfoms the copies

woeful dove Jul 7, 2023, 3:05 PM

#

the other thing i can do to handle that scenario is just short circuit if the first control in the dirty rect takes up the entire dirty rect.

#

that would prevent that code from running on a move, without me having to do breaking changes to UIX internals

#

right now, a control's "parent" is simply an invalidation_tracker (which a screen implements) so I'd have to add another interface for it to do more. I orchestrated it such that i can, but would rather avoid it

tribal locust Jul 7, 2023, 3:08 PM

#

in fact, the kd-tree thing could probably be put where you're managing the controls so that you can always just go and iterate over the non-control regions or smth.

woeful dove Jul 7, 2023, 3:08 PM

#

ah yeah

tribal locust Jul 7, 2023, 3:08 PM

#

and leave it to the GUI system to figure out what the non-control regions actually are

#

dunno

woeful dove Jul 7, 2023, 3:10 PM

#

i've posted a question about how LVGL (https://lvgl.io ) does it on their forums. It's open source, and I've contributed to the project so the author and i have something of a rapport - I'm hoping it will bear fruit and give me some more approaches. since it sorts, it may be using a kd-tree or something like it

LVGL

LVGL - Light and Versatile Embedded Graphics Library

LVGL is the most popular free and open source embedded graphics library targeting any MCU, MPU and display type to build beautiful UIs. It's boosted by a professional yet affordable drag and drop UI editor, called SquareLine Studio. We also do services like UI design, implementation and consulting.

#

i hate that my functionality overlaps theirs. it didn't used to, but Espressif (an MCU designer) forced my hand by making stateless graphics untenable on their platform. Long story

#

i still need my lib because LVGL doesn't handle things like e-paper or indexed color displays very well.

woeful dove Jul 8, 2023, 1:55 PM

#

I'm marking this as solved even though it isn't. I may repost in the future when I have gotten further with it

#

!solved

#Filling a screen with rectangles - a brain teaser