第5章二維變換和二維觀察

1、第五章第五章 二維變換和二維觀察二維變換和二維觀察1二維變換內(nèi)容二維變換內(nèi)容n圖形變換預(yù)備知識(shí)圖形變換預(yù)備知識(shí)nBasic transformation（基本變換）（基本變換）nMatrix representation（矩陣表示）（矩陣表示）nOther 2D transformations （其他變換）（其他變換）nComposite transformation（復(fù)合變換）（復(fù)合變換）nTransformation between Coordinate Systems（坐標(biāo)系間的變換）（坐標(biāo)系間的變換）nRaster method of transformation（變換（變換的光柵方法

2、）的光柵方法）25.1 5.1 圖形變換預(yù)備知識(shí)圖形變換預(yù)備知識(shí)n 矢量n矢量和 zyxuuuUzyxvvvVzzyyxxvuvuvuVU5.1.1 矢量和矩陣矢量和矩陣3n矢量的數(shù)乘 n矢量的點(diǎn)積n性質(zhì)zyxkukukuUkzzyyxxvuvuvuVUUVVUVUVU000UUU4n矢量的長度 n單位矢量 n矢量的夾角n矢量的叉積 222zyxuuuUUUVUVUcoszyxzyxvvvuuukjiVU5n矩陣 n 階矩陣nn階方陣n零矩陣n行向量與列向量n單位矩陣n矩陣的加法 n矩陣的數(shù)乘 n矩陣的乘法 n矩陣的轉(zhuǎn)置 n矩陣的逆 m n6矩陣的含義矩陣：由mn個(gè)數(shù)按一定位置排列的一個(gè) 整體

3、，簡稱mn矩陣。mnmmnnaaaaaaaaa . . . . . . 21222211 1211A=7矩陣運(yùn)算n加法設(shè)A，B為兩個(gè)具有相同行和列元素的矩陣A+B = n數(shù)乘kA = k*aij|i=1.m, j=1,. n . b . . . . b m22111112121111mnmnmmmnnbaababaaba8n乘法設(shè)A為32矩陣，B為23矩陣 C = A B = C=Cmp = Am n Bnp cij = aik*bkjn單位矩陣 在一矩陣中，其主對(duì)角線各元素aii=1,其余皆為0的矩陣稱為單位矩陣。n階單位矩陣通常記作In 。 Am n = Am n In babab aba

4、babababababababa322322221221312321221121321322121211311321121111 k=1,n9n逆矩陣若矩陣A存在AA-1=A-1A=I，則稱A-1為A的逆矩陣n矩陣的轉(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是對(duì)稱矩陣。10矩陣運(yùn)算的基本性質(zhì)n交換律與結(jié)合律 A+B=B+A; A+(B+C)=(A+B)+Cn數(shù)乘的分配律及結(jié)合律 a(A+B) = aA+a

5、B; a(A B) = (aA) B=A (aB) (a+b)A = aA + bA a(bA) = (ab)A11n矩陣乘法的結(jié)合律及分配律 A(B C) = (A B)C (A+B) C = A C+ B C C (A+B) = C A + C Bn矩陣的乘法不適合交換律12所謂所謂齊次坐標(biāo)表示法齊次坐標(biāo)表示法就是由就是由n+1維向量表示一個(gè)維向量表示一個(gè)n維向量。如維向量。如n維向量維向量(P1,P2, ,Pn)表示為（表示為（hP1,hP2,hPn,h），其中），其中h稱為稱為啞坐標(biāo)。啞坐標(biāo)。1. h可以取不同的值，所以同一點(diǎn)的齊次坐標(biāo)不是唯一的。如可以取不同的值，所以同一點(diǎn)的齊次坐標(biāo)

6、不是唯一的。如普 通 坐 標(biāo) 系 下 的 點(diǎn) （普 通 坐 標(biāo) 系 下 的 點(diǎn) （ 2 , 3 ） 變 換 為 齊 次 坐 標(biāo) 可 以 是） 變 換 為 齊 次 坐 標(biāo) 可 以 是(1,1.5,0.5)(4,6,2)(6,9,3)等等。等等。2. 普通坐標(biāo)與齊次坐標(biāo)的關(guān)系為普通坐標(biāo)與齊次坐標(biāo)的關(guān)系為“一對(duì)多一對(duì)多”由普通坐標(biāo)由普通坐標(biāo) h齊次坐標(biāo)齊次坐標(biāo)由齊次坐標(biāo)由齊次坐標(biāo)h普通坐標(biāo)普通坐標(biāo)3. 當(dāng)當(dāng)h=1時(shí)產(chǎn)生的齊次坐標(biāo)稱為時(shí)產(chǎn)生的齊次坐標(biāo)稱為“規(guī)格化坐標(biāo)規(guī)格化坐標(biāo)”，因?yàn)榍埃驗(yàn)榍皀個(gè)個(gè)坐標(biāo)就是普通坐標(biāo)系下的坐標(biāo)就是普通坐標(biāo)系下的n維坐標(biāo)。維坐標(biāo)。5.1.2 齊次坐標(biāo)齊次坐標(biāo)13(x,y)

7、點(diǎn)對(duì)應(yīng)的齊次坐標(biāo)為 (x,y)點(diǎn)對(duì)應(yīng)的齊次坐標(biāo)為三維空間的一條直線 (, )xyhhh0,hhyyhxxhhhzhyyhxxhhh141. 1. 將各種變換用階數(shù)統(tǒng)一的矩陣來表示。提供了用矩陣運(yùn)將各種變換用階數(shù)統(tǒng)一的矩陣來表示。提供了用矩陣運(yùn)算把二維、三維甚至高維空間上的一個(gè)點(diǎn)從一個(gè)坐標(biāo)系算把二維、三維甚至高維空間上的一個(gè)點(diǎn)從一個(gè)坐標(biāo)系變換到另一坐標(biāo)系的有效方法。變換到另一坐標(biāo)系的有效方法。2. 2. 便于表示無窮遠(yuǎn)點(diǎn)。便于表示無窮遠(yuǎn)點(diǎn)。例如：（例如：（x x h, y h, y h, h) h, h)，令，令h h等于等于0 03. 3. 齊次坐標(biāo)變換矩陣形式把直線變換成直線段，平面變換齊次

