基于obb碰撞检测算法的研究

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

1、辽宁工程技术大学硕士学位论文基于OBB的碰撞检测算法研究姓名：董向阳申请学位级别：硕士专业：计算机应用技术指导教师：张佐刚20070301辽宁工程技术大学硕士擘位论文摘要碰撞检测是虚拟现实、动画仿真、计算机辅助设计等领域不可回避的问题之一，其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管人们已经取得了一系列成果，但是这些算法侧重于考虑碰撞检测的精确性，很少涉及实时性。随着计算机软硬件及网络等技术的日益成熟，交互实时性、场景真实性要求令碰撞检测再度成为图形学研究的热点。层次包围盒方法是解决碰撞检测问题固

2、有时间复杂性的一种有效的方法，它是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树状层次结构来逼近对象的几何模型，从而在对包围盒树进行遍历的过程中，通过包围盒间的快速相交测试来及早地排除明显不可能相交的基本几何元素对，而只对包围盒重叠的部分元素进行进一步的相交测试，以提高碰撞检测的速度。包围盒类型的选择是层次包围盒方法的基础和关键。文章首先对各类包围盒算法进行了全面的分析，然后重点探讨基于OBB层次包围盒算法的思想和流程，并在此基础上研究提高基于OBB层次包围盒算法执行效率的措施。本文主要研

3、究了以下几个方面的内容：(1)在研究OBB等层次包围盒固有特性的基础上，通过具体实现构建OBB和OBB树、包围盒间重叠测试等技术，比较了OBB适用于复杂环境中刚体碰撞检测的优势，并针对OBB存在的缺点和不足加以优化。(2)针对虚拟环境中物体移动时每帧之间的时空相关性，在原有的二叉树结点结构和遍历算法基础上，研究利用缓存、排序等方法优化碰撞检测算法。(3)针对基于OBB碰撞检测算法存在的缺陷，研究利用包围盒与基本几何元素相交测试的优化方法，消除叶子结点包围盒，精简OBB层次结构；同时在基本几何元素相交测试中引入类似分

4、离轴的方法，加快检测速度。通过多种检测方法的组合，得出基于OBB的优化层次结构和混合算法。实验结果和具体应用表明，基于OBB的碰撞检测方法能很好地解决复杂环境中刚体间的碰撞检测问题。本文的研究成果对大规模复辽宁工程技术大学硕士学位论文II杂环境中的碰撞检测有一定的理论价值和实际意义。关键词：碰撞检测；包围盒；OBB树：时空相关性辽宁工程技术大擘硕士学位论文IIIAbstractCollisionDetectionisoneofthebasicquestionsinmanyfields，suchasvirtualre

5、ality，cartoonemulation，CAD，etc．Itsbasictaskistoconfirmwhethertwooralotofobjectsarekeptintouchorpiercedthrougheachother．Thoughpeoplehavealreadymadeaseriesofachievements，thesealgorithmslayparticularemphasisonaccuracymeasure，andseldominvolvereal—timecharacter．Fol

6、lowingbythedevelopmentofcomputersoftware、hardwareandnetwork，mutualreal—timecharacterandsceneauthenticitymakeitbecomeahotfocusagain．Boundingvolumehierarchyprovidesaneffectivemethodtoresolvetheintrinsictimecomplexityincollisiondetection．Theideabehinditistoapprox

7、imatetheobjectwithasimplerboundingvolumethatisalittlebiggerthantheobject．Inbuildinghierarchiesonobject，onecanobtainincreasinglymoreaccurateapproximationsoftheobjects．Soduringtraversingboundingvolumehierarchy，itspeedsupcollisiondetectionbypruneawayprimitivepair

8、s，whichwillnotintersectclearlythoughrapidintersectiontestbetweenboundingvolumesandjustdealwiththosewhoseboundingvolumeisintersected．Thechoiceofboundingvolumeisthebasicandkeyproblem