計(jì)算機(jī)圖形學(xué)課件chapter

第31233.1.1DDA3.1.1DDA4X圖3.1微分方程:dy/dx=m,y[i+1]=y[i]+m(x[i+1]-x[i]) 設(shè)一直線段的起點(diǎn)和終點(diǎn)坐標(biāo)分別為(xsys)和(xe,△x=xe-xs，△y=ye-

(3-(3-,xi1xidxxix/tyi1yidyyiy/t

(3-(3-6Procedurevark,i:integer;x,y,dx,dy:real;x:=x1;y:=y1;fori:=1tokplot(round(x),round(y)); x:=x+dx;y:=y+dy; 8 9長方向在此方向上每次遞增一個(gè)單位步長(或者一個(gè)像素單位另一個(gè)方向上是否同時(shí)產(chǎn)生這種情況下,選擇X方向?yàn)橛?jì)長方向,即增量線最近的像素,現(xiàn)在要決定Pi+1是T還是S。顯然若d<0.5則S比較靠近直線應(yīng)選S；若d>=0.5,則應(yīng)選T。(m=△y/△x)e<0時(shí) 選Pi+1(xi+1,yi),更新e>=0時(shí)選Pi+1(xi+1yi+1更新e=e+m- (xs,

S

(xe,TTd圖3.2Bresenhame=初值ee=初值ee=e+2e>=0時(shí)選Pi+1(xi+1e=e+2△y-2其中△x=xe-xs△y=ye-intx,y,deltax,deltay,e:=-deltax;x:=xs;y:=ys;for(i:=0todeltax)doif(e>=0)theny:=y+1;e:=e-2*deltax;x:=x+1;生成端點(diǎn)為(2010)和(30,18)的直線段。deltax=10deltay=8e=-10x=20,y=10,e=6;x=21,y=10,x=22,y=11,e=-x=23,y=12,

算法中可以全部采用整數(shù)運(yùn)算,且判別式的計(jì)算中只含+、-以及*2(計(jì)算機(jī)內(nèi)以移位方法實(shí)實(shí)現(xiàn),算法構(gòu)思巧妙。擴(kuò)展。當(dāng)斜率大于1時(shí)可以將x和y交換即以Y方向作為計(jì)長方向,每次變化1個(gè)單位步長或者1個(gè)像素單位。對于任意的直線段,則可以在直線段的生成程序中通常應(yīng)允許用戶選擇直線段的屬性參數(shù)。在實(shí)用系統(tǒng)中可把常用屬性值設(shè)置為默認(rèn)值,如黑色的細(xì)實(shí)線。使線段生成過程中可以按實(shí)線小段和空白小段相間的方式顯示允許用戶指定每個(gè)小段的長度參數(shù)例如在PHIGS應(yīng)用程序中設(shè)置線型屬性用戶在素的寬度或者繪圖筆的畫線寬度)作為基準(zhǔn),再重復(fù)調(diào)用線段生成程序畫幾次即可。此時(shí),還應(yīng)考慮直線的斜率以便決定在端點(diǎn)處是沿X方向還是沿Y方向增減坐標(biāo)。另外對于粗線在連接處,往往還應(yīng)作特殊處理?？蛇x顏色的數(shù)目取決于顯示器中每個(gè)像素單元的大小(如8bit,256種),像素單元的內(nèi)容是 與Bresenham直線生成算法一樣,其基本方法Y P1P2如圖3.4所示。X 圖3.4第1的點(diǎn)Pi(xi,yi),使其誤差項(xiàng)2|D(Pi)|=|xi2+yi2-R2設(shè)Pi-1(xi-1,yi-1)已被選定為最靠近圓弧的點(diǎn),下一步x=xi-1+1時(shí),參見圖3.5,要決定T還是S更接近D(S)=(xi-1+1)2+yi-12-D(T)=(xi-1+1)2+(yi-1-1)2-顯然|D(S)|>=|D(T)|時(shí),應(yīng)該取T點(diǎn)反之則取Sdi=|D(S)|-則di>=0選擇T點(diǎn)否則選取S

SF yi-1-

圖3.5Bresenhamdi=D(S)+D(T)=2(xi-1+1)2+yi-12+(yi-1-1)2-di>=0弧AB在園C的下方選擇T點(diǎn)否則選取S ,簡化di的計(jì)x0=0;y0=R;x1=x0d1=D(S)+D(T)=(12+y02-R2)+(12+(y0-1)2-=3-2y0=3-di=(xi2+yi-12-R2)+(xi2+(yi-1-1)2-R2=2xi2+2yi-12-2yi-1-2R2di+1=(xi+1)2+yi2-R2+(xi+1)2+(yi-1)2-R2=2xi2+4xi+2yi2-2yi-2R2d1=3-如果di<0,選Pi(xi,yi-1),將yiyi-1代入求di+1：di+1=di+4xi+2=di+4xi-1+6如果di>=0,選Pi(xi,yi-1-1),將yiyi-1-1代入求di+1：對稱性,就可以將45o圓弧擴(kuò)展到整個(gè)圓周。如圖3.6,如果點(diǎn)(x,y)在圓周上則與之對稱的另外7個(gè)點(diǎn)也在圓周上,它們的坐標(biāo)如圖所示。(-x,(-x,yY(-y,(-y,-(-x,-(x,(y,(y,-(x,-圖3.6圓周上的8varx,y,d:integer;x:=0;y:=r;d:=3-2*r;whilex<ydo{ifd<0then

} Bresenham圓弧算法是最有效的算法之一生僅用加、減和移位即可計(jì)算,算法效率高。然后選定圓弧起點(diǎn)后,在輸出圓弧的過程中根決定下一步的,每次只在一個(gè)方向(XY)這樣一步步地A(xA(xc,BC(xcyc),半徑為R令F(x,yx-xc)2y-yc)2則圓的方程為：F(x,y當(dāng)點(diǎn)(xy)在圓內(nèi)時(shí)有F(x,y0；當(dāng)點(diǎn)(xy)在圓外時(shí),有F(x,y)>0。取P0(x0y0)為A點(diǎn),即x0xcy0=yc+R。求得Pi(xi,yi)后找下一點(diǎn)Pi+1的原則為：當(dāng)Fi(xiyi)<0時(shí)向+X方向(圓外方向)走步,xi+1=xi+1,yi+1=當(dāng)Fi(xiyi)>=0時(shí)向-Y方向(圓內(nèi)方向)走步xi+1=xi,yi+1=yi–?注意?當(dāng)xi+1xi1,yi+1=yi(圓外方向走)時(shí),F(xi+1,yi+1)=(xi+1-xc)2+(yi–yc)2-R2=(xi–xc)2+(yi–yc)2-=F(xi,yi)當(dāng)xi+1=xiyi+1=yi1(圓內(nèi)方向走)時(shí),F(xi+1,yi+1)=(xi–xc)2+(yi–1-yc)2-R2=F(xi,yi)-2(yi–當(dāng)Fi<0時(shí)(在圓內(nèi)選Pi+1(xi1,yi),Fi+1=Fi+2(xi-當(dāng)Fi>=0時(shí)(在圓外選Pi+1(xiyi1),Fi+1=Fi-2(yi-varx,y,f:integer;x:=xc;y:=yc+r;whiley>ycdo iff>0then{f:=f-2*(y- else{f:=f+2*(x-xc)+1; }if(y=yc) 值是不斷增加的,因而其運(yùn)算規(guī)律相同；對于順圓的一、三象限,其X絕對值不斷增加, 移位(乘2)運(yùn)算,無乘除,因此運(yùn)算效率高,這很 較之Bresenham算法,正負(fù)法的運(yùn)算更為簡單,但對于同一段圓弧而言,由于正負(fù)法每次只是3.2.33.2.3當(dāng)圓的內(nèi)接多邊形邊數(shù)足夠多時(shí),該多邊形可以和圓接近到任意程度,因此在允許的誤差范個(gè)像素的寬度),可用顯示多邊形代替顯示圓。為C(xc,yc),半徑為r。

圖3.8用正多邊 近圓設(shè)內(nèi)接正多邊形的一個(gè)頂點(diǎn)為Pi(xiyiCPi的幅角為i,則xi=xc+rcosyi=yc+rsin[方法2]利用遞 分析:在上述遞推 中,因?yàn)槭浅?shù),cos和sin只要在開始時(shí)算一次,這樣求Pi+1的坐標(biāo)需要 穩(wěn)定,以免誤差多次積累后嚴(yán)重偏離真解?？梢?平面曲線可分為兩大類規(guī)則曲線(函數(shù)曲線)和如圓、橢圓、雙曲線、漸開線等;不規(guī)則曲線通直線段,通過連接各直 Y 圖3.92橢圓的標(biāo)準(zhǔn)方程為： 2

2 2

y

a2x(aa2x,(x,y)連接為一個(gè)直線段,反復(fù)執(zhí)行(2),直至x=a定后,在整個(gè)過程中就是常數(shù),但是曲率大的兩端個(gè)夸大的圖形見圖3.10,橢圓兩端出現(xiàn)棱角。若dx取值減小,兩端情況會好轉(zhuǎn),但是對于相對平滑的兩側(cè)而言,計(jì)算 圖3.10步進(jìn)增量dx拉大時(shí)生成的橢 橢圓的參數(shù)方程為：x=ay=b

(0t2計(jì)算下一點(diǎn)坐標(biāo),即t=t+dt時(shí)的點(diǎn)(x,y),并且與前一點(diǎn)連接為一個(gè)直線段,反復(fù)執(zhí)行(2),直至由橢圓的參數(shù)方程可以得到參數(shù)t有增量dt時(shí),引 dx=-asint?dtdy=bcost?dt當(dāng)t接近0或時(shí),有|dx|0和|dy|b?dt,這就是說，x幾乎不增加的情況下y有一定的增值,當(dāng)t接近/2或3/2時(shí)有|dx|a?dt和|dy|0這就是說,y幾乎不增加的情況下,x有一定的增值,這與橢圓兩側(cè)所需要的趨勢符合。 而且由于a>b因此兩側(cè)的增值大于兩端的增值,做到了曲率大處點(diǎn)密,曲率小處點(diǎn)稀。以坐標(biāo)原點(diǎn)為頂點(diǎn)焦點(diǎn)在(0p)的拋物線其標(biāo)在該表達(dá)式中,自變量x的取值范圍是任意的,2O圖3.11確定x對于曲線2,顯然x的取值范圍為[-XL/2,XL/2];對于曲線1y=YH時(shí)的x1與x2值,這時(shí)x的取值范圍為[x1,x2]。因此決定x的取值范圍[x1,x2]若y<=YH,則x1=-XL/2否則y=YH代入拋物線方程解得x1和x2設(shè)定x的步進(jìn)增量dx,從x=x1開始,求出對應(yīng)的y值直到xx2為止。相鄰點(diǎn)以直線段相連即可。首先建立對曲線生成有利的幾何描述(數(shù)學(xué)表用直線段近曲線時(shí),必須考慮近的精度,選擇合理的步進(jìn)增量大小,兼顧生成圖形的質(zhì)量實(shí)際曲線總有一個(gè)預(yù)定的范圍生成時(shí)注意不 符。另外還有很多面向各種應(yīng)用的符號如電子線路中的電阻、電容符號;機(jī)械圖紙中的加 息、交換用漢字編碼字符基本集”中,共收集字符7445個(gè),其中國標(biāo)一級漢字3755個(gè),國標(biāo)二級生成的字符效果好,但計(jì)算量大；另一種是在計(jì)算機(jī)內(nèi)用位圖(點(diǎn)陣)來表示,存這是傳統(tǒng)的方法,簡單、速度快,但不靈活。3.4.213.4.212選1616,3232,6464,128128等)中,其每一筆劃兩端點(diǎn)相對網(wǎng)格左下角(00)點(diǎn)的(x,重復(fù),也不能越界)。為節(jié)省空間,查找迅速,壓縮：如將每一端點(diǎn)的x、y坐標(biāo)和劃線標(biāo)志3個(gè)信息用兩個(gè)字節(jié)保存x、y坐標(biāo)各占7用定長記錄字模：這樣可以加快查找在應(yīng)用中,用戶必須指定字符的顯示位置,另外還可等),這些都可用坐標(biāo)變換的方法實(shí)現(xiàn)。(1)確定字符顯示時(shí)字符界框的左下角點(diǎn)坐標(biāo)(x,y)；(2)根據(jù)字符代碼CODE,取出該字符的 (3)進(jìn)行一系列坐標(biāo)變換,計(jì)算出該字符的每個(gè)端點(diǎn)3.4.3字符,保存在字符發(fā)生器中。所謂字符掩膜,3.4.3置(x0,y0)后,就可將此字符掩膜中每個(gè)像素相對(x0,y0)平移后的值寫入顯示緩存,從而在屏幕上將字符掩膜相應(yīng)的像素值置成背景色,MN,外環(huán)頂點(diǎn)數(shù)為M,(N=0時(shí)即無內(nèi)孔定義二維數(shù)組P(2MN)存

P P3 之間的垂直間隔h。 :

其中b=h/|cos 為Bmax最小值為Bmin,B0=距范圍是(Bmin,Bmax)每一條陰影線只與多邊形的部分棱邊有交點(diǎn),設(shè)某條陰影線的截距為bj,對于某一棱邊而言,設(shè)它的兩個(gè)端點(diǎn)分別為P(xp,yp)和Q(xq,yq從P和Q按陰影線斜率引線,對應(yīng)的截距為bp和bq,可用以下公bp=yp-kxpbq=yq-當(dāng)滿足min(bp,bqbjmax(bp,bq)時(shí)xlxpyqypxqbj(xqxp)(yqyp)k(xqxp)ylkxl交點(diǎn)以決定相應(yīng)的陰影線在填充時(shí)開始/終止于何處,因而有必要事先計(jì)算出所有棱邊的兩個(gè)端點(diǎn)按陰影線斜率引線的對應(yīng)截距,方便每一次的判斷,避免重復(fù)計(jì)算。鑒于上述原因,定義數(shù)組B(2,MN)記錄各棱邊兩434312按順序產(chǎn)生奇數(shù)點(diǎn)到對于MN條棱邊,計(jì)算每一條棱邊Li的兩個(gè)端點(diǎn)分別按陰影線斜率k=tg引線得到的截距,其中較小值放在B(1,i)中,較大值放在B(2,i)中。求出Bmin=minB(1,i),Bmax=maxB(2,ii=1,2,...,MN3).取第一條陰影線截距為b=Bmin+b,(b=h/|cos|)判斷當(dāng)前陰影線與各棱邊是否有交點(diǎn)若存在則計(jì)取下一條陰影線b=b+b,若bBmax轉(zhuǎn)4)繼續(xù)。

選 thenbegin適用對象邊界定義區(qū)域,把邊界包圍的區(qū)域內(nèi) thenbeginflood-fill-4(x,y+1,boundary-color,new-color);flood-fill-4(x,y-1,boundary-color,new-color);flood-fill-4(x+1,y,boundary-color,new-color);flood-fill-4(x-1,y,boundary-color,new-color);通常是將由頂點(diǎn)定義的多邊形區(qū)域其內(nèi)部用預(yù)期的像素值予以填充因此稱為多邊形的掃 在圖3.16中對于y=8這條掃描線,可以求出交點(diǎn)A、B、C、D在AB和CD區(qū)段內(nèi)的像素都位于多邊形之內(nèi),因此可以按每一條掃描線處理：與多邊形各棱邊求交若為水平邊則跳過Y A A 27 271e1 (xjj若PQ與掃描線y=j+1仍有交點(diǎn)存在Pxj+1=xj利用這種邊的連貫性,交

邊的分類表ET：指針數(shù)組,記錄對多邊形的所有棱邊(水平邊除外),按下端點(diǎn)的縱坐標(biāo)y的分類。下端點(diǎn)的縱坐標(biāo)y=j的邊歸入第j描線,就設(shè)多少類。同類中的邊構(gòu)成一個(gè)鏈。交點(diǎn)序列。初值為空,在處理過程中利用ET表 d.邊的活化鏈表AEL初始化,使其為空；e1把ET表中縱坐標(biāo)為y的鏈取下與AEL表合并并保持AEL表中元素按xx相同時(shí)按x)域e2對于當(dāng)前掃描線y從左到右將AEL表中元素