有金字塔束-AABB相交算法吗？

Question

我正在尝试找出一种方法来检查轴对齐边界框（AABB）是否与金字塔梁相交。是否有已知的算法？有谁知道如何解决这个问题？

我所说的金字塔光束本质上是厚度不断增加的光线 - 它们可以被认为是射入 3D 场景的无限金字塔体积。下面是我想要实现的目标的 2D 示意图。

梁由以下数据定义：

• 原点（3个浮点数，基本上是金字塔尖）
• 方向（3 个浮点数，标准化）
• 单位宽度和单位高度（浮动，距离 1.0f 处梁的宽度和高度）

我使用单位宽度和单位高度方法而不是角度，因为当光束变得足够窄时，角度会遇到浮点舍入误差。距离原点一定距离处的梁的宽度或高度可以用以下公式计算：

width = unit_width * distance
height = unit_height * distance

AABB 由以下任一定义：

• 最少（3 个浮点数）
• 最大（3 个浮点数）

或：

• 中心（3 个浮子）
• 半维（3 个浮点数）

我将选择对交集算法更有利的表示形式。我所需要的只是一个布尔值，指示光束是否与特定 AABB 相交 - 不需要相交点。谁能分享一些关于如何有效解决这个问题的见解？

Answer 1

您的两个物体都是凸多面体（您的“金字塔束”是无界凸多面体），因此分离轴测试将起作用。基本上，您可以看到梁是否完全位于 AABB 的面平面之一之上，AABB 是否完全位于梁的面平面之一之上，或者每个边方向的叉积（请注意，AABB 只有三个不同的面）边缘方向）产生一个轴，其中两个形状在轴上的投影是不相交的。如果这些测试都没有产生分离轴，则两个形状相交。

需要检查 6+4+3*4=19 个轴。如果更多的话，你会想使用 GJK 之类的东西来减少测试次数，但我认为在这里不值得。