第五章1圖形顯示算法基礎(chǔ)

13.1直線的生成算法3.1.1基本知識(shí)

只有畫水平線,垂直線,及正方形對(duì)角線時(shí),象素點(diǎn)集的位置才是準(zhǔn)確的。顯示一條直線,實(shí)際上是用最靠近這條直線的象素點(diǎn)集來(lái)近似地表示這條直線.有限的象素矩陣畫點(diǎn)設(shè)備光柵顯示器:

緩沖存儲(chǔ)器，顯示控制器，數(shù)/模轉(zhuǎn)換器，陰級(jí)射線管（CRT）A(x1,y1)、B(x2,y2)、在紙上畫一條直線和在計(jì)算機(jī)屏幕上畫一條直線有什么本質(zhì)的區(qū)別? 2生成直線的一般要求是：1.DDA算法（數(shù)值微分法）2.直線的Bresenham算法

確定象素最佳逼近某圖形的過(guò)程通常稱為光柵化。圖形生成算法的工作:在顯示器所給定的有限個(gè)象素組成的矩陣中,確定最佳逼近于圖形的象素點(diǎn)集.1.象素是均勻分布的2.所畫的線應(yīng)是直的，且有精確的起點(diǎn)和終點(diǎn)4.最后直線的生成速度要快3.所顯示的亮度應(yīng)沿直線不變，且與直線的長(zhǎng)度和方向無(wú)關(guān)。3.1.2直線光柵化的方法3已知端點(diǎn)A(x1,y1)、B(x2,y2),直線的微分方程：dy/dx=(y2-y1)/(x2-x1)=常數(shù)=m

yi+1＝y(tǒng)i+(y2-y1)/(x2-x1)*Δx=yi+m*Δx

yi=mxi+Byi+1=mxi+1+B=m(xi+Δx)+BA(x1,y1)B(x2,y2)Pi(xi,yi)Pi+1(xi+1,yi+1)dy=k·dxdx3.1.3

DDA算法(DigitalDifferentialAlgorithm)通過(guò)同時(shí)對(duì)x,y各增加一個(gè)小的增量,計(jì)算下一步的x,y值。在一個(gè)迭代算法中,如果每一步的x,y值是用前一步的值加上一個(gè)增量來(lái)獲得,那么這種算法稱為增量算法。4光柵中Δx=1直線的遞推公式

yi+1＝y(tǒng)i+(y2-y1)/(x2-x1)xi+1＝xi+1doublex=x1,y=y1;m=(y2-y1)/(x2-x1);intk=abs(x2-x1);for(inti=0;i<k;i++){x=x+1;y=y+m;}

如果x2>x1≥0,y2>y1≥05oxyk>1討論:oxyk<1xi+1=xi+1yi+1=yi+kyi+1=yi+1xi+1=xi+1/k(xi,yi)(xi+1,yi+1)(xi,yi)(xi+1,yi+1)因而造成隔行顯示解決辦法:將y看作自變量6結(jié)論：第一象限的直線DDA算法：(round(xi+1),yi+1)yi+1=yi+1xi+1=xi+1/kk>1(xi+1,round(yi+1)）xi+1=xi+1yi+1=yi+kk<1逼近直線的象素點(diǎn)的坐標(biāo)直線上點(diǎn)的坐標(biāo)遞推公式直線的斜率起點(diǎn)（x1,y1），終點(diǎn)（x2,y2）(x2>x1,y2>y1)以（x1,y1）為起點(diǎn)7DDA算法的優(yōu)、缺點(diǎn)

DDA算法的本質(zhì):效率低,不利于硬件實(shí)現(xiàn)直觀可行

DDA算法也是一個(gè)增量算法。缺陷:做除法;須采用浮點(diǎn)數(shù)據(jù)計(jì)算要取整數(shù)->算法效率不高算法程序?qū)崿F(xiàn)k=abs(x2-x1);if(abs(y2-y1)>k)doubledeltx=(x2-x1)/k;doubledelty=(y2-y1)/k;for(inti=0;i<=k;i++){x+=deltx;//x=x+deltx;y+=delty;//y=y+delty;}k=abs(y2-y1);

putpixel((int)x,(int)y,2);用數(shù)值方法解微分方程(數(shù)值微分法)81.問(wèn)題的提出2.基本思想a.效率的意義b.希望找到一個(gè)簡(jiǎn)單的判決條件,迅速確定直線上的點(diǎn)。借助于一個(gè)決策變量d的正負(fù)符號(hào),來(lái)確定下一個(gè)該點(diǎn)亮的象素點(diǎn)。最逼近Pi+1點(diǎn)的象素點(diǎn)是Ti+1點(diǎn)還是Si+1點(diǎn)？由ti+1與si+1二者的相對(duì)大小決定。若ti+1<si+1,則取Ti點(diǎn)(xi+1,yi+1)若ti+1>si+1,則取Si點(diǎn)(xi+1,yi)ti+1與si+1二者的大小可以由si+1-ti+1的正負(fù)來(lái)判定。stTiSi(r,q)3.1.4直線的Bresenham算法9為討論方便,假定:直線斜率k在0,1之間起點(diǎn)坐標(biāo)A(x1,y1)終點(diǎn)坐標(biāo)B(x2,y2)將直線平移到原點(diǎn)則起點(diǎn)坐標(biāo)（0，0),終點(diǎn)坐標(biāo)B(dx,dy)dx=x2-x1dy=y2-y1其中直線方程為：且其中r=xi-1,q=yi-1stTiSi(r,q)所以定義di=dx(s-t)為決策變量10經(jīng)推導(dǎo)di+1=di+2dy-2dx*(yi-yi-1)如果1)當(dāng)di0，即s-t0,st,則點(diǎn)亮Ti，2)當(dāng)di0，即s-t0,s<t,則點(diǎn)亮Si，di+1=di+2(dy-dx)下一個(gè)決策變量stTiSi(r,q)下一個(gè)決策變量yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1+1;di+1=di+2dy起點(diǎn)為(0,0)時(shí),初始值d1=2dy-dx11x=0,y=0,dx=5,dy=4決策變量的初值d0=2*x*dx-2*y*dy+2*dy-dx＝3點(diǎn)亮點(diǎn)（0，0）d1=d0+2(dy-dx)＝3＋2*(4-5)=1>=0點(diǎn)亮點(diǎn)（1，1）點(diǎn)亮點(diǎn)（2，1）d3=d2+2dy＝-1＋2*4=7>=0d2=d1+2(dy-dx)＝1＋2*(4-5)=-1<=0點(diǎn)亮點(diǎn)（3，2）d3=d2+2(dy-dx)＝7＋2*(4-5)=5>=0點(diǎn)亮點(diǎn)（4，3）d4=d3+2(dy-dx)＝5＋2*(4-5)=3>=0點(diǎn)亮點(diǎn)（5，4）舉例:從點(diǎn)A(0,0)到B(5,4)畫一直線.di0di0yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1+1;12一個(gè)完整的直線算法應(yīng)考慮以下幾個(gè)方面1.水平線2.垂直線4.直線的斜率為m,|m|>15.|m|<16.Δy<07.Δx<0等3.45

