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

二維圖形裁剪裁剪概述線段裁剪直接求交算法；Cohen-Sutherland算法；（重點(diǎn)，算法實(shí)現(xiàn)）

梁友棟-Barsky算法多邊形裁剪

Sutlerland_Hodgman算法（難點(diǎn)，算法實(shí)現(xiàn)）

Weiler-Athenton算法

字符裁剪二維圖形裁剪裁剪概述1裁剪二維圖形裁剪預(yù)備知識(shí)：求交（矩形窗口）裁剪三維裁剪長(zhǎng)方體裁剪體棱錐體體裁剪體直接求交算法編碼裁剪算法中點(diǎn)分割算法……被裁剪對(duì)象：直線段、多邊形、三維實(shí)體……一、裁剪概述裁剪：是裁去窗口之外物體或物體部分的一種操作。裁二維圖形裁剪預(yù)備知識(shí)：求交（矩形窗口）裁剪三維裁剪長(zhǎng)方體2剪裁的應(yīng)用1、從定義的場(chǎng)景中抽取出用于觀察的部分；

2、在三維視圖中標(biāo)識(shí)出可見面；

3、防止線段或?qū)ο蟮倪吔缁煜?/p>

4、用實(shí)體造型來創(chuàng)建對(duì)象；

5、顯示多窗口的環(huán)境；

6、允許選擇圖形的一部分來進(jìn)行拷貝，移動(dòng)和刪除。

剪裁的應(yīng)用1、從定義的場(chǎng)景中抽取出用于觀察的部分；

2、在三3“取景器”=窗口視區(qū)1視區(qū)2（viewport）“取景器”=窗口視區(qū)1視區(qū)24裁剪的目的判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交假定條件矩形裁剪窗口：[xmin,xmax]×[ymin,ymax]待裁剪點(diǎn)或線段：裁剪的目的5點(diǎn)裁剪點(diǎn)(x,y)在窗口內(nèi)的充分必要條件是：

問題：對(duì)于任何多邊形窗口，如何判別？WytWybWxlWxrP1P2P3點(diǎn)裁剪WytWybWxlWxrP1P2P36線段相對(duì)于該窗口的情況有:①線段全部位于窗口的內(nèi)部（A）；②線段全部位于窗口外部（B、C）；③線段的中間部分在窗口內(nèi)，而二端點(diǎn)在窗口外部（D）；④線段的一端在窗口內(nèi)，而另一端在窗口外（E）。x=xLx=xRy=yBy=yTABCDE二、線段裁剪線段相對(duì)于該窗口的情況有:x=xLx=xRy=yBy=yTA7待裁剪線段和窗口的關(guān)系

線段完全可見顯然不可見線段至少有一端點(diǎn)在窗口之外，但非顯然不可見

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

根據(jù)直線段和窗口的關(guān)系可知：（1）整條線在窗口之內(nèi)。此時(shí)，不需剪裁，顯示整條線段。（2）整條線在窗口之外，此時(shí)，不需剪裁，不顯示整條線段。（3）部分線在窗口之內(nèi)，部分線在窗口之外。此時(shí)，需要求出線段與窗口邊界的交點(diǎn)，并將窗口外的線段部分剪裁掉，顯示窗口內(nèi)的部分。直接求交算法基本思想是：判斷直線與窗口的位置關(guān)系，確定該直線9例1設(shè)有直線段P0P1，有一個(gè)矩形裁剪窗口，寫出對(duì)該線段裁剪的算法。1）求出直線P0P1與窗口的交點(diǎn)I，如圖（a）所示。2）取P0I線段顯示，擦除IP1線段，并將P1替換I，即得P0P1線段，裁剪結(jié)束。如圖（b）所示。

