裁剪和幾何變換

1、第第4章章 裁剪與幾何變換裁剪與幾何變換第第4章章 幾何變換幾何變換 窗口到視區(qū)的變換窗口到視區(qū)的變換 裁剪（線段、字符串、多邊形）裁剪（線段、字符串、多邊形） 齊次坐標(biāo)表示與二維幾何變換齊次坐標(biāo)表示與二維幾何變換 組合變換組合變換 三維幾何變換三維幾何變換4.1 窗口到視區(qū)的變換一、用戶域和窗口區(qū)一、用戶域和窗口區(qū)1 .1 .用戶域：程序員用來定義草圖的整個(gè)自然空間用戶域：程序員用來定義草圖的整個(gè)自然空間( (WDWD) ) 人們所要描述的圖形均在用戶域中定義。人們所要描述的圖形均在用戶域中定義。 用戶域是一個(gè)實(shí)數(shù)域，理論上是連續(xù)無限的。用戶域是一個(gè)實(shí)數(shù)域，理論上是連續(xù)無限的。2.2.窗口區(qū)

2、：用戶指定的任一區(qū)域窗口區(qū)：用戶指定的任一區(qū)域( (W W) ) 窗口區(qū)窗口區(qū)W W小于或等于用戶域小于或等于用戶域WDWD 小于用戶域的窗口區(qū)小于用戶域的窗口區(qū)W W叫做用戶域的子域。叫做用戶域的子域。 窗口可以有多種類型，矩形窗口、圓形窗口、多邊形窗口等等窗口可以有多種類型，矩形窗口、圓形窗口、多邊形窗口等等 窗口可以嵌套，即在第一層窗口中可再定義第二層窗口，在第窗口可以嵌套，即在第一層窗口中可再定義第二層窗口，在第I I層窗層窗口中可再定義第口中可再定義第I+1I+1層窗口等等。層窗口等等。 4.1窗口到視區(qū)的變換二、屏幕域和視圖區(qū)二、屏幕域和視圖區(qū)1.屏幕域屏幕域(DC)： 設(shè)備輸出圖

3、形的最大區(qū)域，是有限的整數(shù)域。如圖形顯示器設(shè)備輸出圖形的最大區(qū)域，是有限的整數(shù)域。如圖形顯示器分辨率為分辨率為10241024 768768DCDC0.10230.1023 0.7670.7672.視圖區(qū)視圖區(qū)：任何小于或等于屏幕域的區(qū)域任何小于或等于屏幕域的區(qū)域 視圖區(qū)用設(shè)備坐標(biāo)定義在屏幕域中視圖區(qū)用設(shè)備坐標(biāo)定義在屏幕域中 窗口區(qū)顯示在視圖區(qū)，需做窗口區(qū)到視圖區(qū)的坐標(biāo)轉(zhuǎn)換。窗口區(qū)顯示在視圖區(qū)，需做窗口區(qū)到視圖區(qū)的坐標(biāo)轉(zhuǎn)換。 視圖區(qū)可以有多種類型：圓形、矩形、多邊形等。視圖區(qū)可以有多種類型：圓形、矩形、多邊形等。 視圖區(qū)也可以嵌套。視圖區(qū)也可以嵌套。 4.1 窗口到視區(qū)的變換窗口區(qū)和視圖區(qū)的坐

4、標(biāo)變換窗口區(qū)和視圖區(qū)的坐標(biāo)變換設(shè)窗口的四條邊界設(shè)窗口的四條邊界WXLWXL, ,WXRWXR, ,WYBWYB, ,WYTWYT視圖的四條邊界視圖的四條邊界VXLVXL, ,VXRVXR, ,VYBVYB, ,VYTVYT則用戶坐標(biāo)系下的點(diǎn)（即窗口內(nèi)的一點(diǎn)）則用戶坐標(biāo)系下的點(diǎn)（即窗口內(nèi)的一點(diǎn)）( (XwXw, ,YwYw) )對應(yīng)屏幕視圖區(qū)中對應(yīng)屏幕視圖區(qū)中的點(diǎn)（的點(diǎn)（XsXs, ,YsYs），其變換公式為），其變換公式為VYBWYBYWYBWYTVYBVYTYVXLWXLXWXLWXRVXLVXRXwsws4.1 窗口到視區(qū)的變換l簡化為：式) 1 (dYcYbXaXwsws三、窗口區(qū)和視圖

5、區(qū)的坐標(biāo)變換三、窗口區(qū)和視圖區(qū)的坐標(biāo)變換如令a（VXR-VXL）/(WXR-WXL)bVXL-WXL（VXR-VXL）/(WXR-WXL)c=(VYT-VYB)/(WYT-WYB)dVYB-WYB (VYT-VYB)/(WYT-WYB)4.1 窗口到視區(qū)的變換l簡化為：l1) 當(dāng)當(dāng)a c時(shí)，即時(shí)，即x 方向的變化與方向的變化與y方向的變化不同時(shí)，視圖中的圖方向的變化不同時(shí)，視圖中的圖形會(huì)有伸縮變化，圖形變形。形會(huì)有伸縮變化，圖形變形。l2) 當(dāng)當(dāng)a=c=1，b=d=0,且窗口與視圖區(qū)的坐標(biāo)原點(diǎn)也相同，則在視且窗口與視圖區(qū)的坐標(biāo)原點(diǎn)也相同，則在視圖區(qū)產(chǎn)生與窗口區(qū)相同的圖形。圖區(qū)產(chǎn)生與窗口區(qū)相同的

6、圖形。式) 1 (dYcYbXaXwsws三、窗口區(qū)和視圖區(qū)的坐標(biāo)變換三、窗口區(qū)和視圖區(qū)的坐標(biāo)變換n識別圖形在指定區(qū)域內(nèi)和區(qū)域外的部分的過程稱為裁剪算法，簡稱裁剪（識別圖形在指定區(qū)域內(nèi)和區(qū)域外的部分的過程稱為裁剪算法，簡稱裁剪（clipping）n二維窗口是投影平面上的一個(gè)矩形。一般來說，這個(gè)矩形的邊和投影平面二維窗口是投影平面上的一個(gè)矩形。一般來說，這個(gè)矩形的邊和投影平面上的坐標(biāo)軸平行，圖形在窗口內(nèi)的部分被顯示出來，窗口外的部分被裁剪上的坐標(biāo)軸平行，圖形在窗口內(nèi)的部分被顯示出來，窗口外的部分被裁剪掉了。平面上的圖形受該矩形的裁剪稱為二維裁剪。掉了。平面上的圖形受該矩形的裁剪稱為二維裁剪。4.

7、2 二維裁剪二維裁剪裁剪的應(yīng)用n從定義的場景中抽取用于觀察的部分從定義的場景中抽取用于觀察的部分n在三維視圖中識別出可見面在三維視圖中識別出可見面n防止線段或?qū)ο蟮倪吔缁煜乐咕€段或?qū)ο蟮倪吔缁煜齨用實(shí)體造型來創(chuàng)建對象用實(shí)體造型來創(chuàng)建對象n顯示多窗口的環(huán)境顯示多窗口的環(huán)境n允許選擇圖形的一部分來進(jìn)行拷貝、移動(dòng)或允許選擇圖形的一部分來進(jìn)行拷貝、移動(dòng)或刪除等繪圖操作刪除等繪圖操作裁剪算法類型n圖形裁剪與窗口圖形裁剪與窗口視圖變換的先后視圖變換的先后n窗口邊界裁剪窗口邊界裁剪n視區(qū)邊界裁剪視區(qū)邊界裁剪n圖形生成與裁剪先后圖形生成與裁剪先后n先生成后裁剪先生成后裁剪n先裁剪后生成先裁剪后生成2021-

