圖形變換及裁剪

1、哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院唐好選2022年年2月月10日日?qǐng)D形變換與裁剪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） 窗口區(qū)與視圖區(qū)間的映射關(guān)系： 窗口區(qū)中的任一點(diǎn)(x w , y w) 與視圖區(qū)中的任一點(diǎn)(x v , y v) 存在如下對(duì)應(yīng)關(guān)系：xlxrxlxrxlwxlvwwvvwxvxybytybytybwybvwwvvwyvy（5-1）（5-2）X wO wW x lW x rY

2、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)定義 二維圖形的幾何變換：對(duì)點(diǎn)或?qū)χ本€段端點(diǎn)的變

3、換yxP yxP平行于x軸的方向上的移動(dòng)量平行于y軸的方向上的移動(dòng)量 xT yT 5.2.2幾種典型的二維圖形幾何變換xxTyPPyT平移變換yxTyyTxx幾何關(guān)系（5-7）yxTTyxyx矩陣形式（5-8）平行于x軸的方向上的縮放量平行于y軸的方向上的縮放量xSyS指相對(duì)于原點(diǎn)的比例變換 yx相對(duì)于原點(diǎn)原點(diǎn)的比例變換相對(duì)于重心重心的比例變換yx重心yxSSyxyx00 矩陣形式（5-10）yxSyySxx幾何關(guān)系（5-9）比例變換的性質(zhì)當(dāng) 時(shí)，變換前的圖形與變換后的圖形相似 當(dāng) 時(shí)，圖形將放大，并遠(yuǎn)離坐標(biāo)原點(diǎn) 當(dāng) 時(shí)，圖形將縮小，并靠近坐標(biāo)原點(diǎn)當(dāng) 時(shí)，圖形將發(fā)生畸變 10yxSSyxSS

4、1yxSSyxSS 1yxSSyxSS 點(diǎn)P繞原點(diǎn)逆時(shí)針轉(zhuǎn)角（設(shè)逆時(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)變換 1.齊次坐標(biāo)技術(shù)的引入齊次坐標(biāo)技術(shù)的引入 平移、比例和旋轉(zhuǎn)等變換的組合變換 處理形式不統(tǒng)一，將很難把它們級(jí)聯(lián)在一起。 2.變換具有統(tǒng)一表示形式的優(yōu)點(diǎn)變換具有統(tǒng)一表示形式的優(yōu)點(diǎn) 便于變換合成 便于硬件實(shí)現(xiàn) 3.齊次坐