線Bresenhanm算法的優(yōu)點(diǎn)：(3)只有加法和乘2運(yùn)算,在計(jì)算機(jī)內(nèi)部是用位移操作實(shí)現(xiàn)的,效率高。因此，Bresenhanm算法的運(yùn)算速度很快，并適于用硬件實(shí)現(xiàn)。(1)不必計(jì)算直線的斜率，因此不必作除法；(2)不用浮點(diǎn)數(shù)，只用整數(shù)；13開始x=x1;y=y1;dx=abs(x2-x1);dy=abs(y2-y1);s1=sign(x2-x1);s2=sign(y2-y1);T=dxdx=dydy=Tinter=1x>yInter=0d=2(x*dx-y*dy)+2*dy-dxi=1;putpixel(x,y,color)d>0YNYNd>0x=x+s1y=y+s2d=d+2(dy-dx)inter=1x=x+s1d=d+2*dyy=y+s2i=i+1YYNN14voidline(intx1,inty1,intx2,inty2,intc)/*參數(shù)c為直線的顏色*/{intdx,dy,x,y,d,const1,const2,,tmp;ints1,s2,inter;dx=abs(x2-x1);dy=abs(y2-y1);if(x2>x1)s1=1;elses1=-1;if(y2>y1)s2=1;elses2=-1;if(dy>dx){tmp=dx;dx=dy;dy=tmp;inter=1;}elseinter=-1;d=2*dy-dx;const1=2*dy;/*注意此時(shí)誤差的*/const2=2*(dy-dx);/*變化參數(shù)取值.*/x=x1;y=y1;putpixel(x,y,c);for(i=1;i<dx;i++){if(d>=0){y+=s2;x+=s1;d+=const2;}else{if(inter==1)y+=s2;elsex+=s1;d+=const2;}putpiexl(x,y,c);}}15生成直線算法的進(jìn)一步改進(jìn)

1987年有人提出二步法，即沒循環(huán)一次不是繪制一個(gè)象素，而是繪制二個(gè)象素，這樣無(wú)疑可以把生成直線的速度提高一倍。只可能出現(xiàn)的四種情況ABCD同樣，我們先考慮當(dāng)直線的斜率m屬于區(qū)間[0，1]時(shí)，在x方向每增加兩個(gè)單元163.2.1

圓弧的掃描法已知圓的圓心坐標(biāo)為（xc,yc），半徑為R圓的直角坐標(biāo)方程表示為(x-xc)2+(y-yc)2=R2x0=xc-Ry0=ycxi+1=xi+1yi+1(xi+1,Round(yi+1))缺點(diǎn):

(1)運(yùn)算速度慢

(2)顯示質(zhì)量不好(xc,yc)(xc-R,yc)角度DDA算法圓弧的掃描法正負(fù)法、圓弧的Bresenham算法、T-N方法等3.2圓弧的生成算法17由圓的參數(shù)方程推導(dǎo)出圓弧的增量算法的表達(dá)式:缺點(diǎn)：所產(chǎn)生的圓是不封閉的，且該圓的半徑有不斷增大的趨勢(shì)。取微分令x0=Ry0=0起點(diǎn)(x0,y0)=0～2

,為所畫圓弧的圓心角單位為弧度d＝2-m

——角度增量，m為整數(shù)。已知圓的圓心坐標(biāo)為（0,0），半徑為R(0,0)(R,0)3.2.2角度DDA算法(近似法)18PiPi+1原因：

Pi+1是在Pi上加一個(gè)小的矢量而得到，這個(gè)矢量垂直于位置矢量Pi。因此新的半徑經(jīng)常比前一個(gè)半徑大，從而得到的曲線是一條螺線。將第二式中的xi用xi+1

代替,則有:yi+1=yi+xi+1d=yi+(xi-yid)d=d

xi+(1-d

2)yixi+1=xi-yid

為橢圓

d＝2-m，當(dāng)m=4時(shí)，此橢圓與精確圓之間的誤差E＝1.6％3.2.3橢圓差分法192024/9/9

–hjy-19dPi+1PiOXY1pixel=Rsind

