文档介绍：裁剪算法
反走样方法
第五章 裁剪、反走样方法
浙江大学信息学院计算机图形学
二维裁剪
直线段裁剪
直接求交算法
Cohen-Sutherland算法
中点分割算法
参数化裁剪算法
Liang-Barskey算法
多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法
浙江大学信息学院计算机图形学
裁剪
裁剪:确定图形中哪些部分落在显示区之内,哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。
图形裁剪算法,直接影响图形系统的效率。
浙江大学信息学院计算机图形学
点的裁剪
图形裁剪中最基本的问题。
假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT),对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式: xL <= x <= xR
并且yB <= y <= yT 否则,P点就在窗口外。
问题:对于任何多边形窗口,如何判别?
(xL,yB )
(xR,yT )
浙江大学信息学院计算机图形学
直线段裁剪
直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似,从而裁剪问题也可以化为直线段的裁剪问题。
直接求交算法
Cohen-Sutherland算法
中点算法
梁友栋-barskey算法
参数化裁剪算法
浙江大学信息学院计算机图形学
直线段裁剪
裁剪线段与窗口的关系:(1)线段完全可见;(2)显然不可见;(3)其它
提高裁剪效率:
快速判断情形(1)(2),
对于情形(3),设法减
少求交次数和每次求
交时所需的计算量。
浙江大学信息学院计算机图形学
直接求交算法
直线与窗口边都
写成参数形式,
求参数值。
浙江大学信息学院计算机图形学
Cohen-Sutherland裁剪
基本思想:
对于每条线段P1P2分为三种情况处理:
(1)若P1P2完全在窗口内,则显示该线段P1P2。
(2)若P1P2明显在窗口外,则丢弃该线段。
(3)若线段不满足(1)或(2)的条件,则在交点处把线段分为两段。其中一段完全在窗口外,可弃之。然后对另一段重复上述处理。
为快速判断,采用如下编码方法:
浙江大学信息学院计算机图形学
实现方法:
将窗口边线两边沿长,得到九个区域,每一个区域都用一个四位二进制数标识,直线的端点都按其所处区域赋予相应的区域码,用来标识出端点相对于裁剪矩形边界的位置。
1001
0001
0101
1000
0000
0100
1010
0010
0110
A
B
C
D
Cohen-Sutherland裁剪
浙江大学信息学院计算机图形学
Cohen-Sutherland算法
将区域码的各位从右到左编号,则坐标区 域与各位的关系为:
上下右左 X X X X 任何位赋值为1,代表端点落在相应的位置上,否则该位为0。若端点在剪取矩形内,区域码为0000。如果端点落在矩形的左下角,则区域码为0101。
浙江大学信息学院计算机图形学