计算机科学与技术专业课程 计算机图形学 宋传鸣 chmsong@lnnu.edu.cn 辽宁师范大学计算机与信息技术学院

光栅图形的基本概念 光栅图形的本质是点阵表示,采用面着色,使得画面明暗自然、色彩丰富 与线框图相比:更加生动、直观、真实感强 基本概念 扫描转换填充 区域填充 字符表示 线框平面多边形 着色的平面多边形 线框多边形物体 填充多边形物体 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

光栅图形的基本概念 通用图形软件包中有一种输出图元:填充图元 实心或图案填充的多边形区域 可能有其它种类的填充区域图元,但多边形有线性边界,更容易处理 二维多边形区域填充是三维面着色的基础 多边形就是用一系列首尾相连的线段构成图形.图形学中的多边形指的是无自相交的简单多边形 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

光栅图形的基本概念 多边形又分为两大类:凸多边形与凹多边形 凸多边形是指这样一类多边形:如果在多边形内任找两个点,将这两个点用线段连接后,此线段上所有的点都在多边形内 凹多边形就是非凸多边形 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” 凸多边形 凹多边形

多边形的两种表示方式 顶点表示:用多边形的顶点序列来刻画多边形 优点:直观,几何意义强,占空间少,易于进行几何变换,被广泛应用于各种几何造型系统中 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” 多边形的顶点表示

多边形的两种表示方式 顶点表示:用多边形的顶点序列来刻画多边形 优点:直观,几何意义强,占空间少,易于进行几何变换，被广泛应用于各种几何造型系统中 基本概念 扫描转换填充 区域填充 字符表示 P0 P3 P2 P1 glBegin(GL_POLYGON); glVertex3f (0.25, 0.25, 0.0); glVertex3f (0.75, 0.25, 0.0); glVertex3f (0.75, 0.75, 0.0); glVertex3f (0.25, 0.75, 0.0); glEnd(); 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

? 多边形的两种表示方式 顶点表示:用多边形的顶点序列来刻画多边形 点阵表示:用多边形内部的像素的集合刻画多边形 优点:直观,几何意义强,占空间少,易于进行几何变换，被广泛应用于各种几何造型系统中 不足:难以判断哪些像素位于多边形内部不能直接用于多边形着色 点阵表示:用多边形内部的像素的集合刻画多边形 优点:便于用帧缓冲器(Frame buffer)表示图形,是光栅显示系统显示时所需的表示形式 不足:失去了很多重要几何信息（如边界、顶点等),占用存储空间多 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” ? 多边形的顶点表示 多边形的点阵表示

多边形的扫描转换 大多数图形学应用采用顶点序列表示多边形,而顶点表示又不能直接用于显示 多边形的扫描转换:把顶点表示转换为点阵表示 从多边形的给定边界出发,求出其内部的各个像素 并给帧缓冲器中各个对应元素设置相应灰度或颜色 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” 多边形的顶点表示 多边形的点阵表示

逐点判断算法 基本思路:逐个像素判别其是否位于多边形内部 射线法:从当前像素发射一条射线,计算射线与多边形的交点个数 内部:奇数个交点 外部:偶数个交点 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

逐点判断算法 基本思路:逐个像素判别其是否位于多边形内部 射线法:从当前像素发射一条射线，计算射线与多边形的交点个数 不足: 内部:奇数个交点 外部:偶数个交点 不足: 必须要作一些额外处理才能确定正确的内部点 速度慢:几十万甚是几百万像素的多边形内外判断，大量的求交、乘除运算 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” 3个或4个交点？ 4个或5个交点？

连贯性原理 如果能够充分利用相邻像素之间的连贯性,避免对像素的逐点判断和求交运算,则会提高填充效率 像素的连贯性包括:区域连贯性、扫描线连贯性和边的连贯性 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

连贯性原理 区域的连贯性是指多边形定义的区域内部相邻的像素具有相同的性质,例如具有相同的颜色 两条扫描线之间的长方形区域被所处理的多边形分割成若干梯形(三角形可以看作退化梯形) 梯形分为两类:多边形内部和多边形外部,并且两类梯形在多边形内部相间排列(相邻的两个梯形必然有一个位于多边形内部，有一个在多边形外部) 如果一个梯形属于多边形内(外),那么该梯形内所有点的均属于多边形内(外) 效率提高的根源:逐点判断区域判断 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

连贯性原理 扫描线连贯性是区域连贯性在一条扫描线上的反映 扫描线与多边形的交点个数为偶数(1,2,3,4,5,6) 红色区间(1,2)(3,4)(5,6)位于多边形内部,而其余绿色区间位于多边形外部,并且两类区间相间排列 如果某个交点区间属于多边形内(外),那么该区间内所有点均属于多边形内(外) 效率提高的根源：逐点判断区间判断 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

