计算机图形学第五章-课件

计算机图形学第五章第五章裁剪教学学时：6课时教学目的与要求：让学生初步了解裁剪的定义，掌握对直线段裁剪的一些基本算法，掌握简单的对多边形裁剪的算法，掌握算法的理论原理，能够分析基本算法的优缺点。教学重点：Cohen-Sutherland算法，中点分割算法，梁友栋—Barsky算法，参数化算法，Sutlerland_Hodgman算法。2第五章裁剪

5.1裁剪概述5.2二维裁剪5.2.1直线段裁剪5.2.2多边形裁剪35.1裁剪概述

在使用计算机处理图形信息时，遇到的情况往往是计算机内部存储的图形比较大，而屏幕显示只是图的一部分。例如，虽然计算机内部可以存储全国地图，但是，如果把全国地图整幅显示在屏幕上，则不能看到各地局部的细节。这时，可以使用缩放技术，把地图中的局部区域放大显示。在放大显示一幅图形的一部分区域时，必须确定图形中哪些部分落在显示区之内，哪些部分落在显示区之外，以便显示落在显示区内的那部分图形。这个选择处理过程称为裁剪。在进行裁剪时，画面中对应于屏幕显示的那部分区域称为窗口。一般把窗口定义为矩形，由上、下、左、右四条边围成。裁剪的实质就是决定图形中哪些点、线段、文字以及多边形在窗口之内。4

裁剪可以在世界坐标系中进行，即相对于窗口进行；也可以把对象变换为设备坐标之后相对于视区进行。前者可以把不在窗口范围内的部分剪掉，避免了不必要的变换处理；后者在设备坐标系中裁剪易于用硬件实现。裁剪处理的基础是：点在窗口区域内外的判断以及计算图形元素与窗口区域边界的交点。其原理虽然简单，但涉及的图形元素多，提高裁剪速度是算法应考虑的重要问题。以下介绍直线段裁剪算法及多边形裁剪算法。5

最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。6裁剪算法有二维的和三维的，裁剪对象也可以是规则形体，也可以是不规则形体。本章重点介绍二维裁剪，三维裁剪涉及到后面章节三维消隐等内容，后面再简要介绍。5.2二维裁剪7大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流85.2.1直线段裁剪直接求交算法Cohen-Sutherland算法中点分割算法Liang-Barskey算法参数化裁剪算法5.2.2多边形裁剪Sutlerland_Hodgman算法

Weiler-Athenton算法

5.2二维裁剪9

直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。所以本章重点讨论直线段的裁剪算法。算法一般取的裁剪多边形都是矩形，有些特殊的算法采用任意多边形裁剪。5.2.1直线段裁剪10点的裁剪图形裁剪中最基本的问题。假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：

xL<=x<=xR并且yB<=y<=yT

否则，P点就在窗口外。(xL,yB)(xR,yT)11直线段裁剪裁剪线段与窗口的关系：(1)线段完全可见；(2)显然不可见；(3)其它提高裁剪效率：快速判断情形(1)(2)，对于情形(3)，设法减少求交次数和每次求交时所需的计算量。12直接求交算法直线与窗口边都写成参数形式，求参数值。13Cohen-Sutherland裁剪基本思想：对于每条线段P1P2分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段P1P2

。（2）若P1P2明显在窗口外，则丢弃该线段。（3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。为快速判断，采用如下编码方法：14图5.1区域划分及编码

15图5.2区位码各位含义16编码的思想在图形学中非常重要。Sutherland：Coons,图灵,IEEE计算机先驱奖。17Cohen-Sutherland算法一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：18Cohen-Sutherland裁剪若P1P2完全在窗口内code1=0,且code2=0,则“取”若P1P2明显在窗口外code1&code2≠0，则“弃”在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。19Cohen-Sutherland

直线裁剪算法小结本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。特点：用编码方法可快速判断线段的完全可见和显然不可见。20中点分割裁剪算法

中点分割裁剪算法是对Cohen-Sutherland直线段裁剪算法的改进。在Cohen-Sutherland直线段裁剪算法中,为了避免求直线段与窗口边界的交点,用不断对分线段的方法排斥线段在窗口外的部分,最后求出离线段端点最远的可见点(所谓可见点就是线段落在窗口内的点),若这两点存在,则这两点就是线段P1P2的可见线段端点。21中点分割裁剪算法基本思想：与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:全部可见、完全不可见和线段部分可见。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。22问：算法为什么可行？会不会无限循环、不断二分？因为屏幕像素是有限的，一般计算次数不会太多，而且算法思想是用取中点的方法最后在误差允许的范围内去逼近真正的与裁剪矩形边的交点。23下面我们仅介绍如何在线段P1P2上求离P1最远的可见点(求P2最远的可见点同p1),其具体步骤如下：①测试P2是否在窗口内，若是，则P2就是离P1最远的可见点，结束。否则，进行下一步。

②测试P1P2是否在窗外同侧，若是，P1P2全部不可见，结束。否则，进行下一步。③取P1P2的中点Pm，若PmP2在窗外同侧，舍去，剩余段以P2代替Pm重复第二步。否则，以P1代替Pm重复第二步。直到线段不能再分为止。24图中,对线段a,求离P1最远的可见点算法在第一步结束;对线段b,算法在第二步结束;对线段c,算法进入第三步后开始对分线段,最终重复第二步结束。

