第03章2-基于光柵掃描轉(zhuǎn)換的二維圖元生成算法

1、第3章 基于光柵掃描的二維圖元生成算法第二部分在許多應(yīng)用中，面對一張大的畫面，或者是由于實(shí)際需要，或者是顯示屏幕有限，常要求在一個(gè)矩形區(qū)域內(nèi)指定要顯示的部分畫面。這種用來指定圖形顯示內(nèi)容的矩形區(qū)域稱為裁剪窗口。窗口內(nèi)的圖形被顯示出來了，而窗口之外的圖形則被裁剪掉。從圖形的顯示過程知道，任何圖形在顯示之前都要經(jīng)過裁剪工作。因此圖形的裁剪和圖形的變換一樣，直接影響圖形系統(tǒng)的效率。裁剪的方法很多，效率的高低常與計(jì)算機(jī)圖形硬件水平及圖形復(fù)雜程度有關(guān)，要根據(jù)實(shí)際情況來選擇合適的裁剪算法裁剪的基本目的是判斷這個(gè)圖形元素是否落在窗口區(qū)域之內(nèi)，如落在區(qū)域之內(nèi)則進(jìn)一步求出位于區(qū)域之內(nèi)的部分。因此裁剪處理的基礎(chǔ)有

2、兩個(gè)方面：一是圖元在窗口區(qū)域內(nèi)外的判別，二是圖形元素與窗口的求交。 裁剪可以對掃描轉(zhuǎn)換之后的點(diǎn)陣圖形在設(shè)備坐標(biāo)系中進(jìn)行，也可以在世界坐標(biāo)系中對掃描轉(zhuǎn)換之前的參數(shù)表示的圖形進(jìn)行。前者算法簡單，但效率不高，因?yàn)闊o論圖形落在窗口的內(nèi)部還是外部，都要掃描轉(zhuǎn)換，它一般適用于求交難度較大的圖形。而后者主要應(yīng)用于點(diǎn)、線、多邊形等簡單圖元。由于世界坐標(biāo)系一般為浮點(diǎn)坐標(biāo)系，故有時(shí)也稱世界坐標(biāo)系中的裁剪為分析裁剪，它是大多數(shù)圖形系統(tǒng)所采用的裁剪方法窗口：由用戶坐標(biāo)系定義的一個(gè)矩形區(qū)域；視口：由設(shè)備坐標(biāo)系定義的一個(gè)矩形區(qū)域；當(dāng)把用戶坐標(biāo)系中的圖形在圖形設(shè)備上輸出時(shí)，可以定義適當(dāng)?shù)拇翱诤鸵暱?，使窗口的圖形在視口內(nèi)顯示

3、，處于窗口外或視口外的圖形則不被顯示即稱被裁剪掉。固定視口而改變窗口，就可以在視口中觀察到用戶描述的全部圖形了視口HVLV(XV1，YV1)窗口HW(XW1，YW1)LW窗口與視口的關(guān)系用戶坐標(biāo)系設(shè)備坐標(biāo)系裁剪算法有二維的和三維的，裁剪對象可以是規(guī)則形體，也可以是不規(guī)則形體，其裁剪算法有二維的和三維的，裁剪對象可以是規(guī)則形體，也可以是不規(guī)則形體，其裁剪算法可以用硬件實(shí)現(xiàn)，也可以用軟件實(shí)現(xiàn)。裁剪算法可以用硬件實(shí)現(xiàn)，也可以用軟件實(shí)現(xiàn)。在進(jìn)行裁剪時(shí)，畫面中對應(yīng)于屏幕顯示的那部分區(qū)域也即窗口，把其定義為矩形，在進(jìn)行裁剪時(shí)，畫面中對應(yīng)于屏幕顯示的那部分區(qū)域也即窗口，把其定義為矩形，由上、下、左、右四條邊

