直线裁剪算法研究Cohen-Sutherland算法和Liang-Barsky算法.doc

word直线裁剪算法研究摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的根底上，针对Cohen-Sutherland算法和Liang-Barsky算法进展了分析研究。并对两种算法了计算直线与窗口边界的交点时，进展了有效有比拟。关键词：裁剪；算法；Cohen-Sutherland；LiangBarsky；1引言直线是图形系统中使用最多的一个根本元素。所以对于直线段的裁剪算法是被研究最深入的一类算法，目前在矩形窗口的直线裁剪算法中，出现了许多有效的算法。其中比拟著名的有：Cohen-Sutherland算法、中点分割算法、Liang-Barsky算法、Sobkow-Pospisil-Yang算法，与Nicholl-Lee-Ncholl算法等。2直线裁剪的根本原理图1所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之如图1中P5到P6的直线，如此此直线应保存。如果一条直线的一个端点在窗口外如P9另一个点在窗口如P10，如此应从直线与边界的交点P9处裁剪掉边界之外的线段。如果直线的两个端点均在边界外，如此可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应保存P7到P8的线段，其余局部均裁剪掉。图1直线相对干窗口边界的栽剪直线裁剪算法应首先确定哪些直线全部保存或全部裁剪，剩下的即为局部裁剪的直线。对于局部裁剪的直线如此首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的局部裁剪掉。一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。3 cohensutherland直线裁剪算法Cohen-Sutherland算法的大意是：对于每条线段P1P2，分为3种情况处理。假如P1P2完全在窗口，如此显示该线段P1P2，简称“取之。假如P1P2明显在窗口外，如此丢弃该线段，简称“弃之。假如线段既不满足“取的条件，也不满足“弃的条件，如此把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。1区域码与其建立Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右。区域码从右到左的各位所代表的坐标区如下所示：位 4 3 2 1坐标区 上 下 右 左上述各位中某位为1，如此表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见，位于窗中的点，其区域码应为0000，位于窗口左下方的点，其区域码应为0101，其余类推。区域码各位的值可以通过对端点坐标x，y与窗口边界的比拟求得。如果x<xwmin，如此区域码的第一位为1，其余各位确实定与此相似。现在的计算机语言都可以进展位操作，因此，可以通过以下步骤建立区域码：计算出端点坐标与窗口边界的差。按计算出的各个差的符号把区域码的相应位置为0或1，即区域码的第一位置为xxwmin的符号位；区域码的第二位置为xwmin-x的符号位；图2 区域码区域码的第三位置为y-ywmin的符号位；区域码的第四位置为ywmin-y的符号位。2区域码裁剪算法 对所有直线的端点都建立了区域码之后，就可按区域码判断直线在窗口之或窗口之外。这可分为如下几种情况：假如一直线的两个端点的区域码均为0000如此此直线在窗口边界之，应子保存。假如一直线的两个端点的区域码的同一位同时为1，如此此直线全部在窗口边界之外，应子裁剪。例如，假如一直线的一个端点的区域码为1001，另一个端点的区域码为0101，如此此两端点的区域码的第一位均为1，说明此两端点均在窗口边界之左，因此，直线在窗口边界之外，应予裁剪。可用将直线两个端点的区域码进展与操作的方法，判断直线是否在窗口之外，假如与操作的结果为0000如此两端点的区域码任何位均不同时为1，此直线不一定被裁剪。以上两种情况之外的直线，有可能穿过窗口，也有可能不穿过窗口，如图87所示。图中所示的两条直线都不符合情况的要求，但一条直线P1P2穿过窗口，另一直线P3P4不守过窗口。对这类直线可以进展如下处理：取窗口外的一个端点与窗口边界比拟以确定可排除直线的哪一局部，然后，把直线剩下的局部与其他边界比拟，这样一直到直线全部被排除或确定直线的哪一局部在窗口之为止。可按“左、右、下、上的次序建立检查直线端点与窗口边界关系的算法。下面介绍对图3所示的两条直线进展处理的过程。从直线P1P2的下端点P1开始，依次检查窗口的左、上、右与下边界，可发现此点在窗口之下因为区域码的第三位为1。然后求得直线与下边界的交点P1排除线段P1P1这样直线就缩短为P1P2。因为P2在边界之外，将此端点与各边界比拟，可发现此端点在窗口上面。计算出交点P2线段P1P2保存下来。这样就完成了对这条线的处理并开始处理下一直线P3P4。端点P3在窗口之左，可计算出交点讲裁剪掉线段。检查的区域码，可发现直线的这一剩余局部在窗口之下故也可排除。由于窗口边界均平行于坐标轴，所以直线与窗口边界的交点可以用直线方程的各参数很方便地求出，对于一条端点坐标为与的直线，其与一垂直边界的交点的y坐标可以用下式计算：这里互的取值可取x或，斜率m可用公式计算。同样地，与水平边界交点的x坐标可用下式计算： 这里y的值可取几或。 下面是区域码直线裁剪算法的C语言描述，其中每个端点的区域码用4元素布尔数组表示。区域码直线裁剪算法代码Void Line_Clipping(x1,y1,x2,y2,xw_xmin,yw_ymin,xw_max,yw_max)float x1,y1,x2,y2,xw_xmin,yw_ymin,xw_max,xw_max,yw_max;/*和是线段端点坐标*/ Int draw,done; Int code1,code2,code;float x,y; Draw=FALSE; done=FALSE; code1=get_code(x1,y1,xw_xmin,yw_ymin,xw_max,yw_max);code2=get_code(x2,y2,xw_xmin,yw_ymin,xw_max,yw_max); while(! Done) if (code1= =0 && code= =2) draw=TRUE;done=TRUE; else if (code1 & code2 !=0) done=TRUE; else If (code1 !=0) code=code1; else code=code2; 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=get_codex1,y1,xw_xmin,yw_ymin,xw_max,yw_max; else x2=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) code|=BOTTOM; if (x>xw_xmax) code|=RIGHT; else if (x<xw_xmin) code|=LEFT; return code; 4 LiangBarsky算法Liang梁友栋)-Barsky算法又称为参数方程法。首先写出端点与之间连线的参数方程如下：其中，。参数u可取0 1之间的值，坐标表示此围的u值定义的直线上的一个点。当u0时，直线的另一端u0时，。我们发现，如果直线上的某点处于与与所定义的窗口之，如此满足以下条：这四个不等式可以表示为：， k=1,2,3,4其中，参数定义为；按照直线与窗口边界的相对位置，可分为以下几种倩况。任何一条与窗口边界平行的直线，其，此处值表示取哪一个边界=1,2,3与4，分别相应于左、右、下与上边界。如果对某一值，还满足，如此此直线完全在边界外，可不进一步考虑；如果0，如此此与边界平行的直线在边界。如果，如此情况较复杂。此时，可把直线按从到连线方向作为正向，将此直线无限延伸，同时把各窗口边界也无限延伸见图3；然后分以下两种情况讨论：a当时，如此是由窗口外发出的一条直线的无限延伸线进入相应窗口边界的无限延伸线的部。b当时，情况相反。即直线的延伸线是由窗口边界延伸线的部到外部。以图3中的直线为例，说明以上两图3 直线与窗口边界的相对位置种情况。表给出的延伸线相对于4个边界延伸线的方向与取值。表 直线方向与取值边界取值方向交点左由外到右由到外下由外到上由到外当时，可以用下式计算出一参数u，此u值应于直线延伸线与窗口边界k的延伸线的交点：对于每条直线，可计算出一对u值与，由此两参数可判断直线是如何裁剪的。其中，的值可由从窗口边界外发出进人窗口边界之的直线所涉与的窗口边界确定。对于这些窗口边界，可计算出各，取各中最大值即为回，可由自窗口边界发出至窗口边界外的直线所涉与的窗口边界确定，同样可计算出这些窗口边界的值，取各中的最小值即为。如果，如此此直线全部在窗口外而可排除：否如此，此直线在窗口，可由与计算出彼裁剪直线的端点。图3中标出直线与相应于与的与边界的交点。的，如此彼裁剪，并可由与计算出裁剪点；而的，如此此直线全部彼排除。此算法可用以下过程表示。此过程中开始把交点参数置为与。对每一窗口边界计算出相应的与值，然后用函数CliPtest由参数与决定此直线能否彼排除或者决定交点参数是否要调整。当时，用参数修改值：当时，用参数修改值。如果最后的结果为，如此排除此直线；否如此，只有当新的值使直线缩短时，才修改相应的参数。当，可排除此直线，因为直线与边界平行且在边界之外。如果四个与均被检查而直线被排除，如此被裁剪直线的端点可由与的值确定。LiangBarsky裁剪算法代码Void Line_Clipping (x1,y1,x2,y2,rect)Float x1,y1,x2,y2,*rect; Float dx,dy,t0,t1;t0=0;t1=1; if (Clip Top(-dx,x1-rect->xw_xmin,&t0,&t1) if (Clip Top(dx,rect->xw_xmax-x1,&t0,&t1)dy=y2-y1; if (Clip Top(-dy,y1-rect->yx_xmin,&t0,&t1) if (Clip Top(dy,rect->xw_xmax-y1,&t0,&t1) Line (int) (x1+t0*dx),(int) (y1+t0*dy) (int) (x1+t1*dx) (int) (y1+t1*dy);return; writeText(“p1p2完全不可见)； Void Line_Clipping(q,d,*t0,*t1) float q,d,*t0,*t1; float r;if (r>t1) return(FALSE); else if (r>t0) t0=r; return (TRUE); else if (q>0) r=d/q; if (r<t0) return (FALSE); else if (r<t1) t1=r; return (TRUE); else if (d<0)return (FALSE); return (TRUE);5两种算法比拟Cohen-Sutherland直线裁剪算法与LiangBarsky裁剪算法所需的各种运算的次数进展比拟，列表如下：加法次数减法次数乘法次数除法次数Cohen-Sutherland4462Liang-Barsky2422 由上表可知：在求被裁剪计算直线与窗口边界的交点交点时，LiangBarsky算法的效率也高于Cohen-Sutherland算法。6结论区域码直线裁剪算法方法直观方便，速度较快，是一种较好的裁剪方法，但有两个问题还有待进一步解决。(1)由于采用位逻辑乘的运算，这在有些高级语言中是不便进展的。 (2)全部舍弃的判断只适合于那些仅在窗口的线段,对于跨越3个区域的线段(如线段),就不能一次作出判别面舍弃它们。LiangBarsky裁剪算法所需的计算量较小。每修改一次或只需要一次除法，在与。确定后，直线与窗口边界的交点只需计算一次，但该算法只能应用于矩形窗口的情形。而区域码方法要屡次重复计算直线与窗口边界的交点，且每计算一次交点需要一次除法与一次乘法。参考文献1 Donald Hearn.计算机图形学第三版M.,电子工业,20052家广,长贵.计算机图形学根底第三版M.,清华大学,20023钦,徐永安.计算机图形学M.:清华大学,20054孔德惠等.对cohen-sutherland线段裁剪算法的改良J.工业大学学报,20025郭长友等.一种快速的二维线段裁减新算法J.电脑,20069 / 9