计算几何new教材

计算几何刘玉琳什么是计算几何称为计算几何的学科主要分为以下几种：Minsky和Papert提出作为模式识别的代用词Forrest提出依据样条函数处理曲线曲面Shamos提出研究几何问题的算法及复杂性图形信息处理及图形运算几何定理证明的探索方法及证明过程的推断Forrest计算几何1972年A.R.Forrest定义计算几何为：“对几何外形信息的计算机表示、分析和综合。”几何外形信息是指：那些确定某些几何外形如平面曲线或空间曲线的型值点或特征多角形，如样条曲线在各端点的几阶函数导数值就是样条曲线的信息按照这些信息作出数学模型（如曲线方程），通过计算机进行计算，求得足够多的信息（如曲线上许许多多点）——计算机表示，然后进行分析和综合（如研究曲线段上会不会出现尖点，有没有多余的拐点，等等），这个研究内容形成了计算几何Forrest计算几何同CAGD，计算机图形学有密切关系，是一门由函数逼近论、微分几何、代数几何、计算数学、数控等形成的边缘学科。在CAD、CAE领域中广泛应用，服务于造船工业、航空工业和汽车制造工业及众多工业产品的外形设计和制造领域参考书：《计算几何》苏步青《计算机辅助几何设计与非均匀有理B样条》施法中Forrest计算几何研究内容包括：曲线曲面参数化孔斯(Coons)曲面与样条插值Bezier曲线曲面B样条曲线曲面NURBS曲线曲面曲面的几何处理曲面造型实例预备知识：曲线的参数矢量方程坐标系、点、矢量回顾刻舟求剑的故事—坐标系的人为性和相对性点－－坐标系中的绝对位置。矢量－－具有长度和方向，且服从相等、相加、相减及数乘诸法则的量。点与矢量的关系－－绝对位置与相对位置。例：直线的参数方程矢量形式：

曲线的参数矢量方程曲线的参数矢量方程或圆的非参数方程例：圆的参数方程采用参数矢量方程的几点理由：1．参数方程便于曲线的绘制2．参数方程与坐标系选取无关3．参数方程可以方便地表示垂直切线4．参数方程可以方便地表示空间曲线圆弧？例:曲线的参数矢量方程一般形式：基表示形式：规范性例

曲线的参数矢量方程曲面的参数矢量方程1.一般形式

曲面的参数矢量方程例1:例2:

例3：Shamos计算几何主要研究解决几何问题的算法计算机的出现使很多原本十分繁琐的工作得以大幅度简化，但存在一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。计算几何常用的算法包括：折线段的拐向判断、判断点是否在线段上、判断两线段是否相交、判断点在多边形内外、计算点到线段最近点、求交点、凸包计算等等《计算几何——算法分析与设计》周培德折线段的拐向判断可由矢量叉积的性质推出P0P1P2P0P1P2((p2-p0)×(p1-p0)).n<0((p2-p0)×(p1-p0)).n>0n=(0,0,1)判断两线段是否相交解析几何解法列直线方程：Ax+By+C=0判断解的情况若无解则平行无穷多解——共线唯一解判断是否分别在两条线段的内部判断两线段是否相交解析几何解法的问题求解方程需要浮点除法运算浮点误差特别是接近平行时浮点除法运算速度总体效率低计算几何的算法仅需要加、减、乘不求交点判断两线段是否相交（1）包围盒快速排斥试验设以线段P1P2为对角线的矩形为R，设以线段Q1Q2为对角线的矩形为T，如果R和T不相交，显然两线段不会相交（2）跨立试验如两线段相交，则两线段必然相互跨立对方。判断P1P2跨立Q1Q2的依据是：((P1-Q1)×(Q2-Q1))∙((Q2-Q1)×(P2-Q1))≥0同理判断Q1Q2跨立P1P2的依据是：((Q1-P1)×(P2-P1))∙((P2-P1)×(Q2-P1))≥0矢量及矢量点积叉积非常有用点积用于计算投影、夹角、判断是否同向叉积用于计算面积、法矢等第一章参数样条曲线曲面

参数三次（PC）曲线段给定曲线段的两个端点，和在两个端点处的一阶导矢，设曲线段的表达式为：将已知端点条件带入到上两式中：

参数三次（PC）曲线段（续）三次Hermite基函数PC曲线段实质就是参数三次Hermite插值