4、圍成，即：由上、下、左、右四條邊圍成，即：( (x xL L，y yB B) )，(x(xR R，y yH H) )。裁剪的實(shí)質(zhì)就是決定圖形裁剪的實(shí)質(zhì)就是決定圖形中哪些點(diǎn)、線段、文字、以及多邊形在裁剪窗口之內(nèi)，中哪些點(diǎn)、線段、文字、以及多邊形在裁剪窗口之內(nèi)，在窗口內(nèi)的圖形被保留顯示，而窗口之外的畫面被裁去。如圖所示。在窗口內(nèi)的圖形被保留顯示，而窗口之外的畫面被裁去。如圖所示。對于點(diǎn)對于點(diǎn)( (x x，y)y)，只要判別兩對不等式：只要判別兩對不等式：x xL L x x x xR R，y yB B y y y yH H若四個(gè)不等式均成立，則點(diǎn)在窗口矩形之內(nèi)；否則，點(diǎn)在窗口矩形之外。其中若四個(gè)不

5、等式均成立，則點(diǎn)在窗口矩形之內(nèi)；否則，點(diǎn)在窗口矩形之外。其中, ,等號等號表示點(diǎn)位于窗口的邊界上。表示點(diǎn)位于窗口的邊界上。Cohen-Sutherland算法有時(shí)也稱為編碼算法，該算法分為三個(gè)步驟：第一步：判別線段兩端是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進(jìn)入第二步第二步：判別線段是否為顯然不可見，即線段的兩端點(diǎn)均落在窗口某邊所在直線的外側(cè)，如果是，則裁剪結(jié)束；否則進(jìn)入第三步第三步：求線段與窗口邊延長線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，舍棄。對余下的另一段重新進(jìn)行第一步、第二步判斷，直至結(jié)束。整個(gè)裁剪過程可以看作一個(gè)遞歸過程。為了實(shí)現(xiàn)這個(gè)算法，首先用窗口四條邊所在的直

6、線將整個(gè)二維平面分成9個(gè)區(qū)域，如圖3-36。每個(gè)區(qū)域賦予一個(gè)四位的編碼CtCbCrCl，其中各位編碼的含義如下：其他當(dāng)01maxyyCt其他當(dāng)01minyyCb其他當(dāng)01maxxxCr其他當(dāng)01minxxCl如圖是各個(gè)區(qū)的編碼的十進(jìn)制數(shù)。判斷線段的一個(gè)端點(diǎn)是否在窗口內(nèi)部，只需判斷它的編碼值是否為0。注意到編碼中各個(gè)位的含義，當(dāng)兩個(gè)端點(diǎn)的編碼的邏輯“與”非0時(shí)，它們必然落在窗口某邊的外側(cè)，也即線段為顯然不可見的線段端點(diǎn)編碼實(shí)例線段端點(diǎn)編碼實(shí)例兩個(gè)端點(diǎn)“邏輯與”操作的語義是兩個(gè)“端點(diǎn)都怎么樣”對既非完全可見，又非顯然不可見的線段，如圖3-38中的AD，需要進(jìn)行求交運(yùn)算。求交前實(shí)現(xiàn)要測試線段和窗口哪

7、條邊所在直線有交，這只要判斷線段兩端點(diǎn)編碼中各位的值即可。如圖中的AD，D點(diǎn)編碼中的Cl=1，而A點(diǎn)編碼中的Cl=0，則知道AD和窗口的左邊所在直線有交。在程序中，求交測試的順序是固定的。不妨假定求交測試的順序?yàn)榇翱诘淖筮?、上邊、右邊、下邊。按照這個(gè)順序，線段EJ和窗口四邊被求出的交點(diǎn)順序?yàn)镕、I、H、G。從而在Cohen-Sutherland裁剪算法中，最壞的情況下，一條線段在裁剪時(shí)需要求交四次int LineClip(CPoint &posBeg, CPoint &posEnd, CRect rect)int accept,done;char c0,c1,code;int

