計(jì)算機(jī)圖形學(xué)課件第4講：圖形裁剪算法

第6講圖形裁剪算法

圖形裁剪計(jì)算機(jī)內(nèi)部存儲的圖形數(shù)據(jù)量往往比較大，而屏幕顯示的只是圖的局部部分。因此需要確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，以便只顯示落在顯示區(qū)內(nèi)的那部分圖形窗口：矩形2圖形裁剪的策略先變換后裁剪將圖形經(jīng)過掃描轉(zhuǎn)換后變成像素的集合，然后對圖形中的每一個像素進(jìn)行裁剪先裁剪后變換將原始圖形進(jìn)行裁剪，保留窗口內(nèi)的可見部分，舍棄窗口外的不可見部分。然后對窗口內(nèi)保留的這部分圖形進(jìn)行掃描轉(zhuǎn)換先裁剪后變換！可以省去許多不必要的掃描轉(zhuǎn)換的工作3圖形裁剪的處理步驟圖形裁剪的目的：判斷圖形元素是否在所考慮的區(qū)域內(nèi)如在區(qū)域內(nèi)，則進(jìn)一步求出區(qū)域內(nèi)的那一部分處理步驟：點(diǎn)在區(qū)域內(nèi)外的判斷計(jì)算圖形元素與區(qū)域邊界的交點(diǎn)4點(diǎn)的裁剪對于一點(diǎn)P(x,y)，要判斷其是否可見

xmin≤x≤xmaxandymin≤y≤ymax

滿足上述不等式組的點(diǎn)則在窗口范圍內(nèi)，則保留；反之，該點(diǎn)落在窗口外，應(yīng)裁剪5xminymaxyminxmax直線的裁剪對于矩形窗口任何直線至多只有一段處于該窗口之內(nèi)即在此窗口范圍內(nèi)永遠(yuǎn)不會產(chǎn)生一條直線的兩條或更多的可見部分線段基本思想：判斷直線與窗口的位置關(guān)系，確定該直線是完全可見、部分可見或完全不可見輸出處于窗口內(nèi)線段的端點(diǎn)，并顯示此線段6直線的裁剪整條線在窗口之內(nèi)不需剪裁，顯示整條線段整條線在窗口之外不需剪裁，不顯示整條線段部分線在窗口之內(nèi)求出線段與窗口邊界的交點(diǎn)將窗口外的線段部分剪裁掉顯示窗口內(nèi)的部分7直線裁剪的效率策略快速排除完全在窗口內(nèi)完全在窗口外的直線若是部分在窗口內(nèi)的情況減少直線與窗口邊界的求交次數(shù)和每次的求交計(jì)算量8直線裁剪算法Cohen-Sutherland裁剪算法中點(diǎn)分割算法梁友棟-Barsky裁剪算法9基本思想：對于每條待裁剪的線段P1P2分三種情況處理若P1P2完全在窗口內(nèi)，則顯示該線段若P1P2完全在窗口外，則丟棄該線段若線段不滿足上述條件則求線段與窗口邊界的交點(diǎn)，在交點(diǎn)處把線段分為兩段其中一段完全在窗口外，可舍棄之，然后對另一段重復(fù)上述處理10Cohen-Sutherland裁剪算法Cohen-Sutherland裁剪算法如何快速排除完全在窗口內(nèi)完全在窗口外的直線編碼9個區(qū)域4位編碼CtCbCrCl按位運(yùn)算11100110101000000000010100011000100101ymaxyminxmaxxmin延長窗口的四條邊線(ymin,ymax,xmin,xmax)，將二維平面分成九個區(qū)域,區(qū)域賦予4位編碼CtCbCrCl第一位為1：端點(diǎn)處于上邊界的上方第二位為1：端點(diǎn)處于下邊界的下方第三位為1：端點(diǎn)處于右邊界的右方第四位為1：端點(diǎn)處于左邊界的左方否則，相應(yīng)位為012Cohen-Sutherland裁剪算法Cohen-Sutherland裁剪算法對線段的每個頂點(diǎn)，根據(jù)其所在區(qū)域賦予此編碼if(x<XL)c|=0x0001; …一個在窗口內(nèi)的頂點(diǎn)編碼為000013100110101000000000010100011000100101Cohen-Sutherland裁剪算法先排除簡單情形：若某線段兩個端點(diǎn)的四位二進(jìn)制編碼全為0000線段位于窗口內(nèi)，顯示之若對兩端點(diǎn)的四位二進(jìn)制編碼進(jìn)行邏輯與運(yùn)算（&）結(jié)果不為0線段位于窗口外，直接舍棄再裁剪遞歸執(zhí)行14100110101000000000010100011000100101Cohen-Sutherland裁剪算法裁剪：若線段既不能直接保留，也不能直接舍棄它可能與窗口相交對線段進(jìn)行再分割，并找到與窗口邊線的一個交點(diǎn)，根據(jù)交點(diǎn)位置，賦予4位二進(jìn)制編碼，對分割后的線段舍棄一定在窗口外部分另一部分做進(jìn)一步檢查15100110101000000000010100011000100101例：如圖，裁剪AB、CD、EF直線段。解：根據(jù)編碼算法，各直線段的端點(diǎn)四位二進(jìn)制編碼如下：

