33
votes

Given 2 set of points

((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and

((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space.

How will you find out whether these triangles intersect or not?

One obvious solution to this problem is to find the equation of the plane formed by each triangle. If the planes are parallel, then they don't intersect.

Else, find out the equation of line formed by the intersection of these planes using the normal vectors of these planes.

Now, if this line lies in both of the triangular regions, then these two triangles intersect, otherwise not.

trianglesIntersect(Triangle T1, Triangle T2)
{
   if(trianglesOnParallelPlanes(T1, T2))
   {
      return false
   }
   Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2))
   if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1))
   {
      return true
   }
   return false
}

Given that I know how to write the above functions, what other implementations of trianglesIntersect should I consider?

Are there faster algorithms that solve this problem?

2
Try asking on math.stackexchange.com instead. SO is for programming questions.PengOne
I am disappointed that this question was closed. This is a well-known programming problem that crops up in computer graphics, ray-tracing, video games. I have programmed it myself more than once. How can it be off-topic here?Gareth Rees
@gareth It is a math problem, not a programming problem. If you were making cooking applications, would you allow the question of whether to whip the egg before pouring in milk or vice versa?Lasse V. Karlsen
From the FAQ: Questions that cover "a specific programming problem" or "a software algorithm". This is not a "math" problem, it's more like computational geometry and comes up ALL the time in graphics, games, simulation.phkahler
@Lasse V. Karlsen : So you mean to say that programming problems and math problems are two disjoint sets?Atishay

2 Answers

31
votes

Visit this table of geometric intersection algorithms courtesy of realtimerendering.com, look at the entry for triangle/triangle intersections, and follow the references, for example to Christer Ericson, Real-Time Collision Detection, page 172. (A book which I recommend highly.)

The basic idea is straightforward. If two triangles intersect, then either two edges of one triangle intersect the other (left configuration in the diagram below), or one edge of each triangle intersects the other (right configuration).

enter image description here

So perform six line segment–triangle intersection tests and see if either of these configurations is found.

Now, you ask, how do you do a line segment/triangle intersection test? Well, it's easy. Visit this table of geometric intersection algorithms, look at the entry for line segment (ray)/triangle intersections, and follow the references...

(It's important to mention that the simple test outlined above doesn't handle coplanar triangles correctly. For many applications this does not matter: for example, when detecting a collision between meshes of triangles, the coplanar cases are ambiguous so it does not matter which result is returned. But if your application is one of the exceptions, you'll need to check for that as a special case, or read on in Ericson for some other methods, for example, the separating-axis method, or Tomas Möller's interval overlap method.)

1
votes

I implemented the algorithm described in Dynamic Collision Detection using Oriented Bounding Boxes for non-coplanar triangles only, which is based on the separating axis theorem.

Here's my GitHub repo with the code (in the file collision-tests.js) and a demo/test page:

The code is deliberately written to match the relevant portion of the 'Dynamic Collision' document. Below is the intersection test function (and the whole contents of the collision-tests.js file). Note that a three.js triangle object has a, b, and c properties for the triangle's three vertices.

/**
 * @function
 * @param {THREE.Triangle} t1 - Triangular face
 * @param {THREE.Triangle} t2 - Triangular face
 * @returns {boolean} Whether the two triangles intersect
 */
function doTrianglesIntersect(t1, t2) {

  /*
  Adapated from section "4.1 Separation of Triangles" of:

   - [Dynamic Collision Detection using Oriented Bounding Boxes](https://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf)
  */


  // Triangle 1:

  var A0 = t1.a;
  var A1 = t1.b;
  var A2 = t1.c;

  var E0 = A1.clone().sub(A0);
  var E1 = A2.clone().sub(A0);

  var E2 = E1.clone().sub(E0);

  var N = E0.clone().cross(E1);


  // Triangle 2:

  var B0 = t2.a;
  var B1 = t2.b;
  var B2 = t2.c;

  var F0 = B1.clone().sub(B0);
  var F1 = B2.clone().sub(B0);

  var F2 = F1.clone().sub(F0);

  var M = F0.clone().cross(F1);


  var D = B0.clone().sub(A0);


  function areProjectionsSeparated(p0, p1, p2, q0, q1, q2) {
    var min_p = Math.min(p0, p1, p2),
        max_p = Math.max(p0, p1, p2),
        min_q = Math.min(q0, q1, q2),
        max_q = Math.max(q0, q1, q2);

    return ((min_p > max_q) || (max_p < min_q));
  }


  // Only potential separating axes for non-parallel and non-coplanar triangles are tested.


  // Seperating axis: N

  {
    var p0 = 0,
        p1 = 0,
        p2 = 0,
        q0 = N.dot(D),
        q1 = q0 + N.dot(F0),
        q2 = q0 + N.dot(F1);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Separating axis: M

  {
    var p0 = 0,
        p1 = M.dot(E0),
        p2 = M.dot(E1),
        q0 = M.dot(D),
        q1 = q0,
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E0 × F0

  {
    var p0 = 0,
        p1 = 0,
        p2 = -(N.dot(F0)),
        q0 = E0.clone().cross(F0).dot(D),
        q1 = q0,
        q2 = q0 + M.dot(E0);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E0 × F1

  {
    var p0 = 0,
        p1 = 0,
        p2 = -(N.dot(F1)),
        q0 = E0.clone().cross(F1).dot(D),
        q1 = q0 - M.dot(E0),
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E0 × F2

  {
    var p0 = 0,
        p1 = 0,
        p2 = -(N.dot(F2)),
        q0 = E0.clone().cross(F2).dot(D),
        q1 = q0 - M.dot(E0),
        q2 = q1;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E1 × F0

  {
    var p0 = 0,
        p1 = N.dot(F0),
        p2 = 0,
        q0 = E1.clone().cross(F0).dot(D),
        q1 = q0,
        q2 = q0 + M.dot(E1);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E1 × F1

  {
    var p0 = 0,
        p1 = N.dot(F1),
        p2 = 0,
        q0 = E1.clone().cross(F1).dot(D),
        q1 = q0 - M.dot(E1),
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E1 × F2

  {
    var p0 = 0,
        p1 = N.dot(F2),
        p2 = 0,
        q0 = E1.clone().cross(F2).dot(D),
        q1 = q0 - M.dot(E1),
        q2 = q1;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E2 × F0

  {
    var p0 = 0,
        p1 = N.dot(F0),
        p2 = p1,
        q0 = E2.clone().cross(F0).dot(D),
        q1 = q0,
        q2 = q0 + M.dot(E2);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E2 × F1

  {
    var p0 = 0,
        p1 = N.dot(F1),
        p2 = p1,
        q0 = E2.clone().cross(F1).dot(D),
        q1 = q0 - M.dot(E2),
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E2 × F2

  {
    var p0 = 0,
        p1 = N.dot(F2),
        p2 = p1,
        q0 = E2.clone().cross(F2).dot(D),
        q1 = q0 - M.dot(E2),
        q2 = q1;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  return true;
}