8、x0,y0,x1,y1,x,y;double m;accept=0;/線段可見標(biāo)志done=0;/裁剪完成標(biāo)志x0=m_posBeg.x;y0=m_posBeg.y;x1=m_posEnd.x;y1=m_posEnd.y;c0=GetCSCode(x0,y0,rect);/返回線段起點(diǎn)的編碼c1=GetCSCode(x1,y1,rect);/返回線段終點(diǎn)的編碼 while(!done) if(!c0 & !c1)/線段完全可見 posBeg.x=x0;posBeg.y=y0; posEnd.x=x1;posEnd.y=y1; accept=1; done=1; else if(c0&a

9、mp;c1)/線段完全不可見 posBeg.x=0;posBeg.y=0; posEnd.x=0;posEnd.y=0; accept=0; done=1; else/處理非完全可見又非顯然不可見的情況 if(c0)/首點(diǎn)不可見。Code=首點(diǎn) code=c0;（code指向不可見的那一方） else/首點(diǎn)可見，code=終點(diǎn) code=c1; if(code&0 x01)/線段與窗口的左邊有交 x=rect.left; m=(double)(y1-y0)/(double)(x1-x0); y=y0+(int)(x-x0)*m); else if(code&0 x08)/線段與

10、窗口的上邊有交 y=rect.top; m=(double)(x1-x0)/(double)(y1-y0); x=x0+(int)(y-y0)*m); else if(code&0 x02)/線段與窗口的右邊有交 x=rect.right; m=(double)(y1-y0)/(double)(x1-x0); y=y0+(int)(x-x0)*m); else if(code&0 x04)/線段與窗口的下邊有交 y=rect.bottom; m=(double)(x1-x0)/(double)(y1-y0); x=x0+(int)(y-y0)*m); if(code=c0) x

11、0=x;y0=y; c0=GetCSCode(x0,y0,rect); else x1=x;y1=y; c1=GetCSCode(x1,y1,rect); return accept;Char GetCSCode(int x, int y, CRect rt)char code=0;if(xrt.right)/編碼為*1*code=code|0 x02;else/編碼為*0*code=code&0 xfd; if(yrt.top)/編碼為1*code=code|0 x08; else/編碼為0*code=code&0 xf7; return code;在圖中的b線段，檢查端點(diǎn)編

12、碼可知它既不是完全可見段，也不是完全不可見段，則在中點(diǎn)Pm1處將b分為二段，兩段的情況仍然相同。先不考慮P1Pm1，在Pm2處將Pm1P2分為二段從圖中可見，Pm1Pm2完全可見，而Pm2P2部分可見。這樣處理的結(jié)果將導(dǎo)致線段的可見部分被劃分成一系列的可見小段然后再逐段畫出，顯然效率降低。求P1最遠(yuǎn)可見點(diǎn)的算法：1) 若P2在窗口內(nèi)，則P2就是離P1最遠(yuǎn)的可見點(diǎn)，結(jié)束該算法，否則進(jìn)行下一步;2) 若P1P2為完全不可見，則結(jié)束該算法， 否則進(jìn)行下一步；3) 取P1P2中點(diǎn)Pm，若Pm點(diǎn)在窗口內(nèi)部，則處理PmP2線段來尋找P1的最遠(yuǎn)可見點(diǎn)，即用Pm代替P1，執(zhí)行2，否則P2用Pm代替，執(zhí)行2。直

