ch05 二維圖形變換及裁剪0402.ppt

1、1,第5章 二維圖形變換及裁剪,2,第5章 二維圖形變換及裁剪,5.1 變換的數(shù)學(xué)基礎(chǔ) 5.2 二維幾何變換 5.3 二維圖形裁剪,3,5.1 變換的數(shù)學(xué)基礎(chǔ),5.1.1 矢量及其運算 5.1.2 矩陣及其運算 5.1.3 齊次坐標(biāo),4,5.1.1 矢量及其運算,矢量的定義 矢量：n元組。(由n個實數(shù)組成的集合) 如：二維矢量(x,y)，三維矢量(x,y,z),5,5.1.1 矢量及其運算,矢量 矢量的加法,6,5.1.1 矢量及其運算,矢量的數(shù)乘 矢量的點積(內(nèi)積) U V=|U | |V | cos,7,5.1.1 矢量及其運算,矢量點積(內(nèi)積)的性質(zhì)：,8,5.1.1 矢量及其運算,矢量

2、點積(內(nèi)積)的性質(zhì)： 交換律 結(jié)合律 分配律,9,5.1.1 矢量及其運算,矢量的長度 單位矢量：長度為1的矢量(i,j,k,e,) 矢量的夾角:,10,5.1.1 矢量及其運算,矢量的叉積(向量積) 2個互不平行的矢量，其叉積形成一個與2個矢量都垂直的新的矢量，它的方向符合右手判別法，大小為： | UV |=|U|*|V|*Sin 如果U平行于V，則UV=(0,0,0),11,5.1.1 矢量及其運算,矢量叉積的性質(zhì)： 結(jié)合律 分配律,12,5.1.1 矢量及其運算,矢量叉積的性質(zhì)： 在直角坐標(biāo)系下：,13,5.1 變換的數(shù)學(xué)基礎(chǔ),5.1.1 矢量及其運算 5.1.2 矩陣及其運算 5.1.

3、3 齊次坐標(biāo),14,5.1.2 矩陣及其運算,矩陣的定義： 由mn個數(shù)按m行n列排列的一個整體，簡稱mn矩陣。 其中，aij 稱為矩陣A的第i 行第j 列元素,15,矩陣運算 加法 設(shè)A，B為兩個具有相同行和列數(shù)的矩陣， 數(shù)乘 kA = k*aij |i=1.m, j=1,. n,5.1.2 矩陣及其運算,16,乘法 設(shè)A為mn矩陣，B為np矩陣 單位矩陣 在一矩陣中，主對角線各元素aii =1，其余元素皆為0的矩陣稱為單位矩陣。n階單位矩陣通常記作In 。 Am n = Am n In,5.1.2 矩陣及其運算,17,逆矩陣 若矩陣A存在AA-1=A-1A=I，則稱A-1為A的逆矩陣。 矩陣

4、的轉(zhuǎn)置 把矩陣A=(aij)mn的行和列互換而得到的nm矩陣稱為A的轉(zhuǎn)置矩陣，記作AT 。 (AT) T = A (A+B)T = AT + BT (aA)T = aAT (AB)T = BT AT 當(dāng)A為n階矩陣，且A=AT ，則A是對稱矩陣。,5.1.2 矩陣及其運算,18,矩陣運算的基本性質(zhì) 加法的交換律與結(jié)合律 A+B=B+A; A+(B+C)=(A+B)+C 數(shù)乘的分配律及結(jié)合律 a(A+B) = aA+aB; a(A B) = (aA) B=A (aB) (a+b)A = aA + bA a(bA) = (ab)A,5.1.2 矩陣及其運算,19,矩陣乘法的結(jié)合律及分配律 A(B

5、C) = (A B)C (A+B) C = A C+ B C C (A+B) = C A + C B 矩陣的乘法不滿足交換律！,5.1.2 矩陣及其運算,20,5.1 變換的數(shù)學(xué)基礎(chǔ),5.1.1 矢量及其運算 5.1.2 矩陣及其運算 5.1.3 齊次坐標(biāo),21,5.1.3 齊次坐標(biāo),所謂齊次坐標(biāo)表示法就是由n+1維向量表示一個n 維向量。如n 維向量(P1,P2, ,Pn)表示為（hP1,hP2,hPn，h），其中h是任一不為0的比例系數(shù)，稱為啞坐標(biāo)或比例因子。 h可以取不同的值，所以同一點的齊次坐標(biāo)不是唯一的。如普通坐標(biāo)系下的點（2,3）變換為齊次坐標(biāo)可以是(1,1.5,0.5)、(4,6

6、,2)、(6,9,3)等等。 普通坐標(biāo)與齊次坐標(biāo)的關(guān)系為“一對多” 由普通坐標(biāo)h齊次坐標(biāo) 由齊次坐標(biāo)h普通坐標(biāo) 當(dāng)h=1時，稱為規(guī)格化的齊次坐標(biāo)。 在計算機(jī)圖形學(xué)中，通常使用規(guī)格化的齊次坐標(biāo)。,22,例：(x,y)點對應(yīng)的齊次坐標(biāo)為: (x,y)點對應(yīng)的齊次坐標(biāo)為三維空間的一條直線：,5.1.3 齊次坐標(biāo),23,齊次坐標(biāo)的作用 1. 將各種變換用階數(shù)統(tǒng)一的矩陣來表示。使變換矩陣具有統(tǒng)一的表示形式，便于變換的合成(組合變換)及軟、硬件實現(xiàn)。 2. 便于表示n維無窮遠(yuǎn)點。 例如：(xh, yh, h)，令h等于0時，表示二維平面中的無窮遠(yuǎn)點。,5.1.3 齊次坐標(biāo),24,第5章 二維圖形變換及裁剪

