Triangle-Cube/Voxel Intersection

Question

What would be the best algorithm to detect whether a triangle intersects with a voxel/cube in 3D space? I have this source, written in C: http://tog.acm.org/resources/GraphicsGems/gemsiii/triangleCube.c . I was trying to refactor and convert this code to C++, but I realized that I really have no idea what is going on. Moreover, the comments state that the triangle intersection is compared with a unit cube, however I am unable to find a way to extend the algorithm to work with any arbitrary cube/voxel.

Is there a more clear implementation (preferably in C++) of detecting triangle-cube intersection? If not, what would be the best way for me to extend the C code to work with any arbitrary cube?

Thank you in advance

Answer 1

A simple algorithm would be to:

• Calculate the plane on which the triangle lies.
• Find the intersection between this plane and the cube (if any).
• If there is no intersection then the problem is solved.
• Otherwise, find the straight line which runs through each of the triangles edges.
• For each line: If the intersection is on the "outside" then there is no intersection.
• Otherwise there is an intersection.

If your criteria for the "best" algorithm is simplicity, then this would be a good one. If your looking for performance, there are probably some faster ones out there.

You could also try looking at the code hosted at:

http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/