計算機(jī)圖形學(xué)第5章(3)

1、第第 五五 章章 二維變換及二維觀察二維變換及二維觀察5.1 5.1 基本概念基本概念5.2 5.2 基本幾何變換基本幾何變換5.3 5.3 復(fù)合變換復(fù)合變換5.4 5.4 二維觀察二維觀察5.5 5.5 剪剪 裁裁提出問題提出問題如何對二維圖形進(jìn)行方向、尺寸和形如何對二維圖形進(jìn)行方向、尺寸和形狀方面的變換狀方面的變換如何方便地實現(xiàn)在顯示設(shè)備上對二維如何方便地實現(xiàn)在顯示設(shè)備上對二維圖形進(jìn)行觀察圖形進(jìn)行觀察5.1.1 5.1.1 齊次坐標(biāo)齊次坐標(biāo)齊次坐標(biāo)表示就是用齊次坐標(biāo)表示就是用n+1維向量表示一個維向量表示一個n維向量。維向量。例：二維平面上的點例：二維平面上的點(x,y)的齊次坐標(biāo)表示為的

2、齊次坐標(biāo)表示為(hx,hy,h)，其中，其中h0。 (x1, , xn) 的的齊次坐標(biāo)表示：齊次坐標(biāo)表示：(hx1, , hxn, h) n+1個分量中，個分量中，只有只有n個是獨立的個是獨立的，具有這種，具有這種特征的坐標(biāo)就叫齊次坐標(biāo)。特征的坐標(biāo)就叫齊次坐標(biāo)。5.1 5.1 基本概念基本概念5.1 5.1 基本概念基本概念 齊次坐標(biāo)的不唯一性齊次坐標(biāo)的不唯一性 規(guī)范化齊次坐標(biāo)表示就是規(guī)范化齊次坐標(biāo)表示就是h=1的齊次坐標(biāo)表示。的齊次坐標(biāo)表示。 如何從齊次坐標(biāo)轉(zhuǎn)換到規(guī)范化齊次坐標(biāo)？如何從齊次坐標(biāo)轉(zhuǎn)換到規(guī)范化齊次坐標(biāo)？ 提供了用矩陣運(yùn)算把二維、三維甚至高維空提供了用矩陣運(yùn)算把二維、三維甚至高維空

3、間中的一個點集從一個坐標(biāo)系變換到另一個間中的一個點集從一個坐標(biāo)系變換到另一個坐標(biāo)系的有效方法。坐標(biāo)系的有效方法。 可以表示無窮遠(yuǎn)點?？梢员硎緹o窮遠(yuǎn)點。5.1.2 5.1.2 幾何變換幾何變換 圖形的幾何變換是指對圖形的幾何信息經(jīng)過圖形的幾何變換是指對圖形的幾何信息經(jīng)過平平移移、縮放縮放、旋轉(zhuǎn)旋轉(zhuǎn)等變換后產(chǎn)生新的圖形，是圖形等變換后產(chǎn)生新的圖形，是圖形在方向、尺寸和形狀方面的變換。在方向、尺寸和形狀方面的變換。5.1 5.1 基本概念基本概念5.1.3 5.1.3 二維變換矩陣二維變換矩陣 smlqdcpbayxTyxyxD11121T3T2T4T平移投影整體比例變換整體比例變換比例、旋轉(zhuǎn)、對稱

4、5.1 5.1 基本概念基本概念5.2 5.2 基本幾何變換基本幾何變換基本幾何變換都是相對于坐標(biāo)原點和坐標(biāo)軸基本幾何變換都是相對于坐標(biāo)原點和坐標(biāo)軸進(jìn)行的幾何變換。進(jìn)行的幾何變換。 5.2.1 5.2.1 平移變換平移變換平移是指將平移是指將P點沿直線路徑從一個坐標(biāo)位置點沿直線路徑從一個坐標(biāo)位置移到另一個坐標(biāo)位置的重定位過程。移到另一個坐標(biāo)位置的重定位過程。平移是一種不產(chǎn)生變形而移動物體的剛體變換平移是一種不產(chǎn)生變形而移動物體的剛體變換（rigid-body transformation）YXTxTy圖6-1 平移變換PPTTx，Ty稱為平移矢量平移矢量1010001yxTT舉例說明舉例說明：