7、,5.1 變換的數(shù)學(xué)基礎(chǔ) 5.2 二維幾何變換 5.3 二維圖形裁剪,25,5.2 二維幾何變換,1. 平移變換 2. 縮放變換 3. 旋轉(zhuǎn)變換 4. 變形變換 5. 反射(對稱)變換 6. 組合變換,26,總結(jié)以上這些變換后的圖形結(jié)果，可以得到這樣的結(jié)論： 圖形變化了，但原圖形的構(gòu)成規(guī)則（拓?fù)潢P(guān)系）沒有改變； 圖形發(fā)生的變化，是其頂點位置（幾何信息）的改變決定的。 這種通過維持圖形的拓?fù)潢P(guān)系不變，而僅改變圖形的幾何位置來實現(xiàn)圖形改變的方法，我們稱之為圖形的幾何變換。,幾種常見的幾何變換：旋轉(zhuǎn)、錯切、縮放。,5.2 二維幾何變換 概 述,27,幾何變換： 在二維圖形處理過程中，常常需要對平面圖

8、形的形狀、尺寸、方向和位置進(jìn)行修改，來達(dá)到改變圖形的目的。 幾何變換：是一種線性變換。 對原來圖形中一點的坐標(biāo)通過變換生成一個新的點坐標(biāo)；對原來圖形中的一條直線的變換是通過直線上的兩點作變換生成新的端點坐標(biāo)，然后連接這兩個新的端點，便得到變換后的直線；類似的，可以進(jìn)行各種圖形的幾何變換。 幾何變換的表示采用矩陣形式，稱為變換矩陣；點的坐標(biāo)表示采用齊次坐標(biāo)形式。故幾何變換操作的過程是將變換矩陣M作用于齊次坐標(biāo)點P生成新的坐標(biāo)點P,即P=MP。,5.2 二維幾何變換 概 述,28,P(x,y),1. 平移變換,點的平移變換是指該點在X軸和Y軸方向上分別移動一段距離。設(shè)圖形上點P(x,y)，在X軸和

9、Y軸方向分別移動Tx和Ty，結(jié)果生成新的點P(x,y),如圖所示，則有,y,x,P(x,y),Tx,Ty,其中TX,TY稱為點在X軸和Y軸上的位移。 用齊次坐標(biāo)和矩陣形式可表示為：,29,令二維平移變換矩陣為： 如果Tx 或Ty大于零，則點向右或向上移動； 如果Tx或Ty小于零，則點向左或向下移動。,1. 平移變換,30,2. 縮放變換,點的縮放是指將該點沿X軸和Y軸方向按比例縮小或放大。 設(shè)圖形上的點P(x,y)，在X軸和Y軸方向分別作Sx和Sy的縮放，結(jié)果生成新的點坐標(biāo)P(x,y)，如圖所示，則： 其中Sx，Sy稱為點在X軸和Y軸上的縮放比例。 用齊次坐標(biāo)和矩陣形式可表示為：,以坐標(biāo)原點為

10、放縮參照點，不僅改變了物體的大小和形狀，也改變了它離原點的距離。,當(dāng)|Sx|=|Sy|時，變換前的圖形與變換后的圖形相似。 當(dāng)|Sx|=|Sy|1時，圖形將放大，并遠(yuǎn)離坐標(biāo)原點； 當(dāng)|Sx|=|Sy|1時，圖形將縮小，并靠近坐標(biāo)原點； 當(dāng)|Sx|Sy|時，圖形將發(fā)生畸變。,令二維縮放變換矩陣為：,2. 縮放變換,32,點的旋轉(zhuǎn)變換是將點繞坐標(biāo)原點旋轉(zhuǎn)一角度的坐標(biāo)變換。,用齊次坐標(biāo)和矩陣形式可表示為,二維旋轉(zhuǎn)矩陣R2(),3. 旋轉(zhuǎn)變換,設(shè)有圖形上點P(x,y)，將其繞原點旋轉(zhuǎn)角度(逆時針旋轉(zhuǎn)為正)，結(jié)果生成的新的點坐標(biāo)P(x,y)。順時針時的變換矩陣？,33,4. 變形變換,變形變換是用來產(chǎn)生

11、一個目標(biāo)圖形的失真，也稱錯切變換?，F(xiàn)考慮y-變形和x-變形兩種： y-變形是將點P(x,y)變換到點P(x,y)，使x=xy=xshy+y(shy0) 其中shy為變形系數(shù)。,shy0， shy0，,錯切參數(shù)shy=tg ，表示y方向的錯切程度。,34,4. 變形變換,x-變形變換是指將點P(x,y)變換到點P(x,y)，應(yīng)有 x=x+yshx (shx0) y=y 其中shx為變形系數(shù)，shx的符號決定了圖形向右或向左變形。,shx0， shx0，,錯切變換引起圖形角度關(guān)系的改變，甚至導(dǎo)致圖形發(fā)生變形。,錯切參數(shù)shx=tg ，表示X方向的錯切程度。,35,5.對稱變換(反射變換),當(dāng)b=d