8、坐標(biāo)變換矩陣形式把直線變換成直線段，平面變換成平面，多邊形變換成多邊形，多面體變換成多面體。成平面，多邊形變換成多邊形，多面體變換成多面體。4. 變換具有統(tǒng)一表示形式的優(yōu)點(diǎn)變換具有統(tǒng)一表示形式的優(yōu)點(diǎn)n便于變換合成便于變換合成n便于硬件實(shí)現(xiàn)便于硬件實(shí)現(xiàn)齊次坐標(biāo)的作用齊次坐標(biāo)的作用15圖形變換是計(jì)算機(jī)圖形學(xué)基礎(chǔ)內(nèi)容之一。圖形變換是計(jì)算機(jī)圖形學(xué)基礎(chǔ)內(nèi)容之一。幾何變換，投影變換，視窗變換幾何變換，投影變換，視窗變換線性變換，屬性不變，拓?fù)潢P(guān)系不變。線性變換，屬性不變，拓?fù)潢P(guān)系不變。作用：作用：n把用戶坐標(biāo)系與設(shè)備坐標(biāo)系聯(lián)系起來；把用戶坐標(biāo)系與設(shè)備坐標(biāo)系聯(lián)系起來；n可由簡單圖形生成復(fù)雜圖形；可由簡單圖形

9、生成復(fù)雜圖形；n可用二維圖形表示三維形體；可用二維圖形表示三維形體；n動(dòng)態(tài)顯示。動(dòng)態(tài)顯示。5.1.3 圖形變換圖形變換16圖形的幾何變換圖形的幾何變換n圖形變換：對(duì)圖形的幾何信息經(jīng)過幾何變換后產(chǎn)生新圖形變換：對(duì)圖形的幾何信息經(jīng)過幾何變換后產(chǎn)生新的圖形。的圖形。n圖形變換的兩種形式：圖形變換的兩種形式：1.圖形不變，坐標(biāo)系改變；圖形不變，坐標(biāo)系改變；2.圖形圖形改變，坐標(biāo)系不變。改變，坐標(biāo)系不變。n我們所討論的是針對(duì)坐標(biāo)系的改變而講的。我們所討論的是針對(duì)坐標(biāo)系的改變而講的。 175.2 基本二維變換內(nèi)容基本二維變換內(nèi)容n圖形變換預(yù)備知識(shí)圖形變換預(yù)備知識(shí)nBasic transformation（

10、基本變換）（基本變換）nMatrix representation（矩陣表示）（矩陣表示）nOther 2D transformations （其他變換）（其他變換）nComposite transformation（復(fù)合變換）（復(fù)合變換）nTransformation between Coordinate Systems（坐標(biāo)系間的變換）（坐標(biāo)系間的變換）nRaster method of transformation（變換（變換的光柵方法）的光柵方法）185.2 Basic Transformations基本變換基本變換nDef. 改變改變對(duì)象對(duì)象坐標(biāo)描述坐標(biāo)描述的變換稱為幾何變換，例如的

11、變換稱為幾何變換，例如改變對(duì)象的方向、尺寸和形狀。改變對(duì)象的方向、尺寸和形狀。 nDef. Geometric transformations alter coordinate descriptions of objects, such as changes in orientation, size and shape.nTypesnTranslation平移平移nRotation旋轉(zhuǎn)旋轉(zhuǎn)nScaling變比變比195.2.1 2D 平移平移nTranslation平移平移nDef. 圖形對(duì)象沿直線運(yùn)動(dòng)產(chǎn)生的圖形對(duì)象沿直線運(yùn)動(dòng)產(chǎn)生的變換變換nParameters:平移平移向向量量(tx, ty

12、)nFormula:x = x+txy = y+tyxyPP20n矩陣表示矩陣表示 x x txP= P= T= y y tyP = P + TxyPP215010050100(-20，20)308070120 xyxyExample225.2.2 2D 旋轉(zhuǎn)旋轉(zhuǎn)nRotation旋轉(zhuǎn)旋轉(zhuǎn)nDef.圖形對(duì)象沿圓弧路徑運(yùn)動(dòng)產(chǎn)生的變換圖形對(duì)象沿圓弧路徑運(yùn)動(dòng)產(chǎn)生的變換nParametersn基準(zhǔn)點(diǎn)基準(zhǔn)點(diǎn)(pivot)(pivot)，坐標(biāo)原點(diǎn)或任意點(diǎn)，坐標(biāo)原點(diǎn)或任意點(diǎn)n旋轉(zhuǎn)角旋轉(zhuǎn)角n方向方向, ,約定：約定：逆時(shí)針逆時(shí)針為正為正23xy(x,y)(x,y)rxy(x,y)(x,y)r(Xr,Yr)繞原

13、點(diǎn)旋轉(zhuǎn)繞原點(diǎn)旋轉(zhuǎn)繞任意點(diǎn)旋轉(zhuǎn)繞任意點(diǎn)旋轉(zhuǎn)24nFormula 針對(duì)坐標(biāo)原點(diǎn)針對(duì)坐標(biāo)原點(diǎn)x=x*cos- y*sin y= x*sin+ y*cosn 如何得到上述公式如何得到上述公式?n 針對(duì)任意點(diǎn)針對(duì)任意點(diǎn)(xr, yr)旋轉(zhuǎn)的計(jì)算公式旋轉(zhuǎn)的計(jì)算公式?xyPP x=r*cos(+ ) =r*(cos *cos-sin*sin) =rcos*cos - rsin*sin = x*cos- y*sin y=r*sin(+ )=r*(cos*sin+sin*cos) =rcos*sin + rsin*cos = x*sin+ y*cos25n矩陣表示矩陣表示 x x cos - -sin P= P

14、= R= y y sin cos P = R P26xy旋轉(zhuǎn)旋轉(zhuǎn)也是一種也是一種不產(chǎn)生變形而不產(chǎn)生變形而移動(dòng)對(duì)象的剛移動(dòng)對(duì)象的剛體變換。體變換。27nScaling變比變比nDef. 改變改變圖形對(duì)象大小的變換圖形對(duì)象大小的變換nParameters:變比因子變比因子(Sx, Sy), 基準(zhǔn)點(diǎn)，方向基準(zhǔn)點(diǎn)，方向nFormula: 針對(duì)坐標(biāo)原點(diǎn)針對(duì)坐標(biāo)原點(diǎn) 針對(duì)固定參考點(diǎn)針對(duì)固定參考點(diǎn)(xf,yf)x=x*Sxx=xf+(x-xf)*Sxy=y*Sy y=yf+(y-yf)*Sy5.2.3 2D 變比（縮放）變比（縮放）28n矩陣表示矩陣表示 x x sx 0 P= P= S= y y 0 sy