13、到Pm與線段端點(diǎn)的距離達(dá)到分辯率精度為止。在光柵顯示系統(tǒng)中，常常需要顯示輸出具有連續(xù)色彩的圖形區(qū)域，圖形區(qū)域一般由多邊形構(gòu)成，這時(shí)就需要處理多邊形區(qū)域的裁剪問題了。通常有一種錯(cuò)覺，認(rèn)為只要把多邊形的每條邊用對直線段的裁剪方法裁剪后，就完成了對多邊形的裁剪，其實(shí)不然。在圖形學(xué)中，多邊形定義了一個(gè)封閉的二維區(qū)域，裁剪結(jié)果也應(yīng)該是一個(gè)封閉的多邊形區(qū)域。多邊形裁剪有其自身的特殊性，這種特殊性表現(xiàn)在：第一，多邊形的邊被裁剪后一般就不再封閉了，需要用窗口邊界的適當(dāng)部分來封閉它，如何確定這部分的邊界？如圖第二，一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？如圖Sutherland-Ho

14、dgman多邊形裁剪算法采用了分割處理的策略，將多邊形關(guān)于矩形窗口的裁剪分割為多邊形關(guān)于窗口四邊所在直線的裁剪。所以該算法有時(shí)也稱為逐邊裁剪算法。多邊形關(guān)于窗口四邊的裁剪是相繼進(jìn)行的，不妨假定裁剪順序?yàn)樽筮?、上邊、右邊，下邊，那么原多邊形關(guān)于窗口左邊的裁剪結(jié)果多邊形作為關(guān)于上邊裁剪的輸入多邊形，。裁剪過程是一個(gè)流水線過程，如圖假設(shè)當(dāng)前處理的多邊形的邊為SP，頂點(diǎn)S在上一輪處理過了。在情況1中，SP完全落在裁剪邊的內(nèi)側(cè)(半空間之內(nèi))，將P輸出到結(jié)果多邊形頂點(diǎn)表中；在情況2中，P點(diǎn)在外側(cè)不可見，而交點(diǎn) i 應(yīng)輸出；在情況3中，SP完全在外側(cè)，沒有輸出；在情況4中，交點(diǎn)i和P點(diǎn)都是結(jié)果多邊形的頂點(diǎn)，

15、按順序先輸出i再輸出P。從上面分析知道，裁剪結(jié)果多邊形的頂點(diǎn)由兩部分構(gòu)成，一部分是落在裁剪邊內(nèi)側(cè)的原多邊形頂點(diǎn)，一部分是多邊形的邊與裁剪邊的交點(diǎn)。只要將這兩部分頂點(diǎn)按一定的順序連接起來就得到了裁剪結(jié)果多邊形BOOL SHPolygonClip(int &k, CPoint *p, CRect rect)const int maxVertics=100;/ 最大頂點(diǎn)數(shù)目int i;CPoint pb,pe;int m=m_nVertics;CPoint *a=new CPointmaxVertics;for(i=0;im;i+) ai=m_pHeadi;/裁剪左邊pb.x=rect.le

16、ft;pb.y=rect.top;pe.x=rect.left;pe.y=rect.bottom;Clip(m,a,pb,pe);/裁剪下邊pb.x=rect.left;pb.y=rect.bottom;pe.x=rect.right;pe.y=rect.bottom;Clip(m,a,pb,pe); /裁剪右邊pb.x=rect.right;pb.y=rect.bottom;pe.x=rect.right;pe.y=rect.top;Clip(m,a,pb,pe);/裁剪上邊pb.x=rect.right;pb.y=rect.top;pe.x=rect.left; pe.y=rect.top

17、;Clip(m,a,pb,pe);k=m;for(i=0;ik;i+)pi=ai;delete a;return TRUE;/按邊裁剪多邊形，返回被某邊裁剪后的結(jié)果多邊形頂點(diǎn)數(shù)組Void Clip(int &m, CPoint *a, CPoint pb, CPoint pe)const int maxVertics=100;/ 最大頂點(diǎn)數(shù)目int i,k;CPoint p0;CPoint s,p;/線段SP的起點(diǎn)與終點(diǎn)CPoint* b=new CPointmaxVertics;/存放結(jié)果臨時(shí)頂點(diǎn)數(shù)組k=0;/開始時(shí)，結(jié)果多邊形的頂點(diǎn)數(shù)為0s=am-1;/從多邊形的第n個(gè)頂點(diǎn)開始 f

