多邊形裁剪算法

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

2、)第3頁，共40頁，2022年，5月20日，14點18分，星期二5.6直線段裁剪直線段裁剪算法是復雜圖形裁剪的基礎。復雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。主要的四種算法 直接求交算法 Cohen-Sutherland算法 中點算法 梁友棟barskey算法第4頁，共40頁，2022年，5月20日，14點18分，星期二5.6直線段裁剪裁剪線段與窗口的關系：(1)線段完全可見；(2)顯然不可見；(3)其它提高裁剪效率：快速判斷情形(1)(2)，對于情形(3)，設法減少求交次數(shù)和每次求交時所需的計算量。第5頁，共40頁，2022年，5月20日，14點18分，星期二直

3、接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。第6頁，共40頁，2022年，5月20日，14點18分，星期二Cohen-Sutherland裁剪基本思想：對于每條線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。為快速判斷，采用如下編碼方法：第7頁，共40頁，2022年，5月20日，14點18分，星期二 實現(xiàn)方法： 將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一個四位二進制數(shù)標識，直線的端點都

4、按其所處區(qū)域賦予相應的區(qū)域碼，用來標識出端點相對于裁剪矩形邊界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪第8頁，共40頁，2022年，5月20日，14點18分，星期二Cohen-Sutherland算法將區(qū)域碼的各位從右到左編號，則坐標區(qū)域與各位的關系為： 上 下 右 左 X X X X任何位賦值為1，代表端點落在相應的位置上，否則該位為0。若端點在剪取矩形內，區(qū)域碼為0000。如果端點落在矩形的左下角，則區(qū)域碼為0101。第9頁，共40頁，2022年，5月20日，14點18分，星期二Cohen-Sutherla

5、nd算法一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內，哪條直線完全在窗口外。所以得到一個規(guī)律：第10頁，共40頁，2022年，5月20日，14點18分，星期二Cohen-Sutherland裁剪若P1P2完全在窗口內code1=0,且code2=0,則“取”若P1P2明顯在窗口外code1&code20，則“棄” 在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。 編碼 線段裁剪第11頁，共40頁，2022年，5月20日，14點18分，星期二Cohen-Sutherland裁剪如何判定應該與窗口的哪條邊求交呢？ 編碼中對應位為1的邊。計算

6、線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點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(BOTTOM&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);具體算法見p201第12頁，共40頁，2022年，5月20日，14點18分，星期二Cohen

7、-Sutherland直線裁剪算法小結本算法的優(yōu)點在于簡單，易于實現(xiàn)?？梢院唵蔚拿枋鰹閷⒅本€在窗口左邊的部分刪去，按左，右，下，上的順序依次進行，處理之后，剩余部分就是可見的了。在這個算法中求交點是很重要的，決定了算法的速度。另外，本算法對于其它形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。第13頁，共40頁，2022年，5月20日，14點18分，星期二中點分割裁剪算法基本思想：從P0點出發(fā)找出離P0最近的可見點，和從P1點出發(fā)找出離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。與Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線

8、段與窗口的關系分為三種情況，對前兩種情況，進行一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距P0 、 P1最近的可見點，Pm為P0P1中點。 第14頁，共40頁，2022年，5月20日，14點18分，星期二中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時Pm收斂于交點

9、。從P1出發(fā)找距離P1最近可見點采用上面類似方法。第15頁，共40頁，2022年，5月20日，14點18分，星期二中點分割裁剪算法第16頁，共40頁，2022年，5月20日，14點18分，星期二對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點分割裁剪算法第17頁，共40頁，2022年，5月20日，14點18分，星期二 設要裁剪的線段是P0P1。 P0P1和窗口邊界交于A,B,C,D四點，見圖。算法的基本思想是從A,B和P0三點中找出最靠近的P1點，圖中要找的點是P0。從C,D和P1中找出

10、最靠近P0的點。圖中要找的點是C點。那么P0C就是P0P1線段上的可見部分。梁友棟-Barsky算法第18頁，共40頁，2022年，5月20日，14點18分，星期二梁友棟-Barsky算法 線段的參數(shù)表示x=x0+txy=y0+ty 0=t tl,則可見線段區(qū)間 tl , tut0t1t2t301梁友棟-Barsky算法：交點計算第20頁，共40頁，2022年，5月20日，14點18分，星期二梁友棟-Barsky算法始邊和終邊的確定及交點計算：令 QL= - x DL= x0-xL QR= x DR= xR-x0 QB= - y DB= y0-yB QT= y DT= yT-y0交點為 ti=

11、 Di / Qi i=L,R,B,TQi 0 ti為與終邊交點參數(shù)Qi =0 Di 0 時, 分析另一D, EFAB第21頁，共40頁，2022年，5月20日，14點18分，星期二梁友棟-Barsky算法當Qi =0時 若Di 0 時,線段不可見（如圖中AB，有QR=0，DR0 時, 分析另一D, （如圖中的EF就是這種情況，它使QL=0，DL0和QR=0，DR0。這時由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交點，而讓EF和y=yT及y=yB的交點決定直線段上的可見部分。） EFAB第22頁，共40頁，2022年，5月20日，14點18分，星期二第5章圖形變換與

