Voxels in Unity: Octrees & Quadtrees
For a project, I was asked to create a simple game that is based on some kind of grid. I decided to stretch that idea to make a project with my own voxels from scratch.
Voxels are a kind of tree-based data structure that takes a region of space, large or small, and represents it with a square- or cube-shaped "node". The node representing that space can store a piece of data. That node can also cut itself in half in each dimension (x, y, and z), and create children nodes that each occupy the portions of its total space, called quadrants in 2D space, or octants in 3D space. The idea of using a tree of nodes is very similar to a binary tree, except each node in this case will have either 4 or 8 children (in 2D and 3D, respectively).
Following some online tutorials, I decided to focus more on my implementation of the quadtrees in 2D space, even though I created the skeleton of my own octrees (shown above). As you can see, the tree gets exponentially more detailed as you add more levels to the tree by subdividing the nodes.
With the quadtrees, I was able to make it sparsely subdivide (shown above). This means it doesn't uniformly subdivide to get a ton of detail everywhere if it doesn't need such high detail in certain spots. I made these quadtrees store integers that map to an array of 4 textures that I use, and then I was able to procedurally create one mesh (through C# code) in Unity to represent the whole chunk.
The project came out to be over 800 lines of C# code (shown above on the left), which I counted with a small console program I made! These scripts included the Octree and Quadtree as well as their respective Node classes, as well as generating a populated quadtree from a noise texture, generating the mesh to graphically see it.
I used vertex colors on the mesh to let the graphics side of things know what texture to render where. This is partially seen above in the Cg/HLSL graphics code above on the right, on line 32 where I used the "COLOR" semantic.
Because the colors are 32-bits by standard (8 bits per channel, 4 channels total for RGBA), I was able to most simply represent up to 4 textures on the mesh. The RGBA color for transparent red (1, 0, 0, 0) represented the first texture, (0, 1, 0, 0) represented the second texture, and so on. This means that (0.5, 0.5, 0, 0) could represent a perfectly halfway blend between the first and second textures.
Because the colors are 32-bits by standard (8 bits per channel, 4 channels total for RGBA), I was able to most simply represent up to 4 textures on the mesh. The RGBA color for transparent red (1, 0, 0, 0) represented the first texture, (0, 1, 0, 0) represented the second texture, and so on. This means that (0.5, 0.5, 0, 0) could represent a perfectly halfway blend between the first and second textures.
The final part of the project for me was making the quadtree interactable outside of the Unity editor -- in a build. Thus, I finalized the project by adding support for input in the game view, added some instructional/informative UI text, and got it up and running fairly quickly!
These 2D voxels were later expanded to use Unity editor tooling, along with Marching Squares to smooth out the resulting mesh.
Finally, the project was upgraded to support 3D, Marching Cubes, and notably make use of parallelism on the GPU and asynchronous requests to update the Mesh to improve responsiveness.
This was done using Unity Compute Shaders and C# Tasks (from the Task Parallel Library (TPL)).
Huge thanks to The World of Zero's tutorial series on voxel terrains in Unity!