5、標(biāo)技術(shù)的基本思想齊次坐標(biāo)技術(shù)的基本思想 把一個(gè)n維空間中的幾何問題轉(zhuǎn)換到n+1維空間中解決 齊次坐標(biāo)表示不是唯一的),.,(21nxxx)/,.,/,/(21nxxx ),.,(21nxxx有n個(gè)分量的向量),.,(21nxxx有n+1個(gè)分量的向量1規(guī)格化的齊次坐標(biāo) 平移變換 101000111yxTTyxyx 100000011yxSSyxyx 1000cossin0sincos11yxyx 比例變換 旋轉(zhuǎn)變換：時(shí)，齊次坐標(biāo) 表示一個(gè)n維的無窮遠(yuǎn)點(diǎn) 0),.,(21nxxx 1.對(duì)稱變換對(duì)稱變換（symmetry）（反射變換或鏡像變換） （1）相對(duì)于y軸對(duì)稱yyxx關(guān)系幾何 11000100

6、01 11yxyxyx形式矩陣oyx對(duì)稱變換（1）yxo對(duì)稱變換（2）（2）相對(duì)于x軸對(duì)稱yyxx關(guān)系幾何 1100010001 11yxyxyx形式矩陣（3）相對(duì)于原點(diǎn)對(duì)稱（即中心對(duì)稱）（4）相對(duì)于直線y=x對(duì)稱yyxx 1100010001 11yxyxyx關(guān)系幾何形式矩陣形式矩陣關(guān)系幾何xyyx 110000101011xyyxyxoxy對(duì)稱變換（3）xyoy=x對(duì)稱變換（4）（5）相對(duì)于直線y=-x對(duì)稱xyyx幾何關(guān)系 110000101011xyyxyx矩陣形式xyoy=-x對(duì)稱變換（5）（1）沿 x 軸方向關(guān)于 y 軸錯(cuò)切 將圖形上關(guān)于y軸的平行線沿x方向推成角的 傾斜線，而保持y

7、坐標(biāo)不變。x 錯(cuò)切變換（1）yxayyctgx 有ctga 令yyayxx yyxxx 幾何關(guān)系11000100111yayxayxyx矩陣形式（2）沿 y 軸方向關(guān)于 x 軸錯(cuò)切 將圖形上關(guān)于x軸的平行線沿y方向推成角的傾斜線，而保持x坐標(biāo)不變。 x 錯(cuò)切變換（2）yy 11000100111ybxxbyxyx矩陣形式幾何關(guān)系yyyxx bxxctgyctgb 令bxyyxx 1.相對(duì)于任意點(diǎn)（相對(duì)于任意點(diǎn)（x0 , y0）的比例變換）的比例變換 對(duì)任意點(diǎn)比例變換的步驟： （1）平移變換 （2）相對(duì)于原點(diǎn)的比例變換 （3）平移變換 當(dāng)（x0 , y0）為圖形重心的坐標(biāo)時(shí)，這種變換實(shí)現(xiàn)的是相對(duì)

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

9、)的旋轉(zhuǎn)變換 1000cossin0sincos 112233yxyx 1010001 11001122yxyxyx 1010001 11003344yxyxyx任意點(diǎn)旋轉(zhuǎn)變換示意圖平移 100yx平移旋轉(zhuǎn)1010001001yxT1000cossin0sincos R1010001002yxT 21RTTT TyxRTTyxyxyx 1 11111211144三維齊次坐標(biāo)三維齊次坐標(biāo)(x,y,z)點(diǎn)對(duì)應(yīng)的齊次坐標(biāo)為點(diǎn)對(duì)應(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平移變換平移變換 1010000100001

10、zyxTTTT放縮變換放縮變換1000000000000zyxsssS 旋轉(zhuǎn)變換旋轉(zhuǎn)變換:右手螺旋方向?yàn)檎沂致菪较驗(yàn)檎?繞繞x軸軸100000000001cossinsincos)(xRyxyzzyzoox軸指向紙外10000001000cossinsincos)(yR 繞繞y軸軸zyzxxzxooy軸指向紙外 繞繞z軸軸100001000000cossinsincos)(zRxzxyyxyooz軸指向紙外錯(cuò)切變換錯(cuò)切變換zyxzyxzyxzyxzyxzyx三維錯(cuò)切變換沿z含x錯(cuò)切沿z含y錯(cuò)切沿y含x錯(cuò)切沿y含z錯(cuò)切沿x含y錯(cuò)切 沿x含z錯(cuò)切三維變換的一般形式三維變換的一般形式旋轉(zhuǎn)、比例、

11、錯(cuò)切、對(duì)稱平移透視投影總體比例44434241343332312423222114131211aaaaaaaaaaaaaaaaA1 三維圖形的基本問題 n 平面幾何投影 n 平行投影2 透視投影顯示器屏幕、繪圖紙等是二維的顯示對(duì)象是三維的解決方法-投影1. 在二維屏幕上如何顯示三維物體？在二維屏幕上如何顯示三維物體？2. 如何表示三維物體？如何表示三維物體？三維形體的表示-空間直線段、曲線段、多邊形、曲面片三維形體的輸入、運(yùn)算、有效性保證-困難解決方法-各種用于形體表示的理論、模型、方法3. 如何反映遮擋關(guān)系？如何反映遮擋關(guān)系？物體之間或物體的不同部分之間存在相互遮擋關(guān)系解決方法-消除隱藏面與

12、隱藏線何謂真實(shí)感圖形？真實(shí)感來源于透視關(guān)系和遮擋關(guān)系光線傳播引起的物體表面顏色的自然分布解決方法建立光照明模型真實(shí)感圖形繪制4. 如何產(chǎn)生真實(shí)感圖形如何產(chǎn)生真實(shí)感圖形三維圖形的基本研究內(nèi)容投影三維形體的表示消除隱藏面與隱藏線1. 建立光照明模型、研究真實(shí)感圖形繪制方法 如何投影? 生活中的類比-如何拍攝景物？拍攝過程選景取景-裁剪對(duì)焦參考點(diǎn)按快門-成像移動(dòng)方式移動(dòng)景物移動(dòng)照相機(jī)投影照相機(jī)模型選定投影類型 設(shè)置投影參數(shù) 拍攝方向、距離等三維裁剪 取景投影和顯示 成像平面幾何投影及其分類 投影將n維的點(diǎn)變換成小于n維的點(diǎn) 將3維的點(diǎn)變換成小于3維的點(diǎn)投影中心觀察點(diǎn)、視點(diǎn)投影面不經(jīng)過投影中心投影線從

13、投影中心向物體上各點(diǎn)發(fā)出的射線 平面幾何投影 投影面是平面投影線為直線 投影變換投影過程投影的數(shù)學(xué)表示 投影分類透視投影透視投影平行投影平行投影平行投影 投影中心與投影平面之間的距離為無限投影方向投影方向投影平面投影平面正投影與斜投影正平行投影正平行投影斜平行投影斜平行投影 三視圖：正視圖、側(cè)視圖和俯視圖 yx主視圖俯視圖側(cè)視圖一個(gè)直角棱臺(tái)的三視圖z 1000010000000001vTyx主視圖一個(gè)直角棱臺(tái)的三視圖z正視圖側(cè)視圖yx側(cè)視圖一個(gè)直角棱臺(tái)的三視圖z100010000100001100001000090cos90sin0090sin90cos1000010000100000LwxT

14、俯視圖 yx俯視圖一個(gè)直角棱臺(tái)的三視圖z10001000010000110000)90cos()90sin(00)90sin()90cos(000011000000000100001phzT從三視圖很難想象出實(shí)際物體的空間形狀解決：投影平面不垂直于任何一個(gè)坐標(biāo)軸正軸測投影正軸測投影 yxz圖5 正軸測投影平面的定義10000cossin00sincos0000110000cos0sin00100sin0cosxyyxRRR10000coscossincossin0sincos00cossinsinsincos1000000000100001yxRT100000sincossin00cos000

15、sinsincos Tzyxzyx11 投影方程：120 120120(a) 正等軸測 y z x投影平面三個(gè)單位向量將投影成三個(gè)長度相等的平面向量，即三根坐標(biāo)軸有相同的變形系數(shù) Tzyxx.10011.10sinsincosTzyxy.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)，看起來更

