圖形學(xué)教案第四章曲線和曲面.ppt

第四章 曲線和曲面,第一節(jié) 曲線和曲面表示的基礎(chǔ)知識 第二節(jié) Hermite多項式 第三節(jié) Coons曲面 第四節(jié) Bezier曲線和曲面 第五節(jié) B樣條曲線和曲面,第一節(jié) 曲線和曲面表示的基礎(chǔ)知識,曲線和曲面參數(shù)表示 （1）與坐標(biāo)軸相關(guān)的，不便于進(jìn)行坐標(biāo)變換； （2）會出現(xiàn)斜率為無窮大的情況； （3）難以靈活地構(gòu)造復(fù)雜的曲線、曲面 （4）非參數(shù)的顯示方程只能描述平面曲線，空間曲線必須定義為兩張柱面的交線。 （5）假如我們使用非參數(shù)化函數(shù)，在某個xoy坐標(biāo)系里一條曲線，一些x值對應(yīng)多個y值，而一些y值對應(yīng)多個x值。,在空間曲線的參數(shù)表示中，曲線上每一點的坐標(biāo)均要表示成某個參數(shù)t的一個函數(shù)式，則曲線上每一點笛卡爾坐標(biāo)參數(shù)式是：,，,把三個方程合寫到一起，曲線上一點坐標(biāo)的矢量表示是：,關(guān)于參數(shù)t的切矢量或?qū)Ш瘮?shù)是：,曲面寫為參數(shù)方程形式為:,曲線或曲面的某一部分，可以簡單地用atb界定它的范圍,直線段 端點坐標(biāo)分別是 P1x1,y1,P2x2,y2， 直線段的參數(shù)表達(dá)式是： P(t)= P1+( P2- P1) t = (1-t)P1+ tP2 0t1； 參數(shù)表示相應(yīng)的x,y坐標(biāo)分量是： x(t)= x1+(x2-x1) t y(t)= y1+(y2-y1) t 0t1,參數(shù)方程具有如下優(yōu)點。 (1) 對參數(shù)表示的曲線、曲面可對其參數(shù)方程直接進(jìn)行幾何變換（如平移、比例、旋轉(zhuǎn)）。 (2) 便于處理斜率為無限大的問題。 (3) 有更大的自由度來控制曲線、曲面的形狀。具有很強的描述能力和豐富的表達(dá)能力。 (4) 參數(shù)方程中，代數(shù)、幾何相關(guān)和無關(guān)的變量是完全分離的，而且對變量個數(shù)不限，從而便于用戶把低維空間中的曲線、曲面擴展到高維空間去。,(5) 規(guī)格化的參數(shù)變量t0,1,使其相應(yīng)的幾何分量是有界的，而不必用另外的參數(shù)去定義其邊界。便于曲線和曲面的分段、分片描述。易于實現(xiàn)光順連接。 (6) 易于用矢量和矩陣表示幾何分量，計算處理簡便易行。,曲線和曲面可以分為兩類。一類要求通過事先給定的離散的點，稱為是插值的曲線或曲面。另一類不要求通過事先給定的各離散點，而只是用給定各離散點形成的控制多邊形來控制形狀，稱為是逼近的曲線或曲面。,基本概念,插值 要求構(gòu)造一條曲線順序通過型值點，稱為對這些型值點進(jìn)行插值（interpolation）。 逼近 構(gòu)造一條曲線，使它在某種意義上最佳逼近這些型值點，稱之為對這些型值點進(jìn)行逼近（approximation）。,參數(shù)連續(xù)性 一函數(shù)在某一點x0處具有相等的直到k階的左右導(dǎo)數(shù)，稱它在x0處是k次連續(xù)可微的，或稱它在x0處是k階連續(xù)的，記作Ck。幾何上C0、C1、C2依次表示該函數(shù)的圖形、切線方向、曲率是連續(xù)的。 幾何連續(xù)性 兩曲線段的相應(yīng)的弧長參數(shù)化在公共連接點處具有Ck連續(xù)性，則稱它們在該點處具有k階幾何連續(xù)性，記作Gk 。零階幾何連續(xù)G0與零階參數(shù)連續(xù)C0是一致的。一階幾何連續(xù)G1指一階導(dǎo)數(shù)在兩個相鄰曲線段的交點處成比例，即方向相同，大小不同。二階幾何連續(xù)G2指兩個曲線段在交點處其一階和二階導(dǎo)數(shù)均成比例。,光順 光順（smoothness）是指曲線的拐點不能太多，要光滑順暢。對于平面曲線相對光順的條件應(yīng)該是：（1）具有二階幾何連續(xù)（G2）；（2）不存在多余拐點和奇異點；（3）曲率變化較小。,拉格朗日n階多項式： 令P0(x0,y0),Pn(xn,yn)表示n+1個數(shù)據(jù)點，t0,t1,t2為任意數(shù)字，其拉格朗日n階多項式如下： 對任意j i ,有Li(xi)=1且Lj(xj)=0,拉格朗日插值： 令P0(x0,y0),Pn(xn,yn)表示n+1個數(shù)據(jù)點，希望找出通過這些點的曲線。 這里： Li(xi)是拉格朗日多項式， L(x)是插值各數(shù)據(jù)點的第n階拉格朗日多項式,第二節(jié) Hermite多項式,已知函數(shù)f(t)在k+1個點ti處的函數(shù)值和導(dǎo)數(shù)值f (j)(ti)，i=0,1,k，j=0,1,mi-1，要求確定一個N = m0 + m1 + + mk - 1次的多項式P(t)，滿足下面的插值條件：,考查k=1，m0 = m1 = 2的情形。 已知表示一條曲線的某個函數(shù)f(t)在兩點t0，t1的函數(shù)值f(t0), f(t1)和一階導(dǎo)數(shù)值f(t0), f(t1)，求三次多項式P(t):,把a0，a1，a2和a3代入則有：,經(jīng)整理，所求多項式P 0(t)可以寫出如下：,式中選取兩個端點及其及其切向量作為曲線構(gòu)造條件 混合函數(shù)如下：,設(shè)表示一條曲線的某個函數(shù)f(t)在四點t0，t1，t2，t3的函數(shù)值f(t0), f(t1),f(t2), f(t3)，根據(jù)Lagrange插值法，則三次多項式P(t)可表示為：,選擇四個不同的點作為構(gòu)造曲線的條件,混合函數(shù)如下：,經(jīng)驗證可知：,為了使P0(t)的定義區(qū)間t0tt1變?yōu)閰^(qū)間0u1，可以做如下變換,解出 ，代入混合函數(shù)式中，得：,將關(guān)于u的混合函數(shù)代入，所求的三次多項式成為：,令,得,對一般的Hermite插值問題，一般來說得到的插值多項式次數(shù)較高，應(yīng)用起來不方便。通常的處理辦法是將前面給出的參數(shù)的三次多項式逐段光滑地連接，如此來確定一般情況下的插值多項式。 將前面t0和t1視為ti和ti+1，設(shè)給定f(ti)，f(ti+1)，f(ti)，f(ti+1)，則在區(qū)間ti，ti+1的Hermite三次插值多項式Pi(t)是：,為了完整地寫出這個插值多項式，可以在區(qū)間ti，ti+1中引入如下一些基本函數(shù)：,完整的插值多項式可寫為：,上式區(qū)間t0，tn中有定義，且為分段定義。在每個區(qū)間 ti，ti+1上，都恰有四項。滿足插值條件,每段曲線Pi(t)只在ti，ti+1中有定義：,自變量的線性變換,用逆變換 代入，將所得關(guān)于u的多項式記為 ，得,其中 = =,設(shè)在平面上有兩點P0，Pl，它們的位置向量分別為(1，1)，(4，2)，在P0的導(dǎo)數(shù)值即在該點的切線向量P0 =(1，1)，在Pl處P1 =(1，-1),第三節(jié) Coons曲面,uw表示了曲面片的方程 0w，1w，u0，u1表示四條邊界曲線 u0u表示在邊界線u0上的點沿u向的一階偏導(dǎo)數(shù)向量，稱邊界線的切向量 u0w表示邊界線u0上的點沿w向的一階偏導(dǎo)數(shù)向量，稱邊界線的跨界切向量。 uwuu ，uwuw，uwww分別表示曲面片uw關(guān)于u和w的二階偏導(dǎo)數(shù)向量，于是u0uu表示邊界線u0上的二階切向量，u0ww表示邊界線u0上的二階跨界切向量。,uwuw為曲面片P在點(u,w)處的扭曲向量。特別，用00，01，10，11分別表示曲面片四個角點時，00uw，01uw，10uw，11uw就分別表示在四個角點的扭曲向量。,構(gòu)造具有指定邊界曲線的曲面片 Coons給出的一個解法是：尋找兩個混合函數(shù)f0(t)和f1(t)，它們是連續(xù)的，并且滿足f0(0)=1，f0(1)=0，f1(0)=0，f1(1)=1，且f0(t)+f1(t)=1，0t1。 利用這樣的混合函數(shù)，通過四條邊界構(gòu)造曲面片，并通過疊加修正曲面片，產(chǎn)生滿足用戶需要的曲面。,若給定四條邊界曲線u0，u1，0w，1w，且0u1，0w1 在u向進(jìn)行線性插值，得到直紋面為：,在w向進(jìn)行線性插值，得到直紋面為：,若把這兩張直紋面疊加可得到一張新曲面Ps(u,w)：,Ps(u,w)上的任意一點，其位移矢量包含兩個部分，一部分是由于線性插值而產(chǎn)生的位移，另一部分是由于邊界曲線而產(chǎn)生的位移。,為消除Ps(u,w)中由于線性插值而產(chǎn)生的位移，需要構(gòu)造一個新的曲面P3(u,w),構(gòu)造曲面P3(u,w)后，從Ps(u,w)中去除P3(u,w)，即去除線性插值的成分，則得到Coons構(gòu)造曲面 P(u,w)= Ps(u,w) -P3(u,w) =P1(u,w)+ P2(u,w)- P3(u,w) 可寫成如下形式：,其中矩陣M是：,矩陣中四個元素是四個角點的位置向量，可用已知四條邊界曲線計算求出。 u0，u1可以是關(guān)于u的三次多項式，0w，1w可以是關(guān)于w的三次多項式，混合函數(shù)也是不超過三次的關(guān)于u或w的三次多項式，這時公式關(guān)于u看，或關(guān)于w看，都是三次多項式，是關(guān)于u或w的雙三次多項式,不難驗證它們符合所提問題的要求，例如我們來驗證0w是它的一條邊界線，這只要把u=0代入公式右端，得,曲面片以指定的曲線為其邊界曲線，且有指定的跨界切向量 。 利用本章第二節(jié)定義的四個混合函數(shù)q00(t), q01(t), q10(t), q11(t)。這四個函數(shù)均是三次多項式 ，連續(xù)可微，并且還滿足下面的條件：,設(shè)已經(jīng)給定四條邊界曲線u0，u1，0w，1w及沿這四條邊界曲線的跨界切向量u0w，u1w，0wu，1wu。 這時可以計算求得四個角點的位置向量00，01，10，11，切向量00w，01w，10w，11w，00u，01u，10u，11u，以及扭曲向量00uw，01uw，10uw，11uw，可以寫出符合要求曲面片的數(shù)學(xué)表達(dá)式如下：,容易地驗證所寫出的公式滿足要求，例如以u=0代入該式右端，得：,曲面片沿邊界線取給定的各跨界切向量，可先對該式關(guān)于某一變量求導(dǎo)，例如對u求導(dǎo)，然后再代入u=0，這時有,指定四個角點以及在這些點上的切向量和扭曲向量后，求解曲面的表達(dá)式。 已知角點位置向量00，10以及在這兩點關(guān)于u的切向量00u和01u，可以用Hermite插值公式來指定一條u邊界線：,將上兩式代入前式，就可以得到：,給出四個角點以及在該角點上的切向量和扭曲向量來構(gòu)造Coons曲面表達(dá)式。設(shè)在平面上有四點P0，Pl，P2，P3，它們的位置向量分別為(0，0，0)，(0，0.75，0)，(0.75，0，0)，(0.75，0.75，0)。該四點的切向量、跨界切向量和扭曲向量，定義在關(guān)于角點的信息矩陣M中：,第四節(jié) Bezier曲線和曲面,Bezier曲線 給出型值點P0，P1，Pn，它們所確定的n次Bezier曲線是：,涉及到的0!及00，按約定均為1。 在n=1時,公式成為：,在n=2時，公式成為：,在n=3時，公式成為：,Bezier曲線的一些重要性質(zhì),P(0)= P0，P(1)= P1，曲線通過所給出型值點列的起點和終點。,Bezier曲線的對稱性,曲線的凸包性 對給定的型值點P0，P1，Pn點集,分段的三次Bezier曲線光滑連接,設(shè)給出兩個Bezier多邊形P0P1P2P3和Q0QlQ2Q3，顯然，使所決定的兩條Bezier曲線在連接點處連續(xù)的條件是P3=Q0。 Bezier曲線在連接點處G1連續(xù)，即一階導(dǎo)數(shù)幾何連續(xù)，就要求Q0=aP3，這里a應(yīng)該是一個正數(shù)。由前面的公式，知Q0=3(Q1Q0)，P3=3(P3P2)，因此可知使在連接點處G1連續(xù)的條件是：,由此得,連接點處達(dá)到C2連續(xù)，即二階導(dǎo)數(shù)參數(shù)連續(xù)的條件 對前面的公式求兩次導(dǎo)數(shù)，可得，,于是知， 要求， 即 ，注意到Q0=P3，由此得：,繪制Bezier曲線時，可以利用其定義式，對參數(shù)t選取足夠多的值，計算曲線上的一些點，然后用折線連接來近似畫出實際的曲線。隨著選取點增多，折線和曲線可以任意接近。 假設(shè)給定的四個型值點是P0=(1，1)，Pl=(2，3)，P2=(4，3)， P3=(3，1)，則計算結(jié)果見表,繪制Bezier曲線的方法,幾何作圖法 分裂法,記點Pk，Pk+l，Pl可以生成的Bezier曲線為Pk,l(t)，0t1，則成立下面的遞推關(guān)系：,證明上式，要用到組合等式：,void bez_to_points(int n,int npoints,double P,double points) / P為控制點坐標(biāo) points為采用幾何作圖算法生成的Bezier曲線上的離散點序列 離散點序列points的個數(shù)為npoints 控制點P的個數(shù)為n +1 double t,delt; delt=1.0/(double)npoints;/將參數(shù)t npoints等分 t=0.0; for(int i=0;i=npoints;i+) pointsi=decas(n, P, t); /分別求出npoints+1個離散點points的坐標(biāo) t+=delt; ,double decas(int n,double P,double t) int m,i; double *R, *Q, P0; R = new doublen +1; Q = new doublen +1; for(i=0;i0;m-) ,/n次Bezier曲線在點t的值，可由兩條n-1次Bezier曲線 /在點t的值通過線性組合而求得。 Qi= R i+t*( R i+1- R i); for(i=0;i= m -1;i+) Ri= Q i; P0=R0; delete R; delete Q; return (P0); ,設(shè)給出四點的坐標(biāo)是(1，1)，(2，3)，(4，3)，(3，1)，求所確定三次Bezier曲線在t=1/3時的值P(1/3)，算法的計算過程,Bezier幾何作圖算法計算過程,設(shè)控制點序列P0，P1，Pn確定的n次Bezier曲線是P(t)，用如下遞歸方式計算另一組點集：,如果令Pa(s)和Pb(s)分別是以控制點序列 和 確定的Bezier曲線，其中0s1，那么就有：,己知四點P0，P1，P2，P3，確定了一條三次Bezier曲線P(t)，可寫出下式，,分裂法中的遞歸計算,分裂法的示意圖,可通過計算驗證Bezier曲線由前后兩段構(gòu)成?，F(xiàn)以P0的系數(shù)為例，驗證兩端它的系數(shù)是相等的。 左端顯然就是 。先看右端。若0t ，這時就用前半段的表達(dá)式，觀察分裂計算圖注意到 中有1份P0， 中有 份， 中是 份， 中是 份，因此全部P0的系數(shù)是：,右端對 t1，注意到僅 中有 份的P0，知P0的系數(shù)是：,設(shè)己知三次Bezier曲線P(t)的控制頂點是P0，P1，P2，P3，在P( )處將曲線分為兩段，求出前半段的控制頂點Q0，Ql，Q2，Q3和后半段的控制頂點R0，R1，R2，R3，。有算法如下,void split_Bezier(Point P) Point R4,Q4; int i,j; for(i=0;i=3;i+) Ri=Pi;,for(i=0;i=2;i+) Qi=R0; for(j=0;j=2-i;j+) Rj.x=(Rj.x+Rj+1.x)/2; /分別對相鄰兩控制點間的線段進(jìn)行分裂 Rj.y=(Rj.y+Rj+1.y)/2; Q3=R0; ,分裂算法的計算,根據(jù)Bezier曲線的凸包性質(zhì)，知道曲線上任意一點到線段P0P3的距離，小于P1和P2到線段P0P3距離中的較大者，即有：,任意事先給定的對畫出曲線近似程度的要求0，可以取max(d(P1，P0P3)，d(P2，P0P3)為分裂停止的條件。,void new_split_Bezier(Point P) Point R4,Q4; int i,j; const double epsilon=0.01; if(maxdistance(P)epsilon) /*maxdistance(P) 為求max(d(P1,P0P3)，d(P2,P0P3)的函數(shù)*/, MoveTo(P0.x,P0.y); LineTo(P3.x,P3.y); else for(i=0;i=3;i+) Ri=Pi; for(i=0;i=2;i+) Qi=R0; for(j=0;j=2-i;j+) Rj.x=(Rj.x+Rj+1.x)/2; Rj.y=(Rj.y+Rj+1.y)/2; Q3=R0; new_split_Bezier(Q); new_split_Bezier(R); ,有理Bezier曲線,圖中h0=h1= h3=1，當(dāng)h2=0、1/2、1、2、4時曲線逐漸地靠近P2點,Bezier曲面,若在空間給定(m+1)(n十1)個控制點，Vij，i=0，1，m，j=0，1，n，令,上式曲面為mn次的Bezier曲面,當(dāng)m=n=1，公式成為：,設(shè)v00，v01，v10，v11四點依次是(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)，則可得P1,1(u，w)的坐標(biāo)形式的參數(shù)方程為：,消去參數(shù)，就得馬鞍面方程：,當(dāng)m=n=3，曲面成為：,設(shè)同一個曲面片，用Coons曲面形式確定它，又用Bezier形式確定它，現(xiàn)在來考查、矩陣M與矩陣B有什么關(guān)系。,求解上式得：,四個角點00，0l，10和11分別對應(yīng)控制點V00，V03，V30和V33，這是很自然的。關(guān)于切向量，例如00w=3(V01-V00)，表明00w，是沿從V00到V01邊的方向，大小是兩個位置向量差的3倍，其余切向量是類似的。,00uw，有：,00uw還可以寫做：,雙三次Coons曲面與Bezier曲面間的關(guān)系,第五節(jié) B樣條曲線和曲面,B樣條曲線 給定n+1個控制點P0，P1，Pn，它們所確定的k階B樣條曲線是：,其中Ni，k(u)遞歸定義如下：,這里u0，u1，un+k，是一個非遞減的序列，稱為節(jié)點，(u0，u1，un+k)稱為節(jié)點向量。定義中可能出現(xiàn) ，這時約定為0。,選取，n=2，k=1，控制頂點是P0，P1，P2，這樣應(yīng)選擇參數(shù)節(jié)點n+k+1=4個，設(shè)節(jié)點向量是(u0，u1，u2，u3)，按式定義，可寫出三個基函數(shù)：,由公式可知所定義的B樣條曲線是,選取n=3，k=2，于是有四個控制頂點P0，P1，P2，P3，應(yīng)有參數(shù)節(jié)點n+k+1=6個，設(shè)節(jié)點向量是(0，0，1，2，3，3)，試畫出所確定的2階B樣條曲線。 取u=0.5，進(jìn)行計算。因為0.50，1=u1，u2，因此N1,1(0.5)=1，而其它的Ni,1(0.5)=0，i1。往下公式做遞歸計算。,N2,2(0.5)和N3,2(0.5)，不必計算，因為計算它們需要的i2時的Ni,1(0.5)=0，所以知N2,2(0.5)=N3,2(0.5)=0。這樣代入公式計算P(0.5)，有：,再取u其它一些值進(jìn)行計算，結(jié)果如表所示。,選取n=3，k=4，平面上四個控制頂點P0，P1，P2，P3的坐標(biāo)依次是(1，1)，(2，3),(4，3)，(3，1)，這時應(yīng)取參數(shù)節(jié)點n+k+1=8個，設(shè)選取節(jié)點向量為(0，0，0，0，1，1，1，1)，畫出所確定的4階B樣條曲線。 計算N1,4(0.5) ，其中0.50，1=u3，u4,N3,1(0.5)=1，而對i3，Ni,1(0.5)=0。,用類似的過程可計算求出：,曲線上對應(yīng)參數(shù)u=0.5的點是：,可以證明更一般的結(jié)論，即，n+1個控制點P0，P1，Pn所確定的最高階的B樣條曲線是k=n+1階的，這時由節(jié)點向量(0，0，0，1，1，1)所確定的B樣條曲線，與該n+1個控制點所確定的Bezier曲線相同。 在參數(shù)節(jié)點的眾多選取方法中，最多使用的是選擇參數(shù)u的每一區(qū)間為等長的情況，這時所得到的B樣條函數(shù)稱為是等距的，或均勻的。以下我們轉(zhuǎn)入討論等距的B樣條曲線?？紤]使用較多的情況，可假定ui=i,i=0