如何使用jmonkeyengine3（或可能是另一个库）在3D空间中找到两条线的交点？

Question

起初，我想是这样的：

Ray ray1 = new Ray(); 
    Vector3f originRay1 = new Vector3f(0, 0, 1); 
    ray1.setOrigin(originRay1); 
    Vector3f directionRay1 = new Vector3f(0, 0, -1); 
    ray1.setDirection(directionRay1); 

    Ray ray2 = new Ray(); 
    Vector3f originRay2 = new Vector3f(1, 0, 0); 
    Vector3f directionRay2 = new Vector3f(-1, 0, 0); 
    ray2.setDirection(directionRay2); 
    ray2.setOrigin(originRay2); 

    CollisionResults results= new CollisionResults(); 
    int collide = ray1.collideWith(ray2, results); 

但是，这引发UnsupportedCollisionException，所以它不是东西，可以使用两个Ray对象进行计算。

说实话，我不知道我想什么时，我尝试了这一点。如果不考虑某种类型的错误或者不同类型的结果的差异，例如通过返回两条线之间的最短向量，就不能有任何线路碰撞算法。或者至少这样的算法对我来说没有多大意义！

在任何情况下，我也看了成类线和线段，但他们没有实现的可碰撞接口。然后我找了一些执行Collidable的候选人，并且类似于一行，但我没有看到明确的候选人。

我宁愿做使用jme3或JDK库如果可能的话，但我愿意读其他建议。

正如之前提到的，我将不得不考虑到精度莫名其妙。例如，将有一个交叉点，如果线之间的距离低于“增量”，我通过作为参数，然后它返回对线中的一条的点，如果线之间的最短距离小于增量。

Answer 1

一种安全的方法是计算两条线之间的最短距离。

这很容易完成，取两条线的方向向量的叉积，给出公共垂线的方向，对其进行归一化处理，然后计算这个向量的标量积，其中任意向量第一行到第二个点。

让矢量方程式是

A1 + t1 D1 
A2 + t2 D2 

然后，距离：

d12 = |(A2 - A1).(D1 x D2)|/|D1 x D2| 

如果线通过点PQ和RS给出

d = |(P - R).((Q - P) x (S - R))|/|(Q - P) x (S - R)| 

Answer 2

我认为如果我在这里发布我的Java实现可能对别人有用，这不过是上面评论和一些单元测试中建议的this c implementation的翻译。

我也相信结果是更具可读性比原来的，它引发异常时参数无效返回一个空样的结果和变量的范围减小，而不是。

几个关于代码的观察：

1. 我理解在原始版本的两个点的坐标之间的最小距离的εEPS，以便限定一条线。我已经使用了这种经常性与长期，明确的名称NUMBERS_SHOULD_BE_DIFFERENT_DELTA它是如此的精度计算的损失没有在结果产生不利影响两个点之间所需的最小距离。我相信在比较点是否几乎相等时，几何计算应用中需要另一种这样的增量。因此，用长名来区分它们。

2. LineSegment3D类，这里不包括，为以防万一瘦包装为jme3的LineSegment你想知道为什么我使用jme3而不是jme3的LineSegment。

与问题不相关，但其原因是我更喜欢区分向量和点的语义（jme3只使用向量遍地）。

import static com.google.common.base.Preconditions.checkNotNull; 
import static com.google.common.base.Preconditions.checkArgument; 
import static java.lang.Math.abs; 
import javax.vecmath.Point3d; 