12、裁剪5.1 齊次坐標5.2 窗口到視區(qū)的變換5.3 圖形幾何變換5.4 三維圖形的基本問題 5.5 平面幾何投影5.6 直線段裁剪5.7 多邊形裁剪第23頁，共40頁，2022年，5月20日，14點18分，星期二5.7多邊形裁剪錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當部分來封閉它，如何確定其邊界？第24頁，共40頁，2022年，5月20日，14點18分，星期二5.7多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？第25頁，共40頁，2022年，5月20日，14點18分，星期二Sutherland-Hodgman算法分割處理策略：

13、將多邊形關于矩形窗口的裁剪分解為多邊形關于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結果是后邊的輸入。亦稱逐邊裁剪算法第26頁，共40頁，2022年，5月20日，14點18分，星期二Sutherland-Hodgman算法基本思想是一次用窗口的一條邊裁剪多邊形。考慮窗口的一條邊以及延長線構成的裁剪線該線把平面分成兩個部分:可見一側；不可見一側多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關系只有四種第27頁，共40頁，2022年，5月20日，14點18分，星期二Sutherland-Hodgman算法情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的

14、交點I；情況（4）輸出線段SP與裁剪線的交點I和終點P第28頁，共40頁，2022年，5月20日，14點18分，星期二 SP與裁剪線相交 求SP與裁剪線的交點I輸出IP位于可見一側輸出頂點PYNYN 處理線段SP過程子框圖開始第一個頂點 S第一個頂點 F頂點輸入完畢輸入頂點P處理線段SPF P處理線段SP結束YN逐邊裁剪法算法框圖P S第29頁，共40頁，2022年，5月20日，14點18分，星期二Sutherland-Hodgman算法上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，算法框圖同上，只是判斷點在窗口哪一側以及求線段SP

15、與裁剪邊的交點算法應隨之改變。第30頁，共40頁，2022年，5月20日，14點18分，星期二Sutherland-Hodgeman算法對凸多邊形應用本算法可以得到正確的結果，但是對凹多邊形的裁剪將如圖所示顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現(xiàn)。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。再有就是Weiler-Athenton算法。第31頁，共40頁，2022年，5月20日，14點1

16、8分，星期二Sutherland-Hodgman算法思考：如何推廣到任意凸多邊形裁剪窗口？第32頁，共40頁，2022年，5月20日，14點18分，星期二Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內環(huán)）的情況：主多邊形：被裁剪多邊形，記為A 裁剪多邊形：裁剪窗口，記為B 第33頁，共40頁，2022年，5月20日，14點18分，星期二Weiler-Athenton算法多邊形頂點的排列順序（使多邊形區(qū)域位于有向邊的左側 ）外環(huán)：逆時針 ；內環(huán)：順時針主多邊形和裁剪多邊形把二維平面分成兩部分。內裁剪：AB外裁剪：A-B裁剪結果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構成

17、，并且在交點處邊界發(fā)生交替，即由A的邊界轉至B的邊界，或由B的邊界轉至A的邊界 BA第34頁，共40頁，2022年，5月20日，14點18分，星期二Weiler-Athenton算法如果主多邊形與裁剪多邊形有交點，則交點成對出現(xiàn)，它們被分為如下兩類：進點：主多邊形邊界由此進入裁剪多邊形內 如，I1,I3, I5, I7, I9, I11出點：主多邊形邊界由此離開裁剪多邊形區(qū)域. 如， I0,I2, I4, I6, I8, I10 第35頁，共40頁，2022年，5月20日，14點18分，星期二Weiler-Athenton算法1）建頂點表；2）求交點；3）裁剪 1、建立主多邊形和裁剪多邊的頂點

18、表2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針 。3、裁剪: 如果存在沒有被跟蹤過的交點，執(zhí)行以下步驟： 第36頁，共40頁，2022年，5月20日，14點18分，星期二Weiler-Athenton算法第37頁，共40頁，2022年，5月20日，14點18分，星期二Weiler-Athenton算法 (1)建立空的裁剪結果多邊形的頂點表 (2)選取任一沒有被跟蹤過的交點為始點，將其輸出到結果多邊形頂點表中 (3)如果該交點為進點，跟蹤主多邊形邊邊界；否則跟蹤裁剪多邊形邊界 (4) 跟蹤多邊形邊界，每遇到多邊形頂點，將其輸出到結果多邊形頂點表中，直至遇到新的交點 (5)將該交點輸出到結果多邊形頂點表中，并通過連接該交點的雙向指針改變跟蹤方向（如果上一步跟蹤的是主多邊形邊界，現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊界，現(xiàn)在改為跟蹤主多邊形邊界） (6)重復(4)、(5)直至回到起點取I7為起點，所得裁剪結果多邊形I7I