P0P1IP0P1（a）（b）例1設(shè)有直線段P0P1，有一個(gè)矩形裁剪窗口，寫出對(duì)該線段裁10求線段與窗口交點(diǎn)設(shè)線段兩端點(diǎn)坐標(biāo)為：和則過這兩點(diǎn)的直線方程為：其中k為斜率。上述直線方程與窗口各邊界的交點(diǎn)為：左：右：下：上：求線段與窗口交點(diǎn)設(shè)線段兩端點(diǎn)坐標(biāo)為：和則過這11基本思想：對(duì)于每條待裁剪的線段P1P2分三種情況處理：①若P1P2完全在窗口內(nèi)，則顯示該線段P1P2，簡(jiǎn)稱“取”之；②若P1P2完全在窗口外，則丟棄該線段，簡(jiǎn)稱“舍”之；③若線段既不滿足“取”的條件，也不滿足“舍”的條件，則求線段與窗口邊界的交點(diǎn)，在交點(diǎn)處把線段分為兩段，其中一段完全在窗口外，可舍棄之，然后對(duì)另一段重復(fù)上述處理。

核心思想：分區(qū)編碼和線段分割。

Cohen-Sutherland算法(編碼算法)基本思想：對(duì)于每條待裁剪的線段P1P2分三種情況處理：Co12分區(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的左方。000000010010100001001001101001010110x=xLx=xRy=yBy=yT11111

1

1

1#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8編碼原則分區(qū)編碼方法：圖形區(qū)域劃分成九個(gè)區(qū)域。000000010013每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下右左；編碼方法練習(xí)：請(qǐng)給出右圖的線段端點(diǎn)編碼（端點(diǎn)編碼：定義為它所在區(qū)域的編碼）x=xLx=xRy=yBy=yTABCDE每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下右左；編碼方14第一步判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進(jìn)入第二步；第二步判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；否則進(jìn)行第三步；第三步求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束

Cohen-Sutherland算法步驟第一步判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，Cohen-15當(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í)，線段為顯然不可見16當(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í)，線段為顯然不可見17對(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ù)這一過程，直到全部線段均被舍棄或保留為止。對(duì)一條線段的可見性測(cè)試方法：18例：分別給下列直線段編碼，并判斷是否需要剪裁。P1P2C1=0001C2=0000P1P2C1=0100C2=0101BCP1P2C1=0101C2=1010P1P2ADC1=0000C2=0000例：分別給下列直線段編碼，并判斷是否需要剪裁。P1P2C1=19例：Cohen-SutherLand算法過程：例：Cohen-SutherLand算法過程：20過程：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|codeB≠0，對(duì)AB不能全部保留；又因?yàn)閏odeA&codeB=0，對(duì)AB不能全部舍棄，因此要對(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ì)剩下的直線段AB再進(jìn)行判斷，現(xiàn)在A編碼為0000，B編碼為0000，由于codeA|codeB=0，全在窗口中，故全部保留。最后得到裁剪后的線段為AB，算法結(jié)束。過程：21求交測(cè)試順序固定(左上右下）最壞情形，線段求交四次。對(duì)于那些非完全可見、又非顯然不可見的線段，需要求交（如線段AD)，求交前先測(cè)試與窗口哪條邊所在直線有交？(按序判斷端點(diǎn)編碼中各位的值ClCtCrCb）1）特點(diǎn)：用編碼方法可快速判斷線段-- 完全可見和顯然不可見。2）特別適用二種場(chǎng)合：大窗口場(chǎng)合；窗口特別小的場(chǎng)合(如,光標(biāo)拾取圖形時(shí), 光標(biāo)看作小的裁剪窗口。）編碼算法特點(diǎn)求交測(cè)試順序固定(左上右下）對(duì)于那些非完全可見、又非顯然不可22設(shè)要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,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è)要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,C23線段的參數(shù)表示x=x0+t△xy=y0+t△y0<=t<=1

△x=x1-x0

△y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。線段的參數(shù)表示241.求出P0P1與兩條始邊的交點(diǎn)參數(shù)t0,t1

,令tl=max(t0,t1,P0)，則tL即為三者中離p1最近的點(diǎn)的參數(shù)2.求出p0p1與兩條終邊的交點(diǎn)參數(shù)t2,t3,令tu=min(t2,t3,P1)，則tU即為三者中離p0最近的點(diǎn)的參數(shù)若tu>tl,則可見線段區(qū)間[tl,tu]t0t1t2t3P01交點(diǎn)計(jì)算P11.求出P0P1與兩條始邊的交點(diǎn)參數(shù)t0,t1,令tl253.始邊和終邊的確定及交點(diǎn)計(jì)算：令QL=△xDL=x0-xLQR=△xDR=xR-x0

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

Qii=L,R,B,TQi<0ti為與始邊交點(diǎn)參數(shù)Qi>0ti為與終邊交點(diǎn)參數(shù)3.始邊和終邊的確定及交點(diǎn)計(jì)算：26當(dāng)Qi=0時(shí)若Di<0時(shí),線段不可見（如圖中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)決定直線段上的可見部分。）

ABEFAB當(dāng)Qi=0時(shí)ABEFAB27三、多邊形裁剪錯(cuò)覺：直線段裁剪的組合？關(guān)鍵：要保持窗口內(nèi)多邊形的邊界部分，而且要將窗框的有關(guān)部分按一定次序插入多邊形的保留邊界之間，從而使剪裁后的多邊形的邊仍然保持封閉狀態(tài)。新的問題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？三、多邊形裁剪錯(cuò)覺：直線段裁剪的組合？282）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何29Sutherland-Hodgman算法思路：將多邊形邊界作為一個(gè)整體，分而治之。將多邊形的各邊先相對(duì)于窗口的某一條邊界進(jìn)行裁剪，然后將裁剪結(jié)果再與另一條邊界進(jìn)行裁剪，如此重復(fù)多次，便可得到最終結(jié)果。流水線過程(左上右下)：左邊的結(jié)果是上邊的開始。亦稱逐邊裁剪算法Sutherland-Hodgman算法思路：將多邊形邊界作30內(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不輸出內(nèi)側(cè)空間與外側(cè)空間PIS可PS31p1p2p3p4p5q1q2q3q4需要設(shè)置二個(gè)表：

輸入頂點(diǎn)表(向量)—存放被裁剪多邊形的頂點(diǎn)p1-pm。

輸出頂點(diǎn)表(線性鏈表)—存放裁剪過程中及結(jié)果的頂點(diǎn)q1-qn。p1p2p3p4p5q1q2q3q4需要設(shè)置二個(gè)表：32q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：裁剪后：輸入頂點(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。q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：33實(shí)現(xiàn)方法：①設(shè)置二個(gè)表

輸入頂點(diǎn)表(向量)—存放被裁剪多邊形的頂點(diǎn)p1-pm。

輸出頂點(diǎn)表(線性鏈表)—存放裁剪過程中及結(jié)果的頂點(diǎn)q1-qn。②輸入頂點(diǎn)表中各頂點(diǎn)要求按一定順序排列，一般可采用順時(shí)針或逆時(shí)針方向。③相對(duì)于裁剪窗口的各條邊界，按頂點(diǎn)表中的順序，逐邊進(jìn)行裁剪。算法中相對(duì)于各窗口邊界的裁剪過程相同，且每次都是相對(duì)于前一次的結(jié)果進(jìn)行處理。實(shí)現(xiàn)方法：算法中相對(duì)于各窗口邊界的裁剪過程相同，且每次都是相34裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多邊形的邊與裁剪邊的交點(diǎn)。順序連接。特點(diǎn)：裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)。可推廣到任意凸多邊形裁剪窗口裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；特點(diǎn)：35問題：一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？AFEDCBV1V2V3V4AFEDCBV1V2V3V4AEDSutherland-Hodgman多邊形裁剪：輸入頂點(diǎn)BAFEDC，輸出頂點(diǎn)：V1AV2V3EDV4Sutherland-Hodgman算法問題：一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小36Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為BWeiler-Athenton算法裁剪窗口為任意多邊形（凸、37主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-B裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界

主多邊形和裁剪多邊形把二維平面分成兩部分。裁剪結(jié)果區(qū)域的邊界38Weiler-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,I8,I10

Weiler-Athenton算法39

Weiler-Atherton（W-A）算法（雙邊裁剪法）可以用一個(gè)有內(nèi)孔的凹多邊形去裁剪另一個(gè)也有內(nèi)孔的凹多邊形。被裁剪的多邊形——主多邊形裁剪區(qū)域——裁剪多邊形

各多邊形的外部邊界取順時(shí)針方向，而其內(nèi)部邊界或孔取逆時(shí)針方向。思路：主多邊形和裁剪多邊形均用它們的頂點(diǎn)表來定義。這兩類交點(diǎn)分別用進(jìn)點(diǎn)表和出點(diǎn)表來存放。主多邊形和裁剪多邊形的邊界若相交，交點(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)）。 Weiler-Atherton（W-A）算法（雙邊裁剪法）40c1c2c3c4s1s2s3s4s5s6s7I1I2I3I4I5I6I7I8裁剪窗口多邊形主多邊形主多邊形裁剪窗口頂點(diǎn)表頂點(diǎn)表

s1c1

I1I8I2I1s2c2

I3I2s3I3I4c3s4I4

I5I5I6c4s5I6

I7I7s6c1I8s7s1起點(diǎn)簡(jiǎn)單例4:

W-A算法進(jìn)行多邊形裁剪進(jìn)點(diǎn)出點(diǎn)c1c2c3c4s1s2s3s4s5s6s7I1I2I3I441算法：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)表為空thenfinish （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算法：42復(fù)雜例5，分析裁剪過程，分別寫出主多邊形、裁剪多邊形的頂點(diǎn)表，以及最終裁剪結(jié)果。復(fù)雜例5，分析裁剪過程，分別寫出主多邊形、裁剪多邊形的頂點(diǎn)表43Weiler-Athenton算法交點(diǎn)的奇異情況處理1.與裁剪多邊形邊重合的主多邊形的邊不參與求交點(diǎn)；2.對(duì)于頂點(diǎn)落在裁剪多邊形的邊上的主多邊形的邊，如果落在該裁剪邊的內(nèi)側(cè)，將該頂點(diǎn)算作交點(diǎn)；而如果這條邊落在該裁剪邊的外側(cè)，將該頂點(diǎn)不看作交點(diǎn)Weiler-Athenton算法交點(diǎn)的奇異情況處理44四、字符裁剪方法點(diǎn)陣字符——每個(gè)字符用一個(gè)位圖(掩膜)來表示，其大小由位圖的尺寸來確定，如7×9，9×16，16×24等。

1111000

010010001001000111000

0100000

0100000

01000001110000

0000000P在字庫(kù)的表示P的顯示結(jié)果四、字符裁剪方法1111000045

矢量字符——選一個(gè)正方形網(wǎng)格，作為字符的局部坐標(biāo)空間，網(wǎng)格的大小可選16×16，32×32，64×64等。每個(gè)字符由構(gòu)成它的筆畫組成，每個(gè)筆畫又由其兩端確定。每個(gè)端點(diǎn)保存它的坐標(biāo)值及連線標(biāo)志。xyop1p2p3p4p5p66363字符的編碼x1y10x2y21x3y30x4y41x5y50x6y61－10表示不連線1表示連線字符結(jié)束標(biāo)志特點(diǎn)：除用直線段表示筆畫外，還可采用二次三次曲線段。對(duì)矢量字符的變換是對(duì)其端點(diǎn)進(jìn)行圖形的幾何變換。矢量字符——選一個(gè)正方形網(wǎng)格，作為字符的局46（一）字符的裁剪

1.簡(jiǎn)單裁剪方法：用點(diǎn)陣字符的掩膜或矢量字符的網(wǎng)格大小作為字符的包圍框，若該包圍框在窗口內(nèi)，則顯示字符；否則，不予顯示。

4.精確裁剪方法：對(duì)于點(diǎn)陣字符，判斷組成其筆畫的每個(gè)像素點(diǎn)是否位于窗口內(nèi)。對(duì)于矢量字符，對(duì)組成其筆畫的每條線段進(jìn)行裁剪。（一）字符的裁剪47二維圖形裁剪裁剪概述線段裁剪直接求交算法；Cohen-Sutherland算法；（重點(diǎn)，算法實(shí)現(xiàn)）

梁友棟-Barsky算法多邊形裁剪

Sutlerland_Hodgman算法（難點(diǎn)，算法實(shí)現(xiàn)）

Weiler-Athenton算法

字符裁剪二維圖形裁剪裁剪概述48裁剪二維圖形裁剪預(yù)備知識(shí)：求交（矩形窗口）裁剪三維裁剪長(zhǎng)方體裁剪體棱錐體體裁剪體直接求交算法編碼裁剪算法中點(diǎn)分割算法……被裁剪對(duì)象：直線段、多邊形、三維實(shí)體……一、裁剪概述裁剪：是裁去窗口之外物體或物體部分的一種操作。裁二維圖形裁剪預(yù)備知識(shí)：求交（矩形窗口）裁剪三維裁剪長(zhǎng)方體49剪裁的應(yīng)用1、從定義的場(chǎng)景中抽取出用于觀察的部分；

2、在三維視圖中標(biāo)識(shí)出可見面；

3、防止線段或?qū)ο蟮倪吔缁煜?/p>

