第六章..优秀PPT.ppt

《第六章..优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第六章..优秀PPT.ppt（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、计算机图形学基础计算机图形学基础Computer Graphics 赵东保赵东保 华北水利水电学院华北水利水电学院2011.92011.9第六章 自由曲线和曲面1自由曲线和曲面是指那些形态比较困难、不能用初等解析函数干脆表示出来的曲线和曲面。汽车车身、飞机机翼和轮船船体等的曲线和曲面均属于这一类。一般状况下，它们须要利用插值或靠近的方法，对型值点进行拟合，得到拟合曲线和曲面。1 1 概述概述22 2 曲线的参数表示曲线的参数表示曲线的参数方程为曲线的参数方程为归一化处理：为了便利起见，可以将参数归一化处理：为了便利起见，可以将参数t t的范围区的范围区间规范化成间规范化成00，11。参数化表示

2、比显式、隐式有更多的优点！参数化表示比显式、隐式有更多的优点！参数化表示方式易于用矢量和矩阵运算，对曲率、参数化表示方式易于用矢量和矩阵运算，对曲率、斜率等的计算也有别于传统方式。斜率等的计算也有别于传统方式。3n n设设设设已已已已知知知知某某某某个个个个函函函函数数数数关关关关系系系系 在在在在某某某某些些些些离离离离散散散散点点点点上上上上的的的的函函函函数值：数值：数值：数值：n n依依依依据据据据这这这这些些些些已已已已知知知知数数数数据据据据来来来来构构构构造造造造原原原原始始始始函函函函数数数数y=f(x)y=f(x)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、点点处处处处的的的的函函函函数数数数值值值值yi yi=f(xi),i=0,1,n=f(xi),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此方程组的系数行列式为此方程组的系数行列式为 上上式式即即为为范范得得蒙蒙行行列列式式，由由于于插

7、插值值结结点点xi互互不不相相同同，故故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构造各个插值节点上的基函数构造各个插值节点上的基函数 li(x)(i=0,1,n)满足如下条件满足如下条件1 10 00 00 0

8、0 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 拉格朗日插值拉格朗日插值特殊地，当特殊地，当n=1时，为线性插

9、值：时，为线性插值：记记记记则有：则有：满足插值条件。满足插值条件。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 个插值条件，就可以构造出一个插值条件，就可以构造出一个个 m 次次

11、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插值条件：插值条件：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.

12、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 多项式的思想，设多项式的思想，设其中其中 均为均为 3 次多项式，且满足次多项式，且满足i,j=0,14.2 4.2 埃尔米特插值埃尔米特插值21将插值条件代入马上可得将插值条件代入马上可得 0(x),1(x),0(x),1(x)的表达式？的表达式？0(x)4.2 4.

13、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的的三次三次 Hermite 插值多项式为插值多项式为4.2 4.2 埃尔米特插值埃尔米特插值244.2 4.2 埃尔米特插值埃尔米特插值参数连续性条件参数连续性条件参数连续性条件参数连续性条件 0 0 0 0阶阶阶阶导导导导数数数数连连连连续续续续性性性性，记记记记作作作作C0C0C0C0连连连连续续续续，是是是是指指指指两两

14、两两个个个个曲曲曲曲线线线线段段段段在在在在公公公公共共共共点处有相同的坐标。点处有相同的坐标。点处有相同的坐标。点处有相同的坐标。一一一一阶阶阶阶导导导导数数数数连连连连续续续续性性性性，记记记记作作作作C1C1C1C1连连连连续续续续，指指指指两两两两个个个个相相相相邻邻邻邻曲曲曲曲线线线线段段段段在在在在交交交交点处有相同的一阶导数。点处有相同的一阶导数。点处有相同的一阶导数。点处有相同的一阶导数。二二二二阶阶阶阶导导导导数数数数连连连连续续续续性性性性，记记记记作作作作C2C2C2C2连连连连续续续续，指指指指两两两两个个个个相相相相邻邻邻邻曲曲曲曲线线线线段段段段在在在在交交交交点处