12、=0,a=-1,e=1時，(x y 1)=(-x y 1)： 與y軸對稱的反射變換。 當(dāng)b=d=0,a=1,e=-1時，(x y 1)=( x -y 1)： 與x軸對稱的反射變換。 當(dāng)b=d=0,a=e=-1時，(x y 1)=(-x -y 1)： 與原點對稱的反射變換。 當(dāng)b=d=1,a=e=0時，(x y 1)=(y x 1)： 與y=x對稱的反射變換。 當(dāng)b=d=-1,a=e=0時，(x y 1)=(-y -x 1)： 與y=-x對稱的反射變換。,36,6. 組合變換,如何實現(xiàn)復(fù)雜變換？ 實際上，一般的圖形變換更多的是組合變換，即由一系列基本的幾何變換組合而成。 則組合變換矩陣也可由一系

13、列基本幾何變換矩陣的乘積來表示。 矩陣的乘法滿足結(jié)合律，但不滿足交換律。 下面將舉例說明組合變換的方法。,37,6. 組合變換 例1,例:對一線段先放大2倍(即Sx=Sy=2)，再平移Tx=10，Ty=0。 解:設(shè)點(x,y)為線段上的任意一點，點(x,y)為點(x,y)放大后的坐標(biāo)，則：x,y,1T=S2(2,2)x,y,1T 設(shè)點(x,y)為點(x,y)經(jīng)平移后的坐標(biāo)，則：x,y,1T= T2(10,0) x,y,1T， 即：x,y,1T= T2(10,0) S2(2,2) x,y,1T,38,6. 組合變換 例1（續(xù)）,令： M即為組合變換矩陣。 設(shè)線段的兩端點坐標(biāo)為(x1,y1) 和(

14、x2,y2)，經(jīng)M變換后，得到新的坐標(biāo)(x1,y1)和(x2,y2)，連接這兩個新的坐標(biāo)點便生成了變換后的線段。,39,6. 組合變換 例2,例：對一圖形，繞平面上的一點(Cx,Cy) 作旋轉(zhuǎn)變換，旋轉(zhuǎn)角度為， 計算其變換矩陣。 解：旋轉(zhuǎn)變換是繞坐標(biāo)原點旋轉(zhuǎn)的，此處不能直接使用旋轉(zhuǎn)變換矩陣，應(yīng)先將點(Cx,Cy)平移至原點，然后作旋轉(zhuǎn)變換，最后再把該點移回原處。設(shè)點(x,y)為圖形中的點，點(x,y)為點(x,y)經(jīng)變換后的坐標(biāo)，則: x,y,1T = T2(Cx,Cy) R2()T2(-Cx,-Cy) x,y,1T 組合變換矩陣為：,40,6. 組合變換 例3,圖形關(guān)于任意的反射軸y =a

15、+bx 的反射(對稱)變換。,41,6. 組合變換 例3（續(xù)）,解： 1. 將坐標(biāo)原點平移到(0,a)處 2. 將反射軸（已平移后的直線）按順時針方向旋轉(zhuǎn)角，使之與x軸重合 3. 圖形關(guān)于x軸的反射變換 4. 將反射軸逆時針旋轉(zhuǎn)角 5. 恢復(fù)反射軸的原始位置 組合變換矩陣為：,42,6. 組合變換 例4,通用固定點縮放 平移物體使固定點與坐標(biāo)原點重合； 對于坐標(biāo)原點縮放； 用步驟1的反向平移將物體移回原始位置。,43,6. 組合變換 例5,通用定向縮放 比例變換中的比例因子Sx，Sy只能在x軸方向或y軸方向起作用。實際圖形變換中，不僅是在x，y方向變換，往往要求在任意方向進(jìn)行比例變換。通過旋轉(zhuǎn)

16、變換和比例變換的組合，可以實現(xiàn)任意方向的比例變換。,繞=450方向縮放,s1,s2,44,6. 組合變換 小結(jié),矩陣運算滿足結(jié)合律，但不滿足交換律。所以，一般情況下，不同順序的變換將得到不同的結(jié)果。,剛體變換。 直線段或多邊形的變換可通過每個頂點的變換，再在新位置重畫圖形得到。曲線的變換：變換矩陣乘以曲線的參數(shù)方程。,45,5.2.1 二維幾何變換 小結(jié),整體比例 變換,用規(guī)范化齊次坐標(biāo)表示的二維基本幾何變換矩陣是一個33的方陣：,46,5.2.1 二維幾何變換 小結(jié),上面討論的五種基本變換(平移、比例、旋轉(zhuǎn)、反射(對稱)和錯切)給出的都是點變換的公式，對于復(fù)雜對象(如線框模型)，圖形的變換實

17、際上都可以通過點變換來完成。 例如直線段的變換可以通過對兩個頂點坐標(biāo)進(jìn)行變換，連接新頂點得到變換后的新直線； 多邊形的變換可以通過對每個頂點進(jìn)行變換，連接新頂點得到變換后的新多邊形來實現(xiàn)。 曲線的變換可通過變換控制多邊形的控制點并重新畫線來完成。,47,5.2.1 二維幾何變換 小結(jié),符合下面形式的坐標(biāo)變換稱為二維仿射變換（Affine Transformation）。 變換后的坐標(biāo)x和y都是變換前的坐標(biāo)x和y的線性函數(shù)。參數(shù)aij是由變換類型確定的常數(shù)。 仿射變換具有平行線變換成平行線，有限點映射到有限點的一般特性。平移、比例、旋轉(zhuǎn)、反射(對稱)和錯切五種變換都是二維仿射變換的特例。 任何一

