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

[Soeren Sandmann]

Federico Mena Quintero <federico at ximian.com> writes:

> Say you have a big unfilled Bézier curve, represented with "." here.
> You also have some shapes scattered around, represented with "X":
> 
>              .........               XXXX
>        ......         ............    XXXX
>       .                           ...   XXX
>        .     XXX            XX       O  XX
>       .       XXXXXXX      XXXX      O
>      .          XXXXXX    XXX        O
>       .   XXXX     XXX     XXX      O
>    XX  ... XXX                    ..
>   XXXXX   ......               ...
>    XXXXXX       ...............
> 
> The "O"s there represent a single segment of the Bézier curve (i.e. if
> handles were displayed for the control points, dragging them would only
> modify the "O" region and not the rest of the curve).
> 
> You drag one of the handles and only the "O" region moves a bit.  The
> rest doesn't change.  A *really* well-written canvas item for editing
> Bézier curves would be able to see that it only needs to repaint the
> area with the "O", both in its old position and its new position.

I think _that_ optimization is pretty clearly overkill. But the
optimization of 

        - computing a reasonably tight coverage of the old and new
          positions of the curve

        - for each item ask if its bounding box intersects the region

is almost certainly worth it, since the area inside the bezier curve
could be arbitrarily complex, meaning it would take arbitrarily long
time to repaint, *regardless* of any hardware acceleration or
profiling you do. 

In my opinion, adding to cairo the ability to rasterize to "fat"
pixels, is the best compromise between code bloat and repaint
efficiency, especially if rasterizing to fat pixels can be just a
matter of 

        - tesselating to trapezoids (which cairo needs to do anyway)

        - computing which fat pixels are touched by the bounding box
          of each trapezoid (a trivial computation).


Soren