Stale Battenberg and Powdery Snow

It’s snowing today. Me and my friend just went to Sainsburys and back and still it shows no sign of letting up. Gradually its covering the roads and paths – even those outside my window which are very busy. It’s late, and I’ve still a lot of things to get done, but then I got up late too, so I still have plenty of waking hours left.

That said, I thought I’d spend some time writing about a another pet project of mine – you know, the ones there’s rarely time for amongst your real work these days and you just keep putting off as they pile higher and higher like the snow outside.

The first iteration of Battenberg was a little application I threw together in a single day back when I was investigating OpenGL last summer (2011). I was tired of the constant step by step progression through the stages of learning OpenGL, so I thought I’d take a day out to program something more personal.

Battenberg is a name I gave this project very recently; it seemed appropriate given the application’s goal. The idea is to take a small image (preferably a very small pixel art sprite), or series of small images, and transform every pixel with a non-zero alpha value into a cube. The original program simply looped through each pixel in turn and added another cube to a buffer for each opaque pixel, then rendered this buffer in a OpenGL application with an fps style camera. That was nice, and I had a lot of fun loading old sprites from games I’d made and watching them march on the spot in glorious (blocky) 3D.

However, this christmas I was once again stuck for a less-mundane source of constructive-amusement when perusing DirectX tutorials. With 3D rendering on the brain my thoughts quickly went back to what I now refer to as Battenberg. What would I have to do if I actually wanted to use those 3D sprites as assets in a game? Preferably I’d be able to export them to a common model format so that conversion did not have to occur every time the game loaded resources. Boring. Too easy. Then I thought of something I had considered before – how could I make these assets more efficient?

For a start you didn’t need all those faces inside of the model resulting from forming it out of lots of cubesĀ  – that would be easily done. But what about all those tiny triangles? Maybe I could get an outline of the shape and triangle tesselate it for better results? I’ve done triangle tessellation pretty recently as part of the XNA framework I was building with my friends at home, so that wouldn’t be too hard, surely…

Actually I’d never gone as far as to do tessellation of polygons with holes in them, and first I needed to identify polygons from the pixel data supplied. Slowly it dawned on me that this had become rather complicated; there were some pretty non-trivial algorithms to write if I wanted it tow work, and even my precious triangle tessellation algorithm needed expanding.

Step 1: Load the Sprites
This is the definition of trivial. Dragging and dropping a bunch of files on to an exe will give me their paths as command line arguments and each can be easily separated and processed one by one. I can use DevIL to load a huge variety of image formats with little effort.

Step 2: Define the Polygons
The biggest roadblock: I need to identify the shapes that will make up the front and back faces of the model. This is tricky because I need to know about all of the shapes within the image, and all of the holes within each shape. I’m considering simply storing holes as a shape within a shape, and any shapes within holes as simply another unrelated shape. I hope to sort out all the shapes with a system of edge-walking and polygon fills (for pixel ownership) which I care not to make an arse out of myself by explaining without first trying out. I’m trying not to impose any limitations on the images that can be processed, so my job is made slightly more difficult by the fact that I can’t reliably identify a surrounding transparent zone at the beginning (e.g. I can’t assume the first pixel is transparent and go from there).

Step 3: Give it Sides
If we’re going to have some depth then we need sides. I’m going to generate these before step 4 because we only need sides for the edges we currently have defined. These can easily be formed from triangles and will already be in their optimal state.

Step 4: Triangle tessellation
Let’s take those ugly polygons and make them into triangles. By doing this you’re almost guaranteed to end up with less polygons than if you simply used two triangles for each pixel. Ear-clipping is fairly efficient and I’ve written it before using this fine article as a guide. I merely need to port what I wrote to C++ and expand it to deal with holes. This should be much easier than stage 2, but also quite fun to write.

Step 5: Copy Cat
Once the front face is done we can simply copy it, add a bit more Z, and call it the back face. No-one will be any the wiser.

Step 6: Output
Now I’ve never written to a model format before, but I’m sure it’s about as easy as reading from one. This should be a piece of cake. If all else fails the crappiest of image formats will do so long as you can convert it to another using a modelling tool or other program.

It should be no problem to calculate normals and save these if this is necessary, especially given the cubular nature of our models.
Texture coordinates can easily be assigned as we loop through them in order to form our polygons in the first place. It might be wiser, however, to generate another texture containing only one instance of each colour used, and use this to assign texture coordinates.
It may be useful to also output a model which uses the old cube-per-pixel approach for use in pixel-explosion effects and such.

This is an interesting little project for me. It won’t take long to write once I nail down the algorithms and find a night or two to commit to it, and there’s the promise of pretty results to keep me motivated. I like the aesthetics of sprites processed in this way and I do want to use the application for a project sometime in the future.