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.

Voxtric – Update 4: Better physics simulation

Texture Arrays

There are several key changes in the latest update to Voxtric to be discussed starting with the new way the rendering blocks is handled. Instead of using a texture atlas as I had been before and storing the texture position of each block in an array to be accessed by block index, I now use texture arrays. This means I still only need to to one texture binding and only use one texture per mesh, but the way it is accessed is now completely different. It is literally like having an array of textures that can be used. I don’t have to store a texture position at all, and instead just use the block ID of a voxel to access the right index of the texture array which the fragment shader can then sample.

There are several benefits to handling my rendering of meshes this way compared against using a texture atlas. The first major one is that it now means I can have individual images for each texture that can be named specifically for the block that they represent. The second major in game benefit is that texel bleeding as can be seen in my previous videos of Voxtric is no longer an issue. The pixels in the texture surrounding the block the fragment shader needs to sample will not be taken into account at different mipmap levels.

Frustum Culling

Another key change that I have made to rendering is to implement frustum culling. There is no doubt that this is an absolutely essential part of any game engine, but initially I had not done it as my test scenes didn’t need it to run. Now that I have a better grasp of the Bullet physics engine and the key underlying structure of what I am trying to accomplish with Voxtric is in, I decided now was the time to go back and re-do the rendering pipe-line.

Physics Improvements

The final important point that has changed is that the centre of mass and total mass of the RegionCollections are no longer broken. Each block is defined in a .csv file containing its ID, name, if it’s visible, if it’s solid, and of course its mass. When each block is checked in the voxel data for building a mesh, it’s position compared to the middle position the data is multiplied by it’s mass which is then added to a total position.

At the end of the mesh generation the total is divided by the number of voxels stored. This position is then considered to be the centre of mass. The average of all the different mesh position centres is then used to decide the RegionCollection centre of mass. As can be seen in the video above, it is a massive improvement when compared to my previous videos.

Voxtric – Update 3: Integrity Splitting

This post and the video above are short due to the single change that took place in Voxtric for this post to be made, but the change itself is a big one. After a fairly large amount of work I managed to get algorithm for checking for and splitting off of disconnected collections of voxel data.

Method (Has since been far and away improved)

It works by storing a series of points around each block that is removed at once (6 for each block removed), and then checking each point for a solid block at that positing, throwing the point away if there is no solid block at the position. Doing it this way means that large areas of blocks are able to be removed at once and the rest of the algorithm as is about to be explained will still work.

A DataSplitFinder is then created at each point which stores a std::vector of positions found, an std::map of the positions found in the most recent round of checks (explained in a moment), and a std::vector of the positions found in the previous round of checks. It also stores the total number of positions found.

Each DataSplitFinder then performs a breadth first search for the other finders around it. When one is encountered, they are merged together and the process continues. If a finder cannot continue its breadth first search as there is nowhere else for it to search, it means that this finder has detected a collection of voxel data that is no long connected to the main body of voxel data. A new RegionCollection is then created and the voxel data that has been identified as not connected is copied over to the new RegionCollection. This process continues until there is only one finder left as all active finders will have been merged together of removed when copying data.

As it is faster to copy the least data possible from a large voxel data collection, the DataSplitFinder with the least voxel positions found is the one that performs each round of its search more often than the others. This is because, in the case that a split has occurred, in places where the finders can reach each other they will quickly merge into one finder and each round will spread over a much larger area. The smaller section though will have the constraints of being on a boundary of voxel data and will have merged with fewer if any finders.

As this smaller section is the bit we want to copy out, it is the one we perform the breadth first search operation on until it is either confirmed to show a split in the voxel data, it finally meets up with the other finders, or the number of positions it holds becomes more than that of any one of the other active finders. In the latter case, the exact same process is repeated, just with whatever finder now has the least voxel data positions stored.

Voxtric – Update 2: Improving mesh generation

There were only two changes to Voxtric that can be seen in the video above, but they were both major changes that make Voxtric so much easier to work with.

Debugging Tools

By the time I had got to the stage that I was at with the previous video, I had hardly implemented any debugging tools. I very, very quickly learned how important debugging tools were when trying to get the Bullet physics engine working in the way that I wanted it to, and so I dedicated a large amount of time to implementing several. In doing so I ended up implementing a way of rendering text to the screen which I had not intended to do at that point originally, though it has made my life much easier now that it has been done.

