计算机图形学第6章二维图形的裁剪(4).ppt

《计算机图形学第6章二维图形的裁剪(4).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、7.3多边形的裁剪前面讨论了线段的裁剪，多边形的裁剪是以线段裁剪为基础的，但又不同于线段的裁剪。通常有一种错觉，认为只要把多边形的每条边用直线裁剪方法裁剪后，就完成了对多边形的裁剪。P110其实不然，在计算机图形学中，多边形定义了一个封闭的二维区域，它把平面分成多边形内区和外区，一个多边形的裁剪结果仍应该是封闭的多边形，而不是一些孤立的线段。如图中所示，裁剪后的多边形仍应保留原多边形各边的连接顺序并加入一些新顶点（交点、窗口顶点）及删除界外顶点；一个凹多边形裁剪后，可能分裂为几个多边形。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多边形裁剪新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两个部分：一部分称为边界内侧；另一部分称为边界外侧。如下图所示,依序考虑多边形的各条边。假设当前处理的多边形的边为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多边形裁剪算法实现：三、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在边界外侧。练习作业Sutherland-Hodgeman多边形裁剪中，常用向量叉积法来测试当前点P是否在边界内侧。已知窗口边界A(50,80)、B(75,130)，某点P(

8、60,150),请问点P在边界内侧吗？五、Sutherland-Hodgeman多边形裁剪算法特点：Sutherland－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是