裁剪算法 反走樣方法

1、,裁剪算法 反走樣方法,第五章裁剪、反走樣方法,二維裁剪,直線段裁剪 直接求交算法 Cohen-Sutherland算法 中點分割算法 梁友棟-Barskey算法 參數(shù)化裁剪算法多邊形裁剪 Sutherland_Hodgman算法 Weiler-Athenton算法,裁剪,裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。

2、 圖形裁剪算法，直接影響圖形系統(tǒng)的效率。,點的裁剪,圖形裁剪中最基本的問題。 假設(shè)窗口的左下角坐標(biāo)為(xL,yB),右上角坐標(biāo)為(xR,yT)，對于給定點P(x,y),則P點在窗口內(nèi)的條件是要滿足下列不等式：否則，P點就在窗口外。問題：對于任何多邊形窗口，如何判別？,,,xL <= x <= xR 并且yB <= y <= yT,直線段裁剪,直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以

3、通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。直接求交算法Cohen-Sutherland算法中點分割算法梁友棟－barskey算法參數(shù)化裁剪算法,直線段裁剪,裁剪線段與窗口的關(guān)系：(1)線段完全可見；(2)顯然不可見；(3)其它提高裁剪效率：快速判斷情形(1)(2)，對于情形(3)，設(shè)法減少求交次數(shù)和每次求交時所需的計算量。,直接求交算法,直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。,Cohen

4、-Sutherland裁剪,基本思想：對于每條線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。為快速判斷，采用如下編碼方法：,實現(xiàn)方法： 將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一個四位二進(jìn)制數(shù)標(biāo)識，直線

5、的端點都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來標(biāo)識出端點相對于裁剪矩形邊界的位置。,,,,,1001,0001,0101,1000,0000,0100,1010,0010,0110,,,,,,A,B,C,D,Cohen-Sutherland裁剪,Cohen-Sutherland算法,將區(qū)域碼的各位從左到右編號，則坐標(biāo)區(qū)域與各位的關(guān)系為： 上 下 右 左

6、 X X X X任何位賦值為1，代表端點落在相應(yīng)的位置上，否則該位為0。若端點在剪取矩形內(nèi)，區(qū)域碼為0000。如果端點落在矩形的左下角，則區(qū)域碼為0101。,Cohen-Sutherland算法,一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。所以得到一個規(guī)律：,Cohen-Suthe

7、rland裁剪,若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取”若P1P2明顯在窗口外code1&code2≠0，則“棄” 在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。,,,,,1001,0001,0101,1000,0000,0100,1010,0010,0110,,,,,,B,C,D,A,Cohen-Sutherland裁剪,如何判定應(yīng)該與窗口的哪條邊求交呢？ 編碼

8、中對應(yīng)位為1的邊。計算線段P1(x1,y1)--P2(x2,y2)與窗口邊界的交點if ( LEFT &code !=0 ){x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);}else if ( RIGHT & code !=0 ){x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);}else if ( BOTTOM & code !=0 )

9、 {y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);} else if ( TOP & code !=0 ) {y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);},Cohen-Sutherland直線裁剪算法小結(jié),優(yōu)點：簡單，易于實現(xiàn)。可以簡單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進(jìn)行，處理之后，剩余部分就是可見的了。算法中求交點是很重要的，他

10、決定了算法的速度。另外，本算法對于其他形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。,中點分割裁剪算法,基本思想：從P0點出發(fā)找離P0最近的可見點，從P1點出發(fā)找離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。首先對線段端點進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況，對前兩種情況，進(jìn)行與Cohen-Sutherland算法一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A

11、、B分別為距P0 、 P1最近的可見點，Pm為P0P1中點。,中點分割算法-求線段與窗口的交點,從P0出發(fā)找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復(fù)上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時Pm收斂于交點。從P1出

12、發(fā)找距離P1最近可見點采用上面類似方法。,中點分割裁剪算法,,對分辯率為2N*2N的顯示器，上述二分過程至多進(jìn)行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。,中點分割裁剪算法,設(shè)要裁剪的線段是P0P1。 P0P1和窗口邊界交于A,B,C,D四點。 算法的基本思想是從A,B和P0三點中找出最靠近P1的點，圖中要找的點是P0。從C,D和P1中找出最靠近P0的點，圖中要找的點是C

