图型变换与裁减

关于图型变换与裁减1第一页，共五十页，编辑于2023年，星期日2图形裁剪

直线段的裁剪多边形的裁剪第二页，共五十页，编辑于2023年，星期日3图形裁剪裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。第三页，共五十页，编辑于2023年，星期日4裁剪的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交裁剪、覆盖第四页，共五十页，编辑于2023年，星期日5裁剪窗口矩形、圆形、一般多边形被裁剪对象线段、多边形、曲线、字符裁剪的策略先裁剪，后变换先变换，后裁剪裁剪算法的核心问题效率第五页，共五十页，编辑于2023年，星期日6直线段裁剪直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。第六页，共五十页，编辑于2023年，星期日7直线段裁剪点裁剪点(x,y)在窗口内的充分必要条件是：

问题：极其费时第七页，共五十页，编辑于2023年，星期日8直线段裁剪把直线当作一个整体来裁剪矩形裁剪窗口：

[Xmin,Xmax]×[Ymin,Ymax]待裁剪线段：前提：任何平面线段在凸多边形窗口进行裁剪后，落在窗口内的线段不会多于1条。第八页，共五十页，编辑于2023年，星期日9直线段裁剪待裁剪线段和窗口的关系完全落在窗口内完全落在窗口外部分在内，部分在外第九页，共五十页，编辑于2023年，星期日10直线段裁剪

直接求交算法

Cohen-Sutherland算法中点算法梁友栋－barskey算法第十页，共五十页，编辑于2023年，星期日11直接求交算法直线与窗口边都写成参数形式，求参数值。第十一页，共五十页，编辑于2023年，星期日12直线段裁剪直接求交算法Cohen-Sutherland算法中点算法梁友栋－barskey算法第十二页，共五十页，编辑于2023年，星期日13直线段裁剪为提高效率，算法设计时应考虑：1.快速判断情形(1)(2)；2.设法减少情形(3)求交次数和每次求交时所需的计算量待裁剪线段和窗口的关系完全落在窗口内完全落在窗口外部分在内，部分在外第十三页，共五十页，编辑于2023年，星期日14Cohen-Sutherland算法(编码算法)算法步骤：判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步；求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行1、2判断，直至结束。裁剪过程是递归的。第十四页，共五十页，编辑于2023年，星期日15编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码， CtCbCrCl，上下右左；Cohen-Sutherland算法第十五页，共五十页，编辑于2023年，星期日16100110001010000100000010010101000110第十六页，共五十页，编辑于2023年，星期日此算法也称为编码裁剪算法端点编码：定义为它所在区域的编码结论：当线段的两个端点的编码的逻辑“与”非零时，显然不可见。逻辑“或”为零时，显然可见。Cohen-Sutherland算法100000010010000001001001010101101010窗口bca第十七页，共五十页，编辑于2023年，星期日18对于那些非完全可见、又非完全不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交。Cohen-Sutherland算法

逐个端点判断其编码CtCbCrCl中各位是否为1，若是，则需求交最坏情形线段求交四次第十八页，共五十页，编辑于2023年，星期日19Cohen-Sutherland裁剪如何判定应该与窗口的哪条边求交呢？ 编码中对应位为1的边。计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点

if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}第十九页，共五十页，编辑于2023年，星期日201）特点： 用编码方法可快速判断线段——

完全可见或完全不可见。

2）特别适用二种场合：大窗口场合窗口特别小的场合

(如：光标拾取图形时，光标看作小的裁剪窗口)Cohen-Sutherland算法的特点第二十页，共五十页，编辑于2023年，星期日21直线段裁剪

直接求交算法

Cohen-Sutherland算法中点算法梁友栋－barskey算法第二十一页，共五十页，编辑于2023年，星期日22中点分割裁剪算法基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0

、P1最近的可见点，Pm为P0P1中点。第二十二页，共五十页，编辑于2023年，星期日23中点分割算法-求线段与窗口的交点从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm；若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1；再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点；从P1出发找距离P1最近可见点采用上面类似方法。第二十三页，共五十页，编辑于2023年，星期日24中点分割裁剪算法第二十四页，共五十页，编辑于2023年，星期日25主要过程只用到加法和除法运算，适合硬件实现，它可以用右移位来代替除法，这样就大大加快了速度。中点分割裁剪算法第二十五页，共五十页，编辑于2023年，星期日26直线段裁剪

