計算機圖形學

計算機圖形學多媒體課件YourSiteHere洛陽理工學院計算機與信息工程系第二章光柵圖形學什么是光柵圖形學？

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

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

已知過端點的直線段L：

直線斜率為

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

例：畫直線段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)格點表示象素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;

問題：當k

1時，會如何？注意上述分析的算法僅適用于k

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

1時，必須把x，y地位互換k<1示意圖2.1.2中點畫線法

采用增量思想的DDA算法，每計算一個象素，只需計算一個加法，是否最優(yōu)？如非最優(yōu)，如何改進？目標：進一步將一個加法改為一個整數(shù)加法。新思路－>DDA算法采用點斜式，可否采用其他的直線表示方式？基本思想當前象素點為(xp,yp)。下一個象素點為P1

或P2

。設(shè)M=(xp+1,yp+0.5)，為p1與p2之中點，Q為理想直線與x=xp+1垂線的交點。將Q與M的y坐標進行比較。當M在Q的下方，則P2應(yīng)為下一個象素點；M在Q的上方，應(yīng)取P1為下一點。構(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<0，M在L(Q點)下方，取右上方P2為下一個象素；當d>0，M在L(Q點)上方，取右方P1為下一個象素；當d=0，選P1或P2均可，約定取P1為下一個象素；但這樣做，每一個象素的計算量是4個加法，兩個乘法?！吧礁F水盡疑無路”如果也采用增量算法呢？

d是xp,yp的線性函數(shù)，因此可采用增量計算，提高運算效率。若當前象素處于d0情況，則取正右方象素P1(xp+1,yp),要判下一個象素位置，應(yīng)計算

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量為a若d<0時，則取右上方象素P2(xp+1,yp+1)。要判斷再下一象素，則要計算

d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b；增量為a＋b至此，至少新算法可以和DDA算法一樣好。能否再做改進？能否實現(xiàn)整數(shù)運算？畫線從(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,我們有如下算法。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*/例：用中點畫線法

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

2.1.3Bresenham算法基本思想DDA算法采用點斜式，中點法采用隱式表示。中點法可以有整數(shù)算法。其他表示可以推出整數(shù)算法嗎？過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后根據(jù)誤差項的符號確定該列象素中與此交點最近的象素。設(shè)直線方程為：，其中k=dy/dx。因為直線的起始點在象素中心，所以誤差項d的初值d0＝0。X下標每增加1，d的值相應(yīng)遞增直線的斜率值k，即d＝d＋k。一旦d≥1，就把它減去1，這樣保證d在0、1之間。當d≥0.5時，最接近于當前象素的右上方象素（）而當d<0.5時，更接近于右方象素（

）。為方便計算，令e＝d-0.5，e的初值為-0.5，增量為k。當e≥0時，取當前象素（xi，yi）的右上方象素（

）；而當e<0時，更接近于右方象素（）。可以改用整數(shù)以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換：例：Line:P0(0,0),P1(5,2)k=dy/dx=0.4xye00-0.510-0.1210.331-0.3420.152-0.5大于零，y加一，小于零，不變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;}}}最終，Bresenham算法也是每個象素，需一個整數(shù)算法，其優(yōu)點是可以用于其他二次曲線。至此，直線光柵化是否終結(jié)？新方法：BRDC:binaryrepresentationofdisplacementcodeforlineMiaoLF,LiuXG,PengQS,BaoHJCOMPUTERS&GRAPHICS-UK26(3):401-408JUN20022.2圓弧的掃描轉(zhuǎn)換算法圓的特征:八對稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個圓弧的象素集中點畫圓法考慮中心在原點，半徑為R的第二個8分圓，構(gòu)造判別式（圓方程）若d<0,則取P1為下一象素，而且再下一象素的判別式為若d>=0,則應(yīng)取P2為下一象素，而且下一象素的判別式為第一個象素是（0,R），判別式d的初始值為為了進一步提高算法的效率，可以將上面的算法中的浮點數(shù)改寫成整數(shù)，將乘法運算改成加法運算，即僅用整數(shù)實現(xiàn)中點畫圓法。使用e=d-0.25代替de0=1-R算法過程MidPointCircle(intrintcolor){ intx,y;floatd;x=0;y=r;d=1.25-r;

circlepoints(x,y,color);//顯示圓弧上的八個對稱點

while(x<=y){ if(d<0) d+=2*x+3; else{d+=2*(x-y)+5;y--;}x++;circlepoints(x,y,color); }}2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形有兩種重要的表示方法：頂點表示和點陣表示。多邊形的掃描轉(zhuǎn)換:把多邊形的頂點表示轉(zhuǎn)換為點陣表示。區(qū)域可采用內(nèi)點表示和邊界表示兩種表示形式。區(qū)域填充:指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。2.3.1多邊形的掃描轉(zhuǎn)換2.3.1.1掃描線算法基本思想：按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。對于一條掃描線填充過程可以分為四個步驟：求交排序配對填色

