直线裁剪算法研究

摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的基础上，针对Cohen-Sutherland算法和Liang-Barsky算法进行了分析研究。并对两种算法了计算直线与窗口边界的交点时，进行了有效有比较。

关键词：裁剪；算法；Cohen-Sutherland；Liang－Barsky；

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 cohen－sutherland直线裁剪算法

Cohen-Sutherland算法的大意是：对于每条线段P1P2，分为3种情况处理。

①若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之。 ②若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。

③若线段既不满足“取”的条件，也不满足“弃”的条件，则把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

1．区域码及其建立

Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右。区域码从右到左的各位所代表的坐标区如下所示：

位 4 3 2 1 坐标区 上 下 右 左

上述各位中某位为1，则表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见，位于窗中内的点，其区域码应为0000，位于窗口左下方的点，其区域码应为0101，其余类推。

区域码各位的值可以通过对端点坐标（x，y）与窗口边界的比较求得。如果x①计算出端点坐标与窗口边界的差。

②按计算出的各个差的符号把区域码的相应位置为0或1，即 区域码的第一位置为（x－xwmin）的符号位； 区域码的第二位置为（xwmin-x）的符号位；

区域码的第三位置为（y-ywmin）的符号位； 区域码的第四位置为（ywmin-y）的符号位。 2．区域码裁剪算法

对所有直线的端点都建立了区域码之后，就可按区域码判断直线在窗口之内或窗口之外。这可分为如下几种情况：

①若一直线的两个端点的区域码均为0000则此直线在窗口边界之内，应子保留。

②若一直线的两个端点的区域码的同一位同时为1，则此直线全部在窗口边界之外，应子裁剪。例如，若一直线的一个端点的区域码为1001，另一个端点的区域码为0101，则此两端点的区域码的第一位均为1，说明此两端点均在窗口边界之左，因此，直线在窗口边界之外，应予裁剪。可用将直线两个端点的区域码进行与操作的方法，判断直线是否在窗口之外，若与操作的结果为0000则两端点的区域码任何位均不同时为1，此直线不一定被裁剪。

③以上两种情况之外的直线，有可能穿过窗口，也有可能不穿过窗口，如图87所示。图中所示的两条直线都不符合情况②的要求，但一条直线（P1P2）穿过窗口，另一直线（P3P4）不守过窗口。对这类直线可以进行如下处理：取窗口外的一个端点与窗口边界比较以确定可排除直线的哪一部分，然后，把直线剩下的部分与其他边界比较，这样一直到直线全部被排除或确定直线的哪一部分在窗口之内为止。可按“左、右、下、上”的次序建立检查直线端点与窗口边界关系的算法。

图2 区域码

下面介绍对图3所示的两条直线进行处理的过程。从直线P1P2的下端点P1开始，依次检查窗口的左、上、右及下边界，可发现此点在窗口之下（因为区域码的第三位为1）。然后求得直线与下边界的交点P1排除线段P1 P1这样直线就缩短为P1 P2。因为P2在边界之外，将此端点与各边界比较，可发现此端点在窗口上面。计算出交点P2线段P1P2保留下来。这样就完成了对这条线的处理并开始处理下一直线P3 P4。端点P3在窗口之左，可计算出交点P3讲裁剪掉线段P3P3。检查P3P4的区域码，可发现直线的这一剩余部分在窗口之下故也可排除。

由于窗口边界均平行于坐标轴，所以直线与窗口边界的交点可以用直线方程的各参数很方便地求出，对于一条端点坐标为x1,y1及x2,y2的直线，其与一垂直边界的交点的y坐标可以用下式计算：

yy1mxx1

这里互的取值可取x或xwmax，斜率m可用公式my2y1x2x1计算。同样地，与水平边界交点的x坐标可用下式计算：

xx1yy1m

这里y的值可取几ywmin或ywmax。

4 Liang－Barsky算法

Liang（梁友栋)-Barsky算法又称为参数方程法。首先写出端点x1,y1及x2,y2之间连线的参数方程如下：

xx1x2x1ux1xu yy1y2y1uy1yu

其中，xx2x1,yy2y1。参数u可取0 1之间的值，坐标x,y表示此范围内的u值定义的直线上的一个点。当u＝0时，x,yx1,y1，直线的另一端u＝0时，x,yx2,y2。

我们发现，如果直线上的某点处于x,y及xwmin,ywmin及xwmax,ywmax所定义的窗口之内，则满足以下条：

xwmin≤x1xu≤xwmax ywmin≤y1yu≤ywmax

这四个不等式可以表示为：

upk≤qk， k=1,2,3,4

其中，参数p,q定义为；

p1x, q1x1xwmin p2x, q2xwmaxx1