8、9-2311點(diǎn)的裁剪點(diǎn)的裁剪 圖形裁剪中的最基本的問題。圖形裁剪中的最基本的問題。 假設(shè)裁剪窗口為一個(gè)在標(biāo)準(zhǔn)位置的矩形，即邊與坐標(biāo)軸平行的假設(shè)裁剪窗口為一個(gè)在標(biāo)準(zhǔn)位置的矩形，即邊與坐標(biāo)軸平行的矩形，由上（矩形，由上（y=ymin）、下（）、下（y=ymax）、左（）、左（x=xmin）、右）、右（x=xmax）四條邊描述。）四條邊描述。 點(diǎn)點(diǎn)(x, y)在窗口內(nèi)的充分必要條件是：在窗口內(nèi)的充分必要條件是： 裁剪窗口（裁剪窗口（Xmin，Xmax，Ymin，Ymax）是世界坐標(biāo)系的窗口邊界或視區(qū)邊界是世界坐標(biāo)系的窗口邊界或視區(qū)邊界 應(yīng)用舉例應(yīng)用舉例爆炸場景或海面泡沫的顯示爆炸場景或海面泡沫的顯示

9、 問題：對于任何多邊形窗口，如何判別？問題：對于任何多邊形窗口，如何判別？maxminxxx maxminyyy (xmin,ymin )(xmax,ymax ) 直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。 裁剪的目的裁剪的目的判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分 裁剪處理的基礎(chǔ)裁剪處理的基礎(chǔ) 圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元關(guān)于窗口內(nèi)外關(guān)系的判別 圖元

