Today’s subject is collision. There are a number of ways one could setup a collision and physics system with voxel data. I could build my own full physics solution, but I really don’t need (or want) to. Unity has its own physics system; the question is then how to interface with it.

Like last time, we’re talking about a single cubic chunk of voxel data. I already have the mesh data used to display the chunk, so Unity’s Mesh Colliders could turn that mesh data into collision, but Mesh Colliders have some pretty severe performance issues when used in bulk. Other developers have also mentioned that the procedural generation of a Mesh Collider can take a long time. I want to have effectively limitless terrain with good draw distances, and I also want my terrain chunks to react to user changes quickly, so Mesh Colliders for terrain are right out.

That leaves building a collision set to represent the voxel data out of collider primitives (box, sphere, and capsule colliders). One option is to place one Box Collider for every cube in the chunk. This results in several thousand colliders however, and we can do better.

An Illustration of Octrees

I mentioned this in my last post, but this voxel terrain is being stored in octrees, which is a data structure that can store eight sub-versions of itself. We can use this data structure to generate a much more efficient collection of Box Colliders. For simplicity’s sake, let’s look at the cube without the mesh, just viewing the Box Collider borders:

This Box Collider represents the root octree of the voxel data. An octree knows its own center and size (the distance between opposite faces) and also holds onto a piece of voxel data.

Now, say we want to remove the top right corner. To do this, the octree constructs eight children, each positioned in a corner and with a copy of the original octree’s block data. Then, the octree in the top right is told that it is empty. At this point, the series of Box Colliders are regenerated:

First Division

Second Division

Third Division

This operation can be repeated until we hit the minimum size of the octree structure. Since the octree uses integers for size and positioning, that value is 1. The smallest block I want is a half-meter, so the Mesh and Collision Generators are set to translate a “1” in octree space to a “0.5” in world space, but this is freely adjustable.

Generating Colliders

The actual process of generating the colliders is quite simple. You just need to loop through the octrees and place a Box Collider where the solid octrees are. This dramatically cuts down on the number of colliders used per chunk when compared to simply placing a collider for every block.

Fourth Division

I’ve broken this process up into two discrete operations: the object that loops through the octrees (called a Crawler) and the object that translates this information into the actual Unity objects (the “Generator”). The CollisionGenerator class has no idea about the octree or how the data is stored. It only requires a VolumeCrawler interface. Meanwhile, the OctreeVolumeCrawler class implements that VolumeCrawler interface and provides a sequence of volumes defined by their minimum and maximum points.

This separation is an important programming pattern that means I can, for example, decide to completely change how the voxel data is held in memory. So long as I write a class that implements the VolumeCrawler interface that can handle the translation of the data, the CollisionGenerator will continue to work perfectly. Having each process segmented out into its own class that is only loosely connected to others makes code more reusable and easier to understand.

Some Code

Let’s now take a look at the actual bits of code that are being used here (I apologize in advance to those who prefer their braces on individual lines). First up is the VolumeCrawler interface:

public interface FoGVolumeCrawler {
	/// <summary>
	/// Loads in the next volume
	/// </summary>
	/// <returns>If there is data available</returns>
	bool Next();

	/// <summary>
	/// Resets the crawler information to the start
	/// </summary>
	void Reset();

	/// <summary>
	/// The minimum corner of the volume
	/// </summary>
	FoGPosition min { get; }

	/// <summary>
	/// The maximum corner of the volume
	/// </summary>
	FoGPosition max { get; }
}

In developing this framework, I’ve been keeping it as separate from Unity as possible. That meant, for example, making my own Position struct consisting of X, Y, and Z integers. Next, let’s take a look at the OctreeVolumeCrawler. I won’t include the WorldOctree code as it’s exceptionally long, but I’ve added comments to the appropriate function calls.

public class OctreeVolumeCrawler : VolumeCrawler {

	private WorldOctree masterOctree;

	private IList<WorldOctree> octrees;
	private int index;

	private Position _min;
	private Position _max;

	public OctreeVolumeCrawler(WorldOctree octree) {
		masterOctree = octree;
		Reset();
	}

	public bool Next() {
		if (octrees == null) {
			octrees = new List<WorldOctree>();
			// WorldOctree.Solids() returns a list of all solid octrees in the hierarchy.
			octrees = masterOctree.Solids();
		}

		if (index < octrees.Count) {
			// WorldOctree.center is the center Position of the Octree.
			Position center = octrees[index].center;

			// WorldOctree.size is the width of the Octree between two opposite faces.
			int halfSize = octrees[index].size / 2;
				if (!octrees[index].IsLeaf()) {
				_min = center - halfSize;
				_max = center + halfSize;
			}
			else {
				_min = center;
				_max = center + 1;
			}


			index++;
			return true;
		}

		return false;
	}

	public void Reset() {
		octrees = null;
		index = 0;
	}

	public Position min {
		get {
			return _min;
		}
	}

	public Position max {
		get {
			return _max;
		}
	}
}

Finally, we can look at the CollisionGenerator itself.

public class CollisionGenerator {

	private float blockSize;

	public CollisionGenerator(float blockSize) {
		this.blockSize = blockSize;
	}

	public void Generate(VolumeCrawler crawler, GameObject chunkRoot) {
		int i = 0;
		float startTime = Time.realtimeSinceStartup;

		// The existing box colliders
		BoxCollider[] boxColliders = chunkRoot.GetComponents<BoxCollider>();
		// The index of the existing box colliders
		int index = 0;

		while (crawler.Next()) {
			Vector3 min = new Vector3(crawler.min.x, crawler.min.y, crawler.min.z) * blockSize;
			Vector3 max = new Vector3(crawler.max.x, crawler.max.y, crawler.max.z) * blockSize;

			BoxCollider collider = null;
			if (index < boxColliders.Length) {
				// Retrofit an existing collider
				collider = boxColliders[index];
				index++;
			}
			else {
				// Add a new one once there are no more existing ones.
				collider = chunkRoot.AddComponent<BoxCollider>();
			}

			collider.center = (min + max) / 2;
			collider.size = max - min;

			i++;
		}

		// Remove any old box colliders
		while (index < boxColliders.Length) {
			Object.Destroy(boxColliders[index]);
			index++;
		}

		float timeSpent = Time.realtimeSinceStartup - startTime;
		Debug.Log(i + " collision volumes created in " + timeSpent + " seconds");
	}
}

There are two important things to mention about this class. The first is that it attempts to reuse any existing BoxColliders attached to the GameObject. This is a major time saver, as generally any single action is only going to add or remove a handful of colliders. Reusing the ones that are already there means we don’t get hit trying to Destroy() and instantiate new ones every time we want to update a chunk. With this very simple optimization, I was able to cut the time it takes to regenerate the collision by nearly a factor of 10. Time is very important in this process. Any code that interacts with Unity has to play on the main thread, and an operation that takes a long time in that thread will make the game appear to “hang” until the process is finished. The second thing to note is that this collision is regenerated during FixedUpdate() on the Unity side. I found that this fixed a problem of sometimes falling through the collision while it was being regenerated.

I hope that was informative. If you have any questions, leave a comment, and I will do my best to answer. The next step in development is building outwards and creating the structures to manage the several hundred chunks that will make up the player’s view of the world.