1
余 敦 辉湖北大学 数计学院计算机图形学
2
第五章 基本图形生成算法
5.4 区域填充填充共有如下三种：
1、有序边表法：
优点：对每个元素值访问一次，输入输出要求降为最少，适于软件实现；
2、边填充算法（正负相消算法）：适于硬件实现；
边填充分类,栅栏填充；
边标志法；
3、种子填充：为一个递归算法。
可分为 漫水法 简单种子填充种子填充法扫描线填充
3
第五章 基本图形生成算法
5.4 区域填充区域,指相互连通的一组象素的集合。区域通常由一个封闭的轮廓线来定义，处于一个封闭轮廓线内的所有象素点构成一个区域。
区域填充,将区域内的象素置成新的颜色，新的颜色可以是常数，表示填以某种颜色；也可以是变量，
表示填充的是图案。
区域填充需解决的问题：
1）确定需要填充哪些象素；
2）确定用什么颜色；
4
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充顶点表示,用多边形的顶点序列来刻划多边形点阵表示,用位于多边形内的象素的集合来刻划多边形多边形的扫描转换或多边形的填充
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 0
p 2
p 0 p 6
5
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 1）凸多边形和凹多边形凸多边形：对于多边形内任意两点，连接他们的直线上的所有点均在该多边形内部，该多边形即为凸多边形；
凹多边形：不满足上述条件的多边形即为凹多边形；
（ 2）多边形的内点和外点：
内点：填充成固定颜色或图案；
外点：不填充；
边界点：作为内点还是外点视要求而定。
6
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 3）内外点判定 —— 奇偶性原理从无穷远处向该点引一条射线，如果这条射线与多边形的交点为奇数时，此点为内点，否则为外点。
推导,当射线与多边形相交奇数次后，线上点都是内点，偶数次相交后线上点都是外点。
特例,顶点是交点。
若射线与多边形顶点相交
a）共享顶点的两条边分别位于扫描线的两边，交点算一个。
b）共享顶点的两条边都位于扫描线的下边，交点算零个。
c）共享顶点的两条边都位于扫描线的上边，交点算二个。
7
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充请分别回答 A～ H点中哪些点需要填充？为什么？
8
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 4）边界处理屏幕坐标顶点在
(0,0),(4,0),(4,3),(0,3)的矩型
0 321 4
1
2
3
0 321 4 5
1
2
3
4
边界上象素的取舍原则：
左闭右开下闭上开
9
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 5）确定扫描线 y=scan
ymin ≤ scan ≤ ymax
原因：所有的边和扫描线求交，
效率很低。因为一条扫描线往往只和少数几条边相交。
如何判断多边形的一条边与扫描线是否相交？
(ymin,ymax)
10
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 6）扫描线的连贯性当前扫描线与各边的交点顺序，与下一条扫描线与各边的交点顺序很可能相同或类似。
只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。
（ 7）边的连贯性当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交。
与当前扫描线相交的边称为活动边（ active edge)，把它们按与扫描线交点 x坐标递增的顺序存入一个链表中，称为活动边表（ AET,Active edge table)
11
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充根据如下分析，得到如下步骤：
对每条扫描线分为 4步 (以扫描线 6为例 )
(1) 求交点，即计算该扫描线与多边形各边的交点
(2) 排序，由于交点不一定由左到右求出，因此将求出的交点按 x 坐标值排序
(3) 交点配对,1与 2,3与 4,… …,每对表示一个区间
(4) 区间填充
12
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 8）数据结构
①,新边表” (有序边表 ) 9
91 2 3 4 5 6 87 1000
1
8
7
6
4
5
3
2
11
0次 0次
2次1次
1 2 3 4
例：对下图的多边形进行填充
13
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充扫描线号
8 ^
7 ^
6
5 ^
4 ^
3
2
1
0 ^
5 2 8
11 0 8 ^
2 0 7 ^
5 -3 2 5 3 3 ^
5 -1.5 7 ^
新边表如下：
14
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
15
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充算法步骤：
(1)初始化：构造边表 ET,将 AET表置空；
(2)将第一个不空的 ET表中的边与 AET表合并；
(3)由 AET表中取出交点对进行填充 。 填充之后删除
y=ymax的边；
(4)yi+1=yi+1,根据 xi+1=xi+1/m计算并修改 AET表,同时合并 ET表中 y=yi+1桶中的边,按次序插入到 AET表中
,形成新的 AET表；
(5)AET表不为空则转 (3),否则结束 。
注：算法见 P182
16
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法
1、正负相消算法：
基本思想,对于每一条扫描线和每条多边形的交点，将该扫描线上交点右方所有的象素取补。对多边形的每一条边作此处理，多边形各边的处理顺序随意。
优点,算法简单缺点,1）每个象素可能被访问多次；
2）输入 /输出量大。
17
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法再例：
18
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法
2,栅栏填充算法栅栏：与扫描线垂直的直线，通常过多边形顶点，且将多边形分成两半方法：对每个扫描线与多边形的交点，将交点与栅栏间的像素取,补”
特点：
方法简单
减少了被重复访问的像素，特别是有多个填充对象时，效果显著
19
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法
3,边标志算法步骤：
1,对多边形的 每一条边 进行扫描转换，即对多边形边界所经过的象素作一个 边界标志 。
2.填充 。对每条与多边形相交的扫描线，按 从左到右 的顺序，
逐个 访问该扫描线上的象素。
取一个 布尔变量 inside来指示当前点的状态，若点在多边形内，
则 inside为真 。若点在多边形外，则 inside为假 。
Inside 的 初始值为假,每当当前访问象素为被打上标志的点，
就把 inside取反 。对未打标志的点,inside不变 。
20
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法分为两个步骤：
(1)打标记
(2)填充
Inside
初值：假遇到标记点：取反真：填充；
假：不填充当用软件实现本算法时,速度与改进的有效边表算法相当,但本算法用硬件实现后速度会有很大提高 。 注：算法见 P184
21
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
1、原理：
假设在多边形区域内部右一象素已知，由此出发找到区域内的所有象素。
2、前提：
区域边界上所有象素均具有某个特定值，区域内部所有象素均不取这一特定值。而边界外的象素则可具有与边界相同的值。
一句话，区域边界上所有象素的值和内部所有象素的值必须要不一样。
22
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
3、区域分类：
四向连通：从区域上任意一点出发，可通过四个方向，即上、
下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素。
八向连通：区域内的每个象素，可以通过左、右、上、下、左上、右上、左下、右下这八个方向的移动的组合来到达。
23
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
A,简单的种子填充算法
1,初始化：种子像素入栈，当栈非空时，重复 2～ 4的步骤
2,栈顶像素出栈
3,将出栈像素置为多边形颜色
4,按右、上、左、下顺序依次检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，
则该像素入栈
5,当堆栈为空时，算法终止注：算法见 P186
例：
则各元素出栈顺序：
S1,2,8,9,3,4,6，
7,5,9,7,4
24
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
B,扫描线种子填充算法为减少像素重复入栈，限定任一扫描线与多边形相交区间，只取一个种子像素
1,初始化：种子像素入栈，当栈非空时，重复 2～ 6的步骤
2,栈顶像素出栈
3,沿扫描线对种子像素的左右像素进行填充，
直至边界，从而填满该区间
4,区间内最左和最右像素分别记为 xL 和 xR
5,在区间 [xL,xR]中检查与当前扫描线相邻的上下两条扫描线是否全为边界或已经填充，
若存在非边界、未填充的像素，将检查区间的最右像素作种子入栈
6,当堆栈为空时，算法终止
25
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理
1,线刷子和方刷子处理线宽线刷子：垂直刷子,水平刷子图5 - 3 9 线刷子
( a ) ( b )
26
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理原理,设直线斜率在 【 － 1,1】 之间，此时可把刷子置成垂直方向，刷子的中点对准直线某一端点，然后让刷子中心往直线的另一端移动，即可刷出具有一定宽度的线。
反之，若直线斜率不在 【 － 1,1】 之间，把刷子置成水平方向即可。
具体实现,略为修改直线的扫描转换算法即可例,当直线斜率在 【 － 1,1】 之间时，把每步迭代的点的上下方半线宽之内的象素全部置为直线颜色即可。
27
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理特点
实现简单,效率高 。
斜线与水平 (或垂直 )线不一样粗 （ 斜线较细 ） 。
当线宽为偶数个象素时,线的中心将偏移半个象素 。
利用线刷子生成线的始末端总是水平或垂直的,看起来不太自然 。
解决：添加,线帽 （ line cap）,
图5 - 4 0 线“帽子”
( a ) 方帽 ( c ) 圆帽( b ) 突方帽
28
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理当比较接近水平的线与比较接近垂直的线汇合时,汇合处外角将有缺口图5-4 1 线刷子 产生的缺口解决：斜角连接 （ miter join）,圆连接 （ round join）,斜切连接 （ bevel join）
图5 - 4 2 线刷子产生的缺口
( a ) 斜角连接 ( b ) 圆连接 ( c ) 斜切连接
29
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理方刷子特点：
方刷子绘制的线条 （ 斜线 ） 比用线刷子所绘制的线条要粗一些方刷子绘制的斜线与水平 （ 或垂直 ） 线不一样粗 （ 斜线较细 ）
方刷子绘制的线条自然地带有一个,方线帽,
图5 - 4 3 方刷子
30
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理原理,把边宽为指定线宽的正方形的中心对准单象素宽的线条上的各个象素，并沿直线作平行移动，即可获得具有线宽的线条。
具体实现,采用区域填充的算法实现 ;
方法,采用与活性边表类似的技术实现：
① 为每条扫描线建一个表，存放该扫描线与线条的相交区间左右端点位置；
② 在每个象素使用方形刷子时，用该方形与各扫描线的相交区间端点坐标去更新原表内端点数据，从而得到线条各角点；
③ 再用直线段把相邻角点连接起来，最后调用多边形填充算法把所得的四边形进行着色，即可得到具有线宽的线条。
31
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.2 圆弧线宽的处理
1、采用线刷子 （见 P192，图 4.4.5）
在经过曲线斜率为 ± 1的点时，必须把线刷子在水平和垂直方向之间切换。
故此：
在曲线接近水平与垂直的地方，线条更粗一些；
在曲线斜率接近 ± 1的地方，线条更细一些；
32
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.2 圆弧线宽的处理
2、采用正方形刷子 （见 P192，图 4.4.6）
原理：无需变换刷子方向，只需顺着单象素宽的轨迹将正方形中心对准轨迹上的象素，把方形内的象素全部用线条颜色填充。
故此：
在曲线接近水平与垂直的地方，线条更细；
在曲线斜率接近 ± 1的地方，线条更粗；
33
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.2 圆弧线宽的处理
3、采用填充法 （见 P193，图 4.4.7）
原理,先绘制圆弧线条的内、外边界，然后在内外边界之间对其填色。
具体方法,
（ 1）可让内外边界都与单象素弧线轨迹距离半线宽；
（ 2）将内外边界之一对准单象素弧线轨迹，另一边界线离开此线一个线宽距离。
34
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.3 线型的处理在绘图应用中常用到的线条有：
点线：表示立体线框中可见的轮廓线；
虚线：表示立体线框中不可见的轮廓线；
点划线：用于表示中心线；
具体画法：
虚线：可通过在实线段之间插入与实线段等长的空白段来显示；
划线：由用户指定各段划线的长度和空白段的长度；
点线：可通过生成很短的划线和等于和大于划线大小的空白段来显示；
点划线：点与等长实线段的交错出现；
35
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.3 线型的处理实现方法：
实心段和中间空白段的长度（
象素数目）可用象素模板
(pixel mask)指定存在问题,如何保持任何方向的划线长度近似地相等解决,可根据线的斜率来调整实心段和中间空白段的象素数目 。
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
a
图5 - 3 8 相同数目象素显示的不等长划线
b
36
第五章 基本图形生成算法
5.6 字符
1）字符,是指数字、字母和汉字等符号，用于图形的标注、
说明等；
2） ASCII:共 128个。
0－ 31 不可见，控制字符。
32－ 127可见（大小写字母，数字，运算符号，标点符号等）
它的编码用一个字节可以表示，最高位为 0；
3）汉字编码,汉字量大，共含六千多个常用汉字、英文字母、
数字和其他图形符号。分为 94个区 94个位。每个汉字的编码由两个字节构成。
“信息交换用汉字编码字符集基本集”
－ GB2312-80
37
第五章 基本图形生成算法
5.6 字符
4）字符库,为了在终端显示器和绘图仪上输出字符，系统中必须装备有相应的字符库。字符库中存储了每个字符的形状信息。
分类：
① 矢量型字符库,采用矢量代码序列表示字符的各个笔画。
输出一个字符时，系统中的字符处理器解释该字符的每个矢量代码，输出对应的矢量，达到产生字符的目的；
适用于：利用笔式绘图仪绘制字符；
② 点阵型字符库,为每个字符产生一个字符掩膜，即表示该字符的象素图案的一个点阵。
适用于：利用终端显示器显示字符
38
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符不同的应用使用不同的方法。
对每个字符定义一个矢量代码序列来描述字符的几何形状
。下面以 AutoCAD中所采用的定义方法为例，介绍矢量字符的原理。
AutoCAD采用一种称为形（ SHAPE）的实体来定义字符的。描述格式如下：
* <形编号 >,<字节数 >,<形名称 >
<字节 1>,<字节 2>,.....,0
39
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符在标题栏中：
形编号,是 1～ 255的整数值；
字节数,表示形定义中包括结束符 0在内的字节数目；
形名称,必须为大写字母方可被调用。否则只作为形的一种解释性信息，不存入存储器，因而不占用存储空间；
描述行,由若干个用逗号隔开的字节组成，并以 0作为行定义的结束字节。每个字节由标识位、低四位和高四位三组数字组成。
① 标志位,带有前缀 0的字节是十六进制，无前缀 0的字节是十六进制，
② 高四位表示矢量的长度，低四位表示矢量方向。
例如 040即表示一 16进制数，其中,4表示矢量的长度,0
表示矢量方向。
40
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符所有矢量都具有
“相同”的长度，
即（ 2）的单位长度是（ 0）的单位长度的?2倍
41
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符例 1,下图中所示的二极管符号的形定义为：
*133,11,DIODE
040,044,04C,042,04C,040,
048,04C,046,04C,0
42
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符例 2：“北京”两字的形定义分别为：
*250,17,BEI
024,049,041,044,038,030,044,2,020,1,05C,031,
039,05C,040,024,0
*251,23,JING
032,2,02C,1,02D,054,028,024,040,02C,028,2,0
1E,1,03E,2,086,1,050,025,02D,040,0
43
第五章 基本图形生成算法
5.6 字符
5.6.2 点阵字符
2,点阵字符西文字符：至少用 5*7的点阵描述,存储需 35位,4个多字节汉文字符：至少用 16*16的点阵描述,存储需 256位,32个字节特殊字符：按需要确定。
二进制数表示的矩阵编码（ ASCII）
问题：信息量大，质量，变换，动画，
解决：压缩，矢量。
44
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术当应用对输入字符的要求较高时（如排版印刷）
，需要高质量的点阵字符。
但由于汉字众多，且每个汉字又有多种字型、字号，故直接存储几乎不可能。
例,设汉字为 72× 72点阵，每个汉字支持 10种字型（
宋体、仿宋体等），每种字型又含 10种字号。则整个汉字字库大小为
（ 72× 72× 6763× 10× 10） /8 ＝ 440MB
45
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术解决方法：采用压缩技术对字型数据压缩后再存储，使用时将压缩的数据还原为字符位图矩阵。
常见压缩方法：
1、黑白段压缩法：
优点：简单、还原快、不失真；
缺点：压缩较差，使用起来也不方便；
适用于：低级的文字处理系统中。
2、部件压缩法：
优点：压缩比大；
缺点：字型质量不能保证。
46
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术
3、轮廓字形法：
优点,压缩比大，且能保证字符质量，当前最为流行；
方法,采用直线、或者二、三次 Bezier曲线的集合来描述一个字符的轮廓线，轮廓线构成一个或若干个封闭的平面区域。
轮廓线定义加上一些指示横宽、竖宽、基点、基线等的控制信息
，即构成字符的压缩数据。
采用适当的区域填充算法,可以从字符的轮廓线定义产生的字符位图点阵，该算法用硬件、软件均可实现。
47
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术字型技术的应用：
1、用于印刷行业：
例,北大方正和华光印刷系统，其采用的字型技术是汉字字型轮廓矢量法。
优点,能够准确地把字符地信息描述下来，保证了还原地字符质量，又对字符数据进行了大量地压缩。调用字符时，可以任意放大、缩小或进行花样变化。
2、用于 CAD、图形学领域。
48
第五章 基本图形生成算法
5.6 字符
5.6.4 字符输出
1、对于矢量字符,一般利用绘图仪输出；
方法：将有关地方向和位移值转换成设备驱动指令。
2、对于点阵字符,一般利用显示器或打印机输出；
方法：将指定字符掩膜的原点与帧缓冲器中的字符坐下角位置（ x0,y0）对应，即可将字符掩膜中的值平移地写入帧缓冲器。
49
第五章 基本图形生成算法
5.6 字符
5.6.4 字符输出算法,WriteChar（ x0,y0,value）
int x0,y0,value；
{ for( j=0 ; j <= ymax ; j++ )
for( i=0 ; i <= xmax ; i++ )
if( Mask( i,j ) <> 0 )
Writepixel( x0+i,y0+j,value )
else
Writepixel( x0+i,y0+j,background )
其中,Mask是存放掩膜位图的矩阵,（ xmin，
ymin），（ xmax,ymax）
是掩膜矩阵的坐下角位置与右上角位置的下标。
value是字符的颜色
50
第五章 基本图形生成算法
5.7 反走样走样 （ Liasing）,
用离散量表示连续量引起的失真反走样（ antialiasing）：
用于减少或消除走样现象的技术
51
第五章 基本图形生成算法
5.7 反走样走样现象：
光栅图形产生的阶梯形
图形的细节或纹理绘制失真 图5 - 4 8 绘制直线时的反走样现象
图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁图5 - 4 9 丢失细节
( a ) 需显示的矩形 ( b ) 显示结果图5 - 5 0 运动图形的闪烁
( a ) 显示 ( b ) 不显示 ( c ) 显示 ( d ) 不显示
52
第五章 基本图形生成算法
5.7 反走样反走样的方法：
– 提高分辨率
– 提高采样频率
– 区域取样
– 过滤技术
– 像素移相技术
53
第五章 基本图形生成算法
5.7 反走样
5.7.1 提高分辨率
1）提高分辨率方法简单，但代价非常大 。
显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的 4倍，而扫描转换同样大小的图元却要花 4倍时间。
图5 - 5 1 分辨率提高一倍,阶梯状程度减小一倍
54
第五章 基本图形生成算法
5.7 反走样
5.7.1 提高分辨率
2）提高采样频率原理,用较高的分辨率进行计算，然后采用某种平均算法，把结果转换到较低分辨率的显示器上进行显示。
具体实现,将每个象素划分为四个子象素，扫描转换得到各子象素的颜色值。然后，对四个子象素的颜色值进行简单平均
，即可得到象素颜色值。
图5 - 5 2 简单的过取样方式
1 2
3 4
6 7
5
55
第五章 基本图形生成算法
5.7 反走样
5.7.1 提高分辨率
3) 折衷方案：
设显示器分辨率为 m× n(m＝ 4,n＝ 3)
，把显示器窗口分为 (2m＋
1)× (2n+1),即 9× 7个子象素，计算各子象素颜色值，并根据权值表规定权值，对位于象素中心及四周的九个象素颜色作加权平均，以得到显示图像颜色值。
1 2 1
2 4 2
1 2 1 3× 3子像素加权矩阵图5 - 5 3 另一过取样方式以上三种方法实质：在高于显示分辨率的较高分辨率下，用点取样方法计算图象，然后对几个象素的属性进行平均得到较低分辨率下的象素属性。
56
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样
– 解决方法：改变直线段模型，由此产生算法
– 方法步骤,
1、将直线段看作具有一定宽度的狭长矩形；
2、当直线段与某象素有交时，求出两者相交区域的面积；
3、根据相交区域的面积，确定该象素的亮度值
57
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样方法性质：
1）直线段对一个像素亮度的贡献与两者相交区域的面积成正比，从而和像素中心点距直线段的距离成反比 (因为像素中心点距直线段距离越元，相交区域的面积越小）；
2） 当直线段和某个像素不相交时，它对该像素的亮度无影响；
3） 相同面积的相交区域对像素的亮度贡献相同，而与这个相交区域落在像素内麽位置无关。
关键：如何计算这个面积？
58
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样
D m
计算相交区域的面积设直线斜率为 m,则
(1) 中三角形阴影面积为：
(2) 中梯形阴影面积为：
(3) … …
求出的相交阴影面积介于 0－ 1间，用它对像素亮度加权可收到良好效果，
m
D
m
DD
22
1 2
2
mD?
上述处理相当于使用一个二维盒式滤波器对图形进行前置滤波！
59
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样
– 求相交区域的近似面积的离散计算方法
1、将屏幕象素分割成 n个更小的子象素；
2、计算中心点落在直线段内的子象素的个数，记为 k，
3,k/n为线段与象素相交区域面积的近似值目的：简化计算
n = 16,k = 3
近似面积 = 3/16
60
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样改进 非加权区域采样方法的 第 3条性质,
相交区域对象素亮度的贡献依赖于该区域与象素中心的距离
61
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样原理：
假想一个连续的加权曲面 （ 或过滤函数 ） 覆盖象素
。 当直线条经过该象素时,该象素的灰度值是在二者重叠区域上对滤波器 （ 过滤函数 ） 进行积分的积分值 。
特点：
1） 接近理想直线的象素将被分配更多的灰度值；
2） 相邻两个象素的滤波器相交,有利于缩小直线条上相邻象素的灰度差 。
( a ) 立方体滤波 ( b ) 圆锥滤波 ( c ) 高斯滤波图5 - 5 7 常用的过滤函数底面
63
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 权函数 W(x,y)
以象素 A的中心为原点建立二维坐标系
w(x,y)反应了微面积元 dA对整个象素亮度的贡献大小,与 d成反比。
权性（为讨论方便而设）
位于 (x,y)处的微面积元 dA对像素的亮度的贡献为
w(x,y) dA
dyxw
1),(?
1),(A dAyxw
64
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 相交区域 对该象素的亮度贡献?A w x y dA
A (,)
的面积AdAyxwA ),(特例,时，
加权区域采样方法退化为非加权区域采样方法
65
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 实现步骤
1,求直线段与象素的相交区域 ；
2,计算的值 ；
3．上面所得到的值介于 0,1之间，用它乘象素的最大灰度值，即设该象素的显示灰度。
– 问题：计算量大
A
w x y dAA (,)
66
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 离散计算方法
1,将屏幕象素均匀分割成 m个子象素,则每个子象素的面积为,计算每个子象素对原象素亮度的贡献
,记为,将 保存在一张加权表中 ;
2,求出所有中心落于直线段内的子象素,记为
，
3．计算所有这些子象素对原象素亮度贡献之和 该值乘以象素的最大灰度值即为象素的显示灰度值,
– 加权表的取法
Ai im?1
dA mA
i?
1
wiwi im?1
A ii,
wii
w w w
w w w
w w w
1 2 3
4 5 6
7 8 9
1
16
1 2 1
2 4 2
1 2 1
67上机作业
1,修改扫描线算法，使它能处理边自交的多边形？
2,实现一个反混淆的算法。
68
②①③④
余 敦 辉湖北大学 数计学院计算机图形学
2
第五章 基本图形生成算法
5.4 区域填充填充共有如下三种：
1、有序边表法：
优点：对每个元素值访问一次，输入输出要求降为最少，适于软件实现；
2、边填充算法（正负相消算法）：适于硬件实现；
边填充分类,栅栏填充；
边标志法；
3、种子填充：为一个递归算法。
可分为 漫水法 简单种子填充种子填充法扫描线填充
3
第五章 基本图形生成算法
5.4 区域填充区域,指相互连通的一组象素的集合。区域通常由一个封闭的轮廓线来定义，处于一个封闭轮廓线内的所有象素点构成一个区域。
区域填充,将区域内的象素置成新的颜色，新的颜色可以是常数，表示填以某种颜色；也可以是变量，
表示填充的是图案。
区域填充需解决的问题：
1）确定需要填充哪些象素；
2）确定用什么颜色；
4
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充顶点表示,用多边形的顶点序列来刻划多边形点阵表示,用位于多边形内的象素的集合来刻划多边形多边形的扫描转换或多边形的填充
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
p 1
p 3
p 4
p 5
( a ) 多边形P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 0
p 2
p 0 p 6
5
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 1）凸多边形和凹多边形凸多边形：对于多边形内任意两点，连接他们的直线上的所有点均在该多边形内部，该多边形即为凸多边形；
凹多边形：不满足上述条件的多边形即为凹多边形；
（ 2）多边形的内点和外点：
内点：填充成固定颜色或图案；
外点：不填充；
边界点：作为内点还是外点视要求而定。
6
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 3）内外点判定 —— 奇偶性原理从无穷远处向该点引一条射线，如果这条射线与多边形的交点为奇数时，此点为内点，否则为外点。
推导,当射线与多边形相交奇数次后，线上点都是内点，偶数次相交后线上点都是外点。
特例,顶点是交点。
若射线与多边形顶点相交
a）共享顶点的两条边分别位于扫描线的两边，交点算一个。
b）共享顶点的两条边都位于扫描线的下边，交点算零个。
c）共享顶点的两条边都位于扫描线的上边，交点算二个。
7
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充请分别回答 A～ H点中哪些点需要填充？为什么？
8
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 4）边界处理屏幕坐标顶点在
(0,0),(4,0),(4,3),(0,3)的矩型
0 321 4
1
2
3
0 321 4 5
1
2
3
4
边界上象素的取舍原则：
左闭右开下闭上开
9
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 5）确定扫描线 y=scan
ymin ≤ scan ≤ ymax
原因：所有的边和扫描线求交，
效率很低。因为一条扫描线往往只和少数几条边相交。
如何判断多边形的一条边与扫描线是否相交？
(ymin,ymax)
10
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 6）扫描线的连贯性当前扫描线与各边的交点顺序，与下一条扫描线与各边的交点顺序很可能相同或类似。
只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。
（ 7）边的连贯性当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交。
与当前扫描线相交的边称为活动边（ active edge)，把它们按与扫描线交点 x坐标递增的顺序存入一个链表中，称为活动边表（ AET,Active edge table)
11
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充根据如下分析，得到如下步骤：
对每条扫描线分为 4步 (以扫描线 6为例 )
(1) 求交点，即计算该扫描线与多边形各边的交点
(2) 排序，由于交点不一定由左到右求出，因此将求出的交点按 x 坐标值排序
(3) 交点配对,1与 2,3与 4,… …,每对表示一个区间
(4) 区间填充
12
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
（ 8）数据结构
①,新边表” (有序边表 ) 9
91 2 3 4 5 6 87 1000
1
8
7
6
4
5
3
2
11
0次 0次
2次1次
1 2 3 4
例：对下图的多边形进行填充
13
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充扫描线号
8 ^
7 ^
6
5 ^
4 ^
3
2
1
0 ^
5 2 8
11 0 8 ^
2 0 7 ^
5 -3 2 5 3 3 ^
5 -1.5 7 ^
新边表如下：
14
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充
15
第五章 基本图形生成算法
5.4 区域填充
5.4.1 多边形填充算法步骤：
(1)初始化：构造边表 ET,将 AET表置空；
(2)将第一个不空的 ET表中的边与 AET表合并；
(3)由 AET表中取出交点对进行填充 。 填充之后删除
y=ymax的边；
(4)yi+1=yi+1,根据 xi+1=xi+1/m计算并修改 AET表,同时合并 ET表中 y=yi+1桶中的边,按次序插入到 AET表中
,形成新的 AET表；
(5)AET表不为空则转 (3),否则结束 。
注：算法见 P182
16
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法
1、正负相消算法：
基本思想,对于每一条扫描线和每条多边形的交点，将该扫描线上交点右方所有的象素取补。对多边形的每一条边作此处理，多边形各边的处理顺序随意。
优点,算法简单缺点,1）每个象素可能被访问多次；
2）输入 /输出量大。
17
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法再例：
18
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法
2,栅栏填充算法栅栏：与扫描线垂直的直线，通常过多边形顶点，且将多边形分成两半方法：对每个扫描线与多边形的交点，将交点与栅栏间的像素取,补”
特点：
方法简单
减少了被重复访问的像素，特别是有多个填充对象时，效果显著
19
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法
3,边标志算法步骤：
1,对多边形的 每一条边 进行扫描转换，即对多边形边界所经过的象素作一个 边界标志 。
2.填充 。对每条与多边形相交的扫描线，按 从左到右 的顺序，
逐个 访问该扫描线上的象素。
取一个 布尔变量 inside来指示当前点的状态，若点在多边形内，
则 inside为真 。若点在多边形外，则 inside为假 。
Inside 的 初始值为假,每当当前访问象素为被打上标志的点，
就把 inside取反 。对未打标志的点,inside不变 。
20
第五章 基本图形生成算法
5.4 区域填充
5.4.2 边填充算法分为两个步骤：
(1)打标记
(2)填充
Inside
初值：假遇到标记点：取反真：填充；
假：不填充当用软件实现本算法时,速度与改进的有效边表算法相当,但本算法用硬件实现后速度会有很大提高 。 注：算法见 P184
21
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
1、原理：
假设在多边形区域内部右一象素已知，由此出发找到区域内的所有象素。
2、前提：
区域边界上所有象素均具有某个特定值，区域内部所有象素均不取这一特定值。而边界外的象素则可具有与边界相同的值。
一句话，区域边界上所有象素的值和内部所有象素的值必须要不一样。
22
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
3、区域分类：
四向连通：从区域上任意一点出发，可通过四个方向，即上、
下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素。
八向连通：区域内的每个象素，可以通过左、右、上、下、左上、右上、左下、右下这八个方向的移动的组合来到达。
23
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
A,简单的种子填充算法
1,初始化：种子像素入栈，当栈非空时，重复 2～ 4的步骤
2,栈顶像素出栈
3,将出栈像素置为多边形颜色
4,按右、上、左、下顺序依次检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，
则该像素入栈
5,当堆栈为空时，算法终止注：算法见 P186
例：
则各元素出栈顺序：
S1,2,8,9,3,4,6，
7,5,9,7,4
24
第五章 基本图形生成算法
5.4 区域填充
5.4.3 种子填充算法
B,扫描线种子填充算法为减少像素重复入栈，限定任一扫描线与多边形相交区间，只取一个种子像素
1,初始化：种子像素入栈，当栈非空时，重复 2～ 6的步骤
2,栈顶像素出栈
3,沿扫描线对种子像素的左右像素进行填充，
直至边界，从而填满该区间
4,区间内最左和最右像素分别记为 xL 和 xR
5,在区间 [xL,xR]中检查与当前扫描线相邻的上下两条扫描线是否全为边界或已经填充，
若存在非边界、未填充的像素，将检查区间的最右像素作种子入栈
6,当堆栈为空时，算法终止
25
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理
1,线刷子和方刷子处理线宽线刷子：垂直刷子,水平刷子图5 - 3 9 线刷子
( a ) ( b )
26
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理原理,设直线斜率在 【 － 1,1】 之间，此时可把刷子置成垂直方向，刷子的中点对准直线某一端点，然后让刷子中心往直线的另一端移动，即可刷出具有一定宽度的线。
反之，若直线斜率不在 【 － 1,1】 之间，把刷子置成水平方向即可。
具体实现,略为修改直线的扫描转换算法即可例,当直线斜率在 【 － 1,1】 之间时，把每步迭代的点的上下方半线宽之内的象素全部置为直线颜色即可。
27
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理特点
实现简单,效率高 。
斜线与水平 (或垂直 )线不一样粗 （ 斜线较细 ） 。
当线宽为偶数个象素时,线的中心将偏移半个象素 。
利用线刷子生成线的始末端总是水平或垂直的,看起来不太自然 。
解决：添加,线帽 （ line cap）,
图5 - 4 0 线“帽子”
( a ) 方帽 ( c ) 圆帽( b ) 突方帽
28
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理当比较接近水平的线与比较接近垂直的线汇合时,汇合处外角将有缺口图5-4 1 线刷子 产生的缺口解决：斜角连接 （ miter join）,圆连接 （ round join）,斜切连接 （ bevel join）
图5 - 4 2 线刷子产生的缺口
( a ) 斜角连接 ( b ) 圆连接 ( c ) 斜切连接
29
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理方刷子特点：
方刷子绘制的线条 （ 斜线 ） 比用线刷子所绘制的线条要粗一些方刷子绘制的斜线与水平 （ 或垂直 ） 线不一样粗 （ 斜线较细 ）
方刷子绘制的线条自然地带有一个,方线帽,
图5 - 4 3 方刷子
30
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.1 直线线宽的处理原理,把边宽为指定线宽的正方形的中心对准单象素宽的线条上的各个象素，并沿直线作平行移动，即可获得具有线宽的线条。
具体实现,采用区域填充的算法实现 ;
方法,采用与活性边表类似的技术实现：
① 为每条扫描线建一个表，存放该扫描线与线条的相交区间左右端点位置；
② 在每个象素使用方形刷子时，用该方形与各扫描线的相交区间端点坐标去更新原表内端点数据，从而得到线条各角点；
③ 再用直线段把相邻角点连接起来，最后调用多边形填充算法把所得的四边形进行着色，即可得到具有线宽的线条。
31
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.2 圆弧线宽的处理
1、采用线刷子 （见 P192，图 4.4.5）
在经过曲线斜率为 ± 1的点时，必须把线刷子在水平和垂直方向之间切换。
故此：
在曲线接近水平与垂直的地方，线条更粗一些；
在曲线斜率接近 ± 1的地方，线条更细一些；
32
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.2 圆弧线宽的处理
2、采用正方形刷子 （见 P192，图 4.4.6）
原理：无需变换刷子方向，只需顺着单象素宽的轨迹将正方形中心对准轨迹上的象素，把方形内的象素全部用线条颜色填充。
故此：
在曲线接近水平与垂直的地方，线条更细；
在曲线斜率接近 ± 1的地方，线条更粗；
33
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.2 圆弧线宽的处理
3、采用填充法 （见 P193，图 4.4.7）
原理,先绘制圆弧线条的内、外边界，然后在内外边界之间对其填色。
具体方法,
（ 1）可让内外边界都与单象素弧线轨迹距离半线宽；
（ 2）将内外边界之一对准单象素弧线轨迹，另一边界线离开此线一个线宽距离。
34
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.3 线型的处理在绘图应用中常用到的线条有：
点线：表示立体线框中可见的轮廓线；
虚线：表示立体线框中不可见的轮廓线；
点划线：用于表示中心线；
具体画法：
虚线：可通过在实线段之间插入与实线段等长的空白段来显示；
划线：由用户指定各段划线的长度和空白段的长度；
点线：可通过生成很短的划线和等于和大于划线大小的空白段来显示；
点划线：点与等长实线段的交错出现；
35
第五章 基本图形生成算法
5.5 线宽与线型处理
5.5.3 线型的处理实现方法：
实心段和中间空白段的长度（
象素数目）可用象素模板
(pixel mask)指定存在问题,如何保持任何方向的划线长度近似地相等解决,可根据线的斜率来调整实心段和中间空白段的象素数目 。
x
y
21 3 4 5 6 7 8 9 11
1
2
3
4
5
6
7
8
9
10
11
12
10 12
a
图5 - 3 8 相同数目象素显示的不等长划线
b
36
第五章 基本图形生成算法
5.6 字符
1）字符,是指数字、字母和汉字等符号，用于图形的标注、
说明等；
2） ASCII:共 128个。
0－ 31 不可见，控制字符。
32－ 127可见（大小写字母，数字，运算符号，标点符号等）
它的编码用一个字节可以表示，最高位为 0；
3）汉字编码,汉字量大，共含六千多个常用汉字、英文字母、
数字和其他图形符号。分为 94个区 94个位。每个汉字的编码由两个字节构成。
“信息交换用汉字编码字符集基本集”
－ GB2312-80
37
第五章 基本图形生成算法
5.6 字符
4）字符库,为了在终端显示器和绘图仪上输出字符，系统中必须装备有相应的字符库。字符库中存储了每个字符的形状信息。
分类：
① 矢量型字符库,采用矢量代码序列表示字符的各个笔画。
输出一个字符时，系统中的字符处理器解释该字符的每个矢量代码，输出对应的矢量，达到产生字符的目的；
适用于：利用笔式绘图仪绘制字符；
② 点阵型字符库,为每个字符产生一个字符掩膜，即表示该字符的象素图案的一个点阵。
适用于：利用终端显示器显示字符
38
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符不同的应用使用不同的方法。
对每个字符定义一个矢量代码序列来描述字符的几何形状
。下面以 AutoCAD中所采用的定义方法为例，介绍矢量字符的原理。
AutoCAD采用一种称为形（ SHAPE）的实体来定义字符的。描述格式如下：
* <形编号 >,<字节数 >,<形名称 >
<字节 1>,<字节 2>,.....,0
39
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符在标题栏中：
形编号,是 1～ 255的整数值；
字节数,表示形定义中包括结束符 0在内的字节数目；
形名称,必须为大写字母方可被调用。否则只作为形的一种解释性信息，不存入存储器，因而不占用存储空间；
描述行,由若干个用逗号隔开的字节组成，并以 0作为行定义的结束字节。每个字节由标识位、低四位和高四位三组数字组成。
① 标志位,带有前缀 0的字节是十六进制，无前缀 0的字节是十六进制，
② 高四位表示矢量的长度，低四位表示矢量方向。
例如 040即表示一 16进制数，其中,4表示矢量的长度,0
表示矢量方向。
40
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符所有矢量都具有
“相同”的长度，
即（ 2）的单位长度是（ 0）的单位长度的?2倍
41
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符例 1,下图中所示的二极管符号的形定义为：
*133,11,DIODE
040,044,04C,042,04C,040,
048,04C,046,04C,0
42
第五章 基本图形生成算法
5.6 字符
5.6.1 矢量字符例 2：“北京”两字的形定义分别为：
*250,17,BEI
024,049,041,044,038,030,044,2,020,1,05C,031,
039,05C,040,024,0
*251,23,JING
032,2,02C,1,02D,054,028,024,040,02C,028,2,0
1E,1,03E,2,086,1,050,025,02D,040,0
43
第五章 基本图形生成算法
5.6 字符
5.6.2 点阵字符
2,点阵字符西文字符：至少用 5*7的点阵描述,存储需 35位,4个多字节汉文字符：至少用 16*16的点阵描述,存储需 256位,32个字节特殊字符：按需要确定。
二进制数表示的矩阵编码（ ASCII）
问题：信息量大，质量，变换，动画，
解决：压缩，矢量。
44
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术当应用对输入字符的要求较高时（如排版印刷）
，需要高质量的点阵字符。
但由于汉字众多，且每个汉字又有多种字型、字号，故直接存储几乎不可能。
例,设汉字为 72× 72点阵，每个汉字支持 10种字型（
宋体、仿宋体等），每种字型又含 10种字号。则整个汉字字库大小为
（ 72× 72× 6763× 10× 10） /8 ＝ 440MB
45
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术解决方法：采用压缩技术对字型数据压缩后再存储，使用时将压缩的数据还原为字符位图矩阵。
常见压缩方法：
1、黑白段压缩法：
优点：简单、还原快、不失真；
缺点：压缩较差，使用起来也不方便；
适用于：低级的文字处理系统中。
2、部件压缩法：
优点：压缩比大；
缺点：字型质量不能保证。
46
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术
3、轮廓字形法：
优点,压缩比大，且能保证字符质量，当前最为流行；
方法,采用直线、或者二、三次 Bezier曲线的集合来描述一个字符的轮廓线，轮廓线构成一个或若干个封闭的平面区域。
轮廓线定义加上一些指示横宽、竖宽、基点、基线等的控制信息
，即构成字符的压缩数据。
采用适当的区域填充算法,可以从字符的轮廓线定义产生的字符位图点阵，该算法用硬件、软件均可实现。
47
第五章 基本图形生成算法
5.6 字符
5.6.3 字型技术字型技术的应用：
1、用于印刷行业：
例,北大方正和华光印刷系统，其采用的字型技术是汉字字型轮廓矢量法。
优点,能够准确地把字符地信息描述下来，保证了还原地字符质量，又对字符数据进行了大量地压缩。调用字符时，可以任意放大、缩小或进行花样变化。
2、用于 CAD、图形学领域。
48
第五章 基本图形生成算法
5.6 字符
5.6.4 字符输出
1、对于矢量字符,一般利用绘图仪输出；
方法：将有关地方向和位移值转换成设备驱动指令。
2、对于点阵字符,一般利用显示器或打印机输出；
方法：将指定字符掩膜的原点与帧缓冲器中的字符坐下角位置（ x0,y0）对应，即可将字符掩膜中的值平移地写入帧缓冲器。
49
第五章 基本图形生成算法
5.6 字符
5.6.4 字符输出算法,WriteChar（ x0,y0,value）
int x0,y0,value；
{ for( j=0 ; j <= ymax ; j++ )
for( i=0 ; i <= xmax ; i++ )
if( Mask( i,j ) <> 0 )
Writepixel( x0+i,y0+j,value )
else
Writepixel( x0+i,y0+j,background )
其中,Mask是存放掩膜位图的矩阵,（ xmin，
ymin），（ xmax,ymax）
是掩膜矩阵的坐下角位置与右上角位置的下标。
value是字符的颜色
50
第五章 基本图形生成算法
5.7 反走样走样 （ Liasing）,
用离散量表示连续量引起的失真反走样（ antialiasing）：
用于减少或消除走样现象的技术
51
第五章 基本图形生成算法
5.7 反走样走样现象：
光栅图形产生的阶梯形
图形的细节或纹理绘制失真 图5 - 4 8 绘制直线时的反走样现象
图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁图5 - 4 9 丢失细节
( a ) 需显示的矩形 ( b ) 显示结果图5 - 5 0 运动图形的闪烁
( a ) 显示 ( b ) 不显示 ( c ) 显示 ( d ) 不显示
52
第五章 基本图形生成算法
5.7 反走样反走样的方法：
– 提高分辨率
– 提高采样频率
– 区域取样
– 过滤技术
– 像素移相技术
53
第五章 基本图形生成算法
5.7 反走样
5.7.1 提高分辨率
1）提高分辨率方法简单，但代价非常大 。
显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的 4倍，而扫描转换同样大小的图元却要花 4倍时间。
图5 - 5 1 分辨率提高一倍,阶梯状程度减小一倍
54
第五章 基本图形生成算法
5.7 反走样
5.7.1 提高分辨率
2）提高采样频率原理,用较高的分辨率进行计算，然后采用某种平均算法，把结果转换到较低分辨率的显示器上进行显示。
具体实现,将每个象素划分为四个子象素，扫描转换得到各子象素的颜色值。然后，对四个子象素的颜色值进行简单平均
，即可得到象素颜色值。
图5 - 5 2 简单的过取样方式
1 2
3 4
6 7
5
55
第五章 基本图形生成算法
5.7 反走样
5.7.1 提高分辨率
3) 折衷方案：
设显示器分辨率为 m× n(m＝ 4,n＝ 3)
，把显示器窗口分为 (2m＋
1)× (2n+1),即 9× 7个子象素，计算各子象素颜色值，并根据权值表规定权值，对位于象素中心及四周的九个象素颜色作加权平均，以得到显示图像颜色值。
1 2 1
2 4 2
1 2 1 3× 3子像素加权矩阵图5 - 5 3 另一过取样方式以上三种方法实质：在高于显示分辨率的较高分辨率下，用点取样方法计算图象，然后对几个象素的属性进行平均得到较低分辨率下的象素属性。
56
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样
– 解决方法：改变直线段模型，由此产生算法
– 方法步骤,
1、将直线段看作具有一定宽度的狭长矩形；
2、当直线段与某象素有交时，求出两者相交区域的面积；
3、根据相交区域的面积，确定该象素的亮度值
57
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样方法性质：
1）直线段对一个像素亮度的贡献与两者相交区域的面积成正比，从而和像素中心点距直线段的距离成反比 (因为像素中心点距直线段距离越元，相交区域的面积越小）；
2） 当直线段和某个像素不相交时，它对该像素的亮度无影响；
3） 相同面积的相交区域对像素的亮度贡献相同，而与这个相交区域落在像素内麽位置无关。
关键：如何计算这个面积？
58
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样
D m
计算相交区域的面积设直线斜率为 m,则
(1) 中三角形阴影面积为：
(2) 中梯形阴影面积为：
(3) … …
求出的相交阴影面积介于 0－ 1间，用它对像素亮度加权可收到良好效果，
m
D
m
DD
22
1 2
2
mD?
上述处理相当于使用一个二维盒式滤波器对图形进行前置滤波！
59
第五章 基本图形生成算法
5.7 反走样
5.7.2 简单 区域采样
– 求相交区域的近似面积的离散计算方法
1、将屏幕象素分割成 n个更小的子象素；
2、计算中心点落在直线段内的子象素的个数，记为 k，
3,k/n为线段与象素相交区域面积的近似值目的：简化计算
n = 16,k = 3
近似面积 = 3/16
60
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样改进 非加权区域采样方法的 第 3条性质,
相交区域对象素亮度的贡献依赖于该区域与象素中心的距离
61
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样原理：
假想一个连续的加权曲面 （ 或过滤函数 ） 覆盖象素
。 当直线条经过该象素时,该象素的灰度值是在二者重叠区域上对滤波器 （ 过滤函数 ） 进行积分的积分值 。
特点：
1） 接近理想直线的象素将被分配更多的灰度值；
2） 相邻两个象素的滤波器相交,有利于缩小直线条上相邻象素的灰度差 。
( a ) 立方体滤波 ( b ) 圆锥滤波 ( c ) 高斯滤波图5 - 5 7 常用的过滤函数底面
63
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 权函数 W(x,y)
以象素 A的中心为原点建立二维坐标系
w(x,y)反应了微面积元 dA对整个象素亮度的贡献大小,与 d成反比。
权性（为讨论方便而设）
位于 (x,y)处的微面积元 dA对像素的亮度的贡献为
w(x,y) dA
dyxw
1),(?
1),(A dAyxw
64
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 相交区域 对该象素的亮度贡献?A w x y dA
A (,)
的面积AdAyxwA ),(特例,时，
加权区域采样方法退化为非加权区域采样方法
65
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 实现步骤
1,求直线段与象素的相交区域 ；
2,计算的值 ；
3．上面所得到的值介于 0,1之间，用它乘象素的最大灰度值，即设该象素的显示灰度。
– 问题：计算量大
A
w x y dAA (,)
66
第五章 基本图形生成算法
5.7 反走样
5.7.3 加权 区域采样
– 离散计算方法
1,将屏幕象素均匀分割成 m个子象素,则每个子象素的面积为,计算每个子象素对原象素亮度的贡献
,记为,将 保存在一张加权表中 ;
2,求出所有中心落于直线段内的子象素,记为
，
3．计算所有这些子象素对原象素亮度贡献之和 该值乘以象素的最大灰度值即为象素的显示灰度值,
– 加权表的取法
Ai im?1
dA mA
i?
1
wiwi im?1
A ii,
wii
w w w
w w w
w w w
1 2 3
4 5 6
7 8 9
1
16
1 2 1
2 4 2
1 2 1
67上机作业
1,修改扫描线算法，使它能处理边自交的多边形？
2,实现一个反混淆的算法。
68
②①③④