10、與窗口的求交圖元與窗口的求交 假定條件假定條件 矩形裁剪窗口：矩形裁剪窗口：xmin,xmaxXymin,ymax 待裁剪線段：待裁剪線段：2021-9-2312直線段裁剪直線段裁剪),(),(111000yxPyxP2021-9-2313直線段裁剪直線段裁剪待裁剪線段和窗口的關(guān)系待裁剪線段和窗口的關(guān)系 （1）完全落在窗口內(nèi)，線段完全可見）完全落在窗口內(nèi)，線段完全可見（2）完全落在窗口外，顯然不可見）完全落在窗口外，顯然不可見 （3）與窗口邊界相交，線段至少有一端點(diǎn)在窗口之外，但非）與窗口邊界相交，線段至少有一端點(diǎn)在窗口之外，但非顯然不可見顯然不可見 要確定一條直線段上位于窗口內(nèi)的可見段，要確

11、定一條直線段上位于窗口內(nèi)的可見段，只須求出它的兩個(gè)位于窗口內(nèi)的可見端點(diǎn)即可。只須求出它的兩個(gè)位于窗口內(nèi)的可見端點(diǎn)即可。算法的基本思想算法的基本思想把所有的直線按照它和窗口的關(guān)系分類，不把所有的直線按照它和窗口的關(guān)系分類，不同的直線使用不同的處理方法確定其可見部分。同的直線使用不同的處理方法確定其可見部分。2021-9-23142021-9-2315為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：(一）快速判斷情形一）快速判斷情形(1)(2)；(二二) 設(shè)法減少情形設(shè)法減少情形(3)求交次數(shù)和每次求交時(shí)所需的計(jì)求交次數(shù)和每次求交時(shí)所需的計(jì)算量。算量。直線裁剪算法的主要步驟：直線裁剪算

12、法的主要步驟：首先將不需要裁剪的直線挑出，并刪去其中在窗外的首先將不需要裁剪的直線挑出，并刪去其中在窗外的直線；直線；其次，對其余直線，逐條與窗框求交點(diǎn)，并將窗外部其次，對其余直線，逐條與窗框求交點(diǎn)，并將窗外部分刪去分刪去2021-9-2316實(shí)交點(diǎn)實(shí)交點(diǎn)是直線段與窗口矩形邊界的交點(diǎn)。是直線段與窗口矩形邊界的交點(diǎn)。虛交點(diǎn)虛交點(diǎn)則是直線段與窗口矩形邊界延長線或直線則是直線段與窗口矩形邊界延長線或直線段的延長線與窗口矩形邊界的交點(diǎn)。段的延長線與窗口矩形邊界的交點(diǎn)。 窗口圖6-25 實(shí)交點(diǎn)與虛交點(diǎn)ABCDEFHGIJ虛交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)虛交點(diǎn)虛交點(diǎn)2021-9-2317直接求交算法直接求交算法直

13、線與窗口邊直線與窗口邊都寫成參數(shù)形都寫成參數(shù)形式，求參數(shù)值。式，求參數(shù)值。2021-9-2318矢量裁剪法矢量裁剪法算法思想算法思想先從線段的一個(gè)端點(diǎn)出發(fā)進(jìn)行判斷或進(jìn)行求交運(yùn)算，所得交先從線段的一個(gè)端點(diǎn)出發(fā)進(jìn)行判斷或進(jìn)行求交運(yùn)算，所得交點(diǎn)坐標(biāo)保存在（點(diǎn)坐標(biāo)保存在（xs，ys）中，然后再從線段的另一個(gè)端點(diǎn)）中，然后再從線段的另一個(gè)端點(diǎn)出發(fā)用前面的判斷及其求交運(yùn)算求得交點(diǎn)坐標(biāo)（出發(fā)用前面的判斷及其求交運(yùn)算求得交點(diǎn)坐標(biāo)（x，y），），最后只輸出兩個(gè)交點(diǎn)間的線段。最后只輸出兩個(gè)交點(diǎn)間的線段。用窗口的四條邊界的直線將窗口分為用窗口的四條邊界的直線將窗口分為9個(gè)區(qū)。個(gè)區(qū)。012345678(x2,y2)y

14、bytxlxr(x1,y1)2021-9-2319排斥性測試排斥性測試若線段滿足下述四個(gè)條件之一時(shí)：若線段滿足下述四個(gè)條件之一時(shí)：max(x1,x2)xlmin(x1,x2)xrmax(y1,y2)ybmin(y1,y2)yt則線段必定位于窗口之外，無輸出線段。則線段必定位于窗口之外，無輸出線段。包含性測試包含性測試 若線段滿足：若線段滿足：xlx1 xr, yby1 yt,則線段的始點(diǎn)在則線段的始點(diǎn)在0區(qū)，也即線段可見段的起點(diǎn)為：區(qū)，也即線段可見段的起點(diǎn)為： xs = x1 , ys= y12021-9-2320求交點(diǎn)，并判斷求交點(diǎn)，并判斷I. 若若x1xl,則：則：線段的起點(diǎn)坐標(biāo)可能線段的

15、起點(diǎn)坐標(biāo)可能位于位于3區(qū)、區(qū)、4區(qū)、區(qū)、5區(qū)。區(qū)。而新起點(diǎn)的坐標(biāo)可能在而新起點(diǎn)的坐標(biāo)可能在直線直線y= yb和線段的交點(diǎn)上和線段的交點(diǎn)上直線直線y= yt和線段的交點(diǎn)上和線段的交點(diǎn)上直線直線x= xl和線段的交點(diǎn)上和線段的交點(diǎn)上012345678(x1,y1)(x2,y2)ybytxlxr2021-9-2321第一種情況：第一種情況： 此時(shí)，若此時(shí)，若xlxs xr 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。第二種情況：第二種情況： 此時(shí)，若此時(shí)，若xlxs xr 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。 bsbyyyyxxyyxx)/()(121211s tstyyyyxxyyxx

16、)/()(121211s第三種情況：第三種情況： 此時(shí)，若此時(shí)，若ybys yt 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。 )/()(01001xxxxyyyyxxlll2021-9-2322II. 若若x1xr線段的起點(diǎn)坐標(biāo)可能線段的起點(diǎn)坐標(biāo)可能位于位于6區(qū)、區(qū)、7區(qū)、區(qū)、8區(qū)。區(qū)。而新起點(diǎn)的坐標(biāo)可能在而新起點(diǎn)的坐標(biāo)可能在直線直線y= yb和線段的交點(diǎn)上和線段的交點(diǎn)上直線直線y= yt和線段的交點(diǎn)上和線段的交點(diǎn)上直線直線x= xr和線段的交點(diǎn)上和線段的交點(diǎn)上012345678(x1,y1)ybytxlxr2

17、021-9-2323第一種情況：第一種情況： 此時(shí)，若此時(shí)，若xlxs xr 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。第二種情況：第二種情況： 此時(shí)，若此時(shí)，若xlxs xr 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。第三種情況：第三種情況： 此時(shí)，若此時(shí)，若ybys yt 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。若此三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。若此三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。 bsbyyyyxxyyxx)/()(121211s tstyyyyxxyyxx)/()(121211s )/()(y121211sxxyyxxyxxrrs2021-9-2324I

18、II 若若Xl=X=Xr線段的起點(diǎn)坐標(biāo)可能位于線段的起點(diǎn)坐標(biāo)可能位于1區(qū)和區(qū)和2區(qū)。區(qū)。而新起點(diǎn)的坐標(biāo)可能在而新起點(diǎn)的坐標(biāo)可能在直線直線y= yb和線段的交點(diǎn)上和線段的交點(diǎn)上直線直線y= yt和線段的交點(diǎn)上和線段的交點(diǎn)上012345678(x1,y1)ybytxlxr2021-9-2325第一種情況：第一種情況： 此時(shí)，若此時(shí)，若xlxs xr 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。第二種情況：第二種情況： 此時(shí)，若此時(shí)，若xlxs xr 則則(xs ys)為有效新起點(diǎn)。為有效新起點(diǎn)。若此二種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。若此二種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。 tstsyy

19、yyyyxxxx)/()(010010 bsbsyyyyyyxxxx)/()(010010使用同樣的方法，可得到直線在窗口的另一個(gè)可見使用同樣的方法，可得到直線在窗口的另一個(gè)可見端點(diǎn)。端點(diǎn)。2021-9-2326Cohen-Sutherland 算法算法 (編碼算法編碼算法) 基本思想：基本思想：Cohen-Sutherland直線剪裁算法以區(qū)域編碼為基礎(chǔ)，將窗口直線剪裁算法以區(qū)域編碼為基礎(chǔ)，將窗口及其周圍的八個(gè)方向以及其周圍的八個(gè)方向以4 bit的二進(jìn)制數(shù)進(jìn)行編碼。的二進(jìn)制數(shù)進(jìn)行編碼。對每條直對每條直線段線段p0(x0,y0)p1(x1,y1)分三種情況處理：分三種情況處理：(1) 直線段完

20、全可見，直線段完全可見，“簡取簡取”之。之。(2) 直線段完全不可見，直線段完全不可見，“簡棄簡棄”之。之。(3) 直線段既不滿足直線段既不滿足“簡取簡取”的條件，的條件，也不滿足也不滿足“簡棄簡棄”的條件，需要對的條件，需要對直線段按交點(diǎn)進(jìn)行分段，分段后重復(fù)上述處理。直線段按交點(diǎn)進(jìn)行分段，分段后重復(fù)上述處理。 2021-9-2327算法步驟：算法步驟：第一步第一步 判別線段兩端點(diǎn)是否都落在窗口內(nèi)，判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進(jìn)入第二步；如果是，則線段完全可見；否則進(jìn)入第二步；第二步第二步 判別線段是否為顯然不可見，判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；

21、否則進(jìn)行第三步；如果是，則裁剪結(jié)束；否則進(jìn)行第三步；第三步第三步 求線段與窗口邊延長線的交點(diǎn)，求線段與窗口邊延長線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束 裁剪過程是遞歸的。裁剪過程是遞歸的。2021-9-2328Cohen-SutherLand算法算法(編碼算法編碼算法)特點(diǎn)：對顯然不可見線段的快速判別特點(diǎn)：對顯然不可見線段的快速判別編碼方法：延長窗口的四條邊線，由窗口四條邊所在直編碼方法：延長窗口的四條邊線，由窗口四條邊所在

22、直線把二維平面分成線把二維平面分成9個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼，碼，CtCbCrCl，上下右左；，上下右左； elseyyCt0max1當(dāng)當(dāng) elsexxCr0max1當(dāng)當(dāng) elsexxCl0min1當(dāng)當(dāng) elseyyCb0min1當(dāng)當(dāng)左域左域右域右域上域上域下域下域內(nèi)域內(nèi)域2021-9-2329第一位第一位 1：點(diǎn)處于上邊框線的上邊；：點(diǎn)處于上邊框線的上邊；第二位第二位 1：點(diǎn)處于下邊框線的下邊；：點(diǎn)處于下邊框線的下邊；第三位第三位 1：點(diǎn)處于右邊框線的右邊；：點(diǎn)處于右邊框線的右邊；第四位第四位 1：點(diǎn)處于左邊框線的左邊；：點(diǎn)處于左邊框線的左邊；顯然：顯然

23、： 如果某線段的兩端點(diǎn)的兩個(gè)四位代碼全為零時(shí)那么該線段完全位于窗口如果某線段的兩端點(diǎn)的兩個(gè)四位代碼全為零時(shí)那么該線段完全位于窗口內(nèi)，即全為內(nèi)，即全為“0000”，可直接保留；，可直接保留； 如果兩端點(diǎn)的標(biāo)識碼的邏輯與（按位乘）運(yùn)算，結(jié)果不為零，那么該線如果兩端點(diǎn)的標(biāo)識碼的邏輯與（按位乘）運(yùn)算，結(jié)果不為零，那么該線段必位于窗口外，可直接舍棄。段必位于窗口外，可直接舍棄。 否則，這一線段可能與窗口相交。此時(shí)，需要對線段進(jìn)行再分割，即找否則，這一線段可能與窗口相交。此時(shí)，需要對線段進(jìn)行再分割，即找到與窗口邊線的一個(gè)交點(diǎn)，根據(jù)交點(diǎn)位置，賦予四位二進(jìn)制編碼，然后到與窗口邊線的一個(gè)交點(diǎn)，根據(jù)交點(diǎn)位置，賦予

24、四位二進(jìn)制編碼，然后再進(jìn)行上述測試，測試結(jié)果是必有一段在窗口之外，可被排除，另一段再進(jìn)行上述測試，測試結(jié)果是必有一段在窗口之外，可被排除，另一段再重復(fù)上述處理過程。再重復(fù)上述處理過程。 直到全部線段均被舍棄或被保留為止。直到全部線段均被舍棄或被保留為止。2021-9-2330Cohen-SutherLand算法算法(編碼算法編碼算法)端點(diǎn)編碼：定義為它所在區(qū)域的編碼端點(diǎn)編碼：定義為它所在區(qū)域的編碼結(jié)論：當(dāng)線段的兩個(gè)端點(diǎn)的編碼的結(jié)論：當(dāng)線段的兩個(gè)端點(diǎn)的編碼的邏輯邏輯“與與”非零非零時(shí)時(shí) ，線段為顯然不可見的線段為顯然不可見的 2021-9-2331 求交測試順序固定求交測試順序固定( (左上右下

25、）左上右下） 最壞情形，線段求交四次。最壞情形，線段求交四次。Cohen-SutherLand算法算法(編碼算法編碼算法)對于那些非完全可見、又非顯然不可見的線段，需要對于那些非完全可見、又非顯然不可見的線段，需要求交求交（如，線段（如，線段AD)AD)，求交前，求交前先測試先測試與窗口哪條邊所在與窗口哪條邊所在直線有交？直線有交？( (按序判斷端點(diǎn)編碼中各位的值按序判斷端點(diǎn)編碼中各位的值ClCtCrCbClCtCrCb）2021-9-2332 1）特點(diǎn)：）特點(diǎn)：容易將不需要裁剪的直線挑出。容易將不需要裁剪的直線挑出。規(guī)則是：如果一條直線的兩端在同一區(qū)域，則該直線不需要裁剪，規(guī)則是：如果一條直

26、線的兩端在同一區(qū)域，則該直線不需要裁剪，否則該直線為可能裁剪直線。否則該直線為可能裁剪直線。對可能裁剪的直線縮小了與之求交的邊框范圍。對可能裁剪的直線縮小了與之求交的邊框范圍。規(guī)則是：如果直線的一個(gè)端點(diǎn)在上（下、左、右）域，則此直線規(guī)則是：如果直線的一個(gè)端點(diǎn)在上（下、左、右）域，則此直線與上邊框求交，然后刪去上邊框以上的部分。該規(guī)則對直線的另與上邊框求交，然后刪去上邊框以上的部分。該規(guī)則對直線的另一端點(diǎn)也適用。一條直線至多只需要與兩條邊框求交。一端點(diǎn)也適用。一條直線至多只需要與兩條邊框求交。用編碼方法可快速判斷線段用編碼方法可快速判斷線段-完全可見和顯然不可見。完全可見和顯然不可見。 2）特別

27、適用二種場合：）特別適用二種場合：大窗口場合；大窗口場合；窗口特別小的場合，如光標(biāo)拾取圖形時(shí)窗口特別小的場合，如光標(biāo)拾取圖形時(shí),光標(biāo)看作小的裁剪光標(biāo)看作小的裁剪窗口。窗口。2021-9-2333P1：(-3/2, 1/6)；編碼；編碼 (0001)P2：(1/2, 3/2)；編碼；編碼 (1000)(2) 求右邊交點(diǎn)，得求右邊交點(diǎn)，得 P1(1, 11/6) P2(-1, 1/2)； 并編碼，并編碼， 判別之不可見判別之不可見求左邊交點(diǎn)，得求左邊交點(diǎn)，得P1P2; P1:(-1,1/2); 編碼編碼(0000) 判別知非完全可見，且判別知非完全可見，且P1在窗口內(nèi)，在窗口內(nèi)， 因此交換因此交換

28、P1P2得新線段得新線段P1P2； P1：(1/2, 3/2)；編碼；編碼 (1000)P2：(-1, 1/2)； 編碼編碼 (0000)(3) 求上邊交點(diǎn)，得求上邊交點(diǎn)，得 P1(-1/4, 1) P2(-1, 1/2)；并編碼，兩端點(diǎn)編碼全部為并編碼，兩端點(diǎn)編碼全部為0， 線段完全可見，程序結(jié)束線段完全可見，程序結(jié)束P1P1P12021-9-2334Cohen-SutherLand算法算法(編碼算法編碼算法)如何判定該與窗口的哪條邊求交呢？如何判定該與窗口的哪條邊求交呢？編碼中對應(yīng)位為編碼中對應(yīng)位為1的邊。的邊。P1P2P3P40000010001011001000110100110100

29、00010圖6-27 直線段p1p2的編碼裁剪2）if(ai=bi=ci=di=0)則顯示整條直線，取出下一條直線，返回則顯示整條直線，取出下一條直線，返回1）；）；否則否則if(a1&a2)or(b1&b2) or(c1&c2) or(d1&b2)=1)則取出下一條直線，返則取出下一條直線，返回回1）；否則）；否則例子：依次對每條直線例子：依次對每條直線P1P2作如下處理作如下處理1）對直線兩端點(diǎn)）對直線兩端點(diǎn)P1、P2按各自所在的區(qū)域編碼，按各自所在的區(qū)域編碼， P1、P2的編碼分別記為：的編碼分別記為：C1(P1)=a1,b1,c1,d1，C2(P2)=a2,b2,c2,d2其中其中ai

30、，bi，ci，di取值域?yàn)槿≈涤驗(yàn)?，1，i=1,2 3）if (a1&a2=1)，則求直線與窗上邊（，則求直線與窗上邊（yyw_max)之交之交點(diǎn)，并刪去交點(diǎn)以上部分；點(diǎn)，并刪去交點(diǎn)以上部分； if (b1&b2=1)，則求直線與窗下邊（，則求直線與窗下邊（yyw_min)之交點(diǎn)，之交點(diǎn)，并刪去交點(diǎn)以下部分；并刪去交點(diǎn)以下部分； if (c1&c2=1)，則求直線與窗右邊，則求直線與窗右邊（xxw_max)之交點(diǎn)，并刪去交點(diǎn)以右部分；之交點(diǎn)，并刪去交點(diǎn)以右部分； if (d1&d2=1)，則求直線與窗左邊（，則求直線與窗左邊（xxw_max)之交點(diǎn)，之交點(diǎn)，并刪去交點(diǎn)以左部分；并刪去交點(diǎn)以左

