Computer Graphics Stack Exchange is a question and answer site for computer graphics researchers and programmers. It only takes a minute to sign up.
Sign up to join this community
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?
A brute force method which works well and we use in production code:
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...
Identify which voxels are intersected by the triangle plane.
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.
A solution could be on the lines of:
Consider the side that has the largest extent along some coordinate and draw the Bresenham line along it. Also draw the other two sides and for every voxel of the initial side, find the voxel that has the same coordinate on another side. Then draw segments between the corresponding voxels.
