光柵圖形學(xué)課件

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

第2章光柵圖形學(xué)什么是光柵圖形學(xué)？

光柵顯示器－>圖形光柵化、光柵化圖形的處理

2.1直線段的掃描轉(zhuǎn)換算法直線的掃描轉(zhuǎn)換：確定最佳逼近于該直線的一組象素，并且按掃描線順序，對(duì)這些象素進(jìn)行寫操作。三個(gè)常用算法：數(shù)值微分法（DDA）中點(diǎn)畫線法Bresenham算法。2.1.1數(shù)值微分(DDA)法

基本思想

已知過端點(diǎn)的直線段L：

直線斜率為

從的左端點(diǎn)開始，向右端點(diǎn)步進(jìn)。步長=1(個(gè)象素)，計(jì)算相應(yīng)的y坐標(biāo)；取象素點(diǎn)(x,round(y))作為當(dāng)前點(diǎn)的坐標(biāo)。這種方法直觀，但效率太低，因?yàn)槊恳徊叫枰淮胃↑c(diǎn)乘法、一次加法和一次舍入運(yùn)算。),(),,(111000yxPyxP2.1.1數(shù)值微分(DDA)法作為最底層的光柵圖形算法，在通常的CAD/圖形系統(tǒng)中，會(huì)被大量應(yīng)用，因此，哪怕節(jié)約一個(gè)加法或減法，也是很了不起的改進(jìn)。由此出發(fā)點(diǎn)，導(dǎo)致增量算法的思想。增量算法：在一個(gè)迭代算法中，如果每一步的x、y值是用前一步的值加上一個(gè)增量來獲得，則稱為增量算法。2.1.1數(shù)值微分(DDA)法例：畫直線段k=0.4xyint(y+0.5)y+0.50 0 0 0注：網(wǎng)格點(diǎn)表示象素012345321Line:P0(0,0)--P1(5,2)2.1.1數(shù)值微分(DDA)法例：畫直線段xint(y+0.5) y+0.50 0 01 0 0.4+0.52 1 0.8+0.5 3 1 1.2+0.54 2 1.6+0.55 2 2.0+0.5注：網(wǎng)格點(diǎn)表示象素2.1.1數(shù)值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx； floatdx,dy,y,k; dx=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;xx1,x++)

drawpixel(x,int(y+0.5),color); y=y+k;

2.1.1數(shù)值微分(DDA)法當(dāng)k

1時(shí)，必須把x，y地位互換，y每增加1，x相應(yīng)增加1/k。2.1.1數(shù)值微分(DDA)法缺點(diǎn)：

在此算法中，y、k必須是float，且每一步都必須對(duì)y進(jìn)行舍入取整，不利于硬件實(shí)現(xiàn)。DDA算法小結(jié)直線的顯式方程（兩點(diǎn)式）象素是整數(shù)的（x每次增加1，取象素點(diǎn)(x,round(y))）最簡(jiǎn)單算法效率低改進(jìn)為增量算法（當(dāng)x每遞增1，y遞增k）2.1.2中點(diǎn)畫線法基本思想當(dāng)前象素點(diǎn)為(xp,yp)。下一個(gè)象素點(diǎn)為P1

或P2

。設(shè)M=(xp+1,yp+0.5)，為p1與p2之中點(diǎn)，Q為理想直線與x=xp+1垂線的交點(diǎn)。將Q與M的y坐標(biāo)進(jìn)行比較。當(dāng)M在Q的下方->P2離直線更近更近->取P2。M在Q的上方->P1離直線更近更近->取P1M與Q重合，P1、P2任取一點(diǎn)。2.1.2中點(diǎn)畫線法問題：如何判斷M與Q點(diǎn)的關(guān)系？2.1.2中點(diǎn)畫線法假設(shè)直線方程為：F(x,y)=ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常識(shí)知：∴欲判斷M點(diǎn)是在Q點(diǎn)上方還是在Q點(diǎn)下方，只需把M代入F(x,y),并檢查它的符號(hào)。2.1.2中點(diǎn)畫線法但這樣做，每一個(gè)象素的計(jì)算量是4個(gè)加法，兩個(gè)乘法。d=a(xp+1)+b(yp+0.5)+c2.1.2中點(diǎn)畫線法如果也采用增量算法呢？2.1.2中點(diǎn)畫線法d是xp,yp的線性函數(shù)，因此可采用增量計(jì)算，提高運(yùn)算效率。