A:0000B:0000A,B編碼全為0，AB直接保留

C:0010D:0110C,D編碼進(jìn)行邏輯與運(yùn)算，結(jié)果非0，CD直線段直接舍棄

E:0001F:0000E,F編碼進(jìn)行邏輯與運(yùn)算，結(jié)果為0，此時應(yīng)求EF與窗口邊界的交點(diǎn)16ABCDEFCohen-Sutherland裁剪算法Cohen-Sutherland裁剪算法求交將兩個端點(diǎn)的編碼CtCbCrCl進(jìn)行邏輯或操作，根據(jù)其結(jié)果中1的位置來確定可能相交的窗口邊求交按照固定的順序來進(jìn)行（左右下上或上下右左）一條線段與窗口最多求交4次17A(1010)B(0101)DCEFCohen-Sutherland裁剪算法特點(diǎn)：簡單，易實(shí)現(xiàn)依次裁剪在窗口外部分，直到直線完全處于窗口內(nèi)快速判斷線段的完全可見和顯然不可見巧妙的編碼方法18中點(diǎn)分割算法類似于Cohen-Sutherland算法將直線的兩端點(diǎn)P1、P2編碼得：C1、C2；根據(jù)C1和C2的具體值，可以有三種情況：C1＝C2＝0，表明兩端點(diǎn)全在窗口內(nèi)，因而整個線段也在窗內(nèi)，應(yīng)予保留。C1&C2≠0，表明兩端點(diǎn)全在窗口外同側(cè)，整個線段全在窗外，應(yīng)予舍棄。不屬于上面兩種情況，均需要求交點(diǎn)，并進(jìn)行裁剪裁剪：裁剪一端，得到最近可見點(diǎn)求最近可見點(diǎn)（交點(diǎn)）：中點(diǎn)分割算法！19中點(diǎn)分割算法中點(diǎn)觀察：中點(diǎn)將線段P1P2分為兩部分，必定有一部分存在最近可見點(diǎn)（交點(diǎn)）保留存在最近可見點(diǎn)部分，舍棄另一部分20P1P2P中點(diǎn)分割算法當(dāng)線段P1P2求出中點(diǎn)P后，舍棄線段的哪部分？若如果P1與P同側(cè)，移動P1點(diǎn)；（即可能的交點(diǎn)只能出現(xiàn)在PP2段）

if((C1&C)!=0)P1=P;若P1與P不同側(cè)，移動P2點(diǎn)。（即可能的交點(diǎn)只能出現(xiàn)在P1P段）

