直线裁剪算法研究(Cohen_Sutherland算法和Liang_Barsky算法)

1、直线裁剪算法研究摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的根底上，针对Cohen-Sutherland 算法和Liang-Barsky算法进行了分析研究。并对两 种算法了计算直线与窗口边界的交点时，进行了有效有比拟。关键词：裁剪；算法；Cohen-Sutherland ； Liang Barsky ；1引言直线是图形系统中使用最多的一个根本元素。所以对于直线段的裁剪算法是被研究最 深入的一类算法，目前在矩形窗口的直线裁剪算法中，出现了许多有效的算法。其中比拟 著名的有：Cohen-Sutherlanc算法、中点分割算法、Liang-Barsky算法、Sobk

2、ow-Pospisil-Yang 算法，及 Nicholl - Lee-Ncholl 算法等。2直线裁剪的根本原理图1所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之如图1中P5到P6的直线，那么此直线应保存。如果一条直线的一个端点在窗口外如P9另一个点在窗口如P10，那么应从直线与边界的交点P9处裁剪掉边界之外的线段。如果直 线的两个端点均在边界外，那么可分为两种情况：一种情况是该直线全部在窗口之外；另一 种情况是直线穿过两个窗口边界。图中从 P3到P4的直线属于前一种情况，应全部裁剪掉； 从P7到

3、P8的直线属于后一种情况，应保存P7到 P8的线段，其余局部均裁剪掉。图1直线相对干窗口边界的栽剪直线裁剪算法应首先确定哪些直线全部保存或全部裁剪，剩下的即为局部裁剪的直 线。对于局部裁剪的直线那么首先要求出这些直线与窗口边界的交点，把从交点开始在边界 外的局部裁剪掉。一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁 剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。3 cohe n sutherla nd 直线裁剪算法Cohen-Sutherlan算法的大意是：对于每条线段 P1P2,分为3种情况处理。 假设P1P2完全在窗口，那么显示该线段P1P2,简称“取之。 假设P

4、1P2明显在窗口外，那么丢弃该线段，简称“弃之。 假设线段既不满足“取的条件，也不满足“弃的条件，那么把线段分为两段。其中 一段完全在窗口外，可弃之。然后对另一段重复上述处理。1 区域码及其建立Cohe n-Sutherla n直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位 置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码， 即区域码的4位分别代表端点位于窗口的上、下、左、右。区域码从右到左的各位所代表 的坐标区如下所示:位 一 4321坐标区 一上下右左上述各位中某位为1,那么表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见，位于窗中

5、的点，其区域码应为 0000,位于窗口左下方的点，其区域码应 为0101，其余类推。区域码各位的值可以通过对端点坐标X，y 与窗口边界的比拟求得。如果 XVXwmin， 那么区域码的第一位为1,其余各位确实定与此相似。现在的计算机语言都可以进行位操作， 因此，可以通过以下步骤建立区域码： 计算出端点坐标与窗口边界的差。 按计算出的各个差的符号把区域码的相应位置为0或1 ,即区域码的第一位置为 区域码的第二位置为 区域码的第三位置为 区域码的第四位置为2 区域码裁剪算法X Xwmin 的符号位;Xwmin-X 的符号位； y-ywmin 的符号位； ywmin-y 的符号位。图2区域码对所有直线

6、的端点都建立了区域码之后，就可按区域码判断直线在窗口之或窗口之 外。这可分为如下几种情况： 假设一直线的两个端点的区域码均为 0000那么此直线在窗口边界之，应子保存。 假设一直线的两个端点的区域码的同一位同时为1,那么此直线全部在窗口边界之外，应子裁剪。例如，假设一直线的一个端点的区域码为1001，另一个端点的区域码为 0101,那么此两端点的区域码的第一位均为1,说明此两端点均在窗口边界之左，因此，直线在窗口边界之外，应予裁剪。可用将直线两个端点的区域码进行与操作的方法，判断直线是否 在窗口之外，假设与操作的结果为0000那么两端点的区域码任何位均不同时为 1,此直线不一 定被裁剪。 以上