13、點。 P0C就是P0P1線段上的可見部分。,梁友棟-Barsky算法,梁友棟-Barsky算法,線段的參數(shù)表示x=x0+t△xy=y0+t△y 0<=t<=1 △x=x1-x0 △y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。,求出P0P1與兩條始邊的交點參數(shù)t0, t1 , 令tl=max(t0 ,t1,0)，則tL即為三者中離p1最近的點的參數(shù)。求出p

14、0p1與兩條終邊的交點參數(shù)t2, t3, 令tu=min(t2,t3,1) ，則tU即為三者中離p0最近的點的參數(shù)若tu > tl,則可見線段區(qū)間 [tl , tu],梁友棟-Barsky算法：交點計算,梁友棟-Barsky算法,始邊和終邊的確定及交點計算：令 QL= - △x DL= x0-xL QR= △x DR= xR-x0 QB= - △y DB= y0-yB

15、 QT= △y DT= yT-y0交點為 ti= Di / Qi i=L,R,B,TQi 0 ti為與終邊交點參數(shù)Qi =0 Di 0 時, 分析另一D,,梁友棟-Barsky算法,當(dāng)Qi =0時 若Di 0 時, 分析另一D, （如圖中的EF就是這種情況，它使QL=0，DL>0和QR=0，DR>0。 這時求EF和y=yT及y=y

16、B的交點決定直線段上的可見部分。）,,,,E,F,A,B,參數(shù)化算法(Cyrus-Beck),考慮凸多邊形區(qū)域R和直線段P1P2P(t)=(P2-P1)*t+P1 設(shè)A是區(qū)域R的邊界上一點，N是區(qū)域邊界在A點的內(nèi)法線向量,參數(shù)化算法(Cyrus-Beck),則對于線段P1P2上任一點P(t)N ·(P(t)-A)外側(cè)N ·(P(t)-A)>0->內(nèi)側(cè)N ·(P(t)-A)=

17、0->邊界或其延長線上,,,,,,,,,,,A,R,N,P1,P2,參數(shù)化算法(Cyrus-Beck),凸多邊形的性質(zhì)：點P(t)在凸多邊形內(nèi)的充要條件是，對于凸多邊形邊界上任意一點A和該點處內(nèi)法向N，都有N·(P(t)-A)>0,參數(shù)化算法(Cyrus-Beck),K+1條邊的多邊形，可見線段參數(shù)區(qū)間的解:Ni· (p(t)-Ai)>=0, i=0,…,k, 0≤t ≤1.即：Ni&

18、#183; (P1-Ai)+ Ni· (P2-P1) t>=0 (1)式可得： 令ti= Ni· (P1-Ai)/[Ni· (P2-P1) ],參數(shù)化算法(Cyrus-Beck),Ni· (P2-P1) =0-> 平行于對應(yīng)邊。此時判斷Ni· (P1-Ai)若Ni· (P1-Ai) P1 P2在多邊形外側(cè)->不可見，若Ni·

19、 (P1-Ai) >0->P1 P2在多邊形內(nèi)側(cè)->繼續(xù)其它邊的判斷,參數(shù)化算法(Cyrus-Beck),對于t值的選擇：首先,要符合0≤t≤1；其次,對于凸窗口來說，每一個線段與其至多有兩個交點，即有兩個相應(yīng)的t值。所以把計算出的t值分成兩組：一組為下限組，分布在線段起點一側(cè)；一組為上限組，分布在線段終點一側(cè)。找出下限組中的最大值及上限組中的最小值，就可確定線段了。分組的依據(jù)是：如果Ni·(P2-P1)

20、＜0,則計算出的值屬于上限組如果Ni·(P2-P1)＞0,則計算出的值屬于下限組,參數(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ù)化算法的幾何意

21、義,下限組以Ni· (P2-P1) >0為特征，表示在該處沿P1P2方向前進(jìn)將接近或進(jìn)入多邊形內(nèi)側(cè)。,上限組以Ni·(P2-P1)<0為特征，表示在該處沿P1P2方向前進(jìn)將越來越遠(yuǎn)地離開多邊形區(qū)域。,參數(shù)化算法,當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時，該算法退化為Liang-Barsky算法。,多邊形裁剪,錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確

