圖型變換與裁減

關(guān)于圖型變換與裁減1第1頁，課件共50頁，創(chuàng)作于2023年2月2圖形裁剪

直線段的裁剪多邊形的裁剪第2頁，課件共50頁，創(chuàng)作于2023年2月3圖形裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過程稱為裁剪。第3頁，課件共50頁，創(chuàng)作于2023年2月4裁剪的目的判斷圖形元素是否在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交裁剪、覆蓋第4頁，課件共50頁，創(chuàng)作于2023年2月5裁剪窗口矩形、圓形、一般多邊形被裁剪對(duì)象線段、多邊形、曲線、字符裁剪的策略先裁剪，后變換先變換，后裁剪裁剪算法的核心問題效率第5頁，課件共50頁，創(chuàng)作于2023年2月6直線段裁剪直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。第6頁，課件共50頁，創(chuàng)作于2023年2月7直線段裁剪點(diǎn)裁剪點(diǎn)(x,y)在窗口內(nèi)的充分必要條件是：

問題：極其費(fèi)時(shí)第7頁，課件共50頁，創(chuàng)作于2023年2月8直線段裁剪把直線當(dāng)作一個(gè)整體來裁剪矩形裁剪窗口：

[Xmin,Xmax]×[Ymin,Ymax]待裁剪線段：前提：任何平面線段在凸多邊形窗口進(jìn)行裁剪后，落在窗口內(nèi)的線段不會(huì)多于1條。第8頁，課件共50頁，創(chuàng)作于2023年2月9直線段裁剪待裁剪線段和窗口的關(guān)系完全落在窗口內(nèi)完全落在窗口外部分在內(nèi)，部分在外第9頁，課件共50頁，創(chuàng)作于2023年2月10直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)算法梁友棟－barskey算法第10頁，課件共50頁，創(chuàng)作于2023年2月11直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。第11頁，課件共50頁，創(chuàng)作于2023年2月12直線段裁剪直接求交算法Cohen-Sutherland算法中點(diǎn)算法梁友棟－barskey算法第12頁，課件共50頁，創(chuàng)作于2023年2月13直線段裁剪為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：1.快速判斷情形(1)(2)；2.設(shè)法減少情形(3)求交次數(shù)和每次求交時(shí)所需的計(jì)算量待裁剪線段和窗口的關(guān)系完全落在窗口內(nèi)完全落在窗口外部分在內(nèi)，部分在外第13頁，課件共50頁，創(chuàng)作于2023年2月14Cohen-Sutherland算法(編碼算法)算法步驟：判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進(jìn)入第二步；判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；否則進(jìn)行第三步；求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新進(jìn)行1、2判斷，直至結(jié)束。裁剪過程是遞歸的。第14頁，課件共50頁，創(chuàng)作于2023年2月15編碼方法：由窗口四條邊所在直線把二維平面分成9個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼， CtCbCrCl，上下右左；Cohen-Sutherland算法第15頁，課件共50頁，創(chuàng)作于2023年2月16100110001010000100000010010101000110第16頁，課件共50頁，創(chuàng)作于2023年2月此算法也稱為編碼裁剪算法端點(diǎn)編碼：定義為它所在區(qū)域的編碼結(jié)論：當(dāng)線段的兩個(gè)端點(diǎn)的編碼的邏輯“與”非零時(shí)，顯然不可見。邏輯“或”為零時(shí)，顯然可見。Cohen-Sutherland算法100000010010000001001001010101101010窗口bca第17頁，課件共50頁，創(chuàng)作于2023年2月18對(duì)于那些非完全可見、又非完全不可見的線段，需要求交，求交前先測(cè)試與窗口哪條邊所在直線有交。Cohen-Sutherland算法

逐個(gè)端點(diǎn)判斷其編碼CtCbCrCl中各位是否為1，若是，則需求交最壞情形線段求交四次第18頁，課件共50頁，創(chuàng)作于2023年2月19Cohen-Sutherland裁剪如何判定應(yīng)該與窗口的哪條邊求交呢？ 編碼中對(duì)應(yīng)位為1的邊。計(jì)算線段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);}第19頁，課件共50頁，創(chuàng)作于2023年2月201）特點(diǎn)： 用編碼方法可快速判斷線段——

完全可見或完全不可見。

