宽阶段碰撞检测

刚体碰撞流程主要分为五部分。首先，对可能产生碰撞的n个刚体构建包围盒树（包括：AABB树（轴平行包围盒树，Aixe align bounding box tree）和OBB树（有向包围盒树），下述将以AABB树为例），将AABB树的根节点对应的区域，作为的碰撞区域；然后，使用Z空间填充曲线（Z-SFC）对碰撞区域进行划分，生成单元空间，并使用Morton码（莫顿码）对单元空间进行编码，生成Z空间填充曲线（Z-SFC）索引，以便后续构建内部节点的邻接关系；接着，根据生成的Z空间填充曲线（Z-SFC）索引自底向上、并行的构建压缩八叉树；其次，对构建出来的压缩八叉树进一步并行的恢复成完整的八叉树结构；最后，根据完整的八叉树自底向上的进行并行碰撞检测。接下来详细介绍每一个步骤：

1、构建AABB树

AABB树中每个子节点也是AABB树的结构，它只需要log(n)的时间复杂度就能完成节点的搜索过程。假设我们要检测刚体1-9的碰撞。根据刚体1-9的轮廓生成AABB包围盒。接下来通过执行以下操作来构建AABB树：

  • 把刚体1作为AABB树的根节点；

  • 把刚体2和刚体1作比较，判断刚体2与刚体1所在的区域有没有交集。如果有交集则继续判断刚体2是否与刚体1的子集有交集，将其加入到与节点1有公共交集的子集的最小的公共子节点之后。如果刚体2与刚体1没有交集，则根据刚体1和刚体2的区域重新生成一个公共区域，作为节点1和节点2的公共节点；

  • 重复步骤b)，直达把所有的节点都加入到AABB树中，并将AABB树的根节点对应的区域，作为的碰撞区域。

2、构建Z空间填充曲线（Z-SFC）和索引

Z空间填充曲线（Z-SFC）技术易于实现，并行化高，可用于将二维或三维空间中的区域进行有效的线性化。假设在D维空间中，将空间的每个维度均匀的分成k分，则会产生 个相等的非重叠的小空间单元。例如使用Z空间填充曲线（Z-SFC）对二维正方形区域进行划分，结果如下图所示；根据划分的结果按顺序进行标记：

例如刚体1-9进行空间划分之后可得到：

通常将划分的结果左下角的小单元空间设置为Z空间填充曲线（Z-SFC）的起点，并对区域进行Morton码编码。在二维空间中，假设存在刚体P的重心位置坐标为（x，y），则将该坐标作为叶子节点的坐标。经过Z空间填充曲线（Z-SFC）划分之后，该点所属的单元将为。对于刚体9横跨多个区域的需要进行去重操作$(\left\lfloor {{2^k}x/D} \right\rfloor ,\left\lfloor {{2^k}y/D} \right\rfloor )$，此时刚体9的Z空间填充曲线索引设置为数值最小的区域即11110000，并保存这几个区域的信息。二维空间创建Z空间填充曲线索引如下图所示：

根据Z空间填充曲线（Z-SFC）索引，我们可以创建不同层级的Z空间填充曲线（Z-SFC），如下图所示：

3、基于GPU的并行压缩八叉树的构建

