五講剪裁ppt課件

1、內(nèi)容摘要 裁剪裁剪 窗口視圖變換窗口視圖變換 線段裁剪線段裁剪 線段端點與窗口區(qū)域關(guān)系判別線段端點與窗口區(qū)域關(guān)系判別 Cohen-SutherlandCohen-Sutherland線段裁剪算法線段裁剪算法 中點分割算法中點分割算法 最遠可見點算法最遠可見點算法 中點分割算法處置流程中點分割算法處置流程 多邊形裁剪多邊形裁剪 多邊形裁剪多邊形裁剪 多邊形裁剪流程圖多邊形裁剪流程圖裁剪裁剪在運用計算機處置圖形信息時，往往計算機內(nèi)部存儲在運用計算機處置圖形信息時，往往計算機內(nèi)部存儲的圖形比較大，而屏幕顯示只是圖的一部分。例如，的圖形比較大，而屏幕顯示只是圖的一部分。例如，雖然計算機內(nèi)部可以存儲全國

2、地圖。但是，假設(shè)把全雖然計算機內(nèi)部可以存儲全國地圖。但是，假設(shè)把全國整幅顯示在屏幕上，那么不能看到各地部分的細節(jié)國整幅顯示在屏幕上，那么不能看到各地部分的細節(jié)。這時，可以運用縮放技術(shù)，把地圖中的部分區(qū)域放。這時，可以運用縮放技術(shù)，把地圖中的部分區(qū)域放大顯示。在放大一幅圖形的一部分區(qū)域，必需確定圖大顯示。在放大一幅圖形的一部分區(qū)域，必需確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些部分落在顯示區(qū)形中哪些部分落在顯示區(qū)之內(nèi)，哪些部分落在顯示區(qū)之外，以便顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選之外，以便顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇處置過程稱為裁剪，就好象從一個大的圖形中剪出擇處置過程稱為裁剪，就好象從

3、一個大的圖形中剪出需求的一個小塊。需求的一個小塊。裁剪在圖形處置中很有意義，本章節(jié)專門研討裁剪的裁剪在圖形處置中很有意義，本章節(jié)專門研討裁剪的方法，根據(jù)這些方法還可以構(gòu)造出更高級的裁剪算法方法，根據(jù)這些方法還可以構(gòu)造出更高級的裁剪算法窗口視圖變換窗口視圖變換窗口：由用戶坐標(biāo)系定義的一個矩形區(qū)窗口：由用戶坐標(biāo)系定義的一個矩形區(qū)域；域；視口：由設(shè)備坐標(biāo)系定義的一個矩形區(qū)視口：由設(shè)備坐標(biāo)系定義的一個矩形區(qū)域；域；當(dāng)把用戶坐標(biāo)系中的圖形在圖形設(shè)備上當(dāng)把用戶坐標(biāo)系中的圖形在圖形設(shè)備上輸出時，可以定義適當(dāng)?shù)拇翱诤鸵暱?，輸出時，可以定義適當(dāng)?shù)拇翱诤鸵暱?，使窗口的圖形在視口內(nèi)顯示，處于窗口使窗口的圖形在視口內(nèi)

4、顯示，處于窗口外或視口外的圖形那么不被顯示即稱被外或視口外的圖形那么不被顯示即稱被裁剪掉。固定視口而改動窗口，就可以裁剪掉。固定視口而改動窗口，就可以在在視口HVLV(XV1，YV1)窗口HW( X W 1 ，YW1)LW窗口與視口的關(guān)系用戶坐標(biāo)系設(shè)備坐標(biāo)系視口中察看到用戶描畫的全部圖形了。視口中察看到用戶描畫的全部圖形了。窗口與視口存在變換關(guān)系：窗口與視口存在變換關(guān)系：設(shè)：視口的寬為設(shè)：視口的寬為LVLV，高為，高為HVHV，左下角為，左下角為(XV1(XV1，YV1)YV1)，窗口的寬為，窗口的寬為LWLW，高為，高為HWHW，左下，左下角為角為(XW1(XW1，YW1)YW1)，如下圖。

