《维图形裁剪》PPT课件.ppt

第七讲二维图形裁剪,在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。在进行裁剪时，对应于屏幕显示的那部分区域称为窗口，一般窗口定义为矩形，由上、下、左、右四条边围成。裁剪的实质，就是决定图形中哪些点、线段、文字以及多边形在窗口之内。,主要内容,1.点的裁剪2.直线的裁剪3.多边形的裁剪4.字符的裁剪,1.点的裁剪,设窗口由x=xL,x=xR,y=yB,y=yT围成。对于点(x,y)判别两对不等式：xL=x=xR，yB=y=yT；若四个不等式均成立，则点在窗口之内；否则，点在窗口之外。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。,2.直线段裁剪,直线段裁剪算法比较简单，但非常重要，是复杂图元裁剪的基础。因为复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。常用的线段裁剪方法有三种：Cohen-Sutherland，中点分割算法和梁友栋barskey算法。,Cohen-Sutherland裁剪算法,该算法的思想是：对于每条线段P1P2分为三种情况处理。（1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,问题：如何判断线段与窗口的关系？,为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法。延长窗口的边，将二维平面分成九个区域。每个区域赋予4位编码CtCbCrCl.其中各位编码的定义如下：,裁剪一条线段时，先求出P1P2所在的区号code1,code2。若code1=0,且code2=0，则线段P1P2在窗口内，应取之。若按位与运算code1多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种,Sutherland-Hodgman算法,情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P,Sutherland-Hodgman算法框图,处理线段SP过程子框图,Sutherland-Hodgman算法,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。,Sutherland-Hodgeman算法,对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。,4字符裁剪,前面我们介绍了字符和文本的输出。当字符和文本部分在窗口内，部分在窗口外时，就提出了字符裁剪问题。字符串裁剪可按三个精度来进行：串精度、字符精度、以及笔画象素精度。采用串精度进行裁剪时，将包围字串的外接矩形对窗口作裁剪。当字符串方框整个在窗口内时予以显示，否则不显示。采用字符精度进行裁剪时，将包围字的外接矩形对窗口作裁剪，某个字符方框整个落在窗口内予以显示，否则不显示。采用笔画象素精度进行裁剪时，将笔划分解成直线段对窗口作裁剪，处理方法同上。,换种说法，字符串剪裁有三种可选择的方法：1、字符串的有或无剪裁（all-or-none-tex）（基于字符串）效果如下图，其算法思想是：根据字符串所含字符的个数，及字符的大小、间隔、轨迹，求出字符串的外包盒（box）。以外包盒的边界极值与窗边极值比较而决定该字串的去留。,(a)待裁剪字符串(b)串精度裁剪(c)字符精度裁剪(d)象素精度裁剪,2、字符的有或无剪裁（all-or-none-character）（基于字符）效果如下图，其算法思想是：1）先以字串box与窗边比较而决定字串的全删、全留或部分留。2）对部分留的字串中，逐个测量字符的box与窗边关系而决定该字符的去留。,3、字符的精密剪裁（基于构成字符的最小元素）点阵字符：点裁剪；矢量字符：线裁剪效果如下图，其算法思想是：1）用字串box与窗边相比较。决定字串的全删、全留或部分删；2）对部分留的字串中，逐个测量字符的box与窗边的关系，决定字符的全删、全留或部分删；3）对部分留的字符的每一笔划，用直线剪裁法对窗边进行剪裁。,