Anti-aliased Polygon Filling Algorithm

I have always found this an extremely interesting computer science problem, and have written various polygon scanline conversion routines in my life. In January 2002 while at my parents waiting for the work year to start again, I decided to write a new one, this time in Java. (The source code is available on request to anyone who's interested.)

These days, no doubt, many polygon fill routines are available open source, and the descriptions of how one should work are also easily available on the web. Not so when I was a child and wanted to write my first one.

I wanted to create a program similar to Corel Draw which could have various different effects (graduations, fractals) as the fill for a polygon. The system-supplied polygon routines were insufficient, and thus I had to write my own. The system routines could only fill solid colour, and had no hooks to allow one to use their rasterization algorithm yet using ones own plotting system.

The essence of a polygon plotting routine is to consider the polygon one horizontal scanline at a time, from the lowest Y in any of the points, to the highest Y in any of the points. An ordered list is kept of which edges of the polygon are intersecting the current scanline. Moving up a scanline involves incrementing the position of this intersection by the gradient of the edge. If a node is encountered, one edge is removed from the list and the neighbouring edge (i.e. the other edge which shares that node) is added in its place.

It sounds deceptively simple and I think that's why I keep coming back to it. However there are a number of tricky special cases to consider.

• What about horizontal edges, or multiple horizontal edges next to each other, where you encounter a bunch of nodes all on the same scanline? Solution: write special case code.
• If you put in checks for horizontal edges, then what about nearly-horizontal edges where the entirety of the edge appears on the same scanline, but where the Ys are not actually the same? Solution: pre-compute all X-Y coordinates to the screen resolution before applying the algorithm.
• What about rounding problems when tracing edges? Solution: use integer arithmetic similar to Bresenham's algorithm.
• What about clipping? If you want to plot a polygon which is 100k pixels high (e.g. on a high zoom) you only want to trace the scanlines which are visible. But if the user scrolls down and exposes 10 extra pixels, the newly-plotted part must join the previously-plotted part exactly. Solution: With the integer node coordinates, and integer arithmetic for the edge-scanline intersection, this can be done.
• What about anti-aliasing? (My) solution: Run the algorithm at 4x X and Y resolution, and for each scanline of the algorithm, build up an internal array (one entry for each horizontal screen pixel), how many of the potential 16 subpixels should be plotted. After 4 subpixel scanlines, plot the actual pixel scanline and clear the internal array.
• Converting a pixel with 4×4 subpixels to a colour value is not as easy as it sounds. There are 16 subpixels meaning there are 17 different values (from 0 subpixels filled, to all 16 subpixels filled, inclusive). Yet your graphics device needs a value from 0 to 255 inclusive. And you want to use integer maths there. Solution: Multiply by 15.
• Pixel rounding: If you plot the rectangle (0,0), (3,0), (3,3), (0,3) then you want to have pixel (0,0) 100% filled but pixel (3,3) 0% filled. In that way adjacent rectangles will abut and not overlap. Solution: whole-number node coordinate values represent positions between pixels, not pixels themselves. Solution part 2: Carefully keeping track of when integers represent pixels and when they represent between-pixel coordinates.

Here is some output from the program, drawing a random quadrilateral and a random star, with semi-transparency.

Here is a demonstration of an extremely thin shape showing the benefits of the anti-aliasing:

And here is the program displaying text using a vector font.

That font uses a simple text-based format which is easy to parse.

Strangely I got the font when my father bought me a program costing £4.99 when I was about 10. I loved that program as it was able to do large lettering using vector graphics, and render them and print them out on the dot-matrix printer. It was not fast and the fonts did not have Bezier curves so it was not perfect, but it was a lot better than the character-based word processing I was able to do otherwise. It opened up a whole new world to me about what vector graphics were capable of.

The program came on a single floppy, for my 8-bit Z80-based Amstrad PCW. I rescued the 4 fonts that came with it (as they were the only vector fonts I had access to at that time) and moved them to my Archimedes, and now they live on in my Subversion repository, and are accessible from my Java IDE.