面向虛擬裝配的干涉檢測關鍵技術研究

《面向虛擬裝配的干涉檢測關鍵技術研究》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、摘要干涉檢測技術是計算機圖形學中的一個關鍵技術，在虛擬裝配、虛擬手術、飛行導航、機器人路徑規(guī)劃和計算機游戲動畫等領域中有著非常廣泛的應用。這些應用領域通常要求系統(tǒng)能預計可能發(fā)生的干涉，并根據(jù)距離信息及時地對路徑進行調(diào)整和變更，以避免可能發(fā)生的干涉。因此，對于這些應用領域來說，快速地判定對象的位置關系并提供一個準確的距離信息(分離距離、穿透深度和距離實現(xiàn)向量)成為圖形學算法設計工作的首要任務。它不僅僅局限于某個特定問題，涉及到計算機科學、動力學、機械工程和數(shù)學等多個學科，對它展開研究具有重要的實踐意義和理論價值。但是迄今為止這個課題仍然存在許多問題沒有解決·特別是對計算精度要

2、求很高的應用環(huán)境。本論文研究的目的是將掃描線技術、包圍體層次樹、分支限界策略、啟發(fā)式搜索算法和非線性規(guī)劃理論等應用到本課題的研究中，尋求本課題一些關鍵問題的快速和有效的解決方法。本論文主要針對平面多邊形、凸多面體和空間曲面這三種模型的干涉檢測和距離求解問題進行了研究，并且獲得了一些有意義的成果。本論文的主要創(chuàng)新性工作如下：1．提出了求解平面凸多邊形最小平移距離的QuasiQuickHull算法—QQH算法。QQH算法在QuickHull算法基礎上，利用面積計算對形態(tài)和進行隱式構造，解決了平面凸多邊形的最小平移距離問題。算法先通過執(zhí)行兩次GJK(Gilbert-Johnson

3、-Kemhi)算法獲得TCSO(translafionalC-spaceobstacle)對象膨上的兩互異頂點；再根據(jù)(三角形)面積計算獲得與肘內(nèi)接的初始多邊形只然后確定P上距離原點最近的邊，并通過面積計算搜索J】If上與最近邊對應的對拓頂點；然后利用新搜索到的對拓頂點更新P的邊界，迭代測試，直至找到肘邊界上距離原點最近的邊或頂點為止。該方法給出了基于面積值判斷的快速終止條件，避免了異常情形的特殊處理，并能通過區(qū)域測試快速判定兩多邊形是否發(fā)生干涉。2．提出了判定平面簡單多邊形位置關系的掃描線算法。算法在包圍體層次樹干涉檢測算法基礎上，利用掃描線技術判定單調(diào)鏈的位置關系，解決

4、了一般多邊形之間的位置關系判定問題。該方法先對多邊形進行單調(diào)鏈分解；然后對單調(diào)鏈構造包國鑫層次樹，并利用包圍體層次樹的干涉檢測技術確定包圍盒發(fā)生干涉的單調(diào)鏈對；再根據(jù)掃描線技術判定鏈對的位置關系；最后，根據(jù)鏈對的測試結果來精確判定多邊形的位置關系。該方法能有效地區(qū)別邊界接觸和內(nèi)部相交兩種情形，并且提高了射線求交法判定多邊形包含關系的穩(wěn)定性。3．提出了一種計算平面簡單多邊形分離距離的單調(diào)鏈配對算法。該算法在包圍體層次樹距離算法基礎上，通過對單調(diào)鏈進行選擇性配對來確定可能包含最近點對的子邊界，解決了一般多邊形之間的分離距離問題。該算法先根據(jù)多邊形包圍盒的位置關系初步確定對可能包

5、含最近點的關聯(lián)邊界，并對多邊形距離上界值進行初始化；然后，對關聯(lián)邊界進行單調(diào)性分解，并對單調(diào)性相同的鏈構造包圍體層次樹；再利用包圍體層次樹距離算法對單調(diào)性互異的鏈對進行選擇性匹配，并根據(jù)最近獲得的鏈對的幾何信息來動態(tài)更新距離上界值：最后，利用層次樹距離算法迭代計算單調(diào)鏈的距離，從而獲得多邊形的最近距離。該方法采用基于距離閱值的篩選策略對單調(diào)性互異的鏈對進行選擇性匹配，減少了包圍盒距離計算和邊對距離計算的次數(shù)，從而大大提高了算法的效率。4．提出了一種求解平面簡單多邊形穿透深度的平移向量算法。該算法在旋轉(zhuǎn)標尺算法和邊界凸分解技術基礎上，通過搜索使得多邊形剛好發(fā)生接觸的最短平移向

6、量來確定穿透深度的實現(xiàn)向量，解決了一般多邊形之間的穿透深度問題。該算法首先對一般多邊形構造凸包并計算凸包的穿透深度；然后，對多邊形邊界進行凹、凸鏈分解，并用凸包穿透深度對鏈對進行篩選；再利用旋轉(zhuǎn)標尺算法確定發(fā)生在鏈對之間的對拓特征對，并計算對拓特征對的距離實現(xiàn)向量，同時用凸包穿透深度對之進行篩選；最后，搜索距離實現(xiàn)向量中使得多邊形剛好發(fā)生邊界接觸的最優(yōu)平移向量，進而確定一般多邊形之間的穿透深度的實現(xiàn)向量。該方法避免了形態(tài)和的顯式構造，實現(xiàn)起來比較簡單，并且僅需進行少量的迭代即可確定最優(yōu)平移向量。s．提出了用非線性規(guī)劃理論求解凸多面體最小平移距離的新方法。該方法在分離軸理論和

7、非線性規(guī)劃的基礎上，通過搜索與最小平移距離實現(xiàn)向量對應的一對最優(yōu)廣義分離平面，解決了凸多面體的最小平移距離問題。該方法首先提出了廣義分離平面的概念，并用一對最優(yōu)廣義分離平面準確地確定多面體的最小平移距離；然后根據(jù)最優(yōu)廣義分離平面對滿足的約束條件建立非線性等價模型，將最優(yōu)廣義分離平面對的搜索問題轉(zhuǎn)化非線性規(guī)劃問題；最后利用非線性優(yōu)化工具軟件對問題進行求解，從而獲得最小平移距離及其實現(xiàn)向量。該方法能有效避免死循環(huán)和異常情形的特殊處理，并且采用梯度下降法的迭代規(guī)則，經(jīng)過少量的迭代就可收斂。6．提出了計算曲面距離的統(tǒng)一方法