Determine voxels that a triangle is in [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 2 years ago.

Improve this 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.

Answer 2

The best way is rasterization using a DDA, because it will be several times faster than any triangle-in-box test. Rasterization is a scattering techqiues, so it only touches the voxels that are on the triangle surface. Box-tests are gathering techniques, so they require that every voxel check which triangles touch it. The former (scattering) is O(n^2) while the latter, gathering, is O(n^3).

For a good CPU comparison of the two, see: https://github.com/ramakarl/voxelizer

This code demos two gather techniques, Schwarz-Seidel and Akenine-Moller, and one scatter technique, the edge-based 2D DDA.