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

[doc] 基于Sphere和OBB混合的碰撞检测算法 基于Sphere和OBB混合的碰撞检测算法 软件2011年第32卷第5期Software国际IT传媒品牌 基于Sphere和OBB混合的碰撞检测算法 文卫蔚范利君白云菲 (中南民族大学计算机科学学院,武汉430074) :层次包围盒是碰撞检测中常用的方法.实现了一种混合使用 摘要 Sphere和OBB两种包围盒的碰撞检测算法,这种算法在 包围盒树的上层使用Spherc,下层使用OBB,吸取了Sphere构造简单,相交测试简单以及OBB紧密性好的优点,可以快速排除没有 发生碰撞的对象,在对象发生旋转之后仅需要对下层OBB部分进行相应旋转.通过灵活选择不同昙次的数量,可以适用于不同的 虚拟场景.通过模拟两辆汽车碰撞的实验,证明了算法在检测速度上优于仅适用OBB的RAPID算法. 关键词:碰撞检测;层次包围盒;包围球 中图分类号:TP391文献标识码:ADOI:10.3969/j.issn.1003—6970.2011.05.006 CollisionDetectionAlgorithmBasedontheMixofSphereandOBB WENWei—wei,FANLi-jun,BAIYun—fei (CollegeOfCompute1Science,South—eenn~lUniversityForNationalities ,Wuhan430074,China) 【Abstract]Hierarchicalboundingvolumeiscommonlyusedmethodincollisiondetection.WemixSphereandOBBtoachievea collisiondetectionalgorithm,whichusesSphereintheupperlayersofthetreeofboundingvolume,theloweruseofOBB.Itlearnsfrom Spheretheadvantageofsimplestructureandsimpleintersectiontest,learnsfromOBBtheadvantageofgoodtightness,aftertheobject isrotatedonlyneedtorotatethecorrespondingpartoflowerOBB.Throughtheflexibilitytochoosethenumberofdifferentlevels.this algorithmcanbeappliedtodifferentvirtualscenes,TheexperimentsimulatedtWOcarscollidedshowthatthealgorithmissuperiorinthe deiectionratethanRAPIDwhichonlyusesOBB. [Keywords】 Collisiondetection;Hierarchicalboundingvolume;boundingsphere 0引言1层次包围盒 碰撞检测是虚拟现实中的一项关键技术,碰撞检测的目 的是针对空间中的两个不可穿透的物体不能共享相同的空间 区域这个事实,检测它们是否发生碰撞并产生 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 ….在通过 模拟现实场景生成的虚拟现实场景中,为了给用户带来更强 烈更真实的沉浸感,有必要在虚拟现实技术中实现碰撞检测 (CollisionDetection),以提高虚拟系统的真实性. 近年来,层次包围盒技术在碰撞检测中得到了广泛的应 用,它的基本思想是使用简单的几何包围体来代替复杂的几何 体,先对物体的包围盒进行粗略检测,当包围盒相交时其包围 的几何体才有可能相交;若包围盒不相交,其包围的几何体一 定不相交.常用的包围盒类型包括包围球(Sphere),轴向包 围盒AABB(Axis-AlignedBoundingBoxes),沿任意方向 包围盒OBB(OrientedBoundingBoxes),离散方向多面体 k-dop(K-DirectionOrientationPolytopes)等.目前没有 一 种包围盒可以在任意场景下达到最佳的检测效果,本文将包 围球构造与检测简单的特性与OBB的紧密性相结合,提出一 种灵活的混合层次包围盒算法. 1.1包围盒层次结构 虚拟空间中的几何对象是由多个基本几何元素组成的,该 对象的包围盒就是包含该对象的一个简单的几何体,利用这个 简单的几何体代替原来的几何对象作一些近似的原始计算吲. 图1为二维空间中包围盒为圆形的例子,由此可见我们建立层 次包围盒的过程就是建立一个度为2的树,根结点为所有组成 对象的几何元素的集合S的包围盒,再将这个集合分为两部分 分别建立它们的包围盒,即为根结点的孩子,递归建立到包围 盒包围的集合只有一个基本几何元素的时候即到达叶子结点. 图1包围盒层次结构示例 对两个物体的碰撞检测即为对他们的包围盒树进行交叠 测试的过程,对包围盒树A和B,若A中结点经测试与B中某 结点不相交,则与B中该结点的子结点部不相交,若A得结点 可以遍历至B中的叶子结点,再用该叶子结点对树A进行遍 作者简介:文卫蔚(1988一),男,硕士研究生在读,_丰要从事图像处理和虚拟现实方面的研究. ? 21? 软件文卫蔚,等:基于Sphere和OBB混合的碰撞检测算法 历,若也可遍历至A的叶子结点,则对这两个叶子结点进行更 进一步的基本几何元素检测,以获得发生碰撞的具体信息. 基于层次包围盒的碰撞检测算法代价公式为: r=--~×C+X+xCu-I-(1) 其中T是碰撞检测的总代价,N代表需要进行包围盒间 相交测试的对数,C代表进行一对包围盒相交测试的代价, 代表需要进行基本几何元素相交测试的对数,c代表进行一对 基本几何元素测试的代价,代表当对象发生旋转后需要更新 的包围盒的数目,代表更新一个包围盒需要的代价,代表 当对象变形后更新包围盒树所需要的代价.下面对本文所使 用的两种包围盒进行介绍. 1.2包围球Sphere 包围球(Spheres)是包含对象的最小体积的球体.描述 一 个包围球仅仅需要两个变量——半径和球心,因此包围球的 构造十分简单,同样对于包围球的相交测试也相对比较简单. 这里假设两个包围球球心分别为(a,a),(,口),半径分别为 r,,只需要比较两个球心的距离和半径的和的大小就可以判 断是否发生了碰撞.即判断: ?(a一)2+:一(/4)+(2) 公式(2)成立则发生碰撞. 在对象发生旋转以后,并不需要对对象的包围球作出更 新,包围球的优点是构造与检测快速,能够快速排除对象不相 交的情况,缺点是紧密性不好. 1.3沿任意方向包围盒OBB 对象的OBB是包含该对象且相对于坐标轴方向任意的最 小的长方体.它的最大特点是方向的任意性,从而可以根据对 象的形状尽可能紧密的包围物体,具有较好的紧密性. 计算对象的OBB关键在于寻找包围盒的最佳方向,然后 再确定在该方向上包围盒的尺寸.首先,必须计算出物体的凸 壳,这可以用类似于QuickHull这样的算法来实现.假设可 以得到N个三角形,记做?pkQyk,其中pk,q,rk分别是三角 形k的三个顶点,可以将三角形的面积记作A,三角形i的质 心为: =(?++ri)/3(3) 整个凸壳的质心就是所有三角形质点的加权平均值: H : 艺0 然后计算3X3协方差矩阵C,其特征向量就是所求包围 盒的方向向量: 一 】 c:【】:f?(9mfm~+pp+gg+)一/A](5)k=O1二 协方差矩阵C的三个特征向量是正交的,将其正规化后这 些向量就是OBB的三个方向向量,找到OBB的中心及其半长, 可以将凸壳上的点投影到方向向量的方向上,找到每个方向上 的最大值和最小值,这几个值就决定了包围盒的大小和位置. OBB包围盒的构造较为复杂,相交测试也较为复杂,OBB 间的相交测试是基于分离轴理论的.如果在空间中存在一个 向量使得两个OBB在这个向量上的投影不相交,那么这个向 量就是一个分离轴,如果两个OBB在空间中存在一个分离轴, 那么这两个OBB不相交.对于一对OBB,最多存在l5个潜在 的分离轴,其中6条为两个OBB的方向向量,另外9条是两个 OBB方向向量的两两叉乘的结果. 利用分离轴进行相交测试的方法如图2所示,向量T是A 的中心到B的中心的距离,单位向量L是一个分离轴,r口,rb分 别是A,B在L上的投影半径,有公式: I,?三I>ra+rh(6) lalb 图2一对OBB间的相交测试 满足公式(5)则可以判定两个OBB不相交,否则继续对余 下的分离轴进行判定,如果所有分离轴都不能满足这个条件, 那么两个OBB相交. 2混合层次包围盒算法 2.1算法的基本思想 我们将传统的单一种类包围盒树进行改进,在包围盒树的 上层(A层),选择Sphere作为包围盒,在包围盒树的下层(B 层)选择OBB作为包围盒.选择在上层使用Sphere是考虑到 Sphere在对象发生旋转后不需要更新,并且相交测试容易进 行,可以快速排除没有发生碰撞的对象.下层选择OBB作为 包围盒,是由于之前对上层的测试使得检测的对象越来越逼近 原始对象,在这种情况下使用OBB保证了在对象实际发生了 碰撞时检测的精确度. 在建立包围盒树的过程中,选择树的度为2.对于包围球 的建立,我们首先建立三角形集合的轴向包围盒,以此包围盒 的中心为球心,再遍历三角形的每个顶点得到到球心的最大距 离即为包围球的半径.OBB的建立方法则采用上述章节(2.3 节)描述的建立OBB的方法.在A层和B层中,我们对集合 的划分都采用包围盒的最长轴为分裂轴进行划分. 在进行包围盒树相交测试的过程中,首先判断进行相交测 试的两个包围盒分另IJ位于包围盒树的哪个层次,如果都位于A 层则进行Sphere—Sphere相交测试,如果都位于B层则进行 OBB一0BB相交测试,如果处于不同层次则进行Sphere-OBB 桕交测试,Sphere与OBB的相交测试算法如下: 软件文卫蔚,等:基于Sphere和OBB混合的碰撞检测算法 lals 图3OBB与Sphere的相交测试 Sphere与OBB的相交测试仍然采用分离轴理论,这里潜 在的分离轴只有三条,就是OBB的三个方向向量.T为OBB 中心到圆心的距离,L为一个分离轴,ra为包围盒A在L上的 投影半径,rb为T在球内的部分在L上的投影,有以下公式: l?I>+(7) 公式(6)成立则表明OBB与Sphere不相交,否则继续针 对下一条分离轴利用此公式进行判断,如果所有分离轴都不能 将它们分离,那么OBB与Sphere相交. 2.2相交测试的流程 空间中两个对象的相交测试是碰撞检测的核心部分,相 交测试从两个对象A,B的根结点开始.首先,确定两个节点 在各自包围盒树里所属的层次,如果都属于上层,则执行Col- lide—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都是叶子结点,则进行 基本几何元素的相交测试,这里基本几何元素假设为三角形, 则进行三角形的相交测试.算法的流程如下: CoUide— recursive(A,B) { 确定A和B所在层次; If(A?上层且B?上层); Coliide— Sphere—Sphere(A,B); Elseif(A?下层且B?下层) Collide— Obb—Obb(A,B); Elseif(A?上层且B?下层) Collide_ Sphere_Obb(A,B); ElseCollide_Sphere_Obb(B,A); If(A与B相交) { If(A是叶子节点) { If(B是叶子节点) RetrunCollide_ tri_tri(A,B); ElseB--取叶子节点(B); } ElseA=取叶子节点(A); } Colliderecursive(A,B); , 16)ElseReturnFalse; 3实验结果与分析 使用VC8.0与OpenGL在PC机(InterCore3.00GHz, ATIHD4650,2GB内存)上实现了本文算法.图4为模拟两 辆车碰撞的场景.每辆车由33104个三角形面片组成.选择 以OBB为包围盒的RAPID系统进行比较,它们在不同情况下 的碰撞检测时间如表l所示. 表1本文算法与RAPID的碰撞时间比较 通过实验数据可以看出随着相交面片数量的增加,RAPID 和本文算法处理碰撞检测的时间都在增加,在没有碰撞的情况 下,由于本文算法在构造包围盒树的过程中相比RAPID增加 了构造Sphere的步骤,因此耗费时间较大;在有相交面片的情 况下,本文算法的效率要优于单纯以OBB为包围盒的RAPID 系统,在最好的情况下可以提升大约l倍的速率. 图4模拟两辆车相撞的虚拟场景 4结语 碰撞检测对于提高虚拟环境的真实性和沉浸感有重要作 用,本文利用了Sphere和OBB两种包围盒各自的优点提出了 一 种新的混合层次包围盒算法,在时间消耗上提高了碰撞检铡 的效率.迄今为止,没有任何一种包围盒可以完美的适用于任 何虚拟场景,我们可以灵活的改变A层和B层的数量来达到适 用于当前虚拟环境的结果. 参考文献 [1]李德湘,彭斌.虚拟现实技术发展综述【J].技术与创新管理, 2004,25(6):10—14. [2]P.M.Hubbard.Interactivecollisiondetection.InProceed- ingsofIEEESymposiumonResearchFrontiersinVirtual Reality,Octoberl993:24-31. 下转第28页 软件袁志:解排列优化的整数编码多智能体进化算法 图2aatt48最优路径图2bart48寻优收敛曲线图 表2几种启发算法在Ofiver30与att48上的测试结果km 4 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 整数编码的多智能体进化算法继承了多智能体进化算法 的全局寻优能力,针对排列优化问题进行专门 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ,大幅提高 了运算速度.它的执行参数简单,只需要设定智能体网格的规 模和进化代数,因此方便应用.在旅行商问题上仿真,表明其 全局寻优能力和收敛稳定性比现有启发算法有明显提升. 参考文献 [1】贵超,黎明,韦雪洁.旅行商问题的几种求解方法【J].计算机仿真, 2006,23(8):153,157. [2】胡玉兰.基于遗传算法的旅行商问题的仿真实现[J】.控制工程, 上接第25页 [3】ZachmannG.Real-TimeandExactCollisionDetectionfor InteractiveVirtualPrototyping[C】.ProceedingofDETC’97, CaliforniaASME,1997:90-97. 【4]4GottschalkS,LinMC,ManochaD.OBB—TreeAHier- archicalStructureforRapidInterferenceDetection[C】.Pro- ceedingofSIGGRAPH’96,NewYork:ACMPress,I996: 171—18O. [5]5JamesTKlosowski,MartinHeld,JosephSBMitchell, 26 2002,9(6):79-81. 刘勤明,吕文元.旅行商问题的改进粒子群算法[J].计算机应用, 2007,27(12):185,187. 刘松兵,李智勇,王永,等.一种新的 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 粒子群算法及其在TSP 中的应用.计算机工程与应用,2008,44(28):62—64. 曹平,陈盼,刘世华.改进的粒子群算法在旅行商问题中的应用 [J].计算机工程,2008,34(6):217—331. 陈星宇,肖伟,全惠云,等.应用LK算法求解旅行商问题的混合 蚂蚁算法【JJ.计算机工程,2008,(4):228—230. 焦李成,刘静,钟伟才.协同进化计算与多智能体系统[M】.北京: 科学出版社,2006:153-157. 钟伟才,刘静,刘芳焦.组合优化多智能体进化算法[J].计算机学 报,2004,27(10):1341,l353. 谢刚,刘静.粒计算研究现状及展望[J].软件,2011,32(3):5-10. eta1.EfficientCo11isionDetectionUsingBoundingVolUme Hierarchiesofk—DOPsfJ].IEEETransactionsonVisualiza- tionandComputerGraphics(S1077—2626),l988,4(1):21-36. 【6]潘振宽,崔树娟,张继萍,李建波.基于层次包围盒的碰撞检测方 法[J】.青岛大学(自然科学版),2005,(3):71-76. I7]B.Barber,D.Dobkin,andH.Huhdanpaa.Thequickhull algorithinforconvexhuUs.ACMTransactionOnMath— ematicalSoftware(TOMS),l996:469-483. b