多邊形裁剪算法第1頁，共40頁，2023年，2月20日，星期一裁剪裁剪：確定圖形中哪些部分落在顯示區之內，哪些落在顯示區之外,以便只顯示落在顯示區內的那部分圖形。這個選擇過程稱為裁剪。圖形裁剪算法，直接影響圖形系統的效率。第2頁，共40頁，2023年，2月20日，星期一點的裁剪圖形裁剪中最基本的問題。假設窗口的左下角坐標為(xL,yB),右上角坐標為(xR,yT)，對于給定點P(x,y),則P點在窗口內的條件是要滿足下列不等式：

xL<=x<=xR并且yB<=y<=yT

否則，P點就在窗口外。問題：對于任何多邊形窗口，如何判別？(xL,yB)(xR,yT)第3頁，共40頁，2023年，2月20日，星期一5.6直線段裁剪直線段裁剪算法是復雜圖形裁剪的基礎。復雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。主要的四種算法直接求交算法Cohen-Sutherland算法中點算法梁友棟－barskey算法第4頁，共40頁，2023年，2月20日，星期一5.6直線段裁剪裁剪線段與窗口的關系：(1)線段完全可見；(2)顯然不可見；(3)其它提高裁剪效率： 快速判斷情形(1)(2)， 對于情形(3)，設法減 少求交次數和每次求 交時所需的計算量。第5頁，共40頁，2023年，2月20日，星期一直接求交算法直線與窗口邊都寫成參數形式，求參數值。第6頁，共40頁，2023年，2月20日，星期一Cohen-Sutherland裁剪基本思想：對于每條線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。為快速判斷，采用如下編碼方法：第7頁，共40頁，2023年，2月20日，星期一實現方法：

將窗口邊線兩邊沿長，得到九個區域，每一個區域都用一個四位二進制數標識，直線的端點都按其所處區域賦予相應的區域碼，用來標識出端點相對于裁剪矩形邊界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪第8頁，共40頁，2023年，2月20日，星期一Cohen-Sutherland算法將區域碼的各位從右到左編號，則坐標區

域與各位的關系為：上下右左 XXXX

任何位賦值為1，代表端點落在相應的位置上，否則該位為0。若端點在剪取矩形內，區域碼為0000。如果端點落在矩形的左下角，則區域碼為0101。第9頁，共40頁，2023年，2月20日，星期一Cohen-Sutherland算法一旦給定所有的線段端點的區域碼，就可以快速判斷哪條直線完全在剪取窗口內，哪條直線完全在窗口外。所以得到一個規律：第10頁，共40頁，2023年，2月20日，星期一Cohen-Sutherland裁剪若P1P2完全在窗口內code1=0,且code2=0,則“取”若P1P2明顯在窗口外code1&code2≠0，則“棄”

在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。

編碼線段裁剪第11頁，共40頁，2023年，2月20日，星期一Cohen-Sutherland裁剪如何判定應該與窗口的哪條邊求交呢？ 編碼中對應位為1的邊。計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點 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=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}具體算法見p201第12頁，共40頁，2023年，2月20日，星期一Cohen-Sutherland

直線裁剪算法小結本算法的優點在于簡單，易于實現。可以簡單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進行，處理之后，剩余部分就是可見的了。在這個算法中求交點是很重要的，決定了算法的速度。另外，本算法對于其它形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。第13頁，共40頁，2023年，2月20日，星期一中點分割裁剪算法基本思想：從P0點出發找出離P0最近的可見點，和從P1點出發找出離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。與Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線段與窗口的關系分為三種情況，對前兩種情況，進行一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距P0、P1最近的可見點，Pm為P0P1中點。

第14頁，共40頁，2023年，2月20日，星期一中點分割算法-求線段與窗口的交點從P0出發找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復上述過程，直到PmP1長度小于給定的控制常數為止，此時Pm收斂于交點。從P1出發找距離P1最近可見點采用上面類似方法。第15頁，共40頁，2023年，2月20日，星期一中點分割裁剪算法第16頁，共40頁，2023年，2月20日，星期一對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。主要過程只用到加法和除法運算，適合硬件實現，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點分割裁剪算法第17頁，共40頁，2023年，2月20日，星期一

設要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,C,D四點，見圖。算法的基本思想是從A,B和P0三點中找出最靠近的P1點，圖中要找的點是P0。從C,D和P1中找出最靠近P0的點。圖中要找的點是C點。那么P0C就是P0P1線段上的可見部分。梁友棟-Barsky算法第18頁，共40頁，2023年，2月20日，星期一梁友棟-Barsky算法線段的參數表示x=x0+t△xy=y0+t△y0<=t<=1

△x=x1-x0

