CG第6章電子教案

1、2022-3-161第6章 二維變換及二維觀察提出問題提出問題 如何對(duì)二維圖形進(jìn)行方向、尺寸和形狀方面的變換 如何方便地實(shí)現(xiàn)在顯示設(shè)備上對(duì)二維圖形進(jìn)行觀察2022-3-1626.1 6.1 基本概念基本概念6.1.1 6.1.1 齊次坐標(biāo)齊次坐標(biāo) (homogeneous coordinates) 齊次坐標(biāo)表示齊次坐標(biāo)表示: 用n+1維向量表示一個(gè)n維向量。l齊次坐標(biāo)的不唯一性例：非齊次坐標(biāo)點(diǎn)Px, y: 3, 5 齊次坐標(biāo)點(diǎn)Phx, hy, h: 12, 20, 4; 6, 10, 2; 3, 5, 1規(guī)范化齊次坐標(biāo)表示規(guī)范化齊次坐標(biāo)表示: h=1的齊次坐標(biāo)表示。如何從齊次坐標(biāo)轉(zhuǎn)換到規(guī)范化齊

2、次坐標(biāo)？ hp1, hp2, ,hpn, h hp1 /h, hp2 /h, , hpn /h, 12022-3-1636.1.2 6.1.2 幾何變換幾何變換圖形的幾何變換幾何變換: 對(duì)圖形的幾何信息經(jīng)過平移、比例、旋轉(zhuǎn)等變換后產(chǎn)生新的圖形，是圖形在方向、尺寸和形狀方面的變換。2022-3-1646.1.3 二維變換矩陣二維變換矩陣 smlqdcpbayxTyxyxD1112假設(shè)：p(x,y)為x0y平面上二維圖形變化前的點(diǎn)， p(x,y)為變換后的點(diǎn)，則二維變換為：其中T2D表示為4個(gè)子矩陣。T T1 1T T2 2T T3 3T T4 4比例、旋轉(zhuǎn)、對(duì)稱、錯(cuò)切等平移投影整體比例2022-

3、3-1656.2 基本幾何變換基本幾何變換基本幾何變換都是相對(duì)于坐標(biāo)原點(diǎn)和坐標(biāo)軸進(jìn)行相對(duì)于坐標(biāo)原點(diǎn)和坐標(biāo)軸進(jìn)行的幾何變換的幾何變換： p(x,y)p(x,y)為xOy平面上二維圖形變化前的點(diǎn)， p(x,y)p(x,y)為變換后的點(diǎn)。6.2.1 平移變換平移變換平移平移是指將p點(diǎn)沿直線路徑從一個(gè)坐標(biāo)位置移到另一個(gè)坐標(biāo)位置的重定位過程。2022-3-166平移是一種不產(chǎn)生變形而移動(dòng)物體的剛體變換（rigid-body transformation）YXTxTy圖6-1 平移變換PPTxTxxyTyy2022-3-167Tx，Ty稱為平移矢量平移矢量1010001yxTT變換矩陣變換矩陣： 1101

4、000111yxyxTyTxTTyxyx平移變換演示平移變換演示2022-3-1686.2.2 比例變換比例變換比例變換比例變換是指對(duì)p點(diǎn)相對(duì)于坐標(biāo)原點(diǎn)沿x方向放縮Sx倍，沿y方向放縮Sy倍。其中Sx和Sy稱為比例系數(shù)比例系數(shù)。YX圖6-2 比例變換(Sx=2,Sy=3)P(4,3)P(2,1)2022-3-169比例變換的齊次坐標(biāo)計(jì)算形式： 1100000011ySxSSSyxyxyxyx2022-3-1610(a) Sx=Sy比例原圖(b) SxSy比例圖示：比例變換原圖Sx=SySySx=Sy1SxSy2022-3-1611整體比例變換整體比例變換： 10001000111SySxSyx