if((C1&C)==0)P2=P;21中點(diǎn)分割算法將中點(diǎn)分割進(jìn)行到底!可收斂到最近可見點(diǎn)22中點(diǎn)分割算法求交點(diǎn)STEP1：令窗外端點(diǎn)為P1，如果窗外點(diǎn)不是P1，則P1和P2交換端點(diǎn)；STEP2：保留窗內(nèi)端點(diǎn)P2到暫存器里；STEP3：對P1編碼為C1；STEP4：用中點(diǎn)公式求出中點(diǎn)，并編碼得C；STEP5：按照中點(diǎn)算法的求交規(guī)則：若P1和P同側(cè)，移動P1點(diǎn)；if((C1&C)!=0)

P1=P;

否則，移動P2點(diǎn)。else

P2=P;GOTOSTEP3，直到P1和P2相差一個單位時：令交點(diǎn)為P2，對暫存器斷點(diǎn)P2裁剪23中點(diǎn)分割算法特點(diǎn)：求交點(diǎn)的次數(shù)（n）與線段長度（L）有關(guān)，其關(guān)系為：L=2n。例如：線段長度為256，則求交點(diǎn)的次數(shù)為8。求出的交點(diǎn)是邊界上的有效交點(diǎn)（最近可見點(diǎn)），而非邊界及其延長線上的交點(diǎn)Cohen－Sutherland直線裁剪算法：邊界上或者邊界的延長線上的交點(diǎn)求中點(diǎn)：加法與除法，容易硬件實(shí)現(xiàn)24梁友棟-Barsky裁剪算法梁友棟生于1935年7月，福建福州人1956-1960年：復(fù)旦大學(xué)研究生，師從蘇步青先生學(xué)習(xí)幾何理論1960年研究生畢業(yè)后任教于浙江大學(xué)數(shù)學(xué)系1984-1990年任浙大數(shù)學(xué)系主任Liang,Y.D.,andBarsky,B.,"ANewConceptandMethodforLineClipping",ACMTransactionsonGraphics,3(1):1-22,January1984.25梁友棟-Barsky裁剪算法算法的基本思想：當(dāng)要裁剪的線段是P0P1，P0P1和窗口邊界交于A,B,C,D四點(diǎn)。從A,B和P0三點(diǎn)中找出最靠近的P1的點(diǎn)，從C,D和P1中找出最靠近P0的點(diǎn)。26yxyTyBxLxRABCDP1P0P0C是P0P1線段上的可見部分梁友棟-Barsky裁剪算法具體計(jì)算時，把P0P1寫成其參數(shù)方程：

其中Δx=x1－x0，Δy=y1－y0窗口內(nèi)線段應(yīng)滿足求u!27梁友棟-Barsky裁剪算法不等式可寫作：即線段與裁剪邊界的交點(diǎn)有28yxyTyBxLxRABCDP1P0梁友棟-Barsky裁剪算法窗口邊界的四條邊分成兩類，一類稱為始邊，另一類稱為終邊當(dāng)Δx≥0時，稱x=xL為始邊，x=xR為終邊當(dāng)Δx<0時，稱x=xL為終邊，x=xR為始邊當(dāng)Δy≥0時，稱y=yB為始邊，y=yT為終邊當(dāng)Δy<0時，稱y=yB為終邊，y=yT為始邊29yxyTyBxLxRP1P0P0P1AB可知邊界交點(diǎn)的參數(shù)：

當(dāng)pi<0時，求得的ti必是P0P1和始邊的交點(diǎn)的參數(shù)當(dāng)pi>0時，ui必是P0P1和終邊的交點(diǎn)的參數(shù)30梁友棟-Barsky裁剪算法求出P0P1和兩條始邊的交點(diǎn)的參數(shù)u0’和u0’’，令

u0=max(u0’，u0’’，0)則u0

就是圖中A、B和P0三點(diǎn)中最靠近P1的點(diǎn)的參數(shù)求出P0P1和兩條終邊的交點(diǎn)的參數(shù)u1’和u1’’，令

