Introduction
This recent Reddit post has inspired me to write a short entry on a method I developed to reduce the data needs of my voxel structure as far as possible. My goal was the commonly cited “1-Bit-Per-Voxel”. From a pure information theory standpoint I strongly believed that this was impossible without encoding the data somewhere else in the algorithm. I still do, but I tried nonetheless to see how close I could get.
I am currently working on a voxel based game (no, it’s neither sandbox, nor first person) with the goal of realistic rendering of voxels sized in milimeters. Obviously this required lots and lots of data. A compression algorithm was needed, but there are few that suited real-time rendering. I started with Gigavoxels and Sparse Voxel Octrees. They formed the basis, but still required lots of data.
After months and months of trying different things, I finally found a method that seemed promising. And it worked! At least at compressing data. My best attempt so far? 1.8-Bits-Per-Voxel compression. I felt like on an episode of Silicon Valley, except that my algorithm sucked. And here I wish to tell you why.
However, I do believe that the method does have some interesting parts and hope that someone, somewhere out there might find inspiration in it and give us a real working compression algorithm for voxels.
Ohh and just to clarify, I am currently rewriting my entire ray-traced voxel engine just to get rid of this method. It’s that bad.
Sooo, what’s this “idea”?
Bloom Filters! Err, what? Yeah, did I mention it was a lossy algorithm? … There go 99% of the readers. Anyway, you, you last person reading this (thanks mom!), here is a breakdown on how it works.
Let’s start with a simple Sparse Voxel Octree of depth 3 trying to represent that blue triangle as pictured below.
This will result in a very blocky representation of said triangle. To improve it, we can either add contour data / marching cubes or simply add more voxel levels to the octree.
Marching cubes and countour data both have their own problems. Furthermore I explicitly wanted square voxels. Ever since the good old Novalogic Comanche and Delta Force days I just love the look and feel of voxels.
So, more Voxels it is! But, adding more depth to our tree requires alot of data. We need to store pointers, colors… And as we go deeper, these pointers will need more bits to address the far away nodes. So, it seemed obvious, at some level down the octree, I stopped using octrees. The octrees job now was to localise where in space we are and use some other data structure to fill that space with voxels (see red voxels below)
This would be equivalent to 2 more Octree levels, except it is now of a different data structure! A simple bit array would do the trick, but I wanted something fancy!
This data structure could then be traversed using a modified 3D Bresenham’s Algorithm in the ray-tracing routine. Simple.
Bloom Filters
And that structure is a Bloom filter! Basically a bloom filter is nothing more than a lossy way of looking up hashes. Each point in space, when hashed in the bloom filter will return 1 of the following 2 outcomes:
- This Spot in Space is NOT a Voxel
- This Spot in Space might be a Voxel
Yes, might. The bloomfilter will only confirm the non-existence of a voxel. But if it returns true, there is a slight chance it might be a false positive. As I said, lossy.
However! Since we “pre-filtered” our space with a sparse voxel octree, the overall shape of our object we voxelized should still be the same! Furthermore, we can scale Bloom Filters in such a way, that the false positive rate is very small. Seems good!
What we still need is a Hashing function. I decided to go with MurmurHash3. The murmur series is really fast and has a great distribution as was visualized in this great StackExchange answer.
Some Pictures
So, what can be done? Let’s first take a look of an early in-game picture I took a while back using said bloom filtered voxels
At first glance, looks like a standard Landscape scene rendered with Voxels. This is in fact a 8192 x 8192 sized Terrain fully loaded inside the VRAM using the presented method. My pure Sparse Octree implementation took around 400 MB (non-optimized). The bloom filtered version here? 56 MB. That’s roughly 7 Bits-Per-Voxel. Not exactly 1-Bit-Per-Voxel territory, but getting there.
The Catch? If you look closely, you will see minor artifacts (false-positive voxels floating around). Furthermore, a big problem with the bloom filtered voxels is, you can’t store any data in them. Merely a “might be here” and “is not here”. All the color data is stored in the Sparse Voxel Octree overlay ontop of the bloom filter. You can see this, as there are alot of 4 x 4 patches in the terrain of the same color. This could be circumvented by introducing procedural texturing or similar.
The details of this are as follows:
- 18 MB of Sparse Voxel Octree overlay
- 38 MB of Bloom Filter data
- 10% false positive rate
- 5 times hashed with MurmurHash3
Yes, the false positive rate does seem rather high. But, visually, it seemed acceptable to me. The seeds for the Hashing were tweaked in such a way to receive the best looking result. No magical numbers I can give, just trial and error.
And the great thing is? It scales! If I wanted a lower false positive rate and higher detail, I simply would need to increase the Bloom Filter size! Voila! Almost like JPGs.
I did say in the beginning that I managed a 1.8-Bits-Per-Voxel compression at some point. Well. Here is a picture of that
And now forget that this abomination ever saw the light of day (Voxelized with Binvox). Yes, some tricks can be applied to reduce the artifact count significantly. For example in the above picture, all “free floating” voxels were not rendered, as I assumed that those must be false-positives. This was done by doing a hash look up for all neighbouring voxels. Slow, but it did improve image quality quite a bit.
Some Conclusions
At first, I was super excited with this method. I believed for sure that I could reach 1-Bit-per-Voxel territory. But I tried and tried and failed. Anyways,
The Good
- Low memory footprint
- It Scales well!
- You can quickly find out if there might be neighbouring voxels
- Adding and deleting voxels is possible
The Bad
- It’s slow, hashing takes time
- It’s super cache unfriendly
And the Ugly
- Nothing can be stored inside of the voxels
- Artifacts… Artifacts everywhere
So, DON’T use it. It’s bad. But I do hope that it might have given someone out there the inspiration to come up with a really usable compression algorithm for our little voxels.
Currently I am using something based on this idea, but far less memory efficient. It’s working really well, and if it turns out as hoped, I’ll do another post. But sadly, I had to abandon my realism based voxel dream.
** Cheers! **