張春亢

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

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

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

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

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

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

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