计算机图形学 55裁剪算法

1、5.5 5.5 裁剪算法裁剪算法 5.1.1 5.1.1 线段裁剪算法线段裁剪算法 5.1.2 5.1.2 多边形裁剪算法多边形裁剪算法 确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形,这个选择过程称为裁剪裁剪。该显示区被称为裁剪窗口裁剪窗口。5.5.1 线段裁剪算法线段裁剪算法 假设矩形窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，则点P(x,y)在窗口内的条件是：(x(xL L,y,yB B ) )(x(xR R,y,yT T ) )P点的位置点的位置是裁剪中最基本的问题是裁剪中最基本的问题否则，P点就在窗口外。满足： xL = x

2、 = xR 和 yB = y = yTl 直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。l 常用的线段裁剪方法 Cohen-Sutherland、 中点分割算法、 梁友栋barskey算法。5.5.1 线段裁剪算法线段裁剪算法快速判断情形(1)(2)，对于情形(3)，设法减少求交次数和每次求交时所需的计算量。abc裁剪线段与窗口的关系：裁剪线段与窗口的关系：(1) 线段完全可见；(2) 显然不可见；(3) 线段至少有一端点在窗口之外，但非显然不可见。如何提高裁剪效率？如何提高裁剪效率？ 线段裁剪有多种算法，但基本思想都是：（1）线段

3、是否全不在窗口内，是则结束。（2）线段是否全在窗口内，是则显示该线段，结束。（3）计算该线段与窗口边界延长线的交点，以此将线段分成两部分；丢弃不可见的部分；对剩下的部分转（2）。它又称为Sutherland-Cohen分割线算法.5.5.1.1 Cohen-Sutherland 端点编码算法将矩形窗口的四边分别延长后，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。1.1.线段的端点编码线段的端点编码 它是最早最流行的裁剪算法, 可以扩展为三维裁剪. 区域码为：区域码为： 上上 下下 右右 左左 X X X X

4、X X X X任何位赋值为任何位赋值为1 1，代表端点落在相应的位置上，否，代表端点落在相应的位置上，否则该位为则该位为0 0。这一编码的这一编码的特点特点是对于窗口的某一条是对于窗口的某一条边外侧的三个区域的四位编码中有一位全为边外侧的三个区域的四位编码中有一位全为1。线段的端点编码线段的端点编码100110001010000101010010011001000000 上上 下下 右右 左左 P1 Y=YT P2 Y=YBP4P3X=XL X=XR线段的各端点编码？线段的各端点编码？对于三维裁剪对于三维裁剪,需要需要6位编码。位编码。(1010)(1001) P3： 0110 P1: 100

5、1 P4：& 1010 P2:& 0010 0010 0000 (0110)(0010) 一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律： 否则，在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。若P1P2明显在窗口外外：code1&code20，则“弃弃”若P1P2完全在窗口内内：code1=0,且code2=0,则“取取”(1)若线段若线段P1P2两端点的四位编码均为两端点的四位编码均为0,则两端点均在窗口内则两端点均在窗口内,该线段完全可见该线段完全可见,显示该线段显示该

6、线段,算法结束算法结束; P6P5P2P1P4P3Cohen-Sutherland端点编码算法(3)若线段两端点的四位编码按位若线段两端点的四位编码按位“与与”结果为结果为0, 找到找到P1P2在窗口外的一个端点在窗口外的一个端点P1(或或P2),用窗口相应的边与用窗口相应的边与P1P2的交的交点取代该端点点取代该端点P1（或（或P2）, 返回返回(1)步。步。(2) 若线段若线段P1P2两端点的四位编码按位两端点的四位编码按位“与与”结果为非结果为非0,则则该线段完全不可见该线段完全不可见,算法结束。算法结束。裁剪一条线段时，先求出端点裁剪一条线段时，先求出端点p1和和p2的编码的编码cod

7、e1和和code2，然后然后 (1)若若code1|code2=0，对直线段应简取之。，对直线段应简取之。 (2)若若code1&code20，对直线段可简弃之。，对直线段可简弃之。 (3)若上述两条件均不成立。则需求出直线段与窗口边界若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。段完全被舍弃或者找到位于窗口内的一段线段为止。 4.求交

