基于两端点区域分布的线裁剪新算法

任洪海(大连交通大学软件学院，辽宁大连116052)*

基于两端点区域分布的线裁剪新算法

任洪海
(大连交通大学软件学院，辽宁大连116052)*

在确定线段完全在窗口内或某边界外初始判断后将两端点的区域分布分成6种情况进行处理.除可直接确定相交关系的情况外，一般过指定顶点在窗外作与对应边呈45度的辅助边界进一步排除完全在窗外的线段，再通过线段与指定边界相交测试确定线段与窗口的位置关系.该方法可以加快线段与窗口的求交进程，有效减少不必要的求交运算和辅助操作，显著提高裁剪效率.

计算机应用;线裁剪;两端点区域分布

0 引言

线裁剪作为计算机图形学基础理论的重要内容之一，经典的算法主要有以区域码为代表的Cohen-Sutherland算法、中点分割算法、参数化的梁-Barsky算法以及Nicholl-Lee-Nicholl算法［1］.文献［2］将线段两端点独立考虑，并将其区域分布分成边域和角域两种基本情况，并根据线段相交对应边界的情况确定线段与窗口的相交关系.近年来也有一些算法将原窗口扩大并旋转45°形成新窗口用来舍弃不与窗口相交的线段［3-4］，但存在冗余边界测试.

本文通过线段完全在窗口之内或某边界之外的初始判断后，将线段两端点相对于窗口边界所划分区域的分布分成5种情况进行处理.在必要情况下过指定窗口顶点作辅助边界排除不与窗口相交的线段，再根据线段相交于指定边界的范围快速确定线段与窗口的相交情况.减少不必要的辅助操作和求交运算，显著提高裁剪效率.

1 区域对应关系及辅助边界

1.1窗口边界划分区域及对应关系

如图1所示，作为矩形裁剪窗口的四条边分别标记为L边、R边、B边、T边.将每条边延长成直线形成对应边界，分别为L边界( x = xwmin)、R边界( x = xwmax)、B边界( y = ywmin)、T边界( y = ywmax).四条边界将平面分成九个区域，根据区域位置及符号标识，区域对应关系如下:

边区与一条边界相对应;而角区和两条垂直相交的边界相对应.例如，T边区与T边界相对应; LB角区与L边界、B边界相对应.窗口顶点是由两条边界垂直相交而成，一条边界可称另一边界对应顶点相关边界.例如，L边界与B边界相交而成顶点VLB，L边界称B边界为顶点VLB相关边界.根据边界所属，一角区与一顶点相对应，两斜对边区与一顶点相对应.例如，LB角区对应顶点VLB，R边区与T边区对应顶点VRT.

图1 裁剪窗口边界区域划分

对应边界相平行的两边区称为对边区.例如，T边区和B边区为对边区，L边区和R边区为对边区.对应边界相垂直的两边区称为斜边区.例如，T边区是L边区的斜边区，T边区是R边区的斜边区.

不同时在任何边界之外的角区和边区称为斜对关系，每个边区都有两个斜对角区.例如，T边区有两个斜对角区，即LB角区和RB角区.

不同时在任何边界之外的两角区为对角区.四个角区中，LT角区和RB角区为对角区，RT角区和LB角区为对角区.

1.2辅助边界

在窗口外分别过指定顶点引与对应边界成45°的直线，定义为辅助边界.判断线段端点在此类辅助边界之外的条件为:

端点在过顶点VLT所引辅助边界之外的条件为: y－x + xwmin＞ywmax

端点在过顶点VLB所引辅助边界之外的条件为: x + y－ywmin＜xwmin

端点在过顶点VRB所引辅助边界之外的条件为: y－x + xwmax＜ywmin

端点在过顶点VRT所引辅助边界之外的条件为: x + y－ywmax＞xwmin

如果线段两端点同时在过任意一条此类边界之外，则线段在窗口之外，裁剪掉该线段.

本文根据线段两端点的区域分布完全可确定过哪个顶点作辅助边界进行测试，而不必同时检测四个辅助边界.