三次Hermite插值的域变换实践中常常需要定义任意参数域上的参数三次Hermite插值，这可以通过定义在上的参数三次Hermite插值作域变换得来。令C1分段三次Hermite插值给定数据点列及其切矢对数据点实行参数化，即确定一个参数分割就可以构造C1分段三次Hermite插值曲线p(u),即有其中参数三次样条曲线对每段曲线求一阶、二阶导矢函数：将u=ui带入，并令其相等，可得

参数三次样条曲线（续）三切矢连续性方程补充两个边界条件，即可求解出所有的切矢。（1）切矢条件（2）自由端点条件（端点曲率为0）（3）抛物线条件（Bessel条件，即使首末段为抛物线）……边界条件应根据实际情况灵活给出。∆i=

?

参数三次样条曲线（续）根据对数据点进行参数化的方法，可以将参数三次样条曲线划分成如下类型：（1）均匀参数三次样条曲线（Ferguson参数样条曲线）此时，三切矢方程简化为：Ferguson

方法的优点是简化，但当数据点分布不均匀时，曲线会产生波动。§3.6参数三次样条曲线（续）此乃最常采用的一种数据点参数化方法。（2）累加弦长参数三次样条曲线根据对数据点进行参数化的方法，可以将参数三次样条曲线划分成如下类型：（3）向心参数三次样条曲线考虑曲线拐折，使向心加速度与曲线段起点到终点的拐角成正比，推得。（4）修正弦长参数三次样条曲线

参数三次样条曲线的性质参数三次样条曲线存在唯一性收敛性不易控制计算稳定整体性缺乏柔性

孔斯曲面孔斯曲面的实质是插值给定的四条边界曲线以及四条边界的各阶跨界导矢曲线

具有给定边界的Coons曲面选定一对混合函数F0、F1，它们具备以下性质：第一步：在u向构造插值边界p(0,v)、p(1,v)的曲面片具有给定边界的Coons曲面选定一对混合函数F0、F1，它们具备以下性质：第二步：在v向构造插值边界p(u,0)、p(u,1)的曲面片具有给定边界的Coons曲面选定一对混合函数F0、F1，它们具备以下性质：

具有给定边界的Coons曲面第三步：用四个角点和混合函数F0、F1构造张量积曲面

具有给定边界的Coons曲面用p1(u,v)＋p2(u,v)－p3(u,v)即完全插值了给定的四条边界。具有给定边界的Coons曲面边界信息方阵

构造曲面的三种基本方法1.张量积法作用于呈矩形阵列的给定矢量例1例2作用于一个参数方向上的给定曲线及导矢等2.母线法

构造曲面的三种基本方法例1:例2：单向蒙皮曲面作用于两个参数方向上的给定曲线及导矢3.布尔和法

构造曲面的三种基本方法例1：孔斯曲面p(u,v)＝p1(u,v)＋p2(u,v)－p3(u,v)例2：双向蒙皮曲面第2章Bézier曲线曲面§2.1Bézier曲线的定义为曲线的控制顶点Bernstein基函数§2.2Bernstein基函数的性质

非负性权性对称性递推性导数递推性端点处：§2.2Bernstein基函数的性质

非负性权性对称性递推性导数递推性证明：§2.2Bernstein基函数的性质

非负性规范性对称性递推性导数递推性§2.2Bernstein基函数的性质

非负性规范性对称性递推性导数递推性证明：§2.2Bernstein基函数的性质

非负性规范性对称性递推性导数递推性证明：§2.3Bézier曲线的性质

端点性质几何不变性对称性凸包性变差减小性保凸性通过首、末控制顶点§2.3Bézier曲线的性质

端点性质几何不变性对称性凸包性变差减小性保凸性因为所以类似地有：跟首末各一条边有关跟首末各两条边有关§2.3Bézier曲线的性质

端点性质几何不变性对称性凸包性变差减小性保凸性☆曲线的形态与坐标系的选取无关，由其控制多边形唯一地确定。原因可以从基函数的权性得到解释。§2.3Bézier曲线的性质