△y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。第19頁，共40頁，2023年，2月20日，星期一求出P0P1與兩條始邊的交點參數t0,t1,令tl=max(t0,t1,0)，則tl即為三者中離p1最近的點的參數求出p0p1與兩條終邊的交點參數t2,t3,令tu=min(t2,t3,1)，則tu即為三者中離p0最近的點的參數若tu>tl,則可見線段區間[tl

,tu]t0t1t2t301梁友棟-Barsky算法：交點計算第20頁，共40頁，2023年，2月20日，星期一梁友棟-Barsky算法始邊和終邊的確定及交點計算：令QL=-△xDL=x0-xLQR=△xDR=xR-x0

QB=-△yDB=y0-yBQT=△yDT=yT-y0交點為ti=Di/

Qii=L,R,B,TQi<0ti為與始邊交點參數Qi>0ti為與終邊交點參數Qi=0Di<0時,線段不可見Di>0時,分析另一D,EFAB第21頁，共40頁，2023年，2月20日，星期一梁友棟-Barsky算法當Qi=0時若Di<0時,線段不可見（如圖中AB，有QR=0，DR<0）若Di>0時,分析另一D,（如圖中的EF就是這種情況，它使QL=0，DL>0和QR=0，DR>0。這時由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交點，而讓EF和y=yT及y=yB的交點決定直線段上的可見部分。）

EFAB第22頁，共40頁，2023年，2月20日，星期一第5章 圖形變換與裁剪5.1齊次坐標5.2窗口到視區的變換5.3圖形幾何變換5.4三維圖形的基本問題

5.5平面幾何投影5.6直線段裁剪5.7多邊形裁剪第23頁，共40頁，2023年，2月20日，星期一5.7多邊形裁剪錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當部分來封閉它，如何確定其邊界？第24頁，共40頁，2023年，2月20日，星期一5.7多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？第25頁，共40頁，2023年，2月20日，星期一Sutherland-Hodgman算法分割處理策略：將多邊形關于矩形窗口的裁剪分解為多邊形關于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結果是后邊的輸入。亦稱逐邊裁剪算法第26頁，共40頁，2023年，2月20日，星期一Sutherland-Hodgman算法基本思想是一次用窗口的一條邊裁剪多邊形。考慮窗口的一條邊以及延長線構成的裁剪線該線把平面分成兩個部分:可見一側；不可見一側多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關系只有四種第27頁，共40頁，2023年，2月20日，星期一Sutherland-Hodgman算法情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點P第28頁，共40頁，2023年，2月20日，星期一

SP與裁剪線相交求SP與裁剪線的交點I輸出IP位于可見一側輸出頂點PYNYN

處理線段SP過程子框圖開始第一個頂點→S第一個頂點→F頂點輸入完畢輸入頂點P處理線段SPF→P處理線段SP結束YN逐邊裁剪法算法框圖P→S第29頁，共40頁，2023年，2月20日，星期一Sutherland-Hodgman算法上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，算法框圖同上，只是判斷點在窗口哪一側以及求線段SP與裁剪邊的交點算法應隨之改變。第30頁，共40頁，2023年，2月20日，星期一Sutherland-Hodgeman算法對凸多邊形應用本算法可以得到正確的結果，但是對凹多邊形的裁剪將如圖所示顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。再有就是Weiler-Athenton算法。第31頁，共40頁，2023年，2月20日，星期一Sutherland-Hodgman算法思考：如何推廣到任意凸多邊形裁剪窗口？第32頁，共40頁，2023年，2月20日，星期一Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內環）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為B第33頁，共40頁，2023年，2月20日，星期一Weiler-Athenton算法多邊形頂點的排列順序（使多邊形區域位于有向邊的左側）外環：逆時針；內環：順時針主多邊形和裁剪多邊形把二維平面分成兩部分。內裁剪：A∩B外裁剪：A-B裁剪結果區域的邊界由A的部分邊界和B的部分邊界兩部分構成，并且在交點處邊界發生交替，即由A的邊界轉至B的邊界，或由B的邊界轉至A的邊界BA第34頁，共40頁，2023年，2月20日，星期一Weiler-Athenton算法如果主多邊形與裁剪多邊形有交點，則交點成對出現，它們被分為如下兩類：進點：主多邊形邊界由此進入裁剪多邊形內如，I1,I3,I5,I7,I9,I11出點：主多邊形邊界由此離開裁剪多邊形區域.如，I0,I2,I4,I6,I8,I10

第35頁，共40頁，2023年，2月20日，星期一Weiler-Athenton算法1）建頂點表；2）求交點；3）裁剪……1、建立主多邊形和裁剪多邊的頂點表．2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針。3、裁剪:如果存在沒有被跟蹤過的交點，執行以下步驟：

第36頁，共40頁，2023年，2月