对Cohen—Sutherland线段裁剪算法的改进.PDF

带：8卷第4期 北京工业大学学报 Vd28N04 3002年12月 JOURNALoFBEUINGPOLy丁ECHNICUNIVERSJTy Dec2002 孔德慧，尹宝才，刘媛媛 (北京工业大学计算机学院，北京100022) 摘要：针对cohen_sumerland线段编码裁剪算法仅是孤立地处理被裁减线段哺端点这一弊端，提出一种基于 cohen_sutIle订and线段裁剪算法的改进算法，它充分利用线段的整体信息，构造出合理分割窗口的辅助线以对线 段与窗口相对位置关系进行更精确的判断，避免无效交点的计算，使线段与窗口交点的计算量降到最低水平．提 高裁剪的整体效率．该改进处理思路同样适用于其他的裁剪算法． 关键词：计算机图形学；裁剪算法；无效交点 分类号：TP391 文献标识码：A 0483一04 文章编号2002)04 对线段进行裁剪是计算机图形学需要解决的最基本问题之一．目前广泛使用的3种经典裁剪算法分 法”“1．这些算法各有特色，在使用上几乎平分秋色．梁友栋一Barsky参数裁剪算法…利用线段的参数表 示形式，把被裁剪线段所在直线与矩形裁剪窗口边框线的交点坐标的计算简化为对交点对应的参数值的 计算，再根据交点参数与被裁剪线段的参数定义区间比较的结果，确定出有效的交点，从而得到裁剪后应 试来减少交点的计算次数的．作者首先分析Cohersumler编码裁剪算法，并在此基础上提出了改进方 案，通过对最后裁减结果的分析，发现本算法与Cohen-Sunher编码裁减算法和Nich01卜kPNich011多区 域判别算法相比，裁减效率得到了较大的提高． 1 Cohen—sutherland裁剪算法分析 应该说cohen-sutherlaIld裁剪算法是上述3种算法中效率较低的一种裁剪算法． 首先，利用矩形裁剪窗口的边框线把平面划分为9个不同的区域并进行编码(见图1)．被裁剪线段的 端点分别设为尸1和尸2．判别两个端点所在的区域，并把相应区域的编码作为端点的编码，分别记为c。 和(2t然后，根据两端点编码及编码的按位与运算结果来判断被裁剪线段与窗口的位置关系： 1)如果ct^c：≠O，则意味着两端点的编码至少有一位同为1，即两端点同时位于某边框线的外侧，因 此该线段被整体裁剪． 线求交，并在交点处分割线段进行取舍，直至满足以上的整体保留或舍弃条件． 可见，该算法在裁减那些不与边框线相交的线段时，裁减效率较高；而对那些与窗口边界的延长线相 交的线段进行裁减时，效率较低．在最坏的情况下(见图2)，被裁减线段与4条边框线计算交点，然而所得 的裁减结果却可能是全部舍弃．不难发现，求交的运算量是裁剪算法中最主要的计算开销，无效交点的计 算带来了较大的额外工作，从而大大降低了算法效率．所以，如果可以对那些与边框线有交的线段再进行 收稿日期：2002．04．12． 基金项目：北京市自然科学基金资助项目(D070601_01)；北京市科委基金资助项目(N0706叭_o” 砒京市教委基金资助项目(P07070l_01)． 作者简介：孔德慧(1968)。女，副教授；尹宝才(1963一)，男，教授，博士生导师． 万方数据 精确的判断，剔除那些实际上落在窗口外的线段，同时准确地判别出有效交点产生的边界，避舒 交点，就可以最大限度地提高计算效率． IOO 1000 1010 n-1_ 一_}●● 000厂：：丌0010 J．．．．．．．．．．．．．．．J I冬11 }lI窗【】边框线划分区域并编码 图2被裁剪线段需与多条边框线求交 2 改进的编码裁剪算法 没被裁剪线段尸．只在以上编码测试中不符合整体裁剪条件，即两端点既没有同时落在窗口内部，也没 有同时落在某边框线外侧．并假设线段尸，只的斜率满足≈≥0，＆O时的处理方法足完全类似的． 图3硅示出在上述的提条件下，线段与