一個多邊形與若干掃描線

數(shù)據(jù)結(jié)構(gòu)活性邊表(AET)：把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中結(jié)點內(nèi)容

x：當前掃描線與邊的交點坐標△x：從當前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線號ymax新邊表（NET）：

存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中 上圖所示各條掃描線的新邊表NET假定當前掃描線與多邊形某一條邊的交點的x坐標為x，則下一條掃描線與該邊的交點不要重計算，只要加一個增量△x。設(shè)該邊的直線方程為：ax+by+c=0；若y＝y(tǒng)i，x=xi；則當y=yi+1時，其中為常數(shù)掃描線與多邊形的頂點或邊界相交時，必須正確的交點的取舍。只需檢查頂點的兩條邊的另外兩個端點的y值。按這兩個y值中大于交點y值的個數(shù)是0,1,2來決定。算法過程voidpolyfill(polygon,color)

intcolor;多邊形polygon;{for(各條掃描線i) {初始化新邊表頭指針NET[i]；把ymin=i的邊放進邊表NET[i];}y=最低掃描線號；初始化活性邊表AET為空；

for(各條掃描線i){

把新邊表NET[i]中的邊結(jié)點用插入排序法插入AET表，使之按x坐標遞增順序排列；遍歷AET表，把配對交點區(qū)間(左閉右開)上的象素(x,y)，用drawpixel(x,y,color)改寫象素顏色值；遍歷AET表，把ymax=i的結(jié)點從AET表中刪除，并把ymax>i結(jié)點的x值遞增x；若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；

}}/*polyfill*/2.3.1.2邊界標志算法基本思想：幀緩沖器中對多邊形的每條邊進行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的象素打上標志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個區(qū)段著上所需顏色。使用一個布爾量inside來指示當前點是否在多邊形內(nèi)的狀態(tài)。算法過程voidedgemark_fill(polydef,color)多邊形定義polydef；

intcolor;{對多邊形polydef

每條邊進行直線掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個象素x){if(象素x被打上邊標志)inside=!(inside);if(inside！=FALSE)

drawpixel(x,y,color);elsedrawpixel(x,y,background); }}用軟件實現(xiàn)時，掃描線算法與邊界標志算法的執(zhí)行速度幾乎相同，但由于邊界標志算法不必建立維護邊表以及對它進行排序，所以邊界標志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。2.3.2區(qū)域填充算法區(qū)域指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。區(qū)域可采用內(nèi)點表示和邊界表示兩種表示形式。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。區(qū)域填充指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的4向連通區(qū)域和8向連通區(qū)域

