一种低次的变次数样条曲线的细分算法

沈莞蔷，张 虎

一种低次的变次数样条曲线的细分算法

沈莞蔷，张 虎

(江南大学理学院，江苏 无锡 214122)

提出一种变次数样条曲线的细分算法，在细分前可指定每段的次数和异次段间的连续性，其中，每段的次数可在[1,4]上任选，异次段间的连续性可在C0和C1中任选，同次段间的连续阶为次数减1。算法使用变次数样条的插节点性质，在所有非零节点区间中，整体插入中点，精确地给出细分前后基函数的关系，同时，利用细分生成的变次数样条的节点区间与次数成比例的方法，使得细分过程中，异次段间的插值系数较为简单。细分过程可表示为线性插值的形式，但不同于非对称的每段分别进行的局部插值方法，而是具有类似均匀B样条的Lane-Riesenfeld细分的整体插值方式，因此，包含次数≤4时的Lane-Riesenfeld细分方法。

变次数样条；B样条；细分；连续阶；线性插值

细分是曲线曲面的一种快速造型方法[1-2]，已成为计算机辅助几何设计(computer aided geometric design，CAGD)中一种强大的造型工具[3]，被广泛应用于汽车、船舶等外形放样工艺的造型领域[4-5]。

曲线的多种细分方法[6]中，有的极限曲线不一定能给出具体的代数表达式，也有针对特定的、有表达式的曲线给出的细分方法。如，B样条作为一种基本的造型工具，其曲线细分已有大量的研究：如经典的均匀B样条的Lane-Riesenfeld的插值细分[7]，一次性加入多个点的高效细分[8]，对应关系明确的均匀B样条细分[9]，基于插节点公式的一般非均匀细分[10]，基于开花的非均匀B样条细分[11]等。随之，其他空间中的均匀或非均匀的细分方法[12-13]逐渐兴起，逐步地被推广开来。

变次数样条作为B样条的之一被直接推广[14-16]，其允许在不同段上使用不同的次数，对于不同特征次数段拼接而成曲线，与B样条造型相比，可减少使用控制顶点的个数。其要求具有类似于B样条的性质[17]，并在B样条的升阶割角过程中产生[18]。特别的，异次段间的连续性不超过C1的变次数样条[19]有重要的应用，因此，本文将这种变次数样条作为研究对象。

变次数样条的基函数由积分形式递归定义，尽管有计算方法[20]，还是期待有高效的细分算法出现。文献[21]针对异次段间的连续性不低于C1的情况，给出了一种次数在[1,3]上变化的、基于插节点性质的细分方法，该方法类似于B样条的插节点细分[10]，每次使用一段的插节点公式，是局部的线性插值的形式，不具有对称性，不能兼容整体插值的均匀B样条的Lane-Riesenfeld细分方法。本文希望能给出另一种细分方法，即具有与Lane-Riesenfeld细分类似的形式，是整体的线性插值，且具有对称性。

本文提出的细分方法是针对异次段间连续性不超过C1、可变次数不超过4的变次数样条，其保留插节点性质，但具有对称性，将包含均匀B样条的Lane-Riesenfeld细分作为特殊情况。

1 理论分析

本文使用文献[16]的方法，去除0节点区间在插节点过程中的影响，即将重节点去除，转而将各段间的连续性作为参数，以此分析相应的理论。并且，设置节点区间的长度与其上的次数成正比，在细分过程中，使插值的系数相对简单。

1.1 变次数样条

其中，[s,s+1)上的次数为d(0≤≤-1)，s处的连续性为c，令d=d-1，0=c=-1，记

由上述定义易得N,D的支撑区间为[s,s)，其中M-1≤<M，M-1-d-1-1≤≤M-d-2。

记

补充定义d=0,d+1=1,···;-1=d-1,-2=d-2,···节点序列、连续性序列、控制顶点序列也依次循环，且-1≠0，则可得到闭曲线的表达式。

1.2 细分前后变次数样条基函数的关系

针对每一个变次数样条的基函数，考虑其支撑区间，分为2种情况：①如果支撑区间内部的节点区间上的次数均相同，称其为同次基函数，也称其为B样条基函数，已得到了长足的研究，且可利用已有的结论；②若支撑区间内的节点区间上的次数不完全相同，称其为异次基函数，将重点分析。

