三種經典網格細分算法的研究與分析

王世江

摘要：曲面造型方法由于其局部性好、計算量小、算法簡中、響應速度高等優點已經廣泛應用于計算機圖形學、CAGD、計算機動畫以及虛擬現實領域。網格細分是一種離散造型方法.可以從數字化儀等設備直接獲得數據。介紹了近年來提出的一些細分算法對其中幾種比較經典的算法進行了簡中的分類和比較，論述了各自的適用范圍。

關鍵詞：細分逼近插值

中圖法分類號：TP391

文獻標識碼：A

0引言

細分思想的產生可以追溯到二十世紀40年代末50年代初，當時G.de Rham使用“砍角算法”描述光滑曲線的生成。細分曲線中常用的許多算法均是砍角算法。1974年，Chaikin在研究曲線的快速繪制時把離散細分的概念引入到圖形學界：1978年Catmnll和Clark…以及Doo和Sabinl21分別發表了一篇在圖形學領域具有里程碑意義的論文，也就是圖形學界推崇的Catmul—Clark算法和Doo—Sabin算法，標志著網格細分方法研究的真正開始：1987年，Loop在他的碩士論文中提出了Loop細分策略，細分造型方法的實質是通過對初始控制點或者初始網格進行一系列的細化過程，細化的極限生成所需要的曲線或者曲面。細分造型方法與傳統樣條、代數方法、變分造型等方法相比，在執行效率、任意拓撲結構、細分曲面特征以及復雜幾何形狀等方面都有其獨特的優勢。

1網格細分算法的分類及比較

1.1概念與術語定義1對于四邊形網格M中的任一頂點v，如果v為內部頂點且價不等于4或v為邊界頂點且價不等于3或2，則稱v為奇異頂點。非奇異頂點稱為正則頂點。

定義2權圖(Masks)表示舊控制點計算新控制點規則的映射，其中新控制點在映射中用黑點表示，在每個舊控制點旁邊的數字代表細分系數。

定義3奇點(0da Vertices)是在每一級細分中，按照某種細分規則所有新生成的點.在三角網格中，奇點也就是邊點，實際上是將每條邊的中點作為一個新點重新計算新的位置所得到的點.

定義4偶點是在每一級細分中，所有從上一級控制點繼承得到的點.

定義5某項點的價(Valence)是指與該項點通過公共邊相連的頂點個數.

定義6在一個網格中，如果的一條邊只屬于一個面，稱這條邊為邊界邊(boundary edge)：如果一個頂點屬于邊界邊則稱此頂點為邊界頂點(或邊界點，boundary vertex)：至少包含一個邊界頂點的面稱為邊界面(boundary face)。非邊界的邊、頂點和面分別稱為內部邊(internal edge)、內部頂點(interna[vertex)和內部面(internaI face)

1.2細分算法的分類一般情況卜，對幾何網格細分算法的分類包括以下四個標準：①生成網格的類型(三角網格和四角網格)；②細分規則的類型(面分裂和點分裂)：③算法是逼近型還是插值型；④規則曲面的極限曲面光滑性(C1，C2等)。

在現有的典型細分算法中，面分裂的細分方法，實際上就是一種1—4的細分策略，對于三角網格，在每一次細分過程中，保留每個三角網格中所有舊控制點的同時，在網格的每條邊上插入新點并兩兩相連，然后與舊控制點一起得到四個新的三角網格；對于四角網格，除了在網格的每條邊上插入新點外，還需要在網格中間另外插入一個新點并與另外四條邊上的新點相連，從而得到四個新的四角網格。點分裂細分方法則是一種1 N的細分策略，N為該點的Valence，每個頂點將分裂為N個新頂點，然后按照一定的規則將新頂點重新連接組成新的網格。

1.3幾種經典細分算法的介紹與比較在細分算法中比較具有代表性的包括Loop算法、Doo-Sabin算法以及Catmull-CIark算法下面對這幾種細分算法分別介紹并進行比較。

1.3.1Loop算法Loop細分算法是Loop于1987年在其碩士論文中提出的一種逼近型三角形面分裂細分算法。它是基于B樣條的一種策略，應用于規則網格時可以產生C²連續的曲面，在非正規點處則可達到C連續。Loop細分策略的權圖如圖1所示，其中圖1(a)為內部的奇點，圖1(b)為內部的偶點，圖1(c)為邊界或褶皺上的奇點，圖l(d)為邊界或褶皺上的偶點。顯然對邊界與褶皺采用特殊的規則實際上產生的是一條三次樣條曲線。

1.3.2Catmull-Clark(C—C)算法C-C算法是一種基于張量積雙三次樣條的逼近型四邊形面分裂細分策略，該策略除了在非正規點處僅C1連續外可以達到處處C2連續，其細分規則源于雙三次B樣條的細分權圖

如圖2所示

圖2中，利用權A可以得到和舊控制網格中每個點相對應的新控制點：權B則生成對應于每條邊的新點：而權C生成的新點與控制網格中的每個面相對應。這三種新生成的點分別稱為V(Ver-tex)型點，E(Edge)型點和F(Face)型點。顯然，V型點是Odd點，E型點和F型點是Even點，F型點為其控制多邊形的質心；E型點則取該邊端點以及兩個相鄰多邊形質心的平均值；V型點的計算相對復雜，它取決于該點的Valence，而邊界與褶皺上的細分規則與Loop格式相同，圖3是Catmull—CIark算法的權圖。

1.3.3Doo-Sabin算法該算法從概念與原理上在幾種細分算法中最簡單，它是一種基于四邊形的點分裂細分策略，僅使用一個權圖就可以定義該策略.Doo-Sabin算法實際上是從Chaikin快速曲線生成算法的思想推廣而來的一種生成光滑曲面的方法，生成的曲面可以達到C1連續，從細分規則可以看出，細分后頂點的度均為4，非四邊形而的個數是細分前非四邊形的個數加定點度不為4的頂點數，且在細分過程中，始終保持不變。此外，細分在極限情形時，某個原始多邊形的細分極限趨向于該原始多邊形的中心，所以極限曲面插值于多邊形的中心，利用這個性質可以在產品設計中用來控制細分的極限曲面。

2結束語

上面介紹了三種經典細分算法的概念、光滑性以及細分規則，它們都是基于常規格式的細分算法，其中Loop格式是基于幾何三角網格的，CatmnlI-Clark和Doo-Sabin算法是基于四角網格的細分方法，對于Loop格式、以及Catmnll－Clark兩種面分裂細分算法，在算法的實現過程中需要以某個面為單位進行遞歸細分，其關鍵是根據算法的細分規則為每個面上各個點建立有序鄰接表，但是有序鄰接表的構造比較復雜，而且在細分的實現過程中會出現重復繪制的情況，因此這種通過有序鄰接表來實現遞歸細分的方法效率不高，Doo-Sabin細分算法是一種點分裂細分策略，能夠有效地將逼近算法和插值算法結合起來發揮兩者的優勢是一個不錯的選擇，這也將是我們今后的一個研究重點。