Storing voxels for a voxel Engine in C++

Question

I am trying to write a little voxel engine because it's fun, but struggle to find the best way to store the actual voxels. I'm aware I will need chunks of some sort so I don't need to have the entire world in memory, and I'm am aware I need render them with reasonable performance.

I read about octrees and from what I understand it starts with 1 cube, and in that cube can be 8 more cubes, and in all those 8 cubes can be another 8 cubes etc. But I don't think this fits my voxel engine because my voxel cubes/items will all be the exact same size.

So another option is to just create an array of 16*16*16 size and have that be one chunk, and you fill it with items. And parts where there aren't any items will have 0 as value (0 = air). But I'm afraid this is going to waste a lot of memory and won't be very fast.

Then another option is a vector for each chunk, and fill it with cubes. And the cube holds its position in the chunk. This saves memory (no air blocks), but makes looking for a cube at a specific location a lot slower.

So I can't really find a good solution, and I'm hoping someone can help me with that. So what would you use and why?

But another problem is rendering. Just reading each chunk and sending it to the GPU using OpenGL is easy, but very slow. Generating one mesh per chunk would be better, but that means every time I break one block, I have to rebuild the entire chunk which could take a bit of time causing a minor but noticeable hiccup, which I obviously don't want either. So that would be harder. So how would I render the cubes? Just create all the cubes in one vertex buffer per chunk and render that and maybe try to put that in another thread, or is there another way?

Thanks!

Answer 1

Storing the blocks as the positions and the values is actually very inefficient. Even without any overhead caused by the struct or object you use, you need to store 4 distinct values per block. It would only make sense to use it over the "storing blocks in fixed arrays" method (the one you described earlier) is when only a quarter of the blocks are solid, and this way you don't even take any other optimization methods into account.

Octrees are actually great for voxel based games, since they specialize at storing data with larger features (e.g. patches of the same block). To illustrate this, I used a quadtree (basically octrees in 2d):

This is my starting set containing 32x32 tiles, which would equal 1024 values:

Storing this as 1024 separate values doesn't seem that inefficient, but once you reach map sizes similar to games, such as Terraria, loading screens would take multiple seconds. And if you increase it to the third dimension, it starts to use up all space in the system.

Quadtrees (or octrees in 3d) can help the situation. To create one, you can either go from tiles and group them together, or go from one huge cell and you divide it until you reach the tiles. I will use the first approach, because it's easier to visualize.

So, in the first iteration you group everything into 2x2 cells, and if a cell only contains tiles of the same type, you drop the tiles and just store the type. After one iteration, our map will look like this:

The red lines mark what we store. Each square is just 1 value. This brought the size down from 1024 values to 439, that's a 57% decrease.

But you know the mantra. Let's go one step further and group these into cells:

This reduced the amount of stored values to 367. That's only 36% of the original size.

You obviously need to do this division until every 4 adjacent cell (8 adjacent block in 3d) inside a chunk is stored inside one cell, essentially converting a chunk to one large cell.

This also has some other benefits, mainly when doing collision, but you might want to create a separate octree for that, which only cares about whether a single block is solid or not. That way, instead of checking against collision for every block inside a chunk, you can just do it against the cells.

Answer 2

Octrees exist to solve exactly the problem you describe, allowing dense storage of sparse data without large search times.

The fact that your voxels are the same size just means that your octree has a fixed depth. eg. for a 16x16x16 chunk, you need at most 5 levels of tree:

• chunk root (16x16x16)
  • first tier octant (8x8x8)
    • second tier octant (4x4x4)
      • third tier octant (2x2x2)
        • single voxel (1x1x1)

This means you have at most 5 steps to go to find out whether there's a voxel at a particular position in the chunk:

• chunk root: is the whole chunk the same value (eg. all air)? If so, we're done. If not...
  • first tier: is the octant that contains this position all the same value? If not...
    • second tier...
      • third tier...
        • now we're addressing a single voxel, and can return its value.

Much shorter than scanning even 1% of the way through an array of up to 4096 voxels!

Notice that this lets us compress the data wherever there's a full octant of the same value - whether that value is all air or all rock or anything else. It's only where octants contain mixed values that we need to subdivide further, down to the limit of single-voxel leaf nodes.

---

For addressing the children of a chunk, typically we'll proceed in Morton order, something like this:

1. X- Y- Z-
2. X- Y- Z+
3. X- Y+ Z-
4. X- Y+ Z+
5. X+ Y- Z-
6. X+ Y- Z+
7. X+ Y+ Z-
8. X+ Y+ Z+

So, our Octree node navigation might look something like this:

GetOctreeValue(OctreeNode node, int depth, int3 nodeOrigin, int3 queryPoint) {
    if(node.IsAllOneValue)
        return node.Value;

    int childIndex =  0;
    childIndex += (queryPoint.x > nodeOrigin.x) ? 4 : 0;
    childIndex += (queryPoint.y > nodeOrigin.y) ? 2 : 0;
    childIndex += (queryPoint.z > nodeOrigin.z) ? 1 : 0;

    OctreeNode child = node.GetChild(childIndex);

    return GetOctreeValue(
                child, 
                depth + 1,
                nodeOrigin + childOffset[depth, childIndex],
                queryPoint
    );
}