Voxel Engine – Mesh Generation

In my previous post, which can be found here, I discussed an unusual approach to storing voxel engine data using run length encoding and interval trees. I didn’t, however, manage to get onto discuss how to generate meshes from this structure. Therefore in this post I would like to do just that and describe how the data structure can be exploited to produce lower polygon count meshes in less time than with traditional methods.

Before we start I’ll just go over a couple of crucial points I neglected to mention in the previous post. Firstly the intervals stored in the tree are inclusive, this means both the start and end coordinate of the run are of the specified voxel type. Secondly, all nodes within the tree store a reference to their parent node and so we can quickly get the runs before and after any given run, i.e we can iterate forward and backwards. Finally each Chunk is guaranteed to contain no intersecting intervals and to contain runs covering the full range of coordinates that it can contain. This again might seem obvious, however, the first version of the data structure I wrote omitted air intervals. This was problematic, however, as when starting out the meshing it is necessary to obtain the first interval that intersects the MegaVoxel. If, however, this first interval is air and therefore not included in the tree we can’t obtain an iterator to its position. We therefore can’t easily get the next non-air run and the whole system breaks.

Now given these points we can move onto discussing how meshing works. The meshing function needs only two parameters, an array interface to populate with the mesh data (this can be backed with hardware Vertex and Index buffers) and the height of the MegaVoxel to generate the mesh for (chunkY). We need to know the height as since MegaVoxels are only 16 high whereas Chunks are as high as the map, it takes multiple MegaVoxels to render one chunk. Throughout this article all coordinates mentioned are relative to the bottom “origin” of the Chunk, not to the world origin. As we have the 1 voxel wide overlap region with the adjacent chunks, this means the coordinates are from (-1,0,-1) to (17,MapHeight,17).

As iterating forward and backwards is still relatively costly we want to keep it to a minimum and we therefore keep track of a number intervals at any given time. We need to keep track of the current, previous and next intervals within the chunk and also the top interval (the first interval in the x-z plane above the end of the current interval) and the bottom interval (the last interval in the x-z plane below the start of the current interval). At any point these intervals may be nil (non-existent) and the code makes sure to handle such situations. At the start of the meshing function a binary search is used to set current to the first run in the MegaVoxel and then the other intervals are obtained via iteration.

As mentioned before, the Interval Tree is 1D and stores coordinates hashed using the function below:

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

However, as ChunkSize is 18 and therefore not a power of two there is no fast function to convert a Hash to its coordinate representation (as non-bitwise modulus is very expensive). Therefore a lookup table is calculated on startup and used by a functor called Hasher, which provides quick conversion between coordinates and hashes.

The core of the meshing function is a simple while loop which will continue indefinitely until either the current interval is nil or its key (start value) is outside the bounds of the MegaVoxel being meshed. At the end of each loop it shuffles the current, previous and next intervals along one. If the current interval is not air we don’t do anything within the loop, instead iterating along until we find a run of air. We look for runs of air as there are likely to be less runs of air within a chunk than runs of solid voxels, particularly if there are different types of solid voxels which can’t be merged together. Once we find a run of air we compute the following values and can then start adding faces.

const int YMult = ChunkSize*ChunkSize;
const int ChunkV = YMult*ChunkHeight;
int CurrentKey = MAX(current->key, i);
int CurrentHigh = MIN(current->high,ChunkY+ChunkV);
Coord AStart = Hasher(CurrentKey);
Coord AEnd = Hasher(CurrentHigh);
int CurrentHighCapped: MIN(currentHigh, Hasher(16, Start.Y, 16));
int CurrentKeyCapped: MAX(currentKey, Hasher(-1, End.Y, -1));

First we add the faces with normals along the x axis.

if (previous != nil) {
++ int blockType = previous->GetType();
++ if (AStart.X > 0 && AStart.Z >= 0 && AStart.Z < 16) {
++++ AddLeft(Coord(AStart.X - 1, AStart.Y, AStart.Z));
++ }
}

if (next != nil) {
++ int blockType = next->GetType();
++ if (AEnd.X < 15 && AEnd.Z >= 0 && AEnd.Z < 16) {
++++ AddRight(Coord(AEnd.X + 1, AEnd.Y, AEnd.Z));
++ }
}

Where AddLeft and AddRight add faces with normals of (1,0,0) and (-1,0,0) respectively. Note that I have omitted the blockType and mesh-data parameters from these and all future function calls for readability.