16、加真實(shí)。透視投影投影方程yxz投影中心dxyPPyxz投影平面一點(diǎn)透視dr/1dzxdzxdx)|(|dzydzydy)|(|1)/(dzxx1)/(dzyy100010000100001rT11111rzzrzyrzxzyx滅點(diǎn)的個(gè)數(shù)滅點(diǎn)的個(gè)數(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/10

17、01rzyx滅點(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)的個(gè)數(shù)由什么決定主滅點(diǎn)的個(gè)數(shù)由什么決定?1 直線段裁剪直接求交算法Cohen-Sutherland算法 中點(diǎn)分割裁剪算法 梁友棟-Basky算法2 多邊形裁剪 Sutlerland_Hodgman算法 Weiler-Atherton算法 裁剪的目的判斷圖形元素是否在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交裁剪、覆蓋裁剪窗口裁剪窗口矩形、圓形、一般多邊形矩形、圓形、一般多邊形被裁剪對(duì)象被裁剪對(duì)象線段、多邊形、曲線、

18、字符線段、多邊形、曲線、字符裁剪的策略裁剪的策略先裁剪，后變換，可避免對(duì)窗口外的圖形進(jìn)行變先裁剪，后變換，可避免對(duì)窗口外的圖形進(jìn)行變換，效率較高換，效率較高先變換，后裁剪先變換，后裁剪裁剪算法的核心問題裁剪算法的核心問題效率效率點(diǎn)裁剪點(diǎn)裁剪 點(diǎn)點(diǎn)(x, y)在窗口內(nèi)的充分必要條件是：在窗口內(nèi)的充分必要條件是： 問題：對(duì)于任意多邊形窗口，如何判別？問題：對(duì)于任意多邊形窗口，如何判別？maxminxxxmaxminyyy假定條件矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪線段：任何平面線段相對(duì)于凸多邊形窗口進(jìn)行裁剪后落在窗口內(nèi)的線段不會(huì)多于一條PxyP xy000111(,)(,)待裁

19、剪線段和窗口的關(guān)系待裁剪線段和窗口的關(guān)系 （1）完全落在窗口內(nèi)）完全落在窗口內(nèi)（2）完全落在窗口外）完全落在窗口外（3）部分在內(nèi)，部分在外）部分在內(nèi)，部分在外為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：1. 快速判斷情形快速判斷情形(1)(2)；2. 設(shè)法減少情形設(shè)法減少情形(3)求交次數(shù)和每次求交時(shí)求交次數(shù)和每次求交時(shí)所需的計(jì)算量所需的計(jì)算量算法步驟：算法步驟：第一步第一步 判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是， 則線段完全可見；否則進(jìn)入第二步；則線段完全可見；否則進(jìn)入第二步；第二步第二步 判別線段是否為顯然不可見，如果是，則裁判別線

20、段是否為顯然不可見，如果是，則裁 剪結(jié)束；否則進(jìn)行第三步剪結(jié)束；否則進(jìn)行第三步 ；第三步第三步 求線段與窗口邊延長線的交點(diǎn)，這個(gè)交點(diǎn)將求線段與窗口邊延長線的交點(diǎn)，這個(gè)交點(diǎn)將 線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束 裁剪過程是遞歸的。裁剪過程是遞歸的。elseyyCt01max當(dāng)elsexxCr01max當(dāng)elsexxCl01min當(dāng)elseyyCb01min當(dāng) 特點(diǎn)：特點(diǎn)：對(duì)顯然不可見線段的快速判別對(duì)顯然不可見線段的快速判別 編碼方法：編碼方法：由窗口四

21、條邊所在直線把二維平面分成由窗口四條邊所在直線把二維平面分成9個(gè)區(qū)域，每個(gè)區(qū)域個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼，賦予一個(gè)四位編碼， CtCbCrCl， 上下右左；上下右左；端點(diǎn)編碼：端點(diǎn)編碼：定義為它所在區(qū)域的編碼定義為它所在區(qū)域的編碼結(jié)論：結(jié)論：當(dāng)線段的兩個(gè)端點(diǎn)的編碼的邏輯當(dāng)線段的兩個(gè)端點(diǎn)的編碼的邏輯“與與”非零時(shí)非零時(shí) ，顯然不可見，顯然不可見 100000010010000001001001010101101010窗口bca 求交測試順序固定求交測試順序固定(左上右下）左上右下） 最壞情形，線段求交四次。最壞情形，線段求交四次。對(duì)于那些非完全可見、又非完全不可見的線段，需要求交，對(duì)于那些

22、非完全可見、又非完全不可見的線段，需要求交，求交前先測試與窗口哪條邊所在直線有交？求交前先測試與窗口哪條邊所在直線有交？(按序判斷端點(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)處將線段一分為二，對(duì)每段線段重復(fù)不斷

23、地在中點(diǎn)處將線段一分為二，對(duì)每段線段重復(fù)Cohen-Sutherland裁剪算法的線段可見性測試方法，直至找到每段線段與窗口邊界線的裁剪算法的線段可見性測試方法，直至找到每段線段與窗口邊界線的交點(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é)束；若不是，再判斷是否完全在窗口外，若是，則無可見線段

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

25、段為空集時(shí)，線段AB不可能在窗口中有可見線段。不可能在窗口中有可見線段。當(dāng)當(dāng)Q不為空集時(shí)，不為空集時(shí)，Q可看成是一個(gè)一維窗口可看成是一個(gè)一維窗口 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口是一維窗口TS中的可見部分中的可見部分基本思想：基本思想： 把二維裁剪化為一維裁剪問題，并向把二維裁剪化為一維裁剪問題，并向x（或（或y）方向投影以決定可見線段。）方向投影以決定可見線段。Q,;,;,maxminmaxmin4321yyxxLPPPPL),;,(),;,(maxminmaxminyyLxxLTURSP4P1P3P2ymaxyminxminxmaxRTSULAB

26、AS是一維窗口是一維窗口TS中的可見部分中的可見部分存在可見線段的充要條件存在可見線段的充要條件 不為空集不為空集 向向x軸投影，就得到可見線段上點(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(),

27、min(,maxmaxminUTBAUTBAxxxxxxxxxx),min(,maxminBAxxxL ),max(,minmaxBAxxxR 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)形成

28、的幾種情況分裂為幾個(gè)多邊形分裂為幾個(gè)多邊形關(guān)鍵：關(guān)鍵：不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)還在于形成正確的頂點(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è)可見一

29、側(cè)窗口窗口(a) 輸出輸出Pi+1當(dāng)前裁剪邊Pi+1Pi可見一側(cè)可見一側(cè)窗口窗口(a) 無輸出無輸出當(dāng)前裁剪邊Pi+1Pi可見一側(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)。可推廣到任意凸多邊形裁剪窗口可推廣到任意凸多邊形裁剪窗口逐邊裁剪要求裁剪窗口為凸多邊形，那么凹多邊形窗口怎么辦？逐邊裁剪要求裁剪窗口為凸多邊形，那么凹多邊形窗口怎么辦？逐邊裁剪法對(duì)凹多邊形裁剪時(shí)，裁剪后分裂為幾個(gè)多邊形，這幾逐邊裁剪法對(duì)凹多邊形裁剪時(shí)，裁剪后分裂為幾個(gè)多邊形，這幾個(gè)多邊形沿邊框產(chǎn)生多余的線段？個(gè)多邊形沿邊框產(chǎn)生多余的線