d=arcsin-11/R令：3.2.4旋轉(zhuǎn)法20xy(xc,yc)方程若F(x,y)<0點(diǎn)(x,y)在圓內(nèi)若F(x,y)>0點(diǎn)(x,y)在圓外若F(x,y)=0點(diǎn)(x,y)在圓上2.F(x,y)=0是二階光滑F(xiàn)－F＋F＋F－1.F(x,y)=0劃分平面域?yàn)?個(gè)點(diǎn)集函數(shù)的特點(diǎn)：F＋F－圓的方程為：3.每一個(gè)點(diǎn)的曲率半徑>步長(zhǎng)(1pixel)3.2.5正負(fù)法（隱函數(shù)曲線)21(0,R)若點(diǎn)Pi在圓內(nèi)或圓上，即F(xi,yi)≤0若點(diǎn)Pi在圓外，即F(xi,yi)＞0以第一個(gè)1/4圓弧為例，取圓弧的最上方點(diǎn)為起始點(diǎn)(x0,y0)，x0=0y0=R點(diǎn)Pi+1取R點(diǎn)，即xi+1=xi+1,yi+1=yi點(diǎn)Pi+1取B點(diǎn)，即xi+1=xi,yi+1=yi-1由當(dāng)前點(diǎn)Pi(xi,yi)選擇下一點(diǎn)Pi+1(xi+1,yi+1)的規(guī)則是：xyo22則當(dāng)xi+1=xi+1,yi+1=yi時(shí)，當(dāng)xi+1=xi,yi+1=yi-1時(shí)，23結(jié)論——第一個(gè)1/4圓弧的正負(fù)法算法：若F(xi,yi)≤0（點(diǎn)在內(nèi)側(cè)，下一點(diǎn)選外側(cè)）若F(xi,yi)＞0（點(diǎn)在外側(cè)，下一點(diǎn)選內(nèi)側(cè)）xi+1=xi+1,yi+1=yixi+1=xi,yi+1=yi-1已知圓心坐標(biāo)為（xc,yc），半徑為R，起始點(diǎn)(x0,y0)x0=xcy0=yc+R以坐標(biāo)原點(diǎn)為圓心的第一象限1/4圓為例XYOV(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)(0,R)(R,0)起點(diǎn)為(0,R)，按順時(shí)針方向生成圓則y為x的單調(diào)遞減函數(shù)設(shè)P(xi,yi)點(diǎn)為當(dāng)前點(diǎn)圓上的亮點(diǎn)下一個(gè)該顯示的象素有三種可能:右方象素H、右下方D、下方象素V決定一象素使其與真正圓的距離的平方最小222)1(RyxmiiV--+=222)1()1(RyxmiiD--++=222)1(RyxmiiH-++=圓在與點(diǎn)P(xi,yi)附近光柵網(wǎng)格的相交關(guān)系只有5種123451.基本思想3.2.6圓弧的Bresenham算法25五種情況分解圖：H,D,V全在圓內(nèi)H在圓外，D,V在圓內(nèi)D在圓上，H在圓外，V在圓內(nèi)D,H在圓外，V在圓內(nèi)D,V,H全在圓外3HDV5HDV4HDV2DVHV(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123451HDV取D點(diǎn)取H點(diǎn)或D點(diǎn)取D點(diǎn)或V點(diǎn)取H點(diǎn)取V點(diǎn)首先計(jì)算圓心到右下角象素D的距離平方與圓心到圓弧上的點(diǎn)的距離平方之差如果Δi<0,說(shuō)明D點(diǎn)在圓內(nèi),只能是1,2情況，可選D點(diǎn)或H點(diǎn)設(shè)為圓到象素H的距離平方與圓到象素D的距離平方之差。

＝|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|MhMd如果

<0,說(shuō)明圓到D點(diǎn)的距離大于圓到H點(diǎn)的距離，應(yīng)選H(xi+1,yi)如果

>0,應(yīng)選D(xi+1,yi-1)如果

=0,規(guī)定選D(xi+1,yi-1)V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123對(duì)于情況2，左下角D總是位于圓內(nèi)，而H點(diǎn)總是位于圓外(xi+1)2+(yi-1)2-R2<0=2(Δi+yi)-1對(duì)于情況1,由于y為一單調(diào)遞減函數(shù)，只能選取H點(diǎn)因?yàn)椋?xi+1)2+(yi)2-R2<0(xi+1)2+(yi-1)2-R2<0=(yi-1)2-(yi)2<0結(jié)論與情況2是一致的所以有：(xi+1)2+(yi)2-R2>=0V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123

＝|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|如果Δi>0,說(shuō)明D點(diǎn)在圓外,只能是4,5情況，可選V點(diǎn)或D點(diǎn)設(shè)‘為圓到象素D的距離平方與圓到象素V的距離平方之差?！絴(xi+1)2+(yi-1)2-R2|-|(xi)2+(yi-1)2-R2|如果‘<0,說(shuō)明圓到V點(diǎn)的距離大應(yīng)選D(xi+1,yi-1)如果‘>0,如果‘=0,規(guī)定選D(xi+1,yi-1)說(shuō)明圓到D點(diǎn)的距離大應(yīng)選V(xi,yi-1)情況4:由于D在圓外，而V在圓內(nèi):

(xi+1)2+(yi-1)2-R2>=0(xi)2+(yi-1)2-R2<0‘=2(Δi－xi)-1對(duì)于情況5,由于y為一單調(diào)遞減函數(shù)，只能選取V點(diǎn)‘=(xi+1)2-(xi)2>0結(jié)論與情況4是一致的對(duì)于情況3,應(yīng)選D點(diǎn)V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)45歸納總結(jié)：當(dāng)Δi<0時(shí)，<=0,取H(xi+1,yi)點(diǎn)>0,取D(xi+1,yi-1)點(diǎn)當(dāng)Δi>0時(shí)，‘<=0,取D(xi+1,yi-1)點(diǎn)‘>0,取V(xi,yi-1)點(diǎn)當(dāng)Δi=0時(shí)，取D(xi+1,yi-1)點(diǎn)V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)30水平移動(dòng)到H(xi+1,yi)點(diǎn)Xi+1=xi+1yi+1=yiΔi+1=(xi+1+1)2+(yi+1-1)2-R2＝(xi+1)2+(yi-1)2-R2＝Δi+2xi+1+1對(duì)角移動(dòng)到D點(diǎn)Xi+1=xi+1yi+1=yi-1Δi+1=Δi+2xi+1-2yi+1+2移動(dòng)到V點(diǎn)Xi+1=xiyi+1=yi-1Δi+1=Δi-2yi+1+1V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)