2 算法实现过程

通过线段两端点坐标与窗口四条边界坐标相比较确定两端点所在区域，并进行如下初始判断:

如果两端点都在四条边界之内，则线段在窗口之内，保留该线段;

如果两端点都在四条边界中任意一条的外侧，则线段在窗口之外，裁剪该线段.

通过两步初始判断后，所剩线段两端点的区域分布情况完全可概括成6类情况:①一端点在窗口内另一端点在边区;②一端点在窗口内另一端点在角区;③一端点在边区另一端点在其对边区;④一端点在边区另一端点在其斜对边区;⑤一端点在边区另一端点在其斜对角区;⑥一端点在角区另一端点在其对角区.

针对6种情况，分别具体处理如下:

对于情况①:可得线段只与边区对应边相交，窗口内端点到交点间线段为裁剪结果(如图2中线段a).

对于情况②:可得线段一定与两角区对应边之一相交(如图3中线段a和线段b).求线段与任一对应边界的交点，判断是否在其对应窗口边上:

如果交点在其对应窗口边上，则内端点到交点间线段为裁剪结果.

否则，线段一定与另一对应窗口边相交.求其交点，内端点到交点间线段为裁剪结果.

图2 窗口内-边区情况

图3 窗口内-角区情况

对于情况③:可得线段分别与两对应边相交，交点间线段为裁剪结果(如图4中线段a ).

对于情况④:可得线段或不与窗口相交或同时与两边区的对应边相交.过两边区对应边界相交而成的顶点作辅助边界，排除两端点都在此辅助边界之外的线段(如图5中线段a ) ;对于辅助边界无法排除的线段，指定两边区对应边界任意一个，判断线段是否相交在对应边上:

如果交点在对应边上，则线段一定与另一边也相交.求在另一边上的交点，交点间线段为裁剪结果(如图5中线段c和线段d ).

否则，线段不与窗口相交(如图5中线段b ).

图4 边区-对边区情况

图5 边区-斜边区情况

对于情况⑤:线段与窗口的位置关系有三种:①线段不与窗口相交;②线段与边区对应边及其垂直的角区对应边相交;③线段与边区对应边及其平行的角区对应边相交.

角区的两个对应边界中，一个与其斜对边区对应边界平行，另一个与其斜对边区对应边界垂直相交.取与斜对边区对应边界垂直相交的角区对应边界为指定边界，过边区对应边界与指定边界相交而成的顶点作辅助边界，排除两端点都在此辅助边界之外的线段后，判断线段与指定边界的相交范围完全可确定线段与窗口相交关系.如图6所示.

( 1)如果线段相交指定边界于边区对应边界之外，则线段不与窗口相交;

( 2)如果线段相交指定边界于对应窗口边上，则线段同时与边区对应边相交，两交点间线段为裁剪结果;

( 3)否则，线段与边区对应边及其对边相交，两交点间线段为裁剪结果.

图6 边区-斜对角区情况

图7 角区-对角区情况

对于情况⑥:此时，线段一定不同时与端点所在角区两对应边相交.因此，线段与窗口的位置关系有五种:①线段不与窗口相交;②相交于窗口两垂直方向对边;③相交于窗口两水平方向对边;④一个非端点所在角区两对应边;⑤另一个非端点所在角区两对应边.如图7所示.

便于描述，将端点所在角区对应顶点称为本顶点，而非端点所在角区对应顶点称为基顶点.过两基顶点分别作辅助边界，排除两端点同时在任意辅助边界之外的线段后.取任意两平行边界为两指定边界，通过判断线段与两指定边界的相交情况可确定线段与窗口的相交关系:

( 1)如果线段相交指定边界于其基顶点相关边界之外，则线段不与窗口相交;

( 2)如果线段相交指定边界对应边上且相交另一平行边界于其本顶点相关边界之外，则线段与指定边界对应边及其基顶点相关边界对应边相交，交点间线段为裁剪结果;

