[cairo] recursive quad-tree, or bounding box of changed area
leonw at mailcan.com
Wed May 31 17:00:54 PDT 2006
thanks for your elaborate explanation of implementations.
Federico Mena Quintero wrote:
> On Wed, 2006-05-31 at 00:41 +0200, Leon Woestenberg wrote:
>> A very nice alternative approach instead of a bounding box, which I
> Microtile arrays indeed have some nice properties: their storage size
> However, *nobody ever did any profiling of any of this*. We don't know
Any profile would be very system specific.
> 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.
Unfortunately, being dumb is not always fast on embedded hardware. Being
fast usually means being smart,
although I would rather be dumb and put a fat GPU in place :-)
> A quadtree sounds very nice, but how are you going to populate it?
Now that you spoke of microtiles, I think that is what I remembered, not
quad trees. (The quad-tree idea is a left-over from a
3d graphics renderer implementation I studied, but that doesn't cancel
But to answer your question, I would think of an approach as follows:
Find extreme coords of paths, use power of two sized area in the tree,
bitmask the extreme pixel coordinate values. I.e. for 256 size: dirty =
(x & 0x7f) left_right=(x & 0x80) for each horizontal halve. Identical
for vertical halves, and trascend the tree as such.
> 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?
Well, this is what I asked for: where should I look for possibilities to
dirty the regions efficiently?
> 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.
Think slow hardware, slow framebuffer access, and no acceleration
whatsoever. Yes, there is DMA available.
I am not yet in the stadium where I can do on-target profiling, but I do
want to find out if cheap paths are available to calculate dirty regions.
Any insights are welcome while I dumbly spit through the code :-)
More information about the cairo