18、組二維仿射變換總可表示為這五種變換的組合。因此，平移、比例、旋轉(zhuǎn)、反射(對稱)的仿射變換保持變換前后兩直線間的角度、平行關(guān)系和長度之比不改變。,48,第5章 二維圖形變換及裁剪,5.1 變換的數(shù)學(xué)基礎(chǔ) 5.2 二維幾何變換 5.3 二維圖形裁剪,49,5.3 二維圖形裁剪,5.3.1 圖形學(xué)中常用的坐標(biāo)系 5.3.2 直線段的裁剪 5.3.3 多邊形的裁剪 5.3.4 字符的裁剪,50,裁剪：確定圖形中哪些部分落在裁剪窗口之內(nèi)，哪些落在裁剪窗口之外,以便只顯示落在裁剪窗口內(nèi)/外的那部分圖形。這個選擇過程稱為裁剪。 圖形裁剪算法，直接影響圖形系統(tǒng)的效率。,5.1 二維圖形的裁剪,51,Displ

19、ay Window,Window3,Window2,Window1,外裁剪在多窗口場合較常用。例如： Display Window：內(nèi)裁剪，針對Window13外裁剪； Window2：內(nèi)裁剪，針對Window1、3外裁剪； Window1、3：各自內(nèi)裁剪。,內(nèi)裁剪、外裁剪,52,第5章 二維光柵圖形的處理,5.1 二維圖形的裁剪 5.1.1 直線段的裁剪 5.1.2 多邊形的裁剪 5.1.3 字符的裁剪 5.2 走樣與反走樣,53,5.1.1 直線段的裁剪,1. 直接求交算法 2. Cohen-SutherLand算法(編碼法) 3. 中點分割算法 4. Nicholl-Lee-Nichol

20、l算法 5. Cyrus-Beck算法(參數(shù)法) 6. LiangBarskey算法 7. 凹多邊形窗口的裁剪,54,5.1.1 直線段的裁剪,任何圖形都可能包含點、直線、曲線、字符和多邊形等圖元， 但它們都可以分解成點的集合。 能否將直線段裁剪問題簡化為點的裁剪問題？ 假設(shè)窗口的左下角坐標(biāo)為(xL,yB ),右上角坐標(biāo)為(xR,yT )，對于給定點P(x,y),則P點在窗口內(nèi)的條件是要滿足下列不等式： xL = x = xRand yB = y = yT否則，P點就在窗口外。,問題：對于任意多邊形窗口，如何判別？ 點與多邊形的內(nèi)外關(guān)系判別。,55,5.1.1 直線段的裁剪,直線段裁剪是復(fù)雜圖

21、形裁剪的基礎(chǔ)。 直線段常見； 可構(gòu)成多邊形； 復(fù)雜的曲線可以通過直線段來逼近。 曲線裁剪可否化為直線段的裁剪？,56,5.1.1 直線段的裁剪,直線段與窗口的關(guān)系通常有以下三種情況： 整個線段全在窗口內(nèi)； 整個線段全在窗口外； 線段部分在窗口外，部分在窗口內(nèi)。 當(dāng)窗口為凸多邊形時，任何一條直線段只會至多有一段在窗口內(nèi)： 當(dāng)一條直線段的兩個端點全在窗口內(nèi)時，該直線段整個在窗口內(nèi)； 當(dāng)一條直線段的兩個端點，一個在窗口內(nèi)，一個在窗口外時，該直線段部分在窗口內(nèi)，部分在窗口外； 當(dāng)一條直線段的兩個端點全在窗口外時，該直線段可能整個在窗口外，也可能部分在窗口內(nèi)，部分在窗口外。,57,5.1.1 直線段的裁

22、剪,直線段裁剪：實質(zhì)上就是快速判斷出線段與裁剪窗口的關(guān)系； (1)線段完全可見； (2)顯然不可見； (3)其它。 然后對于可見部分，求出端點，繪制線段。 為提高效率： 快速判斷情形(1)、(2)； 對于情形(3)，應(yīng)設(shè)法快速求出線段和裁剪窗口的交點。,58,1. 直接求交算法,如何判斷線段是否顯然不可見？ 直線與窗口邊如何求交？,59,1. 直接求交算法,直線段與窗口邊如何求交？兩線段求交 參數(shù)式、非參數(shù)式 設(shè)直線過P1(x1,y1)，P2(x2,y2)，m為斜率，則：,直線與窗口各邊的交點為： L，xL，y=m(xL-x1)+y1，m R，xR，y=m(xR-x1)+y1，m 用斜率解釋

23、Y, yT，x=x1+(1/m)(yT-y1)，m0 B，yB，x=x1+(1/m)(yB-y1)，m0 總會求出一個交點，即使交點位于窗口外。,60,1. 直接求交算法,解方程組求出交點參數(shù) tl、te0,1,61,2. Cohen-SutherLand算法,這是一個最早最流行的線段裁剪算法。自1968年以來被公認(rèn)為是一個好的算法也稱編碼算法。 該算法通過初始測試來減少要計算的交點數(shù)目從而加快線段裁剪算法的速度。 基本思想： 對于每條線段P1P2分為三種情況處理: （1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2 。 （2）若P1P2明顯在窗口外，則丟棄該線段。 （3）若線段不滿足（1）或

