In order to correctly voxelize larger meshes with configurable parameters (shell thickness, seperability parameters, …) I’m now implementing the method described in An Accurate Method for Voxelizing Polygon Meshes, by Jian Huang, Roni Yagel, Vassily Filippov and Yair Kurzion. In the paper, they provide a mathematical basis for voxelizing polygonal meshes, and they define the notion of seperability.
Using 3 tests on every polygonal face, we can define which grid cells form a closed-shell voxelization of any polygon mesh:
- 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.
Writing performant intersection tests which can be performed in parallel (thanks, OpenMP!) is no easy task, but it’s great to see how even the smallest amount of changes has a big impact on voxelisation speed. (And I’m not the only one writing intersection tests this week). I’ve been using AMD Codeanalyst to benchmark the performance and check to how many machine instructions these intersection tests translate.
One cool byproduct is that because I’m not simply doing axis-aligned boxes overlap tests anymore, I can now “walk” face edges and voxelize the wireframes themselves. Which just looks cool, but has no apparent useful application other than verifying that the voxelization works correctly. As you can see in the rightmost image (amount of red = amount of red), raycasting in a voxelized wireframe is quite costly, since a lot of rays just miss the thin voxelized wireframe lines, which consists of deep traces into the octree.