无限圆锥曲面与AABB相交测试

Question

我正在尝试发现一种更快的算法，用于测试一个轴对齐的圆锥曲面是否与一个轴对齐的包围盒的体积相交。

我开发的当前算法如下：

• x = 0
• 对于AABB的任何4个平行边:
• 将其线段与圆锥相交。
• 如果相交点在AABB内:
• 返回true。
• 如果相交点在AABB的特定一侧:
• x += 1
• 如果x == 0 或 x == 4（所有的相交都在AABB的一侧）:
• 返回false。
• 返回true。

有人能想出更有效率的算法吗？这个似乎通过计算每条线段的相交来做了很多额外的工作。

编辑：

上述算法是错误的，例如：

锥体只能以一种方式与盒子的一条边相交，使得所有轴线交点都在一侧，因此除非测试所有边缘或智能选择要测试的边缘（也许是最靠近锥体的边缘），否则上述算法不起作用。

编辑：请参见下面我自己的答案，其中包含我后来发现的解决方案，这似乎对我来说几乎是最优的。

- Forrest Voight

---

显而易见的是，在这种情况下，首先检查一个包围球（在这里是盒子）往往更快。 - sje397

另外，如果圆锥体只穿过一个面且没有任何箱子的边与之相交，那么您的算法是否有可能失败呢？ - sje397

除了其他原因（见上文），是的。 - Forrest Voight

Answer 1

我找到了一个可能是最优解：

一个沿着+-z轴开口的单位右圆锥的方程为x^2 + y^2 - z^2 = 0。

使用区间算术在AABB上查找x^2 + y^2 - z^2的最大值和最小值。提示：对于x^2，最小值为clamp(0, [xmin, xmax])^2，最大值为max(xmin^2, xmax^2)。

• 如果结果区间完全为负数，则该盒子完全在圆锥内部。
• 如果结果区间包含0，则该盒子与圆锥表面相交。
• 如果结果区间完全为正，则该盒子完全在圆锥外部。

- Forrest Voight

---

一些优化是可能的，例如将计算扩展到仅计算上限或下限以进行早期退出，并使用其来完全返回内部或外部。实际上，如果只需要一个真/假结果，则只需要计算下限。 - Forrest Voight

Answer 2

看着这张物体/物体相交测试表，似乎没有一个广为人知的圆锥/AABB交叉测试方法。所以恐怕你只能自己想办法了！

你可以从David Eberly的文章“三角形和圆锥的相交”开始，并看看你能在你的情况下适用多少内容。（在最坏的情况下，一个AABB由12个三角形组成，但我相信你可以做得更好。）

- Gareth Rees

---

希望你不介意我在我的回答中引用了你的链接。如果有问题，我会将其移至评论中。 - celion

不用了，继续吧。我自己懒得做这些功课。 - Gareth Rees

在引用的网站上，有一个锥体和定向边界框之间的交叉测试，它确实依赖于一个锥体-AABB测试。虽然不是很简单，但值得一读。 - Daerst

Answer 3

David Eberly文章的链接，由@Gareth Rees提供的这篇文章很棒，但是如果将所有物体都分成三角形，将会检查冗余的顶点和边缘。我认为以下方法可以很好地解决：

1. （可选）检查AABB是否完全在垂直于锥轴的平面的相反侧。如果是，则不存在交集。

2. 检查每个8个顶点是否在锥体内。如果有任何一个顶点在内，则锥体和AABB相交。这很简单，但在链接的第4页上有解释。

3. 检查每条12条边缘是否与锥体相交。如果有任何一条边缘相交，则锥体和AABB相交。这在链接的第4-5页上有介绍。

4. 检查每个6个面是否与锥体相交。如果任何一条边缘相交，则锥体和AABB相交。只需检查由锥轴形成的射线与AABB的交集即可；这是一个非常标准的相交测试。

将面和边检查的顺序交换可能会更好；我预计面检查比边检查更快，因此您可能能够更早退出。

由于顶点和边数都是4的倍数并且圆锥体轴向对齐，因此可能存在一些很好的SIMD优化机会，但这超出了本答案的范围 :)

- celion

Answer 4

我想出了一个算法来解决任意锥体和aabb的一般情况，但它仍然可以有效地处理您的特定情况。

我在另一个线程中描述了它： 检测立方体和圆锥是否相交？

- Matthew Kenneally

---

啊，太酷了！不过针对这个特定情况，你的解法似乎至少比我的慢一个数量级。我的解法只需要大约10次浮点运算。 - Forrest Voight

我还怀疑我在这里提出的技术（基于区间算术）可以应用于一般情况。 - Forrest Voight

我已经对我的解决方案进行了优化。你的速度仍然更快，但是在这一点上，根据我的经验，这可能意味着你错过了某些情况，因为这是一个非常复杂的问题。如果锥体靠近盒子并且锥体的底部接近盒子的中心，该怎么办？想象一下，锥体的边缘直到在锥体的底部与盒子在中间相交之前都没有接触到盒子。 - Matthew Kenneally

啊，标题是“无限”圆锥，哈。在这种情况下，你的解决方案确实非常有效。即便如此，我上面所说的证明了你的方法，按原样使用，不适用于一般情况。 - Matthew Kenneally