d=a(xp+1)+b(yp+0.5)+c2.1.2中點(diǎn)畫線法若d<0時(shí)，則取右上方象素P2(xp+1,yp+1)。要判斷再下一象素，則要計(jì)算

d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b；增量為a＋b

d=a(xp+1)+b(yp+0.5)+c2.1.2中點(diǎn)畫線法至此，至少新算法可以和DDA算法一樣好。能否再做改進(jìn)？2.1.2中點(diǎn)畫線法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<x1){if(d<0){x++,y++,d+=d2;}else{x++,d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/2.1.2中點(diǎn)畫線法例：用中點(diǎn)畫線法

i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5

中點(diǎn)畫線法小結(jié)中點(diǎn)與交點(diǎn)位置來判斷象素選取引入直接的隱式方程F(x,y)=ax+by+c=0但計(jì)算量大，故又改進(jìn)為增量算法（此處，增量分兩種情況）為進(jìn)一步提高效率，修改為全是整數(shù)計(jì)算的算法（2d代替d，同時(shí)增量也做相應(yīng)調(diào)整）2.1.2中點(diǎn)畫線法思考題：P552-2用中點(diǎn)畫線法掃描轉(zhuǎn)換從點(diǎn)（1,0）到（4,7）經(jīng)過的直線段，并給出每一步的判別值。DDA算法采用點(diǎn)斜式，中點(diǎn)法采用隱式表示。中點(diǎn)法可以有整數(shù)算法。其他表示可以推出整數(shù)算法嗎？2.1.3Bresenham算法基本思想過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后根據(jù)誤差項(xiàng)的符號(hào)確定該列象素中與此交點(diǎn)最近的象素。2.1.3Bresenham算法設(shè)直線方程為：，其中k=dy/dx。因?yàn)橹本€的起始點(diǎn)在象素中心，所以誤差項(xiàng)d的初值d0＝0。X下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即d＝d＋k。當(dāng)d≥0.5時(shí)，選擇當(dāng)前象素的右上方象素（），修改比較的基點(diǎn)為改點(diǎn)，即將d-1而當(dāng)d<0.5時(shí)，選擇當(dāng)前象素的右方象素（），此時(shí)不改變基點(diǎn)為方便計(jì)算，令e＝d-0.5，e的初值為-0.5，增量為k。當(dāng)e≥0時(shí)，取當(dāng)前象素（xi，yi）的右上方象素（）；而當(dāng)e<0時(shí)，更接近于右方象素（）。2.1.3Bresenham算法例：Line:P0(0,0),P1(5,2)k=dy/dx=0.4xye00-0.510-0.1210.331-0.3420.152-0.5e每次加k，若e大于零則y加1且e減1，若e小于零則不變2.1.3Bresenham算法voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy;floatk,e;dx=x1-x0,dy=y1-y0,k=dy/dx;e=-0.5,x=x0,y=y0;for(i=0;idx;i++){drawpixel(x,y,color);x=x+1，e=e+k;if(e0){y++,e=e-1;}}}2.1.3Bresenham算法可以改用整數(shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號(hào)，因此可作如下替換：dxee**2'=2.1.3Bresenham算法voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy,e;dx=x1-x0,dy=y1-y0;

e=-dx,x=x0,y=y0;for(i=0;idx;i++){drawpixel(x,y,color);x=x+1，e=e+2*dy;if(e0){y++,e=e-2*dx;}}}intx,y,dx,dy;floatk,e;dx=x1-x0,dy=y1-y0;k=dy/dx,e=-0.5;x=x0,y=y0;for(i=0;idx;i++){drawpixel(x,y,color);x=x+1，e=e+k;if(e0){y++,e=e-1;}}2.1.3Bresenham算法y每次增k誤差項(xiàng)每次也增k（同DDA算法）通過交點(diǎn)與基點(diǎn)的距離d來判斷為了用正負(fù)號(hào)判斷，e＝d-0.5為了變?yōu)檎麛?shù)算法最終，Bresenham算法也是每個(gè)象素，需一個(gè)整數(shù)算法，其優(yōu)點(diǎn)是可以用于其他二次曲線。dxee**2'=2.2圓弧的掃描轉(zhuǎn)換算法圓的特征：八對(duì)稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個(gè)圓弧的象素集中點(diǎn)畫圓法考慮中心在原點(diǎn)，半徑為R的第二個(gè)8分圓，構(gòu)造判別式（圓方程）2.2圓弧的掃描轉(zhuǎn)換算法若d<0,則取P1為下一象素，而且再下一象素的判別式為若d>=0,則應(yīng)取P2為下一象素，而且下一象素的判別式為第一個(gè)象素是（0,R），判別式d的初始值為2.2圓弧的掃描轉(zhuǎn)換算法MidPointCircle(intrintcolor){ intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);//顯示圓弧上的八個(gè)對(duì)稱點(diǎn)while(x<=y){ if(d<0) d+=2*x+3; else{d+=2*(x-y)+5;y--;}x++;circlepoints(x,y,color); }}2.2圓弧的掃描轉(zhuǎn)換算法為了進(jìn)一步提高算法的效率，可以將上面的算法中的浮點(diǎn)數(shù)改寫成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫圓法。如何改？2.2圓弧的掃描轉(zhuǎn)換算法使用e=d-0.25代替de0=1-R圓弧的中點(diǎn)掃描轉(zhuǎn)換算法利用圓八對(duì)稱性類似于直線的中點(diǎn)法使用了圓的隱式方程兩種不同的增量（>0時(shí)，<0時(shí)）為了改為整數(shù)算法e=d-0.25代替d小結(jié)2.1直線段的掃描轉(zhuǎn)換算法2.1.1數(shù)值微分(DDA)法2.1.2中點(diǎn)畫線法2.1.3Bresenham算法2.2圓弧的掃描轉(zhuǎn)換算法2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的。2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充區(qū)域表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。逐點(diǎn)判斷算法逐點(diǎn)判斷算法：逐個(gè)像素判別其是否位于多邊形內(nèi)部判斷一個(gè)點(diǎn)是否位于多邊形內(nèi)部：射線法從當(dāng)前像素發(fā)射一條射線，計(jì)算射線與多邊形的交點(diǎn)個(gè)數(shù)內(nèi)部：奇數(shù)個(gè)交點(diǎn)外部：偶數(shù)個(gè)交點(diǎn)逐點(diǎn)判斷算法判斷一點(diǎn)是否位于多邊形內(nèi)部？逐點(diǎn)判斷算法算法描述for(y=0;y<=y_resolution;y++)for(x=0;x<=x_resolution;x++){if(inside(polygon,x,y)) setpixel(framebuffer,x,y,polygon_color)else setpixel(framebuffer,x,y,background_color)}逐點(diǎn)判斷算法的不足速度慢：幾十萬甚是幾百萬像素的多邊形內(nèi)外判斷，大量的求交、乘除運(yùn)算沒有考慮像素之間的聯(lián)系結(jié)論：逐點(diǎn)判斷算法不可?。?.3.1.1掃描線算法

