一种快速的可变形物体的碰撞检测算法-论文.pdf

《一种快速的可变形物体的碰撞检测算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1702014，50(9)ComputerEngineeringandApplications计算机工程与应用一种快速的可变形物体的碰撞检测算法谭睿璞，赵伟TANRuipu，ZHAOWei1．福建江夏学院电子信息科学学院，福州3501082．吉林农业大学信息技术系，长春1301181．SchoolofElectronicInformationScience，FujianJiangxiaUniversity,Fuzhou350108，China2．DepartmentofInformationTechnology，JilinAgriculturalUniversity，Changehun

2、130118，ChinaTANRuipu，ZHAOWei．Fastcollisiondetectionalgorithmfordeformableobjects．ComputerEngineeringandAp-plications，2014，50(9)：170-175．Abstract：Inordertoachieveareal—timecollisiondetectionbetweendefo衄ableobjectsandrigidbodyinthevirtualenvl‘ronment，afastparallelcollisiondetectionalgorithmbasedon

3、hybridboundingboxhierarchyisproposed．Takingintoaccountthedifferentcharacteristicsoftheboundingboxinthedetectionspeedandaccuracy,thisalgorithmbuildsasphere—AABBhybridboundingboxhierarchytreefordeformableobject，andestablishesasphere—OBBhybridboundingboxhierarchytreeforrigidbody；inaddition，everyhyb

4、ridboundingboxhierarchytreeisdividedintoupperlayer,middlelayerandlowerlayer,andeachlayerusesadifferentboundingbox；whentraversingthetrees，thisalgorithmusessphere-spheretestintheupperlayer,sphere—OBBtestinthemiddlelayerandAABB-OBBtestinthelowerlayertodetectcollision．Thispaperusesmulti—threadingtec

5、hnologytoachieveparallelcollisiondetectionalgorithmonmulti—coredevices．Experi-mentalresultsshowthatthisalgorithmhasobviousadvantagescomparedwiththeclassicAABBalgorithmintheaspectofeficiency，andcanmeettherequirementofcollisiondetectionbetweendeformableobjectsandrigidbody．Keywords：collisiondetecti

6、on；deformableobjects；rigidbody；hybridboundingvolumehierarchy；multiplethread摘要：为实现虚拟环境中可变形物体与刚体间实时的碰撞检测，提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重，对可变形物体建立Sphere和AABB混合包围盒层次树，对刚体建立Sphere和OBB混合包围盒层次树；每个物体的混合包围盒层次树又分成上层、中层和下层，每层使用不同的包围盒；在碰撞检测遍历时，上层使用Sphere和Sphere相交检测快速排除不相交物体，在中层使用Sphere和

7、OBB的相交检测进一步排除物体相交的可能性，在下层使用AABB和OBB的相交检测较精确地确定物体是否相交；采用多线程技术，在多核设备上实现并行碰撞检测算法。实验结果表明，与经典的AABB算法相比较，该算法在效率方面具有明显优势，能够满足可变形物体与刚体的碰撞检测要求。关键词：碰撞检测；可变形物体；刚体；混合包围盒层次；多线程文献标志码：A中图分类号：TP301．6doi：10．3778／j．issn．1002—8331．1311．00251引言