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.

Looking around my hard disk, I found a program I wrote in December 1997 to demonstrate the capabilities of IFS (Iterated Function Series) using Affine maps. Here is an extract from the documentation I wrote at the time.

(The source code is available on request to anyone who’s interested.)

Description

A shape, an IFS fractal (Iterated Function Series), is defined by a number of transforms. Each one of these transforms map from the whole shape to a smaller self-similar part of it. In an affine IFS fractal, each one of these transforms is affine.

An affine transform is a linear transform with translation. Examples of 2D affine transforms are rotation about an arbitrary point, reflection in an arbitrary line, translation by any amount, etc.

So an affine IFS shape can be described by a set of transforms. An implementation generally has probabilities associated with these.

Algorithm

Given a point on the object, the point transformed by any of the transforms will also be on the object. The algorithm works by this method. Given a point on the object, a transform is chosen according to the probabilities attached to them and the point is transformed. The new point is then marked as having been visited. The process is repeated until some bound on the number of points to be plotted has been reached. The initial point is chosen at random: after a few transforms the point will lie on the object. Hence the first couple of points found are not plotted.

Two great comments from people about their experiences with Windows. I can really sympathize with these people!

From http://blog.seattlepi.nwsource.com/microsoft/archives/132891.asp#102626

Yesterday, it started an update I didn’t even want to initiate on shut-down so I had to walk to my car & drive off with this stupid laptop running in my hand to get to work. Is MS trying to get me fired?

From http://blog.seattlepi.nwsource.com/microsoft/archives/132891.asp#102708

I’ve come very close to picking up my Vista computer and throwing it out the window on several occasions. I got so tired of it constantly running something in the background and me not being able to stop it, that I punched the machine the other day. Yes, I know, not terribly intelligent, but man does Vista frustrate me. It hangs all the time, FOR ABSOLUTELY NO REASON. I could go on, let’s just say that when using Vista you feel like MS just didn’t really care whether or not it works.

You want to get married in the UK to a non-EU citizen? Then you’re going to need a lot of documents.

My fiancée and I have gone through the application form, and created a spreadsheet listing all the supporting documentation required. I think I have about 25 documents to prepare, and Christina a similar number—whereby some documents are not in fact single documents, but tasks such as “all tax documents for the last year”, or “all invoices”!

I’ve now prepared about 1cm of documentation.

(P.S. Thankfully we can both see and even edit the spreadsheet at the same time due to the great collaboration features in Google Spreadsheets!)

My future wife and I have decided to start our lives together in Austria instead of the UK.

Nevertheless I’m leaving Vienna tomorrow for about 5 months, but from August onwards I’ll be back permanently. I’ll be available for software architecture and development work, as before.

Currently I’m working for easyname.eu and uboot.com, and also working on a private project (website allowing collaborative diagram creation); if I ever really make any progress on that I’ll write a blog post describing it in more detail!

Plan for the next few months:

As I do a lot of programming using open source databases, I couldn’t help but notice that inclusion of XML in the database seems to be a hot topic. Postgres 8.1 (just released) and MySQL 5.1 (not released yet) will allow XML documents to be stored as the value of cells, and allow those documents to be manipulated and inspected. (Oracle has had this feature since 2001)

I generally don’t like XML (as Robin put it: most formats are designed to be either conveniently readable by humans, or by computer. XML is conveniently readable by neither.)

So I especially wouldn’t like to store XML in the database. However, there are some times when one would naturally want to store some hierarchical data and the relational model doesn’t really allow that conveniently. Compared to:

• Storing e.g. Java serialized objects as a BLOB in the database (with no chance of ever doing a “select” against that data, or migrating that data using a SQL migration script);
• Or storing direct XML without manipulation functions (slightly more readable, but still not programatically manipulatable using SQL)

I suppose using the XML features provided in the database is better than either of the above solutions.

The following table contains documentation copied from the documentation or the changelog of the database in question:

