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

[Leon Woestenberg]

Federico,

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
> 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
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 
the idea).

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 :-)

Regards,

Leon Woestenberg.