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.

Anyone who has written any graphics or text manipulation software will know the following problem:

• Each character or object has a particular style, for example the size of the writing, the thickness of the stroke, etc.
• There is some user interface element e.g. a dialog or rollup where the user can view and edit the attribute of the currently selected object
• The user may select multiple objects

And there we have it: the user selects two pieces of text, one is 12pt, the other 18pt, and opens the “font size” dialog. What size is it to display? There are a number of solutions to this problem, none particularly elegant:

• Display one of the sizes, i.e. 12pt or 18pt. (It doesn’t matter if the program uses an “intelligent” algorithm to decide which size to display—the largest number, the smallest number, the value of the leftmost character, the value of the character the user selected first or last—the user won’t work out which algorithm has been used!)
• Display either a gray box or the text “multiple selected”. Microsoft Word does this, and I suppose it’s an acceptable solution. The user is clearly informed that the value of all the characters is neither 12pt nor 18pt.

However, amazingly enough, I came across a new solution in the graphics program Inkscape. And it’s worse than any of the above! It has a certain elegance about it, and for sure this lead to the developers thinking its a good idea, but it’s certainly completely useless in practice.

The solution used by Inkscape is to display the average of the values. So if you have a character at 18pt and a character at 12pt, then display 15pt in the dialog. This is really confusing, as none of the characters you’ve selected actually are 15pt.

So if e.g. you have an 18pt character followed by lots of 12pt characters, as you shift-right and select more and more of the 12pt characters, the size displayed in the dialog slowly becomes less, displaying most of the time various fractional values, tending towards 12pt.

In fact–that’s wrong. It’s even more interesting than that. In writing this post I tried it out to check what was really happening. In fact it takes the average of the sizes of constant-sized spans of characters. For example if you have an 18pt char and a 12pt char, then it displays 15pt; if you have 18pt then 12pt then 18pt it displays 16pt; if you have 18pt then 18pt then 12pt, it displays 15pt, as there is one span of 18pt, and one span of 12pt, the average of 18pt and 12pt being 15pt.

It’s crazy stuff. It took me about 20 minutes to work out that this algorithm was what was being used. With my wedding tomorrow, one would imagine I should be concentrating on things other than font size display algorithms at the moment!