Voxel Physics Engine

Solo 24 weeks C++ (Custom Engine)

For a technical explanation of the physics go to Physics Explained →

Inspiration

For a school project we had to make a custom engine feature. I wanted to work on a physics project because it has always been interesting to me. I also wanted to try something different than the norm, so I remembered Teardown, which has voxel physics with destruction, and I really wanted to recreate it. Although it didn’t really seem reasonable to get a result close to the physics in Teardown, I still wanted to see how close I could get. So I started this project with the goal of making 3D box physics, so no interesting shapes, just boxes. I worked on this project for a bit more than half a year, and ended up with a result I’m very happy with.

Physics

When I started this project, I already had the goal in mind of creating voxel physics, but because it was my first 3D physics project I started out by working on 3D physics with OBBs (Oriented Bounding Boxes). This step was crucial for me to learn more about different types of collision detection and resolution methods. I started off using a Direct Impulse Resolution method, but I could not get a stable simulation. That was until I found out about Sequential Impulses. Thanks to Box2D and their excellent documentation, and some other sources, I was able to quickly implement Sequential Impulses for my OBBs.

After getting physics in an acceptable state for OBBs, I changed the collision detection and contact generation to support voxel objects. The OBBs are still used for the early out, but not for creating contacts. The contacts are generated per voxel. It didn’t take me long to implement this, but using a brute force approach has horrible performance and a few other issues. Another new problem that was introduced was multiple voxel penetration, which I solved by storing a 5-bit lookup number for the normal so it would not get inverted. The other 3 bits were used to determine what type of voxel it was, which helps reduce the number of voxel-to-voxel checks. So the voxel physics data is only 1 byte per voxel.

With some optimizations, which include basic sleep states, SAT early out, and only checking overlapping areas and voxel types, my proof of concept looked like this.

Kudzu

Because of the success of my voxel physics proof of concept, we got the chance to build a game engine from my project. So the Kudzu engine was created. This was a group project with multiple engine, tools, graphics, and gameplay programmers. We worked with a total of 7 people on this engine. I continued to add features and performance optimizations to my physics while integrating it into Kudzu. These features include collision layers, triggers, callbacks, scripting interface, and destruction. Later in the project I also helped with creating the demo game.

Destruction

Part of my responsibilities for Kudzu was making functional real-time destruction, with the inspiration being Teardown again. To get the destruction working, a few things needed to happen. I had to find if and where objects separate when a voxel is destroyed, create a new object for each separate piece, and recalculate the physics data for each given piece. Separating the objects and recalculating the physics data was pretty simple, but effectively and quickly finding where voxel objects separate was quite difficult. I did this by doing a flood fill over the whole object across multiple frames. This works well because you can define how much performance you want to put into destruction, at the cost of the object having a delayed reaction. For most objects this is unnoticeable (it only takes 1 to 3 frames), but this approach doesn’t scale linearly. For objects that are, for example, 256^3 in size, it can take a noticeable amount of time (20 to 40 frames). This can still be improved a lot, but the current approach works functionally.

After 8 weeks of working on Kudzu, we got the opportunity to make a full game with the engine. This game became Zentera. This game showed what our engine is capable of. During the development of Zentera, a lot of effort still went into developing the engine.