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

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

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

中圖法分類號(hào)：TP391

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

0 引言

細(xì)分思想的產(chǎn)生可以追溯到二十世紀(jì)40年代末50年代初，當(dāng)時(shí)G.de Rham使用“砍角算法”描述光滑曲線的生成。細(xì)分曲線中常用的許多算法均是砍角算法。1974年，Chaikin在研究曲線的快速繪制時(shí)把離散細(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ì)是通過對(duì)初始控制點(diǎn)或者初始網(wǎng)格進(jìn)行一系列的細(xì)化過程，細(xì)化的極限生成所需要的曲線或者曲面。細(xì)分造型方法與傳統(tǒng)樣條、代數(shù)方法、變分造型等方法相比，在執(zhí)行效率、任意拓?fù)浣Y(jié)構(gòu)、細(xì)分曲面特征以及復(fù)雜幾何形狀等方面都有其獨(dú)特的優(yōu)勢(shì)。

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

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

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

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

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

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

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

1.2 細(xì)分算法的分類一般情況卜，對(duì)幾何網(wǎng)格細(xì)分算法的分類包括以下四個(gè)標(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ì)分策略，對(duì)于三角網(wǎng)格，在每一次細(xì)分過程中，保留每個(gè)三角網(wǎng)格中所有舊控制點(diǎn)的同時(shí)，在網(wǎng)格的每條邊上插入新點(diǎn)并兩兩相連，然后與舊控制點(diǎn)一起得到四個(gè)新的三角網(wǎng)格；對(duì)于四角網(wǎng)格，除了在網(wǎng)格的每條邊上插入新點(diǎn)外，還需要在網(wǎng)格中間另外插入一個(gè)新點(diǎn)并與另外四條邊上的新點(diǎn)相連，從而得到四個(gè)新的四角網(wǎng)格。點(diǎn)分裂細(xì)分方法則是一種1 N的細(xì)分策略，N為該點(diǎn)的Valence，每個(gè)頂點(diǎn)將分裂為N個(gè)新頂點(diǎn)，然后按照一定的規(guī)則將新頂點(diǎn)重新連接組成新的網(wǎng)格。

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

1.3.1 Loop算法Loop細(xì)分算法是Loop于1987年在其碩士論文中提出的一種逼近型三角形面分裂細(xì)分算法。它是基于B樣條的一種策略，應(yīng)用于規(guī)則網(wǎng)格時(shí)可以產(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)。顯然對(duì)邊界與褶皺采用特殊的規(guī)則實(shí)際上產(chǎn)生的是一條三次樣條曲線。

1.3.2 Catmull-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)格中每個(gè)點(diǎn)相對(duì)應(yīng)的新控制點(diǎn)：權(quán)B則生成對(duì)應(yīng)于每條邊的新點(diǎn)：而權(quán)C生成的新點(diǎn)與控制網(wǎng)格中的每個(gè)面相對(duì)應(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)以及兩個(gè)相鄰多邊形質(zhì)心的平均值；V型點(diǎn)的計(jì)算相對(duì)復(fù)雜，它取決于該點(diǎn)的Valence，而邊界與褶皺上的細(xì)分規(guī)則與Loop格式相同，圖3是Catmull—CIark算法的權(quán)圖。

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

2 結(jié)束語(yǔ)

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