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
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
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