碰撞检测中的KDOPS算法论文

　　摘 要 K_DOPS碰撞检测算法是一类重要的碰撞检测算法，本文从K_DOPS的定义、包围盒的选择与计算、包围盒树的构造等几个方面对K_DOPS算法进行研究，并给出一种快速碰撞检测算法并对该算法进行改进，提高算法的效率。
　　关键词 碰撞检测；K_DOPS；包围盒树
　　1 引言
　　碰撞检测问题在计算机图形学中有很长的研究历史，近年来，随着虚拟现实，分布交互仿真等技术的兴起，碰撞检测再一次成为研究的热点，精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感起着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求。
　　包围盒树[7]是解决碰撞检测问题的一种有效的方法，碰撞检测对包围盒树的构造有以下几方面的要求：尽可能平衡以使得树的高度比较低；树的所有结点的包围盒体积尽可能小；每个结点的所有子结点的包围盒的交集尽可能小。但虚拟环境中对象进入的自由性和不可预测性以及碰撞检测的实时性又不允许我们在构造树时进行太复杂的优化，因此如何构造包围盒树将直接影响到碰撞检测的效率。
　　K_DOPS可以看作是AABB[5]的扩展，它不再是用三对平面来包围对象，而是使用了k/2对平面，正是因这这种扩展，它弥补了AABB紧密性差的缺点。因此，K_DOPS是一种很好的包围盒类型。
　　2 K_DOPS (Discrete Orientation Polytopes)的定义
　　Discrete Orientation Polytopes(K_DOPS)包围盒是一种多面体，它的面由一组半空间 所确定，这些半空间的外法向是从 k 个固定的方向（D1，D2，...Dk）中选取的[2] [5]。
　　设固定方向集K（D1，D2，...Dk） ，一元组 （d1，d2，...dk） Rk
　　其中：
　　半空间
　　在设计K_DOPS时，为使相关的耗费尽量小，通常只选择那些共线但方向完全相反的向量作为固定法向，因此，每个K_DOPS实际上只用到k/2个方向，即
　　K_DOPS是一组半空间的集合，无论是在表示、存储还是计算中都是十分不方便的，构成K_DOPS的任何一半空间都可以表示成不等式形式：
　　由于集合D 是固定不变的，可以用一个 k n矩阵来表示集合 D，从而可以把k_dops表示成如下形式：
　　其中由于 方向是可预知的，所以存储每个K_DOPS时无需保存方向，只需保存K个值即可，每个值对应一个平面的位置。而且当对两个K_DOPS做重叠测试时，只需要进行 次测试，这种测试远比两个OBB或凸包间的重叠测试简单。
　　3 K_DOPS的选择与计算3 .1 固定方向集的选择
　　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。
　　3.2 K_DOPS的计算
　　一个几何对象X的K_DOPS的包围盒的计算可以通过X的顶点与固定方向集D中的各个方向的最大点积得到。使用这个蛮力计算法计算有n个顶点的多面体对象的K_DOPS可以在O(kn)时间内完成。
　　为了说明如何计算K_DOPS，我们来考虑一个如图2所示的二维三角形。
　　图2给出了一个简单的二维空间中的例子，设D = { (1，0)， (0，1)， (1，1)， (1，-1) }，X是一个三角形，顶点坐标分别为(2，1)，(6，2)和(4，6)。我们可以通过依次计算三角形三个顶点和D中的方向向量的点积计算这个三角形的K_DOPS。例如，为找到方向(1，1)上的.最大延伸，我们计算下面三个点积。
　　(1， 1) . (2， 1) = 3
　　(1， 1) . (4， 6) = 10
　　(1， 1) . (6， 2) = 8
　　最大值为10，故X在(1，1)上的最大延伸为10，值得注意的是，(-1，-1)是D中和(1，1)方向相反的向量，故X的顶点与(1，1)的点积的最小值即为X在(-1，-1)上的最大延伸。通过计算其它方向上的点积，可以得到X的K_DOPS为(6，2，6，1，10，3，6，-2)。这个过程可以很容易地修改为用于计算复杂的对象的K_DOPS。
　　4 构造BV-tree包围盒树
　　由K_DOPS的定义和计算可知，固定方向凸包是一类比较简单的几何体，它从k个方向上形成对对象的较为紧密的包围。一个复杂的对象是由成千上万个基本几何元素组成的，通过把它们的包围盒组织成层次结构可以逐渐逼近对象，以获得尽可能完善的几何特性。
　　4.1 包围盒树
　　对给定的 n个基本几何元素的集合S ，定义 S上的包围盒层次结构BVT(S )为一棵树，简称包围盒树，它具有以下性质[1] [3] [4] [6]：
　　①树中的每个结点v 对应于 S的一个子集Sv(Sv S) ；
　　②与每个结点v 相关联的还有集合 Sv的包围盒 b（Sv）；
　　③根结点对应全集S 和 S的包围盒b（S）；
　　④树中的每个内部结点（非叶结点）有两个以上的子结点，内部结点的最大子结点数称作度，记为 δ；
　　⑤结点ν 的所有子结点所对应的基本几何元素的子集合构成了对 ν所对应的基本几何元素的子集Sv 的一个划分。
　　4.2 构造方法
　　从输入几何元集合S上构造一棵BV_ tree可采用两种方法：自顶向下和自底向上。
　　1）自底向上方法
　　该方法是从集合S的基本几何元素出发，每个元素对应一个叶节点，然后利用任何局部信息递归地对它们进行分组归并，形成父节点，直到得到一个单一的根节点(即集合 S)，这一方法就是如何把若干个集合归并为一个父集。这个方法的一个典型的例子是Barequet等人的＂BOXTREE＂。
　　2）自顶向下方法
　　自顶向下方法是从一个逼近S的节点开始，利用整个集合的性质递归的划分节点，直至到达叶结点，OBBTree是这个方法的一个典型的例子。
　　自顶向下方法的核心是如何把一个集合划分成若干个不相交的子集，而自底向上方法的核心是如何把若干个集合归并为一个父集。很难说得出这两种方法有什么优劣之分，相对而言，自顶向下的方法在碰撞检测中使用得较多，技术更成熟一些，也比自底向上的方法更为健壮更易实现，故我们采用这一方法构造包围盒树。
　　5 碰撞检测算法及改进措施
　　假定已分别为一静态环境对象E和一活动对象F建立了包围盒树状层次模型（简称为包围盒树）。在包围盒树中，每个结点上的包围盒都对应于组成该对象的基本几何元素集合的一个子集，根结点为整个对象的包围盒。碰撞检测算法的核心就是通过有效的遍历这两棵树，以确定在当前位置下，活动对象的某些部分是否与环境对象的某些部分发生碰撞。这是一个双重遍历的过程。算法首先用活动对象包围盒树的根结点遍历环境对象包围盒树，如果能到达叶结点，再用该叶结点遍历活动对象的包围盒树。如果能到达活动对象的叶结点，则进一步进行基本几何元素的相交测试[7] 。其基本思想是利用几何特性简单的包围盒代替复杂的几何对象进行相交测试，如果两个结点上的包围盒不相交，则它们所包围的对象的基本几何元素的子集必定不相交，从而不需要对子集中的元素做进一步的相交测试。
　　下面我们简单给出基于包围盒树的碰撞检测算法[8]。它主要由一个递归调用函数 Traverse(vE，vF)组成，vF为活动对象包围盒树中的当前结点，vE为环境对象包围盒树中的当前结点。算法的原始输入为活动对象包围盒树的根结点F和环境对象包围盒树的根结点E。
　　和 分别为结点vE和vF所对应的基本几何元素的子集， 和 分别为它们的包围盒。
　　算法1：Traverse(vE，vF)
　　1） If then
　　2） If vE是叶结点 then
　　3） If vF是叶结点 then
　　4） For 中的每一个基本元素
　　5） For 中的每一个基本元素
　　6） If then
　　7） Return 碰撞
　　8） End If
　　9） End For
　　10） End For
　　11） Else
　　12） For vF中的每一个结点vF
　　13） Traverse(vE，vF)
　　14） End For
　　15） End If
　　16） Else
　　17） For vE中的每一个结点ve
　　18） Traverse(ve，vF)
　　19） End for
　　20） End If
　　21） End If
　　算法的开销主要在于包围盒 b（SE）和 b（SF）间的相交测试，如果它们不相交，则可以结束本次调用。否则，如果 vE不是叶结点，则我们在环境对象树中继续向下一层，为 vE的每个孩子 ve递归调用Traverse(vE，vF)。如果 vE是叶结点，则我们检查 vF是否为叶结点，如果是，则我们在 vE的每个基本几何元素和 vF的每个基本几何元素间进行基本几何元素间的相交测试（如，三角形与三角形间的相交测试、三角形与四面体间的相交测试等）；否则，我们在活动对象树中继续向下一层，为 vF的每个孩子vf 递归调用Traverse( vf， vE)。
　　在这里，我们之所以先用活动对象的根结点遍历环境对象树，主要是因为通常情况下环境对象比活动对象更大更复杂一些（例如手术刀无论是大小还是复杂度都小于人体组织），这样做可以快速地定位活动对象在环境中的位置，较早地排除与活动对象不相交的部分；如果先用环境对象的根结点遍历活动对象树，往往会增加包围盒相交测试的次数。考虑下面这种极端情况，当活动对象完全置身于一个很大的环境对象中时，则当环境对象的根结点遍历活动对象树时，不会有任何包围盒不相交的机会。
　　下面对上述算法的改进，对17，18，19进行修改
　　17) If vF是叶结点 then
　　18) ForvE 的每一个子结点ve
　　19) Traverse( ve，vF)
　　20) End for
　　21) else
　　22) For 的每一个子结点 ve
　　23) For 的每一个子结点 vf
　　24) Traverse( ve，vf)
　　25) End for
　　26) End for
　　27) End if
　　这种算法的优点是在遍历过程中环境对象树和活动对象树能同时到达叶结点，降低了纵向搜索的深度，但同时也加大的横向搜索的幅度。对于环境对象与活动对象大小接近且碰撞密集的情况，其性能有明显的提高。
　　6 结论
　　基于K_DOPS包围盒层次结构的碰撞检测方法，其关键是K_DOPS的计算及BV_ TREE的构造，还有就是对环境对象包围盒树和活动对象包围盒树的遍历过程中，对传统的碰撞检测算法进行了改进，使环境对象树和活动对象树能同时到达叶结点，降低了纵向搜索的深度，明显地提高了搜索效率。
　　参考文献
　　[1] J.Canny. Collision Detection for Moving Polyhedra. IEEE Trans. Pattern Anal. Mach. Intel. 1986，8(2)： 200-209
　　[2] A .Smith，Y.Kitamura，H.Takemura，F.Kishino. A Simple Efficient Method for Accurate Collision Detection Among Deformable Polyhedral Objects in Arbitrary Motion. Proceedings of the IEEE Virtual Reality Annual International Symposium，pp.136-145，1995.2
　　[3] MyszKowski K，et al。Fast collision detection between computer solids using rasterizing graphics hardware [J]The Visual Computer，1995 1l(9)；497-511
　　[4]Hubbard，P. M. Approximating polyhedral with spheres for time critical collision detection. ACM Transactions on Graphics，1996，15(3)：179210
　　[5]Van Den Bergen，Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools .1997，2 (4)：1-14
　　[6]James T.Klosowiski. Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops，IEEE Transactions on Visualization and Computer Graphics，Vol. 4，No. 1，1998
　　[7]王志强，洪嘉振，杨辉.碰撞检测问题研究综述.软件学报，1999，10 (5)： 545-551
　　[8]魏迎梅，吴泉源，石教英..碰撞检测中的固定方向凸壳包围盒的研究.软件学报，2001