基于包围盒的碰撞检测算法综述

《基于包围盒的碰撞检测算法综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第18卷第4期2006年4月系统仿真学报@JournalofSystemSimulationVbl．18NO．4Apr．，2006基于包围盒的碰撞检测算法综述马登武，叶文，李瑛(海军航空工程学院兵器科学与技术系，烟台264001)摘要：对基于包围盒的碰撞检测算法中的轴向包围盒法、方向包围盒法、离散方向多面体法、时空包围盒法的检测原理和检测效率进行了详细地分析比较。分析结果表明：包围盒的简单性和它包襄对象的紧密性是一对矛盾，包围盒越简单其包裹紧密性越差，如何更好地兼质简单性和紧密性成为包围盒法的关冀；离散方向多面体是介于轴向包围盒和凸包之同的包圈盒，只要合理地选取平

2、行平面对的个数和方向，就可以在碰撞检洲的简单性和包襄物体的紧密性之间灵活取舍。研究结论对于虚拟场景的动态建模具有一定的指导意义。。关键词：虚拟现实；碰撞检测；算法；包围盒中图分类号：TP391．9文献标识码：A文章编号：1004—731X(2006)04．1058—04SurveyofBox-basedAlgorithmsforCollisionDetectionMADeng·wu，YEWen,LIYing(DepartmentofOrdnanceScienceandTechnology,NAEI，Yantai264001，China)Abstract：Different

3、algorithmsforcollisiondetections(CD)invirtualsceneweresurveyed．Theprincipleandeffectivenessofaxis—alignedboundingboxes(AABB)method，orientedboundingboxmethod(OBB)，discreteorientationpolytopesfk—DOP)methodandSpace．TimeBoundingBoxes(STBB)methodwerediscussedindetail．Theresultsofanalysisprovet

4、hatthesimp跆nessofboundingboxisincontradictionwiththecompactnessofwrappedobjectandthek—DOPmethodiSbetweenAABBmethodandD口Bmethod伽theeffectivenesso，CD．Themainresultsareusefulfordesigningvirtualscene．Keywords：virtualreality：collisiondetection；algorithm；boundingbox引言在虚拟现实中，用户感觉虚拟对象应该是“真实”存在的，例

5、如飞机不可能穿过一座山飞过去，用户用虚拟手敲打石头时，虚拟手不应穿过石头等。这要求虚拟现实系统必须实时、准确判断虚拟物体之间是否发生了碰撞【1，2】。碰撞问题涉及碰撞检测与碰撞响应两个方面，其中碰撞检测用来检测不同对象之间是否发生了碰撞。精确的碰撞检测对提高仿真的真实性、可信性，增强虚拟环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性也对碰撞检测提出了更高的要求[3]。碰撞检测算法总体上可分为空间分解法和层次包围盒方法两大类，其中层次包围盒方法应用得更为广泛，十分适用于复杂环境中的碰撞检测。因此本文基于对国内外有关包围盒碰撞检测算法研究论述的深入研究与系统分

6、析，综述相关研究成果，以期有助于包围盒碰撞检测算法这一研究的继续深入与广泛应用。1碰撞检测的基本原理简单地讲，碰撞检测就是检测虚拟场景中不同对象之间是否发生了碰撞。从几何上讲，碰撞检测表现为两个多面体收稿日期l2005．01．21修回日期l2005—09—24作者简介t马登武(1964．)，男，山东淄博人，副教授，博士，研究方向为航空兵器工程、计算机仿真、虚拟现实；叶文(1979一)，男，安徽黄山人，助教，博士，研究方向为低空突防、计算机仿真、虚拟现实。的求交测试问题；按对象所处的空间可分为二维平面碰撞检测和三维空间碰撞检测。平面碰撞检测相对简单一些，已经有较为成熟的检测

7、算法，而三维空间碰撞检测则要复杂得多【4，5】。在VR系统中，主要是如何解决碰撞检测的实时性和精确性的矛盾。不同的应用场合，对实时性和精确性的要求不尽相同。由于碰撞检测问题在虚拟现实、计算机辅助设计与制造、机器人等领域有着广泛的应用，甚至成为关键技术，人们已经从不同的角度对碰撞检测问题进行了广泛的研究。按照是否考虑时间参数，碰撞检测又可分为连续碰撞检测和离散碰撞检测。连续碰撞检测的定义如下：定义1设三维空间R用三维几何坐标系统Fw表示，其中有N个运动模型，它们的空间位置和姿态随着时间而改变，Fi表示第i个模型所占的空间。F。随