計(jì)算機(jī)軟件及應(yīng)用二維圖形裁剪課件

1、二維圖形裁剪裁剪概述 線段裁剪直接求交算法； Cohen-Sutherland算法；（重點(diǎn)，算法實(shí)現(xiàn)） 梁友棟-Barsky算法 多邊形裁剪 Sutlerland_Hodgman算法（難點(diǎn)，算法實(shí)現(xiàn)） Weiler-Athenton算法 字符裁剪裁 剪二維圖形裁剪預(yù)備知識(shí)：求交（矩形窗口）裁剪三維裁剪長(zhǎng)方體裁剪體棱錐體體裁剪體直接求交算法編碼裁剪算法中點(diǎn)分割算法被裁剪對(duì)象：直線段、多邊形、三維實(shí)體一、裁剪概述 裁剪：是裁去窗口之外物體或物體部分的一種操作。剪裁的應(yīng)用1、從定義的場(chǎng)景中抽取出用于觀察的部分；2、在三維視圖中標(biāo)識(shí)出可見面；3、防止線段或?qū)ο蟮倪吔缁煜?、用實(shí)體造型來(lái)創(chuàng)建對(duì)象；5、

2、顯示多窗口的環(huán)境；6、允許選擇圖形的一部分來(lái)進(jìn)行拷貝，移動(dòng)和刪除。 “取景器”=窗口視區(qū)1 視區(qū)2（viewport） 裁剪的目的判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交假定條件矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪點(diǎn)或線段：點(diǎn)裁剪 點(diǎn)(x, y)在窗口內(nèi)的充分必要條件是： 問題：對(duì)于任何多邊形窗口，如何判別？WytWybWxlWxrP1P2P3線段相對(duì)于該窗口的情況有:線段全部位于窗口的內(nèi)部（A）；線段全部位于窗口外部（B、C）；線段的中間部分在窗口內(nèi)，而二端點(diǎn)在窗口外部（D）；線段的一端在窗口內(nèi)，而另一

