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

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

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

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

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

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

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

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

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

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

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

1 預(yù)備知識

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

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

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

也可以簡寫成

1.2 對稱冪基函數(shù)的運算

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

兩個用對稱冪基函數(shù)表示的多項式函數(shù)的加法和減法計算非常簡單，就是對應(yīng)的分量相加或相減，而對用Bernstein基表示的函數(shù)，不同階的兩個多項式無法直接相加或相減，必須通過升階或降階。

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

由式（5）、（6）、（7）即得對稱冪基表示的多項式的乘法。

1.3 等距曲面的定義

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

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

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

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

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

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

2.3 帶伸縮因子的蒙面算法

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

2.4 誤差估計

3 數(shù)值實例

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

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

圖 2 原Bézier曲面

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

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

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

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

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

4 總結(jié)和展望

本文對等距曲面的有理逼近做了一個有益的嘗試，將對二元曲面的等距有理逼近轉(zhuǎn)換為對一元曲線的等距有理逼近，結(jié)合蒙面算法生成逼近等距曲面，簡化了逼近算法。算法優(yōu)點在于對整張曲面u向曲線變化不大（如有伸縮變化、旋轉(zhuǎn)變化等），做等距曲面有理逼近可以得到較為理想的效果，尤其對工業(yè)設(shè)計中比較規(guī)則的曲面的等距面可以取得很好的效果。對整張曲面而言，若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] 劉利剛, 王國瑾. 基于球面三角網(wǎng)格逼近的等距曲面逼近算法[J]. 工程圖學(xué)學(xué)報, 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] 蘇本躍. 基于三角多項式曲線曲面的幾何造型理論與方法研究[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

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

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