资源描述：
《碰撞检测中的K_DOPS算法的研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、碰撞检测中的K_DOPS算法的研究摘要KDOPS碰撞检测算法是一类重要的碰撞检测算法，本文从K_DOPS的定义、包围盒的选择与计算、包围盒树的构造等几个方面对K_DOPS算法进行研究，并给出一种快速碰撞检测算法并对该算法进行改进，提高算法的效率。关键词碰撞检测；KDOPS；包围盒树1引言碰撞检测问题在计算机图形学中有很长的研究历史，近年来，随着虚拟现实，分布交互仿真等技术的兴起，碰撞检测再一次成为研究的热点，精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感起着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞
2、检测提出了更高的要求。包围盒树［7］是解决碰撞检测问题的一种有效的方法，碰撞检测对包围盒树的构造有以下几方面的要求：尽可能平衡以使得树的高度比较低；树的所有结点的包围盒体积尽可能小；每个结点的所有子结点的包围盒的交集尽可能小。但虚拟环境中对象进入的口由性和不可预测性以及碰撞检测的实时性乂不允许我们在构造树时进行太复杂的优化，因此如何构造包圉盒树将直接影响到碰撞检测的效率。K.DOPS可以看作是AABB[5]的扩展，它不再是用三对平面来包围对象，而是使用了k/2对平面，正是因这这种扩展，它弥补了MBB紧密性差的缺点。因此，
3、K_DOPS是一种很好的包围盒类型。2KDOPS(DiscreteOrientationPolytopes)的定义DiscreteOrientationPolytopes(KDOPS)包围盒是一种多面体，它的面由一组半空间所确定，这些半空间的外法向是从k个固定的方向(DI,D2,・・・Dk)中选取的[2][5]。设固定方向集K(D1,D2,...Dk),一元组(dl,d2,...dk)eRk其中：半空间在设计OOPS时，为使相关的耗费尽量小，通常只选择那些共线但方向完全相反的向量作为固定法向，因此，每个KDOPS实际上只
4、用到”2个方向，即KDOPS是一组半空间的集合，无论是在表示、存储还是计算屮都是十分不方便的，构成K.DOPS的任何一半空间都可以表示成不等式形式：由于集合D是
5、古I定不变的，可以用一个kXn矩阵来表示集合D,从而可以把kdops表示成如下形式：,其中由于方向是可预知的，所以存储每个KD0PS时无需保存方向,只需保存K个值即可，每个值对应一个平面的位置。而且当对两个K_D0PS做重叠测试时，只需要进行次测试，这种测试远比两个0BB或凸包间的重叠测试简单。3KD0PS的选择与计算3・1固定方向集的选择K_D0PS最简单的例
6、子是6.D0PS,其中6个面的法向分别由3个坐标轴的正负轴所决定，三维空间AABB轴向包围实际上是一种6.D0PS的特例。对于14_D0PS,其中除了沿用AABB的六个方向外，还增加了8个对角线的方向，以消除这些方向上可能存在的空缺。对于18.D0PS,其中除了沿MBB的6个方向外，还加入了指向AABB的12条边的方向，以消除这些方向上可能存在的空缺。对于26D0PS,则沿14D0PS和18D0PS合起来的26个方向。图1中分别列举了6DOPS、8_D0PS、14D0PS和18D0PS。图13.2K_D0PS的计算一个儿
7、何对象X的K.DOPS的包围盒的计算可以通过X的顶点与固定方向集D中的各个方向的最大点积得到。使用这个蛮力计算法计算有n个顶点的多面体对象的K_DOPS可以在0(如)时间内完成。为了说明如何计算KDOPS,我们来考虑一个如图2所示的二维三角形。图2图2给出了一个简单的二维空间中的例子，设D={±(1,0),±(0,1),±(1,1),±(1,-1)},X是一个三角形，顶点坐标分别为(2,1),(6,2)和(4,6)o我们可以通过依次计算三角形三个顶点和D中的方向向量的点积计算这个三角形的K_DOPSo例如，为找到方向(1
8、,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的KD0PS为(6,2,6,1,10,3,6,-2)。这个过程可以很容易地修改为用于计算复杂的对象的K_D0PSo4构造BV-tree包围盒树由K_D0PS的定义和计算可知，固定方向凸
9、包是一类比较简单的儿何体，它从k个方向上形成对对象的较为紧密的包围。一个复杂的对象是由成千上万个基本几何元素组成的，通过把它们的包围盒组织成层次结构可以逐渐逼近对象，以获得尽可能完善的几何特性。3.1包围盒树对给定的n个基本几何元素的集合S,定义S上的包围盒层次结构BVT(S)为一•棵树，简称包围盒树，它具有以下性质