5、Syxyx比例變換演示比例變換演示2022-3-16126.2.3 旋轉(zhuǎn)變換旋轉(zhuǎn)變換二維旋轉(zhuǎn)二維旋轉(zhuǎn)是指將p點(diǎn)繞坐標(biāo)原點(diǎn)轉(zhuǎn)動(dòng)某個(gè)角度（逆時(shí)針為正，順時(shí)針為負(fù)）得到新的點(diǎn)p的重定位過程。YX圖6-4 旋轉(zhuǎn)變換PPrrcosrx sinry )sin(ry)cos(rxsinsincoscosrrcossinsincosrrcossinyxsincosyx2022-3-16131000cossin0sincos1yx矩陣矩陣：逆時(shí)針旋轉(zhuǎn)角:順時(shí)針旋轉(zhuǎn)角: 1cossinsincos1000cossin0sincos11yxyxyxyx 1000)cos()sin(0)sin()cos(11yxyx

6、2022-3-1614 100010111yxyx簡(jiǎn)化計(jì)算簡(jiǎn)化計(jì)算: :當(dāng)很小時(shí)，cos1, sin，則有如下簡(jiǎn)化計(jì)算公式： 旋轉(zhuǎn)變換演示旋轉(zhuǎn)變換演示2022-3-16156.2.4 對(duì)稱變換對(duì)稱變換對(duì)稱變換對(duì)稱變換后的圖形是原圖形關(guān)于某一軸線或原點(diǎn)的鏡像。XY(a)關(guān)于x軸對(duì)稱XY(b)關(guān)于y軸對(duì)稱XY(c)關(guān)于原點(diǎn)對(duì)稱2022-3-1616XY(d)關(guān)于x=y對(duì)稱XY(e)關(guān)于x=-y對(duì)稱2022-3-1617(1)關(guān)于關(guān)于x x軸對(duì)稱軸對(duì)稱100010001YXP(x,-y)P(x,y)(a)關(guān)于x軸對(duì)稱2022-3-1618(2)關(guān)于關(guān)于y y軸對(duì)稱軸對(duì)稱YXP(-x,y)p(x,y)

7、(b)關(guān)于y軸對(duì)稱1000100012022-3-1619(3)關(guān)于原點(diǎn)對(duì)稱關(guān)于原點(diǎn)對(duì)稱100010001YXP(x,y)(c)關(guān)于原點(diǎn)對(duì)稱P(-x,-y)2022-3-1620(4)關(guān)于關(guān)于y=xy=x軸對(duì)稱軸對(duì)稱YXp(x,y)p(y,x)x=y(d)關(guān)于x=y對(duì)稱1000010102022-3-1621(5)關(guān)于關(guān)于y=-xy=-x軸對(duì)稱軸對(duì)稱YXP(-y,-x)P(x,y)x=-y(e)關(guān)于x=-y對(duì)稱100001010對(duì)稱變換演示對(duì)稱變換演示2022-3-16226.2.5 錯(cuò)切變換錯(cuò)切變換錯(cuò)切變換錯(cuò)切變換，也稱為剪切、錯(cuò)位變換，用于產(chǎn)生彈性物體的變形處理。YXYXYX(a) 原圖(

8、b) 沿x方向錯(cuò)切(c) 沿y方向錯(cuò)切圖6-7 錯(cuò)切變換2022-3-1623其變換矩陣為： 1000101cb (1)沿x方向錯(cuò)切： b = 0, c 0cyxxyy 10001001c2022-3-162410001001b (2)沿y方向錯(cuò)切: c = 0, b 0 (3)兩個(gè)方向錯(cuò)切: b 0 且 c 0 cyxxybxyybxyxx 1000101cb錯(cuò)切變換演示錯(cuò)切變換演示2022-3-16256.2.6 二維圖形幾何變換的計(jì)算二維圖形幾何變換的計(jì)算 smlqdcpbayxTyxyxD1112sqypxmdybxysqypxlcyaxx2022-3-1626幾何變換均可表示成幾何變

9、換均可表示成 P= P * T 的形式的形式 1. 點(diǎn)的變換：行矩陣或列矩陣 2. 直線的變換：兩端點(diǎn) Tyxyx11Tyxyxyxyx1111221122112022-3-1627 3. 多邊形的變換：每個(gè)頂點(diǎn)的坐標(biāo)位置 4. 曲線的變換 通過變換曲線上的每一點(diǎn)來實(shí)現(xiàn)。Tyxyxyxyxyxyxyxyxnnnn1.1111.1113322113322112022-3-16286.3 復(fù)合變換復(fù)合變換復(fù)合變換復(fù)合變換是指： 圖形作一次以上的幾何變換，變換結(jié)果是每次的變換矩陣相乘。 任何一復(fù)雜的幾何變換都可以看作基本幾何變換的組合形式。復(fù)合變換具有如下形式：nTTTTPTPP 321) 1( n

10、)(321nTTTTP 2022-3-16296.3.1 二維復(fù)合平移二維復(fù)合平移兩個(gè)連續(xù)平移是相加的。10100011010001221121yxyxtttTTTTTTT10100012121yyxxTTTT復(fù)合平移變換演示復(fù)合平移變換演示2022-3-16306.3.2 6.3.2 二維復(fù)合比例二維復(fù)合比例連續(xù)比例變換是相乘的。10000001000000221121yxyxsssSSSSTTT10000002121yyxxSSSS復(fù)合比例變換演示復(fù)合比例變換演示2022-3-16316.3.3 6.3.3 二維復(fù)合旋轉(zhuǎn)二維復(fù)合旋轉(zhuǎn)兩個(gè)連續(xù)旋轉(zhuǎn)是相加的?？蓪憺椋?(21)()(21RRRR

11、1000cossin0sincos1000cossin0sincos2222111121rrrTTT1000)cos()sin(0)sin()cos(21212121復(fù)合旋轉(zhuǎn)變換演示復(fù)合旋轉(zhuǎn)變換演示2022-3-16326.3.4 其它二維復(fù)合變換其它二維復(fù)合變換1000cos000cos100010110001011000cos000cos1000 cos sin0 sincostgtgtgtgR分解旋轉(zhuǎn)變換矩陣為：因此：旋轉(zhuǎn)變換=比例變換+錯(cuò)切變換復(fù)合平移變換演示復(fù)合平移變換演示2022-3-16336.3.5 相對(duì)任一參考點(diǎn)的二維幾何變換相對(duì)任一參考點(diǎn)的二維幾何變換相對(duì)某個(gè)參考點(diǎn)(xF,

12、yF)作二維幾何變換，其變換過程為：(1) 平移(2) 針對(duì)原點(diǎn)進(jìn)行二維幾何變換。(3) 反平移例. 相對(duì)點(diǎn)(xF,yF)的旋轉(zhuǎn)變換 (p155: 6-23)例. 相對(duì)點(diǎn)(xF,yF)的比例變換 (p155: 6-24)2022-3-16346.3.6 相對(duì)任意方向的二維幾何變換相對(duì)任意方向的二維幾何變換相對(duì)任意方向作二維幾何變換，其變換的過程是：(1) 旋轉(zhuǎn)變換(2) 針對(duì)坐標(biāo)軸進(jìn)行二維幾何變換；(3) 反向旋轉(zhuǎn)例. 相對(duì)直線y=x的反射變換（p155: 6-26）2022-3-1635例例(p156) 將正方形ABCO各點(diǎn)沿下圖所示的(0,0)(1,1)方向進(jìn)行拉伸，結(jié)果為如圖所示的菱形，

13、寫出其變換矩陣和變換過程。YX13/21/21/23/222圖6-8 針對(duì)固定方向的拉伸OABCCCBBAA2022-3-1636課后作業(yè)：課后作業(yè)：習(xí)題六（習(xí)題六（p176）6.1 名次解釋：齊次坐標(biāo)，規(guī)范化齊次坐標(biāo)，圖形的幾何變換。6.2 說明二維變換矩陣T2D 中各元素在變換中的具體作用。smlqdcpba2022-3-16376.3.7 坐標(biāo)系之間的變換坐標(biāo)系之間的變換問題問題：圖6-9 坐標(biāo)系間的變換xyxyOOx0y0p(xp,yp)2022-3-1638分析：分析：xyyOO(x0,y0)圖6-11 坐標(biāo)系變換的變換原理xp,也即pp*pxpy *xOp*yOp2022-3-16

14、39可以分兩步進(jìn)行：xyyOOx0y0 x(a)將xy坐標(biāo)系的原點(diǎn)平移到xy坐標(biāo)系的原點(diǎn)p(xp,yp)xyOyx(b)將x軸旋轉(zhuǎn)到x軸上p(xp,yp)2022-3-1640于是： 1000cossin0sincos101000100yxTTRt 1000cossin0sincos101000100yxRtTTpTp Tyxyxppppp11其中： 2022-3-16416.3.8 光柵變換光柵變換直接對(duì)幀緩存中象素點(diǎn)進(jìn)行操作的變換稱為光柵變換光柵變換。 光柵平移變換： (a)讀出象素塊的內(nèi)容(b)復(fù)制象素塊的內(nèi)容(c)擦除原象素塊的內(nèi)容2022-3-1642 90、180和270的光柵旋轉(zhuǎn)

15、變換： (a)逆時(shí)針旋轉(zhuǎn)90(x,y)(y,rowlen-x)rowlen(x,y)(rowlen-x,vollen-y)(b)逆時(shí)針旋轉(zhuǎn)180rowlenvollen2022-3-1643 復(fù)雜情形：任意角度的光柵旋轉(zhuǎn)變換： 旋轉(zhuǎn)的象素陣列光柵網(wǎng)格AA2132022-3-1644 光柵比例變換： ( (b)b)原圖原圖(a)Sx=1/2,Xy=1/2縮小時(shí)原圖中的縮小時(shí)原圖中的相應(yīng)象素區(qū)域相應(yīng)象素區(qū)域(a)Sx=1,Xy=3/2放大時(shí)原圖中的放大時(shí)原圖中的相應(yīng)象素區(qū)域相應(yīng)象素區(qū)域2022-3-16456.3.9 變換的性質(zhì)變換的性質(zhì) 仿射變換具有平行線不變性和有限點(diǎn)數(shù)目的不變性 平移、比例、

16、旋轉(zhuǎn)、錯(cuò)切和反射等變換均是二維仿射變換的特例，反過來，任何常用的二維仿射變換總可以表示為這五種變換的復(fù)合。 ndycxymbyaxx二維仿射變換二維仿射變換是具有如下形式的二維坐標(biāo)變換： 2022-3-1646二維幾何變換具有如下一些性質(zhì)： 直線的中點(diǎn)不變性； 平行直線不變性； 相交不變性； 僅包含旋轉(zhuǎn)、平移和反射的仿射變換維持角度和長度的不變性； 比例變化可改變圖形的大小和形狀； 錯(cuò)切變化引起圖形角度關(guān)系的改變，甚至導(dǎo)致圖形發(fā)生畸變。2022-3-16476.4 二維觀察二維觀察6.4.1 6.4.1 基本概念基本概念 在計(jì)算機(jī)圖形學(xué)中，將在用戶坐標(biāo)系中需要進(jìn)行觀察和處理的一個(gè)坐標(biāo)區(qū)域稱為窗

17、口窗口（Window） 將窗口映射到顯示設(shè)備上的坐標(biāo)區(qū)域稱為視區(qū)視區(qū)（Viewport）2022-3-16484.1.3 坐標(biāo)系用戶坐標(biāo)系建模坐標(biāo)系觀察坐標(biāo)系規(guī)格化的設(shè)備坐標(biāo)設(shè)備坐標(biāo)系坐標(biāo)系直角坐標(biāo)系仿射坐標(biāo)系圓柱坐標(biāo)系球坐標(biāo)系極坐標(biāo)系圖4-4 坐標(biāo)系的分類2022-3-1649要將窗口內(nèi)的圖形在視區(qū)中顯示出來，必須經(jīng)過將 窗 口 到 視 區(qū) 的 變 換 （ W i n d o w - V i e w p o r t Transformation）處理，這種變換就是觀察變換觀察變換（Viewing Transformation）。XYwxlXYwybwxrwyt窗口vxrvybvyt視區(qū)(a)

18、用戶坐標(biāo)系中的窗口(b)屏幕坐標(biāo)系中的視區(qū)vxl2022-3-1650XY窗口用戶坐標(biāo)系中旋轉(zhuǎn)的窗口XY窗口用戶坐標(biāo)系中非矩形窗口2022-3-1651 觀察坐標(biāo)系觀察坐標(biāo)系(View Coordinate)和規(guī)格化設(shè)備坐標(biāo)系和規(guī)格化設(shè)備坐標(biāo)系(Normalized Device Coordinate) :l觀察坐標(biāo)系觀察坐標(biāo)系是依據(jù)窗口的方向和形狀在用戶坐標(biāo)平面中定義的直角坐標(biāo)系。l規(guī)格化設(shè)備坐標(biāo)系規(guī)格化設(shè)備坐標(biāo)系也是直角坐標(biāo)系，它是將二維的設(shè)備坐標(biāo)系規(guī)格化到（0.0，0.0）到（1.0，1.0）的坐標(biāo)范圍內(nèi)形成的。1x用戶y用戶xNDCyNDC窗口視區(qū)y觀察x觀察1(a)觀察坐標(biāo)系(b)規(guī)

19、格化設(shè)備坐標(biāo)系2022-3-1652引入了觀察坐標(biāo)系和規(guī)格化設(shè)備坐標(biāo)系后，觀察變換分為如下圖所示的幾個(gè)步驟，通常稱為二維觀二維觀察流程察流程。 觀 察 坐標(biāo) 系 下對(duì) 窗 口進(jìn) 行 裁剪窗口到視區(qū) (規(guī) 范化設(shè)備坐標(biāo)系中定義 )的 變換視圖區(qū)從規(guī)范化坐標(biāo)系到設(shè)備坐標(biāo)系的變換在圖形設(shè)備上輸出DC用 戶 坐標(biāo) 系 到觀 察 坐標(biāo) 系 間的變換應(yīng)用程序到圖形的用戶坐標(biāo)圖6-19 兩維觀察流程N(yùn)DCVCWCVC2022-3-1653 變焦距效果變焦距效果: : 窗口大小改變，視區(qū)大小不變窗口大小改變，視區(qū)大小不變圖6-20 變焦距效果（窗口變、視區(qū)不變）(a) 原圖及變化的窗口(b)與窗口對(duì)應(yīng)的視區(qū)1

20、(c)與窗口對(duì)應(yīng)的視區(qū)2(d)與窗口對(duì)應(yīng)的視區(qū)31123232022-3-1654 整體縮放效果：整體縮放效果：窗口大小不變，視區(qū)大小改變窗口大小不變，視區(qū)大小改變(a) 原圖及窗口(b) 視區(qū)1圖6-21 整體放縮效果（窗口不變、視區(qū)變）(c) 視區(qū)2(d)視區(qū)3 漫游效果：漫游效果：窗口大小不變，位置移動(dòng)；視區(qū)不變窗口大小不變，位置移動(dòng)；視區(qū)不變 6.4.2 用戶坐標(biāo)系到觀察坐標(biāo)系的變換用戶坐標(biāo)系到觀察坐標(biāo)系的變換用戶坐標(biāo)系到觀察坐標(biāo)系的變換分別由兩個(gè)變換步驟合成：T=TrTR1. 將觀察坐標(biāo)系原點(diǎn)移動(dòng)到用戶坐標(biāo)系原點(diǎn)x用戶y用戶窗口y觀察x觀察(a) 平移變換101000100yxTr2

21、022-3-16562. 繞原點(diǎn)旋轉(zhuǎn)使兩坐標(biāo)系重合 x用戶y用戶窗口y觀察x觀察(b) 旋轉(zhuǎn)變換1000cossin0sincosRT因此，用戶坐標(biāo)系到觀察坐標(biāo)系的變換：1000cossin0sincos101000100yxTTTRrTPP相應(yīng)坐標(biāo)點(diǎn)的變換：2022-3-16586.4.3 窗口到視區(qū)的變換窗口到視區(qū)的變換XYwxlXYwybwxrwyt窗口vxlvybvyt視區(qū)圖6-23 窗口到視區(qū)的變換(a)窗口中的點(diǎn)(b)視區(qū)中的點(diǎn)(xw,yw)(xv,yv)vxr要將窗口內(nèi)的點(diǎn)（xw, yw）映射到相對(duì)應(yīng)的視區(qū)內(nèi)的點(diǎn)（xv, yv）需進(jìn)行以下步驟：(1) 將窗口左下角點(diǎn)(wxl, w

22、yb)移至用戶坐標(biāo)系的坐標(biāo)原點(diǎn):2022-3-1659(2) 針對(duì)原點(diǎn)進(jìn)行比例變換:(3) 進(jìn)行反平移：將視區(qū)左下角點(diǎn)移至設(shè)備坐標(biāo)系原來的位置(vxl, vyb)。wybwytvybvytSy10100011000000101000121vybvxlSSwybwxlTSTyx平移平移反平移反平移比例比例)()(wxlwxrvxlvxrSx2022-3-1660TPyxPvv1100001vybSwybvxlSwxlSSyxyxyxww相應(yīng)坐標(biāo)點(diǎn)的變換：10000vybSwybvxlSwxlSSTyxyx變換矩陣：2022-3-1661課后作業(yè)：課后作業(yè)：習(xí)題六（習(xí)題六（p176-177）6.1

23、 名詞解釋：窗口，視區(qū)，變焦距效果。2022-3-16626.5 裁剪裁剪 在二維觀察中，需要在觀察坐標(biāo)系下對(duì)窗口進(jìn)行裁剪裁剪，即只保留窗口內(nèi)的那部分圖形，去掉窗口外的圖形。 算法：1.圖形元素在窗口內(nèi)外的判別； 2.圖形元素與窗口的交點(diǎn)。XwxlwxlwxrwxrYwybwybwytwyt窗口(a)窗口中的點(diǎn)(xw, yw) 假設(shè)假設(shè)窗口是標(biāo)準(zhǔn)矩形，即邊與坐標(biāo)軸平行的矩形，由四條邊描述: 上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）。2022-3-16636.5.1 點(diǎn)的裁剪點(diǎn)的裁剪wytywybwxrxwxl且, 對(duì)于任意一點(diǎn)P(x, y)， 如果滿足則點(diǎn)p(x,

24、y)在矩形窗口內(nèi)，否則在矩形窗口外。P(x,y)P(x,y)XwxlwxlwxrwxrYwybwybwytwyt窗口(a)窗口中的點(diǎn)(xw, yw)2022-3-16646.5.2 直線段的裁剪直線段的裁剪假定假定直線段用p1(x1, y1) p2(x2, y2)表示。 直線段和剪裁窗口的可能關(guān)系：l完全落在窗口內(nèi)l完全落在窗口外l與窗口邊界相交 窗口圖6-24 直線段與窗口的關(guān)系A(chǔ)BCDEFHGIJ2022-3-1665對(duì)于既不完全落在窗口內(nèi)又不能確定完全落在窗口外的點(diǎn)，計(jì)算它與剪裁窗口邊界的交點(diǎn)： 實(shí)交點(diǎn)實(shí)交點(diǎn)是直線段與窗口矩形邊界的交點(diǎn)。 虛交點(diǎn)虛交點(diǎn)則是直線段與窗口矩形邊界延長線或直線

25、段的延長線與窗口矩形邊界的交點(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)2022-3-16661. Cohen-Sutherland算法算法基本思想基本思想：對(duì)每條直線段p1(x1, y1) p2(x2, y2)分三種情況處理：(1)直線段完全可見，“簡(jiǎn)取”之。wytywybwxrxwxl且, XYwxlwybwxrwyt窗口(a)窗口中的直線2022-3-1667(2)直線段完全不可見，“簡(jiǎn)棄”之。(3)直線段既不滿足“簡(jiǎn)取”的條件，也不滿足“簡(jiǎn)棄”的條件，需要對(duì)直線段按交點(diǎn)進(jìn)行分段，分段后重復(fù)上述處理。 wxlx 1wxlx 2且wxrx 2

26、wxrx 1且wyby 2wyby 1且wyty 2wyty 1且XYwxlwybwxrwyt窗口(a)窗口外的直線2022-3-1668編碼編碼：對(duì)于任一端點(diǎn)(x, y)，根據(jù)其坐標(biāo)所在的區(qū)域，賦予一個(gè)4位的二進(jìn)制碼D3D2D1D0。編碼規(guī)則如下： 若xwxr，則D1=1，否則D1=0； 若ywyt，則D3=1，否則D3=0。 0000窗口01000101100100011010011010000010圖6-26 窗口及區(qū)域編碼D3D2D1D02022-3-1669裁剪：裁剪：裁剪一條線段時(shí)，先求出端點(diǎn)p1和p2的編碼code1和code2，然后：(1)若code1|code2=0，對(duì)直線段

27、應(yīng)簡(jiǎn)取之。(2)若code1&code20，對(duì)直線段可簡(jiǎn)棄之。(3)若上述兩條件均不成立。則需求出直線段與窗口邊界的交點(diǎn)。在交點(diǎn)處把線段一分為二，其中必有一段完全在窗口外，可以棄之。再對(duì)另一段重復(fù)進(jìn)行上述處理，直到該線段完全被舍棄或者找到位于窗口內(nèi)的一段線段為止。2022-3-1670 左、右邊界交點(diǎn)的計(jì)算： ; x為wxl 或wxr窗口圖6-25 實(shí)交點(diǎn)與虛交點(diǎn)ABCDEFHGIJ虛交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)虛交點(diǎn)虛交點(diǎn))(11xxkyy 上、下邊界交點(diǎn)的計(jì)算： ; y為wyb 或wytkyyxx11求交求交：假定直線的端點(diǎn)坐標(biāo)為(x1,y1)和(x2,y2),1212xxyyk2022

28、-3-1671算法步驟算法步驟：(1)輸入直線段的兩端點(diǎn)坐標(biāo)：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標(biāo)：wyt、wyb、wxl和wxr。(2)對(duì)p1、p2進(jìn)行編碼：點(diǎn)p1的編碼為code1，點(diǎn)p2的編碼為code2。(3)若code1|code2=0，對(duì)直線段應(yīng)簡(jiǎn)取之，轉(zhuǎn)(6)；否則，若code1&code20，對(duì)直線段可簡(jiǎn)棄之，轉(zhuǎn)(7)；當(dāng)上述兩條均不滿足時(shí)，進(jìn)行步驟(4)。(4)確保p1在窗口外部：若p1在窗口內(nèi)，則交換p1和p2的坐標(biāo)值和編碼。(5)按左、右、上、下的順序求出直線段與窗口邊界的交點(diǎn)，并用該交點(diǎn)的坐標(biāo)值替換p1的坐標(biāo)值。也即在交點(diǎn)s處把線段一分

29、為二，并去掉p1s這一段。轉(zhuǎn)(2)。(6)用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段p1p2。(7)算法結(jié)束。 2022-3-1672例如例如： P1P2P3P4000001000101100100011010011010000010圖6-27 直線段p1p2的編碼裁剪2022-3-16732. 中點(diǎn)分割算法中點(diǎn)分割算法基本思想基本思想： 當(dāng)對(duì)直線段不能簡(jiǎn)取(不滿足code1|code2=0)也不能簡(jiǎn)棄(不滿足code1&code20)時(shí)，簡(jiǎn)單地把線段等分為二段，對(duì)兩段重復(fù)上述測(cè)試處理，直至每條線段完全在窗口內(nèi)或完全在窗口外。 2022-3-1674中點(diǎn)分割算法的核心思想是通過二分逼近來確定直

30、線段與窗口的交點(diǎn)。p1p2p3p4p5p6p72022-3-1675算法步驟：算法步驟：(1)輸入直線段的兩端點(diǎn)坐標(biāo)：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標(biāo)：wyt、wyb、wxl和wxr。(2)對(duì)p1、p2進(jìn)行編碼：點(diǎn)p1的編碼為code1，點(diǎn)p2的編碼為code2。(3)若code1|code2=0，對(duì)直線段應(yīng)簡(jiǎn)取之，保留當(dāng)前直線段的端點(diǎn)坐標(biāo)，轉(zhuǎn)(5)；否則，若code1&code20，對(duì)直線段可簡(jiǎn)棄之，轉(zhuǎn)(5)；當(dāng)上述兩條均不滿足時(shí)，進(jìn)行步驟(4)。(4)求出直線段的中點(diǎn)求出直線段的中點(diǎn)M，將將p1M、p2M入棧入棧。(5)當(dāng)棧不空時(shí)，從棧中彈出一條直線段

31、，取為p1p2，轉(zhuǎn)(2)進(jìn)行處理。否則，繼續(xù)(6)。(6)當(dāng)棧為空時(shí)，合并保留的直線段端點(diǎn)當(dāng)棧為空時(shí)，合并保留的直線段端點(diǎn)，得到窗口內(nèi)的直線段p1p2。用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段p1p2，算法結(jié)束。2022-3-1676重新構(gòu)造算法步驟算法步驟：(1)若code1|code2=0，對(duì)直線段應(yīng)簡(jiǎn)取之，結(jié)束；否則，若code1&code20，對(duì)直線段可簡(jiǎn)棄之，結(jié)束；當(dāng)這兩條均不滿足時(shí)，進(jìn)行步驟(2)。(2)找出該直線段離窗口邊界最遠(yuǎn)的點(diǎn)和該直線段的中點(diǎn)。判中點(diǎn)判中點(diǎn)是否在窗口內(nèi)是否在窗口內(nèi)：若中點(diǎn)不在窗口內(nèi)，則把中點(diǎn)和離窗口邊界最遠(yuǎn)點(diǎn)構(gòu)成的線段丟掉，以線段上的另一點(diǎn)和該中點(diǎn)再構(gòu)成線

32、段求其中點(diǎn)；如中點(diǎn)在窗口內(nèi)，則又以中點(diǎn)和最遠(yuǎn)點(diǎn)構(gòu)成線段，并求其中點(diǎn)，直到中點(diǎn)與窗口邊界的坐標(biāo)值在規(guī)定的誤差范圍內(nèi)相等，則該中點(diǎn)就是該線段落在窗口內(nèi)的一個(gè)端點(diǎn)坐標(biāo)。(3)如另一點(diǎn)在窗口內(nèi)，則經(jīng)(2)即確定了該線段在窗口內(nèi)的部分。如另一點(diǎn)不在窗口內(nèi)，則該點(diǎn)和所求出的在窗口上的那一點(diǎn)構(gòu)成一條線段，重復(fù)步驟(2)，即可求出落在窗口內(nèi)的另一點(diǎn)。2022-3-1677例如例如： 特點(diǎn)特點(diǎn)： 1.只進(jìn)行加法和位移運(yùn)算，便于硬件實(shí)現(xiàn)； 2. 適合于并行運(yùn)算p1p2p3p4p5p6p72022-3-1678課后作業(yè)：課后作業(yè)：編程并上機(jī)實(shí)現(xiàn)習(xí)題六（習(xí)題六（p177）6.13 試用編碼裁剪算法裁剪如圖6-39所示

33、線段。6.14 試用中點(diǎn)分割算法裁剪如圖6-39所示線段。XY20A(3,3)2窗口圖6-39B(-1,-2)2022-3-16793. Liang-Barsky算法算法梁友棟和Barskey提出了更快的參數(shù)化裁剪算法。首先按參數(shù)化形式寫出裁剪條件:)(121xxuxx)(121yyuyyYTyyuyYB)(121XRxxuxXL)(121這四個(gè)不等式可以表示為形式：upkqk (k=1, 2, 3, 4)其中，參數(shù)pk，qk定義為12xXRqxp2XLxq11xp1YByq13yp314yYTqyp410 u2022-3-1680Liang-Barsky算法的幾何解釋算法的幾何解釋：把直線與

34、窗口邊界的實(shí)交點(diǎn)和虛交點(diǎn)分為兩組：下限組以pk0為特征，表示該處直線從裁剪邊界延長線的內(nèi)部延伸到外部。有交情況下：下限組分布于直線段起點(diǎn)一側(cè)，上限組分布于直線段終點(diǎn)一側(cè)。下限組的最大值和上限組的最小值就分別對(duì)應(yīng)于直線與窗下限組的最大值和上限組的最小值就分別對(duì)應(yīng)于直線與窗口邊界的實(shí)交點(diǎn)口邊界的實(shí)交點(diǎn)。2022-3-1681任何平行于裁剪邊界之一的直線 pk=0，其中k對(duì)應(yīng)于裁剪邊界（k=1,2,3,4對(duì)應(yīng)于左、右、下、上邊界）: 如果還滿足qk0，則線段完全在邊界外，舍棄該線段。 如果qk0，則該線段平行于裁剪邊界并且在窗口內(nèi)。當(dāng)pk0,線段從裁剪邊界延長線的內(nèi)部延伸到外部。pk0時(shí)，可以計(jì)算出

35、線段與邊界k的延長線的交點(diǎn)的u值： u=qk/pk12xXRqxp2XLxq11xp1YByq13yp314yYTqyp42022-3-1682(a)直線段與窗口邊界wxl和wxr平行的情況(b)直線段與窗口邊界wyb和wyt平行的情況wytwybwxlwxrwxrwxlwybwytA AB BC CD DE EF FG GH HI IJ JK KL Lpk=0，qk0: A, F, L, Gpk=0，qk0: B, C, D, E, H, I, J, K特殊情況：2022-3-1683對(duì)于每條直線，可以計(jì)算出參數(shù)umax和umin，它們定義了在裁剪矩形內(nèi)的線段部分：一般情況： umax的值由

36、線段從外到內(nèi)遇到的矩形邊界所決定(p0)。對(duì)這些邊界計(jì)算rk=qk/pk。umin取1和各個(gè)rk值之中的最小值。如果umaxumin，則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個(gè)值umax,umin計(jì)算出來。2022-3-1684Liang-Barsky算法算法步驟步驟：(1) 輸入直線段的兩端點(diǎn)坐標(biāo)：(x1,y1)和(x2,y2)，以及窗口的四條邊界坐標(biāo)：wyt、wyb、wxl和wxr。(2) 若x=0，則p1=p2=0。此時(shí)進(jìn)一步判斷是否滿足q10或q20，若滿足，則該直線段不在窗口內(nèi)，算法轉(zhuǎn)(7)。否則，滿足q10且q2 0，則進(jìn)一步計(jì)算計(jì)算umax和和umin。算法轉(zhuǎn)

37、(5)。(3) 若y=0，則p3=p4=0。此時(shí)進(jìn)一步判斷是否滿足q30或q40，若滿足，則該直線段不在窗口內(nèi)，算法轉(zhuǎn)(7)。否則，滿足q30且q40，則進(jìn)一步計(jì)算計(jì)算umax和和umin。算法轉(zhuǎn)(5)。(4) 若上述兩條均不滿足，則有pk0（k=1,2,3,4）。此時(shí)計(jì)算計(jì)算umax和和umin。(5) 求得umax和umin后，進(jìn)行判斷：若umaxumin，則直線段在窗口外，算法轉(zhuǎn)(7)。若umax umin，利用直線的參數(shù)方程求得直線段在窗口內(nèi)的兩端點(diǎn)坐標(biāo)。(6) 利用直線的掃描轉(zhuǎn)換算法繪制在窗口內(nèi)的直線段。(7) 算法結(jié)束。2022-3-16856.5.3 多邊形的裁剪多邊形的裁剪問題

38、的提出： (a)裁剪前(b)直接采用直線段裁剪的結(jié)果(c)正確的裁剪結(jié)果2022-3-16861. Sutherland-Hodgeman多邊形裁剪多邊形裁剪基本思想基本思想: : 逐邊裁剪算法逐邊裁剪算法輸入：ABCDEFGHABCDEFGH輸出：A12DEFGH12(a)用左邊界裁剪輸出：A134D56FGHADEFGH輸入：A12DEFGH12(b)用下邊界裁剪34562022-3-1687輸入：A134D56FGHADFGH1(c)用右邊界裁剪3456輸出：A134D5678GH78ADGH1(d)用上邊界裁剪345678輸入：A134D5678GH輸出：K34D56789IHJ9IJK2022-3-1688Sutherland-Hodgeman算法原理算法原理： 為窗口各