Cohen- Sutherland算法(编码算法) 算法步骤: 二第一步判别线段两端点是否都落在窗口内,如果是, 则线段完全可见;否则进入第二步; 第二步判别线段是否为显然不可见,如果是,则裁 剪结束;否则进行第三步; 第三步求线段与窗口边延长线的交点,这个交点将 线段分为两段,其中一段显然不可见,丢弃。 对余下的另一段重新进行第一步,第二步判断, 直至结束 裁剪过程是递归的。 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 6 Cohen-Sutherland 算法 (编码算法) 算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断， 直至结束 裁剪过程是递归的
Cohen- Sutherland算法(编码算法) 特点:对显然不可见线段的快速判别 编码方法:由窗口四条边所在直线把二维平面分成9个区 域,每个区域赋予一个四位编码,CCCC,上下右左 ly>ymax else dy<ymn 0 else 1001 1000 1010 ym ax Ix>x 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平面的更细的划分