Lupaş q-Bézier曲线的几何求值算法及其应用

柳丽宏，左 华，韩力文,2

(1.河北师范大学数学科学学院，河北 石家庄 050024；2.河北省计算数学与应用重点实验室，河北 石家庄 050024)

de Casteljau 算法[1]是1959 年由法国汽车工程师de Casteljau 为加速车身设计并使其具有计算能力而提出的。其是一种曲线曲面的几何求值算法，可将一个复杂的几何问题化简为一系列的简单问题，具有数值稳定性，可用于曲线细分和开花[2-3]。de Casteljau 算法已经成为计算机辅助几何设计(computer aided geometric design，CAGD)的基本工具，在汽车和船舶设计、飞机工业以及医学领域均有应用。经典Bézier 曲线的de Casteljau 算法在递归求值的过程中每一层的每个点都是一条低次的Bézier 曲线，每一层节点都有显式的矩阵表示，并且倒数第二层2 个节点的连线与曲线相切。

Bernstein 算子具有许多优良的几何性质及应用[4]，为CAGD 中的曲线曲面造型奠定了坚实的理论基础。随着q-微积分的发展[5]，一类包含q-整数的广义Bernstein 算子应运而生。目前研究较多的有2 类：①Phillipsq-Bernstein 算子；②Lupaşq-Bernstein 算子[6]，其中第一类算子广泛应用于逼近论和几何造型中[7-11]。本文致力于推进Lupaşq-Bernstein 算子的应用。LUPAS[12]是研究广义Bernstein 算子的先驱。1987年，他引入了Lupaşq-Bernstein 算子，其由有理函数而不是多项式表示，当q=1 时，退化为经典Bernstein算子。2014 年，HAN 等[13]基于Lupaşq-Bernstein 算子构造了以q-整数作为形状参数的Lupaşq-Bézier 曲线曲面，该曲线曲面具有与经典Bézier 曲线曲面相似的几何性质和算法。如几何不变性和仿射不变性、凸包性和升阶性质、de Casteljau 算法。2016 年，以此为基础，HAN 等[14]通过增加权因子，构造了加权Lupaşq-Bézier 曲线。本文构造的曲线是基于广义Bernstein 算子，在曲线曲面的形状控制上具有优势。相比于经典Bézier 曲线，Lupaşq-Bézier 曲线多了一个形状参数q，可用于控制曲线，通过调节参数q的大小，可以使曲线靠近或远离控制多边形，而且Lupaşq-Bézier 曲线可以比经典Bézier 曲线更接近控制多边形。相比于Phillipsq-Bézier 曲线，Lupaşq-Bézier 曲线在首末端点处与控制多边形的首尾2 边P1-P0和Pn-Pn-1相切，而Phillipsq-Bézier 曲线不具有此性质。

近几年，学者从de Casteljau 算法的不同角度进行探究。WINKEL[15]利用哑积分位移算子构造了基于哑积分的广义Bézier 曲线的de Casteljau 算法；ŠÍR和JÜTTLER[16]将Lupaşq-Bézier 曲线推广到一般有理空间，通过改变基本元素累乘的顺序给出n！种de Casteljau 算法。张燕和韩力文[17]利用q-二项式系数的Pascal 递推关系式重新构造了Lupaşq-Bézier 曲线的de Casteljau 算法，每一层节点由关于初始控制多边形的显式矩阵表示。WOŹNY 和CHUDY[18]提出了线性时间的Bézier 曲线的几何求值算法，降低算法的计算复杂度。文献[19-20]将曲线曲面的de Casteljau 算法与其他类型求值算法在算法精度与效率方面进行比较。HERMES[21]利用无误差变换的原理，提出了一系列补偿算法，以精确地计算具有浮点系数的Bernstein形式的多项式。除此之外，近几年，de Casteljau 算法思想也被用在了流形值的数据计算[22]。