四個方向運動八個方向運動四連通區(qū)域八連通區(qū)域2.3.2.1區(qū)域填充的遞歸算法內(nèi)點表示的4連通區(qū)域的遞歸填充算法:voidFloodFill4(intx,int

y,int

oldcolor,int

newcolor){if(getpixel(x,y)==oldcolor)//屬于區(qū)域內(nèi)點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);}}邊界表示的4連通區(qū)域的遞歸填充算法:voidBoundaryFill4(intx,int

y,int

boundarycolor,int

newcolor){intcolor; 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);}}2.3.2.2區(qū)域填充的掃描線算法算法步驟：首先填充種子點所在掃描線上的位于給定區(qū)域的一個區(qū)段然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個過程，直到填充結(jié)束。(1)初始化：堆棧置空。將種子點（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當前掃描線。(3)填充并確定種子點所在區(qū)段：從種子點（x，y）出發(fā)，沿當前掃描線向左、右兩個方向填充，直到邊界。分別標記區(qū)段的左、右端點坐標為xl和xr。(4)并確定新的種子點：在區(qū)間[xl，xr]中檢查與當前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（2）步。上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。本課總結(jié)：直線段的掃描轉(zhuǎn)換算法DDA中點算法Bresenham算法圓弧的掃描轉(zhuǎn)換算法多邊形的掃描轉(zhuǎn)換與區(qū)域填充掃描轉(zhuǎn)換區(qū)域填充2.4字符字符指數(shù)字、字母、漢字等符號。計算機中字符由一個數(shù)字編碼唯一標識。國際上最流行的字符集：“美國信息交換用標準代碼集”，簡稱ASCII碼。它是用7位二進制數(shù)進行編碼表示128個字符；包括字母、標點、運算符以及一些特殊符號。漢字編碼的國家標準字符集：GB2312－80。該字符集分為94個區(qū)，94個位，每個符號由一個區(qū)碼和一個位碼共同標識。區(qū)碼和位碼各用一個字節(jié)表示。為了能夠區(qū)分ASCII碼與漢字編碼，采用字節(jié)的最高位來標識：最高位為0表示ASCII碼；最高位為1表示表示漢字編碼。

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

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

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

楷體

黑體隸書字高宋體

宋體

宋體

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

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

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

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

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

計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點

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);}示例編碼的思想在圖形學中非常重要。Sutherland：Coons獎,圖靈獎,IEEE計算機先驅(qū)獎。2.5.1.2中點分割裁剪算法基本思想：與前一種Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線段與窗口的關(guān)系分為三種情況:全在、完全不在和線段和窗口有交。對前兩種情況，進行一樣的處理。對于第三種情況，用中點分割的方法求出線段與窗口的交點。求線段與窗口的交點

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

入邊出邊

=0且<0，則線段完全在邊界外，≥0，則該線段平行于裁剪邊界并且在窗口內(nèi)。當≠0，當<0,線段從裁剪邊界延長線的外部延伸到內(nèi)部。當>0,線段從裁剪邊界延長線的內(nèi)部延伸到外部。對于每條直線，可以計算出參數(shù)u1和u2，它們定義了在裁剪矩形內(nèi)的線段部分u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（p<0）。對這些邊界計算rk=qk/pk

。u1取0和各個rk值之中的最大值。u2的值由線段從內(nèi)到外遇到的矩形邊界所決定（p>0）。對這些邊界計算rk=qk/pk

。u2取1和各個rk值之中的最小值。如果u1>u2，則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個值u1,u2計算出來。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)道寧(工程圖學研究所)、汪國昭（圖形圖像研究所）對三種算法比較:Cohen-Sutherland與中點法在區(qū)域碼測試階段能以位運算方式高效率地進行，因而當大多數(shù)線段能夠簡單的取舍時，效率較好。梁友棟—Barskey算法只能應(yīng)用于矩形窗口的情形，但其效率比前兩者要高，這是因為運算只涉及到參數(shù)，僅到必要時才進行坐標計算。2.5.2多邊形裁剪基本思想是一次用窗口的一條邊裁剪多邊形?？紤]窗口的一條邊以及延長線構(gòu)成的裁剪線