一個(gè)多邊形與若干掃描線

2.3.1多邊形的掃描轉(zhuǎn)換2.3.1.1掃描線算法基本思想：按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。對(duì)于一條掃描線填充過程可以分為四個(gè)步驟：求交排序配對(duì)填色多邊形掃描轉(zhuǎn)換算法P0P1P2P3P4P5P6P7xy掃描轉(zhuǎn)換示意圖相鄰像素之間的連貫性掃描線算法充分利用了相鄰像素之間的連貫性，避免了對(duì)像素的逐點(diǎn)判斷和求交運(yùn)算，提高了算法效率各種連貫性的定義區(qū)域連貫性掃描線連貫性邊的連貫性區(qū)域連貫性區(qū)域的連貫性是指多邊形定義的區(qū)域內(nèi)部相鄰的像素具有相同的性質(zhì)。例如具有相同的顏色

區(qū)域的連貫性區(qū)域連貫性兩條掃描線之間的長方形區(qū)域被所處理的多邊形分割成若干梯形(三角形可以看作退化梯形)梯形的底邊為掃描線，梯形的腰為多邊形的邊或窗口邊緣區(qū)域的連貫性區(qū)域連貫性梯形分為兩類：多邊形內(nèi)部和多邊形外部?jī)深愄菪卧诙噙呅蝺?nèi)部相間排列(相鄰的兩個(gè)梯形必然有一個(gè)位于多邊形內(nèi)部，有一個(gè)在多邊形外部)區(qū)域的連貫性區(qū)域連貫性推論：如果上述梯形屬于多邊形內(nèi)(外)，那么該梯形內(nèi)所有點(diǎn)的均屬于多邊形內(nèi)(外)。效率提高的根源：逐點(diǎn)判斷區(qū)域判斷掃描線連貫性區(qū)域連貫性在一條掃描線上的反映掃描線的連貫性掃描線連貫性交點(diǎn)序列：掃描線與多邊形的交點(diǎn)個(gè)數(shù)為偶數(shù)(1,2,3,4,5,6)紅色區(qū)間(1,2)、(3,4)、(5,6)位于多邊形內(nèi)部其余綠色區(qū)間位于多邊形外部?jī)深悈^(qū)間相間排列掃描線的連貫性掃描線連貫性推論：如果上述交點(diǎn)區(qū)間屬于多邊形內(nèi)(外)，那么該區(qū)間內(nèi)所有點(diǎn)均屬于多邊形內(nèi)(外)。效率提高的根源：逐點(diǎn)判斷區(qū)間判斷邊的連貫性邊的連貫性：直線的線性性質(zhì)在光柵上的表現(xiàn)邊的連貫性1(x1,y1)2(x2,y2)11(x11,y11)22(x22,y22)掃描線與邊的交點(diǎn)邊的連貫性相鄰掃描線(y1=y11+1)與多邊形的同一條邊的交點(diǎn)存在如下關(guān)系：當(dāng)知道掃描線與一條邊的一個(gè)交點(diǎn)之后，通過上述公式可以通過增量算法迅速求出其他交點(diǎn)邊的連貫性邊的連貫性推論：邊的連貫性是連接區(qū)域連貫性和掃描線連貫性的紐帶。掃描線連貫性“＋”邊連貫性“＝”區(qū)域連貫性2.3.1.1掃描線算法掃描線與多邊形的頂點(diǎn)或邊界相交時(shí)，必須進(jìn)行正確的交點(diǎn)取舍。只需檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的y值。按這兩個(gè)y值中大于交點(diǎn)y值的個(gè)數(shù)是0,1,2來決定。123P1P2P3P4P6P5P72.3.1.1掃描線算法數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)內(nèi)容x：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)△x：從當(dāng)前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線號(hào)ymax207P6P1A△xymax3.5-1.57P5P6B△xymax728P4P5C△xymax2.3.1.1掃描線算法數(shù)據(jù)結(jié)構(gòu)新邊表（NET）：存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點(diǎn)為ymin，則該邊就放在掃描線ymin的新邊表中上圖所示各條掃描線的新邊表NET76P4P5P5P6543210P1P2P2P385-3253320711085285-1.57P6P1P3P42.3.1.1掃描線算法數(shù)據(jù)結(jié)構(gòu)活性邊表(AET)：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中2073.5-1.57P6P1P5P6AB7281108P4P5P3P4CD△xymax△xymax△xymax△xymax2.3.1.1掃描線算法假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的x坐標(biāo)為x，則下一條掃描線與該邊的交點(diǎn)不要重計(jì)算，只要加一個(gè)增量△x。設(shè)該邊的直線方程為：ax+by+c=0；若y＝y(tǒng)i，x=xi；則當(dāng)y=yi+1時(shí)，其中為常數(shù)，并約定a=0時(shí)，。算法過程voidpolyfill(polygon,color)intcolor;多邊形polygon;{for(各條掃描線i) {初始化新邊表頭指針NET[i]；把ymin=i的邊放進(jìn)邊表NET[i];}y=最低掃描線號(hào)；初始化活性邊表AET為空；for(各條掃描線i){

算法過程把新邊表NET[i]中的邊結(jié)點(diǎn)用插入排序法插入AET表，使之按x坐標(biāo)遞增順序排列；遍歷AET表，把配對(duì)交點(diǎn)區(qū)間(左閉右開)上的象素(x,y)，用drawpixel(x,y,color)改寫象素顏色值；i++;遍歷AET表，把ymax=i的結(jié)點(diǎn)從AET表中刪除，并把ymax>i結(jié)點(diǎn)的x值遞增x；}}/*polyfill*/思考題已知多邊形P=(P0P1P2P3P4P5P6P0)；其各邊坐標(biāo)分別為[（2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2）]建立其新邊表和活性邊表新邊表y=3y=8活動(dòng)邊表的例子掃描線算法小結(jié)建立新邊表按照掃描線順序處理每條掃描線構(gòu)造活性邊表（x遞增插入排序）中間考慮交點(diǎn)取舍根據(jù)當(dāng)前活性邊表選取像素進(jìn)行填充（x方向）從活性邊表中刪除ymax=i的結(jié)點(diǎn)2.3.1.2邊界標(biāo)志算法基本思想：幀緩沖器中對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對(duì)多邊形邊界所經(jīng)過的象素打上標(biāo)志。填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。Inside的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。邊標(biāo)志算法---例子多邊形P0P1P2P3P4頂點(diǎn)坐標(biāo)為（2,1）,(2,7),(8,5),(8,1),(6,4),以掃描線Y=3為例說明填充過程。開始時(shí)inside=0.1）對(duì)于X=0，該像素未置成邊界值，inside=0，該點(diǎn)為背景色；2）對(duì)于X=1，同上；3）對(duì)于X=2，該像素已置成邊界色，inside取反后為1，該點(diǎn)被置成多邊形顏色；4）對(duì)于X=3，4，像素未置成邊界色，由于inside=1，所以點(diǎn)被置成多邊形顏色；5）對(duì)于X=5，像素被置成邊界色，inside取反后為0，該點(diǎn)被置成背景色；6）對(duì)于X=6，像素未置成邊界色，由于inside=0，所以點(diǎn)被置成背景色；7）對(duì)于X=7，像素被置成邊界色，inside取反后為1，該點(diǎn)被置成多邊形顏色；8）對(duì)于X=8，像素被置成邊界色，inside取反后為0，該點(diǎn)被置成背景色；算法過程voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對(duì)多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；for(每條與多邊形polydef相交的掃描線y){inside=FALSE;for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}}2.3.1.2邊界標(biāo)志算法用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。2.3.2區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的。2.3.2區(qū)域填充算法區(qū)域表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色2.3.2區(qū)域填充算法區(qū)域填充要求區(qū)域是連通的連通性:4連通、8連通4連通：8連通2.3.2區(qū)域填充算法4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對(duì)邊界有要求對(duì)邊界的要求A：適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，oldcolor為G的原色?，F(xiàn)取(x,y)為種子點(diǎn)對(duì)區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為newcolor，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。步驟如下：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作：（1）棧頂象素出棧；（2）將出棧象素置成多邊形色；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。2.3.2.1區(qū)域填充的遞歸算法