8、：假定直线的端点坐标为求交：假定直线的端点坐标为(x1, y1)和和(x2, y2) (1)左、右边界交点的计算：左、右边界交点的计算：y=y1+k(xx1)； (2)上、下边界交点的计算：上、下边界交点的计算：x=x1+(yy1)/k。 Cohen-Sutherland端点编码算法特点：用编码方法可快速判断线段的完全可见和显然不可见。优点：简单，易于实现。如何求窗口边界与线段如何求窗口边界与线段P1P2的交点的交点? 计算线段计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点与窗口边界的交点CodeCode代表线段某个端点的编码。代表线段某个端点的编码。if(LEFT&co

9、de !=0)if(LEFT&code !=0) x=XL;x=XL; y=y1+(y2-y1)y=y1+(y2-y1)* *(XL-x1)/(x2-x1);(XL-x1)/(x2-x1);else if(RIGHT&code !=0)else if(RIGHT&code !=0) x=XR;x=XR; y=y1+(y2-y1)y=y1+(y2-y1)* *(XR-x1)/(x2-x1);(XR-x1)/(x2-x1);else if(BOTTOM&code !=0)else if(BOTTOM&code !=0) y=YB;y=YB; x=x1+(x2

10、-x1)x=x1+(x2-x1)* *(YB-y1)/(y2-y1);(YB-y1)/(y2-y1); else if(TOP & code !=0) else if(TOP & code !=0) y=YT;y=YT; x=x1+(x2-x1)x=x1+(x2-x1)* *(YT-y1)/(y2-y1);(YT-y1)/(y2-y1);如何判定线段应该与窗口的哪条边求交呢？如何判定线段应该与窗口的哪条边求交呢？编码中对应位为编码中对应位为1的窗口边。的窗口边。P1：(-3/2, 1/6)；编码；编码 (0001)P2：(1/2, 3/2)；编码；编码 (1000)(2) 求右

11、边交点，得求右边交点，得 P1(1, 11/6) P2(-1, 1/2)； 并编码，并编码， 判别之不可见判别之不可见(1) 求左边交点，得求左边交点，得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， 线段完全可见，程序结束

12、线段完全可见，程序结束P1P1P1x=x1+(y-y1)*(x2-x1)/(y2-y1)y=y1+(x-x1)*(y2-y1)/(x2-x1)多边形的裁剪多边形的裁剪多边形的裁剪多边形的裁剪 对多边形的裁剪对多边形的裁剪不等于把多边形的每一条边进行不等于把多边形的每一条边进行裁剪裁剪。 因为在图形学中，多边形被认为是一个封闭的区因为在图形学中，多边形被认为是一个封闭的区域，它把平面分为多边形内和多边形外。域，它把平面分为多边形内和多边形外。 (a)(a)裁剪前裁剪前(b)(b)直接采用直线段直接采用直线段裁剪的结果裁剪的结果多边形的裁剪多边形的裁剪 对一个多边形的对一个多边形的裁剪结果仍要求是

13、多边形，裁剪结果仍要求是多边形，且原来是多边且原来是多边形内的点也在裁剪后的多边形内。形内的点也在裁剪后的多边形内。 一部分窗口的边界可能成为裁剪后的多边形的边界，一个一部分窗口的边界可能成为裁剪后的多边形的边界，一个凹多边形裁剪后可能成为几个多边形。凹多边形裁剪后可能成为几个多边形。 多边形裁剪算法的输出应该是定义裁剪后的多边形边界的多边形裁剪算法的输出应该是定义裁剪后的多边形边界的顶点序列。于是，需要构造能产生一个或多个封闭区域的多顶点序列。于是，需要构造能产生一个或多个封闭区域的多边形裁剪算法。边形裁剪算法。(c)(c)正确的裁剪结果正确的裁剪结果对多边形裁剪的对多边形裁剪的Suther

14、land-Hodgman算法是一种算法是一种简便的方法，只要对多边形用窗口的四条边依次裁简便的方法，只要对多边形用窗口的四条边依次裁剪四次，便可得到裁剪后的多边形。剪四次，便可得到裁剪后的多边形。 Sutherland-Hodgman Sutherland-Hodgman算法算法5.1 .2 Sutherland-Hodgman逐次多边形裁剪算法逐次多边形裁剪算法Sutherland-HodgmanSutherland-Hodgman基本基本思想思想基本思想：是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧多边形的各条边的两端点

15、S、P。它们与裁剪线的位置关系只有四种：可见一侧可见一侧可见一侧可见一侧SpSSSppp(1)(2)(3)(4)Sutherland-Hodgman基本思想基本思想假设当前处理的边为SP,顶点S在上一轮中已经处理。对于情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P可见一侧可见一侧可见一侧可见一侧SpSSSppp(1)(2)(3)(4)是否第一点是否第一点?取点取点PSP和和e相交？相交？计算计算SP和和e的交点的交点I输出输出IS PF PS在在e的可见侧的可见侧退出退出输出输出S(a)(a) Sutherland-Hodgman Sutherland-Hodgman算法的框图算法的框图是是是是否否是是否否否否设封闭多边形的顶点为设封闭多边形的顶点为P1,P2,P1,P2,PnPn，框图中，框图中e e是表示窗口是表示窗口的四条边中正在裁剪的一条边，的四条边中正在裁剪的一条边，每次裁剪时每次裁剪时第一个点存放在第一个点存放在F F中，中，以便对最后一条边裁剪时使用。以便对最后一条边裁剪时使用。 用图（用图（a a）中的算法对边）中的算法对边P P1 1P P2 2, ,P P2 2P P3 3, , P Pn-1n-1P Pn n作裁剪。作裁剪。图图(a)用图（用图