15、有相同的一阶和二阶导数。点处有相同的一阶和二阶导数。点处有相同的一阶和二阶导数。点处有相同的一阶和二阶导数。0 0 0 0阶几何连续性，记为阶几何连续性，记为阶几何连续性，记为阶几何连续性，记为G0G0G0G0连续，与连续，与连续，与连续，与0 0 0 0阶导数连续性相同。阶导数连续性相同。阶导数连续性相同。阶导数连续性相同。一一一一阶阶阶阶几几几几何何何何连连连连续续续续性性性性，记记记记为为为为G1G1G1G1连连连连续续续续，指指指指一一一一阶阶阶阶导导导导数数数数在在在在两两两两个个个个相相相相邻邻邻邻段的交点处成比例，而大小不确定相等。段的交点处成比例，而大小不确定相等。段的交点处成

16、比例，而大小不确定相等。段的交点处成比例，而大小不确定相等。二二二二阶阶阶阶几几几几何何何何连连连连续续续续性性性性，记记记记为为为为G2G2G2G2连连连连续续续续，指指指指两两两两个个个个曲曲曲曲线线线线段段段段在在在在相相相相交交交交处处处处其其其其一一一一阶阶阶阶和和和和二二二二阶阶阶阶导导导导数数数数均均均均成成成成比比比比例例例例。G2G2G2G2连连连连续续续续下下下下，两两两两个个个个曲曲曲曲线线线线段段段段在在在在交交交交点处的曲率相等。点处的曲率相等。点处的曲率相等。点处的曲率相等。255 5 基于插值思想的曲线生成基于插值思想的曲线生成基基基基于于于于插插插插值值值值方方

17、方方法法法法生生生生成成成成的的的的曲曲曲曲线线线线通通通通过过过过每每每每个个个个型型型型值值值值点点点点，在在在在GISGISGISGIS地地地地图图图图制制制制图图图图中中中中一一一一般般般般通通通通过过过过插插插插值值值值，使使使使得得得得曲曲曲曲线线线线变变变变得得得得更更更更光光光光滑滑滑滑，如如如如等等等等高高高高线线线线的的的的光光光光滑滑滑滑就就就就常常常常接接接接受受受受插插插插值值值值方方方方法法法法，常常常常见的有：见的有：见的有：见的有：三点光滑法三点光滑法三点光滑法三点光滑法五点光滑法五点光滑法五点光滑法五点光滑法三次样条光滑法三次样条光滑法三次样条光滑法三次样条光

18、滑法265.1 5.1 五点光滑法五点光滑法五点光滑法是等高线光滑中最常运用的方法，其光滑的结果类似于制图员的手工光滑效果。基本思路为：每两个数据点之间建立一条三次多项式曲线方程。曲线具有连续的一阶导数。各数据点的导数是以一点为中心，左右两边各相邻的两个点，一共五个点来确定的。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 五点光滑法五点光滑法当等高线不闭合，对于第一个点和其次

19、个点以及倒数其次个点及第一个点，接受补点的方法求一阶导数，补点接受增量相等的原则来补：当欲求P1点一阶导数时，须要向前补充A点。其补充原则为：P2P1坐标增量-P1P0坐标增量=P1P0坐标增量-P0A坐标增量，由此可以补出A点坐标。295.1 5.1 五点光滑法五点光滑法设每两个数据点的三次多项式为：由此可以对每一个原始等高线的折线段求出一组a,b,c,d四个参数，构建一个三次多项式，实现光滑。插值条件为：305.1 5.1 五点光滑法五点光滑法五点光滑法是等高线光滑中最常运用的方法，其光滑的结果类似于制图员的手工光滑效果。基本思路为：每两个数据点之间建立一条三次多项式曲线方程。曲线具有连续

20、的一阶导数。各数据点的导数是以一点为中心，左右两边各相邻的两个点，一共五个点来确定的。31能否找到一个简洁易算的能否找到一个简洁易算的 p(x)，使得，使得 f(x)p(x)已知已知 f(x)在某些点的函数值：在某些点的函数值：xx0 x1xm f(x)y0y1ym但是但是(1)m 通常很大通常很大(2)yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f(xi)这时不要求这时不要求 p(xi)=yi,而只要而只要 p(xi)yi 总体上尽可能小总体上尽可能小 5 5 拟合方法拟合方法32l 使使 最小最小 p(xi)yi 总体上尽可能小总体上尽可能小 l 使使 最小最小q 常见做

