So everyone in the “blogosphere” is going on about Google Chrome. From one day to the next, a bunch of personal blogs written by random people I don’t know which I for some reason subscribed to all suddenly had 1 new entry – subject “I like Chrome”. A bit like a few days before when Mozilla released some new feature and exactly the same thing happened. And now if I write about Chrome I am one of them as well….

I don’t intend to repeat all that has already been written. But here are a few UI niceties which, as ever, shows Google’s attention to detail.

• If the Chrome window is maximized, one can throw the mouse with wild abandon to the top of the screen to click the tabs, and move the mouse to the absolute right of the screen to access the scroll bars. The tabs and scroll bars are “mile-high” controls. (“Joel on Software” famously asserted Microsoft “snatched defeat from the jaws of victory” by placing the start menu at the edge of the screen, but then adding a one-pixel border so one has to, after one has moved the mouse to the edge of the screen, slowly move it back again 1 pixel to click the control.)
• If one downloads a file, an icon representing the downloaded file appears. This icon is draggable (e.g. to Windows Explorer in order to save the file). In Windows one can normally either drag a file from a directory to an app, or from an app to a directory, but not from an app straight to an app. But the icon in Chrome which one drags away actually already references a (temporary) file, one can drag the file directly from the Chrome app into another one e.g. an FTP program showing a remote directory, and the right thing will happen.
• If there are lots of tabs open, the tabs get smaller. If you close a tab, the tabs get bigger again. This much is standard in all tabbed browsers: but in Chrome the tabs don’t get bigger until you move the mouse out of the tab area. This way, if you want to close multiple tabs, you can look at all the close buttons, then move your mouse over each one and click the buttons. Otherwise (as in other browsers), you have to close one tab, then look at where the tabs have rearranged themselves to, find the close button on the next tab, click it, look at where the tabs have rearranged themselves to, find the next close button—repeat.
• If you double-click a word in the URL bar (e.g. www.mysite.com) then the portion including the separating dot or slash is selected (e.g. “www.”). This means if you press the delete key, then you are left with the syntactically valid “mysite.com”. If, however, you type, it replaces just the “www” so if you type “ftp” you are left with the syntactically valid “ftp.mysite.com”
• The “loading site…” status information at the bottom of the screen overlays the content. This saves space in comparison to having a status bar always displayed, taking up screen space. But, if you want to see the content hidden by this overlaid status bar, simply move the mouse to where the content would be, and the status bar automatically moves away to reveal the content.

Sometimes I am accused of suffering from the “Not Invented Here Syndrome”. It has been suggested I would rather program something myself than take an already existing e.g. open source solution to the problem and integrate it with the product being developed.

I mean that’s clearly a blanket statement. The right solution differs from project to project. (But, for sure, when making such a decision, one must not forget about the cost of integrating external software, especially down the line for maintenance, if the number of technologies and languages have increased by the new software’s addition, hindering code reuse.)

Joel on Software has an article about the benefits of developing things yourself.

So to pay respect to others in our industry who have also developed ridiculously complex things to support a quite different initial aim, here are the “Database & Life Not Invented Here Syndrome Awards”, presented in reverse order.

4th Place – The Corel corporation

Corel was a company producing and marketing desktop publishing computers. But what software should it run? When they couldn’t find any, they decided the only logical course of action was to create their own graphics package. Creating a graphics package like Corel Draw is non-trivial! But it was the right action to take, as Corel Draw became much more successful than any Corel workstation.

(I actually can’t find any evidence on the web that the above information is correct—I remember reading it in a computer magazine a long time ago. But neither can I find any evidence that it’s not correct.)

3rd Place - Stephen Wolfram

The Oxford-educated British mathematician Stephen Wolfram was interested in researching Cellular Automata. In order to do this, he needed mathematical software to conduct his research. Finding no software available to suit his needs, he created Mathematica. Creating a mathematical research project with the capabilities of Mathematica is non-trivial! (Stephen Wolfram about himself.)

