王晶昕，魏春瑋

（遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029）

曲線設(shè)計(jì)的一種細(xì)分格式的改進(jìn)

王晶昕，魏春瑋

（遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029）

細(xì)分方法是曲線曲面造型中的一項(xiàng)重要技術(shù)，在計(jì)算機(jī)輔助幾何設(shè)計(jì)和計(jì)算機(jī)圖形學(xué)等領(lǐng)域得到了廣泛應(yīng)用.本文提出一種非靜態(tài)割角細(xì)分方法，該方法的極限曲線具有保凸性，凸包性等與Bézier方法類似的性質(zhì).可以驗(yàn)證當(dāng)參數(shù)取不同的特定值時(shí)，該方法為Chaikin割角法和Riesenfeld割角法等.另外文中通過調(diào)整參數(shù)得到了一些形狀各異的曲線.

曲線；細(xì)分；割角；逼近

細(xì)分曲線是由初始控制多邊形通過重復(fù)逼近或插值得到的[1].由于細(xì)分曲線具有任意拓?fù)渚W(wǎng)格和從離散到離散的特點(diǎn)，從而在計(jì)算機(jī)輔助幾何設(shè)計(jì)和計(jì)算機(jī)圖形學(xué)中得到了廣泛應(yīng)用.曲線的細(xì)分主要可以分為逼近型和插值型兩類.插值型細(xì)分是在保留原控制點(diǎn)的同時(shí)不斷加入新點(diǎn)，所以插值細(xì)分又可以看成是補(bǔ)角過程；相反的，逼近型細(xì)分是通過對(duì)原始控制多邊形不斷割角磨光而得到的.

割角思想最早可以追溯到上世紀(jì)五十年代，De Rham在他的論文中使用割角法來描述光滑曲線[2].其后的幾十年中割角細(xì)分法得到了廣泛的研究，1974年，在美國Utah大學(xué)舉行的CAGD國際會(huì)議上，Chaikin提出了一種曲線的快速生成方法：割角法細(xì)分[3].1980年，Lane和Riesenfeld[4]把Chaikin細(xì)分方法推廣到對(duì)空間多邊形的所有邊都同時(shí)取中點(diǎn)的遞歸割角法.這兩種方法后來被證明了分別為二次和三次B樣條曲線.他們都屬于均勻穩(wěn)定的細(xì)分方法，即，對(duì)每一層以及整個(gè)多邊形或網(wǎng)格都應(yīng)用同一細(xì)分規(guī)則.雖然這種方法都簡單易行，但是也存在著一定的局限性，例如，不具備局部可調(diào)性、不易表現(xiàn)幾何特性以及造型能力差等.1996年Gregory和Qu Ruibin[5]提出了非均勻割角法，這種方法具備了局部可調(diào)整性.本文推廣上述方法，提出了一種新的細(xì)分格式，其中所帶的兩個(gè)參數(shù)取自了[0，1]，可以驗(yàn)證前面那些方法是這種方法的特例.本方法得到的極限曲線具有良好的保凸性、凸包性等幾何性質(zhì).本文還討論了這種方法的收斂性，最后給出一些具體實(shí)例.

1 基本格式

其中，αk∈[0,1],βk∈[0,1] 參數(shù) αk,βk可以調(diào)整曲線的形狀以及對(duì)初始控制多邊形的逼近程度.參數(shù)越大，曲線與初始控制多邊形的逼近程度越弱，參數(shù)越小，曲線與初始控制多邊形的逼近程度增強(qiáng).

拓?fù)湟?guī)則如圖1所示，其中實(shí)線為第k-1層的控制多邊形，虛線為經(jīng)過一次細(xì)分后第k層的控制多邊形.

圖1 拓?fù)湟?guī)則Fig.1 Topological structure

2 收斂性分析

圖2p到Γk+1的距離Fig.2 The distances betweenpkiandΓk+1

3 極限曲線的幾何性質(zhì)

應(yīng)用本文的方法產(chǎn)生的細(xì)分曲線具有以下良好的幾何性質(zhì).

性質(zhì)1保凸性，若初始控制多邊形Γ0為凸的，則細(xì)分曲線也是凸的.