端点性质几何不变性对称性凸包性变差减小性保凸性☆由基函数的对称性决定。只要控制顶点顺序颠倒一下，即可实现对曲线的反向。因为颠倒控制多边形顶点的顺序，即则新曲线为：叙述并证明Bezier曲线的端点性质Bezier曲线的首末点即为控制多边形首末顶点，首末点的k阶导矢分别与控制多边形的首末k条边有关，与其它边无关。（曲线在首末端点分别与控制多边形首末条边相切）§2.3Bézier曲线的性质

端点性质几何不变性对称性凸包性变差减小性保凸性。☆Bézier曲线的实质是一系列绝对矢量的凸组合（加权组合）。此性质便于确定Bézier曲线的范围。凸包示意图§2.3Bézier曲线的性质

端点性质几何不变性对称性凸包性变差减小性保凸性☆Bézier曲线比其控制多边形更光滑，拐折减少。§2.3Bézier曲线的性质

端点性质几何不变性对称性凸包性变差减小性保凸性☆是变差减小性的推论。§3.3Bézier曲线的递推定义1.几何作图法2.递归分割算法§3.4Bézier曲线的分割用递推算法求出曲线上的一点p(t*)，该点把曲线分为两段Bézier曲线，它们的控制顶点分别如图所示。3.5Bezier曲线的导矢Bezier曲线的各阶导矢可以作为徳卡斯特里奥算法的“副产品”被快速计算出来。将徳卡斯特里奥算法进行了第n-1级递推所得一边矢量的n倍即为切矢，进行了n-2级递推所得两边矢量的差分矢量就是以该两边矢量为邻边的平行四边形的对角线矢量，它的n(n-1)倍就是二阶导矢。3.6Bezier曲线升阶降阶名义次数——n真实次数——按幂次升序排列，非零系数的单项式函数最高次数Bezier曲线升阶：保持Bezier曲线的形状与定向不变，增加定义它的控制顶点数，即增加它的名义次数。如何由老控制顶点求出新控制顶点？设给定老控制顶点b0,b1…,bn，定义一条n次Bezier曲线，增加一个顶点后，仍定义同一条曲线的新控制顶点b*0,b*1…,b*n+1可按如下升阶公式决定3.6Bezier曲线升阶降阶其中，b-1=bn+1=0

新控制多边形是在老控制多边形的凸包内，新控制多边形比老控制多边形更靠近曲线。

升阶虽增加了曲线的控制顶点，但曲线形状、定向保持不变，所以曲线的真实次数不变。但一旦移动生成的新控制顶点，曲线的形状就发生了改变，曲线的真实次数也升高至名义次数。3.6Bezier曲线升阶降阶为什么要升阶？升阶即增加控制顶点，也就增加了对曲线进行形状控制的潜在灵活性。比如，一个二次Bezier曲线，无论怎么调整顶点都不可能使曲线产生拐点，曲线“刚性”有余，“柔性”不足。升阶可以降低其“刚性”，增加“柔性”。升阶在构造曲面方面有着重要的应用。对于一些由曲线生成曲面的算法，要求那些曲线必须是同次的，应用升阶方法，可以把所有这些曲线中低于最高次数者都提升到最高次，从而获得统一的次数。3.6Bezier曲线升阶降阶降阶是升阶的逆过程。一般精确的降阶是不可能的如果n次Bezier曲线的名义次数高于它的真实次数，那么它可以被精确降阶到真实次数。只要控制顶点共线，定义的贝齐儿曲线一定是直线吗？这直线必定是一次的吗？若不，是否一定能降阶到一次？由凸包性质，肯定是直线。不一定是一次的，比如有3个控制顶点，就是2次的，但一定能降阶到一次，因为直线的真实次数是一次。§3.7Bézier曲线的拼接

贝齐尔方法为设计员提供厂一个强有力的工具。但在实践中，经常会遇到一个普遍问题，就是难于用单一的贝齐尔曲线段与贝齐尔曲面片描述复杂的形状。如果一定要这样做，就只能靠提高次数来增加潜在的控制灵活性。但这有其局限性，因为贝齐尔方法对形状的定义是整体方案，欲对其作局部修改时，必然会影响到整体。即贝齐尔方法具有整体控制性质，但却缺乏局部控制性质。因此，次数就不能提得太高。用于实际目的，贝齐尔曲线的次数超过10次是禁忌的。既然单一的贝齐尔曲线曲面不能满足描述复杂形状的需要．就必须采用组合贝齐尔曲线曲面，即对复杂形状的曲线与曲面在满足一定的光滑连接条件下，分别采用分段与分片拟合，以满足实际的需要。这里要解决的关键问题就是怎样实现光滑连接的问题。§3.7Bézier曲线的拼接有两种不同的关于连接的光滑度的度量。一种是多年来沿用的函数曲线的可微性。把组合参数曲线构造成在连接处具有直到n阶连续导矢即n次连续可微，这类光滑度称为Cn或n阶参数连续。另一种称为n阶几何连续性，简记为Gn考察第i-1与第i两相邻曲线段的连接。如要求它们在连接点处具有Cr连续性，由使该点处的左右导矢相等得到Cr连续条件§3.7Bézier曲线的拼接当r=0时，bni=bni当r=1时，bni+1–bni