21、法常见做法太复杂太复杂 不可导，求不可导，求解困难解困难 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=0,1,n最小值点最小值点0jFa

22、=5 5 最小二乘拟合最小二乘拟合355 5 最小二乘拟合最小二乘拟合写成方程组的形式 法方程组法方程组可以证明该方程组有唯一解367 7 基于拟合思想的曲线生成基于拟合思想的曲线生成基基基基于于于于拟拟拟拟合合合合方方方方法法法法生生生生成成成成的的的的曲曲曲曲线线线线靠靠靠靠近近近近每每每每个个个个型型型型值值值值点点点点，但但但但不不不不确定要求通过每个点。常见的主要有：确定要求通过每个点。常见的主要有：确定要求通过每个点。常见的主要有：确定要求通过每个点。常见的主要有：BezierBezier曲线曲线曲线曲线B B样条曲线样条曲线样条曲线样条曲线377.1 Bezier7.1 Bezi

23、er曲线曲线BezierBezier曲曲线线是是由由一一组组多多边边折折线线定定义义的的。在在多多边边折折线线的的各各顶顶点点中中，只只有有第第一一点点和和最最终终一一点点在在曲曲线线上上,第第一一条条和和最最终终一一条条折折线线分分别别表表示示出出曲曲线线在在起起点点和和终终点点处处切切线线方方向向。曲曲线线的的形形态态趋趋向向于于多多边边折折线线的的形形态态，因因此此，多多边边折折线线又又称称为为特特征征多多边边形形，其其顶顶点点称称为为限限制点。制点。387.1 Bezier7.1 Bezier曲线曲线 Bezier Bezier曲线的性质曲线的性质 端端点点性性质质：BezierBez

24、ier曲曲线线的的起起点点和和终终点点同同特特征征多多边边形形的的起起点点和和终终点点重重合合。BezierBezier曲曲线线在在端端点点处处的的一一阶阶导导数数只只同同相相近近的的两两个个限限制制点点有有关关，其其方方向向为为两两点点的的连连线线方方向向。在在端端点点处处的的二二阶阶导数只同相近的三个限制点有关。导数只同相近的三个限制点有关。凸凸包包性性：BezierBezier曲曲线线落落在在特特征征多多边边形形顶顶点点所所形成的凸包内。形成的凸包内。几几何何不不变变性性：BezierBezier曲曲线线的的形形态态由由特特征征多多边边形的顶点唯一确定，与坐标系的选取无关。形的顶点唯一确

25、定，与坐标系的选取无关。39n nBezier曲线的拼接曲线的拼接7.1 Bezier7.1 Bezier曲线曲线407.2 B7.2 B样条曲线样条曲线Bezier曲曲线线事事实实上上是是B样样条条(Basic Spline）曲曲线线的的特特例例。B样样条条曲曲线线除除保保持持了了Bezier曲曲线线的的直直观观性性和和凸凸包包性性等等优优点点之之外外，其其样样条条函函数数中中多多项项式式次次数数也也独独立立于于限限制制点点数数目目，B样样条条曲曲线线还还允允许许局局部部调调整整。由由于于以以上缘由，上缘由，B样条曲线得到了广泛应用。样条曲线得到了广泛应用。417.2 B7.2 B样条曲线样

26、条曲线 B B样条曲线的性质样条曲线的性质 端端点点性性质质：B B样样条条曲曲线线的的起起点点和和终终点点都都不不在在曲线上，只与邻近三个限制点有关。曲线上，只与邻近三个限制点有关。连连续续性性：B B样样条条曲曲线线段段之之间间是是自自行行光光滑滑连连续续的的，B B样样条条曲曲线线段段之之间间是是自自行行光光滑滑连连续续的的。而而且且，n n次次B B样条曲线具有样条曲线具有n-1n-1阶导数的连续性。阶导数的连续性。局局部部性性和和扩扩展展性性：在在三三次次B B样样条条曲曲线线中中，每每个个B B样样条条曲曲线线段段受受四四个个限限制制点点影影响响。假假如如增增加加一一个个限限制制点

27、点，就就相相应应地地增增加加了了一一段段B B样样条条曲曲线线。此时，原有的此时，原有的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/17）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