Voxel Rendering Techniques
Optimal triangulation & more…
Suppose we want to render an image like the one shown above. This is a voxel model by @ephtracy (of MagicaVoxel fame) made up of 226,036 voxels. Each voxel has integral X, Y, Z coordinates and a color from a palette.
Naively, we can triangulate all six faces of every voxel cube. That’s 12 triangles per voxel, or 2,712,432 triangles! It works, but seems like an awful lot for such a simple model.
Many of those voxel faces aren’t even visible. We can track which voxel cells are occupied using a 3D array or hash table. Then we only produce triangles for faces which are exposed. That is, they have no neighboring voxel. With this model, that brings the number down to 138,260 triangles, or just 5% of the original!
That’s an easy optimization. But our mesh still looks like this (zoomed in a bit)…
That’s a lot of tiny little triangles. We can do better. What we want to do is find large rectangular areas of a like color. The best way to do this is to work in 2D. The first step is to extract faces that are in the same plane and have the same color. Here’s an example, showing the top faces (normal = 0,0,1) of all beige voxels at Z = 6 (the floor).
Now this looks like a 2D binary grid (0 = no voxel, 1 = voxel). We want to find the largest rectangle (by area) of 1's. This can be done using a dynamic programming algorithm. I used this implementation from Stack Overflow. Once the largest rectangle is identified, those faces are removed and we repeat until all faces in this color-plane are accounted for.
Of course, each rectangle can then be rendered as two triangles. When we apply this to all 577 color-planes, the entire model uses just 2,966 triangles, or 1,483 rectangular faces, a thousand-fold improvement over the naive approach and just 2% of the visible-faces approach.
One issue is that the mesh now contains T-junctions which can be problematic. I haven’t had an issue in this particular case, perhaps because everything is axis-aligned, but was still interested in removing the T-junctions after someone pointed it out as a potential issue on Reddit. With a little work, we can remove the junctions. I took two different approaches here. My final approach works like this. Each rectangular face starts with four edges. These edges are first segmented where T-junctions occur. We still have a quad, but these points indicate where we need the triangle vertices to be when we triangulate the quad. I use a recursive solution, repeatedly splitting the polygon into two polygons. The base case of the recursion is when we have 3 points, we can just return a triangle. Otherwise we choose the split that gives us an aspect ratio as close to 1 as possible, to avoid long & skinny triangles. The mesh now contains 4,408 triangles.
I had another idea, which I haven’t really attempted yet. When rectangular-izing each plane, we could have a third value which means the face is hidden. In other words, we don’t care if a rectangle covers that face or not. So, 0=no face, 1=face, 2=don’t care. This could allow us to extend the rectangles into hidden areas if it lets us reduce the total number of rectangles needed. An interesting idea, but maybe not worth pursuing… although it could reduce the mesh size, it would increase load on the rasterizer.
Once I made it this far, I really liked the look of the outlines (they are drawn as thick lines in a separate rendering step), but wanted to only draw the lines at joints. To do that, we need to examine the 12 edges of each voxel and see if they should be drawn based on presence and color of several neighboring voxels. Or do we? Actually, we can do this part with the same 2D color-planes that we are already using. We just generate lines around the perimeter and holes, like this…
One minor issue is that this will generate duplicate line segments (exactly 2x, I think), which I haven’t bothered to filter out yet because it doesn’t make much difference.
Putting it all together, we can now render a beautiful voxel model. We’ve mostly been looking at orthographic projections but a perspective projection is shown below. When rendering the black lines, I add in a slight depth buffer bias to avoid z-fighting and make sure the lines show completely.
These images were rendered with FauxGL, a new software renderer I’m writing in Go. I’m doing it mostly for fun and for learning, and I figured some voxel models would make for good test cases.
The code for triangulating and outlining voxels can be found in voxel.go.
Here’s a breakdown of the time spent in each part of the code, for a 1600 px² output with 4x4 supersampling (so actually rendered at 6400 px²)…
loading vox file... 223.133263ms
generating mesh... 259.45309ms
226036 voxels
2966 triangles
4682 lines
rendering triangles... 740.274697ms
rendering lines... 145.852892ms
downsampling image... 264.575909ms
writing output... 133.878484ms
2.058766649sThanks for reading! You can follow me on Twitter: @FogleBird
