浙江大学计算机学院：《计算机图形学》课程教学资源（PPT课件）第五章 裁剪、反走样方法

第五章裁剪、反走样方法 裁剪算法 反走样方法 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 1 裁剪算法 反走样方法 第五章 裁剪、反走样方法

二维裁剪 直线段裁剪 直接求交算法 Cohen- Sutherland算法 中点分割算法 参数化裁剪算法 Liang- Barsky算法 多边形裁剪 Sutherland hodgman算法 Weiler- Atherton算法 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 2 二维裁剪 直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点分割算法 参数化裁剪算法 Liang-Barskey算法 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法

裁剪 裁剪:确定图形中哪些部分落在显示区之内, 哪些落在显示区之外,以便只显示落在显示区 内的那部分图形。这个选择过程称为裁剪。 图形裁剪算法,直接影响图形系统的效率。 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 3 裁剪 ◼ 裁剪：确定图形中哪些部分落在显示区之内， 哪些落在显示区之外,以便只显示落在显示区 内的那部分图形。这个选择过程称为裁剪。 图形裁剪算法，直接影响图形系统的效率

点的裁剪 ■图形裁剪中最基本的问题。 假设窗口的左下角坐标为 R L, yB/3 右上角坐标为 (x,y),对于给定点P(x,y) 则P点在窗口内的条件是要 满足下列不等式 XL R ■并且yB<=y<=yr L, yB 否则,P点就在窗口外。 问题:对于任意多边形窗口, 如何判别? 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 4 点的裁剪 ◼ 图形裁剪中最基本的问题。 ◼ 假设窗口的左下角坐标为 (xL,yB),右上角坐标为 (xR,yT)，对于给定点P(x,y), 则P点在窗口内的条件是要 满足下列不等式： xL <= x <= xR ◼ 并且yB <= y <= yT 否则，P点就在窗口外。 ◼ 问题：对于任意多边形窗口， 如何判别？ (xL,yB ) (xR,yT )

直线段裁剪 ■直线段裁剪算法是复杂图形裁剪的基础。复杂 的曲线可以通过折线段来近似,从而裁剪问题 也可以化为直线段的裁剪问题 直接求交算法 Cohen- Sutherland算法 中点算法 梁友栋一 barsky算法 参数化裁剪算法 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 5 直线段裁剪 ◼ 直线段裁剪算法是复杂图形裁剪的基础。复杂 的曲线可以通过折线段来近似，从而裁剪问题 也可以化为直线段的裁剪问题。 直接求交算法 Cohen-Sutherland算法 中点算法 梁友栋－barskey算法 参数化裁剪算法

直接求交算法 Y 2在窗口内部? 在窗口内部 直线与窗口边 完全可见 P=P 写成参数形式“含“率红 求参数值 R显然不可见Y 34为可见部分 不可见 1t E x min 弓不可见 求交点0 exit XImin Xm ax 04即为可见部分 2021/1/21 exit

2021/1/21 浙江大学计算机图形学 6 直接求交算法 直线与窗口边都 写成参数形式， 求参数值

v直线段裁剪 裁剪线段与窗口的关系:(1)线段完全可见;(2) 显然不可见;(3)其它 ■提高裁剪效率: 快速判断情形(1)(2), 对于情形(3),设法减 ym ax 求交次数和每次求E B H 交时所需的计算量。 ymin Xmin 2021/1/21 浙江大学计算机图形学 7

2021/1/21 浙江大学计算机图形学 7 直线段裁剪 ◼ 裁剪线段与窗口的关系：(1)线段完全可见；(2) 显然不可见；(3)其它 ◼ 提高裁剪效率： 快速判断情形(1)(2)， 对于情形(3)，设法减 少求交次数和每次求 交时所需的计算量

Cohen-Sutherland裁剪 ■基本思想 对于每条线段P1P2分为三种情况处理: (1)若P1P2完全在窗口内,则显示该线段P1P2 (2)若P1P2明显在窗口外,则丢弃该线段。 (3)若线段不满足(1)或(2)的条件,则在交点 处把线段分为两段。其中一段完全在窗口外,可弃 之。然后对另一段重复上述处理 为快速判断,采用如下编码方法: 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 8 Cohen-Sutherland裁剪 ◼ 基本思想： 对于每条线段P1P2分为三种情况处理: （1）若P1P2完全在窗口内，则显示该线段P1P2。 （2）若P1P2明显在窗口外，则丢弃该线段。 （3）若线段不满足（1）或（2）的条件，则在交点 处把线段分为两段。其中一段完全在窗口外，可弃 之。然后对另一段重复上述处理。 ◼ 为快速判断，采用如下编码方法：

v Cohen- Sutherland裁剪 实现方法: A 10011001010 00010000 0010 B 01010100 0110 将窗口边线两边沿长,得到九个区域,每一个区 域都用一个四位二进制数标识,直线的端点都 按其所处区域赋予相应的区域码,用来标识出 端点相对于裁剪矩形边界的位置。 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 9 实现方法： 将窗口边线两边沿长，得到九个区域，每一个区 域都用一个四位二进制数标识，直线的端点都 按其所处区域赋予相应的区域码，用来标识出 端点相对于裁剪矩形边界的位置。 1001 0001 0101 1000 0000 0100 1010 0010 0110 A B C D Cohen-Sutherland裁剪

Cohen- Sutherland裁剪 ■将区域码的各位从右到左编号,则坐标区 域与各位的关系为: 上下右左 100110001010 000100000010 任何位赋值为1,代表端点落在相应的位 置上,否则该位为0。若端点在剪取矩形 010101000110 内,区域码为000如果端点落在矩形的 左下角,则区域码为0101。 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 10 Cohen-Sutherland裁剪 ◼ 将区域码的各位从右到左编号，则坐标区 域与各位的关系为： 上 下 右 左 X X X X 任何位赋值为1，代表端点落在相应的位 置上，否则该位为0。若端点在剪取矩形 内，区域码为0000。如果端点落在矩形的 左下角，则区域码为0101