24、（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。 遞歸的裁剪過程,62,2. Cohen-SutherLand算法,為快速判斷，采用如下編碼方法： 由窗口四條邊所在直線把二維平面分成9個區(qū)域，每個區(qū)域賦予一個四位編碼： CtCbCrCl（上下右左）； 直線的端點都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來標(biāo)識出端點相對于裁剪窗口邊界的位置。 各位編碼含義，端點坐標(biāo)(x,y)： 上：if yyT, Ct=1, else, 0; 下：if yxR, Cr=1, else, 0; 左：if xxL, Cl=1, else, 0;,63,2. Cohen-Sut

25、herLand算法,任何位賦值為1，代表端點落在相應(yīng)的位置上，否則該位為0。 例如：端點B：區(qū)域碼為 0000； 端點A：區(qū)域碼為 1001；,64,2. Cohen-SutherLand算法原理,編碼將窗口及其鄰域分為5個區(qū)域： 內(nèi)域：區(qū)域(0000)。 上域：區(qū)域(1001, 1000, 1010)。 下域：區(qū)域(0101, 0100, 0110)。 右域：區(qū)域(1010, 0010, 0110)。 左域：區(qū)域(1001, 0001, 0101)。 對線段的兩個端點的區(qū)號進(jìn)行“位與”運算，可知這兩個端點是否同在窗口的同一側(cè)(上、下、左、右)； 如果兩端點的編碼均為0000，表示直線在窗口內(nèi)

26、。 如果兩端點的編碼相與不為0000，表示直線在窗口外。 如果兩端點的編碼不全為0000，但相與為0000，則該直線可能部分可見，需計算直線段與窗口的交點，確定哪一部分可見。,65,2. Cohen-SutherLand算法原理,若code1=0，且code2=0，則P1P2完全在窗口內(nèi)，“取”； 若code1 /*done: 完成；draw: 可見；*/Unsigned char code1,code2； /*端點1，端點2的編碼*/ While (!done) if (判斷code1,code2,若為第一種情況) done = TRUE; draw = TRUE; else if (為第二

27、種情況) done = TRUE; draw = FALSE; else if (檢查code1 ,若在窗口內(nèi)) 交換端點及端點的編碼；以左，右，下，上的次序?qū)Χ它c1進(jìn)行判斷及求交；將交點的值賦給端點1 /*End of while*/,69,2. Cohen-SutherLand算法小結(jié),最壞情形，線段求交四次。（左、右、下、上）,P1（0101）,P2（1010）,70,2. Cohen-SutherLand算法小結(jié),本算法的優(yōu)點在于簡單，易于實現(xiàn)。 用編碼方法來快速判斷線段和裁剪窗口的關(guān)系。 他也可以簡單的描述為將直線段在窗口外的部分刪去(按左、右、下、上的順序依次進(jìn)行)，剩余部分就是可

28、見部分。 在這個算法中求交點是很重要的，他決定了算法的速度。 尤其適用于大窗口場合及小窗口場合。 大部分線段完全可見或完全不可見。 本算法對于其他形狀的窗口是否同樣有效就值得討論了。這也說明了在圖形算法中，沒有幾個是對大多數(shù)情況有效的。,71,3. 中點分割算法,基本思想：從P0點出發(fā)找出離P0最近的可見點，從P1點出發(fā)找出離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。 可看作Cohen-Sutherland算法一個硬件實現(xiàn)的特例。,A,B,72,3. 中點分割算法,與Cohen-Sutherland算法一樣，首先對線段端點進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況： (1)線段

29、完全可見； (2)顯然不可見； (3)其它 對前兩種情況，進(jìn)行一樣 的處理； 對于第三種情況， 用中點分割的方法求出線 段與窗口的交點。（A、B分別為距P0 、 P1最近的可見點，Pm為P0P1中點）,73,3. 中點分割算法,求距離P0最近可見點P,74,3. 中點分割算法,中點分割法：從P0出發(fā)找距離P0最近可見點： 先求出P0P1的中點Pm, 若P0Pm不是顯然不可見的，并且P0Pm在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，所以用P0Pm代替P0P1； 否則取PmP1代替P0P1。 再對新的P0P1求中點Pm。重復(fù)上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時P

30、m收斂于交點。 從P1出發(fā)找距離P1最近可見點的方法類似。,75,3. 中點分割算法小結(jié),與Cohen-Sutherlang算法在思想上沒有任何區(qū)別。 采用編碼的方法快速判斷直線段與裁剪窗口的關(guān)系。 區(qū)別在于兩者求與裁剪窗口交點的方法不同。 中點分割算法：二分查找 Cohen-Sutherlang算法：直接計算 更利于硬件實現(xiàn)，可看作C-S算法的一個特例。,76,從P0 出發(fā)找最近可見點的方法: 先求出P0 P1 的中點Pm 若P0 Pm 不是顯然不可見的，并且P0 Pm 在窗口有 可見部分，則距P0 最近的可見點一定落在P0 Pm 上，所以用P0 Pm 代替P0 P1； 否則取PmP1 代替

