王世江

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

關(guān)鍵詞：細分逼近插值

中圖法分類號：TP391

文獻標識碼：A

0引言

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

1網(wǎng)格細分算法的分類及比較

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

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

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

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

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

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

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

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

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

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

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

如圖2所示

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

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

2結(jié)束語

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