3、端在窗口外（E）。x=xLx=xRy=yBy=yTABCDE二、線段裁剪待裁剪線段和窗口的關(guān)系 線段完全可見顯然不可見 線段至少有一端點(diǎn)在窗口之外，但非顯然不可見 保留丟棄裁剪為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：(一）快速判斷線段完全在窗口內(nèi)或外的情形；(二) 設(shè)法減少裁剪情形中求交次數(shù)和每次求交時(shí)所需的計(jì)算量。直接求交算法基本思想是：判斷直線與窗口的位置關(guān)系，確定該直線是完全可見、部分可見或完全不可見，然后輸出處于窗口內(nèi)線段的端點(diǎn)，并顯示此線段。根據(jù)直線段和窗口的關(guān)系可知：（1）整條線在窗口之內(nèi)。此時(shí)，不需剪裁，顯示整條線段。（2）整條線在窗口之外，此時(shí)，不需剪裁，不顯示整條線段。（3）部分線在窗

4、口之內(nèi)，部分線在窗口之外。此時(shí)，需要求出線段與窗口邊界的交點(diǎn)，并將窗口外的線段部分剪裁掉，顯示窗口內(nèi)的部分。例1 設(shè)有直線段P0P1，有一個(gè)矩形裁剪窗口，寫出對(duì)該線段裁剪的算法。1）求出直線P0P1與窗口的交點(diǎn)I，如圖（a）所示。2）取P0 I線段顯示，擦除I P1線段，并將P1替換I，即得P0P1線段，裁剪結(jié)束。如圖（b）所示。 P0P1IP0P1（a）（b）求線段與窗口交點(diǎn)設(shè)線段兩端點(diǎn)坐標(biāo)為：和則過這兩點(diǎn)的直線方程為：其中k為斜率。上述直線方程與窗口各邊界的交點(diǎn)為：左：右：下：上：基本思想：對(duì)于每條待裁剪的線段P1P2分三種情況處理：若P1P2完全在窗口內(nèi)，則顯示該線段P1P2，簡(jiǎn)稱“取”

5、之；若P1P2完全在窗口外，則丟棄該線段，簡(jiǎn)稱“舍”之；若線段既不滿足“取”的條件，也不滿足“舍”的條件，則求線段與窗口邊界的交點(diǎn)，在交點(diǎn)處把線段分為兩段，其中一段完全在窗口外，可舍棄之，然后對(duì)另一段重復(fù)上述處理。 核心思想：分區(qū)編碼和線段分割。 Cohen-Sutherland 算法 (編碼算法) 分區(qū)編碼方法：圖形區(qū)域劃分成九個(gè)區(qū)域。四位編碼 表示端點(diǎn)所處的位置： (-) 上 下 右 左第一位為“1”時(shí)，表示點(diǎn)在y=yT的上方；第二位為“1”時(shí)，表示點(diǎn)在y=yB的下方；第三位為“1”時(shí)，表示點(diǎn)在x=xR的右方；第四位為“1”時(shí)，表示點(diǎn)在x=xL的左方。0000000100101000010

6、01001101001010110 x=xLx=xRy=yBy=yT11111 1 1 1#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8編碼原則每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下右左；編碼方法練習(xí)：請(qǐng)給出右圖的線段端點(diǎn)編碼（端點(diǎn)編碼：定義為它所在區(qū)域的編碼）x=xLx=xRy=yBy=yTABCDE第一步 判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是， 則線段完全可見；否則進(jìn)入第二步；第二步 判別線段是否為顯然不可見，如果是，則裁 剪結(jié)束；否則進(jìn)行第三步 ；第三步 求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將 線段分為兩段

7、，其中一段顯然不可見，丟棄。 對(duì)余下的另一段重新進(jìn)行第一步，第二步判斷， 直至結(jié)束 Cohen-Sutherland 算法步驟當(dāng)線段的兩個(gè)端點(diǎn)的編碼的邏輯“與”非零時(shí) ，線段為顯然不可見的。也可以進(jìn)行“按位與”運(yùn)算，可知這兩個(gè)端點(diǎn)是否同在視區(qū)的上、下、左、右；如code1=0101,code2=0110，則code1&code2=0100,表示在窗口下方。問題：顯然可見的編碼如何判斷？編碼判斷當(dāng)線段的兩個(gè)端點(diǎn)的編碼的邏輯“與”非零時(shí) ，線段為顯然不可見的。也可以進(jìn)行“按位于”運(yùn)算，可知這兩個(gè)端點(diǎn)是否同在視區(qū)的上、下、左、右；如code1=0101,code2=0110，則code1&code2

8、=0100,表示在窗口下方。問題：顯然可見的編碼如何判斷？編碼判斷對(duì)一條線段的可見性測(cè)試方法：（1）若線段兩個(gè)端點(diǎn)的四位二進(jìn)制編碼全為0000，即兩端點(diǎn)編碼邏輯或運(yùn)算為0，那么該線段完全位于窗口內(nèi)，可直接保留；（2）對(duì)兩端點(diǎn)的四位二進(jìn)制編碼進(jìn)行邏輯與運(yùn)算，若結(jié)果不為零，那么整條線段必位于窗口外，可直接舍棄；（3）否則，這條線段既不能直接保留，也不能直接舍棄，它可能與窗口相交。此時(shí)，需要對(duì)線段進(jìn)行再分割，即找到與窗口邊線的一個(gè)交點(diǎn)，根據(jù)交點(diǎn)位置，賦予四位二進(jìn)制編碼，并對(duì)分割后的線段按照一定的順序（如左右下上）進(jìn)行檢查，決定保留、舍棄或再次進(jìn)行分割。重復(fù)這一過程，直到全部線段均被舍棄或保留為止。例

9、：分別給下列直線段編碼，并判斷是否需要剪裁。P1P2C1=0001C2=0000P1P2C1=0100C2=0101BCP1P2C1=0101C2=1010P1P2ADC1=0000C2=0000例：Cohen-SutherLand算法過程：過程： 1）輸入線段AB的兩端點(diǎn)坐標(biāo)A（x0,y0）、B（x1,y1），以及裁剪窗口的四條邊界：yt,yb,xl,xr。2）對(duì)AB編碼，A的編碼codeA=0001，B的編碼為codeB=0110。 3）線段AB裁剪的基本過程（按左右下上的順序）： 由于codeA | codeB0，對(duì)AB不能全部保留；又因?yàn)閏odeA & codeB=0，對(duì)AB不能全部舍

10、棄，因此要對(duì)AB進(jìn)行求交處理。 由codeA=0001知A在窗口左邊外側(cè)，按左右下上的順序求AB與窗口左邊交點(diǎn)為P1，AP1必在窗口外，故裁剪掉，并用A替換P1。如圖（b）所示。（交點(diǎn)替換是為了方便編程循環(huán)）。 對(duì)P1B重復(fù)上述處理。A（原P1）編碼為0000，B編碼為0110；由于A（原P1）已在窗口內(nèi)，交換A和B的坐標(biāo)值與編碼，則B編碼為0000，A編碼變?yōu)?110，按左右下上順序求得右交點(diǎn)為P3；A（原B）P3必在窗口外，故裁剪掉，并用A替換P3。如圖（c）所示。 A的編碼還沒有達(dá)到0000，再求得下邊交點(diǎn)為P2，AP2必定在窗口外，故裁剪掉，并用A替換P2。如圖（d）所示。 對(duì)剩下的直