圓弧的Bresenham算法的優(yōu)點(diǎn):起點(diǎn)和終點(diǎn)準(zhǔn)確，分布均勻，計(jì)算簡(jiǎn)單。由上面的分析,增量算法的遞推公式:31畫圓心為(0,0),半徑R=8的四分之一的圓弧初始條件:x1=0;y1=8;R=8

1=(x1+1)2+(y1-1)2-R2=1+49-64=-14<0;

HD=2(1+y1)-1=2(-14+8)-1=-13<0取H點(diǎn)

2=

1+2x2+1=-14+2*1+1=-11<0

HD=2(2+y2)-1

=2(-11+8)-1=-7<0

HD=2(3+y3)-1

=2(-6+8)-1=3>0取D點(diǎn)取H點(diǎn)點(diǎn)亮點(diǎn)(0,8)可能點(diǎn)亮H或D點(diǎn)x2=1y2=8

3=

2+2x3+1=-11+2*2+1=-6<0x3=2y3=8x4=3y4=7Δ4=Δ3+2x4-2y4+2=-6+2*3-2*7+2=-12<0

HD=2(3+y4)-1

=2(-12+7)-1=-11<0取H點(diǎn)x4=4y4=7Δ5=Δ4+2x5+1=-12+2*4+1=-3<0

HD=2(4+y4)-1=2(-3+7)-1=9>0取D點(diǎn)x5=5y5=6Δ6=Δ5+2x5-2y5+2=-3+2*5-2*6+2=-3<0

HD=2(6+y6)-1=2(-3+6)-1=5>0取D點(diǎn)x6=6y6=5V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)Δ7=Δ6+2x6-2y6+2=-3+2*6-2*5+2=1>0取D點(diǎn)x7=7y7=4

DV=2(6-x6)-1=2(1-6)-1=-11<0Δ8=Δ7+2x7-2y7+2=1+2*7-2*4+2=9>0

DV=2(7-x7)-1=2(9-7)-1=3>0取V點(diǎn)x8=7y8=3Δ9=Δ8

-2y8+1=9-2*3+1=4>0

DV=2(9-x8)-1=2(4-7)-1=-7<0取D點(diǎn)x9=8y9=2Δ10=Δ9+2x9-2y9+2=4+2*8-2*2+2=18>0

DV=2(10-x9)-1=2(18-8)-1=19>0取V點(diǎn)x10=8y10=1Δ11=Δ10

-2y10+1=19-2*2+1=16>0

DV=2(11-x10)-1=2(16-8)-1=15>0取V點(diǎn)x11=8y11=033Yy>=0YN結(jié)束起點(diǎn)x=0y=RΔD<0NYNΔD>0YNYN1/4圓程序流程圖34上機(jī)：

1.編制圓弧正負(fù)法的算法程序；（下次上機(jī)時(shí)提交）

2.讀懂并上機(jī)調(diào)試、運(yùn)行圓弧的Bresenham算法程序；手工：畫圓心為(0,0),半徑R=10的四分之一的圓弧用圓弧的Bresenham算法計(jì)算各個(gè)象素點(diǎn)的坐標(biāo)值作業(yè):

1.完成直線DDA算法程序的實(shí)現(xiàn)2.畫（0，0）到（8，－4）之間的線段3.完成直線Bresenham算法完整程序353.3.1概述曲線規(guī)則曲線——可用標(biāo)準(zhǔn)的解析式來(lái)描述的曲線。如圓、橢圓、拋物線、雙曲線、漸開線、擺線等自由曲線——無(wú)法用標(biāo)準(zhǔn)的曲線方程來(lái)描述的曲線，通常由實(shí)際測(cè)量得到的一系列散亂的數(shù)據(jù)點(diǎn)(型值點(diǎn))來(lái)確定。如汽車的外形曲線、等高線等。計(jì)算機(jī)顯示曲線的基本原理是“以直代曲”,即用許多能滿足精度要求的短的直線段代替曲線.如正多邊形逼近圓3.3規(guī)則曲線的生成算法36xyo圓----圓上任意一點(diǎn)的曲率都相等,因此用角度DDA算法在屏幕上會(huì)產(chǎn)生較好的圖像.1.橢圓等角度DDA算法橢圓若采用等周長(zhǎng)的顯示算法，只要有足夠數(shù)量的段數(shù)，就會(huì)常發(fā)生較好的圖像。希望：曲率較小的兩側(cè)取較大的周長(zhǎng)增量曲率較大的兩側(cè)取較小的周長(zhǎng)增量步長(zhǎng)為等周長(zhǎng)的橢圓算法的缺陷:1.曲率較小的兩側(cè),點(diǎn)過(guò)密,曲率較大的兩側(cè),點(diǎn)過(guò)稀.2.將涉及橢圓積分,計(jì)算費(fèi)時(shí),算法效率低.長(zhǎng)軸兩端的曲率太大,用少數(shù)幾個(gè)等角度增量計(jì)算出來(lái)的點(diǎn)無(wú)法較精確地描述橢圓.3.3.2橢圓的顯示算法37因此橢圓用參數(shù)方程表示:其中：圓心的坐標(biāo)為(xc,yc),a,b為橢圓長(zhǎng)短、半軸,

為參數(shù)取微分得:分析:1.當(dāng)角接近0或時(shí),兩端的曲率較大,有:此時(shí)|dy|近似2.當(dāng)角接近/2或3/2時(shí),兩端的曲率較大,有:此時(shí)|dx|近似由于a>b，所以兩端點(diǎn)多，而兩側(cè)點(diǎn)少。且周長(zhǎng)增量大小之比

a/b我們希望的周長(zhǎng)增量可以自動(dòng)獲得等于弧長(zhǎng)等于弧長(zhǎng)38N——橢圓上顯示點(diǎn)的個(gè)數(shù)i(xc,yc)392.橢圓的生成算法-------中點(diǎn)法給定橢圓參數(shù)中心(0，0)、長(zhǎng)半軸a和短半軸b，該橢圓的一般方程為：

