二维图形的裁剪

关于二维图形的裁剪第1页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院2二维裁剪识别图形在指定区域内和区域外的部分的过程称为裁剪算法，简称裁剪（clipping）二维窗口是投影平面上的一个矩形。一般来说，这个矩形的边和投影平面上的坐标轴平行，图形在窗口内的部分被显示出来，窗口外的部分被裁剪掉了。平面上的图形受该矩形的裁剪称为二维裁剪。第2页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院3裁剪的应用从定义的场景中抽取用于观察的部分在三维视图中识别出可见面防止线段或对象的边界混淆用实体造型来创建对象显示多窗口的环境允许选择图形的一部分来进行拷贝、移动或删除等绘图操作裁剪算法类型图形裁剪与窗口——视图变换的先后窗口边界裁剪视区边界裁剪图形生成与裁剪先后先生成后裁剪先裁剪后生成第3页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院4点的裁剪图形裁剪中的最基本的问题。假设裁剪窗口为一个在标准位置的矩形，即边与坐标轴平行的矩形，由上（y=ymin）、下（y=ymax）、左（x=xmin）、右（x=xmax）四条边描述。点(x,y)在窗口内的充分必要条件是：裁剪窗口（Xmin，Xmax，Ymin，Ymax）是世界坐标系的窗口边界或视区边界应用举例爆炸场景或海面泡沫的显示问题：对于任何多边形窗口，如何判别？(xmin,ymin)(xmax,ymax)第4页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院5直线段裁剪直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交假定条件矩形裁剪窗口：[xmin,xmax]X[ymin,ymax]待裁剪线段：第5页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院6直线段裁剪待裁剪线段和窗口的关系

（1）完全落在窗口内，线段完全可见（2）完全落在窗口外，显然不可见（3）与窗口边界相交，线段至少有一端点在窗口之外，但非显然不可见