11、線段AB再進(jìn)行判斷，現(xiàn)在A編碼為0000，B編碼為0000，由于codeA | codeB=0，全在窗口中，故全部保留。最后得到裁剪后的線段為AB，算法結(jié)束。 求交測(cè)試順序固定(左上右下）最壞情形，線段求交四次。對(duì)于那些非完全可見、又非顯然不可見的線段，需要求交（如線段AD)，求交前先測(cè)試與窗口哪條邊所在直線有交？(按序判斷端點(diǎn)編碼中各位的值ClCtCrCb） 1）特點(diǎn)：用編碼方法可快速判斷線段- 完全可見和顯然不可見。 2）特別適用二種場(chǎng)合： 大窗口場(chǎng)合； 窗口特別小的場(chǎng)合(如, 光標(biāo)拾取圖形時(shí), 光標(biāo)看作小的裁剪窗口。）編碼算法特點(diǎn)設(shè)要裁剪的線段是P0P1。 P0P1和窗口邊界交于A,B,

12、C,D四點(diǎ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線段上的可見部分。梁友棟-Barsky算法 線段的參數(shù)表示x=x0+txy=y0+ty 0=t tl,則可見線段區(qū)間 tl , tut0t1t2t3P01交點(diǎn)計(jì)算P13.始邊和終邊的確定及交點(diǎn)計(jì)算：令 QL= x DL= x0-xL QR= x DR= xR-x0 QB= y DB= y0-yB QT= y DT= yT-y0參數(shù)交點(diǎn)為: ti= Di / Qi i=L,R,B,TQi 0 ti為與終邊交點(diǎn)參數(shù)當(dāng)Qi =0時(shí)

13、 若Di 0 時(shí),線段不可見（如圖中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)決定直線段上的可見部分。） ABEFAB三、多邊形裁剪錯(cuò)覺：直線段裁剪的組合？ 關(guān)鍵：要保持窗口內(nèi)多邊形的邊界部分，而且要將窗框的有關(guān)部分按一定次序插入多邊形的保留邊界之間，從而使剪裁后的多邊形的邊仍然保持封閉狀態(tài)。新的問題： 1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來(lái)封閉它，如何確定其邊界？2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多

14、邊形，如何確定這些小多邊形的邊界？Sutherland-Hodgman算法思路：將多邊形邊界作為一個(gè)整體，分而治之。將多邊形的各邊先相對(duì)于窗口的某一條邊界進(jìn)行裁剪，然后將裁剪結(jié)果再與另一條邊界進(jìn)行裁剪，如此重復(fù)多次，便可得到最終結(jié)果。流水線過程(左上右下)：左邊的結(jié)果是上邊的開始。亦稱逐邊裁剪算法內(nèi)側(cè)空間與外側(cè)空間多邊形的邊與半空間的關(guān)系PIS 可 見 側(cè)PS 可 見 側(cè)PIS 可 見 側(cè)PS 可 見 側(cè)(a)從外到內(nèi) (b)從內(nèi)到內(nèi) (c)從內(nèi)到外(d)從外到外輸出P和I 輸出P 輸出I 不輸出p1p2p3p4p5q1q2q3q4需要設(shè)置二個(gè)表： 輸入頂點(diǎn)表(向量)存放被裁剪多邊形的頂點(diǎn)p1

15、-pm。 輸出頂點(diǎn)表(線性鏈表)存放裁剪過程中及結(jié)果的頂點(diǎn) q1-qn。q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前： 裁剪后：輸入頂點(diǎn)表：p1p2p3p4p5 輸入頂點(diǎn)表: 不變輸出頂點(diǎn)表： 空 輸出頂點(diǎn)表: q1q2p3q7q8q5q6q4q3需要設(shè)置二個(gè)表： 輸入頂點(diǎn)表(向量)存放被裁剪多邊形的頂點(diǎn)p1- pm。 輸出頂點(diǎn)表(線性鏈表)存放裁剪過程中及結(jié)果的頂點(diǎn) q1- qn。實(shí)現(xiàn)方法：設(shè)置二個(gè)表 輸入頂點(diǎn)表(向量)存放被裁剪多邊形的頂點(diǎn)p1-pm。 輸出頂點(diǎn)表(線性鏈表)存放裁剪過程中及結(jié)果的頂點(diǎn) q1-qn。輸入頂點(diǎn)表中各頂點(diǎn)要求按一定順序排列，一般可采用順時(shí)針或逆時(shí)針

16、方向。相對(duì)于裁剪窗口的各條邊界，按頂點(diǎn)表中的順序，逐邊進(jìn)行裁剪。算法中相對(duì)于各窗口邊界的裁剪過程相同，且每次都是相對(duì)于前一次的結(jié)果進(jìn)行處理。裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)； 多邊形的邊與裁剪邊的交點(diǎn)。順序連接。特點(diǎn)：裁剪算法采用流水線方式， 適合硬件實(shí)現(xiàn)?？赏茝V到任意凸多邊形裁剪 窗口問題：一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？AFEDCBV1V2V3V4AFEDCBV1V2V3V4AED Sutherland-Hodgman多邊形裁剪：輸入頂點(diǎn)BAFEDC，輸出頂點(diǎn)：V1 A V2 V3 E D V4Sutherland-Hodgman算法Weiler-

17、Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A 裁剪多邊形：裁剪窗口，記為B 主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：AB外裁剪：A-B裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界 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)：主多邊形邊界由此離開裁剪多邊形區(qū)域. 如， I0,I2, I4, I6,