连贯性原理 边的连贯性是直线的线性性质在光栅上的表现 设扫描线与边的交点分别为: 1(x1,y1), 2(x2,y2), 11(x11,y11), 22(x22,y22) 相邻扫描线与多边形的同一条边的交点存在关系: 当知道扫描线与一条边的一个交点之后,通过上述公式可以通过增量算法迅速求出其它交点 边连贯性是连接区域连贯性和扫描线连贯性的纽带 扫描线连贯性＋边连贯性＝区域连贯性 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

奇异点的处理 奇异点是指扫描线与多边形相交于多边形的顶点 极值点:相邻三个顶点的y坐标满足条件:(yi-1-yi)(yi+1-yi)0,即相邻三个顶点位于扫描线的同一侧 非极值点:相邻三个顶点的y坐标满足如下条件: (yi-3-yi-2)(yi-1-yi-2)<0,即相邻三个顶点位于扫描线的两侧 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 y=yi (xi-2,yi-2) (xi-3,yi-3) y=yi-2 (xi-2,yi-2) (xi-3,yi-3) 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

奇异点的处理 奇异点是指扫描线与多边形相交于多边形的顶点 极值点:相邻三个顶点的y坐标满足条件:(yi-1-yi)(yi+1-yi)0,即相邻三个顶点位于扫描线的同一侧 非极值点:相邻三个顶点的y坐标满足如下条件: (yi-3-yi-2)(yi-1-yi-2)<0,即相邻三个顶点位于扫描线的两侧 在极值点处,按两个交点计算;在非极值点处,按一个交点计算. 实际计算前对非极值点预处理:将扫描线上方线段截断一个单位,这样扫描线就只与多边形有一个交点 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

多边形扫描转换算法的基本思想 计算扫描线 y = ymin与多边形的交点,通常这些交点由多边形的顶点组成 根据多边形边的连贯性,按从下到上的顺序求得各条扫描线的交点序列 根据区域和扫描线的连贯性判断位于多边形内部的区段 对位于多边形内的直线段进行着色 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

多边形扫描转换过程的示意图 y x 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 P4 P0 P2 P3 P1 P7 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法采用的数据结构 边的数据结构 ymax:边的上端点的y坐标 x:边的下端点x坐标.在活化边链表中表示扫描线与边的交点的x坐标 dx:边的斜率的倒数 next:指向下一条边的指针 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法采用的数据结构 分类边表ET(Sorted Edge Table):按边的下端点的纵坐标y对非水平边进行分类的指针数组 下端点的纵坐标等于i的边归入第i类 同一类中,各边按x值(x值相等时,按dx的值)递增的顺序排列 水平边不加入分类边表中 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 非极值点 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法采用的数据结构 活化边链表AEL(Active Edge List):活化链表由与当前扫描线相交的边组成 活化边链表与分类边表的不同 记录了多边形的边沿扫描线的交点序列 根据边的连贯性不断刷新交点序列 活化边链表与分类边表的不同 分类边表记录初始状态 活化边表随扫描线的移动而动态更新 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 ymax xcur dx 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法的主要步骤 初始化y:取扫描线纵坐标y的初始值为ET中非空元素的最小序号 (y=2) 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法的主要步骤 初始化y:取扫描线纵坐标y的初始值为ET中非空元素的最小序号 (y=2) AEL初始化:将边的活化链表AEL设置为空 按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行如下步骤,直到ET和AEL表都变成空为止 如果ET中的第y类元素非空,则将该类的所有边取出并插入AEL表中(同时将ET中相应的边表删除),AEL中的各边按照x值(x值相等时,按dx值)递增方向排序 对于当前扫描线,若AEL非空,则将其中的边交点两两依次配对.每一交点区间位于多边形内部,依次对这些区间上的像素按多边形属性着色 将边的活化链表AEL中满足y=ymax的边删除 将AEL中剩下的每一条边的x累加dx,即:x=x+dx 将当前扫描线的纵坐标值y累加,即y=y+1 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法实例 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

算法分析 优点 不足 充分利用多边形的区域、扫描线和边的连贯性,避免了反复求交的大量运算 算法的数据结构和程序结构复杂 对各种表的维持和排序开销太大,适合软件实现而不适合硬件实现 基本概念 扫描转换填充 逐点判别法 有序边表法 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

点阵表示的区域填充 区域的定义:已经表示成点阵的像素集合 区域的内部表示:把给定区域内的像素枚举出来 区域内所有像素都着同一种颜色 区域边界像素不能着上述颜色 区域的边界表示:把区域边界上的像素枚举出来 边界上所有像素都着同一种颜色 区域内部像素不能着上述颜色 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” 区域的内点表示 区域的边界表示

