[cairo] Survey of polygon rasterization techniques

[Jeff Muizelaar]

I've been looking at redoing cairo's software rasterizer, particularly
to make it more competitive with flash. 

Currently, cairo's software rasterization looks like this:
	- tessellate polygon into trapezoids
	- clip trapezoids
	- additively render each trapezoid onto a mask
	- composite through the mask on the destination surface

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. Although I
don't have any fantastic proof that this approach is better than
tessellate-rasterize approach. What numbers I've seen tend to support
this hypothesis. I haven't seen any literature that suggests the
tessellate method and the recently posted paper "Scanline edge-flag
algorithm for antialiasing" further endorses this approac.

To get a feel for replacing the software rasterizer, I wrote a very
naive (qsort global edge table, qsort aet per scanline) non-antialiased
rasterizer and saw some performance improvements. As part of this
exercise I also wrote a polygon clipper and saw some performance
improvements using the current software rasterizer (if anyone's is
interested in seeing this, ask)

To get quality and performance similar to flash we'll have to do
full-screen-antialiasing. I envision this as a separate software
backend that records to a metasurface and rasterizes the whole scene at
once scanline by scanline so we have 16*w memory usage instead of
16*w*h.

Anyways, below are my notes on a variety of rasterizers (mostly open
source). They are mostly from reading source code, so I could've
misinterpreted stuff. If so, please correct me. If anyone else has any
thoughts on the topic, please share.

Enjoy,

-Jeff

Scanline
--------
coverage based antialiasing
---------------------------
libart
	- (Raph Levien) - scanline (from a sorted vector path) uses active edges
	- I think it handles different winding modes
	- SVP are similar to the critical point stuff
	- at least O(h*c + c log c) could be worse : h is the number of scanlines and c is the number of critical points

agg
	- coverage based antialiasing from freetype
	- compute edge flags for all edges into a list of cells
	- quick sorts cells into pixel order
	- scanline rasterize the cells
	- O(p log p) : p is the number of pixels on edges

freetype
	- scanline? ideas
	- coverage based antialiasing derived/inspired by libart

super sampling
--------------
fitz
	- http://ccxvii.net/apparition/
	- called 'libart2'
	- (Tor Anderson: draw_scan.c) - scanline (active edges) with global edge table does not use critical points
	looks like it uses 15x17 grid for supersampling
	- Based on Mike Abrash -- Graphics Programming Black Book (notably chapter 40)

pisces
	- edge list (super sampling)
	- looks like it also uses the global edge table
	- calls the aet 'crossings'?
	- possible replacement rasterizer for java2d

gnuclasspath
	- written in java by Roman Kennke (rasterizer-rkennke-2007-05-24.zip)
	- looks pretty much textbook
		- sorted aet (ActiveEdges::intersectSortAndPack)
		- bucket sorted edge list (Scanline::addEdge)

"Scanline edge-flag algorithm for antialiasing" by Kiia Kallio
	- bucket sorted edge list
	- n-rooks sampling
	- edge flag per scanline
	- O(n)

Trapezoid based
---------------
cairo
	- tessellate to trapezoids and then rasterize trapezoids
qt
	- tessellate to trapezoids and then rasterize trapezoids
amanith
	- tessellate -> opengl

Other
-----
flash
	- fsaa @ 4x however does not w*h*16 memory
	- My guess is that each scanline of the entire scene is rasterized at 4x the resolution
	  and then averaged down to the resulting image

ductus - US Patent 5,438,656 US Patent 5,589,851, currently used by java2d
synfig ?
FontFusion - www.typesolutions.com - T2K - used by java

Relevant papers
---------------
- "Scanline edge-flag algorithm for antialiasing"
- "Fast Polygon Scene Conversion with Medical Applications"
	- the idea of critical points comes from this one
- "Antialiased Rendering of Self-Intersecting Polygons using Polygon Decomposition"

Some quick unscientific benchmarks
----------------------------
	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

Numbers represent fps on a Intel(R) Xeon(TM) CPU 2.80GHz - 512 KB cache
The 3 polygons from Zack Rusin's benchmark are used:
http://zrusin.blogspot.com/2006/10/benchmarks.htmll
http://zrusin.blogspot.com/2006/10/disappointing.htm