An accurate method for Voxelizing Polygon Meshes
Transforming a polygon mesh into a 3D grid / voxel data set is still the quickest way to play with some interesting data in any voxel-based application. You can do this interactively on the GPU, using Eisemann/Décoret’s method, described in Single-pass GPU solid voxelization for real-time applications (2008).
When it comes to doing this as an offline, pre-process step, there’s a good method in An Accurate Method for Voxelizing Polygon Meshes, by Jian Huang, Roni Yagel, Vassily Filippov and Yair Kurzion. Doing 3 relatively simple tests per polygon, you can have a mathematically correct, thin voxel model with configurable separability.
- A spherical test on every vertex.
- A cylindrical test on every edge of the face.
- A test with 6 planes forming a closed volume around the given face.
These tests can be done with minimal operations by cleverly re-using computed normals and cross products.
The following images show the difference between my crude bounding-box voxelization (which works allright for models with lots of polygons) and the mathematically correct method. The good news is that thanks to some optimization and the inherent parallelism of the problem to be solved, the voxelizer is quite fast, voxelizing at 3 million polygons / second, and supporting different output formats (.binvox, .avox, .mavox, …).