5、對視口中的點，如下圖。對視口中的點(XV(XV，YV)YV)，在窗口中有一點，在窗口中有一點XWXW，YWYW與與之對應(yīng)，且有：之對應(yīng)，且有：(XW-XW1)/(XV-XV1)(XW-XW1)/(XV-XV1)LWLWLV LV (YW-YW1)/(YV-YV1)(YW-YW1)/(YV-YV1)HWHWHV HV 線段裁剪線段裁剪裁剪算法有二維的和三維裁剪算法有二維的和三維的，裁剪對象可以是規(guī)那的，裁剪對象可以是規(guī)那么形體，也可以是不規(guī)那么形體，也可以是不規(guī)那么形體，其裁剪算法可以么形體，其裁剪算法可以用硬件實現(xiàn)，也可以用軟用硬件實現(xiàn)，也可以用軟件實現(xiàn)。件實現(xiàn)。在進展裁剪時，畫面中對在進展裁

6、剪時，畫面中對應(yīng)于屏幕顯示的那部分區(qū)應(yīng)于屏幕顯示的那部分區(qū)域也即窗口，把其定義為域也即窗口，把其定義為矩形，由上、下、左、右矩形，由上、下、左、右四條邊圍成，即：四條邊圍成，即：(xL(xL，yB)yB)，(xR(xR，yH)yH)。裁剪的。裁剪的本質(zhì)就是決議圖形中哪些本質(zhì)就是決議圖形中哪些點、線段、文字、以及多點、線段、文字、以及多邊形在裁剪窗口之內(nèi)，邊形在裁剪窗口之內(nèi)，在窗口內(nèi)的圖形被保管顯示，而窗口之外的畫面被裁去。如下圖。在窗口內(nèi)的圖形被保管顯示，而窗口之外的畫面被裁去。如下圖。對于點對于點(x(x，y)y)，只需判別兩對不等式：，只需判別兩對不等式：xLxLx x xR xR，yBy

7、By yyHyH假設(shè)四個不等式均成立，那么點在窗口矩形之內(nèi)；否那么，點在窗口矩形之外。其假設(shè)四個不等式均成立，那么點在窗口矩形之內(nèi)；否那么，點在窗口矩形之外。其中中, ,等號表示點位于窗口的邊境上。等號表示點位于窗口的邊境上。1線段端點與窗口區(qū)域關(guān)系判別線段端點與窗口區(qū)域關(guān)系判別完全在窗口內(nèi)的線段和完全完全在窗口內(nèi)的線段和完全不在窗口內(nèi)的線段可以用下不在窗口內(nèi)的線段可以用下面的語句判別。面的語句判別。 if XaXR if XaXR then 1then 1 if XbXR if XbXR then 1then 1 if YaYH if YaYH then 1then 1 if YbYH if

8、 YbYH then 1then 1line(Xa,Ya,Xb,Yb) line(Xa,Ya,Xb,Yb) 在窗口在窗口之內(nèi)之內(nèi)1: if XaXL and XbXL 1: if XaXL and XbXR and XbXR if XaXR and XbXR then 2then 2 if YaYH and YbYH if YaYH and YbYH then 2then 2 if YaYB and YbYB if YaYB and YbYB then 2then 2一部分在窗口內(nèi)一部分在窗口內(nèi), ,需求裁剪需求裁剪. .2:line(Xa,Ya,Xb,Yb)2:line(Xa,Ya,Xb,Y

9、b)完全完全在窗口之外。在窗口之外。這樣就可以首先將這兩種特殊情況進展簡單的判別而得到結(jié)果，剩下來的問題就是對這樣就可以首先將這兩種特殊情況進展簡單的判別而得到結(jié)果，剩下來的問題就是對于那些一部分在窗口內(nèi)而另一部分在窗口外的線段的處置了。于那些一部分在窗口內(nèi)而另一部分在窗口外的線段的處置了。(Xa,Ya) (Xb,Yb )3由Dan Cohen和Ivan Sutherland提出的區(qū)域編碼判別方法，它采用四位數(shù)碼來標(biāo)識線段的端點與窗口區(qū)域的關(guān)系。 如右圖所示。編碼規(guī)那么為：線段端點的區(qū)域編碼裁剪矩形010001010110000000010010100010011010端點位于窗口左側(cè)1 1

