# 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?

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?