7、两种情况之外的直线，有可能穿过窗口，也有可能不穿过窗口，如图87所示。图中所示的两条直线都不符合情况的要求，但一条直线(P1P2)穿过窗口，另一直线(P3P4)不守过窗口。对这类直线可以进行如下处理：取窗口外的一个端点与窗口边界比拟以确定 可排除直线的哪一局部，然后，把直线剩下的局部与其他边界比拟，这样一直到直线全部 被排除或确定直线的哪一局部在窗口之为止。可按“左、右、下、上的次序建立检查直 线端点与窗口边界关系的算法。下面介绍对图3所示的两条直线进行处理的过程。从直线P1P2的下端点P1开始，依次检查窗口的左、上、右及下边界，可发现此点在窗口之下(因为区域码的第三位为1)。然后求得直线与下

8、边界的交点 P1排除线段P1 P1这样直线就缩短为P1 P2。因为P2在边界之 外，将此端点与各边界比拟，可发现此端点在窗口上面。计算出交点P2线段P1P2保存下来。这样就完成了对这条线的处理并开始处理下一直线P3 P4。端点P3在窗口之左，可计算出交点P3讲裁剪掉线段P3P3。检查P3P4的区域码，可发现直线的这一剩余局部在窗口之 下故也可排除。由于窗口边界均平行于坐标轴，所以直线与窗口边界的交点可以用直线方程的各参数很方便地求出，对于一条端点坐标为X1,%及X2,y2的直线，其与一垂直边界的交点的y坐标可以用下式计算：y y1 m x x1这里互的取值可取x或Xwmax，斜率m可用公式m

9、y y X2 X1计算。同样地， 与水平边界交点的x坐标可用下式计算：X X1y y1 . m这里y的值可取几ywmin或ywmax。下面是区域码直线裁剪算法的 C语言描述，其中每个端点的区域码用4元素布尔数组表示。区域码直线裁剪算法代码Void Li ne_Clippi ng(x1,y1,x2,y2,xw_xmi n,y w_ymi n, xw_max,yw_max)float x1,y1,x2,y2,xw_x min,yw_ymin, xw_max,xw_max,yw_max;/* X1, y1和X2, y2是线段端点坐标*/Int draw,d one;Int code1,code2,c

10、ode;float x,y;Draw=FALSE; don e=FALSE;code1=get_code(x1,y1,xw_xmi n,y w_ymi n, xw_max,yw_max); code2=get_code(x2,y2,xw_x min,yw_ymin, xw_max,yw_max);while(! Done)if (code1= =0 && code= =2) draw=TRUE;done=TRUE;else if (code1 & code2 !=0) done=TRUE;elseIf (code1 !=0) code=code1;else code=c

11、ode2;if (code&TOP!=0) y=yw_ymax; x=x1+(y-y1)*(x2-x1)/(y2-y1);else if (code&BOTTOM!=0)y=yw_ymin; x=x1+(y-y1)*(x2-x1)/(y2-y1);else if (code&RTGHT!=0)x=xw_xmax; y=y1+(x-x1)*(y2-y1)/(x2-x1);else if (code&LIFT!=0)x=xw_xmin; y=y1+(x-x1)*(y2-y1)/(x2-x1);if (code= =code1)x1=x; y1=y; code1=ge

12、t_codex1,y1,xw_xmin,yw_ymin,xw_max,yw_max; elsex2=x;y2=y; code2=get_codex2,y2,xw_xmin,yw_ymin,xw_max,yw_max; If (draw)Draw_Line(x1,y1,x2,y2);int get_code(x,y,xw_xmin,yw_ymin,xw_max,yw_max)float x,y,xw_xmin,yw_ymin,xw_max,yw_max;int code; code=0; if (y>yw_ymax) code| =TOP; else if (y<yw_ymin) c

13、ode|=BOTTOM; if (x>xw_xmax) code|=RIGHT;else if (x<xw_xmin) code|=LEFT;return code; 4 Liang Barsky 算法Liang (梁友栋)-Barsky算法又称为参数方程法。首先写出端点及 gy 之间连线的参数方程如下：xx1x2x1ux1xuyy1y2y1uy1yu其中， x x2 x1, y y2 y1 。参数 u 可取 0 1 之间的值，坐标 x,y 表示此围的 u 值定义的直线上的一个点。当u= 0时，x, yxi,yi ,直线的另一端 u = 0时，x,yx2, y2 。我们发现，如果直

