ch06二维观察与裁剪2010.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Sutherland-Hodgman算法 例:考虑如图所示的多边形,其顶点由下表,裁剪窗口为一正方形,其边界为 xl=-1, xr=1, yb=-1, yt=1 p1 p2 p3 p4 p5 p6 p7 p8 p9 顶点 坐标 顶点 坐标 P1 (1/2,-3/2) P6 (1/2,0) p2 (-2,-3/2) p7 (1/2,3/2) P3 (-2,-2) P8 (-3/2,3/2) p4 (3/2,2) p9 (-3/2,1/2) p5 (3/2,0) Sutherland-Hodgman算法 p1 p2 p3 p4 p5 p6 p7 p8 p9 对左边裁剪 对顶边裁剪 对右边裁剪 对底边裁剪 q1 最终结果 q2 q7 q8 q9 q6 q3 q5 q4 Sutherland-Hodgema算法小结 对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。 解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。而是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。 思考： 如何推广到任意凸多边形 裁剪窗口？ Sutherland-Hodgman算法 裁剪窗口 内 内 内 内 内 外 外 外 外 外 Weiler-Athenton算法 裁剪窗口为任意多边形(凸、凹、带内环)的情况： 主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为B P0 P1 P2 P3 P4 P1 P2 P3 P4 P0 P0 P1 P2 P3 Q0 Q1 Q2 裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界 Weiler-Athenton算法 多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ） 外环：逆时针 内环：顺时针 四个区域 ： 内裁剪结果： 外裁剪结果： 如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类： 进点：主多边形边界由此进入裁剪多边形内 如，I1,I3, I5, I7, I9, I11 出点：主多边形边界由此离开裁剪多边形区域. 如， I0,I2, I4, I6, I8, I10 Weiler-Athenton算法 P0 P1 P2 P3 P4 P5 Q0 Q1 Q2 Q3 q0 q1 q2 q3 I0 I1 I2 I3 I4 I6 I7 I8 I9 I10 I11 I5 Weiler_Athenton裁剪算法（内裁剪）步骤： 1、建立主多边形和裁剪多边的顶点表． 2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。 3、裁剪 如果存在没有被跟踪过的交点，执行以下步骤： Weiler-Athenton算法 (1) 建立空的裁剪结果多边形的顶点表 (2) 选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中 (3) 如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界． (4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点． (5) 将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界） (6) 重复(4)、(5)直至回到起点 Weiler-Athenton算法 Q0 I6 I7 Q1 I8 I9 Q2 I10 I11 Q3 I4 I5 Q0 q0 I3 q1 I2 q2 I1 q3 I0 q0 Weiler-Athenton算法 裁剪多边形表 P0 I7 I0 P1 I1 I8 P2 I9 I10 P3 I11 I2 P4 I3 I4 P5 I5 I6 P0 主多边形表 P0 P1 P2 P3 P4 P5 Q0 Q1 Q2 Q3 q0 q1 q2 q3 I0 I1 I2 I3 I4 I6 I7 I8 I9 I10 I11 I5 P0 P1 P2 P3 P4 P5 Q0 Q1 Q2 Q3 q0 q1 q2 q3 I0 I1 I2 I3 I4 I6 I7 I8 I9