計算機圖形學(xué)裁剪技術(shù)

1、,裁剪算法 反走樣方法,裁剪,直線段裁剪,點裁剪 點(x, y)在窗口內(nèi)的充分必要條件是：,直線段裁剪,假定條件 矩形裁剪窗口：xmin,xmaxymin,ymax 待裁剪線段：,直線段裁剪,待裁剪線段和窗口的關(guān)系 （1）完全落在窗口內(nèi) （2）完全落在窗口外 （3）部分在內(nèi)，部分在外,求交測試順序固定(左右下上） 最壞情形，線段求交四次。,對于那些非完全可見、又非完全不可見的線段，需要求交，求交前先測試與窗口哪條邊所在直線有交？(按序判斷端點編碼中各位的值ClCtCrCb）,Cohen-Sutherland 算法,直線段裁剪,裁剪,直線段裁剪 Cohen-Sutherland算法 中點分割算法

2、 參數(shù)化裁剪算法 Liang-Barskey算法 多邊形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 字符裁剪,裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。在進行裁剪時，畫面中對應(yīng)于屏幕顯示的那部分區(qū)域稱為窗口。 圖形裁剪算法，直接影響圖形系統(tǒng)的效率。,裁剪,點的裁剪,圖形裁剪中最基本的問題。 假設(shè)窗口的左下角坐標為(xL,yB),右上角坐標為(xR,yT)，對于給定點P(x,y),則P點在窗口內(nèi)的條件是要滿足?,(xL,yB ),(xR,yT ),直線段裁剪,直線段裁剪算法是復(fù)雜圖

3、形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。 常用的線段裁剪方法三種： Cohen-Sutherland算法 中點分割算法 參數(shù)化裁剪算法,Cohen-Sutherland裁剪,基本思想： 對于每條線段P1P2分為三種情況處理: （1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2。 （2）若P1P2明顯在窗口外，則丟棄該線段。 （3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。 如何實現(xiàn)上述的處理呢？,實現(xiàn)方法：采用下面的編碼方法 將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一

4、個四位二進制數(shù)標識，直線的端點都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來標識出端點相對于裁剪矩形邊界的位置。,1001,0001,0101,1000,0000,0100,1010,0010,0110,Cohen-Sutherland算法,將區(qū)域碼的各位從右到左編號，則坐標區(qū)域與各位的關(guān)系為： 任何位賦值為1，代表端點落在相應(yīng)的位置上，否則該位為0。若端點在剪取矩形內(nèi)，區(qū)域碼為0000。如果端點落在矩形的左下角，則區(qū)域碼為0101。,直線段裁剪,裁剪線段與窗口的關(guān)系：(1)線段完全可見；(2)顯然不可見；(3)其它 提高裁剪效率： 快速判斷情形(1)(2)， 對于情形(3)，設(shè)法減 少求交次數(shù)和每次求

5、 交時所需的計算量。,一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。,Cohen-Sutherland算法,若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取” 若P1P2明顯在窗口外code1 if(xXmax) c= c|RIGHT; if(yYmax) c= c| TOP; retrun c; ,Cohen-Sutherland裁剪,如何判定應(yīng)該與窗口的哪條邊求交呢？ 編碼中對應(yīng)位為1的邊。 計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點 if(LEFT,void CS_LineClip(x1,y1,x2,y2,X

6、L,XR,YB,YT) float x1,y1,x2,y2,XL,XR,YB,YT; /(x1,y1)(x2,y2)為線段的端點坐標，其他四個參數(shù)定義窗口的邊界 int code1,code2,code; code1=encode(x1,y1);/對線段A端編碼 code2=encode(x2,y2);/對線段B端編碼 while(code1!=0 |code2!=0)/條件當有一個端點不是零時 if(code1 ,else if(BOTTOM/畫線 ,Cohen-Sutherland直線裁剪算法小結(jié),本算法的優(yōu)點在于簡單，易于實現(xiàn)。他可以簡單的描述為將直線在窗口左邊的部分刪去，按左，右，下，

7、上的順序依次進行，處理之后，剩余部分就是可見的了。在這個算法中求交點是很重要的，他決定了算法的速度。 特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。,中點分割法,基本思想： 從P0點出發(fā)找出距P0最近的可見點 從P1點出發(fā)找出距P1最近的可見點 不斷地在中點處將線段一分為二，對每段線段重復(fù)Cohen-Sutherland裁剪算法的線段可見性測試方法，直至找到每段線段與窗口邊界線的交點或分割子段的長度充分小可視為一點為止 取中點Pm=(P1+P2)/2。,直線段裁剪,（1）如果P1與P同側(cè)，移動P1點；（即可能的交點只能出現(xiàn)在PP2段）if(C1,中點分割法,1、將直線的兩端點P1、P2

8、編碼得：C1、C2； 2、判別 根據(jù)C1和C2的具體值，可以有三種情況： （1）C1C20，表明兩端點全在窗口內(nèi)，因而整個線段也在窗內(nèi)，應(yīng)予保留。 （2）C1 （6）流程轉(zhuǎn)（3），直到P1和P2相差一個給定誤差時：令交點為P2，取出暫存器的端點賦給P1，然后轉(zhuǎn)向流程1。,中點分割法,Liang-Barsky裁剪算法,直線L與區(qū)域的交： 當Q為空集時，線段AB不可能在窗口中有可見線段。 當Q不為空集時，Q可看成是一個一維窗口,直線段裁剪,基本思想： 把二維裁剪化為一維裁剪問題，并向x（或y）方向投影以決定可見線段。,Liang-Barsky裁剪算法,直線段裁剪,存在可見線段的充要條件 不為空集,

9、向x軸投影，就得到可見線段上點的坐標的變化范圍為,左端點,右端點,Liang-Barsky裁剪算法,AB有可見部分的充分必要條件也可表示為,直線段裁剪,多邊形裁剪-1/2,用直線段裁剪算法，可以嗎？ 新的問題：,邊界不再封閉，需要用窗口邊界的恰當部分來封閉它,分裂為幾個多邊形,多邊形裁剪-2/2,關(guān)鍵： 不僅在于求出新的頂點，刪去界外頂點 還在于形成正確的頂點序列,Sutherland-Hodgman算法,分割處理策略： 將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。 流水線過程：左邊的結(jié)果是右邊的開始。,亦稱逐邊裁剪算法,Sutherland-Hodgman算法,裁剪結(jié)果

10、的頂點構(gòu)成： 裁剪邊內(nèi)側(cè)的原頂點； 多邊形的邊與裁剪邊的交點。 順序連接。,優(yōu)點： 裁剪算法采用流水線方式，適合硬件實現(xiàn)。 可推廣到任意凸多邊形裁剪窗口,基本思想是一次用窗口的一條邊裁剪多邊形。 考慮窗口的一條邊以及延長線構(gòu)成的裁剪線該線把平面分成兩個部分:可見一側(cè)；不可見一側(cè) 多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關(guān)系只有四種,Sutherland-Hodgman算法,Sutherland-Hodgman算法,情況（1）僅輸出頂點P； 情況（2）輸出0個頂點； 情況（3）輸出線段SP與裁剪線的交點I； 情況（4）輸出線段SP與裁剪線的交點I和終點P,Sutherland-Hodgman算法,線段與當前裁剪邊的位置關(guān)系,可見一側(cè),(a) 輸出I1和P2,當前裁剪邊,S=P1,P=P2,P3,P4,I1,可見一側(cè),P1,S=P2,P=P3,P4,I1,(b) 輸出P3,可見一側(cè),P1,P2,S=P3,P=P4,I2,可見一側(cè),P=P1,S=P2,P=P3,S=P4,(c) 輸出I2,(d) 無輸出,字符裁剪,前面我們介紹了字符和文本的輸出。當字符和文本部分在窗口內(nèi)，部分在窗口外時，就提出了字符裁剪問題。字符串裁剪可按三個精度來進行：串精度