第六章(曲线插值)...ppt

计算机图形学基础ComputerGraphics 赵东保 华北水利水电学院 2011 9 第六章自由曲线和曲面 2 自由曲线和曲面是指那些形状比较复杂 不能用初等解析函数直接表示出来的曲线和曲面 汽车车身 飞机机翼和轮船船体等的曲线和曲面均属于这一类 一般情况下 它们需要利用插值或逼近的方法 对型值点进行拟合 得到拟合曲线和曲面 1概述 3 2曲线的参数表示 曲线的参数方程为 归一化处理 为了方便起见 可以将参数t的范围区间规范化成 0 1 参数化表示比显式 隐式有更多的优点 参数化表示方式易于用矢量和矩阵运算 对曲率 斜率等的计算也有别于传统方式 4 设已知某个函数关系在某些离散点上的函数值 根据这些已知数据来构造原始函数y f x 的近似表达式 并尽可能逼近它 从而反映这些数据所隐含的函数变化规律 3插值与拟合 5 3插值与拟合 在计算机图形学中 与上述相对应的问题即是自由曲线的生成 给出一组有序的型值点列 根据应用要求求得一条光滑曲线 使其尽可能逼近原始函数曲线 通常采用两种方法 即插值和拟合 插值方法要求生成的曲线通过每个给定的型值点 拟合方法要求生成的曲线靠近每个型值点 但不一定要求通过每个点 6 选用不同类型的插值函数 逼近的效果就不同 一般有 1 拉格朗日插值 lagrange插值 2 Hermite插值 3 三次样条插值 4插值方法 7 已知函数y f x 在n 1个互不相同的点处的函数值yi f xi i 0 1 n 为求得y f x 的近似表达式 容易想到的是选择n次多项式 使Pn x 满足条件 4 1拉格朗日插值 函数y f x 称为被插函数 x0 x1 x2 xn被称为插值节点 条件式被称成为插值条件 8 插值多项式的几何意义实质上是将通过n 1个点 xi yi i 0 1 2 n的多项式曲线当作被插函数曲线y f x 的近似曲线 4 1拉格朗日插值 9 设所要构造的插值多项式为 由插值条件 得到如下线性代数方程组 4 1拉格朗日插值 10 此方程组的系数行列式为 上式即为范得蒙行列式 由于插值结点xi互不相同 故D 0 则Pn x 可由a0 a1 an唯一确定 4 1拉格朗日插值 11 上述多项式插值方法需要解算方程组 而拉格朗日插值公式的基本思想是 把pn x 的构造问题转化为n 1个插值基函数li x i 0 1 n 的构造 4 1拉格朗日插值 12 构造各个插值节点上的基函数li x i 0 1 n 满足如下条件 4 1拉格朗日插值 13 求n次多项式lk x i 0 1 n k 0 1 n 则 i 0 1 2 n 即Pn x 满足插值条件 4 1拉格朗日插值 14 4 1拉格朗日插值 从而得n阶拉格朗日 Lagrange 插值公式 根据lk x 的表达式 xk以外所有的结点都是lk x 的根 15 4 1拉格朗日插值 特别地 当n 1时 为线性插值 记 则有 满足插值条件 16 4 1拉格朗日插值 线性插值多项式 P1 x 可以改写为 故线性插值多项式的几何含义就是构造过插值节点的一条线段 17 4 1拉格朗日插值 当n 2时 为抛物线插值 记 则有 满足插值条件 18 4 1拉格朗日插值 抛物线插值多项式 抛物线插值多项式的几何含义就是从几何上看就是用通过三点抛物线函数P2 x 近似代替原始被插函数f x P2 x 19 在实际应用中 不仅要求插值函数与被插函数在节点上函数值相等 而且要求若干阶导数也相等 如机翼设计等 i 0 1 n 满足函数值相等且导数也相等的插值方法称为埃尔米特 Hermite插值 4 2埃尔米特插值 20 一般来说 给定m 1个插值条件 就可以构造出一个m次Hermite插值多项式 两个典型的Hermite插值 三点三次Hermite插值 两点三次Hermite插值 插值节点 x0 x1 x2插值条件 P xi f xi i 0 1 2 P x1 f x1 插值节点 x0 x1插值条件 P xi f xi P xi f xi i 0 1 4 2埃尔米特插值 21 插值节点 x0 x1插值条件 P xi f xi yi P xi f xi mi i 0 1 两点三次Hermite插值 模仿Lagrange多项式的思想 设 其中均为3次多项式 且满足 i j 0 1 4 2埃尔米特插值 22 将插值条件代入立即可得 0 x 1 x 0 x 1 x 的表达式 0 x 4 2埃尔米特插值 23 同理可得 相类似地 可以推出 4 2埃尔米特插值 24 满足插值条件 P x0 f x0 y0 P x0 f x0 m0P x1 f x1 y1 P x1 f x1 m1 的三次Hermite插值多项式为 4 2埃尔米特插值 25 4 2埃尔米特插值 参数连续性条件0阶导数连续性 记作C0连续 是指两个曲线段在公共点处有相同的坐标 一阶导数连续性 记作C1连续 指两个相邻曲线段在交点处有相同的一阶导数 二阶导数连续性 记作C2连续 指两个相邻曲线段在交点处有相同的一阶和二阶导数 0阶几何连续性 记为G0连续 与0阶导数连续性相同 一阶几何连续性 记为G1连续 指一阶导数在两个相邻段的交点处成比例 而大小不一定相等 二阶几何连续性 记为G2连续 指两个曲线段在相交处其一阶和二阶导数均成比例 G2连续下 两个曲线段在交点处的曲率相等 26 5基于插值思想的曲线生成 基于插值方法生成的曲线通过每个型值点 在GIS地图制图中一般通过插值 使得曲线变得更光滑 如等高线的光滑就常采用插值方法 常见的有 三点光滑法五点光滑法三次样条光滑法 27 5 1五点光滑法 五点光滑法是等高线光滑中最常使用的方法 其光滑的结果类似于制图员的手工光滑效果 基本思路为 每两个数据点之间建立一条三次多项式曲线方程 曲线具有连续的一阶导数 各数据点的导数是以一点为中心 左右两边各相邻的两个点 一共五个点来确定的 28 5 1五点光滑法 五点光滑法各数据点的一阶导数是由其他相邻四个点求得的 图中P1点的一阶导数待求 设其值为t1 K1 K2 K3 K4分别为四个折线段Pi 2Pi 1 Pi 2Pi 1 Pi 2Pi 1 Pi 1Pi 2的斜率 29 5 1五点光滑法 当等高线不闭合 对于第一个点和第二个点以及倒数第二个点及第一个点 采用补点的方法求一阶导数 补点采用增量相等的原则来补 当欲求P1点一阶导数时 需要向前补充A点 其补充原则为 P2P1坐标增量 P1P0坐标增量 P1P0坐标增量 P0A坐标增量 由此可以补出A点坐标 30 5 1五点光滑法 设每两个数据点的三次多项式为 由此可以对每一个原始等高线的折线段求出一组a b c d四个参数 构建一个三次多项式 实现光滑 插值条件为 31 5 1五点光滑法 五点光滑法是等高线光滑中最常使用的方法 其光滑的结果类似于制图员的手工光滑效果 基本思路为 每两个数据点之间建立一条三次多项式曲线方程 曲线具有连续的一阶导数 各数据点的导数是以一点为中心 左右两边各相邻的两个点 一共五个点来确定的 32 能否找到一个简单易算的p x 使得f x p x 已知f x 在某些点的函数值 5拟合方法 33 使最小 p xi yi总体上尽可能小 使最小 常见做法 5拟合方法 34 对于给定的一组数据 xi yi i 0 1 2 n 求m m n 次多项式来拟合原始函数 需要求出多项式的m 1个待定系数即可 且使得以下函数值达到最小 F a0 a1 am Min 5最小二乘拟合 35 要使函数值达到最小 即有多元函数求极值 即 k 0 1 n 最小值点 5最小二乘拟合 36 5最小二乘拟合 写成方程组的形式 法方程组 可以证明该方程组有唯一解 37 7基于拟合思想的曲线生成 基于拟合方法生成的曲线靠近每个型值点 但不一定要求通过每个点 常见的主要有 Bezier曲线B样条曲线 38 7 1Bezier曲线 Bezier曲线是由一组多边折线定义的 在多边折线的各顶点中 只有第一点和最后一点在曲线上 第一条和最后一条折线分别表示出曲线在起点和终点处切线方向 曲线的形状趋向于多边折线的形状 因此 多边折线又称为特征多边形 其顶点称为控制点 39 7 1Bezier曲线 Bezier曲线的性质端点性质 Bezier曲线的起点和终点同特征多边形的起点和终点重合 Bezier曲线在端点处的一阶导数只同相近的两个控制点有关 其方向为两点的连线方向 在端点处的二阶导数只同相近的三个控制点有关 凸包性 Bezier曲线落在特征多边形顶点所形成的凸包内 几何不变性 Bezier曲线的形状由特征多边形的顶点唯一确定 与坐标系的选取无关 40 Bezier曲线的拼接 7 1Bezier曲线 41 7 2B样条曲线 Bezier曲线实际上是B样条 BasicSpline 曲线的特例 B样条曲线除保持了Bezier曲线的直观性和凸包性等优点之外 其样条函数中多项式次数也独立于控制点数目 B样条曲线还允许局部调整 由于以上原因 B样条曲线得到了广泛应用 42 7 2B样条曲线 B样条曲线的性质端点性质 B样条曲线的起点和终点都不在曲线上 只与邻近三个控制点有关 连续性 B样条曲线段之间是自行光滑连续的 B样条曲线段之间是自行光滑连续的 而且 n次B样条曲线具有n 1阶导数的连续性 局部性和扩展性 在三次B样条曲线中 每个B样条曲线段受四个控制点影响 如果增加一个控制点 就相应地增加了一段B样条曲线 此时 原有的B样条曲线不受影响 43 特殊外形设计三顶点共线位于控制多边形边上的一个点 P0 P2 P1 M P 0 P 0 P0 P2 M P1 7 2B样条曲线 44 特殊外形设计四顶点共线含有直线段的曲线 P0 P3 P1 P2 7 2B样条曲线 45 B样条曲线 9 17 特殊外形设计两顶点重合 P0 P2 P1 M P 0 P0 P2 M P1 46 B样条曲线 10 17