基于Sphere和OBB混合的碰撞检测算法

来源 :软件 | 被引量 : 0次 | 上传用户:k413287823
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘 要 层次包围盒是碰撞检测中常用的方法。实现了一种混合使用Sphere和OBB两种包围盒的碰撞检测算法,这种算法在包围盒树的上层使用Sphere,下层使用OBB,吸取了Sphere构造简单,相交测试简单以及OBB紧密性好的优点,可以快速排除没有发生碰撞的对象,在对象发生旋转之后仅需要对下层OBB部分进行相应旋转。通过灵活选择不同层次的数量,可以适用于不同的虚拟场景。通过模拟两辆汽车碰撞的实验,证明了算法在检测速度上优于仅适用OBB的RAPID算法。
  关键词 碰撞检测;层次包围盒;包围球
  中图分类号 TP391 文献标识码 A
  Collision detection algorithm based on the mix of Sphere and OBB
  Wen Wei-wei Fan Li-jun Bai Yun-fei
  (College Of Computer Science, South-central University For Nationalities, Wuhan 430074, China)
  【Abstract】 Hierarchical bounding volume is commonly used method in collision detection. We mix Sphere and OBB to achieve a collision detection algorithm, which uses Sphere in the upper layers of the tree of bounding volume, the lower use of OBB. It learns from Sphere the advantage of simple structure and simple intersection test, learns from OBB the advantage of good tightness, after the object is rotated only need to rotate the corresponding part of lower OBB. Through the flexibility to choose the number of different levels, this algorithm can be applied to different virtual scenes. The experiment simulated two cars collided show that the algorithm is superior in the detection rate than RAPID which only uses OBB.
  【Keywords】 Collision detection ; Hierarchical bounding volume ; bounding sphere
  
  1 引言
  碰撞检测是虚拟现实中的一项关键技术,碰撞检测的目的是针对空间中的两个不可穿透的物体不能共享相同的空间区域这个事实,检测它们是否发生碰撞并产生报告[1]。在通过模拟现实场景生成的虚拟现实场景中,为了给用户带来更强烈更真实的沉浸感,有必要在虚拟现实技术中实现碰撞检测(Collision Detection),以提高虚拟系统的真实性。
  近年来,层次包围盒技术在碰撞检测中得到了广泛的应用,它的基本思想是使用简单的几何包围体来代替复杂的几何体,先对物体的包围盒进行粗略检测,当包围盒相交时其包围的几何体才有可能相交;若包围盒不相交,其包围的几何体一定不相交。常用的包围盒类型包括包围球(Sphere)[2],轴向包围盒AABB(Axis-Aligned Bounding Boxes)[3],沿任意方向包围盒OBB(Oriented Bounding Boxes)[4],离散方向多面体k-dop(K-Direction Orientation Polytopes)[5]等。目前没有一种包围盒可以在任意场景下达到最佳的检测效果,本文将包围球构造与检测简单的特性与OBB的紧密性相结合,提出一种灵活的混合层次包围盒算法。
  2 层次包围盒
  2.1 包围盒层次结构
  虚拟空间中的几何对象是由多个基本几何元素组成的,该对象的包围盒就是包含该对象的一个简单的几何体,利用这个简单的几何体代替原来的几何对象作一些近似的原始计算[6]。图1为二维空间中包围盒为圆形的例子,由此可见我们建立层次包围盒的过程就是建立一个度为2的树,根结点为所有组成对象的几何元素的集合S的包围盒,再将这个集合分为两部分分别建立它们的包围盒,即为根结点的孩子,递归建立到包围盒包围的集合只有一个基本几何元素的时候即到达叶子结点。
  对两个物体的碰撞检测即为对他们的包围盒树进行交叠测试的过程,对包围盒树A和B,若A中结点经测试与B中某结点不相交,则与B中该结点的子结点都不相交,若A得结点可以遍历至B中的叶子结点,再用该叶子结点对树A进行遍历,若也可遍历至A的叶子结点,则对这两个叶子结点进行更进一步的基本几何元素检测,以获得发生碰撞的具体信息。
  基于层次包围盒的碰撞检测算法代价公式为:
   (1)
  其中T是碰撞检测的总代价,Nv 代表需要进行包围盒间相交测试的对数,Cv代表进行一对包围盒相交测试的代价,Np代表需要进行基本几何元素相交测试的对数,Cp代表进行一对基本几何元素测试的代价,Nu代表当对象发生旋转后需要更新的包围盒的数目,Cu代表更新一个包围盒需要的代价,Cd代表当对象变形后更新包围盒树所需要的代价。下面对本文所使用的两种包围盒进行介绍。
  2.2 包围球Sphere
  包围球(Spheres)是包含对象的最小体积的球体。描述一个包围球仅仅需要两个变量——半径和球心,因此包围球的构造十分简单,同样对于包围球的相交测试也相对比较简单。这里假设两个包围球球心分别为(a1,a2),(a3,a4),半径分别为r1,r2,只需要比较两个球心的距离和半径的和的大小就可以判断是否发生了碰撞。即判断:
   (2)
  公式(2)成立则发生碰撞。
  在对象发生旋转以后,并不需要对对象的包围球作出更新,包围球的优点是构造与检测快速,能够快速排除对象不相交的情况,缺点是紧密性不好。
  2.3 沿任意方向包围盒OBB
  对象的OBB是包含该对象且相对于坐标轴方向任意的最小的长方体。它的最大特点是方向的任意性,从而可以根据对象的形状尽可能紧密的包围物体,具有较好的紧密性。
  计算对象的OBB关键在于寻找包围盒的最佳方向,然后再确定在该方向上包围盒的尺寸。首先,必须计算出物体的凸壳,这可以用类似于QuickHull[7]这样的算法来实现。假设可以得到N个三角形,记做Δpkqkrk,其中pk、qk、rk分别是三角形k的三个顶点,可以将三角形的面积记作Ak,三角形i的质心为:
   (3)
  整个凸壳的质心就是所有三角形质点的加权平均值:
   (4)
  然后计算3×3协方差矩阵C,其特征向量就是所求包围盒的方向向量:
   (5)
  协方差矩阵C的三个特征向量是正交的,将其正规化后这些向量就是OBB的三个方向向量,找到OBB的中心及其半长,可以将凸壳上的点投影到方向向量的方向上,找到每个方向上的最大值和最小值,这几个值就决定了包围盒的大小和位置。
  OBB包围盒的构造较为复杂,相交测试也较为复杂,OBB间的相交测试是基于分离轴理论的。如果在空间中存在一个向量使得两个OBB在这个向量上的投影不相交,那么这个向量就是一个分离轴,如果两个OBB在空间中存在一个分离轴,那么这两个OBB不相交。对于一对OBB,最多存在15个潜在的分离轴,其中6条为两个OBB的方向向量,另外9条是两个OBB方向向量的两两叉乘的结果。
  利用分离轴进行相交测试的方法如图2所示,向量T是A的中心到B的中心的距离,单位向量L是一个分离轴,ra、rb分别是A、B在L上的投影半径,有公式:
  满足公式(5)则可以判定两个OBB不相交,否则继续对余下的分离轴进行判定,如果所有分离轴都不能满足这个条件,那么两个OBB相交。
  3 混合层次包围盒算法
  3.1 算法的基本思想
  我们将传统的单一种类包围盒树进行改进,在包围盒树的上层(A层),选择Sphere作为包围盒,在包围盒树的下层(B层)选择OBB作为包围盒。选择在上层使用Sphere是考虑到Sphere在对象发生旋转后不需要更新,并且相交测试容易进行,可以快速排除没有发生碰撞的对象。下层选择OBB作为包围盒,是由于之前对上层的测试使得检测的对象越来越逼近原始对象,在这种情况下使用OBB保证了在对象实际发生了碰撞时检测的精确度。
  在建立包围盒树的过程中,选择树的度为2.。对于包围球的建立,我们首先建立三角形集合的轴向包围盒,以此包围盒的中心为球心,再遍历三角形的每个顶点得到到球心的最大距离即为包围球的半径。OBB的建立方法则采用上述章节(2.3节)描述的建立OBB的方法。在A层和B层中,我们对集合的划分都采用包围盒的最长轴为分裂轴进行划分。
  在进行包围盒树相交测试的过程中,首先判断进行相交测试的两个包围盒分别位于包围盒树的哪个层次,如果都位于A层则进行Sphere-Sphere相交测试,如果都位于B层则进行OBB-OBB相交测试,如果处于不同层次则进行Sphere-OBB相交测试,Sphere与OBB的相交测试算法如下:
  Sphere与OBB的相交测试仍然采用分离轴理论,这里潜在的分离轴只有三条,就是OBB的三个方向向量。T为OBB中心到圆心的距离,L为一个分离轴,ra为包围盒A在L上的投影半径,rb为T在球内的部分在L上的投影,有以下公式:
  公式(6)成立则表明OBB与Sphere不相交,否则继续针对下一条分离轴利用此公式进行判断,如果所有分离轴都不能将它们分离,那么OBB与Sphere相交。
  3.2 相交测试的流程
  空间中两个对象的相交测试是碰撞检测的核心部分,相交测试从两个对象A,B的根结点开始。首先,确定两个节点在各自包围盒树里所属的层次,如果都属于上层,则执行Collide_Sphere_Sphere(A,B),如果都属于下层,则执行Collide_Obb_Obb(A,B),如果A属于上层,B属于下层,执行Collide_Sphere_Obb(A,B),否则执行Collide_Sphere_Obb(B,A),如果A与B不相交,那么它们的子节点都不相交,如果A和B相交,则判断A和B是不是叶子节点,如果不是,则选择A或B的孩子节点继续执行上述步骤,如果A和B都是叶子结点,则进行基本几何元素的相交测试,这里基本几何元素假设为三角形,则进行三角形的相交测试。算法的流程如下:
  Collide_recursive(A,B)
  {
  1) 确定A和B所在层次;
  2) If(A∈上层且B∈上层);
  3) Coliide_Sphere_Sphere(A,B);
  4) Else if(A∈下层且B∈下层)
  5) Collide_Obb_Obb(A,B);
  6) Else if(A∈上层且B∈下层)
  7) Collide_Sphere_Obb(A,B);
  8) Else Collide_Sphere_Obb(B,A);
  9) If(A与B相交)
   {
  10) If(A是叶子节点)
   {
  11) If(B是叶子节点)
  12) Retrun Collide_tri_tri(A,B);
  13) Else B=取叶子节点(B);
   }
  14) Else A=取叶子节点(A);
   }
  15) Collide_recursive(A,B);
   }
   16)Else Return False;
   }
  5 实验结果与分析
  使用VC8.0与OpenGL在PC机(Inter Core 3.00GHz,ATI HD4650,2GB内存)上实现了本文算法。图4为模拟两辆车碰撞的场景。每辆车由33104个三角形面片组成。选择以OBB为包围盒的RAPID系统进行比较,它们在不同情况下的碰撞检测时间如表1所示。
  通过实验数据可以看出随着相交面片数量的增加,RAPID和本文算法处理碰撞检测的时间都在增加,在没有碰撞的情况下,由于本文算法在构造包围盒树的过程中相比RAPID增加了构造Sphere的步骤,因此耗费时间较大;在有相交面片的情况下,本文算法的效率要优于单纯以OBB为包围盒的RAPID系统,在最好的情况下可以提升大约1倍的速率。
  
  5 结束语
  碰撞检测对于提高虚拟环境的真实性和沉浸感有重要作用,本文利用了Sphere和OBB两种包围盒各自的优点提出了一种新的混合层次包围盒算法,在时间消耗上提高了碰撞检测的效率。迄今为止,没有任何一种包围盒可以完美的适用于任何虚拟场景,我们可以灵活的改变A层和B层的数量来达到适用于当前虚拟环境的结果。
  
  参考文献
  [1] 李德湘,彭斌.虚拟现实技术发展综述[J].技术与创新管理,2004,25(6):10-14.
  [2] P.M.Hubbard. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality, October 1993:24-31.
  [3] Zachmann G. Real-Time and Exact Collision Detection for Interactive Virtual Prototyping[C]. Proceeding of DETC’97, California ASME, 1997:90-97.
  [4] Gottschalk S, Lin M C, Manocha D. OBB-Tree A Hierarchical Structure for Rapid Interference Detection[C]. Proceeding of SIGGRAPH’96, New York: ACM Press, 1996: 171-180.
  [5] James T K losowski, Martin Held, Joseph S B Mitchell, et al. Efficient Collision Detection Using Bounding VolUme Hierarchies of k-DOPs[J]. IEEE Transactions on Visualization and Computer Graphics(S1077-2626), 1988,4(1): 21-36.
  [6] 潘振宽,崔树娟,张继萍,李建波. 基于层次包围盒的碰撞检测方法[J]. 青岛大学学报(自然科学版),2005,(3):71-76.
  [7] B.Barber, D.Dobkin, and H.Huhdanpaa. The quickhull algorithm for convex hulls. ACM Transaction on Mathematical Software(TOMS), 1996: 469-483.
  作者简介:文卫蔚(1988-),男,硕士研究生在读,主要从事图像处理和虚拟现实方面的研究。