=bni-bni-1即三顶点必须红线，且顺序成等距分布参数连续性问题1、参数连续性与所取的参数有关。即组合贝齐尔曲线在整体参数下的参数连续条件与在局部参数下的连续条件是不相同的。事实上，当各曲线段的贝齐尔点给定后，各曲线段的形状就完全确定，组合贝齐尔曲线的形状也就完全确定，随之，组合曲线连接的光滑度也就完全确定。它是与所取参数无关的。2、当组合n次贝齐儿曲线的公共连接点bni与前后控制顶点bni-1

，bni+1相重合时，组合曲线在bni处有零切矢，即C1连续。然而，此时组合曲线很可能在该连接点处形成一个尖角，因而是不光滑的；所以曲线的光滑性和可微性不可等价，用参数连续性来衡量曲线的光滑性不是非常合理。取而代之的是被称为视觉连续性的几何连续性。组合曲线在连接处具有n阶几何连续性，简记为Gn§3.7Bézier曲线的拼接对于两个参数曲线段：G0连续条件：G1连续条件：G2连续条件：带入G1条件提高灵活性§3.7Bézier曲线的拼接以三次曲线的拼接为例：G0连续条件：G1连续条件：三点共线G2连续条件：五点共面§3.8Bézier曲线的矩阵表示§3.8Bézier曲线的矩阵表示Bézier曲线的矩阵表示与其他形式等价，矩阵表示形式（即幂基形式）曲线几何意义不明显，并且在数值上不如Bernstian基形式稳定。幂基形式表示曲线、曲面不是很可靠，这是由于幂基形式本质上是曲线段在始点p(0)邻近的泰勒展开，越远离始点，积累的舍入误差将越大，且随着曲线次数的升高，问题将戏剧性地变得越突出。

因此，Bernstian基比幂基形式计算稳定，但在幂基形式下，采用嵌套乘法格式计算曲线上一系列点时，速度要比徳卡斯特里奥算法快得多，所以采用哪种方法表示，应视实际需要和实际条件来定。§3.9Bézier曲线的拟合给定曲线上的型值点列pi,i=0,1,…m，求一条n次Bézier曲线最好地逼近给定的型值点，称为Bézier曲线的拟合问题。其中bj,j=0,1,…n待定。（1）首先，对型值点进行参数化，即确定pi

所对应的参数值，然后将已知条件带入（1）式，得到由m+1个矢量方程组成的方程组：

当m>n时，上面的方程组为矛盾方程组，可用最小二乘法求解。§3.10张量积Bézier曲面给定空间点阵bi,j,i=0,1,…,m;j=0,1,…,n。构造张量积曲面

