计算机图形学第五章

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 裁剪,在进行图形的描述中总是尽可能全面地获取它的有关信息，而在进行图形显示与研究过程中往往对其中某些部分更感兴趣和需要，这就涉及到图形裁剪概念与内容。,本章我们将讨论图形系统中重要的部分,裁剪，研究有关裁剪的算法。,第五章 裁剪,教学学时,：,6,课时,教学目的与要求,：,让学生初步了解裁剪的定义，掌握对直线段裁剪的一些基本算法，掌握简单的对多边形裁剪的算法，掌握算法的理论原理，能够分析基本算法的优缺点。,教学重点：,Cohen-Sutherland,算法，中点分割算法，梁友栋,Barsky,算法，参数化算法，,Sutlerland_Hodgman,算法。,第五章 裁剪,5.1,裁剪概述,5.2,二维裁剪,5.2.1,直线段裁剪,5.2.2,多边形裁剪,5.1,裁剪概述,在使用计算机处理图形信息时，遇到的情况往往是计算机内部存储的图形比较大，而屏幕显示只是图的一部分。例如，虽然计算机内部可以存储全国地图，但是，如果把全国地图整幅显示在屏幕上，则不能看到各地局部的细节。这时，可以使用缩放技术，把地图中的局部区域放大显示。在放大显示一幅图形的一部分区域时，必须确定图形中哪些部分落在显示区之内，哪些部分落在显示区之外，以便显示落在显示区内的那部分图形。这个选择处理过程称为裁剪。在进行裁剪时，画面中对应于屏幕显示的那部分区域称为窗口。一般把窗口定义为矩形，由上、下、左、 右四条边围成。裁剪的实质就是决定图形中,哪些点、线段、文字以及多边形在窗口之内。,裁剪可以在世界坐标系中进行，即相对于窗口进行；也可以把对象变换为设备坐标之后相对于视区进行。前者可以把不在窗口范围内的部分剪掉， 避免了不必要的变换处理；后者在设备坐标系中裁剪易于用硬件实现。,裁剪处理的基础是：点在窗口区域内外的判断以及计算图形元素与窗口区域边界的交点。其原理虽然简单，但涉及的图形元素多， 提高裁剪速度是算法应考虑的重要问题。以下,介绍直线段裁剪算法及多边形裁剪算法。,最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。,裁剪算法有二维的和三维的，裁剪对象也可以是规则形体，也可以是不规则形体。本章重点介绍二维裁剪，三维裁剪涉及到后面章节三维消隐等内容，后面再简要介绍。,5.2,二维裁剪,5.2.1,直线段裁剪,直接求交算法,Cohen-Sutherland,算法,中点分割算法,Liang-Barskey,算法,参数化裁剪算法,5.2.2,多边形裁剪,Sutlerland_Hodgman,算法,Weiler-Athenton,算法,5.2,二维裁剪,直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。所以本章重点讨论直线段的裁剪算法。算法一般取的裁剪多边形都是矩形，有些特殊的算法采用任意多边形裁剪。,5.2.1,直线段裁剪,点的裁剪,图形裁剪中最基本的问题。,假设窗口的左下角坐标为,(,x,L,y,B,),右上角坐标为,(,x,R,y,T,),，,对于给定点,P(x,y),则,P,点在窗口内的条件是要满足下列不等式：,x,L,= x =,x,R,并且,y,B,= y =,y,T,否则，,P,点就在窗口外。,(,x,L,y,B,),(,x,R,y,T,),直线段裁剪,裁剪线段与窗口的关系：,(1),线段完全可见；,(2),显然不可见；,(3),其它,提高裁剪效率：,快速判断情形,(1)(2),，,对于情形,(3),，设法减,少求交次数和每次求,交时所需的计算量。,直接求交算法,直线与窗口边都,写成参数形式，,求参数值。,Cohen-Sutherland,裁剪,基本思想：,对于每条线段,P,1,P,2,分为三种情况处理,:,（,1,）若,P,1,P,2,完全在窗口内，则显示该线段,P,1,P,2,。,（,2,）,若,P,1,P,2,明显在窗口外，则丢弃该线段。,（,3,）若线段不满足（,1,）或（,2,）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,为快速判断，采用如下编码方法：,图,5.1,区域划分及编码,图,5.2,区位码各位含义,编码的思想在图形学中非常重要。,Sutherland,：,Coons,图灵, IEEE,计算机先驱奖。,Cohen-Sutherland,算法,一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：,Cohen-Sutherland,裁剪,若,P,1,P,2,完全在窗口内,code1=0,且,code2=0,则“取”,若,P,1,P,2,明显在窗口外,code1&code20,，,则“弃”,在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,Cohen-Sutherland,直线裁剪算法小结,本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的,速度,。另外，本算法对于其他形状的窗口未必同样有效。,特点：用编码方法可快速判断线段的完全可见和显然不可见。,中点分割裁剪算法,中点分割裁剪算法是对,Cohen-Sutherland,直线段裁剪算法的改进。 在,Cohen-Sutherland,直线段裁剪算法中,为了避免求直线段与窗口边界的交点,用不断对分线段的方法排斥线段在窗口外的部分,最后求出离线段端点最远的可见点,(,所谓可见点就是线段落在窗口内的点,),若这两点存在,则这两点就是线段,P,1,P,2,的可见线段端点。,中点分割裁剪算法,基本思想：,与前一种,Cohen-Sutherland,算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况,:,全部可见、完全不可见和线段部分可见。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。,问：算法为什么可行？会不会无限循环、不断二分？,因为屏幕像素是有限的，一般计算次数不会太多，而且算法思想是用取中点的方法最后在误差允许的范围内去逼近真正的与裁剪矩形边的交点。,下面我们仅介绍如何在线段,P,1,P,2,上求离,P,1,最远的可见点,(,求,P,2,最远的可见点同,p,1,) ,其具体步骤如下：, 测试,P,2,是否在窗口内，若是，则,P,2,就是离,P,1,最远的可见点，结束。否则，进行下一步。, 测试,P,1,P,2,是否在窗外同侧，若是，,P,1,P,2,全部不可见，结束。否则，进行下一步。, 取,P,1,P,2,的中点,P,m,，若,P,m,P,2,在窗外同侧，舍去，剩余段以,P,2,代替,P,m,重复第二步。否则，以,P,1,代替,P,m,重复第二步。直到线段不能再分为止。,图中,对线段,a,求离,P,1,最远的可见点算法在第一步结束,;,对线段,b,算法在第二步结束,;,对线段,c,算法进入第三步后开始对分线段,最终重复第二步结束。,中点分割裁剪算法的优点,取中点的目的是用中点逼近线段与边界的交点。这种方法没有求交计算，适合于没有乘除运算的计算机，易于用硬件实现,。,Liang,-Barsky,算法,* 写入图形学教科书的唯一中国人的算 法,*,Communication of ACM,的论文,梁有栋,教授,(,浙江大学数学系教授,),的二三事,Liang-Barsky,算法,几何连续理论,从几何学与纤维缠绕理论到基因工程,设要裁剪的线段是,P,0,P,1,。,P,0,P,1,和窗口边界交于,A,B,C,D,四点，见图。算法是从,A,B,和,P,0,三点中找出最靠近的,P,1,点，图中要找的点是,P,0,。从,C,D,和,P,1,中找出最靠近,P,0,的点。图中要找的点是,C,点。那么,P,0,C,就是,P,0,P,1,线段上的可见部分。,Liang,-Barsky,算法,基本思想：,把二维裁剪化为一维裁剪问题，并向,x,（或,y,）方向投影以决定可见线段。,Liang-Barsky,算法,线段的参数表示,x=x0+tx,y=y0+ty 0=t,t,l,则可见线段区间,t,l,t,u,t,0,t,1,t,2,t,3,0,1,Liang,-Barsky,算法：,交点计算,Liang-Barsky,算法,始边和终边的确定及交点计算：,令,Q,L,= - x D,L,= x,0,-x,L,Q,R,= x D,R,= x,R,-x,0,Q,B,= - y D,B,= y,0,-y,B,Q,T,= y D,T,= y,T,-y,0,交点为,t,i,=,D,i,/,Q,i,i=L,R,B,T,Q,i,0,t,i,为与终边交点参数,Q,i,=0,D,i,0,时,分析另一,D,E,F,A,B,Liang-Barsky,算法,当,Q,i,=0,时,若,D,i,0,时,线段不可见,（如图中,AB,，有,Q,R,=0,，,D,R,0,时,分析另一,D,（,如图中的,EF,就是这种情况，它使,Q,L,=0,，,D,L,0,和,Q,R,=0,，,D,R,0,。,这时由于,EF,和,x=,x,L,及,x=,x,R,平行，故不必去求出,EF,和,x=,x,L,及,x=,x,R,的交点，而让,EF,和,y=,y,T,及,y=,y,B,的交点决定直线段上的可见部分。）,E,F,A,B,思考：前面几种裁剪直线段算法的裁剪窗口都是矩形区域，如何推广裁剪区域呢？,参数化算法,(Cyrus-Beck),是研究使用凸多边形区域作为裁剪区域进行二维直线段裁剪的算法。,参数化算法,(Cyrus-Beck),考虑凸多边形区域,R,和直线段,P,1,P,2,P(t,)=(P,2,-P,1,)*t+P1,设,A,是区域,R,的边界上一点，,N,是区域边界在,A,点的内法线向量,A,P,2,R,N,P,1,则对于线段,P,1,P,2,上任一点,P(t),N (P(t)-A),外侧,N (P(t)-A)0-,内侧,N (P(t)-A)=0-,边界,或其延长线上,参数化算法,(Cyrus-Beck),参数化算法,(Cyrus-Beck),凸多边形的性质：点,P(t),在凸多边形内的充要条件是，对于凸多边形边界上任意一点,A,和该点处内法向,N,，,都有,N(P(t)-A)0,参数化算法,(Cyrus-Beck),k,条边的多边形，可见线段参数区间的解,:,N,i, (p(t)-A,i,)=0, i=0,k, 0t 1.,即：,N,i, (P,1,-A,i,)+ N,i, (P,2,-P,1,) t=0,可得：,令,t,i,= N,i, (P,1,-A,i,)/N,i, (P,2,-P,1,),参数化算法,(Cyrus-Beck),N,i, (P,2,-P,1,) =0-,平行于对应边。,此时判断,N,i, (P,1,-A,i,),若,N,i, (P,1,-A,i,) P,1,P,2,在多边形外侧,-,不可见，,若,N,i, (P,1,-A,i,) 0-P,1,P,2,在多边形内侧,-,继续其它边的判断,参数化算法,(Cyrus-Beck),总结,Cyrus-Beck,算法将裁剪区域从矩形扩充到凸多边形区域,当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为,Liang-Barsky,算法。,补充知识：,外裁剪,前面讨论的是直线段相对于规则矩形或凸多边形裁剪窗口内部裁剪，取内弃外,-,内裁剪,。,实际上，我们可把直线段相对于窗口外部进行裁剪，决定线段的哪些部分位于窗口之外，并保留之，取外弃内,-,外裁剪,。,错觉,：,直线段裁剪的组合？,新的问题：,边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？,用直线段裁剪法可以解决折线以及封闭折线,(,多边形,),的裁剪问题。但对多边形区域,(,如需进行多边形区域填充时,),的裁剪则不适用。多边形区域裁剪后剩余部分应该仍然是多边形区域，如下页图,5.35.5,所示，裁剪后的多边形区域的边界由原来多边形经裁剪的线段及窗口区域的若干段边界组成。,5.2.2,多边形裁剪,图,5.3,边界线段的连接,图,5.4,边界线段的连接,图,5.5,边界线段的连接,(a),正确；,(b),不正确,多边形裁剪,-1/2,用直线段裁剪算法，可以吗？,新的问题：,图,1,因丢失顶点信息而去法确定裁剪区域,A,B,A,B,图,2,原来封闭的多边形变成了孤立的线段,边界不再封闭，需要用窗口边界的恰当部分来封闭它,1,2,1,2,3,(a),(b),(c),A,B,图,3,裁剪后的多边形顶点形成的几种情况,分裂为几个多边形,多边形裁剪,-2/2,关键：,不仅在于求出新的顶点，删去界外顶点,还在于形成正确的顶点序列,Sutherland-,Hodgman,算法,A,）,适用对象：对凹凸多边形裁剪，裁剪窗口为凸多边形,描述简单算法使用的是矩形裁剪窗口。,B),基本思想,:,是一次用裁剪窗口的一条边所在的直线来裁剪多边形，即将多边形关于裁剪窗口的裁剪分解为多边形关于窗口各边所在直线的裁剪。,Sutherland-,Hodgman,算法,C,）,流水线过程,(,左上右下,),：,前边裁剪的结果是后边裁剪的输入。,亦称逐边裁剪算法,Sutherland-,Hodgman,算法,考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分,:,可见一侧；不可见一侧,多边形的各条边的两端点,S,、,P,。,它们与裁剪线的位置关系只有四种,Sutherland-,Hodgman,算法,情况（,1,）仅输出顶点,P,；,情况（,2,）输出,0,个顶点；,情况（,3,）输出线段,SP,与裁剪线的交点,I,；,情况（,4,）输出线段,SP,与裁剪线的交点,I,和终点,P,Sutherland-,Hodgman,算法框图,一,最后一条边的处理,1,2,3,4,D,）算法中点的判断及交点的获取,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。,对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段,SP,与裁剪边的交点算法应随之改变。,1,）点的可见性判断,2,）交点的获取,可参见前面的直线段裁剪算法,Sutherland-,Hodgman,算法小结,对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将可能显示出一条多余的直线,(,如下页图,5.6,所表示,),。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。,解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再就是,Weiler,-Atherton,算法。,图,5.6,对凹多边形裁剪可能出现的问题,Weiler-Athenton,算法简介,适用对象：裁剪窗口为任意多边形（,凸、凹、带内环）,的情况,是对,Sutherland-,Hodgman,多边形,裁剪算法的推广,(,裁剪区域,),Weiler-Athenton,算法简介,主多边形：被裁剪多边形，记为,SP,裁剪多边形：裁剪窗口，记为,CP,约定：,SP,与,CP,均用它们顶点的环形链表定义,外边界取顺时针方向,内边界取逆时针方向,C,2,C,1,C,3,C,4,C,8,C,7,C,5,C,6,I,1,I,8,I,2,I,3,I,4,I,5,I,6,I,7,Weiler-Athenton,算法简介,SP,和,CP,把二维平面分成两部分。,内裁剪：,SPCP,外裁剪：,SP-CP,裁剪结果区域的边界由,SP,的部分边界和,CP,的部分边界两部分构成，并且在交点处边界发生交替，即由,SP,的边界转至,CP,的边界，或由,CP,的边界转至,SP,的边界,Weiler-Athenton,算法简介,主多边形与裁剪多边形,交点成对出现,分为如下两类：,进点,：主多边形边界由此进入裁剪多边形内,出点,：主多边形边界由此,离开裁剪多边形区域,.,思考题：,1.,直线段裁剪的算法可以推广到多边形裁剪吗？为什么？,2.,线段端点编码的含义是什么？如何简单的通过端点编码判断线段在窗口外？举例说明。,3.,给出一个在坐标系上的带坐标矩形区域,(,裁剪区域,),，给出一条典型的带坐标的直线段,(,直线段二个端点不在矩形区域内，但有部分区间在矩形区域内,),，试用中点分割的方法求出直线段的可见部分，写出每一次分割的步骤和中点变化情况直到求解条件满足为止。,4.,给出一个,Sutherland-,Hodgman,算法裁剪多边形的例子，要求写出步骤。,