18、 I8, I10 Weiler-Atherton（W-A）算法（雙邊裁剪法） 可以用一個(gè)有內(nèi)孔的凹多邊形去裁剪另一個(gè)也有內(nèi)孔的凹多邊形。 被裁剪的多邊形主多邊形 裁剪區(qū)域裁剪多邊形 各多邊形的外部邊界取順時(shí)針方向，而其內(nèi)部邊界或孔取逆時(shí)針方向。思路：主多邊形和裁剪多邊形均用它們的頂點(diǎn)表來(lái)定義。 這兩類交點(diǎn)分別用進(jìn)點(diǎn)表和出點(diǎn)表來(lái)存放。主多邊形和裁剪多邊形的邊界若相交，交點(diǎn)必定成對(duì)地出現(xiàn)，其中一個(gè)交點(diǎn)為主多邊形邊進(jìn)入裁剪多邊形內(nèi)部時(shí)的交點(diǎn)（稱進(jìn)點(diǎn)），另一個(gè)交點(diǎn)則為離開時(shí)的交點(diǎn)（稱出點(diǎn)）。c1c2c3c4s1s2s3s4s5s6s7I1I2I3I4I5I6I7I8裁剪窗口多邊形主多邊形主多邊形 裁剪

19、窗口 頂點(diǎn)表 頂點(diǎn)表 s1 c1 I1 I8 I2 I1 s2 c2 I3 I2 s3 I3 I4 c3 s4 I4 I5 I5 I6 c4 s5 I6 I7 I7 s6 c1 I8 s7 s1起點(diǎn)簡(jiǎn)單例4 : W-A算法進(jìn)行多邊形裁剪進(jìn)點(diǎn)出點(diǎn)算法： 1.分別建立主多邊形和裁剪多邊形的頂點(diǎn)表； 2.求出主多邊形與裁剪多邊形的交點(diǎn)（進(jìn)點(diǎn)和出點(diǎn)）并分別建立進(jìn)點(diǎn)表和出點(diǎn)表； 3.將交點(diǎn)加入各頂點(diǎn)表中； 4. if 進(jìn)點(diǎn)表為空 then finish（1）取一進(jìn)點(diǎn)作為始點(diǎn)；（2）跟蹤主多邊形頂點(diǎn)表，直至發(fā)現(xiàn)下一交點(diǎn)，復(fù)制這一段主多邊形頂點(diǎn)到內(nèi)表中； 根據(jù)交點(diǎn)處指針，轉(zhuǎn)到裁剪多邊形頂點(diǎn)表中的相應(yīng)位置跟蹤裁剪多邊形頂點(diǎn)表，直至發(fā)現(xiàn)下一交點(diǎn)，復(fù)制這一段裁剪多邊形頂點(diǎn)到內(nèi)表中； if 該交點(diǎn)不是起始點(diǎn) then （2） if 進(jìn)點(diǎn)表中還有未遍歷到的交點(diǎn) then （1）（3）finish復(fù)雜例5，分析裁剪過程，分別寫出主多邊形、裁剪多邊形的頂點(diǎn)表，以及最終裁剪結(jié)果。Weiler-Athenton算法交點(diǎn)的奇異情況處理 1.與裁剪多邊形邊重