第5章 图形变换与裁剪3.ppt

《第5章 图形变换与裁剪3.ppt》由会员分享，可在线阅读，更多相关《第5章 图形变换与裁剪3.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章 图形变换与裁剪图形变换与裁剪3二维裁剪二维裁剪1 1 直线段裁剪直线段裁剪直线段裁剪直线段裁剪直接求交算法直接求交算法直接求交算法直接求交算法Cohen-SutherlandCohen-Sutherland算法算法算法算法 中点分割裁剪算法中点分割裁剪算法中点分割裁剪算法中点分割裁剪算法 梁友栋梁友栋梁友栋梁友栋-Basky-Basky算法算法算法算法2 2 多边形裁剪多边形裁剪多边形裁剪多边形裁剪 Sutlerland_Hodgman Sutlerland_Hodgman算法算法算法算法 Weiler-AthertonWeiler-Atherton算法算法算法算法 2 2直线段裁

2、剪直线段裁剪(1/15)裁剪的目的裁剪的目的n n判断图形元素是否在裁剪窗口之内并找出其位于内部的部分判断图形元素是否在裁剪窗口之内并找出其位于内部的部分判断图形元素是否在裁剪窗口之内并找出其位于内部的部分判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础裁剪处理的基础n n图元关于窗口内外关系的判别图元关于窗口内外关系的判别图元关于窗口内外关系的判别图元关于窗口内外关系的判别n n图元与窗口的求交图元与窗口的求交图元与窗口的求交图元与窗口的求交裁剪、覆盖裁剪、覆盖3 3直线段裁剪直线段裁剪(2/15)裁剪窗口裁剪窗口n n矩形、圆形、一般多边形矩形、圆形、一般多边形矩形、圆形

3、、一般多边形矩形、圆形、一般多边形被裁剪对象被裁剪对象n n线段、多边形、曲线、字符线段、多边形、曲线、字符线段、多边形、曲线、字符线段、多边形、曲线、字符裁剪的策略裁剪的策略n n先裁剪，后变换先裁剪，后变换先裁剪，后变换先裁剪，后变换n n先变换，后裁剪先变换，后裁剪先变换，后裁剪先变换，后裁剪裁剪算法的核心问题裁剪算法的核心问题n n效率效率效率效率4 4直线段裁剪直线段裁剪(3/15)点裁剪点裁剪 n n点点点点(x,y)(x,y)在窗口内的充分必要条件是：在窗口内的充分必要条件是：在窗口内的充分必要条件是：在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？问题：对于任何多

4、边形窗口，如何判别？问题：对于任何多边形窗口，如何判别？问题：对于任何多边形窗口，如何判别？5 5直线段裁剪直线段裁剪(4/15)假定条件假定条件n n矩形裁剪窗口：矩形裁剪窗口：矩形裁剪窗口：矩形裁剪窗口：xmin,xmaxXymin,ymaxxmin,xmaxXymin,ymaxn n待裁剪线段：待裁剪线段：待裁剪线段：待裁剪线段：任何平面线段相对于凸多边形窗口进行裁剪后？任何平面线段相对于凸多边形窗口进行裁剪后？6 6直线段裁剪直线段裁剪(5/15)待裁剪线段和窗口的关系待裁剪线段和窗口的关系 n n完全落在窗口内完全落在窗口内完全落在窗口内完全落在窗口内n n完全落在窗口外完全落在窗口

5、外完全落在窗口外完全落在窗口外n n部分在内，部分在外部分在内，部分在外部分在内，部分在外部分在内，部分在外7 7直线段裁剪直线段裁剪(6/15)为提高效率，算法设计时应考虑：为提高效率，算法设计时应考虑：1.快速判断情形快速判断情形(1)(2)；2.设法减少情形设法减少情形(3)求交次数和每次求交时所需的计算量求交次数和每次求交时所需的计算量8 8Cohen-Sutherland 算法算法(编码算法)算法步骤：算法步骤：第一步第一步 判别线段两端点是否都落在窗口内，如果是，判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；则线段完全可见；否则进入第二步；第二步第二步 判

