沈莞薔，張 虎

一種低次的變次數(shù)樣條曲線的細分算法

沈莞薔，張 虎

(江南大學理學院，江蘇 無錫 214122)

提出一種變次數(shù)樣條曲線的細分算法，在細分前可指定每段的次數(shù)和異次段間的連續(xù)性，其中，每段的次數(shù)可在[1,4]上任選，異次段間的連續(xù)性可在C0和C1中任選，同次段間的連續(xù)階為次數(shù)減1。算法使用變次數(shù)樣條的插節(jié)點性質(zhì)，在所有非零節(jié)點區(qū)間中，整體插入中點，精確地給出細分前后基函數(shù)的關(guān)系，同時，利用細分生成的變次數(shù)樣條的節(jié)點區(qū)間與次數(shù)成比例的方法，使得細分過程中，異次段間的插值系數(shù)較為簡單。細分過程可表示為線性插值的形式，但不同于非對稱的每段分別進行的局部插值方法，而是具有類似均勻B樣條的Lane-Riesenfeld細分的整體插值方式，因此，包含次數(shù)≤4時的Lane-Riesenfeld細分方法。

變次數(shù)樣條；B樣條；細分；連續(xù)階；線性插值

細分是曲線曲面的一種快速造型方法[1-2]，已成為計算機輔助幾何設(shè)計(computer aided geometric design，CAGD)中一種強大的造型工具[3]，被廣泛應用于汽車、船舶等外形放樣工藝的造型領(lǐng)域[4-5]。

曲線的多種細分方法[6]中，有的極限曲線不一定能給出具體的代數(shù)表達式，也有針對特定的、有表達式的曲線給出的細分方法。如，B樣條作為一種基本的造型工具，其曲線細分已有大量的研究：如經(jīng)典的均勻B樣條的Lane-Riesenfeld的插值細分[7]，一次性加入多個點的高效細分[8]，對應關(guān)系明確的均勻B樣條細分[9]，基于插節(jié)點公式的一般非均勻細分[10]，基于開花的非均勻B樣條細分[11]等。隨之，其他空間中的均勻或非均勻的細分方法[12-13]逐漸興起，逐步地被推廣開來。

變次數(shù)樣條作為B樣條的之一被直接推廣[14-16]，其允許在不同段上使用不同的次數(shù)，對于不同特征次數(shù)段拼接而成曲線，與B樣條造型相比，可減少使用控制頂點的個數(shù)。其要求具有類似于B樣條的性質(zhì)[17]，并在B樣條的升階割角過程中產(chǎn)生[18]。特別的，異次段間的連續(xù)性不超過C1的變次數(shù)樣條[19]有重要的應用，因此，本文將這種變次數(shù)樣條作為研究對象。

變次數(shù)樣條的基函數(shù)由積分形式遞歸定義，盡管有計算方法[20]，還是期待有高效的細分算法出現(xiàn)。文獻[21]針對異次段間的連續(xù)性不低于C1的情況，給出了一種次數(shù)在[1,3]上變化的、基于插節(jié)點性質(zhì)的細分方法，該方法類似于B樣條的插節(jié)點細分[10]，每次使用一段的插節(jié)點公式，是局部的線性插值的形式，不具有對稱性，不能兼容整體插值的均勻B樣條的Lane-Riesenfeld細分方法。本文希望能給出另一種細分方法，即具有與Lane-Riesenfeld細分類似的形式，是整體的線性插值，且具有對稱性。

本文提出的細分方法是針對異次段間連續(xù)性不超過C1、可變次數(shù)不超過4的變次數(shù)樣條，其保留插節(jié)點性質(zhì)，但具有對稱性，將包含均勻B樣條的Lane-Riesenfeld細分作為特殊情況。

1 理論分析

本文使用文獻[16]的方法，去除0節(jié)點區(qū)間在插節(jié)點過程中的影響，即將重節(jié)點去除，轉(zhuǎn)而將各段間的連續(xù)性作為參數(shù)，以此分析相應的理論。并且，設(shè)置節(jié)點區(qū)間的長度與其上的次數(shù)成正比，在細分過程中，使插值的系數(shù)相對簡單。

1.1 變次數(shù)樣條

其中，[s,s+1)上的次數(shù)為d(0≤≤-1)，s處的連續(xù)性為c，令d=d-1，0=c=-1，記

