SDL_UpdateRects Optimizations

Hey all,

Does anyone out there, in one of the many hundred half-completed SDL
Abstraction libraries I’m sure exist, have a working and
semi-independent update rectangle optimizer?

I’m aware of the tricks that can be done, so please no one just submit a
laundry list of ways to optimize rectangles. I’m wondering if anyone
has a fairly modular chunk of code which can spit out list X of
rectangles from list Y… whereas updating with list X is quicker. (of
course, I have plenty of implementations where new list X is slower :slight_smile: )

Anybody?–

End of Rant.

Jimmy
JimmysWorld.org
-------------- next part --------------
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: This is a digitally signed message part
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20020219/8e10d70a/attachment.pgp

I have some code to avoid unecessary updates over screen,
but not exactly fitting your requirement from Y list to X
list.

The basic idea is to keep accumulating a "rectangle set"
that remembers all “dirty” areas on the screen, then
only redraw widgets intersecting with the “rectangle set”,
and in the final step, update the screen using a rectangle
list which is obtained from the “rectangle set”. If somebody
has an algo from Y list to a more efficient X list, we’d
love to use it too.

We are preparing to release the code in GPL, actually not
just this code itself, but a package that interfaces
between SDL and lua, with a GUI widget set and a GUI editor,
both purely in lua. The ultimate goal is to provide a game-dev
environment all in Lua. It won’t have all the jaw-dropping
features, but nevertheless, enough to create decent games
very quickly.

However, please be patient while we finish the cleanup and
packaging. At least not until April or May.

PS: For those not familiar with Lua, http://www.lua.org/
is a good start.

Regards,
.paul.On Tue, Feb 19, 2002 at 11:46:16PM -0500, Jimmy wrote:

Hey all,

Does anyone out there, in one of the many hundred half-completed SDL
Abstraction libraries I’m sure exist, have a working and
semi-independent update rectangle optimizer?

I’m aware of the tricks that can be done, so please no one just submit a
laundry list of ways to optimize rectangles. I’m wondering if anyone
has a fairly modular chunk of code which can spit out list X of
rectangles from list Y… whereas updating with list X is quicker. (of
course, I have plenty of implementations where new list X is slower :slight_smile: )

Anybody?

End of Rant.

Jimmy
JimmysWorld.org

Hey all,
Hi.

Does anyone out there, in one of the many hundred half-completed SDL
Abstraction libraries I’m sure exist, have a working and
semi-independent update rectangle optimizer?
Yes, perhaps. It’s called GemUta and it’s a part of my C++ SDL wrapper
called SEL (Simple Directmedia Layer Extension Library)
http://sel.sf.net
You can find it in the file src/base/uta.cc .

(I’ve realized that this text is a bit longer than it should have been
so if you want to read the fundamental stuff, feel free to jump to the
UTA part.)

Explanation?

Once, not very long ago, I had a problem similiar to yours. I had a list
of dirty rectangles and wanted to optimize it to avoid overlapping, etc.
I’ve spent some time doing a “research” and searching for available
solutions. The result was not what I hoped it would be.

I’ve seen alogrithms that proudly claimed to prevent overlaping, reduce
the number of rectangles and speed up the screen update. Sounds nice,
doesn’t it? It may sound nice, but the reality differs. I haven’t found
any 100% optimal solution, simply because no 100% optimal solution does
exist. But things are not that bad. (Otherwise I wouldn’t post this
mail, of course :slight_smile:

REGION------

Seeing the results I was a bit upset. Then I remembered, that such a
thing is a part of the mi library, one of the core libraries of the X11
(developed by X/Open, afaik). The part I am speaking about is called
Region abstaction and does extactly what is supposed to do. If you feed
it with a list of rectangles, it will split any overlapping ones and
then coalesce it together. In fact, it can do much more than that. For
instance it can xor a part of the region, etc. The implementation is
precise, but slow. Unfortunately, I’ve underestimated the performance.

In one my program I’ve had 150 small rectangles (+ another 150 for
previous position) and after “optimizing” it I got ~ 1500 small
rectangles that covered exactly the place of the original 300 rectangles
(But without overlapping, of course). Counting it and updating 1500
rectangles per frame is nothing your old 486 will do :slight_smile:

Why am I bothering you with this if I say it’s not suitable for games?
Because this is not the solution I was talking about, but this is
exactly what you need for a gui. In fact gtk 1.3 has adopted this code
(gdkregion-generic). If you need to detect overlapping windows and the
exact area of widget that should be repainted, this may solve your
problems.

UTA (Microtile arrays)

For the rest of you, who endured reading this long boring mail, this is
(or at least I hope it is) what should help you:

Microtile array.
Never heard about it? Originally, it’s a part of the libart_LGPL library
(by Raph Levien). If you want to find out, how UTAs (= microtila arrays)
work, visit http://www.levien.com/libart/uta.html .
I really recommend you visiting this page.

. . .

Okay, the idea of UTA is awesome, but what about the implementation?

Well, after looking to the libuta source code you will realize that the
implementation suffers from big design flaws. It’s slow and somewhat
clumsy. If you for instance want to add a rectangle to uta, You have to
make a new uta from the rectangle, take the new uta and the old uta and
merge them together (another new uta will be created as the union of
previous two).

This, of course, is not at all suitable for games where such things
would happen hundreds times per second. So I decided to write my own
implementation and called it GemUta. As I’ve mentioned, it’s a part of
the SEL C++ library. But don’t despair :), it’s written completely in C.
It’s all in one file (src/base/uta.cc) After stripping the C++ SEL::Uta
stuff (Actually it’s a thin wrapper around GemUta) you will get the
standalone uta implementation that allows:

  • Creation and destruction of microtile arrays
  • Adding rectangles to a microtile array
  • Getting the “dirty” parts of microtile array as a list of rectangles
  • Quering whether a rectangle is contained byor intersects the
    marked part of the array.

It’s fast and it’s definitely worth of try.

Bye.

-Matej Knopp