[cairo] Survey of polygon rasterization techniques

[Tor Andersson]

Since I saw my old project being mentioned, I'd like to
make a few points and clear up any possible misconceptions.

>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)

The Fitz rasterizer uses 17x15 supersampling for calculating the
coverage of individual polygons. There are a few tricks to it though,
that make it a lot faster than you'd expect from a naive implementation
of supersampling.

First you have to understand that this is a minor modification to your
text book sweepline algorithm that is described in the GPBB. The basic
algorithm generates non-antialiased spans to fill for each scanline, and
will draw any polygon with any kind of self intersection, and any fill rule,
trivially. It may not be the highest performance, but it works.

I've made two modifications to it to support antialiasing.
I'm not very good at explaining the whys and hows, so I'll outline
the algorithm instead and let the brains here decide if this is
a good or bad idea :)

I step the segments using bresenham's line algorithm,
but in a coordinate space that is scaled 17x15.

For each scanline I have a coverage accumulation buffer
that is an array of integers as wide as the scanline. This
buffer contains the delta of the coverage value, so scanning
the buffer from left to right adding the numbers, I will generate
the alpha values needed for compositing onto the destination.

I will then generate spans from the outline and add them into
the accumulation buffer 15 times per scanline (once for each
sub-scanline being sampled).

When I "draw" a span I will simply add some numbers into the
accumulation buffer. The start of a span will make the coverage
go from 0 to 1 with a spread over two pixels (distribution depending
on where the middle of the segment falls). The end of the span
will make the coverage go from 1 to 0 with a spread over two pixels.
Thus I have to add four numbers into the accumulation buffer for
the general case.

deltas[x0 / 17 + 0] += 17 - (x0 % 17)
deltas[x0 / 17 + 1] += (x0 % 17)
deltas[x1 / 17 + 0] += (x1 % 17) - 17
deltas[x1 / 17 + 1] += - (x1 % 17)

As you can see this will make all pixels that are fully covered
have a value of 17 when the deltas are added up.

Remember how I generated 15 spans. If a pixel is fully covered
for all 15 scanlines: 15 * 17 = 255, which is exactly
the coverage we want for fully covered pixels.

You can easily adapt this to 5 * 3 sampling if you only need
4 bits of alpha, or 257 * 255 if you want obscene 16-bit precision.

The source for the complete algorithm is here (cryptic and
undocumented as it may be):

http://ccxvii.net/repos/fitz-stable/raster/pathscan.c

In practice, I've found the performance to be quite acceptable, a good
compromise between speed and quality, even with the 17x15 sampling.
The 5x3 sampling is very good speed and still decent quality.

I would be interested in seeing what happens if you combine the
coverage delta accumulation buffer with Kiia Kallios ideas.

Tor