快速查询3D空间中直线与AABB之间最近点的方法。

Question

如何高效地在3D空间中找到无限线和AABB之间的最近点？

我有一个朴素的解决方案，涉及找到AABB的所有12条边到该线的最近点并选择最近的一对，这个方法是有效的，但不够快。我需要更快速的方法适用于我的使用场景。

在我的搜索过程中，我发现了很多关于查找线与AABB之间碰撞的文献以及朴素算法的几种实现方式。但是否有更好的解决方法呢？

- Colonel Thirty Two

---

可能是重复问题：https://gamedev.stackexchange.com/questions/18436/most-efficient-aabb-vs-ray-collision-algorithms - markasoftware

@markasoftware 不错，但链接中的解决方案只提供了距离。看起来这个问题要求找到一对点（即它们的坐标）——一个在线上，另一个在框上——满足最小距离。由于可以有许多这样的点对（即在一般情况下解决方案的不唯一性，虽然通常不是在典型情况下），在边缘情况下，可能任何一个这样的点对都足够（？）。这可能是链接中解决方案的自然扩展，但我不太确定。 - Salmonstrikes

@markasoftware 这些是用于碰撞检测，而不是最近点。 - Colonel Thirty Two

Answer 1

我的（也很天真）解决方案是选择距离AABB中心最近的线上点，并从该点向外工作，按照此处的示例进行迭代： https://math.stackexchange.com/questions/2133217/minimal-distance-to-a-cube-in-2d-and-3d-from-a-point-lying-outside

然后沿着该线迭代，直到距离不再减小（必须向每个方向扫过去）。

这将在线与面或边平行的情况下非常快，但我不知道它是否比您的天真解决方案更快，对于没有与AABB平行方面的线条。

（当然，来自数学堆栈交换的解决方案需要从伪代码适应到您选择的语言，并且在找到最短路径后，您必须计算矢量的坐标以获得您的点。）

- Zach Beed

---

请纠正我，您是在建议在变化点的同时计算12个边缘和一条线上的点之间的距离吗？此外，如何找到最接近边缘的点？ - Mythos

Answer 2

首先，你不需要检查所有12条边。例如，假设你想找到距离线A最近的点。通过一些简单的数学计算，你可以找到一个垂直于AABB中心的垂线A'。你可以找到A和A'的交点，称之为点P。因此，点P基本上是AABB中心在线A上的投影点，有数学公式可以计算。如果您能告诉我们您的无限线是如何定义的（是由两个点定义的，还是由一个点和一个方向向量定义的），我将添加它。
现在，您可以查看P的坐标，以确定它相对于AABB中心所在的八分之一区域，即从中心坐标减去P的坐标，这将导致基本平移中心到原点（原点转换）。立方体最接近的顶点将位于同一八分之一区域内。

现在，最靠近该线的边将是该顶点所属的3条边之一。

这将比您的算法快四分之一。

- Mythos

---

这听起来非常有前途，但也许您可以澄清一下如何从P（AABB中心在该线上的投影）到达P'，后者似乎是AABB面上的一个点，这就是为什么您提到象限 - 一个平面概念。 - Salmonstrikes

@Salmonstrikes 请求原谅，没有点P'。 当我写P'时，我认为P是AABB的中心。 重新阅读后，我意识到我从未命名过中心，而是将P视为AABB中心的投影。 我已编辑我的答案以反映这一点。 - Mythos

明白了。最后一个问题：你是不是指八分体而不是四分体，按照 AABB 居中于原点的约定？ - Salmonstrikes

@Salmonstrikes，又抓住我了。感谢您的更正！ - Mythos

很容易猜到你的意思; 说实话，这更多关乎性能而非术语——四组不等式检查与八组。如果这两种方法（这个和问题中的那个）可以以某种方式进行详细比较，那就太好了... - Salmonstrikes

我认为OP对于每条边都使用了类似这个的方法，但是可以通过这种方式将其减少到只有3条边。这种方法的开销在于计算A'和A与A'的交点。找到一条垂线A是找到最近点解决方案的一小部分（如上面链接所示），这被减少到只需要一次而不是OP的8次。因此，我认为这将是更快的实现。 - Mythos

Answer 3

你的线将类似于 cv + p，其中 v 是方向向量，p 是它经过的点。

