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;