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.

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.

Before I left Vienna, the Internet stopped working in my flat. There were some major electrical engineering works going on in the building, so I assumed this was the cause. Now I’ve come back, they’ve stopped, but my Internet hasn’t started working again.

The modem, from my ISP Chello, was an “ARRIS type”, and the “online” light (light 2 in the following diagram) was permanently flashing.

What was the modem trying to communicate to me? On the Chello homepage it says one should turn the modem off and on if this happens. Needless to say, by the time I read that helpful advice, I’d already done that quite a few times!

But it turns out there is a button on the modem, which is marked “standby”. Amazingly enough pressing this has the effect of

1. making the Internet no longer work, and
2. making the “online” light flash instead of being constant.

Why would one want that? How had it come to be in that state?

Anyway, pressing it resolved the problem, and freed me from the necessity of making a telephone call to Chello support.

To keep up to date with new postings here on my blog you can use one of the following subscription facilities:

1. Enter your email address on the subscribe by email page. You’ll get an email each time I do a post. You can unsubscribe any time. You can also subscribe to just some categories (e.g. Databases, or Life).
2. Use an RSS reader. If you don’t already have one, you can sign up free for Google Reader. Find the “add feed” option (in Google Reader it’s on the left hand side) and just type in my URL, www.databasesandlife.com.

As those who know me know, I was sent a bill for € 2600 from T-Mobile Austria because I’d used their data card in the T-Mobile UK network. I’d downloaded 260MB. T-Mobile Austria claimed that T-Mobile UK was a “foreign network” (choosing to be one brand only when it suits them) and charged me € 10/MB despite charging only € 39/month for 800MB when I’m in Austria. Quite a price difference. It clearly didn’t cost them that much, they only adopt this strategy to rip people off. I even went to the consumer protection agency in Austria who agreed it was outrageous. They wrote T-Mobile AT a letter asking them to reduce the bill. T-Mobile promptly wrote back and said “no”.

I considered switching operators in Austria, but I looked around, and it turns out all the other operators have a similar price structure. Apart from the operator 3. They have a no-roaming-fee policy, as long as one stays within their network.

So, now I have signed up for 3 UK (as I was in the UK at the time I needed it, and I figured with no roaming costs, it doesn’t matter where you sign up). If I’d been with 3 before rather than T-Mobile before, my monthly bill would have been £10 rather than € 2600.

But I was, nevertheless, still extremely suspicious of network operators, after my experience with T-Mobile. And with good reason, it turns out.

3 supply a tool (with a horrible UI! – but it works) to allow you to connect to the Internet. I have only used their tool to connect, not any other. And helpfully it tells you how many MB you have used. You get 1000MB included in the monthly fee and every extra MB costs 10p.

But the other day I booted my computer and found the number of MB used had gone down overnight! The display on the previous day had been around 400MB and now it was showing around 300MB. This couldn’t be right.

One of the things I learned from my T-Mobile experience is that operators have websites where you can check your current bill. Supposing that 3 also had such a facility, I went around looking for it and sure enough it does have one, called my3.

And I suspected, the tool was showing an incorrect amount.

• Here is a screenshot of the tool which says that 439+91MB have been used, i.e. 530MB have been used, so 470MB should be remaining from my monthly 1000MB.
• A screenshot of the website however clearly shows I only 228MB are actually remaining.

If I had believed the 3-branded tool which installs itself onto the computer the first time you plug the 3-branded modem into a USB slot on your computer, I would have surfed e.g. 242MB more than my 1000MB allowance – or maybe more if the used amount goes down again mysteriously. That would have cost £24 extra, which is not the end of the world, but it’s not the £10/month deal I signed up for.

I wrote to customer services explaining the situation and suggesting they file a bug report against their software, as it displays incorrect data, and the data is directly relevant to billing. Amazingly a customer services representative called me and explained to me that only the value on the my3 website was the authoritative value. I explained that I understood that, but he should still get the program fixed, or at least display a warning. He said he’d “look into it” but it didn’t sound to me like he had any power to do anything about that. But maybe I’m wrong.

But basically, be very careful of mobile companies concerning data tariffs.

1. T-Mobile AT charging € 39/month for 800MB is € 0.04 per MB. They charge € 0.20 for any MB used over the 800MB limit. But roaming to the network apparently with the same brand in the UK, they charged me € 10 per MB, which is 50x € 0.20. But they’ve got the UMTS equipment in the UK anyway, for their UK customers who are on similar price-plans. The only extra complexity is provisioning and billing. I don’t believe that costs 50x more than building the UMTS network in the first place.
2. 3 UK produce a 3-branded tool installed from a 3-branded modem which came with my 3 contract, which displays blatantly incorrect data. Upon calling customer services one learns one cannot trust the tool, one can only trust the my3 website. But that is far from obvious. Anyone trusting the number on the tool will end up with a bill for a higher number of MB than they had believed they had used.

I was talking to my father over Christmas and he said that in his career, job titles of bosses had been various things, such as “leader of”, “head of”, etc. But he said when he started, they were called administrators.

I think that’s a great name for a boss. It emphasises that the job of the boss is to get out of the way of the employees and let them get on with their jobs. It also emphasises the positive aspects of a boss from the perspective of the employee, i.e. certain things which do not directly relate to the job, yet have to be done—such as coordinating holidays, managing pay, managing the office—should be done by the boss, to let the employee focus even more solely on their area of competence.

Imagine “administrator of software development” rather than “head of software development”. That sounds to me much more like how it should be!

Installing this into Firefox (takes < 1 minute and doesn’t require a download) allows you to check for the availability of domain names straight from the browser.

It was created by my colleague, who works with me at easyname.eu, but it was his idea, and I genuinely think it’s a cool feature!

