A terrain based on a 3D density function

The terrain engine I’ve implemented thus far uses a three-dimensional density function to calculate its polygons. Density-based geometry generation is nothing new, and in fact my implementation uses the Marching Cubes algorithm, beautifully described in the GPU Gems 3 cookbook. That article is what sparked my interest in the first place.

chunks

However, the article describes a very low-level approach to creating voxels (using shaders), which are very small in rendering terms (up to five triangles). I wanted a more high-level implementation, which could take advantage of all the goodness Unity brings to the table (such as automagic collision detection when given a 3D mesh). I ended up using the majority of the lookup tables given in that article, but I rewrote the entire algorithm from scratch.

At the base of my terrain implementation sits a chunk:

chunkA chunk is a collection of voxels, as described in the GPU Gems article. In the above image, I’m using a 20x20x20 chunk. In a naive implementation, this chunk would have 8000 voxels, and they would each in turn have a small mesh containing from zero to five triangles. This is exactly what I wanted to avoid, since I wanted the meshes to be as big as possible — Unity has solid support for handling meshes, and I wanted to take advantage of that. Using several thousand mesh objects just to display a small piece of the terrain was out of the question.

When generating a chunk, I’m sampling the density function at all 8 corners of each voxel in order to get triangle data needed to construct the given chunk’s mesh. So, for a chunk with NxNxN voxels, I’m sampling the density function (N+1)x(N+1)x(N+1) times in order to generate the mesh.

Note that “voxels” are entirely fictional here, I’m using them simply to illustrate the concept. The algorithm takes a 3D density function and spits out a display-ready Mesh object. It has no internal “voxel collection” or anything like that.

This process is repeated for all chunks in the currently visible part of the terrain, and you get a nice piece of 3D terrain, rendered using only math and no models:

terrain_block

I’m intentionally using flat shading, since that’s the art style I’m aiming for. Unfortunately, that means the meshes have no vertex reuse – every triangle has its own vertices, which greatly increases the size of the vertices array. I might find a better way to do flat shading in the future.

In the next article, I’ll write about how I’m handling the infiniteness of the terrain, using chunk recycling and level of detail (LOD) rendering.

 

2 thoughts on “A terrain based on a 3D density function

  1. David Je

    that is a really nice engine :)
    at the moment im doing a voxel game too with the marching cubes algorithm. but i have some problems. i want to make a voxel planet (density function: X*X+Y*Y+Z*Z -R*R) and the sphere gets rendered properly. but if i want to slice my terrain up into chunks im running into problems. do you have any tipps for “chunking” a sphere with my density function?

    Reply
    1. vl4dimir Post author

      Hi David, sorry for the extremely late reply, I hope it’s not too late to try to help you. Are you talking about just slicing your existing terrain into chunks so that they can be rendered (and possibly LODed) independently? If so, I’d probably go with a polar grid, centered in the middle of the sphere and then have each chunk just sample its own part of the density function. So basically each chunk would be a long “pyramid” with a rectangular slice of the planet surface at the top and narrowing all the way down to the center of the planet.

      If you’re making a fully explorable planet (with tunnels and so on), you can even slice the “pyramids” height-wise (sub-chunk them, so to speak). First level would be the surface of the planet, the second level is the one beneath and so on, while the last level would actually be a sphere in the middle of your planet.

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *