4

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

1
  • 3
    The restriction to a unit cube should not be a problem. You could simply translate and scale the co-ordinate system so that the voxel occupies the same space as the unit cube.
    – andypea
    Feb 10, 2014 at 4:03

1 Answer 1

0

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/

4
  • 3
    This is not a complete or correct algorithm the cube could lie completely in the center of the triangle, intersecting the "face" of the triangle without intersecting any of the edges. Similarly the voxel can lie on the plane of the triangle but very far away from the triangle without intersection. Jan 30, 2015 at 16:48
  • I don't think you understand this algorithm. It first looks at the intersection between a 2D plane and the cube, then checks whether that intersection lies outside of the triangle. The algorithm never directly checks for intersections between an edge of the triangle and the cube.
    – andypea
    Feb 1, 2015 at 1:29
  • 3
    I agree that I don't understand what you wrote. So, what is the intersection in the second and third step? A point? A line? A polygon? Is this the same intersection mentioned in the fourth step? When you write "is on the outside" of the triangle edge, do you mean check whether some point is on the left or right half-space defined by the plane orthogonal to the triangle's passing through this edge? I worry that if you're not careful when computing this initial plane-cube intersection (point?) you could end up with false positives and negatives all the same. Feb 2, 2015 at 15:39
  • 1
    The intersection mentioned in all steps is the same. It is the intersection between the plane containing the triangle and the cube. If it exists it is either a polygon or, rarely, a point. Once this is found the algorithm only needs to consider the 2D system which lies on the plane. Then for each line which runs through an edge of the triangle the algorithm checks to see whether the original intersection lies on the triangle side of the line.
    – andypea
    Feb 2, 2015 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.