第6页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院7 要确定一条直线段上位于窗口内的可见段，只须求出它的两个位于窗口内的可见端点即可。算法的基本思想 把所有的直线按照它和窗口的关系分类，不同的直线使用不同的处理方法确定其可见部分。第7页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院8为提高效率，算法设计时应考虑：(一）快速判断情形(1)(2)；(二)设法减少情形(3)求交次数和每次求交时所需的计算量。直线裁剪算法的主要步骤：首先将不需要裁剪的直线挑出，并删去其中在窗外的直线；其次，对其余直线，逐条与窗框求交点，并将窗外部分删去第8页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院9实交点是直线段与窗口矩形边界的交点。虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。

第9页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院10直线的剪裁算法直接求交算法矢量裁剪法Cohen-Sutherland算法中点分割算法梁友栋－Barsky算法Nicholl-Lee-Nicholl算法第10页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院11直接求交算法直线与窗口边都写成参数形式，求参数值。第11页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院12矢量裁剪法算法思想先从线段的一个端点出发进行判断或进行求交运算，所得交点坐标保存在（xs，ys）中，然后再从线段的另一个端点出发用前面的判断及其求交运算求得交点坐标（x，y），最后只输出两个交点间的线段。用窗口的四条边界的直线将窗口分为9个区。012345678(x2,y2)ybytxlxr(x1,y1)第12页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院13排斥性测试若线段满足下述四个条件之一时：max(x1,x2)≤xlmin(x1,x2)≥xrmax(y1,y2)≤ybmin(y1,y2)≥yt则线段必定位于窗口之外，无输出线段。包含性测试若线段满足：xl≤x1≤xr,yb≤y1≤yt,则线段的始点在0区，也即线段可见段的起点为：

xs=x1,

ys=y1第13页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院14求交点，并判断I.若x1＜xl,则：线段的起点坐标可能位于3区、4区、5区。而新起点的坐标可能在直线y=yb和线段的交点上直线y=yt和线段的交点上直线x=xl和线段的交点上012345678(x1,y1)(x2,y2)ybytxlxr第14页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院15第一种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第二种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第三种情况：此时，若yb≤ys≤yt则(xsys)为有效新起点。三种情况都不满足，则此线段不在窗口区内。第15页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院16II.若x1>xr

线段的起点坐标可能位于6区、7区、8区。而新起点的坐标可能在直线y=yb和线段的交点上直线y=yt和线段的交点上直线x=xr和线段的交点上012345678(x1,y1)ybytxlxr第16页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院17第一种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第二种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第三种情况： 此时，若yb≤ys≤yt则(xsys)为有效新起点。若此三种情况都不满足，则此线段不在窗口区内。第17页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院18III若Xl<=X<=Xr线段的起点坐标可能位于1区和2区。而新起点的坐标可能在直线y=yb和线段的交点上直线y=yt和线段的交点上012345678(x1,y1)ybytxlxr第18页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院19第一种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第二种情况：

此时，若xl≤xs≤xr则(xsys)为有效新起点。若此二种情况都不满足，则此线段不在窗口区内。使用同样的方法，可得到直线在窗口的另一个可见端点。第19页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院20Cohen-Sutherland算法(编码算法)基本思想：Cohen-Sutherland直线剪裁算法以区域编码为基础，将窗口及其周围的八个方向以4bit的二进制数进行编码。对每条直线段p0(x0,y0)p1(x1,y1)分三种情况处理：(1)直线段完全可见，“简取”之。(2)直线段完全不可见，“简弃”之。(3)直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。

第20页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院21算法步骤：第一步判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；第二步判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步；第三步求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束

裁剪过程是递归的。第21页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院22第22页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院23Cohen-SutherLand算法(编码算法)特点：对显然不可见线段的快速判别编码方法：延长窗口的四条边线，由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；左域右域上域下域内域第23页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院24第一位1：点处于上边框线的上边；第二位1：点处于下边框线的下边；第三位1：点处于右边框线的右边；第四位1：点处于左边框线的左边；显然：如果某线段的两端点的两个四位代码全为零时那么该线段完全位于窗口内，即全为“0000”，可直接保留；如果两端点的标识码的逻辑与（按位乘）运算，结果不为零，那么该线段必位于窗口外，可直接舍弃。否则，这一线段可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，然后再进行上述测试，测试结果是必有一段在窗口之外，可被排除，另一段再重复上述处理过程。直到全部线段均被舍弃或被保留为止。第24页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院25Cohen-SutherLand算法(编码算法)端点编码：定义为它所在区域的编码结论：当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的第25页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院26求交测试顺序固定(左上右下）最坏情形，线段求交四次。Cohen-SutherLand算法(编码算法)对于那些非完全可见、又非显然不可见的线段，需要求交（如，线段AD)，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb）第26页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院27

1）特点：容易将不需要裁剪的直线挑出。规则是：如果一条直线的两端在同一区域，则该直线不需要裁剪，否则该直线为可能裁剪直线。对可能裁剪的直线缩小了与之求交的边框范围。规则是：如果直线的一个端点在上（下、左、右）域，则此直线与上边框求交，然后删去上边框以上的部分。该规则对直线的另一端点也适用。一条直线至多只需要与两条边框求交。用编码方法可快速判断线段--完全可见和显然不可见。

2）特别适用二种场合：大窗口场合；窗口特别小的场合，如光标拾取图形时,光标看作小的裁剪窗口。第27页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院28例题：P1P2P1：(-3/2,1/6)；编码(0001)P2：(1/2,3/2)；编码(1000)(2)求右边交点，得P’’1(1,11/6)P2(-1,1/2)；并编码，判别之不可见求左边交点，得P’1P2;P’1:(-1,1/2);编码(0000)

判别知非完全可见，且P’1在窗口内，因此交换P’1P2得新线段P1P2；

P1：(1/2,3/2)；编码(1000) P2：(-1,1/2)；编码(0000)(3)求上边交点，得P’’’1(-1/4,1)P2(-1,1/2)；并编码，两端点编码全部为0，线段完全可见，程序结束P1’P1’’P’’’1第28页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院29Cohen-SutherLand算法(编码算法)如何判定该与窗口的哪条边求交呢？ 编码中对应位为1的边。2）if(ai=bi=ci=di=0)则显示整条直线，取出下一条直线，返回1）；否则if((a1&a2)or(b1&b2)or(c1&c2)or(d1&b2)=1)则取出下一条直线，返回1）；否则例子：依次对每条直线P1P2作如下处理1）对直线两端点P1、P2按各自所在的区域编码，P1、P2的编码分别记为：C1(P1)={a1,b1,c1,d1}，C2(P2)={a2,b2,c2,d2}其中ai，bi，ci，di取值域为{0，1}，i={1,2}第29页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院303）if(a1&a2=1)，则求直线与窗上边（y＝yw_max)之交点，并删去交点以上部分；

