Software that adds another dimension to things

I think that it will come as no surprise to my fellow software engineers if I note that I almost never write new software any more. I maintain, I augment, I refactor, I debug but very, very rarely do I start something new.

This probably has something to do with my maturity as a code monkey, my immediate reaction is to seek out a solution to a problem that already exists and perhaps extend it to fulfil my requirements.

Partially this comes from my innate laziness but also over time I have discovered that I am a "finisher" the role I invariably end up in involves doing all the final bits to make the client accept a project. Because I know my reaction is to always finish something I start, I avoid starting things.

Anyhow, enough introspection, a couple of months ago I was talking on IRC about my 3D printer and was asked "can you print the Debian logo?". So I hunted around for software that would let me convert a bitmap into a suitable 3d format. The result was rather disappointing, the few tools I could find were generally python scripts which simply generated a matrix of cuboids, one for each pixel their heights corresponding to the pixel value.

I used one such script to generate a file for the Debian swirl and imported it into the OpenScad 3d modelling application. I got an inkling of the issues involved after the scene render took over half an hour. The resulting print was blocky and overall I was not terribly happy with the outcome.

So I decided I would write a program to convert images into a 3D representation. I asked myself, how hard can it be?

Sometimes starting from an utterly naive approach with no knowledge of a problem can lead to new insights. In this case I have spent all my free coding time for a month producing a program which I am now convinced has barely even scratched the surface of the possible solutions.

Having said that I have started from a blank editor window and a manual gcc command line compilation and progressed to an actually useful tool and, arguably, of more import to me I have learned and implemented a load of new algorithms which has actually been mentally stimulating and fun!

The basic premise of the tool is to take a PNG image, quantise it into a discrete number of levels , convert that as a height map into a triangle mesh, index that mesh (actually a very hard problem to solve efficiently), simplify the indexed mesh and output the result in a selection of 3D file formats.

The mesh generation alone is a complex field which it appears often devolves into the marching cubes algorithm simply out of despair of anything better ;-) I have failed to implement marching cubes so far (though I have partially implemented marching squares, an altogether simpler algorithm)

The mesh indexing creates an indexed list of vertices from the generated mesh and back annotates it with which faces are connected to which vertices. This effectively generates a useful representation of the meshes topology which can then be used to reduce the complexity of the mesh, or at least describe it. To gain efficiency I implemented my first ever bloom filter as part of my solution. I also learned that generating a plausible hash for said filter is a lot harder than it would seem. In the end I simply used the FNV hash which produces excellent results for very little computation cost.

The mesh simplification area is awash with academic research, most of which I ended up skipping and simply went for the absolute simplest edge removal algorithm. Implementing even this and maintaining a valid mesh topology was challenging.

By comparison the output of the various formats was positively trivial, mainly littered with head scratching over the bizzare de-facto "extensible" formats where only one trivial corner is ever actually implemented.

All in all I have had fun creating the PNG23D project and have actually used it to generate some useful output. I have even printed some of it to generate a lithophane of Turing. I now look forward to several years of maintaining and debugging it and doing all the other things I do instead of writing new software ;-)