31、P0 P1 再對新的P0 P1 求中點Pm 。重復(fù)上述過程，直到長度小 于給定的控制常數(shù)為止，此時Pm 收斂于交點。 從p1出發(fā)找最近可見點采用上面類似方法。,中點分割法,可取為1個象素,77,5. Cyrus-Beck算法,前述算法均假設(shè)裁剪窗口為一規(guī)則的矩形窗口。 若裁剪窗口為非規(guī)則矩形的任意凸多邊形時，以上算法不再完全適用。,78,5. Cyrus-Beck算法,考慮直線段的參數(shù)方程：,直線上任一點的參數(shù)t為：,79,5. Cyrus-Beck算法,裁剪線段P1P2：tL=1/6；tR=5/6 tB=-1/5；tT=7/5 部分t0,1。,0,裁剪線段P3P4： tL=3/8；tR=7/

32、8 tB=0；tT=2/3 所有的t0,1。,部分可見線段：,可否簡單利用交點的t值進(jìn)行判斷？,80,5. Cyrus-Beck算法,裁剪線段P1P2： tL=-1/2；tR=3/2 tB=3/2；tT=-1/2 不是所有的t 0,1 。,0,裁剪線段P3P4： tL=-5；tR=-4 tB=-1/2；tT=3/2 不是所有的t 0,1。,完全可見及完全不可見線段：,可見，不能簡單的利用交點的t值來進(jìn)行裁剪。必須找到一個可靠的方法，用來判定線段上的一點是位于窗口之內(nèi)、之外或邊界上。,81,5. Cyrus-Beck算法原理,下限： 上限： D=P2P1,82,5. Cyrus-Beck算法,C

33、yrus-Beck算法的基本思想是采用法矢量的概念來判定線段上的一點是在窗口之內(nèi)，之外，還是在窗口的邊界上。 對任意凸多邊形，其邊界上任一點a處的內(nèi)法矢量ni滿足： ni(ba)0其中： b為多邊形邊界上另外一點。 ni為過a點邊界的內(nèi)法矢量； no為外法矢量。,V1V2=|V1| |V2| cos,83,如果f是凸區(qū)域邊界上的一點，n是凸區(qū)域邊界在f點的內(nèi)法向量，則對于線段P1P2 上的一點P(t)，滿足下式： 若nP(t)f0，則表示P(t)f指向區(qū)域的外部(相對當(dāng)前邊)； 若nP(t)f=0，則表示P(t)f與包含f的邊界重合且與內(nèi)法矢量n垂直； 若nP(t)f0，則表示P(t)f指向區(qū)

34、域的內(nèi)部(相對當(dāng)前邊) 。 由此可知，P(t)滿足nP(t)f=0的t值的點即為直線與邊界的交點。,nP(t)f0,5. Cyrus-Beck算法原理,84,Cyrus-Beck算法中對于線段的可見性是這樣判斷的： 設(shè)：內(nèi)法矢量ni與連接線段上一點P(t)至邊界上一點fi的矢量的點積為： ni P(t)-fi，(i=1,2,3.) 與式子P(t)=P1 +(P2P1)t，(0t1) 合并得： ni P1+(P2P1)t - fi，(i=1,2,3.) 則線段上一點在邊界上的條件為： ni P1 +(P2P1)t-fi=0 (i=1,2,3.),nP(t)f0,nP(t)f=0,nP(t)f0,

35、fi,5. Cyrus-Beck算法原理,85,線段上點在邊界上的條件為： ni P1 +(P2P1)t - fi=0 (i=1,2,3.) 令：D=P2P1；wi=P1fi，可得交點： 如果D ni=0，則 要么D垂直于ni， 要么P2=P1，線段退化為一點： 如果wini0，表示點位于區(qū)域和窗口之外； 如果wini0，表示點位于區(qū)域和窗口邊界上； 如果wini0，表示點位于區(qū)域和窗口之內(nèi)。,5. Cyrus-Beck算法原理,nP(t)f0,nP(t)f=0,nP(t)f0,fi,式5.1.11,86,否則，可根據(jù)“式5.1.11”求出線段和裁剪窗口的交點。對于交點的t值選擇： 首先，要符

36、合0t1； 其次，對于凸窗口來說，每一個線段與其至多有兩個交點（既有兩個相應(yīng)的t值）。所以我們可以把計算出的t值分成兩組：一組為下限組，是分布在線段起點一側(cè)的；一組為上限組，是分布在線段終點一側(cè)的。 這樣，只要找出下限組中的最大值及上限組中的最小值，就可確定可見線段部分了。 有了這些，整個算法就可以建立了。 分組的依據(jù)？,5. Cyrus-Beck算法原理,87,5. Cyrus-Beck算法原理,下限： 上限： D=P2P1,下限組以D ni0 為特征，表示在該處沿 P1P2方向前進(jìn)將接近或 進(jìn)入多邊形內(nèi)側(cè)。,上限組以D ni0為特征，表示在該處沿P1P2方向前進(jìn)將越來越遠(yuǎn)地離開多邊形區(qū)域。

37、,88,置下限最小值 tL=0；上限最大值 tU=1 while 對于每一個窗口邊i do begin if Dni=0 then If wini0 then /*尋找下限組的tL值*/ If t 0 then tL=max(t,tL) else /*尋找上限組的tU值*/ if t 1 then tU=min(t,tU) end if tL tU then 畫從P(tL)至P(tU)的線段 end of algorithm,5. Cyrus-Beck算法算法描述,89,該算法比Cohen-Sutherland等算法適用的范圍更廣一些，它可以對任何凸多邊形適用，但對于凹多邊形就失效了。為了解決