if(b1&b2=1)，则求直线与窗下边（y＝yw_min)之交点，并删去交点以下部分；if(c1&c2=1)，则求直线与窗右边（x＝xw_max)之交点，并删去交点以右部分；if(d1&d2=1)，则求直线与窗左边（x＝xw_max)之交点，并删去交点以左部分；4）返回1）。第30页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院31第31页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院32中点分割算法基本思想：

从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。定义：

线段端点的最近可见点是指任一线段被窗口裁剪后所得两个新端点中离该端点较近的一个点。从P0点出发找出距P0最近的可见点（图中为A点），从P1点出发找出距P1最近的可见点（图中为B）。取中点Pm=(P1+P2)/2。第32页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院33中点分割法与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:全在、完全不在和线段与窗口有交。

对前两种情况，进行一样的处理。对第三类线段的处理

当对直线段不能简取也不能简弃时，不断地用对分方法，舍去线段的不可见部分，用中点去逼近线段与窗口边界的交点。 简单地用中点分割的方法求出线段与 窗口的交点，把线段等分为二段，对 两段重复上述测试处理，直至每条线 段完全在窗口内或完全在窗口外。第33页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院34实现算法：（以P0点为例说明）

1)排斥性测试 测试线段是否完全被排斥在窗口之外，若是，则无线段输出，算法结束。否则执行下一步；

2)包含性测试 测试P1点是否包含在窗口内，如果是，则P1点即为P0的最远可选点，算法结束，否则，执行下一步；

3)将直线段P0P1于中点Pm处分割，则分如下几种情况处理：第34页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院35线段MP1完全在窗口之外，那么便以线段P0M为新的线段P0P1，然后返回算法的第一步重新开始测试；如果线段MP1没有被完全排斥在窗口之外，那么便以线段MP1作为新线段P0P1，然后返回算法的第一步。P0P1MP0P1MP0P1MP0P1M第35页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院36中点分割算法-求线段与窗口的交点从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm,若P0Pm不是显然不可见的， 并且P0P1在窗口中有可见部分， 则距P0最近的可见点一定落在

P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。从P1出发找距离P1最近可见点采用上面类似方法。第36页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院37中点分割算法框图第37页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院38算法步骤：(1)输入直线段的两端点坐标：p0(x0,y0)、p1(x1,y1)，以及窗口的四条边界坐标：ymin、ymax、xmin和xmax。(2)对p0、p1进行编码：点p0的编码为code1，点p1的编码为code2。(3)若code1|code2=0，对直线段应简取之，保留当前直线段的端点坐标，转(5)；否则，若code1&code2≠0，对直线段可简弃之，转(5)；当上述两条均不满足时，进行步骤(4)。(4)求出直线段的中点M，将p1M、p2M入栈。(5)当栈不空时，从栈中弹出一条直线段，取为p0p1，转(2)进行处理。否则，继续(6)。(6)当栈为空时，合并保留的直线段端点，得到窗口内的直线段p0p1。用直线扫描转换算法画出当前的直线段p0p1，算法结束。第38页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院39 中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。第39页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院40第40页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院41重新构造算法步骤：(1)若code1|code2=0，对直线段应简取之，结束；否则，若code1&code2≠0，对直线段可简弃之，结束；当这两条均不满足时，进行步骤(2)。(2)找出该直线段离窗口边界最远的点和该直线段的中点。判中点是否在窗口内：若中点不在窗口内，则把中点和离窗口边界最远点构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点；如中点在窗口内，则又以中点和最远点构成线段，并求其中点，直到中点与窗口边界的坐标值在规定的误差范围内相等，则该中点就是该线段落在窗口内的一个端点坐标。(3)如另一点在窗口内，则经(2)即确定了该线段在窗口内的部分。如另一点不在窗口内，则该点和所求出的在窗口上的那一点构成一条线段，重复步骤(2)，即可求出落在窗口内的另一点。第41页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院42第42页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院43