該線把平面分成兩個部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關(guān)系只有四種對于情況（1）僅輸出頂點P情況（2）輸出0個頂點情況（3）輸出線段SP與裁剪線的交點I情況（4）輸出線段SP與裁剪線的交點I和終點P上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，只是判斷點在窗口哪一側(cè)以及求線段SP與裁剪邊的交點算法應(yīng)隨之改變。示意圖(5之1)示意圖(5之2)示意圖(5之3)示意圖(5之4)示意圖(5之5)其他窗口的裁剪圓域窗口裁剪：潛望鏡、...任意(凸)多邊形裁剪：個性化電腦顯示器定制，2.5.3字符裁剪串精度:將包圍字串的外接矩形對窗口作裁剪字符精度:將包圍字的外接矩形對窗口作裁剪以及筆畫\象素精度:將筆劃分解成直線段對窗口作裁剪待裁剪字符串 串精度裁剪 字符精度裁剪象素精度裁剪用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing)用于減少或消除這種效果的技術(shù)稱為反走樣(antialiasing)2.6.1提高分辨率2.6.2區(qū)域采樣2.6.3加權(quán)區(qū)域取樣2.6反走樣2.6.1提高分辨率把顯示器分辨率提高一倍，直線經(jīng)過兩倍的象素，鋸齒也增加一倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。增加分辨率雖然簡單，但是不經(jīng)濟的方法，有物理上的困難而且它也只能減輕而不能消除鋸齒問題2.6.2區(qū)域采樣基本思想：每個象素是一個具有一定面積的小區(qū)域，將直線段看作具有一定寬度的狹長矩形。當直線段與象素有交時，求出兩者相交區(qū)域的面積，然后根據(jù)相交區(qū)域面積的大小確定該象素的亮度值。示意圖有寬度的線條輪廓象素相交的五種情況及用于計算面積的量面積計算情況⑴（5)陰影面積為：D2/2m；情況⑵（4)陰影面積為：D-m/2；情況⑶陰影面積為：1-D2/m為了簡化計算可以采用離散的方法

n=9,k=3近似面積為1/3首先將屏幕象素均分成n個子象素，然后計算中心點落在直線段內(nèi)的子象素的個數(shù)k。將屏幕該象素的亮度置為相交區(qū)域面積的近似值可k/n。非加權(quán)區(qū)域采樣方法有兩個缺點：象素的亮度與相交區(qū)域的面積成正比，而與相交區(qū)域落在象素內(nèi)的位置無關(guān)，這仍然會導(dǎo)致鋸齒效應(yīng)。直線條上沿理想直線方向的相鄰兩個象素有時會有較大的灰度差。2.6.3加權(quán)區(qū)域取樣基本思想：使相交區(qū)域?qū)ο笏亓炼鹊呢暙I依賴于該區(qū)域與象素中心的距離當直線經(jīng)過該象素時，該象素的亮度F是在兩者相交區(qū)域A’上對濾波器（函數(shù)w）進行積分的積分值。

