Identify the voxels in which the triangle is located.

Question

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

Answer 1

First you need a voxel / triangles intersection test.

• To achieve this, the natural approach is to re-apply the polygon cropping algorithm (for example, Sutherland-Hodgman in 3D) on a triangle using half-planes of six faces of the cube and check what remains after.

• The best approach is described in Graphics Gems III, Triangle-Cube Intersection, pp. 236-239 ( implementation available).

Then you need to list all the voxels intersected by the triangle.

• The first possible approach:

  • Calculate the bounding three-dimensional boundary of the triangle.
  • Snap this bounding box to the voxel grid (floor / ceiling with min / max window tops) to get a 3D range of voxels [xmin,xmax]x[ymin,ymax]x[zmin,zmax]

  • Expand the voxels to find out which of them intersect with a triangle:

    • For x in [xmin, xmax]

      • For y in [ymin, ymax]

        • For z in [zmin, zmax]

          Check if the voxel (x, y, z) intersects the triangle

  This can be optimized in at least several ways:

  • The values ​​involved in the voxel / triangle intersection test can be calculated incrementally in different for loops.
  • The range of the last for loop can be reduced by considering only voxels crossing the supporting plane of the triangle.
  • The order of the cycles can be changed to prioritize some axis over another (to take into account the orientation of the triangle).

• Second possible approach:

  • Select one of the vertices of the triangle and find a voxel in it. This voxel will be used as a seed.
  • Starting with this seed voxel, do a breadth-first search (BFS) or depth-based search (DFS) of voxels crossing the triangle, i.e.:
    • Track which voxels have been tested to intersect with a triangle,
    • Process all unverified adjacent voxels of intersecting voxel, but
    • Queue (BFS) or push (DFS) are only voxels crossing a triangle.