Voxel Engine – Data Storage

A while ago, almost two years ago, I stumbled across a very interesting article, which can be found here, on different ways of storing data within a voxel engine. Having discussed the common methods employed in voxel engines it proposes a method using interval trees to store the data and it is this method I’d like to talk about in this post.

For those of you who don’t want to read the article I’ll give a brief summary of the data structure suggested, although if you have time I seriously recommend giving it a read: it is well worth it. Firstly the world is broken down into small 16×16 chunks extending from the bottom of the map to the top. The computer then only has to load into RAM the chunks that are relevant and can page out the rest to the disk. Relevant chunks could simply be ones that are within a certain distance of the player, or there could be a more complex method for determining this. Minecraft famously makes use of this chunk technique in order to create near infinite worlds.

In Minecraft, and indeed most voxel engines, these chunks store data using a giant 3D array, with each position in the array corresponding to a location in the chunk and the value corresponding to the voxel type at that coordinate. The data structure suggested, however, works on the premise that within a chunk there is a lot of contiguous space of the same voxel type, for example, air or stone. Therefore rather than storing the voxel type for every position within the chunk, we can save memory by instead storing intervals of voxels. For example, from (0,0,0) to (0,5,0) is stone, from (1,5,0) to (7,6,0) is air and so on… This is commonly referred to as run length encoding and gives us very good memory compression.

The naive implementation of run length encoding is to simply store each of these runs in a long list, however, with this approach random access is linear in time with respect to the number of runs in the chunk. This means if we want to determine the type of voxel at a given coordinate in the worst case situation we have to iterate through every run within the chunk. This is clearly unacceptable and this is where the genius of the data structure is: rather than storing the runs in a list we store them in an interval tree and therefore we can perform random access operations in logarithmic time with respect to the number of runs.

One of the key jobs of a voxel engine is to convert the voxel data into a visible mesh and this is a job that this data structure excels at. But before we discuss that I’ll just take a quick step back and discuss briefly how meshing works in a standard voxel engine. There is another great article on this on the same website as before (here), but again I’ll briefly summarize it. Each voxel can be represented as a cube and therefore the naive approach is to simply add all 6 faces for each solid voxel. The number of faces, however, can be dramatically reduced from 6 per voxel by only adding the faces on the sides on which there are adjacent non-transparent voxels. This can then be improved further by breaking the map into smaller pieces, which I will call MegaVoxels. This saves memory and GPU time rendering chunks that aren’t relevant and also means that when a voxel changes we don’t have to regenerate the whole terrain. In fact in most cases we just have to regenerate the MegaVoxel it is in, voxels on edges of MegaVoxels being the exception to this rule. It should be noted though that unlike chunks, these MegaVoxels are 16x16x16, i.e they don’t extend from the top of the map to the bottom as the chunks do.

Below is a single MegaVoxel containing random noise:

The first decision that I had to make when implementing this data structure was how to convert the 3D positions into 1D scalars, as interval trees are 1D. I briefly toyed with the idea of using Morton Codes (a Z order curve) to give fast dynamic LOD: When the player is far away we can group together adjacent voxels to make a lower polygon count, and therefore faster to render, mesh that to the far away player looks the same. However, the problem with this method is that it doesn’t really lend itself very well to voxel terrain. Morton codes behave very much like octrees, which means they group 8 voxels into a cube and then group 8 of these cubes into a cube of 8 cubes of 8 voxels and so on…

To see why Morton Codes aren’t so great consider a situation in which we have solid stone voxels up to a height of 8 and then the rest of the MegaVoxel is air. This structure fits very nicely into our Morton code system, potentially getting split into just 2 runs, depending on the axis order of the Morton Codes. If, however, we add one block of stone at (0,9,0) things go very badly. As the cube from (0,9,0) to (1,10,1)  is no longer contiguous the voxels can’t be merged together into a cube of 8, and then this cube can’t be merged with the other 8 cubes of voxels surrounding it and so on. Whilst it is fairly simple to have the system merge the 7 remaining air voxels together and then merge these with the other air voxels, doing so loses us the octree like structure which was the main advantage to using Morton Codes in the first place. Meshing is also very inefficient with this structure, as we are only able to group runs of voxels that are powers of 8 long into larger cubes and then determining adjacency to air of these merged cubes adds yet more complication. All this should make it little surprise I abandoned this idea relatively quickly, instead opting for the simple x axis first, followed by z axis followed by y axis (where the y-axis is up/down).

Hash = X + Z * ChunkSize + Y * ChunkSize * ChunkSize

One of the big difficulties with storing data in chunks is how best to handle the voxels on the edges. When meshing, these edge voxels need to know what voxels they are adjacent to, however, on one side of them that data is not easily available, as it is stored in a different chunk. With flat arrays this isn’t such a problem as one simply retrieves the adjacent chunk and asks for the voxel type at the relevant coordinate. However, with this interval tree structure, random access, such as this, is very expensive and therefore best avoided. This issue stumped me for a while and in the end I decided to take a look at the benchmarking code used in the aforementioned article to look for inspiration. Unfortunately none was to be had as the code neatly sidesteps the issue by offsetting the iteration one voxel in from the border of the chunk and therefore no edge voxels are actually processed. However, looking at the engine that the code was taken from it appears that it performs a binary search for each of these 1024 edge voxels!

Therefore realizing I was on my own I thought up a number of different solutions: I considered creating bitmasks for each vertical strip of edge voxels that would be kept up to date with whether the voxel was visible. I also considered creating a second Interval tree of just the regions of air or maintaining two interval trees with one using an X axis first hash and the other a Z axis first hash. However, in the end I decided to make the chunks “overlap” by one voxel with their adjacent chunks, with both containing the edge voxels of the other. This means that each MegaVoxel can determine all the information it needs for meshing from just one chunk. Whilst this does mean that there is duplicate data, the run length encoding mostly counteracts this and also the sharing of the data leads to some nice tricks when meshing. However, as this post has gotten rather long I think I will break off here and save discussing that for another post.