31、部分； 4）返回）返回1）。）。2021-9-23352021-9-23362021-9-2337中點(diǎn)分割算法中點(diǎn)分割算法基本思想：基本思想：從從P P0 0點(diǎn)出發(fā)找出離點(diǎn)出發(fā)找出離P P0 0最近的可見點(diǎn)，和從最近的可見點(diǎn)，和從P P1 1點(diǎn)出發(fā)找出離點(diǎn)出發(fā)找出離P P1 1最最近的可見點(diǎn)。這兩個(gè)可見點(diǎn)的連線就是原線段的可見部分。近的可見點(diǎn)。這兩個(gè)可見點(diǎn)的連線就是原線段的可見部分。定義：定義：線段端點(diǎn)的最近可見點(diǎn)是指任一線段被窗口裁剪后所得兩個(gè)線段端點(diǎn)的最近可見點(diǎn)是指任一線段被窗口裁剪后所得兩個(gè)新端點(diǎn)中離該端點(diǎn)較近的一個(gè)點(diǎn)。新端點(diǎn)中離該端點(diǎn)較近的一個(gè)點(diǎn)。從從P0點(diǎn)出發(fā)找出點(diǎn)出發(fā)找出 距距P0

32、最近的可見點(diǎn)（圖中為最近的可見點(diǎn)（圖中為A點(diǎn)），點(diǎn)），從從P1點(diǎn)出發(fā)找出距點(diǎn)出發(fā)找出距P1最近的可見點(diǎn)（圖中為最近的可見點(diǎn)（圖中為B）。）。取中點(diǎn)取中點(diǎn)Pm=(P1+P2)/2。P0P1PmAB2021-9-2338中點(diǎn)分割法中點(diǎn)分割法與前一種與前一種Cohen-Sutherland算法一樣首先對線段端點(diǎn)進(jìn)行編碼，算法一樣首先對線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況并把線段與窗口的關(guān)系分為三種情況: 全在全在、完全不在完全不在和和線段線段與窗口有交與窗口有交。 對前兩種情況，進(jìn)行一樣的處理。對前兩種情況，進(jìn)行一樣的處理。 對第三類線段的處理對第三類線段的處理當(dāng)對直線段不能簡取也不能

