Managing Voxel Data

Question

I've been programming in C++ as a hobby for about 4 months now, and I've really loved creating stuff using voxels. I wrote a "game" (More of just a personal challenge, as I really only did the terrain, no gameplay) that rendered a Minecraft-like world, but recently I've been thinking about trying to write a game/challenge/etc that uses an algorithm such as Marching Cubes or Dual Contouring and reducing the voxel size. When I wrote my Minecraft-like project, I stored each chunk's data in a multidimensional array of unsigned shorts (thus giving me up to 65536 different block types). Additionally, for rendering, I only stored one point (as a GLubyte) and another GLubyte to indicate which of the 6 faces the point represented. I then rendered the face using a geometry shader. All of this was done to save the amount of RAM usage my project required, as I wanted to have the render distance out as far as possible.

With the new project I've been thinking about, the thing I can't wrap my head around is how I can possibly store enough voxel data to have voxels around ~5cm or 10cm compared to the old 1m sized voxels I had. When I rendered a 704x704x704 area of blocks, my old project used around 670MB of RAM. If I shrunk the voxel size to 10cm and kept the same render distance, that would be around 649GB of Voxel data (assuming 2 bytes per voxel and an area of 7040^3 voxels). Is there any way I can store the voxel data in a more efficient manner that still allows me a wide range of different voxel types?

Answer 1

Do you need to have every single chunk (presuming you're using chunks) in memory at once? Some will be occluded - particularly underground - or behind mountains etc. Lots will probably be just air/empty and so could be marked with a flag.

Also you could use a LOD octree or similar structure to try keep the detail currently visible inversely related to the distance from the observer. As stated by Jason, this is much more likely to buy you performance, but it's a major structural change from a flat chunk map.

See this article about clipmaps from my favourite blog (he has a voxel engine similar to what you describe with a voxel size of ~a decimetre).

Answer 2

The standard approach for engines like Ken Silverman's VoxLap and it's successor Ace of Spades, is to use RLE compression and several other bit-level tricks to both store and access the data. This sort of 1D compression tends to be highly efficient and considerably easier to use than octrees. I believe Silverman's engine achieved a voxel resolution of something like 10cm cubed. Something you don't commonly see today, and which was achieved on much weaker hardware.

I believe it is also true that his approach did not store colours for unexposed voxels, that it instead calculated colour for surface voxels as a function of height, or by remembering which areas of the terrain had been blasted open and colouring these as "fresh soil". You could use some sort of continuous function like perlin noise to do this, but it could rapidly get costly for large surface areas (unless, perhaps, performed on the GPU).

Octrees are not bad, but they are difficult to use in practice, and cache-efficient allocation is considerably more challenging than RLE, which is easy to linearise by chunk. Tero Karras and Samuli Laine's seminal paper on SVOs indicates just how much effort goes into truly performant octree implementation -- and that is considering only rendering, not gameplay or network communications.

Answer 3

I don't know how far you've gone in your project but I and a friend of mine are using the Dual Marching Cubes algorithm, based on Octree chunck structure and using a dual grid to render the data. It has many advantages, like really low memory required and a really fast rendering. It may be a little tricky to implement Level Of Detail (LOD) in chunk borders with other chunks, but if you have some spare time you may find out how Ogre3D developers did.