计算机图形学第五章.ppt
《计算机图形学第五章.ppt》由会员分享,可在线阅读,更多相关《计算机图形学第五章.ppt(58页珍藏版)》请在课桌文档上搜索。
1、第五章 裁剪,在进行图形的描述中总是尽可能全面地获取它的有关信息,而在进行图形显示与研究过程中往往对其中某些部分更感兴趣和需要,这就涉及到图形裁剪概念与内容。本章我们将讨论图形系统中重要的部分裁剪,研究有关裁剪的算法。,第五章 裁剪,教学学时:6课时教学目的与要求:让学生初步了解裁剪的定义,掌握对直线段裁剪的一些基本算法,掌握简单的对多边形裁剪的算法,掌握算法的理论原理,能够分析基本算法的优缺点。教学重点:Cohen-Sutherland算法,中点分割算法,梁友栋Barsky算法,参数化算法,Sutlerland_Hodgman算法。,第五章 裁剪,5.1 裁剪概述5.2 二维裁剪5.2.1
2、直线段裁剪5.2.2 多边形裁剪,5.1 裁剪概述,在使用计算机处理图形信息时,遇到的情况往往是计算机内部存储的图形比较大,而屏幕显示只是图的一部分。例如,虽然计算机内部可以存储全国地图,但是,如果把全国地图整幅显示在屏幕上,则不能看到各地局部的细节。这时,可以使用缩放技术,把地图中的局部区域放大显示。在放大显示一幅图形的一部分区域时,必须确定图形中哪些部分落在显示区之内,哪些部分落在显示区之外,以便显示落在显示区内的那部分图形。这个选择处理过程称为裁剪。在进行裁剪时,画面中对应于屏幕显示的那部分区域称为窗口。一般把窗口定义为矩形,由上、下、左、右四条边围成。裁剪的实质就是决定图形中哪些点、线
3、段、文字以及多边形在窗口之内。,裁剪可以在世界坐标系中进行,即相对于窗口进行;也可以把对象变换为设备坐标之后相对于视区进行。前者可以把不在窗口范围内的部分剪掉,避免了不必要的变换处理;后者在设备坐标系中裁剪易于用硬件实现。裁剪处理的基础是:点在窗口区域内外的判断以及计算图形元素与窗口区域边界的交点。其原理虽然简单,但涉及的图形元素多,提高裁剪速度是算法应考虑的重要问题。以下介绍直线段裁剪算法及多边形裁剪算法。,最简单的裁剪方法是把各种图形扫描转换为点之后,再判断各点是否在窗内。但那样太费时,一般不可取。这是因为有些图形组成部分全部在窗口外,可以完全排除,不必进行扫描转换。所以一般采用先裁剪再扫
4、描转换的方法。,裁剪算法有二维的和三维的,裁剪对象也可以是规则形体,也可以是不规则形体。本章重点介绍二维裁剪,三维裁剪涉及到后面章节三维消隐等内容,后面再简要介绍。,5.2 二维裁剪,5.2.1 直线段裁剪直接求交算法Cohen-Sutherland算法中点分割算法Liang-Barskey算法参数化裁剪算法5.2.2 多边形裁剪Sutlerland_Hodgman算法 Weiler-Athenton算法,5.2 二维裁剪,直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似,从而裁剪问题也可以化为直线段的裁剪问题。所以本章重点讨论直线段的裁剪算法。算法一般取的裁剪多边形都是矩形
5、,有些特殊的算法采用任意多边形裁剪。,5.2.1 直线段裁剪,点的裁剪,图形裁剪中最基本的问题。假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT),对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式:xL=x=xR并且yB=y=yT否则,P点就在窗口外。,直线段裁剪,裁剪线段与窗口的关系:(1)线段完全可见;(2)显然不可见;(3)其它提高裁剪效率:快速判断情形(1)(2),对于情形(3),设法减少求交次数和每次求交时所需的计算量。,直接求交算法,直线与窗口边都写成参数形式,求参数值。,Cohen-Sutherland裁剪,基本思想:对于每条线段P1P2分为三种情况处
6、理:(1)若P1P2完全在窗口内,则显示该线段P1P2。(2)若P1P2明显在窗口外,则丢弃该线段。(3)若线段不满足(1)或(2)的条件,则在交点处把线段分为两段。其中一段完全在窗口外,可弃之。然后对另一段重复上述处理。为快速判断,采用如下编码方法:,图 5.1 区域划分及编码,图 5.2 区位码各位含义,编码的思想在图形学中非常重要。Sutherland:Coons,图灵,IEEE 计算机先驱奖。,Cohen-Sutherland算法,一旦给定所有的线段端点的区域码,就可以快速判断哪条直线完全在剪取窗口内,哪条直线完全在窗口外。所以得到一个规律:,Cohen-Sutherland裁剪,若P
7、1P2完全在窗口内code1=0,且code2=0,则“取”若P1P2明显在窗口外code1&code20,则“弃”在交点处把线段分为两段。其中一段完全在窗口外,可弃之。然后对另一段重复上述处理。,Cohen-Sutherland直线裁剪算法小结,本算法的优点在于简单,易于实现。他可以简单的描述为将直线在窗口左边的部分删去,按左,右,下,上的顺序依次进行,处理之后,剩余部分就是可见的了。在这个算法中求交点是很重要的,他决定了算法的速度。另外,本算法对于其他形状的窗口未必同样有效。特点:用编码方法可快速判断线段的完全可见和显然不可见。,中点分割裁剪算法,中点分割裁剪算法是对Cohen-Suthe
8、rland直线段裁剪算法的改进。在Cohen-Sutherland 直线段裁剪算法中,为了避免求直线段与窗口边界的交点,用不断对分线段的方法排斥线段在窗口外的部分,最后求出离线段端点最远的可见点(所谓可见点就是线段落在窗口内的点),若这两点存在,则这两点就是线段P1P2的可见线段端点。,中点分割裁剪算法,基本思想:与前一种Cohen-Sutherland算法一样首先对线段端点进行编码,并把线段与窗口的关系分为三种情况:全部可见、完全不可见和线段部分可见。对前两种情况,进行一样的处理。对于第三种情况,用中点分割的方法求出线段与窗口的交点。,问:算法为什么可行?会不会无限循环、不断二分?因为屏幕像
9、素是有限的,一般计算次数不会太多,而且算法思想是用取中点的方法最后在误差允许的范围内去逼近真正的与裁剪矩形边的交点。,下面我们仅介绍如何在线段P1P2上求离P1最远的可见点(求P2最远的可见点同p1),其具体步骤如下:测试P2是否在窗口内,若是,则P2就是离P1最远的可见点,结束。否则,进行下一步。测试P1P2是否在窗外同侧,若是,P1P2全部不可见,结束。否则,进行下一步。取P1P2的中点Pm,若PmP2在窗外同侧,舍去,剩余段以P2代替Pm重复第二步。否则,以P1代替Pm重复第二步。直到线段不能再分为止。,图中,对线段a,求离P1最远的可见点算法在第一步结束;对线段b,算法在第二步结束;对
10、线段c,算法进入第三步后开始对分线段,最终重复第二步结束。,中点分割裁剪算法的优点,取中点的目的是用中点逼近线段与边界的交点。这种方法没有求交计算,适合于没有乘除运算的计算机,易于用硬件实现。,Liang-Barsky算法,*写入图形学教科书的唯一中国人的算 法*Communication of ACM的论文梁有栋教授(浙江大学数学系教授)的二三事Liang-Barsky算法几何连续理论从几何学与纤维缠绕理论到基因工程,设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点,见图。算法是从A,B和P0三点中找出最靠近的P1点,图中要找的点是P0。从C,D和P1中找出最靠近P0的点。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 图形学 第五
链接地址:https://www.desk33.com/p-620001.html