区域填充原理 基本思路:从区域的一个内点(称为“种子点”)开始,赋予指定的颜色,然后将该颜色扩展到整个区域 它是对区域重新着色的过程(改变区域颜色或图像) 对边界表示的区域进行填充为边界填充 对内点表示的区域进行填充为泛滥填充 基本过程:从种子点开始,先检测该点的颜色,如果它与边界色和填充色均不相同,就用填充色填充该点,然后用相同方法处理相邻位置的点,直到处理完所有像素 区域填充算法要求区域是连通的 只有在连通区域内,才有可能将种子点的颜色扩展到区域内的其它点 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

区域类型 四连通区域:区域内任意两个像素,从一个像素出发,可以通过上、下、左、右四种运动,到达另一个像素 八连通区域:区域内任意两个像素,从一个像素出发,可以通过水平、垂直、正对角线、反对角线八种运动,到达另一个像素 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

区域类型 四连通区域:区域内任意两个像素,从一个像素出发,可以通过上、下、左、右四种运动,到达另一个像素 八连通区域:区域内任意两个像素,从一个像素出发,可以通过水平、垂直、正对角线、反对角线八种运动,到达另一个像素 两种连通区域的实例 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” 四连通区域实例 八连通区域实例

区域类型 四连通区域:区域内任意两个像素,从一个像素出发,可以通过上、下、左、右四种运动,到达另一个像素 八连通区域:区域内任意两个像素,从一个像素出发,可以通过水平、垂直、正对角线、反对角线八种运动,到达另一个像素 两种连通区域的实例 四连通和八连通区域的关系 四连通区域  八连通区域 四连通区域的边界是八连通区域 八连通区域的边界是四连通区域 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

