第1章光柵圖形學(xué)

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

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

計(jì)算機(jī)圖形學(xué)基礎(chǔ)光柵圖形學(xué)的研究內(nèi)容直線段的掃描轉(zhuǎn)換算法圓弧的掃描轉(zhuǎn)換算法多邊形的掃描轉(zhuǎn)換與區(qū)域填充字符裁剪反走樣消隱計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.1直線段的掃描轉(zhuǎn)換算法直線的掃描轉(zhuǎn)換:確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進(jìn)行寫操作。三個常用算法：數(shù)值微分法（DDA）中點(diǎn)畫線法Bresenham算法。計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.1.1數(shù)值微分(DDA)法基本思想

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

從的左端點(diǎn)開始，向右端點(diǎn)步進(jìn)。步長=1(個象素)，計(jì)算相應(yīng)的y坐標(biāo)；取象素點(diǎn)(x,round(y))作為當(dāng)前點(diǎn)的坐標(biāo)。計(jì)算機(jī)圖形學(xué)基礎(chǔ)作為最底層的光柵圖形算法，在通常的CAD/圖形系統(tǒng)中，會被大量應(yīng)用，因此，哪怕節(jié)約一個加法或減法，也是很了不起的改進(jìn)。由此出發(fā)點(diǎn)，導(dǎo)致增量算法的思想。計(jì)算機(jī)圖形學(xué)基礎(chǔ)計(jì)算當(dāng)時; 即：當(dāng)x每遞增1，y遞增k(即直線斜率)；

計(jì)算機(jī)圖形學(xué)基礎(chǔ)例：畫直線段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)表示象素計(jì)算機(jī)圖形學(xué)基礎(chǔ)voidDDALine(intx0,inty0,intx1,inty1,intcolor,CDC*pdc)

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

pdc->SetPixel(x,int(y+0.5),color); y=y+k;

計(jì)算機(jī)圖形學(xué)基礎(chǔ)問題：當(dāng)k

1時，會如何？計(jì)算機(jī)圖形學(xué)基礎(chǔ)注意上述分析的算法僅適用于k

≤1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng)k

1時，必須把x，y地位互換k<1示意圖計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.1.2中點(diǎn)畫線法

采用增量思想的DDA算法，每計(jì)算一個象素，只需計(jì)算一個加法，是否最優(yōu)？如非最優(yōu)，如何改進(jìn)？目標(biāo)：進(jìn)一步將一個加法改為一個整數(shù)加法。新思路－>DDA算法采用點(diǎn)斜式，可否采用其他的直線表示方式？計(jì)算機(jī)圖形學(xué)基礎(chǔ)基本思想當(dāng)前象素點(diǎn)為(xp,yp)。下一個象素點(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應(yīng)為下一個象素點(diǎn)；M在Q的上方，應(yīng)取P1為下一點(diǎn)。計(jì)算機(jī)圖形學(xué)基礎(chǔ)構(gòu)造判別式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1,b=x1-x0,c=x0y1-x1y0當(dāng)d<0，M在L(Q點(diǎn))下方，取右上方P2為下一個象素；當(dāng)d>0，M在L(Q點(diǎn))上方，取右方P1為下一個象素；當(dāng)d=0，選P1或P2均可，約定取P1為下一個象素；計(jì)算機(jī)圖形學(xué)基礎(chǔ)但這樣做，每一個象素的計(jì)算量是4個加法，兩個乘法?！吧礁F水盡疑無路”如果也采用增量算法呢？d是xp,yp的線性函數(shù)，因此可采用增量計(jì)算，提高運(yùn)算效率。計(jì)算機(jī)圖形學(xué)基礎(chǔ)若當(dāng)前象素處于d0情況，則取正右方象素P1(xp+1,yp),要判下一個象素位置，應(yīng)計(jì)算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量為a若d<0時，則取右上方象素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計(jì)算機(jī)圖形學(xué)基礎(chǔ)至此，至少新算法可以和DDA算法一樣好。能否再做改進(jìn)？能否實(shí)現(xiàn)整數(shù)運(yùn)算？計(jì)算機(jī)圖形學(xué)基礎(chǔ)畫線從(x0,y0)開始，d的初值 d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b=a+0.5b?？梢杂?d代替d來擺脫小數(shù)，提高效率。令d0=2a+b,d1=2a,d2=2a+2b,我們有如下算法。計(jì)算機(jī)圖形學(xué)基礎(chǔ)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*/計(jì)算機(jī)圖形學(xué)基礎(chǔ)例：用中點(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

計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.1.3Bresenham算法基本思想DDA算法采用點(diǎn)斜式，中點(diǎn)法采用隱式表示。中點(diǎn)法可以有整數(shù)算法。其他表示可以推出整數(shù)算法嗎？計(jì)算機(jī)圖形學(xué)基礎(chǔ)過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后根據(jù)誤差項(xiàng)的符號確定該列象素中與此交點(diǎn)最近的象素。計(jì)算機(jī)圖形學(xué)基礎(chǔ)設(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≥1，就把它減去1，這樣保證d在0、1之間。當(dāng)d≥0.5時，最接近于當(dāng)前象素的右上方象素（）而當(dāng)d<0.5時，更接近于右方象素（）。為方便計(jì)算，令e＝d-0.5，e的初值為-0.5，增量為k。當(dāng)e≥0時，取當(dāng)前象素（xi，yi）的右上方象素（）；而當(dāng)e<0時，更接近于右方象素（）。計(jì)算機(jī)圖形學(xué)基礎(chǔ)可以改用整數(shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號，因此可作如下替換：例：Line:P0(0,0),P1(5,2)k=dy/dx=0.4xye00-0.510-0.1210.331-0.3420.152-0.5大于零，y加一，小于零，不變計(jì)算機(jī)圖形學(xué)基礎(chǔ)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;}}}計(jì)算機(jī)圖形學(xué)基礎(chǔ)最終，Bresenham算法也是每個象素，需一個整數(shù)算法，其優(yōu)點(diǎn)是可以用于其他二次曲線。至此，直線光柵化是否終結(jié)？計(jì)算機(jī)圖形學(xué)基礎(chǔ)另一種方法voidBresenhamLine(intx0,inty0,intx1,inty1,longcolor)

{

intx,y,dx,dy;

floatk,e;

dx=x1-x0；

dy=y1-y0；

e=-0.5；

x=x0；

y=y0；

if(dx==0)

{

for(i=0；i≤dy；i++)

{

DrawPixel(x,y+i,color)；//畫像素（x,y+i）

}

return;

}

k=dy/dx;

for(i=0；i≤dx；i++)

{

DrawPixel(x,y,color)；//畫像素（x,y）

x++；

e+=k;

if(e≥0)

{

y++；

e--；

}

}

}

計(jì)算機(jī)圖形學(xué)基礎(chǔ)改進(jìn)算法（e1=2e*dx)voidBresenhamLine(intx0,inty0,intx1,inty1,longcolor)

