Generating Collision Meshes for a Voxel Chunk


A collision mesh for a series of chunks

Handling collisions with voxel based content can be tricky to do in a way that enables accurate collisions whilst also running fast enough to allow for multiple physics bodies at once. This is because checking collisions between concave shapes is a slow process, as is breaking a concave shape into multiple convex ones. Game Engines like Unity will kick up a fuss if you have non-manifold meshes for physics objects, and making the simplest convex mesh of a concave one will not allow for block specific collisions. Ideally, you want to create a compound shape made up of simple convex shapes on mesh generation, and this post will walk you through how to do that.

Every half decent physics engine or full game engine that you come across will have a ‘Box Shape’ collision mesh type and a ‘Compound Shape’ collision mesh type. A compound collision shape is simply a (sometimes concave) shape made up of other collision shapes, whatever they may be. For this method, our compound shapes are going to be made entirely from the box shapes.

Understanding the Method

For the start of this example, we will be using a 16*16*16 voxel grid to represent a single chunk. Voxels will be a simple integer where 0 represents an empty space and any higher value represents another block that will be added to the collision shape. All code snippets will be in C# and specifically for Unity3D, however the method can be carried over to other languages and engines easily. I have used this method both with ‘Unity3D’, and with my own Game Engine using ‘Bullet’ for the physics. Download links for the project can be found at the bottom of the page.

The general theory is to choose a point in the mesh, and expand left, up, and forward from there. When expansion can no longer occur in a single dimension because the block has either been explored, is empty, or is the end of the grid, the box will stop growing in that direction. Once all dimensions for growing have been exhausted, the box will stop growing and will be added to the compound collision shape. A new point will then be chosen and the process will start again.

We’ll start by creating a simple struct by the name of a UIntVec3 that we’re going to store positional information in later. If you know how to, you can extend this struct to allow for different operators to be used on it like Unity3D’s default Vector3, but for now all we need is as below.

Setting Up Voxel Storage

Moving on to our actual chunk class that is going to store the voxels and Generate our collision mesh, the first thing we are going to do is define how the voxel data is actually going to be stored. By making chunk inherit from Monobehaviour, the class that we are now writing can be added to an ‘Empty GameObject’ as a component.

As you can see, the chunk doesn’t use C#’s 3D arrays, and instead uses a single array the size of all the voxels in the chunk. This is because using a 16*16*16 grid means we can use simple bit-shifting to get the index in the array we want from any x, y, and z value we may have. This process can even be reversed, as seen below.

However you’ll notice that this uses two constants that haven’t yet been defined, so we’ll return to the top of the class and add those in, so now the whole class should look as follows.

Now to avoid any confusion in future, we’ll add two simple methods for getting and setting voxels in our grid. We’ll make them public too so that they can be accessed from outside of our class. The two methods will make use of the GetVoxelDataIndex function that we just wrote, but we’ll leave the other function alone for now.

Generating the Mesh

Since we’ve made it so that we can access our voxels quickly and efficiently from any given position, it’s time to write the mesh generating method. Whenever something changes the voxel array, the mesh has to be updated. Seeing as the GetVoxel and SetVoxel methods are both public, so too shall the GenerateMesh method need to be.

The boolean array here is exactly the same size as the voxel array. This is so that we can keep track of what voxels have already been used in creating a mesh so that we don’t re-check them unnecessarily. The reason for using a Dictionary instead of a simple list of Boxes is because C# is a garbage collected language. If new boxes get made directly, then the old box shapes from previous mesh generations have to be destroyed and garbage collected. However, if we just store the information for the box shapes, the old ones can use that information to re-size themselves. You’ll also notices that the UIntVec3 that we created before is now in use too.

Using the method discussed at the beginning of this tutorial, it is now necessary to find a voxel that we can begin expanding a box shape from. We can do this by simply going through our voxel array in a single for loop; skipping over any voxels that have already been tested. Once an untested voxel has been found, it can be marked as tested and, if it contributes to the collision shape (value greater than 0) we can start to create a box shape from it.

Our box shape will now be set up and ready to expand in every direction. The problem is, three different methods are going to be needed to handle the expansion of the box in the three different dimensions. For now, we’ll add the method that are going to be called to the GenerateMesh method, then explore them more in detail. The while loop below ensures that the box keeps spreading in any way it can for as long as it can, ensuring the least boxes possible are made.

Spreading in each different dimension will return whether it succeeded or not. Once canSpreadX, canSpreadY, and canSpreadZ have all been set to false by their respective methods, the while loop will end and the box details will be added to the dictionary. For now we’ll move onto the TrySpread methods, but we’ll be coming back to GenerateMesh for a final piece of code later.

Spreading the Box Shape

