第六章(曲線插值)..

計(jì)算機(jī)圖形學(xué)基礎(chǔ)ComputerGraphics 趙東保 華北水利水電學(xué)院 2011 9 第六章自由曲線和曲面 2 自由曲線和曲面是指那些形狀比較復(fù)雜 不能用初等解析函數(shù)直接表示出來(lái)的曲線和曲面 汽車車身 飛機(jī)機(jī)翼和輪船船體等的曲線和曲面均屬于這一類 一般情況下 它們需要利用插值或逼近的方法 對(duì)型值點(diǎn)進(jìn)行擬合 得到擬合曲線和曲面 1概述 3 2曲線的參數(shù)表示 曲線的參數(shù)方程為 歸一化處理 為了方便起見(jiàn) 可以將參數(shù)t的范圍區(qū)間規(guī)范化成 0 1 參數(shù)化表示比顯式 隱式有更多的優(yōu)點(diǎn) 參數(shù)化表示方式易于用矢量和矩陣運(yùn)算 對(duì)曲率 斜率等的計(jì)算也有別于傳統(tǒng)方式 4 設(shè)已知某個(gè)函數(shù)關(guān)系在某些離散點(diǎn)上的函數(shù)值 根據(jù)這些已知數(shù)據(jù)來(lái)構(gòu)造原始函數(shù)y f x 的近似表達(dá)式 并盡可能逼近它 從而反映這些數(shù)據(jù)所隱含的函數(shù)變化規(guī)律 3插值與擬合 5 3插值與擬合 在計(jì)算機(jī)圖形學(xué)中 與上述相對(duì)應(yīng)的問(wèn)題即是自由曲線的生成 給出一組有序的型值點(diǎn)列 根據(jù)應(yīng)用要求求得一條光滑曲線 使其盡可能逼近原始函數(shù)曲線 通常采用兩種方法 即插值和擬合 插值方法要求生成的曲線通過(guò)每個(gè)給定的型值點(diǎn) 擬合方法要求生成的曲線靠近每個(gè)型值點(diǎn) 但不一定要求通過(guò)每個(gè)點(diǎn) 6 選用不同類型的插值函數(shù) 逼近的效果就不同 一般有 1 拉格朗日插值 lagrange插值 2 Hermite插值 3 三次樣條插值 4插值方法 7 已知函數(shù)y f x 在n 1個(gè)互不相同的點(diǎn)處的函數(shù)值yi f xi i 0 1 n 為求得y f x 的近似表達(dá)式 容易想到的是選擇n次多項(xiàng)式 使Pn x 滿足條件 4 1拉格朗日插值 函數(shù)y f x 稱為被插函數(shù) x0 x1 x2 xn被稱為插值節(jié)點(diǎn) 條件式被稱成為插值條件 8 插值多項(xiàng)式的幾何意義實(shí)質(zhì)上是將通過(guò)n 1個(gè)點(diǎn) xi yi i 0 1 2 n的多項(xiàng)式曲線當(dāng)作被插函數(shù)曲線y f x 的近似曲線 4 1拉格朗日插值 9 設(shè)所要構(gòu)造的插值多項(xiàng)式為 由插值條件 得到如下線性代數(shù)方程組 4 1拉格朗日插值 10 此方程組的系數(shù)行列式為 上式即為范得蒙行列式 由于插值結(jié)點(diǎn)xi互不相同 故D 0 則Pn x 可由a0 a1 an唯一確定 4 1拉格朗日插值 11 上述多項(xiàng)式插值方法需要解算方程組 而拉格朗日插值公式的基本思想是 把pn x 的構(gòu)造問(wèn)題轉(zhuǎn)化為n 1個(gè)插值基函數(shù)li x i 0 1 n 的構(gòu)造 4 1拉格朗日插值 12 構(gòu)造各個(gè)插值節(jié)點(diǎn)上的基函數(shù)li x i 0 1 n 滿足如下條件 4 1拉格朗日插值 13 求n次多項(xiàng)式lk x i 0 1 n k 0 1 n 則 i 0 1 2 n 即Pn x 滿足插值條件 4 1拉格朗日插值 14 4 1拉格朗日插值 從而得n階拉格朗日 Lagrange 插值公式 根據(jù)lk x 的表達(dá)式 xk以外所有的結(jié)點(diǎn)都是lk x 的根 15 4 1拉格朗日插值 特別地 當(dāng)n 1時(shí) 為線性插值 記 則有 滿足插值條件 16 4 1拉格朗日插值 線性插值多項(xiàng)式 P1 x 可以改寫為 故線性插值多項(xiàng)式的幾何含義就是構(gòu)造過(guò)插值節(jié)點(diǎn)的一條線段 17 4 1拉格朗日插值 當(dāng)n 2時(shí) 為拋物線插值 記 則有 滿足插值條件 18 4 1拉格朗日插值 拋物線插值多項(xiàng)式 拋物線插值多項(xiàng)式的幾何含義就是從幾何上看就是用通過(guò)三點(diǎn)拋物線函數(shù)P2 x 近似代替原始被插函數(shù)f x P2 x 19 在實(shí)際應(yīng)用中 不僅要求插值函數(shù)與被插函數(shù)在節(jié)點(diǎn)上函數(shù)值相等 而且要求若干階導(dǎo)數(shù)也相等 如機(jī)翼設(shè)計(jì)等 i 0 1 n 滿足函數(shù)值相等且導(dǎo)數(shù)也相等的插值方法稱為埃爾米特 Hermite插值 4 2埃爾米特插值 20 一般來(lái)說(shuō) 給定m 1個(gè)插值條件 就可以構(gòu)造出一個(gè)m次Hermite插值多項(xiàng)式 兩個(gè)典型的Hermite插值 三點(diǎn)三次Hermite插值 兩點(diǎn)三次Hermite插值 插值節(jié)點(diǎn) x0 x1 x2插值條件 P xi f xi i 0 1 2 P x1 f x1 插值節(jié)點(diǎn) x0 x1插值條件 P xi f xi P xi f xi i 0 1 4 2埃爾米特插值 21 插值節(jié)點(diǎn) x0 x1插值條件 P xi f xi yi P xi f xi mi i 0 1 兩點(diǎn)三次Hermite插值 模仿Lagrange多項(xiàng)式的思想 設(shè) 其中均為3次多項(xiàng)式 且滿足 i j 0 1 4 2埃爾米特插值 22 將插值條件代入立即可得 0 x 1 x 0 x 1 x 的表達(dá)式 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插值多項(xiàng)式為 4 2埃爾米特插值 25 4 2埃爾米特插值 參數(shù)連續(xù)性條件0階導(dǎo)數(shù)連續(xù)性 記作C0連續(xù) 是指兩個(gè)曲線段在公共點(diǎn)處有相同的坐標(biāo) 一階導(dǎo)數(shù)連續(xù)性 記作C1連續(xù) 指兩個(gè)相鄰曲線段在交點(diǎn)處有相同的一階導(dǎo)數(shù) 二階導(dǎo)數(shù)連續(xù)性 記作C2連續(xù) 指兩個(gè)相鄰曲線段在交點(diǎn)處有相同的一階和二階導(dǎo)數(shù) 0階幾何連續(xù)性 記為G0連續(xù) 與0階導(dǎo)數(shù)連續(xù)性相同 一階幾何連續(xù)性 記為G1連續(xù) 指一階導(dǎo)數(shù)在兩個(gè)相鄰段的交點(diǎn)處成比例 而大小不一定相等 二階幾何連續(xù)性 記為G2連續(xù) 指兩個(gè)曲線段在相交處其一階和二階導(dǎo)數(shù)均成比例 G2連續(xù)下 兩個(gè)曲線段在交點(diǎn)處的曲率相等 26 5基于插值思想的曲線生成 基于插值方法生成的曲線通過(guò)每個(gè)型值點(diǎn) 在GIS地圖制圖中一般通過(guò)插值 使得曲線變得更光滑 如等高線的光滑就常采用插值方法 常見(jiàn)的有 三點(diǎn)光滑法五點(diǎn)光滑法三次樣條光滑法 27 5 1五點(diǎn)光滑法 五點(diǎn)光滑法是等高線光滑中最常使用的方法 其光滑的結(jié)果類似于制圖員的手工光滑效果 基本思路為 每?jī)蓚€(gè)數(shù)據(jù)點(diǎn)之間建立一條三次多項(xiàng)式曲線方程 曲線具有連續(xù)的一階導(dǎo)數(shù) 各數(shù)據(jù)點(diǎn)的導(dǎo)數(shù)是以一點(diǎn)為中心 左右兩邊各相鄰的兩個(gè)點(diǎn) 一共五個(gè)點(diǎn)來(lái)確定的 28 5 1五點(diǎn)光滑法 五點(diǎn)光滑法各數(shù)據(jù)點(diǎn)的一階導(dǎo)數(shù)是由其他相鄰四個(gè)點(diǎn)求得的 圖中P1點(diǎn)的一階導(dǎo)數(shù)待求 設(shè)其值為t1 K1 K2 K3 K4分別為四個(gè)折線段Pi 2Pi 1 Pi 2Pi 1 Pi 2Pi 1 Pi 1Pi 2的斜率 29 5 1五點(diǎn)光滑法 當(dāng)?shù)雀呔€不閉合 對(duì)于第一個(gè)點(diǎn)和第二個(gè)點(diǎn)以及倒數(shù)第二個(gè)點(diǎn)及第一個(gè)點(diǎn) 采用補(bǔ)點(diǎn)的方法求一階導(dǎo)數(shù) 補(bǔ)點(diǎn)采用增量相等的原則來(lái)補(bǔ) 當(dāng)欲求P1點(diǎn)一階導(dǎo)數(shù)時(shí) 需要向前補(bǔ)充A點(diǎn) 其補(bǔ)充原則為 P2P1坐標(biāo)增量 P1P0坐標(biāo)增量 P1P0坐標(biāo)增量 P0A坐標(biāo)增量 由此可以補(bǔ)出A點(diǎn)坐標(biāo) 30 5 1五點(diǎn)光滑法 設(shè)每?jī)蓚€(gè)數(shù)據(jù)點(diǎn)的三次多項(xiàng)式為 由此可以對(duì)每一個(gè)原始等高線的折線段求出一組a b c d四個(gè)參數(shù) 構(gòu)建一個(gè)三次多項(xiàng)式 實(shí)現(xiàn)光滑 插值條件為 31 5 1五點(diǎn)光滑法 五點(diǎn)光滑法是等高線光滑中最常使用的方法 其光滑的結(jié)果類似于制圖員的手工光滑效果 基本思路為 每?jī)蓚€(gè)數(shù)據(jù)點(diǎn)之間建立一條三次多項(xiàng)式曲線方程 曲線具有連續(xù)的一階導(dǎo)數(shù) 各數(shù)據(jù)點(diǎn)的導(dǎo)數(shù)是以一點(diǎn)為中心 左右兩邊各相鄰的兩個(gè)點(diǎn) 一共五個(gè)點(diǎn)來(lái)確定的 32 能否找到一個(gè)簡(jiǎn)單易算的p x 使得f x p x 已知f x 在某些點(diǎn)的函數(shù)值 5擬合方法 33 使最小 p xi yi總體上盡可能小 使最小 常見(jiàn)做法 5擬合方法 34 對(duì)于給定的一組數(shù)據(jù) xi yi i 0 1 2 n 求m m n 次多項(xiàng)式來(lái)擬合原始函數(shù) 需要求出多項(xiàng)式的m 1個(gè)待定系數(shù)即可 且使得以下函數(shù)值達(dá)到最小 F a0 a1 am Min 5最小二乘擬合 35 要使函數(shù)值達(dá)到最小 即有多元函數(shù)求極值 即 k 0 1 n 最小值點(diǎn) 5最小二乘擬合 36 5最小二乘擬合 寫成方程組的形式 法方程組 可以證明該方程組有唯一解 37 7基于擬合思想的曲線生成 基于擬合方法生成的曲線靠近每個(gè)型值點(diǎn) 但不一定要求通過(guò)每個(gè)點(diǎn) 常見(jiàn)的主要有 Bezier曲線B樣條曲線 38 7 1Bezier曲線 Bezier曲線是由一組多邊折線定義的 在多邊折線的各頂點(diǎn)中 只有第一點(diǎn)和最后一點(diǎn)在曲線上 第一條和最后一條折線分別表示出曲線在起點(diǎn)和終點(diǎn)處切線方向 曲線的形狀趨向于多邊折線的形狀 因此 多邊折線又稱為特征多邊形 其頂點(diǎn)稱為控制點(diǎn) 39 7 1Bezier曲線 Bezier曲線的性質(zhì)端點(diǎn)性質(zhì) Bezier曲線的起點(diǎn)和終點(diǎn)同特征多邊形的起點(diǎn)和終點(diǎn)重合 Bezier曲線在端點(diǎn)處的一階導(dǎo)數(shù)只同相近的兩個(gè)控制點(diǎn)有關(guān) 其方向?yàn)閮牲c(diǎn)的連線方向 在端點(diǎn)處的二階導(dǎo)數(shù)只同相近的三個(gè)控制點(diǎn)有關(guān) 凸包性 Bezier曲線落在特征多邊形頂點(diǎn)所形成的凸包內(nèi) 幾何不變性 Bezier曲線的形狀由特征多邊形的頂點(diǎn)唯一確定 與坐標(biāo)系的選取無(wú)關(guān) 40 Bezier曲線的拼接 7 1Bezier曲線 41 7 2B樣條曲線 Bezier曲線實(shí)際上是B樣條 BasicSpline 曲線的特例 B樣條曲線除保持了Bezier曲線的直觀性和凸包性等優(yōu)點(diǎn)之外 其樣條函數(shù)中多項(xiàng)式次數(shù)也獨(dú)立于控制點(diǎn)數(shù)目 B樣條曲線還允許局部調(diào)整 由于以上原因 B樣條曲線得到了廣泛應(yīng)用 42 7 2B樣條曲線 B樣條曲線的性質(zhì)端點(diǎn)性質(zhì) B樣條曲線的起點(diǎn)和終點(diǎn)都不在曲線上 只與鄰近三個(gè)控制點(diǎn)有關(guān) 連續(xù)性 B樣條曲線段之間是自行光滑連續(xù)的 B樣條曲線段之間是自行光滑連續(xù)的 而且 n次B樣條曲線具有n 1階導(dǎo)數(shù)的連續(xù)性 局部性和擴(kuò)展性 在三次B樣條曲線中 每個(gè)B樣條曲線段受四個(gè)控制點(diǎn)影響 如果增加一個(gè)控制點(diǎn) 就相應(yīng)地增加了一段B樣條曲線 此時(shí) 原有的B樣條曲線不受影響 43 特殊外形設(shè)計(jì)三頂點(diǎn)共線位于控制多邊形邊上的一個(gè)點(diǎn) P0 P2 P1 M P 0 P 0 P0 P2 M P1 7 2B樣條曲線 44 特殊外形設(shè)計(jì)四頂點(diǎn)共線含有直線段的曲線 P0 P3 P1 P2 7 2B樣條曲線 45 B樣條曲線 9 17 特殊外形設(shè)計(jì)兩頂點(diǎn)重合 P0 P2 P1 M P 0 P0 P2 M P1 46 B樣條曲線 10 17