資源描述：
《碰撞檢測中的包圍盒算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第21卷第12期重慶工學(xué)院學(xué)報(自然科學(xué))20o7年12月、1．2lNo．J2JournalofChon~ngInstituteofTechnology(NaturalScienceEdition)Dec．20ar7【電子與自動化】碰撞檢測中的包圍盒方法何偉，李勇，蘇虎(西南交通大學(xué)電氣工程學(xué)院，成都610031)‘：c_協(xié)^、0■：jk¨2=^=摘要：討論了當(dāng)前虛擬環(huán)境中應(yīng)用比較廣泛的2類碰撞檢測算法——空間剖分法和層次包圍盒霞法．重點對層次包圍盒算法中的軸向包圍盒(AA船)法、方向包圍盒(OBB)法和固定方向凸包包圍盒(F1)H)法從包圍盒的構(gòu)建、相交檢測等方面做了詳細(xì)分析，
2、并從計算復(fù)雜度、適用范圍等方面對這3類方法進行了比較關(guān)鍵詞：虛擬環(huán)境；碰撞檢測；包圍盒中圖分類號：TIB91．7文獻標(biāo)識碼：A文章編號：1671一~2,t(2oo7)12—0148—05電：年爾爾綿簾書出家爾替筇爾爾出牢．矯爾希綿綿爾磚宋出石綿夼希術(shù)爾石綿{AnalysisonBoundingBoxTechnologyinCollisionDetectionHEWei．，UY0ng，SUHu(SchoolofFlectricalEngineering，SouthwestJiaotongUniversity,Ch~n#u610031，China)Abstract：Thispaper
3、discussestwokindsofcolisiondetectionalgorithmwidelyusedinpresentvirtualen—vlronment：SpaceDecompositionmethodandBoundmgBoxmethod，elaboratesOntheintersectiondetectandeffectivenessofaxis．a(chǎn)lignedboundingboxes(AABB)method，orientedboundingbox(OBB)method，fixeddirectionshulls(FDH)method，andcomparesth
4、ethreemethodsintermsofcomputingcomplexity，applicationscope，ete．Keywords：virtualenvironment；collisiondetection；boundingbox碰撞檢測(CollisionDetection)就是檢測虛擬場盒(Oriented"BoundingBox，簡稱OBB)[3l、固定方向景中不同對象之間是否發(fā)生了碰撞．從幾何上講，凸包包圍盒(FixedDirectionsHuls，簡稱FDH)【j碰撞檢測表現(xiàn)為2個多面體的相交測試問題．近等．年來，國內(nèi)外學(xué)者在碰撞檢測領(lǐng)域中做了很多有層次包圍
5、盒方法的核心思想是用體積略大而意義的工作，并提出了一些高效的檢測方法．其中幾何特性簡單的包圍盒來近似地描述復(fù)雜的幾何層次包圍盒方法又是其中較好的算法．根據(jù)包圍對象，從而只需對包圍盒重疊的對象進行進一步盒類型的不同可以分為軸向包圍盒(AxisAligned的相交測試．此算法使用了層次結(jié)構(gòu)模型，其目標(biāo)BoundingBox，簡稱AABB)[1l、包圍球【2l、方向包圍是盡可能地減少進行相交測試的幾何對象的數(shù)·收稿日期：2007—10—13基金項目：成都市科技攻關(guān)課題(0r7ccYB256Gx一010)．作者簡介：何偉(198卜)，男，四川成都人，碩士研究生，主要從事智能交通系統(tǒng)研究何
6、偉，等：碰撞檢測中的包圍盒方法149目．本文中將對層次包圍盒方法中的幾種主要算法加以討論．2經(jīng)典包圍盒算法1層次包圍盒算法2．1包圍球一個給定對象的包圍球(Sphere)被定義為包2個采用層次包圍盒樹結(jié)構(gòu)的物體的碰撞檢含該對象的最小球體．計算給定對象的包圍球，首測過程如下[5]：首先判斷2棵樹的根節(jié)點的包圍先需分別計算對象的基本幾何元素集合中所有元盒是否相交，如果不相交，那么這2個物體肯定不素頂點的坐標(biāo)、'，坐標(biāo)和：坐標(biāo)的均值，以確定發(fā)生碰撞；否則遞歸遍歷2棵樹，對相應(yīng)的子節(jié)點包圍球的球心．再由球心c與3個最大值坐標(biāo)所進行求交判斷．如果參與求交運算的2個子節(jié)點確定的點間的距離計算
7、半徑r，存儲一個包圍球只中至少有一個為非葉節(jié)點，則檢測2節(jié)點的包圍需2個浮點數(shù)．盒是否相交，如果不相交則不必再判斷子節(jié)點；若對于2個包圍球(cl，r1)和(c2，r2)，如果球心2節(jié)點均為葉節(jié)點，且檢測出它們的包圍盒相交，距離小于半徑之和，即Icl—c2I