2nd Place – Linus Torvalds

There are a myriad of source version control systems available. Take a look at the list of version control systems on Wikipedia! (No system is more suited to the creation of lists than Wikipedia!)

Linus Torvalds is well known for creating and managing the open-source operating system Linux. Finding no version control system which had both the features and licensing he desired, he created his own, “git”. Creating a version control system, especially a distributed one, is non-trivial!

For sure he didn’t write all the software himself, but his name does appear on the man pages, and even the conceptual work required in designing a distributed version control system is non-trivial.

1st Place – Donald Knuth

Wanting to write his book(s) “The Art of Computer Programming”, he considered the first layouts produced electronically to be ugly. The only course of action was to create the computer program TeX, capable of laying out such mathematical, and other, documents.

The input to this program is a custom macro language.

A layout program needs to write characters, and these characters need to be in a font, and fonts require description. So to enable the creation of the layout program, he also created the METAFONT program to describe font characters via lines and Bezier curves.

Needless to say, the creation of page layout programs, font specification and rendering algorithms, are definitely non-trivial!

A reader wrote to me with the following question. It’s a topic I used to wonder about a lot too.

I’m trying to write a 2D fillAntiAliasedTriangle() method in Java and trying to understand why everyone is using supersampling (that is, rendering at a higher resolution and then scaling down a grid of NxN subpixels into one pixel) rather than computing everything geometrically? (Say, your line cuts a triangle off a pixel to half its area, then have that pixel be colored at 50% the color intensity)

I think the answer is that although taking a geometric approach sounds like it would be more accurate and simpler, in fact it is more complicated. The shape could have many nodes within a single pixel, for example a line could enter a pixel, change direction at a node, continue within the pixel to a second node within the pixel, then change direction again, and leave the pixel. To calculate the overlap between the shape and the pixel, i.e. how illuminated the pixel should be, would be a complicated affair. And this would need to be repeated for every pixel. Therefore the algorithm would be very slow.

Calculating the set of pixels covered by a polygon, on the other hand, is relatively straightforward – you simply iterate over all rows of pixels, and work out the current intersection between the shape and that row of pixels. You then look at the next set of pixels, and assuming no nodes have been encountered, the intersection points are the same as the previous set of pixels, plus the gradient of the line. And the cases for a node being encountered are not too complex. This is a simple, and therefore fast, computation.

As it is simple to calculate the set of pixels covered by a polygon, it is also simple to calculate the set of subpixels covered by a polygon, in a supersampling algorithm. If one has n subpixels per pixel, the supersampling algorithm does of course take longer than a simple coverage algorithm: but not necessary n times longer, and certainly not n². By extending the simple coverage algorithm, one quickly has an algorithm to determine n set of intersection points for the n rows of subpixels. The algorithm then plots every whole pixel on that pixel row, taking into account these n intersection sets on the n rows of subpixels. Most of the pixels will be either fully covered by the polygon being plotted, or not covered at all. Only the pixels which are partially covered require further complexity. And therefore the extra complexity introduced, and thus the extra time penalty introduced, is minimal.

A supersampling coverage algorithm is simple to program, runs fast, and can cover all strange polygon special cases. That is the reason why it is used.

I’m sure that Joel on Software is well read: his views on user interfaces are certainly well worth reading.

But there’s a point hidden down at the end of Chapter 7 which is well worth repeating. And that’s that using a wide fixed-width font for text entry is much better than a thin proportionally-spaced font.

Recently I noticed that the invitation panel on Google Spreadsheets, allowing you to type in email addresses of people to invite to collaboratively edit the document, used a fixed-width font. And conveniently they didn’t alter their word processing program’s similar facility, making it easy to compare the two.

It really does just feels so much nicer to enter text using a fixed width font. So all projects I’m doing now, I make sure I use a fixed-width font for data entry. And I don’t even think it has to look ugly!

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.