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

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

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

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

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

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

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

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

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

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