2）特別適用二種場(chǎng)合：大窗口場(chǎng)合窗口特別小的場(chǎng)合

(如：光標(biāo)拾取圖形時(shí)，光標(biāo)看作小的裁剪窗口)Cohen-Sutherland算法的特點(diǎn)第20頁，課件共50頁，創(chuàng)作于2023年2月21直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)算法梁友棟－barskey算法第21頁，課件共50頁，創(chuàng)作于2023年2月22中點(diǎn)分割裁剪算法基本思想：從P0點(diǎn)出發(fā)找出離P0最近的可見點(diǎn)，和從P1點(diǎn)出發(fā)找出離P1最近的可見點(diǎn)。這兩個(gè)可見點(diǎn)的連線就是原線段的可見部分。與Cohen-Sutherland算法一樣首先對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況，對(duì)前兩種情況，進(jìn)行一樣的處理；對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。A、B分別為距P0

、P1最近的可見點(diǎn)，Pm為P0P1中點(diǎn)。第22頁，課件共50頁，創(chuàng)作于2023年2月23中點(diǎn)分割算法-求線段與窗口的交點(diǎn)從P0出發(fā)找距離P0最近可見點(diǎn)采用中點(diǎn)分割方法先求出P0P1的中點(diǎn)Pm；若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點(diǎn)一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1；再對(duì)新的P0P1求中點(diǎn)Pm。重復(fù)上述過程，直到PmP1長(zhǎng)度小于給定的控制常數(shù)為止，此時(shí)Pm收斂于交點(diǎn)；從P1出發(fā)找距離P1最近可見點(diǎn)采用上面類似方法。第23頁，課件共50頁，創(chuàng)作于2023年2月24中點(diǎn)分割裁剪算法第24頁，課件共50頁，創(chuàng)作于2023年2月25主要過程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)，它可以用右移位來代替除法，這樣就大大加快了速度。中點(diǎn)分割裁剪算法第25頁，課件共50頁，創(chuàng)作于2023年2月26直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)算法梁友棟－barskey算法第26頁，課件共50頁，創(chuàng)作于2023年2月27Liang-Barsky裁剪算法

直線L與區(qū)域的交：當(dāng)Q為空集時(shí)，線段AB不可能在窗口中有可見線段。當(dāng)Q不為空集時(shí)，Q可看成是一個(gè)一維窗口P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分直線段裁剪(13/15)基本思想：把二維裁剪化為一維裁剪問題，并向x（或y）方向投影以決定可見線段。第27頁，課件共50頁，創(chuàng)作于2023年2月28Liang-Barsky裁剪算法

P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分直線段裁剪(14/15)存在可見線段的充要條件

不為空集

向x軸投影，就得到可見線段上點(diǎn)的坐標(biāo)的變化范圍為

