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

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

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

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

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

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

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

6、。適合平行計算。2021/7/1715GraphicsLab.PKU5.1.6Liang-Barsky算法看作點集之間的交集，即為裁剪結(jié)果。Q0Q1為誘導(dǎo)窗口，一維窗口，二維裁剪簡化成一維裁剪。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)窗口計算：假設(shè)直線l與窗口左、右、上、下四邊的交點為L，R，T，BP0P1的可見部分VW=P0P1∩L

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

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