資源描述：
《《維圖形裁剪》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第七講二維圖形裁剪在使用計算機處理圖形信息時，計算機內(nèi)部存儲的圖形往往比較大，而屏幕顯示的只是圖的一部分。因此需要確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。在進(jìn)行裁剪時，對應(yīng)于屏幕顯示的那部分區(qū)域稱為窗口，一般窗口定義為矩形，由上、下、左、右四條邊圍成。裁剪的實質(zhì)，就是決定圖形中哪些點、線段、文字以及多邊形在窗口之內(nèi)。主要內(nèi)容1.點的裁剪2.直線的裁剪3.多邊形的裁剪4.字符的裁剪1.點的裁剪設(shè)窗口由x=xL,x=xR,y=yB,y=yT圍成。對于點(x,y)判別兩對不等式：xL<=x<=xR，yB<=y<=yT；若
2、四個不等式均成立，則點在窗口之內(nèi)；否則，點在窗口之外。最簡單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點之后，再判斷各點是否在窗內(nèi)。但那樣太費時，一般不可取。這是因為有些圖形組成部分全部在窗口外，可以完全排除，不必進(jìn)行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。2.直線段裁剪直線段裁剪算法比較簡單，但非常重要，是復(fù)雜圖元裁剪的基礎(chǔ)。因為復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。常用的線段裁剪方法有三種：Cohen-Sutherland，中點分割算法和梁友棟－barskey算法。Cohen-Sutherland裁剪算法該算法的思想是：對于每條線段P1P2分為三種情況
3、處理。（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2簡稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡稱“棄”之。（3）若線段既不滿足“取”的條件，也不滿足“棄”的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。問題：如何判斷線段與窗口的關(guān)系？為使計算機能夠快速判斷一條直線段與窗口屬何種關(guān)系，采用如下編碼方法。延長窗口的邊，將二維平面分成九個區(qū)域。每個區(qū)域賦予4位編碼CtCbCrCl.其中各位編碼的定義如下：<裁剪一條線段時，先求出P1P2所在的區(qū)號code1,code2。若code1=0,且code2=0，則線段P1P2在窗口內(nèi)，
4、應(yīng)取之。若按位與運算code1&code2≠0，則說明兩個端點同在窗口的上方、下方、左方或右方?？膳袛嗑€段完全在窗口外，可棄之。否則，按第三種情況處理。求出線段與窗口某邊的交點，在交點處把線段一分為二，其中必有一段在窗口外，可棄之。在對另一段重復(fù)上述處理。在實現(xiàn)本算法時，不必把線段與每條窗口邊界依次求交，只要按順序檢測到端點的編碼不為0，才把線段與對應(yīng)的窗口邊界求交。Cohen-Sutherland裁剪算法步驟：已知直線：（X1，Y1）（X2，Y2）與水平線Y＝K的交點為：與垂直直線X＝R的交點為：在進(jìn)行裁剪是除了要求直線與邊界線的交點外，還要判斷端點與窗口的位置關(guān)系。為此有：若編碼&
5、0001<>0，端點與左邊界有交點；若編碼&0010<>0，端點與右邊界有交點；若編碼&0100<>0，端點與下邊界有交點；若編碼&1000<>0，端點與上邊界有交點；Cohen-Sutherland直線裁剪算法小結(jié)本算法的優(yōu)點在于簡單，易于實現(xiàn)。他可以簡單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進(jìn)行，處理之后，剩余部分就是可見的了。在這個算法中求交點是很重要的，他決定了算法的速度。另外，本算法對于其他形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。中點分割裁剪算法基本思想：從P0點出發(fā)找出離P0最近的可見點，和從P1點出發(fā)找出離P1
6、最近的可見點。這兩個可見點的連線就是原線段的可見部分。與Cohen-Sutherland算法一樣首先對線段端點進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況，對前兩種情況，進(jìn)行一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距P0、P1最近的可見點，Pm為P0P1中點。中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復(fù)上述
7、過程，直到PmP1長度小于給定的控制常數(shù)為止，此時Pm收斂于交點。從P1出發(fā)找距離P1最近可見點采用上面類似方法。中點分割裁剪算法對分辯率為2N*2N的顯示器，上述二分過程至多進(jìn)行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點分割裁剪算法設(shè)要裁剪的線段是P0P1。線段的參數(shù)方程為：P=P0+(P1-P0)t(0≤t≤1)Liang-Barsky算法的基本思想是：確定在窗口內(nèi)的線段的參數(shù)
