UpdateRects DOH!

SDL Development
#1

Let’s look at your code, shall we?
…
I hope this is not the secret behind your good results.

well, because of this and other problems i didn’t catch
this one. after more tidying things aren’t so exciting.
i’m still getting about a 20% speedup. but i think this
is due to aliens. (every sprite has 900 pixels being
double updated, so there’s good gains to be had by
finding and removing those)

No, the Aliens demo is not a real-world usage of SDL.

i’ve been looking through some of the other opensource
games out there. for the games that don’t contain scrolling
background (circus linux, etc) they don’t seem that far off.

well, so much for that. last time i get excited about code
i wrote late at night. :[ on a good note, i learned a
lot more about SDL and looked over a lot of people’s code.
i come out all the wiser

i haven’t totally killed my idea off though, i’ll still be
playin with things from time to time, you haven’t gotten
rid of me so easy :]

#2

well, because of this and other problems i didn’t catch
this one. after more tidying things aren’t so exciting.
i’m still getting about a 20% speedup. but i think this
is due to aliens. (every sprite has 900 pixels being
double updated, so there’s good gains to be had by
finding and removing those)

Don’t worry, this sort of thing happens all the time. You think you have
discovered a new trick that gives massive speedup, but when you actually
analyse it more closely, it turns out not to be that great.

For moving sprites you have usually pairwise overlapping rects (the old
rectangle filled with the background, and the rectangle of the sprite’s
new position). If the sprites are moving just a few pixels per frame,
it’s easiest just to update the bounding rectangle of the new and old
regions.

#3

For moving sprites you have usually pairwise overlapping rects (the old
rectangle filled with the background, and the rectangle of the sprite’s
new position). If the sprites are moving just a few pixels per frame,
it’s easiest just to update the bounding rectangle of the new and old
regions.

I’ve wondered about this before – at what point (in terms of how far a
sprite has moved) is it faster to update the two rectangles as opposed to
the bounding rectangle of both, and then at what point is it no longer worth
the effort to break the rectangles into smaller ones to avoid overlap. And
also is it worth the trouble to have the program choose between different
options on the fly.

#4

I’ve wondered about this before – at what point (in terms of how far a
sprite has moved) is it faster to update the two rectangles as opposed to
the bounding rectangle of both, and then at what point is it no longer worth
the effort to break the rectangles into smaller ones to avoid overlap. And
also is it worth the trouble to have the program choose between different
options on the fly.

If you can reduce the size and numbers to updates then its usually a good
thing. Unless you algo is extremely roundabout and slow. The cost of a few
if statements, comparisons and a bit of maths we nearly always be less
than the cost of an update.

MartinOn Sun, 3 Sep 2000, Peter Nicolai wrote:

Bother, said Pooh, when Tigger came out of the closet.

#5

If you can reduce the size and numbers to updates then its usually a good
thing. Unless you algo is extremely roundabout and slow. The cost of a few
if statements, comparisons and a bit of maths we nearly always be less
than the cost of an update.

This is true, but there is a tradeoff factor which cannot be determined
with anything else than empirical measuring. Consider:

±--------+… If the corner pieces are small (the sprite has moved
|A | . a short distance), then updating the whole bounding
| ±--------+ rectangle is cheap and does much less unnecessary
| | | B| blitting compared to updating A and B.
| | | |
±-|------+ | cost = (a + b*(w+x))*(h+y) + c
. | |
…±--------+

±--------+ But if the corner pieces are large and yet the
|A | overlapping part is non-negligeable, then it may
|…±--------+ be a good idea to update 3 rectangles (cut up as
| | | B | dot-marked). Horisontal runs are usually cheaper
| | | | and should be preferred (another tradeoff).
±—|----+…| Note that this increases the number of updated
| | rectangles, each of which having some constant
±--------+ overhead.
cost = 2(a + bw)y + (a + b(w+x))(h-y) + 3c

±--------+ Here the overlapping area is small and updating
|A | A and B can be faster than splitting it into
| | disjoint fragments.
| ±--------+
| | | B | cost = 2(a + b*w)*h + 2c
±------|-+ |
| |
| |±--------+

