基于雙參數(shù)的幾何細分法

孟慧寧，李亞娟，徐惠霞，劉建貞，鄧重陽

?

基于雙參數(shù)的幾何細分法

孟慧寧1，李亞娟1，徐惠霞2，劉建貞1，鄧重陽1

(1. 杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.浙江萬里學(xué)院數(shù)學(xué)研究所，浙江 寧波 315100)

二次有理Bézier曲線；幾何細分方法；保凸性；1連續(xù)；保圓性

細分方法作為一種重要的造型方法，其算法簡單，易于計算，可有效利用計算機快速繪制相應(yīng)的曲線或曲面，因此被廣泛應(yīng)用于醫(yī)學(xué)界、工業(yè)制造業(yè)、卡通動漫等領(lǐng)域。曲線細分作為細分領(lǐng)域的一個重要分支，是曲面造型方法得以快速發(fā)展的基礎(chǔ)。按照細分規(guī)則，細分方法可以分為線性細分方法和非線性細分方法。

比較典型的線性細分方法有CHAIKIN[1]提出的快速生成光滑曲線的割角法、DYN提出的四點插值法[2]以及改進的四點細分算法[3-4]。這些線性細分方法規(guī)則簡單、計算速度快、收斂性和光滑性便于分析，但不易控制極限曲線的形狀。因此，許多學(xué)者通過引入?yún)?shù)、切(法)向量或曲率等，改進已有的線性細分方法或提出新的非線性細分算法。如鄭紅嬋等[5]通過引入?yún)?shù)提出雙參數(shù)四點曲線細分方法，有效地控制極限曲線的形狀。張宏鑫和王國瑾[6]通過經(jīng)緯標(biāo)注引入方向特性，提出一類新穎的半靜態(tài)回插細分方法，結(jié)合半靜態(tài)回插技術(shù)靈活地控制網(wǎng)格。CONTI和ROMANI[7]提出了二重六點動態(tài)插值細分算法來重構(gòu)二次曲線，使生成的極限曲線2連續(xù)。DENG和WANG[8]基于雙圓弧插值提出內(nèi)心細分方法，使其極限曲線具有較好的保形、保圓、光順等特性，且極限曲線1或2連續(xù)。新的細分方法使極限曲線具有保形、保凸、保圓、高階連續(xù)等特征，但有時計算規(guī)則較復(fù)雜。為此，探索一種既計算簡便又效果良好的細分算法成為一種趨勢。

Bézier曲線法將函數(shù)逼近與幾何表示相結(jié)合，可畫出較復(fù)雜形狀的曲線，并以其保凸性、包絡(luò)性等優(yōu)良特性在細分領(lǐng)域備受關(guān)注。本文基于二次有理Bézier曲線[9]的優(yōu)良性質(zhì)，引入兩個參數(shù)，提出了一種具有保凸性的非線性細分算法。利用二次有理Bézier曲線公式及第一個參數(shù)計算新點，再利用另一參數(shù)控制新點的切向量，算法簡單，易于計算。兩個參數(shù)的選取可有效控制極限曲線的形狀。通過理論分析，證明了極限曲線的保凸性和收斂性。取定不同的特殊參數(shù)值，極限曲線可以是1連續(xù)的分段二次有理Bézier曲線或具有保圓性特征。通過一些實例觀察兩個參數(shù)對極限曲線光順度的影響，并進行比較，驗證了本文方法的有效性。

1 符號說明

給定Bézier控制點，本文所提的Bézier曲線為其Bézier表達式所確定的多項式曲線。

圖1 切向線相交構(gòu)成的多邊形(藍)

2 基于雙參數(shù)的幾何細分方法

2.1 構(gòu)造二次有理Bézier曲線

2.2 新點的計算

其中，為控制參數(shù)(即二次有理Bézier曲線中的權(quán)因子)。

圖4 新增點的位置

2.3 新點的切向量

其中，為切向量的控制參數(shù)()。

3 相關(guān)性質(zhì)及結(jié)論

3.1 保凸性與收斂性

圖6 細分的保凸性

定理(收斂性). 極限曲線收斂到一條連續(xù)的凸曲線。

3.2 特殊參數(shù)下的兩個結(jié)論

此方法是一個非穩(wěn)定的幾何細分法。由上述幾何細分法可知，當(dāng)=0時，所有初始點的切向量保持不變，新增點的切向量與其對應(yīng)的初始邊平行。下面通過權(quán)因子變換的等效性說明利用式(6)可使極限曲線為原始點及初始權(quán)值控制的圓錐曲線。

圖7 重新定義中間控制點的權(quán)值

若所有初始點都在同一圓上，則其極限曲線為該圓。

此方法是一個非均勻的幾何細分法。

圖8 時變參數(shù)下的新增點

4 實例分析

圖9 時變參數(shù)下極限曲線的保圓性

圖10 ，參數(shù)對曲線光順度影響

圖11 ，參數(shù)對曲線光順度影響

