圖形學(xué)第四章

1、第第 四四 章章 圖形的幾何變換及裁剪圖形的幾何變換及裁剪 本本 章章 重重 點(diǎn)點(diǎn) 1. 二維圖形的變換方法。 2.三維圖形的變換方法。 3.二維線段的裁剪方法。 4.多邊形的裁剪方法。 難點(diǎn)：難點(diǎn)： 1.二維圖形的級(jí)聯(lián)(組合)變換。 2.多邊形的裁剪算法。4.1 概述 為了使被顯示的對(duì)象數(shù)字化，通常是采用適當(dāng)?shù)淖鴺?biāo)系坐標(biāo)系耒描述被處理的對(duì)象。圖形和數(shù)字之間的聯(lián)系也就是通過坐標(biāo)建立起來的。因此，所謂圖形的幾何變換實(shí)質(zhì)上就是圖形的坐標(biāo)變換。 一一. .幾種坐標(biāo)系幾種坐標(biāo)系1. 世界坐標(biāo)系(W World C Coordinates) 為了描述被處理的對(duì)象，要在對(duì)象所在的空間中定義一個(gè)坐標(biāo)系，這個(gè)

2、坐標(biāo)系的長(zhǎng)度單位和坐標(biāo)軸的方向要適合對(duì)被處理對(duì)象的描述，這個(gè)坐標(biāo)系通常就稱之為世界坐標(biāo)系或用戶坐標(biāo)系。世界坐標(biāo)系一般采用右手三維笛卡兒坐標(biāo)系。xyzo 2. 觀察坐標(biāo)系(V View C Coordinates) 產(chǎn)生三維物體的視圖，必須規(guī)定觀察點(diǎn)(視點(diǎn))和觀察方向。 好比照相時(shí)選擇拍攝的位置和方向。 左手笛卡兒坐標(biāo)系(上圖)：觀察坐標(biāo)系的原點(diǎn)通常設(shè)置在觀察點(diǎn)(視點(diǎn))，Z軸作為觀察方向。 右手笛卡兒坐標(biāo)系：視點(diǎn)確定在Z軸上的某一個(gè)位置，Z軸仍為觀察方向(下圖)。xyzo視點(diǎn)xyzo視點(diǎn) 3. 設(shè)備坐標(biāo)系(D Device C Coordinates) 與圖形設(shè)備相關(guān)連的坐標(biāo)系叫設(shè)備坐標(biāo)系。 例

3、如，顯示器以分辨率確定坐標(biāo)單位，原點(diǎn)在左下角或左上角；繪圖機(jī)繪圖平面以繪圖精度確定坐標(biāo)單位，原點(diǎn)一般在左下角。4. 規(guī)格化設(shè)備坐標(biāo)系(N Normal D Device C Coordinates) 為了使圖形處理過程做到與設(shè)備無關(guān)，通常采用一種虛擬設(shè)備的方法來處理，也就是圖形處理的結(jié)果是按照一種虛擬設(shè)備的坐標(biāo)規(guī)定耒輸出的。這種設(shè)備坐標(biāo)規(guī)定為0X1，0Y1，這種坐標(biāo)系稱之為規(guī)格化設(shè)備坐標(biāo)系。二二. . 圖形變換的過程圖形變換的過程建立物體的 WC變換到 VC在VC空間 進(jìn)行裁剪投影到 NDC變換到 DC在圖形設(shè)備上輸出三三. . 圖形變換的特點(diǎn)圖形變換的特點(diǎn) 圖形變換就是改變圖形的幾何關(guān)系，即