{

intx,y,dx,dy;

floatk,e;

dx=x1-x0；

dy=y1-y0；

e=-dx;

x=x0；

y=y0；

if(dx==0)

{

for(i=0；i≤dy；i++)

{

DrawPixel(x,y+i,color)；//畫像素（x,y+i）

}

return;

}

for(i=0；i≤dx；i++)

{

DrawPixel(x,y,color)；//畫像素（x,y）

x++；

e+=e+2*dy；

if(e≥0)

{

y++；

e-＝2*dx；

}

}

}

計(jì)算機(jī)圖形學(xué)基礎(chǔ)新方法：BRDC:binaryrepresentationofdisplacementcodeforlineMiaoLF,LiuXG,PengQS,BaoHJCOMPUTERS&GRAPHICS-UK26(3):401-408JUN2002計(jì)算機(jī)圖形學(xué)基礎(chǔ)在VC++或者C++Build中的實(shí)現(xiàn)1.在VC++中的實(shí)現(xiàn)代碼2.在C++Build中的實(shí)現(xiàn)代碼計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.2圓弧的掃描轉(zhuǎn)換算法圓的特征:八對稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個圓弧的象素集。因此，只要求出圓弧的八分之一，其他的就相應(yīng)地求出。中點(diǎn)畫圓法考慮中心在原點(diǎn)，半徑為R的第二個8分圓，構(gòu)造判別式（圓方程）計(jì)算機(jī)圖形學(xué)基礎(chǔ)若d<0,則取P1為下一象素，而且再下一象素的判別式為若d>=0,則應(yīng)取P2為下一象素，而且下一象素的判別式為第一個象素是（0,R），判別式d的初始值為計(jì)算機(jī)圖形學(xué)基礎(chǔ)為了進(jìn)一步提高算法的效率，可以將上面的算法中的浮點(diǎn)數(shù)改寫成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫圓法。使用e=d-0.25代替de0=1-R計(jì)算機(jī)圖形學(xué)基礎(chǔ)算法過程MidPointCircle(intrintcolor){ intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);//顯示圓弧上的八個對稱點(diǎn)while(x<=y){ if(d<0) d+=2*x+3; else{d+=2*(x-y)+5;y--;}x++;circlepoints(x,y,color); }}計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。多邊形的掃描轉(zhuǎn)換:把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域填充:指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程。計(jì)算機(jī)圖形學(xué)基礎(chǔ)多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.3.1多邊形的掃描轉(zhuǎn)換2.3.1.1掃描線算法基本思想：按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。對于一條掃描線填充過程可以分為四個步驟：求交排序配對填色計(jì)算機(jī)圖形學(xué)基礎(chǔ)

一個多邊形與若干掃描線

計(jì)算機(jī)圖形學(xué)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)活性邊表(AET)：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個鏈表中結(jié)點(diǎn)內(nèi)容x：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)△x：從當(dāng)前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線號ymax計(jì)算機(jī)圖形學(xué)基礎(chǔ)新邊表（NET）：

