高質(zhì)量三角網(wǎng)格的生成及性質(zhì)研究.pdf

1、在計算機(jī)圖形學(xué)應(yīng)用和研究領(lǐng)域，三角網(wǎng)格由于其擬合連續(xù)曲面時極高的自由度和精確度、簡潔的數(shù)據(jù)結(jié)構(gòu)、快速的渲染過程等優(yōu)點而被廣泛應(yīng)用于數(shù)字幾何處理、渲染、幾何建模等分支領(lǐng)域。從本質(zhì)上看，所有此類工作的最終目的均在于根據(jù)各自不同的應(yīng)用和研究目的，提出各自不同的高質(zhì)量三角網(wǎng)格定義，并研發(fā)出相應(yīng)的生成算法。由于三角網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)被劃分為網(wǎng)格節(jié)點的幾何坐標(biāo)及節(jié)點之間的三角片拓?fù)溥B接關(guān)系兩部分，各種高質(zhì)量三角網(wǎng)格的生成算法可被劃歸為三大類，即給定節(jié)點

2、的幾何位置求其最優(yōu)拓?fù)浣Y(jié)構(gòu)、給定節(jié)點間的拓?fù)溥B接關(guān)系求其最優(yōu)位置坐標(biāo)、同時改變輸入網(wǎng)格的幾何位置和拓?fù)浣Y(jié)構(gòu)以生成具有更高質(zhì)量的網(wǎng)格。本文以高質(zhì)量三角網(wǎng)格的定義為中心，分別討論了這三類不同的高質(zhì)量三角網(wǎng)格，研究其理論性質(zhì)及實際應(yīng)用并提出相應(yīng)的生成方法，分別用以解決計算幾何領(lǐng)域的Delaunay三角化、數(shù)字幾何處理領(lǐng)域的網(wǎng)格變形以及采樣領(lǐng)域的藍(lán)噪采樣問題。本文主要有以下幾方面貢獻(xiàn)：
　　 1.研究了二維平面內(nèi)給定節(jié)點的幾何位置情況下

3、具有最優(yōu)拓?fù)浣Y(jié)構(gòu)的高質(zhì)量三角網(wǎng)格--Delaunay三角剖分所具有的理論性質(zhì)。我們刻畫了用于生成Delaunay_角化的翻邊操作為其幾何Laplace矩陣所帶來的影響，并用以重新更加簡潔地證明了計算幾何領(lǐng)域的一個經(jīng)典定理。采用該定理，我們進(jìn)一步刻畫了Delaunay三角剖分的譜性質(zhì)，并同樣更加簡潔地證明了關(guān)于Delaunay三角化的另外一個著名定理。
　　 2.研究了給定拓?fù)浣Y(jié)構(gòu)下的高質(zhì)量三角網(wǎng)格在應(yīng)用于二維平面內(nèi)的網(wǎng)格變形問題

4、時其節(jié)點所應(yīng)具有的最優(yōu)幾何位置。我們將該應(yīng)用中的高質(zhì)量三角網(wǎng)格定義為正確的三角化，即變形算法將初始輸入網(wǎng)格嵌入到目標(biāo)邊界形狀內(nèi)所生成的網(wǎng)格與初始網(wǎng)格之間構(gòu)成一一映射關(guān)系。我們分析了一一映射性質(zhì)的幾何含義，并提出了一種迭代式的算法，交替地更新節(jié)點的幾何位置和對應(yīng)的幾何Laplace矩陣直至收斂。我們證明了若存在正確的三角化嵌入，則算法一定能收斂至其中一個；若不存在任何正確的嵌入，則我們的算法必然發(fā)散至崩潰。針對生成的嵌入中包含一些低質(zhì)量的

5、狹長三角片的問題，我們提出一種后處理方法，用于打開這些三角片，使其變得更加均勻。
　　 3.提出了一種同時改變幾何和拓?fù)涞母哔|(zhì)量三角網(wǎng)格重構(gòu)技術(shù)，用于解決平面內(nèi)的藍(lán)噪采樣問題。此時的高質(zhì)量三角網(wǎng)格被定義為容量約束的Delaunay三角化，即網(wǎng)格所包含的三角片面積盡可能均勻分布，同時其拓?fù)浣Y(jié)構(gòu)為Delaunay三角剖分結(jié)構(gòu)。我們提出一種迭代性的生成算法，交替地優(yōu)化節(jié)點的幾何位置和對應(yīng)的Delaunay三角剖分拓?fù)浣Y(jié)構(gòu)直至收斂至某個

6、穩(wěn)定的Delaunay三角化。我們通過譜分析的方法證明了容量約束的Delaunay三角化節(jié)點分布具有優(yōu)異的藍(lán)噪特性，并且生成算法的效率比當(dāng)前主要的競爭者算法快至少一個數(shù)量級。另外，我們進(jìn)一步將算法推廣至采樣區(qū)域內(nèi)任意給定的密度函數(shù)，以生成非均勻的藍(lán)噪分布，該技術(shù)可應(yīng)用于灰度圖的半調(diào)化問題。
　　 4.我們將二維平面內(nèi)的容量約束的Delaunay三角概念其推廣至三維空間曲面，用以解決流形曲面上的藍(lán)噪采樣問題。此時的高質(zhì)量三角網(wǎng)格為

7、容量約束的曲面三角化，在保持三角片面積均勻性的同時其拓?fù)浣Y(jié)構(gòu)為曲面上的類Delaunay三角化結(jié)構(gòu)。我們采用與二維采樣情況相同的思路，在曲面上迭代式地優(yōu)化節(jié)點的幾何位置和拓?fù)浣Y(jié)構(gòu)。曲面上的微分域分析驗證了我們的算法所生成的網(wǎng)格節(jié)點分布具有典型的藍(lán)噪特性，并且我們的算法是第一種能夠嚴(yán)格控制采樣點數(shù)目的曲面藍(lán)噪采樣算法，而其效率與其他算法相比具有極強(qiáng)的競爭力。針對曲面上的非均勻采樣應(yīng)用，我們將密度函數(shù)引入迭代優(yōu)化的能量，使得算法也能生成諸如