[cairo] Optimizing diagonal lines (and more)

[Carl Worth]

Hi Billy,

Thanks for looking into these optimization possibilities. This is very
exciting stuff.

On Sun, 24 Jul 2005 22:39:45 -0500, Billy Biggs wrote:
>   I think a scanline-based algorithm would be both efficient and still
> general enough to be understandable.  The basic algorithm is as follows:
> 
>     - Create and clear a single scanline buffer.
>     - Foreach scanline in the bounding box:
>        =  Rasterize all trapezoids into that scanline buffer, remember
>           the first and last pixels touched.
>        =  Composite only those pixels, if any.
> 
>   Can anyone see any obvious flaws in this proposal?

Not a flaw, but perhaps something simpler:

The tessellator inside cairo is already generating sorted trapezoids
in top-down order. So if cairo is adjusted to call
pixman_composite_trapezoids multiple times, (once for each group of
trapezoids within a scanline), rather than once with the entire set,
then all of the above optimization should be obtained along with two
additional optimizations:

	+ The per-scanline buffer and compositing will only be as
	  large as the trapezoids within that scanline rather than the
	  width of the full bounding box.

	+ We won't waste time examining and rejecting trapezoids that
	  don't belong to the current scanline.

So that should be a fairly easy change to cairo that shouldn't require
any changes in libpixman or in the X server.

After that, a further optimization would be to make separate calls to
composite trapezoids within a single scanline when there are sets of
trapezoids that touch disjoint spans of pixels.

This grouping of trapezoids into scanlines and then into spans within
scanlines is the exact logic I've been wanting to add to also pull out
fully-covered pixel spans and represent those as a single trapezoid
(or an integer-specified rectangle). And then we would just have to
make sure that the composite trapezoids paths recognize and optimizes
rectangular, pixel-aligned rectangles. And, when the source is a
single color, we could sidestep composite trapezoids and use fill
rectangles instead for the fully-covered spans.

-Carl

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050725/f5cb5f16/attachment.pgp