9
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ You should use instancing for rendering your cubes. You can find a tutorial here learnopengl.com/Advanced-OpenGL/Instancing . For storing the cubes: do you have strong memory constraints on the hardware? 16^3 cubes don't seem too much memory. \$\endgroup\$ – Turms May 20 at 14:49
  • \$\begingroup\$ @Turms Thanks for your comment! I don't have strong memory constraints, it's just a regular PC. But I thought, if every top most chunk is 50% air, and the world is very big, then there must be quite a bit of wasted memory. But it's probably not much like you say. So should I just go for 16*16*16 chunks with a static amount of blocks? And also, you say I should use instancing, is that really needed? My idea was to generate a mesh for each chunk, because that way I can leave out all the invisible triangles. \$\endgroup\$ – appmaker1358 May 20 at 15:01
  • 6
    \$\begingroup\$ I don't recommend using instancing for the cubes as Turms describes.This will only reduce your draw calls, but do nothing for overdraw and hidden faces - in fact it ties your hands from solving that problem, since for instancing to work all the cubes have to be the same - you can't delete hidden faces of some cubes or merge coplanar faces into bigger single polygons. \$\endgroup\$ – DMGregory May 20 at 16:02
  • \$\begingroup\$ Choosing the best voxel engine can be a challenge. The big question to ask yourself is "what operations do I need to do on my voxels?" That guides the operations. For example, you are concerned about how hard it is to figure out which voxel is where in an oct-tree. Oct-tree algorithms are great for problems which can generate this information as needed as it walks the tree (often in a recursive manner). If you have specific problems where this is too expensive, then you may look at other options. \$\endgroup\$ – Cort Ammon May 21 at 0:08
  • \$\begingroup\$ Another big question is how often voxels are updated. Some algorithms are great if they can pre-process data to store it efficiently, but less efficient if the data is contstantly being updated (as data might in a particle based fluid simulation) \$\endgroup\$ – Cort Ammon May 21 at 0:09
24
\$\begingroup\$

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: enter image description here

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:

enter image description here

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:

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your reply! It seems octree's are the way to go.(Since my voxel engine will be 3D) I have a frew questions I would like to ask though: Your last picture shows the black parts to have larger squares, since I intend to have a minecraft like engine where you can modify the voxel terrain, I would prefer to keep everything that has a block the same size, because otherwise it would make things very complicated, that's possible right?(I would still simplify the empty/air slots ofcourse.) Second, is there some kind of tutorial on how one would program an octree? Thanks! \$\endgroup\$ – appmaker1358 May 20 at 16:53
  • 7
    \$\begingroup\$ @appmaker1358 that's no problem at all. If the player tries to modify a large block, then you break it into smaller blocks at that moment. There's no need to store 16x16x16 values of "rock" when you could say instead "this whole chunk is solid rock" until that is no longer true. \$\endgroup\$ – DMGregory May 20 at 16:58
  • 1
    \$\begingroup\$ @appmaker1358 As DMGregory said, updating the data stored in an octree is relatively easy. All you have to do is divide the cell the change happened in until every sub cell contains only a single type of block. Here's an interactive example with a quadtree. Generating one is simple as well. You create one large cell, that completely contains the chunk, then you recursively go through every leaf cell (cells that don't have children), check if the part of the terrain it represents contains multiple types of blocks, if yes, subdivide the cell \$\endgroup\$ – Bálint May 20 at 20:51
  • \$\begingroup\$ @appmaker1358 The bigger problem is actually the reverse - making sure the octree doesn't become full of leaves with just one block, which can easily happen in a Minecraft-style game. However, there's many solutions to the problem - it's just about choosing whatever you find appropriate. And it only becomes a real problem when there's a lot of building going on. \$\endgroup\$ – Luaan May 21 at 7:47
  • \$\begingroup\$ Octrees aren't necessarily the best choice. here is an interesting read: 0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines \$\endgroup\$ – Polygnome May 23 at 14:31
8
\$\begingroup\$

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
    );
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for your reply! It seems octree's are the way to go. But I do have 2 questions though, you say octree's are faster than scanning through an array, which is correct. But I wouldn't need to do that as the array could be static meaning I can calculate where the cube I need is. So why would I need to scan? Second question, in the last tier of the octree(the 1x1x1), how do I know which cube is where, since if I understand it correctly, and octree node has 8 more nodes, how do you know which node belongs to which 3d position?(Or am I supposed to remember that myself?) \$\endgroup\$ – appmaker1358 May 20 at 16:46
  • \$\begingroup\$ Yes, you already covered the case of an exhaustive array of 16x16x16 voxels in your question, and seemed to reject the 4K per chunk memory footprint (assuming each voxel ID is a byte) as excessive. The search you mentioned comes when storing a list of voxels with a position, forcing you to scan through the list to find the voxel at your target position. 4096 here is the upper bound of that list length - typically it will be smaller than that, but generally still deeper than a corresponding octree search. \$\endgroup\$ – DMGregory May 20 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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