<p>A brute force method which works well and we use in production code:</p>
<ol>
<li><p>Calculate AABB of triangle to create a sublist of voxels that may or may not be intersected by the triangle, also calculate the triangle edge tangent planes...</p>
</li>
<li><p>Identify which voxels are intersected by the triangle plane.</p>
</li>
<li><p>For voxels which do intersect the triangle plane, calculate the voxel vertex directions for each tangent plane. If these voxels are entirely 'in front' of any tangent plane, they are not intersecting the triangle.</p>
</li>
</ol>
<p>This process can be threaded (although is lighting fast on modern day CPU's anyway, even with large voxel grids), as calculating the intersection of each voxel is mutatally exclusive of any other.</p>
<p>To identify if a voxel intersects a plane, simply calculate the dot product of each voxel vertex (vertexPosition-planePosition) and the plane normal and assign a 'weight' to each point of the voxel (i.e 1, 0, -1 for 'in front' of plane, on plane and 'behind' plane respectively) and sum them. Voxels with +/- 8 sums are not intersecting, voxels with sums != +/- 8 are.</p>
<p>N.B This is if you consider a voxel vertex on the plane as 'intersecting' the plane. If not, you need to ignore any points on the plane when summing and consider the 'weighting' of the voxel wrt to the total number of valid points for that voxel.i.e if 7 not on plane and one is, triangle does not intersect voxel if weigthing sum is equal to +/- 7.</p>
<p>Depending on the data structure of your voxel grid (voxel struct uses shared vertices i.e vertex indexes), you only need to check each vertex once (per plane, so 4 planes at most) within your sub grid, and then can calculate sums for each voxel. Also you only need to calculate voxel vertex-edge tangent plane intersections, if the voxel intersects the triangle plane in the first place.</p>

CC BY-SA 4.0
2023-04-24T15:10:46.283Z
2023-04-24T21:55:00.297Z
2023-04-24T21:55:00.297Z
lfgtm
<p>Is there an algorithm to rasterize triangles into voxels (3D, not 2D) that is linear in the amount of voxels in the output?</p>
<p>I.e. given a triangle and a grid, generate the exact voxels that the triangle touches.</p>
<p>I know that with lines one can use DDA in any dimension to generate the voxels for the line, but what do I do if what I want is the full triangle and not just the edges?</p>

<computational-geometry><triangulation><voxelization><signed-distance-field>
3D triangle rasterization to voxels
Makogan
# 3D triangle rasterization to voxels

(Asked by: username_0 on 2023-04-23)

Is there an algorithm to rasterize triangles into voxels (3D, not 2D) that is linear in the amount of voxels in the output?

I.e. given a triangle and a grid, generate the exact voxels that the triangle touches.

I know that with lines one can use DDA in any dimension to generate the voxels for the line, but what do I do if what I want is the full triangle and not just the edges?

**Tags:** computational-geometry, triangulation, voxelization, signed-distance-field


---

## 1 answers

### Answer by username_1 on 2023-04-24. Score: 2

A brute force method which works well and we use in production code:

1. Calculate AABB of triangle to create a sublist of voxels that may or may not be intersected by the triangle, also calculate the triangle edge tangent planes...
2. Identify which voxels are intersected by the triangle plane.
3. For voxels which do intersect the triangle plane, calculate the voxel vertex directions for each tangent plane. If these voxels are entirely 'in front' of any tangent plane, they are not intersecting the triangle.

This process can be threaded (although is lighting fast on modern day CPU's anyway, even with large voxel grids), as calculating the intersection of each voxel is mutatally exclusive of any other.

To identify if a voxel intersects a plane, simply calculate the dot product of each voxel vertex (vertexPosition-planePosition) and the plane normal and assign a 'weight' to each point of the voxel (i.e 1, 0, -1 for 'in front' of plane, on plane and 'behind' plane respectively) and sum them. Voxels with +/- 8 sums are not intersecting, voxels with sums != +/- 8 are.

N.B This is if you consider a voxel vertex on the plane as 'intersecting' the plane. If not, you need to ignore any points on the plane when summing and consider the 'weighting' of the voxel wrt to the total number of valid points for that voxel.i.e if 7 not on plane and one is, triangle does not intersect voxel if weigthing sum is equal to +/- 7.

Depending on the data structure of your voxel grid (voxel struct uses shared vertices i.e vertex indexes), you only need to check each vertex once (per plane, so 4 planes at most) within your sub grid, and then can calculate sums for each voxel. Also you only need to calculate voxel vertex-edge tangent plane intersections, if the voxel intersects the triangle plane in the first place.


---

