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

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

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

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

二維圖形的顯示流程圖（1/4）坐標(biāo)系：建立了圖形與數(shù)之間的對(duì)應(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ū)域用來(lái)指定要顯示的圖形

視區(qū)在設(shè)備坐標(biāo)系（屏幕或繪圖紙）上指定的矩形區(qū)域用來(lái)指定窗口內(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)系線段完全可見(jiàn)顯然不可見(jiàn)線段至少有一端點(diǎn)在窗口之外，但非顯然不可見(jiàn)

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

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

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

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

1）特點(diǎn)：用編碼方法可快速判斷線段--

完全可見(jiàn)和顯然不可見(jiàn)。

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

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

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

*

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

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

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

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

。u2取1和各個(gè)rk值之中的最小值。30梁友棟－Barsky算法如果u1>u2，則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個(gè)值u1,u2計(jì)算出來(lái)。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; }}

。。。//下頁(yè)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算法對(duì)三種算法比較:Cohen-Sutherland與中點(diǎn)法在區(qū)域碼測(cè)試階段能以位運(yùn)算方式高效率地進(jìn)行，因而當(dāng)大多數(shù)線段能夠簡(jiǎn)單的取舍時(shí)，效率較好。梁友棟—Barskey算法只能應(yīng)用于矩形窗口的情形，但其效率比前兩者要高，這是因?yàn)檫\(yùn)算只涉及到參數(shù)，僅到必要時(shí)才進(jìn)行坐標(biāo)計(jì)算。355.4多邊形裁剪(1/6)錯(cuò)覺(jué)：直線段裁剪的組合？新的問(wèn)題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來(lái)封閉它，如何確定其邊界？第5講二維裁剪365.4多邊形裁剪（2/6）2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？第4節(jié)多邊形裁剪37Sutherland-Hodgman算法（3/6）分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過(guò)程(左上右下)：左邊的結(jié)果是上邊的開(kāi)始。亦稱逐邊裁剪算法第4節(jié)多邊形裁剪38Sutherland-Hodgman算法（4/6）內(nèi)側(cè)空間與外側(cè)空間多邊形的邊與半空間的關(guān)系第4節(jié)多邊形裁剪輸出P輸出i無(wú)輸出輸出i，P39Sutherland-Hodgman算法(主要流程)第4節(jié)多邊形裁剪40Sutherland-Hodgman算法(6/6)裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多邊形的邊與裁剪邊的交點(diǎn)。順序連接。幾點(diǎn)說(shuō)明：裁剪算法采用流水線方式，適合硬件實(shí)現(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)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界

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

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

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

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

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

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

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

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