存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點(diǎn)為ymin，則該邊就放在掃描線ymin的新邊表中 上圖所示各條掃描線的新邊表NET計(jì)算機(jī)圖形學(xué)基礎(chǔ)假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的x坐標(biāo)為x，則下一條掃描線與該邊的交點(diǎn)不要重計(jì)算，只要加一個增量△x。設(shè)該邊的直線方程為：ax+by+c=0；若y＝y(tǒng)i，x=xi；則當(dāng)y=yi+1時，其中為常數(shù)計(jì)算機(jī)圖形學(xué)基礎(chǔ)掃描線與多邊形的頂點(diǎn)或邊界相交時，必須正確的交點(diǎn)的取舍。只需檢查頂點(diǎn)的兩條邊的另外兩個端點(diǎn)的y值。按這兩個y值中大于交點(diǎn)y值的個數(shù)是0,1,2來決定。計(jì)算機(jī)圖形學(xué)基礎(chǔ)算法過程voidpolyfill(polygon,color)intcolor;多邊形polygon;{for(各條掃描線i) {初始化新邊表頭指針NET[i]；把ymin=i的邊放進(jìn)邊表NET[i];}y=最低掃描線號；初始化活性邊表AET為空；for(各條掃描線i){

計(jì)算機(jī)圖形學(xué)基礎(chǔ)把新邊表NET[i]中的邊結(jié)點(diǎn)用插入排序法插入AET表，使之按x坐標(biāo)遞增順序排列；遍歷AET表，把配對交點(diǎn)區(qū)間(左閉右開)上的象素(x,y)，用drawpixel(x,y,color)改寫象素顏色值；遍歷AET表，把ymax=i的結(jié)點(diǎn)從AET表中刪除，并把ymax>i結(jié)點(diǎn)的x值遞增x；若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；}}/*polyfill*/計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.3.1.2邊界標(biāo)志算法基本思想：幀緩沖器中對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的象素打上標(biāo)志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個區(qū)段著上所需顏色。使用一個布爾量inside來指示當(dāng)前點(diǎn)是否在多邊形內(nèi)的狀態(tài)。計(jì)算機(jī)圖形學(xué)基礎(chǔ)算法過程voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}計(jì)算機(jī)圖形學(xué)基礎(chǔ)用軟件實(shí)現(xiàn)時，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。計(jì)算機(jī)圖形學(xué)基礎(chǔ)2.3.2區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的計(jì)算機(jī)圖形學(xué)基礎(chǔ)種子填充算法

種子填充算法又稱為邊界填充算法。其基本思想是：從多邊形區(qū)域的一個內(nèi)點(diǎn)開始，由內(nèi)向外用給定的顏色畫點(diǎn)直到邊界為止。如果邊界是以一種顏色指定的，則種子填充算法可逐個像素地處理直到遇到邊界顏色為止。

種子填充算法常用四連通域和八連通域技術(shù)進(jìn)行填充操作。

從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，通過上、下、左、右四個方向到達(dá)區(qū)域內(nèi)的任意像素。用這種方法填充的區(qū)域就稱為四連通域；這種填充方法稱為四向連通算法。

從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，通過上、下、左、右、左上、左下、右上和右下八個方向到達(dá)區(qū)域內(nèi)的任意像素。用這種方法填充的區(qū)域就稱為八連通域；這種填充方法稱為八向連通算法。

一般來說，八向連通算法可以填充四向連通區(qū)域，而四向連通算法有時不能填充八向連通區(qū)域。例如，八向連通填充算法能夠正確填充如圖2.4a所示的區(qū)域的內(nèi)部，而四向連通填充算法只能完成如圖2.4b的部分填充。計(jì)算機(jī)圖形學(xué)基礎(chǔ)

a)連通域及其內(nèi)點(diǎn)計(jì)算機(jī)圖形學(xué)基礎(chǔ)4向連通區(qū)域和8向連通區(qū)域

四個方向運(yùn)動八個方向運(yùn)動四連通區(qū)域八連通區(qū)域計(jì)算機(jī)圖形學(xué)基礎(chǔ)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);}}計(jì)算機(jī)圖形學(xué)基礎(chǔ)四向連通填充算法：

a）種子像素壓入棧中；

b）如果棧為空，則轉(zhuǎn)e)；否則轉(zhuǎn)c)；

c）彈出一個像素，并將該像素置成填充色；并判斷該像素相鄰的四連通像素是否為邊界色或已經(jīng)置成多邊形的填充色，若不是，則將該像素壓入棧；

d）轉(zhuǎn)b）；

e）結(jié)束。

四向連通填充方法可以用遞歸函數(shù)實(shí)現(xiàn)如下：計(jì)算機(jī)圖形學(xué)基礎(chǔ)voidBoundaryFill4(intx,inty,longFilledColor,longBoundaryColor)

{

longCurrentColor;

CurrentColor=GetPixelColor(x,y);

if(CurrentColor!=BoundaryColor&&CurrentColor!=FilledColor)

{

SetColor(FilledColor);

SetPixel(x,y);

BoundaryFill4(x+1,y,FilledColor,BoundaryColor);

BoundaryFill4(x-1,y,FilledColor,BoundaryColor);

Bo