張 莉， 檀結(jié)慶， 劉 植

（1. 合肥工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)數(shù)學(xué)系，安徽 合肥 230009）

基于一元對(duì)稱冪基的等距曲面有理逼近算法

張 莉1,2， 檀結(jié)慶1,2， 劉 植1,2

（1. 合肥工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)數(shù)學(xué)系，安徽 合肥 230009）

給出了基于一元對(duì)稱冪基的等距曲面蒙面逼近新算法。利用一元對(duì)稱冪基逼近張量積Bézier曲面u向曲線的等距曲線，得到一組等距逼近曲線，取固定的v值，得到一組數(shù)據(jù)點(diǎn)，用反算控制頂點(diǎn)的方法得到過(guò)這組數(shù)據(jù)點(diǎn)的v向曲線。對(duì)這兩組曲線用蒙面算法得到逼近的有理等距曲面。該算法計(jì)算簡(jiǎn)單，將二元等距曲面有理逼近轉(zhuǎn)化為一元曲線有理逼近，同時(shí)方便地解決了整體誤差問(wèn)題，隨著對(duì)稱冪基階數(shù)的升高，可以得到較理想的逼近效果。

計(jì)算機(jī)應(yīng)用；等距曲面；張量積Bézier曲面；對(duì)稱冪基；有理逼近；蒙面算法

隨著機(jī)器人、數(shù)控機(jī)床以及帶厚度薄片實(shí)體（如汽車車身、箱包等）在計(jì)算機(jī)圖形學(xué)和數(shù)控加工中的大量應(yīng)用，等距曲線/曲面(offset)的研究已經(jīng)成為近些年來(lái) CAGD（計(jì)算機(jī)輔助幾何設(shè)計(jì)）的研究熱點(diǎn)。關(guān)于平面曲線的等距曲線已有大量的研究[1-5]，但對(duì)等距曲面的研究工作則相對(duì)較少[6-7]。

對(duì)于簡(jiǎn)單曲面的等距曲面的生成，國(guó)內(nèi)外許多學(xué)者做了大量的工作：Farouki[8]指出三類簡(jiǎn)單實(shí)體：凸多面體、旋轉(zhuǎn)體和拉伸體具有精確的等距曲面。Pottmann[9]在1995年提出了PH 曲面的概念，即具有有理等距曲面的一類曲面。呂偉[10]證明了拋物面、橢球面和雙曲面的等距曲面仍為有理曲面。接著 Pottmann 等[11]證明了不可展有理直紋面的等距曲面在整個(gè)空間是可有理化的。然而對(duì)于更為復(fù)雜的曲面生成其等距曲面卻頗為困難。2000年劉利剛、王國(guó)瑾[12]把等距曲面的問(wèn)題看作球心在原曲面上運(yùn)動(dòng)，半徑為d的基球面沿原曲面掃掠的問(wèn)題，用三角網(wǎng)格來(lái)逼近基球面得到了基于球面三角網(wǎng)格逼近的等距曲面逼近算法。

本文利用一元對(duì)稱冪基逼近張量積 Bézier曲面u向曲線的等距曲線，對(duì)得到的一組等距逼近曲線，取固定的v值，得到一組數(shù)據(jù)點(diǎn)，用反算控制頂點(diǎn)法得到過(guò)這組數(shù)據(jù)點(diǎn)的v向曲線。以u(píng)向等距逼近曲線為平面截線，以得到的v向曲線為脊線，最后用過(guò)關(guān)鍵位置的蒙面算法得到有理等距曲面，較為巧妙的將二元等距曲面的有理逼近問(wèn)題轉(zhuǎn)化為一元等距曲線的有理逼近問(wèn)題，簡(jiǎn)化了算法，同時(shí)方便地解決了整體誤差問(wèn)題。

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

1.1 對(duì)稱冪基函數(shù)的定義

Sánchez-Reyes[13]給 出 如 下 對(duì) 稱 冪 基（Symmetric power basis）的定義：