15、 P = S P2911(2，1)12xyxy1Example302D變比變比討論討論n如果如果|Sx|或或|Sy|大于大于1，則表示圖形在，則表示圖形在X軸方向或軸方向或Y軸方向放大；軸方向放大；n如果如果|Sx|或或|Sy|小于小于1，則表示圖形在，則表示圖形在X軸方向或軸方向或Y軸方向縮??；軸方向縮??；n如果如果|Sx|=|Sy|，則表示均勻縮放；，則表示均勻縮放；n如果如果|Sx|Sy|，則表示差值縮放；，則表示差值縮放；n如果如果|Sx|或或|Sy|等于等于1，則表示圖形在，則表示圖形在X軸方向或軸方向或Y軸方向不變；軸方向不變；n如果如果Sx或或Sy小于零，則表示圖形在小于零，則表

16、示圖形在X軸方向或軸方向或Y軸軸方向作鏡面變換。方向作鏡面變換。31二維變換內(nèi)容二維變換內(nèi)容n圖形變換預(yù)備知識(shí)圖形變換預(yù)備知識(shí)nBasic transformation（基本變換）（基本變換）nMatrix representation（矩陣表示）（矩陣表示）nOther 2D transformations （其他變換）（其他變換）nComposite transformation（復(fù)合變換）（復(fù)合變換）nTransformation between Coordinate Systems（坐標(biāo)系間的變換）（坐標(biāo)系間的變換）nRaster method of transformation（變換

17、（變換的光柵方法）的光柵方法）325.2.4 2D 矩陣表示矩陣表示 n在圖形系統(tǒng)中，矩陣式實(shí)現(xiàn)變換的標(biāo)準(zhǔn)方法。在圖形系統(tǒng)中，矩陣式實(shí)現(xiàn)變換的標(biāo)準(zhǔn)方法。nP P = P+T (= P+T (平移平移););nP P = R= RP (P (旋轉(zhuǎn)旋轉(zhuǎn)););nP P = S= SP P ( (變比變比););n對(duì)于平移、旋轉(zhuǎn)和縮放變換，每個(gè)基本的變換都可表示為對(duì)于平移、旋轉(zhuǎn)和縮放變換，每個(gè)基本的變換都可表示為普通距陣形式：普通距陣形式：P = M1 * P + M2 采用齊次坐標(biāo)采用齊次坐標(biāo)(xh, yh, h)表示每個(gè)表示每個(gè)2D坐標(biāo)位置坐標(biāo)位置(x,y)齊次坐標(biāo)表示就是用齊次坐標(biāo)表示就是用n

18、+1維向量表示維向量表示n維向量。維向量。P = M * P335.2.4 2D 矩陣表示矩陣表示 nPoint (x,y) - (xh, yh, h) - (x, y, 1)Tn2D graph - 3xnn基本變換參數(shù)基本變換參數(shù) - 3x3n2D 圖形變換坐標(biāo)計(jì)算：圖形變換坐標(biāo)計(jì)算： P最終坐標(biāo)最終坐標(biāo) = M變換矩陣變換矩陣* P原坐標(biāo)原坐標(biāo)34n平移變換平移變換 x 1 0 tx xy = 0 1 ty y 1 0 0 1 1 P=T(tx,ty)*P 舉例35n旋轉(zhuǎn)變換旋轉(zhuǎn)變換 x cos - sin 0 x y = sin cos 0 y 1 0 0 1 1 P=R()*P 舉例

19、36n變比變換變比變換 x sx 0 0 xy = 0 sy 0 y 1 0 0 1 1 P=S(sx,sy)*P 注意：上述三種都是針對(duì)坐標(biāo)原點(diǎn)和X/Y軸方向的。 舉例37nBasic transformation（基本變換）（基本變換）nMatrix representation（矩陣表示）（矩陣表示）nOther 2D transformations （其他變換）（其他變換）nComposite transformation（復(fù)合變換）（復(fù)合變換）nTransformation between Coordinate Systems（坐標(biāo)系間的變換）（坐標(biāo)系間的變換）nRaster met

20、hod of transformation（變換（變換的光柵方法）的光柵方法）二維變換內(nèi)容二維變換內(nèi)容385.2.5 2D 其他變換其他變換 nReflections反射反射(對(duì)稱對(duì)稱)nReflection about x-axis X軸反射軸反射nReflection about y-axis Y軸反射軸反射nReflection about (0,0) 原點(diǎn)反射原點(diǎn)反射nReflection about x=y 45度線反射度線反射nShearing錯(cuò)切錯(cuò)切nshearing in x X方向錯(cuò)切方向錯(cuò)切nshearing in y Y方向錯(cuò)切方向錯(cuò)切391. Reflection反射（

21、對(duì)稱）反射（對(duì)稱）about x-axis 1 0 0 0 -1 0 0 0 1 yx123231X軸坐標(biāo)不變Y軸坐標(biāo)變反40about y-axis -1 0 0 0 1 0 0 0 1 xy123132Y軸坐標(biāo)不變X軸坐標(biāo)變反41about (0,0) -1 0 0 0 -1 0 0 0 1 xy123132X軸坐標(biāo)變反Y軸坐標(biāo)變反繞原點(diǎn)旋轉(zhuǎn)18042About x=y 0 1 0 1 0 0 0 0 1 xyy=x1212X,Y坐標(biāo)互換位置舉例432. shearing錯(cuò)切錯(cuò)切(X/Y方向的拉伸方向的拉伸) 1 SHx 0 0 1 0 0 0 1 xy112 3(2,1)(3,1)xy1

22、1SHx=2(1,1)44 1 0 0 SHy 1 0 0 0 1 xy11232(1,3)(1,2)xy11SHy=2(1,1)舉例45nBasic transformation（基本變換）（基本變換）nMatrix representation（矩陣表示）（矩陣表示）nOther 2D transformations （其他變換）（其他變換）nComposite transformation（復(fù)合變換）（復(fù)合變換）nTransformation between Coordinate Systems（坐標(biāo)系間的變換）（坐標(biāo)系間的變換）nRaster method of transformat

23、ion（變換（變換的光柵方法）的光柵方法）二維變換內(nèi)容二維變換內(nèi)容465.3 二維二維復(fù)合復(fù)合變換變換 n進(jìn)行一次以上的基本變換進(jìn)行一次以上的基本變換 復(fù)合變換復(fù)合變換n利用矩陣表示，就可通過計(jì)算單個(gè)變換的矩陣?yán)镁仃嚤硎?，就可通過計(jì)算單個(gè)變換的矩陣乘積，將任意順序變換的矩陣建立為乘積，將任意順序變換的矩陣建立為組合變換組合變換矩陣矩陣。n形成變換矩陣的乘積被稱為矩陣的合并形成變換矩陣的乘積被稱為矩陣的合并(concatenation)或復(fù)合或復(fù)合(composition) 475.3 復(fù)合變換復(fù)合變換 nTranslations 連續(xù)平移連續(xù)平移nRotations 連續(xù)旋轉(zhuǎn)連續(xù)旋轉(zhuǎn)nSca