33、簡棄時(shí)，不斷地用對分方法，舍去線段的不當(dāng)對直線段不能簡取也不能簡棄時(shí)，不斷地用對分方法，舍去線段的不可見部分，用中點(diǎn)去逼近線段與窗口邊界的交點(diǎn)?？梢姴糠郑弥悬c(diǎn)去逼近線段與窗口邊界的交點(diǎn)。簡單地簡單地用中點(diǎn)分割的方法求出線段與用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)，窗口的交點(diǎn)，把線段等分為二段，對把線段等分為二段，對兩段重復(fù)上述測試處理，直至每條線兩段重復(fù)上述測試處理，直至每條線段完全在窗口內(nèi)或完全在窗口外。段完全在窗口內(nèi)或完全在窗口外。P0P1PmAB2021-9-2339實(shí)現(xiàn)算法：（實(shí)現(xiàn)算法：（以以P0點(diǎn)為例說明）點(diǎn)為例說明） 1)排斥性測試排斥性測試測試線段是否完全被排斥在窗口之外，測試線

34、段是否完全被排斥在窗口之外，若是，則無線段輸出，算法結(jié)束。否則若是，則無線段輸出，算法結(jié)束。否則執(zhí)行下一步；執(zhí)行下一步； 2)包含性測試包含性測試測試測試P1點(diǎn)是否包含在窗口內(nèi)，如果是，點(diǎn)是否包含在窗口內(nèi)，如果是，則則P1點(diǎn)即為點(diǎn)即為P0的最遠(yuǎn)可選點(diǎn)，算法結(jié)束，的最遠(yuǎn)可選點(diǎn)，算法結(jié)束，否則，執(zhí)行下一步；否則，執(zhí)行下一步； 3)將直線段將直線段P0P1于中點(diǎn)于中點(diǎn)Pm處分割，則分處分割，則分如下幾種情況處理：如下幾種情況處理：P0P1PmAB2021-9-2340線段線段MP1完全在窗口之外，那么便以線段完全在窗口之外，那么便以線段P0M為新的線為新的線段段P0P1，然后返回算法的第一步重新開始

35、測試；，然后返回算法的第一步重新開始測試；如果線段如果線段MP1沒有被完全排斥在窗口之外，那么便以線沒有被完全排斥在窗口之外，那么便以線段段MP1作為新線段作為新線段P0P1，然后返回算法的第一步。，然后返回算法的第一步。P0P1MP0P1MP0P1MP0P1M2021-9-2341中點(diǎn)分割算法中點(diǎn)分割算法-求線段與窗口的交點(diǎn)求線段與窗口的交點(diǎn) 從從P0出發(fā)找距離出發(fā)找距離P0最近可見點(diǎn)采用中點(diǎn)分割方法最近可見點(diǎn)采用中點(diǎn)分割方法先求出先求出P0P1的中點(diǎn)的中點(diǎn)Pm,若若P0Pm不是顯然不可見的，不是顯然不可見的，并且并且P0P1在窗口中有可見部分，在窗口中有可見部分，則距則距P0最近的可見點(diǎn)一

36、定落在最近的可見點(diǎn)一定落在P0Pm上，所以用上，所以用P0Pm代替代替P0P1；否則取否則取PmP1代替代替P0P1。再對新的再對新的P0P1求中點(diǎn)求中點(diǎn)Pm。重復(fù)上述過程，直到。重復(fù)上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時(shí)長度小于給定的控制常數(shù)為止，此時(shí)Pm收收斂于交點(diǎn)。斂于交點(diǎn)。 從從P1出發(fā)找距離出發(fā)找距離P1最近可見點(diǎn)采用上面類似方法。最近可見點(diǎn)采用上面類似方法。P0P1PmAB2021-9-2342中點(diǎn)分割算法框圖中點(diǎn)分割算法框圖2021-9-2343中點(diǎn)分割算法的中點(diǎn)分割算法的核心思想是是通過二分逼近來確定直通過二分逼近來確定直線段與窗口的交點(diǎn)線段與窗口的交點(diǎn)。p1p

37、2p3p4p5p6p72021-9-23442021-9-2345對分辯率為對分辯率為2N*2N的顯示器，上述二分過程的顯示器，上述二分過程至多進(jìn)行至多進(jìn)行N次。次。主要過程只用到加法和除法運(yùn)算，適合硬主要過程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)，件實(shí)現(xiàn)，它可以用左右移位來代替乘除法，它可以用左右移位來代替乘除法，這樣就大大加快了速度這樣就大大加快了速度。中點(diǎn)分割裁剪算法中點(diǎn)分割裁剪算法2021-9-2346多邊形裁剪多邊形裁剪2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？確定這些小多邊形的邊界？2021-9-2347多邊形

38、的剪裁算法多邊形的剪裁算法SutlerlandHodgman算法算法WeilerAthenton算法算法2021-9-2348Sutherland-Hodgman算法算法 對多邊形裁剪的對多邊形裁剪的Sutherland-Hodgman算法是一算法是一種簡便的方法，只要對多邊形用窗口的四條邊依種簡便的方法，只要對多邊形用窗口的四條邊依次裁剪四次，便可得到裁剪后的多邊形次裁剪四次，便可得到裁剪后的多邊形。分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。解為多邊形關(guān)于窗口四邊所在直線的裁剪。2021-9-2349基本思想：基