10、1 1端點位于窗口右側(cè)端點位于窗口下側(cè)端點位于窗口上側(cè)線段端點與窗口區(qū)域關(guān)系判別線段端點與窗口區(qū)域關(guān)系判別從表3-1中可以看出，當(dāng)兩端點編碼進展邏輯“與 運算后，當(dāng)結(jié)果不為零時，該線段完全在窗口外面，而當(dāng)結(jié)果為零時，還要進一步判別。1Cohen-SutherlandCohen-Sutherland線段裁剪算法線段裁剪算法算法的根本思想如下：算法的根本思想如下：1 1檢查線段檢查線段P1P2P1P2能否為完全可見，或完全不可見，對能否為完全可見，或完全不可見，對于這兩種情況或完全取之，或完全棄之，否那么于這兩種情況或完全取之，或完全棄之，否那么 “2 2。2 2找到找到P1P2P1P2在窗口外的

11、一個端點在窗口外的一個端點P1P1或或P2P2；3 3用窗口的邊與用窗口的邊與P1P2P1P2的交點取代端點的交點取代端點P1P1或或P2P2；4 4P1P2P1P2線段能否完全可見，假設(shè)是，那么終了，否那線段能否完全可見，假設(shè)是，那么終了，否那么轉(zhuǎn)到么轉(zhuǎn)到“2 2“繼續(xù)執(zhí)行。繼續(xù)執(zhí)行。圖中，線段不完全可見，也不是完全不可見，是部分在圖中，線段不完全可見，也不是完全不可見，是部分在窗口內(nèi)、部分在窗口外。窗口內(nèi)、部分在窗口外。P1P1點的編碼為點的編碼為01010101，P2P2點的編碼為點的編碼為00100010。首先獲得首先獲得P1P1點為窗口外的點，由于點為窗口外的點，由于P1P1點的第一

12、位編碼為點的第一位編碼為1 1，因此先求，因此先求P1P2P1P2與左邊境與左邊境X=1X=1的交點的的交點的P1P1 ，對，對P1P1編碼編碼有有01000100依然是窗口外的點，再求依然是窗口外的點，再求P1P1 P1 P1 P1 P2 P1 P2與下邊境與下邊境Y=1Y=1的交點得的交點得P1P1，編碼是，編碼是00000000，故為窗口內(nèi)的，故為窗口內(nèi)的點，而點，而P2P2點仍在窗口外由于編碼中第二位為點仍在窗口外由于編碼中第二位為1 1，故可求，故可求P1 P2P1 P2與右邊境與右邊境X X4 4的交點，求得后為的交點，求得后為P2P2點的編碼為點的編碼為00000000，用，用P

13、2P2P2P2替代原來的替代原來的P2P2點，點， 此時此時P1P2P1P2線段就為完全可見線段了。線段就為完全可見線段了。知直線：知直線：X1X1，Y1Y1，X2X2，Y2Y2，與程度線，與程度線Y YK K的交點為：的交點為：與垂直線與垂直線X=RX=R的交點為的交點為: :所以，在進展裁剪時除了要求直線與邊境的交點外，還要判別端點與窗口的位置關(guān)系。為此有：所以，在進展裁剪時除了要求直線與邊境的交點外，還要判別端點與窗口的位置關(guān)系。為此有：假設(shè)假設(shè) 編碼編碼&0001&00010 0，端點落在左邊境，端點落在左邊境; ;假設(shè)假設(shè) 編碼編碼&0010&0010

14、0 0，端點落在右邊境，端點落在右邊境; ;假設(shè)假設(shè) 編碼編碼&0100&01000 0，端點落在下邊境，端點落在下邊境; ;假設(shè)假設(shè) 編碼編碼&1000&10000 0，端點落在上邊境，端點落在上邊境; ;3中點分割算法中點分割算法在圖在圖3-423-42中的中的b b線段，線段，檢查端點編碼可知它檢查端點編碼可知它既不是完全可見段，既不是完全可見段，也不是完全不可見段也不是完全不可見段，那么在中點，那么在中點Pm1Pm1處將處將b b分為二段，兩段的情分為二段，兩段的情況依然一樣。先不思況依然一樣。先不思索索P1Pm1P1Pm1，在，在Pm2Pm2處將處將P

