Introduction

This is a basic introduction to what voxels are, what they are not and their general use cases.

What is a voxel in theory?

To quote Wikipedia:

In 3D computer graphics, a voxel represents a value on a regular grid in three-dimensional space.

— Wikipedia on Voxels

Since most people don't have a good understanding/foundation of math (in this case: linear algebra), let's explain this piece by piece.

A voxel represents a value...

An individual voxel can be absolutely anything. Yes, anything.

• Numerical things, like density, color and direction.
• Labelled things such as states, types, names, etc. etc.
• Structured things: text, an item, or some other object.
• Another grid of voxels 'inside' each voxel!

And of all this is without taking the encoding, be it in-memory or on-disk, into account.

See the practice section for more details on this.

...on a regular grid...

Taking the definition from Wikipedia...

A regular grid is a tessellation of n-dimensional Euclidean space by congruent parallelotopes (e.g. bricks). [...]

...and breaking it down:

• Tessellation
  The grid is formed by dividing space into cells.
• n-dimensional
  The grid has at least one dimension.
  But since we are in 3D space, at least three.
• Euclidian space
  The axes are at 90° degree angles to each other, everywhere.
• Congruent
  Every cell in the grid has exactly the same shape.
• Parallelotopes
  • The cells are shaped like boxes.
  • Each opposing side has the same area/shape.
  • Their edges in a given axis are parallel.

Now you might think that the cells of the grid are the voxels, but that is not the case! The voxels are theoretically on the corners where the cells meet, they are neither inside the cells nor are they the cells; a voxel is a point sample, not a little cube.

In practice you will usually notice this when either rounding or off-by-one errors occur.

...in three-dimensional space.

• There must be at least three-dimensions, so as to form a volume.
• Adding more spatial dimensions turns the voxels hyper-volumetric,
  making them hypervoxels (there is no shorthand or acronym for this).
• Adding a time-dimension turns them into temporal voxels,
  making them toxels.

That is the definition of a voxel; and if that all sounded complicated... well that's because it is! Mathematics are like that sometimes.

Let us continue with voxels in practice...

What is a voxel in practice?

As noted in the theory section, a voxel can be anything; the only limit is your imagination... and the amount of memory and disk-space you have! Speaking of which, how are voxels represented in practice?

Choosing a Language

In many fields of programming, the choice of language is quite open... even interpreted languages are often acceptable!