Christina and I have a cool HDD/DVD recorder in Macau. One can set up timed programs and it records them from the TV when one is away. You can even copy them to removable media (DVD).

I wish I had something similar in Vienna! Ah yes I do, I realize, I own a VHS recorder :)

To set up a timed program, I have to first the device date/time. I'd never done that (Blinking "–:–" situation). I took a look at the instructions, and there was the "Beispiel" (example) of setting the clock to December 1998. Ah yes, I remember I bought the device in the summer of 1999.

And only today, 2nd December 2007, for the first time, do I set the clock and create my first timed recording :)

P.S. The summer of 1999 is so far away in the past, when I bought the recorder I was seriously stumped by the fact the manual was only in German and I didn't speak German back then.

I’ve taken a look at the state of vector graphics in the browser.

Since the beginning of the web, people have been using GIFs to display their headline texts; tables and CSS to do layout; and GIFs for rounded corners etc. A lot of this would become a lot simpler if the browser was able to display vector graphics.

There are numerous systems for displaying vector graphics but the two I looked at in detail were the <canvas> tag and DOJO. Initially I realized that the <canvas> tag could not plot text, and I thought the DOJO system could. But it turns out it can’t either. So I concentrated on the <canvas> tag.

The <canvas> tag, which works on Firefox, Safari and Opera, and a 1-line Javascipt include of excanvas, also works on Internet Explorer. It works well for trivially simple things. But there are a few things that don’t work like I expected.

(1) No callback for painting. Essentially a <canvas> is just a bitmap (like an <img>) which you can draw into programmatically using Javascript. This contrasts to traditional vector programming, where you register some kind of callback, and the system calls you when it needs the part of the window under your control to be redrawn.

The traditional way is certainly more complex, but it has a few advantages. If you are doing any kind of document editing, e.g. you are programming Word, then documents get big. But only a small amount is displayed on the screen at once. This gets more marked if you zoom in to 500%. With the callback mechanism, your application only get asked to draw the small part of the window on display. With the <canvas> approach, you have to draw everything, all the time. Imagine a grid which needs to draw lines every 5 pixels. That’s a lot of lines on a 1,000 x 1,000 pixel screen; but it’s a lot more if you need to draw everything in a 10,000 x 100,000 pixel workspace that the user could scroll around on.

It simply takes too long to draw everything the user could possibly see if you have a large workspace, or view a large document at a higher zoom. On a 5k x 5k pixel <canvas> with such a grid, Firefox complains “script seems to be unresponsive”, whereas on a 1k x 1k grid (which is all you can see) it works fine.

(2) Large <canvas> takes up lots of memory. As a <canvas> is just a bitmap, if you create a large one, a large amount of memory is immediately allocated. So if you are programming a Word using this technique, and the user scales the document to 500%, immediately their computer will slow down as the browser needs to allocate a huge amount of memory just to store all the pixels the user could potentially scroll around to see. And the Internet Explorer control and the Opera <canvas> seem to have a limit somewhere around 5k pixels.

(3) You can’t draw text. This is surely the most amazing limitation. Look at all the vector graphics examples in the web and you’ll see e.g. beautiful clock examples – but they use a JPEG as the background to the clock including the numbers. That’s hardly the way I had imagined vector graphics would be used!

But there is a “solution”, as we see in this nice windowing example. As the browser can already display text, and the background to a <canvas> is transparent, you can layer one <canvas> on top of another, and put <div> objects inbetween.

If one is to display e.g. a Word document, with various vector graphics and various pieces of text, one would have to create lots of <canvas>es and lots of <div>s and absolute-position them on top of one another. That seems to me like a lot of programming work to create this structure, and to maintain it. And it can’t be easy or quick for the browser to render such a document.

There is a solution in sight though. There will be a <canvas> drawText command in Firefox 3. Currently nobody has Firefox 3 and none of the other browsers support it. But that will no doubt be different in a few years time.

(4) There is no way to query text metrics. If you want to have vector graphics and text on the same page, you need a way to find out the size of text in pixels. For example you want to center text on the screen. Or fit text into a weirdly shaped object. Thankfully this is supported with the Firefox 3 drawText command.

(5) Opera zooming doesn’t work. Maybe this is just an implementation issue, but as the vector graphics are turned into a bitmap at the time the Javascript commands to draw into the canvas are executed, if you say “scale to 200%” in Opera, it scales the generated bitmap, as opposed to scaling the original vectors and re-rendering them.

I always object to the name SVG on the grounds that it stands for “Scalable Vector Graphics”, and vector graphics are scalable by their nature, so I don’t understand why the file format wasn’t just called VG. But it seems someone has indeed managed to implement what I thought was impossible: “non scalar vector graphics”.

Conclusion

So what is one to do to implement a client-side app manipulating vector-based documents? It is clearly the way of the future.

As far as I can see, it’s still not very easy. Which may explain why there are none of them around. The only one I can think of is Gliffy – and that’s written in Flash.

(a) An alternative scrolling technique will have to be found. If the user is manipulating a large document, or a small document at a high zoom, then creating one big <canvas> and using the browser scrolling isn’t going to work. One will have to implement ones own document-navigation (i.e. scrolling) system. This will not be what the users expect. But it’s the technique that Google Maps uses: it doesn’t have windowing-system scrollbars to let you pan the viewable area within the original document (the world map): it has its own navigation system.

(b) Displaying text is going to be a pain. No more myDocument.display(graphicsContext) – where the code to display the document is decoupled from the particular drawing implementation.

The code to display a document is going to have to be quite tightly coupled with the display system (create and maintain <canvas> and <divs>). And for making modifications, I’m not sure if it’s going to look nice to delete those <canvas> and <divs> and recreate them each time, maybe one is actually going to have to modify them e.g. during a drag operation, which will make the code particularly front-end specific.