u1=min(u1’，u1’’，1)則u1就是圖中C、D和P1三點(diǎn)中最靠近P0的點(diǎn)的參數(shù)31xyyTyBxLxRABCDP1P0t0t1梁友棟-Barsky裁剪算法當(dāng)u1>u0時，參數(shù)t∈[u0,u1]的線段就是P0P1的可見部分當(dāng)u1<u0時，整個直線段為不可見32xyyTyBxLxRCABDP1P0u0u1BCADP1P0u0u1當(dāng)pi=0時,若qi<0則P0P1是完全不可見的若qi≥0，則P0P1平行于裁剪邊界,并且至少部分在窗口內(nèi)

33xLxRyxCDABEFyByT梁友棟-Barsky裁剪算法梁友棟-Barsky裁剪算法算法步驟1、初始化線段交點(diǎn)的參數(shù)：u1=0，u2=1；2、計(jì)算出4個裁剪邊界的p、q值；3、調(diào)用函數(shù)clipTest()，在函數(shù)中根據(jù)p、q來判斷：是舍棄線段還是改變交點(diǎn)的參數(shù)。（1）當(dāng)p<0時，參數(shù)r用于更新u0：（u0=max{u0，rk}）（2）當(dāng)p>0時，參數(shù)r用于更新u1：（u1=min{u1，rk}）（3）如果更新了u0或u1后，使u0>u1，則舍棄該線段（4）當(dāng)p=0且q<0時，因?yàn)榫€段平行于邊界并且位于邊界之外，則舍棄該線段。4、p、q的4個值經(jīng)判斷后，如果該線段未被舍棄，則裁剪線段的端點(diǎn)坐標(biāo)由參數(shù)u1和u2的值決定。34梁友棟-Barsky裁剪算法特點(diǎn)通常比Cohen－Sutherland算法效率更高更新參數(shù)u1、u2僅僅需要一次除法Cohen－Sutherland算法：而且每次求交計(jì)算都需要做乘除法35多邊形裁剪多邊形裁剪基于直線的裁剪，可以把多邊形裁剪分解為邊界的線段，逐段來進(jìn)行裁剪不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)，還在于形成正確的頂點(diǎn)序列36多邊形的描述方式多邊形可以描述為一組頂點(diǎn)按一定順序連接而成的有向點(diǎn)列一般可將多邊形的頂點(diǎn)按逆時針方向順序形成有向線段，進(jìn)而連接成一個環(huán)來描述多邊形的組成數(shù)據(jù)結(jié)構(gòu)上，可用鏈表結(jié)構(gòu)來描述372341多邊形裁剪的特點(diǎn)多邊形的各條邊是順次連接直線裁剪把一條線段的兩個端點(diǎn)孤立考慮，會產(chǎn)生鼓勵線段裁剪之后各條邊不一定能保持原來的連接順序38裁剪前錯誤裁剪正確裁剪多邊形裁剪算法Sutherland-Hodgman算法每次用窗口的一條邊界對多邊形進(jìn)行裁剪把落在窗口外部的圖形去掉，落在窗口內(nèi)部的圖形保留并把它作為下一次待裁剪的多邊形連續(xù)用窗口的四條邊界對原始多邊形進(jìn)行裁剪后，最后得到的就是裁剪后的結(jié)果多邊形39每一步考慮窗口的一條邊界及其延長線構(gòu)成的裁剪線。該裁剪線把平面分成兩個部分，一部分包含窗口，稱為可見一側(cè)；另一部分稱為不可見一側(cè)。依序處理多邊形各邊時會有四種情況：邊SP全部處于可見一側(cè)：此時將終點(diǎn)P放入新的頂點(diǎn)序列邊SP全部處于不可見一側(cè)：此時沒有點(diǎn)放入新的頂點(diǎn)序列邊SP從可見一側(cè)進(jìn)入不可見一側(cè)：