計(jì)算機(jī)圖形學(xué)第6章二維圖形的裁剪

《計(jì)算機(jī)圖形學(xué)第6章二維圖形的裁剪》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、7.3多邊形的裁剪前面討論了線段的裁剪，多邊形的裁剪是以線段裁剪為基礎(chǔ)的，但又不同于線段的裁剪。通常有一種錯覺，認(rèn)為只要把多邊形的每條邊用直線裁剪方法裁剪后，就完成了對多邊形的裁剪。P110其實(shí)不然，在計(jì)算機(jī)圖形學(xué)中，多邊形定義了一個封閉的二維區(qū)域，它把平面分成多邊形內(nèi)區(qū)和外區(qū)，一個多邊形的裁剪結(jié)果仍應(yīng)該是封閉的多邊形，而不是一些孤立的線段。如圖中所示，裁剪后的多邊形仍應(yīng)保留原多邊形各邊的連接順序并加入一些新頂點(diǎn)（交點(diǎn)、窗口頂點(diǎn)）及刪除界外頂點(diǎn)；一個凹多邊形裁剪后，可能分裂為幾個多邊形。7.3多邊形的裁剪多邊形裁剪的常用算

2、法1．Sutherland-Hodgeman多邊形裁剪2．Weiler－Atherton任意多邊形裁剪7.3.1Sutherland-Hodgeman多邊形裁剪Sutherland-Hodgman算法也叫逐邊裁剪法，該算法是薩瑟蘭德(I．E．Sutherland)和霍德曼(Hodgman)在1974年提出的。這種算法采用了分割處理、逐邊裁剪的方法。一、Sutherland-Hodgeman多邊形裁剪算法思想：每次用窗口的一條邊界(包括延長線)對要裁剪的多邊形進(jìn)行裁剪，裁剪時，順序地測試多邊形各頂點(diǎn)，保留邊界內(nèi)側(cè)的頂點(diǎn)，刪除

3、外側(cè)的頂點(diǎn)，同時，適時地插入新的頂點(diǎn)：即交點(diǎn)和窗口頂點(diǎn)，從而得到一個新的多邊形頂點(diǎn)序列。然后以此新的頂點(diǎn)序列作為輸入，相對第二條窗邊界線進(jìn)行裁剪，又得到一個更新的多邊形頂點(diǎn)序列。依次下去，相對于第三條、第四條邊界線進(jìn)行裁剪，最后輸出的多邊形頂點(diǎn)序列即為所求的裁剪好了的多邊形。如下圖所示。7.3.1Sutherland-Hodgeman多邊形裁剪新的多邊形頂點(diǎn)序列產(chǎn)生規(guī)則：在用窗口一條邊界及其延長線裁剪一個多邊形時，該邊界線把平面分成兩個部分：一部分稱為邊界內(nèi)側(cè)；另一部分稱為邊界外側(cè)。如下圖所示,依序考慮多邊形的各條邊。假設(shè)

4、當(dāng)前處理的多邊形的邊為SP(箭頭表示順序關(guān)系，S為前一點(diǎn)，P為當(dāng)前點(diǎn))，邊SP與裁剪線的位置關(guān)系只有下面四種情況：1、S在外側(cè)，P在內(nèi)側(cè)。則交點(diǎn)Q、當(dāng)前點(diǎn)P保存到新多邊形中。2、S、P均在內(nèi)側(cè)，則當(dāng)前點(diǎn)P保存到新多邊形中。3、S在內(nèi)側(cè)，P在外側(cè)。則交點(diǎn)Q保存到新多邊形中。4、S、P均在外側(cè)。則沒有點(diǎn)被保存到新多邊形中。7.3.1Sutherland-Hodgeman多邊形裁剪二、Sutherland-Hodgeman多邊形裁剪算法實(shí)現(xiàn)：三、Sutherland-Hodgeman多邊形裁剪算法演示：四、點(diǎn)在邊界內(nèi)側(cè)的判斷方法

5、：為了判斷pi點(diǎn)是否在邊界內(nèi)側(cè)可用坐標(biāo)比較法和更通用的向量叉積符號判別法。1、坐標(biāo)比較法將點(diǎn)的某個方向分量與邊界進(jìn)行比較。例如，判斷某點(diǎn)是否在下邊界內(nèi)側(cè),用條件判別式：if(p[i][1]>=ymin)即可。對其它邊界也一樣。但不能寫成通用公式。7.3.1Sutherland-Hodgeman多邊形裁剪2、向量叉積法為簡單計(jì)，測試點(diǎn)表示為P點(diǎn)。假設(shè)窗口邊界方向?yàn)轫槙r針，如圖中所示，對于其中任一邊界向量，從向量起點(diǎn)A向終點(diǎn)B看過去：如果被測試點(diǎn)P在該邊界線右邊(即內(nèi)側(cè))，AB×AP的方向與X-Y平面垂直并指向屏幕里面，即右手

6、坐標(biāo)系中Z軸的負(fù)方向。反過來，如果P在該邊界線的左邊(即外側(cè))，這時AB×AP的方向與X-Y平面垂直并指向屏幕外面，即右手坐標(biāo)系中Z軸的正方向。設(shè)：點(diǎn)P(x，y)、點(diǎn)A(xA，yA)、點(diǎn)B(xB，yB)，　　　　向量AB={(xB-xA)，(yB-yA)}，　　　　向量AP={(x-xA)，(y-yA)}，那么AB×AP的方向可由下式的符號來確定：V=(xB-xA)·(y-yA)-(x-xA)·(yB-yA)(3-14)因此，當(dāng)V≤0時，P在邊界線內(nèi)側(cè)；而V>0時，P在邊界線外側(cè)。7.3.1Sutherland-Hod

7、geman多邊形裁剪Sutherland-Hodgeman多邊形裁剪中，常用向量叉積法來測試當(dāng)前點(diǎn)P是否在邊界內(nèi)側(cè)。已知窗口邊界A(30,100)、B(40,180)，某點(diǎn)P(50,300),請問點(diǎn)P在邊界內(nèi)側(cè)嗎？計(jì)算V=(xB－xA）·(y－yA)－(x－xA)）·(yB－yA)?????????=(40－30)·(300－100)－(50－30)）·(180－100)?????????=400因?yàn)閂>0時，所以P在邊界外側(cè)。練習(xí)作業(yè)Sutherland-Hodgeman多邊形裁剪中，常用向量叉積法來測試當(dāng)前點(diǎn)P是否

8、在邊界內(nèi)側(cè)。已知窗口邊界A(50,80)、B(75,130)，某點(diǎn)P(60,150),請問點(diǎn)P在邊界內(nèi)側(cè)嗎？五、Sutherland-Hodgeman多邊形裁剪算法特點(diǎn)：Sutherland－Hodgeman多邊形裁剪算法具有一般性，被裁剪多邊形可以是任意凸多邊形或凹多邊形，裁剪窗口不局限于矩形，可以是