資源描述：
《計算機圖形學第6章二維圖形的裁剪(4).ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、7.3多邊形的裁剪前面討論了線段的裁剪，多邊形的裁剪是以線段裁剪為基礎的，但又不同于線段的裁剪。通常有一種錯覺，認為只要把多邊形的每條邊用直線裁剪方法裁剪后，就完成了對多邊形的裁剪。P110其實不然，在計算機圖形學中，多邊形定義了一個封閉的二維區(qū)域，它把平面分成多邊形內區(qū)和外區(qū)，一個多邊形的裁剪結果仍應該是封閉的多邊形，而不是一些孤立的線段。如圖中所示，裁剪后的多邊形仍應保留原多邊形各邊的連接順序并加入一些新頂點（交點、窗口頂點）及刪除界外頂點；一個凹多邊形裁剪后，可能分裂為幾個多邊形。7.3多邊形的裁剪多邊形裁剪的常用算法1．Su
2、therland-Hodgeman多邊形裁剪2．Weiler－Atherton任意多邊形裁剪7.3.1Sutherland-Hodgeman多邊形裁剪Sutherland-Hodgman算法也叫逐邊裁剪法，該算法是薩瑟蘭德(I．E．Sutherland)和霍德曼(Hodgman)在1974年提出的。這種算法采用了分割處理、逐邊裁剪的方法。一、Sutherland-Hodgeman多邊形裁剪算法思想：每次用窗口的一條邊界(包括延長線)對要裁剪的多邊形進行裁剪，裁剪時，順序地測試多邊形各頂點，保留邊界內側的頂點，刪除外側的頂點，同時，適
3、時地插入新的頂點：即交點和窗口頂點，從而得到一個新的多邊形頂點序列。然后以此新的頂點序列作為輸入，相對第二條窗邊界線進行裁剪，又得到一個更新的多邊形頂點序列。依次下去，相對于第三條、第四條邊界線進行裁剪，最后輸出的多邊形頂點序列即為所求的裁剪好了的多邊形。如下圖所示。7.3.1Sutherland-Hodgeman多邊形裁剪新的多邊形頂點序列產生規(guī)則：在用窗口一條邊界及其延長線裁剪一個多邊形時，該邊界線把平面分成兩個部分：一部分稱為邊界內側；另一部分稱為邊界外側。如下圖所示,依序考慮多邊形的各條邊。假設當前處理的多邊形的邊為SP(箭
4、頭表示順序關系，S為前一點，P為當前點)，邊SP與裁剪線的位置關系只有下面四種情況：1、S在外側，P在內側。則交點Q、當前點P保存到新多邊形中。2、S、P均在內側，則當前點P保存到新多邊形中。3、S在內側，P在外側。則交點Q保存到新多邊形中。4、S、P均在外側。則沒有點被保存到新多邊形中。7.3.1Sutherland-Hodgeman多邊形裁剪二、Sutherland-Hodgeman多邊形裁剪算法實現(xiàn)：三、Sutherland-Hodgeman多邊形裁剪算法演示：四、點在邊界內側的判斷方法：為了判斷pi點是否在邊界內側可用坐標比
5、較法和更通用的向量叉積符號判別法。1、坐標比較法將點的某個方向分量與邊界進行比較。例如，判斷某點是否在下邊界內側,用條件判別式：if(p[i][1]>=ymin)即可。對其它邊界也一樣。但不能寫成通用公式。7.3.1Sutherland-Hodgeman多邊形裁剪2、向量叉積法為簡單計，測試點表示為P點。假設窗口邊界方向為順時針，如圖中所示，對于其中任一邊界向量，從向量起點A向終點B看過去：如果被測試點P在該邊界線右邊(即內側)，AB×AP的方向與X-Y平面垂直并指向屏幕里面，即右手坐標系中Z軸的負方向。反過來，如果P在該邊界線的左
6、邊(即外側)，這時AB×AP的方向與X-Y平面垂直并指向屏幕外面，即右手坐標系中Z軸的正方向。設：點P(x，y)、點A(xA，yA)、點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)因此，當V≤0時，P在邊界線內側；而V>0時，P在邊界線外側。7.3.1Sutherland-Hodgeman多邊形裁剪Sutherland-Hodgeman多
7、邊形裁剪中，常用向量叉積法來測試當前點P是否在邊界內側。已知窗口邊界A(30,100)、B(40,180)，某點P(50,300),請問點P在邊界內側嗎？計算V=(xB－xA）·(y－yA)－(x－xA)）·(yB－yA) ?????????=(40－30)·(300－100)－(50－30)）·(180－100) ?????????=400因為V>0時，所以P在邊界外側。練習作業(yè)Sutherland-Hodgeman多邊形裁剪中，常用向量叉積法來測試當前點P是否在邊界內側。已知窗口邊界A(50,80)、B(75,130)，某點P(
8、60,150),請問點P在邊界內側嗎？五、Sutherland-Hodgeman多邊形裁剪算法特點：Sutherland－Hodgeman多邊形裁剪算法具有一般性，被裁剪多邊形可以是任意凸多邊形或凹多邊形，裁剪窗口不局限于矩形，可以是
