第五讲二维裁剪 51直线段裁剪 直接求交算法; Cohen- Sutherland算法; Nichol-Lee- Nichol算法 中点算法 52多边形裁剪 Sutherland Hodgman算法 Weiler- Atherton算法 53字符裁剪 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 1 第五讲 二维裁剪 5.1 直线段裁剪 直接求交算法； Cohen-Sutherland算法； Nicholl-Lee-Nicholl算法 中点算法 5.2 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 5.3 字符裁剪
直线段裁剪(1/18) 裁剪的目的 判断图形元素是否落在裁剪窗口之内并找出 其位于内部的部分 裁剪的处理的基础 图元关于窗口内外关系的判别 图元与窗口的求交 假定条件 矩形栽剪窗口:min,xmax| Xlymin, ymax 待裁剪线段:(xo)P(x12y1) 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 2 直线段裁剪(1/18) • 裁剪的目的 – 判断图形元素是否落在裁剪窗口之内并找出 其位于内部的部分 • 裁剪的处理的基础 – 图元关于窗口内外关系的判别 – 图元与窗口的求交 • 假定条件 – 矩形裁剪窗口：[xmin,xmax]X[ymin,ymax] – 待裁剪线段： P x y P x y 0 0 0 1 1 1 ( , ) ( , )
直线段栽剪(2/18) 待裁剪线段和窗口的关系 -线段完全可见 -显然不可见 线段至少有一端点在窗口之外,但非显然不 可见 为提高效率,算法设计时应考虑 (一)快速判断情形(1)(2) 二)设法减少情形(3)求交次数和每次求交时所需的计算量 Xmin Xm ax 匕大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 3 直线段裁剪(2/18) • 待裁剪线段和窗口的关系 – 线段完全可见 – 显然不可见 – 线段至少有一端点在窗口之外，但非显然不 可见 为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计算量
直线段裁剪3/18) 点裁剪 点(x,y)在窗口内的充分必要条件是: xmn≤x≤Xmax ymin<y≤ymax 问题:对于任何多边形窗口,如何判别? 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 4 直线段裁剪(3/18) • 点裁剪 – 点(x, y)在窗口内的充分必要条件是： 问题：对于任何多边形窗口，如何判别？ x min x x max y min y y max
直接求交算法 2直线与窗口边都<,<取 先全可见 写成参数形式, =2 在密口内部?>y=R气求玄点ct 求参数值 为可见部分 参见P109 <显然不可见 不可 <Q与窗口有交少> 不可见 求交点0、1 exit 04即为可见部分 exit 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 5 直接求交算法 直线与窗口边都 写成参数形式， 求参数值。 参见P109