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

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

0 引 言

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

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

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

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

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

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

1 預(yù)備知識(shí)

(1)

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

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

(2)

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

(3)

其中,a(z)被稱(chēng)為L(zhǎng)aurent多項(xiàng)式。

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

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

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

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

(4)

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

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

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

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

(5)

(6)

(7)

(8)

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

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

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

(9)

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

本文建立下列3類(lèi)插值點(diǎn)選取法規(guī)則。

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

3 連續(xù)性分析

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

引理2[20]假定局部細(xì)分矩陣的5個(gè)特征值λ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ù)值實(shí)例

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

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

圖3 插值正六邊形的部分頂點(diǎn)并逼近其余點(diǎn)

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

圖4 4種植物的極限曲線

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

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

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

5 結(jié) 論

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