直线段裁剪算法.ppt

1、直线段裁剪的 Liang-Barsky算法,线段裁剪的意义 Liang-Barsky算法,0 问题的提出,线段裁剪就是将指定窗口作为图形边界，将窗口内的线段保留，而窗口外的线段则被舍弃。,1.线段裁剪的意义,Before clipping,After clipping,裁剪处理涉及： （1）线段在窗口内外的判别； （2）线段与窗口的求交。,2.Liang-Barsky 算法,（1）算法背景 经典算法 -写入图形学教科书的唯一中国人算法,Sutherland,梁友栋,苏步青,Barsky,梁友栋的贡献： Liang-Barsky算法 几何连续理论 Communication of ACM 论文(

2、83),1935年7月出生,福建福州人.,1956年毕业于复旦大学数学系,1960年复旦大学数学系研究生毕业 1960年分配到浙江大学数学系任教,1979年至1981年在美国Utah大学计算机系作访问学者 获国家教委科技进步一等奖,1987 获国家自然科学三等奖,1991,60sCohen-Sutherland的编码方法:,Cohen,Sutherland,78年Cyrus和Beck的参数化方法-更有效的算法:,84年梁友栋和Barsky提出了更快的参数化线段裁剪算法。,（2） 算法思想,Liang-Barsky算法的几何含义：入边、出边和端点,Parameterized line segme

3、nt: x = x1 + u(x2 x1) = x1 + uDx y = y1 + u (y2 y1) = y1 + uDy 0 u 1,If a point on the line is inside the clipping window, then: xmin x1 + uDx xmax ymin y1 + uDy ymax,xmin x1 +uDx = ( Dx) u x1 xmin,We rewrite the inequalities in the form upk qk Left Border, k= 1: pk = Dx, qk= x1 xmin Right Border, k

4、= 2: pk = Dx, qk= xmax x1 Bottom Border, k=3: pk = Dy, qk= y1 ymin Top Border, k=4: pk = Dy, qk= ymax y1,x1 + uDx xmax = (Dx) u xmax x1,ymin y1 + uDy = ( Dy) u y1 ymin,y1 + uDy ymax = (Dy) u ymax y1,Case 1: pk 0,If pk 0, then the extension of the line segment goes from inside to outside. The order o

5、f going from inside to outside and outside to inside the boundaries indicates whether we need to clip. To determine this, we solve for u for the intersection of the line with each of the extended boundaries: uk = qk / pk,Case 2: pk = 0,If pk = 0, then the line is parallel to the border of the clippi

6、ng window that corresponds to k (e.g. the left border for k=1). if qk 0, the line is completely outside the clipping window. It can be discarded. if qk 0，the line is inside the boundary and further consideration.,ymax,If x2 = x1 then p1 and p2 are zero. q2= xmax x1 0 Discard line.,（3）The Liang-Barsk

7、y Algorithm,1 If pk=0 and qk0,calculate rk=qk / pk. Let u2=minrk ,1. 4 If u1 u2，discard the line since it is completely outside the clipping window. Otherwise, use u1 and u2 to calculate endpoints of the clipped line.,裁减的插曲： 汪嘉业的快速算法 80年代的裁减热：应道宁、汪国昭等 对三种算法比较: Cohen-Sutherland与中点法在区域码测试阶段能以位运算方式高效率的进行，因而当大多数线段能够简单的取舍时，效率较好。 梁友栋Barskey算法只能应用于矩形窗口的情形，但其效率比前两者要高，这是因为运算只涉及到参数，仅到必要时才进行坐标计算。