The myth of "up" and "down" in computer graphics

Today is another of my rare technical rants, er, blog posts. It's a topic that I struggled with a number of years ago until I understood how to think about it properly, and which I still see people struggling with regularly.

The OpenGL coordinate system causes a lot of confusion because it uses a "bottom-left" origin, which is seen as "upside-down" relative to other coordinate systems typically used in window systems. This leads to people putting in lots of extra code to "flip images over" to make them right, often in the wrong part of a pipeline and requiring further reflections elsewhere to correct for it; as well as mis-guided requests for features in various APIs.

The way to stop your brain hurting is to stop labelling things as "up" or "down". Up and down are functions of an eyeball, and so it can only be directly applied to things that you see on a screen. Windows on a screen are visible, and this is the one place where OpenGL really is a bottom-up coordinate system. However, textures are not directly visible on the screen, either for normal sampling or for render-to-texture, so the use of up and down in the specification is purely a convenience for describing the behaviour. When uploading a texture, the first texel that is provided has texel coordinates (0, 0), and when this texture is treated as a rendertarget, that same texel has window coordinates (0, 0). This is true in both OpenGL and in Direct3D - there's no need to make any changes.

Things get more complicated at interface boundaries with other formats that do specify an up and a down. For example, PNG files do not have a standard coordinate system, but they do have a well-defined top and a bottom. So if a PNG file is used as a texture, where should the coordinate system origin be placed? That's not obvious, and needs to be consistent for an entire toolchain e.g. if your 3D modelling package shows you previews in which texture coordinates of (0, 0) map to the bottom-left of your image, then you should probably do the same thing in an application that consumes those models. Note that not all image file formats work the same way: formats created specifically for use with textures (e.g. KTX) may specify an origin rather than an up/down orientation (KTX also has an optional hint to tell viewer/editor applications how to display the image). The asset format may also provide a convention e.g. COLLADA explicitly indicates that (0, 0) corresponds to the lower-left corner of a texture image.

So, to summarize:

• Avoid using the terms "up" and "down" where they are not absolutely necessary. They'll just confuse you.
• Correct applications never flip images "upside-down" - they just sometimes have to re-arrange pixels in memory to conform to an interface. An upside-down image is a bug.
  
• When defining interfaces between systems which have a defined "up" and "down" (e.g. a PNG file) and systems which have a defined coordinate system (e.g. OpenGL textures), make sure you know what the correspondence is (using precedent set by thirdparty tools or file formats where possible), then stick it to throughout your toolchain.

Hopefully this will reduce the amount of confusion in the world.

Going home!

Yes, after 3 years of cold, cloud, not quite so cold, travel, cloud, work, pub lunches, bad pizza, more cloud, rain, snow, more cloud, more work, more travel etc etc, I'M GOING HOME! That's right - as of 5 May, I'll be back in the Mother City, back to my old haunts with my old friends and enjoying and missing my Cambridge friends, instead of the other way around.