( 3)如果线段相交两指定边界对应边上，两对应边上交点间线段为裁剪结果;

( 4)如果线段同时相交两指定边界于本顶点相关边界之外，线段同时与两非指定边界对应边相交，交点间线段为裁剪结果.

3 算法分析与比较

本文根据端点的区域分布通过指定顶点在窗口之外作与对应边呈45°的辅助边界进一步排除不与窗口相交的线段，避免文献［4］中应用45°旋转窗口对应四条新边界测试过程中不必要的边界判断.

通过线段与边界的相交情况确定线段与窗口的相交关系是裁剪判断的有效途径.本文算法将线段两端点区域分布分成6种可能情况:情况①和情况③直接可确定线段与窗口的相交边，情况②、情况④和情况⑤通过判断线段相交一条指定边界范围可完全确定相交情况，情况⑥通过线段相交两条平行边界范围可完全确定相交情况，同时每个相交边界测试过程中都可以排除对应情况下不与窗口相交的线段.

同Cohe-Sutherland算法与文献［2］相比，本文算法能够根据线段两端点区域分布情况确定最佳相交检测边界，从而减少不必要的求交运算.例如排除图6中线段b，Cohen-Sutherland算法边界裁剪如果按照固定的左、右、下、上顺序需要左、右两边界裁剪后在下边界判断中才能将其排除.而文献［2］由于单独考虑两端点区域分布情况分别进行裁剪判断，同样增加了多余判断与边界求交.而本文算法在该边区-斜对角区端点分布情况中确定下边界为指定边界，通过判断线段与下边界一次相交情况就可排除线段b.

在同等硬件条件下，应用C ++编程实现CS算法、ELC算法［2］及本文算法，三个裁剪算法裁剪400万条随机线段所需的时间分别为3.529，3.274和2.418 s，从所用时间可以看出新算法的裁剪效率都高于现有的两个典型算法.

4 结论

本文在初始测试后将线段两端点区域分布分成5种情况分别进行判断并完成裁剪过程，只有在必要的情况，才通过指定顶点在窗口之外作与对应边呈45°的辅助边界进一步排除不与窗口相交的线段，并通过线段相交于指定边界的范围确定线段与窗口的相交关系.以最少的辅助操作和求交判断确定线段与窗口的位置关系，明显提高裁剪效率.

［1］DONALD HEARN，PAULINE BAKER M.Computer Graphics with OpenGL［M］.Third Edition，Upper Saddle River: Prentice Hall，2005: 315-340.

［2］汪灏泓，吴锐迅，蔡士杰.一种基于几何变换的高效的线裁剪新算法［J］.软件学报，1998，9( 10) : 728-733.

［3］陆国栋，吴煊晖.基于变窗口过滤技术的线段裁剪中点分割算法［J］.计算机辅助设计与图形学学报，2002，14( 6) : 513-517.

［4］朱亚臣，谭建荣，陆国栋，等.基于连续分区与串联编码的线段裁剪新算法［J］.中国图象图形学报，2007，12( 4) : 732-739.

A New Line Clipping Algorithm based on Region Distribution of Two Endpoints

REN Honghai
( Software Institute，Dalian Jiaotong University，Dalian 116052，China)

The region distribution of two endpoints is divided into six kinds of cases for processing after the initial testing to determine whether a line segment is completely inside the clipping window or outside some window boundary.Except for the case that the intersection relation is determined directly，the line segments outside window is further eliminated through the 45°auxiliary boundary passing the specified vertex，and the position of a line segment in relation to window is determined by the intersection test between a line segment and the specified boundary.The new algorithm can quickly calculate the intersections between a line segment and window，avoid the unnecessary intersection calculation and auxiliary operation，and further improve the clipping efficiency.

computer applications; line clipping;region distribution of two endpoints

A

1673-9590( 2016) 01-0105-04

2015-04-07

任洪海( 1977－)，男，讲师，硕士，主要从事计算机图形学教学与研究

E-mail: honghai_ren@126.com.