14、线上的某点处于 x, y 及 xwmin,ywmin 及 xwmax, ywmax 所定义的窗口 之，那么满足以下条：xwmin 三 X1XU 仝 xwm axy wmin W y1 yu 三 ywmax这四个不等式可以表示为:upk < qk,k=1,2,3,4其中，参数p, q定义为;P1X,q1X1XwminP2X,q2XwmaxX1P3y,q3y1y w minP4y,q4ywmax屮按照直线与窗口边界的相对位置，可分为以下几种倩况。 任何一条与窗口边界平行的直线，其 pk 0，此处k值表示取哪一个边界k=1,2,3 及4,分别相应于左、右、下及上边界。如果对某一 k值，还满足q

15、k 0，那么此直线完全 在边界外，可不进一步考虑；如果 qk > 0，那么此与边界平行的直线在边界。 如果qk 0，那么情况较复杂。此时，可把直线按从 捲匚！到X2,y2连线方向作为正向，将此直线无限延伸，同时把各窗口边界也无限延伸见图3;然后分以下两种情况讨论：a当qk 0时，那么是由窗口外发出的一条直线 的无限延伸线进入相应窗口边界的无限延伸线的 部。b当qk 0时，情况相反。即直线的延伸线是 由窗口边界延伸线的部到外部。以图3中的直线L!为例，说明以上两种情况。 表1.1给出的延伸线相对于4个边界延伸线的方 向及qk取值。表1.1直线方向与Pk取值边界Pk取值方向交占八、左p1xx

16、2x10由外到山右p2xx2x10由到外下P3y y2 y10由外到上P4y y2y10由到外u2当qk 0时，可以用下式计算出一参数 u，此u值应于直线延伸线与窗口边界 k的延伸线的交点:u qk Pk对于每条直线，可计算出一对u值U1及U2 ，由此两参数可判断直线是如何裁剪的。 其中，u1的值可由从窗口边界外发出进人窗口边界之的直线Pk 0 所涉及的窗口边界确定。对于这些窗口边界，可计算出各 rk q-Pk，取各rk中最大值即为回5, u?可由自窗口边界发出至窗口边界外的直线(Pk 0 )所涉及的窗口边界确定，同样可计算出这些窗口边界的rk值，取各rk中的最小值即为U2。如果uiU2，那么

17、此直线全部在窗口外而可排除：否那么，此直线在窗口，可由ui及U2计算出彼裁剪直线的端点。图3中标出直线Li及L2 相应于ui及U2的与边界的交点。Li的U2ui，那么Li彼裁剪，并可由ui及U2计算出裁剪点；而L2的uiu2，那么此直线全部彼排除。此算法可用以下过程表示。此过程中开始把交点参数置为ui 0及u2 i。对每一窗口 边界计算出相应的p及q值，然后用函数CliPtest由参数p及q决定此直线能否彼排除或者 决定交点参数是否要调整。当p 0时，用参数r修改ui值：当p 0时，用参数r修改u2值。 如果最后的结果为 ui u2 ，那么排除此直线；否那么，只有当新的值使直线缩短时，才修改相

18、 应的参数u。当p 0且q 0时，可排除此直线，因为直线与边界平行且在边界之外。如果 四个p及q均被检查而直线被排除，那么被裁剪直线的端点可由ui及u2的值确定。LiangBarsky 裁剪算法代码Void Line_Clipping (xi,yi,x2,y2,rect)Float xi,yi,x2,y2,*rect;Float dx,dy,t0,ti;t0=0;ti=i;if (Clip Top(-dx,xi-rect->xw_xmin,&t0,&ti)if (Clip Top(dx,rect->xw_xmax-xi,&t0,&ti)dy=y2-y

19、i;if (Clip Top(-dy,yi-rect->yx_xmin,&t0,&ti)if (Clip Top(dy,rect->xw_xmax-yi,&t0,&ti)Line (int) (xi+t0*dx),(int) (yi+t0*dy)(int) (xi+ti*dx)(int) (yi+ti*dy); return;writeText(“pip2 完全不可见 )；Void Line_Clipping(q,d,*t0,*ti)float q,d,*t0,*ti;float r;if (r>ti)return(FALSE);else if (r>t0)tO=r;return (TRUE);else if (q>0)r=d/q;if (r<tO)return (FALSE);else if (r<t1)t1=r;return (TRUE);else if (d<0)return (FALSE);return (TRUE);5两种算法