X2/a2+Y2/b2=1F(x,y)=b2x2+a2y2-a2b2=0 中點(diǎn)畫圓法可以推廣到一般二次曲線的生成現(xiàn)討論第一象限橢圓弧的生成。在處理這段橢圓弧時(shí)，我們進(jìn)一步把它分為兩部分：上部分和下部分，以弧上斜率為-1的點(diǎn)作為分界。上半部分，斜率的絕對(duì)值>1,單位步長(zhǎng)應(yīng)為X方向，來(lái)確定下一個(gè)象素的位置下半部分，斜率的絕對(duì)值<1,單位步長(zhǎng)應(yīng)為Y方向，從而確定下一個(gè)象素的位置則該公式可作為中點(diǎn)算法的判別式：F(x,y)<0=0>0說(shuō)明(x，y)在橢圓邊界內(nèi)說(shuō)明(x，y)在橢圓邊界上說(shuō)明(x，y)在橢圓邊界外40橢圓的斜率：dy/dx=-2b2x/(2a2y)

中點(diǎn)畫橢圓，當(dāng)我們確定一個(gè)象素之后，接著在兩個(gè)候選點(diǎn)的中點(diǎn)計(jì)算一個(gè)判別式的值。并根據(jù)判別式符號(hào)確定哪個(gè)象素離橢圓更近。有一個(gè)象素點(diǎn)（xp,yp),那么下一對(duì)候選象素的中點(diǎn)是（xp+1,yp-0.5)。xp,ypxp+1,yp-0.5當(dāng)斜率為-1時(shí)則：2b2x=2a2y上半部分的條件是：2b2x<=2a2y下半部分的條件是：2b2x>=2a2y假如上半部分橢圓判別式為：dp=F(xp+1,yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b2如果dp<＝0,中點(diǎn)在橢圓內(nèi)，則取正右方的那個(gè)象素且判別式應(yīng)更新為:dp+1=F(xp+2,yp-0.5)=dp+b2(2xp+3)如果dp>0,中點(diǎn)在橢圓外，則取右下方的那個(gè)象素且判別式應(yīng)更新為：dp+1=F(xp+2,yp-1.5)=dp+b2(2xp+3)+2a2(-yp+1)41弧的起點(diǎn)為（b,0)第一個(gè)中點(diǎn)是(1,b-0.5)判別式的初值dp0=b2+a2(-b+0.25).步進(jìn)方向由x改為方向ydp=b2(xp+0.5)2+a2(yp-1)2-a2b2下半部分的終止條件為y=0假如為橢圓弧的下半部分如果上半部分的最后一個(gè)象素為（xp,yp)，則且應(yīng)改為從正下方和右下方兩個(gè)象素中選擇一個(gè)象素中點(diǎn)是（xp+0.5,yp-1)如果dp<＝0,中點(diǎn)在橢圓內(nèi)，則取右下方的那個(gè)象素Pr(xp+1,yp-1)且判別式應(yīng)更新為:dp+1=F(xp+1.5,yp-2)=dp+b2(2xp+2)+a2(-2yp+3)如果dp>0,中點(diǎn)在橢圓外，則取正下方的那個(gè)象素Pl（xp,yp-1）且判別式應(yīng)更新為：dp+1=F(xp+0.5,yp-2)=dp+a2(2yp+3)在編寫程序時(shí)應(yīng)先更新決策變量d，再更新（x，y）上半部分的終止條件為：b2(x+1)<a2（y-0.5)下半部分的d的初值為上半部分計(jì)算的最后點(diǎn)下半部判別式的初值dp0=b2(x+0.5)2+a2(y-1)2-a2b242或拋物線標(biāo)準(zhǔn)方程為:y2=4ax(a為拋物線焦距)xyN——顯示點(diǎn)的個(gè)數(shù)參數(shù)方程3.3.3拋物線的顯示算法43基圓圓心在原點(diǎn)的漸開線參數(shù)方程為令起始角

s=0,終止角e=N——顯示點(diǎn)的個(gè)數(shù)3.3.4漸開線的顯示算法443.4.1基本概念1.插值-----構(gòu)造一函數(shù)，使曲線或曲面嚴(yán)格通過(guò)所有的已知點(diǎn)。通常用已知函數(shù)代替被插的函數(shù)。2.逼近-----構(gòu)造一函數(shù)，但曲線或曲面不嚴(yán)格通過(guò)各型值點(diǎn)，只要求最靠近。Bezier、B-Spline型值點(diǎn)3.擬合----插值逼近在曲線曲面的描述中，所構(gòu)造的數(shù)學(xué)模型要：保證：1.空間的唯一性

2.物體的有界性、連續(xù)性

3.坐標(biāo)變換后形狀不變性（坐標(biāo)獨(dú)立性）Q1Q3Q0Q2P1（x1,y1)P2（x2,y2)P3（x3,y3)3.4自由曲線的生成算法45對(duì)數(shù)學(xué)式的一些要求是：1.有足夠強(qiáng)的描述能力（局部、整體光滑）2.易控制（形）、易預(yù)測(cè)（閉凸包性、變差減小性----不穩(wěn)、擺動(dòng)）平面曲線空間曲線直角坐標(biāo)方程y=f(x)或f(x,y)=0z=f(x,y)或f(x,y,z)=0參數(shù)坐標(biāo)方程代數(shù)形式x=x(t)y=y(t)x=x(t)y=y(t)z=z(t)幾何形式P(t)=[x(t)y(t)]P(t)=[x(t)y(t)z(t)]3.4.2曲線的表示方法461）易于處理多值問(wèn)題；2）在多值的情況下，可以方便地指定曲線的延伸范圍；3）具有幾何不變性，其形狀與坐標(biāo)的選擇無(wú)關(guān)，可以不依靠坐標(biāo)系來(lái)研究圖形的幾何性質(zhì)；4）易于進(jìn)行幾何變換，如仿射變換、射影變換等；5）易于計(jì)算曲線上的點(diǎn)（計(jì)算方便）；6）易定義空間曲線（規(guī)定曲線的范圍和邊界等）；7）便于曲線的分段描述。參數(shù)曲線描述的優(yōu)點(diǎn)：471.型值點(diǎn)2.控制點(diǎn)指用來(lái)控制或調(diào)整曲線形狀的特殊點(diǎn)。如BEZIER曲線段中的Q1與Q2點(diǎn)。Q1Q3Q0Q23.位置矢量表示曲線上任一點(diǎn)的坐標(biāo)的矢量

