Geometric vs supersampling polygon rendering

A reader wrote to me with the following question. It's a topic I used to wonder about a lot too.

I'm trying to write a 2D fillAntiAliasedTriangle() method in Java and trying to understand why everyone is using supersampling (that is, rendering at a higher resolution and then scaling down a grid of NxN subpixels into one pixel) rather than computing everything geometrically? (Say, your line cuts a triangle off a pixel to half its area, then have that pixel be colored at 50% the color intensity)

I think the answer is that although taking a geometric approach sounds like it would be more accurate and simpler, in fact it is more complicated. The shape could have many nodes within a single pixel, for example a line could enter a pixel, change direction at a node, continue within the pixel to a second node within the pixel, then change direction again, and leave the pixel. To calculate the overlap between the shape and the pixel, i.e. how illuminated the pixel should be, would be a complicated affair. And this would need to be repeated for every pixel. Therefore the algorithm would be very slow.

Calculating the set of pixels covered by a polygon, on the other hand, is relatively straightforward – you simply iterate over all rows of pixels, and work out the current intersection between the shape and that row of pixels. You then look at the next set of pixels, and assuming no nodes have been encountered, the intersection points are the same as the previous set of pixels, plus the gradient of the line. And the cases for a node being encountered are not too complex. This is a simple, and therefore fast, computation.

As it is simple to calculate the set of pixels covered by a polygon, it is also simple to calculate the set of subpixels covered by a polygon, in a supersampling algorithm. If one has n subpixels per pixel, the supersampling algorithm does of course take longer than a simple coverage algorithm: but not necessary n times longer, and certainly not _n_². By extending the simple coverage algorithm, one quickly has an algorithm to determine n set of intersection points for the n rows of subpixels. The algorithm then plots every whole pixel on that pixel row, taking into account these n intersection sets on the n rows of subpixels. Most of the pixels will be either fully covered by the polygon being plotted, or not covered at all. Only the pixels which are partially covered require further complexity. And therefore the extra complexity introduced, and thus the extra time penalty introduced, is minimal.

A supersampling coverage algorithm is simple to program, runs fast, and can cover all strange polygon special cases. That is the reason why it is used.