碰撞检测中的KDOPS算法论文

　　摘要KDOPS碰撞检测算法是一类重要的碰撞检测算法，本文从KDOPS的定义、包围盒的选择与计算、包围盒树的构造等几个方面对KDOPS算法进行研究，并给出一种快速碰撞检测算法并对该算法进行改进，提高算法的效率。
　　关键词碰撞检测；KDOPS；包围盒树
　　1引言
　　碰撞检测问题在计算机图形学中有很长的研究历史，近年来，随着虚拟现实，分布交互仿真等技术的兴起，碰撞检测再一次成为研究的热点，精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感起着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求。
　　包围盒树〔7〕是解决碰撞检测问题的一种有效的方法，碰撞检测对包围盒树的构造有以下几方面的要求：尽可能平衡以使得树的高度比较低；树的所有结点的包围盒体积尽可能小；每个结点的所有子结点的包围盒的交集尽可能小。但虚拟环境中对象进入的自由性和不可预测性以及碰撞检测的实时性又不允许我们在构造树时进行太复杂的优化，因此如何构造包围盒树将直接影响到碰撞检测的效率。
　　KDOPS可以看作是AABB〔5〕的扩展，它不再是用三对平面来包围对象，而是使用了k2对平面，正是因这这种扩展，它弥补了AABB紧密性差的缺点。因此，KDOPS是一种很好的包围盒类型。
　　2KDOPS（DiscreteOrientationPolytopes）的定义
　　DiscreteOrientationPolytopes（KDOPS）包围盒是一种多面体，它的面由一组半空间所确定，这些半空间的外法向是从k个固定的方向（D1，D2，。。。Dk）中选取的〔2〕〔5〕。
　　设固定方向集K（D1，D2，。。。Dk），一元组（d1，d2，。。。dk）Rk
　　其中：
　　半空间
　　在设计KDOPS时，为使相关的耗费尽量小，通常只选择那些共线但方向完全相反的向量作为固定法向，因此，每个KDOPS实际上只用到k2个方向，即
　　KDOPS是一组半空间的集合，无论是在表示、存储还是计算中都是十分不方便的，构成KDOPS的任何一半空间都可以表示成不等式形式：
　　由于集合D是固定不变的，可以用一个kn矩阵来表示集合D，从而可以把kdops表示成如下形式：
　　其中由于方向是可预知的，所以存储每个KDOPS时无需保存方向，只需保存K个值即可，每个值对应一个平面的位置。而且当对两个KDOPS做重叠测试时，只需要进行次测试，这种测试远比两个OBB或凸包间的重叠测试简单。
　　3KDOPS的选择与计算3。1固定方向集的选择
　　KDOPS最简单的例子是6DOPS，其中6个面的法向分别由3个坐标轴的正负轴所决定，三维空间AABB轴向包围实际上是一种6DOPS的特例。
　　对于14DOPS，其中除了沿用AABB的六个方向外，还增加了8个对角线的方向，以消除这些方向上可能存在的空缺。
　　对于18DOPS，其中除了沿AABB的6个方向外，还加入了指向AABB的12条边的方向，以消除这些方向上可能存在的空缺。
　　对于26DOPS，则沿14DOPS和18DOPS合起来的26个方向。
　　图1中分别列举了6DOPS、8DOPS、14DOPS和18DOPS。
　　3。2KDOPS的计算
　　一个几何对象X的KDOPS的包围盒的计算可以通过X的顶点与固定方向集D中的各个方向的最大点积得到。使用这个蛮力计算法计算有n个顶点的多面体对象的KDOPS可以在O（kn）时间内完成。
　　为了说明如何计算KDOPS，我们来考虑一个如图2所示的二维三角形。
　　图2给出了一个简单的二维空间中的例子，设D｛（1，0），（0，1），（1，1），（1，1）｝，X是一个三角形，顶点坐标分别为（2，1），（6，2）和（4，6）。我们可以通过依次计算三角形三个顶点和D中的方向向量的点积计算这个三角形的KDOPS。例如，为找到方向（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的KDOPS为（6，2，6，1，10，3，6，2）。这个过程可以很容易地修改为用于计算复杂的对象的KDOPS。
　　4构造BVtree包围盒树
　　由KDOPS的定义和计算可知，固定方向凸包是一类比较简单的几何体，它从k个方向上形成对对象的较为紧密的包围。一个复杂的对象是由成千上万个基本几何元素组成的，通过把它们的包围盒组织成层次结构可以逐渐逼近对象，以获得尽可能完善的几何特性。
　　4。1包围盒树
　　对给定的n个基本几何元素的集合S，定义S上的包围盒层次结构BVT（S）为一棵树，简称包围盒树，它具有以下性质〔1〕〔3〕〔4〕〔6〕：
　　树中的每个结点v对应于S的一个子集Sv（SvS）；
　　与每个结点v相关联的还有集合Sv的包围盒b（Sv）；
　　根结点对应全集S和S的包围盒b（S）；
　　树中的每个内部结点（非叶结点）有两个以上的子结点，内部结点的最大子结点数称作度，记为；
　　结点的所有子结点所对应的基本几何元素的子集合构成了对所对应的基本几何元素的子集Sv的一个划分。
　　4。2构造方法
　　从输入几何元集合S上构造一棵BVtree可采用两种方法：自顶向下和自底向上。
　　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）Ifthen
　　2）IfvE是叶结点then
　　3）IfvF是叶结点then
　　4）For中的每一个基本元素
　　5）For中的每一个基本元素
　　6）Ifthen
　　7）Return碰撞
　　8）EndIf
　　9）EndFor
　　10）EndFor
　　11）Else
　　12）ForvF中的每一个结点vF
　　13）Traverse（vE，vF）
　　14）EndFor
　　15）EndIf
　　16）Else
　　17）ForvE中的每一个结点ve
　　18）Traverse（ve，vF）
　　19）Endfor
　　20）EndIf
　　21）EndIf
　　算法的开销主要在于包围盒b（SE）和b（SF）间的相交测试，如果它们不相交，则可以结束本次调用。否则，如果vE不是叶结点，则我们在环境对象树中继续向下一层，为vE的每个孩子ve递归调用Traverse（vE，vF）。如果vE是叶结点，则我们检查vF是否为叶结点，如果是，则我们在vE的每个基本几何元素和vF的每个基本几何元素间进行基本几何元素间的相交测试（如，三角形与三角形间的相交测试、三角形与四面体间的相交测试等）；否则，我们在活动对象树中继续向下一层，为vF的每个孩子vf递归调用Traverse（vf，vE）。
　　在这里，我们之所以先用活动对象的根结点遍历环境对象树，主要是因为通常情况下环境对象比活动对象更大更复杂一些（例如手术刀无论是大小还是复杂度都小于人体组织），这样做可以快速地定位活动对象在环境中的位置，较早地排除与活动对象不相交的部分；如果先用环境对象的根结点遍历活动对象树，往往会增加包围盒相交测试的次数。考虑下面这种极端情况，当活动对象完全置身于一个很大的环境对象中时，则当环境对象的根结点遍历活动对象树时，不会有任何包围盒不相交的机会。
　　下面对上述算法的改进，对17，18，19进行修改
　　17）IfvF是叶结点then
　　18）ForvE的每一个子结点ve
　　19）Traverse（ve，vF）
　　20）Endfor
　　21）else
　　22）For的每一个子结点ve
　　23）For的每一个子结点vf
　　24）Traverse（ve，vf）
　　25）Endfor
　　26）Endfor
　　27）Endif
　　这种算法的优点是在遍历过程中环境对象树和活动对象树能同时到达叶结点，降低了纵向搜索的深度，但同时也加大的横向搜索的幅度。对于环境对象与活动对象大小接近且碰撞密集的情况，其性能有明显的提高。
　　6结论
　　基于KDOPS包围盒层次结构的碰撞检测方法，其关键是KDOPS的计算及BVTREE的构造，还有就是对环境对象包围盒树和活动对象包围盒树的遍历过程中，对传统的碰撞检测算法进行了改进，使环境对象树和活动对象树能同时到达叶结点，降低了纵向搜索的深度，明显地提高了搜索效率。
　　参考文献
　　〔1〕J。Canny。CollisionDetectionforMovingPolyhedra。IEEETrans。PatternAnal。Mach。Intel。1986，8（2）：200209
　　〔2〕A。Smith，Y。Kitamura，H。Takemura，F。Kishino。ASimpleEfficientMethodforAccurateCollisionDetectionAmongDeformablePolyhedralObjectsinArbitraryMotion。ProceedingsoftheIEEEVirtualRealityAnnualInternationalSymposium，pp。136145，1995。2
　　〔3〕MyszKowskiK，etal。Fastcollisiondetectionbetweencomputersolidsusingrasterizinggraphicshardware〔J〕TheVisualComputer，19951l（9）；497511
　　〔4〕Hubbard，P。M。Approximatingpolyhedralwithspheresfortimecriticalcollisiondetection。ACMTransactionsonGraphics，1996，15（3）：179210
　　〔5〕VanDenBergen，EfficientcollisiondetectionofcomplexdeformablemodelsusingAABBtrees。JournalofGraphicsTools。1997，2（4）：114
　　〔6〕JamesT。Klosowiski。EfficientCollisionDetectionUsingBoundingVolumeHierarchiesofkDops，IEEETransactionsonVisualizationandComputerGraphics，Vol。4，No。1，1998
　　〔7〕王志强，洪嘉振，杨辉。碰撞检测问题研究综述。软件学报，1999，10（5）：545551
　　〔8〕魏迎梅，吴泉源，石教英。。碰撞检测中的固定方向凸壳包围盒的研究。软件学报，2001