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

Leon Woestenberg leonw at mailcan.com
Tue May 30 15:41:57 PDT 2006


I am working on evaluating cairo (and also companion and higher
libraries such as freetype and librsvg) for embedded systems. So far,
the work has not changed any library code, but consisted of:

- minimizing dependency tree, without touching source code.
- performance evaluation on ARM920 and XScale processors.

One optimization (for a system as a whole) is to learn what part of a 
pixel map surface has been changed (as a bounding box) during a drawing

Knowing this makes possible non-redundant 'blit' copies between
back-buffers in double or tripple buffer approaches.

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:

bit 0 = upper left quadrant of pixmap (call this Q0) has changed.
bit 1 = upper right quadrant of pixmap (call this Q1) has changed.
bit 2 = lower right quadrant of pixmap (call this Q2) has changed.
bit 3 = lower left quadrant of pixmap (call this Q3) has changed.

bit 4 = upper left quadrant of Q0 (call this Q4) has changed.
bit 5 = upper right quadrant of Q0 (call this Q5) has changed.
bit 6 = lower right quadrant of Q0 (call this Q6) has changed.
bit 7 = lower left quadrant of Q0 (call this Q7) has changed.
etc. etc. (rinse and repeat).

The blit transfer operation could likewise be optimized by traversing
the quad-tree (to any depth desired) and the blits can then be

Can cairo (or pixman) be queried in similar fashion?

If not, can intimi introduce me to the point where I could introduce
such code?

I can think of two ways:
- keep track of this in the vector representation (just before actually
- keep track of this in the pixel map writeout in pixman (which would
introduce overhead at each pixel write access, very undesirable AFAICS).

Thanks for any insights,

Leon Woestenberg.

More information about the cairo mailing list