4、改變圖形頂點(diǎn)的坐標(biāo)，但圖形的拓?fù)潢P(guān)系不變。 最基本的圖形變換可以分別用矩陣形式表示為：平移變換 PPTm TmMx My Mx、My分別為X方 向和Y方向的平移量。比例變換 PPTs Sx 0 0 Sy Sx、Sy分別表示比例因子。旋轉(zhuǎn)變換 PPTr cos sin -sin cos 0時(shí)為逆時(shí)針旋轉(zhuǎn) 0時(shí)為順時(shí)針旋轉(zhuǎn)Ts Tr四四. . 齊次坐標(biāo)齊次坐標(biāo) 從形式上來說，用一個(gè)有n+1個(gè)分量的向量去表示一個(gè)有n個(gè)分量的向量的方法稱為齊次坐標(biāo)表示。 例如二維平面上的點(diǎn)(x，y)的齊次坐標(biāo)表示為(hx，hy， h)，h是任一不為0的比例系數(shù)。 給定一個(gè)點(diǎn)的齊次坐標(biāo)表示 : (x，y，h)， 該點(diǎn)的

5、二維笛卡兒直角坐標(biāo)： (x / h，y / h)。 同樣，對(duì)于一個(gè)三維空間的向量(x，y，z)， 它在四維空間中對(duì)應(yīng)的向量即齊次坐標(biāo)為(xh，yh，zh，h)，其中h0。 齊次坐標(biāo)的概念可以推廣到n維空間的向量。齊次坐標(biāo)的表示不是唯一的，通常當(dāng)h=1時(shí)，稱為規(guī)格化齊次坐標(biāo)規(guī)格化齊次坐標(biāo)。4.2 二維圖形變換二維圖形變換 采用齊次坐標(biāo)可將二維圖形變換表示成如下形式： a b 0 c d 0 l m 1 P* = P M 二維變換矩陣中： a b c d l m 是對(duì)圖形進(jìn)行平移變換 x* y* 1 = x y 1 變換后的頂點(diǎn)坐標(biāo)變換前的頂點(diǎn)坐標(biāo)二維變換矩陣是對(duì)圖形進(jìn)行縮放、旋轉(zhuǎn)、對(duì)稱、錯(cuò)切等變

6、換。 二維基本變換1.比例變換比例變換是讓點(diǎn)的x,y坐標(biāo)各乘以一個(gè)比例因子，其變換公式為： x = ax y = dy 因此，可令變換矩陣T為：T= ，則：X Y 1 = ax dy 1 = X Y 1 0000001ad0000001ad其中a，d分別為x，y方向上的比例因子(a，d0)。討論： 若a = d = 1, 為恒等變換，即變換后點(diǎn)的坐標(biāo)不變。若a = d1，則為等比變換，變換結(jié)果是圖形等比例放大（a = d 1）或等比例縮?。╝ = d 0時(shí)沿+X向錯(cuò)切；c0時(shí),沿+Y向錯(cuò)切；b 0 時(shí)，圖形沿 X (或 Y )正向錯(cuò)切；當(dāng) c (或 b ) 0 時(shí)，圖形沿 X (或 Y )負(fù)向

7、錯(cuò)切。 平面圖形繞任意點(diǎn)P（Xp,Yp)旋轉(zhuǎn)角，需要通過以下幾個(gè)步驟來實(shí)現(xiàn)： 將旋轉(zhuǎn)中心平移到原點(diǎn)，變換矩陣為： 例例1：繞任意點(diǎn)旋轉(zhuǎn)變換4. 二維圖形的級(jí)聯(lián)(組合)變換 對(duì)于復(fù)雜的圖形變換，需要通過若干個(gè)變換矩陣的級(jí)聯(lián)才能實(shí)現(xiàn)。這里特別要注意的是矩陣級(jí)聯(lián)的順序矩陣級(jí)聯(lián)的順序，由于矩陣的乘法運(yùn)算不適用交換率，因此矩陣級(jí)聯(lián)的順序不同所得到的變換結(jié)果也不相同。 T1 = 1010001ppyx 將圖形繞坐標(biāo)系原點(diǎn)旋轉(zhuǎn)角，變換矩陣為： T2 = 1000cossin0sincos 將旋轉(zhuǎn)中心平移回到原點(diǎn)的位置，變換矩陣為： T3 = 1010001ppyx因此，繞任意點(diǎn)P的旋轉(zhuǎn)變換矩陣為： T =

