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

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 对象计算的东西。

老实说，当我尝试这个时，我并不知道我的期望是什么。如果不考虑某种类型的增量/误差范围或完全不同类型的结果，就不可能有任何线碰撞算法，例如，返回两条线之间的最短向量。或者至少这样的算法对我来说没有多大意义！

无论如何，我也研究了类 Line 和 LineSegment，但它们没有实现 Collidable 接口。然后我寻找一些确实实现 Collidable 并且类似于一条线的候选者，但我没有看到明确的候选者。

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

如前所述，我必须以某种方式考虑精度。例如，如果线之间的距离低于我作为参数传递的 'delta' ，然后如果线之间的最短距离是 returns 其中一条线上的点，则会有一个交点小于那个增量。

Answer 1

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

我也相信结果比原始结果更具可读性，它在参数无效时抛出异常而不是返回 null 类型的结果，并且变量的范围缩小了。

关于代码的几点观察：

我把原版中的epsilon EPS理解为两点坐标之间的最小距离，以便定义一条线。我已经使用了这样一个长而明确的名称 NUMBERS_SHOULD_BE_DIFFERENT_DELTA 的常量，它是两点之间所需的最小距离，因此计算中的精度损失不会对结果产生不利影响。我相信在比较点是否几乎相等时，在几何计算的应用程序中通常需要另一个这样的增量。因此使用长名称来区分它们。
LineSegment3D class，此处未包含，只是 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);
   }

Answer 2

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

这很容易通过取两条线的方向向量的叉积来完成，这给出了公共垂线的方向，对其进行归一化，然后计算该向量与 any[ 的标量积=26=] 从第一行的一个点到第二行的一个点的向量。

设向量方程为

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)|

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

How to find the intersection of two lines in a 3D space using jmonkeyengine3 (or possibly another library)?

java

3d

geometry

jmonkeyengine