The code for spreading in the X, Y, and Z methods are all very similar, but tricky to generalise, so for the purposes of this tutorial we will treat them as three different methods. Copying and pasting one of these methods for the other two and just changing the values you think you need to change is a good way to introduce errors at this point, so be warned.

First things first, we’ll start with spreading in the X dimension. We need to know whether this function should even be able to spread in the X dimension according to its last attempts, so we pass in canSpreadX from before. We also need our array of tested voxels which is going to get changed within the function, so it needs to be passed as a ref parameter. Finally, we need to know where the box shape that’s being expanded started, and how big it currently is. As we’re potentially going to be changing the boxSize this also needs to be a ref parameter. The TrySpreadX function should now look like it does below.

Creating the square along the Y and Z dimensions marks the limits of how the box shape can expand in the X dimension is simply a case of adding the boxSize to the boxStart on both dimensions. Then we can loop through the Y and Z dimensions, but use the X dimensions that we want to expand into for testing. By testing whether the box can actually expand in the X dimension within the for loop, this entire section can be negated if expansion shouldn’t be allowed. The code for that should look like it does below.

Now that we have the X, Y, and Z position of each block that we want to test, we can simply they all contribute to the box shape, but stop the loop if we find any one voxel that doesn’t. A voxel that shouldn’t contribute to the box shape is either one that doesn’t contribute to the collision mesh at all, one that has already been tested and contributed, or one where the X position would actually fall outside the chunk. This should then bring our function to look like this:

Moving on to the next part of the function, canSpreadX will now either be true or false depending on whether the box can expand. If the box is unable to expand, the expansion won’t occur and false will be returned instantly. If it can expand, then we will loop through the Y and Z dimensions the same way that we did before, but instead of testing X, we’re going to mark X as tested instead. This is where we end up using the GetVoxelDataPosition that we wrote near the beginning of this tutorial. Once the loop is complete, the size of the box can be increased by one in the X dimension. Finally, whether the box was able to spread or not can be returned. The finished function should now look as it does below.

You should test you understanding of the above function by writing the TrySpreadX and TrySpreadY functions yourself, however if you find yourself struggling, you can expand the code below and see them there.

Applying the Collision Mesh

By this point in time, all the box shapes that are needed to represent the collision shape of the chunk are stored in the Dictionary created in GenerateMesh. However, now we have to apply it. Going back into Generatemesh, we need to add a single line at the end of it calling SetCollisionMesh and passing the Dictionary as a parameter. GenerateMesh should now look like this:

However, we haven’t actually written any code for SetCollisionMesh, so that’s what we’ll do now. The premise of this new method is that it will take all the information about the box shapes it needs, and turn the old box shapes into the new ones. Any old box shapes that weren’t needed will then be discarded, or if there weren’t enough old box shapes, new ones will be created. To do this, the chunk needs to have a list of all the box shapes that it has active stored as a member variable, so we’ll go back to the top of Chunk and add it in, making the top of the class look like it does below.

Moving on to the actual body of SetCollisionMesh, we can start by creating a foreach loop to go through each element in the Dictionary we passed and, and initialise some of the values that we’re going to need within the loop. The method should now look like this:

At the end of each go round the foreach loop, the colliderIndex should be incremented by one so that the correct box shapes are being changed by information from the Dictionary. This also means that we can test if we actually can be changing existing box shapes or if new ones entirely need to be made. This should result in the SetCollisionMesh method looking as follows.

As Unity3D uses the centre of a box shape to define its position, an extra line will need to be added before the if statement to ensure that the correct position is used. This simply looks like this:

The key of each element in the Dictionary is the bottom left back most position of the box shape, and the value of each element is the box shape’s size. Using this information we can now fill the if statement with the code to both modify and create new box shapes. The method should now look like it does below.

When there are no more old box shapes to be modified, the else statement kicks in and creates an ‘Empty GameObject’, gives it a collider defined by the values in the Dictionary, and makes it a child of the Chunk. It then adds the new box shape to the member variable holding all relevant colliders. However, this doesn’t account for when there was more colliders in the old mesh than was necessary in the new one. To deal with this, we can simply loop backwards through the list of colliders and ‘Destroy’ the unused old ones as Unity3D requires you to do. Once this is done, you can simply remove the whole range from the list storing all the box shapes. Once this is all done, the final form of SetCollisionMesh should look as it does below.

Testing

One final step to ensure you’ve done everything right, we’re gonna add a small ‘Start’ method that will fill our mesh with some garbage data so that we can see mesh generation in action.

Once you’ve done this and added the Chunk component to an ‘Empty GameObject’, you should have something that looks like the image below. If at any point you’ve had any problems with this tutorial, feel free to leave a comment or contact me directly. As for the full source code for a Chunk, it can be downloaded here.