Determine voxels that a triangle is in
First, you need a voxel / triangle intersection test.
To achieve this, a natural approach is to apply repeatedly a polygon-clipping algorithm (for instance Sutherland-Hodgman in 3D) on the triangle using the half-planes of the six faces of the cube and check what is left afterwards.
A better approach is described in Graphics Gems III, Triangle-Cube Intersection, pp. 236-239 (an implementation is available).
Then, you need to enumerate all the voxels intersected by the triangle.
A first possible approach:
- Compute the 3D axis-aligned bounding box of the triangle.
- Snap this bounding-box to the voxel grid (flooring/ceiling the min/max vertices of the box) to get a 3D range of voxels
[xmin,xmax]x[ymin,ymax]x[zmin,zmax]
Sweep the voxels to find out which ones are intersected by the triangle:
For
x
in[xmin, xmax]
For
y
in[ymin, ymax]
For
z
in[zmin, zmax]
Check whether the voxel
(x, y, z)
intersects the triangle
This can be optimized in at least a few ways:
- The quantities involved in the voxel / triangle intersection test can be computed incrementally in the various
for
loops. - The range of the last
for
loop might be reduced by considering only voxels intersecting the supporting plane of the triangle. - The order of the loops might be changed to prioritize some axis over another one (to take into account the orientation of the triangle).
A second possible approach:
- Choose one of the vertex of the triangle and find which voxel contains it. This voxel will be used as a seed.
- Starting from this seed voxel, do a breadth-first search (BFS) or depth-first search (DFS) of the voxels intersecting the triangle, i.e.:
- Keep track of which voxels have been tested for intersection with the triangle,
- Process all the untested neighbor voxels of an intersecting voxel, but
- Queue (BFS) or push (DFS) only voxels intersecting the triangle.