其他文献
【正】 在实现党校教育正规化的过程中,如何与改革党校教育制度相适应,研究和改进教学方法,是党校工作者面临的重要课题。要回答这一问题,就要把备课、讲课和辅导这三个在教
在纪念中国共产党成立90周年之际,人民出版社推出了西北大学马克思主义学院教授、博士生导师梁星亮,西北大学马克思主义学院副院长、教授杨洪主编的专著《中国共产党延安时期政
【正】 从事伟大的事业要有伟大的精神。建设社会主义的物质文明需要愚公精神。端正党风、加强社会主义精神文明建设,同样需要愚公精神。愚公精神的可贵在于:胸有宏图,扎实奋
HB RV-187.5布洛维硬度计有多种负荷,压头和不同计量装置.主要用于洛氏硬度试验,也可以进行布氏、维氏硬度试验.在使用一段时间以后,有以下故障出现:无光源指示;标度尺刻线在
近日,中国机械工业联合会在哈尔滨市组织召开哈电集团哈尔滨锅炉厂有限责任公司(以下简称哈锅)“1000MW等级超超临界二次再热塔式锅炉研制及应用”项目成果鉴定会.
振动样品磁强计利用扬声强器作振源,用一套消振装置使系统稳定,整套装置能在x,y,z三方向可调。利用外磁场对振动样品磁化,以霍耳片检测外部磁场,由锁相电路检测感应信号,通过计算机采集
由我校教育部人文社会科学重点研究基地——中国西部经济发展研究中心主编,组织西部12所高校及科研院所共同研究撰写,全面反映西部经济发展状况的我国学术界首部《西部蓝皮书:中
【正】 1986年9月10日至14日在奥地利林茨召开了第二十一次工运史学者的国际会议,着重讨论了二次大战末期和战后初期工人运动的政治问题和社会问题。大会国际咨询委员会在学
【正】 学术是对客观世界的探讨。学术活动是人们认识客观世界的一种探索性活动,属于认识范畴。它的目的和任务在于追求真理,获得真理。学术自由是学术活动的一项基本原则,是
MATLAB是一种高度集成的计算机语言,它具有非常灵活的程序设计流程。本文充分利用MATLAB的优势,通过对影响脑卒中病的环境因素和相关数据进行分析,建立了一个多元回归模型,并对不