第二章 基本图形生成算法.pptx

第二章基本图形生成算法 裁剪一、裁剪的策略及原理二、二维线段的裁剪三、多边形的裁剪四、字符的裁剪
二维图形的显示流程图
二维图形的裁剪
裁剪的策略及原理
1 分类
直线段裁剪
直接求交算法
Cohen-Sutherland算法
中点分割算法
参数化裁剪算法
Liang-Barskey算法
多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法
2 裁剪
裁剪:确定图形中哪些部分落在显示区之内,哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。
图形裁剪算法,直接影响图形系统的效率。
3 裁剪的策略及原理
裁剪的策略:
(1) 裁剪及窗口-视图变换的先后。
“先裁剪后变换”可以避免窗口外的图形进行无效的窗口-视图变换。
(2) 图形的生成与裁剪的先后。
“先生成后裁剪”只需要简单的直线段裁剪算法,但可能造成无效的生成运算。
“先裁剪后生成”可以避免对那些被裁剪的图形进行无效的生成运算,却要采用比较复杂图形(如圆弧,椭圆弧)的的裁剪处理。
裁剪的原理:
(1) 点在区域内外的判断。
(2) 计算图形元素及区域边界的交点。
4 点在区域内外的判断
图形裁剪中最基本的问题。
假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT),对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式:xL <= x <= xR
并且yB <= y <= yT否则,P点就在窗口外。
问题:对于任何多边形窗口,如何判别?
(xL,yB )
(xR,yT )
5 计算图形元素及区域边界的交点
交点的计算比较复杂,可先作BOX测试。
裁剪线段及窗口的关系:(1)线段完全可见;(2)显然不可见;(3)其它
提高裁剪效率:
快速判断情形(1)(2),
对于情形(3),设法减
少求交次数和每次求
交时所需的计算量。
二二维线段的裁剪
分类:
直接求交算法
Cohen-Sutherland裁剪
中点分割裁剪算法
梁友栋-Barsky算法
参数化算法(Cyrus-Beck)
1 直接求交算法
直线及窗口边都
写成参数形式,
求参数值。