《计算机图形学第6章二维图形的裁剪.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第6章二维图形的裁剪.ppt（20页珍藏版）》请在三一办公上搜索。
1、7.3 多边形的裁剪,前面讨论了线段的裁剪，多边形的裁剪是以线段裁剪为基础的，但又不同于线段的裁剪。通常有一种错觉，认为只要把多边形的每条边用直线裁剪方法裁剪后，就完成了对多边形的裁剪。P110其实不然，在计算机图形学中，多边形定义了一个封闭的二维区域，它把平面分成多边形内区和外区，一个多边形的裁剪结果仍应该是封闭的多边形，而不是一些孤立的线段。如图中所示，裁剪后的多边形仍应保留原多边形各边的连接顺序并加入一些新顶点（交点、窗口顶点）及删除界外顶点；一个凹多边形裁剪后，可能分裂为几个多边形。,7.3 多边形的裁剪,多边形裁剪的常用算法 1Sutherland-Hodgeman多边形裁剪2Wei
2、lerAtherton任意多边形裁剪,7.3.1 Sutherland-Hodgeman多边形裁剪,Sutherland-Hodgman算法也叫逐边裁剪法，该算法是萨瑟兰德(IESutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。一、Sutherland-Hodgeman多边形裁剪算法思想：每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边形顶点序列。然后以此新的顶点序列作为输入，相对第二条窗边界线
3、进行裁剪，又得到一个更新的多边形顶点序列。依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。如下图所示。,7.3.1 Sutherland-Hodgeman多边形裁剪,新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两个部分：一部分称为边界内侧；另一部分称为边界外侧。如下图所示,依序考虑多边形的各条边。假设当前处理的多边形的边为SP(箭头表示顺序关系，S为前一点，P为当前点)，边SP与裁剪线的位置关系只有下面四种情况：1、S在外侧，P在内侧。则交点Q、当前点P保存到新多边形中。2、S、P均在内侧，则当前点
4、P保存到新多边形中。3、S在内侧，P在外侧。则交点Q保存到新多边形中。4、S、P均在外侧。则没有点被保存到新多边形中。,7.3.1 Sutherland-Hodgeman多边形裁剪,二、Sutherland-Hodgeman多边形裁剪算法实现：,三、Sutherland-Hodgeman多边形裁剪算法演示：四、点在边界内侧的判断方法：为了判断pi点是否在边界内侧可用坐标比较法和更通用的向量叉积符号判别法。1、坐标比较法将点的某个方向分量与边界进行比较。例如，判断某点是否在下边界内侧,用条件判别式：if(pi1=ymin)即可。对其它边界也一样。但不能写成通用公式。,7.3.1 Sutherla
5、nd-Hodgeman多边形裁剪,2、向量叉积法为简单计，测试点表示为P点。假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点A向终点B看过去：如果被测试点P在该边界线右边(即内侧)，ABAP的方向与X-Y平面垂直并指向屏幕里面，即右手坐标系中Z轴的负方向。反过来，如果P在该边界线的左边(即外侧)，这时ABAP的方向与X-Y平面垂直并指向屏幕外面，即右手坐标系中Z轴的正方向。设：点P(x，y)、点A(xA，yA)、点B(xB，yB)，向量AB=(xB-xA)，(yB-yA)，向量AP=(x-xA)，(y-yA)，那么ABAP的方向可由下式的符号来确定：,V=(xB-xA)(
6、y-yA)-(x-xA)(yB-yA)(3-14),因此，当V0时，P在边界线内侧；而V0时，P在边界线外侧。,7.3.1 Sutherland-Hodgeman多边形裁剪,Sutherland-Hodgeman多边形裁剪中，常用向量叉积法来测试当前点P是否在边界内侧。已知窗口边界A(30,100)、B(40,180)，某点P(50,300),请问点P在边界内侧吗？,计算 V=(xBxA）(yyA)(xxA)）(yByA)=(4030)(300100)(5030)）(180100)=400 因为V 0时，所以P在边界外侧。,练习,作业Sutherland-Hodgeman多边形裁剪中，常用向量
7、叉积法来测试当前点P是否在边界内侧。已知窗口边界A(50,80)、B(75,130)，某点P(60,150),请问点P在边界内侧吗？,五、Sutherland-Hodgeman多边形裁剪算法特点：SutherlandHodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。,7.3.1 Sutherland-Hodgeman多边形裁剪,7.3.2 W
8、eilerAtherton任意多边形裁剪,SutherlandHodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。一、WeilerAtherton任意多边形裁剪算法描述：在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。,裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称：1、被裁剪多边形为主多边形，记为A；2、裁剪窗口为裁剪多边形，记为B。,7.3.2 WeilerAtherton任意多边形裁剪,
9、主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域：1、AB（交：属于A且属于B）；2、AB（差：属于A不属于B）；3、BA（差：属于B不属于A）；4、AB(并：属于A或属于B，取反；即：不属于A且不属于B)。内裁剪即通常意义上的裁剪，取图元位于窗口之内的部分，结果为AB。外裁剪取图元位于窗口之外的部分，结果为AB。观察右图不难发现裁剪结果区域的边界由被裁剪多边形的部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界，或者反之。由于多边形构成一个封闭的区域，所以，如果被裁剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类：一
10、类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e；一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。,7.3.2 WeilerAtherton任意多边形裁剪,二、WeilerAtherton任意多边形裁剪算法思想：假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。按
11、上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。三、WeilerAtherton任意多边形裁剪算法步骤：1、顺时针输入被裁剪多边形顶点序列放入数组1中。2、顺时针输入裁剪窗口顶点序列放入数组2中。,7.3.2 WeilerAtherton任意多边形裁剪,3、求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”、“出”标记。然后将交点按顺序插入序列得到新的顶点序列，并放入数组3中；同样也将交点按顺序插入
12、序列得到新的顶点序列，放入数组4中；4、初始化输出数组Q，令数组Q为空。接着从数组3中寻找“入”点。如果“入”点没找到，程序结束。5、如果找到“入”点，则将“入”点放入S中暂存。6、将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标 记删去。7、沿数组3顺序取顶点：如果顶点不是“出点”，则将顶点录入到输出数组Q中，流程转第7步。否则，流程转第8步。8、沿数组4顺序取顶点：如果顶点不是“入点”，则将顶点录入到输出数组Q中，流程转第8步。否则，流程转第9步。9、如果顶点不等于起始点S，流程转第6步，继续跟踪数组3。否则，将数组Q输出；流程转第4步，寻找可能存在的分裂多边形。,7.3
13、.2 WeilerAtherton任意多边形裁剪,算法在第4步：满足“入”点没找到的条件时，算法结束。算法的生成过程见下图所示。,7.3.2 WeilerAtherton任意多边形裁剪,四、WeilerAtherton任意多边形裁剪算法实现：1、算法在实现中，需要用到六个数组，分别用来存放：被裁剪多边形、裁剪窗口、交点数组、插入交点后的被裁剪多边形、插入交点后的裁剪窗口、输出多边形。2、由于交点具有“入”、“出”标记，因此凡与交点有关的数组都要采用结构数组类型：struct pointdouble x；double y；int flag；交点数组，数组3，数组4；标记flag有三种状态：0：非
14、交点；1：“入”点；-1：“出”点。,3、求交点时，利用被裁剪多边形的各边去对裁剪窗口的各边求交点：for（被裁剪多边形的各边）；for（裁剪窗口的各边）求有效交点；放入交点数组；4、交点的顺序插入，意味着要对交点数组排序后再分别插入到数组1、数组2的相应位置上。5、所谓找“入”点、“出”点，必须根据flag找寻满足条件的顶点位置。不光数组3中要找“入”点、“出”点，而且找到后还要转到数组4的相应顶点位置处。对数组4的处理也同上。这种处理在本算法中大量遇到。,7.3.2 WeilerAtherton任意多边形裁剪,7.3.2 WeilerAtherton任意多边形裁剪,五、WeilerAthe
15、rton任意多边形裁剪算法：六、WeilerAtherton任意多边形裁剪算法特点：1、裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。2、可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口内的图形或保留窗口外的图形，因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。3、裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数无关。七、WeilerAtherton任意多边形裁剪算法小结：前面介绍的是内裁算法，即保留裁剪窗口内的图形。而外裁算法（保留裁剪窗口外的图形）同内裁算法差不多。外裁算法与内裁算法不同的是：1、从被裁剪多边形的一个“出点”开始，碰到出点，沿着被裁剪多边形按顺时针方向搜
16、集顶点序列；,7.3.2 WeilerAtherton任意多边形裁剪,2、而当遇到“入点”时，则沿着裁剪窗口按逆时针方向搜集顶点序列。按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点为止。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。由于可能存在分裂的多边形，因此算法要考虑：将搜集过的“出点”的出点记号删去，以免重复跟踪。将所有的出点搜集完毕后算法结束。WeilerAtherton算法的的设计思想很巧妙，裁剪是一次完成，不象Sutherland-Hodgman多边形裁剪算法，每次只对裁剪窗口的一条边界及其延长线进行裁剪，如裁剪窗口有n条边，则要调用n次S-H算法后才能最后得
17、出裁剪结果。但WeilerAtherton算法的编程实现比Sutherland-Hodgman算法稍难，主要难在入、出点的查寻以及跨数组搜索上。,7.4 字符的裁剪,字符也是图元的一种，它在输出过程中，同样需要进行裁剪，字符的裁剪有多种策略，依赖于字符的生成及存储方式和具体应用的要求，有如下三种：一、基于字符串采用字符串方式进行裁剪时，将包围字符串的外接矩形对窗口作裁剪。当字符串外接矩形整个在窗口内时予以显示，否则不显示。如下图所示。,二、基于字符采用字符方式进行裁剪时，将包围字符的外接矩形对窗口作裁剪，如某个字符外接矩形整个落在窗口内予以显示，否则不显示。如下图所示。,7.4 字符的裁剪,三、基于构成字符的最小元素对于点阵字符，构成字符的最小元素为象素，此时字符的裁剪转化为点裁剪。对于矢量字符，构成字符的最小元素是直线段（笔画），这样字符的裁剪就转化成了线裁剪。如下图所示。,
