Cohen-Sutherland直线剪裁算法改进

摘要

对直线段进行裁剪是计算机图形学需要解决的最基本问题之一,直线段的裁剪速度直接影响到整个图形的裁剪效率.Cohen-Sutherland直线段裁剪算法因分类的不彻底和计算了直线与窗口边延长线上的交点而降低了算法的效率.提出了一种改进Cohen-Sutherland裁剪算法,其基本思想是根据裁剪窗口顶点与直线的位置关系对直线的分类条件进行改进,引入一条从待剪裁直线的端点距窗口最近顶点的辅助线,计算出引入的辅助线与待裁剪直线的夹角,根据夹角的大小,判断出直线究竟与窗口的哪条边相交,从而使求交点次数降低为最高2次.改进后的算法不仅思想简单直观、易实现、效率高,而且对图形裁剪算法的理论研究与应用均有很高的价值.%Line segment clipping is one of the most basic problems to be solved in computer graphics,and the clipping speed directly affects the clipping efficiency of the whole graph.Cohen-Sutherland line segment clipping algorithm has lower efficiency because line segment classification is not complete and the intersection points are still calculated between straight line and the window extension edge.A modified Cohen-Sutherland line clipping algorithm based on linear angle calculation has been proposed.It is the idea that the line classification conditions can be improved using sign relations of four windows vertex and line,then if an auxiliary line from the end of the line to be cut to the nearest vertex of the window is made,the angle between an auxiliary line and a line to be cut can be calculated,and the intersecting window edge is determined according to the sign of angle.This method reduces the number of intersection.The modified algorithm not only simple and intuitive,easy to implement and of high efficiency,but also valuable for theory research and application of clipping technology.