（種子填充算法）種子填充算法——例子多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示

2.3.2.1區(qū)域填充的遞歸算法內(nèi)點(diǎn)表示的4連通區(qū)域的遞歸填充算法:voidFloodFill4(intx,inty,intoldcolor,intnewcolor){if(getpixel(x,y)==oldcolor)//屬于區(qū)域內(nèi)點(diǎn)oldcolor { drawpixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor);}}2.3.2.1區(qū)域填充的遞歸算法邊界表示的4連通區(qū)域的遞歸填充算法:voidBoundaryFill4(intx,inty,intboundarycolor,intnewcolor){intcolor=getpixel(x,y); if(color!=newcolor&&color!=boundarycolor) { drawpixel(x,y,newcolor); BoundaryFill4(x,y+1,boundarycolor,newcolor); BoundaryFill4(x,y-1,boundarycolor,newcolor); BoundaryFill4(x-1,y,boundarycolor,newcolor); BoundaryFill4(x+1,y,boundarycolor,newcolor);}}該算法也可以填充有孔區(qū)域。

缺點(diǎn)：(1)有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2)遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。改進(jìn)算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線填充算法2.3.2.1區(qū)域填充的遞歸算法2.3.2.2區(qū)域填充的掃描線算法目標(biāo)：減少遞歸層次適用于內(nèi)點(diǎn)表示的4連通區(qū)域算法步驟：首先填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個(gè)過程，直到填充結(jié)束。2.3.2.2區(qū)域填充的掃描線算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點(diǎn)：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。掃描線算法分析（舉例分析）該算法也可以填充有孔區(qū)域。