8、T1 T2 T3 = 1010001ppyx1000cossin0sincos1010001ppyx相乘后得： T = 1)cos1 (sinsin)cos1 (0cossin0sincosppppyxyx顯然，當(dāng)xp=0，yp=0時(shí)，即為對(duì)原點(diǎn)的旋轉(zhuǎn)變換。 例例2 2：對(duì)任意直線的對(duì)稱變換（直線方程為 Ax + By + C = 0） 直線在X軸和Y軸上的截距分別為C/A和C/B，直線與X軸的夾角為， =arctg(A/B)。 xyoxyoxyo 1 0 0 T1 = 0 1 0 C/A 0 1 cos sin 0T2= sin cos 0 0 0 1yxyoxyoxo 1 0 0T3 =

9、0 -1 0 0 0 1 cos sin 0T4 = sin cos 0 0 0 1 1 0 0 T5= 0 1 0 C/A 0 1組合變換矩陣為： cos2 sin2 0T =T1T2T3T4T5= sin2 cos2 0 (cos2-1)C/A sin2*C/A 1 原圖形上的任意一點(diǎn) P(x,y) 對(duì)該直線的對(duì)稱變換都可用下式實(shí)現(xiàn) ： x* y* 1=x y 1T4.3 4.3 三維圖形變換三維圖形變換三維變換矩陣可表示為： a b c p d e f q h i j r l m n s 其中： a b c d e f 產(chǎn)生比例、錯(cuò)切、鏡象和旋轉(zhuǎn)等基本變換。 h i j l m n 產(chǎn)生

10、沿x、y、z三軸方向上的平移變換。 p q 產(chǎn)生透視變換。 r s 產(chǎn)生等比例縮放變換。T = 三維基本變換矩陣左上角的33矩陣的主對(duì)角線上的元素a，e，j的作用是使物體產(chǎn)生比例變換。 比例變換矩陣為： T = 0000000000001aej 其中a，e，j分別為沿x，y，z軸方向的比例因子。 對(duì)點(diǎn)進(jìn)行比例變換： x y z 1T = ax ey jz 1 = x y z 1 三維基本變換1. 比例變換 三維對(duì)稱變換包括對(duì)原點(diǎn)、對(duì)坐標(biāo)軸和對(duì)坐標(biāo)平面的對(duì)稱，常用的是對(duì)坐標(biāo)平面的變換，我們對(duì)此加以討論： 對(duì)xoy平面的對(duì)稱變換 變換矩陣： 1000010000100001xoyT變換后點(diǎn)的坐標(biāo)：

11、 x y z 1 = x y z 1 Txoy = x y z 1 對(duì)xoz平面的對(duì)稱變換2. 對(duì)稱變換變換矩陣為： 1000010000100001xozT變換后點(diǎn)的坐標(biāo)： x y z 1 = x y z 1 Txoz = x y z 1 對(duì)yoz平面的對(duì)稱變換 變換矩陣為： 1000010000100001yozT變換后點(diǎn)的坐標(biāo)： x y z 1 = x y z 1Tyoz = x y z 1上述的對(duì)稱變換結(jié)果如下圖所示。上述的對(duì)稱變換結(jié)果如下圖所示。 ZXYZXYZXY分別對(duì)分別對(duì)XOYXOY（左）、（左）、XOZXOZ（中）和（中）和YOZYOZ（右）平面（右）平面的對(duì)稱變換結(jié)果的對(duì)稱

12、變換結(jié)果 錯(cuò)切變換是指三維立體沿x，y，z三個(gè)方向產(chǎn)生錯(cuò)切，錯(cuò)切變換是畫斜軸測(cè)圖的基礎(chǔ)，其變換矩陣為： 1010100001bcdfhiT x y z 1T = x+dy+hz bx+y+iz cx+fy+z 1 = x y z 1 由變換結(jié)果看出，一個(gè)坐標(biāo)的變化受另外兩個(gè)坐標(biāo)變化的影響。 沿x含y錯(cuò)切 3. 錯(cuò)切變換變換矩陣： ( )100010000100001x ydT錯(cuò)切變換： x y z 1Tx(y) = x+dy y z 1 = x y z 1 沿x含z錯(cuò)切 變換矩陣： x(z)10000100h0100001T錯(cuò)切變換： x y z 1Tx(z) = x+hz y z 1 = x

13、 y z 1 沿y含x錯(cuò)切 變換矩陣: ( )100010000100001y xbT錯(cuò)切變換： x y z 1Ty(x) = x y+bx z 1 = x y z 1 沿y含z錯(cuò)切 變換矩陣： ( )100001000100001y ziT錯(cuò)切變換： x y z 1Ty(z) = x y+iz z 1 = x y z 1 沿z含x錯(cuò)切 變換矩陣： z(x)100010000100001cT錯(cuò)切變換： x y z 1Tz(x) = x y z+cx 1 = x y z 1 沿z含y錯(cuò)切 變換矩陣： z(y)100001000100001fT錯(cuò)切變換： x y z 1Tz(y) = x y z+

14、fy 1 = x y z 1 與二維旋轉(zhuǎn)變換類似，三維旋轉(zhuǎn)變換可分為繞坐標(biāo)軸旋轉(zhuǎn)變換和繞任意軸的旋轉(zhuǎn)變換。 三維旋轉(zhuǎn)變換要比二維旋轉(zhuǎn)變換復(fù)雜得多，但方法是相似的。三維旋轉(zhuǎn)變換可以看作是三個(gè)二維旋轉(zhuǎn)變換，且旋轉(zhuǎn)軸分別為x，y，z軸。 繞x軸旋轉(zhuǎn)角 變換矩陣為： 10000cossin00sincos00001T4. 旋轉(zhuǎn)變換 繞y軸旋轉(zhuǎn)角 變換矩陣為： cos0sin00100sin0cos00001T 繞z軸旋轉(zhuǎn)角 變換矩陣為： cossin00sincos0000100001TZXYZYXXZY 物體分別繞x（左）、y（中）、z（右）軸旋轉(zhuǎn)90變換結(jié)果 將空間一點(diǎn)（x，y，z）平移到一個(gè)新的

15、位置（x y z）的變換矩陣為： 1000010000101lmnT 變換后新點(diǎn)的坐標(biāo)為： x y z 1 = x y z 1T = x+l y+m z+n 1其中：l，m，n分別為沿x，y，z方向上的平移量。 5. 平移變換三維圖形變換中要注意的幾個(gè)問題： 1.在三維圖形的比例變換中，經(jīng)常會(huì)采用 s 來實(shí)現(xiàn)整體的比例變換。當(dāng) |s| 1 時(shí)，三維圖形整體等比例縮小。 2.三維圖形的對(duì)稱變換是相對(duì)于各個(gè)坐標(biāo)平面進(jìn)行的。 3.三維圖形的旋轉(zhuǎn)變換是指繞坐標(biāo)軸的旋轉(zhuǎn)。 在采用右手坐標(biāo)系的情況下，圖形繞坐標(biāo)軸逆時(shí)針旋轉(zhuǎn)時(shí)，轉(zhuǎn)角為正 ( 拇指指向坐標(biāo)軸的方向，其余四指指向旋轉(zhuǎn)方向 )，順時(shí)針旋轉(zhuǎn)為負(fù)。

16、4.三維圖形的級(jí)聯(lián)(組合)變換 對(duì)于復(fù)雜的三維圖形變換，也需要通過若干個(gè)變換矩陣的級(jí)聯(lián)才能實(shí)現(xiàn)。特別要注意的是變換的方法變換的方法和矩陣級(jí)聯(lián)的順序。矩陣級(jí)聯(lián)的順序。例:繞任意軸旋轉(zhuǎn)的問題。如圖所示，設(shè)空間一般位置的旋轉(zhuǎn)軸是AA， A的坐標(biāo)是(xA，yA，zA)，A的坐標(biāo)是(xA，yA，zA)，空間一點(diǎn)P(x，y，z)繞AA軸旋轉(zhuǎn)角到P(x，y,z)，即： x y z 1 = x y z 1TAR TAR 為繞任意軸的旋轉(zhuǎn)變換矩陣，它是由基本變換矩陣組合而成，我們的任務(wù)就是要構(gòu)造矩陣TAR ，步驟如下： XZYOP AAP 將點(diǎn)P與旋轉(zhuǎn)軸AA一直起作平移變換，使旋轉(zhuǎn)軸AA過原點(diǎn)，A與原點(diǎn)重合，其

17、變換矩陣為： 10100001000011AAAtzyxTXZYOAA 令A(yù)A軸首先繞X軸逆時(shí)針旋轉(zhuǎn)角，使其與XOZ平面共面，然后再繞Y軸順時(shí)針旋轉(zhuǎn)角，使其與Z軸重合，該變換矩陣為： 21000cos()0sin()00cossin001000sincos0sin()0cos()000010001rxyT 繞X軸旋轉(zhuǎn)角 繞Y軸旋轉(zhuǎn)角 其中，和角可通過旋轉(zhuǎn)軸的兩個(gè)端點(diǎn)的坐標(biāo)計(jì)算得到。 XZYOAAA1000010000cossin00sincosz3rT 將P點(diǎn)繞Z軸（即AA軸）旋轉(zhuǎn)角，變換矩陣為： 對(duì)步驟作逆變換，將AA旋轉(zhuǎn)回到原來的位置，變換矩陣為： 4xcos( )0sin( )01000

18、01000cos()sin()0sin( )0cos( )00sin()cos()000010001ry T 對(duì)步驟作逆變換，將旋轉(zhuǎn)軸平移回到原來的位置，變換矩陣為： 10100001000015AAAtzyxT上述五步連起來，便組成繞任意軸的旋轉(zhuǎn)變換矩陣： trrrt5yz4z3xy21ARTTTTTT4.4 4.4 窗口窗口視圖區(qū)變換視圖區(qū)變換 窗口窗口：為選擇圖形的局部而設(shè)置的一個(gè)區(qū)域，一般采用矩形。其作用類似于照相機(jī)的取景器。 視圖區(qū)視圖區(qū)：在圖形輸出設(shè)備上定義的用于輸出圖形的區(qū)域，一般也采用矩形。 窗口窗口視圖區(qū)變換視圖區(qū)變換：在窗口和視圖區(qū)確定以后，找出兩者之間的坐標(biāo)對(duì)應(yīng)關(guān)系，以便

19、實(shí)現(xiàn)兩者之間的映射。xyoW(窗口)xyoV(視圖區(qū))wxLwxRwyBwyTvxLvxRvyBvyT(wx,wy)(vx,vy) vx vxL wx wxL 由兩圖的比例關(guān)系： vxR vxL wxR wxL vy vyB wy wyB vyT vyB wyT wyB可得： vxR vxL wxR wxL vyT vyB wyT wyB = =vx = ( wx wxL ) + vxLvy = ( wy wyB ) + vyB若視圖區(qū)為規(guī)格化設(shè)備坐標(biāo)，即： vxR vxL = 1 ； vyT vyB = 1 vxL = 0 ； vyB = 0 則： wx wxL wxR wxL wy wyB

20、 wyT wyB然后，再?gòu)囊?guī)格化設(shè)備坐標(biāo)映射到具體的物理設(shè)備坐標(biāo)中。注意：當(dāng)視圖區(qū)和窗口在 x 方向和 y 方向上的伸縮比不同時(shí)，圖形映射后會(huì)發(fā)生畸變。vx =vy =xyo11V (視圖區(qū))規(guī)格化設(shè)備坐標(biāo)4.5 4.5 二維圖形的裁剪二維圖形的裁剪 當(dāng)用戶在平面上定義一個(gè)窗口之后，要把窗口內(nèi)的圖形映像到視圖區(qū)，而把窗口內(nèi)部分和窗口外部分正確無誤地分離開來，這種分離技術(shù)我們稱之為“裁剪”。 既然裁剪技術(shù)要將一個(gè)圖形窗口內(nèi)的部分和窗口外的部分分離開來，那么裁剪必然包括兩部分內(nèi)容： 1. 圖形上的點(diǎn)是否在窗口內(nèi)的判斷。 2. 求出圖形與窗口邊界的交點(diǎn)。 一一. . 二維線段裁剪方法二維線段裁剪方法

