8

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?

user3146587
  • 4,250
  • 1
  • 16
  • 25
Cenk Baykal
  • 159
  • 3
  • 7

2 Answers2

7

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.
ccorbella
  • 103
  • 4
user3146587
  • 4,250
  • 1
  • 16
  • 25
  • Thank you for the the information! Might be a basic question: but for the first possible approach, is the 3D axis-aligned bounding box of the triangle simply a cube with the triangle extreme points (min/max (x, y, z)) as its edges? Also, would another possible approach be to use Bresenham's algorithm for filling triangles (applied to 3D): http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html ? – Cenk Baykal Feb 08 '14 at 00:46
  • 1
    Yes, the 3D axis-aligned bounding box of the triangle is the box having as vertices the 8 possible combinations of min/max x/y/z coordinates of the triangle. – user3146587 Feb 08 '14 at 00:51
  • 1
    Not sure I would qualify this as Bresenham's in 3D, but you could also also try to use simultaneous ray walking in 3D along two edges of the triangle (starting from one vertex) and report all the intersected voxels on the line segment joining the intermediate points on the edge (keywords to search for are ray walking 3D DDA). – user3146587 Feb 08 '14 at 00:57
  • Thank you for your help! I know this is a bit of an old post, but I am trying to implement the "Check whether the voxel (x, y, z) intersects the triangle" step and I am a little puzzled about the code from Graphics Gems III for the voxel/triangle intersection test. The code seems to be oriented toward the intersection with a unit cube, what would be the best way to modify it so that it works for any arbitrary cube/voxel? Thanks again. – Cenk Baykal Feb 10 '14 at 22:58
  • 3
    @CenkBaykal The code implements a triangle / cube intersection test with a unit cube centered at the origin. To use it with a voxel of bounding box `[xmin,xmax]x[ymin,ymax]x[zmin,zmax]`: apply a translation to the triangle so that the center of the cube `((xmin+xmax)/2,(ymin+ymax)/2,(zmin+zmax)/2)` is at the origin, then apply a non-uniform scaling to the triangle of `(xmax-xmin,ymax-ymin,zmax-zmin)`, and finally invoke the provided implementation (i.e. don't change the code, transform your triangle instead). – user3146587 Feb 10 '14 at 23:32
  • I believe the scale should be `(1/(xmax-xmin), 1/(ymax-ymin), 1/(zmax-zmin))`, not `(xmax-xmin, ymax-ymin, zmax-zmin)`. – Matheus Gadelha May 15 '17 at 23:53
1

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.

Rama Carl Hoetzlein
  • 11
  • 1
  • your demo does not even compile, can you please add the missing functions to the project? https://github.com/ramakarl/voxelizer/issues/1 – Mashpoe Jul 26 '21 at 17:11