algorithm - 多边界框包含检测算法

有谁知 Prop 有以下描述的多边界框包含检测算法(或实现引用):

让我们收集轴对齐边界框，其中一些可能与

相交

和一个简单的 3D 形状，例如一个球体(或者它可以是另一个 AABB)。

我需要可以检测形状是否完全包含在 AABB-s 中的算法。换句话说，球体的任何部分都不在 AABB-s 之外。

问题是:很容易测试单个 AABB 中的包容性，但是在某些情况下，形状可能会在多个 AABB-s 之间 split ，甚至可能与多个 AABB-s 相交，但与球体的某些部分相交在外面。

最佳答案

IMO，您可以通过扫描平面方法来做到这一点。

按顶部和底部的“应用程序”(z 坐标)对所有 AABB 进行排序。现在考虑一个从面到面向下移动的水平面，每次更新事件列表(即与平面相交的那些框)。一个盒子在它的顶面进入列表并在它的底面离开它。

平面的场景部分将由一组矩形组成，可能还有一个圆。在每一步，圆都需要完全包含在矩形的联合中。

请注意，您还需要停在赤道附近的平面(这不会修改事件列表)，因为球体是那里的“最大”球体。

这样做，您将初始问题转化为一组带有矩形和圆形的 2D 包含子问题。

遵循相同的原则，您可以通过扫描线技术解决后者，按矩形的顶/底边的纵坐标对矩形进行排序并移动事件列表。在每一步中，iso-y 线的部分定义了一组段，每个矩形一个，可能一个用于圆，并且通过对 x 的边界进行排序很容易证明包含。



换句话说，通过 3D 扫描过程，您可以分解棱柱板中的空间并构建与球体的交点。通过 2D 扫描过程，您可以将平面分解为矩形板，并与截面圆盘建立交点。

关于algorithm - 多边界框包含检测算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50656051/