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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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