[cairo] Survey of polygon rasterization techniques
cworth at cworth.org
Tue Jul 31 12:42:55 PDT 2007
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
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
Size: 189 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20070731/c2f8a9d2/attachment.pgp
More information about the cairo