p3y, q3y1ywmin p4y, q4ywmaxy1

按照直线与窗口边界的相对位置，可分为以下几种倩况。

①任何一条与窗口边界平行的直线，其pk0，此处k值表示取哪一个边界（k=1,2,3及4，分

别相应于左、右、下及上边界）。如果对某一k值，还满足qk0，则此直线完全在边界外，可不进一步考虑；如果qk≥0，则此与边界平行的直线在边界内。

②如果qk0，则情况较复杂。此时，可把直线按从x1,y1到x2,y2连线方向作为正向，将此直线无限延伸，同时把各窗口边界也无限延伸（见图3）；然后分以下两种情况讨论：

a当qk0时，则是由窗口外发出的一条直线的无限延伸线进入相应窗口边界的无限延伸线的内部。

b当qk0时，情况相反。即直线的延伸线是由窗口边界延伸线的内部到外部。

以图3中的直线L1为例，说明以上两种情况。表1.1给出L1的延伸线相对于4个边界延伸线的方向及qk取值。

表1.1 直线方向与Pk取值 边界 左 右 下 上 图3 直线与窗口边界的相对

Pk取值 方向 由外到内 由内到外 由外到内 由内到外 交点 p1xx2x10 p2xx2x10 u1 p3yy2y10 p4yy2y10 u2 当qk0时，可以用下式计算出一参数u，此u值应于直线延伸线与窗口边界k的延伸线的交点：

uqkpk

对于每条直线，可计算出一对u值（u1及u2），由此两参数可判断直线是如何裁剪的。其中，u1的值可由从窗口边界外发出进人窗口边界之内的直线（Pk0）所涉及的窗口边界确定。对于这些窗口边界，可计算出各rkqkpk，取各rk中最大值即为回u1，u2可由自窗口边界内发出至窗口边界外的直线（Pk0）所涉及的窗口边界确定，同样可计算出这些窗口边界的rk值，取各rk中的最小值即为u2。如果u1u2，则此直线全部在窗口外而可排除：否则，此直线在窗口内，可由u1及u2计算出彼裁剪直线的端点。图3中标出直线L1及L2相应于u1及u2的与边界的交点。L1的u2u1，则L1彼裁剪，并可由u1及u2计算出裁剪点；而L2的u1u2，则此直线全部彼排除。

此算法可用以下过程表示。此过程中开始把交点参数置为u10及u21。对每一窗口边界计算出相应的p及q值，然后用函数CliPtest由参数p及q决定此直线能否彼排除或者决定交点参数是否要调整。当p0时，用参数r修改u1值：当p0时，用参数r修改u2值。如果最后的结果为u1u2，则排除此直线；否则，只有当新的值使直线缩短时，才修改相应的参数u。当p0且q0时，可排除此直线，因为直线与边界平行且在边界之外。如果四个p及q均被检查而直线被排除，则被裁剪直线的端点可由u1及u2的值确定。

5 两种算法比较

Cohen-Sutherland直线裁剪算法与Liang－Barsky裁剪算法所需的各种运算的次数进行比较，列

表1.2如下：

表1.2计算交点时两种算法所需要的各种运算次数比较 Cohen-Sutherland Liang-Barsky 2 4 2 2 加法（次数） 减法（次数） 乘法（次数） 除法（次数） 4 4 6 2 由上表可知：在求被裁剪计算直线与窗口边界的交点交点时，Liang－Barsky算法的效率也高于Cohen-Sutherland算法。

6结论

区域码直线裁剪算法方法直观方便，速度较快，是一种较好的裁剪方法，但有两个问题还有待进一步解决。

(1)由于采用位逻辑乘的运算，这在有些高级语言中是不便进行的。

(2)全部舍弃的判断只适合于那些仅在窗口的线段,对于跨越3个区域的线段(如d线段),就不能一次作出判别面舍弃它们。

Liang－Barsky裁剪算法所需的计算量较小。每修改一次u1或u2只需要一次除法，在u1及u2。确定后，直线与窗口边界的交点只需计算一次，但该算法只能应用于矩形窗口的情形。而区域码方法要多次重复计算直线与窗口边界的交点，且每计算一次交点需要一次除法及一次乘法。

参考文献

[1] Donald Hearn.计算机图形学第三版[M].北京,电子工业出版社,2005 [2]孙家广,杨长贵.计算机图形学基础第三版[M].北京,清华大学出版社,2002 [3]杨钦,徐永安.计算机图形学[M].北京:清华大学出版社,2005

[4]孔德惠等.对cohen-sutherland线段裁剪算法的改进[J].北京工业大学学报,2002 [5]郭长友等.一种快速的二维线段裁减新算法[J].福建电脑,2006