碰撞检测中的包围盒算法

《碰撞检测中的包围盒算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第21卷第12期重庆工学院学报(自然科学)20o7年12月、1．2lNo．J2JournalofChon~ngInstituteofTechnology(NaturalScienceEdition)Dec．20ar7【电子与自动化】碰撞检测中的包围盒方法何伟，李勇，苏虎(西南交通大学电气工程学院，成都610031)‘：c_协^、0■：jk¨2=^=摘要：讨论了当前虚拟环境中应用比较广泛的2类碰撞检测算法——空间剖分法和层次包围盒霞法．重点对层次包围盒算法中的轴向包围盒(AA船)法、方向包围盒(OBB)法和固定方向凸包包围盒(F1)H)法从包围盒的构建、相交检测等方面做了详细分析，

2、并从计算复杂度、适用范围等方面对这3类方法进行了比较关键词：虚拟环境；碰撞检测；包围盒中图分类号：TIB91．7文献标识码：A文章编号：1671一~2,t(2oo7)12—0148—05电：年尔尔绵帘书出家尔替筇尔尔出牢．矫尔希绵绵尔砖宋出石绵夼希术尔石绵{AnalysisonBoundingBoxTechnologyinCollisionDetectionHEWei．，UY0ng，SUHu(SchoolofFlectricalEngineering，SouthwestJiaotongUniversity,Ch~n#u610031，China)Abstract：Thispaper

3、discussestwokindsofcolisiondetectionalgorithmwidelyusedinpresentvirtualen—vlronment：SpaceDecompositionmethodandBoundmgBoxmethod，elaboratesOntheintersectiondetectandeffectivenessofaxis．alignedboundingboxes(AABB)method，orientedboundingbox(OBB)method，fixeddirectionshulls(FDH)method，andcomparesth

4、ethreemethodsintermsofcomputingcomplexity，applicationscope，ete．Keywords：virtualenvironment；collisiondetection；boundingbox碰撞检测(CollisionDetection)就是检测虚拟场盒(Oriented"BoundingBox，简称OBB)[3l、固定方向景中不同对象之间是否发生了碰撞．从几何上讲，凸包包围盒(FixedDirectionsHuls，简称FDH)【j碰撞检测表现为2个多面体的相交测试问题．近等．年来，国内外学者在碰撞检测领域中做了很多有层次包围

5、盒方法的核心思想是用体积略大而意义的工作，并提出了一些高效的检测方法．其中几何特性简单的包围盒来近似地描述复杂的几何层次包围盒方法又是其中较好的算法．根据包围对象，从而只需对包围盒重叠的对象进行进一步盒类型的不同可以分为轴向包围盒(AxisAligned的相交测试．此算法使用了层次结构模型，其目标BoundingBox，简称AABB)[1l、包围球【2l、方向包围是尽可能地减少进行相交测试的几何对象的数·收稿日期：2007—10—13基金项目：成都市科技攻关课题(0r7ccYB256Gx一010)．作者简介：何伟(198卜)，男，四川成都人，硕士研究生，主要从事智能交通系统研究何

6、伟，等：碰撞检测中的包围盒方法149目．本文中将对层次包围盒方法中的几种主要算法加以讨论．2经典包围盒算法1层次包围盒算法2．1包围球一个给定对象的包围球(Sphere)被定义为包2个采用层次包围盒树结构的物体的碰撞检含该对象的最小球体．计算给定对象的包围球，首测过程如下[5]：首先判断2棵树的根节点的包围先需分别计算对象的基本几何元素集合中所有元盒是否相交，如果不相交，那么这2个物体肯定不素顶点的坐标、'，坐标和：坐标的均值，以确定发生碰撞；否则递归遍历2棵树，对相应的子节点包围球的球心．再由球心c与3个最大值坐标所进行求交判断．如果参与求交运算的2个子节点确定的点间的距离计算

7、半径r，存储一个包围球只中至少有一个为非叶节点，则检测2节点的包围需2个浮点数．盒是否相交，如果不相交则不必再判断子节点；若对于2个包围球(cl，r1)和(c2，r2)，如果球心2节点均为叶节点，且检测出它们的包围盒相交，距离小于半径之和，即Icl—c2I