碰撞检测中的KDOPS算法的研究

1、碰撞检测中的K_DOPS算法的研究摘要K_DPS碰撞检测算法是一类紧张的碰撞检测算法，本文从K_DPS的界说、包抄盒的选择与盘算、包抄盒树的布局等几个方面临K_DPS算法举行研究，并给出一种快速碰撞检测算法并对该算法举行革新，进步算法的服从。关键词碰撞检测；K_DPS；包抄盒树碰撞检测题目在盘算机图形学中有很长的研究汗青，比年来，随着假造实际，漫衍交互仿真等技能的鼓起，碰撞检测再一次成为研究的热门，准确的碰撞检测对进步假造环境的真实性、加强假造环境的沉醉感起着至关紧张的作用，而假造环境自身的庞大性和及时性对碰撞检测提出了更高的要求。包抄盒树7是办理碰撞检测题目的一种有用的要领，碰撞检测对包抄盒

2、树的布局有以下几方面的要求：尽大概平衡以使得树的高度比力低；树的全部结点的包抄盒体积尽大概小；每个结点的全部子结点的包抄盒的交集尽大概校但假造环境中工具进入的自由性和不成猜测性以及碰撞检测的及时性又不容许我们在布局树时举行太庞大的优化，因此怎样布局包抄盒树将直接影响到碰撞检测的服从。K_DPS可以看作是AABB5的扩展，它不再是用三对平面来包抄工具，而是利用了k/2对平面，正是因这这种扩展，它补充了AABB精细性差的缺点。因此，K_DPS是一种很好的包抄盒范例。DisreterientatinPlytpes(K_DPS)包抄盒是一种多面体，它的面由一组半空间所确定，这些半空间的外法向是从k个结

3、实的标的目的D1，D2，.Dk中拔取的25。设结实标的目的集KD1，D2，.Dk，一元组d1，d2，.dkRk此中：半空间在方案K_DPS时，为使相干的泯灭只管小，通常只选择那些共线但标的目的完全相反的向量作为结实法向，因此，每个K_DPS实际上只用到k/2个标的目的，即K_DPS是一组半空间的聚集，无论是在表现、存储照旧盘算中都是非常不便利的，构成K_DPS的任何一半空间都可以表现成不等式情势：由于聚集D是结实稳定的，可以用一个kn矩阵来表现聚集D，从而可以把k_dps表现成如下情势：，此中由于标的目的是可预知的，以是存储每个K_DPS时无需保存标的目的，只需保存K个值即可，每个值对应一个平

4、面的位置。并且当对两个K_DPS做重叠测试时，只必要举行次测试，这种测试远比两个BB或凸包间的重叠测试简朴。3.1结实标的目的集的选择K_DPS最简朴的例子是6_DPS，此中6个面的法向别离由3个坐标轴的正负轴所决定，三维空间AABB轴向包抄实际上是一种6_DPS的特例。对付14_DPS，此中除了相沿AABB的六个标的目的外，还增长了8个对角线的标的目的，以消除这些标的目的上大概存在的空缺。对付18_DPS，此中除了沿AABB的6个标的目的外，还参加了指向AABB的12条边的标的目的，以消除这些标的目的上大概存在的空缺。对付26_DPS，那么沿14_DPS和18_DPS合起来的26个标的目的。

5、图1中别离枚举了6_DPS、8_DPS、14_DPS和18_DPS。图13.2K_DPS的盘算一个多少工具X的K_DPS的包抄盒的盘算可以通过X的极点与结实标的目的集D中的各个标的目的的最大点积得到。利用这个蛮力盘算法盘算有n个极点的多面体工具的K_DPS可以在(kn)时间内完成。为了说明怎样盘算K_DPS，我们来思量一个如图2所示的二维三角形。图2图2给出了一个简朴的二维空间中的例子，设D=(1，0)，(0，1)，(1，1)，(1，-1)，X是一个三角形，极点坐标别离为(2，1)，(6，2)和(4，6)。我们可以通过依次盘算三角形三个极点和D中的标的目的向量的点积盘算这个三角形的K_DPS。