22、定其邊界？,多邊形裁剪,,2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？,Sutherland-Hodgman算法,分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。,亦稱逐邊裁剪算法,Sutherland-Hodgman算法,基本思想是一次用窗口的一條邊裁剪多邊形?？紤]窗口的一條邊以及延長線構(gòu)成的裁剪線,把平面分成兩個部分:可見

23、一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關(guān)系只有四種,Sutherland-Hodgman算法,情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點P,Sutherland-Hodgman算法框圖,,處理線段SP過程子框圖,一條裁剪線的處理流程,Sutherland-Hodgman算法,上述算法僅用一條裁剪邊對多邊形進(jìn)行裁剪，

24、得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，算法框圖同上，只是判斷點在窗口哪一側(cè)以及求線段SP與裁剪邊的交點算法應(yīng)隨之改變。,Sutherland-Hodgeman算法,對凸多邊形應(yīng)用本算法可以得到正確的結(jié)果，但是對凹多邊形的裁剪將如圖所示顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現(xiàn)。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是

25、把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。再有就是Weiler-Atherton算法。,,,Weiler-Athenton算法,裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A 裁剪多邊形：裁剪窗口，記為B,Weiler-Athenton算法,多邊形頂點的排列順序（使多邊形區(qū)域位于有向邊的左側(cè) ）外環(huán)：逆時針 ；

26、內(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算法,如果主多邊形與裁剪多邊形有交點，則交點成對出現(xiàn)，它們被分為如下兩類：進(jìn)點：主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi) 如，I1,I3, I5, I7, I9, I11出點：

27、主多邊形邊界由此離開裁剪多邊形區(qū)域. 如， I0,I2, I4, I6, I8, I10,Weiler-Athenton算法,1）建頂點表；2）求交點；3）裁剪… …,1、建立主多邊形和裁剪多邊的頂點表．2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針 。3、裁剪: 如果存在沒有被跟蹤過的交點，執(zhí)行以下步驟：,Weiler-Athenton算

28、法,Weiler-Athenton算法,(1)建立空的裁剪結(jié)果多邊形的頂點表． (2)選取任一沒有被跟蹤過的交點為始點，將其輸出到結(jié)果多邊形頂點表中． (3)如果該交點為進(jìn)點，跟蹤主多邊形邊邊界；否則跟蹤裁剪多邊形邊界． (4) 跟蹤多邊形邊界，每遇到多邊形頂點，將其輸出到結(jié)果多邊形頂點表中，直至遇到新的交點． (5)將該交點輸出到結(jié)果多邊形頂點表中，并通過連接該交點的雙向指針改變跟蹤方向（如果上一步跟蹤

29、的是主多邊形邊界，現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊界，現(xiàn)在改為跟蹤主多邊形邊界）． (6)重復(fù)(4)、(5)直至回到起點取I7為起點，所得裁剪結(jié)果多邊形I7I0q0I3I4I5I6I7。取I8為起點，所得裁剪結(jié)果多邊形為I8I9I10I11I2q2I1I8。,Weiler-Athenton算法,交點的奇異情況處理 1、與裁剪多邊形的邊重合的主多邊形的邊不參與求交點；2、對于頂點落在裁剪多

