It is a simple source release (one header + one source file) under BSD style
license. From the source comments:
RectangleSet - a set of non-intersecting rectangles that can be
used to describe an arbitrary irregular area.
A RectangleSet can be manipulated by 3 operations:
union a RectangleSet with a rectangle
subtract a rectangle from a RectangleSet
clipping/intersecting a RectangleSet with a rectangle
Those who are struggling with SDL_UpdateRects() and dirty rectangle
dectection may find the code useful. In contrast to some other
implementation that uses fixed-size grids, the algorithm I use can be very
precise. It is not super efficient as you may have expected, and I am open
to any suggestions to improve it.
I haven’t had a chance to look at your code yet, but
on a conceptual level I thought you might find this
interesting: A compromise that I have seen (and was
planning on implementing in the next month or two)
that incorporates some of the percision of your
solution with the efficiency of a grid based system is
called a “micro-tile array”… basically the screen is
broken into a grid of tiles (let’s say 16x16 for sake
of discussion). Instead of just having a flag that
says if a tile is dirty or not, the tile has a
rectangle indicating what part of it is dirty, (the
IsDirty flag can be retained, but is only used for
efficiency). So, basically if you dirty a single
pixel on a tile, the tile only has to update that
pixel… if you dirty more than one pixel, the tiles
dirty-rect is expanded to the smallest rectangle
containing all the dirty pixels. Also, at update time
the tiles dirty areas can be recombined on the fly to
minimize calls that will update the dirty area.
Comments?
-Loren
— paul at theV.net wrote:> I’ve made my rectangle set implementation available
It is a simple source release (one header + one
source file) under BSD style
license. From the source comments:
RectangleSet - a set of non-intersecting
rectangles that can be
used to describe an arbitrary irregular area.
A RectangleSet can be manipulated by 3
operations:
union a RectangleSet with a rectangle
subtract a rectangle from a RectangleSet
clipping/intersecting a RectangleSet with a
rectangle
Those who are struggling with SDL_UpdateRects() and
dirty rectangle
dectection may find the code useful. In contrast to
some other
implementation that uses fixed-size grids, the
algorithm I use can be very
precise. It is not super efficient as you may have
expected, and I am open
to any suggestions to improve it.
Regards,
.paul.
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
I haven’t had a chance to look at your code yet, but
on a conceptual level I thought you might find this
interesting: A compromise that I have seen (and was
planning on implementing in the next month or two)
that incorporates some of the percision of your
solution with the efficiency of a grid based system is
called a “micro-tile array”… basically the screen is
broken into a grid of tiles (let’s say 16x16 for sake
of discussion). Instead of just having a flag that
says if a tile is dirty or not, the tile has a
rectangle indicating what part of it is dirty, (the
IsDirty flag can be retained, but is only used for
efficiency).
Why not just have a Uint32/Uint8[4] union for the tiles, and test the Uint32 for 0 to see if the tile is dirty or not? (At least one UTA implementation I’ve seen does that.)
So, basically if you dirty a single
pixel on a tile, the tile only has to update that
pixel… if you dirty more than one pixel, the tiles
dirty-rect is expanded to the smallest rectangle
containing all the dirty pixels. Also, at update time
the tiles dirty areas can be recombined on the fly to
minimize calls that will update the dirty area.
Right. And I think the recombination of tiles you suggest would be very important for some platforms, since there can be a significant per-rectangle overhead when performing the update. (That’s one good reason not to do it inside SDL; it’s not a matter of finding the Right Way™, but rather a target dependent matter of area/count balancing.)
//David
.---------------------------------------
| David Olofson
| Programmer
Basically the algo I use is to always maintain a grid
according to each union/intersection/subtraction operation.
For example, a union of a rect_set to a rect will insert
two horizontal lines and two vertical lines into the grids,
and then mark all cells covered by the rect.
Some opimizations were done to keep the grids efficient,
such as merging identital columns or rows. The other
optimization on speed is to round coordinates up (or down)
to 2^n, where n can be adjusted, but this sacrifices
accuracy.
Overall I find it not too bad unless you have a few hundred
dirty rectangles every frame, in which case, I’d suggest do
a full screen update instead.
Regards,
.paul.On Fri, Jun 07, 2002 at 04:19:55AM -0700, Loren Osborn wrote:
I haven’t had a chance to look at your code yet, but
on a conceptual level I thought you might find this
interesting: A compromise that I have seen (and was
planning on implementing in the next month or two)
that incorporates some of the percision of your
solution with the efficiency of a grid based system is
called a “micro-tile array”… basically the screen is
broken into a grid of tiles (let’s say 16x16 for sake
of discussion). Instead of just having a flag that
says if a tile is dirty or not, the tile has a
rectangle indicating what part of it is dirty, (the
IsDirty flag can be retained, but is only used for
efficiency). So, basically if you dirty a single
pixel on a tile, the tile only has to update that
pixel… if you dirty more than one pixel, the tiles
dirty-rect is expanded to the smallest rectangle
containing all the dirty pixels. Also, at update time
the tiles dirty areas can be recombined on the fly to
minimize calls that will update the dirty area.
It is a simple source release (one header + one
source file) under BSD style
license. From the source comments:
RectangleSet - a set of non-intersecting
rectangles that can be
used to describe an arbitrary irregular area.
A RectangleSet can be manipulated by 3
operations:
union a RectangleSet with a rectangle
subtract a rectangle from a RectangleSet
clipping/intersecting a RectangleSet with a
rectangle
Those who are struggling with SDL_UpdateRects() and
dirty rectangle
dectection may find the code useful. In contrast to
some other
implementation that uses fixed-size grids, the
algorithm I use can be very
precise. It is not super efficient as you may have
expected, and I am open
to any suggestions to improve it.
D?a Pi, 2002-06-07 at 15:44, David Olofson nap?sal:
So, basically if you dirty a single
pixel on a tile, the tile only has to update that
pixel… if you dirty more than one pixel, the tiles
dirty-rect is expanded to the smallest rectangle
containing all the dirty pixels. Also, at update time
the tiles dirty areas can be recombined on the fly to
minimize calls that will update the dirty area.
Right. And I think the recombination of tiles you suggest would be very important for some platforms, since there can be a significant per-rectangle overhead when performing the update. (That’s one good reason not to do it inside SDL; it’s not a matter of finding the Right Way™, but rather a target dependent matter of area/count balancing.)
This remembers me my own uta implementation (inspired by original LibArt
uta, but entirely coded be myself and much faster). I’ve mentioned it
several times in this list but got no response. So I mention it once
more: http://sel.sf.net/gem-uta.tar.gz
The licence is LGPL, but I can optionally (on request) make it BSD.
It’s on my list of interesting things to check out. Just so you know you’re
not totally ignored. :)On Fri, Jun 07, 2002 at 08:42:50PM +0200, Matej Knopp wrote:
This remembers me my own uta implementation (inspired by original LibArt
uta, but entirely coded be myself and much faster). I’ve mentioned it
several times in this list but got no response. So I mention it once
more: http://sel.sf.net/gem-uta.tar.gz