左端點(diǎn)右端點(diǎn)第28頁，課件共50頁，創(chuàng)作于2023年2月29Liang-Barsky裁剪算法AB有可見部分的充分必要條件也可表示為直線段裁剪(15/15)第29頁，課件共50頁，創(chuàng)作于2023年2月30二維線段裁剪直線段裁剪直接求交算法Cohen-Sutherland算法中點(diǎn)算法梁友棟－barskey算法多邊形裁剪Sutherland-Hodgman算法Weiler-Atherton算法第30頁，課件共50頁，創(chuàng)作于2023年2月多邊形裁剪用直線段裁剪算法，可以嗎？新的問題：圖1因丟失頂點(diǎn)信息而無法確定裁剪區(qū)域ABAB圖2原來封閉的多邊形變成了孤立的線段邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它圖1因丟失頂點(diǎn)信息而無法確定裁剪區(qū)域ABAB圖2原來封閉的多邊形變成了孤立的線段第31頁，課件共50頁，創(chuàng)作于2023年2月12123(a)(b)(c)AB圖3裁剪后的多邊形頂點(diǎn)形成的幾種情況分裂為幾個(gè)多邊形多邊形裁剪第32頁，課件共50頁，創(chuàng)作于2023年2月33關(guān)鍵：不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)還在于形成正確的頂點(diǎn)序列常用的方法Sutherland-Hodgman算法Weiler-Atherton算法第33頁，課件共50頁，創(chuàng)作于2023年2月34Sutherland-Hodgman算法分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法第34頁，課件共50頁，創(chuàng)作于2023年2月Sutherland-Hodgman算法基本思想是一次用窗口的一條邊裁剪多邊形?？紤]窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線，該線把平面分成兩個(gè)部分:可見一側(cè)，不可見一側(cè)。多邊形的各條邊的兩端點(diǎn)S、P。它們與裁剪線的位置關(guān)系只有四種：第35頁，課件共50頁，創(chuàng)作于2023年2月36Sutherland-Hodgman算法情況（1）僅輸出頂點(diǎn)P；情況（2）輸出0個(gè)頂點(diǎn)；情況（3）輸出線段SP與裁剪線的交點(diǎn)I；情況（4）輸出線段SP與裁剪線的交點(diǎn)I和終點(diǎn)PII第36頁，課件共50頁，創(chuàng)作于2023年2月37Sutherland-Hodgman算法裁剪結(jié)果的構(gòu)成裁剪邊內(nèi)側(cè)的原頂點(diǎn)多邊形的邊與裁剪邊的交點(diǎn)順序連接幾點(diǎn)說明裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)可推廣到任意凸多邊形裁剪窗口第37頁，課件共50頁，創(chuàng)作于2023年2月38Sutherland-Hodgeman算法缺點(diǎn)：只能正確處理凸多邊形，對(duì)凹多邊形怎么辦呢？對(duì)凹多邊形來說，裁剪后的多邊形有兩個(gè)或者多個(gè)分離部分的時(shí)候，就對(duì)出現(xiàn)多余的線段。因?yàn)橹挥幸粋€(gè)輸出頂點(diǎn)表，所以表中最后一個(gè)頂點(diǎn)總是連著第一個(gè)頂點(diǎn)。第38頁，課件共50頁，創(chuàng)作于2023年2月圖6逐邊裁剪法對(duì)凹多邊形裁剪時(shí)可能出現(xiàn)的問題321876954103217654108932174108956原圖對(duì)左邊裁對(duì)頂邊裁32174108956對(duì)右邊裁對(duì)底邊裁↘第39頁，課件共50頁，創(chuàng)作于2023年2月40

解決這個(gè)問題的方法：一是把凹多邊形分割成若干個(gè)凸多邊形，然后分別處理各個(gè)凸多邊形。二是Weiler-Atherton算法。第40頁，課件共50頁，創(chuàng)作于2023年2月41Weiler-Atherton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為SP裁剪多邊形：裁剪窗口，記為CP第41頁，課件共50頁，創(chuàng)作于2023年2月42約定：SP與CP均用它們頂點(diǎn)的環(huán)形鏈表定義外邊界取順時(shí)針方向內(nèi)邊界取逆時(shí)針方向(多邊形內(nèi)部總在其右邊)Weiler-Atherton算法第42頁，課件共50頁，創(chuàng)作于2023年2月43SP和CP把二維平面分成兩部分。內(nèi)裁剪：SP∩CP外裁剪：SP-CPWeiler-Atherton算法裁剪結(jié)果由兩部分構(gòu)成：1.SP的部分邊界2.CP的部分邊界且在交點(diǎn)處邊界發(fā)生交替即由SP的邊界轉(zhuǎn)至CP的邊界或由CP的邊界轉(zhuǎn)至SP的邊界

第43頁，課件共50頁，創(chuàng)作于2023年2月44Weiler-Atherton算法主多邊形與裁剪多邊形交點(diǎn)成對(duì)出現(xiàn)分為如下兩類：進(jìn)點(diǎn)：主多邊形SP邊界由此進(jìn)入裁剪多邊形CP內(nèi)出點(diǎn)：主多邊形邊界由此離開裁剪多邊形區(qū)域.

第44頁，課件共50頁，創(chuàng)作于2023年2月進(jìn)點(diǎn)：SP邊界由此進(jìn)入CP如：I1、I3、I5、I7出點(diǎn)：SP邊界由此離開CP如：I2、I4、I6、I8C2C1C3C4S1S2S3S4S5S6I1I2I3I4I5I6I7I8裁剪多邊形CP主多邊形SP第45頁，課件共50頁，創(chuàng)作于2023年2月46Weiler-Athenton算法由任一進(jìn)點(diǎn)出發(fā)，沿SP的邊，跟蹤檢測(cè)其與