對(duì)稱冪基函數(shù)有以下特點(diǎn)：① 它是對(duì)稱的，將變量 t用（1-t）替換，得同一組基；② 低階基函數(shù)是高階基函數(shù)的子集；③ 在端點(diǎn)t=0, t=1，直至k-1階導(dǎo)數(shù)為零。因此Sánchez-Reyes稱用這種基函數(shù)表示的多項(xiàng)式為“Hermite兩點(diǎn)展開(kāi)多項(xiàng)式”，稱用對(duì)稱冪基函數(shù)逼近已知函數(shù)為“兩點(diǎn)Hermite插值逼近”。性質(zhì)③ 保證了函數(shù)在端點(diǎn)t=0, t=1處

也可以簡(jiǎn)寫成

1.2 對(duì)稱冪基函數(shù)的運(yùn)算

文獻(xiàn)[14]給出了對(duì)稱冪基函數(shù)表示的多項(xiàng)式之間的四則運(yùn)算以及求平方根運(yùn)算，下面介紹其中的加法、減法及乘法運(yùn)算。

兩個(gè)用對(duì)稱冪基函數(shù)表示的多項(xiàng)式函數(shù)的加法和減法計(jì)算非常簡(jiǎn)單，就是對(duì)應(yīng)的分量相加或相減，而對(duì)用Bernstein基表示的函數(shù)，不同階的兩個(gè)多項(xiàng)式無(wú)法直接相加或相減，必須通過(guò)升階或降階。

給定兩個(gè)對(duì)稱冪基函數(shù)表示的m次和n次多項(xiàng)式，它們的系數(shù)序列分別為，，下面介紹它們的乘法運(yùn)算。為了得到用對(duì)稱冪基函數(shù)表示的兩個(gè)多項(xiàng)式乘法，首先了解它們“系數(shù)”是怎樣相乘的。兩個(gè)線性函數(shù)分別用Bézier坐標(biāo)表示

由式（5）、（6）、（7）即得對(duì)稱冪基表示的多項(xiàng)式的乘法。

1.3 等距曲面的定義

2 張量積Bézier曲面的等距曲面的有理逼近算法和誤差估計(jì)

2.1 張量積Bézier曲面的u向Bézier曲線的等距逼近

利用對(duì)稱冪基到Bernstein基的轉(zhuǎn)換公式，式（14）中計(jì)算出的逼近等距曲線是用 Bernstein基表示的有理表達(dá)式。

圖1是三次平面Bézier曲線，控制頂點(diǎn)為：p0=[0,0]; p1=[1,2]; p2=[3,2]; p3=[4,0]。采用上述方法，取等距距離d = 0.5的等距曲線進(jìn)行有理逼近，其中實(shí)線為原曲線及等距曲線，虛線為等距曲線的有理逼近曲線。誤差分別為：

圖1 三次平面Bézier曲線等距有理逼近

2.2 張量積Bézier曲面的v向數(shù)據(jù)點(diǎn)的插值逼近

2.3 帶伸縮因子的蒙面算法

文獻(xiàn)[15]給出了由截面曲線、脊線以及局部活動(dòng)標(biāo)架構(gòu)造而生成的蒙面曲面

2.4 誤差估計(jì)

3 數(shù)值實(shí)例

圖2是3×3的張量積Bézier曲面，控制頂點(diǎn)分別為

圖3畫出了原Bézier曲面和它的精確等距曲面。圖4按照本文算法生成的截面曲線和脊曲線（給出了多條）。圖5是蒙面后的逼近等距曲面，圖6是原Bézier曲面和它的逼近等距曲面，這里u向曲線的等距逼近曲線使用了u的五次多項(xiàng)式逼近。圖7是逼近等距曲面的誤差曲面。

圖 2 原Bézier曲面

圖 3 原Bézier曲面和它的精確等距曲面

圖 4 本文算法所得的截面曲面曲線和脊曲線

圖 5 圖3蒙面后的逼近等距曲面（k=2）

圖 6 原Bézier曲面和它的逼近等距曲面（k=2）

圖 7 逼近等距曲面的誤差曲面

4 總結(jié)和展望

本文對(duì)等距曲面的有理逼近做了一個(gè)有益的嘗試，將對(duì)二元曲面的等距有理逼近轉(zhuǎn)換為對(duì)一元曲線的等距有理逼近，結(jié)合蒙面算法生成逼近等距曲面，簡(jiǎn)化了逼近算法。算法優(yōu)點(diǎn)在于對(duì)整張曲面u向曲線變化不大（如有伸縮變化、旋轉(zhuǎn)變化等），做等距曲面有理逼近可以得到較為理想的效果，尤其對(duì)工業(yè)設(shè)計(jì)中比較規(guī)則的曲面的等距面可以取得很好的效果。對(duì)整張曲面而言，若u向曲線變化比較復(fù)雜，本算法逼近效果不太理想，需結(jié)合其它較為復(fù)雜的蒙面算法才能得到理想的逼近曲面。

