Anti-aliased polygon filling algorithm

By Adrian Smith20 Mar 2008900 words4 mins to read

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.

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.

This article was written by Adrian Smith on 20 Mar 2008

Follow me: Facebook | Twitter | Email

More on: Graphics Algorithms | Algorithms | Things I've Released