北大计算机系多媒体与人机交互 1
第四讲 二维图元生成算法
4.1 二维线画图元的生成
4.2 二维填充图元的生成
4.3 反混淆算法
所谓 图元的生成，是指完成图元的参数表示形式 （ 由图形软
件包的使用者指定） 到点阵表示形式 （光栅显示系统刷新时所
需的表示形式） 的转换。通常也称扫描转换图元。
北大计算机系多媒体与人机交互 2
4.1 二维线画图元的生成
？扫描转换直线段
DDA算法
中点画线法
？圆弧、椭圆弧扫描转换
中点算法
内接多边形迫近法
等面积多边形逼近法
？生成圆弧的正负法
？线画图元的属性控制
北大计算机系多媒体与人机交互 3
图形显示的几种方式
图形显示前需要：扫描转换 +裁剪
●裁剪 ---〉 扫描转换：最常用，节约计算时间。
●扫描转换 ---〉 裁剪：算法简单；
●扫描转换到画布 --〉 位块拷贝：算法简单，但耗时耗内
存。常用于字符显示。
? 设备级显示算法，考虑运算方式、时间、
次数等细节。
北大计算机系多媒体与人机交互 4
扫描转换直线段
? 扫描转换直线段
– 求与直线段充分接近的像素集
? 两点假设
– 直线段的宽度为 1
– 直线段的斜率, ]1,1[??m
像素间均匀网格
整型坐标系
北大计算机系多媒体与人机交互 5
扫描转换直线段
? DDA（ digital differential analyzer） 算法
– 条件：
? 待扫描转换的直线段：
? 斜率：
? 直线方程：
– 直接求交算法：
? 划分区间 [x0,x1]:
? 计算纵坐标：
? 取整：
)1,1()0,0( 10 yxPyxP
01,01 yyyxxx ??????
xym ??? /
Bxmy ???
1,,,,110 ??? iin xxxxx 其中?
Bxmy ii ???
niii yx 0)},{( ? nirii yx 0,)},{( ?
)5.0( i n t ) ()(,??? iiri yyr o u n dy
北大计算机系多媒体与人机交互 6
扫描转换直线段
? 复杂度：乘法 +加法 +取整
– DDA算法（增量算法）
? 复杂度：加法 +取整
? 程序：见 45页
mymBxm
BxmBxmy
ii
iii
??????
??????? ?? )1(11
北大计算机系多媒体与人机交互 7
扫描转换直线段
? 中点算法
– 目标：消除 DDA算法中的浮点运算 （ 浮点数取整
运算，不利于硬件实现； DDA算法，效率低）
– 条件：
? 同 DDA算法
? 斜 率：
– 直线段的隐式方程（ (x0,y0)(x1,y1)两端点 ）
F(x,y)=ax+by+c=0
式中 a=y0-y1,b=x1-x0,c=X0Y1-X1Y0
]1,0[?m
北大计算机系多媒体与人机交互 8
扫描转换直线段
– 直线的正负划分性
直线上方点,F(X,Y)＞ 0
直线下方的点 F(X,Y)＜ 0
北大计算机系多媒体与人机交互 9
扫描转换直线段
? 问题：判断距直线最近的下一个象素点
构造判别式,d=F(M)=F(Xp+1,Yp+0.5)
由 d＞ 0,＜ 0可判定下一个象素,
P
P2
P1
北大计算机系多媒体与人机交互 10
? 要判定再下一个象素, 分两种情形考虑：
1） 若 d≥0,取正右方象素 P1,再下一个象素判定,
由,d1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a，
d的增量是 a
2） 若 d＜ 0,取右上方象素 P2,再下一个象素,
由,d2=F(Xp+2,Yp+1.5)=d+a+b
d的增量为 a+b
P2
P
P1
扫描转换直线段
北大计算机系多媒体与人机交互 11
? d的初始值
? d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5
? 因 (X0,Y0)在直线上, F(X0,Y0)=0,所以,
d0=a+0.5b
? d的增量都是整数, 只有初始值包含小数,
可以用 2d代替 d,2a改写成 a+a。
? 算法中只有整数变量, 不含乘除法, 可用
硬件实现 。
扫描转换直线段
北大计算机系多媒体与人机交互 12
程序
Midpointline(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int a,b,d1,d2,2,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);
}
}
北大计算机系多媒体与人机交互 13
扫描转换圆弧
? 处理对象：圆心在原点的圆弧
? 圆的八对称性
北大计算机系多媒体与人机交互 14
? 两种直接离散方法：
离散点,
离散角度,
? 开根，三角函数运算，计算量大，不可
取。
)),(,22
222
riiiii yxxRyx
Ryx
，（
利用隐函数方程
取整 ?? ????
??
))s i n(),c o s((
s i n
c o s
ii Rr o u n dRr o u n d
Ry
Rx
??
?
?
?
?
?
?
?
利用参数方程
北大计算机系多媒体与人机交互 15
扫描转换圆弧
? 圆弧的正负划分性
0),( 222 ???? RyxyxF
圆弧外的点,F(X,Y)＞ 0
圆弧内的点,F(X,Y)＜ 0
北大计算机系多媒体与人机交互 16
扫描转换圆弧
? 生成圆弧的中点算法
– 考虑对象,第二个八分圆，
第一象限的八分之一圆弧
P P1
P2
北大计算机系多媒体与人机交互 17
扫描转换圆弧
? 问题,与直线情形类似
? 圆弧的隐函数,F(X,Y)=X2+Y2-R2=0
切线斜率 m in [-1,0]
? 中点 M=(Xp+1,Yp-0.5),
当 F(M)＜ 0时, M在圆内, 说明 P1距离圆弧更近, 取 P1；
当 F(M)＞ 0时, P取 P2
P2
P1P
北大计算机系多媒体与人机交互 18
? 构造判别式
d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2+(Yp-0.5)2-R2
1） 若 d＜ 0,取 P1,再下一个象素的判别式为：
d1=F(Xp+2,Yp-0.5)=d+2Xp+3，
沿正右方向, d的增量为 2Xp+3；
2） 若 d≥0,取 P2,再下一个象素的判别式为：
d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2)
沿右下方向, d的增量为 2(Xp-Yp)+5
? d的初始值 (在第一个象素 (0,R)处 ),
d0=F(1,R-0.5)=1.25-R
? 算法中有浮点数，用 e=d-0.25代替
扫描转换圆弧
北大计算机系多媒体与人机交互 19
所以：初始化运算 d0 = 1.25 – R 对应于 e 0= 1- R
判别式 d < 0 对应于 e < -0.25
又因为,e的初值 e0为整数，运算过程中的分量也为整数，
故 e始终为整数
所以,e < -0.25 等价于 e < 0
程序如下（ 完全用整数实现 ）：
MidpointCircle(r,color)
Int r,color;
{
int x,y,d;
x = 0; y = r; d = 1-r;
putpixcel(x,y,color);
while( x < y)
{ if (d <0)
{ d += 2*x+3; x++; }
else
{ d += 2*(x-y)+5;
x++ ; y--; }
putpixcel(x,y,color);
}
}
北大计算机系多媒体与人机交互 20
椭圆的扫描转换
? F(x,y)=b2x2+a2y2-a2b2=0
? 椭圆的对称性, 只考虑第一象限椭圆弧
生成, 分上下两部分, 以切线斜率为 -1
的点作为分界点 。
? 椭圆上一点处的法向：
N(x,y) = (F)’x i + (F)’y j
= 2b2 x i + 2a2 y j
北大计算机系多媒体与人机交互 21
在上半部分,法向量的 y分量大
在下半部分,法向量的 x分量大
上半部分
下半部分
法向量
两分量相等M1
M2
在当前中点处，法向量 （ 2b2 (Xp+1), 2a2 (Yp-0.5))的 y分量比 x分量大,
即,b2 (Xp+1) < a2 (Yp-0.5),而在下一中点，不等式改变方
向，则说明椭圆弧从上部分转入下部分
北大计算机系多媒体与人机交互 22
椭圆的中点画法
? 与圆弧中点算法类似：确定一个象素后,
接着在两个候选象素的中点计算一个判
别式的值, 由判别式的符号确定更近的
点
先讨论椭圆弧的上部分
(Xp,Yp)中点 (Xp+1,Yp-0.5)
d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2
北大计算机系多媒体与人机交互 23
根据 d1的符号来决定下一像素是取正右方的那个,
还是右上方的那个 。
? 若 d1＜ 0,中点在椭圆内, 取正右方象素, 判别
式更新为：
d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)
d1的增量为 b2(2Xp+3)
? 当 d1≥0,中点在椭圆外, 取右下方象素, 更新判
别式：
d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)
d1的增量为 b2(2Xp+3)+a2(-2Yp+2)
北大计算机系多媒体与人机交互 24
? d1的初始条件：
椭圆弧起点为 (0,b),第一个中点为 (1,b-0.5)
初始判别式, d10=F(1,b-0.5)=b*b+a*a(-b+0.25)
? 转入下一部分, 下一象素可能是一正下方或右
下方, 此时判别式要初始化 。
d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2
若 d2<0,则 d2’= F(Xp+1.5,Yp-2) = d2 + b2(2Xp+2)+a2(-2Yp+3)
若 d2>=0,则 d2’= F(Xp+0.5,Yp-2) = d2 + a2(-2Yp+3)
下半部分弧的终止条件为 y = 0
北大计算机系多媒体与人机交互 25
程序,MidpointEllipe(a,b,color)
int a,b,color;
{ int x,y; float d1,d2;
x = 0; y = b;
d1 = b*b +a*a*(-b+0.25);
putpixel(x,y,color);
while( b*b*(x+1) < a*a*(y-0.5))
{ { if (d1<0)
d1 +=b*b*(2*x+3); x++; }
else { d1 +=(b*b*(2*x+3)+a*a*(-2*y+2))
x++; y--; }
putpixel(x,y,color);
}//上部分
d2 = sqr(b*(x+0.5)) +sqr(a*(y-1)) – sqr(a*b);
while(y >0)
{ if (d2 <0) { d2 +=b*b*(2*x+2)+a*a*(-2*y+3);
x++; y--； }
else {d2 += a*a*(-2*y+3); y--; }
putpixel(x,y,color); }
北大计算机系多媒体与人机交互 26
用正多边形近似代替圆,显示多边形的边可用
扫描转换直线段的中点算法来实现。
生成圆弧的多边形逼近法
圆的正内接多边形迫近法
圆的等面积正多边形迫近法
北大计算机系多媒体与人机交互 27
生成圆弧的多边形逼近法
– 圆的正内接多边形迫近法
? 原理
? 计算多边形各顶点的递推公式
Xi+1 cos a - sin a Xi
=
Yi +1 sin a cosa Yi
因为, a是常数,sin a,cosa只在开始时计算一次
所以，一个顶点只需 4次乘法，共 4n次乘法，外
加直线段的中点算法的计算量。
圆边正内接多边形） ??? nn (lim
北大计算机系多媒体与人机交互 28
?问题：
给定最大逼近误
差（最大 距离）
DELTA,如何确
定多边形的边数
n或 a？
?
?2?n
另外，用矢量运算可以简化计算，推出求顶点的逆推公式 (p60)
d = R – Rcos(a/2) <= DELTA
cos(a/2) >= (R – DELTA)/R
a <= 2 arc cos (R – DELTA)/R
amax =2 arc cos (R – DELTA)/R
n = 360 /a
北大计算机系多媒体与人机交互 29
生成圆弧的多边形逼近法
- 圆的等面积正多边形迫近法
步骤：
?求多边形径
长，从而求
所有顶点生
标值
?由逼近误差
值，确定边
所对应的圆
心角 α
北大计算机系多媒体与人机交互 30
扇形 ODCE的面积 = 三角形 OPiPi+1的面积 (P60页 )
北大计算机系多媒体与人机交互 31
生成圆弧的正负法
? 正负法简介
– 基本原理
假定初始点 P0 ∈ G0，沿某方
向 (假定为 X轴）前进△ X时，到
达 G+或 G-(假定为 G-)中的 P1,在
沿另外一方向 (Y轴 )前进△ Y,到
达 P2。若 P2 ∈ G+，则改变前进
方向，否则继续向 G+前进。 … …
– 易画曲线
? F(x,y)具有正负划分性
? F(x,y)二阶连续
? 曲线上各点曲率半径足够大
北大计算机系多媒体与人机交互 32
生成圆弧的正负法
– 初始定向
? 确定 的符号yx ??,
北大计算机系多媒体与人机交互 33
生成圆弧的正负法
– 前进规则
? 取判别式
xPP
yPP
i
i
?
?
在异侧时，前进与当
在同侧时，前进与当
1
1
)2(
)1(
),(),()()()( 001 yxxFyxFPFPFPD iiii ??????
xPD
yPD
i
i
??
??
时，前进当
时，前进当
0)()2(
0)()1(
北大计算机系多媒体与人机交互 34
生成圆弧的正负法
? 正负法生成圆弧
– 考虑第一像限圆弧段
– 圆弧是易画曲线
取初始点 P0(x0,y0) = (0,R)
初始定向为,D = 4,△ X=1,△ y = -1
则 P1为 （ x0+1,y0) = (1,R);又因为
D(Pi) = F(Pi)F(P1) = F(Pi)F(1,R)
所以由前进规则得前进点递推公式
1）当 D(Pi) >=0时,Xi+1 = Xi,Yi+1 = yi-1;
2) 当 D(Pi) <0时,Xi+1 = Xi+1,Yi+1 = yi；
判别式 D(Pi+1)的递推公式见,P63
判别式的初值 D(P1) = F(P1)= F(1,R) = 1
北大计算机系多媒体与人机交互 35
线画图元的属性控制（ 1/5）
? 线宽控制
– 像素复制方法
? 优点：
– 实现简单
? 缺点：
– 线段两端要么为水平的，要么是竖直的
– 折线顶点处有缺口
北大计算机系多媒体与人机交互 36
线画图元的属性控制（ 2/5）
– 图元的宽度不均匀
– 产生宽度为偶数像素的图元效果不好
北大计算机系多媒体与人机交互 37
线画图元的属性控制（ 3/5）
– 移动刷子
北大计算机系多媒体与人机交互 38
线画图元的属性控制（ 4/5）
– 利用填充图元
? 优点：
– 生成的图形质量高
? 缺点
– 计算量大
– 有些图形的等距线难以获得
例 1,PaintBrush 例 2:PhotoShop
北大计算机系多媒体与人机交互 39
线画图元的属性控制（ 5/5）
? 线型控制
1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0
?例子,PowerPoint
北大计算机系多媒体与人机交互 40
4.2 二维填充图元的生成
4.2.1 扫描转换矩形
4.2.2 扫描转换多边形
逐点判断法、扫描线算法、边缘填充算法
4.2.3 扫描转换扇形
4.2.4 区域填充（ 种子填充法）
递归填充算法、扫描线算法
4.2.5 以图像填充区域
4.2.6 字符的表示与输出
一般步骤
? 确定那些像素
位于填充图元
的内部；
? 确定以什么颜
色填充这些像
素；
北大计算机系多媒体与人机交互 41
4.2.1 扫描转换矩形（ 1/2）
? 方法：
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 of FillRectangle() */
北大计算机系多媒体与人机交互 42
4.2.1扫描转换矩形（ 2/ 2）
? 问题：
– 矩形是简单的多边形，那么为什么要单独处
理矩形？
比一般多边形可简化计算。
应用非常多，窗口系统。
– 共享边界如何处理？
? 原则：左闭右开，下闭上开
属于谁？
北大计算机系多媒体与人机交互 43
4.2.2 扫描转换多边形
? 多边形的表示方法
– 顶点表示
– 点阵表示
– 扫描转换多边形：将顶点表示形式转换成点阵表示
形式
– 三种方法,逐点判断法；扫描线算法；边缘填充法 。
北大计算机系多媒体与人机交互 44
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() */
#define MAX 100
Typedef struct { int PolygonNum; // 多边形顶点个数
Point vertexces[MAX] //多边形顶点数组
} Polygon // 多边形结构
逐点判断法
北大计算机系多媒体与人机交互 45
逐点判断法
? 逐个判断绘图窗口内的像素：
? 如何判断点在多边形的内外关系？
1）射线法：
2）累计角度法
3）编码法；
北大计算机系多媒体与人机交互 46
逐点判断法
1）射线法
? 步骤：
1,从待判别点 v发出射线
2,求交点个数 k
3,K的奇偶性决定了点与多边形的内外关系
? 奇异情况处理
北大计算机系多媒体与人机交互 47
逐点判断法
2）累计角度法
? 步骤
1,从 v点向多边形 P顶点发出射线，形成 有向 角
2,计算有相交的和，得出结论
? 预处理
? 离散计算方法：编码方法
?
?
?
???? 之内位于
之外位于，
Pv
Pvn
i
i,2
0
0 ?
?
i?
北大计算机系多媒体与人机交互 48
3）编码方法,累计角度方法的离散方法
Step:
a.预处理，测试点在边上否？
b.V为中点作局部坐标系,对象限按逆
时针（或顺时针）编码；
c.顶点编码 Ipi，
d.边编码。 PiPi+1,△ PiPi+1=Ipi+1-Ipi
e.计算 ∑ △ PiPi+1 （其中△ PnPn+1 = △ PnP0)：
若 ∑ 为 0,V在 P外； 若 ∑ 为 +/-4,V 在 P内；
逐点判断法程序简单，
速度太慢，效率低。
P0
P1
P2
v
逐点判断法
北大计算机系多媒体与人机交互 49
扫描线算法
? 扫描线算法
– 目标：利用相邻像素之间的连贯性，提高算
法效率
– 处理对象：非自交多边形 （边与边之间除
了顶点外无其它交点）
北大计算机系多媒体与人机交互 50
扫描线算法
– 基本原理
一条扫描线与多边形的边有偶数个交点
– 步骤 (对于每一条扫描线 ):
(1)求交点
(2)交点排序
(3)交点配对，填充区段。
北大计算机系多媒体与人机交互 51
扫描转换多边形 (7/ 19)
– 边的连贯性
? 第一类交点：新出现的边与扫描线的交点
? 第二类交点：位于同一条边上的后继交点
北大计算机系多媒体与人机交互 52
扫描转换多边形 (8/ 19)
– 交点的取整规则
? 要求：使生成的像素全部位于多边形之内
– 用于线画图元扫描转换的四舍五入原则导致部分像素
位于多边形之外，从而不可用
? 假定非水平变与扫描线 y=e
相交，交点的横坐标为 x,
规则如下
北大计算机系多媒体与人机交互 53
扫描线算法
● 规则 1：
X为小数，即交点落于扫描线上两个相邻像素之间
(a)交点位于左边之上，向右取整
(b)交点位于右边之上，向左取整
北大计算机系多媒体与人机交互 54
● 规则 2：
边界上象素的取舍问题，避免填充扩大化。
● 解决方法：
边界象素：规定落在右上边界的象素不予填充。
具体实现时，只要对扫描线与多边形的相交区间左闭右开
扫描线算法
北大计算机系多媒体与人机交互 55
● 规则 3：
扫描线与多边形的顶点相交时，交点的取舍，保证交点正
确配对。
● 解决方法：
检查两相邻边在扫描线的哪一侧。
只要检查顶点的两条边的另外两个端点的 Y值，两个 Y值中大于交点 Y
值的个数是 0,1,2，来决定取 0,1,2个交点。
扫描线算法
北大计算机系多媒体与人机交互 56
扫描线算法
1） 活性边：与当前扫描线相交的边。按交点 x的增量顺序
存放在一个链表中；该链表称作 活性 边表（ AEL)。
算法所涉及的数据结构：
?AEL 与 ET的结点信息（ p75）：
?Ymax,所交边的最高扫描线号
?X：当前扫描线与边的交点的 x坐标
?△ X：边的斜率的倒数
?Nextage,下一条边的指针
typedef struct {int ymax;
float x,deltax;
Edge *nextEdge;
}Edge;
北大计算机系多媒体与人机交互 57
扫描线算法
2）边的分类表 （ ET）
按照边的下端点 y坐标对非水平边进行分类的指针数组,
下端点 y坐标值等于 i的边属于第 i类
typedef struct {int ymax;
float x,deltax;
Edge *nextEdge;
}Edge;
边的分类表的作用是避免盲目求交。
当处理一条扫描线时，为了求出它
与多边形边的所有交点，必须将它
与所有的边进行求交测试。而实际
上只有某几条边与该扫描线有交点。
边的分类表正是用来排除不必要的
求求交测试的。
例如,P76 图 4.17
北大计算机系多媒体与人机交互 58
扫描线算法
– 算法
1、建立 ET；
2、将扫描线纵坐标 y的初值置为 ET中非空元素的最小序号，如在上图中，
y=1；
3、置 AEL为空；
4、执行下列步骤直至 ET和 AEL都为空．
4.1、如 ET中的第 y类非空，则将其中的所有边取出并插入 AEL中；
4.2、如果有新边插入 AEL，则对 AEL中各边排序；
4.3、对 AEL中的边两两配对，（ 1和 2为一对,3和 4为一对,… ），将每
对边中 x坐标按规则取整，获得有效的填充区段，再填充．
4.4、将当前扫描线纵坐标 y值递值 1；
4.5、将 AEL中满足 y=ymax边删去（因为每条边被看作下闭上开的）；
4.6、对 AEL中剩下的每一条边的 x递增 deltax，即 x = x+deltax．
北大计算机系多媒体与人机交互 59
?边的连贯性,某条边与当前扫描线相交，也可能与
下一条扫描线相交；
?扫描线的连贯性,当前扫描线与各边的交点顺序与
下一条扫描线与各边的交点顺序可能相同或类似；
?区间连贯性,同一区间上的像素取同一颜色属性
几个概念
北大计算机系多媒体与人机交互 60
边缘填充算法
▼ 求余运算,假定 A为一个正整数，则 M的余定义为
A – M,记为 。计算机中取 A为 n位能表示的最大整数。
即,A=0xFFFFFFFF
▼ 由来,光栅图形中，如果某区域已着上值为 M的颜色
值做偶数次求余运算，该区域颜色不变；而做奇数次
求余运算，则该区域颜色变为值为 的颜色。这一
规律应用于多边形扫描转换，就为边缘填充算法。
▼ 求余运算可用异或显示模式实现。
▼算法基本思想,对于每条扫描线和每条多边形边的交
点，将该扫描线上交点右方的所有象素取余。
AX o rMMAM ???
M
M
北大计算机系多媒体与人机交互 61
算法 1（以扫描线为中心的边缘填充算法）
1、将当前扫描线上的
所有象素着上 颜色；
2、求余：
for(i = 0;i <= m; i++)
在当前扫描线上，
从横坐标为 Xi的交点
向右求余；
M
北大计算机系多媒体与人机交互 62
算法 2（以边为中心的边缘填充算法）
1、将绘图窗口的背景色置为 ；
2、对多边形的每一条非水平边做：
从该边上的每个象素开始向右求余；
M
北大计算机系多媒体与人机交互 63
边缘填充算法
? 适合用于具有帧缓存的图形系统。处理
后，按扫描线顺序读出帧缓存的内容，
送入显示设备。
? 优点：算法简单
? 缺点：对于复杂图形，每一象素可能被
访问多次，输入 /输出的量比扫描线算法
大得多。
北大计算机系多媒体与人机交互 64
4.2.3 扫描转换扇形区域 (1/5)
? 扇形区域的描述,
? 原理：同扫描转换多边形
? 问题：如何确定扫描线与直线段和圆弧段的相
交顺序
? 方法：分类
按点 和 点所处象限的不同，需要将扇形区域分成
4× 4=16种情况
p1 2p
北大计算机系多媒体与人机交互 65
4.2.3 扫描转换扇形区域 (2/5)
? 假设 点落在第一象限,扇形区域的扫描
转换 分四种情况
1,落在第一象限
p1
2p
北大计算机系多媒体与人机交互 66
4.2.3 扫描转换扇形区域 (3/5)
2,落在第二象限，此时又分为两种情况
? 当 时
? 当 时
2p
y y1 2?
21 yy ?
北大计算机系多媒体与人机交互 67
4.2.3扫描转换扇形区域 (4/5)
3,落在第三象限
4,落在第四象限
2p
2p
北大计算机系多媒体与人机交互 68
4.2.3 扫描转换扇形区域 (5/5)
? 遗留问题：当 落在其它区域时?
? 其它方法：
p1
多边形迫近方法
北大计算机系多媒体与人机交互 69
4.2.4 区域填充
? 区域,点阵表示的图形，像素集合
? 表示方法,内点表示、边界表示
? 内点表示
– 枚举处区域内部的所有像素
– 内部的所有像素着同一个颜色
– 边界像素着与内部像素不同的颜色
? 边界表示
– 枚举出边界上所有的像素
– 边界上的所有像素着同一颜色
– 内部像素着与边界像素不同的颜色
北大计算机系多媒体与人机交互 70
区域填充 (种子填充法 )
区域填充 –对 区域重新着色的过程
– 将指定的颜色从 种子点 扩展到整个区域的过程
– 区域填充算法要求区域是连通的
? 连通性
4连通,8连通
? 4连通：
? 8连通
例子,PaintBrush 例子,PhotoShop
北大计算机系多媒体与人机交互 71
区域填充 (种子填充法 )
? 4连通与 8连通区域的区别
– 连通性,4连通可看作 8连通区域，但对边界有要求
– 对边界的要求
北大计算机系多媒体与人机交互 72
区域填充 (种子填充法 )
1）递归填充算法
– 内点表示的 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);
}
}/*end of FloodFill4() */
取 (x,y)为种子点
北大计算机系多媒体与人机交互 73
区域填充 (种子填充法 )
北大计算机系多媒体与人机交互 74
区域填充 (种子填充法 )
– 边界表示的 4连通区域
void BoundaryFill4(int x,int y,int oldColor,int newColor)
{ int color;
color = GetPixel(x,y);
if((color != boundaryColor) && (color != newColor))
{ PutPixel(x,y,newColor);
BoundaryFill4(x,y+1,oldColor,newColor);
BoundaryFill4(x,y-1,oldColor,newColor);
BoundaryFill4(x-1,y,oldColor,newColor);
BoundaryFill4(x+1,y,oldColor,newColor);
}
}/*end of BoundaryFill4() */
北大计算机系多媒体与人机交互 75
? 问题：
内点表示与边界表示的 8连通区域？
? 缺点,
(1) 有些象素会入栈多次，降低算法效率；栈结构占空间。
(2) 递归执行，算法简单，但效率不高，区域内每一象素
都引起一次递归，进 /出栈，费时费内存。
? 改进算法，减少递归次数，提高效率。
方法之一使用扫描线填充算法；
区域填充 (种子填充法 )
北大计算机系多媒体与人机交互 76
区域填充（扫描线算法 )
? 扫描线算法
– 目标：减少递归层次
– 适用于内点表示的 4连通区域
– 基本过程：
当给定种子点时，首先填充种子点所在的扫描线
上的位于给定区域的一个区段，然后确定与这一区
段相通的上下两条扫描线上位于给定区域内的区段，
并依次保存下来。反复这个过程，直到填充结束。
北大计算机系多媒体与人机交互 77
1、填充并确定种子区段 ；
2、初始化,将种子区段压入堆栈；
3、出栈：如果堆栈为空，则算法结束；否则取栈顶元素
（ y,xLeft,xRight），以纵坐标为 y的扫描线为当前
扫描线,[xLeft,xRight]为搜索区间 ；
4、填充并确定新的区段 。
?算法步骤
区域填充（扫描线算法）
北大计算机系多媒体与人机交互 78
区域填充（扫描线算法 )
像素中的序号标指它所在区段位于堆栈中的位置
北大计算机系多媒体与人机交互 79
4.2.5 以图象填充区域
? 四种填充方法：
– (1)均匀着色方法,将图元内部像素置成同一颜色
– (2)位图不透明,若像素对应的位图单元为 1，则以 前景
色 显示该像素；若为 0，则以背景色显示该像素；
– (3)位图透明,若像素对应的位图单元为 1，则以 前景色
显示该像素； 若为 0，则不做任何处理。
– (4)像素图填充,以像素对应的像素图单元的颜色值显
示该像素。
北大计算机系多媒体与人机交互 80
以图像填充区域
? 基本问题
– 关键是建立区域与图像间的对应关系
– 方法 1：建立整个绘图空间与图像空间的 1-1映射
图像（纹理）
北大计算机系多媒体与人机交互 81
以图像填充区域
适用,动画中漫游
图像 – 例，透
过车窗看外景
北大计算机系多媒体与人机交互 82
以图像填充区域
? 方法 2：建立区域局部坐标空间与图像空间的 1-1映射
适用：图像作为区域表面属性的情况，例如，桌面与
其上的木纹。
北大计算机系多媒体与人机交互 83
4.2.6 字符的表示与输出
点阵字符
矢量字符
自学！
北大计算机系多媒体与人机交互 84
思考题
如何修改扫描线算法，使它能处理边自交
的多边形？
北大计算机系多媒体与人机交互 85
4.3.1 混淆现象
4.3.2 反混淆方法
非加权区域采样
加权区域采样
4.3 反混淆方法
北大计算机系多媒体与人机交互 86
4.3.1 混淆现象
混淆, 用离散量 (像素 )表示连续的量 (图形 )而引起的失
真，叫混淆或叫 走样 (aliasing)。
光栅图形的混淆现象
– 阶梯状边界；
– 图形细节失真；
– 狭小图形遗失：动画序列中时隐时现，产生闪烁。
北大计算机系多媒体与人机交互 87
混淆现象（ 1/3）
? 不光滑 (阶梯状）的图形边界
例子,PaintBrush
北大计算机系多媒体与人机交互 88
混淆现象（ 2/3）
? 图形细节失真
北大计算机系多媒体与人机交互 89
混淆现象（ 3/3）
? 狭小图形的遗失与动态图形的闪烁
北大计算机系多媒体与人机交互 90
反混淆方法
? 什么是反混淆
– 在图形显示过程中，用于减少或消除混淆现象
的方法
1）提高分辨率方法
2）非加权区域采样
3）加权区域采样
北大计算机系多媒体与人机交互 91
反混淆方法
? 提高分辨率的反混淆方法
方法简单，但代价非常大。
显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，
帧缓存容量则增加到原来的 4倍，而扫描转换同样大小的图元却要花 4倍
时间。
北大计算机系多媒体与人机交互 92
非加权区域采样方法
? 方法由来
– 两点假设
1,象素是数学上抽象的点, 它的面积为 0,它的亮度由
覆盖该点的图形的亮度所决定；
2、直线段是数学上抽象直线段，它的宽度为 0。
– 现实
? 像素的面积不为 0；
? 直线段的宽度至少为 1个像素；
– 假设与现实的矛盾是导致混淆出现的原因之一
北大计算机系多媒体与人机交互 93
非加权区域采样方法
– 解决方法：改变直线段模型，由此产生算法
– 方法步骤,
1、将直线段看作具有一定宽度的狭长矩形；
2、当直线段与某象素有交时，求出两者相交区域的面积；
3、根据相交区域的面积，确定该象素的亮度值
北大计算机系多媒体与人机交互 94
方法性质：
非加权区域采样方法
1）直线段对一个像素亮度的贡献与两者相交区域的面积成
正比，从而和像素中心点距直线段的距离成反比 (因为像
素中心点距直线段距离越元，相交区域的面积越小）；
2） 当直线段和某个像素不相交时，它对该像素的亮度无影响；
3） 相同面积的相交区域对像素的亮度贡献相同，而与这个相交
区域落在像素内麽位置无关。
关键：如何计算这个面积？
北大计算机系多媒体与人机交互 95
非加权区域采样方法
-- 计算相交区域的面积
D
D.m
面积 =(m*D*D)/2
D - - - - - - m
面积 =D – m/2
像素实际显示的灰度值 == 所得面积 * 该像素的最大灰度值
北大计算机系多媒体与人机交互 96
反混淆方法
– 求相交区域的近似面积的离散计算方法
1、将屏幕象素分割成 n个更小的子象素；
2、计算中心点落在直线段内的子象素的个数，记为 k，
3,k/n为线段与象素相交区域面积的近似值
目的：简化计算
n = 16,k = 3
近似面积 = 3/16
北大计算机系多媒体与人机交互 97
加权区域采样方法
改进 非加权区域采样方法的 第 3条性质,
相交区域对象素亮度的贡献
依赖于该区域与象素中心的距离
北大计算机系多媒体与人机交互 98
加权区域采样方法
– 权函数 W(x,y)
? 以象素 A的中心为原点建立二维坐标系
? w(x,y)反应了微面积元 dA对整个象素亮度的贡献
大小,与 d成反比。
? 权性（为讨论方便而设）
? 位于 (x,y)处的微面积元 dA对像素的亮度的贡献
为 w(x,y) dA
dyxw
1),( ?
1),( ??A dAyxw
北大计算机系多媒体与人机交互 99
加权区域采样方法
– 相交区域 对该象素的亮度贡献?A
w x y dAA (,)??
的面积AdAyxwA ??? ? ),(特例,时，
加权区域采样方法退化为
非加权区域采样方法
北大计算机系多媒体与人机交互 100
加权区域采样方法
– 实现步骤
1,求直线段与象素的相交区域 ；
2,计算的值 ；
3．上面所得到的值介于 0,1之间，用它乘象素的
最大灰度值，即设该象素的显示灰度。
– 问题：计算量大
?A
w x y dAA (,)??
北大计算机系多媒体与人机交互 101
加权区域采样方法
– 离散计算方法
1,将屏幕象素均匀分割成 m个子象素, 则每个子象素
的面积为, 计算每个子象素对原象素亮度的贡献,
记为,将 保存在一张加权表中 ;
2,求出所有中心落于直线段内的子象素, 记为,
3．计算所有这些子象素对原象素亮度贡献之和 该值
乘以象素的最大灰度值即为象素的显示灰度值,
– 加权表的取法
? ?Ai im?1
dA mA
i?
? 1
wi ? ?wi 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
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
北大计算机系多媒体与人机交互 102
上机作业
1,修改扫描线算法，使它能处理边自交的
多边形？
2,实现一个反混淆的算法。
第四讲 二维图元生成算法
4.1 二维线画图元的生成
4.2 二维填充图元的生成
4.3 反混淆算法
所谓 图元的生成，是指完成图元的参数表示形式 （ 由图形软
件包的使用者指定） 到点阵表示形式 （光栅显示系统刷新时所
需的表示形式） 的转换。通常也称扫描转换图元。
北大计算机系多媒体与人机交互 2
4.1 二维线画图元的生成
？扫描转换直线段
DDA算法
中点画线法
？圆弧、椭圆弧扫描转换
中点算法
内接多边形迫近法
等面积多边形逼近法
？生成圆弧的正负法
？线画图元的属性控制
北大计算机系多媒体与人机交互 3
图形显示的几种方式
图形显示前需要：扫描转换 +裁剪
●裁剪 ---〉 扫描转换：最常用，节约计算时间。
●扫描转换 ---〉 裁剪：算法简单；
●扫描转换到画布 --〉 位块拷贝：算法简单，但耗时耗内
存。常用于字符显示。
? 设备级显示算法，考虑运算方式、时间、
次数等细节。
北大计算机系多媒体与人机交互 4
扫描转换直线段
? 扫描转换直线段
– 求与直线段充分接近的像素集
? 两点假设
– 直线段的宽度为 1
– 直线段的斜率, ]1,1[??m
像素间均匀网格
整型坐标系
北大计算机系多媒体与人机交互 5
扫描转换直线段
? DDA（ digital differential analyzer） 算法
– 条件：
? 待扫描转换的直线段：
? 斜率：
? 直线方程：
– 直接求交算法：
? 划分区间 [x0,x1]:
? 计算纵坐标：
? 取整：
)1,1()0,0( 10 yxPyxP
01,01 yyyxxx ??????
xym ??? /
Bxmy ???
1,,,,110 ??? iin xxxxx 其中?
Bxmy ii ???
niii yx 0)},{( ? nirii yx 0,)},{( ?
)5.0( i n t ) ()(,??? iiri yyr o u n dy
北大计算机系多媒体与人机交互 6
扫描转换直线段
? 复杂度：乘法 +加法 +取整
– DDA算法（增量算法）
? 复杂度：加法 +取整
? 程序：见 45页
mymBxm
BxmBxmy
ii
iii
??????
??????? ?? )1(11
北大计算机系多媒体与人机交互 7
扫描转换直线段
? 中点算法
– 目标：消除 DDA算法中的浮点运算 （ 浮点数取整
运算，不利于硬件实现； DDA算法，效率低）
– 条件：
? 同 DDA算法
? 斜 率：
– 直线段的隐式方程（ (x0,y0)(x1,y1)两端点 ）
F(x,y)=ax+by+c=0
式中 a=y0-y1,b=x1-x0,c=X0Y1-X1Y0
]1,0[?m
北大计算机系多媒体与人机交互 8
扫描转换直线段
– 直线的正负划分性
直线上方点,F(X,Y)＞ 0
直线下方的点 F(X,Y)＜ 0
北大计算机系多媒体与人机交互 9
扫描转换直线段
? 问题：判断距直线最近的下一个象素点
构造判别式,d=F(M)=F(Xp+1,Yp+0.5)
由 d＞ 0,＜ 0可判定下一个象素,
P
P2
P1
北大计算机系多媒体与人机交互 10
? 要判定再下一个象素, 分两种情形考虑：
1） 若 d≥0,取正右方象素 P1,再下一个象素判定,
由,d1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a，
d的增量是 a
2） 若 d＜ 0,取右上方象素 P2,再下一个象素,
由,d2=F(Xp+2,Yp+1.5)=d+a+b
d的增量为 a+b
P2
P
P1
扫描转换直线段
北大计算机系多媒体与人机交互 11
? d的初始值
? d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5
? 因 (X0,Y0)在直线上, F(X0,Y0)=0,所以,
d0=a+0.5b
? d的增量都是整数, 只有初始值包含小数,
可以用 2d代替 d,2a改写成 a+a。
? 算法中只有整数变量, 不含乘除法, 可用
硬件实现 。
扫描转换直线段
北大计算机系多媒体与人机交互 12
程序
Midpointline(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int a,b,d1,d2,2,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);
}
}
北大计算机系多媒体与人机交互 13
扫描转换圆弧
? 处理对象：圆心在原点的圆弧
? 圆的八对称性
北大计算机系多媒体与人机交互 14
? 两种直接离散方法：
离散点,
离散角度,
? 开根，三角函数运算，计算量大，不可
取。
)),(,22
222
riiiii yxxRyx
Ryx
，（
利用隐函数方程
取整 ?? ????
??
))s i n(),c o s((
s i n
c o s
ii Rr o u n dRr o u n d
Ry
Rx
??
?
?
?
?
?
?
?
利用参数方程
北大计算机系多媒体与人机交互 15
扫描转换圆弧
? 圆弧的正负划分性
0),( 222 ???? RyxyxF
圆弧外的点,F(X,Y)＞ 0
圆弧内的点,F(X,Y)＜ 0
北大计算机系多媒体与人机交互 16
扫描转换圆弧
? 生成圆弧的中点算法
– 考虑对象,第二个八分圆，
第一象限的八分之一圆弧
P P1
P2
北大计算机系多媒体与人机交互 17
扫描转换圆弧
? 问题,与直线情形类似
? 圆弧的隐函数,F(X,Y)=X2+Y2-R2=0
切线斜率 m in [-1,0]
? 中点 M=(Xp+1,Yp-0.5),
当 F(M)＜ 0时, M在圆内, 说明 P1距离圆弧更近, 取 P1；
当 F(M)＞ 0时, P取 P2
P2
P1P
北大计算机系多媒体与人机交互 18
? 构造判别式
d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2+(Yp-0.5)2-R2
1） 若 d＜ 0,取 P1,再下一个象素的判别式为：
d1=F(Xp+2,Yp-0.5)=d+2Xp+3，
沿正右方向, d的增量为 2Xp+3；
2） 若 d≥0,取 P2,再下一个象素的判别式为：
d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2)
沿右下方向, d的增量为 2(Xp-Yp)+5
? d的初始值 (在第一个象素 (0,R)处 ),
d0=F(1,R-0.5)=1.25-R
? 算法中有浮点数，用 e=d-0.25代替
扫描转换圆弧
北大计算机系多媒体与人机交互 19
所以：初始化运算 d0 = 1.25 – R 对应于 e 0= 1- R
判别式 d < 0 对应于 e < -0.25
又因为,e的初值 e0为整数，运算过程中的分量也为整数，
故 e始终为整数
所以,e < -0.25 等价于 e < 0
程序如下（ 完全用整数实现 ）：
MidpointCircle(r,color)
Int r,color;
{
int x,y,d;
x = 0; y = r; d = 1-r;
putpixcel(x,y,color);
while( x < y)
{ if (d <0)
{ d += 2*x+3; x++; }
else
{ d += 2*(x-y)+5;
x++ ; y--; }
putpixcel(x,y,color);
}
}
北大计算机系多媒体与人机交互 20
椭圆的扫描转换
? F(x,y)=b2x2+a2y2-a2b2=0
? 椭圆的对称性, 只考虑第一象限椭圆弧
生成, 分上下两部分, 以切线斜率为 -1
的点作为分界点 。
? 椭圆上一点处的法向：
N(x,y) = (F)’x i + (F)’y j
= 2b2 x i + 2a2 y j
北大计算机系多媒体与人机交互 21
在上半部分,法向量的 y分量大
在下半部分,法向量的 x分量大
上半部分
下半部分
法向量
两分量相等M1
M2
在当前中点处，法向量 （ 2b2 (Xp+1), 2a2 (Yp-0.5))的 y分量比 x分量大,
即,b2 (Xp+1) < a2 (Yp-0.5),而在下一中点，不等式改变方
向，则说明椭圆弧从上部分转入下部分
北大计算机系多媒体与人机交互 22
椭圆的中点画法
? 与圆弧中点算法类似：确定一个象素后,
接着在两个候选象素的中点计算一个判
别式的值, 由判别式的符号确定更近的
点
先讨论椭圆弧的上部分
(Xp,Yp)中点 (Xp+1,Yp-0.5)
d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2
北大计算机系多媒体与人机交互 23
根据 d1的符号来决定下一像素是取正右方的那个,
还是右上方的那个 。
? 若 d1＜ 0,中点在椭圆内, 取正右方象素, 判别
式更新为：
d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)
d1的增量为 b2(2Xp+3)
? 当 d1≥0,中点在椭圆外, 取右下方象素, 更新判
别式：
d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)
d1的增量为 b2(2Xp+3)+a2(-2Yp+2)
北大计算机系多媒体与人机交互 24
? d1的初始条件：
椭圆弧起点为 (0,b),第一个中点为 (1,b-0.5)
初始判别式, d10=F(1,b-0.5)=b*b+a*a(-b+0.25)
? 转入下一部分, 下一象素可能是一正下方或右
下方, 此时判别式要初始化 。
d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2
若 d2<0,则 d2’= F(Xp+1.5,Yp-2) = d2 + b2(2Xp+2)+a2(-2Yp+3)
若 d2>=0,则 d2’= F(Xp+0.5,Yp-2) = d2 + a2(-2Yp+3)
下半部分弧的终止条件为 y = 0
北大计算机系多媒体与人机交互 25
程序,MidpointEllipe(a,b,color)
int a,b,color;
{ int x,y; float d1,d2;
x = 0; y = b;
d1 = b*b +a*a*(-b+0.25);
putpixel(x,y,color);
while( b*b*(x+1) < a*a*(y-0.5))
{ { if (d1<0)
d1 +=b*b*(2*x+3); x++; }
else { d1 +=(b*b*(2*x+3)+a*a*(-2*y+2))
x++; y--; }
putpixel(x,y,color);
}//上部分
d2 = sqr(b*(x+0.5)) +sqr(a*(y-1)) – sqr(a*b);
while(y >0)
{ if (d2 <0) { d2 +=b*b*(2*x+2)+a*a*(-2*y+3);
x++; y--； }
else {d2 += a*a*(-2*y+3); y--; }
putpixel(x,y,color); }
北大计算机系多媒体与人机交互 26
用正多边形近似代替圆,显示多边形的边可用
扫描转换直线段的中点算法来实现。
生成圆弧的多边形逼近法
圆的正内接多边形迫近法
圆的等面积正多边形迫近法
北大计算机系多媒体与人机交互 27
生成圆弧的多边形逼近法
– 圆的正内接多边形迫近法
? 原理
? 计算多边形各顶点的递推公式
Xi+1 cos a - sin a Xi
=
Yi +1 sin a cosa Yi
因为, a是常数,sin a,cosa只在开始时计算一次
所以，一个顶点只需 4次乘法，共 4n次乘法，外
加直线段的中点算法的计算量。
圆边正内接多边形） ??? nn (lim
北大计算机系多媒体与人机交互 28
?问题：
给定最大逼近误
差（最大 距离）
DELTA,如何确
定多边形的边数
n或 a？
?
?2?n
另外，用矢量运算可以简化计算，推出求顶点的逆推公式 (p60)
d = R – Rcos(a/2) <= DELTA
cos(a/2) >= (R – DELTA)/R
a <= 2 arc cos (R – DELTA)/R
amax =2 arc cos (R – DELTA)/R
n = 360 /a
北大计算机系多媒体与人机交互 29
生成圆弧的多边形逼近法
- 圆的等面积正多边形迫近法
步骤：
?求多边形径
长，从而求
所有顶点生
标值
?由逼近误差
值，确定边
所对应的圆
心角 α
北大计算机系多媒体与人机交互 30
扇形 ODCE的面积 = 三角形 OPiPi+1的面积 (P60页 )
北大计算机系多媒体与人机交互 31
生成圆弧的正负法
? 正负法简介
– 基本原理
假定初始点 P0 ∈ G0，沿某方
向 (假定为 X轴）前进△ X时，到
达 G+或 G-(假定为 G-)中的 P1,在
沿另外一方向 (Y轴 )前进△ Y,到
达 P2。若 P2 ∈ G+，则改变前进
方向，否则继续向 G+前进。 … …
– 易画曲线
? F(x,y)具有正负划分性
? F(x,y)二阶连续
? 曲线上各点曲率半径足够大
北大计算机系多媒体与人机交互 32
生成圆弧的正负法
– 初始定向
? 确定 的符号yx ??,
北大计算机系多媒体与人机交互 33
生成圆弧的正负法
– 前进规则
? 取判别式
xPP
yPP
i
i
?
?
在异侧时，前进与当
在同侧时，前进与当
1
1
)2(
)1(
),(),()()()( 001 yxxFyxFPFPFPD iiii ??????
xPD
yPD
i
i
??
??
时，前进当
时，前进当
0)()2(
0)()1(
北大计算机系多媒体与人机交互 34
生成圆弧的正负法
? 正负法生成圆弧
– 考虑第一像限圆弧段
– 圆弧是易画曲线
取初始点 P0(x0,y0) = (0,R)
初始定向为,D = 4,△ X=1,△ y = -1
则 P1为 （ x0+1,y0) = (1,R);又因为
D(Pi) = F(Pi)F(P1) = F(Pi)F(1,R)
所以由前进规则得前进点递推公式
1）当 D(Pi) >=0时,Xi+1 = Xi,Yi+1 = yi-1;
2) 当 D(Pi) <0时,Xi+1 = Xi+1,Yi+1 = yi；
判别式 D(Pi+1)的递推公式见,P63
判别式的初值 D(P1) = F(P1)= F(1,R) = 1
北大计算机系多媒体与人机交互 35
线画图元的属性控制（ 1/5）
? 线宽控制
– 像素复制方法
? 优点：
– 实现简单
? 缺点：
– 线段两端要么为水平的，要么是竖直的
– 折线顶点处有缺口
北大计算机系多媒体与人机交互 36
线画图元的属性控制（ 2/5）
– 图元的宽度不均匀
– 产生宽度为偶数像素的图元效果不好
北大计算机系多媒体与人机交互 37
线画图元的属性控制（ 3/5）
– 移动刷子
北大计算机系多媒体与人机交互 38
线画图元的属性控制（ 4/5）
– 利用填充图元
? 优点：
– 生成的图形质量高
? 缺点
– 计算量大
– 有些图形的等距线难以获得
例 1,PaintBrush 例 2:PhotoShop
北大计算机系多媒体与人机交互 39
线画图元的属性控制（ 5/5）
? 线型控制
1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0
?例子,PowerPoint
北大计算机系多媒体与人机交互 40
4.2 二维填充图元的生成
4.2.1 扫描转换矩形
4.2.2 扫描转换多边形
逐点判断法、扫描线算法、边缘填充算法
4.2.3 扫描转换扇形
4.2.4 区域填充（ 种子填充法）
递归填充算法、扫描线算法
4.2.5 以图像填充区域
4.2.6 字符的表示与输出
一般步骤
? 确定那些像素
位于填充图元
的内部；
? 确定以什么颜
色填充这些像
素；
北大计算机系多媒体与人机交互 41
4.2.1 扫描转换矩形（ 1/2）
? 方法：
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 of FillRectangle() */
北大计算机系多媒体与人机交互 42
4.2.1扫描转换矩形（ 2/ 2）
? 问题：
– 矩形是简单的多边形，那么为什么要单独处
理矩形？
比一般多边形可简化计算。
应用非常多，窗口系统。
– 共享边界如何处理？
? 原则：左闭右开，下闭上开
属于谁？
北大计算机系多媒体与人机交互 43
4.2.2 扫描转换多边形
? 多边形的表示方法
– 顶点表示
– 点阵表示
– 扫描转换多边形：将顶点表示形式转换成点阵表示
形式
– 三种方法,逐点判断法；扫描线算法；边缘填充法 。
北大计算机系多媒体与人机交互 44
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() */
#define MAX 100
Typedef struct { int PolygonNum; // 多边形顶点个数
Point vertexces[MAX] //多边形顶点数组
} Polygon // 多边形结构
逐点判断法
北大计算机系多媒体与人机交互 45
逐点判断法
? 逐个判断绘图窗口内的像素：
? 如何判断点在多边形的内外关系？
1）射线法：
2）累计角度法
3）编码法；
北大计算机系多媒体与人机交互 46
逐点判断法
1）射线法
? 步骤：
1,从待判别点 v发出射线
2,求交点个数 k
3,K的奇偶性决定了点与多边形的内外关系
? 奇异情况处理
北大计算机系多媒体与人机交互 47
逐点判断法
2）累计角度法
? 步骤
1,从 v点向多边形 P顶点发出射线，形成 有向 角
2,计算有相交的和，得出结论
? 预处理
? 离散计算方法：编码方法
?
?
?
???? 之内位于
之外位于，
Pv
Pvn
i
i,2
0
0 ?
?
i?
北大计算机系多媒体与人机交互 48
3）编码方法,累计角度方法的离散方法
Step:
a.预处理，测试点在边上否？
b.V为中点作局部坐标系,对象限按逆
时针（或顺时针）编码；
c.顶点编码 Ipi，
d.边编码。 PiPi+1,△ PiPi+1=Ipi+1-Ipi
e.计算 ∑ △ PiPi+1 （其中△ PnPn+1 = △ PnP0)：
若 ∑ 为 0,V在 P外； 若 ∑ 为 +/-4,V 在 P内；
逐点判断法程序简单，
速度太慢，效率低。
P0
P1
P2
v
逐点判断法
北大计算机系多媒体与人机交互 49
扫描线算法
? 扫描线算法
– 目标：利用相邻像素之间的连贯性，提高算
法效率
– 处理对象：非自交多边形 （边与边之间除
了顶点外无其它交点）
北大计算机系多媒体与人机交互 50
扫描线算法
– 基本原理
一条扫描线与多边形的边有偶数个交点
– 步骤 (对于每一条扫描线 ):
(1)求交点
(2)交点排序
(3)交点配对，填充区段。
北大计算机系多媒体与人机交互 51
扫描转换多边形 (7/ 19)
– 边的连贯性
? 第一类交点：新出现的边与扫描线的交点
? 第二类交点：位于同一条边上的后继交点
北大计算机系多媒体与人机交互 52
扫描转换多边形 (8/ 19)
– 交点的取整规则
? 要求：使生成的像素全部位于多边形之内
– 用于线画图元扫描转换的四舍五入原则导致部分像素
位于多边形之外，从而不可用
? 假定非水平变与扫描线 y=e
相交，交点的横坐标为 x,
规则如下
北大计算机系多媒体与人机交互 53
扫描线算法
● 规则 1：
X为小数，即交点落于扫描线上两个相邻像素之间
(a)交点位于左边之上，向右取整
(b)交点位于右边之上，向左取整
北大计算机系多媒体与人机交互 54
● 规则 2：
边界上象素的取舍问题，避免填充扩大化。
● 解决方法：
边界象素：规定落在右上边界的象素不予填充。
具体实现时，只要对扫描线与多边形的相交区间左闭右开
扫描线算法
北大计算机系多媒体与人机交互 55
● 规则 3：
扫描线与多边形的顶点相交时，交点的取舍，保证交点正
确配对。
● 解决方法：
检查两相邻边在扫描线的哪一侧。
只要检查顶点的两条边的另外两个端点的 Y值，两个 Y值中大于交点 Y
值的个数是 0,1,2，来决定取 0,1,2个交点。
扫描线算法
北大计算机系多媒体与人机交互 56
扫描线算法
1） 活性边：与当前扫描线相交的边。按交点 x的增量顺序
存放在一个链表中；该链表称作 活性 边表（ AEL)。
算法所涉及的数据结构：
?AEL 与 ET的结点信息（ p75）：
?Ymax,所交边的最高扫描线号
?X：当前扫描线与边的交点的 x坐标
?△ X：边的斜率的倒数
?Nextage,下一条边的指针
typedef struct {int ymax;
float x,deltax;
Edge *nextEdge;
}Edge;
北大计算机系多媒体与人机交互 57
扫描线算法
2）边的分类表 （ ET）
按照边的下端点 y坐标对非水平边进行分类的指针数组,
下端点 y坐标值等于 i的边属于第 i类
typedef struct {int ymax;
float x,deltax;
Edge *nextEdge;
}Edge;
边的分类表的作用是避免盲目求交。
当处理一条扫描线时，为了求出它
与多边形边的所有交点，必须将它
与所有的边进行求交测试。而实际
上只有某几条边与该扫描线有交点。
边的分类表正是用来排除不必要的
求求交测试的。
例如,P76 图 4.17
北大计算机系多媒体与人机交互 58
扫描线算法
– 算法
1、建立 ET；
2、将扫描线纵坐标 y的初值置为 ET中非空元素的最小序号，如在上图中，
y=1；
3、置 AEL为空；
4、执行下列步骤直至 ET和 AEL都为空．
4.1、如 ET中的第 y类非空，则将其中的所有边取出并插入 AEL中；
4.2、如果有新边插入 AEL，则对 AEL中各边排序；
4.3、对 AEL中的边两两配对，（ 1和 2为一对,3和 4为一对,… ），将每
对边中 x坐标按规则取整，获得有效的填充区段，再填充．
4.4、将当前扫描线纵坐标 y值递值 1；
4.5、将 AEL中满足 y=ymax边删去（因为每条边被看作下闭上开的）；
4.6、对 AEL中剩下的每一条边的 x递增 deltax，即 x = x+deltax．
北大计算机系多媒体与人机交互 59
?边的连贯性,某条边与当前扫描线相交，也可能与
下一条扫描线相交；
?扫描线的连贯性,当前扫描线与各边的交点顺序与
下一条扫描线与各边的交点顺序可能相同或类似；
?区间连贯性,同一区间上的像素取同一颜色属性
几个概念
北大计算机系多媒体与人机交互 60
边缘填充算法
▼ 求余运算,假定 A为一个正整数，则 M的余定义为
A – M,记为 。计算机中取 A为 n位能表示的最大整数。
即,A=0xFFFFFFFF
▼ 由来,光栅图形中，如果某区域已着上值为 M的颜色
值做偶数次求余运算，该区域颜色不变；而做奇数次
求余运算，则该区域颜色变为值为 的颜色。这一
规律应用于多边形扫描转换，就为边缘填充算法。
▼ 求余运算可用异或显示模式实现。
▼算法基本思想,对于每条扫描线和每条多边形边的交
点，将该扫描线上交点右方的所有象素取余。
AX o rMMAM ???
M
M
北大计算机系多媒体与人机交互 61
算法 1（以扫描线为中心的边缘填充算法）
1、将当前扫描线上的
所有象素着上 颜色；
2、求余：
for(i = 0;i <= m; i++)
在当前扫描线上，
从横坐标为 Xi的交点
向右求余；
M
北大计算机系多媒体与人机交互 62
算法 2（以边为中心的边缘填充算法）
1、将绘图窗口的背景色置为 ；
2、对多边形的每一条非水平边做：
从该边上的每个象素开始向右求余；
M
北大计算机系多媒体与人机交互 63
边缘填充算法
? 适合用于具有帧缓存的图形系统。处理
后，按扫描线顺序读出帧缓存的内容，
送入显示设备。
? 优点：算法简单
? 缺点：对于复杂图形，每一象素可能被
访问多次，输入 /输出的量比扫描线算法
大得多。
北大计算机系多媒体与人机交互 64
4.2.3 扫描转换扇形区域 (1/5)
? 扇形区域的描述,
? 原理：同扫描转换多边形
? 问题：如何确定扫描线与直线段和圆弧段的相
交顺序
? 方法：分类
按点 和 点所处象限的不同，需要将扇形区域分成
4× 4=16种情况
p1 2p
北大计算机系多媒体与人机交互 65
4.2.3 扫描转换扇形区域 (2/5)
? 假设 点落在第一象限,扇形区域的扫描
转换 分四种情况
1,落在第一象限
p1
2p
北大计算机系多媒体与人机交互 66
4.2.3 扫描转换扇形区域 (3/5)
2,落在第二象限，此时又分为两种情况
? 当 时
? 当 时
2p
y y1 2?
21 yy ?
北大计算机系多媒体与人机交互 67
4.2.3扫描转换扇形区域 (4/5)
3,落在第三象限
4,落在第四象限
2p
2p
北大计算机系多媒体与人机交互 68
4.2.3 扫描转换扇形区域 (5/5)
? 遗留问题：当 落在其它区域时?
? 其它方法：
p1
多边形迫近方法
北大计算机系多媒体与人机交互 69
4.2.4 区域填充
? 区域,点阵表示的图形，像素集合
? 表示方法,内点表示、边界表示
? 内点表示
– 枚举处区域内部的所有像素
– 内部的所有像素着同一个颜色
– 边界像素着与内部像素不同的颜色
? 边界表示
– 枚举出边界上所有的像素
– 边界上的所有像素着同一颜色
– 内部像素着与边界像素不同的颜色
北大计算机系多媒体与人机交互 70
区域填充 (种子填充法 )
区域填充 –对 区域重新着色的过程
– 将指定的颜色从 种子点 扩展到整个区域的过程
– 区域填充算法要求区域是连通的
? 连通性
4连通,8连通
? 4连通：
? 8连通
例子,PaintBrush 例子,PhotoShop
北大计算机系多媒体与人机交互 71
区域填充 (种子填充法 )
? 4连通与 8连通区域的区别
– 连通性,4连通可看作 8连通区域，但对边界有要求
– 对边界的要求
北大计算机系多媒体与人机交互 72
区域填充 (种子填充法 )
1）递归填充算法
– 内点表示的 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);
}
}/*end of FloodFill4() */
取 (x,y)为种子点
北大计算机系多媒体与人机交互 73
区域填充 (种子填充法 )
北大计算机系多媒体与人机交互 74
区域填充 (种子填充法 )
– 边界表示的 4连通区域
void BoundaryFill4(int x,int y,int oldColor,int newColor)
{ int color;
color = GetPixel(x,y);
if((color != boundaryColor) && (color != newColor))
{ PutPixel(x,y,newColor);
BoundaryFill4(x,y+1,oldColor,newColor);
BoundaryFill4(x,y-1,oldColor,newColor);
BoundaryFill4(x-1,y,oldColor,newColor);
BoundaryFill4(x+1,y,oldColor,newColor);
}
}/*end of BoundaryFill4() */
北大计算机系多媒体与人机交互 75
? 问题：
内点表示与边界表示的 8连通区域？
? 缺点,
(1) 有些象素会入栈多次，降低算法效率；栈结构占空间。
(2) 递归执行，算法简单，但效率不高，区域内每一象素
都引起一次递归，进 /出栈，费时费内存。
? 改进算法，减少递归次数，提高效率。
方法之一使用扫描线填充算法；
区域填充 (种子填充法 )
北大计算机系多媒体与人机交互 76
区域填充（扫描线算法 )
? 扫描线算法
– 目标：减少递归层次
– 适用于内点表示的 4连通区域
– 基本过程：
当给定种子点时，首先填充种子点所在的扫描线
上的位于给定区域的一个区段，然后确定与这一区
段相通的上下两条扫描线上位于给定区域内的区段，
并依次保存下来。反复这个过程，直到填充结束。
北大计算机系多媒体与人机交互 77
1、填充并确定种子区段 ；
2、初始化,将种子区段压入堆栈；
3、出栈：如果堆栈为空，则算法结束；否则取栈顶元素
（ y,xLeft,xRight），以纵坐标为 y的扫描线为当前
扫描线,[xLeft,xRight]为搜索区间 ；
4、填充并确定新的区段 。
?算法步骤
区域填充（扫描线算法）
北大计算机系多媒体与人机交互 78
区域填充（扫描线算法 )
像素中的序号标指它所在区段位于堆栈中的位置
北大计算机系多媒体与人机交互 79
4.2.5 以图象填充区域
? 四种填充方法：
– (1)均匀着色方法,将图元内部像素置成同一颜色
– (2)位图不透明,若像素对应的位图单元为 1，则以 前景
色 显示该像素；若为 0，则以背景色显示该像素；
– (3)位图透明,若像素对应的位图单元为 1，则以 前景色
显示该像素； 若为 0，则不做任何处理。
– (4)像素图填充,以像素对应的像素图单元的颜色值显
示该像素。
北大计算机系多媒体与人机交互 80
以图像填充区域
? 基本问题
– 关键是建立区域与图像间的对应关系
– 方法 1：建立整个绘图空间与图像空间的 1-1映射
图像（纹理）
北大计算机系多媒体与人机交互 81
以图像填充区域
适用,动画中漫游
图像 – 例，透
过车窗看外景
北大计算机系多媒体与人机交互 82
以图像填充区域
? 方法 2：建立区域局部坐标空间与图像空间的 1-1映射
适用：图像作为区域表面属性的情况，例如，桌面与
其上的木纹。
北大计算机系多媒体与人机交互 83
4.2.6 字符的表示与输出
点阵字符
矢量字符
自学！
北大计算机系多媒体与人机交互 84
思考题
如何修改扫描线算法，使它能处理边自交
的多边形？
北大计算机系多媒体与人机交互 85
4.3.1 混淆现象
4.3.2 反混淆方法
非加权区域采样
加权区域采样
4.3 反混淆方法
北大计算机系多媒体与人机交互 86
4.3.1 混淆现象
混淆, 用离散量 (像素 )表示连续的量 (图形 )而引起的失
真，叫混淆或叫 走样 (aliasing)。
光栅图形的混淆现象
– 阶梯状边界；
– 图形细节失真；
– 狭小图形遗失：动画序列中时隐时现，产生闪烁。
北大计算机系多媒体与人机交互 87
混淆现象（ 1/3）
? 不光滑 (阶梯状）的图形边界
例子,PaintBrush
北大计算机系多媒体与人机交互 88
混淆现象（ 2/3）
? 图形细节失真
北大计算机系多媒体与人机交互 89
混淆现象（ 3/3）
? 狭小图形的遗失与动态图形的闪烁
北大计算机系多媒体与人机交互 90
反混淆方法
? 什么是反混淆
– 在图形显示过程中，用于减少或消除混淆现象
的方法
1）提高分辨率方法
2）非加权区域采样
3）加权区域采样
北大计算机系多媒体与人机交互 91
反混淆方法
? 提高分辨率的反混淆方法
方法简单，但代价非常大。
显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，
帧缓存容量则增加到原来的 4倍，而扫描转换同样大小的图元却要花 4倍
时间。
北大计算机系多媒体与人机交互 92
非加权区域采样方法
? 方法由来
– 两点假设
1,象素是数学上抽象的点, 它的面积为 0,它的亮度由
覆盖该点的图形的亮度所决定；
2、直线段是数学上抽象直线段，它的宽度为 0。
– 现实
? 像素的面积不为 0；
? 直线段的宽度至少为 1个像素；
– 假设与现实的矛盾是导致混淆出现的原因之一
北大计算机系多媒体与人机交互 93
非加权区域采样方法
– 解决方法：改变直线段模型，由此产生算法
– 方法步骤,
1、将直线段看作具有一定宽度的狭长矩形；
2、当直线段与某象素有交时，求出两者相交区域的面积；
3、根据相交区域的面积，确定该象素的亮度值
北大计算机系多媒体与人机交互 94
方法性质：
非加权区域采样方法
1）直线段对一个像素亮度的贡献与两者相交区域的面积成
正比，从而和像素中心点距直线段的距离成反比 (因为像
素中心点距直线段距离越元，相交区域的面积越小）；
2） 当直线段和某个像素不相交时，它对该像素的亮度无影响；
3） 相同面积的相交区域对像素的亮度贡献相同，而与这个相交
区域落在像素内麽位置无关。
关键：如何计算这个面积？
北大计算机系多媒体与人机交互 95
非加权区域采样方法
-- 计算相交区域的面积
D
D.m
面积 =(m*D*D)/2
D - - - - - - m
面积 =D – m/2
像素实际显示的灰度值 == 所得面积 * 该像素的最大灰度值
北大计算机系多媒体与人机交互 96
反混淆方法
– 求相交区域的近似面积的离散计算方法
1、将屏幕象素分割成 n个更小的子象素；
2、计算中心点落在直线段内的子象素的个数，记为 k，
3,k/n为线段与象素相交区域面积的近似值
目的：简化计算
n = 16,k = 3
近似面积 = 3/16
北大计算机系多媒体与人机交互 97
加权区域采样方法
改进 非加权区域采样方法的 第 3条性质,
相交区域对象素亮度的贡献
依赖于该区域与象素中心的距离
北大计算机系多媒体与人机交互 98
加权区域采样方法
– 权函数 W(x,y)
? 以象素 A的中心为原点建立二维坐标系
? w(x,y)反应了微面积元 dA对整个象素亮度的贡献
大小,与 d成反比。
? 权性（为讨论方便而设）
? 位于 (x,y)处的微面积元 dA对像素的亮度的贡献
为 w(x,y) dA
dyxw
1),( ?
1),( ??A dAyxw
北大计算机系多媒体与人机交互 99
加权区域采样方法
– 相交区域 对该象素的亮度贡献?A
w x y dAA (,)??
的面积AdAyxwA ??? ? ),(特例,时，
加权区域采样方法退化为
非加权区域采样方法
北大计算机系多媒体与人机交互 100
加权区域采样方法
– 实现步骤
1,求直线段与象素的相交区域 ；
2,计算的值 ；
3．上面所得到的值介于 0,1之间，用它乘象素的
最大灰度值，即设该象素的显示灰度。
– 问题：计算量大
?A
w x y dAA (,)??
北大计算机系多媒体与人机交互 101
加权区域采样方法
– 离散计算方法
1,将屏幕象素均匀分割成 m个子象素, 则每个子象素
的面积为, 计算每个子象素对原象素亮度的贡献,
记为,将 保存在一张加权表中 ;
2,求出所有中心落于直线段内的子象素, 记为,
3．计算所有这些子象素对原象素亮度贡献之和 该值
乘以象素的最大灰度值即为象素的显示灰度值,
– 加权表的取法
? ?Ai im?1
dA mA
i?
? 1
wi ? ?wi 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
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
北大计算机系多媒体与人机交互 102
上机作业
1,修改扫描线算法，使它能处理边自交的
多边形？
2,实现一个反混淆的算法。
