物体层次分割与相交性计算的实时动态仿真

毫无疑问，碰撞检测是动态仿真中最耗时的步骤。理论上，在整个仿真过程中，每个物体都要和其他物体进行碰撞检测。一旦检测到碰撞，仿真引擎需要将时间回溯到碰撞前的那一刻，并根据碰撞物体的相对几何位移，计算碰撞点和碰撞法线。

在通常情况下，碰撞是通过寻找物体间的几何相交性进行检测的。当使用边界表达法定义物体时，可通过寻找每个物体的图元之间的几何相交性来进行检查，也就是说，在定义每个物体边界的多边形面之间检测相交性。显然，像这样进行物体之间的碰撞检测是很费劲的。因此，使用各种中间表达法来加速碰撞检测是实现实时性的关键，特别是针对涉及数千个物体，而且每个物体由数百个图元描述的仿真。

本章研究使用物体的层次表达法来加速碰撞检测，目标是在预处理阶段计算各物体相对于局部坐标系的层次分解。这通常包括关于多种包围体的树形分层，其中最上层的包围体包围了整个物体，而树形层次的中间节点包围了父节点包围体的子部，树形层次的叶节点包围了父节点包围体内部的一个或多个图元。接下来，物体的层次表达用于碰撞检测，快速确定物体不相交（不碰撞），或减少碰撞检测所需图元对的数量。例如，如果每个物体的顶层包围体不相交，则可以肯定物体间没有碰撞。然而，如果顶层包围体相交，则需将树形层次向下移动一层，以检查子包围体是否相交。如果没有相交，则物体不会碰撞；否则，将树形层次再向下移动一层至相交父包围体的子包围体。这个过程将持续到树形结构的叶节点，或检测到物体不相交才停止。如果到达树形结构的叶节点，通过计算各相交叶节点包围的成对图元相交性，则继续执行碰撞检测。

在实践中，当仿真引擎使用层次表达时，有两个要点需要考虑：第一个要点在于包围体的相交测试应比图元的相交测试快很多。否则，层次表达所需的碰撞检测时间将比物体边界表达的碰撞检测时间长。因此，包围体的选择仅限于简单的几何形状，即相互之间能够快速相交测试的四方体和球体。图元也被限制为凸多面形，甚至是三角形，以便进一步加快图元-图元的相交测试。第二个要点是当物体在世界坐标系中平移和旋转时，层次表达的更新。

综上所述，层次分解的计算是相对物体的局部坐标系，而所有的相交测试都是基于世界坐标系，因此涉及坐标变换，即将物体从局部坐标系转换为世界坐标系里的位置和方向。该问题的一个解决方法是，在相交测试开始前，将所有物体的整个树形层次转换到世界坐标系。这么做的缺点是，对于只需检测树形层级的最上层、或仅检测部分内部节点的相交性时，将造成时间的实质性浪费。实际上，其余所有不进行相交测试的内部节点是没必要转换到世界坐标系的，这样耗费在坐标转换上的时间就可以减少。一个想法是仅对必需的节点进行坐标变换。可以按照以下方法操作。(www.xing528.com)

仿真引擎仅用顶层包围体表示世界坐标系中的每个物体，而在物体的局部坐标系中保持整个层次树以及物体的边界表示。在每个时间间隔，仅在世界坐标系中移动物体的顶层包围体。这种移动包括根据所使用的数值方法，如常微分方程的求解，对物体的位置和方向进行更新，并应用于物体的顶层包围体。

在碰撞检测阶段，检测可能碰撞的顶层包围体之间的几何相交性。当顶层包围体相交时，仿真引擎仅将它们的下一层包围体从局部坐标系转换到世界坐标系。如果它们的下一层包围体不相交，物体便不会碰撞，因此无须再进行转换。否则，仿真引擎仅转换相交包围体下一层子包围体，直至得出结论：物体不会相交，或者有相交的叶节点。在此情况下，与相交叶节点相关的各图元首先从局部坐标系转换为世界坐标系；然后执行资源消耗更高的图元-图元相交测试。使用该方法，可以确保仿真引擎仅将物体中绝对有必要进行碰撞检测的部分进行坐标变换，从而节省大量的计算时间。

本章基于层次表达：首先定义了轴向包围盒、方向包围盒、包围球3种包围盒，并对凸包进行了分析；最后针对包围盒介绍了包围盒之间的相交测试，对于图元级，即点、线、面等之间的相交测试可参见参考文献。