18、or(i=0;im;i+)p=ai;if(IsInsideRectangle(p,pb,pe)/點(diǎn)p在邊(pb,pe)的內(nèi)側(cè) if(IsInsideRectangle(s,pb,pe)/情況1Output(p,k,b); else/情況4p0=Intersect(s,p,pb,pe);Output(p0,k,b);Output(p,k,b); else if(IsInsideRectangle(s,pb,pe)/情況2 p0=Intersect(s,p,pb,pe); Output(p0,k,b);/情況3沒有輸出s=p; m=k; for(i=0;ipb.x)/裁剪邊為窗口的下邊if(p.y

19、=pb.y) return 1;else if(pe.xpb.x)/裁剪邊為窗口的上邊if(p.ypb.y)/裁減邊為窗口的右邊if(p.x=pb.x) return 1;else if(pe.y=pb.x) return 1;return 0;/將頂點(diǎn)p加入到多邊形頂點(diǎn)序列中去void Output(CPoint p, int &k, CPoint *a)ak.x=p.x;ak.y=p.y;k+;/求多邊形的邊SP與裁剪邊(pb,pe)的交點(diǎn)CPoint Intersect(CPoint s, CPoint p, CPoint pb, CPoint pe)CPoint p0;doub

20、le m;if(pb.y=pe.y)/水平裁剪邊p0.y=pb.y;m=(double)(p.x-s.x)/(double)(p.y-s.y);p0.x=s.x+(int)(pb.y-s.y)*m);else/豎直裁剪邊p0.x=pb.x;m=(double)(p.y-s.y)/(double)(p.x-s.x);p0.y=s.y+(int)(pb.x-s.x)*m);return p0;用Sutherland-Hodgman算法對多邊形裁剪有時(shí)會出現(xiàn)問題，比如上述算法就沒有考慮裁剪成兩個(gè)分離多邊形的情況，而只是簡單地將所有頂點(diǎn)連接，沒有得到正確的分離的多邊形。為了解決這個(gè)問題，在用窗口的一條

21、邊對多邊形進(jìn)行裁剪時(shí)要設(shè)置一個(gè)記錄，把多邊形的邊和窗口的邊相交的交點(diǎn)都記錄下來，并對交點(diǎn)進(jìn)行排序，把交點(diǎn)兩兩配對（交點(diǎn)的個(gè)數(shù)必為偶數(shù)）。如果只有兩個(gè)交點(diǎn)，則多邊形經(jīng)裁剪后仍為一個(gè)多邊形，如果有4個(gè)交點(diǎn)，則多邊形經(jīng)裁剪后成為兩個(gè)多邊形，以此類推SutherlandSutherlandHodgemanHodgeman算法解決了裁算法解決了裁剪窗口為凸多邊形窗口的問題，但一些剪窗口為凸多邊形窗口的問題，但一些應(yīng)用需要涉及任意多邊形窗口（含凹多應(yīng)用需要涉及任意多邊形窗口（含凹多邊形窗口）的裁剪。邊形窗口）的裁剪。Weiler-AthertonWeiler-Atherton多邊形裁剪算法正是滿足這種要求

22、的算多邊形裁剪算法正是滿足這種要求的算法法在算法中，裁剪窗口、被裁剪多邊形可以是任意多邊形：凸的，凹的在算法中，裁剪窗口、被裁剪多邊形可以是任意多邊形：凸的，凹的，甚至是帶有內(nèi)環(huán)的，甚至是帶有內(nèi)環(huán)的裁剪窗口和被裁剪多邊形處于完全對等的地位，這里我們稱：1、被裁剪多邊形為主多邊形，記為A；2、裁剪窗口為裁剪多邊形，記為B。主多邊形A和裁剪多邊形B的邊界將整個(gè)二維平面分成了四個(gè)區(qū)域：1、AB（交：屬于A且屬于B）；2、AB（差：屬于A不屬于B）；3、BA（差：屬于B不屬于A）；4、AB (并：屬于A或?qū)儆贐，取反；即：不屬于A且不屬于B)。 內(nèi)裁剪即通常意義上的“裁剪”，取圖元位于窗口之內(nèi)的部分，