24、lings 連續(xù)變比連續(xù)變比nGeneral pivot-point transformations 通用基準(zhǔn)點(diǎn)的變換通用基準(zhǔn)點(diǎn)的變換nGeneral Directions transformations 通用方向的變換通用方向的變換485.3.1 Translations 連續(xù)連續(xù)平移平移 nn個(gè)連續(xù)的平移向量個(gè)連續(xù)的平移向量(tx1 , ty1),(tx2 , ty2), ,(txn , tyn)被用被用于點(diǎn)于點(diǎn)P，那么最后的點(diǎn)坐標(biāo)可計(jì)算為，那么最后的點(diǎn)坐標(biāo)可計(jì)算為 P = T(txn, tyn)* T(tx2, ty2) *T(tx1, ty1) P = T(txn, tyn)* T(t

25、x2, ty2) *T(tx1, ty1) P n計(jì)算時(shí)，可先計(jì)算兩個(gè)平移變換矩陣的乘積計(jì)算時(shí)，可先計(jì)算兩個(gè)平移變換矩陣的乘積 T(tx2, ty2) T(tx1, ty1) = T(tx2 + tx1, ty2+ ty1)n連續(xù)平移是可加的連續(xù)平移是可加的49n平移變換平移變換 x 1 0 tx 1 0 tx1y = 0 1 ty 0 1 ty1 *P 1 0 0 1 0 0 1 1 0 tx+ tx1 P= 0 1 ty+ ty1 *P0 01舉例505.3.2 Rotations 連續(xù)連續(xù)旋轉(zhuǎn)旋轉(zhuǎn) n應(yīng)用于點(diǎn)應(yīng)用于點(diǎn)P的的n個(gè)連續(xù)旋轉(zhuǎn)個(gè)連續(xù)旋轉(zhuǎn)(1), (2). (n)，得到，得到的點(diǎn)的

26、點(diǎn)P的坐標(biāo)可計(jì)算為的坐標(biāo)可計(jì)算為 P = R(n) * R(2) R(1) P = R(n) * R(2) R(1) P nR(2) R(1)= R(1+2) 則則P的坐標(biāo)可計(jì)算為的坐標(biāo)可計(jì)算為 P = R(1+2) Pn連續(xù)旋轉(zhuǎn)是可加的連續(xù)旋轉(zhuǎn)是可加的. 自己推導(dǎo)。自己推導(dǎo)。舉例515.3.3 Scalings 連續(xù)連續(xù)變比變比 nn個(gè)連續(xù)縮放操作個(gè)連續(xù)縮放操作S(sx1, sy1), S(sx2, sy2), S(sxn, syn)的變換距陣連接，產(chǎn)生的組合變換距陣的變換距陣連接，產(chǎn)生的組合變換距陣 P= S(sxn, syn)* S(sx2, sy2)* S(sx1, sy1)*Pn S

27、(sx2, sy2) *S(sx1, sy1) = S(sx1*sx2, sy1*sy1) n連續(xù)縮放操作是相乘的連續(xù)縮放操作是相乘的，非疊加的，非疊加的，自己推導(dǎo)自己推導(dǎo)。n前三個(gè)基本變換是針對(duì)原點(diǎn)和前三個(gè)基本變換是針對(duì)原點(diǎn)和X,Y軸的。軸的。舉例525.3.4 通用基準(zhǔn)點(diǎn)變換通用基準(zhǔn)點(diǎn)變換nSolution 平移使基準(zhǔn)點(diǎn)移動(dòng)到坐標(biāo)原點(diǎn)平移使基準(zhǔn)點(diǎn)移動(dòng)到坐標(biāo)原點(diǎn)(T) 針對(duì)原點(diǎn)做指定變換針對(duì)原點(diǎn)做指定變換(M) 反向平移使基準(zhǔn)點(diǎn)回到原始位置反向平移使基準(zhǔn)點(diǎn)回到原始位置(T-1)53Example 1 針對(duì)固定點(diǎn)變比針對(duì)固定點(diǎn)變比 xy(xf,yf)yxxyxy 1 0 xf 0 1 yf 0

28、 0 1 sx 0 0 0 sy 0 0 0 1 1 0 -xf 0 1 -yf 0 0 154Example 2 針對(duì)固定點(diǎn)旋轉(zhuǎn)針對(duì)固定點(diǎn)旋轉(zhuǎn) 1 0 xf 0 1 yf 0 0 1xy(xf,yf)yx cos - sin 0 sin cos 0 0 0 1 1 0 -xf 0 1 -yf 0 0 1xyxy55通用基準(zhǔn)點(diǎn)變換通用基準(zhǔn)點(diǎn)變換旋轉(zhuǎn)旋轉(zhuǎn)nExamples 5-1n將三角形沿基準(zhǔn)點(diǎn)將三角形沿基準(zhǔn)點(diǎn)(2,3)逆時(shí)針旋轉(zhuǎn)逆時(shí)針旋轉(zhuǎn) 45o. 寫出寫出其變換矩陣和變換過程，其變換矩陣和變換過程， 并給出頂點(diǎn)并給出頂點(diǎn)a(4,8)變變化后的坐標(biāo)值?；蟮淖鴺?biāo)值。nSolution 平移使

29、基準(zhǔn)點(diǎn)移動(dòng)到坐標(biāo)原點(diǎn)平移使基準(zhǔn)點(diǎn)移動(dòng)到坐標(biāo)原點(diǎn)T1=T(-2，-3); 繞原點(diǎn)做旋轉(zhuǎn)變換繞原點(diǎn)做旋轉(zhuǎn)變換 R=R(45); 反向平移反向平移，使基準(zhǔn)點(diǎn)回到原始位置使基準(zhǔn)點(diǎn)回到原始位置T2=T(2，3)56xy(xf,yf)575.3.5 通用方向變換通用方向變換nSolution 旋轉(zhuǎn)對(duì)象使任意方向與坐標(biāo)軸方向重合旋轉(zhuǎn)對(duì)象使任意方向與坐標(biāo)軸方向重合 針對(duì)坐標(biāo)軸方向做指定變換針對(duì)坐標(biāo)軸方向做指定變換 反向旋轉(zhuǎn)使任意方向回到原方向反向旋轉(zhuǎn)使任意方向回到原方向nExample 5-2xyS2S158Example 5-2 通用方向的縮放變換通用方向的縮放變換cos-45 sin-45 0Sin-45