In the cost expressions above, w, h are the rectangle sizes, x, y the
displacement, and a, b, c are constants:

a is the cost per line
b is the cost per pixel
c is the cost per rectangle.

(usually b is set to 1 and a, c scaled accordingly.)

This sort of tradeoff must be done by the programmer — either
choosing between two or three of the above cases or sticking to one
all the time. This is also the reason why general rectangle management
can be tricky to write. Note that the constants a, b, c are likely to
be different on different hardware (X11 vs win32 vs MacOS etc).

#6

Wouldn’t it be possible to write a test for the different methods and actually measure the time used for several cases, and from the data retrieved choose the best method. Not something that you would put into SDL, but it might be an idea for a library.
BLiP!On Mon, Sep 04, 2000 at 01:41:13PM +0200, Mattias Engdeg?rd wrote:

If you can reduce the size and numbers to updates then its usually a good
thing. Unless you algo is extremely roundabout and slow. The cost of a few
if statements, comparisons and a bit of maths we nearly always be less
than the cost of an update.

This is true, but there is a tradeoff factor which cannot be determined
with anything else than empirical measuring. Consider:

±--------+… If the corner pieces are small (the sprite has moved
|A | . a short distance), then updating the whole bounding
| ±--------+ rectangle is cheap and does much less unnecessary
| | | B| blitting compared to updating A and B.
| | | |
±-|------+ | cost = (a + b*(w+x))*(h+y) + c
. | |
…±--------+

±--------+ But if the corner pieces are large and yet the
|A | overlapping part is non-negligeable, then it may
|…±--------+ be a good idea to update 3 rectangles (cut up as
| | | B | dot-marked). Horisontal runs are usually cheaper
| | | | and should be preferred (another tradeoff).
±—|----+…| Note that this increases the number of updated
| | rectangles, each of which having some constant
±--------+ overhead.
cost = 2(a + bw)y + (a + b(w+x))(h-y) + 3c

±--------+ Here the overlapping area is small and updating
|A | A and B can be faster than splitting it into
| | disjoint fragments.
| ±--------+
| | | B | cost = 2(a + b*w)*h + 2c
±------|-+ |
| |
| |
±--------+

In the cost expressions above, w, h are the rectangle sizes, x, y the
displacement, and a, b, c are constants:

a is the cost per line
b is the cost per pixel
c is the cost per rectangle.

(usually b is set to 1 and a, c scaled accordingly.)

This sort of tradeoff must be done by the programmer — either
choosing between two or three of the above cases or sticking to one
all the time. This is also the reason why general rectangle management
can be tricky to write. Note that the constants a, b, c are likely to
be different on different hardware (X11 vs win32 vs MacOS etc).

#7

This sort of tradeoff must be done by the programmer — either
choosing between two or three of the above cases or sticking to one
all the time. This is also the reason why general rectangle management
can be tricky to write. Note that the constants a, b, c are likely to
be different on different hardware (X11 vs win32 vs MacOS etc).

Wouldn’t it be possible to write a test for the different methods and
actually measure the time used for several cases, and from the data
retrieved choose the best method. Not something that you would put
into SDL, but it might be an idea for a library.

Yes, and this can be quite practical sometimes: The graphics system can
calibrate itself, either at installation time or at runtime (perhaps
camouflaged as an intro).

Or you can do this once as a developer and enter the cut-off decisions as
constants in the code, maybe different for different platforms.
Especially X11 is important because of its slow screen updates.

#8

Pete Shinners wrote:

i haven’t totally killed my idea off though, i’ll still be
playin with things from time to time, you haven’t gotten
rid of me so easy :]

In Quadra, we use a bitmap of tiles instead of a list. Now, the code
equivalent to UpdateRect is very basic, but just by using a bitmap
instead of a list, we have zero overdraw. Now, the UpdateRect code could
try to issue as few blits as possible (one large blit is more efficient
than many smaller but equivalent blits).–
/* you are not expected to understand this */
– from the UNIX V6 kernel source