23、結(jié)果為AB。外裁剪取圖元位于窗口之外的部分，結(jié)果為AB。觀察右圖不難發(fā)現(xiàn)裁剪結(jié)果區(qū)域的邊界由和兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生，即由被裁剪多邊形的邊界轉(zhuǎn)至裁剪窗口的邊界，或者反之。由于多邊形構(gòu)成一個(gè)封閉的區(qū)域，所以，如果被裁剪多邊形和裁剪窗口有交點(diǎn)，則交點(diǎn)成對出現(xiàn)。這些交點(diǎn)分成兩類：一類稱“”點(diǎn)，即被裁剪多邊形由此點(diǎn)進(jìn)入裁剪窗口，如圖中a、c、e；一類稱“”點(diǎn)，即被裁剪多邊形由此點(diǎn)離開裁剪窗口，如圖中b、d、f。WeilerWeilerAthertonAtherton任意多邊形裁剪算任意多邊形裁剪算法思想：法思想：算法從被裁剪多邊形的一個(gè)入點(diǎn)開始算法從被裁剪多邊形的一個(gè)入點(diǎn)開始，碰到入點(diǎn)，沿著

24、被裁剪多邊形按順時(shí)針，碰到入點(diǎn)，沿著被裁剪多邊形按順時(shí)針方向搜集頂點(diǎn)序列；方向搜集頂點(diǎn)序列；而當(dāng)遇到出點(diǎn)時(shí)，則沿著裁剪窗口按而當(dāng)遇到出點(diǎn)時(shí)，則沿著裁剪窗口按順時(shí)針方向搜集頂點(diǎn)序列。順時(shí)針方向搜集頂點(diǎn)序列。由于可能存在分裂的多邊形，因此算由于可能存在分裂的多邊形，因此算法要考慮：將搜集過的入點(diǎn)的入點(diǎn)記號刪法要考慮：將搜集過的入點(diǎn)的入點(diǎn)記號刪去，以免重復(fù)跟蹤。將所有的入點(diǎn)搜集完去，以免重復(fù)跟蹤。將所有的入點(diǎn)搜集完畢后算法結(jié)束。畢后算法結(jié)束。1、順時(shí)針輸入被裁剪多邊形頂點(diǎn)序列放入數(shù)組1中。2、順時(shí)針輸入裁剪窗口頂點(diǎn)序列放入數(shù)組2中。3、求出被裁剪多邊形和裁剪窗口相交的所有交點(diǎn)，并給每個(gè)交點(diǎn)打上“入”

25、、“出”標(biāo)記。然后將交點(diǎn)按順序插入序列得到新的頂點(diǎn)序列，并放入數(shù)組3中；同樣也將交點(diǎn)按順序插入序列得到新的頂點(diǎn)序列，放入數(shù)組4中；4、初始化輸出數(shù)組Q，令數(shù)組Q為空。接著從數(shù)組3中尋找“入”點(diǎn)。如果“入”點(diǎn)沒找到，程序結(jié)束。5、如果找到“入”點(diǎn)，則將“入”點(diǎn)放入S中暫存。6、將“入”點(diǎn)錄入到輸出數(shù)組Q中。并從數(shù)組3中將該“入”點(diǎn)的“入”點(diǎn)標(biāo)記刪去。7、沿?cái)?shù)組3順序取頂點(diǎn)：如果頂點(diǎn)不是“出點(diǎn)”，則將頂點(diǎn)錄入到輸出數(shù)組Q中，流程轉(zhuǎn)第7步。否則，流程轉(zhuǎn)第8步。8、沿?cái)?shù)組4順序取頂點(diǎn)：如果頂點(diǎn)不是“入點(diǎn)”，則將頂點(diǎn)錄入到輸出數(shù)組Q中，流程轉(zhuǎn)第8步。否則，流程轉(zhuǎn)第9步。9、如果頂點(diǎn)不等于起始點(diǎn)S，流程轉(zhuǎn)

