# Subtle Problem with Triangle Intersection, and an easy solution

So, this bug stole 4 hours of my life a few days back. Right now, intersections between triangles are tested with the method Intersection.intersection(), which is based off of a paper (“A Fast Triangle-Triangle Intersection Test”) written by Tomas Moller. You can find it here: http://jgt.akpeters.com/papers/Moller97/

As it turns out, our java implementation, and likely the original as well, suffers from a subtle floating point error such that certain pairs of triangles will (correctly) be detected as not intersection when they are positioned close to origin, but will incorrectly be detected if those same triangles are translated, for example, 10 units to the right.

The solution is easy: just average the 6 vertices of the two triangles, and subtract each vertex by that amount, to center the triangles about origin before each test.

Heres a test case that demonstrates this for a pair of two triangles formed of 6 vertices (these vertices were determined experimentally).

``` import com.jme.intersection.Intersection; import com.jme.math.Vector3f; public class TestIntersection {    /**     * @param args     */    public static void main(String[] args) {              Vector3f a = new Vector3f(-0.1277684f,2.1343315f,0.122862354f);       Vector3f b = new Vector3f(0.11659971f,2.361037f,0.122862376f);       Vector3f c = new Vector3f(0.21620041f,2.2536764f,-0.23069102f);       Vector3f d = new Vector3f(-0.5554124f,1.7375966f,0.12286234f);       Vector3f e = new Vector3f(-0.31104434f,1.9643021f,0.122862354f);       Vector3f f = new Vector3f(-0.21144362f,1.8569417f,-0.23069105f);                     if (Intersection.intersection(a, b, c, d, e, f))       {          System.out.println("Without offset, these triangles intersect.");       }else          System.out.println("Without offset, these triangles fail to intersect.");              Vector3f offset = new Vector3f(10,0,0);       if (Intersection.intersection(a.add(offset), b.add(offset), c.add(offset), d.add(offset), e.add(offset), f.add(offset)))       {          System.out.println("With offset, these triangles intersect.");       }else          System.out.println("With offset, these triangles fail to intersect.");    } } ```

And here is a patch to Intersection that fixes the problem:

```Index: Intersection.java =================================================================== RCS file: /cvs/jme/src/com/jme/intersection/Intersection.java,v retrieving revision 1.26 diff -u -r1.26 Intersection.java --- Intersection.java   21 Jun 2006 20:33:02 -0000   1.26 +++ Intersection.java   15 Jun 2008 18:23:24 -0000 @@ -120,7 +120,39 @@        }        return false;     } - +    +   /** +    * This method tests for the intersection between two triangles defined by +    * their vertexes. Converted to java from C code found at +    * http://www.acm.org/jgt/papers/Moller97/tritri.html +    * +    * @param v0 +    *            First triangle's first vertex. +    * @param v1 +    *            First triangle's second vertex. +    * @param v2 +    *            First triangle's third vertex. +    * @param u0 +    *            Second triangle's first vertex. +    * @param u1 +    *            Second triangle's second vertex. +    * @param u2 +    *            Second triangle's third vertex. +    * @return True if the two triangles intersect, false otherwise. +    */ +   public static boolean intersection(Vector3f v0prime, Vector3f v1prime, Vector3f v2prime, +         Vector3f u0prime, Vector3f u1prime, Vector3f u2prime) +   { +      return Intersection.intersection(v0prime, v1prime, v2prime, u0prime, u1prime, u2prime, true); +   } +    +   private static final Vector3f _v0 = new Vector3f(); +   private static final Vector3f _v1 = new Vector3f(); +   private static final Vector3f _v2 = new Vector3f(); +   private static final Vector3f _u0 = new Vector3f(); +   private static final Vector3f _u1 = new Vector3f(); +   private static final Vector3f _u2 = new Vector3f(); +   private static final Vector3f _center = new Vector3f();     /**      * This method tests for the intersection between two triangles defined by      * their vertexes. Converted to java from C code found at @@ -138,10 +170,34 @@      *            Second triangle's second vertex.      * @param u2      *            Second triangle's third vertex. +    * @param centerTriangles Certain triangles may incorrectly be detected as intersection if they are +    * located far from origin. Set to true to correct for this problem.      * @return True if the two triangles intersect, false otherwise.      */ -   public static boolean intersection(Vector3f v0, Vector3f v1, Vector3f v2, -         Vector3f u0, Vector3f u1, Vector3f u2) { +   public static boolean intersection(Vector3f v0prime, Vector3f v1prime, Vector3f v2prime, +         Vector3f u0prime, Vector3f u1prime, Vector3f u2prime, boolean centerTriangles) { +       +      Vector3f v0; Vector3f v1; Vector3f v2; Vector3f u0; Vector3f u1; Vector3f u2; +       +      if (centerTriangles) +      { +      Vector3f center = _center.set(v0prime).addLocal(v1prime).addLocal(v2prime).addLocal(u0prime).addLocal(u1prime).addLocal(u2prime); +      center.divideLocal(6f);//find the average translation +      v0 = v0prime.subtract(center, _v0); +      v1 = v1prime.subtract(center, _v1); +      v2 = v2prime.subtract(center, _v2); +      u0 = u0prime.subtract(center, _u0); +      u1 =u1prime.subtract(center, _u1); +      u2 = u2prime.subtract(center, _u2); +      }else +      { +         v0 = v0prime; +         v1 = v1prime; +         v2 = v2prime; +         u0 = u0prime; +         u1 = u1prime; +         u2 = u2prime; +      }        Vector3f e1 = tempVa;        Vector3f e2 = tempVb;        Vector3f n1 = tempVc; ```

