Determine voxels that a triangle is in [closed]

Question

Given a voxelization of the environment and a triangle with vertices A, B, and C, what would be the best way to determine which voxels that the triangle "occupies" or resides in? In other words, how can can I enumerate all of the voxels in which any part of the triangle is in it?

Answer 1

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:

  1. Compute the 3D axis-aligned bounding box of the triangle.
  2. 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]

  3. 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:

  1. The quantities involved in the voxel / triangle intersection test can be computed incrementally in the various for loops.
  2. The range of the last for loop might be reduced by considering only voxels intersecting the supporting plane of the triangle.
  3. 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:

  1. Choose one of the vertex of the triangle and find which voxel contains it. This voxel will be used as a seed.
  2. 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.