//... 

    /** 
    * Calculate the line segment that is the shortest route between the two lines 
    * determined by the segments. 
    * 
    * Even though we are passing segments as arguments the result is the intersection of the lines in which 
    * the segments are contained, not the intersection of the segments themselves. 
    * 
    */ 
    public static LineSegment3D lineToLineIntersection(LineSegment3D segmentA, LineSegment3D segmentB) { 
     checkNotNull(segmentA, "Segment cannot be null."); 
     checkNotNull(segmentB, "Segment cannot be null."); 

     Point3d p1 = segmentA.getPoints().getValue0(); 
     Point3d p2 = segmentA.getPoints().getValue1(); 
     Point3d p3 = segmentB.getPoints().getValue0(); 
     Point3d p4 = segmentB.getPoints().getValue1(); 

     Point3d p43 = new Point3d(p4.x - p3.x, p4.y - p3.y, p4.z - p3.z);  
     checkArgument(!(abs(p43.x) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p43.y) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p43.z) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA), MSG_INVALID_POINTS_FOR_INTERSECTION_CALCULATION); 
     Point3d p21 = new Point3d(p2.x - p1.x, p2.y - p1.y, p2.z - p1.z); 
     checkArgument(!(abs(p21.x) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p21.y) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p21.z) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA), MSG_INVALID_POINTS_FOR_INTERSECTION_CALCULATION); 
     Point3d p13 = new Point3d(p1.x - p3.x, p1.y - p3.y, p1.z - p3.z); 
     double d1343 = p13.x * p43.x + p13.y * p43.y + p13.z * p43.z; 
     double d4321 = p43.x * p21.x + p43.y * p21.y + p43.z * p21.z; 
     double d4343 = p43.x * p43.x + p43.y * p43.y + p43.z * p43.z; 
     double d2121 = p21.x * p21.x + p21.y * p21.y + p21.z * p21.z; 
     double denom = d2121 * d4343 - d4321 * d4321; 
     checkArgument(abs(denom) >= NUMBERS_SHOULD_BE_DIFFERENT_DELTA, MSG_INVALID_POINTS_FOR_INTERSECTION_CALCULATION); 
     double d1321 = p13.x * p21.x + p13.y * p21.y + p13.z * p21.z; 
     double numer = d1343 * d4321 - d1321 * d4343; 

     double mua = numer/denom; 
     double mub = (d1343 + d4321 * mua)/d4343; 

     return new LineSegment3D(
      new Point3d(p1.x+mua*p21.x, p1.y+mua*p21.y, p1.z+mua*p21.z), 
      new Point3d(p3.x+mub*p43.x, p3.y+mub*p43.y, p3.z+mub*p43.z)); 
    } 

几个JUnit 4测试用例。请注意，我还使用自定义的方法来测试，如果两点是相似，足以被认为是相同：

@Test 
    public void testLineToLineIntersection_LineAlongZAxis_LineAlongXAxis() { 
     LineSegment3D segmentA = new LineSegment3D(new Point3d(1, 0, 0), new Point3d(3, 0, 0)); 
     LineSegment3D segmentB = new LineSegment3D(new Point3d(0, 0, -1), new Point3d(0, 0, 5)); 
     LineSegment3D segment = GeometryUtil.lineToLineIntersection(segmentA, segmentB); 

     Point3d expected = new Point3d(0, 0, 0); 
     Pair<Point3d, Point3d> segmentPoints = segment.getPoints(); 

     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue0(), expected)); 
     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue1(), expected)); 
    } 

    @Test 
    public void testLineToLineIntersection_LineAlongZAxis_LineParallelXAxis_DoNotCross() { 
     LineSegment3D segmentA = new LineSegment3D(new Point3d(1, 0, 0), new Point3d(3, 0, 0)); 
     LineSegment3D segmentB = new LineSegment3D(new Point3d(0, 1, -1), new Point3d(0, 1, 5)); 
     LineSegment3D segment = GeometryUtil.lineToLineIntersection(segmentA, segmentB); 

     Pair<Point3d, Point3d> segmentPoints = segment.getPoints(); 

     Point3d expectedFrom = new Point3d(0, 0, 0); 
     Point3d expectedTo = new Point3d(0, 1, 0); 

     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue0(), expectedFrom)); 
     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue1(), expectedTo)); 
    } 

    //I created this test by using 
    //https://technology.cpm.org/general/3dgraph/ 
    //it's pretty easy to create four points and play around until one can ensure that the lines approximately intersect 
    //The calculations for creating intersecting examples are quite easy too, this just saved a little more time and it's good enough for me 
    @Test 
    public void testLineToLineIntersection_RandomLinesAlmostIntersect() { 
     LineSegment3D segmentA = new LineSegment3D(new Point3d(-3, -2, 4), new Point3d(1, 3, 2)); 
     LineSegment3D segmentB = new LineSegment3D(new Point3d(-1, -2, 1), new Point3d(-1, 4, 6)); 
     LineSegment3D segment = GeometryUtil.lineToLineIntersection(segmentA, segmentB); 

     Pair<Point3d, Point3d> segmentPoints = segment.getPoints(); 

     double distance = segmentPoints.getValue0().distance(segmentPoints.getValue1()); 

     Assert.assertTrue(distance < 0.1); 
    }