基于复合层次包围盒的实时碰撞检测研究

《基于复合层次包围盒的实时碰撞检测研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第20卷第2期系统仿真学报©Vol.20No.22008年1月JournalofSystemSimulationJan.,2008基于复合层次包围盒的实时碰撞检测研究朱元峰，孟军，谢光华，马文娟（大连理工大学计算机科学与工程系，辽宁大连116024）摘要：针对各种层次包围盒的特点，提出了基于球状包围盒（Sphere）结构与有向包围盒（OBB）的复合层次包围盒的碰撞检测方法。将复合包围盒树分为X、Y、Z层，X层节点为球状包围盒（Sphere）结构，Y层为OBB-Sphere混合结构，Z层为OBB结构。上层节点间的

2、相交测试采用Sphere与Sphere或者OBB的方式，以此快速排除不可能相交的物体；下层节点间的测试采用OBB与OBB的方式保证精确的判定距离较近的物体的碰撞状态。实验通过与OBB算法的性能比较，证明了复合包围盒能有效地应用于复杂场景的实时碰撞检测。关键词：碰撞检测；层次包围盒；球形包围盒；有向包围盒中图分类号：TP391.9文献标识码：A文章编号：1004-731X(2008)02-372-06ResearchonReal-TimeCollisionDetectionBasedonHybridHierarc

3、hicalBoundingVolumeZHUYuan-feng,MENGJun,XIEGuang-hua,MAWen-juan（DepartmentofComputerScienceandEngineering,DalianUniversityofTechnology,Dalian116024,China）Abstract:Analyzingtheperformanceofvarioushierarchicalboundingvolumes(HBVs),afastalgorithmforreal-timecol

4、lisiondetection(CD)wasproposedusingastructureofhybridhierarchicalboundingvolume(HHBV)basedonOBBandsphereBV.TheHHBVtreeforCDfallsintothreesuccessivelayersinatop-downmanner,whichareLayerXusingsphereasitstreenode,LayerYusingOBB-SphereBVandLayerZusingOBB.Theinte

5、rsectiontestusesspherevs.sphereorspherevs.OBBmethodforfastoverlaptestinupperlayers,eliminatingthepossibilityofcollisionbetweenobjectsfarapart;thenitaccuratelydeterminesthecontactstatusamongobjectsincloserproximitybyOBBvs.OBBtestinlowerones.Experimentswerecom

6、paredwithothercompetitivealgorithm(OBB)toanalyzetheperformance.ResultsshowthealgorithmisasefficientinprecisionasOBB,andfasterincomplexvirtualenvironment.Keywords:collisiondetection;hierarchicalboundingvolumes;sphereboundingboxes;OBB1（X层）用简单的球（Sphere）包围盒，中间层（

7、Y层）用引言混合的包围盒结构（OBB-Sphere），下层（Z层）用有向包碰撞检测作为虚拟现实中一项重要的技术，在实现虚拟围盒（OBB）。相距较远不可能碰撞的对象可以被上层或者场景所应提供的沉浸性、交互性和构想性等方面扮演了重要中层的Sphere-Sphere检测快速排除掉；对那些上层或者中间角色，并再次成为研究热点。碰撞检测的基本任务就是确定层可能相交的对象，进一步进行OBB-Sphere包围盒的相交测[1]两个或多个物体之间是否发生接触或穿透。试；最后对于物体的紧密性已经很好的可能重叠的包围盒，如果对虚拟环

8、境中组成物体的所有n个基本几何元素进则采用精确的OBB包围盒相交测试来确定碰撞状态。2行两两相交测试，复杂度为O(n)，其几何复杂性使碰撞检本方法实时检测速度的代价是Sphere与OBB的折中，具[2]测算法的计算复杂度大大提高。针对复杂虚拟场景的特有Sphere包围盒在复杂场景中能迅速排除不可能相交的物[3]点，已有的经典算法，例如BSP树、K-DOP、OBB、Sphere、体对的特