The Anatomy of Voxels in Imagine Nations
We’ve already discussed the generation thought process in the new year’s post. This will focus on how we can take the data from generation and turn it into blocks that define the terrain including the ability to interact with it. I must warn you, there will be *a little* bit of math here, and it will get a little technical, but nothing crazy.
The beauty of a voxel system is that many systems (such as Physics) are very fast due to a few simple-ish math formulas. Since our “chunks” of terrain are a set size of 32m^3 (with each block being 1m^3), and the planet face is also a defined size (max size now of 131072 x 8192 x 131072 blocks), we can very easily determine a few key pieces of information from two simple formulas. By taking any position in the world via an x/y/z coordinate (let’s say 1024, 512, 1024), we can immediately determine which chunk you’re in *and* the block you’re standing in. Dividing the coordinate by the chunk size of 32 converts the world space coordinate to “chunk” space (which puts the position into chunk 32, 16, 32). Then modulus of the coordinate (effectively getting back the remainder when doing division) by the chunk size of 32 converts the world space coordinate to “block” space (which puts the position into block 0, 0, 0 within the chunk).
We use these two formulas in everything within the game. We can look downwards when applying gravity to find whether a solid block is underneath you. We can hook it to the crosshairs when digging and placing blocks. Outside of dynamic objects (say other characters) which require some sort of physics calculations, the entire terrain can be interacted with nearly instantly. It saves us from some very costly physics which can quickly limit the amount of content in a game such as IN.
At the core of our voxel engine is PlanetFace. This system basically
acts as the composer to our voxel orchestra. Whether you want to have the game show a 32m^3 chunk of terrain, or are busy dropping down blocks to build your masterpiece, PlanetFace is handling the incoming calls and getting them to where they need to go.
Internally, PlanetFace is composed of a way to send in requests for chunks/voxels you need to interact with, a cache system of chunks to ensure memory usage is as low as possible at all times, the planet’s random number generator (hereby referenced as RNG) used for any procedural calculations, and the base data of the planet including the size (in blocks and chunks), the seed, and the initial spawn point (which is set via the town spawned with the same race as the player).
This is a new system currently being experimented on, but derives from a technique called “MegaTexturing” used in some games (see: En.wikipedia.org). Not to get too detailed here, but the concept of MegaTexture is simple: with the increasing detail of objects in games, you have a lot more textures on each object, which means a lot more calls to your GPU.
Calls to the GPU are generally bad as it takes a lot of time (latency) going from the CPU to the GPU. As such, games look to reduce the amount of “draw calls” to the GPU. MegaTexture accomplishes this by combining all the textures used in the game into a mega texture (aha, that’s why the name matters) and sending it once. Then each object simply owns a “page” of that texture on the GPU side and requests it when applicable. This obviously reduces the amount of calls at the cost of more GPU memory being needed for all the texture data at once.How does this apply to SuperChunk? We need to be able to theoretically support a player visiting every single chunk and potentially designing something on them. Just as an example right now, it would cost us 281,474,976,710,656 bytes of data (ignoring the game’s overhead) to have the entire planet in memory. The number is obviously WAY larger than any system’s memory to date (both RAM and hard disk). So we need both a super efficient way to keep memory usage down while also a way to compress 281TB down to a reasonable size (say something like 1-3GB for an entire planet face).SuperChunk accomplishes this for us in two ways since it is the ringleader for all generation (through the layers systems discussed in the new year’s post). First off, as with MegaTexture, we have very efficient systems between SuperChunk coupled with the cache in PlanetFace to ensure that only the chunks we absolutely need are in memory. Generally this comes down to the chunks that have been recently requested via the player and NPCs for physics/pathfinding mixed with a predictive algorithm for chunks that may be needed soon. The amount of chunks that would need to be in memory is minimal, so memory stays low at all times. As most chunks will only need to be rendered, once they have finished their pipeline and show up on the screen, their data can be removed until such time as an object requests it.
Second, SuperChunk uses a very aggressive compression technique to keep the data in the file system (our GPU) to as small as possible after it is generated. I.E. while the pure voxel data would be 281TB, we will have a large amount of chunks that are pure air, or purely solid.
In either case, SuperChunk can represent either as a single bit, combining 8 of each into 1 byte. If 90% of the planet face were either (and the amount would probably be higher than that, with only the surface being contoured and cave systems loosely spread underground), we just reduced the file system usage down to 28TB. Still huge, but we’re getting there.
We now run the individual page data (the individual 32^3 chunks of voxels) through “run length encoding” which basically looks at how many of the same type of block runs in sequence. This stage also uses some pattern recognition to further reduce the size. We can then simply say “there are 15000 air blocks in sequence” which reduces what would’ve cost us 30kb individually into 4 bytes. Generally this results in roughly 10% of the data size with how we generate, putting us now at 2.8TB.
Finally, we run the overall region data (the 32^3 areas of pages/chunks) through run length encoding, pattern recognition, and use traditional compression (such as the 7zip engine) of the final output data. The end goal being roughly in the 1-3GB range as mentioned above.Each page is given instructions on how to quickly put their data back together, and a lot of this data is either cached in memory for most used chunks, or can be predicted based on the movement and actions of dynamic objects (i.e. if you are running forward, we will have the next
Overall, this system is in a very experimental stage. The compression techniques will make or break it, but we’re pretty confident we’ll have the system running just fine. Previously, the overall system functioned around only loading chunks as they are requested and then immediately writing each chunk out (or combining them into regions). The problem we foresaw with this approach is that at some point the entire planet face can be colonized, and we need a system that
can guarantee that memory and hard disk can support it appropriately no matter what the player/cultures do.
As mentioned above, this system used to be the core. It would determine which chunks were in the camera’s range, generate them, and render them to the screen. ChunkSystem would also unload any chunks that fell outside the camera’s range. With SuperChunk moving in, it has been demoted to handling 3 out of the 4. While we understand ChunkSystem’s complaints on losing some of its responsibility, we have reminded it that there are at least 8 systems that have been completely removed from the code base. The complaints quickly ended.
Coming back to reality…ChunkSystem acts as the eyes of the game. It uses the camera’s position, and a predefined radius around it (which can be set by the player as near, default, and far). As we can quickly convert the camera’s position inside Unity to chunk and block space
(using the math earlier in the post), its a very rapid process to find all the chunks that we need to render directly around the player. The system starts at the chunk the camera is in, and moves out 1 radius per frame until it hits the max radius. For each chunk in this area, it sends a request to PlanetFace that we need to get this data and render it. Whenever the camera moves to a new chunk, the process repeats itself.
At the same time, ChunkSystem recognizes during a chunk boundary change that any chunks that have fallen outside the range of the camera need to be unloaded. These are properly cleaned out of PlanetFace (if applicable), and their data is removed from memory (if applicable) within SuperChunk. Generally any chunks removed in ChunkSystem are only being rendered and only their mesh data needs to be removed within Unity.
Finally, when SuperChunk has fully generated a particular page and that chunk has been requested, it is combined with a chunk object inside PlanetFace and ChunkSystem uses this data to create the mesh and material necessary to see the terrain within the game.
The Voxel Trifecta
This delicate dance between PlanetFace, SuperChunk, and ChunkSystem allows Imagine Nations to build a rather large planet (and ultimately is the precursor to supporting multiple planets once Space becomes a reality) that can still be kept within the limitations of today’s hardware. Coupled with an LOD system to render all the terrain outside the chunk distance (which SuperChunk plays a big part in as well but is for another day), and the design of the planets ultimately being “flat” (Static.ddmcdn.com
being the ultimate goal more or less which allows you to see straight across the entire face you’re on versus the 3 mile limit due to Earth’s curvature) with the monstrous mountain ranges at the edge, and we’re expecting a very unique atmosphere with each of our planets. And this
is outside the dynamic of the cultures, and how you as the player fit into it.
If anyone would like to know more details about the voxel system we’re building, feel free to post below or reach out to me directly and I can provide some pointers. After 2.5 years of experimentation with voxels (of which the references online are either incomplete or few and
far between), once we’re confident the system works as intended, I’d like to post a more permanent blog somewhere for any aspiring voxel developers which will break down a lot of what we did in all the technical details so you can at least have a solid base for your game.
– The Imagine Nations Team