如何使用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); 
    }