Voxelizer
by Rama Karl Hoetzlein, http://ramakarl.com
This code is licensed CC-BY (c) 2021
The interface lets you move the vertices of the triangle.
Use 1,2,3,4 keys to change the Algorithm.
Code gives the basic math for the 3D voxelization of a triangle.
Four techniques are provided. The first three are triangle-box intersection tests, and test the triangle against every voxel in the domain O(V^3). The last is a direct DDA Rasterizer, which only visits the voxels touched by the triangle O(Vt).
1- Explicit edge tests: Use edge fuctions to explicitly test each edge of triangle. 27 tests/voxel.
2- Schwarz-Seidel tests: Recent paper that uses a reduced, efficient set of edge tests. 9 tests/voxel.
3- Akenine-Moller tests: The first paper to provide efficient, exact voxelization. 18 tests/voxel.
4- DDA Rasterizer: Starts at one corner and scans along the edges, performing a DDA (2D differential analyzer) to fill the interior of the triangle in 3D. This technique is much faster as it only visits voxels on the triangle.
Sources:
Schwarz & Seidel, 2010, Fast Parallel Surface and Solid Voxelization on GPUs, http://research.michael-schwarz.com/publ/files/vox-siga10.pdf
Akenine-Moller, 2001, Fast 3D Triangle-Box Overlap Testing, https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/tribox.pdf
Pineda, 1998, A Parallel Algorithm for Polygon Rasterization (Edge Functions), https://www.cs.drexel.edu/~david/Classes/Papers/comp175-06-pineda.pdf
Citation of this code when used in papers or projects is appreciated:
- Hoetzlein, Rama. Voxelization of a triangle in 3D. https://github.com/ramakarl/voxelizer
How to Build
- Run cmake in \libmin
- Build the solution for libmin
- Run cmake in \math_voxelizer
- During cmake it should find libmin. If not, set the LIBMIN_ROOT_DIR
- Build the solution. Run it.
Rama Hoetzlein (c) 2019