@Test public void rayTriangleIntersects() throws Exception { for (int i = 0; i < 10000000; i++) { Random rand = new Random(i); float x1 = rand.nextInt(51) - 25 + rand.nextFloat(); float y1 = rand.nextInt(51) - 25 + rand.nextFloat(); float x2 = rand.nextInt(51) - 25 + rand.nextFloat(); float y2 = rand.nextInt(51) - 25 + rand.nextFloat(); float x3 = rand.nextInt(51) - 25 + rand.nextFloat(); float y3 = rand.nextInt(51) - 25 + rand.nextFloat(); int px = rand.nextInt(51) - 25; int py = rand.nextInt(51) - 25; SimpleVector vec1 = new SimpleVector(x1, y1, 0); SimpleVector vec2 = new SimpleVector(x2, y2, 0); SimpleVector vec3 = new SimpleVector(x3, y3, 0); SimpleVector origin = new SimpleVector(px,py,-1); SimpleVector dir = new SimpleVector(0, 0, 1).normalize(); boolean resultsEqual = G2DUtil.inTriangle(px, py, x1, y1, x2, y2, x3, y3) == (Util3D.rayTriangleIntersects(vec1, vec2, vec3, origin, dir, false) != null); if (!resultsEqual) { System.out.println(" :: " + i); System.out.println(x1 + " " + y1 + " " + x2 + " " + y2 + " " + x3 + " " + y3 + " @ " + px + " " + py); System.out.println(G2DUtil.inTriangle(px, py, x1, y1, x2, y2, x3, y3) + " vs " + Util3D.rayTriangleIntersects(vec1, vec2, vec3, origin, dir, false)); } assert resultsEqual; } }
public static SimpleVector rayTriangleIntersects( SimpleVector v0, SimpleVector v1, SimpleVector v2, SimpleVector origin, SimpleVector dir, boolean isSingledSided ) { assert Math.abs(1 - dir.length()) < 0.0001; SimpleVector v0v1 = v1.calcSub(v0); SimpleVector v0v2 = v2.calcSub(v0); SimpleVector N = v0v1.calcCross(v0v2); float nDotRay = N.calcDot(dir); if (nDotRay == 0 || (isSingledSided && nDotRay > 0)) return null; float d = N.calcDot(v0); float t = -(N.calcDot(origin) + d) / nDotRay; if (t < 0) return null; SimpleVector dist = new SimpleVector(dir); dist.scalarMul(t); SimpleVector pos = origin.calcAdd(dist); SimpleVector v0p = pos.calcSub(v0); float v = N.calcDot(v0v1.calcCross(v0p)); if (v < 0) return null; SimpleVector v1p = pos.calcSub(v1); SimpleVector v1v2 = v2.calcSub(v1); float w = N.calcDot(v1v2.calcCross(v1p)); if (w < 0) return null; SimpleVector v2p = pos.calcSub(v2); SimpleVector v2v0 = v0.calcSub(v2); float u = N.calcDot(v2v0.calcCross(v2p)); if (u < 0) return null; return pos; }
Util3D { public static SimpleVector rayTriangleIntersects( SimpleVector v0, SimpleVector v1, SimpleVector v2, SimpleVector origin, SimpleVector dir, boolean isSingledSided ) { assert Math.abs(1 - dir.length()) < 0.0001; SimpleVector v0v1 = v1.calcSub(v0); SimpleVector v0v2 = v2.calcSub(v0); SimpleVector N = v0v1.calcCross(v0v2); float nDotRay = N.calcDot(dir); if (nDotRay == 0 || (isSingledSided && nDotRay > 0)) return null; float d = N.calcDot(v0); float t = -(N.calcDot(origin) + d) / nDotRay; if (t < 0) return null; SimpleVector dist = new SimpleVector(dir); dist.scalarMul(t); SimpleVector pos = origin.calcAdd(dist); SimpleVector v0p = pos.calcSub(v0); float v = N.calcDot(v0v1.calcCross(v0p)); if (v < 0) return null; SimpleVector v1p = pos.calcSub(v1); SimpleVector v1v2 = v2.calcSub(v1); float w = N.calcDot(v1v2.calcCross(v1p)); if (w < 0) return null; SimpleVector v2p = pos.calcSub(v2); SimpleVector v2v0 = v0.calcSub(v2); float u = N.calcDot(v2v0.calcCross(v2p)); if (u < 0) return null; return pos; } }
Util3D { public static SimpleVector rayTriangleIntersects( SimpleVector v0, SimpleVector v1, SimpleVector v2, SimpleVector origin, SimpleVector dir, boolean isSingledSided ) { assert Math.abs(1 - dir.length()) < 0.0001; SimpleVector v0v1 = v1.calcSub(v0); SimpleVector v0v2 = v2.calcSub(v0); SimpleVector N = v0v1.calcCross(v0v2); float nDotRay = N.calcDot(dir); if (nDotRay == 0 || (isSingledSided && nDotRay > 0)) return null; float d = N.calcDot(v0); float t = -(N.calcDot(origin) + d) / nDotRay; if (t < 0) return null; SimpleVector dist = new SimpleVector(dir); dist.scalarMul(t); SimpleVector pos = origin.calcAdd(dist); SimpleVector v0p = pos.calcSub(v0); float v = N.calcDot(v0v1.calcCross(v0p)); if (v < 0) return null; SimpleVector v1p = pos.calcSub(v1); SimpleVector v1v2 = v2.calcSub(v1); float w = N.calcDot(v1v2.calcCross(v1p)); if (w < 0) return null; SimpleVector v2p = pos.calcSub(v2); SimpleVector v2v0 = v0.calcSub(v2); float u = N.calcDot(v2v0.calcCross(v2p)); if (u < 0) return null; return pos; }  }
Util3D { public static SimpleVector rayTriangleIntersects( SimpleVector v0, SimpleVector v1, SimpleVector v2, SimpleVector origin, SimpleVector dir, boolean isSingledSided ) { assert Math.abs(1 - dir.length()) < 0.0001; SimpleVector v0v1 = v1.calcSub(v0); SimpleVector v0v2 = v2.calcSub(v0); SimpleVector N = v0v1.calcCross(v0v2); float nDotRay = N.calcDot(dir); if (nDotRay == 0 || (isSingledSided && nDotRay > 0)) return null; float d = N.calcDot(v0); float t = -(N.calcDot(origin) + d) / nDotRay; if (t < 0) return null; SimpleVector dist = new SimpleVector(dir); dist.scalarMul(t); SimpleVector pos = origin.calcAdd(dist); SimpleVector v0p = pos.calcSub(v0); float v = N.calcDot(v0v1.calcCross(v0p)); if (v < 0) return null; SimpleVector v1p = pos.calcSub(v1); SimpleVector v1v2 = v2.calcSub(v1); float w = N.calcDot(v1v2.calcCross(v1p)); if (w < 0) return null; SimpleVector v2p = pos.calcSub(v2); SimpleVector v2v0 = v0.calcSub(v2); float u = N.calcDot(v2v0.calcCross(v2p)); if (u < 0) return null; return pos; }  static SimpleVector nearestPoint(SimpleVector[] line, SimpleVector point); static SimpleVector[] nearestLinePoints(SimpleVector[] line1, SimpleVector[] line2); static SimpleVector rayTriangleIntersects(
            SimpleVector v0, SimpleVector v1, SimpleVector v2,
            SimpleVector origin, SimpleVector dir,
            boolean isSingledSided
    ); }
