北京大学：《计算机图形学》第五讲 二维裁剪

第五讲二维裁剪 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直线与窗口边都y=R气求玄点ct 求参数值 为可见部分 参见P109 不可见 求交点0、1 exit 04即为可见部分 exit 北大计算机系多媒体与人机交互

北大计算机系多媒体与人机交互 5 直接求交算法 直线与窗口边都 写成参数形式， 求参数值。 参见P109

Cohen- Sutherland算法(编码算法) 算法步骤: 二第一步判别线段两端点是否都落在窗口内,如果是, 则线段完全可见;否则进入第二步; 第二步判别线段是否为显然不可见,如果是,则裁 剪结束;否则进行第三步; 第三步求线段与窗口边延长线的交点,这个交点将 线段分为两段,其中一段显然不可见,丢弃。 对余下的另一段重新进行第一步,第二步判断, 直至结束 裁剪过程是递归的。 北大计算机系多媒体与人机交互

北大计算机系多媒体与人机交互 6 Cohen-Sutherland 算法 (编码算法) 算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断， 直至结束 裁剪过程是递归的

Cohen- Sutherland算法(编码算法) 特点:对显然不可见线段的快速判别 编码方法:由窗口四条边所在直线把二维平面分成9个区 域,每个区域赋予一个四位编码,CCCC,上下右左 ly>ymax else dyx max 0001 0000 0010 e ymin 01011010010110 1当x<xmin Xinin xIn ax 0 else 大计算机系多媒体与人机交互 7

北大计算机系多媒体与人机交互 7 Cohen-SutherLand算法(编码算法) – 特点：对显然不可见线段的快速判别 – 编码方法：由窗口四条边所在直线把二维平面分成9个区 域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；     = else y y Ct 0 1 当 max     = else x x Cr 0 1 当 max     = else x x Cl 0 1 当 min     = else y y Cb 0 1 当 min

Cohen- Sutherland算法(编码算法) °端点编码:定义为它所在区域的编码 结论:当线段的两个端点的编码的逻辑“与”非 零时,线段为显然不可见的 y 1001 100011010 H ymaxF- E 0001 0000 ymin ymin 01011010010110 Xmin Xm ax Xmin Xm ax 北大计算机系多媒体与人机交互

北大计算机系多媒体与人机交互 8 Cohen-SutherLand算法(编码算法) • 端点编码：定义为它所在区域的编码 结论：当线段的两个端点的编码的逻辑“与”非 零时 ，线段为显然不可见的

Cohen- Sutherland算法(编码算法) 对于那些非完全可见、又非显然不可见的线段,需要 求交(如,线段AD,求交前先测试与窗口哪条边所在 直线有交?(按序判断端点编码中各位的值 CICtcrcb) 1)特点:用编码方法可快速判断线段 完全可见和显然不可见。 2)特别适用二种场合: 大窗口场合; 窗口特别小的场合(如,光标拾取图形时, 光标看作小的裁剪窗口。)

北大计算机系多媒体与人机交互 9 • 求交测试顺序固定(左上右下） • 最坏情形，线段求交四次。 Cohen-SutherLand算法(编码算法) 对于那些非完全可见、又非显然不可见的线段，需要 求交（如，线段AD)，求交前先测试与窗口哪条边所在 直线有交？(按序判断端点编码中各位的值ClCtCrCb） 1）特点：用编码方法可快速判断线段-- 完全可见和显然不可见。 2）特别适用二种场合： 大窗口场合； 窗口特别小的场合(如, 光标拾取图形时, 光标看作小的裁剪窗口。）

Nicho-Lee- Nichol算法 消除C-S算法中多次求交的情况。 基本想法:对2D平面的更细的划分 2 5 0 2B 北大计算机系多媒体与人机交互 10

北大计算机系多媒体与人机交互 10 Nicholl-Lee-Nicholl算法 • 消除C-S算法中多次求交的情况。 • 基本想法：对2D平面的更细的划分