第1章曲线曲面基础
1.1隐式和参数表示
第1章曲线曲面基础
1.1隐式和参数表示

在几何造型中，两种最常用的曲线、曲面表示方法是隐式表示和参数表示方法．

xy平面上曲线可以用具有形如f(x,y)=0的隐式方程来表示．这个方程隐含地描述了曲线上点的x,y坐标之间所满足的关系．对于一条给定的曲线，除了差一个常数因子外，


图1.1圆心在原点，半径

为1 的圆周

方程是唯一的
译者注： 还可能差一个恒不为零的因式.
．例如，圆心位于原点的单位圆周，可以由方程f(x,y)=x2+y2-1=0来描述（见图1.1）．
在参数表示形式中，曲线上点的每个坐标分量均被表示为一个独立参数的显函数，其形式为在翻译中保持原书的记法，用黑正体表示点所对应的向量.


C(u)=(x(u),y(u))，a≤u≤b


因此，C(u)是一个独立变量u的矢值函数．尽管区间［a,b］可以是任意的，但通常将其归一化为［0，1］．例如，图1.1中位于第一象限的圆弧采用参数形式可以表示为



x(u)=cos(u)


y(u)=sin(u)0≤u≤π2
(1.1)

令t=tan(u/2)，得到另一种参数表示形式


x(t)=1-t21+t2

y(t)=2t1+t20≤t≤1
(1.2)

因此，一条曲线的参数表示形式是不唯一的．

直观上，我们可以将曲线理解为质点运动所形成的轨迹，将参数u看作时间变量，C(u)=(x(u),y(u))为u时刻质点的位置矢量，［a,b］为时间区间．C(u)的一阶和二阶导矢分别为速度和加速度译者注： 在几何上，一阶导矢也称为切矢.
．对方程（1.1）和方程（1.2）求导，得到速度函数


C′(u)=(x′(u),y′(u))=(-sin(u),cos(u))

C′(t)=(x′(t),y′(t))=-4t(1+t2)2,2(1-t2)(1+t2)2


注意，速度矢量C′(u)的大小为常数


|C′(u)|=sin 2(u)+cos 2(u)=1


即： 虽然质点运动的方向随时间而变化，但其速率是一个常数．这种参数表示形式称为均匀参数化（uniform parameterization）．将t=0和t=1代入C′(t)得： C′(0)=(0,2)，C′(1)=(-1,0)，即： 质点的初始速度是终止速度的2倍（见图1.2）．

曲面的隐式方程具有形式f(x,y,z)=0．例如，球心在原点的单位球面（见图1.3）可以用方程x2+y2+z2-1=0来表示．该球面的一种参数表示形式（不唯一）为S(u,v)=(x(u,v),y(u,v),z(u,v))，其中


x(u,v)=sin(u)cos(v)

y(u,v)=sin(u)sin(v)

z(u,v)=cos(u)0≤u≤π,0≤v≤2π
(1.3)

注意： 在曲面的参数方程中，需要两个参数．固定u不变，让v变化，则产生球面的纬线； 固定v不变，让u变化，则产生球面的经线．



图1.2在端点处的速度矢量
C′(u)和C′(t)译者注： 在图中，C′(u=1)应该改为C′(u=π/2). 




图1.3球心在原点，半径为1的球面




记Su(u,v)=(xu(u,v),yu(u,v),zu(u,v))和Sv(u,v)=(xv(u,v),yv(u,v),zv(u,v))为S(u,v)的偏导矢，即： 分别沿着经线和纬线的速度矢量．在曲面上任一点处，如果Su×Sv
不消失（即Su×Sv为非零矢量），则曲面在该点处的单位法矢N可由下式给出（见图1.4）


N=Su×Sv|Su×Sv|(1.4)




图1.4曲面S(u,v)的偏导矢

和单位法矢

曲面在一点处存在法矢及相应切平面是曲面的几何性质，和曲面的参数化无关．因此，尽管不同的参数化会产生不同的偏导矢，但只要（1.4）式中的分母不为零，则按（1.4）式得到的N都是相同的．由（1.3）式容易发现，对于所有的v（0≤v≤2π）有
Sv(0,v)=Sv(π,v)=0，即： Sv在球面的北极和南极消失（为零矢量）．很明显，球面在两个极点的法矢确实是存在的，但在这种参数化之下，无法用（1.4）式来计算它们．
对于隐式表示形式和参数表示形式，很难断言其中一种总是比另一种好，它们各有自己的优点和缺点．一个成功的几何造型系统往往同时用到以上两种技术．以下对这两种表示方法做一个比较： 
 通过增加一个z坐标，很容易将参数方法推广到三维空间中任意曲线的表示，即： 
