I’m looking for a suitably speedy “dirty rectangles” algorithm to redraw only certain portions of a screen. After fiddling around a bit, here’s what I thought the algorithm should ideally do:
Colasce/Union two seperate dirty rectangles into a bounding rectangle occasionally to reduce drawImage() calls when it’s time to blit to screen.
drawImage() calls have quite a hefty overhead as I’ve found out.
Be wary of Area/AreaOp. These are SLOW, especially when dealing with non-rectangular Areas as I’ve also found out.
Minimize the redraw of unchanged portions of the screen.
I’m having exactly the same problem. Really pissed off that Area is still so incredible slow, especially since I have to transform everything before I know whether to render it.
What I’m going to do is add lots of listeners and callbacks, and have every object cache it’s own Area and a bounding box for it and only re-calc each when it has to. When translating, only the BB will be translated (unless it’s onscreen) becasue even trnaslating areas seems to be not great performance.
It’s a pain though because my code was happy and clean without lots of annoying listeners (I have 7-8 layers in the object type-hierarchy each of which is going to need it’s own listeners to propagate change notifications up the tree). I just wish Area were fast! There seems no excuse for it to be slow from an algorithmic POV: all my Areas are constructed from 1-10 rectangles, which really isn’t much! Although from what I’ve seen much of the performance is burned in keeping the outline path of the Area intact (perhaps the internal data structures were badly chosen for these kinds of ops). Blindly hoping that 1.5.0 will make it all better! (although right now 1.5.0beta2 makes performance drop to less than 0.05 FPS - yes, that’s 20 seconds per frame)
I have a sneeking suspicion that Area objects break down anything more complex than a single, axis-aligned rectangle into a series of per-scanline rectangles. While thats probably a good idea for a circle or oddly irregular shapes, its not terribly good for a couple of overlapped rectangles.
[quote]I have a sneeking suspicion that Area objects break down anything more complex than a single, axis-aligned rectangle into a series of per-scanline rectangles. While thats probably a good idea for a circle or oddly irregular shapes, its not terribly good for a couple of overlapped rectangles.
[/quote]
Yeah, when I was last using them for high performance stuff (sculpting complex shapes) I remember I had to write my own code to break apart Area’s and reassemble them, but I think that was because of bugs in Sun’s Area intersect and union code (it would create invisible holes of 0.1 x 50 pixels etc - just too small to appear on screen, but really screw up your contains and intersects checks!).
[quote]I’m having exactly the same problem. Really pissed off that Area is still so incredible slow, especially since I have to transform everything before I know whether to render it.
[/quote]
Do you have to use Area objects? Is it possible to use bounding box approximations instead?
How are the Area’s transformed? If you are using rotations for instance, maybe you could just do the ol’ pre-calculate everything thing.
How exactly are you rendering your objects?
I found that calling setClip(Area) on a Graphics context is MUCH MUCH SLOWER than simply calling setClip(Rectangle) or even setClip(Ellipse2D), and that slowness extends to rectangle shaped Areas as well. I’m really curious as to how setClip() and the Area class are implemented actually.
Has anyone tried to simulate an Area using GeneralPaths?
Anyway, I’m still lookin for a dirty rects solution - so if you have it, let’s hear it please.
I use Area’s methods sparsely, trying to use Shapes instead and really only use the Area methods as a way to create new shapes by boolean:ing them. I have a utility method to do this which checks if the shapes are Rectangle2Ds (which they mostly are in my case, but not always) and then jump over the Area stuff altogether. For more complex operations it falls back to Area’s methods though.
I always try hard to keep the Rectangle (or rather Rectangle2D) objects intact and not (often implicitly) converting them to GeneralPath objects, which Area’s methods and everything that goes through a PathIterator does.
I use a DirtyRegion class that automatically can have dirty shapes (again, Rectangles handeled separately) added to it, including handing the “empty” initial state (null). Whenever you like, it has a dirtyRegion.paint(Graphics g) that actually repaints the dirty region, but only if there is any.
Also, as a speed tip, don’t count on the Graphics clipping to speed up your code. It is faster to have a current bounds object tied to every visual object (gettable via an Interface) and test these bounds against the clip (BOUNDS!) and refer from even sending them down the graphics pipeline if they wont be painted anyway.
I have also found that the layout of all (that has changed that is) objects should be completed before the paint cycle starts. This will be more flexible when it comes to optimizations later on. Every object can also implement an interface which has a method that will return the dirty region, the downside of this is that you manually has to tell the object when it has been repainted and should clear it’s dirty region. This might introduce thrashing bugs.
Comparing Rectangle:s for overlap is a zillion times (estimated ) faster then painting them i vain.
If you are doing animation/games it is important to not create objects (as for instance Rectangle2D.union(Rectangle2D r) does) in the rendering loop. The loop won’t be slowed down much by the object creations, but the GC will kick in every now and then and make your animations/games choppy. If you are running with the concurrent gc the choppyness goes down, as does the fps…
What class are you using to represent your dirty shapes and how do you accomplish unions of Rectangle/Rectangle2D objects in your code to get a resulting shape?
For my app, the dirty regions are just plain Rectangles, however, they overlap/intersect often, so i’ve taken to using Area as a convenient way to union multiple Rectangles together.
Since the Area class is rather general, I’d really like to have a custom Shape class that will just handle union/adds of simple Rectangle objects, probably using GeneralPaths. But I’m not exactly sure how to implement such a class without overcomplicating things, so I’d appreciate any pointers please.
I agree, especially when clipping Area objects as I’ve mentioned. However, in some instances, it’s unavoidable in my app:
When repainting the dirty regions with the background graphic onto the screen.
When repainting translucent objects in which only a portion of the area occupied by the object is dirty
My current RepaintRegion class (below) only unions Rectangles. The down side with this approach is that if a small rectangle in the upper left and lower right are beeing added, the whole screen is redrawn. This isn’t likely in my code though, and if it was, I would probably make a separate cycle for small very far appart rectangles.
I don’t think (of the top of my head) that setting a clip that is not a rectangle will be good for performance, especially on a platform that has accelerated Java2D. The clipping of an arbitritary shape is slow in the graphics pipeline, that is one reason to only used the class at the bottom.
If you really must have (I have translucency and backgrounds and can do without) a class that implements Shape and is a bunch of rectangles just make a class that maintains a collection of Rectangle objects (in say an ArrayList) and that also maintains a “total bounds” for quick first-off check. All methods in Shape should be pretty straigt forward to implement. If you only have rectangles I would stay away from GeneralPaths as much as possible.
If you are using the clipping to “cut holes” in your graphics, rather than optimizing what to paint, than nothing above applies. Then you’ll probably have to use Area…
Btw, the “union” of two rectangles usually means what the class below does, that is, making a bigger rectangle that both unioned rectangles is inside and not making a shape that is the exact outline of the two (via Area’s add())
Cheers,
Mikael
public class RepaintRegion
{
private Rectangle r = null;
public RepaintRegion()
{
}
/** Constructor
* @param r The initial rect, can be null. Overtaken!
*/
public RepaintRegion(Rectangle r)
{
this.r = r;
}
/** Add a rectangle by "unioning" it with the current rectangle. Handles <code>null</code>.
* @param rect The rect to add. If <code>null</code> nothing happens. Not changed or kept. Cloned locally.
*/
public void add(Rectangle rect)
{
if (rect != null) {
if (r == null)
r = new Rectangle(rect.x, rect.y , rect.width, rect.height);
else
r.add(rect);
}
}
/** Adds the bounds of the shape to the repaing region
* @param shape The shape. Can be <code>null</code> in which case nothing is added.
*/
public void addShape(Shape shape)
{
if (shape instanceof Rectangle)
add((Rectangle) shape);
else
add(shape.getBounds());
}
/** Clears the dirty region
*/
public void clear()
{
r = null;
}
/** Return the current bounds of this region.
* @return The bounds as a reference. Can be null. <b>Not Cloned</b> so do not change!
*/
public Rectangle getBounds()
{
return r;
}
/** Return the current bounds of this region as a clone, free to use
* @return The bounds as a clone. Can be <code>null</code>.
*/
public Rectangle getClonedBounds()
{
return r != null ? new Rectangle(r.x, r.y, r.width, r.height) : null;
}
/** Repaint the current region of <code>this</code> in the component, if this region is not <code>null</code>
* in which case the method does nothing.
* @param comp The component to repaint. Not null.
*/
public void repaint(JComponent comp)
{
if (r != null)
comp.repaint(r);
}
}
[quote]My current RepaintRegion class (below) only unions Rectangles. The down side with this approach is that if a small rectangle in the upper left and lower right are beeing added, the whole screen is redrawn. This isn’t likely in my code though, and if it was, I would probably make a separate cycle for small very far appart rectangles.
[/quote]
Exactly. I originally wanted a simple “snowball” approach to union’ing multiple rectangles, however 2 small and quite far apart rectangles frequently happens in my app which would result in a lot of unneccessary repainting.
While I could probably have a seperate cycle that detects this, I wanted to see if there was a good, general solution out there.
Yes, setting a clip that is an Area is slow as I’ve mentioned. I’m not sure how fast setting a GeneralPath or Polygon clip as compared to setting an Area clip would be though. However in my experience when the clip is set, drawing operations with (at least some polygonal shaped) Area clips are still accelerated in 1.4.2 Java2D.
The problem with just a collection of Rectangles is that I can potentially have lots of overlapping dirty regions since objects in my app overlap frequently. The same intersection between 3 rectangles would be repainted 3 times then. I could probably have an algorithm that splits two overlapping rectangles into three, but then I would end up with lots of rectangles to test for intersections with and also more drawImage() calls as I cycle through the collection and redraw the dirty regions.
What I meant with "union"ing 2 rectangles is similar to Area’s add approach, ie, getting the exact outline. I mentioned in my previous post that I’m not sure how to implement this in a custom Shape class without too much fuss.
I don’t need an exact outline of dirty regions and I could do with a reasonable approximation, but I can’t think of an elegant solution that works well in my app.
Several ideas that I’m hesitant about:
A quadtree approach.
Advantages
A good approximation of dirty regions depending on how small each leaf node is.
Disadvantages
Would result in too many drawImage() calls (depending on how small/accurate the leaf nodes were) to repaint the dirty regions. I could probably combine neighbouring rectangles that are the same size into a larger rectangle to end up with a progressively larger rect, but I guess that would be overcomplicating things.
Snowball approach where I just keep unioning (ie getting the min bounds of) 2 rectangles.
Advantages
Few rectangles to compare intersection/clip with. Results in fewer drawImage() calls to repaint dirty regions. Fastest to calculate and simplest to implement
Disadvantages
Situation in which two small and far away rectangles results in unneccessary repainting as you’ve mentioned also. Has the worst approximation of dirty regions.
Splitting intersecting rectangles into more rectangles to avoid overlapping regions.
Advantages
Would get exact outline of dirty, rectangular, regions.
Disadvantages
Would result in more drawImage calls - ie, many rectangles to compare intersection/clip with. I’m on my way to implementing such a scheme and it’s much more tedious than I thought. If anyone has got an elegant solution, please share.
Use a customised Shape that adds only rectangles (like Area), possibly using GeneralPaths.
Advantages
Exact outline. Only 1 shape to compare intersection/clip with. Only 1 drawImage call to repaint dirty areas.
Disadvantages
Set clip slow. Comparing intersections possibly slower also. And I don’t know how to do unions using GeneralPaths :-[
I’ve finished implementing a dirty rectangle algorithm based on scheme 3 in my above post. I must say I am pleasantly surprised with the results :).
Compared to just clearing the entire screen every frame
During instances where there are not too many animations going on, I can get 3x speed increase. For example, with just clearing the screen, I get about 350fps tops. With dirty rectangles, I can get up to 1000+fps.
During instances where there are a lot of animations going on, I can get 1.5x - 2x improvement.
However, when the screen is full of stuff, I get about about 1.2x max.
I’m using accelerated graphics in 1.4.2 with P4 3.0ghz + 9800 Radeon card, so I really wasn’t expecting much of an improvement given the processing power I have.
I’ll be happy to share the source for my dirty rects implemention if anyone wants.
Nice! I think my rendering cycle (which isn’t really for a game) is a bit to heavy (logic wise) to use that strategy, but I definitely would like to check it out!
) faster then painting them i vain.