[cairo] Survey of polygon rasterization techniques

[Carl Worth]

Hi Jeff,

Thanks so much for starting this discussion and launching into some
really interesting work.

On Mon, 30 Jul 2007 22:42:09 -0400, Jeff Muizelaar wrote:
>
> I'd like to see a different approach that rasterizes directly from a
> clipped polygon. This should be much better from a cache performance
> point of view, especially if we can go a scanline at a time.

Yes, that's a very good idea. The current approach in cairo
(tessellation) was originally conceived of as being useful for systems
that could benefit from hardware-based rasterization. So, if you're
assuming an all-software system, then yes, there are quite likely many
things that could be improved here.

Assuming a complex polygon, you should necessarily have to find all
the intersections at least, which is O(NlogN) for best-known
algorithms, (as far as I'm aware). It might very well be interesting
to allow applications to indicate to cairo that a path is known to
have no intersections.

I'm enjoying the discussion and look forward to seeing more exciting
things here.

-Carl

PS. As a note on the results you cited:

> 	1	2	3
> --------------------------
> libart	60	 1	 4
> cairo	63	22	 1
> agg	94	76	17
> qt	63	63	 6
>
> conclusions: for the polygons in the test suite agg is the clear
> winner with the highest quality and performance

You might take a closer look at these polygons. If I remember
correctly, polygons 2 and 3 are very large and consist of mostly
random edges so they have an enormously large number of
intersections. Cairo's tessellator is an attempt to implement an
algorithm that is O(Nlog(N+k)) where N is number of edges and k is
number of intersections. So, if k starts approaching N*N then its
performance can degrade into O(N*N).

Whether that kind of degenerate case actually happens in any polygons
that you might actually want to render is a question worth
considering. (I, for one, didn't consider either of those polygons
interesting enough to include in cairo's performance test suite, but
polygon #1 is there as the zrusin-another test).
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20070731/c2f8a9d2/attachment.pgp