38、這個問題，又引入對凹多邊形進(jìn)行判斷和分割的算法：叉積法，旋轉(zhuǎn)法。 當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時，該算法退化為Liang-Barsky算法。,5. Cyrus-Beck算法小結(jié),90,6. Liang-Barsky算法,寫入圖形學(xué)教科書的中國人的算法。 設(shè)要裁剪的線段是P1P2。P1P2和窗口邊界交于A,B,C,D四點，見圖。,算法的基本思想是從A,B和P1三點中找出最靠近P2的點，圖中要找的點是P1。從C,D和P2中找出最靠近P1的點。圖中要找的點是C點。那么P1C就是P1P2線段上的可見部分。,本質(zhì)上，可看作是一種特殊形式的Cyrus-Beck算法。,91,6. Liang-

39、Barsky算法,線段的參數(shù)表示： x=x1 + tx y=y1 + ty 0t 1, x = x2-x1, y=y2-y1 窗口邊界的四條邊分為兩類：始邊和終邊。,92,求出P1P2與兩條始邊的交點參數(shù)t1、 t2 ，令tL=max(t1 ,t2,0)，則tL即為三者中離p2最近的點的參數(shù)； 求出p1p2與兩條終邊的交點參數(shù)t3、 t4，令tU=min(t3,t4,1) ，則tU即為三者中離p1最近的點的參數(shù)； 若tU tL,則可見線段區(qū)間為tL , tU；否則，p1p2完全不可見，如： p1p2，tL=t2 , tU=t3, tUtL,6. Liang-Barsky算法,93,6. Lia

40、ng-Barsky算法,裁剪區(qū)域的內(nèi)部可表示為： xLxxR ，yByyT 直線段的參數(shù)表示為： x=x1+tx，y=y1+ty， 0t1,x=x2-x1 ,y=y2-y1 ； 若直線段上一點位于窗口內(nèi)，則：,xL x1+tx xR and yB y1+ty yT ； 即：-txx1-xL , txxR-x1 ；-tyy1-yB , tyyT-x1 ； 記為： tiDi / Qi ，i=L,R,B,T QL= - xQR= x QB= - y QT= y DL= x1-xLDR= xR-x1DB= y1-yB DT= yT-y1,94,6. Liang-Barsky算法,xL x1+tx xR

41、 and yB y1+ty yT ； 交點計算： QL= - x DL= x1-xL QR= x DR= xR-x1 QB= - y DB= y1-yB QT= y DT= yT-y1 交點為：ti= Di / Qi ,i=L,R,B,T 如果Qi 0 ，則ti為與終邊交點參數(shù),95,6. Liang-Barsky算法,有Qi =0的情況時(線段與窗口邊平行)： 若有任意一個i , (i=L,R,B,T) 使得Di 0和QR=0，DR0。這時由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交點，而讓EF和y=yT及y=yB的交點決定直線段上的可見部分。,QL= -x D

42、L= x1-xL QR= x DR= xR-x1 QB= -y DB= y1-yB QT= y DT= yT-y1,96,6. Liang-Barsky算法,對于每條直線，可以計算出參數(shù)tL和tU，它們定義了在裁剪矩形內(nèi)的線段部分： tL的值由線段從外到內(nèi)遇到的矩形邊界(始邊：Qi 0 )所決定；對這些邊界計算ti= Di / Qi；tU取1和各個ti值之中的最小值。 如果tL tU ，則線段完全落在裁剪窗口之外，被舍棄。 否則裁剪線段為tL,tU。,97,6. Liang-Barsky算法小結(jié),一種特殊形式的Cyrus-Beck算法； Cohen-Sutherland與中點法在區(qū)域碼測試階段

43、能以位運算方式高效率地進(jìn)行，因而當(dāng)大多數(shù)線段能夠簡單的取舍時，效率較好； 梁友棟Barskey算法只能應(yīng)用于矩形窗口的情形，通常其效率比前兩者要高，這是因為運算僅到必要時才進(jìn)行求交計算。 兩者都可推廣到三維空間。,98,7. 凹多邊形窗口的裁剪,上述算法都假定裁剪窗口為凸多邊形，對于凹多邊形窗口，線段如何裁剪？ 如何判斷凸、凹多邊形？ 將凹多邊形分割為凸多邊形，利用已有算法進(jìn)行裁剪。,99,矢量叉積定義如下： 2個互不平行的矢量，其叉積形成一個與2個矢量都垂直的新的矢量，它的方向符合右手判別法 | v1v2 |=|v1|*|v2|*Sin 如果v1平行于v2，則 v1v2=(0,0,0),7.

44、 凹多邊形窗口的裁剪,100,如果各叉積全部為零，則多邊形各邊共線； 如果各叉積一部分為正，一部分為負(fù)，則多邊形為凹多邊形； 如果所有叉積全部大于零或等于零，則多邊形為凸多邊形。此時沿著邊的正向，內(nèi)法矢量指向其左側(cè)； 如果所有叉積全部小于零或等于零，則多邊形為凸多邊形，此時沿著邊的正向，內(nèi)法矢量指向其右側(cè)。,凸多邊形,凹多邊形,+,+,+,+,+,+,+,+,-,7. 凹多邊形窗口的裁剪,凸多邊形判定叉積法,101,第5章 二維光柵圖形的處理,5.1 二維圖形的裁剪 5.1.1 直線段的裁剪 5.1.2 多邊形的裁剪 5.1.3 字符的裁剪 5.2 走樣與反走樣,102,多邊形的裁剪可分解為一

