第五部分图形变换与裁剪三

1、计算机学院苏小红xxxminmaxyyyminmaxpxyp xy000111(,)(,)为提高效率，算法设计时应考虑：为提高效率，算法设计时应考虑：1. 快速判断情形快速判断情形(1)(2)；2. 设法减少情形设法减少情形(3)求交次数和每次求交时所需的计算量求交次数和每次求交时所需的计算量(编码算法)算法步骤：算法步骤：第一步第一步 判别线段两端点是否都落在窗口内，如果是，判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步；则线段完全可见；否则进入第二步；第二步第二步 判别线段是否为显然不可见，如果是，则裁判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步

2、剪结束；否则进行第三步 ；第三步第三步 求线段与窗口边延长线的交点，这个交点将求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。线段分为两段，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断，对余下的另一段重新进行第一步，第二步判断， 直至结束直至结束 裁剪过程是递归的。elseyyct0max1当elsexxcr0max1当elsexxcl0min1当elseyycb0min1当100000010010000001001001010101101010窗口bca对于那些非完全可见、又非完全不可见的线段，需要对于那些非完全可见、又非完全不可见的线

3、段，需要求交求交，求交前，求交前先测试先测试与窗口哪条边所在直线有交？与窗口哪条边所在直线有交？(按序判断端点编码中各位的值按序判断端点编码中各位的值clctcrcb） 1）特点：用编码方法可快速判断线段特点：用编码方法可快速判断线段- 完全可见和显然不可见。完全可见和显然不可见。 2）特别适用二种场合：）特别适用二种场合： 大窗口场合大窗口场合 窗口特别小的场合窗口特别小的场合 中点分割法p2p1 p2是离是离p1点最远的可见点点最远的可见点pmp1用用p1pm代替代替p1p2p2p2用用pmp2代替代替p1p2pmp1 p4p1p3p2ymaxyminxminxmaxrtsulabas是一

4、维窗口是一维窗口ts中的可见部分中的可见部分q,;,;,maxminmaxmin4321yyxxlppppl口),;,(),;,(maxminmaxminyylxxlturs p4p1p3p2ymaxyminxminxmaxrtsulabas是一维窗口是一维窗口ts中的可见部分中的可见部分tursab),max(),max(,min),min(),min(,maxmaxminutbautbaxxxxxxxxxxx),max(),max(,min),min(),min(,maxmaxminutbautbaxxxxxxxxxxxx左端点左端点右端点右端点),max(),max(,min),min(

5、),min(,maxmaxminutbautbaxxxxxxxxxx),min(,maxminbaxxxl ),max(,minmaxbaxxxr rxxxxlrlutut),min(),max(多边形裁剪-1/2图图1 因丢失顶点信息而去法确定裁剪区域因丢失顶点信息而去法确定裁剪区域abab图图2 原来封闭的多边形变成了孤立的线段原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它边界不再封闭，需要用窗口边界的恰当部分来封闭它12123(a)(b)(c)ab图图3 裁剪后的多边形顶点形成的几种情况裁剪后的多边形顶点形成的几种情况分裂为几个多边形分裂为几个多边形多边形

6、裁剪-2/2sutherland-hodgman算法-1/4：亦称亦称逐边裁剪算法逐边裁剪算法sutherland-hodgman算法-2/4 线段与当前裁剪边的位置关系线段与当前裁剪边的位置关系可见一侧可见一侧窗口窗口(a) 输出输出pi+1当前裁剪边pi+1pi可见一侧可见一侧窗口窗口(a) 无输出无输出当前裁剪边pi+1pi可见一侧可见一侧窗口窗口(a) 输出输出i当前裁剪边pi+1pi可见一侧可见一侧窗口窗口(a) 输出输出i和和pi+1当前裁剪边pi+1pisutherland-hodgman算法-3/4：优点：优点：裁剪算法采用流水线方式，适合硬件实现。裁剪算法采用流水线方式，适合

7、硬件实现。可推广到任意凸多边形裁剪窗口可推广到任意凸多边形裁剪窗口sutherland-hodgman算法-4/4存在的问题图6 逐边裁剪法对凹多边形裁剪时可能出现的问题321876954103217654108932174108956原图对左边裁对顶边裁32174108956对右边裁对底边裁c2c1c3c4c8c7c5c6i1i8i2i3i4i5i6i7裁剪结果区域的边界由裁剪结果区域的边界由sp的部分边界和的部分边界和cp的部分边界两部分构成，并且在交点的部分边界两部分构成，并且在交点处边界发生交替，即由处边界发生交替，即由sp的边界转至的边界转至cp的边界，或由的边界，或由cp的边界转至的边界转至sp的边界的边界 c2c1c3c4s1s2s3s4s5s6i1i2i3i4i5i6i7i8裁剪多边形cp主多边形sp算法裁剪后所生成的多边形为算法裁剪后所生成的多边形为i1i2i3s3i4i5i6i7s6i8 i1主多边形表裁剪多边形表s1s2i1s3s4s5s6i2i3i4i5i6i7i8c1c2i3i4c4i8i1i2i5c3i5i6s1i7c1开始结束c2c1c3c4c8c7c5c6s2s1s3s4s8s7s5s6i1i8i2i3i4i5i6i7主多边形表裁剪多边形表s1s2i1i4s4s6i5