三種經(jīng)典網(wǎng)格細(xì)分算法的研究與分析

王世江

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

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

中圖法分類號：TP391

文獻(xiàn)標(biāo)識碼：A

0引言

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

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

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

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

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

定義4偶點(diǎn)是在每一級細(xì)分中，所有從上一級控制點(diǎn)繼承得到的點(diǎn).

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

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

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

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

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

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

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

如圖2所示

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

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

2結(jié)束語

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