Tree traversals

I changed my surfel renderer over to use a pre-order traversal layout for the nodes, this generally gives better cache utilisation and I did see a small speed up from using it. The layout is quite nice because to traverse your tree you just linearly iterate over your array and whenever you find a subtree you want to skip you just increment your node pointer by the size of that subtree (which is precomputed, see Real Time Collision Detection 6.6.2).

The best optimisation though comes from compacting the size of the surfel data, which again improves the cache performance. As some parts of the traversal don’t need all of the surfel data it seems to make sense to split things out, for instance to store the hierarchy information and the area seperately from the colour/irradiance information.

In fact it seems like when generalised, this idea leads you to the structure of arrays (SOA) layout, which essentially provides the finest grained breakdown where you only pull into the cache what you use and for all the nodes that you skip over there is no added cost.

I haven’t done any timings to see how much of a win this would actually be, mainly because dealing with SOA data is so damn cumbersome.

It definitely seems like something you should do after you’ve done all your hierarchy building and node shuffling which is just so much more intuitive with structures. Then you can just ‘bake’ it down to SOA format and throw it at the GPU/SIMD.

PBRT

I just bought a copy of Physically Based Rendering, I’ve been meaning to get one for ages as it’s often recommended and I thought it might be useful given my recent interest in global illumination. I’m also hoping to get a more formal background in rendering rather than the hacktastic world of real time.

The subjects covered are broad and it’s very readable. It’s my first exposure to literate programming, where essentially the book describes and contains the full implementation of a program. In fact the source code for their renderer is generated (tangled) from the definition of the book before compilation.

The only problem is the amount it weighs, I like to read on the tube but 1000 page hard backs aren’t exactly light reading.

Profiling

Profiling is one of those things that requires a lot of discipline. It’s basically the scientfic method, recently I’ve been optimizing our PS3 build and I got burnt by all my sloppy habits.

Basically you always need to have a benchmark to verify that what you’re doing has actually made things faster. Lot’s of people will just recommend doing a profile before you start making changes, well of course you should profile first, how else would you know what’s wrong? What you need to do though is to make a copy of you executable at the start of every day (along with saves of any profiling data).

This is because your initial profile has skewed the data so much that you can’t be sure what you’re looking at is execution time or instrumentation time. If you suddenly want to profile some new section of code and all you have is your old capture data you’re screwed. Hence keep the executable around and you can profile the same section and doing a meaningful comparison.

My friend James related this to the Heisenberg uncertainty principle which I quite liked, you can’t observe performance without altering it (except at a very macro scale).

Nothings changed

Whenever an artist (user) comes over to report a bug the typical response from a programmer is “that hasnt changed in ages”, “nothings different”. Of course this is a completely ridciulous response unless you happen to be the only programmer on the project. The user just wants you to acknowledge the fact that something’s wrong so it can be fixed it but of course the programmer doesn’t want anymore work on his plate so he feebly attempts to pass it off.

The other great one is, “it works on my computer”.. brilliant fobbery.

I’m definitely guilty of this every now and then but I do at least try not to give such a lame response.

iPhone GL specs

So I’ve been trying to find out a bit more about the iPhone’s capabilities, this site has some good details. No shaders, roughly enough power for 15000 lit triangles @ 30hz. Not too shabby, I wonder about the power consumption and if certain hardware paths drain the battery faster than others. It would be nice to make something that people can play for more than 3 hours.

So the word on the street is that O2 are bringing out a pre-pay iPhone in December, I’m currently debating whether to wait for that or just get an iPod touch which you can still develop for using pretty much the same feature set.

New job

So I took a new job today, working for Rocksteady in London.  Quite exciting, they use Unreal3 tech which I’ve always respected (and stolen ideas from).  It’s a big game title and technically I don’t know what it is.. but it’s a big franchise and should do well.

Plus working with friends in Kentish Town, s’all good.

Programmer Bum

I want this blog to be mainly code focused and finally I have something worth writing about.  I made a little visualizer for the recently released Radiohead House of Cards data set.

Check it out on YouTube:

http://www.youtube.com/watch?v=YDSHGppDNPg

And / or download the executables & source (Win32 + OpenGL only at this stage):

http://code.google.com/p/hocgl/downloads/list

Oh, and by Programmer Bum I refer to the fact that I have had the last month off work doing whatever I please and it’s been glorious.