基于Morse理論的三角網(wǎng)格特征提取及簡化研究

張春亢

貴州大學(xué)礦業(yè)學(xué)院，貴陽 550025

LiDAR等新技術(shù)能快速獲取海量模型表面離散數(shù)據(jù)，面對這些數(shù)據(jù)，僅通過提高計算機性能已不能滿足實際需求，選擇合適的數(shù)據(jù)表達方式，對其進行簡潔、有效描述是亟待解決的問題。傳統(tǒng)的幾何方法，如三角網(wǎng)格等能對空間表面模型的幾何信息進行精確表達且便于計算與分析，但其數(shù)據(jù)量大、冗余多、計算復(fù)雜?；贛orse理論建立的拓?fù)浔磉_，能用少量的數(shù)據(jù)實現(xiàn)對模型表面的描述，并揭示模型表面的拓?fù)湫螒B(tài)。本文基于Morse理論，對表面模型拓?fù)涮卣鞯臄?shù)據(jù)結(jié)構(gòu)基礎(chǔ)、拓?fù)涮卣魈崛∨c簡化的理論與方法等進行了深入探討。主要內(nèi)容如下：

(1) 詳述了經(jīng)典Morse理論及關(guān)鍵點、關(guān)鍵線、Morse-Smale復(fù)形、拓?fù)浜喕认嚓P(guān)概念，引出了針對離散數(shù)據(jù)模型的經(jīng)典Morse理論的兩種離散化形式：離散Morse理論與分段線性Morse理論，并對分段線性Morse理論及其在地學(xué)中的應(yīng)用進行了較為詳細的闡述。

(2) 三角網(wǎng)格是實現(xiàn)拓?fù)涮卣魈崛〉臄?shù)據(jù)結(jié)構(gòu)基礎(chǔ)，針對拓?fù)涮卣魈崛∨c簡化耗時長，而分塊處理可以有效提高效率的問題，研究了海量三角網(wǎng)格的非耦合剖分方法。首先利用動態(tài)三角網(wǎng)生長算法構(gòu)建分割墻(DeWall)，從點云上切割特定大小與形狀的獨立數(shù)據(jù)塊，避免分治算法的深度遞歸；然后用分治算法對切塊剖分，并給出了切塊邊界錯誤三角形刪除算法；迭代上述過程完成三角網(wǎng)子網(wǎng)剖分，并依據(jù)非耦合區(qū)域分解模式完成子網(wǎng)合并；同時引入流計算的思想，進一步提高算法的空間性能。試驗表明：①算法獲得了優(yōu)異空間性能，且算法的整體時間復(fù)雜度約為O(nlog(δ))，接近線性；②算法構(gòu)建的各子三角網(wǎng)之間具有非耦合性質(zhì)，為分塊進行拓?fù)涮卣魈幚硖峁┝怂惴ㄖ巍?/p>

(3) 研究了小尺度地形拓?fù)涮卣鞯木_提取與簡化算法。針對基于Morse理論提取的小尺度地形拓?fù)涮卣骱写罅俊皞翁卣鳌?，并形成對地形的“過剖分”問題。首先通過定義特征點指數(shù)(FPI)等一系列概念，模擬特征點周圍區(qū)域的地表形態(tài)，建立了特征點重要性度量指標(biāo)。并以此為基礎(chǔ)，提出了地表特征的精確提取與多層次表達算法。新算法可以有效剔除“偽特征”，實現(xiàn)小尺度復(fù)雜地形拓?fù)涮卣骶_提取，且具有良好的抗噪性與穩(wěn)健性，優(yōu)于現(xiàn)有的Persistence法與自然法則法。

(4) 研究推導(dǎo)了三維表面模型拓?fù)涮卣魈崛∨c簡化方法?；贛orse理論的特征提取算法在由二維擴展到三維表面模型時，提取的極大點與下降Morse復(fù)形為模型表面的有效特征，而極小點與上升Morse復(fù)形為無實際意義的錯誤特征，這不但降低了特征提取效率，且易導(dǎo)致簡化誤差。為此，推導(dǎo)了三維表面模型拓?fù)涮卣鞯奶崛》椒?，實現(xiàn)了針對三維表面模型的單復(fù)形拓?fù)淠Ｐ吞崛　；趕eparatrix persistence度量方法與MS復(fù)形簡化算法，推導(dǎo)了單復(fù)形拓?fù)淠Ｐ偷暮喕椒?。試驗表明：單?fù)形模型能有效識別三維模型表面的拓?fù)涮卣鳎苊忮e誤特征的提取，提高了效率；單復(fù)形簡化方法可以有效去除“偽特征”，并且在簡化過程中保持了復(fù)形的完整性與一致性。

(5) 設(shè)計開發(fā)了“基于Morse理論的三角網(wǎng)格拓?fù)涮卣魈崛〖昂喕痹囼炏到y(tǒng)，將論文研究的有關(guān)算法與模型集成為原型系統(tǒng)。通過典型數(shù)據(jù)對試驗系統(tǒng)及相關(guān)算法與模型的可行性、正確性和有效性進行了驗證。