Util3D { public static SimpleVector rayTriangleIntersects( SimpleVector v0, SimpleVector v1, SimpleVector v2, SimpleVector origin, SimpleVector dir, boolean isSingledSided ) { assert Math.abs(1 - dir.length()) < 0.0001; SimpleVector v0v1 = v1.calcSub(v0); SimpleVector v0v2 = v2.calcSub(v0); SimpleVector N = v0v1.calcCross(v0v2); float nDotRay = N.calcDot(dir); if (nDotRay == 0 || (isSingledSided && nDotRay > 0)) return null; float d = N.calcDot(v0); float t = -(N.calcDot(origin) + d) / nDotRay; if (t < 0) return null; SimpleVector dist = new SimpleVector(dir); dist.scalarMul(t); SimpleVector pos = origin.calcAdd(dist); SimpleVector v0p = pos.calcSub(v0); float v = N.calcDot(v0v1.calcCross(v0p)); if (v < 0) return null; SimpleVector v1p = pos.calcSub(v1); SimpleVector v1v2 = v2.calcSub(v1); float w = N.calcDot(v1v2.calcCross(v1p)); if (w < 0) return null; SimpleVector v2p = pos.calcSub(v2); SimpleVector v2v0 = v0.calcSub(v2); float u = N.calcDot(v2v0.calcCross(v2p)); if (u < 0) return null; return pos; }  static SimpleVector nearestPoint(SimpleVector[] line, SimpleVector point); static SimpleVector[] nearestLinePoints(SimpleVector[] line1, SimpleVector[] line2); static SimpleVector rayTriangleIntersects(
            SimpleVector v0, SimpleVector v1, SimpleVector v2,
            SimpleVector origin, SimpleVector dir,
            boolean isSingledSided
    );  }