圖形變換與裁剪

1、哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院唐好選2022年年5月月3日日圖形變換與裁剪1.窗口和視圖區(qū)窗口和視圖區(qū)用戶坐標(biāo)系用戶坐標(biāo)系（world coordinate system，簡稱WCS）設(shè)備坐標(biāo)系設(shè)備坐標(biāo)系（device coordinate system，簡稱DCS）窗口區(qū)窗口區(qū)（window）視圖區(qū)視圖區(qū)（viewport） 2.窗口到視圖區(qū)的變換窗口到視圖區(qū)的變換窗口區(qū)與視圖區(qū)間的映射關(guān)系： 窗口區(qū)中的任一點(diǎn)(x w , y w) 與視圖區(qū)中的任一點(diǎn)(x v , y v) 存在如下對應(yīng)關(guān)系：xlxrxlxrxlwxlvwwvvwxvxybytybytybwybvwwvvwyvy（5-1）（5-2

2、）X wO wW x lW x rY wW y bW y t窗口(x w , y w)Y vX vO uV x lV x rV y bV y t視圖區(qū)(x v , y v)xlxlwxlxrxlxrvvwxwwvvx)(ybybwybytybytvvwywwvvy)(（5-3）（5-4）由式（5-1）和式（5-2）可分別解得：令xlxrxlxrwwvvaybytybytwwvvbxlxlxlxrxlxrvwwwvvcybybybytybytvwwwvvd有baxxwvdcyywv（5-5） （5-6） 5.2.1 二維圖形幾何變換的原理 二維圖形由點(diǎn)或直線段組成 直線段可由其端點(diǎn)坐標(biāo)定義 二維

3、圖形的幾何變換：對點(diǎn)或?qū)χ本€段端點(diǎn)的變換yxP yxP1.平移變換（平移變換（translation）平行于x軸的方向上的移動量平行于y軸的方向上的移動量 xT yT 5.2.2幾種典型的二維圖形幾何變換xxTyPPyT平移變換yxTyyTxx幾何關(guān)系（5-7）yxTTyxyx矩陣形式（5-8）平行于x軸的方向上的縮放量平行于y軸的方向上的縮放量2.比例變換（比例變換（scale）xSyS指相對于原點(diǎn)的比例變換 yx相對于原點(diǎn)原點(diǎn)的比例變換相對于重心重心的比例變換yx重心yxSSyxyx00 矩陣形式（5-10）yxSyySxx幾何關(guān)系（5-9）比例變換的性質(zhì)當(dāng) 時，變換前的圖形與變換后的圖形