不同于CPU的八叉树构建，基于GPU的并行八叉树的构建是自底向上构建的。根据叶子节点所在的位置，反向生成内部节点，进而确定内部节点的关系，从而确定树的结构。自底向上生成树的过程适用于GPU并行计算。具体的实施过程如下图所示：

  • 构建叶子节点

    • 将待检测的刚体1-9作为输入点，使用长度为2n-1（n表示刚体的数量）的数组A保存这9个输入点作为叶子节点。

    • 根据叶子节点的坐标生成Z空间填充曲线（Z-SFC）索引。

    • 根据叶子节点的Z空间填充曲线（Z-SFC）索引，并行对数组A中的9个元素进行排序。

  • 生成内部节点和八叉树的后序遍历 对每个相邻的叶子，使用Z空间填充曲线（Z-SFC）索引中的公共位并行的找出最小公共父节点（LCA）。例如，相邻叶子节点1和节点2的Z空间填充曲线（Z-SFC）索引分别为11000001和11000010，由此可得到节点1和节点2的最小公共父节点为11000000。

    • 分配n − 1个GPU线程。
    • 对于数组A中的每两个相邻叶子（例如数组A[i]和A[i + 1]），并行生成最小公共父节点，其最小公共节点的Z空间填充曲线索引为叶子节点A[i]和A[i + 1]的Z空间填充曲线索引的最大公共部分，并将其值存储在A[n + i]中。
    • 根据公共节点的Z空间填充曲线索引，对不同层的内部节点进行并行排序。如果元素L1包含在元素L2中，则将L2元素置于L1元素之前；否则，将L1元素置于L2元素之前。图7中的（c）显示了排序后的内部节点，其中可能会生成重复项（N2和N3）。
    • 在数组A的后半部分中，删除重复项。
    • 对于没有相同Z空间填充曲线（Z-SFC）索引的两个相邻内部节点，并行地从当前节点开始遍历数组A的后半部分，删除它们重复的项。根据Z空间填充曲线（Z-SFC）索引对数组A进行并行排序，进而可以得到压缩八叉树的后序遍历。

  • 生成压缩八叉树 我们可以注意到数组A的末尾可能会有一些空元素。这是无法避免的，因为CUDA不支持动态内存分配和释放，因此必须在编译时就创建大小为2n−1的数组。然而仅仅得到八叉树的后续遍历还无法确定树的结构。（a）所示节点A和节点B属于同级的情况，因此它们的公共的父节点为C；（b）所示节点B是节点N的子节点，与节点A是相邻节点。（c）所示节点B是节点A的父节点。

    为了进一步确定八叉树的内部结构，执行以下步骤：

    • 分配两倍大小的叶子和内部节点数的数组B（最多4n-2）。将数组A复制到数组B中。
    • 分配（叶子节点数+ 内部节点数-1）个GPU线程。
    • 对于数组B的前半部分中的每两个相邻节点，根据Z空间填充曲线（Z-SFC）索引并行的生成最小公共父节点。例如对于数组B中的每两个相邻叶子B[i]和B[i + 1]，并行生成内部节点，并将其存储在B[n + i]中。
    • 根据Z空间填充曲线（Z-SFC）索引对生成的结果进行并行排序，将所有的内部节点和它们的副本将归并到一起。
    • 对于具有相同Z空间填充曲线（Z-SFC）索引并且至少其中一个不是副本的节点，建立内部节点的父子关系。最终生成的压缩八叉树下图所示：

4、从压缩八叉树中恢复完整的八叉树

两个相邻的节点N4和节点3，其中节点3是节点N4的子节点。通过Z空间填充曲线（Z-SFC）索引来计算两个节点之间的深度差。例如节点N4和节点3的Z空间填充曲线（Z-SFC）索引分别为11000000和11001101，则深度差为2（节点N4处于深度1，节点3处于深度3，假设根深度为0）。这种差异表明压缩八叉树中缺少节点N4和节点3之间的中间节点。

为了生成完整的八叉树结构执行：

  • 分配大小等于数组A长度的线程，即（叶子数+内部节点数）。
  • 计算每个节点与其父节点的深度差并累加，以获取插入内部节点所需的内存总数（由于GPU上不能进行动态的分配内存）。
  • 根据每个节点与其父节点之间的深度差添加新的节点。当深度差大于1时，并行的在其中间插入新的节点。如下图所示，在节点N4和节点3之间插入了一个内部节点CH1，以获得完整八叉树结构。

5、使用八叉树结构自底向上的对刚体进行并行的碰撞检测

从叶子节点开始自底向上进行检测，当发现碰撞点时进一步进行细粒度检测，直到找到发生碰撞的叶子节点对。

  • 假设刚体2和刚体3发生了碰撞。针对待碰撞检测刚体，计算刚体所有八叉树层数及对应叶子节点，利用步骤4中八叉树自底向上查询所有重叠区域对应刚体的AABB包围盒。
  • 如果找到碰撞包围盒，针对上述步骤中得到的AABB包围盒进一步对刚体2和刚体3的边界进行精确的碰撞检测，结果如下图所示：