30、 cos-45 0 0 0 1 1 0 0 0 2 0 0 0 1xyS2S1xy11S1=1, S2=2=45x11ycos45 -sin45 0sin45 cos45 0 0 0 159 3/2 1/2 0 1/2 3/2 0 0 0 1M= 0 3/2 2 1/2 0 1/2 2 3/2 1 1 1 1P=M * 0 1 1 0 0 0 1 1 1 1 1 1=60Example 5-2 通用方向的縮放變換通用方向的縮放變換x11y x rsxx rsxy trsx xy = rsyx rsyy trsy y 1 0 0 1 1 5.3.6 二維變換總結(jié)二維變換總結(jié)通用復(fù)合變換通用復(fù)合變

31、換61n 二維空間中某點(diǎn)的變換矩陣可以表示成點(diǎn)的齊次二維空間中某點(diǎn)的變換矩陣可以表示成點(diǎn)的齊次坐標(biāo)矩陣與坐標(biāo)矩陣與3階方陣階方陣T2D相乘，其中相乘，其中T2D又被稱為二又被稱為二維齊次坐標(biāo)變換矩陣，簡稱維齊次坐標(biāo)變換矩陣，簡稱二維變換矩陣二維變換矩陣。源代碼由 king 創(chuàng)建二維變換內(nèi)容二維變換內(nèi)容nBasic transformation（基本變換）（基本變換）nMatrix representation（矩陣表示）（矩陣表示）nOther 2D transformations （其他變換）（其他變換）nComposite transformation（復(fù)合變換）（復(fù)合變換）nTransf

32、ormation between Coordinate Systems（坐標(biāo)系間的變換）（坐標(biāo)系間的變換）nRaster method of transformation（變換（變換的光柵方法）的光柵方法）76 坐標(biāo)系間的變換坐標(biāo)系間的變換xyxyx0y0 平移平移 (x0,y0) 到到 (0,0) 旋轉(zhuǎn)旋轉(zhuǎn) 軸軸x使與使與x軸重合軸重合M = R(- ) * T(-x0,-y0)77xyxyx0y0 y方向的單位矢量方向的單位矢量v= V/|V| = (vx,vy)V順旋順旋90度獲得度獲得x的單位矢量的單位矢量u=(vy,-vx) = (ux,uy) ux uy 0R= vx vy 0 0

33、 0 1V78二維變換內(nèi)容二維變換內(nèi)容nBasic transformation（基本變換）（基本變換）nMatrix representation（矩陣表示）（矩陣表示）nOther 2D transformations （其他變換）（其他變換）nComposite transformation（復(fù)合變換）（復(fù)合變換）nTransformation between Coordinate Systems（坐標(biāo)系間的變換）（坐標(biāo)系間的變換）nRaster method of transformation（變換（變換的光柵方法）的光柵方法）795.4 二維觀察二維觀察n2D Viewing Pip

34、eline（二維觀察流程）（二維觀察流程）nClipping Window（裁剪窗口）（裁剪窗口）nViewport（視點(diǎn)）（視點(diǎn)）n2D Clipping（二維裁剪）（二維裁剪）nPoint clipping（點(diǎn)裁剪）（點(diǎn)裁剪）nLine clipping（線段裁剪）（線段裁剪）nArea clipping（多邊形裁剪）（多邊形裁剪）nText clipping（文字裁剪）（文字裁剪）805.4.1 二維觀察流程二維觀察流程nDef. 常規(guī)圖形系統(tǒng)中，世界坐標(biāo)系中指定的用于常規(guī)圖形系統(tǒng)中，世界坐標(biāo)系中指定的用于顯示的坐標(biāo)區(qū)域顯示的坐標(biāo)區(qū)域- 裁剪窗口裁剪窗口(clipping window)

35、或或窗口窗口(window)nDef. 顯示設(shè)備上用于窗口映射的坐標(biāo)區(qū)域顯示設(shè)備上用于窗口映射的坐標(biāo)區(qū)域- 視視區(qū)、視口區(qū)、視口(viewport)。nDef. 通常，世界坐標(biāo)系中部分場(chǎng)景映射到設(shè)備坐通常，世界坐標(biāo)系中部分場(chǎng)景映射到設(shè)備坐標(biāo)系的過程標(biāo)系的過程-觀察觀察(視圖、視像視圖、視像)變換變換。81n世界坐標(biāo)系世界坐標(biāo)系(World Coordinates) 圖形定義時(shí)所采用的坐標(biāo)系，坐標(biāo)的大小和尺寸圖形定義時(shí)所采用的坐標(biāo)系，坐標(biāo)的大小和尺寸由用戶確定。由用戶確定。n設(shè)備坐標(biāo)系設(shè)備坐標(biāo)系(Device Coordinates) 與一個(gè)圖形設(shè)備相關(guān)的坐標(biāo)系叫設(shè)備坐標(biāo)系。如與一個(gè)圖形設(shè)備相關(guān)

36、的坐標(biāo)系叫設(shè)備坐標(biāo)系。如顯示器或打印機(jī)有它們自己的坐標(biāo)系。顯示器或打印機(jī)有它們自己的坐標(biāo)系。n規(guī)范化坐標(biāo)系規(guī)范化坐標(biāo)系(Normalized Coordinates) 它是獨(dú)立于具體物理設(shè)備的一種坐標(biāo)系，其顯示它是獨(dú)立于具體物理設(shè)備的一種坐標(biāo)系，其顯示空間在空間在X和和Y方向上都是從方向上都是從0到到1坐標(biāo)系坐標(biāo)系82設(shè)備坐標(biāo)系設(shè)備坐標(biāo)系xyv1v2v3v4視口視口xyw1w2w3w4窗口窗口世界坐標(biāo)系世界坐標(biāo)系83111繪圖儀繪圖儀其他輸出設(shè)備其他輸出設(shè)備建模坐標(biāo)建模坐標(biāo)世界坐標(biāo)世界坐標(biāo)規(guī)范化坐標(biāo)規(guī)范化坐標(biāo)設(shè)備坐標(biāo)設(shè)備坐標(biāo)84窗口窗口-視口變換視口變換xyw1w2w3w4窗口窗口(xw,yw

37、)xyv1v2v3v4視口視口(xv,yv)85保持視口與窗口中的對(duì)象具有同樣的相對(duì)位置，保持視口與窗口中的對(duì)象具有同樣的相對(duì)位置，必須滿足必須滿足 (Xw-W1) / (W2-W1) = (Xv-V1) / (V2-V1) (Yw-W3) / (W4-W3) = (Yv-V3) / (V4-V3)窗口窗口-視口變換視口變換86 Xv = SxXw+tx Yv = SyYw+ty縮放系數(shù)縮放系數(shù) Sx = (V2-V1) / (W2-W1) Sy = (V4-V3) / (W4-W3)平移參數(shù)平移參數(shù) tx = (W2*V1-W1*V2) / (W2-W1) ty = (W4*V3-W3*V4

38、) / (W4-W3)87n已知已知w1=10,w2=20,w3=40,w4=80, v1=80,v2=110,v3=10,v4=130, 窗口中一點(diǎn)窗口中一點(diǎn)P(15，60)，求視區(qū)中的映射點(diǎn)，求視區(qū)中的映射點(diǎn)P?n解：解：(15-10)/(20-10) = (xv-80)/(110-80) (60-40)/(80-40) = (yv-10)/(130-10)n xv = 95, yv=70Example88二維觀察內(nèi)容二維觀察內(nèi)容n2D Viewing Pipeline（二維觀察流程）（二維觀察流程）nClipping WindownViewportn2D Clipping（二維裁剪）（二

