So in Part 1 I discovered that, in order to make it easy to build levels for my game, I need to create my own voxel terrain editor. I’m inordinately proud of myself for this, because after some initial hair-tearing and wrangling it has turned out… rather sumptuous.

Terrain Up the Night

I didn’t actually start work with the terrain engine, mind you. I started with modular structures, diving right back to my roots with nary a backwards glace. The RDZ Industries buildings I made for Warcraft III were always modular segments pieced together, they just had to be copied and pasted into individual models because Milkshape and Warcraft didn’t play that way. Not so in Unity, oh me oh my!

Unity’s main advantage is that a single model import retains all the individual groups from Milkshape, so I can stack up 20 different segment parts in the one file and don’t have to split them up for export — I can use or discard the individual meshes as and when I need them in the editor.

The only problem arose because I was using the FBX format. At first I thought it was Unity but it turned out to be the export after all — it seems that FBX does not save all the vertices relative to the actual model origin, but repositions them relative to the geometric centre of mass. Unity was compensating for this a bit, but my subsequent snapping of all the pieces to the terrain grid so they’d “line up properly” was undoing all of that.

So, quickly re-exporting everything to Wavefront OBJ, that classic static model format from the dawn of 3D modelling, everything went back to where I actually wanted it. With all the pieces aligned correctly, I could lay down the artificial parts of my level — the buildings and walls and roads.

That still paved the way for the voxel terrain editor, mind you. I made all those building parts on the same terrain grid as the natural landscape parts — it’s 2×2 cubes all the way down. Then there was a sharp descent into the seedy world of procedural meshes, and the party started in earnest.

The thing about 3D geometry is that it’s all very low level. There are no shiny abstractions, not like the hoity-toity classes I’m used to in the upper reaches of C# application development. There is an array of X/Y/Z triples that defines vertex positions, and there is an array of indices for that array that defines the triangles strung between them. That’s it.

The meat of the universe as I understand it is the triangles, the pieces of geometry you can see and “feel” — but triangles cannot even be defined without first setting up all the vertices. They are the secondary citizens of the low-level mesh world, and that makes things difficult to manage.

Luckily, I found an abstraction. Not much of one, but it should be enough. I made my own “triangle” class that does not index some array somewhere, but directly holds the positions of each corner. How does that even help? Well, it means I can create triangles in a way that is “human readable”, by putting the coordinates straight in. Yes, there is a lot of redundancy and duplication as triangles edge up against each other, but I don’t need to worry about keeping massive arrays in synch either.

The second half of the system takes care of duplication anyway. I send my list of triangles into the world of the actual mesh geometry and build that up from my sane reference point. Iterating through all of the triangles builds up that underlying array of vertices — but also a dictionary of vertex indices keyed by physical position. That means that when a subsequent triangle shares a vertex with a neighbour, it will find its index in the dictionary by its location and use that; if not, then it will add a new vertex to the list and continue as normal.

With that, I actually have a reasonably simple system with which I can generate any mesh fairly efficiently. Throw in a property to track what side of the voxel a triangle is facing, so I can allow vertices on the same position but pointing in different directions to remain distinct for when I do want hard edges, and I have a beautiful, clean mesh generator.

You might say there’s a lot of overhead in here, which is true. Every time I change the underlying voxel lattice — by adding or removing one — I do have to regenerate the entire mesh from the lattice data. For small platters there was no noticeable lag, but now I’m sitting at over 4,000 voxels that generate more than 12,000 triangles, each addition or subtraction takes an unpleasant eyeblink to assert itself.

I’m not particularly inclined to optimise just yet, though, because this is only an inconvenience during edit time. Once the mesh has been generated, Unity holds onto that data forever — any player actually enjoying the level will see only the 3D model that came out the end of the process, not the juggling work my generator had to do along the way. (Although I could eventually plug it into my previous procedural generation work, that would still be hidden behind a loading screen.)

The other possibly problematic aspect, as you can see in the screenshot above, is that adjacent triangles are not collapsed together. For those big swathes of flat ground and flat walls, 95% of the vertices and triangles are completely unnecessary — you could get the exact same effect with a smaller set of triangles that spanned the whole area.

Unfortunately, I haven’t come far enough to work out an algorithm to cover that. I also figure that, actually, by Unity standards I’m still messing around in the dirt — 10,000 triangles is the standard budget for a whole character model these days. Likewise, a “true” voxel game, where the voxels are created and destroyed in real-time, wouldn’t have the luxury of any optimisation at all in this area — and there are plenty of those around that seem to be just fine. So, probably okay for me to be a little bit fast and loose around the edges.

So with a fully armed and operational voxel terrain editor in place, I have started to lay down a playable landscape to fill in the void between the buildings. That still leaves one final question, though — how am I going to apply suitable textures to all this? How can I make rock and grass and mud and more? Seems like a question ripe for part 3…