《維圖形裁剪》PPT課件

《《維圖形裁剪》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第七講二維圖形裁剪在使用計(jì)算機(jī)處理圖形信息時(shí)，計(jì)算機(jī)內(nèi)部存儲(chǔ)的圖形往往比較大，而屏幕顯示的只是圖的一部分。因此需要確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過(guò)程稱為裁剪。在進(jìn)行裁剪時(shí)，對(duì)應(yīng)于屏幕顯示的那部分區(qū)域稱為窗口，一般窗口定義為矩形，由上、下、左、右四條邊圍成。裁剪的實(shí)質(zhì)，就是決定圖形中哪些點(diǎn)、線段、文字以及多邊形在窗口之內(nèi)。主要內(nèi)容1.點(diǎn)的裁剪2.直線的裁剪3.多邊形的裁剪4.字符的裁剪1.點(diǎn)的裁剪設(shè)窗口由x=xL,x=xR,y=yB,y

2、=yT圍成。對(duì)于點(diǎn)(x,y)判別兩對(duì)不等式：xL<=x<=xR，yB<=y<=yT；若四個(gè)不等式均成立，則點(diǎn)在窗口之內(nèi)；否則，點(diǎn)在窗口之外。最簡(jiǎn)單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點(diǎn)之后，再判斷各點(diǎn)是否在窗內(nèi)。但那樣太費(fèi)時(shí)，一般不可取。這是因?yàn)橛行﹫D形組成部分全部在窗口外，可以完全排除，不必進(jìn)行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。2.直線段裁剪直線段裁剪算法比較簡(jiǎn)單，但非常重要，是復(fù)雜圖元裁剪的基礎(chǔ)。因?yàn)閺?fù)雜的曲線可以通過(guò)折線段來(lái)近似，從而裁剪問(wèn)題也可以化為直線段的裁剪問(wèn)題。常用的線段裁剪方法

3、有三種：Cohen-Sutherland，中點(diǎn)分割算法和梁友棟－barskey算法。Cohen-Sutherland裁剪算法該算法的思想是：對(duì)于每條線段P1P2分為三種情況處理。（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2簡(jiǎn)稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡(jiǎn)稱“棄”之。（3）若線段既不滿足“取”的條件，也不滿足“棄”的條件，則在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。問(wèn)題：如何判斷線段與窗口的關(guān)系？為使計(jì)算機(jī)能夠快速判斷一條直線段與窗

4、口屬何種關(guān)系，采用如下編碼方法。延長(zhǎng)窗口的邊，將二維平面分成九個(gè)區(qū)域。每個(gè)區(qū)域賦予4位編碼CtCbCrCl.其中各位編碼的定義如下：<裁剪一條線段時(shí)，先求出P1P2所在的區(qū)號(hào)code1,code2。若code1=0,且code2=0，則線段P1P2在窗口內(nèi)，應(yīng)取之。若按位與運(yùn)算code1&code2≠0，則說(shuō)明兩個(gè)端點(diǎn)同在窗口的上方、下方、左方或右方?？膳袛嗑€段完全在窗口外，可棄之。否則，按第三種情況處理。求出線段與窗口某邊的交點(diǎn)，在交點(diǎn)處把線段一分為二，其中必有一段在窗口外，可棄之。在對(duì)另一段重復(fù)上

5、述處理。在實(shí)現(xiàn)本算法時(shí)，不必把線段與每條窗口邊界依次求交，只要按順序檢測(cè)到端點(diǎn)的編碼不為0，才把線段與對(duì)應(yīng)的窗口邊界求交。Cohen-Sutherland裁剪算法步驟：已知直線：（X1，Y1）（X2，Y2）與水平線Y＝K的交點(diǎn)為：與垂直直線X＝R的交點(diǎn)為：在進(jìn)行裁剪是除了要求直線與邊界線的交點(diǎn)外，還要判斷端點(diǎn)與窗口的位置關(guān)系。為此有：若編碼&0001<>0，端點(diǎn)與左邊界有交點(diǎn)；若編碼&0010<>0，端點(diǎn)與右邊界有交點(diǎn)；若編碼&0100<>0，端點(diǎn)與下邊界有交點(diǎn)；若編碼&1000<>0，端點(diǎn)與上邊界有

6、交點(diǎn)；Cohen-Sutherland直線裁剪算法小結(jié)本算法的優(yōu)點(diǎn)在于簡(jiǎn)單，易于實(shí)現(xiàn)。他可以簡(jiǎn)單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進(jìn)行，處理之后，剩余部分就是可見的了。在這個(gè)算法中求交點(diǎn)是很重要的，他決定了算法的速度。另外，本算法對(duì)于其他形狀的窗口未必同樣有效。特點(diǎn)：用編碼方法可快速判斷線段的完全可見和顯然不可見。中點(diǎn)分割裁剪算法基本思想：從P0點(diǎn)出發(fā)找出離P0最近的可見點(diǎn)，和從P1點(diǎn)出發(fā)找出離P1最近的可見點(diǎn)。這兩個(gè)可見點(diǎn)的連線就是原線段的可見部分。與Cohen-Suth

7、erland算法一樣首先對(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)。中點(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

8、。重復(fù)上述過(guò)程，直到PmP1長(zhǎng)度小于給定的控制常數(shù)為止，此時(shí)Pm收斂于交點(diǎn)。從P1出發(fā)找距離P1最近可見點(diǎn)采用上面類似方法。中點(diǎn)分割裁剪算法對(duì)分辯率為2N*2N的顯示器，上述二分過(guò)程至多進(jìn)行N次。主要過(guò)程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)，它可以用左右移位來(lái)代替乘除法，這樣就大大加快了速度。中點(diǎn)分割裁剪算法設(shè)要裁剪的線段是P0P1。線段的參數(shù)方程為：P=P0+(P1-P0)t(0≤t≤1)Liang-Barsky算法的基本思想是：確定在窗口內(nèi)的線段的參數(shù)