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...
A grid of voxels containing colours.
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?
From this point on, we assume that you (the reader) know the basics of programming; in concrete terms that would be what bits and bytes are, primitive types like integers, the relation between stack and heap memory and, last of all, pointers/references.
Also, for the purpose of clarity, we will not be using pseudocode.
The following sections are a work-in-progress.
Choosing a Language
In many fields of programming, the choice of language is quite open... even interpreted languages are often acceptable!
But with voxels? Let's do a quick exercise, shall we...- Grab a calculator (we ain't monsters here)!
- Think of how far into the distance you want to 'see', in meters/voxels.
- Type that number into the calculator.
- Double the number once.
- Multiply the number, by itself, twice.
- Look at the result.
- Try this again, from step 2, with some other numbers...
Alternatively, you can use the formula (D*2)³
,
were D
is the initial number from step 2.
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:
- Tightly packing data, via structs and continuous arrays.
- Processing large arrays/lists of numbers at bare-metal speed.
- Creation of complex, nested, but performant, data-structures.
- No copying or cloning of data unless requested.
- Access to graphics hardware acceleration.
- 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;
}
}
The line marked with SCHEME
declares a spatial indexing scheme for us, which defines the order and importance of the x,y,z
axes, but also how to turn coordinates into a usable index. Neat!
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 unwrap
s 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
TODO: Filling a volume via Procedural 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!
Important:
This does not mean that columns of values arranged in a grid, like run-length encoded data might be, are not voxels!
The way that voxels are stored does not matter as long as the grid is indexable.
What are voxels used for?
Many things, but three of them stick out:
Since you are visiting this wiki, you might already know what you intend to use voxels for; if not, please take some time to think about it, otherwise just read on ahead! :)
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?