无限锥面* AABB交点测试

Question

我正在尝试发现一种更快的算法，用于测试轴对齐的conical surface是否与轴对齐的边界框的体积相交。

我开发的当前算法如下：

• x = 0
• 对于AABB的任何4个平行边缘中的每一个： 将其线与锥体相交。 如果交叉点在AABB内： 回归真实。 如果交叉点位于AABB的特定一侧： x + = 1
• 如果x == 0或x == 4（所有交叉点都位于AABB的一侧）： 返回false。
• 回归真实。

谁能想到一个更有效的？这似乎通过计算每个线路交叉点做了很多额外的工作。

编辑：

以上算法很糟糕，例如：

锥体只能与盒子的一个边缘交叉，使得所有轴线交叉点都在一侧，因此除非测试所有边缘或者智能选择要测试的边缘，否则上述算法不起作用（可能是最接近锥体的边缘？）。

编辑编辑：请参阅下面我自己的答案，我后面发现的解决方案对我来说似乎是最优的。

Answer 1

我找到了一个可能的最佳解决方

沿+ -z轴的单位右锥开口的等式是x^2 + y^2 - z^2 = 0。

使用x^2 + y^2 - z^2在AABB上找到interval arithmatic的最大值和最小值。提示：对于x^2，最小值是clamp(0, [xmin, xmax])^2，最大值是max(xmin^2, xmax^2)。

• 如果结果间隔完全为负，则框完全位于圆锥内。
• 如果生成的间隔包含0，则框与锥体的表面相交。
• 如果得到的间隔完全为正，则框完全位于锥体之外。

Answer 2

看看this table of object/object intersection tests似乎没有众所周知的锥形/ AABB交叉测试。所以你是自己的，我害怕！

你可以从David Eberly的文章“Intersection of a Triangle and a Cone”开始，看看你有多少可以适应你的情况。 （在最坏的情况下，AABB由12个三角形组成，但我希望你能做得更好。）

Answer 3

来自@Gareth Rees的link to the David Eberly article是一个很好的，但如果你把所有东西都分成三角形，你最终会检查多余的顶点和边缘。我认为这样可行：

1. （可选）检查AABB是否完全位于垂直于锥轴的平面的另一侧。如果是这样，就没有交集了。
2. 检查8个顶点中的每一个，看它是否在锥体内。如果有任何顶点，锥和AABB交点。这非常简单，但链接的第4页对此进行了解释。
3. 检查12个边缘中的每个边缘，看它们是否与锥体相交。如果有任何边缘，锥体和AABB相交。这是在链接的第4-5页。
4. 检查6个面中的每个面以查看它们是否与锥体相交。如果有任何边缘，锥体和AABB相交。由锥轴对AABB形成的检查射线就足够了;这是一个非常标准的交叉测试。

交换面部和边缘检查的顺序实际上可能更好;我希望面部检查比边缘检查更快，所以你可以提前退出。

SIMD优化可能有一些很好的机会，因为顶点和边的数量都是4的倍数，锥体是轴对齐的，但这超出了这个答案的范围:)

Answer 4

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

我在另一个帖子中描述了它：Detect if a cube and a cone intersect each other?