可采用離散計算方法 如：我們將屏幕劃分為n=3×3個子象素，加權(quán)表可以取作：權(quán)函數(shù)w（x,y）為微面元dA與象素中心距離d的函數(shù)然后求出所有中心落于直線段內(nèi)的子象素。最后計算所有這些子象素對原象素亮度貢獻之和乘以象素的最大灰度值作為該象素的顯示灰度值。2.7消隱消隱的分類消除隱藏線消除隱藏面畫家算法Z緩沖區(qū)(Z-Buffer)算法掃描線Z-buffer算法區(qū)域子分割算法光線投射算法基本概念投影變換失去了深度信息，往往導(dǎo)致圖形的二義性要消除二義性，就必須在繪制時消除被遮擋的不可見的線或面，習慣上稱作消除隱藏線和隱藏面，簡稱為消隱。經(jīng)過消隱得到的投影圖稱為物體的真實圖形。 長方體線框投影圖的二義性消隱的對象是三維物體。三維體的表示主要有邊界表示和CSG表示等。消隱結(jié)果與觀察物體有關(guān)，也與視點有關(guān)。線框圖消隱圖真實感圖形物體的表示CSG表示邊界表示(體、面、環(huán)、邊、點)2.7.1消隱的分類按消隱對象分類線消隱消隱對象是物體上的邊，消除的是物體上不可見的邊。面消隱消隱對象是物體上的面，消除的是物體上不可見的面。Southerland按消隱空間分類物體空間的消隱算法（光線投射、Roberts）將場景中每一個面與其他每個面比較，求出所有點、邊、面遮擋關(guān)系。Roberts的故事：IEEECS計算機先驅(qū)獎圖像空間的消隱算法(Z－buffer、掃描線、Warnock)對屏幕上每個象素進行判斷，決定哪個多邊形在該象素可見。物體空間和圖像空間的消隱算法(畫家算法)在物體空間中預(yù)先計算面的可見性優(yōu)先級，再在圖像空間中生成消隱圖。2.7.2消除隱藏線對造型的要求在線框顯示模型中,要求造型系統(tǒng)中有面的信息，最好有體的信息。坐標變換將視點變換到Z軸的正無窮大處，視線方向變?yōu)閆軸的負方向。最基本的運算判斷面對線的遮擋關(guān)系.反復(fù)地進行線線、線面之間的求交運算平面對直線段的遮擋判斷算法視點與線段同側(cè)包圍盒不交分段交替取值線面相交線面平行，線在面后線面交與線段外(1)若線段的兩端點及視點在給定平面的同側(cè)，線段不被給定平面遮擋，轉(zhuǎn)7(2)若線段的投影與平面投影的包圍盒無交，線段不被給定平面遮擋，轉(zhuǎn)7(3)求直線與相應(yīng)無窮平面的交。若無交點，轉(zhuǎn)4。否則，交點在線段內(nèi)部或外部。若交點在線段內(nèi)部，交點將線段分成兩段，與視點同側(cè)的一段不被遮擋，另一段在視點異側(cè)，轉(zhuǎn)4再判；若交點在線段外部，轉(zhuǎn)4。(4)求所剩線段的投影與平面邊界投影的所有交點，并根據(jù)交點在原直線參數(shù)方程中的參數(shù)值求出Z值(即深度)。若無交點，轉(zhuǎn)5。(5)以上所求得的各交點將線段的投影分成若干段，求出第一段中點。(6)若第一段中點在平面的投影內(nèi)，則相應(yīng)的段被遮擋，否則不被遮擋；其他段的遮擋關(guān)系可依次交替取值進行判斷。(7)結(jié)束。

前向面、后向面為了提高算法的效率，需要設(shè)法減少求交的工作量。若V·N>0，稱該多邊形為后向面。若V·N<0，稱該多邊形為前向面。后向面總是看不見的，不會由于后向面的遮擋，而使別的棱成為不可見的。因此計算時，可以把這些后向面全部去掉，這并不影響消隱結(jié)果。

示意圖

前向面后向面多面體的隱藏線消除

圖3中的JEAF、HCBG和DEABC所在的面均為后向面。其它為前向面。

線消隱基本數(shù)據(jù)結(jié)構(gòu)面表(存放參與消隱的面)+

線表(存放待顯示的線)算法假設(shè)E為面F的一條邊,需判別F以外每一個面與E的遮擋關(guān)系.2.7.3消除隱藏面3.3.1畫家算法（列表優(yōu)先算法）先把屏幕置成背景色，再把物體的各個面按其離視點的遠近進行排序，排序結(jié)果存在一張深度優(yōu)先級表中。然后按照從遠到近的順序逐個繪制各個面。關(guān)鍵是如何對場景中的物體按深度排序?qū)鼍爸械奈矬w按深度排序深度重疊測試.