C(u)=(x(u)，y(u)，z(u)）； 而隐式方法只能用来表示xy(或xz或yz)平面上的曲线．
 用隐式方法表示有界的曲线段（或曲面片）是不方便的，而在参数表示形式中，曲线（或曲面）的有界性由参数区间的有界性自然得到．另一方面，无界的几何元素（例如，由f(x,y)=ax+by+c=0所定义的直线）利用参数方法表示也是不方便的．

 曲线的参数表示同时给出了曲线的一个方向
（设a≤u≤b，方向为从C(a)到C(b)）； 而隐式表示则不然．因此，利用参数表示形式，很容易生成曲线上的有序点列．类似地，根据曲面的参数方程很容易生成曲面上的网格点．
 在用计算机进行形状设计和表示时，参数形式更直观、自然．在很多参数表示形式（如Bézier和B样条）中，系数具有相当重要的几何意义．这导致直观的设计方法和具有几何特色、数值稳定的算法．
 许多几何操作的计算复杂度极大地依赖于所采用的表示方法．两个典型的例子是： 

—当计算曲线或曲面上点的位置时，采用隐式表示形式是困难的； 

—当给定一个点，要判断它是否在曲线或曲面上时，采用参数形式是困难的．
 当采用参数形式时，经常需要处理由参数化引起的奇异性，而这种奇异性并不是由于本身的几何特性引起的．一个这样的例子是由（1.3）式表示的单位球面．按参数方程，它的两个极点是奇点，处理时较为复杂．但在几何上，两个极点和球面上的其他点并无不同之处．

在本书的后续章节中，我们几乎只考虑参数形式．关于隐式和参数形式的更多细节，大家可以参考有关的教材（如［Faux81; Mort85; Hoff89; Beac91］）．
1.2幂基曲线
1.2幂基曲线
显然，如果允许坐标函数x(u),y(u)和 z(u)是任意的，则可以得到范围很广的曲线．但是，在实际开发一个几何造型系统时，我们需要进行一些折中．理想的情况是将坐标函数限制在满足下述条件的一类函数中： 
 能够精确地表示用户需要的所有曲线．
 在计算机中能够被方便、高效、精确地处理．特别是： 

—可以高效地计算曲线上的点及各阶导矢； 

—函数的数值计算对浮点舍入误差（roundoff error）不敏感； 

—函数所需要的存储量较小．
 比较简单，在数学上易于理解．
一类被广泛使用的函数是多项式．尽管它们满足上述标准中的后两项，但有很多类型的重要曲线（以及曲面）不能用多项式精确地表示，在系统中，这些曲线只能用多项式逼近．在本节及1.3节，我们将讨论多项式函数的两种常用表示方法——幂基表示和Bézier表示．尽管两者在数学上是等价的，但是我们将看到Bézier表示更适合于计算机中形状的表示和操作．
一条n次曲线的幂基表示形式是


C(u)=(x(u),y(u),z(u))=∑ni=0aiui，0≤u≤1(1.5)


其中，ai=(xi,yi,zi)是矢量，因而


x(u)=∑ni=0xiui，y(u)=∑ni=0yiui，z(u)=∑ni=0ziui


（1.5）式写成矩阵的形式为


C(u)=［a0a1…an］1

u



un=［ai］T［ui］(1.6)


（我们将行向量写成列向量的转置）．对（1.5）式求导得到


ai=
C(i)(u)|u=0i!



这里，C(i)(u)|u=0是C(u)在u=0处的i阶导矢．n+1个函数{ui}称为基函数（或混合函数），{ai}是幂基表示形式中的系数矢量．
给定u0，计算幂基曲线上的点C(u0)的最有效算法是Horner方法： 
 次数=1时: C(u0)=a1u0+a0
 次数=2时： C(u0)=(a2u0+a1)u0+a0
 
 次数=n时： C(u0)=(…((anu0+an-1)u0+an-2)u0+…+a1)u0+a0
具体算法如下.
算法A1.1

Horner1(a,n,u0,C)

/*计算幂基曲线上的点. */

/*输入: a, n, u0 */

/*输出: C */

{

C=a［n］;

for(i=n-1;i=0; i--) C=C*u0+a［i］;

}

例1.1
当n=1时， C(u)=a0+a1u(0≤u≤1)表示由a0
到a0+a1的直线段（见图1.5）．常矢量C′(u)=a1
给出了直线的方向．



图1.5直线段C(u)=a0+a1u




图1.6抛物线弧C(u)=a0+a1u+a2u2



例1.2当n=2时，一般来说，
C(u)=a0+a1u+a2u2(0≤u≤1）是一段由
a0到
a0+a1+a2的抛物线弧（见图1.6）．这可按如下方法来证明： 
1. 做坐标变换，将C(u)变换到xy平面（注意： C(u)必定位于一个平面内）．
2. 设在新的坐标系中x(u)=x0+x1u+x2u2，y(u)=y0+y1u+y2u2，因此，可将u和u2表示为u=p1x+q1y+r1和u2=p2x+q2y+r2的形式（当x0,x1,x2,y0,y1,y2固定时，p1,q1,r1,p2,q2,r2均为常数），因而可以得到关于x，y的隐式方程： p2x+q2y+r2=(p1x+q1y+r1)2．
3. 显然，以上隐式方程表示一条抛物线（通过坐标变换，上述隐式方程可以变换为Y=kX2的形式）．
注意，对于二次曲线，加速度矢量C″(u)=2a2是一个常量．我们对两种特殊情况（退化的情形）感兴趣，这两种情况都发生在矢量a2平行于起始点处切矢a1（当x2y1=x1y2时）的情形，在这种情形下，切矢量不会转弯，因此，我们得到的是直线段．这时，矢量a2所指的方向和a1相同（见图1.7(a)），或相反（见图1.7(b)）．在图1.7(b)中，对于某个u0(0≤u0≤1)，a1+2a2u0=0（即粒子运动的瞬时速率为零），且直线段的一部分被（粒子）沿相反的方向重新走过一遍．


图1.7a1和a2平行的情形


(a) 方向相同； (b) 方向相反


例1.3当n=3时， 三次曲线C(u)=a0+a1u+a2u2+a3u3是一类很普遍的曲线： 它可以是真正扭曲的（twisted）三维曲线，不位于任一平面（见图1.8（a））； 它可以有一个拐点（
inflectin point）（见图1.8（b））； 一个尖点(cusp)（见图1.8（c）)或一个环（loop）（见图1.8（d）)．如果a0,a1,a2,a3不在同一平面内，则得到扭曲的空间曲线．若平面曲线在某一点处是光滑的（该点非尖点），并且曲线在该点处的切线穿过该曲线，则称该点为该平面曲线的拐点．


