如何将重叠的AABB集细分为不重叠的AABB集？

Question

我有一套3D的AABB。每个AABB跟踪另一个数组中的索引。我想找到这些AABB并将其细分为较小的AABB，无论它们在哪里相交。创建的每个新AABB都需要跟踪不同拆分的AABB之间的索引并集。请参见下面的2D图像示例：

​

​

我希望左边的3个重叠的AABB变成右边的9个不重叠的AABB。

我该如何去实现这个目标呢？

Answer 1

按矩形的y(然后x表示打破平局)坐标对矩形的所有角进行排序。在一次迭代中处理每个角落。

1. 如果是左上角，请将新矩形添加到列表中并更新重叠状态。
2. 如果是右上角，请从列表中删除当前矩形并更新状态。
3. 如果是左下角，则将其添加到列表中。
4. 如果是右下角，则从列表中删除当前矩形。

在此过程中，您需要维护列表中所有矩形的重叠状态。

Answer 2

您可以使用甜线方法。

对所有角坐标进行递增排序。然后考虑所有成对的连续纵坐标，它们在平面上定界一个板。现在，在每个楼板中，你都有一个一维问题，你可以通过对横坐标进行排序来解决这个问题。

​

​

您可以使用活动列表有效地实现这一点，在活动列表中，框可以进入和离开。您可以使用二叉树，通过退出纵坐标和left+right横坐标对其进行排序。然后用“重叠计数器”从左向右扫描，它会告诉你什么时候生成矩形。

Answer 3

第1部分-细分区间

当您将维数限制为1时，长方体只是一个间隔。考虑一个名为“check_point”的数据结构：

struct check_point {
float value;
bool start; // true if this is the start of an interval, false otherwise.
int id; // The id of the interval that is starting or ending at this value.
}

首先，通过数组中的值转换1d间隔的起始点和结束点。迭代此数组，每2个连续的检查点创建一个新的间隔。在遍历检查点时，您可以维护一组当前打开的间隔ids。每当你遇到“开始”检查点时，你就将id添加到集合中，而每当你遇到一个“结束”检查点时，你就从集合中删除id。这看起来像下面的图片。

​

​

第2部分-细分长方体

现在，让我们从第1部分中获取逻辑，并将其调整为更高的维度。

现在我们必须将这些1d间隔转换回盒子。

对于给定的x，y和z输出间隔组合，只有当所有3个间隔(x，y和z)的索引集的交集不是空集时，才应该创建一个框。您可以忽略没有共同索引的xyz间隔组合。这将为您提供一组细分的长方体。

下面的图片演示了2d中的一个示例。虚线显示x和y间隔的所有可能组合。转换为框的组合中有一个复选标记。同样的逻辑也应该在3个或更多的维度上工作。

​

​

注意:此算法给出的框比示例中的框更多(尺寸更小)。但这是更具确定性的，没有遵循细分框的任意约定。您可以根据实际需要随时修改算法以创建更少的长方体。