Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Each voxel datapoint in my terrain model is made up of two properties: density and material type. Each is stored as an unsigned integer value (but the density is interpreted as a decimal value between 0 and 1). The density values are used to generate a mesh with the marching cubes algorithm.

My current idea for rendering these different materials on the terrain mesh is to store eleven extra attributes in each vertex: six material values corresponding to the materials of the voxels that the vertices lie between, three decimal values that correspond to the interpolation each vertex has between each voxel, and two decimal values that are used to determine where the fragment lies on the triangle.

The material and interpolation attributes are the exact same for each vertex in the triangle. The fragment shader samples each texture that corresponds to each material and then uses the aforementioned couple of decimal values to interpolate between these samples and obtain the final textured color of the fragment.

It should work fine, but it seems like a big memory hog. I won't be able to reuse vertices in the mesh with indexing, and each vertex will have a lot of data associated with it. It also seems pretty slow. What are some ways to improve or replace this technique for drawing materials on a voxel terrain mesh?

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

Due to the sheer volume of data in your average voxel world, it will be challenging to draw much geometry with your approach, before hardware limits are reached, without some kind of spatial subdivision approach. You also need to be highly efficient in packing data at the bit/byte level.

Method: RLE

Enter Run-Length Encoding (RLE) compression as a popular option. Voxels are stored columns, as in the following example:

6E1G9A

Which means, from top to bottom, "6 earth, 1 grass, then 9 air".

So instead of storing a byte or more for every voxel, let alone every vertex, you instead create compressed columns of data that allow you to upload far more to the GPU, as uniform variables (GLSL lingo, not sure what they're called in HLSL). Instead of voxels scattered in 3D space, you have a single mesh representing each columnar run of homogeneous voxels (y-axis).

From a mesh building perspective, the idea is that you would then evaluate these RLE columns, fragment them into there individual runs, and create 8 vertices per run. You would simultaneously set up a uniform variable (GLSL) for any additional data you might need for that run, and upload the lot.

You would want to keep the full run-length encoded columns "from fundament to heaven", so to speak, on the CPU side, but you would send individual runs up to the GPU. This is because there will be breaks in a column where meshes end and new ones begin; think of a cross-section of an (x, z) area where there is a cave or air-pocket; you would have to end one columnar mesh where the floor is, and start another where the roof begins. You might have to do this several times in a single (x, z) location.

You largely want to avoid conditional logic / loops in shaders wherever possible, so try to do that sort of thing on the CPU side -- especially as regards basic geometry (see the next method for more on why I say "basic" geometry).

Where RLE gets more difficult is where you have to store eg. lighting, cellular automata or other information as well as data on materials. This causes a higher ratio of fragmentation if the same RLE container is used for that data, since the data is no longer as homogeneous as it was; hence, it may be better to simply upload separate runs for other elements that may affect rendering, such as lighting.

Method: Geometry shader

One way you could do things would be to maintain data for every vertex, but where each vertex represents a voxel. You could then use a geometry shader to spawn an individual cubic geometry for each voxel. This will depend very much on your size per voxel and intended viewing distance (one reason why MineCraft's view distance is so short is that it spams geometry like crazy, brute force). Furthermore, you would use bitflags to pack as much data into whatever space you do allocate per voxel, as possible. For instance, if you only need 32 types of voxel, then use the 5 least significant bytes to represent that, and 3 most significant bytes to represent other data, rather than wasting those last 3 bits (good for 2^3=8 values) and starting a whole new byte. Using bitwise operators to extract that data back out again, is available on the GPU side only in newer versions of GLSL and HLSL (you'll need to check which versions, exactly).

Method: 3D spatial subdivision

I'm not going to go into this too heavily as it is a fairly intense topic more likely to be addressed in computational geometry and rendering research papers than in game engine tech, but what RLE does is to do compression in one axis only, the y-axis. This makes the problem easier to consider in some senses, as it becomes, in many ways, a 2-dimensional planar problem. However, it also introduces it's own concerns; eg. by biasing detail axially, maintaining steady framerates when viewing in different directions can become problematic. Slabs-based approaches are similar in that they have again not utilised compression in all 3 dimensions. OTOH, KD-trees and octrees are two common, highly efficient data structures for the construction of voxel spaces by compressing in all 3 axes as opposed to just one or two. KD-trees are potentially more efficient overall, but contain arbitrary structure and so are more complex to process. Octrees have a regular structure but suffer from heavy processing costs at the corners of very large regions, though they can be very efficient elsewhere.

Method: Unstructured 3D clustering, hybrids

Point cloud data offers a relatively new (to the games industry anyway!) method of storing and rendering data, but is very much experimental technology and so almost certianly not suitable for your purposes. However, like KD-trees, the arbitrary placement of voxels or voxel-sets might provide real value to you in terms of reducing processing cost and memory requirements on the CPU and GPU sides. You may be able to combine the characteristics of several of the above methods into a solution that is most efficient for you. This is what I've done in my engine, though I won't share specifics. :)

share|improve this answer
    
The RLE method sounds like the most promising right now for me. Since the terrain is probably going to be static, I won't have to deal with recalculating the RLE data. The only problem with that method that I can see right now is doing lower LODs. –  Boreal Dec 6 '12 at 21:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.