Zmin(P)<Zmin(Q),若Zmax(P)<Zmin(Q)，則P肯定不能遮擋Q。投影重疊判斷P和Q在oxy平面上投影的包圍盒在x方向上不相交P和Q在oxy平面上投影的包圍盒在y方向上不相交P和Q在oxy平面上的投影不相交P在Q之后。P的各頂點均在Q的遠離視點的一側(cè)Q在P之前。Q的各頂點均在P的靠近視點的一側(cè)精確的重疊測試以上測試失敗，須作進一步判斷。計算時不必具體求出重疊部分。在交點處進行深度比較，只要能判斷出前后順序即可。若遇到多邊形相交或循環(huán)重疊的情況（如圖f），還必須在相交處分割多邊形，然后進行判斷。

P不遮擋Q的各種情況(ab,c,d,e)及互相遮擋f2.7.3.2Z緩沖區(qū)算法幀緩存來存放每個象素的顏色值初值可放對應(yīng)背景顏色的值深度緩存來存放每個象素的深度值。初值取成z的極小值。算法過程在把顯示對象的每個面上每一點的屬性（顏色或灰度）值填入幀緩沖器相應(yīng)單元前，要把這點的z坐標值和z緩沖器中相應(yīng)單元的值進行比較。只有前者大于后者時才改變幀緩沖器的那一單元的值，同時z緩沖器中相應(yīng)單元的值也要改成這點的z坐標值。如果這點的z坐標值小于z緩沖器中的值，則說明對應(yīng)象素已經(jīng)顯示了對象上一個點的屬性，該點要比考慮的點更接近觀察點。對顯示對象的每個面上的每個點都做了上述處理后，便可得到消除了隱藏面的圖。Z-Buffer算法（）{ 幀緩存全置為背景色 深度緩存全置為最小Z值

for(每一個多邊形) {掃描轉(zhuǎn)換該多邊形

for(該多邊形所覆蓋的每個象素(x,y)) { 計算該多邊形在該象素的深度值Z(x,y); if(Z(x,y)大于Z緩存在(x,y)的值) {把Z(x,y)存入Z緩存中(x,y)處 把多邊形在(x,y)處的顏色值存入幀緩存的(x,y)處} }}}Z-Buffer算法在象素級上以近物取代遠物。形體在屏幕上的出現(xiàn)順序是無關(guān)緊要的。這種取代方法實現(xiàn)起來遠比總體排序靈活簡單，有利于硬件實現(xiàn)。缺點：占用空間大，沒有利用圖形的相關(guān)性與連續(xù)性。只用一個深度緩存變量zb的改進算法一般認為，Z-Buffer算法需要開一個與圖象大小相等的緩存數(shù)組ZB，實際上，可以改進算法，只用一個深度緩存變量zb。算法過程z-Buffer(){ 幀緩存全置為背景色

for(屏幕上的每個象素(i,j)){ 深度緩存變量zb置最小值MinValue for(多面體上的每個多邊形Pk) { if(象素點(i,j)在pk的投影多邊形之內(nèi)) {

計算Pk在(i,j)處的深度值depth;

if(depth大于zb) { zb=depth;

indexp=k; } }}

If(zb!=MinValue)計算多邊形Pindexp在交點(I,j)處的光照顏色并顯示

}}該算法主要的計算量在何處？關(guān)鍵問題：判斷象素點(i,j)是否在pk的投影多邊形之內(nèi)計算多邊形在點（i，j）處的深度。設(shè)多邊形的平面方程為：點與多邊形的包含性檢測射線法由被測點P處向y=-方向作射線交點個數(shù)是奇數(shù)，則被測點在多邊形內(nèi)部否則，偶數(shù)，在多邊形外部。若射線正好經(jīng)過多邊形的頂點，則采用“左開右閉”的原則來實現(xiàn)。即：當射線與某條邊的頂點相交時，若邊在射線的左側(cè)，交點有效，計數(shù)；若邊在射線的右側(cè)，交點無效，不計數(shù)。如下情況又如何處理？弧長法（a）被測點p在多邊形外（b）被測點p在多邊形內(nèi)以被測點為圓心，作單位圓，計算其在單位園上弧長的代數(shù)和。代數(shù)和為0，點在多邊形外部；代數(shù)和為2，點在多邊形內(nèi)部；代數(shù)和為，點在多邊形邊上。以頂點符號為基礎(chǔ)的弧長累加方法。將坐標原點移到被測點P。各象限內(nèi)點的符號對分別為(＋,＋)，（－，＋)，(－，－)，(＋，－)。算法規(guī)定：若頂點pi的某個坐標為0,則其符號為＋。若頂點pi的x、y坐標都為0，則說明這個頂點為被測點，我們在這之前予以排除。于是弧長變化如下表。表:符號對變化與弧長變化的關(guān)系