1. Grab a calculator (we ain't monsters here)!
2. Think of how far into the distance you want to 'see', in meters/voxels.
3. Type that number into the calculator.
4. Double the number once.
5. Multiply the number, by itself, twice.
6. Look at the result.
7. Try this again, from step 2, with some other numbers...

Unless you keep the range of the active volume very small (on the order of 16³ to 256³), you will quickly realize that there is a scaling problem: Increasing the size of the volume will consume cubically more and more memory, making computations horrendously expensive.

As such, there are some rather strong requirements when choosing a language:

1. Tightly packing data, via structs and continuous arrays.
2. Processing large arrays/lists of numbers at bare-metal speed.
3. Creation of complex, nested, but performant, data-structures.
4. No copying or cloning of data unless requested.
5. Access to graphics hardware acceleration.
6. Multithreading.

This effectively cuts out all languages that are interpreted instead of compiled, such as Python, JavaScript, PHP, Lua, Perl and Ruby; unless you are fine with a very small volume size, using these languages is not recommended.

Some Just-In-Time Compiled languages may be fine, such as Java and C#, but we wouldn't recommended using them: You will inevitably run into various issues, mostly related to memory management and cache coherency... forcing you to step out of their 'normal' usage, straight into unsafe and often weird, territory.

While Chunking and various acceleration structures help to alleviate the issues posed by interpreted and JIT'd languages somewhat, adding more features makes memory usage and bandwidth become harder and harder to manage... you need the ability to manage memory on both fine and large scales.

Unfortunately, all of this restricts our choice to 'system-level' languages, such as C, C++, Rust, Zig, Go and so on.

For this guide we will be using basic Rust; you do not need to know how lifetimes work for now.

Basic Storage

For a start, let's assume that our voxels store... nothing.

/// This represents a single voxel sample/instance.
type Voxel = (); // using the empty 'unit type' for now.

Since a voxel outside a grid is, by definition, not a voxel, we will have to put it into a grid of voxels...

/// A finite grid of voxels.
pub struct VoxelGrid {
  // ???
}

...but how exactly do we do that?

At first, you might try to use a 3D array; let's say of size 16³:

/// The size of our grid along any axis.
pub const GRID_SIZE: usize = 16;

/// A finite grid of `GRID_SIZE³` voxels.
pub struct VoxelGrid {
  values: [[[Voxel; GRID_SIZE]; GRID_SIZE]; GRID_SIZE];
  // Well ain't that nice to look at, eh?
}

Now accessing it is pretty simple:

// Create the volume, filled with 'nothing'...
let mut volume = VoxelGrid {
  values: [[[Voxel; GRID_SIZE]; GRID_SIZE]; GRID_SIZE]
};

// Have some coordinates...
let (x,y,z) = (0, 1, 2);

// Get a voxel:
let v = volume.values[x][y][z];

// Set a voxel:
*volume.values[x][y][z] = v;

But what happens if x, y or z go outside the volume? We might get an error and crash!

Let's prevent that by defining accessor functions and then only use these:

impl VoxelGrid {
  pub fn get(&self, x: u32, y: u32, z: u32) -> Option<Voxel> {
    self.values.get(x)?.get(y)?.get(z)
  }
  
  pub fn set(&self, x: u32, y: u32, z: u32, v: Voxel) -> Option<()> {
    *self.values.get_mut(x)?.get_mut(y)?.get_mut(z) = v;
  }
}

Alas, this shows us one of three annoyances with using 3D arrays:

• Accessing elements always requires us to 'jump' trough two levels of indirection.
• Iterating/looping over our voxels requires three nested loops, which is a pain to write.
• Creating and filling a 3D array is, unsurprisingly, quite messy.

As such, we will now go ahead and make our array flat, turning it one-dimensional!

pub struct VoxelGrid {
  values: [Voxel; GRID_SIZE * GRID_SIZE * GRID_SIZE];
}

Of course, we will now have to do the bound-checks by ourselves, but as long as we use the correct equality operators, there really is nothing to it!

impl VoxelGrid {
  pub fn get(&self, x: u32, y: u32, z: u32) -> Option<Voxel> {
    if x < 0 || x >= GRID_SIZE {return None}
    if y < 0 || y >= GRID_SIZE {return None}
    if z < 0 || z >= GRID_SIZE {return None}
    self.values[ /* ??? */] // uuuuh...?
  }
}

I suppose a function that turns x,y,z into an index is also needed: an index function! Since it depends on the bounds-check to work correctly, let's move that there too.

impl VoxelGrid {
  pub fn index(&self, x: u32, y: u32, z: u32) -> Option<usize> {
    if x < 0 || x >= GRID_SIZE {return None} // 0 ⋯ GRID_SIZE-1
    if y < 0 || y >= GRID_SIZE {return None} // 0 ⋯ GRID_SIZE-1
    if z < 0 || z >= GRID_SIZE {return None} // 0 ⋯ GRID_SIZE-1
    Some(x + y*16 + z*16*16) // SCHEME
  }
  
  pub fn get(&self, x: u32, y: u32, z: u32) -> Option<Voxel> {
    self.values[ self.index(x,y,z)? ] // yay!
  }
  
  pub fn set(&self, x: u32, y: u32, z: u32, v: Voxel) -> Option<()> {
    *self.values[ self.index(x,y,z)? ] = v;
  }
}

And so our example becomes this:

// Create the volume... somehow.
let mut volume = VoxelGrid { /* ??? */ };

// Have some coordinates...
let (x,y,z) = (/**/, /**/, /**/);

// Get a voxel:
let v = volume.get(x, y, z).unwrap();

// Set a voxel:
volume.set(x, y, z, v).unwrap();

Handling errors is outside the scope of this guide, so do note that the unwraps in the example will, if the coordinates are ever out of bounds, crash our program; but at least you'll know where!

But how to we fill it?

Basic Generation

What is not a voxel?

If values are generated in a two-dimensional grid and expanded into a third dimension on-demand, such as during rendering, you are not using voxels.

That's just a plain old heightmap pretending to be voxels!

What are voxels used for?

Many things, but three of them stick out:

• Videogames
• Simulation
• Medicine

For making art made of voxels, we highly recommend checking out MagicaVoxel, which is currently considered to be the best voxel-editor you can get; it's completely free!
Perhaps share your creation?