21、 規(guī)則的二維裁剪窗口(矩形)。 線段相對(duì)于該窗口的情況:線段全部位于窗口外部（B、C）線段全部位于窗口的內(nèi)部（A）線段的中間部分在窗口內(nèi)，而二端點(diǎn)在窗口外部（D）線段的一端在窗口內(nèi)，而另一端在窗口外（E）由上圖可知，點(diǎn)位于裁剪窗口之內(nèi)的條件是： xL x xR yB y yT x=xLx=xRy=yBy=yTABCDE1. Ivan Sutherland1. Ivan Sutherland算法算法( (編碼裁剪法編碼裁剪法) ) Ivan Sutherland算法也稱Sutherland-Cohen算法。 其核心思想是：分區(qū)編碼分區(qū)編碼和線段分割線段分割。 分區(qū)編碼方法： 以x=xL、x=xR

22、、y=yT、y=yB將圖形區(qū)域劃分成九個(gè)部分。采用四位編碼表示端點(diǎn)所處的位置：第一位為“1”時(shí)，表示點(diǎn)在y=yT的上方；第二位為“1”時(shí)，表示點(diǎn)在y=yB的下方；第三位為“1”時(shí)，表示點(diǎn)在x=xR的右方；第四位為“1”時(shí)，表示點(diǎn)在x=xL的左方。x=xLx=xRy=yBy=yT000000010010100001001001101001010110算法思想：算法思想： 1確定線段二端點(diǎn)P1和P2的代碼值C1和C2（經(jīng)一系列的判斷 p1（x1，y1），p2（x2，y2）和xR、xL、yT、yB的比較，分別給代碼中的各位賦值）。 2對(duì)線段的端點(diǎn)進(jìn)行檢測(cè) 若線段全部在窗口外(c1 and c2 0)

