裁剪算法

反走樣方法

第五章 裁剪、反走樣方法 裁剪算法第五章 裁剪、反走樣方法1二維裁剪直線段裁剪

直接求交算法

Cohen-Sutherland算法

中點分割算法

梁友棟-Barskey算法

參數(shù)化裁剪算法多邊形裁剪

Sutherland_Hodgman算法

Weiler-Athenton算法二維裁剪直線段裁剪2裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。圖形裁剪算法，直接影響圖形系統(tǒng)的效率。裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之3點的裁剪圖形裁剪中最基本的問題。假設(shè)窗口的左下角坐標(biāo)為(xL,yB),右上角坐標(biāo)為(xR,yT)，對于給定點P(x,y),則P點在窗口內(nèi)的條件是要滿足下列不等式：否則，P點就在窗口外。問題：對于任何多邊形窗口，如何判別？(xL,yB)(xR,yT)xL<=x<=xR并且yB<=y<=yT點的裁剪圖形裁剪中最基本的問題。(xL,yB)(xR,y4直線段裁剪直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。直接求交算法Cohen-Sutherland算法中點分割算法梁友棟－barskey算法參數(shù)化裁剪算法直線段裁剪直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以5直線段裁剪裁剪線段與窗口的關(guān)系：(1)線段完全可見；(2)顯然不可見；(3)其它提高裁剪效率： 快速判斷情形(1)(2)， 對于情形(3)，設(shè)法減 少求交次數(shù)和每次求 交時所需的計算量。直線段裁剪6直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。直接求交算法直線與窗口邊都7Cohen-Sutherland裁剪基本思想：對于每條線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。為快速判斷，采用如下編碼方法：Cohen-Sutherland裁剪基本思想：8實現(xiàn)方法：

將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一個四位二進制數(shù)標(biāo)識，直線的端點都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來標(biāo)識出端點相對于裁剪矩形邊界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪實現(xiàn)方法：1001000101011000000009Cohen-Sutherland算法將區(qū)域碼的各位從左到右編號，則坐標(biāo)區(qū)域與各位的關(guān)系為：上下右左 XXXX 任何位賦值為1，代表端點落在相應(yīng)的位置上，否則該位為0。若端點在剪取矩形內(nèi)，區(qū)域碼為0000。如果端點落在矩形的左下角，則區(qū)域碼為0101。Cohen-Sutherland算法將區(qū)域碼的各位從左到右編10Cohen-Sutherland算法一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。所以得到一個規(guī)律：Cohen-Sutherland算法一旦給定所有的線段端點11Cohen-Sutherland裁剪若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取”若P1P2明顯在窗口外code1&code2≠0，則“棄”在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。

100100010101100000000100101000100110BCDACohen-Sutherland裁剪若P1P2完全在窗口內(nèi)c12Cohen-Sutherland裁剪如何判定應(yīng)該與窗口的哪條邊求交呢？ 編碼中對應(yīng)位為1的邊。計算線段P1(x1,y1)--P2(x2,y2)與窗口邊界的交點 if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}Cohen-Sutherland裁剪如何判定應(yīng)該與窗口的哪13Cohen-Sutherland

直線裁剪算法小結(jié)優(yōu)點：簡單，易于實現(xiàn)。可以簡單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進行，處理之后，剩余部分就是可見的了。算法中求交點是很重要的，他決定了算法的速度。另外，本算法對于其他形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。Cohen-Sutherland

直線裁剪算法小結(jié)優(yōu)點：簡14中點分割裁剪算法基本思想：從P0點出發(fā)找離P0最近的可見點，從P1點出發(fā)找離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。首先對線段端點進行編碼，并把線段與窗口的關(guān)系分為三種情況，對前兩種情況，進行與Cohen-Sutherland算法一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距P0、P1最近的可見點，Pm為P0P1中點。

中點分割裁剪算法基本思想：從P0點出發(fā)找離P0最近的可見點，15中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復(fù)上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時Pm收斂于交點。從P1出發(fā)找距離P1最近可見點采用上面類似方法。中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見16中點分割裁剪算法中點分割裁剪算法17對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點分割裁剪算法對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。中點18

