資源描述：
《計算機(jī)圖形學(xué) 5.5裁剪算法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、5.5裁剪算法5.1.1線段裁剪算法5.1.2多邊形裁剪算法確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形,這個選擇過程稱為裁剪。該顯示區(qū)被稱為裁剪窗口。5.5.1線段裁剪算法假設(shè)矩形窗口的左下角坐標(biāo)為(xL,yB),右上角坐標(biāo)為(xR,yT)，則點P(x,y)在窗口內(nèi)的條件是：(xL,yB)(xR,yT)P點的位置是裁剪中最基本的問題否則，P點就在窗口外。滿足：xL<=x<=xR和yB<=y<=yT直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為
2、直線段的裁剪問題。常用的線段裁剪方法Cohen-Sutherland、中點分割算法、梁友棟－barskey算法。5.5.1線段裁剪算法快速判斷情形(1)(2)，對于情形(3)，設(shè)法減少求交次數(shù)和每次求交時所需的計算量。abc裁剪線段與窗口的關(guān)系：(1)線段完全可見；(2)顯然不可見；(3)線段至少有一端點在窗口之外，但非顯然不可見。如何提高裁剪效率？線段裁剪有多種算法，但基本思想都是：（1）線段是否全不在窗口內(nèi)，是則結(jié)束。（2）線段是否全在窗口內(nèi)，是則顯示該線段，結(jié)束。（3）計算該線段與窗口邊界延長線的交點，以此將線段分成兩部分；
3、丟棄不可見的部分；對剩下的部分轉(zhuǎn)（2）。它又稱為Sutherland-Cohen分割線算法.5.5.1.1Cohen-Sutherland端點編碼算法將矩形窗口的四邊分別延長后，得到九個區(qū)域，每一個區(qū)域都用一個四位二進(jìn)制數(shù)標(biāo)識，直線的端點都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來標(biāo)識出端點相對于裁剪矩形邊界的位置。1.線段的端點編碼它是最早最流行的裁剪算法,可以擴(kuò)展為三維裁剪.區(qū)域碼為：上下右左XXXX任何位賦值為1，代表端點落在相應(yīng)的位置上，否則該位為0。這一編碼的特點是對于窗口的某一條邊外側(cè)的三個區(qū)域的四位編碼中有一位全為1。線段的
4、端點編碼10011000101000010101001001100100yxyTyBxLxB0000上下右左P1 □□□□Y=YTP2Y=YBP4P3X=XLX=XR線段的各端點編碼？對于三維裁剪,需要6位編碼。(1010)(1001)P3：0110P1:1001 P4：&1010P2:&001000100000(0110)(0010)一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。所以得到一個規(guī)律：否則，在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。
5、若P1P2明顯在窗口外：code1&code2≠0，則“棄”若P1P2完全在窗口內(nèi)：code1=0,且code2=0,則“取”(1)若線段P1P2兩端點的四位編碼均為0,則兩端點均在窗口內(nèi),該線段完全可見,顯示該線段,算法結(jié)束;P6P5P2P1P4P3Cohen-Sutherland端點編碼算法(3)若線段兩端點的四位編碼按位“與”結(jié)果為0,找到P1P2在窗口外的一個端點P1(或P2),用窗口相應(yīng)的邊與P1P2的交點取代該端點P1（或P2）,返回(1)步。(2)若線段P1P2兩端點的四位編碼按位“與”結(jié)果為非0,則該線段完全不可見
6、,算法結(jié)束。裁剪一條線段時，先求出端點p1和p2的編碼code1和code2，然后(1)若code1
7、code2=0，對直線段應(yīng)簡取之。(2)若code1&code2≠0，對直線段可簡棄之。(3)若上述兩條件均不成立。則需求出直線段與窗口邊界的交點。在交點處把線段一分為二，其中必有一段完全在窗口外，可以棄之。再對另一段重復(fù)進(jìn)行上述處理，直到該線段完全被舍棄或者找到位于窗口內(nèi)的一段線段為止。4.求交：假定直線的端點坐標(biāo)為(x1,y1)和(x2,y2) ???(1)左、右邊界交點的計算：y=y1+k(x－x1)；(2)上、下邊界交點的
8、計算：x=x1+(y－y1)/k。Cohen-Sutherland端點編碼算法特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。優(yōu)點：簡單，易于實現(xiàn)。如何求窗口邊界與線段P1P2的交點?計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點Code代表線段某個端點的編碼。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
9、!=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);}如何判定線段應(yīng)該與窗口的哪條邊求交呢？編碼中對應(yīng)位為1的窗