4、用實(shí)體造型來創(chuàng)建對(duì)象；

5、顯示多窗口的環(huán)境；

6、允許選擇圖形的一部分來進(jìn)行拷貝，移動(dòng)和刪除。

剪裁的應(yīng)用1、從定義的場(chǎng)景中抽取出用于觀察的部分；

2、在三50“取景器”=窗口視區(qū)1視區(qū)2（viewport）“取景器”=窗口視區(qū)1視區(qū)251裁剪的目的判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交假定條件矩形裁剪窗口：[xmin,xmax]×[ymin,ymax]待裁剪點(diǎn)或線段：裁剪的目的52點(diǎn)裁剪點(diǎn)(x,y)在窗口內(nèi)的充分必要條件是：

問題：對(duì)于任何多邊形窗口，如何判別？WytWybWxlWxrP1P2P3點(diǎn)裁剪WytWybWxlWxrP1P2P353線段相對(duì)于該窗口的情況有:①線段全部位于窗口的內(nèi)部（A）；②線段全部位于窗口外部（B、C）；③線段的中間部分在窗口內(nèi)，而二端點(diǎn)在窗口外部（D）；④線段的一端在窗口內(nèi)，而另一端在窗口外（E）。x=xLx=xRy=yBy=yTABCDE二、線段裁剪線段相對(duì)于該窗口的情況有:x=xLx=xRy=yBy=yTA54待裁剪線段和窗口的關(guān)系