图1.8三次曲线


(a) 扭曲的空间曲线； (b) 拐点； (c) 尖点； (d) 环



图1.8(续)


这意味着在该点前后曲线的转弯方向（turning direction）发生了改变．在拐点处，或者C″(u)=0，或者C′(u)||C″(u)．在u=u0处存在尖点的一个必要（但非充分）条件是： C′(u)=0（速率为零）．曲线上出现环的条件可以参看［Ferg66,67,69,93; Forr70,80; Wang81; Ston89; Su89］等文献．
1.3Bézier曲线
1.3Bézier曲线
本节讨论另一种形式的参数多项式曲线——Bézier曲线．由于幂基和Bézier形式都以多项式函数作为坐标函数，因此，它们在数学上是等价的，即： 以其中一种形式表示的曲线也可以表示为另一种形式．但是，当用于几何造型时，Bézier形式比幂基形式优越．需要说明，本书不是专门介绍Bézier曲线曲面的，如果要了解关于Bézier曲线更严格和更全面的知识，读者可参考其他文献（如［Forr72; Bezi72; 86; Gord74a; Chan81; Fari93; Yama88; Hosc93; Roge90］）．
幂基形式具有如下缺点： 
 它用于形状设计时不够自然，系数{ai}只能传递很少的关于曲线形状的直观的几何印象．而且，设计者通常需要指定曲线两端的端点条件，而不仅仅是起点处的条件．
 处理幂基多项式的算法更多地具有代数的风格而非几何的风格（如： Horner方法）．
 在数值计算上，幂基形式不是一种好的形式．例如，当系数的数量级变化比较大时Horner算法易于受舍入误差的影响（参看［Faro87,88; Dani89］）．

