[發(fā)明專利]基于三角網(wǎng)格變形體的自碰撞檢測方法

無效

• 申請?zhí)枺?/td>: 201210030632.3
• 申請日: 2012-02-12
• 公開（公告）號: CN102609992A
• 公開（公告）日: 2012-07-25
• 發(fā)明（設計）人: 沈旭昆;趙凌;鄭小萌;趙沁平
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06T19/00
• 分類號: G06T19/00
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 李新華;成金玉

技術領域

本發(fā)明屬于計算機虛擬現(xiàn)實技術領域，具體地說是從開發(fā)包含真實細節(jié)的可變形物體的交互式仿真系統(tǒng)的實際需求出發(fā)，通過研究可變形物體自碰撞檢測技術的現(xiàn)狀，為方便用戶進行可變形實體建模仿真中真實變形操作而開發(fā)的一個三角網(wǎng)格變形體自碰撞檢測方法或系統(tǒng)。

背景技術

近二十多年來，研究人員在碰撞檢測領域中做了相當多有意義的工作，對虛擬現(xiàn)實的發(fā)展起到了推動作用。碰撞檢測算法種類繁多，各有側重。文獻1-H.C.Longuet-Higgins，A?computer?algorithm?for?reconstructing?a?scene?from?two?projections[J].Nature，1981.293(10)：133-135提出了一類連續(xù)碰撞測算法，連續(xù)碰撞檢測算法通過對結構空間精確建模，較好地解決了離散碰撞檢測算法存在的問題。但這類算法的缺點是計算量較大，計算速度比較慢，尤其是在大規(guī)模場景中無法實現(xiàn)實時的碰撞檢測。所以盡管離散碰撞檢測算法存在一些問題，但因其檢測過程的快速性能夠較好地迎合人們對實時碰撞檢測的需求，目前仍是碰撞檢測算法研究的重點和熱點。

縱觀前人的研究，大致可分為基于圖形和基于圖像的碰撞檢測算法。在基于圖形的碰撞檢測上，研究人員已經(jīng)做了大量的工作，形成了空間分解法和層次包圍體法等成熟算法。文獻2-Jimenez?P，Thomas?F，Torras?C.Collision?Detection：A?Survey.Computers?and?Graphics[J]，2001.25(2)：269-285所采用的空間分解法主要是先將整個虛擬空間劃分成等體積的規(guī)則單元格，以此將場景中的物體分割成更小的組群，并只對占據(jù)了同一單元格或相鄰單元格的幾何對象進行相交測試。一般來說，空間分解法在每次碰撞檢測時都需要確定每個物體占有的空間單元。如果場景中不可動的模型很多，可以預先劃分好空間單元格并確定每個模型占有的空間單元。當有模型運動時，只需要重新計算運動模型所占有的空間就可以了。空間分解法比較典型的例子有k-d樹、八叉樹、BSP樹、四面體網(wǎng)和規(guī)則網(wǎng)格等。采用層次劃分方法進行空間分解可以進一步提高算法的速度。

文獻3-Daniel?S.Coming?and?Oliver?G.Staadt，Kinetic.Sweep?and?Prune?for?Collision?Detection[A]，Workshop?on?Virtual?Reality?Interaction?and?Physical?Simulation[C]，2005提出了包圍盒技術，層次包圍體法的核心思想是用體積略大而幾何特性簡單的包圍體來近似的描述復雜的幾何對象，從而只需對包圍體重疊的對象進行進一步的相交測試。此外通過構造樹狀層次結構可以越來越逼近對象的幾何模型，直到幾乎完全獲得對象的幾何特征。基于包圍體的碰撞檢測方法的不同點在于樹節(jié)點的包圍體類型不同或者采用不同的技術來建立、更新和平衡包圍體樹。典型的包圍體有：軸對齊包圍盒(AABB)、包圍球(Sphere)、有向包圍盒(OBB)和離散有向多面體k-DOP。其中前兩者的計算簡單但是包圍程度相對不夠緊密，而OBB的方法由于考慮到軸向所以包圍相對緊密，但是計算相對比較復雜。而K-DOPs算法則在全局坐標系中計算物體的包圍盒，每當物體運動時，其包圍盒層次結構需要重新計算。

近些年，隨著圖形硬件計算性能的迅速增長，基于圖像的碰撞檢測算法進入了一個新的快速發(fā)展的階段。該方法一般將三維幾何對象通過投影繪制到圖像平面上，降維得到一個二維的圖像空間；然后分析該空間中保存在各類緩存的信息，進而檢測出對象之間是否發(fā)生相交。這類算法的優(yōu)勢在于能有效利用圖形硬件加速技術來減輕的計算負荷，從而達到提高算法效率的目的。