经典有理Bézier 曲线具有相切性质，即倒数第二层2 个节点的仿射组合与曲线相切，可以用于分割曲线。本文将Lupaşq-Bézier 曲线表示成经典有理Bézier 曲线的形式，再应用经典有理Bézier 曲线的de Casteljau 算法，构造的算法具有相切的性质，对于2 次Lupaşq-Bézier 曲线，证得分割后2 条子线段的形状参数相乘等于原来曲线的形状参数，进一步给出Lupaşq-Bézier 曲线导矢的一种新形式，最后将具有显式矩阵表示的、计算复杂度低的Lupaşq-Bézier 曲线的de Casteljau 算法推广到加权Lupaşq-Bézier 曲线上，所得到的de Casteljau 算法具有一些新的特点：每一层每个节点都是一条低次的加权Lupaşq-Bézier 曲线。

1 预备知识

1.1 q-整数的相关概念

为了介绍Lupaşq-Bézier 曲线，首先回顾一下q-整数的相关概念[23]。

定义1.对于给定的实数q＞0，及任意r∈N，定义q-整数为

定义2.对于给定的实数q＞0，及任意r∈N，定义q-阶乘为

定义3.对于给定的实数q＞0，及任意整数n≥r≥0，定义q-二项式系数为

其满足Pascal 递推关系式，即

1.2 Lupaş q-Bézier 曲线的定义及算法

定义4.令实数q＞0，t∈[0,1]，给定n+1 个向量Pi∈R3(i=0,1,…,n)，则称n次参数曲线段

为n次Lupaşq-Bézier 曲线，由相邻2 个控制顶点Pi依次连接得到的n边折线多边形称为控制多边形。

称之为n次Lupaşq-Bernstein 基函数。

文献[13]通过基函数的递推公式，得到Lupaşq-Bézier 曲线的de Casteljau 算法，即

算法1.1

文献[16]利用Pascal 关系式重新构造Lupaşq-Bézier 曲线的de Casteljau 算法，得到了该曲线上某一点的显式递归求值的de Casteljau 算法，即

算法1.2

以上2 种de Casteljau 算法都不具有经典de Casteljau 算法相切的性质，即倒数第二层2 个节点的仿射组合与曲线不相切。在第2 节中本文利用经典有理Bézier 曲线的de Casteljau 算法，构造了具有相切性质的Lupaşq-Bézier 曲线的de Casteljau 算法。此算法具有显式的矩阵表示，并给出了此算法的2个应用。

利用Pascal 关系式构造的算法即算法1.2 与本文提出的算法2.1 均用显式的矩阵表示，本文将这2 种算法在计算复杂度方面进行比较，得到算法1.2计算复杂度小，本文在第3 节中将其推广到加权Lupaşq-Bézier 曲线上。与之前用中心投影所得到算法相比，具有一些新的优良特点。

2 具有相切性质的Lupaş q-Bézier 曲线de Casteljau 算法及其应用

2.1 具有相切性质的de Cateljau 算法

对于n次Lupaşq-Bézier 曲线，可以将其表示成经典有理Bézier 曲线的形式，再应用经典有理Bézier 的de Casteljau 算法，得到de Casteljau 算法的2 种表达形式，①相邻两层控制顶点的关系；②第r层与第0 层控制顶点的关系。进一步，该de Casteljau 算法可以分割曲线，给出细分后的2 条子曲线段以及对于2 次曲线2 条子曲线段形状参数满足的性质。并利用de Casteljau 算法给出Lupaşq-Bézier 曲线导矢的另一种表达形式。

将n次Lupaşq-Bézier 曲线

利用经典有理Bézier 曲线的de Casteljau 算法[24]以及第r层与第0 层间权因子wi的关系可得：

算法2.1.具有相切性质的Lupaşq-Bézier 曲线的de Casteljau 算法。

形式1.

形式2.

注1.形式1 为相邻两层控制顶点之间的关系，形式2 反映了各层控制顶点与初始控制顶点的关系。可直接计算中间节点，用于曲线细分。

每一层的每个节点都可以表示成一条有理Bézier 曲线。由此可得到每一层节点关于初始多边形的显式矩阵

2.2 具有显式矩阵表示的de Casteljau 算法的实现与计算复杂度

算法1.2 与本文提出的算法2.1 均具有显式的矩阵表示，接下来，将比较这2 种算法的计算复杂度。

2.3 Lupaş q-Bézier 曲线导矢的新形式