Proper Multi-threading

The second major change was, as the title suggests, the changes to the way that mesh generation is handled. Much like in the original prototype, I wanted to be able to have any mesh generation handled in a different thread so that lots of editing of voxels would not impact the performance of Voxtric. Unlike in the prototype, I wanted to make sure it was done properly.

Watching the original video will show that the changing of voxel data was done in the main thread with thread pools being used to both generate a mesh and test to see if bodies of voxels had disconnected from each other. Of course this meant it was riddled with race conditions and would mean often disconnected areas would not be recognised as such. I set out to make sure that literally everything to do with editing voxels in Voxtric was done in a single thread to avoid any race conditions, but outside of the main thread to avoid any performance impacts.

At this point disconnecting bodies of voxels was not implemented, but by ensuring when I did come to implement it there wouldn’t shouldn’t be any multi-threading issues it meant that when I did come to implement the feature, it would be far more hassle free.

Voxtric – Update 1: A new game engine

The above video is the first video that I released just documenting where I was up to with Voxtric. This is a little while after the prototype as it took me a fairly large amount of time to rap my mind around OpenGL, Bullet (physics library) and the maths involved in games. I had always been aware that a game engine was a very different undertaking to the production of a game and that Unity3D was doing all the heavy lifting for me, but I never truly appreciated it until this point.

By this point, I had got a very basic rendering pipe-line with OpenGL 3 going and procedural mesh generation to go with it so that the voxel data could be represented. I had the most basic implementation of lighting to give any objects in the scene a bit of definition, but otherwise it was all incredibly basic, and a long shot from what I had working back in Unity3D. That said, it was also working much faster at this stage than it had at the same stage in Unity3D, so it was certainly showing promising results.

Obviously there were lots of issues, a fairly major crash that can be seen in the video, and some fairly poor design decisions, but this was my first foray into creating a game engine, so this was all to be expected. Fast forward to the time of writing and the vast majority of these issues have either been dealt with, or are in the process of being dealt with. I have come to terms with the fact that it’s easy to identify an endless list of things that need to be done, the hard bit is the prioritisation.

Voxtric – Update 0: Initial Showcase

This first post for the development of Voxtric is made quite some time after the initial posting of the video shown above, so the detail may be lighter than in later posts which will be made upon completion of the features talked about in them.

As Unity3D is an exceptional game engine when it comes to speedy development, so I decided it would be a safe bet to prototype my initial ideas in it. At one stage I was going to go ahead and try to make a game using Unity3D in conjunction with the early prototype seen above, but unfortunately being fairly good at everything meant that Unity3D excels in nothing. Subsequently I decided to discontinue development of this prototype just weeks after initially posting this video. An example of where it failed to meet potential project needs is in the handling of rigid bodies where meshes without closed edges would cause the engine to throw errors regardless of the context that they were used in.

Language Choices

Another reason I had intended to try and make this prototype into something more than just a prototype is that I had used Unity3D for about a year before, and had become fairly comfortable with C# as a programming language. However two changes occurred to make me disregard that fact. The first is that the course I wanted to take at the time if I went to university (Northumbria which I shall be attending September 2015) would have me programming in C++.

I came to the conclusion that getting ahead and learning C++ before the course began was probably a good idea anyway. Secondly, research suggested that the games industry relied heavily on C++ for its underlying technology due to its high performance capabilities when in the right hands. Again to get ahead of the curve, I decided that learning C++ was worth the temporary reduction in productivity whilst I acclimatised to the language considering the potential future benefit.

Improved Voxel Storage

In the video above it can be seen that Voxtric had many of the features that it has at the time of writing now, but just less well implemented. For example, voxel data used to be stored in an jagged array of 16*16*16 blocks per voxel, which of course lead to memory fragmentation. Now voxel data is stored in a single array with a size of 4096, and a voxel is accessed through a simple equation to find the right index in the array from 3 co-ordinates as seen in the code snippet below.

There are lots of small optimisations like this that make a big overall difference to both the speed and memory consumption of Voxtric that weren’t in the prototype such as storing all block data in a single 2 byte number and using bit shifting to get different elements of information from the block.