計(jì)算三角網(wǎng)絡(luò)模型上的最直測(cè)地線.pdf

1、測(cè)地線是曲面和任意流形上直線這一概念的一般化,求解三角網(wǎng)格模型的測(cè)地線在計(jì)算機(jī)圖形學(xué)和模式識(shí)別研究以及工業(yè)設(shè)計(jì)和制造領(lǐng)域都有廣泛的應(yīng)用。隨著離散網(wǎng)格模型越來(lái)越多的應(yīng)用,理論研究和工業(yè)設(shè)計(jì)都要求設(shè)計(jì)準(zhǔn)確和高效的求解測(cè)地線算法。
　　 測(cè)地線在光滑曲面上有很好的幾何性質(zhì),也有相應(yīng)的測(cè)地線偏微分方程表達(dá)以及一些解析的方法來(lái)求解。在離散模型上,測(cè)地線不能完全保持連續(xù)情況下的所有幾何性質(zhì),因而產(chǎn)生了不同的定義。目前,在離散網(wǎng)格上研究最多是

2、求解最短測(cè)地線的方法,主要有三類(lèi)解決方案。一類(lèi)是[3]引入的連續(xù)Dijkastra算法,它們從源點(diǎn)開(kāi)始把測(cè)地線經(jīng)過(guò)的多邊形序列展開(kāi)到一個(gè)平面上的。這些算法的絕對(duì)近似性能比都是1,根據(jù)所采用的策略和數(shù)據(jù)結(jié)構(gòu)不同,時(shí)間復(fù)雜度從O(n2logn)到O(nlogn)不等。第二類(lèi)算法用一種前端面向前傳播的方式,每一步在三角形上求解測(cè)地線微分方程來(lái)更新測(cè)地距離,比連續(xù)Dijkastra算法有更好的絕對(duì)近似性能比?；诓煌臏?zhǔn)確性要求算法的時(shí)間復(fù)雜度

3、從O(nlogn)到O(n)不等。最后一類(lèi)方案在當(dāng)前Dijkastra最短路關(guān)聯(lián)的三角形序列上,構(gòu)造新的細(xì)分子圖并求解新的Dijkastra最短路,直到所需的精度。它的時(shí)間和空間花費(fèi)比較大。其中,實(shí)際應(yīng)用最多的FMM(Fast Marching Method)是第二類(lèi)方法。
　　 最直測(cè)地線有更完整的微分幾何定義和理論系統(tǒng),在圖形學(xué)領(lǐng)域內(nèi),對(duì)它的研究和應(yīng)用還比較少。有關(guān)的算法有根據(jù)定義的左右曲面角相等,法截面法和切向投影等。這些

4、方法的精度都局限在一階截?cái)嗾`差,在離散的網(wǎng)格上有嚴(yán)重的累積誤差。我們提出了兩個(gè)個(gè)實(shí)際的線性時(shí)間的算法求解三角網(wǎng)格上一點(diǎn)開(kāi)始沿給定切方向的最直測(cè)地線。我們的算法不需要額外的鈍角三角形處理,并且在網(wǎng)格頂點(diǎn)和網(wǎng)格邊處有統(tǒng)一的計(jì)算,在凹模型和凸模型上都得到了更好的準(zhǔn)確性和效率,很大程度上解決了已有算法的累積誤差問(wèn)題。
　　 本文的主要貢獻(xiàn)有:
　　 1)系統(tǒng)的研究了測(cè)地線的微分幾何定義和離散網(wǎng)格上兩種最主要的定義最短測(cè)地線和最直

5、測(cè)地線。分析了測(cè)地線微分幾何性質(zhì)和行為,最短測(cè)地線與最直測(cè)地線之間的關(guān)系以及不同的特點(diǎn)和求解方式。
　　 2)完整的定義了求解最直測(cè)地線的法截面方法,從幾何的角度解釋了算法的有效性和誤差來(lái)源。通過(guò)實(shí)驗(yàn)和理論證明了算法具有一階截?cái)嗾`差,相當(dāng)于連續(xù)曲面上求解測(cè)地線的歐拉法。
　　 3)提出切向法向調(diào)整算法求解最直測(cè)地線,很好的解決了已有算法的累積誤差問(wèn)題,在粗糙的網(wǎng)格上取得了連續(xù)曲面上的四階龍格-庫(kù)塔法的準(zhǔn)確性。分析和驗(yàn)證了