文献[25]给出了经典有理Bézier 曲线的导矢，若将Lupaşq-Bézier 曲线表示成经典有理Bézier 曲线的形式，易得n次Lupaşq-Bézier 曲线在t处的导矢为

通过2 个节点之间连线的斜率来代替曲线的斜率，从而得到Lupaşq-Bézier 曲线导矢的一种新形式。

定理1.Lupaşq-Bézier 曲线的一种新形式的导矢为

证明：通过倒数第二层2 个节点连线的斜率来代替曲线的斜率。

利用算法2.1 的形式2 可得

容易写出2 点确定的直线斜率，即为所求曲线的斜率。

例1：设3 次Lupaşq-Bézier 曲线的控制顶点为P0=(0,1)，P1=(2,2)，P2=(3,2)，P3=(4,1)，形状参数为q=3。

由算法2.1 可得

此形式的导矢将曲线的斜率转换为2 个节点间直线的斜率，推导过程简单，几何意义明显，计算量少。

2.4 曲线分割

de Casteljau 算法也给出了曲线的分割。给定形状参数q，参数t∈[0,1]运用算法2.1 可求出Lupaşq-Bézier 曲线上的一点P(t0;q)，该点将曲线分割成2条Lupaşq-Bézier 曲线，形状参数分别为q1和q2，其对应的顶点分别为 Lupaşq-Bézier 曲线 de Casteljau 算法所得三角阵列的2 条边上的顶点：

定理2.一条形状参数为q的Lupaşq-Bézier 曲线，在参数t0运用有理Bézier 曲线de Casteljau 算法，分割得到2 条子曲线段：

推论1.特别地，对一条形状参数为q的n=2次Lupaşq-Bézier 曲线分割得到的2 条n次子曲线段的形状参数满足q1×q2=q。

证明：当n=2 时，给定形状参数q，设控制顶点为P0，P1，P2，2 次Lupaşq-Bézier 曲线的表达式为

任取参数t0∈[0,1]，在t0处应用de Casteljau 算法，该点把曲线P(t;q)分成2 条二次的子线段分别为

因为P(u1;q1)和P(u2;q2)分别对应曲线P(t;q)在[0,t0]和[t0,1]上的2 条子线段

在[0,t0]区间有

例2.设二次Lupaşq-Bézier 曲线的形状参数q=3，控制顶点为P0=(1,0)，P1=(3,6)，P2=(5,2)。

根据算法2.1 的形式二可得中间点为

图1 q=3 时，运用de Casteljau 算法分割得到的 2 条子曲线 Fig.1 q=3,the de Casteljua algorithm is used to segment two sub-curve segments

3具有显式矩阵表示的加权Lupaş q-Bézier 曲线的de Castejau 算法

定义5.设实数q＞0 和一组正实数ω0,ω1,…,ωn给出n+1 个空间向量Pi∈R3(i=0,1,…,n)，那么[0,1]上的n次加权Lupaşq-Bézier 曲线定义为

此de Casteljau 算法所具有的新特性

(1) 每一层每一个节点都是一条低次的加权Lupaşq-Bézier 曲线；

(2) 每一层节点都有显式矩阵表示。

下面给出每层节点关于初始多边形的显式矩阵表示

4 结束语

本文构造了具有相切性质的Lupaşq-Bézier 曲线的de Casteljau 算法，当q=1 时，Lupaşq-Bézier曲线的de Casteljau 算法退化为经典Bézier 曲线的de Casteljau 算法。此算法具有显式的矩阵表示，并得到了此算法的2 个应用：①用来分割曲线;对于二次的情况，分割得到的2 条子曲线段的形状参数相乘还是原来曲线的形状参数；②是得到Lupaşq-Bézier 曲线导矢的一种新表示，因本文算法计算量小，并且具有显式的矩阵表示，故将其推广到加权Lupaşq-Bézier 曲线上。后续将探究对于高次曲线分割得到的2 条子曲线段的形状参数满足什么条件。Phillipsq-Bézier 曲线一直以来也是学者研究的比较深入、比较广泛的曲线，Phillipsq-Bézier 曲线没有具有相切性质的de Casteljau 算法。进一步构造具有相切性质的Phillipsq-Bézier 曲线的几何求值算法。