3D线段求交算法不正确

这是一段 Delphi 代码示例，用于计算 3D 空间中两个斜线之间的距离。为了达到您的目的，需要检查结果是否足够小（表示有交点），检查参数 s 和 t 是否在范围 0..1 内，然后使用参数 s 计算点位置。

该方法的数学原理已在 Paul Bourke 页面 的“the shortest line…”章节中进行了描述。

VecDiff 是矢量差函数，Dot 是标量积函数

function LineLineDistance(const L0, L1: TLine3D; var s, t: Double): Double;
var
  u: TPoint3D;
  a, b, c, d, e, det, invdet:Double;
begin
  u := VecDiff(L1.Base, L0.Base);
  a := Dot(L0.Direction, L0.Direction);
  b := Dot(L0.Direction, L1.Direction);
  c := Dot(L1.Direction, L1.Direction);
  d := Dot(L0.Direction, u);
  e := Dot(L1.Direction, u);
  det := a * c - b * b;
  if det < eps then
    Result := -1
  else begin
    invdet := 1 / det;
    s := invdet * (b * e - c * d);
    t := invdet * (a * e - b * d);

    Result := Distance(PointAtParam(L0, s), PointAtParam(L1, t));
  end;
end;

据我所知，你的代码很好。我已经在 JavaScript 中实现了它(在https://jsfiddle.net/SalixAlba/kkrc9kcf/上)，并且似乎对我能想到的所有情况都有效。我所做的唯一更改是将它改成了适用于 JavaScript 而不是 Lua。最终条件被注释掉。

function GetIntersection(dirStart, dirEnd, p1, p2) {
   var s1_x = dirEnd.x - dirStart.x;
   var s1_y = dirEnd.z - dirStart.z;
   var s2_x = p2.x - p1.x;
   var s2_y = p2.z - p1.z;
   var div = (-s2_x * s1_y) + (s1_x * s2_y);

   if (div == 0)
     return new Vector(0,0);

   var s = (-s1_y * (dirStart.x - p1.x) + s1_x * (dirStart.z - p1.z)) / div;
   var t = ( s2_x * (dirStart.z - p1.z) - s2_y * (dirStart.x - p1.x)) / div;

   if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
      //and (Vector(dirStart.x + (t * s1_x), 0, dirStart.z + (t * s1_y)) or nil) then
      var v = new Vector(
        dirStart.x + (t * s1_x),
        dirStart.z + (t * s1_y));
      return v;
   }
   return new Vector(0,0);
}

数学上讲，这是有意义的。如果 A、B 和 C、D 是两条线。让 s1=B-A，s2=C-D。线 AB 上的一点由 A+ts1 给出，线 CD 上的一点由 C+ss2 给出。要想交点，我们需要

A + ts1 = C + ss2，

或者

(A-C) + ts1 = ss2。

你的 s、t 公式是通过使用向量 s1 和 s2 的二维叉积得到的。

(A-C)^s1 + ts1^s1 = ss2^s1 (A-C)^s2 + ts1^s2 = ss2^s2

记得 s1^s1=s2^s2=0 以及 s2^s1=-s1^s2，我们得到

(A-C)^s1 = ss2^s1 (A-C)^s2 + ts1^s2 = 0

这可以用来解决 s 和 t，这与你的方程相匹配。