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

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

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

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

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

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