三维游戏中碰撞检测算法的研究与实现毕业论文

《三维游戏中碰撞检测算法的研究与实现毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉理工大学硕士学位论文三维游戏中碰撞检测算法的研究与实现姓名：刘翼申请学位级别：硕士专业：计算机科学与技术指导教师：高曙20100501武汉理工大学硕士学位论文摘要虚拟环境中物体间的碰撞检测是虚拟现实、计算机动画、计算机图形学、计算机游戏等领域中一个极富挑战性的问题。其基本任务是确定两个或两个以上的模型之间是否发生接触或穿透。快速的碰撞检测对提高虚拟环境的沉浸感和真实感起着至关重要的作用。由于虚拟环境中存在大量的物体对象及物体几何形状的复杂性，使得碰撞检测过程常常占用大量的存储空间和处理时间，碰撞检测算法的效率决定生成虚拟场景的实

2、时性和真实性。本文以三维游戏为应用背景，主要研究三维游戏中存在的两类刚体碰撞检测问题：动态物体与静态物体的碰撞检测，动态物体与动态物体的碰撞检测。围绕这两类刚体碰撞检测问题，在对现有碰撞检测算法作出全面分析的基础上，提出了相应的解决办法。(1)论文描述了碰撞检测算法的一般框架。对三维游戏中的碰撞检测问题进行了分类和比较。在两类碰撞检测算法的详细检测阶段采用AABB层次包围盒法，并对AABB层次包围盒的存储结构进行了优化。(2)针对动态物体与静态物体的碰撞检测，设计了一种空间剖分法与层次包围盒法相结合的碰撞检测算法，在初步检测阶段采用

3、BsP空间剖分法找出可能的相交区域，在详细测试阶段采用AABB层次包围盒法求交。并针对构建BSP树时分割平面选择的问题，采用了一种基于包围球的分割平面选取策略来优化BSP树的构建。(3)针对动态物体与动态物体的碰撞问题，则设计了一种投影区间排序法与层次包围盒法相结合的碰撞检测算法。在初步检测阶段利用AABB投影区间排序法快速排除不可能相交的物体。然后在详细测试阶段采用AABB层次包围盒法求交。并在整个过程中融入时空相关性加速碰撞检测过程。(4)通过实验对本文所采用算法的效率进行了分析和测试。关键字：三维游戏，碰撞检测，AABB层次包

4、围盒法，BSP空间剖分法武汉理工大学硕士学位论文Abstractnisquitechalleng：illgt0detectc01lisionbetweeIlobjectsindomainsofvirtIlal删it弘computefa11imatioll’咖putef孕．a1)hics，computef膨咖e，etc．ItSb嬲ictaskist0identi匆whetlleraC0nt搬orpene附ionh髓happenedi

5、l咖al曲饥ronment，nlereal埘锄de1111anccdi1I】l芏Ilersionof、

6、)l抽chd印eIldl卸gelyonf奴锄dcXactCollisiondetection．Ahugemmlb盯ofobjcctswitllConlpli∞tegeometri器existin鳓c_h淌11IIlenttllatcollisiondeteCtionoR％takesupa10tofstoragespace锄dproceSsingtime，sotllee伍ciellCyofcollisiondetectioneXensavc巧黟eatinnu铋cet0real-time锄daumeIltici够ofvi咖a1蜘啊r0眦

7、ent．T＼Ⅳori百dobjectcollisiondetectionp∞bl即晦int11re枷iIIler】Lsionalgam髂a糟researchedinthispaper'includingcollisiondeteCtionbetweend)111锄ico巧ects锄dstaticobjects，andmatbetweendyn锄icobjects觚ddyn锄icobjects．AccordingtotlleeXistingc01lisiondctectiona190rim】ms，aCorreSpondingsolut

8、ionisproposcdforⅡle觚ocollisiondetectionsform旧e_dimeIlsionalgam骼．(1)111egeIleral触meworkofCollisiondetectiona190rithmsisdes嘶bedalldsomeclassificationalldcomparisonaredone嬲well．AABBllier盯cllicalbo姗dingVolumeisadopted蛳ngdetailedtestingphase，aReroptimizingitSstoragestrIlctu

9、rc．(2)触矗Mmefirstt)，peofdeteCtio玛雏algori咖nmatcombinesSpacesubdivisionalgorithmwimlliefarcllicalb(mrldiI培Vol姗ealgoriⅡlm