5、變換矩陣變換矩陣： 1 ,101000111yxyxTyTxTTyxyx5.2.2 5.2.2 比例變換比例變換 比例變換是指對比例變換是指對P點相對于坐標(biāo)原點沿點相對于坐標(biāo)原點沿x方向縮方向縮放放Sx倍，沿倍，沿y方向縮放方向縮放Sy倍。其中倍。其中Sx和和Sy稱為比例稱為比例系數(shù)。系數(shù)。YX圖6-2 比例變換(Sx=2,Sy=3)P(4,3)P(2,1)舉例說明舉例說明：矩陣矩陣：1000000yxSS 001100,1001xyxySxyxySx Sy S(a) Sx=Sy比例原圖(b) SxSy比例原圖圖6-3 比例變換SxSySx=Sy1Sx=Sy1S1，圖形整體縮小；，圖形整體縮小

6、；0S10S1，圖形整體放大；，圖形整體放大； S0 S0，發(fā)生和原點對稱等比變換。，發(fā)生和原點對稱等比變換。 二維旋轉(zhuǎn)是指將二維旋轉(zhuǎn)是指將P P點繞坐標(biāo)原點轉(zhuǎn)動某個角度（逆點繞坐標(biāo)原點轉(zhuǎn)動某個角度（逆時針為正，順時針為負(fù)）得到新的點時針為正，順時針為負(fù)）得到新的點P P的重定位過程。的重定位過程。YX圖6-4 旋轉(zhuǎn)變換PPrr5.2.3 5.2.3 旋轉(zhuǎn)變換旋轉(zhuǎn)變換舉例說明：舉例說明：矩陣矩陣：逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)角角1000cossin0sincos簡化計算簡化計算 100010111yxyx5.2.4 5.2.4 對稱變換對稱變換對稱變換后的圖形是原圖形關(guān)于某一軸線對稱變換后的圖形是原圖

7、形關(guān)于某一軸線或原點的鏡像?；蛟c的鏡像。XY(a)關(guān)于x軸對稱XY(b)關(guān)于y軸對稱XY(d)關(guān)于x=y對稱XY(e)關(guān)于x=-y對稱100010001YXP(x,-y)P(x,y)(a)關(guān)于x軸對稱(1)(1)關(guān)于關(guān)于x x軸對稱（舉例）軸對稱（舉例）YXP(-x,y)p(x,y)(b)關(guān)于y軸對稱100010001(2)(2)關(guān)于關(guān)于y y軸對稱（舉例）軸對稱（舉例）YXP(x,y)(c)關(guān)于原點對稱100010001(3)(3)關(guān)于原點對稱（舉例）關(guān)于原點對稱（舉例）YXp(x,y)p(y,x)x=y(d)關(guān)于x=y對稱100001010(4)(4)關(guān)于關(guān)于y=xy=x軸對稱（舉例）軸

8、對稱（舉例）YXP(-y,-x)P(x,y)x=-y(e)關(guān)于x=-y對稱100001010(5)(5)關(guān)于關(guān)于y=-xy=-x軸對稱（舉例）軸對稱（舉例） 錯切變換，也稱為剪切、錯位變換，用錯切變換，也稱為剪切、錯位變換，用于產(chǎn)生彈性物體的變形處理。于產(chǎn)生彈性物體的變形處理。YXYXYX(a) 原圖(b) 沿x方向錯切(c) 沿y方向錯切圖6-7 錯切變換5.2.5 5.2.5 錯切變換錯切變換 其變換矩陣為： 1000101cb (1)沿沿x方向錯切方向錯切: b=0 (2)沿沿y方向錯切方向錯切: c=0 (3)兩個方向錯切兩個方向錯切5.2.6 5.2.6 二維圖形幾何變換的計算二維圖

9、形幾何變換的計算幾何變換均可表示成幾何變換均可表示成P P=P=P* *T T的形式的形式1. 1. 點的變換點的變換2. 2. 直線的變換直線的變換3. 3. 多邊形的變換多邊形的變換4. 4. 曲線的變換曲線的變換舉例說明舉例說明 1. 點的變換 rmlqdcpbayxyx112. 直線的變換rmlqdcpbayxyxyxyx111122112211 3. 多邊形的變換rmlqdcpbayxyxyxyxyxyxyxyxnnnn1.1111.1113322113322115.3 復(fù)合變換 圖形作一次以上的幾何變換，變換結(jié)果是每次變換矩陣的乘積。 任何一復(fù)雜的幾何變換都可以看作基本幾何變換的組