設(shè)要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,C,D四點。算法的基本思想是從A,B和P0三點中找出最靠近P1的點，圖中要找的點是P0。從C,D和P1中找出最靠近P0的點，圖中要找的點是C點。P0C就是P0P1線段上的可見部分。梁友棟-Barsky算法設(shè)要裁剪的線段是P0P1。P0P1和窗口邊界交于A19梁友棟-Barsky算法線段的參數(shù)表示x=x0+t△xy=y0+t△y0<=t<=1△x=x1-x0△y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。梁友棟-Barsky算法線段的參數(shù)表示20求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=max(t0,t1,0)，則tL即為三者中離p1最近的點的參數(shù)。求出p0p1與兩條終邊的交點參數(shù)t2,t3,令tu=min(t2,t3,1)，則tU即為三者中離p0最近的點的參數(shù)若tu>tl,則可見線段區(qū)間[tl,tu]梁友棟-Barsky算法：交點計算求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=m21梁友棟-Barsky算法始邊和終邊的確定及交點計算：令QL=-△xDL=x0-xLQR=△xDR=xR-x0

QB=-△yDB=y0-yBQT=△yDT=yT-y0交點為ti=Di/

Qii=L,R,B,TQi<0ti為與始邊交點參數(shù)Qi>0ti為與終邊交點參數(shù)Qi=0Di<0時,線段不可見Di>0時,分析另一D,

EFAB梁友棟-Barsky算法始邊和終邊的確定及交點計算：EFAB22梁友棟-Barsky算法當(dāng)Qi=0時若Di<0時,線段不可見（如圖中AB，有QR=0，DR<0）若Di>0時,分析另一D,（如圖中的EF就是這種情況，它使QL=0，DL>0和QR=0，DR>0。這時求EF和y=yT及y=yB的交點決定直線段上的可見部分。）

EFAB梁友棟-Barsky算法當(dāng)Qi=0時EFAB23參數(shù)化算法(Cyrus-Beck)考慮凸多邊形區(qū)域R和直線段P1P2 P(t)=(P2-P1)*t+P1設(shè)A是區(qū)域R的邊界上一點，N是區(qū)域邊界在A點的內(nèi)法線向量ARNP1P2參數(shù)化算法(Cyrus-Beck)考慮凸多邊形區(qū)域R和直線段24參數(shù)化算法(Cyrus-Beck)則對于線段P1P2上任一點P(t)N·(P(t)-A)<0->外側(cè)N·(P(t)-A)>0->內(nèi)側(cè)N·(P(t)-A)=0->邊界或其延長線上ARNP1P2參數(shù)化算法(Cyrus-Beck)則對于線段P1P2上任一點25參數(shù)化算法(Cyrus-Beck)凸多邊形的性質(zhì)：點P(t)在凸多邊形內(nèi)的充要條件是，對于凸多邊形邊界上任意一點A和該點處內(nèi)法向N，都有 N·(P(t)-A)>0參數(shù)化算法(Cyrus-Beck)凸多邊形的性質(zhì)：點P(t)26參數(shù)化算法(Cyrus-Beck)K+1條邊的多邊形，可見線段參數(shù)區(qū)間的解:Ni·(p(t)-Ai)>=0,i=0,…,k,0≤t≤1.即：Ni·(P1-Ai)+Ni·(P2-P1)t>=0(1)式可得：

令ti=Ni·(P1-Ai)/[Ni·(P2-P1)]參數(shù)化算法(Cyrus-Beck)K+1條邊的多邊形，可見線27參數(shù)化算法(Cyrus-Beck)Ni·(P2-P1)=0->平行于對應(yīng)邊。此時判斷Ni·(P1-Ai)若Ni·(P1-Ai)<0->P1P2在多邊形外側(cè)->不可見，若Ni·(P1-Ai)>0->P1P2在多邊形內(nèi)側(cè)->繼續(xù)其它邊的判斷參數(shù)化算法(Cyrus-Beck)Ni·(P2-P1)=28參數(shù)化算法(Cyrus-Beck)對于t值的選擇：首先,要符合0≤t≤1；其次,對于凸窗口來說，每一個線段與其至多有兩個交點，即有兩個相應(yīng)的t值。所以把計算出的t值分成兩組：一組為下限組，分布在線段起點一側(cè)；一組為上限組，分布在線段終點一側(cè)。找出下限組中的最大值及上限組中的最小值，就可確定線段了。分組的依據(jù)是：如果Ni·(P2-P1)＜0,則計算出的值屬于上限組如果Ni·(P2-P1)＞0,則計算出的值屬于下限組參數(shù)化算法(Cyrus-Beck)對于t值的選擇：首先,要符29參數(shù)化算法(Cyrus-Beck)因此，線段可見的交點參數(shù)：tl=max{0,max{ti:Ni·(P2-P1)>0}}tu=min{1,min{ti:Ni·(P2-P1)<0}}若tl<=tu,[tl，tu]是可見線段的交點參數(shù)區(qū)間，否則，線段不可見。參數(shù)化算法(Cyrus-Beck)因此，線段可見的交點參數(shù)：30參數(shù)化算法的幾何意義下限組以Ni·(P2-P1)>0為特征，表示在該處沿P1P2方向前進將接近或進入多邊形內(nèi)側(cè)。上限組以Ni·(P2-P1)<0為特征，表示在該處沿P1P2方向前進將越來越遠(yuǎn)地離開多邊形區(qū)域。參數(shù)化算法的幾何意義下限組以Ni·(P2-P1)>0為特31參數(shù)化算法當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時，該算法退化為Liang-Barsky算法。參數(shù)化算法當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時，該算32多邊形裁剪錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？多邊形裁剪錯覺：直線段裁剪的組合？33多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確34Sutherland-Hodgman算法分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法Sutherland-Hodgman算法分割處理策略：將多邊35Sutherland-Hodgman算法基本思想是一次用窗口的一條邊裁剪多邊形。考慮窗口的一條邊以及延長線構(gòu)成的裁剪線,把平面分成兩個部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關(guān)系只有四種Sutherland-Hodgman算法基本思想是一次用窗口36Sutherland-Hodgman算法情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點PSutherland-Hodgman算法37Sutherland-Hodgman算法框圖