(sxi

,syi)(sxi+!,syI+1)弧長變化 象限變化

(++) (++) 0 II (++) (-+) /2 III (++) (--) IIII (++) (+-) -/2 IIV

………...值得注意的是，當邊的終點Pi+1在起點Pi的相對象限時，弧長變化可能增加或減少。設(shè)（xi,yi）和（xi＋1,yi＋1）分別為邊的起點和終點坐標。計算若f＝0.則邊穿過坐標原點。若f>0，則弧長代數(shù)和增加，若f<0，則弧長代數(shù)和減少2.7.3.3掃描線Z-buffer算法算法思想:點Buffer,面Buffer到線Buffer利用圖形的連貫性（指深度計算）在處理當前掃描線時，開一個一維數(shù)組作為當前掃描線的Z-buffer。首先找出與當前掃描線相關(guān)的多邊形，以及每個多邊形中相關(guān)的邊對。對每一個邊對之間的小區(qū)間上的各象素，計算深度，并與Z-buffer中的值比較，找出各象素處可見平面。計算顏色，寫幀緩存。采用增量算法計算深度。數(shù)據(jù)結(jié)構(gòu)多邊形Y表：將所有多邊形存在多邊形Y表中。

根據(jù)多邊形頂點中最小的y坐標，插入多邊形Y表中的相應(yīng)位置。 多邊形Y表中只保存多邊形的序號和其頂點的最大y坐標。根據(jù)序號可以從定義多邊形的數(shù)據(jù)結(jié)構(gòu)中取多邊形信息待消隱對象

多邊形y表活化多邊形表APT:與當前掃描線相交的多邊形。APT是一個動態(tài)的鏈表邊Y表ET:活化多邊形表中的每一個多邊形都有一個邊表ET

多邊形P1的邊表ET活化邊對表AET在一條掃描線上，同一多邊形的相鄰兩條邊構(gòu)成一個邊對。活化邊表AET中存放當前多邊形中與當前掃描線相交的各邊對的信息。xl

xl

ylmax

xr

xryrmax

zlIPza

zb

(示意圖見下頁)掃描線Z-buffer算法(){ 建多邊形y表；對每一個多邊形根據(jù)頂點最小的y值，將多邊形置入多邊形y表。 活化多邊形表APT，活化邊表AET初始化為空。

For(每條掃描線i，i從小到大) { 1.幀緩存CB置為背景色。

2.深度緩存ZB(一維數(shù)組)置為無窮大。

3.將對應(yīng)掃描線i的，多邊形y表中的多邊形加入到活化多邊形表APT中。

4.對新加入的多邊形，生成其相應(yīng)的邊Y表。

5.對APT中每一個多邊形，若其邊Y表中對應(yīng)掃描線I增加了新的邊，

將新的邊配對，加到活化邊對表AET中。

6.對AET中的每一對邊：

6.1對xl<x<xr

的每一個象素，按增量公式z=z-za計算各點深度depth。

6.2與ZB中的量比較，depth<ZB(I),則令ZB(I)=depth，并計算顏色值，寫幀緩存。

7.刪除APT中，多邊形頂點最大y坐標為I的多邊形，并刪除相應(yīng)