30、邊形的邊上的主多邊形的邊，如果落在該裁剪邊的內(nèi)側(cè)，將該頂點算作交點；而如果這條邊落在該裁剪邊的外側(cè)，將該頂點不看作交點,反走樣,用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing) 。光柵圖形的走樣現(xiàn)象階梯狀邊界；圖形細(xì)節(jié)失真；狹小圖形遺失：動畫序列中時隱時現(xiàn)，產(chǎn)生閃爍。,走樣現(xiàn)象舉例,不光滑(階梯狀）的圖形邊界,例子：PaintBrush,走樣現(xiàn)象舉例,圖形細(xì)節(jié)失真,走樣現(xiàn)象舉例,狹小圖形的遺失與動態(tài)圖形的閃爍,

31、反走樣概念及方法,用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣(antialiasing)反走樣方法提高分辨率簡單區(qū)域取樣加權(quán)區(qū)域取樣半色調(diào)技術(shù),提高分辨率,把顯示器分辨率提高一倍，直線經(jīng)過兩倍的象素，鋸齒也增加一倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。,提高分辨率,方法簡單，但代價非常大。顯示器的水平、豎直分辯率各提高一倍，則顯示器的點距減少一倍，幀緩存容量則增加到原來的4倍，而掃描轉(zhuǎn)

32、換同樣大小的圖元卻要花4倍時間。而且它也只能減輕而不能消除鋸齒問題另一種方法（軟件方法）： 用較高的分辨率的顯示模式下計算，（對各自像屬下計算，再求（非）加權(quán)平均的顏色值），在較低的分辨率模式下顯示。只能減輕而不能消除鋸齒問題。,軟件方法1,把每個像素分為四個子像素，掃描轉(zhuǎn)換算法求得各子像素的灰度值，然后對四像素的灰度值簡單平均，作為該像素的灰度值。,軟件方法2,設(shè)分辨率為m?n,把顯示窗口分為(2m+1)?(

33、2n+1)個子像素，對每個子像素進(jìn)行灰度值計算，然后根據(jù)權(quán)值表所規(guī)定的權(quán)值，對位于像素中心及四周的九個子像素加權(quán)平均，作為顯示像素的顏色。設(shè)m=3,n=4,簡單區(qū)域取樣,方法由來兩點假設(shè)1、象素是數(shù)學(xué)上抽象的點，它的面積為0，它的亮度由覆蓋該點的圖形的亮度所決定；2、直線段是數(shù)學(xué)上抽象直線段，它的寬度為0?，F(xiàn)實像素的面積不為0；直線段的寬度至少為1個像素；假設(shè)與現(xiàn)實的矛盾是導(dǎo)致混淆出現(xiàn)的原因之一,簡單區(qū)域取樣,解決方法：

34、改變直線段模型，由此產(chǎn)生算法方法步驟：,1、將直線段看作具有一定寬度的狹長矩形；2、當(dāng)直線段與某象素有交時,求出兩者相交區(qū)域的面積；3、根據(jù)相交區(qū)域的面積，確定該象素的亮度值,簡單區(qū)域取樣,基本思想：每個象素是一個具有一定面積的小區(qū)域，將直線段看作具有一定寬度的狹長矩形。當(dāng)直線段與象素有交時，求出兩者相交區(qū)域的面積，然后根據(jù)相交區(qū)域面積的大小確定該象素的亮度值。 有寬度的線條輪廓 象素相交的五

35、種情況及用于計算面積的量,簡單區(qū)域取樣,面積計算情況⑴（5)陰影面積為：D2/2m；情況⑵（4)陰影面積為：D - m/2；情況⑶陰影面積為：1 - D2/m 為了簡化計算可以采用離散的方法,簡單區(qū)域取樣,求相交區(qū)域的近似面積的離散計算方法,1、將屏幕象素分割成n個更小的子象素；2、計算中心點落在直線段內(nèi)的子象素的個數(shù)，記為k，3、k/n為線段與象素相交區(qū)域面積的近似值,目的：簡化計算n = 16, k = 3近

36、似面積 = 3/16,簡單區(qū)域取樣,簡單區(qū)域取樣采用的是一個盒式濾波器，它是一個二維加權(quán)函數(shù)，以w表示。w =1 若在當(dāng)前像素所代表的正方形上w =0 其它區(qū)域上直線條經(jīng)過該像素時，該像素的灰度值可以通過在像素與直線條的相交區(qū)域上對w求積分獲得。此時，面積值=體積值,加權(quán)區(qū)域取樣,采用圓錐形濾波器，圓錐的底圓中心在當(dāng)前像素，底圓半徑為一個像素，錐高為1。當(dāng)直線條經(jīng)過該像素時，該像素的灰度值是在二者相交區(qū)域上對濾波器進(jìn)行積

37、分的積分值。見p213的圖4.7.9,加權(quán)區(qū)域取樣,特點：接近理想直線的像素將被分配更多的灰度值。相鄰的兩個像素的濾波器相交，有利于縮小直線條上相鄰像素的灰度差。具體算法見p213,半色調(diào)技術(shù),簡單區(qū)域取樣和加權(quán)區(qū)域取樣技術(shù)的前提是多級灰度，利用多級灰度來提高視覺分辨率。但是，若只有兩級灰度呢？能否使用上述技術(shù)呢？對于給定的分辨率，通過將幾個像素組合成一個單元來獲得多級灰度。例：在一個顯示器中將四個像素組成一個單元，可產(chǎn)生5

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