姚紅麗, 張 莉, 檀結(jié)慶

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230601)

0 引 言

近40年,細(xì)分方法是CAGD、CAD&CG的研究熱點之一;給定一個控制多邊形,根據(jù)選取的細(xì)分規(guī)則,通過計算機(jī)不斷細(xì)化控制多邊形,直接生成平滑的曲線曲面。由于細(xì)分方法適用于任意拓?fù)渚W(wǎng)格,在曲線/曲面重建以及幾何造型中有著廣泛的應(yīng)用。

根據(jù)極限曲線是否通過初始控制點,曲線細(xì)分格式被分成插值型和逼近型2種。插值型細(xì)分格式直接插值初始控制點并按需產(chǎn)生新點,生成的極限曲線能有效保留目標(biāo)曲線的細(xì)節(jié)特征。文獻(xiàn)[1]提出經(jīng)典的四點二重細(xì)分格式,并證明了生成的極限曲線可達(dá)C1連續(xù);文獻(xiàn)[2-4]提出不同的插值型細(xì)分格式。逼近型細(xì)分格式逼近初始控制多邊形,其生成的極限曲線連續(xù)階更高。文獻(xiàn)[5]提出割角細(xì)分法,引起圖形學(xué)屆的廣泛關(guān)注;文獻(xiàn)[6-10]提出不同的逼近型細(xì)分格式,促進(jìn)了細(xì)分方法的發(fā)展。為了將2種細(xì)分格式結(jié)合起來,文獻(xiàn)[11]首次提出融合型細(xì)分,先利用逼近型細(xì)分格式計算出每步細(xì)分時的偏移量,再通過對參數(shù)的調(diào)整,從而實現(xiàn)對控制點的插值。采用參數(shù)調(diào)節(jié)的方法的文獻(xiàn)也有很多。文獻(xiàn)[12]從三次B樣條曲線細(xì)分格式出發(fā),推導(dǎo)出2種融合型細(xì)分格式并分析了其相應(yīng)的連續(xù)性;文獻(xiàn)[13]通過對融合型細(xì)分格式中參數(shù)變量的適當(dāng)選取,從而衍生出具有良好性質(zhì)的新格式,實現(xiàn)對極限曲線的形狀調(diào)整;文獻(xiàn)[14]提出一種非靜態(tài)融合型細(xì)分格式并分析了其指數(shù)多項式的再生性;文獻(xiàn)[15]對一類融合型三重細(xì)分格式的一系列性質(zhì)進(jìn)行了分析。然而,參數(shù)調(diào)節(jié)的過程是非常冗雜的。文獻(xiàn)[16]“Interproximation”細(xì)分不僅能夠?qū)⒉逯敌秃捅平图?xì)分格式的優(yōu)勢有效地結(jié)合,而且避免了參數(shù)調(diào)節(jié)的冗雜過程;文獻(xiàn)[17]推導(dǎo)出相應(yīng)的幾何規(guī)則,將四點插值和三次B樣條細(xì)分格式結(jié)合起來,給出一種C2連續(xù)的插值逼近型細(xì)分格式;文獻(xiàn)[18]通過相應(yīng)的幾何規(guī)則,將四點插值和切割磨光細(xì)分格式結(jié)合起來,給出一種C1連續(xù)的四點插值-切割磨光細(xì)分格式。

鑒于插值逼近型格式的優(yōu)異表現(xiàn),本文建立一個帶雙參數(shù)的插值逼近型細(xì)分框架。該框架既包含了一些已有的細(xì)分格式,還派生出一些新的細(xì)分格式。它的極限曲線既能插值部分點,同時又能逼近其余點,能有效地生成和復(fù)現(xiàn)復(fù)雜的幾何圖形。

在自然界中,很多幾何圖形的輪廓上既有一些尖銳的地方需要被插值,同時又有其他平滑的地方需要被逼近,如圖1所示。

單一的插值型格式或是單一的逼近型格式都很難復(fù)現(xiàn)其輪廓曲線,而本文框架能夠簡單有效地復(fù)現(xiàn)其輪廓曲線。

圖1 輪廓上的黃色圓點需要被插值,其余地方需要被逼近

1 預(yù)備知識

(1)

其中,系數(shù)a={ai}i∈Z被稱為細(xì)分格式的掩模。

引理1[2]若細(xì)分格式(1)一致收斂,則

(2)

對細(xì)分格式應(yīng)用z-變換,即

(3)

其中,a(z)被稱為Laurent多項式。

2 帶參數(shù)的插值逼近型細(xì)分框架

本節(jié)針對融合型格式調(diào)參過程復(fù)雜的缺陷,構(gòu)造一類帶參數(shù)的插值逼近型細(xì)分框架,該框架無需調(diào)參就能自如地插值指定點并逼近其余點。另外,本節(jié)還設(shè)置了插值點的選取規(guī)則,根據(jù)此規(guī)則,能自動篩選出插值點的位置。

2.1 細(xì)分框架的構(gòu)建

在現(xiàn)有細(xì)分格式中,若想插值指定點并逼近其余點,融合型格式是一個比較合適的選擇,融合型格式為:

(4)

在細(xì)分迭代過程中,不斷產(chǎn)生新邊點和新頂點?？刂贫噙呅蔚拿織l邊所對應(yīng)產(chǎn)生的新點被稱為新邊點,每個控制點所對應(yīng)產(chǎn)生的新點被稱為新頂點。參數(shù)γ是否為0對極限曲線的影響如圖2所示。當(dāng)γ=0時,(4)式退化成插值型格式;當(dāng)γ≠0時,(4)式退化成逼近型格式。

