計(jì)算機(jī)圖形學(xué)裁剪算法詳解

1、裁剪算法詳解在使用計(jì)算機(jī)處理圖形信息時(shí)，計(jì)算機(jī)部存儲(chǔ)的圖形往往比較大，而屏幕顯 示的只是圖的一部分。因此需要確定圖形中哪些部分落在顯示區(qū)之， 哪些落在顯 示區(qū)之外，以便只顯示落在顯示區(qū)的那部分圖形。 這個(gè)選擇過(guò)程稱為裁剪。最簡(jiǎn) 單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點(diǎn)之后，再判斷各點(diǎn)是否在窗。但那樣太 費(fèi)時(shí)，一般不可取。這是因?yàn)橛行﹫D形組成部分全部在窗口外，可以完全排除， 不必進(jìn)行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。(a)裁剪前(b)裁剪后圖1.1多邊形裁剪1直線段裁剪直線段裁剪算法比較簡(jiǎn)單，但非常重要，是復(fù)雜圖元裁剪的基礎(chǔ)。因?yàn)閺?fù)雜的曲線可以通過(guò)折線段來(lái)近似，從而裁剪問(wèn)題也可以化為直線

2、段的裁剪問(wèn)題。 常 用的線段裁剪方法有三種：Cohen-Sutherland,中點(diǎn)分割算法和梁友棟一barskey 算法。1.1 Cohen-Sutherland 裁剪該算法的思想是：對(duì)于每條線段分為三種情況處理。（1）若Pa完全在窗口，則顯示該線段RB簡(jiǎn)稱“取”之。（2）若PR明顯在窗口外，則丟棄該 線段，簡(jiǎn)稱“棄”之。（3）若線段既不滿足“取”的條件，也不滿足“棄”的 條件，則在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另 一段重復(fù)上述處理。為使計(jì)算機(jī)能夠快速判斷一條直線段與窗口屬何種關(guān)系，采用如下編碼方 法。延長(zhǎng)窗口的邊，將二維平面分成九個(gè)區(qū)域。每個(gè)區(qū)域賦予4位編碼CtC

3、bCrCl. 其中各位編碼的定義如下：圖1.2多邊形裁剪區(qū)域編碼 圖5.3線段裁剪裁剪一條線段時(shí)，先求出 P1P2所在的區(qū)號(hào)code1,code2。若code1=0，且 code2=0,則線段P1P2在窗口，應(yīng)取之。若按位與運(yùn)算 code1&code2 0,則說(shuō)明 兩個(gè)端點(diǎn)同在窗口的上方、下方、左方或右方?？膳袛嗑€段完全在窗口外，可棄 之。否則，按第三種情況處理。求出線段與窗口某邊的交點(diǎn)，在交點(diǎn)處把線段一 分為二，其中必有一段在窗口外，可棄之。在對(duì)另一段重復(fù)上述處理。在實(shí)現(xiàn)本 算法時(shí)，不必把線段與每條窗口邊界依次求交， 只要按順序檢測(cè)到端點(diǎn)的編碼不 為0,才把線段與對(duì)應(yīng)的窗口邊界求交。

4、Cohen-Sutherland 裁減算法#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8 int encode(float x,float y) int c=0;if(x<XL) c|=LEFT;if(x>XR) c|=RIGHT;if(x<YB) c|=BOTTOM;if(x<YT) c|=TOP;retrun c;void CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,y2,XL,XR,YB,YT;/(x1,y1)(x2,y2)為線段的端點(diǎn)坐

5、標(biāo)，其他四個(gè)參數(shù)定義窗口的邊界 int code1,code2,code;code1=encode(x1,y1);code2=encode(x2,y2);while(code1!=0 |code2!=0) if(code1&code2 !=0) return;code = codel;if(code1=0) code = code2;if(LEFT&code !=0) x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code !=0) x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BO