25中点分割裁剪算法的优点取中点的目的是用中点逼近线段与边界的交点。这种方法没有求交计算，适合于没有乘除运算的计算机，易于用硬件实现。26Liang-Barsky算法

*写入图形学教科书的唯一中国人的算法

*CommunicationofACM的论文梁有栋教授(浙江大学数学系教授)的二三事Liang-Barsky算法几何连续理论从几何学与纤维缠绕理论到基因工程27

设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。Liang-Barsky算法基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。28Liang-Barsky算法

线段的参数表示x=x0+t△xy=y0+t△y0<=t<=1△x=x1-x0△y=y1-y0窗口边界的四条边分为两类：始边和终边。29求出P0P1与两条始边的交点参数t0,t1,令tl=max(t0,t1,0)，则tL即为三者中离p1最近的点的参数求出p0p1与两条终边的交点参数t2,t3,令tu=min(t2,t3,1)，则tU即为三者中离p0最近的点的参数若tu

>tl,则可见线段区间[tl,tu]t0t1t2t301Liang-Barsky算法：交点计算30Liang-Barsky算法始边和终边的确定及交点计算：令QL=-△xDL=x0-xL

QR=△xDR=xR-x0QB=-△yDB=y0-yB

QT=△yDT=yT-y0交点为ti=Di/Qii=L,R,B,TQi<0ti为与始边交点参数Qi>0ti为与终边交点参数Qi=0Di<0时,线段不可见

Di>0时,分析另一D,EFAB31Liang-Barsky算法当Qi=0时若Di<0时,线段不可见（如图中AB，有QR=0，DR<0）若Di>0时,分析另一D,

（如图中的EF就是这种情况，它使QL=0，DL>0和QR=0，DR>0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）EFAB32思考：前面几种裁剪直线段算法的裁剪窗口都是矩形区域，如何推广裁剪区域呢？参数化算法(Cyrus-Beck)是研究使用凸多边形区域作为裁剪区域进行二维直线段裁剪的算法。33参数化算法(Cyrus-Beck)考虑凸多边形区域R和直线段P1P2P(t)=(P2-P1)*t+P1设A是区域R的边界上一点，N是区域边界在A点的内法线向量AP2RNP134则对于线段P1P2上任一点P(t)N·(P(t)-A)<0->外侧N·(P(t)-A)>0->内侧N·(P(t)-A)=0->边界或其延长线上参数化算法(Cyrus-Beck)35参数化算法(Cyrus-Beck)凸多边形的性质：点P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该点处内法向N，都有

N·(P(t)-A)>036参数化算法(Cyrus-Beck)k条边的多边形，可见线段参数区间的解:Ni·(p(t)-Ai)>=0,i=0,…,k,0≤t≤1.即：Ni·(P1-Ai)+Ni·(P2-P1)t>=0可得：令ti=Ni·(P1-Ai)/[Ni·(P2-P1)]37参数化算法(Cyrus-Beck)Ni·(P2-P1)=0->平行于对应边。此时判断Ni·(P1-Ai)若Ni·(P1-Ai)<0->P1P2在多边形外侧->不可见，若Ni·(P1-Ai)>0->P1P2在多边形内侧->继续其它边的判断38参数化算法(Cyrus-Beck)总结Cyrus-Beck算法将裁剪区域从矩形扩充到凸多边形区域当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为Liang-Barsky算法。39补充知识：外裁剪前面讨论的是直线段相对于规则矩形或凸多边形裁剪窗口内部裁剪，取内弃外--内裁剪。实际上，我们可把直线段相对于窗口外部进行裁剪，决定线段的哪些部分位于窗口之外，并保留之，取外弃内--外裁剪。40错觉：直线段裁剪的组合？新的问题：边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？用直线段裁剪法可以解决折线以及封闭折线(多边形)的裁剪问题。但对多边形区域(如需进行多边形区域填充时)的裁剪则不适用。多边形区域裁剪后剩余部分应该仍然是多边形区域，如下页图5.3~5.5所示，裁剪后的多边形区域的边界由原来多边形经裁剪的线段及窗口区域的若干段边界组成。5.2.2多边形裁剪41图5.3边界线段的连接

42图5.4边界线段的连接

43图5.5边界线段的连接(a)正确；(b)不正确44多边形裁剪-1/2用直线段裁剪算法，可以吗？新的问题：图1因丢失顶点信息而去法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它4512123(a)(b)(c)AB图3裁剪后的多边形顶点形成的几种情况分裂为几个多边形多边形裁剪-2/2关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列46Sutherland-Hodgman算法A）适用对象：对凹凸多边形裁剪，裁剪窗口为凸多边形,描述简单算法使用的是矩形裁剪窗口。B)基本思想:是一次用裁剪窗口的一条边所在的直线来裁剪多边形，即将多边形关于裁剪窗口的裁剪分解为多边形关于窗口各边所在直线的裁剪。47Sutherland-Hodgman算法C）流水线过程(左上右下)：前边裁剪的结果是后边裁剪的输入。亦称逐边裁剪算法48Sutherland-Hodgman算法考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种49Sutherland-Hodgman算法情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P50Sutherland-Hodgman算法框图一最后一条边的处理123451D）算法中点的判断及交点的获取上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。1）点的可见性判断2）交点的获取可参见前面的直线段裁剪算法52Sutherland-Hodgman算法小结对凸多边形应用本算法可以得到正确的结果，但是对凹多边形