計算過程中，由于初始點的選取會使各點的曲率過小，不易觀察其變化情況，故本文圖形對各點的曲率同時擴大相應(yīng)倍數(shù)；本文按照第2節(jié)插值中間點的方法對凹多邊形進行預(yù)處理，將其凹邊轉(zhuǎn)化為兩個凸邊進行細分。

圖12 幾種多邊形的極限曲線曲率圖

圖13 參數(shù)，權(quán)因子變換后的極限曲線(黑色箭頭為各初始點的切向量)

5 結(jié)束語

[1] CHAIKIN G M. An algorithm for high-speed curve generation [J]. Computer Graphics and Image Processing, 1974, 3(4): 346-349.

[2] DYN N, LEVIN D, GREGORY J A. A 4-point interpolatory subdivision scheme for curve design [J]. Computer Aided Geometric Design, 1987, 4(4): 257-268.

[3] HASSAN M F, IVRISSIMITZIS I P, DODGSON N A, et al. An interpolating 4-point C2ternary stationary subdivision scheme [J]. Computer Aided Geometric Design, 2002, 19(1): 1-18.

[4] 金建榮, 汪國昭. 構(gòu)造曲線的插值型細分法——非均勻四點法[J]. 高校應(yīng)用數(shù)學(xué)學(xué)報, 2000, 15(1): 97-100.

[5] 鄭紅嬋, 葉正麟, 趙紅星. 雙參數(shù)四點細分法及其性質(zhì)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2004, 16(8): 1140-1145.

[6] 張宏鑫, 王國瑾. 半靜態(tài)回插細分方法[J]. 軟件學(xué)報, 2002, 13(9): 1830-1839.

[7] CONTI C, ROMANI L. A new family of interpolatory non-stationary subdivision schemes for curve design in geometric modeling [C]//AIP Proceedings of the 8thInternational Conference of Numerical Analysis and Mathematics (ICNAAM). New York: the American Institute of Physics (AIP), 2010: 523-526.

[8] DENG C Y, WANG G Z. Incenter subdivision scheme for curve interpolation [J]. Computer Aided Geometric Design, 2010, 27(1): 48-59.

[9] FARIN G. Algorithms for rational Bézier curves [J]. Computer-Aided Design, 1983, 15(2): 73-77.

[10] 潘日晶, 潘日紅. 基于權(quán)因子的有理Bezier曲線細分算法[J]. 福建師范大學(xué)學(xué)報: 自然科學(xué)版, 2000, 16(3): 25-30.

[11] 鄧重陽, 汪國昭. 曲線插值的一種保凸細分方法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2009, 21(8): 1042-1046.

[12] 施法中. 權(quán)因子, 參數(shù)變換與有理二次Bezier曲線參數(shù)化[J]. 航空學(xué)報, 1994, 15(9): 1151-1154.

[13] B?HM W, FARIN G, KAHMANN J. A survey of curve and surface methods in CAGD [J]. Computer Aided Geometric Design, 1994, 1(1): 1-60.

Double-Parameter Geometric Subdivision Method

MENG Huining1, LI Yajuan1, XU Huixia2, LIU Jianzhen1, DENG Chongyang1

(1. School of Science, Hangzhou Dianzi University, Hangzhou Zhejing 310018, China; 2. Institute of Mathematics, Zhejiang Wanli University, Ningbo Zhejing 315100, China)

A geometric subdivision method based on double parameters is proposed in this paper. Firstly, the new control points are determined by the original control points and their tangents: using the quadratic rational Bézier curves formula in which the parameteris 0.5, let two adjacent points and the intersecting point of their tangents be the control points of Bézier curves, and take its weight as the first parameterto calculate new points. Then we calculate new tangent vectors of all points: after define provisional tangent vectors, the circle-tangent of this point is computed by the point and its two adjacent points; whereafter define the formula of new tangents for all points by introducing the second parameterrelated to tangent vectors. Theoretical analyses show its convexity preserving and convergence. If the second parameter=0, and next step we define a new factor by the initial parameter, its limit curve is a piecewise rational quadratic1curve. The circle preserving of this scheme can be obtained by computing new points with different parametersin every step under=1. The effectiveness of this approach is verified by some numerical examples.

quadratic rational Bézier curves; geometric subdivision method; convexity preserving;1continuity; circle preserving

TP 391

10.11996/JG.j.2095-302X.2018030402

A

2095-302X(2018)03-0402-09

2017-04-29；

2017-07-08

國家自然科學(xué)基金項目(61502128，61370166，61379072)；浙江省自然科學(xué)基金項目(LQ17A010009)；寧波市自然科學(xué)基金項目(2016A610223)

孟慧寧(1990-)，女，河南杞縣人，碩士研究生。主要研究方向為細分曲線造型。E-mail：1065022217@qq.com

鄧重陽(1976-)，男，湖南隆回人，教授，博士。主要研究方向為計算機輔助幾何設(shè)計與圖形學(xué)。E-mail：dcy@hdu.edu.cn