《多邊形裁剪算法》PPT課件.ppt

1、第5章圖形的變換和裁剪，5.1齊次坐標(biāo)5.2從窗口到可視區(qū)域的變換5.3圖形的幾何變換5.4三維圖形的基本問題5.5平面幾何投影5.6直線段的裁剪5.7多邊形裁剪、裁剪、裁剪：確定圖形的哪些部分在顯示區(qū)域內(nèi)，哪些部分在顯示區(qū)域外，這樣只有那些在顯示區(qū)域內(nèi)的部分才能顯示。這個(gè)選擇過程被稱為剪輯。圖形裁剪算法直接影響圖形系統(tǒng)的效率。點(diǎn)裁剪，圖形裁剪中最基本的問題。假設(shè)窗口左下角的坐標(biāo)是(xL，yB)，右上角的坐標(biāo)是(xR，yT)。對于給定點(diǎn)P(x，y)，點(diǎn)P在窗口內(nèi)的條件是滿足以下不等式：xL=x=xR和yB=y=yT。否則，點(diǎn)P在窗口之外。問題：如何區(qū)分任何多邊形窗口？5.6、直線切割，直線切割

2、算法是復(fù)雜圖形切割的基礎(chǔ)。復(fù)雜曲線可以用虛線段來近似，所以切割問題也可以轉(zhuǎn)化為直線段的切割問題。四種主要算法是直接求交算法科恩-薩瑟蘭算法、中點(diǎn)算法梁有東巴爾斯基算法、5.6線段切割、線段與窗口切割的關(guān)系：(1)線段完全可見；(2)明顯不可見；(3)提高切割效率的其他方法：快速判斷案例(1)和(2)。對于情況(3)，盡量減少交叉次數(shù)和每個(gè)交叉所需的計(jì)算量。直接相交算法、直線和窗口邊緣以參數(shù)形式寫入，并計(jì)算參數(shù)值?？贫?薩瑟蘭剪輯，基本思想：對于每一個(gè)線段P1P2，它分為三種情況。 (1)如果P1P2完全在窗口中，它將被顯示。(2)如果P1P2明顯超出窗口，則丟棄該線段。(3)如果線段不滿足(1

3、)或(2)的條件，則線段在交點(diǎn)處被分成兩段。有一段完全在窗外，所以你可以把它扔掉。然后對另一段重復(fù)上述過程。為了快速判斷，采用以下編碼方法：(1)窗口邊緣的兩條邊長，得到九個(gè)區(qū)域，每個(gè)區(qū)域用一個(gè)四位二進(jìn)制數(shù)標(biāo)識，直線的端點(diǎn)根據(jù)它們的區(qū)域分配相應(yīng)的區(qū)域編碼，用于標(biāo)識端點(diǎn)相對于裁剪矩形邊界的位置。1001，0001，0101，1000，0000，0100，1010，0010，A，B，C，D，科恩-薩瑟蘭裁剪，科恩-薩瑟蘭算法，區(qū)域代碼如果端點(diǎn)在裁剪矩形內(nèi)，則區(qū)域代碼為0000。如果端點(diǎn)位于矩形的左下角，則區(qū)號為0101?？贫?薩瑟蘭算法，一旦給定了所有線段的區(qū)域碼，就可以快速判斷哪條線完全在裁剪窗

4、口內(nèi)，哪條線完全在窗口外。因此，我們得到一個(gè)規(guī)則：科恩-薩瑟蘭剪輯，如果P1P2完全在窗口內(nèi)，代碼1=0，代碼2=0，然后“采取”如果P1P2顯然是在窗口外，代碼1代碼20，然后“放棄”線段在交叉點(diǎn)分成兩段。有一段完全在窗外，所以你可以把它扔掉。然后對另一段重復(fù)上述過程。編碼線裁剪，科恩-薩瑟蘭裁剪，如何確定窗口的哪一側(cè)應(yīng)該相交？編碼中相應(yīng)位為1的邊。計(jì)算線段P1(x1，y1)P2(x2，y2)和窗口邊界之間的交點(diǎn)if(左)。參見p201，科恩-薩瑟蘭直線裁剪算法概述。該算法簡單易行。這可以簡單地描述為按左、右、下和上的順序刪除窗口左側(cè)的直線部分。處理后，其余部分可見。在該算法中尋找交點(diǎn)是非常

