圖形學(xué)之二維裁剪.ppt

《圖形學(xué)之二維裁剪.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第五講二維裁剪基本目的：判斷圖形元素是否落在窗口區(qū)域之內(nèi)。顯示部分畫面，指定圖形內(nèi)容，窗口系統(tǒng)。地圖顯示。圖形編輯圖形裁剪算法，直接影響圖形系統(tǒng)的效率。2021/7/171GraphicsLab.PKU二維裁剪兩個(gè)步驟：圖元在窗口區(qū)域內(nèi)外的判別；圖形元素與窗口的求交；裁剪?掃描轉(zhuǎn)換:點(diǎn)陣圖形在設(shè)備坐標(biāo)系中進(jìn)行，算法效率不高，適合求交難度大的圖形。裁剪?掃描轉(zhuǎn)換:點(diǎn)、線、多邊形等簡(jiǎn)單圖形，在世界坐標(biāo)系中進(jìn)行。分析裁剪。2021/7/172GraphicsLab.PKU5.1直線段裁剪是基礎(chǔ)。裁剪線段與窗口的關(guān)系：(1)線段完全可見；(2)顯然不可見

2、；(3)其它提高裁剪效率：快速判斷情形(1)(2)，對(duì)于情形(3)，設(shè)法減少求交次數(shù)和每次求交時(shí)所需的計(jì)算量。點(diǎn)裁剪。2021/7/173GraphicsLab.PKU5.1.2直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。2021/7/174GraphicsLab.PKU5.1.3Cohen-SutherLand算法(編碼算法)裁剪過程是遞歸的。由窗口四條邊所在直線把二維平面分成9個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼CtCbCrCl，上下右左；各位編碼含義：上面：ify>ymax,Ct=1,else,0;下面：ify

3、e,0；右面：ifx>xmax,Cr=1,else,0;左面：ifx

4、種情形：大窗口場(chǎng)合；窗口特別小場(chǎng)合(光標(biāo)拾取圖形)，光標(biāo)看作小的裁剪窗口。2021/7/178GraphicsLab.PKU5.1.4Nicholl-Lee-Nicholl算法消除C-S算法中多次求交的情況?；鞠敕ǎ簩?duì)2D平面的更細(xì)的劃分。2021/7/179GraphicsLab.PKU假定P0點(diǎn)落在區(qū)域0，4，52021/7/1710GraphicsLab.PKU步驟：1.區(qū)域細(xì)分(9個(gè)區(qū)域)，只考察P0在0，4，5情形，其它類似。2.P0點(diǎn)向窗口的四角點(diǎn)引射線，把平面區(qū)域分成4個(gè)有意義的區(qū)域。判斷P1所在區(qū)域位置，可判定P0、P1與窗口那

5、條邊求交。3.用斜率判P1所在區(qū)域4.求交點(diǎn)，確定線段可見部分。特點(diǎn)：效率較高，但僅適合二維矩形窗口。2021/7/1711GraphicsLab.PKU2021/7/1712GraphicsLab.PKU5.1.5中點(diǎn)分割法想法：從P0點(diǎn)出發(fā)找出距P0最近的可見點(diǎn)，從P1點(diǎn)出發(fā)找出距P1最近的可見點(diǎn)。取中點(diǎn)Pm=(P1+P2)/2。（算法見框圖）2021/7/1713GraphicsLab.PKU2021/7/1714GraphicsLab.PKU對(duì)分辯率為2N*2N的顯示器，上述二分過程至多進(jìn)行N次。主要過程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)

6、。適合平行計(jì)算。2021/7/1715GraphicsLab.PKU5.1.6Liang-Barsky算法看作點(diǎn)集之間的交集，即為裁剪結(jié)果。Q0Q1為誘導(dǎo)窗口，一維窗口，二維裁剪簡(jiǎn)化成一維裁剪。2021/7/1716GraphicsLab.PKU一維裁剪問題P0P1至少部分可見的充要條件是Max(0,t0)<=min(1,t1)且可見部分的參數(shù)區(qū)間為[Max(0,t0),min(1,t1)]2021/7/1717GraphicsLab.PKU誘導(dǎo)窗口計(jì)算：假設(shè)直線l與窗口左、右、上、下四邊的交點(diǎn)為L(zhǎng)，R，T，BP0P1的可見部分VW=P0P1∩L

7、R∩TB這就是二維裁剪問題的解。2021/7/1718GraphicsLab.PKU用參數(shù)域方法定可見部分：始邊，終邊(對(duì)窗口邊而言)由有向直線段方向定。誘導(dǎo)窗口與P0P1的交點(diǎn)可用直線的參數(shù)區(qū)間來表示。交點(diǎn)參數(shù)的簡(jiǎn)單確定：用X或Y坐標(biāo)邊的長(zhǎng)度比。2021/7/1719GraphicsLab.PKU5.1.7參數(shù)化算法(Lyrus-Beck)算法考慮凸多邊形區(qū)域R和直線段P1P2P1P2=(P2-P1)*t+P1凸多邊形的性質(zhì)：P(t)在凸多邊形內(nèi)的充要條件是，對(duì)于凸多邊形邊界上任意一點(diǎn)A和該點(diǎn)處內(nèi)法向N，都有N·(P(t)-A)>02021/7

8、/1720GraphicsLab.PKUAP1P2R2021/7/1721GraphicsLab.PKUk條邊的多邊形，可見線段參數(shù)區(qū)間