2013-3-1 华中理工大学计算机学院 陆枫
99-7
1
第 5章 基本图形生成算法
? 提出问题
如何在指定的输出设备上根据坐标描述构造基
本二维几何图形 （ 点, 直线, 圆, 椭圆, 多边
形域, 字符串及其相关属性等 ） 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
2
图形的生成,是在指定的输出设备上, 根据坐标描述
构造二维几何图形 。
图形的扫描转换, 在光栅显示器等数字设备上确定一
个最佳逼近于图形的象素集的过程 。
图5 - 1 用一系列的象素点来逼近直线
2013-3-1 华中理工大学计算机学院 陆枫
99-7
3
5.1 直线的扫描转换
直线的绘制要求,
? 1.直线要直
? 2.直线的端点要准确, 即无定向性和断裂情况
? 3.直线的亮度, 色泽要均匀
? 4.画线的速度要快
? 5.要求直线具有不同的色泽, 亮度, 线型等
2013-3-1 华中理工大学计算机学院 陆枫
99-7
4
5.1.1 数值微分法 (DDA法 )
解决的问题,
给定直线两端点 P0(x0,y0)和 P1(x1,y1),画出该直线 。
直线的微分方程,
1)-(5
01
01 k
xx
yy
x
y
dx
dy ?
?
??
?
??
2013-3-1 华中理工大学计算机学院 陆枫
99-7
5
DDA算法原理,
2)-(5 1
1
yyy
xxx
ii
ii
????
????
?
?
?
?
ε △xx i
y
x
y i
x i +1
y i +1
ε △y
图5 - 2 D D A 算法原理
ε=1/max(|△ x|,|△ y|)
2013-3-1 华中理工大学计算机学院 陆枫
99-7
6
max(|△ x|,|△ y|)=|△ x|,即 |k|≤1的情况,
max(|△ x|,|△ y|)=|△ y|,此时 |k|≥1,
3)-(5
1
1
1
1
1
kyy
x
yyyy
xx
x
xxxx
iiii
iiii
????
?
??????
????
?
??????
?
?
?
?
4)-(5 1
1
11
1
1
????
?
??????
????
?
??????
?
?
iiii
iiii
yy
y
yyyy
k
xx
y
xxxx
?
?
2013-3-1 华中理工大学计算机学院 陆枫
99-7
7
程序
注意,
round(x)=(int)(x+0.5)
图5 - 3 D D A 算法生成直线段
(x i,y i )
(x i +1,r o u n d ( y i +k ))
( r o u n d ( x i + 1 / k ),y i +1 )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
8
特点,
? 增量算法
? 直观, 易实现
? 不利于用硬件实现
2013-3-1 华中理工大学计算机学院 陆枫
99-7
9
5.1.2 中点 Bresenham算法
直线的方程
该直线方程将平面分为三个区域,
? 对于直线上的点, F(x,y)=0；
? 对于直线上方的点, F(x,y)>0；
? 对于直线下方的点, F(x,y)<0。
5)-(5,0),(
01
01
xx
yy
x
ykbkxyyxF
?
??
?
?????? 其中
2013-3-1 华中理工大学计算机学院 陆枫
99-7
10
x
y
F ( x,y ) > 0
F ( x,y ) = 0
F ( x,y ) < 0
图5 - 4 直线将平面分为三个区域
x
y
F ( x,y ) > 0
F ( x,y ) = 0
F ( x,y ) < 0
2013-3-1 华中理工大学计算机学院 陆枫
99-7
11
基本原理,
假定 0≤k≤1,x是最大位移方向
P u (x i + 1,y i +1)
M(x i + 1,y i + 1 / 2 )
P(x i,y i )
P d (x i + 1,y i )
图5 - 5 B r e n s e m h a m 算法生成直线的原理
Q
2013-3-1 华中理工大学计算机学院 陆枫
99-7
12
判别式,
6)-(5 )1(5.0)5.0,1(),( bxkyyxFyxFd iiiiMM ?????????
则有,
?
?
?
?
??
?
)0(
)0( 1
dy
dy
y
P u (x i + 1,y i +1)
M(x i + 1,y i + 1 / 2 )
P(x i,y i )
P d (x i + 1,y i )
图5 - 5 B r e n s e m h a m 算法生成直线的原理
Q
2013-3-1 华中理工大学计算机学院 陆枫
99-7
13
d < 0
(x i,y i )
(x i+1,y i + 0, 5 )
(x i+2,y i + 1, 5 )
误差项的递推
d<0,
kd
kbxky
bxky
yxFd
ii
ii
ii
???
??????
?????
???
1
)1(5.1
)2(5.1
)5.1,2(
2013-3-1 华中理工大学计算机学院 陆枫
99-7
14
误差项的递推
d≥0,
kd
kbxky
bxky
yxFd
ii
ii
ii
??
??????
?????
???
)1(5.0
)2(5.0
)5.0,2(
d > = 0
(x i,y i )
(x i+1,y i + 0, 5 )
(x i+2,y i + 0, 5 )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
15
初始值 d的计算
k
kbkxy
bxky
yxFd
??
?????
?????
???
5.0
5.0
)1(5.0
)5.0,1(
00
00
000
2013-3-1 华中理工大学计算机学院 陆枫
99-7
16
0≤k≤1时 Bresenham算法的 算法步骤 为,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=0.5-k,x=x0,y=y0；
3.绘制点 (x,y)。 判断 d的符号；
若 d<0,则 (x,y)更新为 (x+1,y+1),d更新为 d+1-k；
否则 (x,y)更新为 (x+1,y),d更新为 d-k。
4.当直线没有画完时, 重复步骤 3。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
17
改进,用 2d△ x代替 d
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=△ x-2△ y,x=x0,y=y0。
3.绘制点 (x,y)。 判断 d的符号 。
若 d<0,则 (x,y)更新为 (x+1,y+1),d更新为
d+2△ x-2△ y；
否则 (x,y)更新为 (x+1,y),d更新为 d-2△ y。
4.当直线没有画完时, 重复步骤 3。 否则结束 。
程序
2013-3-1 华中理工大学计算机学院 陆枫
99-7
18
5.1.3 改进的 Bresenham算法
假定直线段的 0≤k≤1
基本原理,
图5 - 8 改进的B r e n s e m h a m 算法绘制直线的原理
d
d
d
d
k
k
k
k
k
2013-3-1 华中理工大学计算机学院 陆枫
99-7
19
?
?
?
?
?
?
?
?
?
??
?
??
?
?
0, 5 )(d
0, 5 )(d 1
1
1
1
i
i
i
ii
y
y
y
xx
误差项的计算
? d初 =0,
? 每走一步,d=d+k
? 一旦 y方向上走了一步, d=d-1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
20
算法步骤,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=0,x=x0,y=y0。
3.绘制点 (x,y)。
4.d更新为 d+k,判断 d的符号 。 若 d>0.5,则 (x,y)更
新为 (x+1,y+1),同时将 d更新为 d-1； 否则 (x,y)更
新为 (x+1,y)。
5.当直线没有画完时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
21
改进 1：令 e=d-0.5
?
?
?
?
?
?
?
?
?
??
?
??
?
?
0)(e
0)(e 1
1
1
1
i
i
i
ii
y
y
y
xx
? e初 =-0.5,
? 每走一步有 e=e+k。
? if (e>0) then e=e-1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
22
算法步骤 为,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,e=-0.5,x=x0,y=y0。
3.绘制点 (x,y)。
4.e更新为 e+k,判断 e的符号 。 若 e>0,则 (x,y)更新
为 (x+1,y+1),同时将 e更新为 e-1； 否则 (x,y)更新
为 (x+1,y)。
5.当直线没有画完时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中科技大学计算机学院 陆枫 23
改进 2：用 2e△ x来替换 e
? e初 =-△ x,
? 每走一步有 e=e+2△ y。
? if (e>0) then e=e-2△ x
2013-3-1 华中理工大学计算机学院 陆枫
99-7
24
算法步骤,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,e=-△ x,x=x0,y=y0。
3.绘制点 (x,y)。
4.e更新为 e+2△ y,判断 e的符号 。 若 e>0,则 (x,y)更
新为 (x+1,y+1),同时将 e更新为 e-2△ x； 否则 (x,y)
更新为 (x+1,y)。
5.当直线没有画完时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
25
程序
几种画线算法的比较
2013-3-1 华中理工大学计算机学院 陆枫
99-7
26
5.2 圆的扫描转换
解决的问题,
绘出圆心在原点, 半径为整数 R的圆 x2+y2==R2
5.2.1 八分法画圆
八分法画圆
2013-3-1 华中理工大学计算机学院 陆枫
99-7
27
( x,y )
y
y = - x y = x
(y,x) (-y,x)
(-x,y)
(-x,-y)
(-y,-x) (y,-x)
(x,-y)
2013-3-1 华中理工大学计算机学院 陆枫
99-7
28
解决问题,
y
y=x
图5 - 1 0 1 / 8 圆弧
x
R
2013-3-1 华中理工大学计算机学院 陆枫
99-7
29
5.2.2 简单方程产生圆弧
算法原理,利用其函数方程，直接离散计算
圆的函数方程为,
222 Ryx ??
? ?
7)-(5 )(
2R0,x1
2
1
2
1
1
??
?
??
???
ii
ii
xRr o u n dy
xx
2013-3-1 华中理工大学计算机学院 陆枫
99-7
30
圆的极坐标方程为,
?
?
s in
c o s
Ry
Rx
?
?
)s in(
8)-(5 )c o s(
)(
11
11
1
??
??
?
?
?
????
ii
ii
ii
Rr o u n dy
Rr o u n dx
?
?
???? 为一固定角度步长
2013-3-1 华中理工大学计算机学院 陆枫
99-7
31
5.2.3 中点 Bresenham画圆
构造函数 F(x,y)=x2-y2-R2。
? 对于圆上的点, 有 F(x,y)=0；
? 对于圆外的点, F(x,y)>0；
? 而对于圆内的点, F(x,y)<0。
算法原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
32
x
y
图5 - 1 1 中点B r e s e n h a m 画圆的原理
P
P u
P d
M
2013-3-1 华中理工大学计算机学院 陆枫
99-7
33
当 d≤0时, 下一点取 Pu(xi +1,yi)；
当 d>0时, 下一点取 Pd(xi +1,yi-1)。
M的坐标为,M(xi +1,yi-0.5)
?当 F(xM,yM)<0时, 取 Pu(xi +1,yi)
?当 F(xM,yM)>0时, 取 Pd(xi +1,yi-1)
?当 F(xM,yM)=0时, 约定取 Pu。
构造判别式,
222 )5.0()1()5.0,1(),( RyxyxFyxFd iiiiMM ?????????
2013-3-1 华中理工大学计算机学院 陆枫
99-7
34
误差项的递推
d≤0,
(a) d<=0的 情况
P
x i
y i - 2
x i + 1
y i
y i - 1
x i + 2
32
32)5.0()1(
)5.0()2(
)5.0,2(
222
222
???
???????
?????
???
i
iii
ii
ii
xd
xRyx
Ryx
yxFd
2013-3-1 华中理工大学计算机学院 陆枫
99-7
35
d>0,
5)(2
)22()32()5.0()1(
)5.1()2(
)5.1,2(
222
222
????
??????????
?????
???
ii
iiii
ii
ii
yxd
yxRyx
Ryx
yxFd
(b) d>0的 情况
P
x i x i + 2x i + 1
y i - 1
y i
y i - 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
36
判别式的初始值
R
RR
RFd
??
????
??
25.1
)5.0(1
)5.0,1(
22
0
2013-3-1 华中理工大学计算机学院 陆枫
99-7
37
算法步骤,
1.输入圆的半径 R。
2.计算初始值 d=1.25-R,x=0,y=R。
3.绘制点 (x,y)及其在八分圆中的另外七个对称点 。
4.判断 d的符号 。 若 d≤0,则先将 d更新为 d+2x+3,再
将 (x,y)更新为 (x+1,y)； 否则先将 d更新为 d+2(x-y)+5，
再将 (x,y)更新为 (x+1,y-1)。
5.当 x<y时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
38
改进,用 d-0.25代替 d
算法步骤,
1.输入圆的半径 R。
2.计算初始值 d=1-R,x=0,y=R。
3.绘制点 (x,y)及其在八分圆中的另外七个对称点 。
4.判断 d的符号 。 若 d≤0,则先将 d更新为 d+2x+3，
再将 (x,y)更新为 (x+1,y)； 否则先将 d更新为 d+2(x-
y)+5,再将 (x,y)更新为 (x+1,y-1)。
5.当 x<y时, 重复步骤 3和 4。 否则结束 。 程序
2013-3-1 华中理工大学计算机学院 陆枫
99-7
39
5.3 椭圆的扫描转换
5.3.1 椭圆的特征 b
a x
y
图5 - 1 4 长半轴为a,短半轴为b 的标准椭圆
( x,y )
( x,- y )( - x,- y )
( - x,y )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
40
0),( 222222 ???? bayaxbyxF
? 对于椭圆上的点, 有 F(x,y)=0；
? 对于椭圆外的点, F(x,y)>0；
? 对于椭圆内的点, F(x,y)<0。
解决问题,
y
x
2013-3-1 华中理工大学计算机学院 陆枫
99-7
41
以弧上斜率为－ 1的点作为分界将第一象限椭圆弧分
为上下两部分。
上半部分
下半部分
二分量相等的法向量
图5 - 1 5 第一象限的椭圆弧
y
x
2013-3-1 华中理工大学计算机学院 陆枫
99-7
42
引理 5-1：若在当前中点，法向量的 y分量比 x分量大，
即
)5.0()1( 22 ??? ii yaxb
而在下一个中点, 不等号改变方向, 则说明椭圆弧
从上部分转入下部分 。
yjaxibj
y
Fi
x
FyxN 22 22),( ??
?
??
?
??
法向量
2013-3-1 华中理工大学计算机学院 陆枫
99-7
43
5.3.2 椭圆的中点 Bresenham算法
算法原理
P u
图5 - 1 6 B r e s e n h a m 椭圆绘制算法的原理
y
x
P d
P
P l P r
P
2013-3-1 华中理工大学计算机学院 陆枫
99-7
44
先推导上半部分的椭圆绘制公式
p ( x i,y i )
p u (x i+1,y i )
p d (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 7 上半部分椭圆弧的绘制原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
45
判别式
2222221 )5.0()1()5.0,1( bayaxbyxFd iiii ????????
? 若 d1≤0,取 Pu(xi+1,yi)
? 若 d1>0,取 Pd(xi+1,yi-1)
p ( x i,y i )
p u (x i+1,y i )
p d (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 7 上半部分椭圆弧的绘制原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
46
误差项的递推
d1≤0,
(a) d<=0的 情况
P
x i
y i - 2
x i + 1
y i
y i - 1
x i + 2
)x(bd
)x(bba).(ya)(xb
ba).(ya)(xb).,yF ( xd
i
iii
iiii
32
32501
502502
2
1
2222222
222222
1
???
????????
????????
2013-3-1 华中理工大学计算机学院 陆枫
99-7
47
d1>0,
)22()32(
)22()32()5.0()1(
)5.1()2()5.1,2(
22
1
22222222
222222
1
??????
??????????
????????
ii
iiii
iiii
yaxbd
yaxbbayaxb
bayaxbyxFd
(b) d>0的 情况
P
x i x i + 2x i + 1
y i - 1
y i
y i - 2
判别式的初始值
)25.0(
)5.0()5.0,1(
22
22222
10
????
??????
bab
bababbFd
2013-3-1 华中理工大学计算机学院 陆枫
99-7
49
p ( x i,y i )
p l (x i,y i-1 ) p r (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 9 下半部分椭圆弧的绘制原理
再来推导椭圆弧下半部分的绘制公式
原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
50
判别式
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii ????????
?若 d2>0,取 Pl(xi,yi-1)
?若 d2≤0,取 Pr(xi+1,yi-1)
p ( x i,y i )
p l (x i,y i-1 ) p r (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 9 下半部分椭圆弧的绘制原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
51
误差项的递推
d2>0,
)y(ad
)y(aba)(ya)(xb
ba)(ya)(xb),yF ( xd
i
iii
iiii
32
3215.0
25.025.0
2
2
2222222
222222
2
????
????????
????????
(a) d>0的 情况
P
x i
y i - 2
x i + 1
y i
y i - 1
x i + 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
52
d2≤0,
)32()22(
)32()22()1()5.0(
)2()5.1()2,5.1(
22
2
22222222
222222
2
??????
??????????
????????
ii
iiii
iiii
yaxbd
yaxbbayaxb
bayaxbyxFd
(b) d<=0的 情况
P
x i x i + 2x i + 1
y i - 1
y i
y i - 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
53
注意,
? 上半部分的终止判别
? 下半部分误差项的初值
算法步骤,
1.输入椭圆的长半轴 a和短半轴 b。
2.计算初始值 d=b2+a2(-b+0.25),x=0,y=b。
3.绘制点 (x,y)及其在四分象限上的另外三个对称点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
54
4.判断 d的符号 。 若 d≤0,则先将 d更新为 d+b2(2x+3)，
再将 ( x,y) 更新为 ( x+1,y)； 否则先将 d 更 新 为
d+b2(2x+3)+a2(-2y+2),再将 (x,y)更新为 (x+1,y-1)。
5.当 b2(x+1)<a2(y-0.5)时, 重复步骤 3和 4。 否则转到步
骤 6。
6.用上半部分计算的最后点 (x,y)来计算下半部分中 d的
初值,
222222 )1()5.0( bayaxbd ?????
2013-3-1 华中理工大学计算机学院 陆枫
99-7
55
7.绘制点 (x,y)及其在四分象限上的另外三个对称点 。
8.判断 d的符号 。 若 d≤0,则先将 d更新为 b2(2xi+2)+a2(-
2yi+3),再将 (x,y)更新为 (x+1,y-1)； 否则先将 d更新
为 d+a2(-2yi+3),再将 (x,y)更新为 (x,y-1)。
9.当 y>0时, 重复步骤 7和 8。 否则结束 。
程序
2013-3-1 华中理工大学计算机学院 陆枫
99-7
56
5.4 多边形的扫描转换与区域填充
多边形的扫描转换 主要是通过确定穿越区域的扫
描线的覆盖区间来填充,
区域填充 是从给定的位置开始涂描直到指定的边
界条件为止 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
57
5.4.1 多边形的扫描转换
顶点表示 用多边形的顶点序列来刻划多边形
点阵表示 是用位于多边形内的象素的集合来刻划多边形
扫描转换多边形或多边形的填充,从多边形顶点表示到
点阵表示的转换 。
1,什么是多边形的扫描转换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
58
2,x-扫描线算法
基本思想
图5 - 2 3 x - 扫描线算法填充多边形
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
2013-3-1 华中理工大学计算机学院 陆枫
99-7
59
算法步骤,
(1)确定多边形所占有的最大扫描线数, 得到多边形顶
点的最小和最大 y值 （ ymin和 ymax） 。
(2)从 y=ymin到 y=ymax,每次用一条扫描线进行填充 。
(3)对一条扫描线填充的过程可分为四个步骤,
a.求交
b.排序
c.交点配对
d.区间填色
2013-3-1 华中理工大学计算机学院 陆枫
99-7
60
存在问题,当扫描线与多边形顶点相交时, 交点
的取舍问题 。
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
图5 - 2 4 与多边形顶点相交的交点的处理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
61
解决,
当扫描线与多边形的顶点相交时,
? 若共享顶点的两条边分别落在扫描线的两边, 交
点只算一个；
? 若共享顶点的两条边在扫描线的同一边, 这时交
点作为零个或两个 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
62
图5 - 2 5 与扫描线相交的多边形顶点的交点数
0
1
1 1 1
0 2
2
2
填充过程实例
2013-3-1 华中理工大学计算机学院 陆枫
99-7
63
3,改进的有效边表算法 （ Y连贯性算法 ）
x i,y i
x i + 1,y i + 1
1
1/k
图5 - 2 6 与多边形边界相交的两条
连续扫描线交点的相关性
改进原理,
? 处理一条扫描线时, 仅对
有效边求交
? 利用扫描线的连贯性
? 利用多边形边的连贯性
2013-3-1 华中理工大学计算机学院 陆枫
99-7
64
有效边 （ Active Edge）, 指与当前扫描线相交的多
边形的边, 也称为活性边 。
有效边表 （ Active Edge Table,AET）, 把有效边按
与扫描线交点 x坐标递增的顺序存放在一个链表中,
此链表称为有效边表 。
有效边表的每个结点,
x ymax 1/k next
2013-3-1 华中理工大学计算机学院 陆枫
99-7
65
边表 （ Edge Table）
边表的构造,
(1)首先构造一个纵向链表, 链表的长度为多边形所占有
的最大扫描线数, 链表的每个结点, 称为一个桶, 则
对应多边形覆盖的每一条扫描线 。
(2)将每条边的信息链入与该边最小 y坐标 （ ymin ） 相对
应的桶处 。 也就是说, 若某边的较低端点为 ymin,则
该边就放在相应的扫描线桶中 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
66
(3)每条边的数据形成一个结点, 内容包括：该扫描
线与该边的初始交点 x（ 即较低端点的 x值 ）, 1/k，
以及该边的最大 y值 ymax。
x|ymin ymax 1/k NEXT
(4)同一桶中若干条边按 X|ymin由小到大排序, 若
X|ymax 相等, 则按照 1/m由小到大排序 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
67
解决顶点交点计为 1时的情形,
图5 - 2 8 将多边形的某些边缩短以分离那些应
计为1 个交点的顶点
（a ) 原图 （b ) 缩短y m a x 的边 （c ) 缩短y m i n 的边
扫描线y
扫描线y + 1
扫描线y - 1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
68
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
2013-3-1 华中理工大学计算机学院 陆枫
99-7
69
1
2
3
4
5
6
7
8
9
10
11
12
3 -1/3 3 5 3/4 8 5 -1/2 8 9 1/2
1 12 2/5
7 12 -1 7 9 5
桶
p 3 p 2 p 3 p 4 p 5 p 4 p 5 p6
p 2 p 1
p 0 p 1 p 0 p6
x|y min ymax 1/k next
( c ) 边表
6
2013-3-1 华中理工大学计算机学院 陆枫
99-7
70
算法步骤,
(1)初始化：构造边表, 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),否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
71
5.4.2 边缘填充算法
边缘填充算法
算法简单, 但对于复杂图型, 每一象素可能被访问多次
栅栏填充算法
栅栏 指的是一条过多边形顶点且与扫描线垂直的直线 。
它把多边形分为两半 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
72
边标志算法
分为两个步骤,
(1)打标记
(2)填充
当用软件实现本算法时, 速度与改进的有效边表算法
相当, 但本算法用硬件实现后速度会有很大提高 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
73
5.4.3 区域填充
区域 是指已经表示成点阵形式的填充图形, 它是像
素集合 。
4-邻接点 和 8-邻接点
4
4p4
4
( b ) p 的8 - 邻接点
8 8 8
8
8
p8
8 8
( a ) p 的4 - 邻接点
图5 - 3 3 邻接点的定义
2013-3-1 华中理工大学计算机学院 陆枫
99-7
74
4-连通区域 和 8-连通区域
把位于给定区域的边界上的象素一一列举出来的方法
称为 边界表示法 。
边界填充算法 （ Boundary-fill Algorithm） 。
枚举出给定区域内所有象素的表示方法称为 内点表示 。
泛填充算法 （ Flood-fill Algorithm）
图5 - 3 2 区域的边界表示和内点表示
( a ) 以边界表示的4 - 连通区域 ( b ) 以内点表示的4 - 连通区域
( c ) 以边界表示的8 - 连通区域 ( d ) 以内点表示的8 - 连通区域
2013-3-1 华中理工大学计算机学院 陆枫
99-7
76
1,边界填充算法
算法的输入：种子点坐标 (x,y),填充色和边界颜色 。
栈结构实现 4-连通边界填充算法 的 算法步骤 为,
种子象素入栈；当栈非空时重复执行如下三步操作,
(1)栈顶象素出栈；
(2)将出栈象素置成填充色；
(3)检查出栈象素的 4-邻接点, 若其中某个象素点不是边界色
且未置成多边形色, 则把该象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
77
栈结构实现 8-连通边界填充算法 的 算法步骤 为,
种子象素入栈；当栈非空时重复执行如下三步操作,
(1)栈顶象素出栈；
(2)将出栈象素置成填充色；
(3)检查出栈象素的 8-邻接点, 若其中某个象素点不是
边界色且未置成多边形色, 则把该象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
78
特点,
? 可以用于填充带有内孔的平面区域 。
? 把太多的象素压入堆栈
改进
通过沿扫描线填充水平象素段, 来代替处理 4-邻
接点和 8-邻接点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
79
沿扫描线填充水平象素段的 4-连通边界填充算法步骤,
种子象素入栈；当栈非空时作如下三步操作,
(1)栈顶象素出栈；
(2)填充出栈象素所在扫描行的连续象素段, 直到遇到
边界象素为止, 即每出栈一个象素, 就对包含该象
素的整个扫描线区间进行填充；
(3)在区间中检查与当前扫描线相邻的上下两条扫描线
的有关象素是否全为边界象素或已填充的象素, 若
存在非边界, 未填充边界的象素, 则把每一区间的
最右象素取作种子象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
80
2,泛填充算法
算法的输入：种子点坐标 (x,y),填充色和内部点的
颜色 。
算法原理,
算法从指定的种子 (x,y)开始, 用所希望的填充颜色
赋给所有当前为给定内部颜色的象素点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
81
8-连通泛填充 算法步骤 如下,
种子象素入栈；当栈非空时重复执行如下三步操作,
(1)栈顶象素出栈；
(2)将出栈象素置成填充色；
(3)检查出栈象素的 8-邻接点, 若其中某个象素点不
是给定内部点的颜色且未置成新的填充色, 则把
该象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
82
注意,
当以边界表示时, 4-连通边界填充算法只能填充 4-
连通区域, 8-连通边界填充算法也只能填充 8-连
通区域 。
当以内点表示时, 8-连通泛填充算法可以填充 8-连
通区域也可以填充 4-连通区域, 当然 4-连通泛填
充算法还是只能填充 4-连通区域 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
83
5.4.4 其他相关的概念
1,内 -外测试
不自交的多边形, 自相交的多边形
奇 -偶规则 （ Odd-even Rule）
从任意位置 p作一条射线, 若与该射线相交的多
边形边的数目为奇数, 则 p是多边形内部点, 否
则是外部点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
84
非零环绕数规则 （ Nonzero Winding Number Rule）
? 首先使多边形的边变为矢量 。
? 将环绕数初始化为零 。
? 再从任意位置 p作一条射线 。 当从 p点沿射线方向移
动时, 对在每个方向上穿过射线的边计数, 每当多
边形的边从右到左穿过射线时, 环绕数加 1,从左到
右时, 环绕数减 1。
? 处理完多边形的所有相关边之后, 若环绕数为非零,
则 p为内部点, 否则, p是外部点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
85
2,曲线边界区域的填充
相交计算
2013-3-1 华中理工大学计算机学院 陆枫
99-7
86
5.5 字符处理
ASCI码：, 美国信息交换用标准代码集, (American
Standard Code for Information Interchange),简称
ASCI码 。
国际码：, 中华人民共和国国家标准信息交换编码,
简称为国际码, 代号 GB2312－ 80。
字库,字库中储存了每个字符的图形信息。
矢量字库 和 点阵字库
5.5.1 点阵字符
在点阵表示中, 每个字符由一个 点阵位图 来表示
显示时,
形成 字符的象素图案
图5 - 3 6 字符A 的点阵表示
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
11
1 1 1
1
1
1
1
1
1
1
1
1
1
1
11 1
1111
1
00000
00000
00000
00000
0
0
0000
0000
0000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
000
0
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
0
(a)字符 A的点 阵位图 (a)字符 A的象 素图案
2013-3-1 华中理工大学计算机学院 陆枫
99-7
88
5.5.2 矢量字符
矢量字符采用直线和曲线段来描述字符形状, 矢量字
符库中记录的是 笔划信息 。
显示时,解释字符的每个笔划信息
2013-3-1 华中理工大学计算机学院 陆枫
99-7
89
5.6 属性处理
当前属性值表
5.6.1 线型和线宽
1,线型处理
实心段和中间空白段的长度 （ 象素数目 ） 可用 象素模
板 (pixel mask)指定 。
存在问题,如何保持任何方向的划线长度近似地相等
2013-3-1 华中理工大学计算机学院 陆枫
99-7
90
解决
可根据线的斜率来调整实心段和中间空白段的象素数目 。
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
2013-3-1 华中理工大学计算机学院 陆枫
99-7
91
2,线刷子和方刷子处理线宽
线刷子：垂直刷子, 水平刷子
图5 - 3 9 线刷子
(a) (b)
2013-3-1 华中理工大学计算机学院 陆枫
99-7
92
特点
? 实现简单, 效率高 。
? 斜线与水平 (或垂直 )线不一样粗 。
? 当线宽为偶数个象素时, 线的中心将偏移半个象素 。
? 利用线刷子生成线的始末端总是水平或垂直的, 看起
来不太自然 。
解决,添加, 线帽 （ line cap）,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
93
图5 - 4 0 线“帽子”
( a ) 方帽 ( c ) 圆帽( b ) 突方帽
2013-3-1 华中理工大学计算机学院 陆枫
99-7
94
? 当比较接近水平的线与比较接近垂直的线汇合时,
汇合处外角将有缺口
图5 - 4 1 线刷子产生的缺口
2013-3-1 华中理工大学计算机学院 陆枫
99-7
95
解决,斜角连接 （ miter join）, 圆连接 （ round
join）, 斜切连接 （ bevel join）
图5 - 4 2 线刷子产生的缺口
( a ) 斜角连接 ( b ) 圆连接 ( c ) 斜切连接
2013-3-1 华中理工大学计算机学院 陆枫
99-7
96
方刷子
特点,
? 方刷子绘制的线条 （ 斜线 ） 比用线刷子所绘制的
线条要粗一些
? 方刷子绘制的斜线与水平 （ 或垂直 ） 线不一样粗
? 方刷子绘制的线条自然地带有一个, 方线帽,
图5 - 4 3 方刷子
3,其它线宽处理方式
? 区域填充
? 改变刷子形状,
1 1 1
1
0
1 1
1 1
1 1
1 0
00
( a ) 象素模板
( b ) 用该模板进行线宽处理
图5 - 4 4 利用象素模板进行线宽处理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
98
4,曲线的线型和线宽
线型,可采用 象素模板 的方法
图5 - 4 5 利用模板1 1 0 进行圆的线型处理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
99
线宽,
? 线刷子
? 方刷子
要显示一致的曲线宽度可通过旋转刷子方向以使其
在沿曲线移动时与斜率方向一致,
? 圆弧刷子
? 采用填充的办法 。
5.6.2 字符的属性
字体, 字形, 字号, 字间距, 行间距等等 。
一般字体确定风格, 字形确定外观, 字号确定尺寸 。
字符的常用属性
字符高
字宽
A
底高
基线
字高
顶高
字符宽
原点
图5 - 4 6 字符的常用属性及其含义
帽线
2013-3-1 华中理工大学计算机学院 陆枫
99-7
101
字符串的属性
文本高度, 文本宽度 （ 扩展 /压缩因子 ）, 字符方向,
文本路径方向, 对齐方式 （ 左对齐, 中心对齐, 或
右对齐, 指定起始, 终止点 ）, 文本字体, 字符的
颜色属性等 。
反绘 （ 从右到左 ）, 倒绘 （ 旋转 180° ）, 写方式
（ 替换或与方式 ） 等 。
5.6.3 区域填充属性
区域填充属性选择包括 颜色, 图案 和 透明度 。
0
0
1
0 1
0 1
11
( a ) 图案模板位图
( b ) 用该模板进行填充
图5 - 4 7 利用图案模板进行三角形的填充
模板图案
2013-3-1 华中理工大学计算机学院 陆枫
99-7
103
根据图案和透明度属性来填充平面区域的基本思想 是,
? 首先用模板定义各种图案。
? 然后, 修改填充的扫描转换算法：在确定了区域内一
象素之后, 不是马上往该象素填色而是先查询模板位
图的对应位置 。 若是以透明方式填充图案, 则当模板
位图的对应位置为 1时, 用前景色写象素, 否则, 不改
变该象素的值 。 若是以不透明方式填充图案, 则视模
板位图对应位置为 1或 0来决定是用前景色还是背景色
去写象素 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
104
确定区域与模板之间的位置关系（对齐方式）,
?一种对齐方式是把有模板原点与填充区域边界或内
部的某点对齐
?一种对齐方式是把模板原点与填充区域外部的某点
对齐
2013-3-1 华中理工大学计算机学院 陆枫
99-7
105
5.7 反走样
用离散量表示连续量引起的失真, 就叫做 走样 （ Liasing） 。
图5 - 4 8 绘制直线时的反走样现象
2013-3-1 华中理工大学计算机学院 陆枫
99-7
106
走样现象,
? 一是光栅图形产生的阶梯形
? 一是图形中包含相对微小的物体时, 这些物体在静
态图形中容易被丢弃或忽略, 在动画序列中时隐时
现, 产生闪烁
2013-3-1 华中理工大学计算机学院 陆枫
99-7
107
图5 - 4 9 丢失细节
( a ) 需显示的矩形 ( b ) 显示结果
图5 - 5 0 运动图形的闪烁
( a ) 显示 ( b ) 不显示 ( c ) 显示 ( d ) 不显示
2013-3-1 华中理工大学计算机学院 陆枫
99-7
108
用于减少或消除这种效果的技术, 称为 反走样
（ antialiasing） 。
一种简单方法,
图5 - 5 1 分辨率提高一倍,阶梯状程度减小一倍
过取样（ supersampling）, 或 后滤波
区域取样（ area sampling）, 或 前滤波
2013-3-1 华中理工大学计算机学院 陆枫
99-7
109
5.7.1 过取样
简单过取样
图5 - 5 2 简单的过取样方式
1 2
3 4
6 7
5
2013-3-1 华中理工大学计算机学院 陆枫
99-7
110
重叠过取样
图5 - 5 3 另一过取样方式
2013-3-1 华中理工大学计算机学院 陆枫
99-7
111
基于加权模板的过取样
1 2 1
2
1
42
1 2
1 1 1
1
1
21
1 1
0 1 0
1
0
41
0 1
图5 - 5 4 加权模板
( a ) ( b ) ( c )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
112
5.7.2 简单的区域取样
图5 - 5 5 有宽度的直线段
1 2
3 4
5 6
2013-3-1 华中理工大学计算机学院 陆枫
99-7
113
如何计算直线段与象素相交区域的面积？
图5 - 5 6 重叠区域面积的计算
D k
D / k
D
( a ) ( b )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
114
可以利用一种求相交区域的近似面积的离散计算方法,
(1)将屏幕象素分割成 n个更小的子象素,
(2)计算中心落在直线段内的子象素的个数 m,
(3)m/n为线段与象素相交区域面积的近似值 。
特点,
? 直线段对一个象素亮度的贡献与两者重叠区域的面积
成正比
? 相同面积的重叠区域对象素的贡献相同
2013-3-1 华中理工大学计算机学院 陆枫
99-7
115
5.7.3 加权区域取样
加权区域取样原理
假想一个连续的加权曲面 （ 或过滤函数 ） 覆盖象素 。
当直线条经过该象素时, 该象素的灰度值是在二
者重叠区域上对滤波器 （ 过滤函数 ） 进行积分的
积分值 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
116
( a ) 立方体滤波 ( b ) 圆锥滤波 ( c ) 高斯滤波
图5 - 5 7 常用的过滤函数
底面
2013-3-1 华中理工大学计算机学院 陆枫
99-7
117
特点,
? 接近理想直线的象素将被分配更多的灰度值；
? 相邻两个象素的滤波器相交, 有利于缩小直线条
上相邻象素的灰度差 。
99-7
1
第 5章 基本图形生成算法
? 提出问题
如何在指定的输出设备上根据坐标描述构造基
本二维几何图形 （ 点, 直线, 圆, 椭圆, 多边
形域, 字符串及其相关属性等 ） 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
2
图形的生成,是在指定的输出设备上, 根据坐标描述
构造二维几何图形 。
图形的扫描转换, 在光栅显示器等数字设备上确定一
个最佳逼近于图形的象素集的过程 。
图5 - 1 用一系列的象素点来逼近直线
2013-3-1 华中理工大学计算机学院 陆枫
99-7
3
5.1 直线的扫描转换
直线的绘制要求,
? 1.直线要直
? 2.直线的端点要准确, 即无定向性和断裂情况
? 3.直线的亮度, 色泽要均匀
? 4.画线的速度要快
? 5.要求直线具有不同的色泽, 亮度, 线型等
2013-3-1 华中理工大学计算机学院 陆枫
99-7
4
5.1.1 数值微分法 (DDA法 )
解决的问题,
给定直线两端点 P0(x0,y0)和 P1(x1,y1),画出该直线 。
直线的微分方程,
1)-(5
01
01 k
xx
yy
x
y
dx
dy ?
?
??
?
??
2013-3-1 华中理工大学计算机学院 陆枫
99-7
5
DDA算法原理,
2)-(5 1
1
yyy
xxx
ii
ii
????
????
?
?
?
?
ε △xx i
y
x
y i
x i +1
y i +1
ε △y
图5 - 2 D D A 算法原理
ε=1/max(|△ x|,|△ y|)
2013-3-1 华中理工大学计算机学院 陆枫
99-7
6
max(|△ x|,|△ y|)=|△ x|,即 |k|≤1的情况,
max(|△ x|,|△ y|)=|△ y|,此时 |k|≥1,
3)-(5
1
1
1
1
1
kyy
x
yyyy
xx
x
xxxx
iiii
iiii
????
?
??????
????
?
??????
?
?
?
?
4)-(5 1
1
11
1
1
????
?
??????
????
?
??????
?
?
iiii
iiii
yy
y
yyyy
k
xx
y
xxxx
?
?
2013-3-1 华中理工大学计算机学院 陆枫
99-7
7
程序
注意,
round(x)=(int)(x+0.5)
图5 - 3 D D A 算法生成直线段
(x i,y i )
(x i +1,r o u n d ( y i +k ))
( r o u n d ( x i + 1 / k ),y i +1 )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
8
特点,
? 增量算法
? 直观, 易实现
? 不利于用硬件实现
2013-3-1 华中理工大学计算机学院 陆枫
99-7
9
5.1.2 中点 Bresenham算法
直线的方程
该直线方程将平面分为三个区域,
? 对于直线上的点, F(x,y)=0；
? 对于直线上方的点, F(x,y)>0；
? 对于直线下方的点, F(x,y)<0。
5)-(5,0),(
01
01
xx
yy
x
ykbkxyyxF
?
??
?
?????? 其中
2013-3-1 华中理工大学计算机学院 陆枫
99-7
10
x
y
F ( x,y ) > 0
F ( x,y ) = 0
F ( x,y ) < 0
图5 - 4 直线将平面分为三个区域
x
y
F ( x,y ) > 0
F ( x,y ) = 0
F ( x,y ) < 0
2013-3-1 华中理工大学计算机学院 陆枫
99-7
11
基本原理,
假定 0≤k≤1,x是最大位移方向
P u (x i + 1,y i +1)
M(x i + 1,y i + 1 / 2 )
P(x i,y i )
P d (x i + 1,y i )
图5 - 5 B r e n s e m h a m 算法生成直线的原理
Q
2013-3-1 华中理工大学计算机学院 陆枫
99-7
12
判别式,
6)-(5 )1(5.0)5.0,1(),( bxkyyxFyxFd iiiiMM ?????????
则有,
?
?
?
?
??
?
)0(
)0( 1
dy
dy
y
P u (x i + 1,y i +1)
M(x i + 1,y i + 1 / 2 )
P(x i,y i )
P d (x i + 1,y i )
图5 - 5 B r e n s e m h a m 算法生成直线的原理
Q
2013-3-1 华中理工大学计算机学院 陆枫
99-7
13
d < 0
(x i,y i )
(x i+1,y i + 0, 5 )
(x i+2,y i + 1, 5 )
误差项的递推
d<0,
kd
kbxky
bxky
yxFd
ii
ii
ii
???
??????
?????
???
1
)1(5.1
)2(5.1
)5.1,2(
2013-3-1 华中理工大学计算机学院 陆枫
99-7
14
误差项的递推
d≥0,
kd
kbxky
bxky
yxFd
ii
ii
ii
??
??????
?????
???
)1(5.0
)2(5.0
)5.0,2(
d > = 0
(x i,y i )
(x i+1,y i + 0, 5 )
(x i+2,y i + 0, 5 )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
15
初始值 d的计算
k
kbkxy
bxky
yxFd
??
?????
?????
???
5.0
5.0
)1(5.0
)5.0,1(
00
00
000
2013-3-1 华中理工大学计算机学院 陆枫
99-7
16
0≤k≤1时 Bresenham算法的 算法步骤 为,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=0.5-k,x=x0,y=y0；
3.绘制点 (x,y)。 判断 d的符号；
若 d<0,则 (x,y)更新为 (x+1,y+1),d更新为 d+1-k；
否则 (x,y)更新为 (x+1,y),d更新为 d-k。
4.当直线没有画完时, 重复步骤 3。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
17
改进,用 2d△ x代替 d
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=△ x-2△ y,x=x0,y=y0。
3.绘制点 (x,y)。 判断 d的符号 。
若 d<0,则 (x,y)更新为 (x+1,y+1),d更新为
d+2△ x-2△ y；
否则 (x,y)更新为 (x+1,y),d更新为 d-2△ y。
4.当直线没有画完时, 重复步骤 3。 否则结束 。
程序
2013-3-1 华中理工大学计算机学院 陆枫
99-7
18
5.1.3 改进的 Bresenham算法
假定直线段的 0≤k≤1
基本原理,
图5 - 8 改进的B r e n s e m h a m 算法绘制直线的原理
d
d
d
d
k
k
k
k
k
2013-3-1 华中理工大学计算机学院 陆枫
99-7
19
?
?
?
?
?
?
?
?
?
??
?
??
?
?
0, 5 )(d
0, 5 )(d 1
1
1
1
i
i
i
ii
y
y
y
xx
误差项的计算
? d初 =0,
? 每走一步,d=d+k
? 一旦 y方向上走了一步, d=d-1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
20
算法步骤,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,d=0,x=x0,y=y0。
3.绘制点 (x,y)。
4.d更新为 d+k,判断 d的符号 。 若 d>0.5,则 (x,y)更
新为 (x+1,y+1),同时将 d更新为 d-1； 否则 (x,y)更
新为 (x+1,y)。
5.当直线没有画完时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
21
改进 1：令 e=d-0.5
?
?
?
?
?
?
?
?
?
??
?
??
?
?
0)(e
0)(e 1
1
1
1
i
i
i
ii
y
y
y
xx
? e初 =-0.5,
? 每走一步有 e=e+k。
? if (e>0) then e=e-1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
22
算法步骤 为,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,e=-0.5,x=x0,y=y0。
3.绘制点 (x,y)。
4.e更新为 e+k,判断 e的符号 。 若 e>0,则 (x,y)更新
为 (x+1,y+1),同时将 e更新为 e-1； 否则 (x,y)更新
为 (x+1,y)。
5.当直线没有画完时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中科技大学计算机学院 陆枫 23
改进 2：用 2e△ x来替换 e
? e初 =-△ x,
? 每走一步有 e=e+2△ y。
? if (e>0) then e=e-2△ x
2013-3-1 华中理工大学计算机学院 陆枫
99-7
24
算法步骤,
1.输入直线的两端点 P0(x0,y0)和 P1(x1,y1)。
2.计算初始值 △ x,△ y,e=-△ x,x=x0,y=y0。
3.绘制点 (x,y)。
4.e更新为 e+2△ y,判断 e的符号 。 若 e>0,则 (x,y)更
新为 (x+1,y+1),同时将 e更新为 e-2△ x； 否则 (x,y)
更新为 (x+1,y)。
5.当直线没有画完时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
25
程序
几种画线算法的比较
2013-3-1 华中理工大学计算机学院 陆枫
99-7
26
5.2 圆的扫描转换
解决的问题,
绘出圆心在原点, 半径为整数 R的圆 x2+y2==R2
5.2.1 八分法画圆
八分法画圆
2013-3-1 华中理工大学计算机学院 陆枫
99-7
27
( x,y )
y
y = - x y = x
(y,x) (-y,x)
(-x,y)
(-x,-y)
(-y,-x) (y,-x)
(x,-y)
2013-3-1 华中理工大学计算机学院 陆枫
99-7
28
解决问题,
y
y=x
图5 - 1 0 1 / 8 圆弧
x
R
2013-3-1 华中理工大学计算机学院 陆枫
99-7
29
5.2.2 简单方程产生圆弧
算法原理,利用其函数方程，直接离散计算
圆的函数方程为,
222 Ryx ??
? ?
7)-(5 )(
2R0,x1
2
1
2
1
1
??
?
??
???
ii
ii
xRr o u n dy
xx
2013-3-1 华中理工大学计算机学院 陆枫
99-7
30
圆的极坐标方程为,
?
?
s in
c o s
Ry
Rx
?
?
)s in(
8)-(5 )c o s(
)(
11
11
1
??
??
?
?
?
????
ii
ii
ii
Rr o u n dy
Rr o u n dx
?
?
???? 为一固定角度步长
2013-3-1 华中理工大学计算机学院 陆枫
99-7
31
5.2.3 中点 Bresenham画圆
构造函数 F(x,y)=x2-y2-R2。
? 对于圆上的点, 有 F(x,y)=0；
? 对于圆外的点, F(x,y)>0；
? 而对于圆内的点, F(x,y)<0。
算法原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
32
x
y
图5 - 1 1 中点B r e s e n h a m 画圆的原理
P
P u
P d
M
2013-3-1 华中理工大学计算机学院 陆枫
99-7
33
当 d≤0时, 下一点取 Pu(xi +1,yi)；
当 d>0时, 下一点取 Pd(xi +1,yi-1)。
M的坐标为,M(xi +1,yi-0.5)
?当 F(xM,yM)<0时, 取 Pu(xi +1,yi)
?当 F(xM,yM)>0时, 取 Pd(xi +1,yi-1)
?当 F(xM,yM)=0时, 约定取 Pu。
构造判别式,
222 )5.0()1()5.0,1(),( RyxyxFyxFd iiiiMM ?????????
2013-3-1 华中理工大学计算机学院 陆枫
99-7
34
误差项的递推
d≤0,
(a) d<=0的 情况
P
x i
y i - 2
x i + 1
y i
y i - 1
x i + 2
32
32)5.0()1(
)5.0()2(
)5.0,2(
222
222
???
???????
?????
???
i
iii
ii
ii
xd
xRyx
Ryx
yxFd
2013-3-1 华中理工大学计算机学院 陆枫
99-7
35
d>0,
5)(2
)22()32()5.0()1(
)5.1()2(
)5.1,2(
222
222
????
??????????
?????
???
ii
iiii
ii
ii
yxd
yxRyx
Ryx
yxFd
(b) d>0的 情况
P
x i x i + 2x i + 1
y i - 1
y i
y i - 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
36
判别式的初始值
R
RR
RFd
??
????
??
25.1
)5.0(1
)5.0,1(
22
0
2013-3-1 华中理工大学计算机学院 陆枫
99-7
37
算法步骤,
1.输入圆的半径 R。
2.计算初始值 d=1.25-R,x=0,y=R。
3.绘制点 (x,y)及其在八分圆中的另外七个对称点 。
4.判断 d的符号 。 若 d≤0,则先将 d更新为 d+2x+3,再
将 (x,y)更新为 (x+1,y)； 否则先将 d更新为 d+2(x-y)+5，
再将 (x,y)更新为 (x+1,y-1)。
5.当 x<y时, 重复步骤 3和 4。 否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
38
改进,用 d-0.25代替 d
算法步骤,
1.输入圆的半径 R。
2.计算初始值 d=1-R,x=0,y=R。
3.绘制点 (x,y)及其在八分圆中的另外七个对称点 。
4.判断 d的符号 。 若 d≤0,则先将 d更新为 d+2x+3，
再将 (x,y)更新为 (x+1,y)； 否则先将 d更新为 d+2(x-
y)+5,再将 (x,y)更新为 (x+1,y-1)。
5.当 x<y时, 重复步骤 3和 4。 否则结束 。 程序
2013-3-1 华中理工大学计算机学院 陆枫
99-7
39
5.3 椭圆的扫描转换
5.3.1 椭圆的特征 b
a x
y
图5 - 1 4 长半轴为a,短半轴为b 的标准椭圆
( x,y )
( x,- y )( - x,- y )
( - x,y )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
40
0),( 222222 ???? bayaxbyxF
? 对于椭圆上的点, 有 F(x,y)=0；
? 对于椭圆外的点, F(x,y)>0；
? 对于椭圆内的点, F(x,y)<0。
解决问题,
y
x
2013-3-1 华中理工大学计算机学院 陆枫
99-7
41
以弧上斜率为－ 1的点作为分界将第一象限椭圆弧分
为上下两部分。
上半部分
下半部分
二分量相等的法向量
图5 - 1 5 第一象限的椭圆弧
y
x
2013-3-1 华中理工大学计算机学院 陆枫
99-7
42
引理 5-1：若在当前中点，法向量的 y分量比 x分量大，
即
)5.0()1( 22 ??? ii yaxb
而在下一个中点, 不等号改变方向, 则说明椭圆弧
从上部分转入下部分 。
yjaxibj
y
Fi
x
FyxN 22 22),( ??
?
??
?
??
法向量
2013-3-1 华中理工大学计算机学院 陆枫
99-7
43
5.3.2 椭圆的中点 Bresenham算法
算法原理
P u
图5 - 1 6 B r e s e n h a m 椭圆绘制算法的原理
y
x
P d
P
P l P r
P
2013-3-1 华中理工大学计算机学院 陆枫
99-7
44
先推导上半部分的椭圆绘制公式
p ( x i,y i )
p u (x i+1,y i )
p d (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 7 上半部分椭圆弧的绘制原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
45
判别式
2222221 )5.0()1()5.0,1( bayaxbyxFd iiii ????????
? 若 d1≤0,取 Pu(xi+1,yi)
? 若 d1>0,取 Pd(xi+1,yi-1)
p ( x i,y i )
p u (x i+1,y i )
p d (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 7 上半部分椭圆弧的绘制原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
46
误差项的递推
d1≤0,
(a) d<=0的 情况
P
x i
y i - 2
x i + 1
y i
y i - 1
x i + 2
)x(bd
)x(bba).(ya)(xb
ba).(ya)(xb).,yF ( xd
i
iii
iiii
32
32501
502502
2
1
2222222
222222
1
???
????????
????????
2013-3-1 华中理工大学计算机学院 陆枫
99-7
47
d1>0,
)22()32(
)22()32()5.0()1(
)5.1()2()5.1,2(
22
1
22222222
222222
1
??????
??????????
????????
ii
iiii
iiii
yaxbd
yaxbbayaxb
bayaxbyxFd
(b) d>0的 情况
P
x i x i + 2x i + 1
y i - 1
y i
y i - 2
判别式的初始值
)25.0(
)5.0()5.0,1(
22
22222
10
????
??????
bab
bababbFd
2013-3-1 华中理工大学计算机学院 陆枫
99-7
49
p ( x i,y i )
p l (x i,y i-1 ) p r (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 9 下半部分椭圆弧的绘制原理
再来推导椭圆弧下半部分的绘制公式
原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
50
判别式
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii ????????
?若 d2>0,取 Pl(xi,yi-1)
?若 d2≤0,取 Pr(xi+1,yi-1)
p ( x i,y i )
p l (x i,y i-1 ) p r (x i+1,y i-1 )
M (x i+1,y i - 0, 5 )
5 - 1 9 下半部分椭圆弧的绘制原理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
51
误差项的递推
d2>0,
)y(ad
)y(aba)(ya)(xb
ba)(ya)(xb),yF ( xd
i
iii
iiii
32
3215.0
25.025.0
2
2
2222222
222222
2
????
????????
????????
(a) d>0的 情况
P
x i
y i - 2
x i + 1
y i
y i - 1
x i + 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
52
d2≤0,
)32()22(
)32()22()1()5.0(
)2()5.1()2,5.1(
22
2
22222222
222222
2
??????
??????????
????????
ii
iiii
iiii
yaxbd
yaxbbayaxb
bayaxbyxFd
(b) d<=0的 情况
P
x i x i + 2x i + 1
y i - 1
y i
y i - 2
2013-3-1 华中理工大学计算机学院 陆枫
99-7
53
注意,
? 上半部分的终止判别
? 下半部分误差项的初值
算法步骤,
1.输入椭圆的长半轴 a和短半轴 b。
2.计算初始值 d=b2+a2(-b+0.25),x=0,y=b。
3.绘制点 (x,y)及其在四分象限上的另外三个对称点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
54
4.判断 d的符号 。 若 d≤0,则先将 d更新为 d+b2(2x+3)，
再将 ( x,y) 更新为 ( x+1,y)； 否则先将 d 更 新 为
d+b2(2x+3)+a2(-2y+2),再将 (x,y)更新为 (x+1,y-1)。
5.当 b2(x+1)<a2(y-0.5)时, 重复步骤 3和 4。 否则转到步
骤 6。
6.用上半部分计算的最后点 (x,y)来计算下半部分中 d的
初值,
222222 )1()5.0( bayaxbd ?????
2013-3-1 华中理工大学计算机学院 陆枫
99-7
55
7.绘制点 (x,y)及其在四分象限上的另外三个对称点 。
8.判断 d的符号 。 若 d≤0,则先将 d更新为 b2(2xi+2)+a2(-
2yi+3),再将 (x,y)更新为 (x+1,y-1)； 否则先将 d更新
为 d+a2(-2yi+3),再将 (x,y)更新为 (x,y-1)。
9.当 y>0时, 重复步骤 7和 8。 否则结束 。
程序
2013-3-1 华中理工大学计算机学院 陆枫
99-7
56
5.4 多边形的扫描转换与区域填充
多边形的扫描转换 主要是通过确定穿越区域的扫
描线的覆盖区间来填充,
区域填充 是从给定的位置开始涂描直到指定的边
界条件为止 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
57
5.4.1 多边形的扫描转换
顶点表示 用多边形的顶点序列来刻划多边形
点阵表示 是用位于多边形内的象素的集合来刻划多边形
扫描转换多边形或多边形的填充,从多边形顶点表示到
点阵表示的转换 。
1,什么是多边形的扫描转换
2013-3-1 华中理工大学计算机学院 陆枫
99-7
58
2,x-扫描线算法
基本思想
图5 - 2 3 x - 扫描线算法填充多边形
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
2013-3-1 华中理工大学计算机学院 陆枫
99-7
59
算法步骤,
(1)确定多边形所占有的最大扫描线数, 得到多边形顶
点的最小和最大 y值 （ ymin和 ymax） 。
(2)从 y=ymin到 y=ymax,每次用一条扫描线进行填充 。
(3)对一条扫描线填充的过程可分为四个步骤,
a.求交
b.排序
c.交点配对
d.区间填色
2013-3-1 华中理工大学计算机学院 陆枫
99-7
60
存在问题,当扫描线与多边形顶点相交时, 交点
的取舍问题 。
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
图5 - 2 4 与多边形顶点相交的交点的处理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
61
解决,
当扫描线与多边形的顶点相交时,
? 若共享顶点的两条边分别落在扫描线的两边, 交
点只算一个；
? 若共享顶点的两条边在扫描线的同一边, 这时交
点作为零个或两个 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
62
图5 - 2 5 与扫描线相交的多边形顶点的交点数
0
1
1 1 1
0 2
2
2
填充过程实例
2013-3-1 华中理工大学计算机学院 陆枫
99-7
63
3,改进的有效边表算法 （ Y连贯性算法 ）
x i,y i
x i + 1,y i + 1
1
1/k
图5 - 2 6 与多边形边界相交的两条
连续扫描线交点的相关性
改进原理,
? 处理一条扫描线时, 仅对
有效边求交
? 利用扫描线的连贯性
? 利用多边形边的连贯性
2013-3-1 华中理工大学计算机学院 陆枫
99-7
64
有效边 （ Active Edge）, 指与当前扫描线相交的多
边形的边, 也称为活性边 。
有效边表 （ Active Edge Table,AET）, 把有效边按
与扫描线交点 x坐标递增的顺序存放在一个链表中,
此链表称为有效边表 。
有效边表的每个结点,
x ymax 1/k next
2013-3-1 华中理工大学计算机学院 陆枫
99-7
65
边表 （ Edge Table）
边表的构造,
(1)首先构造一个纵向链表, 链表的长度为多边形所占有
的最大扫描线数, 链表的每个结点, 称为一个桶, 则
对应多边形覆盖的每一条扫描线 。
(2)将每条边的信息链入与该边最小 y坐标 （ ymin ） 相对
应的桶处 。 也就是说, 若某边的较低端点为 ymin,则
该边就放在相应的扫描线桶中 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
66
(3)每条边的数据形成一个结点, 内容包括：该扫描
线与该边的初始交点 x（ 即较低端点的 x值 ）, 1/k，
以及该边的最大 y值 ymax。
x|ymin ymax 1/k NEXT
(4)同一桶中若干条边按 X|ymin由小到大排序, 若
X|ymax 相等, 则按照 1/m由小到大排序 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
67
解决顶点交点计为 1时的情形,
图5 - 2 8 将多边形的某些边缩短以分离那些应
计为1 个交点的顶点
（a ) 原图 （b ) 缩短y m a x 的边 （c ) 缩短y m i n 的边
扫描线y
扫描线y + 1
扫描线y - 1
2013-3-1 华中理工大学计算机学院 陆枫
99-7
68
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
2013-3-1 华中理工大学计算机学院 陆枫
99-7
69
1
2
3
4
5
6
7
8
9
10
11
12
3 -1/3 3 5 3/4 8 5 -1/2 8 9 1/2
1 12 2/5
7 12 -1 7 9 5
桶
p 3 p 2 p 3 p 4 p 5 p 4 p 5 p6
p 2 p 1
p 0 p 1 p 0 p6
x|y min ymax 1/k next
( c ) 边表
6
2013-3-1 华中理工大学计算机学院 陆枫
99-7
70
算法步骤,
(1)初始化：构造边表, 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),否则结束 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
71
5.4.2 边缘填充算法
边缘填充算法
算法简单, 但对于复杂图型, 每一象素可能被访问多次
栅栏填充算法
栅栏 指的是一条过多边形顶点且与扫描线垂直的直线 。
它把多边形分为两半 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
72
边标志算法
分为两个步骤,
(1)打标记
(2)填充
当用软件实现本算法时, 速度与改进的有效边表算法
相当, 但本算法用硬件实现后速度会有很大提高 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
73
5.4.3 区域填充
区域 是指已经表示成点阵形式的填充图形, 它是像
素集合 。
4-邻接点 和 8-邻接点
4
4p4
4
( b ) p 的8 - 邻接点
8 8 8
8
8
p8
8 8
( a ) p 的4 - 邻接点
图5 - 3 3 邻接点的定义
2013-3-1 华中理工大学计算机学院 陆枫
99-7
74
4-连通区域 和 8-连通区域
把位于给定区域的边界上的象素一一列举出来的方法
称为 边界表示法 。
边界填充算法 （ Boundary-fill Algorithm） 。
枚举出给定区域内所有象素的表示方法称为 内点表示 。
泛填充算法 （ Flood-fill Algorithm）
图5 - 3 2 区域的边界表示和内点表示
( a ) 以边界表示的4 - 连通区域 ( b ) 以内点表示的4 - 连通区域
( c ) 以边界表示的8 - 连通区域 ( d ) 以内点表示的8 - 连通区域
2013-3-1 华中理工大学计算机学院 陆枫
99-7
76
1,边界填充算法
算法的输入：种子点坐标 (x,y),填充色和边界颜色 。
栈结构实现 4-连通边界填充算法 的 算法步骤 为,
种子象素入栈；当栈非空时重复执行如下三步操作,
(1)栈顶象素出栈；
(2)将出栈象素置成填充色；
(3)检查出栈象素的 4-邻接点, 若其中某个象素点不是边界色
且未置成多边形色, 则把该象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
77
栈结构实现 8-连通边界填充算法 的 算法步骤 为,
种子象素入栈；当栈非空时重复执行如下三步操作,
(1)栈顶象素出栈；
(2)将出栈象素置成填充色；
(3)检查出栈象素的 8-邻接点, 若其中某个象素点不是
边界色且未置成多边形色, 则把该象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
78
特点,
? 可以用于填充带有内孔的平面区域 。
? 把太多的象素压入堆栈
改进
通过沿扫描线填充水平象素段, 来代替处理 4-邻
接点和 8-邻接点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
79
沿扫描线填充水平象素段的 4-连通边界填充算法步骤,
种子象素入栈；当栈非空时作如下三步操作,
(1)栈顶象素出栈；
(2)填充出栈象素所在扫描行的连续象素段, 直到遇到
边界象素为止, 即每出栈一个象素, 就对包含该象
素的整个扫描线区间进行填充；
(3)在区间中检查与当前扫描线相邻的上下两条扫描线
的有关象素是否全为边界象素或已填充的象素, 若
存在非边界, 未填充边界的象素, 则把每一区间的
最右象素取作种子象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
80
2,泛填充算法
算法的输入：种子点坐标 (x,y),填充色和内部点的
颜色 。
算法原理,
算法从指定的种子 (x,y)开始, 用所希望的填充颜色
赋给所有当前为给定内部颜色的象素点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
81
8-连通泛填充 算法步骤 如下,
种子象素入栈；当栈非空时重复执行如下三步操作,
(1)栈顶象素出栈；
(2)将出栈象素置成填充色；
(3)检查出栈象素的 8-邻接点, 若其中某个象素点不
是给定内部点的颜色且未置成新的填充色, 则把
该象素入栈 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
82
注意,
当以边界表示时, 4-连通边界填充算法只能填充 4-
连通区域, 8-连通边界填充算法也只能填充 8-连
通区域 。
当以内点表示时, 8-连通泛填充算法可以填充 8-连
通区域也可以填充 4-连通区域, 当然 4-连通泛填
充算法还是只能填充 4-连通区域 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
83
5.4.4 其他相关的概念
1,内 -外测试
不自交的多边形, 自相交的多边形
奇 -偶规则 （ Odd-even Rule）
从任意位置 p作一条射线, 若与该射线相交的多
边形边的数目为奇数, 则 p是多边形内部点, 否
则是外部点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
84
非零环绕数规则 （ Nonzero Winding Number Rule）
? 首先使多边形的边变为矢量 。
? 将环绕数初始化为零 。
? 再从任意位置 p作一条射线 。 当从 p点沿射线方向移
动时, 对在每个方向上穿过射线的边计数, 每当多
边形的边从右到左穿过射线时, 环绕数加 1,从左到
右时, 环绕数减 1。
? 处理完多边形的所有相关边之后, 若环绕数为非零,
则 p为内部点, 否则, p是外部点 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
85
2,曲线边界区域的填充
相交计算
2013-3-1 华中理工大学计算机学院 陆枫
99-7
86
5.5 字符处理
ASCI码：, 美国信息交换用标准代码集, (American
Standard Code for Information Interchange),简称
ASCI码 。
国际码：, 中华人民共和国国家标准信息交换编码,
简称为国际码, 代号 GB2312－ 80。
字库,字库中储存了每个字符的图形信息。
矢量字库 和 点阵字库
5.5.1 点阵字符
在点阵表示中, 每个字符由一个 点阵位图 来表示
显示时,
形成 字符的象素图案
图5 - 3 6 字符A 的点阵表示
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
11
1 1 1
1
1
1
1
1
1
1
1
1
1
1
11 1
1111
1
00000
00000
00000
00000
0
0
0000
0000
0000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
000
0
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
0
(a)字符 A的点 阵位图 (a)字符 A的象 素图案
2013-3-1 华中理工大学计算机学院 陆枫
99-7
88
5.5.2 矢量字符
矢量字符采用直线和曲线段来描述字符形状, 矢量字
符库中记录的是 笔划信息 。
显示时,解释字符的每个笔划信息
2013-3-1 华中理工大学计算机学院 陆枫
99-7
89
5.6 属性处理
当前属性值表
5.6.1 线型和线宽
1,线型处理
实心段和中间空白段的长度 （ 象素数目 ） 可用 象素模
板 (pixel mask)指定 。
存在问题,如何保持任何方向的划线长度近似地相等
2013-3-1 华中理工大学计算机学院 陆枫
99-7
90
解决
可根据线的斜率来调整实心段和中间空白段的象素数目 。
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
2013-3-1 华中理工大学计算机学院 陆枫
99-7
91
2,线刷子和方刷子处理线宽
线刷子：垂直刷子, 水平刷子
图5 - 3 9 线刷子
(a) (b)
2013-3-1 华中理工大学计算机学院 陆枫
99-7
92
特点
? 实现简单, 效率高 。
? 斜线与水平 (或垂直 )线不一样粗 。
? 当线宽为偶数个象素时, 线的中心将偏移半个象素 。
? 利用线刷子生成线的始末端总是水平或垂直的, 看起
来不太自然 。
解决,添加, 线帽 （ line cap）,
2013-3-1 华中理工大学计算机学院 陆枫
99-7
93
图5 - 4 0 线“帽子”
( a ) 方帽 ( c ) 圆帽( b ) 突方帽
2013-3-1 华中理工大学计算机学院 陆枫
99-7
94
? 当比较接近水平的线与比较接近垂直的线汇合时,
汇合处外角将有缺口
图5 - 4 1 线刷子产生的缺口
2013-3-1 华中理工大学计算机学院 陆枫
99-7
95
解决,斜角连接 （ miter join）, 圆连接 （ round
join）, 斜切连接 （ bevel join）
图5 - 4 2 线刷子产生的缺口
( a ) 斜角连接 ( b ) 圆连接 ( c ) 斜切连接
2013-3-1 华中理工大学计算机学院 陆枫
99-7
96
方刷子
特点,
? 方刷子绘制的线条 （ 斜线 ） 比用线刷子所绘制的
线条要粗一些
? 方刷子绘制的斜线与水平 （ 或垂直 ） 线不一样粗
? 方刷子绘制的线条自然地带有一个, 方线帽,
图5 - 4 3 方刷子
3,其它线宽处理方式
? 区域填充
? 改变刷子形状,
1 1 1
1
0
1 1
1 1
1 1
1 0
00
( a ) 象素模板
( b ) 用该模板进行线宽处理
图5 - 4 4 利用象素模板进行线宽处理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
98
4,曲线的线型和线宽
线型,可采用 象素模板 的方法
图5 - 4 5 利用模板1 1 0 进行圆的线型处理
2013-3-1 华中理工大学计算机学院 陆枫
99-7
99
线宽,
? 线刷子
? 方刷子
要显示一致的曲线宽度可通过旋转刷子方向以使其
在沿曲线移动时与斜率方向一致,
? 圆弧刷子
? 采用填充的办法 。
5.6.2 字符的属性
字体, 字形, 字号, 字间距, 行间距等等 。
一般字体确定风格, 字形确定外观, 字号确定尺寸 。
字符的常用属性
字符高
字宽
A
底高
基线
字高
顶高
字符宽
原点
图5 - 4 6 字符的常用属性及其含义
帽线
2013-3-1 华中理工大学计算机学院 陆枫
99-7
101
字符串的属性
文本高度, 文本宽度 （ 扩展 /压缩因子 ）, 字符方向,
文本路径方向, 对齐方式 （ 左对齐, 中心对齐, 或
右对齐, 指定起始, 终止点 ）, 文本字体, 字符的
颜色属性等 。
反绘 （ 从右到左 ）, 倒绘 （ 旋转 180° ）, 写方式
（ 替换或与方式 ） 等 。
5.6.3 区域填充属性
区域填充属性选择包括 颜色, 图案 和 透明度 。
0
0
1
0 1
0 1
11
( a ) 图案模板位图
( b ) 用该模板进行填充
图5 - 4 7 利用图案模板进行三角形的填充
模板图案
2013-3-1 华中理工大学计算机学院 陆枫
99-7
103
根据图案和透明度属性来填充平面区域的基本思想 是,
? 首先用模板定义各种图案。
? 然后, 修改填充的扫描转换算法：在确定了区域内一
象素之后, 不是马上往该象素填色而是先查询模板位
图的对应位置 。 若是以透明方式填充图案, 则当模板
位图的对应位置为 1时, 用前景色写象素, 否则, 不改
变该象素的值 。 若是以不透明方式填充图案, 则视模
板位图对应位置为 1或 0来决定是用前景色还是背景色
去写象素 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
104
确定区域与模板之间的位置关系（对齐方式）,
?一种对齐方式是把有模板原点与填充区域边界或内
部的某点对齐
?一种对齐方式是把模板原点与填充区域外部的某点
对齐
2013-3-1 华中理工大学计算机学院 陆枫
99-7
105
5.7 反走样
用离散量表示连续量引起的失真, 就叫做 走样 （ Liasing） 。
图5 - 4 8 绘制直线时的反走样现象
2013-3-1 华中理工大学计算机学院 陆枫
99-7
106
走样现象,
? 一是光栅图形产生的阶梯形
? 一是图形中包含相对微小的物体时, 这些物体在静
态图形中容易被丢弃或忽略, 在动画序列中时隐时
现, 产生闪烁
2013-3-1 华中理工大学计算机学院 陆枫
99-7
107
图5 - 4 9 丢失细节
( a ) 需显示的矩形 ( b ) 显示结果
图5 - 5 0 运动图形的闪烁
( a ) 显示 ( b ) 不显示 ( c ) 显示 ( d ) 不显示
2013-3-1 华中理工大学计算机学院 陆枫
99-7
108
用于减少或消除这种效果的技术, 称为 反走样
（ antialiasing） 。
一种简单方法,
图5 - 5 1 分辨率提高一倍,阶梯状程度减小一倍
过取样（ supersampling）, 或 后滤波
区域取样（ area sampling）, 或 前滤波
2013-3-1 华中理工大学计算机学院 陆枫
99-7
109
5.7.1 过取样
简单过取样
图5 - 5 2 简单的过取样方式
1 2
3 4
6 7
5
2013-3-1 华中理工大学计算机学院 陆枫
99-7
110
重叠过取样
图5 - 5 3 另一过取样方式
2013-3-1 华中理工大学计算机学院 陆枫
99-7
111
基于加权模板的过取样
1 2 1
2
1
42
1 2
1 1 1
1
1
21
1 1
0 1 0
1
0
41
0 1
图5 - 5 4 加权模板
( a ) ( b ) ( c )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
112
5.7.2 简单的区域取样
图5 - 5 5 有宽度的直线段
1 2
3 4
5 6
2013-3-1 华中理工大学计算机学院 陆枫
99-7
113
如何计算直线段与象素相交区域的面积？
图5 - 5 6 重叠区域面积的计算
D k
D / k
D
( a ) ( b )
2013-3-1 华中理工大学计算机学院 陆枫
99-7
114
可以利用一种求相交区域的近似面积的离散计算方法,
(1)将屏幕象素分割成 n个更小的子象素,
(2)计算中心落在直线段内的子象素的个数 m,
(3)m/n为线段与象素相交区域面积的近似值 。
特点,
? 直线段对一个象素亮度的贡献与两者重叠区域的面积
成正比
? 相同面积的重叠区域对象素的贡献相同
2013-3-1 华中理工大学计算机学院 陆枫
99-7
115
5.7.3 加权区域取样
加权区域取样原理
假想一个连续的加权曲面 （ 或过滤函数 ） 覆盖象素 。
当直线条经过该象素时, 该象素的灰度值是在二
者重叠区域上对滤波器 （ 过滤函数 ） 进行积分的
积分值 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
116
( a ) 立方体滤波 ( b ) 圆锥滤波 ( c ) 高斯滤波
图5 - 5 7 常用的过滤函数
底面
2013-3-1 华中理工大学计算机学院 陆枫
99-7
117
特点,
? 接近理想直线的象素将被分配更多的灰度值；
? 相邻两个象素的滤波器相交, 有利于缩小直线条
上相邻象素的灰度差 。
