图型变换和裁减

1、关于图型变换与裁减1第1页，共50页，2022年，5月20日，5点13分，星期四2图形裁剪 直线段的裁剪 多边形的裁剪第2页，共50页，2022年，5月20日，5点13分，星期四3图形裁剪裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。第3页，共50页，2022年，5月20日，5点13分，星期四4裁剪的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交裁剪、覆盖第4页，共50页，2022年，5月20日，5点13分，星期四5裁剪窗口矩形、圆形、一般多边形被裁剪对象线

2、段、多边形、曲线、字符裁剪的策略先裁剪，后变换先变换，后裁剪裁剪算法的核心问题效率第5页，共50页，2022年，5月20日，5点13分，星期四6直线段裁剪直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。第6页，共50页，2022年，5月20日，5点13分，星期四7直线段裁剪点裁剪 点(x, y)在窗口内的充分必要条件是： 问题：极其费时第7页，共50页，2022年，5月20日，5点13分，星期四8直线段裁剪把直线当作一个整体来裁剪矩形裁剪窗口： Xmin , Xmax Ymin , Ymax 待裁剪线段：前提：任何平面线段在凸多边形窗

3、口进行裁剪后，落在窗口内的线段不会多于1条。第8页，共50页，2022年，5月20日，5点13分，星期四9直线段裁剪待裁剪线段和窗口的关系 完全落在窗口内完全落在窗口外部分在内，部分在外第9页，共50页，2022年，5月20日，5点13分，星期四10直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点算法 梁友栋barskey算法第10页，共50页，2022年，5月20日，5点13分，星期四11直接求交算法直线与窗口边都写成参数形式，求参数值。第11页，共50页，2022年，5月20日，5点13分，星期四12直线段裁剪直接求交算法Cohen-Sutherland算法中点算法梁友

4、栋barskey算法第12页，共50页，2022年，5月20日，5点13分，星期四13直线段裁剪为提高效率，算法设计时应考虑：1. 快速判断情形(1)(2)；2. 设法减少情形(3)求交次数和每次求交时所需的计算量待裁剪线段和窗口的关系 完全落在窗口内完全落在窗口外部分在内，部分在外第13页，共50页，2022年，5月20日，5点13分，星期四14Cohen-Sutherland 算法 (编码算法)算法步骤：判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步 ；求线段与窗口边延长线的交点，这个交点将线段分为两段，

5、其中一段显然不可见，丢弃。对余下的另一段重新进行1、2判断，直至结束 。裁剪过程是递归的。第14页，共50页，2022年，5月20日，5点13分，星期四15编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；Cohen-Sutherland 算法第15页，共50页，2022年，5月20日，5点13分，星期四16100110001010000100000010010101000110第16页，共50页，2022年，5月20日，5点13分，星期四此算法也称为编码裁剪算法端点编码：定义为它所在区域的编码结论：当线段的两个端点的编码的逻辑“与”非

6、零时 ，显然不可见 。逻辑“或”为零时 ，显然可见 。Cohen-Sutherland 算法100000010010000001001001010101101010窗口bca第17页，共50页，2022年，5月20日，5点13分，星期四18对于那些非完全可见、又非完全不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交。Cohen-Sutherland 算法 逐个端点判断 其编码CtCbCrCl中各位是否为1，若是，则需求交 最坏情形 线段求交四次第18页，共50页，2022年，5月20日，5点13分，星期四19Cohen-Sutherland裁剪如何判定应该与窗口的哪条边求交呢？ 编

7、码中对应位为1的边。计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT&code !=0)x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code !=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BOTTOM&code !=0) y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1); else if(TOP & code !=0) y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);第19页，共50页，2022年，5月20日，5点13分，星期四20

8、1）特点：用编码方法可快速判断线段 完全可见或完全不可见。 2）特别适用二种场合： 大窗口场合 窗口特别小的场合 (如：光标拾取图形时，光标看作小的裁剪窗口)Cohen-Sutherland 算法的特点第20页，共50页，2022年，5月20日，5点13分，星期四21直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点算法 梁友栋barskey算法第21页，共50页，2022年，5月20日，5点13分，星期四22中点分割裁剪算法基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。与Cohen-Sutherl

9、and算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点。第22页，共50页，2022年，5月20日，5点13分，星期四23中点分割算法-求线段与窗口的交点从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm；若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1；再对新的P0P1求中点Pm。重复上述过程，直到PmP1长

10、度小于给定的控制常数为止，此时Pm收敛于交点；从P1出发找距离P1最近可见点采用上面类似方法。第23页，共50页，2022年，5月20日，5点13分，星期四24中点分割裁剪算法第24页，共50页，2022年，5月20日，5点13分，星期四25主要过程只用到加法和除法运算，适合硬件实现，它可以用右移位来代替除法，这样就大大加快了速度。中点分割裁剪算法第25页，共50页，2022年，5月20日，5点13分，星期四26直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点算法 梁友栋barskey算法第26页，共50页，2022年，5月20日，5点13分，星期四27Liang-Bars