P(t)=[x(t)y(t)z(t)]P1（x1,y1)P2（x2,y2)P3（x3,y3)P2’指通過(guò)測(cè)量或計(jì)算得到的曲線或曲面上少量描述曲線或曲面幾何形狀的數(shù)據(jù)點(diǎn)。3.4.3常用名詞術(shù)語(yǔ)484.切矢量P'0P'1P0P1t=0t=1P(t)RP(t+△t)Q5.曲率T——單位切矢量△C△PC--弧長(zhǎng)當(dāng)Q趨向于r時(shí)：在極限情況下|△P|=△C設(shè)以弧長(zhǎng)c為參數(shù)，曲線的方程為p(c)T(c+△c)T(c)T(c+△c)T(c)RQ△

△c若曲線上R，Q兩點(diǎn)的參數(shù)分別為t和t＋△t，矢量△p＝p(t+△t)-p(t)496.幾何連續(xù)性指兩段曲線或兩片曲面在連接處的連續(xù)狀態(tài)。(1)Q1(1)=Q2(0)——C0（幾何位置的連續(xù)）和G0連續(xù)(2)Q1(1)=Q2(0)Q'1(1)=Q'2(0)——C1連續(xù)（切矢連續(xù)）(3)Q1(t)和Q2(t)在P點(diǎn)處已有C0，C1連續(xù)

Q"1(1)=Q"2(0)——C2連續(xù)（曲率連續(xù)）Q1Q2Q4PQ3507.插值—函數(shù)逼近的重要方法插值設(shè)計(jì)方法：要求建立的曲線與曲面數(shù)學(xué)模型，嚴(yán)格通過(guò)已知的每一個(gè)型值點(diǎn)。在曲線、曲面中最常用的是線性插值和拋物線插值。（1）線性插值xyx1x2y1y2—點(diǎn)斜式—兩點(diǎn)式假設(shè)給定函數(shù)f(x)在兩個(gè)不同點(diǎn)x1和x2的值，y1=f(x1),y2=f(x2)現(xiàn)要求用一線性函數(shù)：y=(x)=ax+b,近似代替y=f(x).51（2）拋物線插值—---二次插值(0≤t≤1)P1P2P3P(0)=P1P(1)=P3P(0.5)=P2A0=P1A1=4P2-P3-3P1A2=2P1+2P3-4P2設(shè)已知f（x）在三個(gè)互異點(diǎn)P1,P2,P3,要求構(gòu)造一個(gè)函數(shù)

(x)，使得(x)在各結(jié)點(diǎn)處與f（x）的值相等。528.逼近逼近設(shè)計(jì)方法:用這種方法建立的曲線與曲面數(shù)學(xué)模型只是近似地接近已知的型值點(diǎn)。逼近最常用的方法是最小二乘法。逼近好壞常用各點(diǎn)偏差的平方和或加權(quán)的方差和最小。9.擬合

擬合是指在曲線、曲面的設(shè)計(jì)中，用插值或逼近的方法使生成的曲線、曲面達(dá)到某些設(shè)計(jì)要求。如在允許的范圍內(nèi)貼近原始的型值點(diǎn)或控制點(diǎn)序列；曲線、曲面看上去要“光滑”等。53三次曲線：

二次曲線：參數(shù)變量的規(guī)格化一次曲線：0次曲線：連接兩點(diǎn)的多項(xiàng)式的參數(shù)方程為：（A0，A1，A2，A3）為向量常數(shù)一次曲線：P'0P0P‘1P1t=1,P1t=0,P0P(0)=P0=A0P(1)=P1=A0+A1t

=P1P(t)=P0+(P1-P0)t54P(0)=P0=A0P(1)=A0+A1t

+A1t2=P1二次曲線：P'0P0P‘1P1P(0)’=A1+2A1t=P0’P(t)=P0+P0’t+(P1-P0-P0’

)t2三次曲線：

P(0)=P0=A0P(1)=A0+A1t

+A1t2=P1P(0)’=A1+2A1t=P0’P(1)’=A1+2A1t=P1’P(t)=P0+P0’t+(3P1–P1’

-3P0-2P0’

)t2+(2P1-2P0+P1’

+P0’

)t355三次曲線的參數(shù)方程的幾何形式如下：其中T=[t3t2t11]

A=[A3A2A1A0]T

——代數(shù)系數(shù)矩陣已知曲線的端點(diǎn)位置矢量及切矢量：P0，P1，P'0，P'1P(0)=A0=P0P(1)=A3+A2+A1+A0=P1P'(0)=A1=P'0P'(1)=3A3+2A2+A1=P'1P'(t)=3A3t2+2A2t+A1A0=P0A1=P'0A2=-3P0+3P1-2P'0-P'1A3=2P0-2P1+P'0+P'1P'0P0P‘1P13.4.4三次參數(shù)樣條曲線----HERMITE插值曲線56P(t)=(2P0-3P1+P'0+P'1)t3+(3P0+3P1-2P'0-P'1)t2+P'0t+P0

=(2t3-3t2+1)P0+(-2t3+3t2)P1+(t3-2t2+t)P'0

+(t3-t2)P'1

令H1=2t3-3t2+1H2=-2t3+3t2H3=t3-2t2+tH4=t3-t2

P(t)=H1P0+H2P1+H3P'0+H4P'1=HB其中H=[H1

H2

H3

H4]——調(diào)和函數(shù)

