vercidium

Real-Time Voxelisation

Added 2025-07-14 23:49:42 +0000 UTC

Since audio raytracing is performed against voxels, I need a way to convert the 3D terrain, meshes and shapes in your games to voxels.

I had this working for my Raytraced Audio video:

This worked great, but it was slow. Each frame I was removing all the voxels, then converting each triangle in each model to voxels. The performance didn't matter since I wasn't rendering the video in real time, but for your games it needs to be faster.

My approach interpolated between each of the 3 positions in the triangle, placing voxels evenly throughout. This worked, but it was overkill and placed a lot of voxels on top of each other.

Approach 2

The 2nd approach involved using a 2D triangle rasteriser, with some tweaks to make it work with voxels. I followed Jason Tsorlini's tutorial on triangle rasterisation, using edge functions to place voxels within a 2D triangle, then pushing them into the 3rd axis using edge weights.

However I didn't fully understand the math and my implementation had a few bugs. There were missing voxels in thin triangles:

And in some cases it completely broke:

But in most cases it did produce some nice looking triangles:

The performance wasn't great as it was running the edge function on every voxel in the mesh, which involved many float multiplications and additions.

Approach 3

My next idea was to use my voxel raymarcher to create a triangle. First I would raymarch from point A to point B in the triangle, adding voxels at each step of the way:

Then I would cast another ray to point C, from each voxel in the line:

This is very fast to run, and the triangles it produced were chunky, but had no gaps:

I used this approach to voxelise each triangle in this 3D headphones model. Apart from some unrelated meshing issues, it worked great!

Rotation

The next task was to be able to rotate a 3D model and update its voxels in real time. The challenge here is that the old voxels need to be removed, or else the model leaves a trail of voxels, like the old Windows trail bug:

Battlefield 4 is one of my favourite games. I was surprised when I found this image!

To solve this, I'd keep a list of pointers to all the voxels that the model wrote to. When the model moves/rotates, I'd remove all the old voxels, and then re-voxelise the model. This worked great:

However it gets more complicated when multiple models overlap.

Overlap

If we have two 3D models overlapping each other, the process is to:

Voxelise model A
Voxelise model B

Model B won't overwrite the voxels that model A placed, so if model A moves away, we're left with empty voxels. It looked like a bite was taken out of model B.

So when a model moves/rotates, we need to check which other models it overlapped with, and re-voxelise them.

I'm terrible with math, so I asked ChatGPT how to check if two rotated rectangular prisms are overlapping. It told me this is called an OBB (Oriented Bounding Box) collision test, explained how it worked, and produced a C# function for me. The code worked and I'm blown away that AI has come this far.

Here you can see the OBB boxes around each model, which turn white when they overlap:

It works great and looks like the models are passing through each other.

Spikes

Before I mentioned that when a voxelised model rotates, I would remove its old voxels and then re-voxelise it. This works great for visualisations like this, but it breaks raytraced audio.

Since raytraced audio runs continuously on a background thread, sounds would become clear for a split second when then voxels are removed, then muffled again when the model is re-voxelised.

So I gave each model two HashSets - one to store the voxels it added last frame, and one for the voxels it added this frame. After voxelising a model, I'd compare the sets and remove the old voxels. This worked, but was very slow with thousands of voxels, and uses a lot of memory to keep track of all these voxels.

Solution

I experimented with all sorts of HashSets, dictionaries, lists, etc, but couldn't seem to get these models to voxelise in under 30ms. Keeping track of the voxels a model places was just too expensive.

The next idea I had was to have two copies of the voxel map. The 1st map will be used for Raytraced Audio, and models will be voxelised into the 2nd 'background' map.

Each map is composed of groups of 32x32x32 voxels called chunks. After the models have been voxelised into the 2nd map, the chunks that were modified get swapped into the 1st map. This swap is instant, so the only downside here is allocating a 2nd voxel map, which is only 32kb per chunk.

You can see the modified chunks in the video below:

This is much faster, and uses less memory as I don't need to keep track of all the voxels that every model touched.

It also simplifies the overlap checks. When a voxel model moves, its old chunks that it modified last frame are marked as 'dirty'. Then any other 3D models that previously touched these dirty chunks are also marked as dirty.

All affected models are then re-voxelised into the 2nd map in a batch, and then the affected chunks are swapped into the 1st map.

This takes about 5-7ms to update 170,000 voxels on my main PC, and 14-20ms on my laptop on power saver mode. The total map size here is 256x256x256.

Ideally you wouldn't be updating this many voxels every frame - and the voxelisation will occur on background threads - but it's nice when it's fast!

Next Steps

The next step is to voxelise basic shapes like cylinders, spheres and prisms, as well as terrain and heightmaps.

I also need to move this voxelisation process to a background thread so it doesn't impact your game's performance. Theoretically each model can be voxelised on its own thread, which would be awesome for performance.

The Raytraced Audio documentation is also coming along nicely. It's a work in progress, but feel free to read through it.