計算機圖形學 55裁剪算法

1、5.5 5.5 裁剪算法裁剪算法 5.1.1 5.1.1 線段裁剪算法線段裁剪算法 5.1.2 5.1.2 多邊形裁剪算法多邊形裁剪算法 確定圖形中哪些部分落在顯示區(qū)之內，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內的那部分圖形,這個選擇過程稱為裁剪裁剪。該顯示區(qū)被稱為裁剪窗口裁剪窗口。5.5.1 線段裁剪算法線段裁剪算法 假設矩形窗口的左下角坐標為(xL,yB),右上角坐標為(xR,yT)，則點P(x,y)在窗口內的條件是：(x(xL L,y,yB B ) )(x(xR R,y,yT T ) )P點的位置點的位置是裁剪中最基本的問題是裁剪中最基本的問題否則，P點就在窗口外。滿足： xL = x

2、 = xR 和 yB = y = yTl 直線段裁剪算法是復雜圖形裁剪的基礎。復雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。l 常用的線段裁剪方法 Cohen-Sutherland、 中點分割算法、 梁友棟barskey算法。5.5.1 線段裁剪算法線段裁剪算法快速判斷情形(1)(2)，對于情形(3)，設法減少求交次數(shù)和每次求交時所需的計算量。abc裁剪線段與窗口的關系：裁剪線段與窗口的關系：(1) 線段完全可見；(2) 顯然不可見；(3) 線段至少有一端點在窗口之外，但非顯然不可見。如何提高裁剪效率？如何提高裁剪效率？ 線段裁剪有多種算法，但基本思想都是：（1）線段

3、是否全不在窗口內，是則結束。（2）線段是否全在窗口內，是則顯示該線段，結束。（3）計算該線段與窗口邊界延長線的交點，以此將線段分成兩部分；丟棄不可見的部分；對剩下的部分轉（2）。它又稱為Sutherland-Cohen分割線算法.5.5.1.1 Cohen-Sutherland 端點編碼算法將矩形窗口的四邊分別延長后，得到九個區(qū)域，每一個區(qū)域都用一個四位二進制數(shù)標識，直線的端點都按其所處區(qū)域賦予相應的區(qū)域碼，用來標識出端點相對于裁剪矩形邊界的位置。1.1.線段的端點編碼線段的端點編碼 它是最早最流行的裁剪算法, 可以擴展為三維裁剪. 區(qū)域碼為：區(qū)域碼為： 上上 下下 右右 左左 X X X X

4、X X X X任何位賦值為任何位賦值為1 1，代表端點落在相應的位置上，否，代表端點落在相應的位置上，否則該位為則該位為0 0。這一編碼的這一編碼的特點特點是對于窗口的某一條是對于窗口的某一條邊外側的三個區(qū)域的四位編碼中有一位全為邊外側的三個區(qū)域的四位編碼中有一位全為1。線段的端點編碼線段的端點編碼100110001010000101010010011001000000 上上 下下 右右 左左 P1 Y=YT P2 Y=YBP4P3X=XL X=XR線段的各端點編碼？線段的各端點編碼？對于三維裁剪對于三維裁剪,需要需要6位編碼。位編碼。(1010)(1001) P3： 0110 P1: 100

5、1 P4：& 1010 P2:& 0010 0010 0000 (0110)(0010) 一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內，哪條直線完全在窗口外。所以得到一個規(guī)律： 否則，在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。若P1P2明顯在窗口外外：code1&code20，則“棄棄”若P1P2完全在窗口內內：code1=0,且code2=0,則“取取”(1)若線段若線段P1P2兩端點的四位編碼均為兩端點的四位編碼均為0,則兩端點均在窗口內則兩端點均在窗口內,該線段完全可見該線段完全可見,顯示該線段顯示該