像素中的序號(hào)標(biāo)指它所在區(qū)段位于堆棧中的位置掃描線算法分析（舉例分析）掃描線算法分析（舉例分析）掃描線算法分析（舉例分析）多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較聯(lián)系：都是光柵圖形面著色，用于真實(shí)感圖形顯示?？上嗷マD(zhuǎn)換。多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充問題：當(dāng)給定多邊形內(nèi)一點(diǎn)為種子點(diǎn)，并用Bresenham或DDA算法將多邊形的邊界表示成八連通區(qū)域后，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換；若已知給定多邊形的頂點(diǎn)，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。

多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較不同點(diǎn)：1.基本思想不同；前者是頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，后者只改變區(qū)域內(nèi)填充顏色，沒有改變表示方法。2.對(duì)邊界的要求不同前者只要求掃描線與多邊形邊界交點(diǎn)個(gè)數(shù)為偶數(shù)。后者：區(qū)域封閉，防止遞歸填充跨界。3.基本的條件不同前者：從邊界頂點(diǎn)信息出發(fā)。后者：區(qū)域內(nèi)種子點(diǎn)。第二章光柵圖形學(xué)2.1直線段的掃描轉(zhuǎn)換算法2.2圓弧的掃描轉(zhuǎn)換算法2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充2.4字符2.5裁剪2.6反走樣2.7消隱2.4字符字符指數(shù)字、字母、漢字等符號(hào)。計(jì)算機(jī)中字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)。國際上最流行的字符集：“美國信息交換用標(biāo)準(zhǔn)代碼集”，簡(jiǎn)稱ASCII碼。它是用7位二進(jìn)制數(shù)進(jìn)行編碼表示128個(gè)字符；包括字母、標(biāo)點(diǎn)、運(yùn)算符以及一些特殊符號(hào)。漢字編碼的國家標(biāo)準(zhǔn)字符集：GB2312－80。該字符集分為94個(gè)區(qū)，94個(gè)位，每個(gè)符號(hào)由一個(gè)區(qū)碼和一個(gè)位碼共同標(biāo)識(shí)。區(qū)碼和位碼各用一個(gè)字節(jié)表示。為了能夠區(qū)分ASCII碼與漢字編碼，采用字節(jié)的最高位來標(biāo)識(shí)：最高位為0表示ASCII碼；最高位為1表示表示漢字編碼。

