How to display a world made of cubes, part 1.

In a world where everything is made out of cubes (that computer guys like to call voxels!), it is important to be able to display efficiently a lot of them. This post describes how the game Castle Defender does it and why it needs to be optimised!

Part 1/ Data Structure

First of all, before displaying anything, the cubes in the game need to be stored somehow, and depending on what you want to do with them, they will be stored in different ways.

For example, if your game only uses a few cubes (let's say a few thousands cubes) that can be physically animated, their positions, speeds and rotations can be stored individually, so they can be easily updated.

Example of Rigid Physics Simulation from Blender

However, in our game, we are not interested in the tracking of individual voxels (except for the physics engine of the game, but we'll discuss this another day...). Our voxels don't live on their own, they are always part of larger group that describes an object in the game (for example a character or a tree), and they are positioned regularly on a three-dimensional grid.
Thus, it makes sense to store them on a 3D matrix.

A character in its 3D matrix.

The problem with this mode of storage, is that a big part of the stored voxels are "empty-voxels". Thus part of the memory is used to store emptiness! So we want to avoid storing empty voxels as much as much as possible.

Okay, one could argue that nowadays computers are packed with memory anyway, so there is no point in trying to save memory. Indeed the above character is stored on a 16x16x16 grid, which represents 4 kilobytes of memory if each voxel is encoded on a byte. This is very small when compared to the several gigabytes of RAM computers have nowadays!

But what if the totality of the game-word is saved this way? If the player is 16 voxels large, we want the world to be at least 100 times bigger, i.e., 1600 voxels large. Cubed, this correspond to 4096000000 voxels, i.e., 4 gigabytes of memory, which fills up most of the available RAM, if not all of it. Of course, we probably don't need the world to be a thousand of cubes high, so this could be reduced, but what if we want a larger world that can extend as far as the horizon?

One solution could be to use an octree structure, which uses encapsulated hierarchical grids to store voxels only where they are.

Octree Structure of a Stanford bunny!

But sadly, even if this method can save a lot of memory, it makes the algorithms in our game (like iterating over adjacent voxels) much slower. And it's also more difficult to program! As we are not going to use this method in our game, I'm not going to explain it in more details, if you've never came across voxel octrees before, I advise you to type "sparse voxel octree" in Google, and have a look at all the nice videos people have made!

Another solution is to regroup the voxels in chunks that can be streamed in and out of the RAM to the hard-disk, where a lot more space is available (several hundreds of gigabytes).

A chunk of world in Minecraft.

Once on the hard-disk, chunks can be compressed for long term storage. This is the solution chosen in the famous game Minecraft.

In our game, we chose an alternative method for storage after noticing that:

• The ground is going to be mostly flat, so no need to store it as voxels, just use a big square and apply a texture on top of it. And no need to store what's underground either, we are never going to see it!

• Objects in the world are always on the ground and they can only move on the ground (basically, the movements are in 2D!). Each object can be composed of a various number of voxels, but it's usually small (like 4096!).

So why not store the voxels on a "per-object" basis? This way, all the empty space between the trees and the characters does not have to be stored anywhere.
 An object has a position which states where it should be placed in the world. And this position does not have have to be an integer, so the object can move smoothly in between "world-voxels" which wouldn't be possible otherwise.
Also an object can have a rotation, and the voxel can be rotated with it. This wouldn't be possible in standard chunk storage either.
And while we are it, why not allow for different object sizes (corresponding to different voxels sizes). This way a forest can be made out of a single tree model, without too much visual repetition (see one of the previous video below)

Also this allows to create big castles without using too many voxels.

In the end, the voxels are stored on a regular 3D grid, that can be positioned, rotated and resized in any way. Each voxel is encoded on a byte (8 bits) of memory, so there can be 256 different types of voxel (255 if you exclude the empty type). At the minute, only 40 of these states are used, which means there are only 40 different colors, but these colors can be redefined per object. Meaning an object can use a complete different set of colors to an other object.

Everything is voxels!

I can believe how long this post already is!

Okay I'll stop here, in part 2 we'll discuss how to display all these voxels.

Nick.