内容发布更新时间 : 2024/6/22 4:03:05星期一 下面是文章的全部内容请认真阅读。

第18卷第4期2006年4月 系统仿真学报@

Journal of System Simulation Vbl.18NO.4

Apr.,2006基于包围盒的碰撞检测算法综述 马登武,叶文,李瑛

(海军航空工程学院兵器科学与技术系,烟台264001

摘要:对基于包围盒的碰撞检测算法中的轴向包围盒法、方向包围盒法、离散方向多面体法、时空包围盒法的检测原理和检测效率进行了详细地分析比较。分析结果表明:包围盒的简单性和它包襄对象的紧密性是一对矛盾,包围盒越简单其包裹紧密性越差,如何更好地兼质简单性和紧密性成为包围盒法的关冀;离散方向多面体是介于轴向包围盒和凸包之同的包圈盒,只要合理地选取平行平面对的个数和方向,就可以在碰撞检洲的简单性和包襄物体的紧密性之间灵活取舍。研究结论对于虚拟场景的动态建模具有一定的指导意义。。

关键词:虚拟现实;碰撞检测;算法;包围盒

中图分类号:TP391.9文献标识码:A文章编号:1004—731X(200604.1058—04 Survey of Box-based Algorithms for Collision Detection MA Deng?wu,YE Wen,LI Ying

(Department ofOrdnanceScienceandTechnology,NAEI,Yantai264001,China Abstract:Different algorithms for collision detections(CDin virtual scene were surveyed.The principle and effectiveness of axis—aligned bounding

boxes(AABBmethod,oriented bounding box method(OBB,discrete orientation polytopes fk—DOPmethod and Space.Time Bounding Boxes(STBBmethod were discussed in detail.The results of analysis prove that the simp跆ness of bounding box is in contradiction with the compactness of wrapped object and the k—DOP method iS between AABB method and D口B method伽the effectiveness o,CD.The main results are useful for designing virtual scene. Key words:virtual reality:collision detection;algorithm;bounding box

引言

在虚拟现实中,用户感觉虚拟对象应该是“真实”存在的,例如飞机不可能穿过一座山飞过去,用户用虚拟手敲打石头时,虚拟手不应穿过石头等。这要求虚拟现实系统必须实时、准确判断虚拟物体之间是否发生了碰撞【1,2】。碰撞问题涉及碰撞检测与碰撞响应两个方面,其中碰撞检测用来检测不同对象之间是否发生了碰撞。精确的碰撞检测对提高仿真的真实性、可信性,增强虚拟环境的沉浸感有着至关重要的作用,而虚拟环境自身的复杂性和实时性也对碰撞检测提出了更高的要求[3]。

碰撞检测算法总体上可分为空间分解法和层次包围盒方法两大类,其中层次包围盒方法应用得更为广泛,十分适用于复杂环境中的碰撞检测。因此本文基于对国内外有关包围盒碰撞检测算法研究论述的深入研究与系统分析,综述相关研究成果,以期有助于包围盒碰撞检测算法这一研究的继续深入与广泛应用。

1碰撞检测的基本原理

简单地讲,碰撞检测就是检测虚拟场景中不同对象之间是否发生了碰撞。从几何上讲,碰撞检测表现为两个多面体

收稿日期l2005.01.21修回日期l2005—09—24

作者简介t马登武(1964.,男,山东淄博人,副教授,博士,研究方向为航空兵器工程、计算机仿真、虚拟现实;叶文(1979一,男,安徽黄山人,助教,博士,研究方向为低空突防、计算机仿真、虚拟现实。

的求交测试问题;按对象所处的空间可分为二维平面碰撞检测和三维空间碰撞检测。平面碰撞检测相对简单一些,已经有较为成熟的检测算法,而三维空间碰撞检测则要复杂得多【4,5】。在VR系统中,主要是如何解决碰撞检测的实时性和精确性的矛盾。不同的应用场合,对实时性和精确性的要求不尽相同。由于碰撞检测问题在虚拟现实、计算机辅助设计与制造、机器人等领域有着广泛的应用,甚至成为关键技术,人们已经从不同的角度对碰撞检测问题进行了广泛的研究。

按照是否考虑时间参数,碰撞检测又可分为连续碰撞检测和离散碰撞检测。连续碰撞检测的定义如下:

定义1设三维空间R用三维几何坐标系统Fw表示,其中有N个运动模型,它们的空间位置和姿态随着时间而改变,Fi表示第i个模型所占的空间。F。随着时间的变化形成四维坐标系统Cw,模型Fi沿着一定的轨迹运动形成四维坐标系统Cj,碰撞检测就是判断C】nC2nC3..n CtI=o是否成立。

碰撞检测问题若用算法表示具体表示为图1的形式。

在图1的表示当中有三层循环:首先是最外层的for循环,该循环中时间t以步长At递增。步长At越大,检测速度越快,但检测精度却会下降,且这种固定步长的检测算法不能根据具体情况调整步长和精度。其次是二、三两层for 循环,它们要对所有“对象对”(Ai和Ai进行检测,使问题的时间复杂度变为O(N2。第三是四、五两层表示的最内层的for循环,即对组成多面体的基本几何元素进行相交测试。如果虚拟场景中有N个多面体,每个多面体有M个顶点,则碰撞检测的时间复杂度为O(N2M2。