Triangle - Triangle Intersection Test.

Question

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

Answer 1

I suppose that you have the x,y coordinates for the triangle vertices. eg.
for Triangle A:
1. Side A1: xa1, ya1 2. Side A2: xa2, ya2 3. Side A3: xa3, ya3 for Triangle B:
1. Side B1: xb1, yb1 2. Side B2: xb2, yb2 3. Side B3: xb3, yb3

The triangles intersect if any combination of their lines intercect. Meaning if A1 intersects B1 or B2 or B3, or if A2 intersects B1 or B2 or B3, or if A3 intersects B1 or B2 or B3.

So you need the algorithm that decects if two lines intersect. Here is the easiest example I found: http://www.mathopenref.com/coordintersection.html

Answer 2

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.

Answer 3

The method you posted looks like it is using something akin to this algorithm to detect if convex polygons intersect, based on the Separating Axis Theorem. It's not very difficult to understand.

If a line, called a separating axis, can be drawn between two polygons, they do not intersect. Each edge of each polygon is a candidate separating axis. The polygons are projected onto a vector perpendicular to that axis, and the 1D extents are tested for overlap. If there is no 1D overlap, the current edge is a separating axis and the two polygons do not intersect. If there is 1D overlap, the results are inconclusive until all candidate edges have been tested, at which point it is concluded that the two polygons do intersect. Note that two polygons are allowed to share an edge.