第3章B样条曲线曲面参数样条不具备形状定义和设计的灵活性；Bezier方法具有整体性和拼接问题的确定B样条方法保留了Bezier方法的优点，同时克服了其由于整体表示带来不具有局部性质的缺点，及解决在描述复杂形状时带来的连接问题B-样条曲线示例。三次均匀B样条曲线3.1B样条曲线方程及其与Bezier曲线的比较为了保留Bezier方法的优点，仍采用控制顶点定义曲线。为了能描述复杂形状和具有局部性质，改用另一套特殊的基函数即B样条基函数。B样条曲线方程Ni,k(u)称为k次B样条基函数。它是由一个称为节点矢量的非递减参数u的序列U所决定的k次分段多项式，即k次多项式样条。B样条基是多项式样条空间具有最小支承的一组基，故称为基本样条（basicspline)，简称B样条3.1B样条曲线方程及其与Bezier曲线的比较B样条曲线与Bezier曲线比较，差别在于：（1）对于Bezier曲线，基函数的次数等于控制顶点数减1。对于B样条曲线，基函数的次数k与控制顶点数无关。（2）Bezier曲线的基函数即伯恩斯坦基函数是多项式函数。B样条曲线的基函数即B样条基函数是多项式样条。（3）Bezier曲线是一种特殊表示形式的参数多项式曲线。B样条曲线则是一种特殊表示形式的参数样条曲线。（4）Bezier曲线缺乏局部性质。B样条曲线具有局部性质。补充知识——样条在数值分析中，样条是一种特殊的函数，由多项式分段定义。样条是一种在造船和工程制图时用来画出光滑形状的工具。在中国大陆，早期曾经被称做“齿函数”。后来因为工程学术语中“放样”一词而得名。在插值问题中，样条插值通常比多项式插值好用。用低阶的样条插值能产生和高阶的多项式插值类似的效果，并且可以避免被称为龙格现象的数值不稳定的出现。并且低阶的样条插值还具有“保凸”的重要性质。在计算机科学的计算机辅助设计和计算机图形学中，样条通常是指分段定义的多项式参数曲线。由于样条构造简单，使用方便，拟合准确，并能近似曲线拟合和交互式曲线设计中复杂的形状，样条是这些领域中曲线的常用表示方法。☆

B样条基函数Ni,m(u)的支撑区间为[ui,ui+m+1]§3.2B样条的递推定义及其性质§3.2B样条的递推定义及其性质曲线方程中相应n+1个控制顶点di

(i=0,1,…,n),要用到n+1个k次B样条基函数Ni,k(u)(i=0,1,…,n),它们每个都是k次B样条。它们的支承区间所含节点的并集就是定义这一组B样条基的节点矢量U=[u0,u1,…,un+k+1]B样条性质：递推性；规范性；局部支承性质；可微性☆B样条曲线的几何性质：直观性。局部性。比Bezier曲线更强的凸包性。保凸性。对称性－－曲线易于反向。与Bezier曲线一样具有几何不变性、变差减小性。

§3.2B样条的递推定义及其性质3.3B样条曲线的局部性质k次B样条的支撑区间包含k+1个节点区间[ui

,ui+k+1].于是在参数u轴上任一点u∈[ui,ui+1]处，就至多只有k+1个非零的k次B样条Nj,k(u)(j=i-k,i-k+1,…,i),其它k次B样条在该处均为零。B样条曲线定义在区间u∈[ui,ui+1]上那一曲线段可表示为该是表明了B样条曲线的局部性质的一个方面u∈[ui,ui+1]3.3B样条曲线的局部性质k次B样条曲线上定义域内参数为u∈[ui,ui+1]的一点p(u)至多与k+1个顶点dj

(j=i-k,i-k+1,…,i)有关，与其它顶点无关。而Bezier曲线上除两端点外的所有点都与控制多边形的全部顶点有关。从另一方面看，如果移动k次B样条曲线的一个控制顶点di,将对曲线有怎样的影响范围呢？与di

相联系的基函数Ni,k(u)有支承区间[ui,ui+k+1].因此移动第i个控制顶点di至多影响到定义在区间(ui,ui+k+1)上那部分曲线，对B样条曲线的其他部分将不发生影响。

3.3B样条曲线的局部性质完整表述：k次B样条曲线上定义域内参数为u∈[ui,ui+1]的一点p(u)至多与k+1个顶点dj

(j=i-k,i-k+1,…,i)有关，与其它顶点无关。移动第i个控制顶点di至多影响到定义在区间(ui,ui+k+1)上那部分曲线，对B样条曲线的其他部分将不发生影响。k次B样条曲线的定义域为u∈[uk,un+1][ui,ui+1]上的k次B样条基仅涉及节点序列ui-k+1

,…,ui+k,共包含2k个节点。3.3B样条曲线的局部性质[ui,ui+1]上的k次B样条基Nj,k(u)(j=i-k,i-k+1,…,i)涉及的节点序列应该是ui-k，ui-k+1

,…,ui+k

，ui+k+1，但由于但在[ui,ui+1]上，

，所以不含ui-k，不受ui-k的影响，同理不受ui+k+1的影响，所以[ui,ui+1]上的k次B样条基仅涉及节点序列ui-k+1

