基于雙參數的幾何細分法

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

?

基于雙參數的幾何細分法

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

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

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

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

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

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

1 符號說明

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

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

2 基于雙參數的幾何細分方法

2.1 構造二次有理Bézier曲線

2.2 新點的計算

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

圖4 新增點的位置

2.3 新點的切向量

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

3 相關性質及結論

3.1 保凸性與收斂性

圖6 細分的保凸性

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

3.2 特殊參數下的兩個結論

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

圖7 重新定義中間控制點的權值

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

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

圖8 時變參數下的新增點

4 實例分析

圖9 時變參數下極限曲線的保圓性

圖10 ，參數對曲線光順度影響

圖11 ，參數對曲線光順度影響

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

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

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

5 結束語

[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] 金建榮, 汪國昭. 構造曲線的插值型細分法——非均勻四點法[J]. 高校應用數學學報, 2000, 15(1): 97-100.

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

[6] 張宏鑫, 王國瑾. 半靜態回插細分方法[J]. 軟件學報, 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] 潘日晶, 潘日紅. 基于權因子的有理Bezier曲線細分算法[J]. 福建師范大學學報: 自然科學版, 2000, 16(3): 25-30.

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

[12] 施法中. 權因子, 參數變換與有理二次Bezier曲線參數化[J]. 航空學報, 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

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

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

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