内部表示区域种子填充算法 假设内部表示区域为G,其中的像素原有颜色为OldColor,需要填充的颜色为NewColor 具体算法如下(四连通区域): 基本概念 扫描转换填充 区域填充 泛滥填充 边界填充 扫描线种子 字符表示 Flood_Fill_4(int x, int y, int OldColor, int NewColor) { if(GetPixel(x,y) ==OldColor ) //GetPixel(x,y)返回(x,y)的颜色 SetPixel(x, y, NewColor); //将(x,y)的添上新颜色 Flood_Fill_4(x-1, y, OldColor, NewColor); Flood_Fill_4(x, y+1, OldColor, NewColor); Flood_Fill_4(x+1, y, OldColor, NewColor); Flood_Fill_4(x, y-1, OldColor, NewColor); } 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

内部表示区域种子填充算法 假设内部表示区域为G, 像素原有颜色为OldColor,需要填充的颜色为NewColor 具体算法如下(四连通区域): 基本概念 扫描转换填充 区域填充 泛滥填充 边界填充 扫描线种子 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

边界表示区域种子填充算法 具体算法如下(四连通区域): 基本概念 扫描转换填充 区域填充 泛滥填充 边界填充 扫描线种子 字符表示 Fill_Boundary_4_Connnected(x, y, BoundaryColor, NewColor) { int Color=getpixel(x,y); if(Color != BoundaryColor && Color!= NewColor ) putpixel(x, y, NewColor); // 将像素(x,y)置成填充颜色 Fill_Boundary_4Connnected(x, y+1, BoundaryColor, NewColor)； Fill_Boundary_4Connnected(x, y-1, BoundaryColor, NewColor)； Fill_Boundary_4Connnected(x-1, y, BoundaryColor,NewColor)； Fill_Boundary_4Connnected(x+1, y, BoundaryColor,NewColor)； } 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

边界表示区域种子填充算法 具体算法如下(四连通区域): 基本概念 扫描转换填充 区域填充 泛滥填充 边界填充 扫描线种子 字符表示 Fill_Boundary_4_Connnected(x, y, BoundaryColor, NewColor) { int Color=getpixel(x,y); if(Color != BoundaryColor && Color!= NewColor ) putpixel(x, y, NewColor); // 将像素(x, y)置成填充颜色 Fill_Boundary_4Connnected(x, y+1, BoundaryColor, NewColor)； Fill_Boundary_4Connnected(x, y-1, BoundaryColor, NewColor)； Fill_Boundary_4Connnected(x-1, y, BoundaryColor,NewColor)； Fill_Boundary_4Connnected(x+1, y, BoundaryColor,NewColor)； } 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

扫描线种子填充算法 种子填充算法过程非常简单,但需要深度递归,算法效率低,并且空间消耗很高 解决方法是使堆栈最小化,在任意不间断的扫描线中只取一个种子像素,称为扫描线种子填充算法 扫描线种子填充算法适用于边界定义的四连通区域 算法的主要步骤 初始化:清空堆栈,将给定的种子压入堆栈 出栈:从包含种子象素的栈中弹出种子像素 区间填充:沿着扫描线对种子像素的左右像素进行填充,直到遇到边界像素为止,这样就将种子所在扫描线中的元素填充 进栈:找到区间内的最左和最右元素,并在二者之间 检查与当前扫描线相邻的上、下两条扫描线是否全为边界像素或正填充过的像素.若不是,则把每一区间的最右像素作为种子压入堆栈,直至栈空,算法结束 基本概念 扫描转换填充 区域填充 泛滥填充 边界填充 扫描线种子 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

扫描线种子填充算法 基本概念 扫描转换填充 区域填充 泛滥填充 边界填充 扫描线种子 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

多边形扫描转换与区域填充比较 基本思想不同 对边界的要求不同 多边形扫描转换将多边形顶点表示转换为点阵表示,扫描过程利用了多边形的各种连贯性 区域填充只改变区域的颜色,不改变区域的表示方法.填充过程利用了区域的连贯性 对边界的要求不同 多边形扫描转换只要求每一条扫描线与多边形有偶数个交点 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率” 多边形扫描转换允许边界 区域填充允许边界

多边形扫描转换与区域填充比较 基本思想不同 对边界的要求不同 出发点不同 多边形扫描转换将多边形顶点表示转换为点阵表示,扫描过程利用了多边形的各种连贯性 区域填充只改变区域的颜色,不改变区域的表示方法.填充过程利用了区域的连贯性 对边界的要求不同 多边形扫描转换只要求每一条扫描线与多边形有偶数个交点 区域填充中,四连通区域必须是封闭的八连通边界,八连通区域必须是封闭的四连通边界 出发点不同 区域填充:知道需要区域内一个种子点(复杂计算) 多边形扫描转换:没有要求 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

字符的表示与输出 字符包括数字、字母和汉字等符号,在计算机中由数字编码唯一标识 国际字符编码:ASCII (American Standard Code for Information Interchange) 7位二进制编码,共128个字符,包括字母,标点,运算符及一些特殊符号 一个字符的ASCII码用一个字节(8位)表示,其最高位不用或作为奇偶校验位 汉字编码:国家标准信息交换编码GB 2312-80 所有字符由94×94矩阵表示,行称为区,列称为位 一个字符由一个区码和一个位码共同标识.区码和位码分别需要7个二进制,汉字字符国标码占两个字节 汉字6763个、图形符号682个 通常,采用字符中冗余的最高位来标识一个字节所表示的码.0为ASCII码,1为汉字编码 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

点阵字符的存储 点阵字符是由一个位图表示 字位为1表示字符笔画经过此位,对应像素应设置为字符颜色;否则,对应像素应设置为背景色 字型7×9、9×16、16×24等指的是位图的尺寸 一个16×24的汉字需要16×24=384位,共48个字节.常用汉字有6763个,从而存储这种型号需要6763×48≈324K字节 在实际应用中需要多种字体(如宋体、揩体等),每种字体又有十多种型号 汉字字库所占的存 储空间相当庞大 采用压缩技术 轮廓字形法 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

点阵字符的显示 从给定字符编码,到在屏幕上将它显示出来,需要经历两个步骤 从字库中将它的位图检索出来.由于表示同一型号字符的位图所占空间大小相同,可以直接将一个字符在字库中的位置计算出来 将检索到的位图写到帧缓存中,这可以利用光栅系统的位拷贝功能 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

矢量字符的存储 字符矢量表示中,记录的是字符的笔画信息 表示一个矢量字符最终只需要所有的端点坐标信息及其是否连线的标志 选一个正方形网格作为字符的局部坐标空间,网格大小可取:16×16、32×32、64×64等 对一个字符来说,它由构成它的笔画组成,而每一笔又由其两端确定 表示一个矢量字符最终只需要所有的端点坐标信息及其是否连线的标志 实际的矢量字符的存储结构要加上一些管理信息和字型信息等 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”

点阵字符和矢量字符的比较 字符变换不同 占用空间不同 矢量字符美观 表示点阵字符的是位图,对点阵字符的变换要对位图中的每一个像素进行, 放大或旋转时会失真 表示矢量字符的是端点坐标,对矢量字符的变换是对端点的变换,是图形的几何变换,不会影响显示效果 占用空间不同 矢量字符只需保存一套字符,不同型号的字符可通过相应的几何变换来产生.因此,矢量字符占用空间较少 矢量字符美观 除了直线段外,还可以用二次曲线段、三次曲线段等来表示笔画,使字符更加美观 矢量字符占用空间小、美观、变换方便等优点得到越来越广泛的应用,特别是在排版、软件和工程图软件中它几乎已经完全取代了点阵字符 基本概念 扫描转换填充 区域填充 字符表示 线画图元：用矢量表示的二维图形。其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示，其过程就是扫描转换过程 填充图元：用点阵表示的二维图元。其核心是如何确定给定区域内构成图形的内部的点的表示 光点称为“像素”，其数量称为“分辨率”