Jme2 uses the same Intersection class right now; heres a patch against the jme2 source (in case that makes it easier to apply):

```Index: C:/Users/Sam/workspace/jme2/src/com/jme/intersection/Intersection.java =================================================================== --- C:/Users/Sam/workspace/jme2/src/com/jme/intersection/Intersection.java   (revision 3870) +++ C:/Users/Sam/workspace/jme2/src/com/jme/intersection/Intersection.java   (working copy) @@ -121,6 +121,7 @@        return false;     }   +        /**      * This method tests for the intersection between two triangles defined by      * their vertexes. Converted to java from C code found at @@ -140,8 +141,64 @@      *            Second triangle's third vertex.      * @return True if the two triangles intersect, false otherwise.      */ -   public static boolean intersection(Vector3f v0, Vector3f v1, Vector3f v2, -         Vector3f u0, Vector3f u1, Vector3f u2) { +   public static boolean intersection(Vector3f v0prime, Vector3f v1prime, Vector3f v2prime, +         Vector3f u0prime, Vector3f u1prime, Vector3f u2prime) +   { +      return Intersection.intersection(v0prime, v1prime, v2prime, u0prime, u1prime, u2prime, true); +   } +    +   private static final Vector3f _v0 = new Vector3f(); +   private static final Vector3f _v1 = new Vector3f(); +   private static final Vector3f _v2 = new Vector3f(); +   private static final Vector3f _u0 = new Vector3f(); +   private static final Vector3f _u1 = new Vector3f(); +   private static final Vector3f _u2 = new Vector3f(); +   private static final Vector3f _center = new Vector3f(); +   /** +    * This method tests for the intersection between two triangles defined by +    * their vertexes. Converted to java from C code found at +    * http://www.acm.org/jgt/papers/Moller97/tritri.html +    * +    * @param v0 +    *            First triangle's first vertex. +    * @param v1 +    *            First triangle's second vertex. +    * @param v2 +    *            First triangle's third vertex. +    * @param u0 +    *            Second triangle's first vertex. +    * @param u1 +    *            Second triangle's second vertex. +    * @param u2 +    *            Second triangle's third vertex. +    * @param centerTriangles Certain triangles may incorrectly be detected as intersection if they are +    * located far from origin. Set to true to correct for this problem. +    * @return True if the two triangles intersect, false otherwise. +    */ +   public static boolean intersection(Vector3f v0prime, Vector3f v1prime, Vector3f v2prime, +         Vector3f u0prime, Vector3f u1prime, Vector3f u2prime, boolean centerTriangles) { +       +      Vector3f v0; Vector3f v1; Vector3f v2; Vector3f u0; Vector3f u1; Vector3f u2; +       +      if (centerTriangles) +      { +      Vector3f center = _center.set(v0prime).addLocal(v1prime).addLocal(v2prime).addLocal(u0prime).addLocal(u1prime).addLocal(u2prime); +      center.divideLocal(6f);//find the average translation +      v0 = v0prime.subtract(center, _v0); +      v1 = v1prime.subtract(center, _v1); +      v2 = v2prime.subtract(center, _v2); +      u0 = u0prime.subtract(center, _u0); +      u1 =u1prime.subtract(center, _u1); +      u2 = u2prime.subtract(center, _u2); +      }else +      { +         v0 = v0prime; +         v1 = v1prime; +         v2 = v2prime; +         u0 = u0prime; +         u1 = u1prime; +         u2 = u2prime; +      }        Vector3f e1 = tempVa;        Vector3f e2 = tempVb;        Vector3f n1 = tempVc; ```

Interesting.  I wonder if you've done any checking about performance impact?

Not yet, no. The patch is set up with a boolean flag to restore the old behavior if necessary.

But the number of operations doesn't seem to be unreasonable, compared to the method as a whole: 6 vector additions, one vector division, 6 vector subtractions. All the (7) variables I added are static, so theres no extra garbage collection.

I make extensive use of jME's triangle intersection's, so if there does turn out to be a big performance hit, I will certainly notice it.

Alternatively, it could turn out that there is another way to fix the problem? But I didn't really feel confident enough of my understanding of that routine to make anything but superficial changes.