6、線段,算法結束算法結束; P6P5P2P1P4P3Cohen-Sutherland端點編碼算法(3)若線段兩端點的四位編碼按位若線段兩端點的四位編碼按位“與與”結果為結果為0, 找到找到P1P2在窗口外的一個端點在窗口外的一個端點P1(或或P2),用窗口相應的邊與用窗口相應的邊與P1P2的交的交點取代該端點點取代該端點P1（或（或P2）, 返回返回(1)步。步。(2) 若線段若線段P1P2兩端點的四位編碼按位兩端點的四位編碼按位“與與”結果為非結果為非0,則則該線段完全不可見該線段完全不可見,算法結束。算法結束。裁剪一條線段時，先求出端點裁剪一條線段時，先求出端點p1和和p2的編碼的編碼cod

7、e1和和code2，然后然后 (1)若若code1|code2=0，對直線段應簡取之。，對直線段應簡取之。 (2)若若code1&code20，對直線段可簡棄之。，對直線段可簡棄之。 (3)若上述兩條件均不成立。則需求出直線段與窗口邊界若上述兩條件均不成立。則需求出直線段與窗口邊界的交點。在交點處把線段一分為二，其中必有一段完全在窗的交點。在交點處把線段一分為二，其中必有一段完全在窗口外，可以棄之。再對另一段重復進行上述處理，直到該線口外，可以棄之。再對另一段重復進行上述處理，直到該線段完全被舍棄或者找到位于窗口內的一段線段為止。段完全被舍棄或者找到位于窗口內的一段線段為止。 4.求交

8、：假定直線的端點坐標為求交：假定直線的端點坐標為(x1, y1)和和(x2, y2) (1)左、右邊界交點的計算：左、右邊界交點的計算：y=y1+k(xx1)； (2)上、下邊界交點的計算：上、下邊界交點的計算：x=x1+(yy1)/k。 Cohen-Sutherland端點編碼算法特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。優(yōu)點：簡單，易于實現(xiàn)。如何求窗口邊界與線段如何求窗口邊界與線段P1P2的交點的交點? 計算線段計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點與窗口邊界的交點CodeCode代表線段某個端點的編碼。代表線段某個端點的編碼。if(LEFT&co

9、de !=0)if(LEFT&code !=0) x=XL;x=XL; y=y1+(y2-y1)y=y1+(y2-y1)* *(XL-x1)/(x2-x1);(XL-x1)/(x2-x1);else if(RIGHT&code !=0)else if(RIGHT&code !=0) x=XR;x=XR; y=y1+(y2-y1)y=y1+(y2-y1)* *(XR-x1)/(x2-x1);(XR-x1)/(x2-x1);else if(BOTTOM&code !=0)else if(BOTTOM&code !=0) y=YB;y=YB; x=x1+(x2

10、-x1)x=x1+(x2-x1)* *(YB-y1)/(y2-y1);(YB-y1)/(y2-y1); else if(TOP & code !=0) else if(TOP & code !=0) y=YT;y=YT; x=x1+(x2-x1)x=x1+(x2-x1)* *(YT-y1)/(y2-y1);(YT-y1)/(y2-y1);如何判定線段應該與窗口的哪條邊求交呢？如何判定線段應該與窗口的哪條邊求交呢？編碼中對應位為編碼中對應位為1的窗口邊。的窗口邊。P1：(-3/2, 1/6)；編碼；編碼 (0001)P2：(1/2, 3/2)；編碼；編碼 (1000)(2) 求右

11、邊交點，得求右邊交點，得 P1(1, 11/6) P2(-1, 1/2)； 并編碼，并編碼， 判別之不可見判別之不可見(1) 求左邊交點，得求左邊交點，得P1P2; P1:(-1,1/2); 編碼編碼(0000) 判別知非完全可見，且判別知非完全可見，且P1在窗口內，在窗口內， 因此交換因此交換P1P2得新線段得新線段P1P2； P1：(1/2, 3/2)；編碼；編碼 (1000)P2：(-1, 1/2)； 編碼編碼 (0000)(3) 求上邊交點，得求上邊交點，得 P1(-1/4, 1) P2(-1, 1/2)； 并編碼，并編碼， 兩端點編碼全部為兩端點編碼全部為0， 線段完全可見，程序結束

