計算機圖形學(xué)chp5-Cut

計算機圖形學(xué)吳偉計算機學(xué)院E-mail:wuwei_imu@163.com2第5講二維觀察5.1觀察流程5.2窗口到視口的變換5.3直線段裁剪直接求交算法；Cohen-Sutherland算法；中點算法

Nicholl-Lee-Nicholl算法5.4多邊形裁剪

Sutlerland_Hodgman算法5.5文字裁剪計算機圖形學(xué)課程ComputerGraphicsCourse3第5講要求掌握二維圖形的顯示流程圖，窗口到視區(qū)的變換掌握什么是裁剪、裁剪窗口，裁剪算法的基本內(nèi)容；掌握裁剪直線段的Cohen-Sutherland算法、中點分割算法；了解裁剪直線段的Nicholl-Lee-Nicholl算法掌握裁剪多邊形的Sutherland-Hodgman算法（又稱逐邊裁剪算法）；掌握如何裁剪一個字符串，如何裁剪一個點陣表示（或矢量表示）的字符第5講二維裁剪4

二維圖形的顯示流程圖（1/4）坐標(biāo)系：建立了圖形與數(shù)之間的對應(yīng)聯(lián)系世界坐標(biāo)系(worldcoordinate)用戶坐標(biāo)系(usercoordinate)局部坐標(biāo)系(localcoordinate)

5

二維圖形的顯示流程圖（2/4)屏幕坐標(biāo)系(screencoordinate)設(shè)備坐標(biāo)系(devicecoordinate)

6

二維圖形的顯示流程圖（3/4）窗口在世界坐標(biāo)系中指定的矩形區(qū)域用來指定要顯示的圖形

視區(qū)在設(shè)備坐標(biāo)系（屏幕或繪圖紙）上指定的矩形區(qū)域用來指定窗口內(nèi)的圖形在屏幕上顯示的大小及位置

窗口到視區(qū)的變換

7

二維圖形的顯示流程圖（4/4）8

窗口到視區(qū)的變換（1/2）目標(biāo)將窗口之中的圖形變換到視區(qū)中變換的求法變換的分解與合成9

窗口到視區(qū)的變換（2/2）105.3直線段裁剪(1/18)裁剪的目的判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交假定條件矩形裁剪窗口：

[xmin,xmax]X[ymin,ymax]待裁剪線段：第5講二維裁剪115.3直線段裁剪(2/18)待裁剪線段和窗口的關(guān)系線段完全可見顯然不可見線段至少有一端點在窗口之外，但非顯然不可見