39、維裁剪）nPoint clippingnLine clippingnArea clippingnText clipping895.4.4 2D裁剪裁剪n裁剪定義Clipping 識(shí)別圖形在指定區(qū)域內(nèi)或區(qū)域外的過程-裁剪n裁剪的時(shí)機(jī) (1) 針對(duì)窗口邊界裁剪 (2) 針對(duì)視區(qū)邊界裁剪90n裁剪類型裁剪類型n點(diǎn)裁剪點(diǎn)裁剪n直線裁剪直線裁剪n多邊形多邊形區(qū)域區(qū)域裁剪裁剪n曲線裁剪（自學(xué)）曲線裁剪（自學(xué)）n文文字字裁剪裁剪915.4.5 點(diǎn)的裁剪點(diǎn)的裁剪點(diǎn)點(diǎn)(x,y)如果滿足下列不如果滿足下列不等式則保留：等式則保留： w1 = x = w2 w3 = y = w4w1w2w3w4(x,y)925.4

40、.6 直線段的裁剪直線段的裁剪93假定直線段用假定直線段用p1(x1,y1)p2(x2,y2)表示。表示。n直線段和剪裁窗口的可能關(guān)系：直線段和剪裁窗口的可能關(guān)系：n完全落在窗口內(nèi)（完全可見）完全落在窗口內(nèi)（完全可見）n完全落在窗口外（顯然不可見）完全落在窗口外（顯然不可見）n與窗口邊界相交與窗口邊界相交窗口窗口 直線段與窗口的關(guān)系直線段與窗口的關(guān)系A(chǔ) AB BC CD DE EF FH HG GI IJ J94實(shí)交點(diǎn)實(shí)交點(diǎn)是直線段與窗口是直線段與窗口矩形邊界的交點(diǎn)。矩形邊界的交點(diǎn)。虛交點(diǎn)虛交點(diǎn)則是直線段與窗則是直線段與窗口矩形邊界延長線或直口矩形邊界延長線或直線段的延長線與窗口矩線段的延長線

41、與窗口矩形邊界的交點(diǎn)。形邊界的交點(diǎn)。窗口 實(shí)交點(diǎn)與虛交點(diǎn)ABCDEFHGIJ虛交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)虛交點(diǎn)虛交點(diǎn)95nCohen-Sutherland直線裁剪算法直線裁剪算法nLiang梁友棟梁友棟-Barsky直線裁剪算法直線裁剪算法n中點(diǎn)分割算法中點(diǎn)分割算法nNicholl-Lee-Nicholl直線裁剪算法直線裁剪算法nCyrus-Beck算法（自學(xué)）算法（自學(xué)）直線段的裁剪算法直線段的裁剪算法961. Cohen-Sutherland直線裁剪算法直線裁剪算法基本思想基本思想：n直線由端點(diǎn)標(biāo)識(shí)；直線由端點(diǎn)標(biāo)識(shí)；n測(cè)試直線端點(diǎn)和窗口邊界的關(guān)系以確定是否測(cè)試直線端點(diǎn)和窗口邊界的關(guān)系以確定是否

42、 需要計(jì)算交點(diǎn)需要計(jì)算交點(diǎn) ；9798nCS 編碼方案編碼方案n擴(kuò)展窗口的邊界將整個(gè)擴(kuò)展窗口的邊界將整個(gè)2D平面劃分為平面劃分為9個(gè)區(qū)域個(gè)區(qū)域n每個(gè)區(qū)域賦予一個(gè)每個(gè)區(qū)域賦予一個(gè)4位編位編碼碼, 稱為區(qū)域碼稱為區(qū)域碼000001100100010100100001100110001010上上下下右右左左w1w2w3w499n編碼規(guī)則編碼規(guī)則nb0 = 1 if x w2nb2 = 1 if y w4000001100100010100100001100110001010上上下下右右左左w1w2w3w4100n算法描述算法描述n計(jì)算直線端點(diǎn)編碼計(jì)算直線端點(diǎn)編碼, c1 和和 c2;n判斷判斷nc1

43、 和和 c2 均為均為0000，保留直線，保留直線nc1 & c2 不為零，同在某一邊界外，刪除該直線不為零，同在某一邊界外，刪除該直線nc1 和和 c2不不 均為均為0000 且且c1 & c2 為零，需要進(jìn)一為零，需要進(jìn)一步求解交點(diǎn)步求解交點(diǎn)n以以L,R,B,T 為序，將為序，將x=w1/w2或或y=w3/w4帶入直帶入直線方程，計(jì)算直線與窗口邊界的交點(diǎn)，將交點(diǎn)和另一線方程，計(jì)算直線與窗口邊界的交點(diǎn)，將交點(diǎn)和另一端點(diǎn)重復(fù)上述過程，直至線段保留或刪除端點(diǎn)重復(fù)上述過程，直至線段保留或刪除101CS線段裁剪算法線段裁剪算法 舉例舉例P3P410000011001000101001

44、00001100110001010102CS線段裁剪算法線段裁剪算法 舉例舉例132P1P2000001100100010100100001100110001010103算法的步驟：算法的步驟：(1)輸入直線段的兩端點(diǎn)坐標(biāo)：輸入直線段的兩端點(diǎn)坐標(biāo)：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界，以及窗口的四條邊界坐標(biāo)：坐標(biāo)：wyt、wyb、wxl和和wxr。(2)對(duì)對(duì)p1、p2進(jìn)行編碼：點(diǎn)進(jìn)行編碼：點(diǎn)p1的編碼為的編碼為code1，點(diǎn)，點(diǎn)p2的編碼為的編碼為code2。(3)若若code1|code2=0，對(duì)直線段應(yīng)簡取之，轉(zhuǎn)，對(duì)直線段應(yīng)簡取之，轉(zhuǎn)(6)；否則，若；否則，若code