10、合形式。 復(fù)合變換具有形式：) 1( )(321321nTTTTPTTTTPTPPnn1010001101000110100012121221121yyxxyxyxtttTTTTTTTTTTT復(fù)合變換復(fù)合變換二維復(fù)合平移二維復(fù)合平移1000000100000010000002121221121yyxxyxyxsssSSSSSSSSTTT復(fù)合變換復(fù)合變換二維復(fù)合比例二維復(fù)合比例)(21)()(21RRRR1000)cos()sin(0)sin()cos(1000cossin0sincos1000cossin0sincos212121212222111121rrrTTT復(fù)合變換復(fù)合變換二維復(fù)合旋轉(zhuǎn)

11、二維復(fù)合旋轉(zhuǎn)1000cos000cos100010110001011000cos000cos1000 cos sin0 sincostgtgtgtgR其他二維復(fù)合變換其他二維復(fù)合變換相對任一參考點的二維幾何變換相對某個參考點(xF,yF)作二維幾何變換，其變換過程為：(1) 平移；(2) 針對原點進(jìn)行二維幾何變換；(3) 反平移。例1. 相對點(xF,yF)的旋轉(zhuǎn)變換100cossin0100010sincos001010011cossin0sincos0(cossin )(cossin )1RFFFFFFFFFFFTxyxyxxyyyx 相對任一參考點的二維幾何變換相對任一參考點的二維幾何變

12、換例2. 相對點(xF,yF)的比例變換10000100010000101001100001xRFyFFFFxyFxFFyFSTSxyxySSx Sxy Sy 相對任一參考點的二維幾何變換5.3.6 5.3.6 相對任意方向的二維幾何變換相對任意方向的二維幾何變換 相對任意方向作二維幾何變換，其變換的過程是：相對任意方向作二維幾何變換，其變換的過程是：(1) (1) 旋轉(zhuǎn)變換旋轉(zhuǎn)變換(2) (2) 針對坐標(biāo)軸進(jìn)行二維幾何變換；針對坐標(biāo)軸進(jìn)行二維幾何變換；(3) (3) 反向旋轉(zhuǎn)反向旋轉(zhuǎn)例例3. 3. 相對直線相對直線y=xy=x的反射變換的反射變換例例4. 4. 將正方形將正方形ABCOABC

13、O各點各點沿 圖沿 圖 6 - 86 - 8 所 示 的所 示 的(0,0)(1,1)(0,0)(1,1)方向進(jìn)行方向進(jìn)行拉伸，結(jié)果為如圖所示拉伸，結(jié)果為如圖所示的，寫出其變換矩陣和的，寫出其變換矩陣和變換過程。變換過程。YX13/21/21/23/222圖6-8 針對固定方向的拉伸OABCCBAoooooooocos( 45 )sin( 45 ) 000cos(45 )sin(45 ) 0sin( 45 ) cos( 45 ) 000sin(45 ) cos(45 ) 0001001001xySTS 112211222222222222222222000 0()() 00000()() 00

14、0100 100 1001xxyxyyxyxySSSSSSSSSS根據(jù)根據(jù)P= PP= P* *T T，計算得出，計算得出SxSx和和SySy。(0,0)(1,1)方向 即x=y 方向 ，于是按針對固定方向的變換形式進(jìn)行計算。拉伸，即比例變換（Sx=？Sy=？）5.3.7 5.3.7 坐標(biāo)系之間的變換坐標(biāo)系之間的變換問題問題：圖6-9 坐標(biāo)系間的變換xyxyOOx0y0p(xp,yp)可以分兩步進(jìn)行：可以分兩步進(jìn)行：xyyOOx0y0 x(a)將xy坐標(biāo)系的原點平移到xy坐標(biāo)系的原點p(xp,yp)xyOyx(b)將x軸旋轉(zhuǎn)到x軸上p(xp,yp)于是： RTtTpTpTpypxpypxp11

15、1000cossin0sincos101000100yxTTTrt5.3.8 5.3.8 光柵變換光柵變換直接對直接對幀緩存中像素點幀緩存中像素點進(jìn)行操作的變換稱為光柵進(jìn)行操作的變換稱為光柵變換。變換。 光柵平移變換：光柵平移變換： 9090、180180和和270270的光柵旋轉(zhuǎn)變換：的光柵旋轉(zhuǎn)變換： (y,rowlen-x)(y,rowlen-x)(rowlen-x,vollen-y)(rowlen-x,vollen-y)任意角度的光柵旋轉(zhuǎn)變換：任意角度的光柵旋轉(zhuǎn)變換： 旋轉(zhuǎn)的象素陣列光柵網(wǎng)格AA213光柵比例變換：光柵比例變換： 5.4 5.4 二維觀察二維觀察5.4.1 5.4.1 基

16、本概念基本概念在計算機(jī)圖形學(xué)中，將在用戶坐標(biāo)系中需要進(jìn)行在計算機(jī)圖形學(xué)中，將在用戶坐標(biāo)系中需要進(jìn)行觀察和處理的一個坐標(biāo)區(qū)域稱為觀察和處理的一個坐標(biāo)區(qū)域稱為窗口窗口（WindowWindow）。）。 （ 用戶坐標(biāo)系定義）用戶坐標(biāo)系定義）顯示設(shè)備上的坐標(biāo)區(qū)域稱為顯示設(shè)備上的坐標(biāo)區(qū)域稱為視區(qū)視區(qū)（ViewportViewport）（ 設(shè)備坐標(biāo)系定義）設(shè)備坐標(biāo)系定義）要將窗口內(nèi)的圖形在視區(qū)中顯示出來，必須經(jīng)過將窗口到視區(qū)要將窗口內(nèi)的圖形在視區(qū)中顯示出來，必須經(jīng)過將窗口到視區(qū)的變換（的變換（Window-Viewport TransformationWindow-Viewport Transformat

17、ion）處理，這種變換）處理，這種變換就是就是觀察變換觀察變換（Viewing TransformationViewing Transformation）。）。XYwxlXYwybwxrwyt窗口vxrvybvyt視區(qū)(a)用戶坐標(biāo)系中的窗口(b)屏幕坐標(biāo)系中的視區(qū)vxlXY窗口圖6-17 用戶坐標(biāo)系中旋轉(zhuǎn)的窗口獨立于設(shè)備獨立于設(shè)備 觀察坐標(biāo)系觀察坐標(biāo)系(View Coordinate)(View Coordinate)和規(guī)范化設(shè)備坐標(biāo)和規(guī)范化設(shè)備坐標(biāo)系系(Normalized Device Coordinate) (Normalized Device Coordinate) 觀察坐標(biāo)系是依據(jù)

18、窗口的方向和形狀在用戶坐標(biāo)平觀察坐標(biāo)系是依據(jù)窗口的方向和形狀在用戶坐標(biāo)平面中定義的直角坐標(biāo)系。面中定義的直角坐標(biāo)系。規(guī)范化設(shè)備坐標(biāo)系也是直角坐標(biāo)系，它是將二維的規(guī)范化設(shè)備坐標(biāo)系也是直角坐標(biāo)系，它是將二維的設(shè)備坐標(biāo)系規(guī)范化到（設(shè)備坐標(biāo)系規(guī)范化到（0.00.0，0.00.0）到（）到（1.01.0，1.01.0）的坐標(biāo)范圍內(nèi)形成的。的坐標(biāo)范圍內(nèi)形成的。引入了觀察坐標(biāo)系和規(guī)范化設(shè)備坐標(biāo)系后，觀察引入了觀察坐標(biāo)系和規(guī)范化設(shè)備坐標(biāo)系后，觀察變換分為如下圖所示的幾個步驟，通常稱為二維變換分為如下圖所示的幾個步驟，通常稱為二維觀察流程。觀察流程。 變焦距效果變焦距效果圖6-20 變焦距效果（窗口變、視區(qū)不變

19、）(a) 原圖及變化的窗口(b)與窗口對應(yīng)的視區(qū)1(c)與窗口對應(yīng)的視區(qū)2(d)與窗口對應(yīng)的視區(qū)3112323 整體放縮效果整體放縮效果(a) 原圖及窗口(b) 視區(qū)1圖6-21 整體放縮效果（窗口不變、視區(qū)變）(c) 視區(qū)2(d)視區(qū)3漫游效果漫游效果 5.4.2 5.4.2 用戶坐標(biāo)系到觀察坐標(biāo)系的變換用戶坐標(biāo)系到觀察坐標(biāo)系的變換用戶坐標(biāo)系到觀察坐標(biāo)系的變換分由兩個變換步驟用戶坐標(biāo)系到觀察坐標(biāo)系的變換分由兩個變換步驟合成：合成：1. 1. 將觀察坐標(biāo)系原點移動到用戶坐標(biāo)系原點將觀察坐標(biāo)系原點移動到用戶坐標(biāo)系原點x用戶y用戶窗口y觀察x觀察(a) 平移變換2. 2. 繞原點旋轉(zhuǎn)使兩坐標(biāo)系重合

20、繞原點旋轉(zhuǎn)使兩坐標(biāo)系重合 x用戶y用戶窗口y觀察x觀察(b) 旋轉(zhuǎn)變換00100cossin0010 . sincos01001tRTTTxy 5.4.3 5.4.3 窗口到視區(qū)的變換窗口到視區(qū)的變換XYwxlXYwybwxrwyt窗口vxlvybvyt視區(qū)圖6-23 窗口到視區(qū)的變換(a)窗口中的點(b)視區(qū)中的點(xw,yw)(xv,yv)vxr窗口視圖變換窗口視圖變換變換過程變換過程 要將窗口內(nèi)的點（要將窗口內(nèi)的點（xw,yw）映射到相對應(yīng)的視）映射到相對應(yīng)的視區(qū)內(nèi)的點（區(qū)內(nèi)的點（xv,yv）需）需進(jìn)行以下步驟：進(jìn)行以下步驟：(1) (1) 將窗口左下角點移至用戶系將窗口左下角點移至用戶

21、系統(tǒng)系的坐標(biāo)原點統(tǒng)系的坐標(biāo)原點( (平移平移) )(2) (2) 針對原點進(jìn)行比例變換針對原點進(jìn)行比例變換(3) (3) 進(jìn)行反平移進(jìn)行反平移5.5 5.5 裁剪裁剪在二維觀察中，需要在觀察坐標(biāo)系下對窗口進(jìn)行在二維觀察中，需要在觀察坐標(biāo)系下對窗口進(jìn)行裁剪，即只保留窗口內(nèi)的那部分圖形，去掉窗口裁剪，即只保留窗口內(nèi)的那部分圖形，去掉窗口外的圖形。外的圖形。( (判斷一個圖形元素是否落在窗口區(qū)域判斷一個圖形元素是否落在窗口區(qū)域內(nèi)內(nèi)) )假設(shè)窗口是標(biāo)準(zhǔn)矩形，即邊與坐標(biāo)軸平行的矩形，假設(shè)窗口是標(biāo)準(zhǔn)矩形，即邊與坐標(biāo)軸平行的矩形，由上（由上（y=wyty=wyt）、下（）、下（y=wyby=wyb）、左（）

22、、左（x=wxlx=wxl）、）、右（右（x=wxrx=wxr）四條邊描述。）四條邊描述。5.5.1 5.5.1 點的裁剪點的裁剪wytywybwxrxwxl且, 則點則點P(x,y)在窗口內(nèi)；在窗口內(nèi)；否則，在窗口之外。否則，在窗口之外。5.5.2 5.5.2 直線段的裁剪直線段的裁剪假定直線段用假定直線段用p p1 1(x(x1 1,y,y1 1)p)p2 2(x(x2 2,y,y2 2) )表示。表示。直線段和剪裁窗口的可能關(guān)系：直線段和剪裁窗口的可能關(guān)系：完全落在窗口內(nèi)完全落在窗口內(nèi)完全落在窗口外完全落在窗口外與窗口邊界相交與窗口邊界相交 窗口圖6-24 直線段與窗口的關(guān)系A(chǔ)BCDEF

23、HGIJ實交點是直線段與窗口矩形邊界的交點。實交點是直線段與窗口矩形邊界的交點。虛交點則是直線段與窗口矩形邊界延長線或直線虛交點則是直線段與窗口矩形邊界延長線或直線段的延長線與窗口矩形邊界的交點。段的延長線與窗口矩形邊界的交點。 窗口圖6-25 實交點與虛交點ABCDEFHGIJ虛交點實交點實交點實交點虛交點虛交點1 1. Cohen-Sutherland算法算法基本思想：對每條直線段基本思想：對每條直線段p1(x1,y1)p2(x2,y2)分三種情分三種情況處理：況處理：(1) 直線段完全可見，直線段完全可見，“簡取簡取”之。之。(2) 直線段完全不可見，直線段完全不可見，“簡棄簡棄”之。之

24、。(3) 直線段既不滿足直線段既不滿足“簡取簡取”的條件，也不滿足的條件，也不滿足“簡簡棄棄”的條件，需要對直線段按交點進(jìn)行分段，分的條件，需要對直線段按交點進(jìn)行分段，分段后重復(fù)上述處理。段后重復(fù)上述處理。 編碼：對于任一端點編碼：對于任一端點(x,y)，根據(jù)其坐標(biāo)所在的區(qū)域，賦予，根據(jù)其坐標(biāo)所在的區(qū)域，賦予一個一個4位的二進(jìn)制碼位的二進(jìn)制碼D3D2D1D0。編碼規(guī)則如下：編碼規(guī)則如下： 若若xwxr，則，則D1=1，否則，否則D1=0； 若若ywyt，則，則D3=1，否則，否則D3=0。 0000窗口01000101100100011010011010000010圖6-26 窗口及區(qū)域編碼D

25、3D2D1D0裁裁 剪剪裁剪一條線段時，先求出端點裁剪一條線段時，先求出端點p p1 1和和p p2 2的編碼的編碼code1code1和和code2code2，然后：，然后：(1)(1)若若code1|code2=0code1|code2=0，對直線段應(yīng)簡取之。，對直線段應(yīng)簡取之。(2)(2)若若code1&code20code1&code20，對直線段可簡棄之。，對直線段可簡棄之。(3)(3)若上述兩條件均不成立。則需求出直線段若上述兩條件均不成立。則需求出直線段與窗口邊界的交點。在交點處把線段一分為二，其與窗口邊界的交點。在交點處把線段一分為二，其中必有一段完全在窗口外，

26、可以棄之。再對另一段中必有一段完全在窗口外，可以棄之。再對另一段重復(fù)進(jìn)行上述處理，直到該線段完全被舍棄或者找重復(fù)進(jìn)行上述處理，直到該線段完全被舍棄或者找到位于窗口內(nèi)的一段線段為止。到位于窗口內(nèi)的一段線段為止。求交：假定直線的端點坐標(biāo)為求交：假定直線的端點坐標(biāo)為(x1,y1)和和(x2,y2)左、右邊界交點的計算：左、右邊界交點的計算： y = y1 + k(x - x1)上、下邊界交點的計算：上、下邊界交點的計算： x = x1 + (y-y1)/k其中，k（y2-y1）/（x2-x1）。）。窗口ABCDEFHGIJ虛交點實交點實交點實交點虛交點虛交點(1)(1)輸入直線段的兩端點坐標(biāo)：輸入直

27、線段的兩端點坐標(biāo)：p p1 1(x(x1 1,y,y1 1) )、p p2 2(x(x2 2,y,y2 2) )，以及窗，以及窗口的四條邊界坐標(biāo)：口的四條邊界坐標(biāo)：wytwyt、wybwyb、wxlwxl和和wxrwxr。(2)(2)對對p p1 1、p p2 2進(jìn)行編碼：點進(jìn)行編碼：點p p1 1的編碼為的編碼為code1code1，點，點p p2 2的編碼為的編碼為code2code2。(3)(3)若若code1|code2=0code1|code2=0，對直線段應(yīng)簡取之，轉(zhuǎn)，對直線段應(yīng)簡取之，轉(zhuǎn)(6)(6)；否則，若；否則，若code1&code20code1&code2

28、0，對直線段可簡棄之，轉(zhuǎn)，對直線段可簡棄之，轉(zhuǎn)(7)(7)；當(dāng)上述兩條；當(dāng)上述兩條均不滿足時，進(jìn)行步驟均不滿足時，進(jìn)行步驟(4)(4)。(4)(4)確保確保p p1 1在在窗口外部窗口外部：若：若p p1 1在窗口內(nèi)，則交換在窗口內(nèi)，則交換p p1 1和和p p2 2的坐標(biāo)的坐標(biāo)值和編碼。值和編碼。(5)(5)按按p p1 1的編碼從低位開始找編碼值為的編碼從低位開始找編碼值為1 1的地方，確定的地方，確定p p1 1在哪一在哪一側(cè)，然后求出與相應(yīng)窗口邊界的交點，并用該交點的坐標(biāo)側(cè)，然后求出與相應(yīng)窗口邊界的交點，并用該交點的坐標(biāo)值替換值替換p p1 1的坐標(biāo)值。也即在交點的坐標(biāo)值。也即在交點s

29、 s處把線段一分為二，并去處把線段一分為二，并去掉掉p p1 1s s這一段?？紤]到這一段。考慮到p p1 1是窗口外的一點，因此可以去掉是窗口外的一點，因此可以去掉p p1 1s s。轉(zhuǎn)轉(zhuǎn)(2)(2)。(6)(6)用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段p p1 1p p2 2。(7)(7)算法結(jié)束。算法結(jié)束。 算法演示算法演示算法的步驟：算法的步驟： 作業(yè)1 直線段裁剪的Cohen-Sutherland算法實現(xiàn) 要求要求：編寫直線段裁剪函數(shù)以及主函數(shù)。輸入輸入：觀察窗口的四個邊界值wxl,wxr,wyb,wyt和直線段的端點坐標(biāo)p1(x1,y1)，p2(x2,y

30、2)。輸出輸出：觀察窗口內(nèi)部的線段端點坐標(biāo)。如不在觀察窗口內(nèi)，則輸出提示信息。語言語言：cc+javac#。注意注意：提交代碼（不要使用附件），包含必要的注釋，抄襲零分。 截止日期 2015年10月20日 下午11時59分00秒 滿分15分第一次作業(yè) 用編碼方法實現(xiàn)了對完全可見和不可見直線段的快速接受和拒絕； 求交點過程復(fù)雜，有冗余計算，并且包含浮點運(yùn)算，不利于硬件實現(xiàn)。Cohen-Sutherland算法2. 2. 中點分割算法中點分割算法基本思想：基本思想： 當(dāng)對直線段不能簡取也不能簡棄時，簡單當(dāng)對直線段不能簡取也不能簡棄時，簡單地把線段等分為二段，對兩段重復(fù)上述測試處地把線段等分為二段，

