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

《計算機圖形學(xué)裁剪算法詳解》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、裁剪算法詳解???在使用計算機處理圖形信息時，計算機內(nèi)部存儲的圖形往往比較大，而屏幕顯示的只是圖的一部分。因此需要確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。最簡單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點之后，再判斷各點是否在窗內(nèi)。但那樣太費時，一般不可取。這是因為有些圖形組成部分全部在窗口外，可以完全排除，不必進行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。(a)裁剪前??????????????????(b)裁剪后圖1.1多邊形裁剪1直線段

2、裁剪???直線段裁剪算法比較簡單，但非常重要，是復(fù)雜圖元裁剪的基礎(chǔ)。因為復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。常用的線段裁剪方法有三種：Cohen-Sutherland,中點分割算法和梁友棟－barskey算法。1.1Cohen-Sutherland裁剪???該算法的思想是：對于每條線段P1P2分為三種情況處理。（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2簡稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡稱“棄”之。（3）若線段既不滿足“取”的條件，也不滿足

3、“棄”的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。???為使計算機能夠快速判斷一條直線段與窗口屬何種關(guān)系，采用如下編碼方法。延長窗口的邊，將二維平面分成九個區(qū)域。每個區(qū)域賦予4位編碼CtCbCrCl.其中各位編碼的定義如下：圖1.2多邊形裁剪區(qū)域編碼圖5.3線段裁剪???裁剪一條線段時，先求出P1P2所在的區(qū)號code1,code2。若code1=0,且code2=0，則線段P1P2在窗口內(nèi)，應(yīng)取之。若按位與運算code1&code2≠0，則說明兩個端點同在窗口

4、的上方、下方、左方或右方?？膳袛嗑€段完全在窗口外，可棄之。否則，按第三種情況處理。求出線段與窗口某邊的交點，在交點處把線段一分為二，其中必有一段在窗口外，可棄之。在對另一段重復(fù)上述處理。在實現(xiàn)本算法時，不必把線段與每條窗口邊界依次求交，只要按順序檢測到端點的編碼不為0，才把線段與對應(yīng)的窗口邊界求交。Cohen-Sutherland裁減算法#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8intencode(floatx,floaty){intc=0;?if(

5、x

6、=LEFT;?if(x>XR)c

7、=RIGHT;?if(x

8、=BOTTOM;?if(x

9、=TOP;?retrunc;}void?CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatx1,y1,x2,y2,XL,XR,YB,YT;//(x1,y1)(x2,y2)為線段的端點坐標，其他四個參數(shù)定義窗口的邊界{intcode1,code2,code;?code1=encode(x1,y1);?code2=encode(x2,y2);?while(co

10、de1!=0

11、

12、code2!=0)?{if(code1&code2!=0)return;???code=code1;???if(code1==0)code=code2;???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=x

13、1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){y=YT;?x=x1+(x2-x1)*(YT-y1)/(y2-y1);}????if(code==code1){?x1=x;y1=y;code1=encode(x,y);}else{x2=x;y2=y;code2=encode(x,y);}?}?displayline（x1,y1,x2,y2);}1.2中點分割裁剪算法???中點分割算法的大意是，與前一種Cohen-Sutherland算法一樣首先對線段端點進行編碼

14、，并把線段與窗口的關(guān)系分為三種情況:全在、完全不在和線段和窗口有交。對前兩種情況，進行一樣的處理。對于第三種情況，用中點分割的方法求出線段與窗口的交點。即從p0點出發(fā)找出距p0最近的可見點A和從p1點出發(fā)找出距p1最近的可見點B，兩個可見點之間的連線即為線段p0p1的可見部分。從p0出發(fā)找最近可見點采用中點分割方法：先求出p0p1的中點pm,若p0pm不是顯然不可見的，并且p0p1在窗口中有可見部分，則距p0最近