23、退出 若線段全部在窗口內(nèi)(c1= 0 且c2 = 0)畫線 否則(c10 or c20 且 c1 and c2 = 0)要對(duì)線段進(jìn)行分割，關(guān)鍵是求與窗口四邊的交點(diǎn)( 利用直線的兩點(diǎn)式方程 )。交點(diǎn)求出后，要對(duì)其重新編碼，并繼續(xù)判斷。例圖：P1P2C1=0001C2=0000P1P2C1=0100C2=0100P1P2C1=0101C2=1010P1P2ABCDC1=0000C2=00002.中點(diǎn)分割算法中點(diǎn)分割算法算法的思路： 采用與前相似的線段端點(diǎn)編碼和相應(yīng)的檢查方法，先判定完全不可見線段和完全可見線段。 否則，將線段分割成相等的兩段，然后對(duì)每一小段重復(fù)上述的檢查，直至找到每段與窗口邊界的交

24、點(diǎn)或分割小段的長(zhǎng)度充分小，可以視為一點(diǎn)時(shí)為止。 實(shí)際上，這相當(dāng)于采用對(duì)分查找法求交，分割次數(shù)最多不超過線段端點(diǎn)的表示精度。 以找出直線段AB上離端點(diǎn)A最遠(yuǎn)的可見點(diǎn)a為例。(1)排斥性測(cè)試 測(cè)試直線段AB是否完全被排斥在窗口之外。如果是，則無輸出線段，過程就此結(jié)束。否則，繼續(xù)進(jìn)行(2)。(2)包含性測(cè)試 測(cè)試B點(diǎn)是否包含在窗口之內(nèi)。如果是，則B點(diǎn)就是離A點(diǎn)最遠(yuǎn)的可見點(diǎn)a，過程退出。如果B點(diǎn)沒有被包含在窗口之內(nèi)，那么繼續(xù)執(zhí)行(3)。(3)分割直線段AB于中點(diǎn)M，并判斷。 若MB被完全排斥在窗口之外，那么便以線段AM為新的線段AB，并返回算法第(1)步重新開始測(cè)試。 若MB沒有被完全排斥在窗口之外，