線段完全可見顯然不可見線段至少有一端點(diǎn)在窗口之外，但非顯然不可見

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

根據(jù)直線段和窗口的關(guān)系可知：（1）整條線在窗口之內(nèi)。此時(shí)，不需剪裁，顯示整條線段。（2）整條線在窗口之外，此時(shí)，不需剪裁，不顯示整條線段。（3）部分線在窗口之內(nèi)，部分線在窗口之外。此時(shí)，需要求出線段與窗口邊界的交點(diǎn)，并將窗口外的線段部分剪裁掉，顯示窗口內(nèi)的部分。直接求交算法基本思想是：判斷直線與窗口的位置關(guān)系，確定該直線56例1設(shè)有直線段P0P1，有一個(gè)矩形裁剪窗口，寫出對(duì)該線段裁剪的算法。1）求出直線P0P1與窗口的交點(diǎn)I，如圖（a）所示。2）取P0I線段顯示，擦除IP1線段，并將P1替換I，即得P0P1線段，裁剪結(jié)束。如圖（b）所示。

P0P1IP0P1（a）（b）例1設(shè)有直線段P0P1，有一個(gè)矩形裁剪窗口，寫出對(duì)該線段裁57求線段與窗口交點(diǎn)設(shè)線段兩端點(diǎn)坐標(biāo)為：和則過這兩點(diǎn)的直線方程為：其中k為斜率。上述直線方程與窗口各邊界的交點(diǎn)為：左：右：下：上：求線段與窗口交點(diǎn)設(shè)線段兩端點(diǎn)坐標(biāo)為：和則過這58基本思想：對(duì)于每條待裁剪的線段P1P2分三種情況處理：①若P1P2完全在窗口內(nèi)，則顯示該線段P1P2，簡(jiǎn)稱“取”之；②若P1P2完全在窗口外，則丟棄該線段，簡(jiǎn)稱“舍”之；③若線段既不滿足“取”的條件，也不滿足“舍”的條件，則求線段與窗口邊界的交點(diǎn)，在交點(diǎn)處把線段分為兩段，其中一段完全在窗口外，可舍棄之，然后對(duì)另一段重復(fù)上述處理。