26、第6步，繼續(xù)跟蹤數(shù)組3。否則，將數(shù)組Q輸出；流程轉(zhuǎn)第4步，尋找可能存在的分裂多邊形。算法在第4步：滿足“入”點(diǎn)沒找到的條件時(shí)，算法結(jié)束。WeilerAtherton任意多邊形裁剪算法特點(diǎn)：1. 裁剪窗口可以是矩形、任意凸多邊形、任意凹多邊形。2. 可實(shí)現(xiàn)被裁剪多邊形相對裁剪窗口的內(nèi)裁或外裁，即保留窗口內(nèi)的圖形或保留窗口外的圖形，因此在三維消隱中可以用來處理物體表面間的相互遮擋關(guān)系。3. 裁剪思想新穎，方法簡潔，裁剪一次完成，與裁剪窗口的邊數(shù)無關(guān)。當(dāng)字符或文本整個(gè)不在窗口時(shí)，則不予顯示。然而，當(dāng)字符和文本部分在窗口內(nèi)，部分在窗口外時(shí)，就提出了字符裁剪的問題。最簡單的字符裁剪方法是把字符方框（即字

27、符掩膜）與窗口比較。若整個(gè)方框位于窗口內(nèi)，則顯示對應(yīng)字符，否則不予顯示。有些應(yīng)用要求更準(zhǔn)確的處理：即使字符只有一部分在窗口內(nèi)，也要把這一部分顯示出來。若字符為點(diǎn)陣型的，只要在把字符掩膜各位寫入象素之前，先判斷該位對應(yīng)的象素是否在窗口內(nèi)，若該位在窗口內(nèi)則寫，否則就不寫。在字符為矢量型的情形，問題就更復(fù)雜一些。這時(shí)要對跨越窗口邊界的筆劃進(jìn)行裁剪，裁去筆劃伸到窗口外的部分，保留筆劃在窗口內(nèi)的部分，這個(gè)問題可以轉(zhuǎn)化為線段的裁剪。在光柵顯示器上顯示圖形時(shí)，直線段或圖形邊界或多或少會呈現(xiàn)鋸齒狀，原因是圖形信號是連續(xù)的，而在光柵顯示系統(tǒng)中，用來表示圖形的卻是一個(gè)個(gè)離散的像素。這種用離散的量來表示連續(xù)的量而引

28、起的失真，叫做走樣。用于減少或消除走樣的技術(shù)，稱為反走樣。常見的走樣現(xiàn)象有三種：階梯走樣、細(xì)節(jié)走樣、遺失走樣。所謂階梯走樣是在掃描轉(zhuǎn)換線段時(shí)，線段呈現(xiàn)階梯形狀；所謂細(xì)節(jié)走樣是指圖形在用象素顯示時(shí)會發(fā)生變大變小的現(xiàn)象；而遺失走樣則是對于過小的圖形，用象素現(xiàn)有的分辨率無法顯示的現(xiàn)象。常用的反走樣方法分為兩類 提高分辨率 區(qū)域采樣 非加權(quán)區(qū)域采樣 加權(quán)區(qū)域采樣假設(shè)將顯示器的水平和垂直分辨率都提高一倍，則同樣長度的直線段穿過的掃描線條數(shù)增加了一倍，線段上的寬度減小了一倍。這樣顯示出的直線段看起來就平直光滑了一些，達(dá)到了減少走樣的效果提高顯示系統(tǒng)的分辨率可以減小走樣的程度，方法也很簡單，但付出的代價(jià)卻非

