Marching cubes.

I discovered the transvoxel algorithm here while surfing around looking for inspiration some weeks later which provided the spark of inspiration I needed.

It builds on an algorithm named "marching cubes" which is commonly found in medical scanners such as CT and MRI machines. These machines, as opposed to an xray for example,  scan a volume as opposed to a single image.
The problem this algorithm solves is how to efficiently extract a mesh representing the isosurface of a three-dimensional scalar field (voxel volume) so that it can be 3d rendered on a computer.

Marching cubes:

 When I first started the implementation, I must admit, it stood outside of my abilities as a programmer at that point - however that had been true for each step of the way so far already.  I firmly believe that  one of the best ways to learn is to push yourself to achieve something that is just outside of your capabilities until you grow in understanding and achieve it.

Anyway, the approach is in some ways similar to the previous blog post where I built a terrain out of cubes, except in this case, instead of just plonking down a cube when it is discovered that it lies on the border between empty and solid space, a sample is taken of the densities on the 8 corners of the cell and if one corner is solid and one corner is not - then the isosurface must travel through this cell.
Marching cubes is the implementation of a look up table which holds information on what triangles need to be created to triangulate the isosurface within that cell for all the possible combinations of the corners being in solid or empty space.

http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html

You can see from this image where the corners represented by black dots are in solid space, that for each case the triangles needed to form a watertight mesh separating the solid areas from the open corners is defined. Each of these cases can be rotated in order to satisfy any combination of empty / solid corners.

Once all the cells are processed in this way the triangles are combined to form a mesh.

This approach has a flaw however in that by taking each cell on it's own there are a huge number of duplicated vertices which inflates memory usage in what is already an enormously memory intensive process.  Eric Lengyel for the C4 game engine provided a fantastic and thorough explanation here in his dissertation of how it could be done - I won't try to replicate his work here though I will post the result of my implementation and provide the actual source code here

You will notice in the previous image a kind of stair stepping going on.  It is blurred because the vertices and the normals are being reused but the effect is still clear and by having a closer look at the geometry it becomes apparent that the mesh is in fact very angular.

Solving this was also described in Eric's paper, the key observation is that all vertices which need to be created for any given case are created in the center of one of the 12 edges of the cube.  By interpolating the vertex position along the edge towards one corner or the other depending on how close the density at that corner was to being considered empty or solid as opposed to the other corner meant that the isosurface could be represented much more exactly.

There are still a few bumps here and there caused by my simplex noise generator which needs a bit of tweaking, however, the algorithm itself is working properly.

The transvoxel algorithm:

The inevitable problem, just as it was last time, is the planets are just too big.  The level of detail adjustments are not optional - they are required.

The issue is, just as there were with the height map style terrain,   two levels of detail next to each other,.  This means there will be cracks forming in the mesh where they do not line up.

http://www.terathon.com/voxels/

To solve this is not as simple as just sewing the chunks together or interpolating the levels of detail because the geometry is so much more dynamic.

The is what the transvoxel algorithm sets out to solve.  It provides a whole host of additional configurations which extend the look up tables to support seamless sewing of adjacent terrain chunks of different detail levels.

This permits me to render a planet this way.
Since the terrain is no longer composed of cubes, having the voxels aligned to the planet surface is no longer required.  The planet can be represented as one giant volume rather than the 6 separate cube faces.
This eliminates the cause of the awful distortion at the edges where the cube faces met and honestly I was glad to move away from the cube style terrain anyway.
Representing the terrain this way provides a pretty cool way to tunnel but finding a way to have the building blocks sit flush with the terrain sounded tricky.

Moving on.. again..

 

In the end what pushed me away from this approach was the sheer amount of data that needed to be generated in order to generate these terrains in the first place.  If you had a pre computed world then I'm sure this approach would work just fine, however,  for a procedural world like mine the generation times were just too long.

After some profiling I discovered some 98% of the time used to generate each chunk of mesh was used simply coming up with the density values in the first place,  largely because of the requirement to fill n^3 data points instead of n^2  required for a height map.

All was not lost, however, I learned an enormous amount from these experiments and I felt that I had come out the other side a much more skilled programmer than the one who entered.

The solution I decided on was a height map terrain after all.  The volumes were just not feasible on this scale. To support tunnelling, I would also have to be cutting holes in meshes.

Once again I was out of my depth but I am nothing, if not stubborn so I set off to learn how to accomplish this.