處理線段SP過程子框圖一條裁剪線的處理流程Sutherland-Hodgman算法框圖處理線段SP過程38Sutherland-Hodgman算法上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，算法框圖同上，只是判斷點在窗口哪一側(cè)以及求線段SP與裁剪邊的交點算法應(yīng)隨之改變。Sutherland-Hodgman算法上述算法僅用一條裁剪39Sutherland-Hodgeman算法對凸多邊形應(yīng)用本算法可以得到正確的結(jié)果，但是對凹多邊形的裁剪將如圖所示顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現(xiàn)。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。再有就是Weiler-Atherton算法。Sutherland-Hodgeman算法對凸多邊形應(yīng)用本算40Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為BWeiler-Athenton算法41Weiler-Athenton算法多邊形頂點的排列順序（使多邊形區(qū)域位于有向邊的左側(cè)）外環(huán)：逆時針；內(nèi)環(huán)：順時針主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-B裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界Weiler-Athenton算法多邊形頂點的排列順序（使多42Weiler-Athenton算法如果主多邊形與裁剪多邊形有交點，則交點成對出現(xiàn)，它們被分為如下兩類：進點：主多邊形邊界由此進入裁剪多邊形內(nèi)如，I1,I3,I5,I7,I9,I11出點：主多邊形邊界由此離開裁剪多邊形區(qū)域.如，I0,I2,I4,I6,I8,I10Weiler-Athenton算法如果主多邊形與裁剪多邊形有43Weiler-Athenton算法1）建頂點表；2）求交點；3）裁剪……1、建立主多邊形和裁剪多邊的頂點表．2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針。3、裁剪:如果存在沒有被跟蹤過的交點，執(zhí)行以下步驟：

Weiler-Athenton算法1）建頂點表；1、建立主多44Weiler-Athenton算法Weiler-Athenton算法45Weiler-Athenton算法(1)建立空的裁剪結(jié)果多邊形的頂點表．(2)選取任一沒有被跟蹤過的交點為始點，將其輸出到結(jié)果多邊形頂點表中．(3)如果該交點為進點，跟蹤主多邊形邊邊界；否則跟蹤裁剪多邊形邊界．(4)跟蹤多邊形邊界，每遇到多邊形頂點，將其輸出到結(jié)果多邊形頂點表中，直至遇到新的交點．(5)將該交點輸出到結(jié)果多邊形頂點表中，并通過連接該交點的雙向指針改變跟蹤方向（如果上一步跟蹤的是主多邊形邊界，現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊界，現(xiàn)在改為跟蹤主多邊形邊界）．(6)重復(fù)(4)、(5)直至回到起點取I7為起點，所得裁剪結(jié)果多邊形I7I0q0I3I4I5I6I7。取I8為起點，所得裁剪結(jié)果多邊形為I8I9I10I11I2q2I1I8。Weiler-Athenton算法(1)建立空的裁剪46Weiler-Athenton算法交點的奇異情況處理

