《第六章曲线插值》由会员分享，可在线阅读，更多相关《第六章曲线插值（50页珍藏版）》请在金锄头文库上搜索。
1、计算机图形学基础计算机图形学基础Computer Graphics 赵东保赵东保 华北水利水电学院华北水利水电学院2011.92011.9第六章 自由曲线和曲面1自由曲线和曲面是指那些形状比较复杂、不能用初等解析函数直接表示出来的曲线和曲面。汽车车身、飞机机翼和轮船船体等的曲线和曲面均属于这一类。一般情况下，它们需要利用插值或逼近的方法，对型值点进行拟合，得到拟合曲线和曲面。1 1 概述概述22 2 曲线的参数表示曲线的参数表示曲线的参数方程为曲线的参数方程为归一化归一化处理：为了方便起见，可以将参数t的范围区间规范化成0，1。 参数化表示比显式、隐式有更多的优点！参数化表示比显式、隐式有更多
2、的优点！参数化表示方式易于用矢量和矩阵运算，对曲率、参数化表示方式易于用矢量和矩阵运算，对曲率、斜率等的计算也有别于传统方式。斜率等的计算也有别于传统方式。3n n设设设设已已已已知知知知某某某某个个个个函函函函数数数数关关关关系系系系 在在在在某某某某些些些些离离离离散散散散点点点点上上上上的的的的函函函函数值：数值：数值：数值：n n根根根根据据据据这这这这些些些些已已已已知知知知数数数数据据据据来来来来构构构构造造造造原原原原始始始始函函函函数数数数y=f(x)y=f(x)的的的的近近近近似似似似表表表表达达达达式式式式，并并并并尽尽尽尽可可可可能能能能逼逼逼逼近近近近它它它它，从从从从
3、而而而而反反反反映映映映这这这这些些些些数数数数据据据据所所所所隐隐隐隐含的函数变化规律。含的函数变化规律。含的函数变化规律。含的函数变化规律。3 3 插值与拟合插值与拟合43 3 插值与拟合插值与拟合在在计计算算机机图图形形学学中中，与与上上述述相相对对应应的的问问题题即即是是自自自自由由由由曲曲曲曲线线线线的的的的生生生生成成成成：给给出出一一组组有有序序的的型型值值点点列列，根根据据应应用用要要求求求求得得一一条条光光滑滑曲曲线线，使使其其尽尽可可能能逼逼近近原原始始函函数数曲线，通常采用两种方法，即插值和拟合。曲线，通常采用两种方法，即插值和拟合。插值插值插值插值方法要求生成的曲线通过
4、每个给定的型值点。方法要求生成的曲线通过每个给定的型值点。拟拟拟拟合合合合方方法法要要求求生生成成的的曲曲线线靠靠近近每每个个型型值值点点，但但不不一一定要求通过每个点。定要求通过每个点。5选选用用不不同同类类型型的的插插值值函函数数，逼逼近近的的效效果果就就不不同，一般有：同，一般有：（1）拉格朗日插值（）拉格朗日插值（lagrange插值）插值）（2）Hermite插值插值（3）三次样条插值）三次样条插值4 4 插值方法插值方法6已已已已知知知知函函函函数数数数y=f(x)y=f(x)在在在在n+1n+1个个个个互互互互不不不不相相相相同同同同的的的的点点点点处处处处的的的的函函函函数数数
5、数值值值值y yi i =f=f(x(xi i),i=0,1,n),i=0,1,n ，为为为为求求求求得得得得y=f(x)y=f(x)的的的的近近近近似似似似表表表表达达达达式式式式，容容容容易易易易想到的是选择想到的是选择想到的是选择想到的是选择n n次多项式次多项式次多项式次多项式使使Pn(x) 满足条件满足条件4.1 4.1 拉格朗日插值拉格朗日插值函函函函数数数数y=f(x)y=f(x)称称称称为为为为被被被被插插插插函函函函数数数数，x x0 0,x ,x1 1,x ,x2 2,x,xn n被被被被称称称称为为为为插插插插值节点，条件式被称成为插值条件。值节点，条件式被称成为插值条件
6、。值节点，条件式被称成为插值条件。值节点，条件式被称成为插值条件。7插插值值多多项项式式的的几几何何意意义义实实质质上上是是将将通通过过n+1个个点点(xi,yi),i=0,1,2,n的的多多项项式式曲曲线线当当作作被被插插函函数数曲线曲线y=f(x)的近似曲线。的近似曲线。4.1 4.1 拉格朗日插值拉格朗日插值8设所要构造的插值多项式为：设所要构造的插值多项式为： 由插值条件由插值条件 得到如下线性代数方程组：得到如下线性代数方程组：4.1 4.1 拉格朗日插值拉格朗日插值9此方程组的系数行列式为此方程组的系数行列式为 上上式式即即为为范范得得蒙蒙行行列列式式，由由于于插插值值结结点点xi
7、互互不不相相同同，故故D 0 ，则，则Pn(x)可由可由a0, a1, an唯一确定。唯一确定。4.1 4.1 拉格朗日插值拉格朗日插值10 上上述述多多项项式式插插值值方方法法需需要要解解算算方方程程组组，而而拉拉格格朗朗日日插插值值公公式式的的基基本本思思想想是是，把把pn(x)的的 构构 造造 问问 题题 转转 化化 为为 n+1个个 插插 值值 基基 函函 数数li(x)(i=0,1,n)的构造。的构造。 4.1 4.1 拉格朗日插值拉格朗日插值11构造各个插值节点上的基函数构造各个插值节点上的基函数 l li i(x)(i=0,1,n)(x)(i=0,1,n) 满足如下条件满足如下条
8、件1 10 00 00 00 01 10 00 00 00 00 01 14.1 4.1 拉格朗日插值拉格朗日插值12求求n次多项式次多项式l lk k(x)(i=0,1,n)(x)(i=0,1,n)， k = 0, 1, n则则 i = 0, 1, 2, n即即 Pn(x) 满足插值条件满足插值条件 4.1 4.1 拉格朗日插值拉格朗日插值134.1 4.1 拉格朗日插值拉格朗日插值从而得从而得n 阶拉格朗日（阶拉格朗日（Lagrange）插值公式：）插值公式：根据根据lk(x) 的表达式，的表达式，xk 以外所有的结点都是以外所有的结点都是lk(x)的根的根144.1 4.1 拉格朗日插值
9、拉格朗日插值特别地，当特别地，当n=1时，为线性插值：时，为线性插值：记记记记则有：则有：满足插值条件。满足插值条件。154.1 4.1 拉格朗日插值拉格朗日插值线性插值多项式线性插值多项式 P1(x)可以改写为可以改写为故故线线性性插插值值多多项项式式的的几几何何含含义义就就是是构构造造过过插插值值节点的一条线段节点的一条线段164.1 4.1 拉格朗日插值拉格朗日插值当当n=2时，为抛物线插值：时，为抛物线插值：记记记记则有：则有：满足插值条件。满足插值条件。174.1 4.1 拉格朗日插值拉格朗日插值抛物线插值多项式抛物线插值多项式 抛抛物物线线插插值值多多项项式式的的几几何何含含义义就
10、就是是从从几几何何上上看看就就是是用用通通过过三三点点抛抛物物线线函函数数P2(x)近近似似代代替替原原始始被插函数被插函数f(x)。P2(x)18在在实实际际应应用用中中，不不仅仅要要求求插插值值函函数数与与被被插插函函数数在在节节点点上上函函数数值值相相等等，而而且且要要求求若若干干阶阶导导数数也也相相等等，如如机翼设计等。机翼设计等。（i = 0, 1, , n）满满足足函函数数值值相相等等且且导导数数也也相相等等的的插插值值方方法法称称为为埃埃尔尔米米特（特（HermiteHermite插值）插值）4.2 4.2 埃尔米特插值埃尔米特插值19一般来说，给定一般来说，给定 m+1 个插值
11、条件，就可以构造出一个插值条件，就可以构造出一个个 m 次次 Hermite 插值多项式插值多项式 n 两个典型的两个典型的 Hermite 插值插值l 三点三次三点三次 Hermite 插值插值l 两点三次两点三次 Hermite 插值插值插值节点：插值节点：x x0 0 , , x x1 1 , , x x2 2 插值条件：插值条件：P P( (x xi i) = ) = f f( (x xi i) )，i =i = 0, 1, 2 0, 1, 2，P P ( (x x1 1) = ) = f f ( (x x1 1) )插值节点：插值节点：x x0 0 , , x x1 1插值条件：插值
12、条件：P P( (x xi i) = ) = f f( (x xi i) )，P P ( (x xi i) = ) = f f ( (x xi i) ) ，i =i = 0, 1 0, 14.2 4.2 埃尔米特插值埃尔米特插值20插值节点：插值节点：x x0 0 , , x x1 1 插值条件：插值条件：P P( (x xi i) = ) = f f( (x xi i) = ) = y yi i，P P ( (x xi i) = ) = f f ( (x xi i) = ) = mmi i，i =i = 0, 1 0, 1两两点三次点三次 Hermite 插值插值模仿模仿 Lagrange
13、多项式的思想，设多项式的思想，设其中其中 均为均为 3 次多项式，且满足次多项式，且满足i, j= 0, 14.2 4.2 埃尔米特插值埃尔米特插值21将插值条件代入立即可得将插值条件代入立即可得 0(x), 1(x), 0(x), 1(x) 的表达式？的表达式？ 0(x)4.2 4.2 埃尔米特插值埃尔米特插值22同理可得同理可得相类似地，可以推出相类似地，可以推出 4.2 4.2 埃尔米特插值埃尔米特插值23满足插值条件满足插值条件P(x0) = f(x0) = y0，P(x0) = f(x0) = m0P(x1) = f(x1) = y1，P(x1) = f(x1) = m1的的三次三次
14、 Hermite 插值多项式为插值多项式为4.2 4.2 埃尔米特插值埃尔米特插值244.2 4.2 埃尔米特插值埃尔米特插值参数连续性条件参数连续性条件参数连续性条件参数连续性条件 0 0阶阶导导数数连连续续性性，记作C C0 0连连续续，是指两个曲线段在公共点处有相同的坐标。 一一阶阶导导数数连连续续性性，记作C C1 1连连续续，指两个相邻曲线段在交点处有相同的一阶导数。 二二阶阶导导数数连连续续性性，记作C C2 2连连续续，指两个相邻曲线段在交点处有相同的一阶和二阶导数。 0 0阶几何连续性阶几何连续性，记为G G0 0连续连续，与0阶导数连续性相同。 一一阶阶几几何何连连续续性性，
15、记为G G1 1连连续续，指一阶导数在两个相邻段的交点处成比例，而大小不一定相等。 二二阶阶几几何何连连续续性性，记为G G2 2连续，指两个曲线段在相交处其一阶和二阶导数均成比例。G2连续下，两个曲线段在交点处的曲率相等。255 5 基于插值思想的曲线生成基于插值思想的曲线生成基基基基于于于于插插插插值值值值方方法法生生成成的的曲曲线线通通过过每每个个型型值值点点，在在GISGIS地地图图制制图图中中一一般般通通过过插插值值，使使得得曲曲线线变变得得更更光光滑滑，如如等等高高线线的的光光滑滑就就常常采采用用插插值值方方法法，常常见的有：见的有：p三点光滑法p五点光滑法p三次样条光滑法265.
16、1 5.1 五点光滑法五点光滑法五点光滑法是等高线光滑中最常使用的方法，其光滑的结果类似于制图员的手工光滑效果。基本思路为：p每两个数据点之间建立一条三次多项式曲线方程。p曲线具有连续的一阶导数。p 各数据点的导数是以一点为中心，左右两边各相邻的两个点，一共五个点来确定的。275.1 5.1 五点光滑法五点光滑法五点光滑法各数据点的一阶导数是由其他相邻四个点求得的。图中P1点的一阶导数待求，设其值为t1K1，K2，K3，K4分别为四个折线段Pi-2Pi-1，Pi-2Pi-1, Pi-2Pi-1,Pi+1Pi+2的斜率。285.1 5.1 五点光滑法五点光滑法当等高线不闭合，对于第一个点和第二个
17、点以及倒数第二个点及第一个点，采用补点的方法求一阶导数，补点采用增量相等的原则来补：当欲求P1点一阶导数时，需要向前补充A点。其补充原则为：P2P1坐标增量-P1P0坐标增量= P1P0坐标增量-P0A坐标增量，由此可以补出A点坐标。295.1 5.1 五点光滑法五点光滑法设每两个数据点的三次多项式为：由此可以对每一个原始等高线的折线段求出一组a,b,c,d四个参数，构建一个三次多项式，实现光滑。插值条件为：305.1 5.1 五点光滑法五点光滑法五点光滑法是等高线光滑中最常使用的方法，其光滑的结果类似于制图员的手工光滑效果。基本思路为：p每两个数据点之间建立一条三次多项式曲线方程。p曲线具有
18、连续的一阶导数。p 各数据点的导数是以一点为中心，左右两边各相邻的两个点，一共五个点来确定的。31能否找到一个简单易算的能否找到一个简单易算的 p(x) ，使得，使得 f(x) p(x)已知已知 f(x) 在某些点的函数值：在某些点的函数值：xx0x1xm f(x)y0y1ym但是但是(1) m 通常很大通常很大 (2) yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f (xi) 这时不要求这时不要求 p(xi) = yi , 而只要而只要 p(xi) yi 总体上尽可能小总体上尽可能小 5 5 拟合方法拟合方法32l 使使 最小最小 p(xi) yi 总体上尽可能小总体上尽可
19、能小 l 使使 最小最小q 常见做法常见做法太复杂太复杂 不可导，求不可导，求解困难解困难 l 使使 最小最小最小二乘法：最小二乘法：目前最好的多项式曲线拟合算法目前最好的多项式曲线拟合算法5 5 拟合方法拟合方法33对于给定的一组数据对于给定的一组数据(xi,yi)(i=0,1,2,.,n)求求m(m=n)m(m=n)次多项式来拟合原始函数次多项式来拟合原始函数需要求出多项式的需要求出多项式的m+1m+1个待定系数即可，且使得个待定系数即可，且使得以下函数值达到最小以下函数值达到最小F(a0，a1，am)=Min5 5 最小二乘拟合最小二乘拟合34要使函数值达到最小，即有多元函数求极值即k
20、= 0, 1, , n最小值点最小值点0jFa = = 5 5 最小二乘拟合最小二乘拟合355 5 最小二乘拟合最小二乘拟合写成方程组的形式 法方程组法方程组可以证明该方程组有唯一解367 7 基于拟合思想的曲线生成基于拟合思想的曲线生成基基基基于于于于拟拟拟拟合合合合方方法法生生成成的的曲曲线线靠靠近近每每个个型型值值点点，但但不不一定要求通过每个点。常见的主要有：一定要求通过每个点。常见的主要有：pBezier曲线pB样条曲线377.1 Bezier7.1 Bezier曲线曲线BezierBezier曲曲线线是是由由一一组组多多边边折折线线定定义义的的。在在多多边边折折线线的的各各顶顶点点
21、中中，只只有有第第一一点点和和最最后后一一点点在在曲曲线线上上, , 第第一一条条和和最最后后一一条条折折线线分分别别表表示示出出曲曲线线在在起起点点和和终终点点处处切切线线方方向向。曲曲线线的的形形状状趋趋向向于于多多边边折折线线的的形形状状，因因此此，多多边边折折线线又又称称为为特特特特征征征征多多多多边边边边形形形形，其其顶顶点点称称为为控控控控制点制点制点制点。387.1 Bezier7.1 Bezier曲线曲线 Bezier Bezier曲线的性质曲线的性质p 端端端端点点点点性性性性质质质质：BezierBezierBezierBezier曲曲曲曲线线线线的的的的起起起起点点点点和
22、和和和终终终终点点点点同同同同特特特特征征征征多多多多边边边边形形形形的的的的起起起起点点点点和和和和终终终终点点点点重重重重合合合合。BezierBezierBezierBezier曲曲曲曲线线线线在在在在端端端端点点点点处处处处的的的的一一一一阶阶阶阶导导导导数数数数只只只只同同同同相相相相近近近近的的的的两两两两个个个个控控控控制制制制点点点点有有有有关关关关，其其其其方方方方向向向向为为为为两两两两点点点点的的的的连连连连线线线线方方方方向向向向。在在在在端端端端点点点点处处处处的的的的二二二二阶阶阶阶导导导导数数数数只只只只同同同同相相相相近近近近的的的的三三三三个个个个控控控控制点
23、有关。制点有关。制点有关。制点有关。p 凸凸凸凸包包包包性性性性：BezierBezierBezierBezier曲曲曲曲线线线线落落落落在在在在特特特特征征征征多多多多边边边边形形形形顶顶顶顶点点点点所所所所形形形形成成成成的凸包内。的凸包内。的凸包内。的凸包内。p 几几几几何何何何不不不不变变变变性性性性：BezierBezierBezierBezier曲曲曲曲线线线线的的的的形形形形状状状状由由由由特特特特征征征征多多多多边边边边形形形形的的的的顶点唯一确定，与坐标系的选取无关。顶点唯一确定，与坐标系的选取无关。顶点唯一确定，与坐标系的选取无关。顶点唯一确定，与坐标系的选取无关。39n
24、nBezier曲线的拼接曲线的拼接7.1 Bezier7.1 Bezier曲线曲线407.2 B7.2 B样条曲线样条曲线Bezier曲曲线线实实际际上上是是B样样条条(Basic Spline）曲曲线线的的特特例例。B样样条条曲曲线线除除保保持持了了Bezier曲曲线线的的直直观观性性和和凸凸包包性性等等优优点点之之外外，其其样样条条函函数数中中多多项项式式次次数数也也独独立立于于控控制制点点数数目目，B样样条条曲曲线线还还允允许许局局部部调调整整。由由于于以以上原因，上原因，B样条曲线得到了广泛应用。样条曲线得到了广泛应用。417.2 B7.2 B样条曲线样条曲线 B B样条曲线的性质样条
25、曲线的性质p 端端端端点点点点性性性性质质质质：B B样样样样条条条条曲曲曲曲线线线线的的的的起起起起点点点点和和和和终终终终点点点点都都都都不不不不在在在在曲曲曲曲线线线线上，只与邻近三个控制点有关。上，只与邻近三个控制点有关。上，只与邻近三个控制点有关。上，只与邻近三个控制点有关。p连连连连续续续续性性性性：B B样样样样条条条条曲曲曲曲线线线线段段段段之之之之间间间间是是是是自自自自行行行行光光光光滑滑滑滑连连连连续续续续的的的的，B B样样样样条条条条曲曲曲曲线线线线段段段段之之之之间间间间是是是是自自自自行行行行光光光光滑滑滑滑连连连连续续续续的的的的。而而而而且且且且，n n次次次
26、次B B样样样样条曲线具有条曲线具有条曲线具有条曲线具有n-1n-1阶导数的连续性。阶导数的连续性。阶导数的连续性。阶导数的连续性。p局局局局部部部部性性性性和和和和扩扩扩扩展展展展性性性性：在在在在三三三三次次次次B B样样样样条条条条曲曲曲曲线线线线中中中中，每每每每个个个个B B样样样样条条条条曲曲曲曲线线线线段段段段受受受受四四四四个个个个控控控控制制制制点点点点影影影影响响响响。如如如如果果果果增增增增加加加加一一一一个个个个控控控控制制制制点点点点，就就就就相相相相应应应应地地地地增增增增加加加加了了了了一一一一段段段段B B样样样样条条条条曲曲曲曲线线线线。此此此此时时时时，原原
27、原原有有有有的的的的B B样样样样条曲线不受影响。条曲线不受影响。条曲线不受影响。条曲线不受影响。42n n特殊外形设计n n三顶点共线三顶点共线n n位于控制多边形边上的一个点位于控制多边形边上的一个点P0P2P1MP(0)P(0)P0P2MP1P(0)7.2 B7.2 B样条曲线样条曲线43n n特殊外形设计n n四顶点共线四顶点共线n n含有直线段的曲线含有直线段的曲线P0P3P1P2P(0)M1P(1)M27.2 B7.2 B样条曲线样条曲线44B样条曲线（9/17）n n特殊外形设计n n两顶点重合两顶点重合P0P2P1MP(0)P0P2MP1P(0)P(0)45B样条曲线（10/1
28、7）n n特殊外形设计n n两顶点重合两顶点重合n n相切于控制多边形边的曲线相切于控制多边形边的曲线P2P5P1P0P4P346B样条曲线（11/17）n n特殊外形设计n n三顶点重合三顶点重合n n含有尖点的曲线含有尖点的曲线P2P6P1P0P4P3P547n地形表面的生成地形表面的生成l l由离散点集构建由离散点集构建TINTINn地形表面的光滑地形表面的光滑l l双线性内插双线性内插l l三次曲面内插三次曲面内插8 8 曲面的生成曲面的生成48三次曲面方程为格网中的p点为待插点，设原始被插函数方程为f(x,y)，令该点所在格网内插函数为三次多项式曲面方程。8 8 曲面的生成曲面的生成49插值条件50