I am probably one of the rare type of Mac owners who did neither of the following:

• Bought Mac OS X 10.5 (including Safari 3)
• Upgraded to Safari 3 by downloading it for free from Apple’s website

Therefore I was still using Safari 2 on my Mac.

A few nights ago, Apple’s software-update program pushed Safari 3 to my computer.

Although I could have deselected that download, I assume that the sort of people who would deselect an update that are the sort of people who care about their computer, and those are probably the sort of people who’ve already got Safari 3 by one of the above methods.

Therefore I assume nearly nobody is using Safari 2 any more, and thus see no need why it need be explicitly supported for future web projects.

The monitor I am using at work suddenly went white. I.e. every pixel went white; not black, and not blue. A white screen of death, as it were.

I was in the middle of programming an algorithm requiring some degree of thought, so I wasn’t really up for being interrupted by unreliable technology.

The monitor a 22″ wide-screen flat monitor. My initial suspicion obviously lay with Windows.

For some reason, some instinct told me to turn the monitor off and on. I pressed the on/off button but amazingly nothing happened, and the “on” light stayed on. The on/off button is hidden in some inconvenient place, and one can’t see it unless one gets up and peers round the side of the monitor. It has no real tactile feedback when pressed, so initially I assumed, when the button did nothing, that I’d pressed it wrongly.

But getting up and looking at the button and pressing it a few more times confirmed that it was in fact doing nothing.

Again, some instinct told me to hold the button down for 5 seconds. Amazingly, that did turn the monitor off.

I had managed to crash my monitor !

To quote my friend Robin:

As life goes on, one owns more and more devices which need rebooting.

I suddenly got an email out of the blue today:

Dear Sir / Madam:

We have received your application, an interview will be arranged for shortlisted candidates. Thank you for your interest to join our team!

Human Resources

Initially I thought it was spam (although the normally good Gmail spam system hadn’t marked it as spam), then I saw the company name, and saw they were based in Macau.

A quick search for that company’s name in my email found one outgoing message to them, applying for a job, dated December 8th, 2006! Today is February 19th, 2008.

Every object has a hashCode and an equals method. These are used to determine where to place an object within a hashing algorithm, and if two objects with the same place in the hashing algorithm actually are the same, respectively. If you want to add objects to a Set—which stores only unique objects—it uses these methods to determine whether two objects are the same and thus shouldn’t both be stored.

If you have code like:

Set<byte[]> uniqueArrays = new HashSet<byte[]>();
uniqueArrays.add(new byte[] { 1,2,3 });
uniqueArrays.add(new byte[] { 1,2,3 });
uniqueArrays.add(new byte[] { 1,2 });
System.out.println(uniqueArrays.size() + " unique byte arrays");

This code prints 3. You might expect this program to print 2, as there are only two unique arrays within the Set. But arrays’ hashCode methods do not return the same result for two different arrays with the same contents. This is in contrast to, for example, the String class, which does indeed consider the String’s contents when computing the hashCode.

Set<String> uniqueStrings = new HashSet<String>();
uniqueStrings.add(new String("123"));
uniqueStrings.add(new String("123"));
uniqueStrings.add(new String("12"));
System.out.println(uniqueStrings.size() + " unique strings");

This code prints 2. (The slightly strange-looking “new String” here is to make sure that there are actually different object instances with the same content being passed to the add method; otherwise the Java compiler would use the same object instance for the two calls, as the string-content is the same.)

The solution is to use the Arrays.hashCode(anArray) method.

This isn’t particularly convenient if you want to store unique arrays in a set. But if you have an object with e.g. a byte[] instance variable, then you can implement the hashCode method on that object to use Arrays.hashCode, or you can use the code:

Map<Integer, byte[]> map = new HashMap<Integer, byte[]>();
map.put(Arrays.hashCode(anArray), anArray);
Collection<byte[]> uniqueByteArrays = map.values();