直接求交算法

Cohen-Sutherland算法中点算法梁友栋－barskey算法第二十六页，共五十页，编辑于2023年，星期日27Liang-Barsky裁剪算法

直线L与区域的交：当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分直线段裁剪(13/15)基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。第二十七页，共五十页，编辑于2023年，星期日28Liang-Barsky裁剪算法

P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分直线段裁剪(14/15)存在可见线段的充要条件

不为空集

向x轴投影，就得到可见线段上点的坐标的变化范围为

左端点右端点第二十八页，共五十页，编辑于2023年，星期日29Liang-Barsky裁剪算法AB有可见部分的充分必要条件也可表示为直线段裁剪(15/15)第二十九页，共五十页，编辑于2023年，星期日30二维线段裁剪直线段裁剪直接求交算法Cohen-Sutherland算法中点算法梁友栋－barskey算法多边形裁剪Sutherland-Hodgman算法Weiler-Atherton算法第三十页，共五十页，编辑于2023年，星期日多边形裁剪用直线段裁剪算法，可以吗？新的问题：图1因丢失顶点信息而无法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它图1因丢失顶点信息而无法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段第三十一页，共五十页，编辑于2023年，星期日12123(a)(b)(c)AB图3裁剪后的多边形顶点形成的几种情况分裂为几个多边形多边形裁剪第三十二页，共五十页，编辑于2023年，星期日33关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列常用的方法Sutherland-Hodgman算法Weiler-Atherton算法第三十三页，共五十页，编辑于2023年，星期日34Sutherland-Hodgman算法分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：前边的结果是后边的输入。亦称逐边裁剪算法第三十四页，共五十页，编辑于2023年，星期日Sutherland-Hodgman算法基本思想是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线，该线把平面分成两个部分:可见一侧，不可见一侧。多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种：第三十五页，共五十页，编辑于2023年，星期日36Sutherland-Hodgman算法情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点PII第三十六页，共五十页，编辑于2023年，星期日37Sutherland-Hodgman算法裁剪结果的构成裁剪边内侧的原顶点多边形的边与裁剪边的交点顺序连接几点说明裁剪算法采用流水线方式，适合硬件实现可推广到任意凸多边形裁剪窗口第三十七页，共五十页，编辑于2023年，星期日38Sutherland-Hodgeman算法缺点：只能正确处理凸多边形，对凹多边形怎么办呢？对凹多边形来说，裁剪后的多边形有两个或者多个分离部分的时候，就对出现多余的线段。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。第三十八页，共五十页，编辑于2023年，星期日图6逐边裁剪法对凹多边形裁剪时可能出现的问题321876954103217654108932174108956原图对左边裁对顶边裁32174108956对右边裁对底边裁↘第三十九页，共五十页，编辑于2023年，星期日40

解决这个问题的方法：一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是Weiler-Atherton算法。第四十页，共五十页，编辑于2023年，星期日41Weiler-Atherton算法裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为SP裁剪多边形：裁剪窗口，记为CP第四十一页，共五十页，编辑于2023年，星期日42约定：SP与CP均用它们顶点的环形链表定义外边界取顺时针方向内边界取逆时针方向(多边形内部总在其右边)Weiler-Atherton算法第四十二页，共五十页，编辑于2023年，星期日43SP和CP把二维平面分成两部分。内裁剪：SP∩CP外裁剪：SP-CPWeiler-Atherton算法裁剪结果由两部分构成：1.SP的部分边界2.CP的部分边界且在交点处边界发生交替即由SP的边界转至CP的边界或由CP的边界转至SP的边界

第四十三页，共五十页，编辑于2023年，星期日44Weiler-Atherton算法主多边形与裁剪多边形交点成对出现分为如下两类：进点：主多边形SP边界由此进入裁剪多边形CP内出点：主多边形边界由此离开裁剪多边形区域.

第四十四页，共五十页，编辑于2023年，星期日进点：SP边界由此进入CP如：I1、I3、I5、I7出点：SP边界由此离开CP如：I2、I4、I6、I8C2C1C3C4S1S2S3S4S5S6I1I2I3I4I5I6I7I8裁剪多边形CP主多边形SP第四十五页，共五十页，编辑于2023年，星期日46Weiler-Athenton算法由任一进点出发，沿SP的边，跟踪检测其与CP