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 tr开发者_运维技巧y 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

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.

My answer is simple ... this problem is hard in an arbitrary coordinate system, so Change it to something that makes the problem easy. The Matrix class in xna has a CreateLookAt function which can be used to create a useful transformation on all verticies.

The following example is not optimized, it is written only for understanding of the solution. The Exceptions and their corresponding if statements can all be removed, along with a few vector transformations.

    public static bool CheckColision(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//rotates each edge of the first triangle to the Z axis and checks the second triangle against it then repeats with the second one against the first, and lastly checks to see if all points of the second triangle are on the same side as the first
        if(! CheckColisionLookAt(t1a, t1b, t1c, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1b, t1c, t1a, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1c, t1a, t1b, t2a, t2b, t2c))
            return false;

        if (!CheckColisionLookAt(t2a, t2b, t2c, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2b, t2c, t2a, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2c, t2a, t2b, t1a, t1b, t1c))
            return false;

        return CheckColisionAllOnOneSide(t1a, t1b, t1c, t2a, t2b, t2c);
    }

    public static bool CheckColisionAllOnOneSide(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//simply performs a transformation to check if all points on one triangle are on the same side of the other triangle
        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.X < 0 && t2b.X < 0 && t2c.X < 0)
            return false;
        if (0 < t2a.X && 0 < t2b.X && 0 < t2c.X)
            return false;
        return true;
    }

    public static bool CheckColisionLookAt(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//performs a transformation and checks if all points of the one triangle are under the other triangle after the transformation

        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t1a = Vector3.Transform(t1a, m);//  (0,     0,      0)
        if ( ZERRO < Math.Abs(t1a.X)|| ZERRO < Math.Abs(t1a.Y) || ZERRO < Math.Abs(t1a.Z))
            throw new Exception();
        t1b = Vector3.Transform(t1b, m);//  (0,     0,      maxZ)
        if (ZERRO < Math.Abs(t1a.X) || ZERRO < Math.Abs(t1a.Y))
            throw new Exception();
        t1c = Vector3.Transform(t1c, m);//  (0,     maxY,   someZ)
        if (ZERRO < Math.Abs(t1a.X))
            throw new Exception();
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.Y < 0 && t2b.Y < 0 && t2c.Y < 0)
            return false;
        return true;
    }

Here's a website that contains references to a lot of intersections:

Real-Time Rendering Object/Object Intersection Page

Here's what they list for Tri/Tri:

Möller jgt 2(2);
Held jgt 2(4);
GTweb;
Möller;
GPG p.393;
GTCG p.539;
TGS;
RTCD p.155,172;
Shen jgt 8(1);
Guigue jgt 8(1);
SoftSurfer;
Real-Time Rendering, 2nd Edition  p.590;
Real-Time Rendering, Third Edition p.757

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

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.