1第五章圖形變換與裁剪（三）

5.5二維線段裁剪蘇小紅計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)25.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法2多邊形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

31.直線段裁剪(1/18)裁剪（clipping）的目的判斷圖形元素是否在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交裁剪與覆蓋的區(qū)別41.直線段裁剪(2/18)裁剪窗口矩形、圓形、一般多邊形被裁剪對(duì)象線段、多邊形、曲線、字符設(shè)計(jì)裁剪算法的核心問題效率高，速度快51.直線段裁剪(3/18)把直線當(dāng)作點(diǎn)的集合，逐點(diǎn)裁剪點(diǎn)(x,y)在窗口內(nèi)的充分必要條件是：

問題：極其費(fèi)時(shí)，精度不高。61.直線段裁剪(4/18)把直線當(dāng)作一個(gè)整體來裁剪矩形裁剪窗口：

[xmin，xmax]

[ymin，ymax]待裁剪線段：前提：任何平面線段在凸多邊形窗口進(jìn)行裁剪后，落在窗口內(nèi)的線段不會(huì)多于1條。71.直線段裁剪(5/18)待裁剪線段和窗口的關(guān)系完全落在窗口內(nèi),完全落在窗口外,部分在內(nèi)，部分在外.85.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法9直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。1.直線段裁剪(6/18)105.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法11Cohen-Sutherland算法1.直線段裁剪(7/18)為提高效率，該算法強(qiáng)調(diào)：快速判斷情形(1)(2)；減少情形(3)的求交次數(shù)和求交所需的計(jì)算量。待裁剪線段和窗口的關(guān)系完全落在窗口內(nèi),完全落在窗口外,部分在內(nèi)，部分在外.12Cohen-Sutherland算法算法步驟：判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見，轉(zhuǎn)至第4步；判別線段是否為顯然不可見，如果是，則裁剪結(jié)束，轉(zhuǎn)至第4步；求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新進(jìn)行第1步處理，結(jié)束裁剪過程是遞歸的。1.直線段裁剪(8/18)13關(guān)鍵問題：如何快速判別完全可見和完全不可見線段？解決方法——編碼：由窗口四條邊所在直線把二維平面分成9個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下右左；Cohen-Sutherland

算法1.直線段裁剪(9/18)11100000011100000011100000011100000014端點(diǎn)編碼：定義為它所在區(qū)域的編碼快速判斷“完全不可見”

線段兩端點(diǎn)編碼的邏輯“與”運(yùn)算結(jié)果非零

，則完全不可見。Cohen-Sutherland算法1.直線段裁剪(10/18)所以也稱為編碼裁剪算法15逐個(gè)端點(diǎn)判斷其編碼ClCtCrCb中各位是否為“1”，若是，則需求交。最壞情形：線段求交四次。對(duì)于那些部分可見又部分不可見的線段，需要求交，求交前先測(cè)試與窗口哪條邊所在直線有交？Cohen-Sutherland算法1.直線段裁剪(11/18)16

1）特點(diǎn)：用編碼方法可快速判斷線段-——

完全可見或完全不可見。

2）特別適用兩種場(chǎng)合：大窗口場(chǎng)合；窗口特別小的場(chǎng)合（如：光標(biāo)拾取圖形時(shí)，光標(biāo)看作小的裁剪窗口）1.直線段裁剪(12/18)Cohen-Sutherland算法175.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法

中點(diǎn)分割裁剪算法梁友棟-Barsky算法18中點(diǎn)分割法基本思想：利用對(duì)分搜索思想搜索交點(diǎn)從P1點(diǎn)出發(fā)找出距P1最近的可見點(diǎn)從P2點(diǎn)出發(fā)找出距P2最近的可見點(diǎn)不斷地在中點(diǎn)處將線段一分為二，對(duì)每段線段重復(fù)Cohen-Sutherland裁剪算法的線段可見性測(cè)試方法，直至找到每段線段與窗口邊界線的交點(diǎn)或分割子段的長(zhǎng)度充分小可視為一點(diǎn)為止取中點(diǎn)Pm=(P1+P2)/2。P2P1從P1點(diǎn)出發(fā)找距P1最近的可見點(diǎn)PmP1用P1Pm代替P1P2P2P2用PmP2代替P1P2PmP11.直線段裁剪(13/18)191.直線段裁剪(13/18)優(yōu)點(diǎn)：算法原理和編碼裁剪是一致的，不同之處在于用移位運(yùn)算代替求交計(jì)算適合硬件實(shí)現(xiàn)中點(diǎn)分割法205.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法

梁友棟-Barsky算法21Liang-Barsky裁剪算法

P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分1.直線段裁剪(14/18)基本思想：把二維裁剪化為一維裁剪問題，并向x（或y）方向投影以決定可見線段22Liang-Barsky裁剪算法

