高質量三角網格的生成及性質研究.pdf

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

2、的幾何位置求其最優(yōu)拓撲結構、給定節(jié)點間的拓撲連接關系求其最優(yōu)位置坐標、同時改變輸入網格的幾何位置和拓撲結構以生成具有更高質量的網格。本文以高質量三角網格的定義為中心，分別討論了這三類不同的高質量三角網格，研究其理論性質及實際應用并提出相應的生成方法，分別用以解決計算幾何領域的Delaunay三角化、數字幾何處理領域的網格變形以及采樣領域的藍噪采樣問題。本文主要有以下幾方面貢獻：
　　 1.研究了二維平面內給定節(jié)點的幾何位置情況下

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

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

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

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

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