字庫：為了在顯示器等輸出設(shè)備上輸出字符，系統(tǒng)中必須裝備有相應(yīng)的字庫。字庫中存儲(chǔ)了每個(gè)字符的形狀信息，字庫分為矢量型和點(diǎn)陣型兩種。點(diǎn)陣字符:每個(gè)字符由一個(gè)位圖表示，該位為1表示字符的筆畫經(jīng)過此位，對(duì)應(yīng)于此位的象素應(yīng)置為字符顏色。該位為0表示字符的筆畫不經(jīng)過此位，對(duì)應(yīng)于此位的象素應(yīng)置為背景顏色。點(diǎn)陣字符點(diǎn)陣字庫中的位圖表示在實(shí)際應(yīng)用中，有多種字體（如宋體、楷體等），每種字體又有多種大小型號(hào)，因此字庫的存儲(chǔ)空間是很龐大的。解決這個(gè)問題一般采用壓縮技術(shù)。點(diǎn)陣字符的顯示分為兩步。首先從字庫中將它的位圖檢索出來。然后將檢索到的位圖寫到幀緩沖器中。矢量字符:記錄字符的筆畫信息，而不是整個(gè)位圖，具有存儲(chǔ)空間小，美觀、變換方便等優(yōu)點(diǎn)。對(duì)于字符的旋轉(zhuǎn)、縮放等變換，點(diǎn)陣字符的變換需要對(duì)表示字符位圖中的每一象素進(jìn)行；矢量字符的變換只要對(duì)其筆畫端點(diǎn)進(jìn)行變換就可以了。矢量字符的顯示也分為兩步。