6、比方，为寻到标的目的(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_DPS为(6，2，6，1，10，3，6，-2)。这个历程可以很轻易地修改为用于盘算庞大的工具的K_DPS。由K_DPS的界说和盘算可知，结实标的目的凸包是一类比力简朴的多少体，它从k个标的目的上形成对工具的较为精细的包抄

7、。一个庞大的工具是由成千上万个根本多少元素构成的，通过把它们的包抄盒构造成条理布局可以渐渐迫近工具，以得到尽大概美满的多少特性。4.1包抄盒树对给定的n个根本多少元素的聚集S，界说S上的包抄盒条理布局BVT(S)为一棵树，简称包抄盒树，它具有以下性子1346：树中的每个结点v对应于S的一个子集Sv(SvS)；与每个结点v相干联的另有聚集Sv的包抄盒bSv；根结点对应全集S和S的包抄盒bS；树中的每个内部结点非叶结点有两个以上的子结点，内部结点的最大子结点数称作度，记为；结点的全部子结点所对应的根本多少元素的子聚集构成了对所对应的根本多少元素的子集Sv的一个分别。4.2布局要领从输入多少元聚集S

8、上布局一棵BV_tree可接纳两种要领：自顶向下和自底向上。1自底向上要领该要领是从聚集S的根本多少元素动身，每个元素对应一个叶节点，然后利用任何局部信息递归地对它们举行分组归并，形成父节点，直到得到一个单一的根节点(即聚集S)，这一要领就是怎样把多少个聚集归并为一个父集。这个要领的一个典范的例子是Barequet等人的“BXTREE。2自顶向下要领自顶向下要领是从一个迫近S的节点开始，利用整个聚集的性子递归的分别节点，直至到达叶结点，BBTree是这个要领的一个典范的例子。自顶向下要领的焦点是怎样把一个聚集分别成多少个不相交的子集，而自底向上要领的焦点是怎样把多少个聚集归并为一个父集。很难说

9、得出这两种要拥有什么优劣之分，相对而言，自顶向下的要领在碰撞检测中利用得较多，技能更成熟一些，也比自底向上的要领更为结实更易实现，故我们接纳这一要领布局包抄盒树。假定已别离为一静态环境工具E和一运开工具F创立了包抄盒树状条理模子简称为包抄盒树。在包抄盒树中，每个结点上的包抄盒都对应于构成该工具的根本多少元素聚集的一个子集，根结点为整个工具的包抄盒。碰撞检测算法的焦点就是通过有用的遍历这两棵树，以确定在当前位置下，运开工具的某些部门是否与环境工具的某些部门产生碰撞。这是一个双重遍历的历程。算法起首用运开工具包抄盒树的根结点遍历环境工具包抄盒树，假设能到达叶结点，再用该叶结点遍历运开工具的包抄盒树

10、。假设能到达运开工具的叶结点，那么进一步举行根本多少元素的相交测试7。其根本头脑是利用多少特性简朴的包抄盒取代庞大的多少工具举行相交测试，假设两个结点上的包抄盒不相交，那么它们所包抄的工具的根本多少元素的子集肯定不相交，从而不必要对子会合的元素做进一步的相交测试。下面我们简朴给出基于包抄盒树的碰撞检测算法8。它重要由一个递归调用函数Traverse(vE，vF)构成，vF为运开工具包抄盒树中的当前结点，vE为环境工具包抄盒树中的当前结点。算法的原始输入为运开工具包抄盒树的根结点F和环境工具包抄盒树的根结点E。和别离为结点vE和vF所对应的根本多少元素的子集，和别离为它们的包抄盒。算法1：Tra

11、verse(vE，vF)1Ifthen2IfvE是叶结点then3IfvF是叶结点then4Fr中的每一个根本元素5Fr中的每一个根本元素6Ifthen7Return碰撞8EndIf9EndFr10EndFr11Else12FrvF中的每一个结点vF13Traverse(vE，vF)14EndFr15EndIf16Else17FrvE中的每一个结点ve18Traverse(ve，vF)19Endfr20EndIf21EndIf算法的开销重要在于包抄盒bSE和bSF间的相交测试，假设它们不相交，那么可以竣事本次调用。不然，假设vE不是叶结点，那么我们在环境工具树中继承向下一层，为vE的每个孩子v

12、e递归调用Traverse(vE，vF)。假设vE是叶结点，那么我们查抄vF是否为叶结点，假设是，那么我们在vE的每个根本多少元素和vF的每个根本多少元素间举行根本多少元素间的相交测试如，三角形与三角形间的相交测试、三角形与四周体间的相交测试等；不然，我们在运开工具树中继承向下一层，为vF的每个孩子vf递归调用Traverse(vf，vE)。在这里，我们之以是先用运开工具的根结点遍历环境工具树，重要是由于通常环境下环境工具比运开工具更大更庞大一些比方手术刀无论是巨细照旧庞大度都小于人体构造，如许做可以快速地定位运开工具在环境中的位置，较早地去除与运开工具不相交的部门；假设先用环境工具的根结点遍

13、历运开工具树，每每会增长包抄盒相交测试的次数。思量下面这种极度环境，当运开工具完全置身于一个很大的环境工具中时，那么当环境工具的根结点遍历运开工具树时，不会有任何包抄盒不相交的时机。下面临上述算法的革新，对17，18，19举行修改17)IfvF是叶结点then18)FrvE的每一个子结点ve19)Traverse(ve，vF)20)Endfr21)else22)Fr的每一个子结点ve23)Fr的每一个子结点vf24)Traverse(ve，vf)25)Endfr26)Endfr27)Endif这种算法的长处是在遍历历程中环境工具树和运开工具树能同时到达叶结点，低落了纵向搜刮的深度，但同时也加大的横向搜刮的幅度。对付环境工具与运开工具巨细靠近且碰撞麋集的环境，其性能有显着的进步。基于K_DPS包抄盒条理布局的碰撞检测要领，其关键是K_DPS的盘算及BV_TREE的布局，另有就是对环境工具包抄盒树和运开工具包抄盒树的遍历历程中，对传统的碰撞检测算法举行了革新，使环境工具树和运开工具树能同时到达叶结点，低落了纵向搜刮的深度，显着地进步了搜刮服从。3yszKskiK，etal。Fastllisindetetinbeteenput