6、TTOM&code !=0) y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);else if(TOP & code !=0) y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);if(code =code1) x1=x;y1=y; codel =encode(x,y);else x2=x;y2=y; code2 =encode(x,y);displayline (x1,y1,x2,y2);1.2 中點(diǎn)分割裁剪算法中點(diǎn)分割算法的大意是，與前一種 Cohen-Sutherland算法一樣首先對(duì)線段 端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況：

7、全在、完全不在和線段和 窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。即從 p0點(diǎn)出發(fā)找出距p0最近的可見(jiàn)點(diǎn)A和從pl點(diǎn) 出發(fā)找出距pl最近的可見(jiàn)點(diǎn)B,兩個(gè)可見(jiàn)點(diǎn)之間的連線即為線段 p0p1的可見(jiàn)部 分。從p0出發(fā)找最近可見(jiàn)點(diǎn)采用中點(diǎn)分割方法： 先求出p0p1的中點(diǎn)pm,若p0pm 不是顯然不可見(jiàn)的，并且p0p1在窗口中有可見(jiàn)部分，則距p0最近的可見(jiàn)點(diǎn)一定 落在p0pm上，所以用p0pm代替p0p1;否則取pmpl代替p0p1。再對(duì)新的p0p1 求中點(diǎn)pm重復(fù)上述過(guò)程，直到pmpl長(zhǎng)度小于給定的控制常數(shù)為止，此時(shí) pm 收斂于交點(diǎn)。由于該算法的主

8、要計(jì)算過(guò)程只用到加法和除2運(yùn)算，所以特別適合硬件實(shí)現(xiàn)，同時(shí)也適合于并行計(jì)算。圖5.4 A、B分別為距p0、pl最近的可見(jiàn)點(diǎn)，Pm為p0p1中點(diǎn)1.3 梁友棟Barskey算法梁友棟和Barskey提出了更快的參數(shù)化裁剪算法。首先按參數(shù)化形式寫(xiě)出裁 剪條件:這四個(gè)不等式可以表示為形式:其中，參數(shù)pk,qk定義為：任何平行于裁剪邊界之一的直線 pk=0,其中k對(duì)應(yīng)于裁剪邊界（k=1,2,3,4 對(duì)應(yīng)于左、右、下、上邊界）如果還滿足 qk<0,則線段完全在邊界外，舍棄該線 段。如果qk>0,則該線段平行于裁剪邊界并且在窗口。當(dāng)pk<0,線段從裁剪邊界延長(zhǎng)線的外部延伸到部。當(dāng) pk&

9、gt;0,線段從裁剪邊界延 長(zhǎng)線的部延伸到外部。當(dāng)pkW0,可以計(jì)算出線段與邊界k的延長(zhǎng)線的交點(diǎn)的u 值：U=qk/p k對(duì)于每條直線，可以計(jì)算出參數(shù) u1和u2,它們定義了在裁剪矩形的線段部 分。u1的值由線段從外到遇到的矩形邊界所決定（p<0）。對(duì)這些邊界計(jì)算 rk=qk/pk。u1取0和各個(gè)rk值之中的最大值。u2的值由線段從到外遇到的矩形 邊界所決定（p>0）。對(duì)這些邊界計(jì)算rk=qk/p k o u2取1和各個(gè)rk值之中的最小 值。如果u1>u2,則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù) u的兩個(gè)值u1,u2計(jì)算出來(lái)。void LB_LineClip(

10、x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,y2,XL,XR,YB,YT; float dx,dy,u1,u2;tl=0;tu=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) retur

11、n;bool ClipT(p,q,u1,u2) float p,q,*u1,*u2; float r;if(p<0) r=q/p；if(r>*u2)return FALSE;else if(r>*u1) *u1=r;return TRUE;else if(p>0) r=p/q;if(r<*u1) return FALSE;else if(r<*u2) *u2=r;return TRUE;else if（q<0） return FALSE;return TRUE;2多邊形裁剪對(duì)于一個(gè)多邊形，可以把它分解為邊界的線段逐段進(jìn)行裁剪。但這樣做會(huì)使原來(lái)封閉的多邊