39、本思想：1）令多邊形的頂點(diǎn)按邊線逆時(shí)針走向排序。各邊先與左）令多邊形的頂點(diǎn)按邊線逆時(shí)針走向排序。各邊先與左窗邊求交。求交后刪去多邊形在窗之左的部分，并插入窗邊求交。求交后刪去多邊形在窗之左的部分，并插入左窗邊及其延長線的交點(diǎn)之間的部分，從而形成一個(gè)新左窗邊及其延長線的交點(diǎn)之間的部分，從而形成一個(gè)新的多邊形。然后，新的多邊形按相同的方法與上窗邊相的多邊形。然后，新的多邊形按相同的方法與上窗邊相裁剪。如此重復(fù)，直至與裁剪。如此重復(fù)，直至與各窗邊都裁剪各窗邊都裁剪完畢。完畢。2）多邊形與每一條窗邊相交，生成新的多邊形頂點(diǎn)序列）多邊形與每一條窗邊相交，生成新的多邊形頂點(diǎn)序列的過程，是一個(gè)對多邊形的過程

40、，是一個(gè)對多邊形各頂點(diǎn)依次處理各頂點(diǎn)依次處理的過程。的過程。2021-9-2350輸入：ABCDEFGHABCDEFGH輸出：A12DEFGH12(a)用左邊界裁剪輸出：A134D56FGHADEFGH輸入：A12DEFGH12(b)用下邊界裁剪34562021-9-2351輸入：A134D56FGHADFGH1(c)用右邊界裁剪3456輸出：A134D5678GH78ADGH1(d)用上邊界裁剪345678輸入：A134D5678GH輸出：K34D56789IHJ9IJK2021-9-23522021-9-2353Weiler-Athenton算法算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）裁

41、剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：的情況：主多邊形：被裁剪多邊形，記為主多邊形：被裁剪多邊形，記為A A 裁剪多邊形：裁剪窗口，記為裁剪多邊形：裁剪窗口，記為B B 2021-9-2354主多邊形和裁剪多邊形把二維平面分成兩部分。主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：內(nèi)裁剪：AB外裁剪：外裁剪：A-BWeiler-Athenton算法算法裁剪結(jié)果區(qū)域的邊界由裁剪結(jié)果區(qū)域的邊界由A的部分邊的部分邊界和界和B的部分邊界兩部分構(gòu)成，并的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至的邊界轉(zhuǎn)至B的邊界，或由的邊界，或由B的邊界的邊界轉(zhuǎn)至

42、轉(zhuǎn)至A的邊界的邊界 2021-9-2355Weiler-Athenton算法算法如果主多邊形與裁剪多邊形有交點(diǎn)，則如果主多邊形與裁剪多邊形有交點(diǎn)，則交點(diǎn)成對出現(xiàn)，交點(diǎn)成對出現(xiàn)，它們被分為如下兩類：它們被分為如下兩類：進(jìn)點(diǎn)進(jìn)點(diǎn)：主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi)：主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi) 如，如，I1,I3, I5, I7, I9, I11出點(diǎn)出點(diǎn)：主多邊形邊界由：主多邊形邊界由此離開裁剪多邊形區(qū)域此離開裁剪多邊形區(qū)域. 如，如， I0,I2, I4, I6, I8, I10 2021-9-2356Weiler-Athenton算法算法1）建頂點(diǎn)表；）建頂點(diǎn)表；2）求交點(diǎn)；）求交點(diǎn)；3）裁

43、剪）裁剪 Weiler_Athenton裁剪算法（內(nèi)裁剪）步驟：裁剪算法（內(nèi)裁剪）步驟：1、建立主多邊形和裁剪多邊的頂點(diǎn)表、建立主多邊形和裁剪多邊的頂點(diǎn)表2、求主多邊形和裁剪多邊形的交點(diǎn)，并將這些交、求主多邊形和裁剪多邊形的交點(diǎn)，并將這些交點(diǎn)按順序插入兩多邊形的頂點(diǎn)表中。在兩多邊表形點(diǎn)按順序插入兩多邊形的頂點(diǎn)表中。在兩多邊表形頂點(diǎn)表中的相同交點(diǎn)間建立雙向指針頂點(diǎn)表中的相同交點(diǎn)間建立雙向指針 。3、裁剪、裁剪 如果存在沒有被跟蹤過的交點(diǎn)，執(zhí)行以下步驟：如果存在沒有被跟蹤過的交點(diǎn)，執(zhí)行以下步驟： 2021-9-2357 (1)建立裁剪結(jié)果多邊形的頂點(diǎn)表建立裁剪結(jié)果多邊形的頂點(diǎn)表 (2)選取任一沒有

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

45、一步跟蹤的是主多邊形邊界，現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊界，現(xiàn)在改為跟蹤主多邊形邊界）界，現(xiàn)在改為跟蹤主多邊形邊界） (6)重復(fù)重復(fù)(4)、(5)直至回到起點(diǎn)直至回到起點(diǎn)2021-9-23計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院58Weiler-Athenton算法算法2021-9-2359Weiler-Athenton多邊形裁剪算法多邊形裁剪算法12345678910111213從目標(biāo)多邊形從目標(biāo)多邊形A A開始，逆時(shí)針掃描邊界：開始，逆時(shí)針掃描邊界：如果進(jìn)入裁剪窗口多邊形，記錄交點(diǎn)，然后繼續(xù)掃描目標(biāo)多邊形如果進(jìn)入裁剪窗口多邊形，記錄

46、交點(diǎn)，然后繼續(xù)掃描目標(biāo)多邊形如果離開裁剪窗口多邊形，記錄交點(diǎn)，并右轉(zhuǎn)，然后以同樣方式繼續(xù)跟蹤裁剪如果離開裁剪窗口多邊形，記錄交點(diǎn)，并右轉(zhuǎn)，然后以同樣方式繼續(xù)跟蹤裁剪窗口多邊形（即將裁剪窗口多邊形作為目標(biāo)多邊形，將目標(biāo)多邊形作為裁剪窗口窗口多邊形（即將裁剪窗口多邊形作為目標(biāo)多邊形，將目標(biāo)多邊形作為裁剪窗口多邊形，繼續(xù)前面操作。）多邊形，繼續(xù)前面操作。） 當(dāng)遍歷路徑產(chǎn)生子多邊形時(shí)，將子多邊形作為結(jié)果的一部分輸出，然后從標(biāo)記當(dāng)遍歷路徑產(chǎn)生子多邊形時(shí)，將子多邊形作為結(jié)果的一部分輸出，然后從標(biāo)記為沒有遍歷的邊的起點(diǎn)或部分邊的交點(diǎn)處開始，繼續(xù)對原目標(biāo)多邊形進(jìn)行遍歷。為沒有遍歷的邊的起點(diǎn)或部分邊的交點(diǎn)處開始

47、，繼續(xù)對原目標(biāo)多邊形進(jìn)行遍歷。當(dāng)原目標(biāo)多邊形所有邊都遍歷后，算法結(jié)束。當(dāng)原目標(biāo)多邊形所有邊都遍歷后，算法結(jié)束。上圖從上圖從1-21-2求交，求交，2-32-3，3-43-4，4-54-5右轉(zhuǎn)，右轉(zhuǎn)，5-65-6，6-76-7，7-87-8第二次右轉(zhuǎn)，輸出子多邊形；第二次右轉(zhuǎn)，輸出子多邊形；從第一次變換窗口處的交點(diǎn)開始遍歷從第一次變換窗口處的交點(diǎn)開始遍歷A A，從，從9 9到到1010再到再到1111，沒有輸出。跳過已經(jīng)遍歷，沒有輸出。跳過已經(jīng)遍歷的的6 6和和7 7后，繼續(xù)遍歷后，繼續(xù)遍歷1212和和1313直到結(jié)束。直到結(jié)束。2021-9-2360Weiler-Athenton算法算法交點(diǎn)的

