*中点分割算法-求线段与窗口的交点从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm；若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1；再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点；从P1出发找距离P1最近可见点采用上面类似方法。第23页，共50页，星期日，2025年，2月5日*中点分割裁剪算法第24页，共50页，星期日，2025年，2月5日*主要过程只用到加法和除法运算，适合硬件实现，它可以用右移位来代替除法，这样就大大加快了速度。中点分割裁剪算法第25页，共50页，星期日，2025年，2月5日*直线段裁剪直接求交算法Cohen-Sutherland算法中点算法梁友栋－barskey算法第26页，共50页，星期日，2025年，2月5日*Liang-Barsky裁剪算法直线L与区域的交：当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分直线段裁剪(13/15)基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。第27页，共50页，星期日，2025年，2月5日*Liang-Barsky裁剪算法P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分直线段裁剪(14/15)存在可见线段的充要条件不为空集向x轴投影，就得到可见线段上点的坐标的变化范围为左端点右端点第28页，共50页，星期日，2025年，2月5日*Liang-Barsky裁剪算法AB有可见部分的充分必要条件也可表示为直线段裁剪(15/15)第29页，共50页，星期日，2025年，2月5日*二维线段裁剪直线段裁剪直接求交算法Cohen-Sutherland算法中点算法梁友栋－barskey算法多边形裁剪Sutherland-Hodgman算法Weiler-Atherton算法第30页，共50页，星期日，2025年，2月5日多边形裁剪用直线段裁剪算法，可以吗？新的问题：图1因丢失顶点信息而无法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它图1因丢失顶点信息而无法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段第31页，共50页，星期日，2025年，2月5日12123(a)(b)(c)AB图3裁剪后的多边形顶点形成的几种情况分裂为几个多边形多边形裁剪第32页，共50页，星期日，2025年，2月5日*关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列常用的方法Sutherland-Hodgman算法Weiler-Atherton算法第33页，共50页，星期日，2025年，2月5日*Sutherland-Hodgman算法分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：前边的结果是后边的输入。亦称逐边裁剪算法第34页，共50页，星期日，2025年，2月5日Sutherland-Hodgman算法基本思想是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线，该线把平面分成两个部分:可见一侧，不可见一侧。多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种：第35页，共50页，星期日，2025年，2月5日*第1页，共50页，星期日，2025年，2月5日*图形裁剪直线段的裁剪多边形的裁剪第2页，共50页，星期日，2025年，2月5日*图形裁剪裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。第3页，共50页，星期日，2025年，2月5日*裁剪的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交裁剪、覆盖第4页，共50页，星期日，2025年，2月5日*裁剪窗口矩形、圆形、一般多边形被裁剪对象线段、多边形、曲线、字符裁剪的