調(diào)和函數(shù)通過(guò)端點(diǎn)及其切失量產(chǎn)生整個(gè)t值范圍內(nèi)的其余各點(diǎn)列的坐標(biāo)，并且只與參數(shù)t有關(guān)，由此便于我們通過(guò)修改邊界條件來(lái)改變曲線形狀。H1(t)H2(t)H3(t)H4(t)B=[P0P0P'0P'1]T

——幾何系數(shù)矩陣或邊界條件矩陣57A=MB

P(t)=TMB表示的曲線是由端點(diǎn)及其切矢量定義的三次參數(shù)曲線，稱為三次Hermite曲線或Ferguson曲線或Coons曲線。58Coons曲線的性態(tài)分析:P(t)=H0,0(t)*[0,0]+H0,1(t)*[1,0]+H1,0(t)*[k,k]

+H1,1(t)*[k,-k]

設(shè)給出曲線的始點(diǎn)P0=[0,0]終點(diǎn)P1=[1,0]切矢的方向P'0=[k,+k]，P'

1=[k,-k]給出位置矢量曲線P0，P1和切矢量P'0，P'1，可以唯一確定一條Coons曲線。若切矢的方向和大小改變，則曲線的形狀也隨之變化。x=2(k-1)t3+3(k-1)t2+kty=k(-t2+t)為了求出尖點(diǎn)，可令：（1）當(dāng)t=1/2,k=3時(shí)，曲線上將產(chǎn)生一個(gè)尖點(diǎn)。曲線不光滑（2）當(dāng)k=0時(shí)，曲線退化為連接兩個(gè)端點(diǎn)的直線段（3）當(dāng)k>3時(shí)，曲線上將出現(xiàn)一個(gè)閉環(huán)。59

1962年法國(guó)雷諾(Renault)汽車公司的P.E.Bezier構(gòu)造了一種以逼近為基礎(chǔ)的參數(shù)曲線,這種曲線稱為Bezier曲線，并以此為基礎(chǔ)設(shè)計(jì)了UNISURF系統(tǒng),該公司于1972年開始應(yīng)用此系統(tǒng)。Bezier曲線是由一組折線集，或稱之為Bezier曲線的特征多邊形來(lái)定義的。

曲線的起點(diǎn)和終點(diǎn)和該多邊形的起點(diǎn)和終點(diǎn)重合，且多邊形的第一條邊和最后一條邊表示曲線在起點(diǎn)和終點(diǎn)處的切矢量方向。3.4.5

BEZIER曲線60

Coons曲線的幾何信息是端點(diǎn)的位矢和切矢，曲線的形狀很大程度上取決于切矢的大小。為了能更加直觀地控制曲線的形狀:在兩端點(diǎn)切矢上適當(dāng)選擇兩個(gè)點(diǎn)P0Q1Q0Q'1Q'0P0=Q0+(1/q)Q0’P1=Q1-(1/q)Q1’Q0’=q(P0-Q0)Q1’=q(Q1-P1)P(t)=TMB=[t3

t2t1]代入=[t3t2t1]1.三次Bezier曲線的公式通過(guò)切矢來(lái)控制曲線形狀是比較困難的并且用這兩點(diǎn)P0和P1以及Q0和Q1四個(gè)點(diǎn)來(lái)描述控制曲線Q0P0和Q0P0的長(zhǎng)度取為各所在切矢長(zhǎng)度的1/qP161BEZIER曲線的一般表達(dá)方式:P(t)=[t3

t2t1]（0

t

1）當(dāng)q=3時(shí)，曲線最為接近多邊形Q0P0P1Q1。令q＝3，得三次Bezier曲線的矩陣表達(dá)式：62B0,3B3,3B2,3B1,3三次Bezier曲線的調(diào)和函數(shù)63Q0,

Q1,Q2,Q3——曲線的特征矢量一階導(dǎo)數(shù)的表達(dá)式64用B曲線逼近直線或圓弧1.直線P(t)=(1-t)3Q1+3(1-t)2tQ2+3(1-t)

t2Q3+t3Q4=(Q4–Q1+3Q2–3Q3)t3

+3(Q1–2Q2+Q3)t2

+3(Q2-Q1)t+Q1由于P(t)為直線,所以有:Q4–Q1+3Q2–3Q3=0Q1–2Q2+Q3=0Q3=Q1+2/3(Q4–Q1)Q2=Q1+1/3(Q4–Q1)P(t)=(1-t)Q1+tQ4為典型的直線參數(shù)方程Q1Q2Q3Q4Q1Q4Q2Q31/31/31/3652.圓弧P(t)=(1-t)3Q1+3(1-t)2tQ2+3(1-t)

t2Q3+t3Q4=(Q4–Q1+3Q2–3Q3)t3

+3(Q1–2Q2+Q3)t2

+3(Q2-Q1)t+Q1半徑為1,第一象限的1/4圓弧Q1=[1,0]Q4=[0,1]Q2=[1,k]Q3=[k,1]P(1/2)=[,]誤差=0.0027%OYXQ1(1,0)Q4(0,1)Q2(1,k)Q3(k,1)t=1/266

當(dāng)給定空間n+1個(gè)點(diǎn)的位置矢量，Bezier曲線上各點(diǎn)坐標(biāo)的公式為：Bi,n(t)——Bernstein基函數(shù)，調(diào)和函數(shù)Qi——構(gòu)成該曲線的特征多邊形各頂點(diǎn)的位置矢量當(dāng)n=3時(shí)，2.BEZIER曲線67當(dāng)n=1時(shí)Bezier曲線的表達(dá)式：0<=t<=1;矩陣表示：P(t)=[t1]-1110Q0Q10<=t>=1當(dāng)n=2時(shí)Bezier曲線的表達(dá)式：0<=t<=1P(t)=[t2t1]-21-220100Q0Q1Q20<=t<=1矩陣表示：68Bezier曲線的不足：（1）曲線離特征多邊形較遠(yuǎn)，逼近效果不好（2）Bezier曲線改變某一個(gè)控制點(diǎn)的位置對(duì)整條曲線都有影響，不能作局部修改，不易控制形狀。（3）特征多邊形的頂點(diǎn)個(gè)數(shù)決定了Bezier曲線的階次，并且當(dāng)n較大時(shí)，次數(shù)增大，計(jì)算不便。特征多邊形對(duì)曲線的控制將會(huì)減弱；

