碰撞检测中的K_DOPS算法的研究(1)

    碰撞检测问题在计算机图形学中有很长的研究历史，近年来，随着虚拟现实，分布交互仿真等技术的兴起，碰撞检测再一次成为研究的热点，精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感起着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求。

包围盒树^[7]是解决碰撞检测问题的一种有效的方法，碰撞检测对包围盒树的构造有以下几方面的要求：尽可能平衡以使得树的高度比较低；树的所有结点的包围盒体积尽可能小；每个结点的所有子结点的包围盒的交集尽可能小。但虚拟环境中对象进入的自由性和不可预测性以及碰撞检测的实时性又不允许我们在构造树时进行太复杂的优化，因此如何构造包围盒树将直接影响到碰撞检测的效率。

    K_DOPS可以看作是AABB^[5]的扩展，它不再是用三对平面来包围对象，而是使用了k/2对平面，正是因这这种扩展，它弥补了AABB紧密性差的缺点。因此，K_DOPS是一种很好的包围盒类型。

    Discrete Orientation Polytopes(K_DOPS)包围盒是一种多面体，它的面由一组半空间 所确定，这些半空间的外法向是从 k 个固定的方向（D₁，D₂，...D_k）中选取的^{[2] [5]}。

    设固定方向集K（D₁，D₂，...D_k） ，一元组 （d₁，d₂，...d_k）∈R^k

    其中：

        

      半空间  

    在设计K_DOPS时，为使相关的耗费尽量小，通常只选择那些共线但方向完全相反的向量作为固定法向，因此，每个K_DOPS实际上只用到k/2个方向，即  

         

         

        

    K_DOPS是一组半空间的集合，无论是在表示、存储还是计算中都是十分不方便的，构成K_DOPS的任何一半空间都可以表示成不等式形式：

          

    由于集合D 是固定不变的，可以用一个 k×n矩阵来表示集合 D，从而可以把k_dops表示成如下形式：

    ，其中

    由于 方向是可预知的，所以存储每个K_DOPS时无需保存方向，只需保存K个值即可，每个值对应一个平面的位置。而且当对两个K_DOPS做重叠测试时，只需要进行 次测试，这种测试远比两个OBB或凸包间的重叠测试简单。                                  

    K_DOPS最简单的例子是6_DOPS，其中6个面的法向分别由3个坐标轴的正负轴所决定，三维空间AABB轴向包围实际上是一种6_DOPS的特例。

    对于14_DOPS，其中除了沿用AABB的六个方向外，还增加了8个对角线的方向，以消除这些方向上可能存在的空缺。

    对于18_DOPS，其中除了沿AABB的6个方向外，还加入了指向AABB的12条边的方向，以消除这些方向上可能存在的空缺。

    对于26_DOPS，则沿14_DOPS和18_DOPS合起来的26个方向。

    图1中分别列举了6_DOPS、8_DOPS、14_DOPS和18_DOPS。

图1  

    一个几何对象X的K_DOPS的包围盒的计算可以通过X的顶点与固定方向集D中的各个方向的最大点积得到。使用这个蛮力计算法计算有n个顶点的多面体对象的K_DOPS可以在O(kn)时间内完成。

为了说明如何计算K_DOPS，我们来考虑一个如图2所示的二维三角形。