31、對兩段重復(fù)上述測試處理，直至每條線段完全在窗口內(nèi)或完全在窗口理，直至每條線段完全在窗口內(nèi)或完全在窗口外。外。 (1)(1)輸入直線段的兩端點坐標(biāo)：輸入直線段的兩端點坐標(biāo)：p p1 1(x(x1 1,y,y1 1) )、p p2 2(x(x2 2,y,y2 2) )，以及窗，以及窗口的四條邊界坐標(biāo)：口的四條邊界坐標(biāo)：wytwyt、wybwyb、wxlwxl和和wxrwxr。(2)(2)對對p p1 1、p p2 2進(jìn)行編碼：點進(jìn)行編碼：點p p1 1的編碼為的編碼為code1code1，點，點p p2 2的編碼為的編碼為code2code2。(3)(3)若若code1|code2=0code1|

32、code2=0，對直線段應(yīng)簡取之，保留當(dāng)前直線段的，對直線段應(yīng)簡取之，保留當(dāng)前直線段的端點坐標(biāo)，轉(zhuǎn)端點坐標(biāo)，轉(zhuǎn)(5)(5)；否則，若；否則，若code1&code20code1&code20，對直線段可，對直線段可簡棄之，轉(zhuǎn)簡棄之，轉(zhuǎn)(5)(5)；當(dāng)上述兩條均不滿足時，進(jìn)行步驟；當(dāng)上述兩條均不滿足時，進(jìn)行步驟(4)(4)。(4)(4)求出直線段的中點求出直線段的中點M M，將，將p p1 1M M、p p2 2M M入棧。入棧。(5)(5)當(dāng)棧不空時，從棧中彈出一條直線段，取為當(dāng)棧不空時，從棧中彈出一條直線段，取為p p1 1p p2 2，轉(zhuǎn)，轉(zhuǎn)(2)(2)進(jìn)進(jìn)行處理。否則，繼續(xù)行處理。否則，繼續(xù)(6)(6)。(6)(6)當(dāng)棧為空時，合并保留的直線段端點，得到窗口內(nèi)的直線當(dāng)棧為空時，合并保留的直線段端點，得到窗口內(nèi)的直線段