證明由于初始控制多邊形Γ0是凸的，所以多邊形Γ0的內(nèi)角都小于π，由細(xì)分規(guī)則可知，每次細(xì)分后的多邊形的內(nèi)角都小于π，因此多邊形Γk也是凸的，既細(xì)分曲線也是凸的.

性質(zhì)2凸包性，細(xì)分曲線落在初始控制多邊形 Γ0的凸包內(nèi)，若所有頂?shù)闹睾蠒r(shí)，曲線也縮為一點(diǎn).

證明由細(xì)分規(guī)則可知Γk位于Γk-1的凸包內(nèi)，因此Γk一定位于Γ0的凸包內(nèi)，于是當(dāng)k→∞時(shí)，極限曲線 ?！抟欢ㄎ挥讦?的凸包內(nèi).

性質(zhì)3局部性，變動(dòng)初始控制多邊形Γ0的一個(gè)頂點(diǎn)，僅影響曲線在該點(diǎn)附近的部分.

證明由細(xì)分的規(guī)則可知，每個(gè)新的控制點(diǎn)的產(chǎn)生僅依賴于相鄰的兩個(gè)舊控制點(diǎn)，且控制多邊形的每條邊上僅產(chǎn)生2個(gè)新的控制點(diǎn)，也就是說每個(gè)舊控制點(diǎn)僅影響下一層的4個(gè)控制點(diǎn)，因此變動(dòng)初始控制多邊形Γ0的一個(gè)頂點(diǎn)，僅影響曲線在該點(diǎn)附近的部分.

4 實(shí)例分析

本節(jié)通過實(shí)例來展現(xiàn)本章方法的強(qiáng)大曲線造型能力.首先通過調(diào)整參數(shù)研究參數(shù)對(duì)曲線形狀的影響，其次介紹初始控制多邊形為正方形時(shí)，取不同的參數(shù)生成形狀各異的曲線.

從圖3—圖6可以看出，細(xì)分得到的曲線都與控制多邊形相切，并且當(dāng)參數(shù)越大，曲線與初始控制多邊形的逼近程度越弱，但曲線的整體感增強(qiáng)，當(dāng)參數(shù)越小，曲線與初始控制多邊形的逼近程度增強(qiáng)，而曲線的整體感減弱.

本細(xì)分法具有強(qiáng)大的造型能力，下面介紹應(yīng)用本細(xì)分法生成的一些有趣的曲線.初始控制多邊形都為正方形，取不同的參數(shù)值產(chǎn)生形狀各異的曲線，見圖7—圖12.

[1]王仁宏,李崇軍,朱春剛.計(jì)算幾何教程[M].北京:科學(xué)出版社,2008:199-234.

[2]朱心雄.自由曲線造型技術(shù)[M].北京:科學(xué)出版社,2000:236-249.

[3]Chaikin.An algorithm for high speed curve generation[J].Computer Graphics And Image Processing,1974,3(1):346-349.

[4]Lane J M,Riesenfeld R F.A theoretical development for the computer generation and display of piecewise poly sur?faces[J].Pattern Anal Mach Intelling,1980,2(1):35-45.

[5]Gregory J A,Qu Ruibin.Nonuniform corner cutting[J].Computer Aider Geometric Design,1996,13(8):763-772.

[6]施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條[M].北京:高等教育出版社,2001,8(1):214-243.

An Improvement Subdivision Scheme for Curve Design

WANG Jingxin，WEI Chunwei
（School of Mathematics，Liaoning Normal University，Dalian116029，China）

Subdivision is one important technology in curves and surfaces modeling,and subdivision has been widely used in computer aided geometric design and computer graphics.In this paper a new subdivision scheme—Non-statio?nery corner cutting subdivision scheme was proposed.Compared with the other existing methods,such as Bézier this scheme also has convexity-preserving.By choosing appropriate parameters,this subdivision scheme could be content Chaikin and Riesenfeld scheme.In this thesis some different curves were obtained by choosing appropriate parameters.

Curves；subdivision；corner cutting；approximating

O 241.5

A

1674-4942（2011）04-0375-04

2011-09-21

國家自然科學(xué)基金項(xiàng)目（11071031）

畢和平