Voxel Rendering Techniques
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.
Rendering just the triangles, without the nice blacklines.
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)…
Only rendering exposed faces, but still lots of triangles.
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).
Top faces for beige voxels atZ=6.
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.
Finding the largest rectangular regions.
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.