資源描述：
《層次包圍盒碰撞檢測算法的優(yōu)化及其并行化》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、學校代碼：10289分類號：TP391密級：公開學號：132070002江蘇科技大學碩士學位論文層次包圍盒碰撞檢測算法的優(yōu)化及其并行化研究生姓名于凱導師姓名俞孟蕻申請學位類別工學碩士學位授予單位江蘇科技大學學科專業(yè)模式識別與智能系統(tǒng)論文提交日期2015年12月31日研究方向模式識別論文答辯日期2016年3月26日答辯委員會主席段先華評閱人2016年3月26日分類號：TP391密級：公開學號：132070002工學碩士學位論文層次包圍盒碰撞檢測算法的優(yōu)化及其并行化學生姓名于凱指導教師俞孟蕻教授江蘇科技大學二O一六年三月AThesisSubmittedinFulfillmentoftheRe
2、quirementsfortheDegreeofMasterofEngineeringOptimizationandParallelizationofHierarchicalBoundingBoxCollisionDetectionAlgorithmSubmittedbyYuKaiSupervisedbyYuMenghongJiangsuUniversityofScienceandTechnologyMarch，2016江蘇科技大學學位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的學位論文，是本人在導師的指導下，獨立進行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個人或集
3、體已經(jīng)發(fā)表或撰寫過的作品成果。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明的法律結(jié)果由本人承擔。學位論文作者簽名：年月日摘要隨著虛擬現(xiàn)實的發(fā)展和人們對體驗要求的提高，碰撞檢測算法實時性與準確性的要求也隨之提高。層次包圍盒碰撞檢測算法將物體分為粒度不同的包圍盒進行測試，具有較高的準確性，但是實時性較差。本文優(yōu)化了傳統(tǒng)的層次包圍盒碰撞檢測算法，并使用GPU并行計算，進一步加快了碰撞檢測算法的速度。本文主要研究內(nèi)容如下：（1）以現(xiàn)有碰撞檢測算法為基礎(chǔ)，歸納總結(jié)了基于空間分解的碰撞檢測算法和基于層次包圍盒的碰撞檢測算法，分析并比較各類碰撞檢測算法的優(yōu)缺點。
4、（2）對構(gòu)造層次包圍盒樹算法進行優(yōu)化。分析哈夫曼法構(gòu)造層次包圍盒樹的實現(xiàn)方式，提出使用平衡二叉樹法對構(gòu)造層次包圍盒樹的優(yōu)化方案，節(jié)省了構(gòu)造層次包圍盒樹的耗時。（3）實現(xiàn)優(yōu)化后的構(gòu)造層次包圍盒樹算法的并行化。對優(yōu)化后的構(gòu)造層次包圍盒算法進行可行性分析，并在CUDA平臺上對其進行并行化，進一步節(jié)省了構(gòu)造層次包圍盒樹的耗時。（4）實現(xiàn)層次包圍盒碰撞檢測算法的并行化。分析串行碰撞檢測算法中雙重遍歷層次包圍盒樹的實現(xiàn)方式，針對其存在無效遍歷增加算法耗時的缺點，提出并行化的解決方案，并在CUDA平臺上對其進行并行化。并行遍歷層次包圍盒樹屏蔽了無效遍歷的算法耗時，從而加快了碰撞檢測算法的速度。試驗驗證
5、表明，優(yōu)化后的層次包圍盒碰撞檢測算法具有更高的效率，有效的提高了構(gòu)造層次包圍盒樹和遍歷層次包圍盒樹的速度。關(guān)鍵詞碰撞檢測；層次包圍盒；CUDA；平衡二叉樹；并行化；IAbstractWiththedevelopmentofvirtualrealityandtheimprovementofpeople'srequirementofexperience,theinstantaneityandaccuracyofcollisiondetectionisalsoincreased.Thehierarchicalboundingboxcollisiondetectionalgorithmsdivi
6、deobjectintodifferentscaleofboundingbox,sothesealgorithmhashigheraccuracyandlowerinstantaneity.Thispaperoptimizesthetraditionalhierarchicalboundingboxcollisiondetectionalgorithmandimplementsthealgorithm'sparallelizationusingGPU,acceleratingthespeedofcollisiondetectionalgorithm.Thefollowingpartsar
7、eincludedinthisarticle:(1)Basedontheexistingcollisiondetectionalgorithm,thispapersummarizesthecollisiondetectionalgorithmbasedonspacedecompositionandthecollisiondetectionalgorithmbasedonhierarchicalboundingbox,analyzin
