层次包围盒碰撞检测算法的优化及其并行化

《层次包围盒碰撞检测算法的优化及其并行化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：10289分类号：TP391密级：公开学号：132070002江苏科技大学硕士学位论文层次包围盒碰撞检测算法的优化及其并行化研究生姓名于凯导师姓名俞孟蕻申请学位类别工学硕士学位授予单位江苏科技大学学科专业模式识别与智能系统论文提交日期2015年12月31日研究方向模式识别论文答辩日期2016年3月26日答辩委员会主席段先华评阅人2016年3月26日分类号：TP391密级：公开学号：132070002工学硕士学位论文层次包围盒碰撞检测算法的优化及其并行化学生姓名于凯指导教师俞孟蕻教授江苏科技大学二O一六年三月AThesisSubmittedinFulfillmentoftheRe

2、quirementsfortheDegreeofMasterofEngineeringOptimizationandParallelizationofHierarchicalBoundingBoxCollisionDetectionAlgorithmSubmittedbyYuKaiSupervisedbyYuMenghongJiangsuUniversityofScienceandTechnologyMarch，2016江苏科技大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集

3、体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：年月日摘要随着虚拟现实的发展和人们对体验要求的提高，碰撞检测算法实时性与准确性的要求也随之提高。层次包围盒碰撞检测算法将物体分为粒度不同的包围盒进行测试，具有较高的准确性，但是实时性较差。本文优化了传统的层次包围盒碰撞检测算法，并使用GPU并行计算，进一步加快了碰撞检测算法的速度。本文主要研究内容如下：（1）以现有碰撞检测算法为基础，归纳总结了基于空间分解的碰撞检测算法和基于层次包围盒的碰撞检测算法，分析并比较各类碰撞检测算法的优缺点。

4、（2）对构造层次包围盒树算法进行优化。分析哈夫曼法构造层次包围盒树的实现方式，提出使用平衡二叉树法对构造层次包围盒树的优化方案，节省了构造层次包围盒树的耗时。（3）实现优化后的构造层次包围盒树算法的并行化。对优化后的构造层次包围盒算法进行可行性分析，并在CUDA平台上对其进行并行化，进一步节省了构造层次包围盒树的耗时。（4）实现层次包围盒碰撞检测算法的并行化。分析串行碰撞检测算法中双重遍历层次包围盒树的实现方式，针对其存在无效遍历增加算法耗时的缺点，提出并行化的解决方案，并在CUDA平台上对其进行并行化。并行遍历层次包围盒树屏蔽了无效遍历的算法耗时，从而加快了碰撞检测算法的速度。试验验证

5、表明，优化后的层次包围盒碰撞检测算法具有更高的效率，有效的提高了构造层次包围盒树和遍历层次包围盒树的速度。关键词碰撞检测；层次包围盒；CUDA；平衡二叉树；并行化；IAbstractWiththedevelopmentofvirtualrealityandtheimprovementofpeople'srequirementofexperience,theinstantaneityandaccuracyofcollisiondetectionisalsoincreased.Thehierarchicalboundingboxcollisiondetectionalgorithmsdivi

6、deobjectintodifferentscaleofboundingbox,sothesealgorithmhashigheraccuracyandlowerinstantaneity.Thispaperoptimizesthetraditionalhierarchicalboundingboxcollisiondetectionalgorithmandimplementsthealgorithm'sparallelizationusingGPU,acceleratingthespeedofcollisiondetectionalgorithm.Thefollowingpartsar

7、eincludedinthisarticle:(1)Basedontheexistingcollisiondetectionalgorithm,thispapersummarizesthecollisiondetectionalgorithmbasedonspacedecompositionandthecollisiondetectionalgorithmbasedonhierarchicalboundingbox,analyzin