25、那么便以線段MB作為新的線段AB，然后返回算法第(1)步重新開始測(cè)試。 反復(fù)執(zhí)行上述算法中的三步，直至找到離線段端點(diǎn)A最遠(yuǎn)的可見點(diǎn)a為止。 這個(gè)過程找到了距離端點(diǎn)A的最遠(yuǎn)的可見點(diǎn)a，而對(duì)直線段BA（把直線段的兩個(gè)端點(diǎn)對(duì)調(diào)一下）實(shí)施同樣的算法步驟，便可找到離端點(diǎn)B最遠(yuǎn)的可見點(diǎn)b。這樣，處于窗口內(nèi)的可見段的兩個(gè)端點(diǎn)便確定了。AbBaM算法中的關(guān)鍵點(diǎn)：算法中的關(guān)鍵點(diǎn)： 求離端點(diǎn)最遠(yuǎn)的可見點(diǎn)。 新求得的端點(diǎn)必需重新編碼（可采用子程序）。 線段的可見否均由端點(diǎn)的編碼狀態(tài)確定（可采用子程序）。特點(diǎn)特點(diǎn)：避免了復(fù)雜的乘除運(yùn)算；可采用并行算法。3. Liang(Liang(梁友棟梁友棟)-Barsky )-B

26、arsky 算法算法算法的基本思想： 從A、B和 P1三點(diǎn)中找出最靠近P2 的點(diǎn)( P1)，從C、D和 P2三點(diǎn)中找出最靠近 P1的點(diǎn)(C )，則 P1C 就是 P1P2 線段上的可見部分。將被裁剪的線段 P1P2 表示成參數(shù)方程形式： xx1xt 其中 xx2x1 yy1yt yy2y1xyxLxRyByTP1P2ABCD( 0 t 1 ) 另外，把窗口的四條邊分成二類：始邊和終邊。x0， xxL為始邊， xxR為終邊。y0，yyB為始邊，yyT為終邊。反之，x0， xxR為始邊， xxL為終邊。y0， yyT為始邊，yyB為終邊。求出P1P2和二條始邊的交點(diǎn)的參數(shù)t1和t1令 t1max