15、m1P2Pm1P2分為二段從圖中分為二段從圖中可見，可見，Pm1Pm2Pm1Pm2完全可完全可見，而見，而Pm2P2Pm2P2部分可見部分可見。這樣處置的結(jié)果將。這樣處置的結(jié)果將導(dǎo)致線段的可見部分導(dǎo)致線段的可見部分被劃分成一系列的可被劃分成一系列的可見小段然后再逐段畫見小段然后再逐段畫出，顯然效率降低。出，顯然效率降低。2最遠可見點算法最遠可見點算法求求P1P1最遠可見點的算法：最遠可見點的算法：1) 1) 假設(shè)假設(shè)P2P2在窗口內(nèi)，那在窗口內(nèi)，那么么P2P2就是離就是離P1P1最遠的可見最遠的可見點，終了該算法，否那么點，終了該算法，否那么進展下一步進展下一步; ;2) 2) 假設(shè)假設(shè)P1P

16、2P1P2為完全不可為完全不可見，那么終了該算法，見，那么終了該算法， 否那么進展下一步；否那么進展下一步；3) 3) 取取P1P2P1P2中點中點PmPm，假設(shè)，假設(shè)PmPm點在窗口內(nèi)部，那么處點在窗口內(nèi)部，那么處置置PmP2PmP2線段來尋覓線段來尋覓P1P1的最的最遠可見點，即用遠可見點，即用PmPm替代替代P1P1，執(zhí)行，執(zhí)行2 2，否那么，否那么P2P2用用PmPm替代，執(zhí)行替代，執(zhí)行2 2。直到。直到PmPm與與線段端點的間隔到達分辯線段端點的間隔到達分辯率精度為止。率精度為止。7多邊形裁剪多邊形裁剪多邊形可以看作是線段的多邊形可以看作是線段的集合。但是，這樣做會使集合。但是，這樣

17、做會使原來封鎖的多邊形變成不原來封鎖的多邊形變成不封鎖的或者成為一些離散封鎖的或者成為一些離散的線段。假設(shè)只思索畫線的線段。假設(shè)只思索畫線圖形，問題還不大。但是圖形，問題還不大。但是當(dāng)多邊形作為實體思索時當(dāng)多邊形作為實體思索時，封鎖的多邊形裁剪后還，封鎖的多邊形裁剪后還應(yīng)是封鎖的多邊形，以便應(yīng)是封鎖的多邊形，以便進展填充。為了到達這個進展填充。為了到達這個目的，可以運用目的，可以運用SutherlandSutherland和和HodgemanHodgeman所所發(fā)明的逐次多邊形裁剪發(fā)明的逐次多邊形裁剪R e e n t r a n t P o l y g o n R e e n t r a n

18、 t P o l y g o n ClippingClipping算法。該算法算法。該算法的根本思想是一次用窗口的根本思想是一次用窗口的一條邊裁剪多邊形，如的一條邊裁剪多邊形，如下圖。下圖。多邊形裁剪多邊形裁剪算法的輸入是以頂點序列表算法的輸入是以頂點序列表示的多邊形。用示的多邊形。用P1P2P1P2PnPn表表示把示把P1P1連到連到P2P2，P2P2連到連到P3P3，最后把，最后把PnPn連到連到P1P1所成的所成的多邊形，如右上圖所示。算多邊形，如右上圖所示。算法的輸出也是一個頂點序列法的輸出也是一個頂點序列，構(gòu)成一個或多個多邊形，構(gòu)成一個或多個多邊形，如右上角圖所示。如右上角圖所示。算法的每一步，思索以窗口算法的每一步，思索以窗口的一條邊以及延伸線構(gòu)成的的一條邊以及延伸線構(gòu)成的裁剪線。該線把平面分成兩裁剪線。該線把平面分成兩部分部分: :一部分包含窗口，稱一部分包含窗口，稱為可見一側(cè)為可見一側(cè); ;另一部分稱為另一部分稱為不可見一側(cè)。依序思索多邊不可見一側(cè)。依序思索多邊形各條邊的兩端點形各條邊的兩端點S S、P