计算机图形学5.5裁剪算法.ppt
5.5 裁剪算法 5.1.1 线段裁剪算法 5.1.2 多边形裁剪算法,确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形,这个选择过程称为裁剪。该显示区被称为裁剪窗口。,5.5.1 线段裁剪算法,假设矩形窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，则点P(x,y)在窗口内的条件是：,(xL,yB),(xR,yT),P,点的位置是裁剪中最基本的问题,否则，P点就在窗口外。,满足：xL=x=xR 和 yB=y=yT,直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。常用的线段裁剪方法 Cohen-Sutherland、中点分割算法、梁友栋barskey算法。,5.5.1 线段裁剪算法,快速判断情形(1)(2)，对于情形(3)，设法减少求交次数和每次求交时所需的计算量。,裁剪线段与窗口的关系：,(1)线段完全可见；(2)显然不可见；(3)线段至少有一端点在窗口之外，但非显然不可见。,如何提高裁剪效率？,线段裁剪有多种算法，但基本思想都是：,（1）线段是否全不在窗口内，是则结束。（2）线段是否全在窗口内，是则显示该线段，结束。（3）计算该线段与窗口边界延长线的交点，以此将线段分成两部分；丢弃不可见的部分；对剩下的部分转（2）。,它又称为Sutherland-Cohen分割线算法.,5.5.1.1 Cohen-Sutherland 端点编码算法,将矩形窗口的四边分别延长后，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。,1.线段的端点编码,它是最早最流行的裁剪算法,可以扩展为三维裁剪.,区域码为：上 下 右 左 X X X X任何位赋值为1，代表端点落在相应的位置上，否则该位为0。这一编码的特点是对于窗口的某一条边外侧的三个区域的四位编码中有一位全为1。,线段的端点编码,上 下 右 左 P1 Y=YT P2 Y=YB,P4,P3,X=XL X=XR,线段的各端点编码？,对于三维裁剪,需要6位编码。,(1010),(1001),P3：0110 P1:1001 P4：&1010 P2:&0010 0010 0000,(0110),(0010),一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：,否则，在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,若P1P2明显在窗口外：code1&code20，则“弃”,若P1P2完全在窗口内：code1=0,且code2=0,则“取”,(1)若线段P1P2两端点的四位编码均为0,则两端点均在窗口内,该线段完全可见,显示该线段,算法结束;,Cohen-Sutherland端点编码算法,(3)若线段两端点的四位编码按位“与”结果为0,找到P1P2在窗口外的一个端点P1(或P2),用窗口相应的边与P1P2的交点取代该端点P1（或P2）,返回(1)步。,(2)若线段P1P2两端点的四位编码按位“与”结果为非0,则该线段完全不可见,算法结束。,裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后(1)若code1|code2=0，对直线段应简取之。(2)若code1&code20，对直线段可简弃之。(3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。4.求交：假定直线的端点坐标为(x1,y1)和(x2,y2)(1)左、右边界交点的计算：y=y1+k(xx1)；(2)上、下边界交点的计算：x=x1+(yy1)/k。,Cohen-Sutherland端点编码算法,特点：用编码方法可快速判断线段的完全可见和显然不可见。,优点：简单，易于实现。,如何求窗口边界与线段P1P2的交点?,计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点Code代表线段某个端点的编码。if(LEFT,如何判定线段应该与窗口的哪条边求交呢？,编码中对应位为1的窗口边。,P1：(-3/2,1/6)；编码(0001)P2：(1/2,3/2)；编码(1000),(2)求右边交点，得 P1(1,11/6)P2(-1,1/2)；并编码，判别之不可见,求左边交点，得P1P2;P1:(-1,1/2);编码(0000)判别知非完全可见，且P1在窗口内，因此交换P1P2得新线段P1P2；P1：(1/2,3/2)；编码(1000)P2：(-1,1/2)；编码(0000),(3)求上边交点，得 P1(-1/4,1)P2(-1,1/2)；并编码，两端点编码全部为0，线段完全可见，程序结束,P1,x=x1+(y-y1)*(x2-x1)/(y2-y1)y=y1+(x-x1)*(y2-y1)/(x2-x1),多边形的裁剪,多边形的裁剪,对多边形的裁剪不等于把多边形的每一条边进行裁剪。因为在图形学中，多边形被认为是一个封闭的区域，它把平面分为多边形内和多边形外。,多边形的裁剪,对一个多边形的裁剪结果仍要求是多边形，且原来是多边形内的点也在裁剪后的多边形内。一部分窗口的边界可能成为裁剪后的多边形的边界，一个凹多边形裁剪后可能成为几个多边形。多边形裁剪算法的输出应该是定义裁剪后的多边形边界的顶点序列。于是，需要构造能产生一个或多个封闭区域的多边形裁剪算法。,对多边形裁剪的Sutherland-Hodgman算法是一种简便的方法，只要对多边形用窗口的四条边依次裁剪四次，便可得到裁剪后的多边形。,5.1.2 Sutherland-Hodgman逐次多边形裁剪算法,Sutherland-Hodgman基本思想,基本思想：是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种：,Sutherland-Hodgman基本思想,假设当前处理的边为SP,顶点S在上一轮中已经处理。对于情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P,是否第一点?,取点P,SP和e相交？,计算SP和e的交点I,输出I,S P,F P,S在e的可见侧,退出,输出S,(a),Sutherland-Hodgman算法的框图,是,是,否,是,否,否,设封闭多边形的顶点为P1,P2,Pn，框图中e是表示窗口的四条边中正在裁剪的一条边，每次裁剪时第一个点存放在F中，以便对最后一条边裁剪时使用。用图（a）中的算法对边P1P2,P2P3,Pn-1Pn作裁剪。,图(a),用图（b）中的算法对最后一条边PnP1作裁剪。裁剪好一条边便输出一条边。,SP和e相交？,计算SP和e的交点I,输出I,退出,(b),是,否,取点F为P,图(b),上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。,流水线过程(左上右下)：亦称逐边裁剪算法,