5、重要的，它決定了算法的速度。此外，這種算法對于其他形狀的窗口可能不是同樣有效。特點(diǎn)：該編碼方法可以快速判斷線段是完全可見還是明顯不可見。中點(diǎn)分割裁剪算法，基本思想：從P0和P1中找出最近的可見點(diǎn)。連接這兩個(gè)可見點(diǎn)的線是原始線段的可見部分。像科恩-薩瑟蘭算法一樣，首先對線段的端點(diǎn)進(jìn)行編碼，并將線段與窗口之間的關(guān)系分為三種情況，前兩種情況處理相同；在第三種情況下，線段和窗口之間的交點(diǎn)通過中點(diǎn)分割獲得。a和b分別是離P0和P1最近的可見點(diǎn)，Pm是P0P1的中點(diǎn)。中點(diǎn)分割算法-找出線段和窗口的交點(diǎn)，并從P0找到最近的可見點(diǎn)。首先，通過中點(diǎn)分割法找到P0P1的中點(diǎn)Pm。如果P0Pm不是明顯不可見的，并且

6、P0P1在窗口中有一個(gè)可見部分，那么離P0最近的可見點(diǎn)必須落在P0Pm上，因此P0Pm被用來代替P01。否則，用PmP1代替P0P1。然后找到新P0P1的中點(diǎn)Pm。重復(fù)上述過程，直到PmP1的長度小于給定的控制常數(shù)，此時(shí)Pm收斂到交點(diǎn)。從P1開始，使用上述類似方法找到離P1最近的可見點(diǎn)。中點(diǎn)分割和裁剪算法，對于分辨率為2N*2N的顯示器，上述二分法過程最多可以執(zhí)行n次。主進(jìn)程僅使用加法和除法，這適用于硬件實(shí)現(xiàn)。它可以用左右移位代替乘法和除法，大大加快了速度。中點(diǎn)切割算法，讓待切割的線段為P0P1。P0P1和窗口邊界在四個(gè)點(diǎn)相交：a、b、c和d，如圖所示。該算法的基本思想是從三個(gè)點(diǎn)A、B和P0中

7、找到最近的P1點(diǎn)，在圖中找到的點(diǎn)是P0。從C、D和P1找到最靠近P0的點(diǎn)。圖片中的點(diǎn)是c點(diǎn)，P0C是P0P1線段的可見部分。梁有東-巴爾斯基算法，梁有東-巴爾斯基算法，線段的參數(shù)表示X=x0 TX Y=Y0 Ty0=t=1x=x1-x0 Y=y1-y0窗口邊界的四條邊可以分為兩類：開始邊和結(jié)束邊。得到p0p1與兩個(gè)起始邊之間的相交參數(shù)t0、t1，設(shè)tl=max(t0，t1，0)，則tl是三者中最靠近p1的點(diǎn)的參數(shù)，并得到p0p1與兩個(gè)最終邊之間的相交參數(shù)t2、t3，設(shè)tu=min(t2，t3，1)，則tu是三者中最靠近P0的點(diǎn)的參數(shù)。如果tu tl，則可以看到線段間隔t1。t0，t1，t2，t

8、3，0，1，梁有東-巴爾斯基算法：求交算法，梁有東-巴爾斯基算法，確定起點(diǎn)和終點(diǎn)邊并計(jì)算交點(diǎn)：讓QL=-XDL=x0-XLQR=XDR=XR-X0QB=-YDB=Y0-YQT=YDT=YT-Y0，當(dāng)交點(diǎn)為ti=Di/QI=L，R，B，T Qi 0 ti為與終點(diǎn)邊Qi=0 Di 0，E的交點(diǎn)參數(shù)此時(shí)，因?yàn)镋F和x=xL和x=xR是平行的，所以沒有必要求出EF和x=xL和x=xR的交點(diǎn)，而是讓EF和y=yT和y=yB的交點(diǎn)確定直線上的可見部分。)，E，F(xiàn)，A，B，第5章圖形變換和裁剪，5.1齊次坐標(biāo)5.2從窗口到視口的變換5.3圖形的幾何變換5.4三維圖形的基本問題5.5平面幾何投影5.6線性線段

9、的裁剪5.7多邊形裁剪，5.7多邊形裁剪，錯覺：線性線段的裁剪組合？新問題：1)邊界不再閉合，它需要用窗口邊界的適當(dāng)部分來閉合。如何確定它的邊界？5.7多邊形裁剪，2)凹多邊形可以裁剪成幾個(gè)小多邊形。如何確定這些小多邊形的邊界？薩瑟蘭-霍奇曼算法，分割處理策略：將矩形窗口的多邊形切割分解為窗口四邊所在直線的多邊形切割。流水線處理(左上角和右下角):前面的結(jié)果是后面的輸入。也稱為逐邊裁剪算法，薩瑟蘭-霍奇曼算法，其基本思想是一次用一個(gè)窗口的邊來裁剪多邊形。考慮由窗口的一側(cè)和延長線形成的剪裁線，它將平面分成兩部分，的可見側(cè)；不可見多邊形每邊的兩個(gè)端點(diǎn)s和p。它們與裁剪線之間只有四種位置關(guān)系，薩瑟蘭