12、形變成不封閉的或者一些離散的線段。當(dāng)多邊形作為實(shí)區(qū)域考慮時(shí)，封閉的多邊形裁剪后仍應(yīng)當(dāng)是封閉的多邊形，以便進(jìn)行填充。為此，可以使 用Sutherland-Hodgman算法。該算法的基本思想是一次用窗口的一條邊裁剪多 邊形。算法的每一步，考慮窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線。該線把平面分成兩個(gè)部分：一部分包含窗口，稱為可見(jiàn)一側(cè)；另一部分稱為不可見(jiàn)一側(cè)。依序 考慮多邊形的各條邊的兩端點(diǎn) S P。它們與裁剪線的位置關(guān)系只有四種。（1）S,P均在可見(jiàn)一側(cè)（2） S,P均在不可見(jiàn)一側(cè)（3）S可見(jiàn),P不可見(jiàn)（4）S不可見(jiàn),P可見(jiàn)。圖1.3 S、P與裁剪線的四種位置關(guān)系每條線段端點(diǎn)S、P與裁剪線比較之后，

13、可輸出0至兩個(gè)頂點(diǎn)。對(duì)于情況（1） 僅輸出頂點(diǎn)P;情況（2）輸出0個(gè)頂點(diǎn)；情況（3）輸出線段SP與裁剪線的交 點(diǎn)I ;情況（4）輸出線段SP與裁剪線的交點(diǎn)I和終點(diǎn)P上述算法僅用一條裁剪邊對(duì)多邊形進(jìn)行裁剪， 得到一個(gè)頂點(diǎn)序列，作為下一 條裁剪邊處理過(guò)程的輸入。對(duì)于每一條裁剪邊，算法框圖一樣，只是判斷點(diǎn)在窗 口哪一側(cè)以及求線段SP與裁剪邊的交點(diǎn)算法應(yīng)隨之改變?；?divide and conquer 策略的 Sutherland-Hodgman 算法typedef struct float x; float y; Vertex;typedef Vertex Edge2;SutherlandHod

14、gmanClip (VertexArray InVertexArray, VertexArrayOutVertexArray, edge ClipBoundary, int &Inlength, int &Outlength Vertex s, p, ip;int j;Outlength = 0;S = InVertexArray InLength -1;For (j = 0; j < Inlength; j+)P = InVertexArray j;if(Inside (P, ClipBoundary) if(Inside (S, ClipBoundary)/SP在窗口

15、，情況 1Output(p, OutLength, OutVertex Array)else /S 在窗口外，情況4Intersect (S, P, ClipBoundary, &ip);Output (ip, OutLength, OutVertexArray);Output (P, OutLength, OutVertexArray);else if (Inside (S, WindowsBoundary)/S在窗口，P在窗口外，情況3Intersect (S, P, ClipBoundary, &ip);Output (ip, OutLength, OutVertexAr

16、ray); / 情況2沒(méi)有輸出S = P;/判點(diǎn)在窗口bool Inside (Vertex &TestPt, Edge ClipBoundary) if(ClipBoundary1.x> ClipBoundary0.x)/裁剪邊為窗 口下邊if(testpt.y>= ClipBoundary0.y)return TRUE;else if(ClipBoundary1.x< ClipBoundary0.x) /裁剪邊為窗口上邊if(testpt.y<= ClipBoundary0.y)return TRUE;else if(ClipBoundary1.y> ClipBoundary0.y) /裁剪邊為窗口右邊if(testpt.x<= ClipBoundary0.x)return TRUE;else if(ClipBoundary1.y< ClipBoundary0.y) /裁剪邊為窗口左邊if(testpt.x>= ClipBoundary0.x)return TRUE;Return FALSE;/直線段SP和窗口邊界求交，返回交點(diǎn);void Intersect (Vertex&S,Vertex &P,Edge ClipBoundary,Vertex&