Triangle Triangle Intersection in 3d-Space

Question

I'm working with some 3d geometry. I need to find the intersection of triangle with another triangle.

What algorithm could I use?

Solution 1

Many people apparently rely on an implementation (link to source code) of the method described in 2006 in the following paper (link to PDF):

Tropp, Oren, Ayellet Tal, and Ilan Shimshoni. "A fast triangle to triangle intersection test for collision detection." Computer Animation and Virtual Worlds 17.5 (2006): 527-535.

There is however a problem with that code (except for adopting an old programming style, using unconventional notations and loosing the underlying geometrical interpretation): "determinant thing" don't necessarily make your math more robust, if done the wrong way.

I suggest to either use Moeller's method (link to PDF) or take a look at Delliver's paper (link to PDF), implemented in the CGAL library (link, "Triangle_3_Triangle_3_do_intersect.h").

An example: the intersection routine implemented above tells that the triangles (p0,p1,p2) and (q0,q1,q2) defined by the following points

p0 = (-21, -72, 63)
p1 = (-78, 99, 40)
p2 = (-19, -78, -83)
q0 = (96, 77, -51)
q1 = (-95, -1, -16)
q2 = (9, 5, -21)

are not intersecting. Here is a picture of the triangles:

And here is the code snippet (append to original code):

#include <iostream>

inline void setPoint(double p[3], const double x, const double y, const double z)
{
    p[0] = x; p[1] = y; p[2] = z;
}

inline void computeEdges(double v0[3], double v1[3], const double p0[3], const double p1[3], const double p2[3])
{
    v0[0] = p1[0]-p0[0];
    v0[1] = p1[1]-p0[1];
    v0[2] = p1[2]-p0[2];
    v1[0] = p2[0]-p0[0];
    v1[1] = p2[1]-p0[1];
    v1[2] = p2[2]-p0[2];
}

void main()
{
    unsigned int numErrors(0), count(0);
    double p0[3], p1[3], p2[3], q0[3], q1[3], q2[3];
    double v0[3], v1[3], w0[3], w1[3];
    bool res, answer;
    int ret;

    std::cout << "Testing the correctness of tr_tri_intersect3D" << std::endl;

    {
        // Non excluding triangles in generic positions, big determinants, intersecting
        ++count;
        setPoint(p0, -21, -72, 63);
        setPoint(p1, -78, 99, 40);
        setPoint(p2, -19, -78, -83);
        setPoint(q0, 96, 77, -51);
        setPoint(q1, -95, -1, -16);
        setPoint(q2, 9, 5, -21);
        answer = true;

        computeEdges(v0, v1, p0, p1, p2);
        computeEdges(w0, w1, q0, q1, q2);
        int ret = tr_tri_intersect3D(p0, v0, v1, q0, w0, w1);
        bool res = ( ret != 0 );

        if( res != answer )
        {
            std::cout << "# wrong answer on test " << count << "!\n";
            ++numErrors;
        }
    }

}

A final note on the number of arithmetic operations: since the method takes in input pre-computed edge vectors, 12 +/- operations should be added to Table I. of the paper.

Last but not least: please verify what I am writing on your own and give me feedback if you think that I misunderstood something!

Solution 2

This paper describes one implementation:

http://knight.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf

Note that there are different techniques depending on whether you want to know the point/segment where the intersection occurred, or just tell whether an intersect happened. This paper will give you the line segment representing the intersection.

Solution 3

There's a good paper by Devillers et al with the title "Faster Triangle-Triangle Intersection Tests" -- (yes, did a google search, but the search keywords are important...)

Anyway, their point (compared to the Moeller paper in MichaelM's answer) is that you really should get your combinatorial information by doing determinants of selected groups of 4 points (the paper describes how). This avoids computing intermediate values that can be problematically inconsistent, and which probably won't actually be any faster...

You can look at these determinants as figuring out whether the tetrahedron formed by the 4 points is right-handed, left-handed, or degenerate (i.e., planar). This value also determines whether any one of the 4 points is on one side or the other of the plane formed by the other three, and whether the (directed) line formed by any two of the 4 is on one side or the other of the line formed by the other two.

To make a long story short, doing the determinant thing makes your math more robust, and if you pay attention, you can usually convert algorithms that didn't initially do the determinant thing into ones that do. Or, you could just read the paper.

Comments

[Botond]

Just found this code, might be useful for someone looking for a quick, already implemented solution of the Delliver's method: raw.githubusercontent.com/erich666/jgt-code/master/Volume_08‌​/…