Next come the faces of the voxels above the current run of air.

while (top != nil && top->high < currentKey + YMult) {
++top = GetNext(top);
}
while (top != nil) {
++int blockType = top->GetType();
++if (blockType == 0) {
++++if (top->high >= currentHigh + YMult)
++++++break;
++++top = GetNext(top);
++++continue;
++}
++Coord start = Hasher(MAX(top->key,currentKey+YMult));
++Coord end = Hasher(MIN(top->high,currentHigh+YMult));
++Coord cur = start;
++//First Row Remainder
++if (start.X > 0 && start.X < ChunkSize && end.Z != start.Z) {
++++AddTop(start, Coord(16, start.Y, start.Z+1));
++++cur.Set(0, start.Y, start.Z + 1);
++}
++if (end.Y != start.Y) {
++//Iterate to end of top corner
++++AddTop(cur, Coord(16, start.Y, 16));
++} else {
++++if (end.Z - cur.Z > 1 && end.X < 15) {
++++++//Add full section
++++++AddTop(cur, Coord(16, cur.Y, end.Z));
++++++//Add Remainder
++++++AddTop(Coord(0,cur.Y,end.Z), Coord(end.X+1,end.Y,end.Z+1));
++++} else if (end.Z - cur.Z > 1) {
++++++AddTop(cur, Coord(16, cur.Y, end.Z + 1));
++++} else {
++++++AddTop(cur, Coord(end.X + 1, end.Y, end.Z + 1));
++++}
++}
++if (top->high >= currentHigh + YMult)
++++break;
++top = GetNext(top);
}


Where AddTop adds a face with the bottom left and top right coordinates passed as parameters. It also clamps the coordinates to within the MegaVoxel, performing wrapping where needed. For example (-1,Y,Z) as the second parameter gets converted to (16,Y,Z-1) and (X,Y,-1) as the first parameter goes to (0,Y,0). This clamping is necessary as the region overlapping with other chunks shouldn’t be rendered. Instead it will be rendered by the MegaVoxel’s of other chunks.

The reason for having the explicit “break” statements is so that we don’t move the top iterator forward more than is absolutely necessary. As the top iterator isn’t ever reset or moved backwards, not having the explicit breaks leads to missing faces.

The next faces to add are those for the voxels below the run of air. However, as the code for adding the bottom faces is much the same as the top, I’ll save space by not including it here. The only differences are that “+ YMult” is changed to “- YMult”, we use the bottom iterator instead of the top iterator and AddTop is changed to AddBottom, which behaves as you would expect.

The final faces to add are those pointing along the Z axis. The code for adding faces with normals of (0,0,1) is below.

back = previous;
while (back != nil && back->key > currentHighCapped - ChunkSize)
++back = GetPrevious(back);
while (back != nil && back->high >= currentKey - ChunkSize) {
++int blockType = back->GetType();
++if (blockType == 0) {
++++back = GetPrevious(back);
++++continue;
++}
++Coord RunEnd = Hasher(MIN(back->high, currentHighCapped - ChunkSize));
++Coord RunStart = Hasher(MAX(back->key, currentKey - ChunkSize));
++if (RunEnd.Z != RunStart.Z) {
++++AddBack(Coord(0, RunEnd.Y, RunEnd.Z), Coord(RunEnd.X + 1, RunEnd.Y + 1, RunEnd.Z));
++++AddBack(RunStart, Coord(16, RunStart.Y + 1, RunStart.Z));
++} else {
++++AddBack(RunStart, Coord(RunEnd.X + 1, RunEnd.Y + 1, RunEnd.Z));
++}
++back = GetPrevious(back);
}

All of this is enclosed in an “if (AStart.Z >= 0)” block as if Z is -1 then those faces will be handled by another MegaVoxel.

The code for adding the front faces is again much the same. The differences are “- ChunkSize” is changed to “+ ChunkSize”, GetPrevious is changed to GetNext, AddBack is changed to AddFront and the iterator is initially assigned to next not previous. For similar reasons as before this procedure is enclosed in a “if (AStart.Z < 16)” block.

And with that we are finally done! Whilst I am aware I have skimmed over a few details here and there and not explained the reasoning behind everything, I hope this article provides a good head-start for anyone looking to implement a similar voxel engine. It took me quite a while to work out and debug all the cases involved and I hope I can save someone else that hassle. In the next post I intend to analyze the performance of this algorithm and compare it to the more traditional method of meshing.