复杂虚拟环境下的实时碰撞检测算法new

《复杂虚拟环境下的实时碰撞检测算法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第22卷第1期系统仿真学报©Vol.22No.12010年1月JournalofSystemSimulationJan.,2010复杂虚拟环境下的实时碰撞检测算法1,232赵伟，谭睿璞，李勇(1.吉林农业大学信息技术学院，长春130118；2.吉林大学数学学院,长春130012；3.福建经济管理干部学院，福建350002)摘要：提出了一种共享存储系统的并行碰撞检测算法。利用AABB包围盒的优点来构建任意物体的混合包围盒层次，利用并行模型来并行遍历混合包围盒层次，进一步加速碰撞检测算法。实验结果表明，与现有的经典算法相比，该算法在效率、精确性方面

2、具有明显优势，能够满足交互式复杂虚拟环境的实时性和精确性的要求。关键词：虚拟环境；实时碰撞检测；混合包围盒层次；并行算法中图分类号：TP301.6文献标识码：A文章编号：1004-731X(2010)01-0125-05RealTimeCollisionDetectionAlgorithminComplexVirtualEnvironment1,232ZHAOWei,TANRui-pu,LIYong(1.SchoolofInformationTechnology,JilinAgriculturalUniversity,Changchun1301

3、18,China;2.CollegeofComputerScience&Technology,JilinUniversity,Changchun130012China;3.FujianInstituteofEconomicsManagement,Fujian350002,China)Abstract:Asharedmemoryparallelcollisiondetectionalgorithmwasproposed.First,themeritsofbothAABBboundingboxwereincorporatedtoconstructa

4、mixedboundingvolumehierarchyofarbitrarynon-convexpolyhedraforattainingspeed,andthentheparallelprogrammingmodelwasusedtotraversalthebuiltmixedboundingvolumehierarchy.Experimentresultsshowthatthealgorithmisefficiencyandaccuracyoverothercurrenttypicalcollisiondetectionalgorithm

5、.Itcanmeetthereal-timeandaccuraterequirementsincomplexinteractivevirtualenvironment.Keywords:virtualenvironment;realtimecollisiondetection;mixedboundingvolumehierarchy;parallelalgorithm1引言助制造等领域应用越来越广泛。文献[3]提出了如何采用面向对象的方法检测物体之间是否存在着碰撞，指出了在分布式随着虚拟现实技术的不断发展，碰撞检测技术在计算机条件下碰撞检测的完

6、全性和唯一性的问题，但对于复杂虚拟应用领域有了广泛的应用。碰撞检测在计算机图形图像处环境下的物体碰撞检测没有好的解决办法；理、虚拟建模、三维动画、计算机辅助制造、计算机辅助设文献[4]提出了基于凸多面体结构的并行碰撞检测算法，计、军事模拟训练等领域中都是必须解决的关键问题，国内但其实验条件必须为凸多面体，对于非凸体没有提出解决的外很多学者一直关注这一问题的研究。碰撞检测是指空间中任算法。文献[5]提出了一种与时间空间相关的并行碰撞检测算[1]意两个不可刺穿的物体，不能存在于相同位置的空间区域。法，算法速度有了较明显的提高，但虚拟空间物体的树形表

7、近几年研究人员对虚拟环境下的碰撞检测问题进行了示结构复杂，多进程通讯影响物体的碰撞检测效率。文献[6]较深入地研究，提出了很多虚拟环境下的快速碰撞检测算提出了一种基于并行分治及流水线技术的快速碰撞检测算法，从宏观上可归为两类：时间域划分方法和空间域划分方法，虽然算法加快了碰撞检测速度，但系统执行过程的进程[2]法。时间域划分方法包括静态碰撞检测方法、离散碰撞检数很难确定，难于找到最佳适应值。测方法、连续碰撞检测方法。空间域划分方法包括基于物体本文提出了基于包围盒与包围球混合数据结构的并行空间的碰撞检测方法和基于图像空间的碰撞检测方法。基于化碰撞

8、检测算法。采用并行技术中的分治策略为虚拟空间中时间域的碰撞检测方法主要缺点是存在着刺穿问题，基于空每个物体建立树形模型，采用并行算法遍历树形模型结构，