I'll be doing a post-doc in the computer science department at UCT. When people ask me exactly what it is I'm going to do I find it hard to explain (possibly because I don't precisely know yet myself), but you can read the job advert here.

I've decided that nanny states are a real pain. Time was, people just made sure they had something put away for when they couldn't work any more. Now governments have very complicated rules by which you get a tax break if you put money into a pension scheme which you then can't withdraw from and can only spend in certain ways, and it creates a huge amount of red tape. Frankly dealing with red tape is the most stressful part about moving back - the actual moving is stressful but a doddle by comparison.

Anyway, if you're friend/acquaintance in the UK and want to see me before I leave, get in touch; and if you're a Cape Town friend/acquaintance I'll see you soon!

Bored in Vegas

As usual, my advice on Vegas is, don't bother. This trip, I've gotten sick (something flu-like), been fed far too much, sucked in a lot of signature smoke, been too hot outside and too cold inside, and now my flight home is indefinitely delayed due to mechanical problems (I'm now in the airport).

Unfortunately, I'm coming back in 2 weeks for the TopCoder Open. Oh well.

Visualising sorting algorithms

This is another one of my rare technical posts, as opposed to news of which countries I've been visiting.

If you're in computer science, you've probably seen an animation of sorting algorithms, maybe heard a rendition, or seen a visual representation. I have, somewhat by accident, discovered a different way to visualise a sorting algorithm: plot points for memory accesses, with address on the X axis and time (counted by accesses) on the Y axis, and different colours for reads and writes. It produces some rather pretty pictures. Note that these are not to scale relative to each other - the Y axis has been compressed to fit the entire sort into a fixed height.

Ye olde bubblesort. Some of the patterns are an optical illusion due to aliasing, but the green spikes are a feature of the algorithm.

Insertion sort - the version optimized for mostly sorted content. Although the data is random, you can see that in many cases it reduces the search distance.Shellsort, clearly showing the phases.

Selection sort:Heapsort: the solid lines at the top are the heap-building phase, while the rest shows the extraction. Note the very slight slope to the bottom-right line: as the heap gets smaller, the heap extraction gets faster, but only as O(log N).
Divide-and-conquer algorithms have a pretty fractal nature. This is quicksort - the perturbations in the fractal indicate the random selection of pivots (it just picks the middle, rather than median-of-3). Mergesort: this diagram is twice as wide as the others because it uses temporary storage on the right.

Budapest (again)

Yes, it's blog time again! Once again, it was the 24-hour Challenge in Budapest.

Like last year, there were some very interesting and tough problems. This year they did a much better job of implementation, and there were far fewer issues with things crashing and so it was more enjoyable. Unfortunately we didn't do as well as last year, but we still managed to come 5th.

After the contest, we finally got our cruise on the Danube. This time we came better prepared with info on where to catch the tourist boats. It turns out we were just looking in the wrong area, and if you go to the right place there are scores of them.

IT Challenge over

It ran smoothly, so not much to report. Stellenbosch won, UKZN came second and UCT third. Now I get a week of holiday in Cape Town; too bad half my friends have moved to other places.

IT Challenge 2010

I'm off to South Africa next week to help run the finals of the Standard Bank IT Challenge. This is a contest for teams of 4 university students. We've already run the heats to select one team from each of 9 universities; on Thursday the teams will meet at Standard Bank headquarters to do the final.

It's been some crazy hard work (including just about every free moment for the last week or two), but it should be a really great contest. We're hoping to have live standings during the contest (although we'll stop them an hour before the end) at http://sbitc2010.dyndns.org/ (yes, that link won't work right now, and probably won't after the contest either).

After that it's off to Cape Town for a week of hard-earned relaxation.

All Jammed up

Following my usual trend of only blogging when I travel and have some pictures I need to post, here's some photos from my last trip to the Googleplex for Google Code Jam. I was somewhat off form, but still managed to make 10th. If you want to see some seriously scary problems, take a look at the site. There is also an article about it here, including a video showing some of my ugly mug.

Photos from Bulgaria

I'm back in England. The contest was great fun and I'm going to miss the Bulgarian warmth and sunshine.

How not to be seen

Don't turn up.

That seems to be the view of most of the people I've talked to about the IOI planned excursion to the Black Sea. It apparently involves 4-6 hours on a bus. Each way. Not including the time you spend waiting around at the beginning until everyone gets on the bus. And leaving at 6am. When the time comes, I for one won't be found wanting. I won't be found at all, since I will be sleeping the sleep of the just, or possible just very tired.

Apart from the attempt to inflict long periods of time on buses (which in my case normally consists of periods of boredom interspersed by vomiting), things have been going pretty well here - in fact far smoother than usual. The SA team also did pretty respectably on the first day, and the second day is finishing in a few minutes. I haven't been on any of the excursions so far (being on the scientific committee seems to involve lots of work, but it's all been fun), but I plan to take myself off to the old town tomorrow (hopefully with some other leaders to make it more fun).

Bulgaria, land of enormous hotel rooms

It's blog time again! As usual, it's because I'm travelling - this time to IOI again, in Bulgaria. Haven't been here long, but so far I've been blown away by the size of the hotel room. More news when I've actually been out and about more.

Fording the... ox?

So, now that Tim is living in Oxford, I had a sufficiently good excuse to go and visit, and so I did so last weekend. The weather was rubbish, the company was good, and the town is quite pretty, in a more spread-out way than Cambridge. We went to see the science museum (which had lots of surveying stuff), and otherwise just wandered around the place. Um, not sure what else to add to that really.

We came second!

I don't have photos to post yet, but there are more details and pictures at http://www.challenge24.org/2009/blog

And the contest was... was... I still don't know!

There were technical problems (a fair number of them) during the contest, so the closing ceremony is only at 12. And since the scoreboard was one of the casualties, we still don't know how we did. But talking to one or two other teams, it sounds like we did reasonably well. Details to follow.

Also, I have now been awake well over 24 hours, with more to come. If you feel yourself going a bit squiggly and turning into a 6-foot chicken, do not be alarmed - I am merely hallucinating.

Hungry in Hungary

I'm sitting in Budapest, in preparation for a 24-hour programming contest. And lunch on the plane was a small ham sandwich, so I'm feeling peckish. Um, I don't really have much to add to that for the moment - more news once we've actually done the contest and done some touristy stuff. Tonight we're just going to crash and get a good night's sleep.

Don't let it snow...

... I want my flight to leave on time. So yes, life has been exciting, since yesterday England suffered about 10cm of snow, which apparently is the most in almost 20 years. So needless to say, they're totally unequipped for it, and large parts of the transport network including Heathrow ground to a halt. Fortunately, today had no snow that I've noticed and bright (if anemic) sunshine, so it looks like I'll be catching my flight in spite of the 3.5-hour journey from my house to Heathrow (normally it would be around 2.5).

This seems like it's going to be the things-falling-apart trip. Apart from the transport system, I opened my suitcase up to put my warm things in it just before checkin, and when I came to lock it up again I found that my lock had turned into a collection of bits on the floor. All very educational, but not much fun right before flying into Joburg airport which is notorious for baggage theft. So, any luggage thieves reading this: there is nothing valuable in my luggage. I promise. Don't bother.

Then after that, my watch started falling apart as I was checking in. Fortunately the pin didn't fall out and I was able to stick it back together.

Let's hope nothing else falls apart, like the plane, or my presentation on Friday.

The smallest park in the world

I've just got back from Portland, Oregon, from a business trip. I knew absolutely nothing about it before leaving, and I started with assumption of a typical American sprawl with end-to-end freeways and strip-malls. In fact the central part where I was a very pleasant surprise - good sidewalks, very short blocks, a river with a nice green bit next to it to walk along, etc.

It also features the smallest park in the world (Mill Ends park), which I thought was suitably amusing:


I only had one morning of free time (the rest of it being spent in the hotel eating too much food and trying not to get sucked into pointless arguments). Apart from the park, I went to Powell's book store, which is as large as the park is small. Just the SF/F section was about the size of a small public library, and I discovered a lot of books I'd never heard of, and bought a few for an insanely low price.

It burns us!

For those of you who don't already know, I've spent the last 11 days or so in Cape Town. The first morning I walked outside, squinted, and went "Ah, so that's what sunlight looks like." It made me realise just how sun-starved I've been in the UK winter.

It's been a great time here, and I've been out or seen people almost every day. Sadly, tonight I return to the land of clouds, roundabouts, pubs and 700-year old architecture.

Code Jam (like raspberry jam, but better)

Normally I blog about my trips while I'm on them (to kill time in airports), but this one was so short I didn't even both taking a laptop. In fact, I didn't even bother taking checked baggage, instead fitting everything for two days into a backpack. That sounds reasonably enough until you realise that it includes a keyboard and sufficient warm weather gear to stand around waiting for a bus in Cambridge. On the way back I think the backpack was about 99% of its theoretical maximum capacity.

The Code Jam itself is a contest run by Google. I've been to a previous one that ran on the TopCoder engine, but this time they've made a new format which really suits me. It's a lot less time-pressured than TC, and also more forgiving of mistakes. Having won my regional and finished in the top 3 in every round, I thought my chances were pretty good, but unfortunately I panicked near the end (partially because I forgot the contest started late and so I had more time than I thought), and so ended up third. Nevertheless I'm fairly happy since I didn't screw anything else up.

Pictures to follow - unfortunately not many or very exciting, since I didn't take my camera to the Googleplex on the assumption that they wouldn't allow photography (and indeed they didn't allow it inside the buildings).

How I learnt to stop worrying and love AMD's shader compiler

Normally I just post about travel and other daily trivia here, but I feel the need to get some good old tech ranting in. So, normal people (i.e. non-nerds), feel free to stop reading now :-)

I've been trying to do some OpenGL development at home, with the ATI X1600 in my laptop, and I've managed to find 3 serious bugs within about an hour. Firstly, my program would just crash while trying to compile a shader. After tinkering with my program for a while to try and eliminate anything I might have broken, I started removing bits of the shader. And guess what? If you index an array with a ternary expression, it crashes the driver.

Ok, I can work around that by moving the ternary into a temporary variable. Fix a few genuine compilation errors, and get to this message:

Fragment shader failed to compile with the following errors:

Well, that's helpful. Would be more helpful if it was followed by a list of errors, as is traditional in such cases. However, by again randomly removing pieces of code, I determine that a loop with an indeterminate number of iterations will cause this. Some hardware doesn't actually support loops (it just unrolls them), so fine, I'll run up to the maximum number of iterations I might need, and just early-out once I hit the number I actually need. Even when unrolling, such hardware normally supports forward branches, since it can just conditionalise the instructions hit by the branch. But not this sorry excuse for a compiler, it just gives me the same error. However, if I wrap the loop body in an "if" statement, it's happy to forward branch there.

Now, I finally have both my shaders compiled, I'm ready to link! It's much harder to make linker errors than compiler errors, although I did accidentally end up not writing to a varying that I was reading and which the linker helpfully complained about. I fix that, and is was well. And if you believe that, you haven't been paying attention. Of course it isn't. In spite of the cheery "Fragment shader was successfully compiled to run on hardware" from the compiler, the linker now asserts that "Fragment Shader not supported by HW". Why not? Well, remember that ternary expression? It turns out that while refactoring it fixed the crash, it's still not supported. It appears that the fragment shader can't do dynamic indexing, at least on varying arrays. So, some more refactoring, to move the array lookup inside each branch of the ternary, and now it all compiles and links.

I haven't tried running it yet, of course. I'm not sure I want to.