Doughnuts and Coffee Mugs

My first attempts to extract a smooth surface out of the voxels had failed. Relaxation was not good enough to preserve the features of traditional meshes once they were converted into voxels. Maybe it was a sign that I should move away from voxels?

There was another advantage in voxels that was key for the results I had envisioned. I will take a break from the surface extraction topic to discuss this.

It is mainly about doughnuts and coffee mugs. But I will come to them later.

The number of pixels in the screen is constant. Objects, when viewed in perspective, appear in different size depending on how close they are. A rock next to the viewer may take 1000 pixels on the screen. The same rock when viewed from a distance, may be only 10 pixels. It would take 100 rocks the same size to fill the same screen space a single rock occupied when viewed up close. It is fairly obvious that in a perspective view objects multiply in the distance.

This is a big problem for most 3D engines. There are a few tricks for this, like a dense fog that eats everything in the distance, or popping in the objects in when they are close enough. In most cases engines use a Level Of Detail (LOD) system, which switches to low-resolution models for objects far away. Still, this is not enough to have details preserved at large distances.

I wanted to have the horizon line very far away, and I wanted all the complexity of the world visible even at that distance. If there was a village a couple of miles away, I wanted the windows in the houses to appear as tiny dots, and still be able to see all the walls and roofs for the entire village.

Current terrain engines are able to display very large expanses of land using a technique called Clipmaps. The scene around the viewer is broken into multiple tiles. The tiles get bigger depending on how far they are from the viewer. A tile next to the viewer may be just a few square meters, but a tile next to the horizon line may be kilometers wide.

The nice thing about clipmaps is that each tile, no matter where it is located, has roughly the same amount of information. Due to the perspective projection tiles far away are shrunk. Even if they cover a larger expanse of terrain, they end up taking the same space on screen than nearby tiles. As a result, it is possible to cover very large areas at a fairly constant degree of detail.

This technique is normally restricted to the terrain. Any objects on top of it, like vegetation and architecture, are not part of the clipmap. This is where the traditional LOD approach comes in, but it is not good enough to handle all the instances necessary for a distant horizon line. Distance to horizon is severely restricted an the benefits of the terrain clipmap go to waste.

I wanted to use clipmaps for all the virtual world's geometry. The classical clipmap algorithm is 2D. Terrain is usually represented as a heigthtmap. In my case I would need to extend clipmaps to 3D. There are a few non-trivial issues there, like how to generate seams between tiles of different resolution, but I will address them in a future post.

I set my tile resolution at 64x64x64. Each unit would be a decimeter for the tiles closest to the viewer. That would give tiles of 6.4 meters. The next level tiles would be twice that length, 12.8 meters. If I wanted the horizon at 5km, then some of the tiles would be one kilometer length and even more.

This all sounds very nice in theory. Now remember that each tile, no matter its size, must have roughly the same amount of information. I could easily see my small 6.4 meter tile fitting in a budget of 1000 triangles, but how can I fit an entire one cubic kilometer of my world into 1000 triangles and still make it look good?

This is where the doughnuts and mugs come into play. Traditional mesh optimization methods can reduce a lot the number of polygons in a mesh, but they either cannot simplify the topology of the mesh at all, or are not very good at that. An example will help:

Let assume we have a large wall with a small window. The window in this case is just a square whole in the wall. Traditional mesh simplification methods collapse edges in the mesh until the desired triangle count is reached. Still, no matter how much you crank the optimization up, the algorithm will preserve the hole in the wall. If the algorithm could remove the hole -it is a tiny hole anyway- it could save a lot of triangles.

The problem here is that the topology of a wall is different than the topology of a wall with a hole. It is not like the doughnut and the mug, which are topologically identical:

This is what mathematicians call the Genus of the object, which is probably a fancy way to say how many holes a solid has. Traditional mesh optimization cannot cross that barrier, they cannot close holes in the solid to make the object simpler. There are other mesh optimization methods that use clustering of vertices. While they do modify the topology of the mesh, it is hard to control the results.

But if we optimize in voxel space, then it is adifferent story. Voxels can be filtered, summed up and transformed in many advantageous ways. In the example of the large wall with the small window, the voxels of the wall eventually would take the space of the window, naturally filling up the hole.

I knew voxels would provide an edge when it was time to synthesize the larger tiles of my clipmap. I just needed a better way to extract the surfaces out of them.