顯示：首先從字庫中將它的字符信息。然后取出端點(diǎn)坐標(biāo)，對(duì)其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點(diǎn)的標(biāo)志顯示出字符。

點(diǎn)陣字符點(diǎn)陣字庫中的位圖表示矢量輪廓字符特點(diǎn)：點(diǎn)陣字符：存儲(chǔ)量大，易于顯示矢量字符：存儲(chǔ)量小，美觀，變換方便;但 需要光柵化后才能顯示。字符屬性字體 宋體仿宋體

楷體

黑體隸書字高宋體

宋體

宋體

宋體字寬字傾斜角 傾斜傾斜對(duì)齊(左對(duì)齊、中心對(duì)齊、右對(duì)齊)字色紅色、綠色、藍(lán)色

2.5裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過程稱為裁剪。

在使用計(jì)算機(jī)處理圖形信息時(shí)，計(jì)算機(jī)內(nèi)部存儲(chǔ)的圖形往往比較大，而屏幕顯示的只是圖的一部分。

問：為什么要裁減，直接處理呢？即：在繪制（寫幀緩存時(shí)）再處理？

最簡(jiǎn)單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點(diǎn)之后，再判斷各點(diǎn)是否在窗內(nèi)。但那樣太費(fèi)時(shí)，一般不可取。這是因?yàn)橛行﹫D形組成部分全部在窗口外，可以完全排除，不必進(jìn)行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。2.5.1直線段裁剪直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。2.5.1.1Cohen-Sutherland2.5.1.2中點(diǎn)分割算法2.5.1.3梁友棟－Barskey算法。2.5.1.1Cohen-Sutherland裁剪基本思想：對(duì)于每條線段P1P2分為三種情況處理分為三種情況處理:（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2簡(jiǎn)稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡(jiǎn)稱“棄”之。（3）若線段不滿足“取”或“棄”的條件，則在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。為快速判斷，采用如下編碼方法：每個(gè)區(qū)域賦予4位編碼編碼線段裁剪若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取”若P1P2明顯在窗口外,code1&code2≠0（？），則“棄”在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。

計(jì)算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點(diǎn) if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}示例編碼的思想在圖形學(xué)中非常重要。Sutherland：Coons獎(jiǎng),圖靈獎(jiǎng),IEEE計(jì)算機(jī)先驅(qū)獎(jiǎng)。2.5.1.2中點(diǎn)分割裁剪算法基本思想：與前一種Cohen-Sutherland算法一樣首先對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況:全在、完全不在和線段和窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。求線段與窗口的交點(diǎn)