由上述定義易得N,D的支撐區(qū)間為[s,s)，其中M-1≤<M，M-1-d-1-1≤≤M-d-2。

記

補充定義d=0,d+1=1,···;-1=d-1,-2=d-2,···節(jié)點序列、連續(xù)性序列、控制頂點序列也依次循環(huán)，且-1≠0，則可得到閉曲線的表達式。

1.2 細分前后變次數(shù)樣條基函數(shù)的關(guān)系

針對每一個變次數(shù)樣條的基函數(shù)，考慮其支撐區(qū)間，分為2種情況：①如果支撐區(qū)間內(nèi)部的節(jié)點區(qū)間上的次數(shù)均相同，稱其為同次基函數(shù)，也稱其為B樣條基函數(shù)，已得到了長足的研究，且可利用已有的結(jié)論；②若支撐區(qū)間內(nèi)的節(jié)點區(qū)間上的次數(shù)不完全相同，稱其為異次基函數(shù)，將重點分析。

根據(jù)插節(jié)點性質(zhì)，插節(jié)點前的基函數(shù)可表示為插節(jié)點后的基函數(shù)的線性組合，因此，細分前后的基函數(shù)有下述關(guān)系。

組合系數(shù)可通過異次基函數(shù)和同次基函數(shù)，按支撐區(qū)間的分類討論得到。

(1) 當N,D的支撐區(qū)間長度為2時，

①當c+1=0時，

②當c+1=1時，

(2) 當N,D的支撐區(qū)間長度為3時，

①當d+1=2時，

②當d+1=d+2≥3時，

③當d=d+1≥3時，

④當d+1=1，c+1=1，c+2=0時，

⑤當d+1=1，c+1=0，c+2=1時，

⑥當c+1= c+2=1時，

(3) 當N,D的支撐區(qū)間長度為4時，

①當d+1=d+2=1時，

②當d+1=1，d+2=2時，

③當d+1=2，d+2=1時，

④當d+1=1，d+2≥3時，

⑤當d+1≥3，d+2=1時，

(4) 當N,D的支撐區(qū)間長度為5時，

(1) 當N,D的支撐區(qū)間長度為1時，此時d≥2，

(2) 當N,D的支撐區(qū)間長度為2時，

①當d=1時，

②當d=2時，

③當d=3時，

④當d=4時，

(3) 當N,D的支撐區(qū)間長度為3時，

①當d=2時，

②當d=3時，

③當d=4時，

(4) 當N,D的支撐區(qū)間長度為4時，

①當d=3時，

②當d=4時，

(5) 當N,D的支撐區(qū)間長度為5時，

對于開曲線而言，補充

綜上所有情況，均有如下性質(zhì)。

1.3 細分前后控制頂點的關(guān)系

通過上述基函數(shù)細分前后的關(guān)系，可以得到細分后控制頂點的關(guān)系。由性質(zhì)1可知，

其中，

則

2 算 法

根據(jù)理論分析，給出變次數(shù)樣條曲線的細分算法。

算法.

步驟2. 考察d段對應的控制多邊形，=0,1,···,-1。

備注：

當=1時，

當≥2時，

當d=3時，

當d=4，=2時，

當d=4，≥3時，

當每段次數(shù)都相等時，節(jié)點區(qū)間為均勻的，算法即為不斷取中點的均勻B樣條的Lane-Riesenfled算法。從系數(shù)選取，也可看出算法具有如下描述的對稱性，即若控制頂點順序相反，算法每步生成點的順序剛好相反。

d=3段在步驟2中依次生成

3 例 子

本節(jié)給出例子，采用文獻[17]中的方法，將次數(shù)標注到控制多邊形上。其中，偶次段的次數(shù)標在最中間的控制頂點處，奇次段的次數(shù)標在控制多邊形最中間的邊上。段與段間的連續(xù)階即為2段所對的控制多邊形的重合邊數(shù)。

一次細分過程的例子如圖1所示，空心圈表示初始控制頂點，實心點表示每步插值得到的點，其中，步驟1生成的點為藍色，步驟2生成的點為黑色，步驟3生成的點為綠色，步驟4生成的點為紅色。

(b)