11、ky裁剪算法 直线L与区域的交：当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分直线段裁剪(13/15)基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。第27页，共50页，2022年，5月20日，5点13分，星期四28Liang-Barsky裁剪算法 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分直线段裁剪(14/15)存在可见线段的充要条件 不为空集 向x轴投影，就得到可见线段上点的坐标的

12、变化范围为 左端点右端点第28页，共50页，2022年，5月20日，5点13分，星期四29Liang-Barsky裁剪算法AB有可见部分的充分必要条件也可表示为 直线段裁剪(15/15)第29页，共50页，2022年，5月20日，5点13分，星期四30二维线段裁剪直线段裁剪直接求交算法Cohen-Sutherland算法中点算法梁友栋barskey算法多边形裁剪Sutherland-Hodgman算法Weiler-Atherton算法第30页，共50页，2022年，5月20日，5点13分，星期四多边形裁剪用直线段裁剪算法，可以吗？新的问题：图1 因丢失顶点信息而无法确定裁剪区域ABAB图2 原

13、来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它图1 因丢失顶点信息而无法确定裁剪区域ABAB图2 原来封闭的多边形变成了孤立的线段第31页，共50页，2022年，5月20日，5点13分，星期四12123(a)(b)(c)AB图3 裁剪后的多边形顶点形成的几种情况分裂为几个多边形多边形裁剪第32页，共50页，2022年，5月20日，5点13分，星期四33关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列常用的方法Sutherland-Hodgman算法Weiler-Atherton算法第33页，共50页，2022年，5月20日，5点13分，星期四34S

14、utherland-Hodgman算法分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：前边的结果是后边的输入。亦称逐边裁剪算法第34页，共50页，2022年，5月20日，5点13分，星期四Sutherland-Hodgman算法基本思想是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线，该线把平面分成两个部分:可见一侧，不可见一侧。多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种：第35页，共50页，2022年，5月20日，5点13分，星期四36Sutherland-Hodgman算法情况（1）仅输出顶点P

15、；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点PII第36页，共50页，2022年，5月20日，5点13分，星期四37Sutherland-Hodgman算法裁剪结果的构成裁剪边内侧的原顶点多边形的边与裁剪边的交点顺序连接几点说明裁剪算法采用流水线方式，适合硬件实现可推广到任意凸多边形裁剪窗口第37页，共50页，2022年，5月20日，5点13分，星期四38Sutherland-Hodgeman算法缺点：只能正确处理凸多边形，对凹多边形怎么办呢？对凹多边形来说，裁剪后的多边形有两个或者多个分离部分的时候，就对出现多余的线段。因为只

16、有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。第38页，共50页，2022年，5月20日，5点13分，星期四图6 逐边裁剪法对凹多边形裁剪时可能出现的问题321876954103217654108932174108956原图对左边裁对顶边裁32174108956对右边裁对底边裁第39页，共50页，2022年，5月20日，5点13分，星期四40解决这个问题的方法：一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是Weiler-Atherton算法。第40页，共50页，2022年，5月20日，5点13分，星期四41Weiler-Atherton算法裁剪窗口为任意多边形（

17、凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为SP 裁剪多边形：裁剪窗口，记为CP第41页，共50页，2022年，5月20日，5点13分，星期四42约定：SP与CP均用它们顶点的环形链表定义外边界取顺时针方向内边界取逆时针方向(多边形内部总在其右边)Weiler-Atherton算法第42页，共50页，2022年，5月20日，5点13分，星期四43SP和CP把二维平面分成两部分。内裁剪：SPCP外裁剪：SP-CPWeiler-Atherton算法裁剪结果由两部分构成：1.SP的部分边界2.CP的部分边界且在交点处边界发生交替即由SP的边界转至CP的边界或由CP的边界转至SP的边界 第43

18、页，共50页，2022年，5月20日，5点13分，星期四44Weiler-Atherton算法主多边形与裁剪多边形交点成对出现分为如下两类：进点：主多边形SP边界由此进入裁剪多边形CP内 出点：主多边形边界由此离开裁剪多边形区域. 第44页，共50页，2022年，5月20日，5点13分，星期四进点：SP边界由此进入CP如：I1、I3、I5、I7出点：SP边界由此离开CP如： I2、I4、I6、I8C2C1C3C4S1S2S3S4S5S6I1I2I3I4I5I6I7I8裁剪多边形CP主多边形SP第45页，共50页，2022年，5月20日，5点13分，星期四46Weiler-Athenton算法由任一进点出发，沿SP的边，跟踪检测其与CP的交点，判断该交点为进点还是出点；若是进点，则沿SP边所示方向收集顶点序列；若是出点，则从此点开始，检测CP的边所示方向收集顶点序列；如此交替沿两个多边形的边行进，直至回到起始点为止。第46页，共50页，2022年，5月20日，5点13分，星期四Weiler-Atherton算法C2C1C3C4S1S2S3S4S5S6I1I2I3I4I5I6I7I8裁剪多边形CP主多边形SP算法裁剪后所生成的多边形为I1I2I3S3I4I5I6I7S6I8 I1主多边形表裁剪多边形表S1S2I1S3S4S5S6I2I3I4I5