[1] Klass R. An offset spline approximation for plane cubic splines [J]. Computer Aided Design, 1983, 15(5): 297-299.

[2] Tiller W, Hanson F. Offsets of two dimensional profiles [J]. IEEE Computer Graphics and Its Applications, 1984, 4(9): 36-46.

[3] Hoschek J. Spline approximation of offset curves [J]. Computer Aided Geometric Design, 1988, 5(1): 33-40.

[4] Lee I K , Kim M S, Elber G . Planar curve offset based on circle approximation [J]. Computer Aided Design, 1996, 28(8): 617-630.

[5] Elber G Lee. Comparing offset curve approximation methods [J]. IEEE Computer Graphics and ItsApplications, 1997(5-6): 62-71.

[6] Pham B. Offset curves and surfaces: a brief survey [J]. Computer Aided Design, 1992, 24(4): 223-229.

[7] Maekawa T. An overview of offset curves and surfaces [J]. Computer Aided Design, 1999, 31(3): 165-173.

[8] Farouki R T. Exact offset procedures for simple solids [J]. Computer Aided Geometric Design, 1985, 2(3): 257-279.

[9] Pottmann H. Rational curves and surfaces with rational offsets [J]. Computer Aided Geometric Design. 1995, 12(2): 175-192.

[10] Lü W, Wien. Rational parameterization of quadrics and their offsets [J]. Computing, 1996, 57(2): 135-147.

[11] Pottmann H, Lü W, Ravani B. Rational ruled surfaces and their offsets [J]. Graphical Models and Image Processing, 1996, 58(6): 544-552.

[12] 劉利剛, 王國(guó)瑾. 基于球面三角網(wǎng)格逼近的等距曲面逼近算法[J]. 工程圖學(xué)學(xué)報(bào), 2000, 21(3): 70-75.

[13] Sánchez-Reyes J. The symmetric analogue of the polynomial power basis [J]. ACM Transactions on Graphics, 1997, 16(3): 319-357.

[14] Sánchez-Reyes J. Applications of the polynomial s-power basis in geometry processing [J]. ACM Transactions on Graphics, 2000, 19 (1): 27-55.

[15] 蘇本躍. 基于三角多項(xiàng)式曲線曲面的幾何造型理論與方法研究[D]. 合肥: 合肥工業(yè)大學(xué), 2007.

Rational Approximation of Offset Surface by Univariate S-Power Basis

ZHANG Li1,2, TAN Jie-qing1,2, LIU Zhi1,2
( 1. College of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China; 2. Department of Mathematics, Hefei University of Technology, Hefei Anhui 230009, China )

A new algorithm for approximating offset surfaces by using univariate symmetric power basis is presented. It uses symmetric power basis to approximate u directional curves of tensor product Bézier surface, then it gets a set of offset approximating curves. From fixed v value of these curves, it will get a set of data points. The paper gets v directional approximating curves which get through these data points by anti algorithm of control points. Finally, rational approximating offset surface is got by using skinning surface algorithm. The algorithm is easy and solves the integral tolerance. Numerical examples show that it can achieve good effect with the raise of the S-power basis’ degree.

computer application; offset surface; tensor product Bézier surface; symmetric power basis; rational approximation; skinning surface algorithm

TP 391

A

：1003-0158(2010)01-0104-06

2008-07-16

國(guó)家自然科學(xué)基金資助項(xiàng)目（60773043；60473114）；安徽省自然科學(xué)基金資助項(xiàng)目（070416273X）；安徽省教育廳科技創(chuàng)新團(tuán)隊(duì)基金資助項(xiàng)目（2005TD03）；安徽省高等學(xué)校青年教師科研資助計(jì)劃項(xiàng)目（2007jq1001）；合肥工業(yè)大學(xué)科學(xué)研究發(fā)展基金資助項(xiàng)目（061007F）

張 莉（1976-），女，安徽合肥人，副教授，博士研究生，主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)。