,…,ui+k

,共包含2k个节点。3.4B样条可微性或参数连续性另一占支配地位的性质在每一曲线段内部是无限次可微在定义域内部重复度为r的节点处是k-r次可微§3.5重节点的影响☆节点重复度增加1，支撑区间中减少一个非零节点区间，该节点处的可微性降低1次。例：零阶连续零阶不连续！根据Ck-r连续性的结论，可在B样条曲线内部构造尖点和尖角甚至断点。§3.5重节点的影响（续）☆端节点重复度为k＋1时，B样条曲线具有与Bezier曲线相同的端点性质。☆端节点重复度为k＋1，其它内部节点的重复度均为1，且均匀分布时，称为准均匀B样条曲线。3.5重节点对B样条曲线的影响k次B样条曲线在重复度为r的节点处是Ck-r连续的。一条位置连续的曲线，其内节点所取的最大重复度等于曲线的次数k，端节点的最大重复度为k+1.当在曲线定义域内有重复度为k的节点时，k次B样条曲线插值于相应的控制顶点。与设置k重顶点达到插值顶点不同之处在于，不致引起曲线在该点处切矢消失，保持曲线的正则性。当端节点重复度为k+1时，k次B样条曲线就具有k次贝齐儿曲线相同的端点几何性质若端节点重复度为k+1的k次B样条曲线的定义域仅有一个非零节点区间，则所定义的该k次B样条曲线就是k次贝齐儿曲线。3.6B样条曲线的类型划分对于B样条曲线来说，决定其性质的最重要的属性是节点矢量。国际标准化组织（ISO）制定的标准也是按照节点矢量中节点的分布情况不同给出B样条曲线的类型划分。均匀B样条曲线准均匀B样条曲线节点矢量中两端节点具有重复度k+1,所有内节点均匀分布，具有重复度1一般非均匀B样条曲线§3.7非均匀B样条曲线节点矢量确定

m次非均匀B样条曲线除给定控制顶点，还必须按照一定的规则确定节点矢量中具体的节点值。开曲线一般取m＋1重端节点，并且将定义域取成规范参数域，即u0=…=um=0,un+1=…=un+m+1=1,[um,un+1]=[0,1]。主要的问题是考虑内节点的确定。

节点是B样条曲线分段连接点对应的参数值。参数值的确定应遵循均匀性原则。对B样条曲线来说，是给定控制顶点和曲线次数，分段连接点尚未给定。如何找到分段连接点与控制顶点和次数的关系，利用顶点和次数确定合理的节点矢量就是问题之所在。§3.7非均匀B样条曲线节点矢量确定弦长参数化使得相邻分段连接点的参数值之差与相邻顶点间的距离成正比与实际有相当的出入。一个替代就是采用控制多边形相应k条边的和，在予以规范化——哈特利-贾徳方法构成k条边的k+1个控制顶点定义相应的B样条曲线段，其他控制顶点对该曲线段没有影响，不予考虑3.8.1B样条曲线上点的计算

