Search code examples
c#mathphysicscollision-detectioncollision

Triangle - Triangle Intersection Test

I'd like to know if there is out there some tutorial or guide to understand and implement a Triangle-Triangle intersection test in a 3D Environment. (i don't need to know precise where the intersection happened, but only that an intersection has occurred)

I was going to implement it following a theoric pdf, but i'm pretty stuck at the

  1. Compute plane equation of triangle 2.
  2. Reject as trivial if all points of triangle 1 are on same side.
  3. Compute plane equation of triangle 1.
  4. Reject as trivial if all points of triangle 2 are on same side.
  5. Compute intersection line and project onto largest axis.
  6. Compute the intervals for each triangle.
  7. Intersect the intervals.

point 5 of this guide. I don't really know what's asking (all 5,6 and 7). XD

As i don't have high knowledge in mathematics (well, i know as far the couple of exams at the university has given me (i'm a raw programmer XD)), please try to be as simple as possible with me. :D (I tried to search on google, but most of the links point to some 4-5 pages full of formulas I don't really care to know and I don't understand.)

Thanks for the help

Solution

  • You said:

    I'd like to know if there is out there some tutorial or guide to understand and implement a Triangle-Triangle intersection test in a 3D Environment.

    And then you said:

    most of the links point to some 4-5 pages full of formulas I don't really care to know

    I note that those two statements totally contradict each other. So which is it? Do you want to understand how triangle-triangle intersection works, or do you just want an implementation that works but you don't understand it?

    It's not like all those web pages are full of unnecessary math. All the math is necessary to understanding how the intersection algorithm works. Start at the beginning and learn how all of it works.

    Steps 5, 6 and 7 are straightforward to understand once you know what the words mean. The intersection line is the line made by the intersection of the two planes. Each triangle lies in a plane. There are three cases:

    • the planes are parallel and do not intersect. The triangles obviously do not intersect.
    • the planes are the same plane. The triangles might meet or might not.
    • the planes are two different planes that meet at a line. If the triangles intersect, they obviously must intersect on that line.

    Suppose we're in the third case. Compute the segment of the intersection line which is contained in the first triangle. Compute the segment of the intersection line which is in the second triangle. The question is now "do these segments overlap?"

    You can work that out by projecting the segments onto a convenient axis, and seeing whether the line segments on that axis overlap. Basically, it works like this: imagine you are shining a light on the line segments, such that their shadows fall onto an axis. If the shadows on the axis intersect then the line segments must intersect. If there is a gap between the shadows on the axis, then clearly there must be a gap between the line segments, and therefore the triangles do not intersect.

    If you want to understand how this works then there's no getting around the fact that you are going to need to understand all this stuff -- all the algebra that works out how planes intersect and how projects onto an axis work. It's all necessary. And all that stuff is basic building blocks out of which more complex transformations, projections, and so on, will be built, so understand the basics thoroughly if you want to go farther.