Six months ago, I managed to generate the following table. It’s not remotely relevant to Urbanspoon.

{ 0xc7, 0xc6, 0xc2, 0xbc,
  0xb3, 0xa9, 0x9c, 0x8e,
  0x7f, 0x70, 0x62, 0x54,
  0x46, 0x3a, 0x2f, 0x25,
  0x1c, 0x15, 0x0e, 0x09,
  0x05, 0x03, 0x01, 0x00 }

This is the coverage table for rendering antialiased lines using the Gupta-Sproull algorithm. Apparently, this little table is included in their original paper, first published in 1981. I couldn’t find the coverage table online. I eventually bought a copy of the paper from the ACM for $10, but it didn’t include the damned table!

Finally, I bit the bullet, sat down and read the paper. Then I hacked together a Java class to generate the table. I wasted two full days of my short life on those 24 numbers.

You’ll thank me later.

…

I spent two weeks trying to efficiently render antialiased lines as part of a consulting project for a consumer electronics company. During those two weeks I was completely obsessed with line rendering. I raved about it to my friends, long after they’d stopped listening. I dreamed of lines. I learned a lot about line rendering, most of which I’ve forgotten.

I eventually implemented Wu lines with a Gupta-Sproull style coverage table. In addition to the body pixel coverage table above, I also calculated an endpoint coverage table. Divide a pixel into a 16×16 grid. Move the fractional line endpoint to the nearest grid location, round the slope to the nearest 1/16, and then perform a lookup in the table. The lookup returns the coverage for the 6 pixels surrounding the endpoint. For those of you following along at home, the table is 16*16*16*6 bytes, or 24k.

The original paper dealt with integer (not fractional) endpoints. The authors suggested that it might be possible to support fractional endpoints by generating a table similar to the one I created, but that it would be too big for practical use. That was in 1981. Here in 2006, even portable consumer electronics devices can spare 24k. The Gupta-Sproull lines were much faster than agg’s lines, and looked just as good.

I came up with a great hack to generate the table. I drew some really fat lines in Java and then manually measured the coverage! A picture is worth a thousand words:

The moral of the story? A mediocre pixel tweaker like me needs to piggyback on 25 years of Moore’s Law in order to implement a basic line rendering algorithm.