圖2為多次細分結(jié)果的比較，初始控制頂點用空心圈表示，初始的控制多邊形用藍色實線表示，黑色表示細分1次所得，綠色表示細分2次所得，紅色表示細分5次所得。

(b)

4 結(jié)束語

本文針對每段次數(shù)不超過4，異次段間連續(xù)性不超過C1，同次段間連續(xù)階為次數(shù)減1的變次數(shù)樣條，給出了一種曲線細分算法。已有的變次數(shù)樣條的細分算法在文獻[21]中，每段次數(shù)不超過3，連續(xù)階與節(jié)點區(qū)間要求均與本文不同。為了相比，考慮完全相同的前提條件，即次數(shù)≤3，節(jié)點區(qū)間長度與次數(shù)成比例，異次段間連續(xù)性為C1，同次段間連續(xù)階為次數(shù)減1。在該前提下，兩者算法相同之處在于均以插節(jié)點性質(zhì)為基礎(chǔ)，并且，如果采用完全相同的輸入，每次細分輸出的多邊形完全一致。不同之處在于每次細分的中間步驟，即線性插值的過程：文獻[21]的算法使用局部的線性插值，插值過程不具有對稱性，不包含Lane-Riesenfled算法；本文的算法使用整體的線性插值，具有對稱性，包含次數(shù)≤4的Lane-Riesenfled算法。

實際上，如果采用局部段的線性插值方法，可以很簡單地推廣到次數(shù)任意可變的情況，正如插節(jié)點算法可適用于任意非均勻的B樣條的細分。然而，類似于Lane-Riesenfled算法的變次數(shù)B樣條的細分算法是相當困難的，原因在于次數(shù)可變造成的高度非均勻性。本文嘗試去構(gòu)造這樣的算法，目前僅能針對次數(shù)≤4的情況。今后，希望可以推廣到任意次的情況，這還需要進一步的研究。

[1] DYN N, LEVIN D. Subdivision schemes in geometric modelling[J]. Acta Numerica, 2002, 11: 73-144.

[2] MA W Y. Subdivision surfaces for CAD: an overview[J]. Computer-Aided Design, 2005, 37(7): 693-709.

[3] 王國瑾, 汪國昭, 鄭建民. 計算機輔助幾何設(shè)計[M]. 北京: 高等教育出版社, 2001: 249-250. WANG G J, WANG G Z, ZHENG J M. Computer aided geometric design[M]. Beijing: Higher Education Press, 2001: 249-250 (in Chinese).

[4] 李桂清. 細分曲面造型及應用[D]. 北京: 中國科學院計算技術(shù)研究所, 2001. LI G Q. Subdivision surface modeling and its application[D]. Beijing: Computing Laboratory of Chinese Academy of Sciences, 2001 (in Chinese).

[5] GRESHAKE S H, BRONSART R. Application of subdivision surfaces in ship hull form modeling[J]. Computer-Aided Design, 2018, 100: 79-92.

[6] 鄧重陽, 汪國昭. 曲線插值的一種保凸細分方法[J]. 計算機輔助設(shè)計與圖形學學報, 2009, 21(8): 1042-1046. DENG C Y, WANG G Z. A convex perserving subdivision method for curve interpolation[J]. Journal of Computer Aided Design Computer Graphics, 2009, 21(8): 1042-1046 (in Chinese).