A、B分別為距P0、P1最近的可見點(diǎn)，Pm為P0P1中點(diǎn)從出發(fā)找最近可見點(diǎn)的方法先求出的中點(diǎn)若不是顯然不可見的，并且在窗口中有可見部分，則距最近的可見點(diǎn)一定落在上，所以用代替；否則取代替再對(duì)新的求中點(diǎn)。重復(fù)上述過程，直到長度小于給定的控制常數(shù)為止，此時(shí)收斂于交點(diǎn)。從出發(fā)找最近可見點(diǎn)采用上面類似方法。問：算法為什么可行？會(huì)不會(huì)無限循環(huán)、不斷二分？2.5.1.3梁友棟－Barsky算法梁-Barsky算法的幾何含義：入邊、出邊與端點(diǎn)*寫入圖形學(xué)教科書的唯一中國人的算法*CommunicationofACM的論文梁有棟教授的二三事Liang-Barsky算法幾何連續(xù)理論：葉、馬、鄭從幾何學(xué)與纖維纏繞理論到基因工程參數(shù)化形式寫出裁剪條件：可以統(tǒng)一表示為形式：

入邊出邊=0且<0，則線段完全在邊界外，≥0，則該線段平行于裁剪邊界并且在窗口內(nèi)。當(dāng)≠0，當(dāng)<0,線段從裁剪邊界延長線的外部延伸到內(nèi)部。當(dāng)>0,線段從裁剪邊界延長線的內(nèi)部延伸到外部。對(duì)于每條直線，可以計(jì)算出參數(shù)u1和u2，它們定義了在裁剪矩形內(nèi)的線段部分u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（p<0）。對(duì)這些邊界計(jì)算rk=qk/pk。u1取0和各個(gè)rk值之中的最大值。u2的值由線段從內(nèi)到外遇到的矩形邊界所決定（p>0）。對(duì)這些邊界計(jì)算rk=qk/pk。u2取1和各個(gè)rk值之中的最小值。如果u1>u2，則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個(gè)值u1,u2計(jì)算出來。voidLB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatx1,y1,x2,y2,XL,XR,YB,YT;{ floatdx,dy,u1,u2;

u1=0;u2=1; dx=x2-x1;dy=y2-y1;if(ClipT(-dx,x1-XL,&u1,&u2)if(ClipT(dx,XR-x1,&u1,&u2)if(ClipT(-dy,y1-YB,&u1,&u2)if(ClipT(dy,YT-y1,&u1,&u2){ displayline(x1+u1*dx,y1+u1*dy,x1+u2*dx,y1+u2*dy) return; }}boolClipT(p,q,u1,u2)floatp,q,*u1,*u2;{floatr;if(p<0){ r=q/p; if(r>*u2)returnFALSE; elseif(r>*u1) { *u1=r; returnTRUE; }}。。。//下頁elseif(p>0){ r=p/q; if(r<*u1)returnFALSE; elseif(r<*u2){ *u2=r;returnTRUE;}}elseif(q<0)returnFALSE;returnTRUE;}裁減的插曲：汪嘉業(yè)的快速算法80年代的裁減熱：應(yīng)道寧(工程圖學(xué)研究所)、汪國昭（圖形圖像研究所）對(duì)三種算法比較:Cohen-Sutherland與中點(diǎn)法在區(qū)域碼測(cè)試階段能以位運(yùn)算方式高效率地進(jìn)行，因而當(dāng)大多數(shù)線段能夠簡(jiǎn)單的取舍時(shí)，效率較好。梁友棟—Barskey算法只能應(yīng)用于矩形窗口的情形，但其效率比前兩者要高，這是因?yàn)檫\(yùn)算只涉及到參數(shù)，僅到必要時(shí)才進(jìn)行坐標(biāo)計(jì)算。2.5.2多邊形裁剪基本思想是一次用窗口的一條邊裁剪多邊形。考慮窗口的一條邊以及延長線構(gòu)成的裁剪線

該線把平面分成兩個(gè)部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點(diǎn)S、P。它們與裁剪線的位置關(guān)系只有四種對(duì)于情況