基于窗口与线段双重几何变换的线段裁剪新算法  

A New Line Clipping Algorithm Based on Window and Line Geometry Transformation

作　　者：商明清[1] 陆国栋[1] 谭建荣[1] 

机构地区：[1]浙江大学CAD&CG国家重点实验室,杭州310027

出　　处：《计算机工程与应用》2003年第20期71-73,121,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助(编号:50106014)

摘　　要：鉴于裁剪算法中求交的时间复杂性和求交的技术必要性,如何尽快舍弃与窗口根本不相交的冗余线段成为提高裁剪效率的关键。鉴于传统编码技术取舍线段的高效性,引入一次编码技术;针对一次编码技术的局限性,文章首次提出窗口几何变换的概念,并引入二次编码技术,通过广义窗口高效舍弃冗余线段,尽量避免求交运算;后续流程引入线段几何变换技术实施裁剪,尽可能加快求交进程。窗口变换与线段变换集成的双重变换技术,将线段重新划分为六类,分别采取高效的处理策略,算法实现表明裁剪算法效率显著提高。该文算法具有一定的理论意义和普遍的应用意义。Because intersection calculation is very necessary but huge time consuming in clipping algorithm,it becomes the key to improve clipping efficiency that abandon those lines without intersecting with clipping window as soon as possible.The technique of first encoding is introduced,because the traditional encoding technique is higher efficient when rejecting totally invisible lines and accepting totally visible lines.In order to avoid the weakness of first encoding,a new concept of window geometry transformation is proposed for the first time ,and the technique of second encoding is been put forward.The intersection calculation is avoided as much as possible through second encoding of generalized window,and part of redundant lines is abandoned.In order to enhance clipping velocity as much as possible,the technique of line geometric transformation is imported to later flow of the new algorithm.The lines are divided into six kinds in the technique of double transformation which including window transformation and line transformation,and six kinds of high-er efficient tactics are put forward.Example testing shows that the new algorithm is better than well known algorithms.The new algorithm has general applied value as well as theoretic value.

关 键 词：线段裁剪 窗口几何变换 线段几何变换 广义窗口 编码技术 冗余线段 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]