1、與裁剪多邊形的邊重合的主多邊形的邊不參與求交點；2、對于頂點落在裁剪多邊形的邊上的主多邊形的邊，如果落在該裁剪邊的內(nèi)側(cè)，將該頂點算作交點；而如果這條邊落在該裁剪邊的外側(cè)，將該頂點不看作交點Weiler-Athenton算法交點的奇異情況處理47反走樣用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing)。光柵圖形的走樣現(xiàn)象階梯狀邊界；圖形細(xì)節(jié)失真；狹小圖形遺失：動畫序列中時隱時現(xiàn)，產(chǎn)生閃爍。反走樣用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(alias48走樣現(xiàn)象舉例不光滑(階梯狀）的圖形邊界例子：PaintBrush走樣現(xiàn)象舉例不光滑(階梯狀）的圖形邊界例子：PaintBru49走樣現(xiàn)象舉例圖形細(xì)節(jié)失真走樣現(xiàn)象舉例圖形細(xì)節(jié)失真50走樣現(xiàn)象舉例狹小圖形的遺失與動態(tài)圖形的閃爍走樣現(xiàn)象舉例狹小圖形的遺失與動態(tài)圖形的閃爍51反走樣概念及方法用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣(antialiasing)反走樣方法提高分辨率簡單區(qū)域取樣加權(quán)區(qū)域取樣半色調(diào)技術(shù)反走樣概念及方法用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣(an52提高分辨率把顯示器分辨率提高一倍，直線經(jīng)過兩倍的象素，鋸齒也增加一倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。提高分辨率把顯示器分辨率提高一倍，53提高分辨率方法簡單，但代價非常大。顯示器的水平、豎直分辯率各提高一倍，則顯示器的點距減少一倍，幀緩存容量則增加到原來的4倍，而掃描轉(zhuǎn)換同樣大小的圖元卻要花4倍時間。而且它也只能減輕而不能消除鋸齒問題另一種方法（軟件方法）：用較高的分辨率的顯示模式下計算，（對各自像屬下計算，再求（非）加權(quán)平均的顏色值），在較低的分辨率模式下顯示。只能減輕而不能消除鋸齒問題。提高分辨率方法簡單，但代價非常大。顯示器的水平、豎直分辯率各54軟件方法1把每個像素分為四個子像素，掃描轉(zhuǎn)換算法求得各子像素的灰度值，然后對四像素的灰度值簡單平均，作為該像素的灰度值。軟件方法1把每個像素分為四個子像素，掃描轉(zhuǎn)換算法求得各子像素55軟件方法2設(shè)分辨率為mn,把顯示窗口分為(2m+1)(2n+1)個子像素，對每個子像素進行灰度值計算，然后根據(jù)權(quán)值表所規(guī)定的權(quán)值，對位于像素中心及四周的九個子像素加權(quán)平均，作為顯示像素的顏色。設(shè)m=3,n=4軟件方法2設(shè)分辨率為mn,把顯示窗口分為(2m+1)(256簡單區(qū)域取樣方法由來兩點假設(shè)1、象素是數(shù)學(xué)上抽象的點，它的面積為0，它的亮度由覆蓋該點的圖形的亮度所決定；2、直線段是數(shù)學(xué)上抽象直線段，它的寬度為0。現(xiàn)實像素的面積不為0；直線段的寬度至少為1個像素；假設(shè)與現(xiàn)實的矛盾是導(dǎo)致混淆出現(xiàn)的原因之一簡單區(qū)域取樣方法由來57簡單區(qū)域取樣解決方法：改變直線段模型，由此產(chǎn)生算法方法步驟：1、將直線段看作具有一定寬度的狹長矩形；2、當(dāng)直線段與某象素有交時,求出兩者相交區(qū)域的面積；3、根據(jù)相交區(qū)域的面積，確定該象素的亮度值簡單區(qū)域取樣解決方法：改變直線段模型，由此產(chǎn)生算法1、將直線58簡單區(qū)域取樣基本思想：每個象素是一個具有一定面積的小區(qū)域，將直線段看作具有一定寬度的狹長矩形。當(dāng)直線段與象素有交時，求出兩者相交區(qū)域的面積，然后根據(jù)相交區(qū)域面積的大小確定該象素的亮度值。

有寬度的線條輪廓象素相交的五種情況及用于計算面積的量簡單區(qū)域取樣基本思想：59簡單區(qū)域取樣面積計算情況⑴（5)陰影面積為：D2/2m；情況⑵（4)陰影面積為：D-m/2；情況⑶陰影面積為：1-D2/m為了簡化計算可以采用離散的方法簡單區(qū)域取樣面積計算60簡單區(qū)域取樣求相交區(qū)域的近似面積的離散計算方法1、將屏幕象素分割成n個更小的子象素；2、計算中心點落在直線段內(nèi)的子象素的個數(shù)，記為k，3、k/n為線段與象素相交區(qū)域面積的近似值目的：簡化計算n=16,k=3近似面積=3/16簡單區(qū)域取樣求相交區(qū)域的近似面積的離散計算方法1、將屏幕象61簡單區(qū)域取樣簡單區(qū)域取樣采用的是一個盒式濾波器，它是一個二維加權(quán)函數(shù)，以w表示。w=1若在當(dāng)前像素所代表的正方形上w=0其它區(qū)域上直線條經(jīng)過該像素時，該像素的灰度值可以通過在像素與直線條的相交區(qū)域上對w求積分獲得。此時，面積值=體積值簡單區(qū)域取樣簡單區(qū)域取樣采用的是一個盒式濾波器，它是一個二維62加權(quán)區(qū)域取樣采用圓錐形濾波器，圓錐的底圓中心在當(dāng)前像素，底圓半徑為一個像素，錐高為1。當(dāng)直線條經(jīng)過該像素時，該像素的灰度值是在二者相交區(qū)域上對濾波器進行積分的積分值。見p213的圖4.7.9加權(quán)區(qū)域取樣采用圓錐形濾波器，圓錐的底圓中心在當(dāng)前像素，底圓63加權(quán)區(qū)域取樣特點：接近理想直線的像素將被分配更多的灰度值。相鄰的兩個像素的濾波器相交，有利于縮小直線條上相鄰像素的灰度差。具體算法見p213加權(quán)區(qū)域取樣特點：64半色調(diào)技術(shù)簡單區(qū)域取樣和加權(quán)區(qū)域取樣技術(shù)的前提是多級灰度，利用多級灰度來提高視覺分辨率。但是，若只有兩級灰度呢？能否使用上述技術(shù)呢？對于給定的分辨率，通過將幾個像素組合成一個單元來獲得多級灰度。例：在一個顯示器中將四個像素組成一個單元，可產(chǎn)生5種光強。半色調(diào)技術(shù)簡單區(qū)域取樣和加權(quán)區(qū)域取樣技術(shù)的前提是多級灰度，利65半色調(diào)技術(shù)可用如下矩陣來表示：

它表示黑色像素填入22個位置中的次序，每一級灰度再添上一個黑色像素就得到下一級灰度。注意：1．要盡量避免連成一條直線的花樣。2．花樣是可以選擇的。單元也可以是長方形，如半色調(diào)技術(shù)可用如下矩陣來表示：66半色調(diào)技術(shù)一般來說，對于兩級灰度顯示器可能構(gòu)成的灰度數(shù)等于單元中像素個數(shù)加1∴單元越大，灰度級別越高它是以犧牲空間分辨率為代價的。半色調(diào)技術(shù)一般來說，對于兩級灰度顯示器可能構(gòu)成的灰度數(shù)等于單67半色調(diào)技術(shù)例：灰度級別=4,每個單元=2*2若有m級灰度，nn個像素組成一個單元，則灰度級別數(shù)為nn(m-1)+1半色調(diào)技術(shù)例：灰度級別=4,每個單元=2*268

裁剪算法

反走樣方法

第五章 裁剪、反走樣方法 裁剪算法第五章 裁剪、反走樣方法69二維裁剪直線段裁剪

直接求交算法

Cohen-Sutherland算法

中點分割算法

梁友棟-Barskey算法

參數(shù)化裁剪算法多邊形裁剪

Sutherland_Hodgman算法

Weiler-Athenton算法二維裁剪直線段裁剪70裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。圖形裁剪算法，直接影響圖形系統(tǒng)的效率。裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之71點的裁剪圖形裁剪中最基本的問題。假設(shè)窗口的左下角坐標(biāo)為(xL,yB),右上角坐標(biāo)為(xR,yT)，對于給定點P(x,y),則P點在窗口內(nèi)的條件是要滿足下列不等式：否則，P點就在窗口外。問題：對于任何多邊形窗口，如何判別？(xL,yB)(xR,yT)xL<=x<=xR并且yB<=y<=yT點的裁剪圖形裁剪中最基本的問題。(xL,yB)(xR,y72直線段裁剪直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。直接求交算法Cohen-Sutherland算法中點分割算法梁友棟－barskey算法參數(shù)化裁剪算法直線段裁剪直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以73直線段裁剪裁剪線段與窗口的關(guān)系：(1)線段完全可見；(2)顯然不可見；(3)其它提高裁剪效率： 快速判斷情形(1)(2)， 對于情形(3)，設(shè)法減 少求交次數(shù)和每次求 交時所需的計算量。直線段裁剪74直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。直接求交算法直線與窗口邊都75Cohen-Sutherland裁剪基本思想：對于每條線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。為快速判斷，采用如下編碼方法：Cohen-Sutherland裁剪基本思想：76實現(xiàn)方法：

將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一個四位二進制數(shù)標(biāo)識，直線的端點都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來標(biāo)識出端點相對于裁剪矩形邊界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪實現(xiàn)方法：10010001010110000000077Cohen-Sutherland算法將區(qū)域碼的各位從左到右編號，則坐標(biāo)區(qū)域與各位的關(guān)系為：上下右左 XXXX 任何位賦值為1，代表端點落在相應(yīng)的位置上，否則該位為0。若端點在剪取矩形內(nèi)，區(qū)域碼為0000。如果端點落在矩形的左下角，則區(qū)域碼為0101。Cohen-Sutherland算法將區(qū)域碼的各位從左到右編78Cohen-Sutherland算法一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。所以得到一個規(guī)律：Cohen-Sutherland算法一旦給定所有的線段端點79Cohen-Sutherland裁剪若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取”若P1P2明顯在窗口外code1&code2≠0，則“棄”在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。

100100010101100000000100101000100110BCDACohen-Sutherland裁剪若P1P2完全在窗口內(nèi)c80Cohen-Sutherland裁剪如何判定應(yīng)該與窗口的哪條邊求交呢？ 編碼中對應(yīng)位為1的邊。計算線段P1(x1,y1)--P2(x2,y2)與窗口邊界的交點 if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}Cohen-Sutherland裁剪如何判定應(yīng)該與窗口的哪81Cohen-Sutherland

直線裁剪算法小結(jié)優(yōu)點：簡單，易于實現(xiàn)。可以簡單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進行，處理之后，剩余部分就是可見的了。算法中求交點是很重要的，他決定了算法的速度。另外，本算法對于其他形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。Cohen-Sutherland

直線裁剪算法小結(jié)優(yōu)點：簡82中點分割裁剪算法基本思想：從P0點出發(fā)找離P0最近的可見點，從P1點出發(fā)找離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。首先對線段端點進行編碼，并把線段與窗口的關(guān)系分為三種情況，對前兩種情況，進行與Cohen-Sutherland算法一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距P0、P1最近的可見點，Pm為P0P1中點。

中點分割裁剪算法基本思想：從P0點出發(fā)找離P0最近的可見點，83中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復(fù)上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時Pm收斂于交點。從P1出發(fā)找距離P1最近可見點采用上面類似方法。中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見84中點分割裁剪算法中點分割裁剪算法85對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點分割裁剪算法對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。中點86

設(shè)要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,C,D四點。算法的基本思想是從A,B和P0三點中找出最靠近P1的點，圖中要找的點是P0。從C,D和P1中找出最靠近P0的點，圖中要找的點是C點。P0C就是P0P1線段上的可見部分。梁友棟-Barsky算法設(shè)要裁剪的線段是P0P1。P0P1和窗口邊界交于A87梁友棟-Barsky算法線段的參數(shù)表示x=x0+t△xy=y0+t△y0<=t<=1△x=x1-x0△y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。梁友棟-Barsky算法線段的參數(shù)表示88求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=max(t0,t1,0)，則tL即為三者中離p1最近的點的參數(shù)。求出p0p1與兩條終邊的交點參數(shù)t2,t3,令tu=min(t2,t3,1)，則tU即為三者中離p0最近的點的參數(shù)若tu>tl,則可見線段區(qū)間[tl,tu]梁友棟-Barsky算法：交點計算求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=m89梁友棟-Barsky算法始邊和終邊的確定及交點計算：令QL=-△xDL=x0-xLQR=△xDR=xR-x0

QB=-△yDB=y0-yBQT=△yDT=yT-y0交點為ti=Di/

Qii=L,R,B,TQi<0ti為與始邊交點參數(shù)Qi>0ti為與終邊交點參數(shù)Qi=0Di<0時,線段不可見Di>0時,分析另一D,

EFAB梁友棟-Barsky算法始邊和終邊的確定及交點計算：EFAB90梁友棟-Barsky算法當(dāng)Qi=0時若Di<0時,線段不可見（如圖中AB，有QR=0，DR<0）若Di>0時,分析另一D,（如圖中的EF就是這種情況，它使QL=0，DL>0和QR=0，DR>0。這時求EF和y=yT及y=yB的交點決定直線段上的可見部分。）

EFAB梁友棟-Barsky算法當(dāng)Qi=0時EFAB91參數(shù)化算法(Cyrus-Beck)考慮凸多邊形區(qū)域R和直線段P1P2 P(t)=(P2-P1)*t+P1設(shè)A是區(qū)域R的邊界上一點，N是區(qū)域邊界在A點的內(nèi)法線向量ARNP1P2參數(shù)化算法(Cyrus-Beck)考慮凸多邊形區(qū)域R和直線段92參數(shù)化算法(Cyrus-Beck)則對于線段P1P2上任一點P(t)N·(P(t)-A)<0->外側(cè)N·(P(t)-A)>0->內(nèi)側(cè)N·(P(t)-A)=0->邊界或其延長線上ARNP1P2參數(shù)化算法(Cyrus-Beck)則對于線段P1P2上任一點93參數(shù)化算法(Cyrus-Beck)凸多邊形的性質(zhì)：點P(t)在凸多邊形內(nèi)的充要條件是，對于凸多邊形邊界上任意一點A和該點處內(nèi)法向N，都有 N·(P(t)-A)>0參數(shù)化算法(Cyrus-Beck)凸多邊形的性質(zhì)：點P(t)94參數(shù)化算法(Cyrus-Beck)K+1條邊的多邊形，可見線段參數(shù)區(qū)間的解:Ni·(p(t)-Ai)>=0,i=0,…,k,0≤t≤1.即：Ni·(P1-Ai)+Ni·(P2-P1)t>=0(1)式可得：

令ti=Ni·(P1-Ai)/[Ni·(P2-P1)]參數(shù)化算法(Cyrus-Beck)K+1條邊的多邊形，可見線95參數(shù)化算法(Cyrus-Beck)Ni·(P2-P1)=0->平行于對應(yīng)邊。此時判斷Ni·(P1-Ai)若Ni·(P1-Ai)<0->P1P2在多邊形外側(cè)->不可見，若Ni·(P1-Ai)>0->P1P2在多邊形內(nèi)側(cè)->繼續(xù)其它邊的判斷參數(shù)化算法(Cyrus-Beck)Ni·(P2-P1)=96參數(shù)化算法(Cyrus-Beck)對于t值的選擇：首先,要符合0≤t≤1；其次,對于凸窗口來說，每一個線段與其至多有兩個交點，即有兩個相應(yīng)的t值。所以把計算出的t值分成兩組：一組為下限組，分布在線段起點一側(cè)；一組為上限組，分布在線段終點一側(cè)。找出下限組中的最大值及上限組中的最小值，就可確定線段了。分組的依據(jù)是：如果Ni·(P2-P1)＜0,則計算出的值屬于上限組如果Ni·(P2-P1)＞0,則計算出的值屬于下限組參數(shù)化算法(Cyrus-Beck)對于t值的選擇：首先,要符97參數(shù)化算法(Cyrus-Beck)因此，線段可見的交點參數(shù)：tl=max{0,max{ti:Ni·(P2-P1)>0}}tu=min{1,min{ti:Ni·(P2-P1)<0}}若tl<=tu,[tl，tu]是可見線段的交點參數(shù)區(qū)間，否則，線段不可見。參數(shù)化算法(Cyrus-Beck)因此，線段可見的交點參數(shù)：98參數(shù)化算法的幾何意義下限組以Ni·(P2-P1)>0為特征，表示在該處沿P1P2方向前進將接近或進入多邊形內(nèi)側(cè)。上限組以Ni·(P2-P1)<0為特征，表示在該處沿P1P2方向前進將越來越遠(yuǎn)地離開多邊形區(qū)域。參數(shù)化算法的幾何意義下限組以Ni·(P2-P1)>0為特99參數(shù)化算法當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時，該算法退化為Liang-Barsky算法。參數(shù)化算法當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時，該算100多邊形裁剪錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？多邊形裁剪錯覺：直線段裁剪的組合？101多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確102Sutherland-Hodgman算法分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法Sutherland-Hodgman算法分割處理策略：將多邊103Sutherland-Hodgman算法基本思想是一次用窗口的一條邊裁剪多邊形。考慮窗口的一條邊以及延長線構(gòu)成的裁剪線,把平面分成兩個部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關(guān)系只有四種Sutherland-Hodgman算法基本思想是一次用窗口104Sutherland-Hodgman算法情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點PSutherland-Hodgman算法105Sutherland-Hodgman算法框圖

處理線段SP過程子框圖一條裁剪線的處理流程Sutherland-Hodgman算法框圖處理線段SP過程106Sutherland-Hodgman算法上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，算法框圖同上，只是判斷點在窗口哪一側(cè)以及求線段SP與裁剪邊的交點算法應(yīng)隨之改變。Sutherland-Hodgman算法上述算法僅用一條裁剪107Sutherland-Hodgeman算法對凸多邊形應(yīng)用本算法可以得到正確的結(jié)果，但是對凹多邊形的裁剪將如圖所示顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現(xiàn)。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。再有就是Weiler-Atherton算法。Sutherland-Hodgeman算法對凸多邊形應(yīng)用本算108Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為BWeiler-Athenton算法109Weiler-Athenton算法多邊形頂點的排列順序（使多邊形區(qū)域位于有向邊的左側(cè)）外環(huán)：逆時針；內(nèi)環(huán)：順時針主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-B裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界Weiler-Athenton算法多邊形頂點的排列順序（使多110Weiler-Athenton算法如果主多邊形與裁剪多邊形有交點，則交點成對出現(xiàn)，它們被分為如下兩類：進點：主多邊形邊界由此進入裁剪多邊形內(nèi)如，I1,I3,I5,I7,I9,I11出點：主多邊形邊界由此離開裁剪多邊形區(qū)域.如，I0,I2,I4,I6,I8,I10Weiler-Athenton算法如果主多邊形與裁剪多邊形有111Weiler-Athenton算法1）建頂點表；2）求交點；3）裁剪……1、建立主多邊形和裁剪多邊的頂點表．2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針。3、裁剪:如果存在沒有被跟蹤過的交點，執(zhí)行以下步驟：

Weiler-Athenton算法1）建頂點表；1、建立主多112Weiler-Athenton算法Weiler-Athenton算法113Weiler-Athenton算法(1)建立空的裁剪結(jié)果多邊形的頂點表．(2)選取任一沒有被跟蹤過的交點為始點，將其輸出到結(jié)果多邊形頂點表中．(3)如果該交點為進點，跟蹤主多邊形邊邊界；否則跟蹤裁剪多邊形邊界．(4)跟蹤多邊形邊界，每遇到多邊形頂點，將其輸出到結(jié)果多邊形頂點表中，直至遇到新的交點．(5)將該交點輸出到結(jié)果多邊形頂點表中，并通過連接該交點的雙向指針改變跟蹤方向（如果上一步跟蹤的是主多邊形邊界，現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊界，現(xiàn)在改為跟蹤主多邊形邊界）．(6)重復(fù)(4)、(5)直至回到起點取I7為起點，所得裁剪結(jié)果多邊形I7I0q0I3I4I5I6I7。取I8為起點，所得裁剪結(jié)果多邊形為I8I9I10I11I2q2I1I8。Weiler-Athenton算法(1)建立空的裁剪114Weiler-Athenton算法交點的奇異情況處理

1、與裁剪多邊形的邊重合的主多邊形的邊不參與求交點；2、對于頂點落在裁剪多邊形的邊上的主多邊形的邊，如果落在該裁剪邊的內(nèi)側(cè)，將該頂點算作交點；而如果這條邊落在該裁剪邊的外側(cè)，將該頂點不看作交點Weiler-Athenton算法交點的奇異情況處理115反走樣用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing)。光柵圖形的走樣現(xiàn)象階梯狀邊界；圖形細(xì)節(jié)失真；狹小圖形遺失：動畫序列中時隱時現(xiàn)，產(chǎn)生閃爍。反走樣用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(alias116走樣現(xiàn)象舉例不光滑(階梯狀）的圖形邊界例子：PaintBrush走樣現(xiàn)象舉例不光滑(階梯狀）的圖形邊界例子：PaintBru117走樣現(xiàn)象舉例圖形細(xì)節(jié)失真走樣現(xiàn)象舉例圖形細(xì)節(jié)失真118走樣現(xiàn)象舉例狹小圖形的遺失與動態(tài)圖形的閃爍走樣現(xiàn)象舉例狹小圖形的遺失與動態(tài)圖形的閃爍119反走樣概念及方法用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣(antialiasing)反走樣方法提高分辨率