第四章 基本图形生成算法
? 用某种颜色编码的图形生成的基本原理：
在光栅显示器上的图形是一组象素的集
合，其中每个象素都具有某种颜色的编码，
这些象素（及其颜色）是通过对图形的扫描
得到的。
? 图形的扫描过程称为 扫描转换 或 光栅化
?主要内容,基本图形的扫描转换如 线，圆，
椭圆 的扫描转换，及封闭的 多边形的填充问
题,字符处理,图形裁剪, 反走样技术 等。
4.0 概述,--图形生成的基本原理，主要内容
Mathemtaical Equation and
Rasterized pixels
1 1 2 2 3 3 4 4
()
(,),(,),(,),(,),..,(,)
nn
y f x
x y x y x y x y x y
?
数学方程
光栅化的象素点
第四章 基本图形生成算法
? Step1:确定图形的象素
? Step2:确定图形的颜色等属性，并对象
素做写操作
4.0 概述,--图形扫描转换的两个步骤
任务一,因 Step2调用图形设备驱动程序
完成，故仅考虑 Step1的任务，即确定
最能反映图形特征的象素集合 。 --如
何扫描图形？？
例如,1D图形的扫描得到（线宽） 象素序列, 2D
图形的扫描得到一个 封闭的区域 --边界 和 内部填充
图形 或 颜色。
第四章 基本图形生成算法
4.0 概述：
任务二：由于图形要在一个 窗口 中显示，所以还
要确定图形的范围 --图形的 窗口裁剪 技术 注,窗口
裁剪应在
图形扫描
前进行。
裁剪窗口
象素点
第四章 基本图形生成算法
4.0 概述：
任务三,象素序列的锯齿形引起走样，所以要用
反走样技术克服图形走样。
说明,提高显示器的分辨率可以部分克服反走样
但成本太高。
反走样算法基本原理,尽量减少相邻象素点的亮
度或或颜色的差别。
例如：
第四章 基本图形生成算法
4.1 直线生成算法
直线段扫描转换,在扫描过程中，求与直线段最接近的像素点集 。
(误差是多少？？？ )
一个象素宽度的直线扫描的三个算法（ 假设：直线段宽度为
1个象素点，斜率 -1<=k<=1）
? 数值微分法（ DDA）
? 中点画线法
? Bresenham算法。
掌握：
?算法思想
?算法伪代码
?上机编程运行的源代码（ C or C++/Visual C++ ）
基本思路：
问题模型
00
.
(,),., (,)nn
y k x b
X Y X Y
??
??
直线的斜率方程
起点 终点
问题求解步骤
? 从起点
? 到终点（）
00(,)XX
(,)nnXX
数值微分 (DDA)法
? 已知过端点 P0 (x0,y0),P1(x1,y1)的直线段
L(P0,P1),；直线斜率为,画线过程从 x
? 的 左端点 x0开始，向 x右端点步进,步长 =1(个
象素 )，计算相应的 y坐标 y=kx+B；取象素点 (x,
round(y))作为当前点的坐标。计算
? yi+1 = kxi+1+B = kxi+B+kDx = yi+kDx
? 当 Dx=1 yi+1 = yi+k,即：当 x每递增 1,y递增
k(直线斜率 ).
? round(yi)=int(yi+0.5)
数值微分 (DDA)法
? DDA画线算法程序
? void LineDDA(int x0,int y0,int x1,int y1,int
color) /* 假定 x0<x1,-1<=k<=1 */
? { int x；
? float dx,dy,y,k;
? dx= x1-x0;
? dy=y1-y0;
? k=dy/dx;
? y=y0;
? for(x=x0; x<= x1,x++)
? { Putpixel(x,int(y+0.5),color);
? y+=k;
? }
? }
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 分析：上述算法仅适用于 | k| ≤1 的情形 。特
点是：在这种情况下,x每增加 1,y最多增
加 1。当 | k| > 1时，必须把 x,y地位互换，
y每增加 1,x相应增加 1/k。
? 缺点,在这个算法中,y与 k必须用浮点数表示，
而且每一步都要对 y进行四舍五入后取整。这
使得它 不利于硬件实现。
4.2 中点画线法
? 中点画线法的基本原理：
画直线段的过程中，当前
象素点为 (xp,yp)，下一
个象素点有 两种可选择点
p1(xp+1,yp)或 p2(xp+1,
yp+1)。若 M=(xp+1,
yp+0.5)为 p1与 p2之中点，
Q为理想直线与 x=xp+1垂
线的交点。当 M在 Q的下方,
则 P2 应为下一个象素点；
M在 Q的上方，应取 P1 为
下一点。
中点画线法
? 中点画线法的算法：
? 令直线段 L(p0(x0,y0),p1(x1,y1)),其方程式 F(x,
y)=ax+by+c=0。其中,a=y0-y1,b=x1-x0,c=x0y1-
x1y0; 点与 L的关系,on,F(x,y)=0; up,F(x,y)>0;
down,F(x,y)<0;
因此，欲判断中 M在 Q点的上方还是下方，只要把 M代入 F（ x，
y），并判断它的符号。
构造判别式,
d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c
1,当 d<0,M在 L(Q点 )下方，取 P2为下一个象素；
2,当 d>0,M在 L(Q点 )上方，取 P1为下一个象素；
3,当 d=0,选 P1或 P2均可，约定取 P1为下一个象
素；
中点画线法
判别式 d的计算,注意到 d是 xp,yp的线性函数，可采用增量计算，提
高运算效率,
若当前象素处于 d>=0情况，则取正右方象素 P1（ xp+1,yp）,要判下
一个象素位置，应计算
d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量为 a
若 d<0时，则取右上方象素 P2（ xp+1,yp+1）。要判断再下一象素，
则要计算
d2= F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ； 增量为 a＋ b
画线从 (x0,y0)开始,d的初值 d0=F(x0+1,y0+0.5)=F(x0,
y0)+a+0.5b 因 F(x0,y0)=0，则 d0=a+0.5b。
由于我们使用的只是 d的符号，而且 d的增量都是整数，只是初始值
包含小数。因此，我们可以用 2d代替 d来摆脱小数，写出仅包含整数
运算的算法。
中点画线法
算法程序
void MidpointLine (int x0,int y0,int x1,int y1,int color)
{ int a,b,d1,d2,d,x,y;
a=y0-y1；
b=x1-x0；
d=2*a+b;
d1=2*a；
d2=2*(a+b);
x=x0；
y=y0;
Putpixel(x,y,color);
while (x<x1)
{ if (d<0) {x++,y++,
d+=d2; }
else {x++,d+=d1;}
Putpixel (x,y,color);
} /* while */
} /* mid PointLine */
中点画线法
举例 用中点画线方法扫描转换连接两点 P0（ 0,0）和 P1（ 5,2）的直
线段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-
4;d2=2*(a+b)=6,
X y d
0 0 1
1 0 -3 d1
2 1 3 d2
3 1 -1 d1
4 2 5 d2
4.3 Bresenham算法
? 基本原理,该方法类似于中点法，由误差
项符号决定下一个象素取右边点还是右上
点。 是计算机图形学领域使用最广泛的直
线扫描转换算法。
算法原理, 过各行各列象
素中心构造一组虚拟网格线。
按直线从起点到终点的顺序计
算直线与各垂直网格线的交点，
然后确定该列象素中与此交点
最近的象素。该算法的巧妙之
处在于采用 增量计算,使得对
于每一列，只要检查一个误差
项的符号，就可以确定该列的
所求象素。
Bresenham算法
? 图示
设直线方程为,
其中 k=dy/dx。 假设 x列的象素已经确定为 xi，
其行坐标为 yi。那么下一个象素的列坐标为 xi＋ 1，
而行坐标要么不变为 yi，要么递增 1为 yi＋ 1。是
否增 1取决于如图所示误差项 d的值。因为直线的
起始点在象素中心，所以误差项 d的初值 d0＝ 0。
X下标每增加 1,d的值相应递增直线的斜率值 k，
即 d＝ d＋ k。一旦 d≥1,就把它减去 1，这样保证
d在 0,1之间。当 d≥0.5 时，直线与 xi＋ 1列垂直
网格交点最接近于当前象素（ xi,yi）的右上方
象素（ xi＋ 1,yi＋ 1）；而当 d<0.5时，更接近于
右方象素（ xi＋ 1,yi）。为方便计算，令 e＝ d－
0.5,e的初值为－ 0.5，增量为 k。当 e≥0 时，取
当前象素（ xi,yi）的右上方象素（ xi＋ 1,yi＋
1）；而当 e<0时，更接近于右方象素（ xi＋ 1，
yi）。
Bresenham算法
Bresenham画线算法程序：
void Bresenhamline (int x0,int y0,int x1,int y1,int color)
{ int x,y,dx,dy;
float k,e;
dx = x1-x0;
dy = y1- y0;
k=dy/dx;
e=-0.5;
x=x0;
y=y0;
for (i=0; i<=dx; i++)
{ Putpixel (x,y,color);
x=x+1;
e=e+k;
if (e>= 0)
{ y++,e=e-1;}
}
}
Bresenham算法
举例,用 Bresenham方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x y e
0 0 -0.5
1 0 -0.1 0.3-1
2 1 -0.7
3 1 -0.3 0.1-1
4 2 -0.9
5 2 -0.5
Bresenham算法
分析,上述 bresenham算法在计算直线斜率与误差项时用到小数与除法。
可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可
作如下替换,e=e*2dx,改进的 Bresenham画线算法程序：
void
InterBresenhamline
(int x0,int y0,int x1,int
y1,int color)
{ dx = x1-x0;
dy = y1- y0;
e=-dx;
x=x0;
y=y0;
for (i=0; i<= dx; i++)
{Putpixel (x,y,color);
x++;
e=e+2*dy;
if (e>= 0) { y++; e=e-2*dx;}
}
}
4.4 圆与椭圆的扫描转换
X2+Y2=R2 (X/a)2+(Y/b)2=R2
4.4.1 圆的扫描转换 X2+Y2=R2
圆的定义：
中心,（ xc,yc）
半径,r
的圆弧上的点集。
圆心位于原点的圆有四条
对称轴 x=0,y=0,x=y和 x=-
y。若已知圆弧上一点
（ x,y）,可以得到其关于
四条对称轴的其它 7个点，
这种性质称为 八分对称性 。
因此，只要扫描转换八分
之一圆弧，就可以求出 整
个圆弧的象素集。
显示圆弧上的八个对称点的算法
void CirclePoints(int x,int y,int color)
{ Putpixel(x,y,color); Putpixel(y,x,color);
Putpixel(-x,y,color); Putpixel(y,-x,color);
Putpixel(x,-y,color); Putpixel(-y,x,color);
Putpixel(-x,-y,color); Putpixel(-y,-x,color);
}
中点画圆法
圆函数：
圆上的点：
圆外的点,
圆内的点：
思路,与中点画线法一
样，构造判别式 d。
1,若 则应取 P1为下一象素，而且再下一象素的
判别式为
2,若 则应取 P2为下一象素，而且下一象素的判别式为
讨论按顺时针方向生成第二个八分圆。则第一个象素是 （ 0,R）,
判别式 d的初始值为
圆弧生成的中点算法 (圆心在原点 )
void MidPointCircle(int r,int color)
{ int x,y;
float d;
x=0;
y=r;
d=1.25-r;
Circlepoints (x,y,color);
while(x<=y)
{ if(d<0) d+=2*x+3;
else { d+=2*(x-y)+5;
y--;}
x++;
Circlepoints (x,y,color);
}
}
分析,为提高算法的效率，可将上面算法中的浮点数改成整
数，将乘法运算改加法运算，即仅用整数实现中点画圆法。
（ 留做习题 ）
例子：圆的中心在原点 （ 0,0）,半径为 7
4.4.2 圆弧生成的 Bresenham算法 (略 )
4.4.3 椭圆弧的生成算法
算法：基本同圆弧算法，方程是
F(x,y)=(bx)^2+(ay)^2-(ab)^2.
对称性,4分对称，画第一象限
分段依据：斜率为一点
上段圆弧
下段圆弧
4.4.4 圆弧生成的多边形逼近算法 (略 )
4.4.5 易画曲线的正负法
正负法简介：
易画曲线 ----
（ 1） F(x,y)具有正负划分性
（ 2） F(x,y)二阶导数连续
（ 3） 曲线上各点的曲率半
径大于步长，即在步长度量下，曲
线是平坦的
线宽处理算法
线宽控制：
如何画线宽大于一个像素的线？
选取宽度适当的刷子在屏幕上绘图，刷子轨迹即为所求。
问题：
? 刷子形状如何？（圆形，长方形。。。）
? 非圆形刷子，其朝向如何？（水平、垂直、
变化？）
? 线形如何？
像素复制方法（线刷子）,斜
率在（ -1,1）之间，用垂直刷
子，否则用水平刷子。
优点：实现简单
缺点,线段两端要么垂直，
要么水平；
折线顶点处有缺口；
图元的宽度不均匀；
宽度为偶像素的图元效
果不好；
水平垂直宽度正确，斜
线宽度变小（与斜率有关）
移动刷子方法（方刷子）
优点,实现简单
缺点,线段两端要么垂直，
要么水平；
折线顶点处有缺口；
图元的宽度不均匀；
宽度为偶像素的图元效
果不好；
水平垂直宽度正确，斜
线宽度变大（与斜率有关）
填充图元方法
优点,生成图形质量
高
缺点：
计算量大； 有些图形
的等距线不容易求
线型控制：
一般用位屏蔽器实现
如：用一个 16位整数表示一个位串，当对
应为 1时，显示像素，否则不显示。
以 16个像素为周期重复，在程序实现时将无条件
写像素 Putpixel(x,y,color)改为：
if(位串 [i%16]) Putpixel(x,y,color);
4.5 区域填充算法
图形填充的两个问题：
（ 1）确定哪些像素位于图元的内部
（ 2）以什么颜色填充这些像素
(3) 用什么图形及何种颜色填充
主要内容：
扫描转换矩形，多边形的两种表示方法，扫描转换
多边形的逐点判断算法、扫描线算法、边缘填充算法，判
断一个点关于多边形区域内外关系的射线法、累计角度法、
编码方法，扫描转换扇形区域，区域的表示，区域的连通
性，填充区域的递归算法、扫描线算法，以图像填充区域，
点阵字符与矢量字符。
掌握要点,
1,了解矩形区域的扫描转换；
2,掌握多边形的两种表示方法：顶点表示与点阵表示 ;
3,掌握扫描转换多边形的逐点判断算法、扫描线算法和
边缘填充算法以及它们采用的数据结构，了解这几个
算法各自的优缺点；
4,掌握判断一个点关于多边形区域内外关系的射线法、
累计角度法、编码方法；
5,了解如何扫描转换扇形区域；
6,掌握什么是区域，区域的两种表示方法：内点表示和
边界表示，区域的连通性,4连通和 8连通；
7,掌握填充区域的递归算法、扫描线算法；
8,了解如何以图像来填充一个多边形或一个区域；
9,了解两种典型的字符表示方法：点阵表示和矢量表示，
以及它们的优缺点。
4.5.1 矩阵的扫描转换
问题背景：
矩形是特殊的多边形，但一般多边形的扫描算法要
用到复杂的数据结构，效率不高，而矩形常用且经常会用
到，所以一般图形软件包把它作为一类基本的图元加以设
计。
矩形的表示,四个自由度
（ 1）四个顶点的坐标为
Xmin,Xmax,Ymin,Ymax.
（ 2）左上角坐标（ x,y）,长 l,宽 w
扫描转换程序：
typedef struct {int xmin,xmax,ymin,ymax;}Rectangle;
void FillRectangle(Rectangle *rect,int color)
{int x,y;
for(y=rect->ymin;y<=rect->ymax;y++)
for(x=rect->xmin;x<=rect->xmax;x++)
Putpixel(x,y,color);
} /*end */
问题：
共享边会重复绘制，边界属于谁？
处理规则：
左闭右开，下闭上开（左下原则：左边和下边像
素属于图元）
4.5.2 多边形的扫描转换
多边形的两种表示方法：
1,顶点表示
2,点阵表示
顶点表示,用多边形的顶点序
列（ P0,P1,… Pn）来表示多边形。
顶点表示的优点,直观、几何
意义强、占内存少，易于进行几
何变换，但没有明确指出哪些象
素在多边形内，故不能直接用于
面着色。
点阵表示, 用位于多边形
内的 象素集合 来刻画多边形。
缺点,丢失了许多几何信息。
优点,便于帧缓冲器表示图
形，是面着色所需要的图形
表示形式。
光栅图形的一个基本问题：把多边形的 顶点表示 转换为
点阵表示 。这种转换称为 多边形的扫描转换 。
例如：
多边形的种类
① 凸多边形任意两顶点间的
任意两顶点间的连线均在多边形内
② 凹多边形：任意两顶点间的连线有不在多边 形内
的部分
③ 含内环的多边形
多边形扫描转换的逐点判断算法
算法原理,逐个判断绘图窗口内的
像素，确定它们是否在多边形区域
内部。
void FillPolygonPbyP(Polygon *P,int polygonColor)
{ int x,y;
for(y = ymin;y <= ymax;y++)
for(x = xmin;x <= xmax;x++)
if(IsInside(P,x,y))
PutPixel(x,y,polygonColor);
else PutPixel(x,y,backgroundColor);
}/*end of FillPolygonPbyP() */
问题,如
何判别点
(x,y)关于
多边形区
域 P的内外
关系？
（ 1）射线法
（ 2） 累计角度法
（ 3）编码算法（略）
（ 1） 射线法
步骤：
* 从待判别点 v发出射线
* 求交点个数 k
* k 的奇偶性决定了点与多边形的内外关系
* 奇异情况处理
（ 2）累计角度法
步骤：
* 从 v点向多边形 P顶点
发出射线，形成有向角
* 计算有相交的和，得
出结论
奇异情况处理
优点：简单
缺点：计算量大，速度慢。
扫描线算法
逐点判断法简单，但效率不高，为提高效率，
对不自交多边形，可以用扫描线算法。
扫描线多边形区域填充算法：
按扫描线顺序，计算扫描线
与多边形的 相交区间,再用
要求的颜色显示这些区间的
象素，即完成 填充工作 。区
间的端点可以通过计算扫描
线与多边形边界线的交点获
得。
知识,对于一条扫描线，它
与多边形的交点总是偶数
（若重复，按重复的次数累
加计算交点个数）
对于一条扫描线，多边形的填充过程可以分为四个步
骤：
（ 1） 求交,计算扫描线与多边形各边的交点；
（ 2） 排序,把所有交点按 x值递增顺序排序；
（ 3） 配对,第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间，
（ 4） 填色,把相交区间内的象素置成多边形颜色，
把相交区间外的象素置成背景色。
关键问题：求交！ 为了减少求交的计算量，可以利
用 边的连贯性：相邻扫描线与边的交点的坐标有连贯
性
第一类交点,新出现的边与扫描线的交点，
第二类交点,位于同一条变上的后继交点
第一类交点,新出现的边与扫描
线的交点，
第二类交点,位于同一条变上
的后继交点
边的数据结构为
typedef struct {int ymax; float x,deltax; struct Edge *nextEdge;}
Edge;
参数含义：
1,ymax,边的上端点 y坐标 ;
2,x:初值为边下端点的 x坐标,AEL中为当前扫描线与边的
交点的 X坐标 ;
3,deltax:边的斜率的倒数；
4,nextEdge:指向下一条边的指针。
为了提高效率，在处理一条扫描线时,仅对与它相交的多边形
的边进行求交运算 。我们把 与当前扫描线相交的边称为活性边，
并把它们按与扫描线交点 x坐标递增的顺序 存放在一个链表中，
称此链表为 活性边表 (AEL)。
算法分析
假定当前扫描线与多边形某一条边的交点的 x坐
标为 x，则下一条扫描线与该边的交点不要重计
算，只要加一个增量△ x。
设该边的直线方程为,ax+by+c=0；
若 y＝ yi,x=xi；则当 y = yi+1时，
其中 为常数，
另外使用增量法计算时，我们 需要知道一条
边何时不再与下一条扫描线相交，以便及时把
它从活性边表中删除出去。
为了方便活性边表的建立与更新，我们 为每
一条扫描线建立一个新边表（ NET）,存放在该
扫描线第一次出现的边。也就是说，若某边的
较低端点为 ymin，则该边就放在扫描线 ymin的
新边表中。
Question:各
条扫描线的
新边表 NET?
各条扫描线
的新边表 NET
算法与分析
算法
void polyfill (polygon,color)
int color;多边形 polygon;
{ for (各条扫描线 i )
{ 初始化新边表头指针 NET [i]；
把 y min = i 的边放进边表 NET [i];
}
y = 最低扫描线号；
初始化活性边表 AEL为空；
for (各条扫描线 i )
? { 把新边表 NET[i]中的边
结点用插入排序法插入 AEL
表，使之按 x坐标递增顺序
排列；
? 遍历 AEL表，把 y max= i
的结点从 AEL表中删除，并
把 y max > i结点的 x值递增 D
x；
? 若允许多边形的边自相
交，则用冒泡排序法对 AEL
表重新排序；
? 遍历 AEL表，把配对交
点区间 (左闭右开 )上的象素
(x,y)，用 Putpixel (x,y,color)
改写象素颜色值； }
} /* polyfill */
分析,扫描线与多边形顶点相交时，必须明确交
点的取舍：
* 扫描线与多边形相交的边分处扫描线的两
侧，则计一个交点。
* 扫描线与多边形相交的边分处扫描线同侧，
且 yi<yi-1,yi<yi+1,则计 2个交点 (填色 )，如
P2。 若 yi>yi-1,yi>yi+1，则计 0个交点 (不填
色 )。
* 扫描线与多边形边界重合 (当要区分边界
和边界内区域时需特殊处理 )，则计 1个交点。
具体实现时，只需检查顶点的两条边的另外
两个端点的 y值。按这两个 y值中大于交点 y值
的个数是 0,1,2来决定。
扫描线与多边形相交，特殊情况的处理（图
示）
边界标志算法
基本思想是,在帧缓冲器中对多边形的每条边进
行直线扫描转换，亦即对多边形边界所经过的象
素打上标志。然后再采用和扫描线算法类似的方
法将位于多边形内的各个区段着上所需颜色。对
每条与多边形相交的扫描线依从左到右的顺序，
逐个访问该扫描线上的象素。使用一个布尔量
inside来指示当前点是否在多边形内的状态。 Inside
的初值为假，每当当前访问的象素为被打上边标
志的点，就把 inside取反。对未打标志的象素，
inside不变。若访问当前象素时,inside为真，说明
该象素在多边形内，则把该象素置为填充颜色。
边界标志算法：
void edgemark_fill(polydef,color)
多边形定义 polydef； int color;
{ 对多边形 polydef 每条边进行直线扫描转换；
inside = FALSE;
for (每条与多边形 polydef相交的扫描线 y )
for (扫描线上每个象素 x )
{ if(象素 x 被打上边标志 )inside = ! (inside);
if(inside！ = FALSE) drawpixel (x,y,color);
else drawpixel (x,y,background);
}
}
例子：正方形内切 n个圆的边界标志算法
分析和比较：
用软件实现时,扫描线算法与边界标志算法 的执
行速度几乎相同，但由于边界标志算法不必建立
维护边表以及对它进行排序，所以边界标志算法
更适合硬件实现，这时它的执行速度比有序边表
算法快一至两个数量级。
4.5.3 边缘填充算法
原理：以求余运算代替扫描线算法中的排序运算
求余：
(A=0xFFFFFFFF)
算法 1：（以扫描线为中心的边缘填充算法）
1、将当前扫描线上的所有象素着上值为 的
颜色；
2、求余：
for(i = 0;i <= m; i++)
在当前扫描线上，从 x坐标为交点向右求余；
算法 2：（以边为中心的边缘填充算法）
1、将绘图窗口的背景色置为；
2、对多边形的每一条非水平边做：
从该边上的每个象素开始向右求余
4.5.4 栅栏填充算法
4.5.5 扇形扫描转换
? 扇形区域可以直接推广多边形的扫描线
算法，对每条扫描线，先计算交点，再
把配对之间的像素用指定颜色填充。
? 扇形区域的描述,半径，起始角，终止
角（设圆心在原点）
原理,同扫描转换多边
形
问题,如何确定扫描线
与直线段和圆弧段的相
交顺序
方法：分类
按起点和终点所处象限的不同，需要将扇形
区域分成 4× 4=16种情况：
? * 假设起点落在第一象限,扇形区域的扫描转换
可分四种情况
1、终点落在第一象限
2、终点落在第二象限，此时又分为两种情况
– y2>=y1 y2<y1
3、终点落在第三象限
4、终点落在第四象限
*当起点落在其它象限时，一般是先旋转，使起
点在第一象限，待扫描转换后再转 回去。
4.5.6 连通区域填充算法
? 基本 概念
? 区域 ----指已经表示成 点阵形式 的填充图形，它
是 象素的集合 。
*区域可采用 内点表示和边界表示 两种表示形式。
– 内点表示,n枚举出区域内部的所有像素，内部的
所有像素着同一个颜色，边界像素着与内部像素不
同的颜色。
– 边界表示,枚举出边界上的所有像素，边界上的
所有像素着同一个颜色，内部像素着与边界像素不
同的颜色。
4.5.6 连通区域填充算法
? 基本 概念
? *区域填充 ----指先将区域的一点（ seed种子 ）赋
予指定的颜色，然后将该颜色扩展（ flood fill）
到整个区域的过程。
? *区域填充算法 前提,连通的区域。
因为只有在连通区域中，才可能将种子点的颜色扩展到区域
内的其它点。
区域连同类型
*区域可分为 4向连通区域 和 8向连通区域。
– 4向连通区域指的是从区域上一点出发，可通
过四个方向，即上、下、左、右移动的组合，
在不越出区域的前提下，到达区域内的任意象
素；
– 8向连通区域指的是从区域内每一象素出发，
可通过八个方向，即上、下、左、右、左上、
右上、左下、右下这八个方向的移动的组合来
到达。
区域连同类型
*区域可分为 4向连通区域 和 8向连通区域。
– 4向连通区域指的是从区域上一点出发，可通
过四个方向，即 上、下、左、右 移动的组合，
在不越出区域的前提下，到达区域内的任意象
素；
四
连
通
区
域
区域连同类型
*区域可分为 4向连通区域 和 8向连通区域。
– 8向连通区域指的是从区域内每一象素出发，
可通过八个方向，即上、下、左、右、左上、
右上、左下、右下这八个方向的移动的组合来
到达。
八
连
通
区
域
区域的内点表示和边界表示 —
例子
4.5.6.1 区域填充的递归算法 --
种子填充算法：
? 种子填充算法,假设在多边形内有一象素 (种
子 )已知，由此出发利用连通性找到 区域内的
所有象素 。
假设,设 （ x,y） 为内点表示的 4连通区域内的一
点,oldcolor为区域的原色（背景色），要将整
个区域填充为新的颜色 newcolor（前景色） 。
算法例子：
– 内点表示 的 4连通区域的递归填充算法。
– 边界表示 的 4连通区域的递归填充算法。
内点表示的 4连通区域的递归填充算法。
? void FloodFill4(int x,int y,int oldcolor,int newcolor)
? { if(getpixel(x,y)==oldcolor)
? { Putpixel(x,y,newcolor);//种子
? FloodFill4(x,y+1,oldcolor,newcolor);//上
? FloodFill4(x,y-1,oldcolor,newcolor);//下
? FloodFill4(x-1,y,oldcolor,newcolor);//左
? FloodFill4(x+1,y,oldcolor,newcolor);//右
? }
? }
边界表示的 4连通区域的递归填充算法。
? void BoundaryFill4(int x,int y,int boundarycolor,int
newcolor)
{ int color;
if(color!=newcolor && color!=boundarycolor)
{ Putpixel(x,y,newcolor);//种子
BoundaryFill4 (x,y+1,boundarycolor,newcolor);//上
BoundaryFill4 (x,y-1,boundarycolor,newcolor);//下
BoundaryFill4 (x-1,y,boundarycolor,newcolor);//左
BoundaryFill4 (x+1,y,boundarycolor,newcolor);//右
}
}
8连通区域的填充算法
? 对于内点表示和边界表示的 8连通区域的
填充，只要将上述相应代码中递归填充
相邻的 4个象素增加到递归填充 8个象素
即可。 （留做练习）
递归算法分析
? 算法简单，效率不高！
? 原因：
– 递归算法需要较多内存
– 不方便并行运行
– 多次重复判断同一象素点
4.5.6.2 区域填充的扫描线算法
? 基本过程, 当给定 种子点 (x,y)时,首先 填充种子点所在扫描线
上的位于给定区域的一个区段，然后确定与这一区段相连通的 上、
下两条扫描线上 位于给定区域内的区段，并依次保存下来。反复这
个过程，直到填充结束。
? 四个步骤
– (1)初始化,堆栈置空。将种子点（ x,y）入栈。
– (2)出栈,若栈空则结束。否则取栈顶元素（ x,y），
以 y作为当前扫描线。
– (3)填充并确定种子点所在区段,从种子点（ x,y）
出发，沿当前扫描线向左、右两个方向填充，直到
边界。分别标记区段的左、右端点坐标为 xl和 xr。
– (4)确定新的种子点,在区间 [xl,xr]中检查与当前扫
描线 y上、下相邻的两条扫描线上的象素。若存在非
边界、未填充的象素，则把每一区间的最右象素作
为种子点压入堆栈，返回第（ 2）步。
4.5.6.2 区域填充的扫描线算法
? typedef struct{ //记录种子点
? int x;
? int y；
? } Seed;
? void ScanLineFill4(int x,int y,COLORREF
oldcolor,COLORREF newcolor)
? { int xl,xr,i;
? bool spanNeedFill;
? Seed pt;
? setstackempty();//设栈空
? pt.x =x; pt.y=y;
? stackpush(pt); //将前面生成的区段压入堆栈
4.5.6.2 区域填充的扫描线算法
? while(!isstackempty())//检查堆栈状态，空返回 F，否则返回 T
? { pt = stackpop();//取堆栈顶元素
? y=pt.y;
? x=pt.x;
? while(getpixel(x,y)==oldcolor) //向右填充
? { Putpixel(x,y,newcolor);
? x++;
? }
? xr = x-1;
? x = pt.x-1;
? while(getpixel(x,y)==oldcolor) //向左填充
? { Putpixel(x,y,newcolor);
? x--;
? }
4.5.6.2 区域填充的扫描线算法
? xl = x+1;
? //处理上面一条扫描线
? x = xl;
? y = y+1;
? while(x<xr)
? { spanNeedFill=FALSE;
? while(getpixel(x,y)==oldcolor)
? { spanNeedFill=TRUE;
? x++;
? }
? if(spanNeedFill)
? { pt.x=x-1;pt.y=y;
? stackpush(pt);
? spanNeedFill=FALSE;
? }
? while(getpixel(x,y)!=oldcolor && x<xr) x++;
? }//End of while(i<xr)
4.5.6.2 区域填充的扫描线算法
//处理下面一条扫描线，代码与处理上面一条扫描线类似
? x = xl;
? y = y-2;
? while(x<xr)
? {,...
? }//End of while(i<xr)
? }//End of while(!isstackempty())
? }
分析,递归算法与扫描线算法的比较
? 扫描线算法 对于每一个待填充区段，只需压栈
一次；
? 递归算法中,每个象素都需要压栈。
因此，扫描线填充算法提高了区域填充的效率。
4.5.6.2 区域填充的扫描线算法 —例子 1
4.5.6.2 区域填充的扫描线算法 —例子 2
4.6 图像填充区域算法（略）
? 填充图元四种方式：
– （ 1）均匀着色
– （ 2）位图不透明方式
– （ 3）位图透明方式
– （ 4）像素图填充方式
（ 2）（ 3）（ 4）与（ 1）的不同：在确定了区域内的一个像素后，
首先查询它对应的图像中的单元，再以该单元的值按填充方式的
不同显示该像素。
位图不透明方式,若像素对应位图单元为 1，则仍以前景色显示，
若为 0，则以背景色显示。
位图透明方式,若像素对应位图单元为 1，则仍以前景色显示，
若为 0，则不改变颜色（不做任何处理）。
像素图填充方式,以像素对应的像素图单元的颜色植显示。
区域与图像间的位置关系
4.7 字符的表示与输出
? 字符,指数字、字母、汉字等编码符号 。
? 字符编码,8位或 16位编码。
? 字符存储,点阵形式如 8x8,16*8,24*24等形式表示的字库，存
储了每个字符的形状信息，方便在显示器等输出设备上输出。
字库中字库分为 矢量型和点阵型两种 。
? 字符标准：
– ASCII：,美国信息交换用标准代码集”简称 ASCII（ American
Standard Code for Information Interchange）码。它是用 7位二进制数进
行编码表示 128个字符，包括字母、标点、运算符以及一些特殊符号。
– GB2312－ 80,汉字编码的国家标准字符集 GB2312－ 80。该字符集分
为 94个区,94个位，每个符号由一个区码和一个位码共同标识。区码
和位码各用一个字节表示。为了能够区分 ASCII码与汉字编码，采用
字节的最高位来标识：最高位为 0表示 ASCII码；最高位为 1表示汉字
编码。
– UNICODE字符
4.7.1 点阵型字库
在点阵字符库中，每个字符由一个位图表示。该位为 1
表示字符的笔画经过此位，对应于此位的象素应置为字符
颜色 。该位为 0表示字符的笔画不经过此位，对应于此位
的象素应置为背景颜色 。
? 存储,保存字符就是保存其位图，在实际应用中，有多种字体
（如宋体、楷体等），每种字体又有多种大小型号，因此字库的存储
空间是很庞大的，如某种字体型号为 16X24，则保存一个汉字要
16X24=384位 =48字节，常用汉字 6763个，需 324K字节。解决这个问
题一般采用压缩技术。如：黑白段压缩、部件压缩、轮廓字形压缩等。
其中，轮廓字形法压缩比大，且能保证字符质量，是当今国际上最流
行的一种方法。轮廓字形法采用直线或二 /三次 bezier曲线的集合来描
述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮
廓线定义加上一些指示横宽、竖宽、基点、基线等等控制信息就构成
了字符的压缩数据。
? 显示,点阵字符的显示分为 两步 。首先从字库中将它的位图检索
出来。然后将检索到的位图写到帧缓冲器中。
? 见下图
4.7.2 矢量字符
? 矢量字符记录字符的笔画信息而不是整个位图，
具有存储空间小、美观、变换方便等优点。对
于字符的旋转、缩放等变换，点阵字符的变换
需要对表示字符位图中的每一象素进行；而矢
量字符的变换只要对其笔画端点进行变换就可
以了。
? 矢量字符的显示也分为两步。首先从字库中
将它的字符信息。然后取出端点坐标，对其进
行适当的几何变换，再根据各端点的标志显示
出字符。
4.7.3字符属性
1,* 字体 宋体 仿宋体 楷体 黑体 隶书
2,* 字高 宋体 宋体 宋体 宋体
3,* 字宽因子 (扩展 /压缩 ) 大海 大海 大海 大海
4,* 字倾斜角 倾斜 倾斜
5,* 对齐 (左对齐、中心对齐、右对齐 )
6,* 字色
7,* 写方式：替换方式时，对应字符掩模中空
白区被置成背景色。与方式时，这部分区域
颜色不受影响。
作业：了解 TrueType字体
4.8二维光栅图形的混淆与反混淆
? 问题,直线段或图形边界或多或少会呈锯齿状
? 原因,图形信号是连续的，而在光栅显示系统
中，用来表示图形的却是一个个离散的象素。
这种用离散量表示连续量引起的失真现象称之
为混淆 (走样,aliasing)；
? 解决技术,反混淆 (反走样, antialiasing)
– 光栅图形的走样现象除了阶梯状的边界外，还有图
形细节失真（图形中的那些比象素更窄的细节变
宽），狭小图形遗失等现象。常用的反走样方法主
要有,提高分辨率、区域采样和加权区域采样 。
?
4.8.1 二维光栅图形的混淆现象
? 假设：把像素看成中心为坐标点、边长
为 1的正方形。
? 不光滑（阶梯状）
的图形边界
? 图形细节失真
（小变大）
? 狭小图形遗失与
动态图形的闪烁
不光滑（阶梯状）的图形边界 —例子
图形细节失真（小变大）
狭小图形遗失与动态图形的闪烁 （略）
4.8.2 反混淆技术
? 减少或消除混淆现象的算法称为反混淆技术
? 适用于线段和多边形的三种算法
– （ 1）提高分辨率的方法
– （ 2）非加权区域采样的方法
– （ 3）加权区域采样的方法
（ 1）提高分辨率的方法
? 把显示器分辨率（水平、垂直）提高一倍，直线经过两倍的象素，
线段上的阶梯锯齿也增加一倍，但同时每个阶梯的宽度也减小了
一倍，所以显示出的直线段看起来就平直光滑了一些。这种 反走
样方法是以 4倍的存储器代价和扫描转换时间获得的 。因此，增加
分辨率虽然简单，但是不经济的方法，而且它也只能 减轻而不能
消除锯齿问题 。例如：
(Left)用
中点算法扫
描转换的一
条直线
(Right)把显
示器分辨率
提高一倍后
的结果
提高分辨率的示意图
（ 2）非加权区域采样方法
? 直线扫描转换算法假定,像素是抽象的点，面
积为 0，其亮度由覆盖该点的图形亮度决定；
直线段是抽象的线，没有宽度。
? 实际像素,不是一个点，有面积，直线也有宽
度，为了减少混淆，必须改变直线段模型
? 所以假定：
* 每个像素是一个具有一定面积的小区域
* 直线段为具有一定宽度的狭长矩形
非加权区域采样方法的实现步骤：
1）将直线段看成为具有一定宽度的狭长矩形
2）当直线段与象素有交时，求出两者相交区域的面积
3）根据相交区域面积的大小确定该象素的亮度值。
例子：左图为相交示意图，右边为象诉的亮度图
性质
? *直线段对亮度的贡献与相交面积成正比
? *不相交对亮度无贡献
? *相交面积相同，对亮度贡献相同
相交面积的计算：
（ 3）加权区域采样方法
? 加权区域取样方法,相交区域对象素亮度的
贡献依赖于该区域与象素中心的距离 。当直线
经过该象素时，该象素的亮度 F是在两者相交
区域 A’上对滤波器（权函数 w）进行积分的积
分值。滤波器函数 w可以取高斯滤波器。
? 用某种颜色编码的图形生成的基本原理：
在光栅显示器上的图形是一组象素的集
合，其中每个象素都具有某种颜色的编码，
这些象素（及其颜色）是通过对图形的扫描
得到的。
? 图形的扫描过程称为 扫描转换 或 光栅化
?主要内容,基本图形的扫描转换如 线，圆，
椭圆 的扫描转换，及封闭的 多边形的填充问
题,字符处理,图形裁剪, 反走样技术 等。
4.0 概述,--图形生成的基本原理，主要内容
Mathemtaical Equation and
Rasterized pixels
1 1 2 2 3 3 4 4
()
(,),(,),(,),(,),..,(,)
nn
y f x
x y x y x y x y x y
?
数学方程
光栅化的象素点
第四章 基本图形生成算法
? Step1:确定图形的象素
? Step2:确定图形的颜色等属性，并对象
素做写操作
4.0 概述,--图形扫描转换的两个步骤
任务一,因 Step2调用图形设备驱动程序
完成，故仅考虑 Step1的任务，即确定
最能反映图形特征的象素集合 。 --如
何扫描图形？？
例如,1D图形的扫描得到（线宽） 象素序列, 2D
图形的扫描得到一个 封闭的区域 --边界 和 内部填充
图形 或 颜色。
第四章 基本图形生成算法
4.0 概述：
任务二：由于图形要在一个 窗口 中显示，所以还
要确定图形的范围 --图形的 窗口裁剪 技术 注,窗口
裁剪应在
图形扫描
前进行。
裁剪窗口
象素点
第四章 基本图形生成算法
4.0 概述：
任务三,象素序列的锯齿形引起走样，所以要用
反走样技术克服图形走样。
说明,提高显示器的分辨率可以部分克服反走样
但成本太高。
反走样算法基本原理,尽量减少相邻象素点的亮
度或或颜色的差别。
例如：
第四章 基本图形生成算法
4.1 直线生成算法
直线段扫描转换,在扫描过程中，求与直线段最接近的像素点集 。
(误差是多少？？？ )
一个象素宽度的直线扫描的三个算法（ 假设：直线段宽度为
1个象素点，斜率 -1<=k<=1）
? 数值微分法（ DDA）
? 中点画线法
? Bresenham算法。
掌握：
?算法思想
?算法伪代码
?上机编程运行的源代码（ C or C++/Visual C++ ）
基本思路：
问题模型
00
.
(,),., (,)nn
y k x b
X Y X Y
??
??
直线的斜率方程
起点 终点
问题求解步骤
? 从起点
? 到终点（）
00(,)XX
(,)nnXX
数值微分 (DDA)法
? 已知过端点 P0 (x0,y0),P1(x1,y1)的直线段
L(P0,P1),；直线斜率为,画线过程从 x
? 的 左端点 x0开始，向 x右端点步进,步长 =1(个
象素 )，计算相应的 y坐标 y=kx+B；取象素点 (x,
round(y))作为当前点的坐标。计算
? yi+1 = kxi+1+B = kxi+B+kDx = yi+kDx
? 当 Dx=1 yi+1 = yi+k,即：当 x每递增 1,y递增
k(直线斜率 ).
? round(yi)=int(yi+0.5)
数值微分 (DDA)法
? DDA画线算法程序
? void LineDDA(int x0,int y0,int x1,int y1,int
color) /* 假定 x0<x1,-1<=k<=1 */
? { int x；
? float dx,dy,y,k;
? dx= x1-x0;
? dy=y1-y0;
? k=dy/dx;
? y=y0;
? for(x=x0; x<= x1,x++)
? { Putpixel(x,int(y+0.5),color);
? y+=k;
? }
? }
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 举例,用 DDA方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x int(y+0.5) y+0.5
0 0 0
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
数值微分 (DDA)法
? 分析：上述算法仅适用于 | k| ≤1 的情形 。特
点是：在这种情况下,x每增加 1,y最多增
加 1。当 | k| > 1时，必须把 x,y地位互换，
y每增加 1,x相应增加 1/k。
? 缺点,在这个算法中,y与 k必须用浮点数表示，
而且每一步都要对 y进行四舍五入后取整。这
使得它 不利于硬件实现。
4.2 中点画线法
? 中点画线法的基本原理：
画直线段的过程中，当前
象素点为 (xp,yp)，下一
个象素点有 两种可选择点
p1(xp+1,yp)或 p2(xp+1,
yp+1)。若 M=(xp+1,
yp+0.5)为 p1与 p2之中点，
Q为理想直线与 x=xp+1垂
线的交点。当 M在 Q的下方,
则 P2 应为下一个象素点；
M在 Q的上方，应取 P1 为
下一点。
中点画线法
? 中点画线法的算法：
? 令直线段 L(p0(x0,y0),p1(x1,y1)),其方程式 F(x,
y)=ax+by+c=0。其中,a=y0-y1,b=x1-x0,c=x0y1-
x1y0; 点与 L的关系,on,F(x,y)=0; up,F(x,y)>0;
down,F(x,y)<0;
因此，欲判断中 M在 Q点的上方还是下方，只要把 M代入 F（ x，
y），并判断它的符号。
构造判别式,
d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c
1,当 d<0,M在 L(Q点 )下方，取 P2为下一个象素；
2,当 d>0,M在 L(Q点 )上方，取 P1为下一个象素；
3,当 d=0,选 P1或 P2均可，约定取 P1为下一个象
素；
中点画线法
判别式 d的计算,注意到 d是 xp,yp的线性函数，可采用增量计算，提
高运算效率,
若当前象素处于 d>=0情况，则取正右方象素 P1（ xp+1,yp）,要判下
一个象素位置，应计算
d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量为 a
若 d<0时，则取右上方象素 P2（ xp+1,yp+1）。要判断再下一象素，
则要计算
d2= F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ； 增量为 a＋ b
画线从 (x0,y0)开始,d的初值 d0=F(x0+1,y0+0.5)=F(x0,
y0)+a+0.5b 因 F(x0,y0)=0，则 d0=a+0.5b。
由于我们使用的只是 d的符号，而且 d的增量都是整数，只是初始值
包含小数。因此，我们可以用 2d代替 d来摆脱小数，写出仅包含整数
运算的算法。
中点画线法
算法程序
void MidpointLine (int x0,int y0,int x1,int y1,int color)
{ int a,b,d1,d2,d,x,y;
a=y0-y1；
b=x1-x0；
d=2*a+b;
d1=2*a；
d2=2*(a+b);
x=x0；
y=y0;
Putpixel(x,y,color);
while (x<x1)
{ if (d<0) {x++,y++,
d+=d2; }
else {x++,d+=d1;}
Putpixel (x,y,color);
} /* while */
} /* mid PointLine */
中点画线法
举例 用中点画线方法扫描转换连接两点 P0（ 0,0）和 P1（ 5,2）的直
线段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-
4;d2=2*(a+b)=6,
X y d
0 0 1
1 0 -3 d1
2 1 3 d2
3 1 -1 d1
4 2 5 d2
4.3 Bresenham算法
? 基本原理,该方法类似于中点法，由误差
项符号决定下一个象素取右边点还是右上
点。 是计算机图形学领域使用最广泛的直
线扫描转换算法。
算法原理, 过各行各列象
素中心构造一组虚拟网格线。
按直线从起点到终点的顺序计
算直线与各垂直网格线的交点，
然后确定该列象素中与此交点
最近的象素。该算法的巧妙之
处在于采用 增量计算,使得对
于每一列，只要检查一个误差
项的符号，就可以确定该列的
所求象素。
Bresenham算法
? 图示
设直线方程为,
其中 k=dy/dx。 假设 x列的象素已经确定为 xi，
其行坐标为 yi。那么下一个象素的列坐标为 xi＋ 1，
而行坐标要么不变为 yi，要么递增 1为 yi＋ 1。是
否增 1取决于如图所示误差项 d的值。因为直线的
起始点在象素中心，所以误差项 d的初值 d0＝ 0。
X下标每增加 1,d的值相应递增直线的斜率值 k，
即 d＝ d＋ k。一旦 d≥1,就把它减去 1，这样保证
d在 0,1之间。当 d≥0.5 时，直线与 xi＋ 1列垂直
网格交点最接近于当前象素（ xi,yi）的右上方
象素（ xi＋ 1,yi＋ 1）；而当 d<0.5时，更接近于
右方象素（ xi＋ 1,yi）。为方便计算，令 e＝ d－
0.5,e的初值为－ 0.5，增量为 k。当 e≥0 时，取
当前象素（ xi,yi）的右上方象素（ xi＋ 1,yi＋
1）；而当 e<0时，更接近于右方象素（ xi＋ 1，
yi）。
Bresenham算法
Bresenham画线算法程序：
void Bresenhamline (int x0,int y0,int x1,int y1,int color)
{ int x,y,dx,dy;
float k,e;
dx = x1-x0;
dy = y1- y0;
k=dy/dx;
e=-0.5;
x=x0;
y=y0;
for (i=0; i<=dx; i++)
{ Putpixel (x,y,color);
x=x+1;
e=e+k;
if (e>= 0)
{ y++,e=e-1;}
}
}
Bresenham算法
举例,用 Bresenham方法扫描转换连接两点 P0（ 0,0）
和 P1（ 5,2）的直线段。
x y e
0 0 -0.5
1 0 -0.1 0.3-1
2 1 -0.7
3 1 -0.3 0.1-1
4 2 -0.9
5 2 -0.5
Bresenham算法
分析,上述 bresenham算法在计算直线斜率与误差项时用到小数与除法。
可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可
作如下替换,e=e*2dx,改进的 Bresenham画线算法程序：
void
InterBresenhamline
(int x0,int y0,int x1,int
y1,int color)
{ dx = x1-x0;
dy = y1- y0;
e=-dx;
x=x0;
y=y0;
for (i=0; i<= dx; i++)
{Putpixel (x,y,color);
x++;
e=e+2*dy;
if (e>= 0) { y++; e=e-2*dx;}
}
}
4.4 圆与椭圆的扫描转换
X2+Y2=R2 (X/a)2+(Y/b)2=R2
4.4.1 圆的扫描转换 X2+Y2=R2
圆的定义：
中心,（ xc,yc）
半径,r
的圆弧上的点集。
圆心位于原点的圆有四条
对称轴 x=0,y=0,x=y和 x=-
y。若已知圆弧上一点
（ x,y）,可以得到其关于
四条对称轴的其它 7个点，
这种性质称为 八分对称性 。
因此，只要扫描转换八分
之一圆弧，就可以求出 整
个圆弧的象素集。
显示圆弧上的八个对称点的算法
void CirclePoints(int x,int y,int color)
{ Putpixel(x,y,color); Putpixel(y,x,color);
Putpixel(-x,y,color); Putpixel(y,-x,color);
Putpixel(x,-y,color); Putpixel(-y,x,color);
Putpixel(-x,-y,color); Putpixel(-y,-x,color);
}
中点画圆法
圆函数：
圆上的点：
圆外的点,
圆内的点：
思路,与中点画线法一
样，构造判别式 d。
1,若 则应取 P1为下一象素，而且再下一象素的
判别式为
2,若 则应取 P2为下一象素，而且下一象素的判别式为
讨论按顺时针方向生成第二个八分圆。则第一个象素是 （ 0,R）,
判别式 d的初始值为
圆弧生成的中点算法 (圆心在原点 )
void MidPointCircle(int r,int color)
{ int x,y;
float d;
x=0;
y=r;
d=1.25-r;
Circlepoints (x,y,color);
while(x<=y)
{ if(d<0) d+=2*x+3;
else { d+=2*(x-y)+5;
y--;}
x++;
Circlepoints (x,y,color);
}
}
分析,为提高算法的效率，可将上面算法中的浮点数改成整
数，将乘法运算改加法运算，即仅用整数实现中点画圆法。
（ 留做习题 ）
例子：圆的中心在原点 （ 0,0）,半径为 7
4.4.2 圆弧生成的 Bresenham算法 (略 )
4.4.3 椭圆弧的生成算法
算法：基本同圆弧算法，方程是
F(x,y)=(bx)^2+(ay)^2-(ab)^2.
对称性,4分对称，画第一象限
分段依据：斜率为一点
上段圆弧
下段圆弧
4.4.4 圆弧生成的多边形逼近算法 (略 )
4.4.5 易画曲线的正负法
正负法简介：
易画曲线 ----
（ 1） F(x,y)具有正负划分性
（ 2） F(x,y)二阶导数连续
（ 3） 曲线上各点的曲率半
径大于步长，即在步长度量下，曲
线是平坦的
线宽处理算法
线宽控制：
如何画线宽大于一个像素的线？
选取宽度适当的刷子在屏幕上绘图，刷子轨迹即为所求。
问题：
? 刷子形状如何？（圆形，长方形。。。）
? 非圆形刷子，其朝向如何？（水平、垂直、
变化？）
? 线形如何？
像素复制方法（线刷子）,斜
率在（ -1,1）之间，用垂直刷
子，否则用水平刷子。
优点：实现简单
缺点,线段两端要么垂直，
要么水平；
折线顶点处有缺口；
图元的宽度不均匀；
宽度为偶像素的图元效
果不好；
水平垂直宽度正确，斜
线宽度变小（与斜率有关）
移动刷子方法（方刷子）
优点,实现简单
缺点,线段两端要么垂直，
要么水平；
折线顶点处有缺口；
图元的宽度不均匀；
宽度为偶像素的图元效
果不好；
水平垂直宽度正确，斜
线宽度变大（与斜率有关）
填充图元方法
优点,生成图形质量
高
缺点：
计算量大； 有些图形
的等距线不容易求
线型控制：
一般用位屏蔽器实现
如：用一个 16位整数表示一个位串，当对
应为 1时，显示像素，否则不显示。
以 16个像素为周期重复，在程序实现时将无条件
写像素 Putpixel(x,y,color)改为：
if(位串 [i%16]) Putpixel(x,y,color);
4.5 区域填充算法
图形填充的两个问题：
（ 1）确定哪些像素位于图元的内部
（ 2）以什么颜色填充这些像素
(3) 用什么图形及何种颜色填充
主要内容：
扫描转换矩形，多边形的两种表示方法，扫描转换
多边形的逐点判断算法、扫描线算法、边缘填充算法，判
断一个点关于多边形区域内外关系的射线法、累计角度法、
编码方法，扫描转换扇形区域，区域的表示，区域的连通
性，填充区域的递归算法、扫描线算法，以图像填充区域，
点阵字符与矢量字符。
掌握要点,
1,了解矩形区域的扫描转换；
2,掌握多边形的两种表示方法：顶点表示与点阵表示 ;
3,掌握扫描转换多边形的逐点判断算法、扫描线算法和
边缘填充算法以及它们采用的数据结构，了解这几个
算法各自的优缺点；
4,掌握判断一个点关于多边形区域内外关系的射线法、
累计角度法、编码方法；
5,了解如何扫描转换扇形区域；
6,掌握什么是区域，区域的两种表示方法：内点表示和
边界表示，区域的连通性,4连通和 8连通；
7,掌握填充区域的递归算法、扫描线算法；
8,了解如何以图像来填充一个多边形或一个区域；
9,了解两种典型的字符表示方法：点阵表示和矢量表示，
以及它们的优缺点。
4.5.1 矩阵的扫描转换
问题背景：
矩形是特殊的多边形，但一般多边形的扫描算法要
用到复杂的数据结构，效率不高，而矩形常用且经常会用
到，所以一般图形软件包把它作为一类基本的图元加以设
计。
矩形的表示,四个自由度
（ 1）四个顶点的坐标为
Xmin,Xmax,Ymin,Ymax.
（ 2）左上角坐标（ x,y）,长 l,宽 w
扫描转换程序：
typedef struct {int xmin,xmax,ymin,ymax;}Rectangle;
void FillRectangle(Rectangle *rect,int color)
{int x,y;
for(y=rect->ymin;y<=rect->ymax;y++)
for(x=rect->xmin;x<=rect->xmax;x++)
Putpixel(x,y,color);
} /*end */
问题：
共享边会重复绘制，边界属于谁？
处理规则：
左闭右开，下闭上开（左下原则：左边和下边像
素属于图元）
4.5.2 多边形的扫描转换
多边形的两种表示方法：
1,顶点表示
2,点阵表示
顶点表示,用多边形的顶点序
列（ P0,P1,… Pn）来表示多边形。
顶点表示的优点,直观、几何
意义强、占内存少，易于进行几
何变换，但没有明确指出哪些象
素在多边形内，故不能直接用于
面着色。
点阵表示, 用位于多边形
内的 象素集合 来刻画多边形。
缺点,丢失了许多几何信息。
优点,便于帧缓冲器表示图
形，是面着色所需要的图形
表示形式。
光栅图形的一个基本问题：把多边形的 顶点表示 转换为
点阵表示 。这种转换称为 多边形的扫描转换 。
例如：
多边形的种类
① 凸多边形任意两顶点间的
任意两顶点间的连线均在多边形内
② 凹多边形：任意两顶点间的连线有不在多边 形内
的部分
③ 含内环的多边形
多边形扫描转换的逐点判断算法
算法原理,逐个判断绘图窗口内的
像素，确定它们是否在多边形区域
内部。
void FillPolygonPbyP(Polygon *P,int polygonColor)
{ int x,y;
for(y = ymin;y <= ymax;y++)
for(x = xmin;x <= xmax;x++)
if(IsInside(P,x,y))
PutPixel(x,y,polygonColor);
else PutPixel(x,y,backgroundColor);
}/*end of FillPolygonPbyP() */
问题,如
何判别点
(x,y)关于
多边形区
域 P的内外
关系？
（ 1）射线法
（ 2） 累计角度法
（ 3）编码算法（略）
（ 1） 射线法
步骤：
* 从待判别点 v发出射线
* 求交点个数 k
* k 的奇偶性决定了点与多边形的内外关系
* 奇异情况处理
（ 2）累计角度法
步骤：
* 从 v点向多边形 P顶点
发出射线，形成有向角
* 计算有相交的和，得
出结论
奇异情况处理
优点：简单
缺点：计算量大，速度慢。
扫描线算法
逐点判断法简单，但效率不高，为提高效率，
对不自交多边形，可以用扫描线算法。
扫描线多边形区域填充算法：
按扫描线顺序，计算扫描线
与多边形的 相交区间,再用
要求的颜色显示这些区间的
象素，即完成 填充工作 。区
间的端点可以通过计算扫描
线与多边形边界线的交点获
得。
知识,对于一条扫描线，它
与多边形的交点总是偶数
（若重复，按重复的次数累
加计算交点个数）
对于一条扫描线，多边形的填充过程可以分为四个步
骤：
（ 1） 求交,计算扫描线与多边形各边的交点；
（ 2） 排序,把所有交点按 x值递增顺序排序；
（ 3） 配对,第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间，
（ 4） 填色,把相交区间内的象素置成多边形颜色，
把相交区间外的象素置成背景色。
关键问题：求交！ 为了减少求交的计算量，可以利
用 边的连贯性：相邻扫描线与边的交点的坐标有连贯
性
第一类交点,新出现的边与扫描线的交点，
第二类交点,位于同一条变上的后继交点
第一类交点,新出现的边与扫描
线的交点，
第二类交点,位于同一条变上
的后继交点
边的数据结构为
typedef struct {int ymax; float x,deltax; struct Edge *nextEdge;}
Edge;
参数含义：
1,ymax,边的上端点 y坐标 ;
2,x:初值为边下端点的 x坐标,AEL中为当前扫描线与边的
交点的 X坐标 ;
3,deltax:边的斜率的倒数；
4,nextEdge:指向下一条边的指针。
为了提高效率，在处理一条扫描线时,仅对与它相交的多边形
的边进行求交运算 。我们把 与当前扫描线相交的边称为活性边，
并把它们按与扫描线交点 x坐标递增的顺序 存放在一个链表中，
称此链表为 活性边表 (AEL)。
算法分析
假定当前扫描线与多边形某一条边的交点的 x坐
标为 x，则下一条扫描线与该边的交点不要重计
算，只要加一个增量△ x。
设该边的直线方程为,ax+by+c=0；
若 y＝ yi,x=xi；则当 y = yi+1时，
其中 为常数，
另外使用增量法计算时，我们 需要知道一条
边何时不再与下一条扫描线相交，以便及时把
它从活性边表中删除出去。
为了方便活性边表的建立与更新，我们 为每
一条扫描线建立一个新边表（ NET）,存放在该
扫描线第一次出现的边。也就是说，若某边的
较低端点为 ymin，则该边就放在扫描线 ymin的
新边表中。
Question:各
条扫描线的
新边表 NET?
各条扫描线
的新边表 NET
算法与分析
算法
void polyfill (polygon,color)
int color;多边形 polygon;
{ for (各条扫描线 i )
{ 初始化新边表头指针 NET [i]；
把 y min = i 的边放进边表 NET [i];
}
y = 最低扫描线号；
初始化活性边表 AEL为空；
for (各条扫描线 i )
? { 把新边表 NET[i]中的边
结点用插入排序法插入 AEL
表，使之按 x坐标递增顺序
排列；
? 遍历 AEL表，把 y max= i
的结点从 AEL表中删除，并
把 y max > i结点的 x值递增 D
x；
? 若允许多边形的边自相
交，则用冒泡排序法对 AEL
表重新排序；
? 遍历 AEL表，把配对交
点区间 (左闭右开 )上的象素
(x,y)，用 Putpixel (x,y,color)
改写象素颜色值； }
} /* polyfill */
分析,扫描线与多边形顶点相交时，必须明确交
点的取舍：
* 扫描线与多边形相交的边分处扫描线的两
侧，则计一个交点。
* 扫描线与多边形相交的边分处扫描线同侧，
且 yi<yi-1,yi<yi+1,则计 2个交点 (填色 )，如
P2。 若 yi>yi-1,yi>yi+1，则计 0个交点 (不填
色 )。
* 扫描线与多边形边界重合 (当要区分边界
和边界内区域时需特殊处理 )，则计 1个交点。
具体实现时，只需检查顶点的两条边的另外
两个端点的 y值。按这两个 y值中大于交点 y值
的个数是 0,1,2来决定。
扫描线与多边形相交，特殊情况的处理（图
示）
边界标志算法
基本思想是,在帧缓冲器中对多边形的每条边进
行直线扫描转换，亦即对多边形边界所经过的象
素打上标志。然后再采用和扫描线算法类似的方
法将位于多边形内的各个区段着上所需颜色。对
每条与多边形相交的扫描线依从左到右的顺序，
逐个访问该扫描线上的象素。使用一个布尔量
inside来指示当前点是否在多边形内的状态。 Inside
的初值为假，每当当前访问的象素为被打上边标
志的点，就把 inside取反。对未打标志的象素，
inside不变。若访问当前象素时,inside为真，说明
该象素在多边形内，则把该象素置为填充颜色。
边界标志算法：
void edgemark_fill(polydef,color)
多边形定义 polydef； int color;
{ 对多边形 polydef 每条边进行直线扫描转换；
inside = FALSE;
for (每条与多边形 polydef相交的扫描线 y )
for (扫描线上每个象素 x )
{ if(象素 x 被打上边标志 )inside = ! (inside);
if(inside！ = FALSE) drawpixel (x,y,color);
else drawpixel (x,y,background);
}
}
例子：正方形内切 n个圆的边界标志算法
分析和比较：
用软件实现时,扫描线算法与边界标志算法 的执
行速度几乎相同，但由于边界标志算法不必建立
维护边表以及对它进行排序，所以边界标志算法
更适合硬件实现，这时它的执行速度比有序边表
算法快一至两个数量级。
4.5.3 边缘填充算法
原理：以求余运算代替扫描线算法中的排序运算
求余：
(A=0xFFFFFFFF)
算法 1：（以扫描线为中心的边缘填充算法）
1、将当前扫描线上的所有象素着上值为 的
颜色；
2、求余：
for(i = 0;i <= m; i++)
在当前扫描线上，从 x坐标为交点向右求余；
算法 2：（以边为中心的边缘填充算法）
1、将绘图窗口的背景色置为；
2、对多边形的每一条非水平边做：
从该边上的每个象素开始向右求余
4.5.4 栅栏填充算法
4.5.5 扇形扫描转换
? 扇形区域可以直接推广多边形的扫描线
算法，对每条扫描线，先计算交点，再
把配对之间的像素用指定颜色填充。
? 扇形区域的描述,半径，起始角，终止
角（设圆心在原点）
原理,同扫描转换多边
形
问题,如何确定扫描线
与直线段和圆弧段的相
交顺序
方法：分类
按起点和终点所处象限的不同，需要将扇形
区域分成 4× 4=16种情况：
? * 假设起点落在第一象限,扇形区域的扫描转换
可分四种情况
1、终点落在第一象限
2、终点落在第二象限，此时又分为两种情况
– y2>=y1 y2<y1
3、终点落在第三象限
4、终点落在第四象限
*当起点落在其它象限时，一般是先旋转，使起
点在第一象限，待扫描转换后再转 回去。
4.5.6 连通区域填充算法
? 基本 概念
? 区域 ----指已经表示成 点阵形式 的填充图形，它
是 象素的集合 。
*区域可采用 内点表示和边界表示 两种表示形式。
– 内点表示,n枚举出区域内部的所有像素，内部的
所有像素着同一个颜色，边界像素着与内部像素不
同的颜色。
– 边界表示,枚举出边界上的所有像素，边界上的
所有像素着同一个颜色，内部像素着与边界像素不
同的颜色。
4.5.6 连通区域填充算法
? 基本 概念
? *区域填充 ----指先将区域的一点（ seed种子 ）赋
予指定的颜色，然后将该颜色扩展（ flood fill）
到整个区域的过程。
? *区域填充算法 前提,连通的区域。
因为只有在连通区域中，才可能将种子点的颜色扩展到区域
内的其它点。
区域连同类型
*区域可分为 4向连通区域 和 8向连通区域。
– 4向连通区域指的是从区域上一点出发，可通
过四个方向，即上、下、左、右移动的组合，
在不越出区域的前提下，到达区域内的任意象
素；
– 8向连通区域指的是从区域内每一象素出发，
可通过八个方向，即上、下、左、右、左上、
右上、左下、右下这八个方向的移动的组合来
到达。
区域连同类型
*区域可分为 4向连通区域 和 8向连通区域。
– 4向连通区域指的是从区域上一点出发，可通
过四个方向，即 上、下、左、右 移动的组合，
在不越出区域的前提下，到达区域内的任意象
素；
四
连
通
区
域
区域连同类型
*区域可分为 4向连通区域 和 8向连通区域。
– 8向连通区域指的是从区域内每一象素出发，
可通过八个方向，即上、下、左、右、左上、
右上、左下、右下这八个方向的移动的组合来
到达。
八
连
通
区
域
区域的内点表示和边界表示 —
例子
4.5.6.1 区域填充的递归算法 --
种子填充算法：
? 种子填充算法,假设在多边形内有一象素 (种
子 )已知，由此出发利用连通性找到 区域内的
所有象素 。
假设,设 （ x,y） 为内点表示的 4连通区域内的一
点,oldcolor为区域的原色（背景色），要将整
个区域填充为新的颜色 newcolor（前景色） 。
算法例子：
– 内点表示 的 4连通区域的递归填充算法。
– 边界表示 的 4连通区域的递归填充算法。
内点表示的 4连通区域的递归填充算法。
? void FloodFill4(int x,int y,int oldcolor,int newcolor)
? { if(getpixel(x,y)==oldcolor)
? { Putpixel(x,y,newcolor);//种子
? FloodFill4(x,y+1,oldcolor,newcolor);//上
? FloodFill4(x,y-1,oldcolor,newcolor);//下
? FloodFill4(x-1,y,oldcolor,newcolor);//左
? FloodFill4(x+1,y,oldcolor,newcolor);//右
? }
? }
边界表示的 4连通区域的递归填充算法。
? void BoundaryFill4(int x,int y,int boundarycolor,int
newcolor)
{ int color;
if(color!=newcolor && color!=boundarycolor)
{ Putpixel(x,y,newcolor);//种子
BoundaryFill4 (x,y+1,boundarycolor,newcolor);//上
BoundaryFill4 (x,y-1,boundarycolor,newcolor);//下
BoundaryFill4 (x-1,y,boundarycolor,newcolor);//左
BoundaryFill4 (x+1,y,boundarycolor,newcolor);//右
}
}
8连通区域的填充算法
? 对于内点表示和边界表示的 8连通区域的
填充，只要将上述相应代码中递归填充
相邻的 4个象素增加到递归填充 8个象素
即可。 （留做练习）
递归算法分析
? 算法简单，效率不高！
? 原因：
– 递归算法需要较多内存
– 不方便并行运行
– 多次重复判断同一象素点
4.5.6.2 区域填充的扫描线算法
? 基本过程, 当给定 种子点 (x,y)时,首先 填充种子点所在扫描线
上的位于给定区域的一个区段，然后确定与这一区段相连通的 上、
下两条扫描线上 位于给定区域内的区段，并依次保存下来。反复这
个过程，直到填充结束。
? 四个步骤
– (1)初始化,堆栈置空。将种子点（ x,y）入栈。
– (2)出栈,若栈空则结束。否则取栈顶元素（ x,y），
以 y作为当前扫描线。
– (3)填充并确定种子点所在区段,从种子点（ x,y）
出发，沿当前扫描线向左、右两个方向填充，直到
边界。分别标记区段的左、右端点坐标为 xl和 xr。
– (4)确定新的种子点,在区间 [xl,xr]中检查与当前扫
描线 y上、下相邻的两条扫描线上的象素。若存在非
边界、未填充的象素，则把每一区间的最右象素作
为种子点压入堆栈，返回第（ 2）步。
4.5.6.2 区域填充的扫描线算法
? typedef struct{ //记录种子点
? int x;
? int y；
? } Seed;
? void ScanLineFill4(int x,int y,COLORREF
oldcolor,COLORREF newcolor)
? { int xl,xr,i;
? bool spanNeedFill;
? Seed pt;
? setstackempty();//设栈空
? pt.x =x; pt.y=y;
? stackpush(pt); //将前面生成的区段压入堆栈
4.5.6.2 区域填充的扫描线算法
? while(!isstackempty())//检查堆栈状态，空返回 F，否则返回 T
? { pt = stackpop();//取堆栈顶元素
? y=pt.y;
? x=pt.x;
? while(getpixel(x,y)==oldcolor) //向右填充
? { Putpixel(x,y,newcolor);
? x++;
? }
? xr = x-1;
? x = pt.x-1;
? while(getpixel(x,y)==oldcolor) //向左填充
? { Putpixel(x,y,newcolor);
? x--;
? }
4.5.6.2 区域填充的扫描线算法
? xl = x+1;
? //处理上面一条扫描线
? x = xl;
? y = y+1;
? while(x<xr)
? { spanNeedFill=FALSE;
? while(getpixel(x,y)==oldcolor)
? { spanNeedFill=TRUE;
? x++;
? }
? if(spanNeedFill)
? { pt.x=x-1;pt.y=y;
? stackpush(pt);
? spanNeedFill=FALSE;
? }
? while(getpixel(x,y)!=oldcolor && x<xr) x++;
? }//End of while(i<xr)
4.5.6.2 区域填充的扫描线算法
//处理下面一条扫描线，代码与处理上面一条扫描线类似
? x = xl;
? y = y-2;
? while(x<xr)
? {,...
? }//End of while(i<xr)
? }//End of while(!isstackempty())
? }
分析,递归算法与扫描线算法的比较
? 扫描线算法 对于每一个待填充区段，只需压栈
一次；
? 递归算法中,每个象素都需要压栈。
因此，扫描线填充算法提高了区域填充的效率。
4.5.6.2 区域填充的扫描线算法 —例子 1
4.5.6.2 区域填充的扫描线算法 —例子 2
4.6 图像填充区域算法（略）
? 填充图元四种方式：
– （ 1）均匀着色
– （ 2）位图不透明方式
– （ 3）位图透明方式
– （ 4）像素图填充方式
（ 2）（ 3）（ 4）与（ 1）的不同：在确定了区域内的一个像素后，
首先查询它对应的图像中的单元，再以该单元的值按填充方式的
不同显示该像素。
位图不透明方式,若像素对应位图单元为 1，则仍以前景色显示，
若为 0，则以背景色显示。
位图透明方式,若像素对应位图单元为 1，则仍以前景色显示，
若为 0，则不改变颜色（不做任何处理）。
像素图填充方式,以像素对应的像素图单元的颜色植显示。
区域与图像间的位置关系
4.7 字符的表示与输出
? 字符,指数字、字母、汉字等编码符号 。
? 字符编码,8位或 16位编码。
? 字符存储,点阵形式如 8x8,16*8,24*24等形式表示的字库，存
储了每个字符的形状信息，方便在显示器等输出设备上输出。
字库中字库分为 矢量型和点阵型两种 。
? 字符标准：
– ASCII：,美国信息交换用标准代码集”简称 ASCII（ American
Standard Code for Information Interchange）码。它是用 7位二进制数进
行编码表示 128个字符，包括字母、标点、运算符以及一些特殊符号。
– GB2312－ 80,汉字编码的国家标准字符集 GB2312－ 80。该字符集分
为 94个区,94个位，每个符号由一个区码和一个位码共同标识。区码
和位码各用一个字节表示。为了能够区分 ASCII码与汉字编码，采用
字节的最高位来标识：最高位为 0表示 ASCII码；最高位为 1表示汉字
编码。
– UNICODE字符
4.7.1 点阵型字库
在点阵字符库中，每个字符由一个位图表示。该位为 1
表示字符的笔画经过此位，对应于此位的象素应置为字符
颜色 。该位为 0表示字符的笔画不经过此位，对应于此位
的象素应置为背景颜色 。
? 存储,保存字符就是保存其位图，在实际应用中，有多种字体
（如宋体、楷体等），每种字体又有多种大小型号，因此字库的存储
空间是很庞大的，如某种字体型号为 16X24，则保存一个汉字要
16X24=384位 =48字节，常用汉字 6763个，需 324K字节。解决这个问
题一般采用压缩技术。如：黑白段压缩、部件压缩、轮廓字形压缩等。
其中，轮廓字形法压缩比大，且能保证字符质量，是当今国际上最流
行的一种方法。轮廓字形法采用直线或二 /三次 bezier曲线的集合来描
述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮
廓线定义加上一些指示横宽、竖宽、基点、基线等等控制信息就构成
了字符的压缩数据。
? 显示,点阵字符的显示分为 两步 。首先从字库中将它的位图检索
出来。然后将检索到的位图写到帧缓冲器中。
? 见下图
4.7.2 矢量字符
? 矢量字符记录字符的笔画信息而不是整个位图，
具有存储空间小、美观、变换方便等优点。对
于字符的旋转、缩放等变换，点阵字符的变换
需要对表示字符位图中的每一象素进行；而矢
量字符的变换只要对其笔画端点进行变换就可
以了。
? 矢量字符的显示也分为两步。首先从字库中
将它的字符信息。然后取出端点坐标，对其进
行适当的几何变换，再根据各端点的标志显示
出字符。
4.7.3字符属性
1,* 字体 宋体 仿宋体 楷体 黑体 隶书
2,* 字高 宋体 宋体 宋体 宋体
3,* 字宽因子 (扩展 /压缩 ) 大海 大海 大海 大海
4,* 字倾斜角 倾斜 倾斜
5,* 对齐 (左对齐、中心对齐、右对齐 )
6,* 字色
7,* 写方式：替换方式时，对应字符掩模中空
白区被置成背景色。与方式时，这部分区域
颜色不受影响。
作业：了解 TrueType字体
4.8二维光栅图形的混淆与反混淆
? 问题,直线段或图形边界或多或少会呈锯齿状
? 原因,图形信号是连续的，而在光栅显示系统
中，用来表示图形的却是一个个离散的象素。
这种用离散量表示连续量引起的失真现象称之
为混淆 (走样,aliasing)；
? 解决技术,反混淆 (反走样, antialiasing)
– 光栅图形的走样现象除了阶梯状的边界外，还有图
形细节失真（图形中的那些比象素更窄的细节变
宽），狭小图形遗失等现象。常用的反走样方法主
要有,提高分辨率、区域采样和加权区域采样 。
?
4.8.1 二维光栅图形的混淆现象
? 假设：把像素看成中心为坐标点、边长
为 1的正方形。
? 不光滑（阶梯状）
的图形边界
? 图形细节失真
（小变大）
? 狭小图形遗失与
动态图形的闪烁
不光滑（阶梯状）的图形边界 —例子
图形细节失真（小变大）
狭小图形遗失与动态图形的闪烁 （略）
4.8.2 反混淆技术
? 减少或消除混淆现象的算法称为反混淆技术
? 适用于线段和多边形的三种算法
– （ 1）提高分辨率的方法
– （ 2）非加权区域采样的方法
– （ 3）加权区域采样的方法
（ 1）提高分辨率的方法
? 把显示器分辨率（水平、垂直）提高一倍，直线经过两倍的象素，
线段上的阶梯锯齿也增加一倍，但同时每个阶梯的宽度也减小了
一倍，所以显示出的直线段看起来就平直光滑了一些。这种 反走
样方法是以 4倍的存储器代价和扫描转换时间获得的 。因此，增加
分辨率虽然简单，但是不经济的方法，而且它也只能 减轻而不能
消除锯齿问题 。例如：
(Left)用
中点算法扫
描转换的一
条直线
(Right)把显
示器分辨率
提高一倍后
的结果
提高分辨率的示意图
（ 2）非加权区域采样方法
? 直线扫描转换算法假定,像素是抽象的点，面
积为 0，其亮度由覆盖该点的图形亮度决定；
直线段是抽象的线，没有宽度。
? 实际像素,不是一个点，有面积，直线也有宽
度，为了减少混淆，必须改变直线段模型
? 所以假定：
* 每个像素是一个具有一定面积的小区域
* 直线段为具有一定宽度的狭长矩形
非加权区域采样方法的实现步骤：
1）将直线段看成为具有一定宽度的狭长矩形
2）当直线段与象素有交时，求出两者相交区域的面积
3）根据相交区域面积的大小确定该象素的亮度值。
例子：左图为相交示意图，右边为象诉的亮度图
性质
? *直线段对亮度的贡献与相交面积成正比
? *不相交对亮度无贡献
? *相交面积相同，对亮度贡献相同
相交面积的计算：
（ 3）加权区域采样方法
? 加权区域取样方法,相交区域对象素亮度的
贡献依赖于该区域与象素中心的距离 。当直线
经过该象素时，该象素的亮度 F是在两者相交
区域 A’上对滤波器（权函数 w）进行积分的积
分值。滤波器函数 w可以取高斯滤波器。
