基于包围盒和空间分解的碰撞检测算法-论文.pdf

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

1、第24卷第1期计算机技术与发展Vo1．24No．12014年1月COMPUTERTECHNOLOGYANDDEVELOPMENTJan．2014基于包围盒和空间分解的碰撞检测算法宋城虎，闵林，朱琳，郭拯危(河南大学计算机与信息工程学院，河南开封475002)摘要：文中提出一种基于包围盒和空间分解的碰撞检测算法，用以解决软体的碰撞检测。算法使用AABB包围盒做初步检测，确定可能发生碰撞的物体。再根据包围盒的重叠情况缩小可能发生碰撞的区域，利用哈希表作为数据储存结构进行空间分解，将物体包围盒重叠区域的基本几

2、何元素的空间网格映射到哈希表中，将碰撞区域缩小到基本几何元素，最后用基元碰撞检测找出具体碰撞点。由于前期AABB包围盒的处理减少了空间分解阶段需要映射的基本几何元素数量，该算法具有较高的运算速度。关键词：碰撞检测；空间分解；AABB；哈希表中图分类号：TP391文献标识码：A文章编号：1673—629X(2014)Ol一0057—04doi：10．3969／j．issn．1673—629X．2014．01．015ACollisionDetectionAlgorithmBasedonBoundingBox

3、andSpatialSubdivisionSONGCheng—hu，MINLin，ZHULin，GUOZheng-wei(CollegeofComputerandInformationEngineering，HenanUniversity，Kaifeng475002，China)Abstract：Acollisiondetectionalgorithmbasedontheboundingvolumeandspatialsubdivisionforthecollisiondetectionofdeform

4、ableobjectsisproposed．ThealgorithmdoespreliminarydetectionwithAABBboundingvolumeboxestofindtheobjectswhichmaybecolli·ded．Thenaccordingcotheareaofoverlapoftheboundingboxreducethepossiblecollision．usehashtableasadatastorageslxUCtUreforspatialdecomposition，

5、thespatialgridofbasicgeome~celementsintheobjectboundingboxoverlapareaismappedtoahashtable，re—ducingthecollisionareatobasicgeometricelements，withprimitivecollisiondetectiontofindoutspecificcollisionpointfinally．OwingtOthedetectionofAABBtoreducethenumberof

6、objectprimitives，SOthisalgorithmhasabetterperformance．Keywords：collisiondetection；spatialsubdivision；AABB；hashtaleO引言刚体和软体是虚拟环境中对象的基本形态，由于碰撞检测(CollisionDetection，CD)也称为干涉检软体的形状会随时间变化，和刚体的碰撞检测相比，软测或者接触检测，是虚拟现实技术、系统仿真等领域中体碰撞检测有许多方面与之不同，这使得该问题的复的关键性问题。虚拟现实的

7、应用使得使用者可以进入杂性大大增加。在布料仿真或手术仿真中，软体一个由计算机产生的虚拟世界，为保证虚拟环境的真的碰撞检测都是一个必不可少的组成部分。实性，要求参与者能够身临其境地与它们发生各种交近几十年来，在碰撞检测领域，国内外研究人员已互，这就要求物理对象之间能够实时地进行交互活动。经做了相当多有意义的工作。层次包围盒和空这里有两个关键的问题：间分解作为两个经典算法被广泛运用，层次包围盒(1)要求虚拟现实技术能够进行实时的碰撞检算法设计的重点在于包围和类型的选取，常见的包围测；盒类型有spheres，

8、DOPs，AABB，OBB。在刚体的碰(2)做出相应的碰撞响应动作，从而避免物体问撞检测中，包围盒显得十分有效，但在物体的形状发生相互穿透的发生。变化后，某些包围盒树(如OBB)的更新便成为了问收稿日期：2013-03—18修回日期：2013—06—24网络出版时间：2013—11～12基金项目：国家自然科学基金资助项目(61202098)作者简介：宋城虎(1986-)，男，硕士研究生，研究方向为虚拟现实技术；闵林，教授，研究方向为无线传感