多邊形裁剪算法

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

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

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

將窗口邊線(xiàn)兩邊沿長(zhǎng)，得到九個(gè)區(qū)域，每一個(gè)區(qū)域都用一個(gè)四位二進(jìn)制數(shù)標(biāo)識(shí)，直線(xiàn)的端點(diǎn)都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來(lái)標(biāo)識(shí)出端點(diǎn)相對(duì)于裁剪矩形邊界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪第8頁(yè)，共40頁(yè)，2023年，2月20日，星期一Cohen-Sutherland算法將區(qū)域碼的各位從右到左編號(hào)，則坐標(biāo)區(qū)

域與各位的關(guān)系為：上下右左 XXXX

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

在交點(diǎn)處把線(xiàn)段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。

編碼線(xiàn)段裁剪第11頁(yè)，共40頁(yè)，2023年，2月20日，星期一Cohen-Sutherland裁剪如何判定應(yīng)該與窗口的哪條邊求交呢？ 編碼中對(duì)應(yīng)位為1的邊。計(jì)算線(xiàn)段P1(x1,y1)P2(x2,y2)與窗口邊界的交點(diǎn) 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);}具體算法見(jiàn)p201第12頁(yè)，共40頁(yè)，2023年，2月20日，星期一Cohen-Sutherland

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

第14頁(yè)，共40頁(yè)，2023年，2月20日，星期一中點(diǎn)分割算法-求線(xià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)。從P1出發(fā)找距離P1最近可見(jiàn)點(diǎn)采用上面類(lèi)似方法。第15頁(yè)，共40頁(yè)，2023年，2月20日，星期一中點(diǎn)分割裁剪算法第16頁(yè)，共40頁(yè)，2023年，2月20日，星期一對(duì)分辯率為2N*2N的顯示器，上述二分過(guò)程至多進(jìn)行N次。主要過(guò)程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)，它可以用左右移位來(lái)代替乘除法，這樣就大大加快了速度。中點(diǎn)分割裁剪算法第17頁(yè)，共40頁(yè)，2023年，2月20日，星期一

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

△x=x1-x0

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

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

QB=-△yDB=y0-yBQT=△yDT=yT-y0交點(diǎn)為ti=Di/

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

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

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

SP與裁剪線(xiàn)相交求SP與裁剪線(xiàn)的交點(diǎn)I輸出IP位于可見(jiàn)一側(cè)輸出頂點(diǎn)PYNYN

處理線(xiàn)段SP過(guò)程子框圖開(kāi)始第一個(gè)頂點(diǎn)→S第一個(gè)頂點(diǎn)→F頂點(diǎn)輸入完畢輸入頂點(diǎn)P處理線(xiàn)段SPF→P處理線(xiàn)段SP結(jié)束YN逐邊裁剪法算法框圖P→S第29頁(yè)，共40頁(yè)，2023年，2月20日，星期一Sutherland-Hodgman算法上述算法僅用一條裁剪邊對(duì)多邊形進(jìn)行裁剪，得到一個(gè)頂點(diǎn)序列，作為下一條裁剪邊處理過(guò)程的輸入。對(duì)于每一條裁剪邊，算法框圖同上，只是判斷點(diǎn)在窗口哪一側(cè)以及求線(xiàn)段SP與裁剪邊的交點(diǎn)算法應(yīng)隨之改變。第30頁(yè)，共40頁(yè)，2023年，2月20日，星期一Sutherland-Hodgeman算法對(duì)凸多邊形應(yīng)用本算法可以得到正確的結(jié)果，但是對(duì)凹多邊形的裁剪將如圖所示顯示出一條多余的直線(xiàn)。這種情況在裁剪后的多邊形有兩個(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è)，2023年，2月20日，星期一Sutherland-Hodgman算法思考：如何推廣到任意凸多邊形裁剪窗口？第32頁(yè)，共40頁(yè)，2023年，2月20日，星期一Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為B第33頁(yè)，共40頁(yè)，2023年，2月20日，星期一Weiler-Athenton算法多邊形頂點(diǎn)的排列順序（使多邊形區(qū)域位于有向邊的左側(cè)）外環(huán)：逆時(shí)針；內(nèi)環(huán)：順時(shí)針主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-B裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界BA第34頁(yè)，共40頁(yè)，2023年，2月20日，星期一Weiler-Athenton算法如果主多邊形與裁剪多邊形有交點(diǎn)，則交點(diǎn)成對(duì)出現(xiàn)，它們被分為如下兩類(lèi)：進(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è)，2023年，2月20日，星期一Weiler-Athenton算法1）建頂點(diǎn)表；2）求交點(diǎn)；3）裁剪……1、建立主多邊形和裁剪多邊的頂點(diǎn)表．2、求主多邊形和裁剪多邊形的交點(diǎn)，并將這些交點(diǎn)按順序插入兩多邊形的頂點(diǎn)表中。在兩多邊表形頂點(diǎn)表中的相同交點(diǎn)間建立雙向指針。3、裁剪:如果存在沒(méi)有被跟蹤過(guò)的交點(diǎn)，執(zhí)行以下步驟：

第36頁(yè)，共40頁(yè)，2023年，2月