為提高效率，算法設(shè)計時應(yīng)考慮：(一）快速判斷情形(1)(2)；(二)設(shè)法減少情形(3)求交次數(shù)和每次求交時所需的計算量。第3節(jié)直線段裁剪125.3直線段裁剪(3/18)點裁剪點(x,y)在窗口內(nèi)的充分必要條件是：

第3節(jié)直線段裁剪135.3直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。第3節(jié)直線段裁剪145.3Cohen-Sutherland算法(編碼算法)

算法步驟：第一步判別線段兩端點是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進入第二步；第二步判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；否則進行第三步；第三步求線段與窗口邊延長線的交點，這個交點將線段分為兩段，其中一段顯然不可見，丟棄。對余下的另一段重新進行第一步，第二步判斷，直至結(jié)束裁剪過程是遞歸的第3節(jié)直線段裁剪155.3Cohen-SutherLand算法(編碼算法)特點：對顯然不可見線段的快速判別編碼方法：由窗口四條邊所在直線把二維平面分成9個區(qū)域，每個區(qū)域賦予一個四位編碼， CtCbCrCl，上下右左；第3節(jié)直線段裁剪165.3Cohen-SutherLand算法(編碼算法)端點編碼：定義為它所在區(qū)域的編碼結(jié)論：當(dāng)線段的兩個端點的編碼的邏輯“與”非零時，線段為顯然不可見的

第3節(jié)直線段裁剪17求交測試順序固定(左上右下）最壞情形，線段求交四次。5.3Cohen-SutherLand算法(編碼算法)對于那些非完全可見、又非顯然不可見的線段，需要求交（如，線段AD)，求交前先測試與窗口哪條邊所在直線有交？(按序判斷端點編碼中各位的值ClCtCrCb）

1）特點：用編碼方法可快速判斷線段--

完全可見和顯然不可見。

2）特別適用二種場合：大窗口場合；窗口特別小的場合(如,光標(biāo)拾取圖形時,

光標(biāo)看作小的裁剪窗口。）第3節(jié)直線段裁剪185.3Cohen-SutherLand算法第3節(jié)直線段裁剪195.3

中點分割法想法：從P0點出發(fā)找出距P0最近的可見點，從P1點出發(fā)找出距P1最近的可見點。取中點Pm=(P1+P0)/2。第3節(jié)直線段裁剪對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)。適合平行計算。205.3Nicholl-Lee-Nicholl算法(1/4)消除C-S算法中多次求交的情況。基本想法：對2D平面的更細的劃分。第3節(jié)直線段裁剪215.3Nicholl-Lee-Nicholl算法(2/4)假定待裁剪線段P0P1為非完全可見且非顯然不可見。步驟：第一步，窗口四邊所在的直線將二維平面劃分成9個區(qū)域，假定落在區(qū)域0、4、5第3節(jié)直線段裁剪225.3Nicholl-Lee-Nicholl算法(3/4)第二步：從P0點向窗口的四個角點發(fā)出射線，這四條射線和窗口的四條邊所在的直線一起將二維平面劃分為更多的小區(qū)域。此時P1的位置決定了P0P1和窗口邊的相交關(guān)系。第3節(jié)直線段裁剪235.3Nicholl-Lee-Nicholl算法(4/4)第三步，確定P1所在的區(qū)域（判斷P1所在區(qū)域位置，可判定P0、P1與窗口那條邊求交)。 根據(jù)窗口四邊的坐標(biāo)值及P0P1和各射線的斜率可確定P1所在的區(qū)域。第四步，求交點，確定P0P1的可見部分。特點：效率較高，但僅適合二維矩形窗口。第3節(jié)直線段裁剪24梁友棟－Barsky算法梁-Barsky算法的幾何含義：入邊、出邊與端點25梁友棟－Barsky算法

*

寫入圖形學(xué)教科書的唯一中國人的算法*CommunicationofACM的論文梁有棟教授的二三事Liang-Barsky算法幾何連續(xù)理論從幾何學(xué)與纖維纏繞理論到基因工程26梁友棟－Barsky算法參數(shù)化形式寫出裁剪條件：可以統(tǒng)一表示為形式：

入邊出邊27梁友棟－Barsky算法

=0且<0，則線段完全在邊界外，≥0，則該線段平行于裁剪邊界并且在窗口內(nèi)。28梁友棟－Barsky算法當(dāng)≠0，當(dāng)<0,線段從裁剪邊界延長線的外部延伸到內(nèi)部。當(dāng)>0,線段從裁剪邊界延長線的內(nèi)部延伸到外部。29梁友棟－Barsky算法對于每條直線，可以計算出參數(shù)u1和u2，它們定義了在裁剪矩形內(nèi)的線段部分u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（p<0）。對這些邊界計算rk=qk/pk

。u1取0和各個rk值之中的最大值。u2的值由線段從內(nèi)到外遇到的矩形邊界所決定（p>0）。對這些邊界計算rk=qk/pk

。u2取1和各個rk值之中的最小值。30梁友棟－Barsky算法如果u1>u2，則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個值u1,u2計算出來。31梁友棟－Barsky算法voidLB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatx1,y1,x2,y2,XL,XR,YB,YT;{ floatdx,dy,u1,u2; u1=0;u2=1; dx=x2-x1;dy=y2-y1;if(ClipT(-dx,x1-Xl,&u1,&u2)if(ClipT(dx,XR-x1,&u1,&u2)if(ClipT(-dy,y1-YB,&u1,&u2)if(ClipT(dy,YT-y1,&u1,&u2){ displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy) return; }}32梁友棟－Barsky算法boolClipT(p,q,u1,u2)floatp,q,*u1,*u2;{floatr;if(p<0){ r=q/p; if(r>*u2)returnFALSE; elseif(r>*u1) { *u1=r; returnTRUE; }}

。。。//下頁33梁友棟－Barsky算法elseif(p>0){ r=p/q; if(r<*u1)returnFALSE; elseif(r<*u2){ *u2=r;returnTRUE;}}elseif(q<0)returnFALSE;returnTRUE;}34梁友棟－Barsky算法對三種算法比較:Cohen-Sutherland與中點法在區(qū)域碼測試階段能以位運算方式高效率地進行，因而當(dāng)大多數(shù)線段能夠簡單的取舍時，效率較好。梁友棟—Barskey算法只能應(yīng)用于矩形窗口的情形，但其效率比前兩者要高，這是因為運算只涉及到參數(shù)，僅到必要時才進行坐標(biāo)計算。355.4多邊形裁剪(1/6)錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？第5講二維裁剪365.4多邊形裁剪（2/6）2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？第4節(jié)多邊形裁剪37Sutherland-Hodgman算法（3/6）分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：左邊的結(jié)果是上邊的開始。亦稱逐邊裁剪算法第4節(jié)多邊形裁剪38Sutherland-Hodgman算法（4/6）內(nèi)側(cè)空間與外側(cè)空間多邊形的邊與半空間的關(guān)系第4節(jié)多邊形裁剪輸出P輸出i無輸出輸出i，P39Sutherland-Hodgman算法(主要流程)第4節(jié)多邊形裁剪40Sutherland-Hodgman算法(6/6)裁剪結(jié)果的頂點構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點；多邊形的邊與裁剪邊的交點。順序連接。幾點說明：裁剪算法采用流水線方式，適合硬件實現(xiàn)?？赏茝V到任意凸多邊形裁剪窗口第4節(jié)多邊形裁剪415.4Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為B第4節(jié)多邊形裁剪42主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-BWeiler-Athenton算法（1/5）裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界

第4節(jié)多邊形裁剪43Weiler-Athenton算法（2/5）如果主多邊形與裁剪多邊形有交點，則交點成對出現(xiàn)，它們被分為如下兩類：進點：主多邊形邊界由此進入裁剪多邊形內(nèi)

如I1,I3,I5,I7,I9,I11出點：主多邊形邊界由此離開裁剪多邊形區(qū)域.如I0,I2,I4,I6,I8,I10

第4節(jié)多邊形裁剪44Weiler-Athenton算（3/5）1）建頂點表；2）求交點；3）裁剪……Weiler_Athenton裁剪算法（內(nèi)裁剪）步驟：1、建立主多邊形和裁剪多邊形的頂點表．2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針。3、裁剪如果存在沒有被跟蹤過的交點，執(zhí)行以下步驟：

(1)建立裁剪結(jié)果多邊形的頂點表．

(2)選取任一沒有被跟蹤過的交點為始點，將其輸出到結(jié)果多邊形頂點表中．

(3)如果該交點為進點，跟蹤主多邊形邊邊界；否則跟蹤裁剪多邊形邊界．

(4)跟蹤多邊形邊界，每遇到多邊形頂點，將其輸出到結(jié)果多邊形頂點表中，直至遇到新的交點．

(5)將該交點輸出到結(jié)果多邊形頂點表中，并通過連接該交點的雙向指針改變跟