48、奇異情況處理交點(diǎn)的奇異情況處理 1、與裁剪多邊形邊重合的主多邊形的邊不參與求交點(diǎn)；、與裁剪多邊形邊重合的主多邊形的邊不參與求交點(diǎn)；2、對于頂點(diǎn)落在裁剪多邊形的邊上的主多邊的邊，如果落在、對于頂點(diǎn)落在裁剪多邊形的邊上的主多邊的邊，如果落在該裁剪邊的內(nèi)側(cè)，將該頂點(diǎn)算作交點(diǎn)；而如果這條邊落該裁剪邊的內(nèi)側(cè)，將該頂點(diǎn)算作交點(diǎn)；而如果這條邊落在該裁剪邊的外側(cè)，將該頂點(diǎn)不看作交點(diǎn)在該裁剪邊的外側(cè)，將該頂點(diǎn)不看作交點(diǎn) 2021-9-2361Weiler-Atherton算法裁剪凹多邊形的過程和結(jié)果算法裁剪凹多邊形的過程和結(jié)果ABCDECEV1V2V3V4V1V2V3V4圖6-34 Weiler-Atherto

49、n算法裁剪凹多邊形(a)裁剪前(b)Weiler-Atherton算法的裁剪結(jié)果返回返回2021-9-23622021-9-2363字符串的剪裁字符串的剪裁字符串的有或無剪裁字符串的有或無剪裁字符的有或無剪裁字符的有或無剪裁字符的精密剪裁字符的精密剪裁 2021-9-2364字符裁剪字符裁剪 1)基于字符串，字符串的有或無裁剪基于字符串，字符串的有或無裁剪算法思想：算法思想：根據(jù)字符串所含字符的個(gè)數(shù)及其字符的大小、間隔、軌跡，求根據(jù)字符串所含字符的個(gè)數(shù)及其字符的大小、間隔、軌跡，求出字符串的外包圍盒（出字符串的外包圍盒（box）。）。外包圍盒的邊界極值與窗邊極值比較而決定該字符串的去留。外包圍

50、盒的邊界極值與窗邊極值比較而決定該字符串的去留。2021-9-2365字符裁剪字符裁剪 2)2)基于字符，字符的有或無裁剪：基于字符，字符的有或無裁剪：算法思想：算法思想：以字串以字串boxbox與窗邊比較而決定字串的全刪、全留或部分留；與窗邊比較而決定字串的全刪、全留或部分留；對部分留的字串中，逐個(gè)測量字符的對部分留的字串中，逐個(gè)測量字符的boxbox與窗邊關(guān)系而決定與窗邊關(guān)系而決定該字符的去留該字符的去留。2021-9-2366字符裁剪字符裁剪3）基于構(gòu)成字符的最小元素）基于構(gòu)成字符的最小元素 ，字符的精細(xì)裁剪，字符的精細(xì)裁剪算法思想：用字串算法思想：用字串box與窗邊相比較，決定字串的全

51、刪、全與窗邊相比較，決定字串的全刪、全留或部分留；對部分留的字串中，逐個(gè)測量字符的留或部分留；對部分留的字串中，逐個(gè)測量字符的box與窗與窗邊的關(guān)系，決定字符的全刪、全留或部分留；對部分留的字邊的關(guān)系，決定字符的全刪、全留或部分留；對部分留的字符的每一筆劃，用直線裁剪法對窗邊進(jìn)行裁剪。符的每一筆劃，用直線裁剪法對窗邊進(jìn)行裁剪。點(diǎn)陣字符：點(diǎn)裁剪點(diǎn)陣字符：點(diǎn)裁剪矢量字符：線裁剪矢量字符：線裁剪4.2 二維基本變換圖形變換圖形變換一般是指對圖形的幾何信息經(jīng)過幾何變換后產(chǎn)生新的圖一般是指對圖形的幾何信息經(jīng)過幾何變換后產(chǎn)生新的圖形。形。l對于線框圖的變換，通常以點(diǎn)變換作為基礎(chǔ)，把圖形的一系對于線框圖的變

52、換，通常以點(diǎn)變換作為基礎(chǔ)，把圖形的一系列頂點(diǎn)作幾何變換，連接新的頂點(diǎn)系列即可產(chǎn)生新的圖形列頂點(diǎn)作幾何變換，連接新的頂點(diǎn)系列即可產(chǎn)生新的圖形l對于用參數(shù)方程描述的圖形，可以通過參數(shù)方程作幾何變換，對于用參數(shù)方程描述的圖形，可以通過參數(shù)方程作幾何變換，實(shí)現(xiàn)對圖形的變換實(shí)現(xiàn)對圖形的變換4.2.1 平移變換平移是一物體從一個(gè)位置到另一個(gè)位置所作的直線移動(dòng)。如果要平移是一物體從一個(gè)位置到另一個(gè)位置所作的直線移動(dòng)。如果要把一個(gè)位于把一個(gè)位于P（x，y）的點(diǎn)移到新位置）的點(diǎn)移到新位置p（x，y），則只要在），則只要在原坐標(biāo)上加上平移距離原坐標(biāo)上加上平移距離Tx和和Ty即可即可平移距離（平移距離（T Tx x

53、，T Ty y）稱為平移向量或向量。）稱為平移向量或向量。如果用向量形式來表示位移前后的兩個(gè)點(diǎn)如果用向量形式來表示位移前后的兩個(gè)點(diǎn)4.2.1 平移變換平移向量表示為：平移向量表示為：那么，可以用矩陣相加來表示那么，可以用矩陣相加來表示P P點(diǎn)的位移點(diǎn)的位移記為：記為：4.2.2 比例變換比例變換：比例變換：用來改變一物體大小的變換，也稱為用來改變一物體大小的變換，也稱為縮放變換?？s放變換。如果要對一個(gè)多邊形進(jìn)行比例變換，那么可把各頂點(diǎn)的坐標(biāo)（如果要對一個(gè)多邊形進(jìn)行比例變換，那么可把各頂點(diǎn)的坐標(biāo)（x x，y y）均乘以比例因子均乘以比例因子S Sx x，S Sy y，以產(chǎn)生變換后的坐標(biāo)（，以產(chǎn)生

54、變換后的坐標(biāo)（x x，y y）1.S1.Sx x、S Sy y可以是任意正數(shù)可以是任意正數(shù)2.Sx2.Sx、Sy1Sy1Sy1，則物體放大，則物體放大4.Sx4.Sx、SySy1 1，則物體大小形狀不變，則物體大小形狀不變4.2.2 比例變換如果令如果令則比例變換可以表示成以下的矩陣形式：則比例變換可以表示成以下的矩陣形式：4.2.3 旋轉(zhuǎn)變換旋轉(zhuǎn)變換：物體上的各點(diǎn)繞一固定點(diǎn)沿圓周路徑作轉(zhuǎn)動(dòng)稱為旋轉(zhuǎn)變換。旋轉(zhuǎn)變換：物體上的各點(diǎn)繞一固定點(diǎn)沿圓周路徑作轉(zhuǎn)動(dòng)稱為旋轉(zhuǎn)變換?？捎眯D(zhuǎn)角表示旋轉(zhuǎn)量的大小?？捎眯D(zhuǎn)角表示旋轉(zhuǎn)量的大小。一個(gè)點(diǎn)由由位置（一個(gè)點(diǎn)由由位置（x，y）旋轉(zhuǎn)到（）旋轉(zhuǎn)到（x，y）的角度為

