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

張 莉， 檀結慶， 劉 植

（1. 合肥工業大學計算機學院，安徽 合肥 230009；2. 合肥工業大學數學系，安徽 合肥 230009）

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

張 莉1,2， 檀結慶1,2， 劉 植1,2

（1. 合肥工業大學計算機學院，安徽 合肥 230009；2. 合肥工業大學數學系，安徽 合肥 230009）

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

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

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

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

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

1 預備知識

1.1 對稱冪基函數的定義

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

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

也可以簡寫成

1.2 對稱冪基函數的運算

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

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

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

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

1.3 等距曲面的定義

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

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

利用對稱冪基到Bernstein基的轉換公式，式（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向數據點的插值逼近

2.3 帶伸縮因子的蒙面算法

文獻[15]給出了由截面曲線、脊線以及局部活動標架構造而生成的蒙面曲面

2.4 誤差估計

3 數值實例

圖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 總結和展望

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

[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] 劉利剛, 王國瑾. 基于球面三角網格逼近的等距曲面逼近算法[J]. 工程圖學學報, 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]. 合肥: 合肥工業大學, 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

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

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