CODEWITHSUNDEEP
c++graphicsgeometryintersectionvoxel
Cenk Baykal
Cenk Baykal

Reputation: 159

Triangle-Cube/Voxel Intersection

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

Upvotes: 4

Views: 6956

Answers (1)

andypea
andypea

Reputation: 1401

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/

Upvotes: 0

Related Questions