45、條一條線段進(jìn)行嗎？ 分解為線段裁剪后多邊形不再封閉，無法填充，需要用窗口邊界的適當(dāng)部分來關(guān)閉它。 一個凹多邊形可能被裁剪成幾個小的多邊形，因而需要決定這些小多邊形的邊界。,5.1.2 多邊形的裁剪,103,5.1.2 多邊形的裁剪,1. Sutherland-Hodgman算法,104,通過對單一邊的裁剪來實現(xiàn)多邊形的裁剪。 分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。 流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。 亦稱逐邊裁剪算法。,1. Sutherland-Hodgema算法原理,105,流水線：(左上右下)前邊的結(jié)果是后邊的輸入。 算法的每一次輸

46、出（包括中間結(jié)果）都是一個多邊形的頂點表(逆時針排列)， 且所有頂點均位于相應(yīng)窗口裁剪邊的可見一側(cè)。 由于多邊形的每一條邊需要與裁剪邊分別進(jìn)行比較，因此只需要討論單條邊和單個裁剪邊之間可能的位置關(guān)系。,1. Sutherland-Hodgema算法原理,106,窗口邊界所在直線將平面分為兩部分：可見一側(cè)、不可見一側(cè)。 假設(shè)S,P為多邊形的兩個相鄰頂點：S為該邊的起點，P為該邊的終點。則SP與裁剪邊之間只有4種可能的關(guān)系。,1. Sutherland-Hodgema算法原理,107,由上可見，每一次將多邊形的一條邊與裁剪邊或面比較后，輸出一個或兩個頂點，也可能無輸出點： 如果SP邊完全可見，則輸

47、出P點，不必輸出起點S，因為頂點是按順序處理的，S是作為前一邊的終點輸出的； 如果SP邊完全不可見，則無輸出；,1. Sutherland-Hodgema算法原理,108,如果SP邊部分可見，則SP邊可能進(jìn)入或離開裁剪邊或面的可見一側(cè)。 如果SP邊離開裁剪邊或面的可見一側(cè)，則輸出SP與裁剪邊或面交點。 如果SP邊進(jìn)入裁剪邊或面的可見一側(cè)，則輸出兩點，一個為SP與裁剪邊或面的交點，一個是P點。,1. Sutherland-Hodgema算法原理,109,對于多邊形的第一個頂點，只需判斷其可見性。如果可見，則輸出且作為起點S；否則無輸出，但還是要作為S保存，以便后續(xù)點處理。 對于最后一條邊PnP1

48、，其處理方法是：標(biāo)志第一頂點為F，這樣最后一條邊則為PnF，可與其他邊作相同的處理。,1. Sutherland-Hodgema算法原理,110,while 對于每一個窗口邊或面 do begin if P1在窗口邊的可見一側(cè) then 輸出P1 for i=1 到 n do begin if Pi在窗口邊的可見一側(cè) then if Pi+1在窗口邊的可見一側(cè) then 輸出Pi+1 else 計算交點并輸出交點 else if Pi不在可見一側(cè)， Pi+1在可見一側(cè)， then 計算交點并輸出交點，同時輸出Pi+1 endend end of algorithm,1. Sutherland-

49、Hodgema算法描述,111,實現(xiàn)方法： 設(shè)置二個表 輸入頂點表：用于存放被裁剪多邊形的頂點p1-pm。 輸出頂點表：用于存放裁剪過程中及結(jié)果的頂點q1-qn。 頂點表中各頂點要求按一定順序排列，一般采用逆時針方向。 相對于裁剪窗口的各條邊界，逐邊進(jìn)行裁剪。 點的可見性判斷 交點的計算,1. Sutherland-Hodgema算法示例,112,輸入頂點表：p1p2p3 輸出頂點表：空 左：q1p2p3q2（逆時針方向） 上：q1p2p3q2 右：q1p2p3q2 下：q3p3q2q4,1. Sutherland-Hodgema算法示例,113,對凸多邊形應(yīng)用本算法可以得到正確的結(jié)果，但是對

50、凹多邊形的裁剪將如圖所示顯示出一條多余的直線。 這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現(xiàn)。因為只有一個輸出頂點表。 解決這個問題有多種方法 一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。 二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。,1. Sutherland-Hodgema算法小結(jié),114,第5章 二維光柵圖形的處理,5.1 二維圖形的裁剪 5.1.1 直線段的裁剪 5.1.2 多邊形的裁剪 5.1.3 字符的裁剪 5.2 幾何變換 5.3 二維圖形的顯示流程 5.4 走樣與反走樣,115,Stroke,文本是由字符組成的。一般地，字符可分為兩種：一種是矢量字符，即由若干個線段或筆畫構(gòu)成；一種是點陣字符，即由點陣來表示。所以文本的裁剪與多邊形的裁剪相類似，它按裁剪的精度可分為筆畫裁剪、字符裁剪、和字符串裁剪等三種類型。 筆畫裁剪是指在顯示文本時，把窗口以外的字符予以裁剪，并且對與窗口相交的字符，也把其在窗口以外的部分予以裁剪。若是矢量字符，可以按直線的裁剪方法來裁剪與窗口相交的字符。若是點陣字符，則可按點