[7] LANE J M, RIESENFELD R F. A theoretical development for the computer generation and display of piecewise polynomial surfaces[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980, 2(1): 35-46.

[8] 管曉鶴, 章仁江. 均勻B樣條曲線的高效細分公式[J]. 中國計量學院學報, 2009, 20(4): 362-366. GUAN X H, ZHANG R J. Efficient subdivision formula for uniform B-spline curves[J]. Journal of China Jiliang University, 2009, 20(4): 362-366 (in Chinese).

[9] 丁永勝, 李朝紅, 何彥波, 等. 一種n次均勻B樣條曲線細分算法[J]. 計算機工程, 2008, 34(12): 58-60. DING Y S, LI Z H, HE Y B, et al. A subdivision algorithm for n-degree uniform B-spline curves[J]. Computer Engineering, 2008, 34(12): 58-60 (in Chinese).

[10] CASHMAN T J, AUGSD?RFER U H, DODGSON N A, et al. NURBS with extraordinary points: high-degree, non-uniform, rational subdivision schemes[C]//SIGGRAPH’09: ACM SIGGRAPH 2009 Papers New York: ACM Press, 2009: 341-352.

[11] 韓力文, 楊玉婷, 邱志宇. 一種任意次非均勻B樣條的細分算法[J]. 圖學學報, 2013, 34(5): 56-61. HAN L W, YANG Y T, QIU Z Y. A subdivision algorithm for arbitrary degree non-uniform B-spline[J]. Journal of Graphics, 2013, 34(5): 56-61 (in Chinese).

[12] FANG M E, MA W Y, WANG G Z. A generalized curve subdivision scheme of arbitrary order with a tension parameter[J]. Computer Aided Geometric Design, 2010, 27(9): 720-733.

[13] FANG M E, JEONG B, YOON J. A family of non-uniform subdivision schemes with variable parameters for curve design[J]. Applied Mathematics and Computation, 2017, 313: 1-11.

[14] SHEN W Q, WANG G Z. A basis of multi-degree splines[J]. Computer Aided Geometric Design, 2010, 27(1): 23-35.

[15] SHEN W Q, WANG G Z. Changeable degree spline basis functions[J]. Journal of Computational and Applied Mathematics, 2010, 234(8): 2516-2529.

[16] BECCARI C V, CASCIOLA G, MORIGI S. On multi-degree splines[J]. Computer Aided Geometric Design, 2017, 58: 8-23.

[17] SEDERBERG T W, ZHENG J M, SONG X W. Knot intervals and multi-degree splines[J]. Computer Aided Geometric Design, 2003, 20(7): 455-468.

[18] WANG G Z, DENG C Y. On the degree elevation of B-spline curves and corner cutting[J]. Computer Aided Geometric Design, 2007, 24(2): 90-98.

[19] BECCARI C V, CASCIOLA G. A Cox-de Boor-type recurrence relation for C1 multi-degree splines[J]. Computer Aided Geometric Design, 2019, 75(4): 101-109.

[20] SPELEERS H. Algorithm 999: computation of multi-degree B-splines[J]. ACM Transactions on Mathematical Software, 2019, 45(4): 1-15.

[21] LI X, HUANG Z J, LIU Z. A geometric approach for multi-degree spline[J]. Journal of Computer Science and Technology, 2012, 27(4): 841-850.

A subdivision algorithm for changeable degree spline curves of low degrees

SHEN Wan-qiang, ZHANG Hu

(School of Science, Jiangnan University, Wuxi Jiangsu 214122, China)

A subdivision scheme of changeable degree spline curves was proposed, in which the degree of each segment and the continuity between different segments can be specified before subdivision. In the algorithm, the degree of each segment can be selected from [1,4], the continuity between different degree segments was optional from C0or C1, and the continuity between the same degree segments was the degree minus 1. The scheme was based on the knot insertion of changeable degree spline. The midpoints were inserted into all non-zero knot intervals, and the relation of basis functions before and after the subdivision process were given accurately. At the same time, the length of each knot interval was proportional to its degree, which simplified the interpolation coefficients of different degree segments in the subdivision process. The subdivision process can be expressed in the form of linear interpolation, but it is different from the asymmetric local interpolation method for each segment. Instead, it is a global interpolation method, which is similar to the Lane-Riesenfeld subdivision of uniform B-spline. Therefore, the Lane-Riesenfeld subdivision scheme with degree ≤4 is included.

changeable degree spline; B-spline; subdivision; continuity order; linear interpolation

TP 391

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

A

2095-302X(2021)01-0110-07

2020-05-29；

29 May，2020；

2020-09-13

13 September，2020

國家自然科學基金項目(61772013)；中央高校基本科研業(yè)務費專項(JUSRP21816)

：National Natural Science Foundation of China (61772013); Fundamental Research Funds for the Central Universities (JUSRP21816)

沈莞薔(1981–)，女，江蘇無錫人，副教授，博士，碩士生導師。主要研究方向為計算機輔助幾何設(shè)計、計算機圖形學等。E-mail：wq_shen@163.com

SHEN Wan-qiang (1981–), female, associate professor, Ph.D. Her main research interests cover computer aided geometric design, computer graphics, etc. E-mail：wq_shen@163.com