#defineTRUE1#defineFALSE0intmid_trim(p1,p2,xmin,ymin,xmax,ymax,a)floatp1[3],p2[3],xmin,ymin,xmax,ymax,a[3];{floatA[3],B[3],M[3];set_point(p1,A);set_point(p2,B);while(TRUE){if(Identify_line_out(A,B,xmin,ymin,xmax,ymax)==TRUE)retuenFALSE;if(Identify_pt_in(B,xmin,ymin,xmax,ymax)==TRUE){set_point(B,a);returnTRUE;}第43页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院44

else{get_midpoint(A,B,M);if(Identify_line_out(M,B,xmin,ymin,xmax,ymax)==TRUE){set_point(M,B);}else{set_point(M,A);}}}第44页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院45第45页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院46对分辩率为2N*2N的显示器，上述二分过程至多进行N次。主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。中点分割裁剪算法第46页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院47梁友栋－Barsky算法算法基本思想：设要裁剪的线段为P0P1

，和窗口边界交于A,B,C,D四点。首先从D、A和P0三点中找出最靠近P1的点。图中显然为A其次从C、B和P1中找出最靠近P0的点，图中显然为B那么AB就是P0P1线段上的可见部分第47页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院48梁友栋－Barsky算法具体计算时将P0P1写成参数方程其中：0<=t<=1第48页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院49梁友栋－Barsky算法窗口边界分类：始边和终边第49页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院50梁友栋－Barsky算法——交点计算xyyTyBxLxBABCDP1P0第50页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院51梁友栋－Barsky算法为了确定始边和终边，以及求P0P1与它们的交点，令易知交点的参数为第51页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院52梁友栋－Barsky算法EFAB分析另外一个D第52页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院53梁友栋-Barsky算法当Qi=0时若Di<0时，线段不可见（如图中AB，有QR=0，DR<0）若Di>0时,分析另一D,

（如图中的EF就是这种情况，它使QL=0，DL>0和QR=0，DR>0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）EFAB第53页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院54P1yxyTyBxLxBABCDP0t0’t0’’t1’t1’’lP0lP1第54页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院55第55页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院56Nicholl-Lee-Nicholl算法NLN算法在求交计算前进行更多的区域测试来减少求交计算，消除C-S算法中多次求交的情况。基本想法：通过在裁剪窗口周围创立多个区域来对一条直线段的多次裁剪。也即对2D平面的更细的划分。第56页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院57Nicholl-Lee-Nicholl算法假定待裁剪线段P0P1为非完全可见且非显然不可见。步骤：第一步，窗口四边所在的直线将二维平面划分成9个区域，假定落在区域0、4、5