插值型格式固定舊頂點的位置,生成新邊點,呈向外擴(kuò)張的趨勢。逼近型格式移動舊頂點的位置,生成新頂點及新邊點,呈向內(nèi)收縮的趨勢。

插值型格式和逼近型格式都有其自身獨特的優(yōu)勢。然而在實際應(yīng)用中,不僅要插值部分點,同時還要逼近其余點。因此,本文基于融合型格式,通過分段設(shè)置參數(shù)來滿足實際應(yīng)用需求。

圖2 參數(shù)γ的影響效果

(5)

(6)

(7)

(8)

根據(jù)初始數(shù)據(jù)點集被分成插值點集DI和逼近點集DA,新點的產(chǎn)生有4種情形。若相鄰兩點都是插值點,則選用(5)式進(jìn)行迭代,引入?yún)?shù)ω1;若相鄰兩點都是逼近點,則選用(6)式進(jìn)行迭代,引入?yún)?shù)ω2、γ;若相鄰兩點中既有插值點,又有逼近點,則選用(7)～(8)式進(jìn)行迭代。

設(shè)給定的初始控制多邊形是不封閉的,其頂點為P0、P1、…、Pn,需要增加2個頂點P-1、Pn+1。一般地,這2個頂點的位置向量分別取P-1=P0,Pn+1=Pn或P-1=2P0-P1，Pn+1=2Pn-Pn-1,從而得到新增的2個頂點P-1、Pn+1。

2.2 插值點的選取規(guī)則

(9)

利用差分代替微分,從而實現(xiàn)對離散數(shù)據(jù)點曲率的計算[19]。

本文建立下列3類插值點選取法規(guī)則。

拐點:拐點是曲線的凹凸分界點。在實際應(yīng)用中,曲率也用來判斷拐點的位置。首先,點Pi兩側(cè)的曲率值變號,即K(ti-1)K(ti+1)<0;其次,點Pi的曲率值K(ti)∈(-ε,ε)或不存在。若上述2個條件同時被滿足,點Pi為拐點。

3 連續(xù)性分析

為了兼顧實際應(yīng)用需求,本節(jié)給出參數(shù)具體的取值范圍,使得(5)～(8)式生成的極限曲線達(dá)到C2連續(xù)。

引理2[20]假定局部細(xì)分矩陣的5個特征值λ0、λ1、λ2、λ3、λ4依次遞減,其中λ0=1。若特征值滿足(λ1)2=λ2,則該細(xì)分格式生成的極限曲線是C2連續(xù)的。

證明由上述分析可知,要證明本文細(xì)分框架(5) ～(8)式生成的極限曲線可達(dá)C2連續(xù),即證(6)～(8)式生成的極限曲線可達(dá)C2連續(xù)。

(10)

綜上所述,定理1成立。

(11)

(12)

綜上所述,定理2成立。

4 數(shù)值實例

本節(jié)給出一些數(shù)值實例,利用本文的細(xì)分框架以及插值點的選取規(guī)則來復(fù)現(xiàn)復(fù)雜圖形的極限曲線,其中參數(shù)ω1=-1/16、ω2=0、γ=1/8。

如圖3所示,由本文細(xì)分框架生成的極限曲線能夠自如地插值正六邊形的部分頂點。給定初始正六邊形,任意指定插值點的位置和數(shù)量,并將其余點標(biāo)記為逼近點,則生成的極限曲線能夠自如地插值指定點。圖3中:藍(lán)色虛線表示初始控制多邊形;紅色實線表示生成的極限曲線;星形是插值點的位置。

圖3 插值正六邊形的部分頂點并逼近其余點

梅、蘭、竹、菊4種植物的極限曲線如圖4所示。圖4中:黑實線和紅實線分別表示初始控制多邊形與極限曲線;藍(lán)色、綠色、亮紅色實心圓圈分別為極大曲率點、拐點、尖點的位置。

圖4 4種植物的極限曲線

梅蘭竹菊是詩畫中最常見的題材,它們的造型各有特色。圖4a通過采集植物輪廓的數(shù)據(jù)點來形成藍(lán)色控制多邊形;圖4b利用本文提出的細(xì)分框架,插值植物花瓣、枝葉的邊緣等特征點,生成極限曲線;圖4c展示了梅蘭竹菊的最終效果,其極限曲線不僅保留了細(xì)節(jié)特征,而且呈現(xiàn)了植物的美麗姿態(tài)。

以上實例說明了本文算法的靈活性,通過插值細(xì)節(jié)特征點,逼真地復(fù)現(xiàn)了上述復(fù)雜造型,通過在耐克Logo的幾何輪廓上采取控制頂點,利用本文格式與文獻(xiàn)[8-9,14]等4種格式分別進(jìn)行迭代,復(fù)現(xiàn)耐克Logo的極限曲線。通過比較可以看出,本文格式生成的極限曲線更加貼合耐克Logo的幾何形狀,如圖5所示。

圖5 4種格式復(fù)現(xiàn)耐克Logo幾何形狀的對比

5 結(jié) 論

本文基于融合型細(xì)分格式,給出新頂點及新邊點生成的幾何規(guī)則,提出一類二重插值逼近型細(xì)分框架。該細(xì)分框架不僅包含了一些已有的經(jīng)典細(xì)分格式,還派生出一些新型細(xì)分格式。它可以同時插值指定點并逼近其余點,且極限曲線是C2連續(xù)的。另外,本文還給出了一套插值點的選取法則,控制點集被分成插值點集和逼近點集。數(shù)值實例表明,本文所提出的細(xì)分框架能有效地生成和復(fù)現(xiàn)復(fù)雜的幾何圖形,其生成的極限曲線不僅能保細(xì)節(jié)特征,而且有良好的視覺效果。