6、别线段是否为显然不可见，如果是，则裁判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步剪结束；否则进行第三步 ；第三步第三步 求线段与窗口边延长线的交点，这个交点将求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，对余下的另一段重新进行第一步，第二步判断，直至结束直至结束 裁剪过程是递归的。直线段裁剪直线段裁剪(7/15)9 9特点：特点：特点：特点：n n对显然不可见线段的快速判别对显然不可见线段的快速判别对显然不可见线段的快速判别对显然不可见线段的快速判别编码方法：编

7、码方法：编码方法：编码方法：n n由窗口四条边所在直线把二维平面分成由窗口四条边所在直线把二维平面分成由窗口四条边所在直线把二维平面分成由窗口四条边所在直线把二维平面分成9 9个区域，每个区域赋予一个四个区域，每个区域赋予一个四个区域，每个区域赋予一个四个区域，每个区域赋予一个四位编码，位编码，位编码，位编码，C Ct tC Cb bC Cr rC Cl l，上下右左；，上下右左；，上下右左；，上下右左；Cohen-Sutherland 算法算法直线段裁剪直线段裁剪(8/15)1010端点编码：端点编码：n n定义为它所在区域的编码定义为它所在区域的编码定义为它所在区域的编码定义为它所在区域的

8、编码结论：结论：n n当线段的两个端点的编码的当线段的两个端点的编码的当线段的两个端点的编码的当线段的两个端点的编码的逻辑逻辑逻辑逻辑“与与与与”非零非零非零非零时时时时 ，显然不可见，显然不可见，显然不可见，显然不可见 Cohen-Sutherland 算法算法直线段裁剪直线段裁剪(9/15)100000010010000001001001010101101010窗口bca1111求交测试顺序固定求交测试顺序固定求交测试顺序固定求交测试顺序固定(左上右下）左上右下）左上右下）左上右下）最坏情形，线段求交四次。最坏情形，线段求交四次。最坏情形，线段求交四次。最坏情形，线段求交四次。对于那些非完

9、全可见、又非完全不可见的线段，需要对于那些非完全可见、又非完全不可见的线段，需要求交求交，求交前，求交前先测试先测试与窗口哪条边所在直线有交？与窗口哪条边所在直线有交？(按序判断端点编码中各位的值按序判断端点编码中各位的值ClCtCrCb）Cohen-Sutherland 算法算法直线段裁剪直线段裁剪(10/15)1212 1）特点：用编码方法可快速判断线段特点：用编码方法可快速判断线段-完全可见和显然不可见。完全可见和显然不可见。2）特别适用二种场合：）特别适用二种场合：大窗口场合大窗口场合 窗口特别小的场合窗口特别小的场合 Cohen-Sutherland 算法的特点算法的特点直线段裁剪直

10、线段裁剪(11/15)1313中点分割法基本思想：基本思想：基本思想：基本思想：n n从从从从P0P0点出发找出距点出发找出距点出发找出距点出发找出距P0P0最近的可见点最近的可见点最近的可见点最近的可见点n n从从从从P1P1点出发找出距点出发找出距点出发找出距点出发找出距P1P1最近的可见点最近的可见点最近的可见点最近的可见点n n不断地在中点处将线段一分为二，对每段线段重复不断地在中点处将线段一分为二，对每段线段重复不断地在中点处将线段一分为二，对每段线段重复不断地在中点处将线段一分为二，对每段线段重复Cohen-Cohen-SutherlandSutherland裁剪算法的线段可见性测

11、试方法，直至找到每段线段与窗裁剪算法的线段可见性测试方法，直至找到每段线段与窗裁剪算法的线段可见性测试方法，直至找到每段线段与窗裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止口边界线的交点或分割子段的长度充分小可视为一点为止口边界线的交点或分割子段的长度充分小可视为一点为止口边界线的交点或分割子段的长度充分小可视为一点为止取中点取中点取中点取中点Pm=(P1+P2)/2Pm=(P1+P2)/2。P2P1 P2是离是离P1点最远的可见点点最远的可见点PmP1用用P1Pm代替代替P1P2P2P2用用PmP2代替代替P1P2PmP1直线段裁剪直线

12、段裁剪(12/15)1414Liang-Barsky裁剪算法裁剪算法 直线直线直线直线L L与区域的交：与区域的交：与区域的交：与区域的交：n n当当当当QQ为空集时，线段为空集时，线段为空集时，线段为空集时，线段ABAB不可能在窗口中有可见线段。不可能在窗口中有可见线段。不可能在窗口中有可见线段。不可能在窗口中有可见线段。n n当当当当QQ不为空集时，不为空集时，不为空集时，不为空集时，QQ可看成是一个一维窗口可看成是一个一维窗口可看成是一个一维窗口可看成是一个一维窗口 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口是一维窗口TS中的可见部分中的可见部分直线段裁

13、剪直线段裁剪(13/15)基本思想：基本思想：基本思想：基本思想：n n把二维裁剪化为一维裁剪问题，并向把二维裁剪化为一维裁剪问题，并向把二维裁剪化为一维裁剪问题，并向把二维裁剪化为一维裁剪问题，并向x x（或（或（或（或y y）方向投影以决定可见线段。）方向投影以决定可见线段。）方向投影以决定可见线段。）方向投影以决定可见线段。1515Liang-Barsky裁剪算法裁剪算法 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口是一维窗口TS中的可见部分中的可见部分直线段裁剪直线段裁剪(14/15)存在可见线段的充要条件存在可见线段的充要条件存在可见线段的充要条件存在

14、可见线段的充要条件n n 不为空集不为空集不为空集不为空集 向向向向x x轴投影，就得到可见线段上点的坐标的变化范围为轴投影，就得到可见线段上点的坐标的变化范围为轴投影，就得到可见线段上点的坐标的变化范围为轴投影，就得到可见线段上点的坐标的变化范围为 左端点左端点右端点右端点1616Liang-Barsky裁剪算法裁剪算法AB有可见部分的充分必要条件也可表示为有可见部分的充分必要条件也可表示为 直线段裁剪直线段裁剪(15/15)1717多边形裁剪-1/2用直线段裁剪算法，可以吗？用直线段裁剪算法，可以吗？用直线段裁剪算法，可以吗？用直线段裁剪算法，可以吗？新的问题新的问题新的问题新的问题：图图

15、1 因丢失顶点信息而去法确定裁剪区域因丢失顶点信息而去法确定裁剪区域ABAB图图2 原来封闭的多边形变成了孤立的线段原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它边界不再封闭，需要用窗口边界的恰当部分来封闭它181812123(a)(b)(c)AB图图3 裁剪后的多边形顶点形成的几种情况裁剪后的多边形顶点形成的几种情况分裂为几个多边形分裂为几个多边形多边形裁剪-2/2关键：关键：n n不仅在于求出新的顶点，删去界外顶点不仅在于求出新的顶点，删去界外顶点不仅在于求出新的顶点，删去界外顶点不仅在于求出新的顶点，删去界外顶点n n还在于形成正确的顶点序列还在于形成正确

16、的顶点序列还在于形成正确的顶点序列还在于形成正确的顶点序列1919Sutherland-Hodgman算法-1/4分割处理策略分割处理策略分割处理策略分割处理策略：n n将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。在直线的裁剪。在直线的裁剪。在直线的裁剪。流水线过程流水线过程流水线过程流水线过程(左上右下左上右下左上右下左上右下)：左边的结果是右边的开始左边的结果是右边的开始左边的结果是右边的开始左边的结果是右边的开始

17、。亦称亦称逐边裁剪算法逐边裁剪算法2020Sutherland-Hodgman算法-2/4n n内侧空间与外侧空间内侧空间与外侧空间内侧空间与外侧空间内侧空间与外侧空间n n多边形的边与半空间的关系多边形的边与半空间的关系多边形的边与半空间的关系多边形的边与半空间的关系 线段与当前裁剪边的位置关系线段与当前裁剪边的位置关系可见一侧可见一侧窗口窗口(a)输出输出Pi+1当前裁剪边Pi+1Pi可见一侧可见一侧窗口窗口(a)无输出无输出当前裁剪边Pi+1Pi可见一侧可见一侧窗口窗口(a)输出输出I当前裁剪边Pi+1Pi可见一侧可见一侧窗口窗口(a)输出输出I和和Pi+1当前裁剪边Pi+1Pi2121

18、Sutherland-Hodgman算法-3/4裁剪结果的顶点构成裁剪结果的顶点构成裁剪结果的顶点构成裁剪结果的顶点构成：n n裁剪边内侧的原顶点；裁剪边内侧的原顶点；裁剪边内侧的原顶点；裁剪边内侧的原顶点；n n多边形的边与裁剪边的交点。多边形的边与裁剪边的交点。多边形的边与裁剪边的交点。多边形的边与裁剪边的交点。顺序连接。顺序连接。顺序连接。顺序连接。优点：优点：l裁剪算法采用流水线方式，适合硬件实现。裁剪算法采用流水线方式，适合硬件实现。l可推广到任意凸多边形裁剪窗口可推广到任意凸多边形裁剪窗口2222Sutherland-Hodgman算法-4/4存在的问题逐边裁剪要求裁剪窗口为凸多边

19、形，那么凹多边形窗口怎么办？逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几个多边形沿边框产生多余的线段？几个多边形沿边框产生多余的线段？几个多边形沿边框产生多余的线段？几个多边形沿边框产生多余的线段？图6 逐边裁剪法对凹多边形裁剪时可能出现的问题3218769

20、54103217654108932174108956原图对左边裁对顶边裁32174108956对右边裁对底边裁2323Weiler-Atherton算法算法-1/6裁剪窗口为任意多边形（裁剪窗口为任意多边形（裁剪窗口为任意多边形（裁剪窗口为任意多边形（凸、凹、带内环）凸、凹、带内环）的情况的情况的情况的情况n n主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为SP SP n n裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为CP CP 2424约定：约定：n nSPSP与与与

21、与CPCP均用它们顶点的环形链表定义均用它们顶点的环形链表定义均用它们顶点的环形链表定义均用它们顶点的环形链表定义n n外边界取顺时针方向外边界取顺时针方向外边界取顺时针方向外边界取顺时针方向n n内边界取逆时针方向内边界取逆时针方向内边界取逆时针方向内边界取逆时针方向Weiler-Atherton算法算法-2/6C2C1C3C4C8C7C5C6I1I8I2I3I4I5I6I72525SP和和CP把二维平面分成两部分。把二维平面分成两部分。内裁剪：内裁剪：SPCP外裁剪：外裁剪：SP-CPWeiler-Atherton算法算法-3/6裁剪结果区域的边界由裁剪结果区域的边界由SP的部分边界和的部

22、分边界和CP的部分边界两部分构成，并且在交点的部分边界两部分构成，并且在交点处边界发生交替，即由处边界发生交替，即由SP的边界转至的边界转至CP的边界，或由的边界，或由CP的边界转至的边界转至SP的边界的边界 2626Weiler-Atherton算法算法-4/6n n主多边形与裁剪多边形主多边形与裁剪多边形主多边形与裁剪多边形主多边形与裁剪多边形交点成对出现交点成对出现交点成对出现交点成对出现n n分为如下两类：分为如下两类：分为如下两类：分为如下两类：进点进点进点进点：主多边形边界由此进入裁剪多边形内：主多边形边界由此进入裁剪多边形内：主多边形边界由此进入裁剪多边形内：主多边形边界由此进入

23、裁剪多边形内 出点出点出点出点：主多边形边界由此：主多边形边界由此：主多边形边界由此：主多边形边界由此 离开裁剪多边形区域离开裁剪多边形区域离开裁剪多边形区域离开裁剪多边形区域.2727Weiler-Atherton算法算法-5/6C2C1C3C4S1S2S3S4S5S6I1I2I3I4I5I6I7I8裁剪多边形CP主多边形SP算法裁剪后所生成的多边形为算法裁剪后所生成的多边形为I1I2I3S3I4I5I6I7S6I8 I1主多边形表裁剪多边形表S1S2I1S3S4S5S6I2I3I4I5I6I7I8C1C2I3I4C4I8I1I2I5C3I5I6S1I7C1开始结束2828Weiler-Atherton算法算法-6/6C2C1C3C4C8C7C5C6S2S1S3S4S8S7S5S6I1I8I2I3I4I5I6I7主多边形表裁剪多边形表S1S2I1I4S4S6I5I2I3S3S1S5S7I6S8I7I8S5C1C2C3C4I4I5I1I8C1C5C5C6I2I3I6C7C8I7算法裁剪后所生成的多边形为算法裁剪后所生成的多边形为I1I2I7I8I1和和I3I4I5I6I3 裁剪多边形主多边形开始开始结束结束2929