[cairo] Survey of polygon rasterization techniques

[Carl Worth]

On Tue, 07 Aug 2007 21:06:34 +0200, "David Turner" wrote:
> the program is now available at the following address:
>
>     http://david.freetype.org/rasterizer-shootout/raster-comparison-20070807.tar.bz2

Great stuff, David. Thanks so much!

>   - "tor16x16_7" seems to lead if you do not want to sacrifice quality for performance. for
>     something that is capable of producing 256 truly distinct gray levels, this is pretty
>     remarkable.
>
>     I find this a very good thing because this algorithm is much simpler to implement and
>     understand than kiia32_7 (the heavily optimized multi-sampler), which is only capable
>     of producing 32 distinct gray levels.

So there's some interesting material for Jeff to digest there, as he
looks to replace cairo's software rasterization.

>   - keep in mind though that this test is skewed towards rendering glyph shapes, which
>     do not necessarily correspond to general Cairo paths as seen by its rasterizer.
>     more work is needed to generalize these conclusions !

This is an interesting point. Does anyone have anything like a good
set of polygons and curves? Maybe a collection of real-world SVG
files?

>   I'm going to continue working on this next week-end. I'd like to get rid of the FreeType
>   dependency entirely, and be able to get Zack's polygon data (or any other sort of thing
>   like that) to better the comparison. A program being able to generate pictures to compare
>   the rendering results of each algorithm would be a good thing too.

Hopefully some body in the cairo community can easily step in and help
out here. Obviously, it's not hard work for anyone that knows cairo
already. Any takers?

>   I've started writing a pixman-style rasterizer but this takes time. However, from what
>   I've seen now, I hardly see any hope of decent performance out of it :-)

I wouldn't kill yourself trying to reimplement/integrate something
like this if I were you. The tessellation on top was intended for
something targeting hardware rasterization, and the trapezoid
rasterization below was coded as trivially as possible, (read, known
to not be at all fast). So, other than just seeing the number, there's
not any algorithm interest in what cairo+pixman is currently doing
here.

-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.cairographics.org/archives/cairo/attachments/20070807/e768c375/attachment.pgp