类似于Bezier曲线的递推求值，B样条曲线也有几何直观的递推求值方法。k为递推次数3.8.2B样条曲线导矢计算k次B样条曲线上一点处的r阶导矢可按如下递推公式计算：计算r阶导矢步骤：先计算出k-r+1个中间顶点然后，应用德布尔算法，计算出由这些顶点和节点矢量定义的k-r次B样条曲线上参数值为u的那一点，即为所求的r阶导矢3.9B样条曲线的配套算法控制顶点反算注意：待计算的控制顶点数目要比数据点数目多出k-1个，需补充k-1个由合适的边界条件给出的附加方程。插入节点插入节点算法是B样条方法配套技术中最重要的技术之一。它既有重要的理论价值，又在曲线曲面设计中有着广泛的用途。通过插入节点：（1）能很简单的证明B样条曲线的变差减少性质（2）可以进一步改善B样条曲线的局部性质，提高对B样条曲线形状控制的潜在灵活性3.9B样条曲线的配套算法（3）可以求出B样条曲线上的点（4）可以生成曲线的贝齐儿点，得到B样条曲线的分段贝齐儿表示（5）可以实现对曲线的分割（6）在生成曲面时，可以使不相同的节点矢量统一起来节点插入算法类似德布尔递推算法：插入一个节点——一级德布尔递推算法重复插入同一节点l次——l级德布尔递推算法3.9B样条曲线的配套算法插入节点进一步结论：1、插入节点是一个局部过程。对k次B样条曲线插入一个节点仅与k-r+1个老顶点有关，且这些老顶点中仅除首末顶点外的其余k-r-1个被新顶点所替代，其它顶点不受影响。2、当插入多个节点时，最后结果与插入的先后次序无关3、插入节点将改变B样条基在所插节点处的可微性，每插入一次，可微性降一阶3.9B样条曲线的配套算法当插入节点无限加密时，其控制多边形序列将收敛到所定义的B样条曲线。其收敛速度要比贝齐儿曲线的升阶与B样条曲线的升阶的收敛速度快得多。通过插入节点对B样条曲线进行重复分割，生成的控制多边形将充分地接近于曲线，可用来替代直接绘制曲线。插入节点是一个变差减少过程。通过插入节点，直到使所有节点达到满重复度，B样条控制多边形就是分段贝齐儿多边形。而后者具有变差减少性质，因此B样条曲线也具有变差减少性质。3.9B样条曲线的配套算法B样条曲线的升阶——B样条曲线的次数提升是B样条方法配套技术中另一项重要技术。1、升阶可以增加曲线的柔性，提高其形状控制的潜在灵活性。因为通过升阶，增加了控制顶点数，也就增加了自由度。通过插入节点也可以在某个区域增加形状控制的灵活性，但是一旦移动生成的新控制顶点，样条曲线在插入节点处的连续性将遭受损失。如果采用升阶的方法，则不论怎样移动升阶后生成的新控制顶点，样条曲线的参数连续性将保持不变。3.9B样条曲线的配套算法2、B样条曲线的升阶在表示与设计组合曲线时是必不可少的手段之一。两条或若干条不同次的B样条曲线要顺序连接成为一条组合B样条曲线，用一个统一的方程表示，必须先采用升阶方法，使它们的次数统一起来，才有可能实现这样的连接。3、B样条曲线的升阶在生成曲面时，在表示与设计组合曲面时同样有重要的用途。3.9B样条曲线的配套算法与贝齐儿曲线的升阶相比，B样条曲线的升阶要复杂得多。复杂在第一步要将定义域内所有相异节点重复度增加1；第二步是确定未知新的控制顶点，可有普劳茨方法及科恩-利切-舒马克方法。§3.10B样条曲面次B样条曲面可以表达为：其中，为呈拓扑矩形排列的曲面的控制顶点阵列。B样条曲面为张量积曲面。第4章NURBS曲线曲面NURBS——Non-UniformRationalB-Spline参数样条、Bezier方法、B样条方法回顾与分析，有待解决的一个重要问题是自由曲线曲面和解析曲线曲面（二次曲线弧与二次曲面）的精确统一表示。1974

，美国的K.J.Versprille以博士论文的形式发表了第1篇有关NURBS的文章，以后L.Piegl

和W.Tiller对NURBS进行了深入研究，使之在理论和应用上趋于成熟。IGES和STEP标准分别将其列为优化类型和唯一的自由曲线曲面表示方法。§4.1概述

学习NURBS重点掌握的问题：

1.NURBS的定义

2.权因子的意义

3.解析曲线的NURBS表示

4.NURBS的各种算法

5.各种构型曲面的NURBS表示§4.1概述（续）☺1.有理分式表示:其中，wi,i=0,1,…,n为与控制顶点相联系的权因子。w0，wn>0其余wi≥

0。Ni,k为k次规范B样条基函数。§4.2NURBS曲线的定义2.有理基函数表示有理B样条基函数的性质：局部支撑性质规范性可微性

节点区间内,节点区间上若

，则若，则若，则若，则§4.2NURBS曲线的定义（续）3.齐次坐标表示§4.2NURBS曲线的定义（续）NURBS的定义步骤：确定带权控制顶点2.用带权控制顶点定义一条齐次空间中的K次B样条曲线将齐次空间中的K次B样条曲线投影到的平面上，得§4.2NURBS曲线的定义（续）§4.2NURBS曲线的定义三种等价的NURBS曲线方程比较三种等价表示虽是等价的，但却具有不同的作用。分式表示是有理的由来，从NURBS曲线的有理分式表示可见，当所有权因子均为