对cohen-sutherland线段裁剪算法的改进

《对cohen-sutherland线段裁剪算法的改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京工业大学学报Vol.28No.4粼20025CEX1244)1JOURNALOFBEUINGPOLYTECHNICUNIVERSITYDec.2002对Cohen-Sutherland线段裁剪算法的改进孔德慧，尹宝才，刘媛媛北京工业大学计算机学院，北京100022摘要:针对Cohen-Sutherland线段编码裁剪算法仅是孤立地处理被裁减线段两端点这一弊端，提出一种基于Cohen-Sutherland线段裁剪算法的改进算法，它充分利用线段的整体信息，构造出合理分割窗口的辅助线以对线段与窗口相对位置关系进行更精确的判断，避免

2、无效交点的计算，使线段与窗口交点的计算量降到最低水平提高裁剪的整体效率.该改进处理思路同样适用于其他的裁剪算法.关健词:计算机图形学‘裁剪算法;无效交点分类号:TP391文献标识码:A文童编号:0254一0037(2002)04一0483一04对线段进行裁剪是计算机图形学需要解决的最基本间题之一目前广泛使用的3种经典裁剪算法分别是梁友栋一Batsky参数裁剪算法、Ncholl-Lee-Ncholl多区域判别算法和Cohen-Sutherland编码裁剪算法「‘·‘].这些算法各有特色，在使用上几乎平分秋色.梁友栋一Batsky参

3、数裁剪算法t3】利用线段的参数表示形式.把被裁剪线段所在直线与矩形裁剪窗口边框线的交点坐标的计算简化为对交点对应的参数值的计算，再根据交点参数与被裁剪线段的参数定义区间比较的结果，确定出有效的交点，从而得到裁剪后应保留的部分线段.Nicholl-Lee-Ncholl多区域判别算法14]是在编码算法的基础上通过增加更多的区域测试来减少交点的计算次数的.作者首先分析Cohen-Surther编码裁剪算法，并在此基础上提出了改进方案，通过对最后裁减结果的分析，发现本算法与Cohen-Surther编码裁减算法和Ncholl-Lee-N

4、choll多区域判别算法相比，裁减效率得到了较大的提高.1Cohen-Sutherland裁剪算法分析应该说Cohen-Sutherland裁剪算法是上述3种算法中效率较低的一种裁剪算法.首先，利用矩形裁剪窗口的边框线把平面划分为9个不同的区域并进行编码(见图1).被裁剪线段的端点分别设为A和P2.判别两个端点所在的区域，并把相应区域的编码作为端点的编码，分别记为。1和C2然后，根据两端点编码及编码的按位与运算结果来判断被裁剪线段与窗口的位置关系:I)如果CAC2*O，则意味着两端点的编码至少有一位同为I，即两端点同时位于某边框

5、线的外侧，因此该线段被整体裁剪.2)如果C}AC2=0，若Cj=0且C2=0，表示该线段整体位于窗口内，应保留;否则被裁剪线段需与边框线求交，并在交点处分割线段进行取舍，直至满足以上的整体保留或舍弃条件.可见，该算法在裁减那些不与边框线相交的线段时，裁减效率较高;而对那些与窗口边界的延长线相交的线段进行裁减时，效率较低.在最坏的情况下(见图2)，被裁减线段与4条边框线计算交点，然而所得的裁减结果却可能是全部舍弃.不难发现，求交的运算量是裁剪算法中最主要的计算开销，无效交点的计算带来了较大的额外工作，从而大大降低了算法效率.所以，

6、如果可以对那些与边框线有交的线段再进行孺需鼻羹墓姜萎鑫纂瞥滁思{吸怨1-01);北京市科委基金资助项目(N07060‘一’‘作者简介孔德慧(1968-)，女，副教授;尹宝才(1963-)，男，教授，博士生导师.北京上业大学学报2002年精确的判断，剔除那些实际上落在窗口外的线段，同时准确地判别出有效交点产生的边界，避角洲‘交点，就可以最大限度地提高计算效率.1001’1000:1010000100100101-010010110图1山窗11边框线划分区域并编码图2被裁剪线段需与多条边框线求交2改进的编码裁剪算法设被裁剪线段PIP

7、,在以上编码测试中不符合整体裁剪条件，即两端点既没有同时落在窗口内部，也没有同时落在某边框线外侧.并假设线段P几的斜率满足k>O,k<0时的处理方法是完全类似的.图3显示出在上述前提条件下，线段与窗口边界的可能的裁剪关系.显然，在各种不同情形下，线段与窗Ll边界的有效交点可以是0个(如图中线段AB所示),1个(如图中线段cn所示)或2个(如图中线段EF所q;).为方便起见按照匕下、左、右的顺序把裁剪窗L]的4条边框线的方程分别表示为:1'=Y-!'=)'_"一‘一rmm"S一x-1‘窗[11的左上、左下、右上、右下角点分别记为P

8、'r"PL.,PVT,Pn.为避免计算无效交点，将引人若干辅助线以精确判别交点出现情形.分别过角点Prr,P-，以k为斜率定义两条辅助线l"h(如图4所ITO显然，若被裁剪线段位于两条辅助线之问，则线段与窗口边界有至少一个的有效交点，否则与窗口边界无交点.具体实