29、常大。假設(shè)要將光柵顯示器系統(tǒng)的水平、垂直分辨率提高一倍，則顯示器的點(diǎn)距要減小一倍，幀緩存的容量要增加到原來的4倍，顯示卡和顯示器之間的傳輸帶寬度也要增加到原來的4倍，而掃描轉(zhuǎn)換同樣大小的圖元卻要花費(fèi)4倍的時(shí)間前面介紹的直線掃描轉(zhuǎn)換算法做了兩點(diǎn)假定： (1) 像素是數(shù)學(xué)上抽象的點(diǎn)，它的亮度由覆蓋該點(diǎn)的圖形的亮度所決定； (2) 直線段是數(shù)學(xué)上抽象的直線段，它的寬度為0。但實(shí)際上，象素不是一個(gè)點(diǎn)，而是一個(gè)個(gè)具有一定面積的小區(qū)域，該區(qū)域的形狀依賴于光柵顯示系統(tǒng)的硬件。直線段的寬度也不是0，在屏幕上顯示的直線段的寬度至少為一象素。算法中所假定的條件和實(shí)際情況之間的差距是造成走樣的原因之一，所以，為了減

30、少走樣，必須改變直線段模型。非加權(quán)區(qū)域采樣反混淆方法，歸納為如下幾個(gè)步驟： (1) 將直線段看作具有一定寬度的狹長矩形； (2) 當(dāng)直線段與象素有交時(shí)，求出兩者相交區(qū)域的面積； (3) 根據(jù)相交區(qū)域的面積，確定該象素的亮度值（在矩形內(nèi)占的面積越大，顏色越深）在非加權(quán)區(qū)域采用方法中，起關(guān)鍵作用的是直線段與象素相交區(qū)域的面積，如何計(jì)算這個(gè)面積呢？假設(shè)一條直線段的斜率為m，若規(guī)定它的顯示寬度為一個(gè)象素，那么直線段與象素的相交情況有三種有時(shí)為了簡化上述計(jì)算，可以通過下面的離散計(jì)算方法求出相交區(qū)域的近似面積，用這個(gè)近似的面積替代真實(shí)的面積來確定像素的顯示灰度。求相交區(qū)域的近似面積的離散計(jì)算方法：(1)

31、將屏幕像素分割成n個(gè)更小的子像素；(2) 計(jì)算中心點(diǎn)落在直線段內(nèi)的子像素的個(gè)數(shù)，記為k；(3) k/n為線段與像素相交區(qū)域面積的近似值。這樣做的目的是為了簡化計(jì)算，例如： n = 16, k = 3 近似面積 = 3/16為了實(shí)現(xiàn)反走樣，可對圖為了實(shí)現(xiàn)反走樣，可對圖形信號作含核的卷積，卷形信號作含核的卷積，卷積積分為：積積分為：c( )= h( x)y(x)dx其中其中h( x)是函數(shù)的卷積是函數(shù)的卷積核，核，y(x)是被卷積的函數(shù)是被卷積的函數(shù)，c( )是是h( x)和和y(x)的卷的卷積。積。- 例如卷積核如圖所示。例如卷積核如圖所示。然后將這一卷積核然后將這一卷積核h(x)，反射核反射核h(x)及平移核及平移核h( x)與卷積函與卷積函數(shù)數(shù)y=x相乘得結(jié)果如圖。相乘得結(jié)果如圖。卷積核、反射核及平移核的表卷積核、反射核及平移核的表達(dá)式為：達(dá)式為：h(x)y(x) 0,2-0.50.5-1211故有故有 c( )= h( x)y(x)dx0 1 = h( x)y(x)dx = h( x)y(x)dx1 2代入：代入：h( x)1 ，y(x)=x有有 c( )= (1) (x)dx= 2/2 0 1 = xdx = /2 (2 ) 1 2若若y(x)的斜率為的斜率為m，則結(jié)果為則結(jié)果為m 2/2及及m /2 (2 )