10、-霍奇曼算法，其中(1)只輸出頂點(diǎn)p；案例(2)輸出0個(gè)頂點(diǎn)；在情況(3)中，輸出線段SP和裁剪線之間的交點(diǎn)I；在情況(4)中，交點(diǎn)薩瑟蘭-霍奇曼算法，它可以得到正確的結(jié)果時(shí)，適用于凸多邊形，但切割凹多邊形將顯示一個(gè)額外的直線，如圖所示。當(dāng)切割的多邊形有兩個(gè)或更多分開的部分時(shí)，就會發(fā)生這種情況。因?yàn)橹挥幸粋€(gè)輸出頂點(diǎn)表，表中的最后一個(gè)頂點(diǎn)總是連接到第一個(gè)頂點(diǎn)。有很多方法可以解決這個(gè)問題。一種是將凹多邊形分成幾個(gè)凸多邊形，然后分別處理每個(gè)凸多邊形。第二是修改算法，檢查沿任意裁剪窗口邊緣的頂點(diǎn)表，并正確連接頂點(diǎn)對。然后是魏勒-阿森頓算法。薩瑟蘭-霍奇曼算法，思想：如何擴(kuò)展到任意凸多邊形裁剪窗口？魏勒

11、-阿森頓算法，當(dāng)裁剪窗口是任意多邊形(凸、凹、帶內(nèi)環(huán)):主多邊形：裁剪多邊形，表示為A裁剪多邊形：裁剪窗口，表示為B，魏勒-阿森頓算法，多邊形頂點(diǎn)的排列順序(使多邊形區(qū)域在有向邊的左側(cè))外環(huán)：逆時(shí)針；內(nèi)環(huán)：順時(shí)針主多邊形和裁剪多邊形將2D平面分成兩部分。內(nèi)部裁剪：AB外部裁剪：A-B，裁剪結(jié)果區(qū)域的邊界由兩部分組成：A部分邊界和B部分邊界，邊界在交點(diǎn)處交替，即從A邊界到B邊界，或者從B邊界到A邊界。魏勒-阿森頓算法，如果主多邊形和裁剪多邊形有交點(diǎn)，交點(diǎn)成對出現(xiàn)。它們分為以下兩類：入口點(diǎn)：主多邊形邊界進(jìn)入裁剪多邊形，例如I1，I3，I5，I7，I9，I11出口點(diǎn)：主多邊形邊界離開裁剪多邊形區(qū)域，

12、例如i0，I2，i4，i6，i8，i10，魏勒-雅典娜算法，1)建立頂點(diǎn)表；2)找到交點(diǎn)；3)切割：1。建立主多邊形和切割多邊形的頂點(diǎn)表；2.找出主多邊形和切割多邊形的交點(diǎn)，并將這些交點(diǎn)依次插入兩個(gè)多邊形的頂點(diǎn)表中。雙向指針建立在兩個(gè)多邊形頂點(diǎn)表的相同交點(diǎn)之間。3.裁剪：如果存在未跟蹤的交點(diǎn)，執(zhí)行以下步驟：魏勒-阿森頓算法、魏勒-阿森頓算法，(1)建立裁剪結(jié)果多邊形的空頂點(diǎn)表，(2)選擇任何未跟蹤的交點(diǎn)作為起點(diǎn)，并將其輸出到結(jié)果多邊形的頂點(diǎn)表，(3)如果交點(diǎn)是入口點(diǎn)，則跟蹤主多邊形的邊緣邊界；否則，跟蹤多邊形邊界(4)，并在每次遇到多邊形頂點(diǎn)時(shí)將其輸出到結(jié)果多邊形頂點(diǎn)表，直到遇到新的交點(diǎn)(5)，將交點(diǎn)輸出到結(jié)果多邊形頂點(diǎn)表，并通過連接交點(diǎn)的雙向指針改變跟蹤方向(如果在上一步中跟蹤了主多邊形邊界，現(xiàn)在將跟蹤切割的多邊形邊界；如果在上一步中跟蹤了切割多邊形邊界，現(xiàn)在將跟蹤主多邊形邊界。(6)重復(fù)(4)和(5)直到回到起點(diǎn)，以I7為起點(diǎn)，得到切割結(jié)