[cairo] recursive quad-tree, or bounding box of changed area during drawing?

[Federico Mena Quintero]

On Wed, 2006-05-31 at 00:41 +0200, Leon Woestenberg wrote:

> A very nice alternative approach instead of a bounding box, which I
> *think* is from libart, is a recursive quad-tree approach which roughly
> works as follows:

A bit of history may be interesting:

The original GNOME canvas (Xlib only, no libart) took a very simple
approach.  The canvas would simply grow a "dirty rectangle" whenever a
canvas item changed, by asking the item about its new bounding box.
This would create bigger-than-needed repaints if you changed two small
canvas items far apart from each other.  However, it was really fast
because it was simple, and Xlib drawing was quick anyway.  This is the
approach taken in the Tk canvas, by the way.

The libart-ified GNOME canvas does this:

1. The canvas keeps a "microtile array", which is actually a pretty
clever way of storing dirty regions.

2. When a canvas item changes, it updates the microtile array by adding
its own dirty region to it.  For items that are Bézier paths, it does
this by "filling" the microtile squares tha are inside the Bézier path.

3. When the time comes to draw the canvas, it walks the item hierarchy,
culling out items whose bounding boxes are outside the dirty region from
the microtile array.  Due to the way the microtile array is processed,
this may involve several walks over the item hierarchy.

Microtile arrays indeed have some nice properties:  their storage size
is O(area) regardless of the complexity of the dirty region, and so is
the time required to process them.  When you finish populating a
microtile array, you ask it to give you a list of rectangles which you
must repaint.  The length of this list is also O(area), regardless of
the complexity of the dirty region.  Microtile arrays are described
here:

http://www.usenix.org/event/usenix2000/freenix/full_papers/quintero/quintero_html/node16.html
http://developer.gnome.org/doc/books/WGA/graphics-libart.html

However, *nobody ever did any profiling of any of this*.  We don't know
how expensive it is to "rasterize" the Bézier paths to figure out their
contribution to the microtile region.  Applications tend to have shallow
hierarchies of items, so recursive bounding boxes don't help you much
when traversing the tree of items.  The tree must be traversed for each
of the bounded-in-number, dirty rectangles that got generated from the
microtile array.

Raph Levien, the author of Libart, was tring to do minimal repainting
for the case where you are dragging one endpoint of a long diagonal line
(repainting its bounding box could repaint many other items), or
dragging a control point of a large Bézier curve (so only part of the
curve actually changes, and you want to redraw only that area instead of
the whole bounding box of the curve).

I suspect that in the current incarnation of the GNOME canvas, figuring
out the minimal area to repaint is actually more expensive than being
dumb and fast.

A quadtree sounds very nice, but how are you going to populate it?

For your particular implementation, do take a good look at what the slow
part is.  Take some profiles.  Is it slow to compute your dirty regions?
Is it slow to paint dumbly?  See how those assumptions would change if
Cairo/X were perfectly hardware accelerated, i.e. when drawing is
basically free.

  Federico