FluidX3D v2.1 (fast voxelization)
Fast GPU voxelization update:
- new algorithm for
.stl
mesh GPU voxelization: ~500x faster now, from minutes to milliseconds - added unvoxelize kernel, to quickly remove all boundaries in the mesh bounding box.
- removed old hull voxelization algorithm
Old: naive GPU voxelization
- For each voxel in the 3D grid, cast a ray from the voxel center in an arbitrary direction, and check with all mesh triangles for intersection.
- Count the number of intersections.
- Odd number of intersections means the voxel is inside.
- Runtime: N³×Triangles
New: fast GPU voxelization
- Only for the 2D bottom layer of grid points, shoot vertical rays upward and check with all mesh triangles for intersection.
- The vertical rays pass through all voxels in the columns above, so these don't have to be checked for ray-mesh intersection at all.
- Store all intersection distances in a short array in registers.
- Sort this array with insertion sort.
- Iterate through the vertical column of voxels.
- The first voxel is inside/outside depending on odd/even total intersection count.
- Each time one of the stored distances in the sorted array is passed, switch inside/outside state.
- Optimizations
- Only check inside the bounding box of the mesh.
- Don't always start from the bottom (z-direction), but from the direction where the mesh bounding box has the smallest cross-section area, so the smallest number of ray-mesh intersections have to be tested.
- To avoid errors on the odd/even total number of intersections, shoot a second ray in the opposite direction and only count the intersection number. Both have to be odd for the bottom voxel to start in inside state.
- Runtime: N²×Triangles, if N=500, this is 500x faster than naive voxelization
Known issues:
- voxelization might not always produce binary identical results in multi-GPU (floating-point round-off on ray-triangle instersection distances may differ for different ray origin) --> fixed in v2.16!