55、自水平軸算起的角）的角度為自水平軸算起的角度，度， 為旋轉(zhuǎn)角，可由三角關(guān)系得：為旋轉(zhuǎn)角，可由三角關(guān)系得：4.2.3 旋轉(zhuǎn)變換相對于坐標(biāo)原點(diǎn)的旋轉(zhuǎn)變換公式：相對于坐標(biāo)原點(diǎn)的旋轉(zhuǎn)變換公式：如果令如果令則有則有4.3 二維幾何變換的齊次坐標(biāo)表示4.3.1齊次坐標(biāo)技術(shù)三種基本幾何變換的矩陣表示形式三種基本幾何變換的矩陣表示形式：平移變換的處理方法與其他兩種變換的形式不一樣，希望能夠用平移變換的處理方法與其他兩種變換的形式不一樣，希望能夠用一種一致的或同類的方法來處理這一種一致的或同類的方法來處理這3種變換，使得這種變換，使得這3種基本變種基本變換能很容易地結(jié)合在一起，形成各種復(fù)雜的組合變換。換能很容易

56、地結(jié)合在一起，形成各種復(fù)雜的組合變換。4.3.1齊次坐標(biāo)技術(shù)齊次坐標(biāo)齊次坐標(biāo)：基本思想基本思想：把一個(gè)：把一個(gè)n n維空間的幾何問題，轉(zhuǎn)換到維空間的幾何問題，轉(zhuǎn)換到n n1 1維空間中去解決。維空間中去解決。形式形式：用一個(gè)有：用一個(gè)有n n1 1個(gè)分量的向量去表示一個(gè)有個(gè)分量的向量去表示一個(gè)有n n個(gè)分量的向量的方法個(gè)分量的向量的方法如二維平面上的點(diǎn)（如二維平面上的點(diǎn)（x x，y y）的齊次坐標(biāo)表示為（）的齊次坐標(biāo)表示為（ hx，hy ，h），），h h是任是任一不為一不為0 0的比例系數(shù)。的比例系數(shù)。齊次坐標(biāo)表示（齊次坐標(biāo)表示（x x，y y，h h）二維笛卡兒直角坐標(biāo)（二維笛卡兒直角坐標(biāo)

57、（x/hx/h，y/hy/h）規(guī)格化齊次坐標(biāo)規(guī)格化齊次坐標(biāo)：齊次坐標(biāo)表示不是唯一的，通常將：齊次坐標(biāo)表示不是唯一的，通常將h h1 1時(shí)的齊次坐標(biāo)稱時(shí)的齊次坐標(biāo)稱為規(guī)格化的齊次坐標(biāo)。為規(guī)格化的齊次坐標(biāo)。4.3.1齊次坐標(biāo)技術(shù)使用齊次坐標(biāo)表示法在計(jì)算機(jī)圖形處理中的優(yōu)越性：使用齊次坐標(biāo)表示法在計(jì)算機(jī)圖形處理中的優(yōu)越性：（1 1）將平移、旋轉(zhuǎn)、縮放）將平移、旋轉(zhuǎn)、縮放3 3種變換用統(tǒng)一的方式，即用矩陣乘積的方式表種變換用統(tǒng)一的方式，即用矩陣乘積的方式表達(dá)。提供了用矩陣運(yùn)算將二維、三維或更高維空間中的一個(gè)點(diǎn)集從一個(gè)坐達(dá)。提供了用矩陣運(yùn)算將二維、三維或更高維空間中的一個(gè)點(diǎn)集從一個(gè)坐標(biāo)系變換到另一個(gè)坐標(biāo)系

58、的有效方法。標(biāo)系變換到另一個(gè)坐標(biāo)系的有效方法。（2 2）可以表示無窮遠(yuǎn)點(diǎn)）可以表示無窮遠(yuǎn)點(diǎn)齊次坐標(biāo)（齊次坐標(biāo)（hxhx，hyhy，h h）lh h 0 0時(shí)，隨著時(shí)，隨著h h的變化，每個(gè)齊次點(diǎn)代表了空間的一條線的變化，每個(gè)齊次點(diǎn)代表了空間的一條線l將將3 3個(gè)坐標(biāo)都除以個(gè)坐標(biāo)都除以h h，得到（，得到（x x，y y，1 1）代表該直線與（）代表該直線與（x x，y y，w w）空間）空間中中h h1 1平面交的點(diǎn)。平面交的點(diǎn)。lh h0 0，代表該直線趨于無窮遠(yuǎn)點(diǎn)。，代表該直線趨于無窮遠(yuǎn)點(diǎn)。4.3.2 幾何變換的齊次坐標(biāo)表示由于齊次坐標(biāo)表示的點(diǎn)是用由于齊次坐標(biāo)表示的點(diǎn)是用3 3個(gè)分量的行向

59、量來表示的，這樣變換矩陣也必個(gè)分量的行向量來表示的，這樣變換矩陣也必須是須是3 33 3的矩陣，以便于矩陣相乘，當(dāng)然變換后得到的點(diǎn)也是有的矩陣，以便于矩陣相乘，當(dāng)然變換后得到的點(diǎn)也是有3 3個(gè)分量的個(gè)分量的齊次坐標(biāo)。齊次坐標(biāo)。1.1.平移變換平移變換平移矩陣可寫為：平移矩陣可寫為：4.3.2 幾何變換的齊次坐標(biāo)表示1.1.平移變換平移變換對含有平移距離對含有平移距離T Tx x及及T Ty y的的3 33 3的變換矩陣，可引入縮寫符號的變換矩陣，可引入縮寫符號平移變換的矩陣形式縮寫為：平移變換的矩陣形式縮寫為：4.3.2 幾何變換的齊次坐標(biāo)表示2.2.比例變換比例變換比例變換的矩陣形式為：比例

60、變換的矩陣形式為：縮寫為：縮寫為：式中：式中：是用參數(shù)是用參數(shù)S Sx x及及S Sy y表示的表示的3 33 3的比例變換矩陣。的比例變換矩陣。4.3.2 幾何變換的齊次坐標(biāo)表示3.3.旋轉(zhuǎn)變換旋轉(zhuǎn)變換旋轉(zhuǎn)變換矩陣形式為：旋轉(zhuǎn)變換矩陣形式為：縮寫為：縮寫為：式中：式中：為一個(gè)含有參數(shù)為一個(gè)含有參數(shù) 的的33的旋轉(zhuǎn)變換矩陣。的旋轉(zhuǎn)變換矩陣。4.3.3 其他變換在大多數(shù)圖形系統(tǒng)中，都包含平移、比例及旋轉(zhuǎn)等基本變換。有的還提供在大多數(shù)圖形系統(tǒng)中，都包含平移、比例及旋轉(zhuǎn)等基本變換。有的還提供另外幾種很有用的變換如反射變換及錯(cuò)切變換等。另外幾種很有用的變換如反射變換及錯(cuò)切變換等。1.1.反射變換反射變