直線L與區(qū)域的交：1.直線段裁剪(15/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB當(dāng)Q為空集時(shí)，線段AB不可能在窗口中有可見線段。當(dāng)Q不為空集時(shí)，Q可看成是一個(gè)一維窗口

23存在可見線段的充要條件即不為空集。1.直線段裁剪(16/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB當(dāng)Q為空集時(shí)，線段AB不可能在窗口中有可見線段。當(dāng)Q不為空集時(shí)，Q可看成是一個(gè)一維窗口。

24Liang-Barsky裁剪算法

1.直線段裁剪(17/18)向x軸投影，得到可見線段端點(diǎn)的x坐標(biāo)變化范圍

左端點(diǎn)x坐標(biāo)右端點(diǎn)x坐標(biāo)RS,AB,TU三條線段的交集的端點(diǎn)坐標(biāo)等價(jià)于求三條線段的左端點(diǎn)的最大值，右端點(diǎn)的最小值

y坐標(biāo)可由將x坐標(biāo)代入直線方程計(jì)算得到P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分URTS25Liang-Barsky裁剪算法AB有可見部分的充要條件也可表示為1.直線段裁剪(18/18)P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分URTS265.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法2多邊形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

272.多邊形裁剪（Ploygonclipping）-1/3錯(cuò)覺：多邊形裁剪是直線段裁剪的組合？新的問題：圖1因丟失頂點(diǎn)信息而去法確定裁剪區(qū)域ABAB圖2原來封閉的多邊形變成了孤立的線段邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它2812123(a)(b)(c)AB裁剪后的多邊形頂點(diǎn)形成的幾種情況分裂為幾個(gè)多邊形2.多邊形裁剪-2/329關(guān)鍵：不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)還在于形成正確的頂點(diǎn)序列常用算法

Sutherland_Hodgman算法

Weiler-Atherton算法

2.多邊形裁剪-3/330Sutherland-Hodgman算法-1/4分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：左邊的結(jié)果是右邊的開始。亦稱逐邊裁剪算法31Sutherland-Hodgman算法-2/4內(nèi)側(cè)空間與外側(cè)空間多邊形的邊與半空間的關(guān)系

線段與當(dāng)前裁剪邊的位置關(guān)系可見一側(cè)窗口(a)輸出Pi+1當(dāng)前裁剪邊Pi+1Pi可見一側(cè)窗口(a)無輸出當(dāng)前裁剪邊Pi+1Pi可見一側(cè)窗口(a)輸出I當(dāng)前裁剪邊Pi+1Pi可見一側(cè)窗口(a)輸出I和Pi+1當(dāng)前裁剪邊Pi+1PiII32Sutherland-Hodgman算法-3/4裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多邊形的邊與裁剪邊的交點(diǎn)。順序連接。幾點(diǎn)說明：裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)?？赏茝V到任意凸多邊形裁剪窗口33Sutherland-Hodgman算法-4/4

存在的問題逐邊裁剪要求裁剪窗口為凸多邊形，那么凹多邊形窗口怎么辦？

逐邊裁剪法對(duì)凹多邊形裁剪時(shí)，裁剪后分裂為幾個(gè)多邊形，這幾個(gè)多邊形沿邊框產(chǎn)生多余的線段？圖6逐邊裁剪法對(duì)凹多邊形裁剪時(shí)可能出現(xiàn)的問題321876954103217654108932174108956原圖對(duì)左邊裁對(duì)頂邊裁32174108956對(duì)右邊裁對(duì)底邊裁Demo34Weiler-Atherton算法-1/7裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為SP裁剪多邊形：裁剪窗口，記為CP35約定：SP與CP均用它們頂點(diǎn)的環(huán)形鏈表定義外邊界取順時(shí)針方向內(nèi)邊界取逆時(shí)針方向使得沿多邊形的邊走動(dòng)，其右邊為多邊形的內(nèi)部。Weiler-Atherton算法-2/7C2C1C3C4C8C7C5C6I1I8I2I3I4I5I6I736SP和CP把二維平面分成兩部分。內(nèi)裁剪：SP∩CP外裁剪：SP-CPWeiler-Atherton算法-3/7裁剪結(jié)果區(qū)域的邊界由兩部分構(gòu)成：SP的部分邊界CP的部分邊界且在交點(diǎn)處，邊界發(fā)生交替即由SP邊界轉(zhuǎn)至CP邊界或由CP邊界轉(zhuǎn)至SP邊界

37Weiler-Atherton算法-4/7如果SP與CP有交點(diǎn)，則交點(diǎn)成對(duì)出現(xiàn)，它們被分為如下兩類：進(jìn)點(diǎn)：SP邊界由此進(jìn)入CP

如，I1,I3,I5,I7,I9,I11出點(diǎn)：SP邊界由此離開CP

如，I0,I2,I4,I6,I8,I10

38Weiler-Atherton算法-5/7由任一個(gè)進(jìn)點(diǎn)出發(fā)，沿SP的邊，跟蹤檢測(cè)其與CP的交點(diǎn)（前交點(diǎn)），并判斷該交點(diǎn)是進(jìn)點(diǎn)還是出點(diǎn)。若是進(jìn)點(diǎn)：則沿SP邊所示方向收集頂點(diǎn)序列。若是出點(diǎn)：則從此點(diǎn)開始，檢測(cè)CP的邊所示方向收集頂點(diǎn)序列。如此交替沿兩個(gè)多邊形的邊行進(jìn)。直至回到跟蹤的起始點(diǎn)為止。39Weiler-Atherton算法-6/7C2C1C3C4S1S2S3S4S5S6I1I