# Optimizing UpdateRect

My apologies if this is slightly off-topic, but…

I’ve been attempting to write a list of rectangles (x,y,w,h) and am
having trouble determining the best way to insert new rectangles into
the list given the premise that no two rectangles should overlap.

The idea being to have a list of dirty rectangles which could then be
passed to SDL_UpdateRects.

Various questions have sprung up in the development of this routine:

1. At what point would it it be advisable to do away with the list and
do a ‘full’ screen update? Once ‘n’ rectangles are on the list, or an
area exceeding ‘p’% of the target surface (normally the screen).

2. Assuming we don’t want minature rectangles (i.e. 1x1) stored, is
there any algorithmic reasons for not choosing a granularity of say 8
pixels (i.e. every rectangle has its size adjusted to fit in an 8x8 grid.

3. When a rectangle being added overlaps an existing rectangle, what
would be the best (read fastest) method of splitting one of the
rectangles into smaller components. I suspect this involves choosing
small or large rectangles.

4. Finally, when producing the resulting SDL_Rect* list, is there an
optimal way of creating this list? Larger/smaller rectangles first/last,
higher/lower (with regard to screen y coordinate) first/last–
Alan McFarlane

My apologies if this is slightly off-topic, but…

I’ve been attempting to write a list of rectangles (x,y,w,h) and am
having trouble determining the best way to insert new rectangles into
the list given the premise that no two rectangles should overlap.

There have been other posts on this topic, including a merged rectangle

1. Finally, when producing the resulting SDL_Rect* list, is there an
optimal way of creating this list? Larger/smaller rectangles first/last,
higher/lower (with regard to screen y coordinate) first/last

It’s probably best to sort in increasing y order, to reduce tearing.

See ya!
-Sam Lantinga, Software Engineer, Blizzard Entertainment

Speaking of that, is there any plan to include this in SDL itself? It
would be cool (and not that hard to do, I guess) to have a new
initialization flag (or something of the like) you could pass to SDL so
that it would automatically update the parts of the screen which have
been blitted to, using an internal list of SDL_Rect’s to remember
them… The algorithm could even be fine tuned to do a full screen
update if the surface to be updated is too large.

Ga?tan.On Sun, 2002-10-27 at 19:28, Sam Lantinga wrote:

My apologies if this is slightly off-topic, but…

I’ve been attempting to write a list of rectangles (x,y,w,h) and am
having trouble determining the best way to insert new rectangles into
the list given the premise that no two rectangles should overlap.

There have been other posts on this topic, including a merged rectangle

Speaking of that, is there any plan to include this in SDL itself? It
would be cool (and not that hard to do, I guess) to have a new
initialization flag (or something of the like) you could pass to SDL so
that it would automatically update the parts of the screen which have
been blitted to, using an internal list of SDL_Rect’s to remember
them… The algorithm could even be fine tuned to do a full screen
update if the surface to be updated is too large.