27、(t1，t1，0)則 t1 即為A、B、P1三點(diǎn)中最靠近P2的點(diǎn)的參數(shù)。求出P1P2和二條終邊的交點(diǎn)的參數(shù)t2和t2令 t2min (t2，t2，1)則 t2 即為C、D、P2三點(diǎn)中最靠近P1的點(diǎn)的參數(shù)。當(dāng) t2t1時(shí)，方程(1)中參數(shù)tt1,t2的線段就是P1P2的可見部分。當(dāng) t2 t1時(shí)，整個(gè)線段為不可見。xyxLxRyByTP1P2ABCD二二. . 字符裁剪方法字符裁剪方法1. 1. 字符的表示方法 點(diǎn)陣字符點(diǎn)陣字符每個(gè)字符用一個(gè)位圖(掩膜) 來表示，其大小由位圖的尺寸來確定，如 7 9，9 16，16 24 等。 1 1 1 1 0 0 0 0 1 0 0 1 0 00 1 0 0

28、 1 0 00 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 01 1 1 0 0 0 0 0 0 0 0 0 0 0P在字庫(kù)的表示P的顯示結(jié)果 矢量字符矢量字符 選一個(gè)正方形網(wǎng)格網(wǎng)格，作為字符的局部坐標(biāo)局部坐標(biāo)空間，網(wǎng)格的大小可選16 16，32 32，64 64等。每個(gè)字符由構(gòu)成它的筆畫筆畫組成，每個(gè)筆畫又由其兩端確定。每個(gè)端端點(diǎn)點(diǎn)保存它的坐標(biāo)值坐標(biāo)值及連線標(biāo)志連線標(biāo)志。xyop1p2p3p4p5p66363字符的編碼x1 y1 0 x2 y2 1x3 y3 0 x4 y4 1x5 y5 0 x6 y6 1 10表示不連線1表示連線