而Bézier方法则克服了以上缺点．
一条n次Bézier曲线可以表示为


C(u)=∑ni=0Bi,n(u)Pi，0≤u≤1(1.7)


其中，基函数（也称为混合函数）{Bi,n(u)}是著名的n次Bernstein多项式（［Bern12； Lore86］），其定义为


Bi,n(u)=n!i!(n-i)!ui(1-u)n-i(1.8)


（1.7）式中的几何系数{Pi}称为控制点．注意： 在定义（1.7）式中，要求u∈［0,1］．
例1.4当n=1时，由（1.8）式有B0,1(u)=1-u和B1,1(u)=u，由(1.7)式可得C(u)=(1-u)P0+uP1，这是一段由P0到P1的直线段（见图1.9）．
例1.5当n=2时，由（1.7）式和（1.8）式可得
C（u）=（1-u）2P0+
2u(1-u)P1+u2P2，这是一段由P0到P1的抛物线弧（见图1.10）．我们注意到： 
 由{P0，P1，
P2}形成的多边形，称为控制多边形（control polygon），很好地逼近了曲线的形状．
 P0=C(0)，P2=
C（1）.
 曲线在两个端点处的切方向分别平行于
P1-P0和
P2-P1（关于这一点，我们将在后面给出具体的推导）．
 曲线包含在由
{P0，P1，P2}形成的三角形内．



图1.9一次Bézier曲线




图1.10二次Bézier曲线




例1.6
当n=3时，我们有C（h）=（1-u）3P0+3u(1-u)2P1+3u2(1-u)
P2+u3P3.
图1.11（a）~（f）给出了三次Bézier曲线的几个例子．我们注意到： 
 控制多边形逼近于曲线的形状．
 P0=C（0），
P3=C（1）.
 端点处的切方向平行于
P1-P0和P3-P2.
 凸包性： 这些曲线包含在定义它们的控制点的凸包内（见图1.11(c)）．
 变差减少性： 任意直线和曲线的交点个数不多于它和曲线的控制多边形的交点个数（对于三维Bézier曲线，需要将上述语句中的“直线”替换为“平面”）．这表明Bézier曲线大体沿着它的控制多边形前进，不会比它的控制多边形更拐来拐去（见图1.11(f)）．
 在起点（u=0）处，曲线的转弯方向（turning direction）和
P0P1P2相同； 而在u=1处，则和
P1P2P3相同．
 由控制多边形上存在环并不能推断曲线上存在环，也不能推断曲线上不存在环．图1.11(e)和(f)之间的过渡情况是存在一个尖点曲线．


图1.11三次Bézier曲线


例1.7
n=6的情况．图1.12给出了一条6次封闭的Bézier曲线．由于
P1-P0平行于
P6-P5，曲线在
C（0）（=C（1））处是光滑的．这里光滑性指的是曲线在u=0和u=1处的切矢具有相同的方向．


图1.12一条光滑、封闭的

6次Bézier曲线


除了前面提到的性质，Bézier曲线在通常的变换（平移、旋转、缩放）下具有几何不变性，即： 要对Bézier曲线进行上述变换，只需对其各个控制点进行该变换即可实现．我们将在第3章针对B样条曲线来更严格地讨论这个概念（Bézier曲线属于B样条曲线的特例）．
在任何一种曲线（曲面）的表示方法中，基函数的选择决定了曲线的几何特性．图1.13（a）~（d）给出了当n=1,2,3,9时基函数
{Bi,n(u)}的图形．这些函数具有以下性质： 



图1.13Bernstein多项式


(a) n=1; (b) n=2; (c) n=3; (d) n=9


P1.1非负性： Bi,n(u)≥0，对所有的i, n和0≤u≤1．
P1.2规范性： ∑ni=0Bi,n(u)=1， 对所有的0≤u≤1．
P1.3端点性质： B0,n(0)=Bn,n(1)=1.
P1.4最大值B
i,n(u)在区间［0,1］内只达到最大值一次，即仅当u=i/n时Bi,n(u)取得最大值．
P1.5对称性： 对于任意n>0，多项式序列{Bi,n(u)}是关于u=1/2对称的．