文档介绍：华北电力大学
课程论文
|
|
论文题目直线裁剪算法研究
课程名称计算机图形学
|
|
专业班级:软件11K1 学生姓名:张振兴
学号:1********** 成绩:
直线裁剪算法研究
摘要:直线裁剪是计算机图形学中的一个重要技术,在对常见的直经线裁剪的算法分析的基础上,针对Cohen-Sutherland算法和Liang-Barsky算法进行了分析研究。并对两种算法了计算直线与窗口边界的交点时,进行了有效有比较。
关键词:裁剪;算法;Cohen-Sutherland;Liang-Barsky;
引言
直线是图形系统中使用最多的一个基本元素。所以对于直线段的裁剪算法是被研究最深入的一类算法,目前在矩形窗口的直线裁剪算法中,出现了许多有效的算法。其中比较著名的有:Cohen-Sutherland算法、中点分割算法、Liang-Barsky算法、Sobkow-Pospisil-Yang算法,及Nicholl-Lee-Ncholl算法等。
1、直线裁剪的基本原理
图1所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之内确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之内(如图1中P5到P6的直线),则此直线应保留。如果一条直线的一个端点在窗口外(如P9)另一个点在窗口内(如P10),则应从直线与边界的交点(P9处裁剪掉边界之外的线段。如果直线的两个端点均在边界外,则可分为两种情况:一种情况是该直线全部在窗口之外;另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况,应全部裁剪掉;从P7到P8的直线属于后一种情况,应保留P7到P8的线段,其余部分均裁剪掉。
图1直线相对干窗口边界的栽剪
直线裁剪算法应首先确定哪些直线全部保留或全部裁剪,剩下的即为部分裁剪的直线。对于部分裁剪的直线则首先要求出这些直线与窗口边界的交点,把从交点开始在边界外的部分裁剪掉。一个复杂的画面中可能包含有几千条直线,为了提高算法效率,加快裁剪速度,应当采用计算量较小的算法求直线与窗口边界的交点。
2、两种重要的算法
2、1 cohen-sutherland直线裁剪算法
Cohen-Sutherland算法的大意是:对于每条线段P1P2,分为3种情况处理。
①若P1P2完全在窗口内,则显示该线段P1P2,简称“取”之。
②若P1P2明显在窗口外,则丢弃该线段,简称“弃”之。
③若线段既不满足“取”的条件,也不满足“弃”的条件,则把线段分为两段。其中一段完全在窗口外,可弃之。然后对另一段重复上述处理。
Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码,即区域码的4位分别代表端点位于窗口的上、下、左、右。区域码从右到左的各位所代表的坐标区如下所示:
位 4 3 2 1
坐标区上下右左
上述各位中某位为1,则表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见,位于窗中内的点,其区域码应为0000,位于窗口左下方的点,其区域码应为0101,其余类推。
区域码各位的值可以通过对端点坐标(x,y)与窗口边界的比较求得。如果x