45、1&code20，對(duì)直線段可簡棄之，轉(zhuǎn)，對(duì)直線段可簡棄之，轉(zhuǎn)(7)；當(dāng)上述兩條均不滿足時(shí)，；當(dāng)上述兩條均不滿足時(shí)，進(jìn)行步驟進(jìn)行步驟(4)。(4)確保確保p1在窗口外部：若在窗口外部：若p1在窗口內(nèi)，則交換在窗口內(nèi)，則交換p1和和p2的坐標(biāo)值和編碼。的坐標(biāo)值和編碼。(5)按左、右、上、下的順序求出直線段與窗口邊界的交點(diǎn)，并用該交點(diǎn)的按左、右、上、下的順序求出直線段與窗口邊界的交點(diǎn)，并用該交點(diǎn)的坐標(biāo)值替換坐標(biāo)值替換p1的坐標(biāo)值。也即在交點(diǎn)的坐標(biāo)值。也即在交點(diǎn)s處把線段一分為二，并去掉處把線段一分為二，并去掉p1s這這一段?？紤]到一段?？紤]到p1是窗口外的一點(diǎn)，因此可以去掉是窗口外的一點(diǎn)，因

46、此可以去掉p1s。用。用p1替代替代s轉(zhuǎn)轉(zhuǎn)(2)。(6)用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段p1p2。(7)算法結(jié)束。算法結(jié)束。104計(jì)算線段計(jì)算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點(diǎn)與窗口邊界的交點(diǎn)if(LEFT & code !=0)if(LEFT & code !=0) x=XL;x=XL;y=y1+(y2-y1)y=y1+(y2-y1)* *(XL-x1)/(x2-x1);(XL-x1)/(x2-x1);else if(RIGHT & code !=0)else if(RIGHT & code !=0)

47、x=XR;x=XR;y=y1+(y2-y1)y=y1+(y2-y1)* *(XR-x1)/(x2-x1);(XR-x1)/(x2-x1);else if(BOTTOM & code !=0)else if(BOTTOM & code !=0) y=YB;y=YB;x=x1+(x2-x1)x=x1+(x2-x1)* *(YB-y1)/(y2-y1);(YB-y1)/(y2-y1); else if(TOP & code !=0) else if(TOP & code !=0) y=YT;y=YT;x=x1+(x2-x1)x=x1+(x2-x1)* *(YT-y1)

48、/(y2-y1);(YT-y1)/(y2-y1);105n程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)p1p2p3p41321舉例舉例。106n程序流程圖程序流程圖107n優(yōu)點(diǎn)優(yōu)點(diǎn)：簡單，易于實(shí)現(xiàn)。簡單，易于實(shí)現(xiàn)。n算法中求交點(diǎn)的次數(shù)決定了算法的速度，最算法中求交點(diǎn)的次數(shù)決定了算法的速度，最壞要求交三次，反復(fù)循環(huán)。壞要求交三次，反復(fù)循環(huán)。n在裁剪窗口非常大或非常小時(shí)效率很高。在裁剪窗口非常大或非常小時(shí)效率很高。CS線段裁剪算法小結(jié)線段裁剪算法小結(jié)1082 2 Liang-Barsky直線裁剪算法直線裁剪算法n思想：基于直線段參數(shù)方程分析的快速直思想：基于直線段參數(shù)方程分析的快速直線裁剪算法。線裁剪算法。n參數(shù)方程參數(shù)方程

49、直線兩端點(diǎn)直線兩端點(diǎn) P1(x1, y1), P2 (x2, y2)x = x1 + (x2 - x1)uy = y1 + (y2 - y1)u, 0u1109n已知直線端點(diǎn)已知直線端點(diǎn) ： 起點(diǎn)起點(diǎn)P1(x1, y1)，終點(diǎn)，終點(diǎn)P2(x2, y2)n參數(shù)方程：參數(shù)方程：x = x1 + (x2 - x1)uy = y1 + (y2 - y1)u P1P2u1110nLB算法推導(dǎo)如果直線在窗口內(nèi), 則w1 x1 + dx * u w2w3 y1 + dy * u w4統(tǒng)一表示為：Pk * u Qk k = 1, 2, 3, 4 P1 = - dx, Q1 = x1-w1 P2 = dx, Q

50、2 = w2-x1 P3 = - dy, Q3 = y1-w3 P4 = dy, Q4 = w4-y1111w1w2w3w4ubulutur01dxdyP1 = - dx, Q1 = x1-w1 P2 = dx, Q2 = w2-x1P3 = - dy, Q3 = y1-w3 P4 = dy, Q4 = w4-y1112n算法描述算法描述n計(jì)算計(jì)算 Pk, Qk, k=14nPk = 0，表示直線平行于窗口某邊界，表示直線平行于窗口某邊界nQk = 0，直線在窗口內(nèi)，平行邊界內(nèi)，直線在窗口內(nèi)，平行邊界內(nèi)n對(duì)對(duì) Pk0的情形的情形, 用用Qk/Pk計(jì)算交點(diǎn)所對(duì)計(jì)算交點(diǎn)所對(duì)應(yīng)的應(yīng)的u值值113n對(duì)

51、每條線計(jì)算參數(shù)對(duì)每條線計(jì)算參數(shù)u1&u2u1=Max(Qk/Pk|Pk 0 U 1)n如果如果u1 u2, 則直線在窗口外，否則計(jì)算則直線在窗口外，否則計(jì)算交點(diǎn)坐標(biāo)交點(diǎn)坐標(biāo) x(u) = x1+dx*u y(u) = y1+dy*u114LBLB線段裁剪算法線段裁剪算法 例例1 1n已知線段的兩個(gè)端點(diǎn)已知線段的兩個(gè)端點(diǎn)P1(3, 4)，P2(8, 2) 窗口邊界窗口邊界x=1, x=4, y=1, y=3n用用LB算法對(duì)線段進(jìn)行裁剪算法對(duì)線段進(jìn)行裁剪115n線段的參數(shù)方程線段的參數(shù)方程 x = 3 + 5u y = 4 - 2unP1 = -5, Q1 = 2, R1 = -2/5P2