核心思想：分區(qū)編碼和線段分割。

Cohen-Sutherland算法(編碼算法)基本思想：對(duì)于每條待裁剪的線段P1P2分三種情況處理：Co59分區(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的左方。000000010010100001001001101001010110x=xLx=xRy=yBy=yT11111

1

1

1#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8編碼原則分區(qū)編碼方法：圖形區(qū)域劃分成九個(gè)區(qū)域。000000010060每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下右左；編碼方法練習(xí)：請(qǐng)給出右圖的線段端點(diǎn)編碼（端點(diǎn)編碼：定義為它所在區(qū)域的編碼）x=xLx=xRy=yBy=yTABCDE每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下右左；編碼方61第一步判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進(jìn)入第二步；第二步判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；否則進(jìn)行第三步；第三步求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束

Cohen-Sutherland算法步驟第一步判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，Cohen-62當(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í)，線段為顯然不可見63當(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í)，線段為顯然不可見64對(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ù)這一過程，直到全部線段均被舍棄或保留為止。對(duì)一條線段的可見性測(cè)試方法：65例：分別給下列直線段編碼，并判斷是否需要剪裁。P1P2C1=0001C2=0000P1P2C1=0100C2=0101BCP1P2C1=0101C2=1010P1P2ADC1=0000C2=0000例：分別給下列直線段編碼，并判斷是否需要剪裁。P1P2C1=66例：Cohen-SutherLand算法過程：例：Cohen-SutherLand算法過程：67過程：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|codeB≠0，對(duì)AB不能全部保留；又因?yàn)閏odeA&codeB=0，對(duì)AB不能全部舍棄，因此要對(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ì)剩下的直線段AB再進(jìn)行判斷，現(xiàn)在A編碼為0000，B編碼為0000，由于codeA|codeB=0，全在窗口中，故全部保留。最后得到裁剪后的線段為AB，算法結(jié)束。過程：68求交測(cè)試順序固定(左上右下）最壞情形，線段求交四次。對(duì)于那些非完全可見、又非顯然不可見的線段，需要求交（如線段AD)，求交前先測(cè)試與窗口哪條邊所在直線有交？(按序判斷端點(diǎn)編碼中各位的值ClCtCrCb）1）特點(diǎn)：用編碼方法可快速判斷線段-- 完全可見和顯然不可見。2）特別適用二種場(chǎng)合：大窗口場(chǎng)合；窗口特別小的場(chǎng)合(如,光標(biāo)拾取圖形時(shí), 光標(biāo)看作小的裁剪窗口。）編碼算法特點(diǎn)求交測(cè)試順序固定(左上右下）對(duì)于那些非完全可見、又非顯然不可69設(shè)要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,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è)要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,C70線段的參數(shù)表示x=x0+t△xy=y0+t△y0<=t<=1

△x=x1-x0

△y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。線段的參數(shù)表示711.求出P0P1與兩條始邊的交點(diǎn)參數(shù)t0,t1

,令tl=max(t0,t1,P0)，則tL即為三者中離p1最近的點(diǎn)的參數(shù)2.求出p0p1與兩條終邊的交點(diǎn)參數(shù)t2,t3,令tu=min(t2,t3,P1)，則tU即為三者中離p0最近的點(diǎn)的參數(shù)若tu>tl,則可見線段區(qū)間[tl,tu]t0t1t2t3P01交點(diǎn)計(jì)算P11.求出P0P1與兩條始邊的交點(diǎn)參數(shù)t0,t1,令tl723.始邊和終邊的確定及交點(diǎn)計(jì)算：令QL=△xDL=x0-xLQR=△xDR=xR-x0

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

Qii=L,R,B,TQi<0ti為與始邊交點(diǎn)參數(shù)Qi>0ti為與終邊交點(diǎn)參數(shù)3.始邊和終邊的確定及交點(diǎn)計(jì)算：73當(dāng)Qi=0時(shí)若Di<0時(shí),線段不可見（如圖中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)決定直線段上的可見部分。）

ABEFAB當(dāng)Qi=0時(shí)ABEFAB74三、多邊形裁剪錯(cuò)覺：直線段裁剪的組合？關(guān)鍵：要保持窗口內(nèi)多邊形的邊界部分，而且要將窗框的有關(guān)部分按一定次序插入多邊形的保留邊界之間，從而使剪裁后的多邊形的邊仍然保持封閉狀態(tài)。新的問題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？三、多邊形裁剪錯(cuò)覺：直線段裁剪的組合？752）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何76Sutherland-Hodgman算法思路：將多邊形邊界作為一個(gè)整體，分而治之。將多邊形的各邊先相對(duì)于窗口的某一條邊界進(jìn)行裁剪，然后將裁剪結(jié)果再與另一條邊界進(jìn)行裁剪，如此重復(fù)多次，便可得到最終結(jié)果。流水線過程(左上右下)：左邊的結(jié)果是上邊的開始。亦稱逐邊裁剪算法Sutherland-Hodgman算法思路：將多邊形邊界作77內(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不輸出內(nèi)側(cè)空間與外側(cè)空間PIS可PS78p1p2p3p4p5q1q2q3q4需要設(shè)置二個(gè)表：

輸入頂點(diǎn)表(向量)—存放被裁剪多邊形的頂點(diǎn)p1-pm。

輸出頂點(diǎn)表(線性鏈表)—存放裁剪過程中及結(jié)果的頂點(diǎn)q1-qn。p1p2p3p4p5q1q2q3q4需要設(shè)置二個(gè)表：79q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：裁剪后：輸入頂點(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。q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：80實(shí)現(xiàn)方法：①設(shè)置二個(gè)表

輸入頂點(diǎn)表(向量)—存放被裁剪多邊形的頂點(diǎn)p1-pm。

輸出頂點(diǎn)表(線性鏈表)—存放裁剪過程中及結(jié)果的頂點(diǎn)q1-qn。②輸入頂點(diǎn)表中各頂點(diǎn)要求按一定順序排列，一般可采用順時(shí)針或逆時(shí)針方向。③相對(duì)于裁剪窗口的各條邊界，按頂點(diǎn)表中的順序，逐邊進(jìn)行裁剪。算法中相對(duì)于各窗口邊界的裁剪過程相同，且每次都是相對(duì)于前一次的結(jié)果進(jìn)行處理。實(shí)現(xiàn)方法：算法中相對(duì)于各窗口邊界的裁剪過程相同，且每次都是相81裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多邊形的邊與裁剪邊的交點(diǎn)。順序連接。特點(diǎn)：裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)?？赏茝V到任意凸多邊形裁剪窗口裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；特點(diǎn)：82問題：一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？AFEDCBV1V2V3V4AFEDCBV1V2V3V4AEDSutherland-Hodgman多邊形裁剪：輸入頂點(diǎn)BAFEDC，輸出頂點(diǎn)：V1AV2V3EDV4Sutherland-Hodgman算法問題：一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小83Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為BWeiler-Athenton算法裁剪窗口為任意多邊形（凸、84主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-B裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界

主多邊形和裁剪多邊形把二維平面分成兩部分。裁剪結(jié)果區(qū)域的邊界85Weiler-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,I8,I10

Weiler-Athenton算法86

Weiler-Atherton（W-A）算法（雙邊裁剪法）可以用一個(gè)有內(nèi)孔的凹多邊形去裁剪另一個(gè)也有內(nèi)孔的凹多邊形。被裁剪的多邊形——主多邊形裁剪區(qū)域——裁剪多邊形

各多邊形的外部邊界取順時(shí)針方向，而其內(nèi)部邊界或孔取逆時(shí)針方向。思路：主多邊形和裁剪多邊形均用它們的頂點(diǎn)表來定義。這兩類交點(diǎn)分別用進(jìn)點(diǎn)表和出點(diǎn)表來存放。主多邊形和裁剪多邊形的邊界若相交，交點(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)）。 Weiler-Atherton（W-A）算法（雙邊裁剪法）87c1c2c3c4s1s2s3s4s5s6s7I1I2I3I4I5I6I7I8裁剪窗口多邊形主多邊形主