根据插节点性质，插节点前的基函数可表示为插节点后的基函数的线性组合，因此，细分前后的基函数有下述关系。

组合系数可通过异次基函数和同次基函数，按支撑区间的分类讨论得到。

(1) 当N,D的支撑区间长度为2时，

①当c+1=0时，

②当c+1=1时，

(2) 当N,D的支撑区间长度为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的支撑区间长度为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的支撑区间长度为5时，

(1) 当N,D的支撑区间长度为1时，此时d≥2，

(2) 当N,D的支撑区间长度为2时，

①当d=1时，

②当d=2时，

③当d=3时，

④当d=4时，

(3) 当N,D的支撑区间长度为3时，

①当d=2时，

②当d=3时，

③当d=4时，

(4) 当N,D的支撑区间长度为4时，

①当d=3时，

②当d=4时，

(5) 当N,D的支撑区间长度为5时，

对于开曲线而言，补充

综上所有情况，均有如下性质。

1.3 细分前后控制顶点的关系

通过上述基函数细分前后的关系，可以得到细分后控制顶点的关系。由性质1可知，

其中，

则

2 算 法

根据理论分析，给出变次数样条曲线的细分算法。

算法.

步骤2. 考察d段对应的控制多边形，=0,1,···,-1。

备注：

当=1时，

当≥2时，

当d=3时，

当d=4，=2时，

当d=4，≥3时，

当每段次数都相等时，节点区间为均匀的，算法即为不断取中点的均匀B样条的Lane-Riesenfled算法。从系数选取，也可看出算法具有如下描述的对称性，即若控制顶点顺序相反，算法每步生成点的顺序刚好相反。

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

3 例 子

本节给出例子，采用文献[17]中的方法，将次数标注到控制多边形上。其中，偶次段的次数标在最中间的控制顶点处，奇次段的次数标在控制多边形最中间的边上。段与段间的连续阶即为2段所对的控制多边形的重合边数。

一次细分过程的例子如图1所示，空心圈表示初始控制顶点，实心点表示每步插值得到的点，其中，步骤1生成的点为蓝色，步骤2生成的点为黑色，步骤3生成的点为绿色，步骤4生成的点为红色。

(b)

图2为多次细分结果的比较，初始控制顶点用空心圈表示，初始的控制多边形用蓝色实线表示，黑色表示细分1次所得，绿色表示细分2次所得，红色表示细分5次所得。

(b)

4 结束语

本文针对每段次数不超过4，异次段间连续性不超过C1，同次段间连续阶为次数减1的变次数样条，给出了一种曲线细分算法。已有的变次数样条的细分算法在文献[21]中，每段次数不超过3，连续阶与节点区间要求均与本文不同。为了相比，考虑完全相同的前提条件，即次数≤3，节点区间长度与次数成比例，异次段间连续性为C1，同次段间连续阶为次数减1。在该前提下，两者算法相同之处在于均以插节点性质为基础，并且，如果采用完全相同的输入，每次细分输出的多边形完全一致。不同之处在于每次细分的中间步骤，即线性插值的过程：文献[21]的算法使用局部的线性插值，插值过程不具有对称性，不包含Lane-Riesenfled算法；本文的算法使用整体的线性插值，具有对称性，包含次数≤4的Lane-Riesenfled算法。

实际上，如果采用局部段的线性插值方法，可以很简单地推广到次数任意可变的情况，正如插节点算法可适用于任意非均匀的B样条的细分。然而，类似于Lane-Riesenfled算法的变次数B样条的细分算法是相当困难的，原因在于次数可变造成的高度非均匀性。本文尝试去构造这样的算法，目前仅能针对次数≤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] 王国瑾, 汪国昭, 郑建民. 计算机辅助几何设计[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]. 北京: 中国科学院计算技术研究所, 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]. 计算机辅助设计与图形学学报, 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)；中央高校基本科研业务费专项(JUSRP21816)

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

沈莞蔷(1981–)，女，江苏无锡人，副教授，博士，硕士生导师。主要研究方向为计算机辅助几何设计、计算机图形学等。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