4、相似 當(dāng) 時，圖形將放大，并遠(yuǎn)離坐標(biāo)原點(diǎn) 當(dāng) 時，圖形將縮小，并靠近坐標(biāo)原點(diǎn)當(dāng) 時，圖形將發(fā)生畸變 10yxSSyxSS 1yxSSyxSS 1yxSSyxSS 3.旋轉(zhuǎn)變換（旋轉(zhuǎn)變換（rotation） 點(diǎn)P繞原點(diǎn)逆時針轉(zhuǎn)角（設(shè)逆時針旋轉(zhuǎn)方向?yàn)檎较颍ヽossinsincos)sin(sinsincoscos)cos(rrryrrrx（5-12）cossinsincosyxyyxx將式（5-11）代入式（5-12）得：（5-13）sincos ryrx（5-11）幾何關(guān)系（5-14） cossinsincos yxyx矩陣形式PPyx旋轉(zhuǎn)變換（homogeneous coordinates）

5、 1.齊次坐標(biāo)技術(shù)的引入齊次坐標(biāo)技術(shù)的引入 平移、比例和旋轉(zhuǎn)等變換的組合變換 處理形式不統(tǒng)一，將很難把它們級聯(lián)在一起。 2.變換具有統(tǒng)一表示形式的優(yōu)點(diǎn)變換具有統(tǒng)一表示形式的優(yōu)點(diǎn) 便于變換合成 便于硬件實(shí)現(xiàn) 3.齊次坐標(biāo)技術(shù)的基本思想齊次坐標(biāo)技術(shù)的基本思想 把一個n維空間中的幾何問題轉(zhuǎn)換到n+1維空間中解決 4.4.齊次坐標(biāo)表示齊次坐標(biāo)表示齊次坐標(biāo)表示不是唯一的),.,(21nxxx)/,.,/,/(21nxxx ),.,(21nxxx有n個分量的向量),.,(21nxxx有n+1個分量的向量1規(guī)格化的齊次坐標(biāo) 平移變換 101000111yxTTyxyx 100000011yxSSyxyx 1

6、000cossin0sincos11yxyx 比例變換 旋轉(zhuǎn)變換：6. 無窮遠(yuǎn)點(diǎn)或無窮遠(yuǎn)區(qū)域的齊次坐標(biāo)表示無窮遠(yuǎn)點(diǎn)或無窮遠(yuǎn)區(qū)域的齊次坐標(biāo)表示時，齊次坐標(biāo) 表示一個n維的無窮遠(yuǎn)點(diǎn) 0),.,(21nxxx 1.對稱變換對稱變換（symmetry）（反射變換或鏡像變換） （1）相對于y軸對稱yyxx關(guān)系幾何 1100010001 11yxyxyx形式矩陣oyx對稱變換（1）yxo對稱變換（2）（2）相對于x軸對稱yyxx關(guān)系幾何 1100010001 11yxyxyx形式矩陣（3）相對于原點(diǎn)對稱（即中心對稱）（4）相對于直線y=x對稱yyxx 1100010001 11yxyxyx關(guān)系幾何形式矩陣

7、形式矩陣關(guān)系幾何xyyx 110000101011xyyxyxoxy對稱變換（3）xyoy=x對稱變換（4）（5）相對于直線y=-x對稱xyyx幾何關(guān)系 110000101011xyyxyx矩陣形式xyoy=-x對稱變換（5）2.錯切變換（錯切變換（shear）（1）沿 x 軸方向關(guān)于 y 軸錯切 將圖形上關(guān)于y軸的平行線沿x方向推成角的 傾斜線，而保持y坐標(biāo)不變。x 錯切變換（1）yxayyctgx 有ctga 令yyayxx yyxxx 幾何關(guān)系 11000100111yayxayxyx矩陣形式（2）沿 y 軸方向關(guān)于 x 軸錯切 將圖形上關(guān)于x軸的平行線沿y方向推成角的傾斜線，而保持x坐

8、標(biāo)不變。 x 錯切變換（2）yy 11000100111ybxxbyxyx矩陣形式幾何關(guān)系yyyxx bxxctgyctgb 令bxyyxx 1.相對于任意點(diǎn)（相對于任意點(diǎn)（x0 , y0）的比例變換）的比例變換 對任意點(diǎn)比例變換的步驟： （1）平移變換 （2）相對于原點(diǎn)的比例變換 （3）平移變換 當(dāng)（x0 , y0）為圖形重心的坐標(biāo)時，這種變換實(shí)現(xiàn)的是相對于重心的比例變換。 1010001001yxT1000000yxSSS1010001002yxT 1000000 112233yxSSyxyx 1010001 11001122yxyxyx 1010001 11003344yxyxyx任意點(diǎn)

9、比例變換示意圖平移 111yx平移比例 21STTT TyxSTTyxyxyx 1 111112111442.繞任意點(diǎn)（繞任意點(diǎn)（x0 , y0）的旋轉(zhuǎn)變換）的旋轉(zhuǎn)變換 繞任意點(diǎn)旋轉(zhuǎn)變換的步驟： （1）平移變換 （2）對圖形繞原點(diǎn)進(jìn)行旋轉(zhuǎn)變換 （3）平移變換 (x2,y2)(x3,y3)(x0,y0)Oxy(x1,y1)(x4,y4)相對于任意點(diǎn)(x0,y0)的旋轉(zhuǎn)變換 1000cossin0sincos 112233yxyx 1010001 11001122yxyxyx 1010001 11003344yxyxyx任意點(diǎn)旋轉(zhuǎn)變換示意圖平移 100yx平移旋轉(zhuǎn)1010001001yxT1000

10、cossin0sincos R1010001002yxT 21RTTT TyxRTTyxyxyx 1 11111211144三維齊次坐標(biāo)三維齊次坐標(biāo)(x,y,z)點(diǎn)對應(yīng)的齊次坐標(biāo)為點(diǎn)對應(yīng)的齊次坐標(biāo)為標(biāo)準(zhǔn)齊次坐標(biāo)標(biāo)準(zhǔn)齊次坐標(biāo)(x,y,z,1)右手坐標(biāo)系右手坐標(biāo)系),(hzyxhhh0,hhzzhyyhxxhhhxyz平移變換平移變換 1010000100001zyxTTTT放縮變換放縮變換1000000000000zyxsssS 旋轉(zhuǎn)變換旋轉(zhuǎn)變換:右手螺旋方向?yàn)檎沂致菪较驗(yàn)檎?繞繞x軸軸100000000001cossinsincos)(xRyxyzzyzoox軸指向紙外1000000100

11、0cossinsincos)(yR 繞繞y軸軸zyzxxzxooy軸指向紙外 繞繞z軸軸100001000000cossinsincos)(zRxzxyyxyooz軸指向紙外錯切變換錯切變換zyxzyxzyxzyxzyxzyx三維錯切變換沿z含x錯切沿z含y錯切沿y含x錯切沿y含z錯切沿x含y錯切 沿x含z錯切三維變換的一般形式三維變換的一般形式旋轉(zhuǎn)、比例、錯切、對稱平移透視投影總體比例44434241343332312423222114131211aaaaaaaaaaaaaaaaA1 三維圖形的基本問題 2平面幾何投影 平行投影 透視投影顯示器屏幕、繪圖紙等是二維的顯示對象是三維的解決方法-

12、投影1. 在二維屏幕上如何顯示三維物體？在二維屏幕上如何顯示三維物體？2. 如何表示三維物體？如何表示三維物體？三維形體的表示-空間直線段、曲線段、多邊形、曲面片三維形體的輸入、運(yùn)算、有效性保證-困難解決方法-各種用于形體表示的理論、模型、方法3. 如何反映遮擋關(guān)系？如何反映遮擋關(guān)系？物體之間或物體的不同部分之間存在相互遮擋關(guān)系解決方法-消除隱藏面與隱藏線何謂真實(shí)感圖形？真實(shí)感來源于透視關(guān)系和遮擋關(guān)系光線傳播引起的物體表面顏色的自然分布解決方法建立光照明模型真實(shí)感圖形繪制4. 如何產(chǎn)生真實(shí)感圖形如何產(chǎn)生真實(shí)感圖形三維圖形的基本研究內(nèi)容1. 投影2. 三維形體的表示3. 消除隱藏面與隱藏線4.

13、建立光照明模型、研究真實(shí)感圖形繪制方法 如何投影? 生活中的類比-如何拍攝景物？拍攝過程選景取景-裁剪對焦參考點(diǎn)按快門-成像移動方式移動景物移動照相機(jī)投影照相機(jī)模型選定投影類型 設(shè)置投影參數(shù) 拍攝方向、距離等三維裁剪 取景投影和顯示 成像平面幾何投影及其分類 投影將n維的點(diǎn)變換成小于n維的點(diǎn) 將3維的點(diǎn)變換成小于3維的點(diǎn)投影中心觀察點(diǎn)、視點(diǎn)投影面不經(jīng)過投影中心投影線從投影中心向物體上各點(diǎn)發(fā)出的射線 平面幾何投影 投影面是平面投影線為直線 投影變換投影過程投影的數(shù)學(xué)表示 投影分類透視投影透視投影平行投影平行投影平行投影 投影中心與投影平面之間的距離為無限投影方向投影方向投影平面投影平面正投影與斜

14、投影正平行投影正平行投影斜平行投影斜平行投影 三視圖：正視圖、側(cè)視圖和俯視圖 yx主視圖俯視圖側(cè)視圖一個直角棱臺的三視圖z 1000010000000001vTyx主視圖一個直角棱臺的三視圖z正視圖側(cè)視圖yx側(cè)視圖一個直角棱臺的三視圖z100010000100001100001000090cos90sin0090sin90cos1000010000100000LwxT俯視圖 yx俯視圖一個直角棱臺的三視圖z10001000010000110000)90cos()90sin(00)90sin()90cos(000011000000000100001phzT從三視圖很難想象出實(shí)際物體的空間形狀解決

15、：投影平面不垂直于任何一個坐標(biāo)軸正軸測投影正軸測投影 yxz圖5 正軸測投影平面的定義10000cossin00sincos0000110000cos0sin00100sin0cosxyyxRRR10000coscossincossin0sincos00cossinsinsincos1000000000100001yxRT100000sincossin00cos000sinsincos Tzyxzyx11 投影方程：120 120120(a) 正等軸測 y z x投影平面三個單位向量將投影成三個長度相等的平面向量，即三根坐標(biāo)軸有相同的變形系數(shù) Tzyxx.10011.10sinsincosTz

16、yxy.10101.10cos0Tzyxz.11001 .10sincossin100000sincossin00cos000sinsincosT(c)正三軸測yzx投影平面(b)正二軸測投影平面 y z x透視投影 投影中心與投影平面之間的距離為有限 參數(shù)：投影方向，距離 例子：室內(nèi)白熾燈的投影，視覺系統(tǒng)特點(diǎn)：產(chǎn)生近大遠(yuǎn)小的視覺效果，由它產(chǎn)生的圖形深度感強(qiáng)，看起來更加真實(shí)。透視投影投影方程yxz投影中心dxyPPyxz投影平面一點(diǎn)透視dr/1dzxdzxdx)|(|dzydzydy)|(|1)/(dzxx1)/(dzyy100010000100001rT11111rzzrzyrzxzyx滅點(diǎn)

17、的個數(shù)滅點(diǎn)的個數(shù)?滅點(diǎn)：不平行于投影平面的平行線，經(jīng)過透視投影之后相交于一點(diǎn)，稱為滅點(diǎn).yxzz軸滅點(diǎn)正方體的一點(diǎn)透視及其滅點(diǎn)正方體的一點(diǎn)透視及其滅點(diǎn)空間平行線可認(rèn)為是相交于無窮遠(yuǎn)點(diǎn)，空間平行線可認(rèn)為是相交于無窮遠(yuǎn)點(diǎn)，滅點(diǎn)可以看成是無窮遠(yuǎn)點(diǎn)經(jīng)透視投影后得到的點(diǎn)滅點(diǎn)可以看成是無窮遠(yuǎn)點(diǎn)經(jīng)透視投影后得到的點(diǎn) rrHzyx1001000100001000010100 1/1001rzyx滅點(diǎn)的位置滅點(diǎn)的位置?一點(diǎn)透視兩點(diǎn)透視三點(diǎn)透視主滅點(diǎn):平行于坐標(biāo)軸的平行線產(chǎn)生的滅點(diǎn)。 一點(diǎn)透視 兩點(diǎn)透視 三點(diǎn)透視主滅點(diǎn)的個數(shù)由什么決定主滅點(diǎn)的個數(shù)由什么決定?圖形變換與裁剪（三）圖形變換與裁剪（三）1 直線段裁剪直

18、接求交算法Cohen-Sutherland算法 中點(diǎn)分割裁剪算法 梁友棟-Basky算法2 多邊形裁剪 Sutlerland_Hodgman算法 Weiler-Atherton算法 裁剪的目的判斷圖形元素是否在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交裁剪、覆蓋裁剪窗口裁剪窗口矩形、圓形、一般多邊形矩形、圓形、一般多邊形被裁剪對象被裁剪對象線段、多邊形、曲線、字符線段、多邊形、曲線、字符裁剪的策略裁剪的策略先裁剪，后變換，可避免對窗口外的圖形進(jìn)行變先裁剪，后變換，可避免對窗口外的圖形進(jìn)行變換，效率較高換，效率較高先變換，后裁剪先變換，后裁剪裁剪算

19、法的核心問題裁剪算法的核心問題效率效率點(diǎn)裁剪點(diǎn)裁剪 點(diǎn)點(diǎn)(x, y)在窗口內(nèi)的充分必要條件是：在窗口內(nèi)的充分必要條件是： 問題：對于任意多邊形窗口，如何判別？問題：對于任意多邊形窗口，如何判別？maxminxxxmaxminyyy假定條件矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪線段：任何平面線段相對于凸多邊形窗口進(jìn)行裁剪后落在窗口內(nèi)的線段不會多于一條PxyP xy000111(,)(,)待裁剪線段和窗口的關(guān)系待裁剪線段和窗口的關(guān)系 （1）完全落在窗口內(nèi)）完全落在窗口內(nèi)（2）完全落在窗口外）完全落在窗口外（3）部分在內(nèi)，部分在外）部分在內(nèi)，部分在外為提高效率，算法設(shè)計(jì)時應(yīng)考慮：為

20、提高效率，算法設(shè)計(jì)時應(yīng)考慮：1. 快速判斷情形快速判斷情形(1)(2)；2. 設(shè)法減少情形設(shè)法減少情形(3)求交次數(shù)和每次求交時求交次數(shù)和每次求交時所需的計(jì)算量所需的計(jì)算量Cohen-Sutherland 算法算法 (編碼算法編碼算法)算法步驟：算法步驟：第一步第一步 判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是， 則線段完全可見；否則進(jìn)入第二步；則線段完全可見；否則進(jìn)入第二步；第二步第二步 判別線段是否為顯然不可見，如果是，則裁判別線段是否為顯然不可見，如果是，則裁 剪結(jié)束；否則進(jìn)行第三步剪結(jié)束；否則進(jìn)行第三步 ；第三步第三步 求線段與窗口邊延長線的交點(diǎn)，這

21、個交點(diǎn)將求線段與窗口邊延長線的交點(diǎn)，這個交點(diǎn)將 線段分為兩段，其中一段顯然不可見，丟棄。對余下的另線段分為兩段，其中一段顯然不可見，丟棄。對余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束 裁剪過程是遞歸的。裁剪過程是遞歸的。elseyyCt01max當(dāng)elsexxCr01max當(dāng)elsexxCl01min當(dāng)elseyyCb01min當(dāng) 特點(diǎn)：特點(diǎn)：對顯然不可見線段的快速判別對顯然不可見線段的快速判別 編碼方法：編碼方法：由窗口四條邊所在直線把二維平面分成由窗口四條邊所在直線把二維平面分成9個區(qū)域，每個區(qū)域個區(qū)域，每個區(qū)域賦予一個四位編碼，賦予一個四位編

22、碼， CtCbCrCl， 上下右左；上下右左；端點(diǎn)編碼：端點(diǎn)編碼：定義為它所在區(qū)域的編碼定義為它所在區(qū)域的編碼結(jié)論：結(jié)論：當(dāng)線段的兩個端點(diǎn)的編碼的邏輯當(dāng)線段的兩個端點(diǎn)的編碼的邏輯“與與”非零時非零時 ，顯然不可見，顯然不可見 100000010010000001001001010101101010窗口bca 求交測試順序固定求交測試順序固定(左上右下）左上右下） 最壞情形，線段求交四次。最壞情形，線段求交四次。對于那些非完全可見、又非完全不可見的線段，需要求交，對于那些非完全可見、又非完全不可見的線段，需要求交，求交前先測試與窗口哪條邊所在直線有交？求交前先測試與窗口哪條邊所在直線有交？(按序

23、判斷端點(diǎn)編按序判斷端點(diǎn)編碼中各位的值碼中各位的值ClCtCrCb） 1）特點(diǎn)：用編碼方法可快速判斷線段特點(diǎn)：用編碼方法可快速判斷線段-完全可見和顯然完全可見和顯然不可見。不可見。 2）特別適用二種場合：）特別適用二種場合： 大窗口場合大窗口場合 窗口特別小的場合窗口特別小的場合 基本思想：基本思想： 從從P0點(diǎn)出發(fā)找出距點(diǎn)出發(fā)找出距P0最近的可見點(diǎn)最近的可見點(diǎn) 從從P1點(diǎn)出發(fā)找出距點(diǎn)出發(fā)找出距P1最近的可見點(diǎn)最近的可見點(diǎn) 不斷地在中點(diǎn)處將線段一分為二，對每段線段重復(fù)不斷地在中點(diǎn)處將線段一分為二，對每段線段重復(fù)Cohen-Sutherland裁剪算法的線段可見性測試方法，直至找到每段線段與窗口邊

24、界線的裁剪算法的線段可見性測試方法，直至找到每段線段與窗口邊界線的交點(diǎn)或分割子段的長度充分小可視為一點(diǎn)為止交點(diǎn)或分割子段的長度充分小可視為一點(diǎn)為止 取中點(diǎn)取中點(diǎn)Pm=(P1+P2)/2。P2P1 P2是離是離P1點(diǎn)最遠(yuǎn)的可見點(diǎn)點(diǎn)最遠(yuǎn)的可見點(diǎn)PmP1用用P1Pm代替代替P1P2P2P2用用PmP2代替代替P1P2PmP1 步驟： 步驟1：利用線段的端點(diǎn)編碼判斷P1P2是否完全在窗口內(nèi)，若是，則畫線段P1P2,裁剪過程結(jié)束；若不是，再判斷是否完全在窗口外，若是，則無可見線段輸出，裁剪結(jié)束，否則轉(zhuǎn)步驟2； 步驟2：固定P1，測試P2是否在窗口內(nèi)，若是，則P2是離P1最遠(yuǎn)的可見點(diǎn)，返回，否則，轉(zhuǎn)步驟3

25、； 步驟3：將線段P1P2對分，求出中點(diǎn)Pm,編碼判斷線段PmP2是否全部在窗口外，若是，則舍棄PmP2,用P1Pm代替P1P2，若不是，則用PmP2代替P1P2； 步驟4：對新的P1P2重復(fù)步驟1-3，直到線段的長度小于給定的誤差時為止，此時可認(rèn)為在給定精度內(nèi)求得離P1最遠(yuǎn)的可見點(diǎn)Pm; 步驟5：固定P2,再測P1,即將線段P1P2的端點(diǎn)對調(diào)，重復(fù)步驟1-3，找出離點(diǎn)P2最遠(yuǎn)的可見點(diǎn)Pm; 步驟6：畫可見線段PmPm直線直線L與區(qū)域的交：與區(qū)域的交：當(dāng)當(dāng)Q為空集時，線段為空集時，線段AB不可能在窗口中有可見線段。不可能在窗口中有可見線段。當(dāng)當(dāng)Q不為空集時，不為空集時，Q可看成是一個一維窗口可

26、看成是一個一維窗口 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口是一維窗口TS中的可見部分中的可見部分基本思想：基本思想： 把二維裁剪化為一維裁剪問題，并向把二維裁剪化為一維裁剪問題，并向x（或（或y）方向投影以決定可見線段。）方向投影以決定可見線段。Q,;,;,maxminmaxmin4321yyxxLPPPPL),;,(),;,(maxminmaxminyyLxxLTURSP4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口是一維窗口TS中的可見部分中的可見部分存在可見線段的充要條件存在可見線段的充要條件 不為空集不為空集 向向x軸投

27、影，就得到可見線段上點(diǎn)的坐標(biāo)的變化范圍為軸投影，就得到可見線段上點(diǎn)的坐標(biāo)的變化范圍為 TURSAB),max(),max(,min),min(),min(,maxmaxminUTBAUTBAxxxxxxxxxxx),max(),max(,min),min(),min(,maxmaxminUTBAUTBAxxxxxxxxxxxx左端點(diǎn)左端點(diǎn)右端點(diǎn)右端點(diǎn)AB有可見部分的充分必要條件也可表示為有可見部分的充分必要條件也可表示為 ),max(),max(,min),min(),min(,maxmaxminUTBAUTBAxxxxxxxxxx),min(,maxminBAxxxL ),max(,minm

28、axBAxxxR RxxxxLRLUTUT),min(),max(用直線段裁剪算法，可以嗎？用直線段裁剪算法，可以嗎？新的問題新的問題：圖圖1 因丟失頂點(diǎn)信息而無法確定裁剪區(qū)域因丟失頂點(diǎn)信息而無法確定裁剪區(qū)域ABAB圖圖2 原來封閉的多邊形變成了孤立的線段原來封閉的多邊形變成了孤立的線段邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它12123(a)(b)(c)AB圖圖3 裁剪后的多邊形頂點(diǎn)形成的幾種情況裁剪后的多邊形頂點(diǎn)形成的幾種情況分裂為幾個多邊形分裂為幾個多邊形關(guān)鍵：關(guān)鍵：不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)還在

29、于形成正確的頂點(diǎn)序列還在于形成正確的頂點(diǎn)序列分割處理策略分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。在直線的裁剪。流水線過程流水線過程(左上右下左上右下)：左邊的結(jié)果是右邊的開始左邊的結(jié)果是右邊的開始。亦稱逐邊裁剪算法亦稱逐邊裁剪算法內(nèi)側(cè)空間與外側(cè)空間內(nèi)側(cè)空間與外側(cè)空間多邊形的邊與半空間的關(guān)系多邊形的邊與半空間的關(guān)系 線段與當(dāng)前裁剪邊的位置關(guān)系線段與當(dāng)前裁剪邊的位置關(guān)系可見一側(cè)可見一側(cè)窗口窗口(a) 輸出輸出Pi+1當(dāng)前裁剪邊Pi+1Pi可見一側(cè)可見一側(cè)窗口窗口(a) 無輸出無輸出當(dāng)前裁剪邊Pi+1Pi可見

30、一側(cè)可見一側(cè)窗口窗口(a) 輸出輸出I當(dāng)前裁剪邊Pi+1Pi可見一側(cè)可見一側(cè)窗口窗口(a) 輸出輸出I和和Pi+1當(dāng)前裁剪邊Pi+1Pi裁剪結(jié)果的頂點(diǎn)構(gòu)成裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多邊形的邊與裁剪邊的交點(diǎn)。多邊形的邊與裁剪邊的交點(diǎn)。順序連接。順序連接。優(yōu)點(diǎn)：優(yōu)點(diǎn)：裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)。裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)?？赏茝V到任意凸多邊形裁剪窗口可推廣到任意凸多邊形裁剪窗口逐邊裁剪要求裁剪窗口為凸多邊形，那么凹多邊形窗口怎么辦？逐邊裁剪要求裁剪窗口為凸多邊形，那么凹多邊形窗口怎么辦？逐邊裁剪法對凹多邊形裁剪時，裁剪后分裂為幾個多邊形，這幾逐邊裁剪法對凹多邊形裁剪時，裁剪后分裂為幾個多邊形，這幾個多邊形