29、字符結(jié)束標(biāo)志特點(diǎn)特點(diǎn)：除用直線段表示筆畫外，還可采用二次三次曲線段。 對(duì)矢量字符的變換是對(duì)其端點(diǎn)進(jìn)行圖形的幾何變換。2. 字符的裁剪 簡(jiǎn)單裁剪方法： 用點(diǎn)陣字符的掩膜或矢量字符的網(wǎng)格大小作為字符的包圍框，若該包圍框在窗口內(nèi)，則顯示字符；否則，不予顯示。 精確裁剪方法： 對(duì)于點(diǎn)陣字符，判斷組成其筆畫的每個(gè)像素點(diǎn)是否位于窗口內(nèi)。 對(duì)于矢量字符，對(duì)組成其筆畫的每條線段進(jìn)行裁剪。3 3多邊形的裁剪多邊形的裁剪 平面多邊形是由若干直線段圍成的平面封閉圖形，因此裁剪后的結(jié)果仍應(yīng)是一個(gè)多邊形，即是封閉的圖形，而且仍應(yīng)保持原多邊形各邊的連接順序。 對(duì)于多邊形的裁剪要著重考慮下列問題：如何把多邊形落在窗口邊界上

30、的交點(diǎn)正確地、按序連接成裁剪后的多邊形，其中包括決定窗口邊界及拐角點(diǎn)地取舍。1Sutherland-Hodgman(S-H)算法 該算法的出發(fā)點(diǎn)是把一個(gè)解決復(fù)雜問題的全過程分解為幾個(gè)簡(jiǎn)單過程。其中的每個(gè)簡(jiǎn)單過程僅僅是完成一個(gè)單邊裁剪，所以每一個(gè)簡(jiǎn)單過程都是類似的重復(fù)，這樣就使復(fù)雜問題的解決方法最終得到簡(jiǎn)化。思路思路：將多邊形的各邊先相對(duì)于窗口的某一條邊界進(jìn)行裁剪，然后將裁剪結(jié)果再用另一條邊界進(jìn)行裁剪，如此重復(fù)多次，便可得到最終結(jié)果。實(shí)現(xiàn)方法實(shí)現(xiàn)方法：設(shè)置二個(gè)表 輸入頂點(diǎn)表(向量)用于存放被裁剪多邊形的頂點(diǎn)p1-pm。 輸出頂點(diǎn)表(線性鏈表)用于存放裁剪過程中及結(jié)果的頂 點(diǎn) q1-qn。輸入頂點(diǎn)

31、表中各頂點(diǎn)要求按一定順序排列，一般可采用順時(shí) 針或逆時(shí)針方向。相對(duì)于裁剪窗口的各條邊界，按頂點(diǎn)表中的順序，逐邊進(jìn)行 裁剪。具體操作具體操作： 讀入頂點(diǎn)Pi，除第一個(gè)頂點(diǎn)外，要檢查每一個(gè) Pi 和前一頂 點(diǎn) Pi-1是否位于窗口邊界的同一側(cè)，若不在同一側(cè)，則需計(jì)算出交點(diǎn)送輸出頂點(diǎn)表。 Pi 若位于邊界線的可見一側(cè)，則 Pi 送輸出頂點(diǎn)表 Pi 若位于邊界線的不可見一側(cè)，則將其舍棄。 最后一個(gè)頂點(diǎn)還要與第一個(gè)頂點(diǎn)一起進(jìn)行同樣的檢查。p1p2p3p4p5q1q2q3q4p1p3p4p5q1q2p3p4p5q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前： 裁剪后：輸入頂點(diǎn)表：p1p2p3p4p5 輸入頂點(diǎn)表: 不變輸出頂點(diǎn)表： 空 輸出頂點(diǎn)表: q3q1q2p3q7q8q5q6q4算法特點(diǎn)算法特點(diǎn)： 算法中相對(duì)于各窗口邊界的裁剪過程相同，且每次都是相對(duì)于前一次的結(jié)果進(jìn)行處理。 可采用遞歸遞歸算法，可不保留中間多邊形的頂點(diǎn)，而節(jié)省數(shù)據(jù)的存儲(chǔ)量，但遞歸會(huì)影響速度。q3q4q1q2p3p4q5q6q3q4q1q2p3S-H算法流程圖 單邊裁剪開 始Pi