12、線段完全可見，程序結束P1P1P1x=x1+(y-y1)*(x2-x1)/(y2-y1)y=y1+(x-x1)*(y2-y1)/(x2-x1)多邊形的裁剪多邊形的裁剪多邊形的裁剪多邊形的裁剪 對多邊形的裁剪對多邊形的裁剪不等于把多邊形的每一條邊進行不等于把多邊形的每一條邊進行裁剪裁剪。 因為在圖形學中，多邊形被認為是一個封閉的區(qū)因為在圖形學中，多邊形被認為是一個封閉的區(qū)域，它把平面分為多邊形內和多邊形外。域，它把平面分為多邊形內和多邊形外。 (a)(a)裁剪前裁剪前(b)(b)直接采用直線段直接采用直線段裁剪的結果裁剪的結果多邊形的裁剪多邊形的裁剪 對一個多邊形的對一個多邊形的裁剪結果仍要求是

13、多邊形，裁剪結果仍要求是多邊形，且原來是多邊且原來是多邊形內的點也在裁剪后的多邊形內。形內的點也在裁剪后的多邊形內。 一部分窗口的邊界可能成為裁剪后的多邊形的邊界，一個一部分窗口的邊界可能成為裁剪后的多邊形的邊界，一個凹多邊形裁剪后可能成為幾個多邊形。凹多邊形裁剪后可能成為幾個多邊形。 多邊形裁剪算法的輸出應該是定義裁剪后的多邊形邊界的多邊形裁剪算法的輸出應該是定義裁剪后的多邊形邊界的頂點序列。于是，需要構造能產(chǎn)生一個或多個封閉區(qū)域的多頂點序列。于是，需要構造能產(chǎn)生一個或多個封閉區(qū)域的多邊形裁剪算法。邊形裁剪算法。(c)(c)正確的裁剪結果正確的裁剪結果對多邊形裁剪的對多邊形裁剪的Suther

14、land-Hodgman算法是一種算法是一種簡便的方法，只要對多邊形用窗口的四條邊依次裁簡便的方法，只要對多邊形用窗口的四條邊依次裁剪四次，便可得到裁剪后的多邊形。剪四次，便可得到裁剪后的多邊形。 Sutherland-Hodgman Sutherland-Hodgman算法算法5.1 .2 Sutherland-Hodgman逐次多邊形裁剪算法逐次多邊形裁剪算法Sutherland-HodgmanSutherland-Hodgman基本基本思想思想基本思想：是一次用窗口的一條邊裁剪多邊形?？紤]窗口的一條邊以及延長線構成的裁剪線該線把平面分成兩個部分:可見一側；不可見一側多邊形的各條邊的兩端點

15、S、P。它們與裁剪線的位置關系只有四種：可見一側可見一側可見一側可見一側SpSSSppp(1)(2)(3)(4)Sutherland-Hodgman基本思想基本思想假設當前處理的邊為SP,頂點S在上一輪中已經(jīng)處理。對于情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點P可見一側可見一側可見一側可見一側SpSSSppp(1)(2)(3)(4)是否第一點是否第一點?取點取點PSP和和e相交？相交？計算計算SP和和e的交點的交點I輸出輸出IS PF PS在在e的可見側的可見側退出退出輸出輸出S(a)(a) Sutherland-Hodgman Sutherland-Hodgman算法的框圖算法的框圖是是是是否否是是否否否否設封閉多邊形的頂點為設封閉多邊形的頂點為P1,P2,P1,P2,PnPn，框圖中，框圖中e e是表示窗口是表示窗口的四條邊中正在裁剪的一條邊，的四條邊中正在裁剪的一條邊，每次裁剪時每次裁剪時第一個點存放在第一個點存放在F F中，中，以便對最后一條邊裁剪時使用。以便對最后一條邊裁剪時使用。 用圖（用圖（a a）中的算法對邊）中的算法對邊P P1 1P P2 2, ,P P2 2P P3 3, , P Pn-1n-1P Pn n作裁剪。作裁剪。圖圖(a)用圖（用圖