面向虛擬裝配的干涉檢測關(guān)鍵技術(shù)研究.pdf

1、干涉檢測技術(shù)是計算機圖形學中的一個關(guān)鍵技術(shù)，在虛擬裝配、虛擬手術(shù)、飛行導航、機器人路徑規(guī)劃和計算機游戲動畫等領(lǐng)域中有著非常廣泛的應(yīng)用。這些應(yīng)用領(lǐng)域通常要求系統(tǒng)能預(yù)計可能發(fā)生的干涉，并根據(jù)距離信息及時地對路徑進行調(diào)整和變更，以避免可能發(fā)生的干涉。因此，對于這些應(yīng)用領(lǐng)域來說，快速地判定對象的位置關(guān)系并提供一個準確的距離信息(分離距離、穿透深度和距離實現(xiàn)向量)成為圖形學算法設(shè)計工作的首要任務(wù)。它不僅僅局限于某個特定問題，涉及到計算機科學、動力

2、學、機械工程和數(shù)學等多個學科，對它展開研究具有重要的實踐意義和理論價值。但是迄今為止這個課題仍然存在許多問題沒有解決，特別是對計算精度要求很高的應(yīng)用環(huán)境。本論文研究的目的是將掃描線技術(shù)、包圍體層次樹、分支限界策略、啟發(fā)式搜索算法和非線性規(guī)劃理論等應(yīng)用到本課題的研究中，尋求本課題一些關(guān)鍵問題的快速和有效的解決方法。 本論文主要針對平面多邊形、凸多面體和空間曲面這三種模型的干涉檢測和距離求解問題進行了研究，并且獲得了一些有意義的成果

3、。 本論文的主要創(chuàng)新性工作如下： 1．提出了求解平面凸多邊形最小平移距離的QuasiQuickHull算法-QQH算法。QQH算法在QuickHull算法基礎(chǔ)上，利用面積計算對形態(tài)和進行隱式構(gòu)造，解決了平面凸多邊形的最小平移距離問題。算法先通過執(zhí)行兩次GJK(Gilbert-Johnson-Kerrthi)算法獲得TCSO(translational C-space obstacle)對象M上的兩互異頂點；再根據(jù)(三角形

4、)面積計算獲得與M內(nèi)接的初始多邊形P；然后確定P上距離原點最近的邊，并通過面積計算搜索M上與最近邊對應(yīng)的對拓頂點；然后利用新搜索到的對拓頂點更新P的邊界，迭代測試，直至找到M邊界上距離原點最近的邊或頂點為止。該方法給出了基于面積值判斷的快速終止條件，避免了異常情形的特殊處理，并能通過區(qū)域測試快速判定兩多邊形是否發(fā)生干涉。 2．提出了判定平面簡單多邊形位置關(guān)系的掃描線算法。算法在包圍體層次樹干涉檢測算法基礎(chǔ)上，利用掃描線技術(shù)判定單

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

6、包圍體層次樹距離算法基礎(chǔ)上，通過對單調(diào)鏈進行選擇性配對來確定可能包含最近點對的子邊界，解決了一般多邊形之間的分離距離問題。該算法先根據(jù)多邊形包圍盒的位置關(guān)系初步確定對可能包含最近點的關(guān)聯(lián)邊界，并對多邊形距離上界值進行初始化；然后，對關(guān)聯(lián)邊界進行單調(diào)性分解，并對單調(diào)性相同的鏈構(gòu)造包圍體層次樹；再利用包圍體層次樹距離算法對單調(diào)性互異的鏈對進行選擇性匹配，并根據(jù)最近獲得的鏈對的幾何信息來動態(tài)更新距離上界值；最后，利用層次樹距離算法迭代計算單調(diào)

7、鏈的距離，從而獲得多邊形的最近距離。該方法采用基于距離閾值的篩選策略對單調(diào)性互異的鏈對進行選擇性匹配，減少了包圍盒距離計算和邊對距離計算的次數(shù)，從而大大提高了算法的效率。 4．提出了一種求解平面簡單多邊形穿透深度的平移向量算法。該算法在旋轉(zhuǎn)標尺算法和邊界凸分解技術(shù)基礎(chǔ)上，通過搜索使得多邊形剛好發(fā)生接觸的最短平移向量來確定穿透深度的實現(xiàn)向量，解決了一般多邊形之間的穿透深度問題。該算法首先對一般多邊形構(gòu)造凸包并計算凸包的穿透深度；然

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

9、離的新方法。該方法在分離軸理論和非線性規(guī)劃的基礎(chǔ)上，通過搜索與最小平移距離實現(xiàn)向量對應(yīng)的一對最優(yōu)廣義分離平面，解決了凸多面體的最小平移距離問題。該方法首先提出了廣義分離平面的概念，并用一對最優(yōu)廣義分離平面準確地確定多面體的最小平移距離；然后根據(jù)最優(yōu)廣義分離平面對滿足的約束條件建立非線性等價模型，將最優(yōu)廣義分離平面對的搜索問題轉(zhuǎn)化非線性規(guī)劃問題；最后利用非線性優(yōu)化工具軟件對問題進行求解，從而獲得最小平移距離及其實現(xiàn)向量。該方法能有效避免死