图形变换与裁剪三1

《图形变换与裁剪三1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图形变换与裁剪（三）计算机学院苏小红1二维裁剪1直线段裁剪直接求交算法Cohen-Sutherland算法中点分割裁剪算法梁友栋-Basky算法2多边形裁剪Sutlerland_Hodgman算法Weiler-Atherton算法2直线段裁剪(1/15)裁剪的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交裁剪、覆盖3直线段裁剪(2/15)裁剪窗口矩形、圆形、一般多边形被裁剪对象线段、多边形、曲线、字符裁剪的策略先裁剪，后变换先变换，后裁剪裁

2、剪算法的核心问题效率4直线段裁剪(3/15)点裁剪点(x,y)在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？5直线段裁剪(4/15)假定条件矩形裁剪窗口：[xmin,xmax]X[ymin,ymax]待裁剪线段：任何平面线段相对于凸多边形窗口进行裁剪后？6直线段裁剪(5/15)待裁剪线段和窗口的关系完全落在窗口内完全落在窗口外部分在内，部分在外7直线段裁剪(6/15)为提高效率，算法设计时应考虑：1.快速判断情形(1)(2)；2.设法减少情形(3)求交次数和每次求交时所需的计算量8Cohen-Su

3、therland算法(编码算法)算法步骤：第一步判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；第二步判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步；第三步求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束裁剪过程是递归的。直线段裁剪(7/15)9特点：对显然不可见线段的快速判别编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；Cohen-S

4、utherland算法直线段裁剪(8/15)10端点编码：定义为它所在区域的编码结论：当线段的两个端点的编码的逻辑“与”非零时，显然不可见Cohen-Sutherland算法直线段裁剪(9/15)100000010010000001001001010101101010窗口bca11求交测试顺序固定(左上右下）最坏情形，线段求交四次。对于那些非完全可见、又非完全不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb）Cohen-Sutherland算法直线段裁剪(

5、10/15)121）特点：用编码方法可快速判断线段--完全可见和显然不可见。2）特别适用二种场合：大窗口场合窗口特别小的场合Cohen-Sutherland算法的特点直线段裁剪(11/15)13中点分割法基本思想：从P0点出发找出距P0最近的可见点从P1点出发找出距P1最近的可见点不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止取中点Pm=(P1+P2)/2。P2P1P2是离P1点最远的

6、可见点PmP1用P1Pm代替P1P2P2P2用PmP2代替P1P2PmP1直线段裁剪(12/15)14Liang-Barsky裁剪算法直线L与区域的交：当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分直线段裁剪(13/15)基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。15Liang-Barsky裁剪算法P4P1P3P2ymaxyminxminxmaxRT

7、SULABAS是一维窗口TS中的可见部分直线段裁剪(14/15)存在可见线段的充要条件不为空集向x轴投影，就得到可见线段上点的坐标的变化范围为左端点右端点16Liang-Barsky裁剪算法AB有可见部分的充分必要条件也可表示为直线段裁剪(15/15)17多边形裁剪-1/2用直线段裁剪算法，可以吗？新的问题：图1因丢失顶点信息而去法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它1812123(a)(b)(c)AB图3裁剪后的多边形顶点形成的几种情况分裂为几个

8、多边形多边形裁剪-2/2关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列19Sutherland-Hodgman算法-1/4分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：左边的结果是右边的开始。亦称逐边裁剪算法20Sutherland-Hodgman算法-2/4内侧空间与外侧空间多边形的边与半空间的