从线到你的盒子上最近点的方向将垂直于该线，因此获取一对法向量 v，称为 n 和 m。

实际上最接近的点将是 n 和 m 的线性组合，并带有线上的一个点。（你从线上的一个点开始，沿着某个垂直于该线的方向前往目标点，每个垂直于该线的方向都是通过该点的法向量的线性组合。）

因此解决 an + bm + cv + p = s，其中 s 是你的盒子的每个角落。

不失一般性，我们可以假设 v 在其前两个分量中没有零。（如果有一个，则重新排列索引使其成为第三个。如果有两个，则这变成了一个更简单的问题，我们可以单独解决。）

这意味着我们可以取 n = (1, 0, N) 和 m = (0, 1, M)。

由于 n * v = 0 和 m * v = 0，我们可以找到 N = -v1/v3 和 M = -v2/v3。我们不需要进行所有这些替换，只需要知道这些是数字而不是变量即可。

现在我们想要解决 an + bm + cv = s - p。我们可以使用普通代数来完成。我们得到

c = (s3 - p3 - N(s1 - p1)- M(s2 - p2))/(v3 - N v1 - M v2)

而cv + p则是你的线上最接近那个角落的点。

同时我们还有：

b = s2 - p2 - v2 c
a = s1 - p1 - v1 c

该直线距离您的角落的距离为|an + bm|，因此距离的平方是

D^2 = (an + bm) * (an + bm) = (a^2 + b^2 + (aM + bM)^2)

当你看角落时，可以考虑到你有一个盒子。选择一个角落并前往邻居，然后去到把你对角线的邻居。如果这三个值中有一个比同一方向上的另外两个更远，则最近点不在通往该点的边上。这就排除了所有与该点相关的边缘。由于直线可能穿过您的盒子，因此可能不会发生这种情况。但这种情况非常不可能。

对于每对（未被排除的）构成一条边的角落，我们有一个 c 值范围xc0 +（1-x）c1，其中x在[0,1]表示最接近边缘的线上最接近点的范围。

相应的a和b值是：

a = s1-p1-v2(x c0 + (1-x)c1) = s1-p1-v2-(c0-c1)v2 x
b = s2-p2-v1(x c0 + (1-x)c1) = s2-p2-v1-(c0-c1)v1 x

再次强调，只要常量是已知的，我们就可以将其写成：

a = A0 + A1x
b = B0 + B1x

现在，从上面来看

D^2 = (a^2 + b^2 + (aN + bM)^2)

这样我们就可以用x的术语得到平方距离。

D^2 = (A0 + A1 x)^2 + (B0 + B1 x)^2 + 
      (A0 N + A1 Nx)^2 + (B0 M + B1 MX)^2

将所有这些相乘，x项将成为每个平方的中间项，x²项将成为每个平方的平方项。

显然，抛物线k + rx + qx²的最小值是在'r + 2qx = 0'处，通过微分可得'x = -1/2 r/q'。

因此，最小值将为：

x = -(A0 A1 + B0 B2 + (NA0 A1 + MB0 B1))/
     (A1^2 + B1^2 + (A1 N + B1 M)^2)

当x在0和1之间时，你会有一个最小值或最大值。通过比较这些结果，你应该能够丢弃最大值。

如果最小值在面上而不是边缘上，那么你将有太多的符合条件的值。在这种情况下，答案显然是零——线条碰到了盒子。

- Jay Obermark

---

不错的尝试！快速澄清请求：您提到“对于构成边缘的每一对角落...<涉及x的进一步计算>”。如果这意味着您正在运行12次最小化例程，则可能无法满足提问者比其12个边缘检查更快的要求。如果您能澄清您的答案在性能方面意味着什么，那将是很好的。 - Salmonstrikes

但是“运行最小化例程”正在评估非常简单的算术，这些算术已经给出。 - Jay Obermark

@Salmonstrikes，我还注意到你不一定需要查看所有的边缘。构成一个面的角落给了你足够的信息来排除其中更远的角落。只有当线穿过盒子时，你才会最终查看所有的角落。但是这样你会立即得到三个候选点。因此，你只需要查看四个点和与它们相连的边缘。所以我想我已经包含了所有的代数内容，并省略了策略性考虑，使得这个算法变得简短。我稍后会回来再讨论它。 - Jay Obermark