1972年，Gordon（通用汽車公司）,Riesenfeld（20多歲）等人拓?cái)U(kuò)了Bezier曲線，用B樣條函數(shù)代替了Bernstein函數(shù)，從而改進(jìn)了Bezier特征多邊形與Bernstein多項(xiàng)式次數(shù)有關(guān)，且是整體逼近的弱點(diǎn)。

由空間n+1個(gè)控制點(diǎn)生成的k階B樣條曲線是由L+1(L=n-k+1)段B樣條曲線逼近而成，每個(gè)曲線段的形狀僅由點(diǎn)列中的k+1個(gè)順序排列的點(diǎn)所控制。1.概述3.4.6

B-SPLINE曲線69若從空間n+1個(gè)頂點(diǎn)Qi（i=0,1,…,n）中取相鄰的三個(gè)頂點(diǎn)，構(gòu)造出一段兩次均勻B樣條曲線，其矩陣表示為：2.二次均勻B樣條曲線其中1)位置連續(xù):相鄰的兩段曲線Pi(t)

和Pi+1(t),分別在t=0和t=1處滿足:Pi-1(1)=Pi(0)1

in-1

代入上式Qi-1QiQi+1702)切矢連續(xù)：P’i-1(1)=P’i(0)1

in-2

3)增加柯西條件:(坐標(biāo)變換后形狀不變性)解得:其矩陣表達(dá)式:71二次均勻B樣條曲線的特性幾何特性首端:t=0末端:t=1曲線段的起點(diǎn)和終點(diǎn)為兩線段的中點(diǎn)切矢:曲線段與兩直線段相切Qi+1QiQi-1移動(dòng)一個(gè)控制點(diǎn),不影響整體,局部性好72如圖所示,給出有序的n+1個(gè)位置矢量Qi（i=0,1,…,n),每相鄰四個(gè)點(diǎn)一組,可以依次構(gòu)成(n-2)個(gè)線性組合,即3.三次均勻B樣條曲線Q0Q1Q2Q3Q8Q5Q6Q7Q41)位置連續(xù):相鄰的兩段曲線Pi(t)和Pi+1(t),分別在t=0和t=1處滿足:Pi-1(1)=Pi(0)1

in-1

代入上式732)切矢和曲率連續(xù)：P’i-1(1)=P’i(0)P”i-1(1)=P”i(0)(1

in-2)

3)增加柯西條件:(坐標(biāo)變換后形狀不變性)解得:和考慮函數(shù)的對(duì)稱性,可以假設(shè)

X0(t)=X3(1-t)X1(t)=X4(1-t)74其矩陣表達(dá)式:Qi-1QiQi+1Qi+2Pi(0)Pi(1)式中Qi-1QiQi+1Qi+2為特征多邊形的四個(gè)相鄰頂點(diǎn)特征多邊形有更多的頂點(diǎn)，則一條完整的B-Spline曲線將由若干段曲線所組成。75均勻三次B-Spline曲線的幾何關(guān)系1.曲線段首、末端點(diǎn)的位置矢量2.曲線段首、末端點(diǎn)的切矢量3.曲線段首、末端點(diǎn)的曲率Qi-1QiQi+1Qi+2ABCDPi(1)Pi(0)Pi'(0)Pi'(1)Pi"(0)Pi''(1)其中ABCD為此段Bezier曲線的特征多邊形的四個(gè)相鄰頂點(diǎn)76（1）凸包性。即曲線位于控制多邊形凸包范圍內(nèi)；（2）幾何不變性。曲線的幾何形狀和位置與坐標(biāo)系的選擇無(wú)關(guān)；（3）變差縮減性。（4）連續(xù)性。（5）局部性。（6）造型的靈活性。可構(gòu)造直線段、尖點(diǎn)、切線等特殊情況。4.B-SPLINE曲線的性質(zhì)77

上機(jī)調(diào)試BEZIER曲線的生成程序，并編寫B(tài)樣條曲線程序。作業(yè)78doublex=x1,y=y1; m=(y2-y1)/(x2-x1);intk=abs(x2-x1);putpixel((int)x,(int)y,2);++x;//x=x+1\x++;y+=m;//y=y+m;}對(duì)于第一象限的直線，如斜率<1，x1<x2，其直線生成的程序?yàn)椋?{for(inti=1;i<=k;i++)當(dāng)m>1時(shí),x,

y>1因而造成隔行顯示解決辦法:將y看作自變量分析：公式變?yōu)?其中:m=(x2-x1)/(y2-y1)令deltx=x;delty=y;79改進(jìn)的Bresenham算法由圖可知若ε(xi+1)≥0yi+1,r=yir+1，(2)

若ε(xi+1)≤0yi+1,r=yir，xiXi+1Yi,rYi+1,rBADε(x)的幾何意義Cxi列上已用（xi,yir）作為表示直線的點(diǎn)，設(shè)B點(diǎn)是直線上的點(diǎn)，其坐標(biāo)為（xi+1,yi+1）

顯然下一個(gè)表示直線的點(diǎn)（xi+1,yi+1,r）只能從圖中的C或者D點(diǎn)中去選。設(shè)A為CD邊的中點(diǎn)若B在A點(diǎn)上面則應(yīng)取D點(diǎn)作為（xi+1,yi+1,r）

否則應(yīng)取C點(diǎn)（xi+1,yi,r）為了能確定B在A點(diǎn)上面或下面，令ε(xi+1)=yi+1,r-yir-0.5（1）若B在A的下面，則有ε(xi+1)<0，