52、 = 5, Q2 = 1, R2 = 1/5P3 = 2, Q3 = 3, R3 = 3/2P4 = -2, Q4 = -1, R4 = 1/2nu1 = max(0, -2/5, 1/2) = 1/2u2 = min(1, 1/5, 3/2) = 1/5nu1 u2 所以線段所以線段全部被裁剪全部被裁剪116線段的兩個(gè)端點(diǎn)（線段的兩個(gè)端點(diǎn)（-2，-1）和（）和（1，1.5）窗口邊界窗口邊界x1 = -1, x2 = 1, y1 = -1, y2 = 1LB線段裁剪算法線段裁剪算法 例例2117x = 3, y = 2.5 p1 = -3q1 = -1 r1 = 1/3 p2 = 3q2 =

53、3r2 = 1p3 = -2.5 q3 = 0r3 = 0p4 = 2.5 q4 = 2r1 = 4/5對(duì)于對(duì)于p 0，u2 = min1，1， 4/5 = 4/5則則u1u2，則可見線段的端點(diǎn)坐標(biāo)：，則可見線段的端點(diǎn)坐標(biāo)：x = x1 + u1 x = -1,y = y1 + u1 y = -1/6 即即(-1, -1/6)x=x1+u2 x=2/5,y=y1+u2 y =1 即(2/5, 1)118void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,

54、y2,XL,XR,YB,YT;float x1,y1,x2,y2,XL,XR,YB,YT; float dx,dy,u1,u2;float dx,dy,u1,u2;tl=0;tu=1;tl=0;tu=1;dx =x2-x1;dy =y2-y1;dx =x2-x1;dy =y2-y1; if(ClipT(-dx,x1-Xl,&u1,&u2) if(ClipT(-dx,x1-Xl,&u1,&u2) if(ClipT(dx,XR-x1, &u1,&u2) if(ClipT(dx,XR-x1, &u1,&u2)if(ClipT(-dy,y

55、1-YB, &u1,&u2)if(ClipT(-dy,y1-YB, &u1,&u2) if(ClipT(dy,YT-y1, &u1,&u2) if(ClipT(dy,YT-y1, &u1,&u2) displayline(x1+u1displayline(x1+u1* *dx,y1+u1dx,y1+u1* *dy, dy, x1+u2x1+u2* *dx,y1+u2dx,y1+u2* *dy)dy)return;return; 程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)119bool ClipT(p,q,u1,u2)bool ClipT(p,q,u1,u2

56、)float p,q,float p,q,* *u1,u1,* *u2;u2; float r; float r;if(p0)if(pif(r* *u2) return FALSE;u2) return FALSE;else if(relse if(r* *u1)u1) * *u1=r;u1=r;return TRUE;return TRUE; 。/下頁下頁120else if(p0)else if(p0) r=p/q;r=p/q;if(rif(r* *u1)return FALSE;u1)return FALSE;else if(relse if(r* *u2)u2) * *u2=r;ret

57、urn TRUE;u2=r;return TRUE; else if(q0) return FALSE; else if(q0) return FALSE; return TRUE; return TRUE; 121nLB vs. CSnLB 效率高于效率高于 CS, 因?yàn)闇p少了交點(diǎn)計(jì)算次數(shù)。因?yàn)闇p少了交點(diǎn)計(jì)算次數(shù)。 參數(shù)參數(shù)u1 和和 u2 的更新需要四次除法的更新需要四次除法, 交點(diǎn)坐交點(diǎn)坐標(biāo)計(jì)算至多標(biāo)計(jì)算至多4次乘法。次乘法。nLiang-Barsky和和Cohen-Sutherland算算法很容易擴(kuò)展為三維裁剪算法法很容易擴(kuò)展為三維裁剪算法1223 中點(diǎn)分割裁剪算法中點(diǎn)分割裁剪算法基本

58、思想：基本思想： 與前一種與前一種Cohen-SutherlandCohen-Sutherland算法一樣首先對(duì)線段端點(diǎn)算法一樣首先對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況: : n全在、完全不在和線段和窗口有交。對(duì)前兩種情況，全在、完全不在和線段和窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。進(jìn)行一樣的處理。n對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)?？诘慕稽c(diǎn)。123求線段與窗口的交點(diǎn)求線段與窗口的交點(diǎn)A、B分別為距P0、P1最近的可見點(diǎn)，Pm為P0P1中點(diǎn)P0P1PmAB124中點(diǎn)分割算

59、法的核心思想核心思想是通過二分逼近來確定直線段與窗口的交點(diǎn)。n從 出發(fā)找最近可見點(diǎn)的方法n先求出 的中點(diǎn)n若 不是顯然不可見的，并且 在窗口中有可見部分，則距 最近的可見點(diǎn)一定落在 上，所以用 代替 ；0P10PPmPmPP0mPP00PmPP0mPP010PP125n否則取 代替n再對(duì)新的 求中點(diǎn) 。重復(fù)上述過程，直到 長度小于給定的控制常數(shù)為止，此時(shí) 收斂于交點(diǎn)。n從 出發(fā)找最近可見點(diǎn)采用上面類似方法。10PP1PPm10PPmP1PPmmP1Pn問：算法為什么可行？會(huì)不會(huì)無限循環(huán)、不斷二分？1264 NLN直線裁剪算法直線裁剪算法(自學(xué)自學(xué))nIDEA 通過在裁剪窗口周圍創(chuàng)立通過在裁剪窗

60、口周圍創(chuàng)立多個(gè)區(qū)域多個(gè)區(qū)域，并在求交運(yùn)算，并在求交運(yùn)算之前進(jìn)行更多的區(qū)域測(cè)試，從而之前進(jìn)行更多的區(qū)域測(cè)試，從而避免避免對(duì)直線段進(jìn)行對(duì)直線段進(jìn)行多次剪裁多次剪裁。n適用范圍適用范圍 僅僅適用于僅僅適用于2D剪裁剪裁127n算法步驟算法步驟n從從P1點(diǎn)向窗口的四個(gè)角點(diǎn)發(fā)出射線，這四點(diǎn)向窗口的四個(gè)角點(diǎn)發(fā)出射線，這四條射線和窗口的四條邊界直線一起將二維平條射線和窗口的四條邊界直線一起將二維平面劃分為更多的小區(qū)域面劃分為更多的小區(qū)域 。128線段端點(diǎn)線段端點(diǎn)P1的三種位置的三種位置129Case 1130Case 2131Case 3A132Case 3B133nP2位置位置? 比較直線段比較直線段P1P2的斜的斜率和剪裁區(qū)域邊界的率和剪裁區(qū)域邊界的斜率斜率. yt-y1 y2-y1 yt-y1xr-x1 x2-x1 xl-x1n交點(diǎn)計(jì)算交點(diǎn)計(jì)算p2134n裁剪類型裁剪類型n點(diǎn)裁剪點(diǎn)裁剪n直線裁剪直線裁剪n多邊形多