无限锥面*AABB交点测试

Question

我正在尝试发现一种更快的算法,用于测试轴对齐的锥形表面是否与轴对齐的边界框的体积相交.

我开发的当前算法如下:

• 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 上的最大值和最小值。提示：对于，最小值为，最大值为。x^2clamp(0, [xmin, xmax])^2max(xmin^2, xmax^2)

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