第57页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院58Nicholl-Lee-Nicholl算法第二步：从P0点向窗口的四个角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域。此时P1的位置决定了P0P1和窗口边的相交关系。第58页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院59Nicholl-Lee-Nicholl算法第三步，确定P1所在的区域（判断P1所在区域位置，可判定P0、P1与窗口哪条边求交)。 根据窗口四边的坐标值及P0P1和各射线的斜率可确定P1所在的区域。第四步，求交点，确定P0P1的可见部分特点：效率较高，但仅适合二维矩形窗口。第59页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院60非矩形窗口的线段裁剪思考：凹多边形窗口的线段裁剪圆和曲线窗口的线段裁剪第60页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院61多边形裁剪几个概念凸多边形如果多边形任意两个内点的连线都在多边形里，则该多边形称为凸多边形；凹多边形一个非凸多边形称为凹多边形多边形正方向顶点为P1,…,PN（并且边为Pi-1Pi，PNP1）的多边形，如果按照这种顺序遍历产生一个逆时针回路，则该多边形被认为是正方向的。第61页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院62多边形裁剪错觉：直线段裁剪的组合？新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？第62页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院63多边形裁剪2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？第63页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院64多边形的剪裁算法Sutlerland－Hodgman算法Weiler－Athenton算法第64页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院65Sutherland-Hodgman算法对多边形裁剪的Sutherland-Hodgman算法是一种简便的方法，只要对多边形用窗口的四条边依次裁剪四次，便可得到裁剪后的多边形。分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。第65页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院66基本思想：1）令多边形的顶点按边线逆时针走向排序。各边先与左窗边求交。求交后删去多边形在窗之左的部分，并插入左窗边及其延长线的交点之间的部分，从而形成一个新的多边形。然后，新的多边形按相同的方法与上窗边相裁剪。如此重复，直至与各窗边都裁剪完毕。2）多边形与每一条窗边相交，生成新的多边形顶点序列的过程，是一个对多边形各顶点依次处理的过程。第66页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院67第67页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院68第68页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院69第69页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院70Sutherland-Hodgman算法流水线过程(左上右下)：左边的结果是上边的开始。亦称逐边裁剪算法第70页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院71算法实施策略：为窗口各边界裁剪的多边形存储输入与输出顶点表。在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。窗口的一条边以及延长线构成的裁剪线把平面分为两个区域，包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧。第71页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院72沿着多边形依次处理顶点会遇到四种情况：第72页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院73第73页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院74Sutherland-Hodgman算法框图是否第一点?取点PSPFPS在e的可见侧退出输出SSP和e相交？计算SP和e的交点I输出I(a)(b)是是是否是否否否开始处理线段SP顶点输入完毕？退出第74页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院75设封闭多边形的顶点为P1,P2,…Pn，框图中e是表示窗口的四条边中正在裁剪的一条边，每次裁剪时第一个点存放在F中，以便对最后一条边裁剪时使用。用图（a）中的算法对边P1P2,P2P3,…Pn-1Pn作裁剪，用图（b）中的算法对最后一条边PnP1作裁剪。裁剪好一条边便输出一条边。上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。第75页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院76Sutherland-Hodgman算法裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。几点说明：裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口第76页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院77Weiler-Athenton算法裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为A裁剪多边形：裁剪窗口，记为B第77页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院78主多边形和裁剪多边形把二维平面分成两部分。内裁剪：A∩B外裁剪：A-BWeiler-Athenton算法裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界

第78页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院79Weiler-Athenton算法如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：进点：主多边形边界由此进入裁剪多边形内如，I1,I3,I5,I7,I9,I11出点：主多边形边界由此离开裁剪多边形区域.

如，I0,I2,I4,I6,I8,I10第79页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院80Weiler-Athenton算法1）建顶点表；2）求交点；3）裁剪……Weiler_Athenton裁剪算法（内裁剪）步骤：1、建立主多边形和裁剪多边的顶点表．2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针。3、裁剪如果存在没有被跟踪过的交点，执行以下步骤：

第80页，共93页，2023年，2月20日，星期二2023/2/22计算机科学与技术学院81

(1)建立裁剪结果多边形的顶点表．

(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．

(3)如果该交点为进点，跟踪主多边形边界；否则跟踪裁剪多边形边界．

(4)跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点．

(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