1
余 敦 辉湖北大学 数计学院计算机图形学
2
第五章 基本图形生成算法光栅扫描图形系统的结构光柵扫描特点：
* 数据量大 － 快的要求
* 显示的离散化 － 准的要求
* 独立的图形显示处理器 － 快速，实时硬件处理的扫描转换
CP
U
系统总线显示处理器 系统存储器显示处理器存储器帧缓存视频控制器
I/O设备监视器
3
第五章 基本图形生成算法图形显示处理器 (加速引擎 )
任务,进行扫描转换 (Scan Conversion)
扫描转换,将应用程序给出的图形定义数字化为一组像素强度值,并放到帧缓存器扫描转换的工作内容：
－基本图形的生成
－字符的生成
－填充,裁剪
－线型的处理
－彩色处理
－某些变换和管理
4
第五章 基本图形生成算法坐标系统为描述对象、构造场景或完成图形变换，需要不同的坐标系！
1,建模坐标系 － 定义对象
2,世界坐标系 － 定义对象与外界环境的关系
3,设备坐标系 － 定义图形显示的位置、大小
4,规范化坐标 － 为保证互换性（与设备无关）
而定义的辅助坐标
5
第五章 基本图形生成算法坐标系统建模坐标
Modeling CoordinateLocal Coordinate
Master Coordinate
世界坐标
World Coordinate
绘图仪其它输出设备设备坐标
Device Coordinate
Screen Coordinate
1
1
1
规范化坐标
NormalizedCoordinate
6
第五章 基本图形生成算法
5.1 直线的扫描转换光栅扫描显示下画直线存在的问题：
(1) 显示速度问题：
例：分辨率,1024× 768,24Bit 彩色,
帧存容量,1024× 768× 3＝ 2,359,296 Byte
刷新率 85Hz,85× 2,359,296 ＝ 200,540,160 (Byte / S)
存储器读出时间,~5nS
(2) 显示质量问题：
阶梯状
线的粗细不一
线的亮度差异
7
第五章 基本图形生成算法
5.1 直线的扫描转换直线的绘制要求：
1.直线要直
2.直线的端点要准确,即无定向性和断裂情况
3.直线的亮度,色泽要均匀
4.画线的速度要快
5.要求直线具有不同的色泽,亮度,线型等解决的问题：
给定直线两端点 P0(x0,y0)和 P1(x1,y1),画出该直线 。
8
5.1.1 数值微分法 (DDA法 )
直线的微分方程：
1)-(5
01
01 kxx yyxydxdy
第五章 基本图形生成算法
5.1 直线的扫描转换
DDA算法原理：
2)-(5 1
1
yyy
xxx
ii
ii
ε=1/max(|△ x|,|△ y|)
ε △xx i
y
x
y i
x i +1
y i +1
ε △y
图5 - 2 D D A 算法原理
9
第五章 基本图形生成算法
5.1 直线的扫描转换
max(|△ x|,|△ y|)=|△ x|,即 |k|≤1的情况：
max(|△ x|,|△ y|)=|△ y|,此时 |k|≥1：
4)-(5 1
1
11
1
1
iiii
iiii
yy
y
yyyy
k
xx
y
xxxx
3)-(5
1
1
1
1
1
kyy
x
yyyy
xx
x
xxxx
iiii
iiii
10
第五章 基本图形生成算法
5.1 直线的扫描转换注意,round(x)=(int)(x+0.5)
图5- 3 D DA 算法生成直线段
(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 )
11
第五章 基本图形生成算法
5.1 直线的扫描转换
Void DDAline(int x0,int y0,int x1,int y1)
{
int dx,dy,eps1,k;
float x,y,xIncre,yIncre;
dx=x1-x0; dy=y1-y0;
x=x0; y=y0;
If (abs(dx)>abs(dy)) eps1=abs(dx);
else eps1=abs(dy);
xIncre=(float)dy/(float)eps1;
yIncre=(float)dy/(float)eps1;
for (k=0;k<=eps1;k++) {
putpixel((int)(x+0.5),(int)(y+0.5));
x+=xIncre;
y+=yIncre;
}
}
12
第五章 基本图形生成算法
5.1 直线的扫描转换特点：
增量算法直观,易实现缺点：
浮点运算、取整－－,废时，且不利于硬件实现。
不利于用硬件实现
13
14
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
其中
5.1 直线的扫描转换
15
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
16
基本原理,
假定 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
17
判别式,
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
18
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(
19
误差项的递推
d≥0：
d > = 0
(x i,y i )
(x i+1,y i+0.5 )
(x i+2,y i+0.5 )
kd
kbxky
bxky
yxFd
ii
ii
ii
)1(5.0
)2(5.0
)5.0,2(
20
初始值 d的计算
k
kbkxy
bxky
yxFd
5.0
5.0
)1(5.0
)5.0,1(
00
00
000
21
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。 否则结束 。
5.1.2 中点 Bresenham算法
5.1 直线的扫描转换
22
改进,用 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。
当直线没有画完时,重复步骤 。 否则结束 。
5.1.2 中点 Bresenham算法
5.1 直线的扫描转换
23
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
5.1 直线的扫描转换
24
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
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
25
算法步骤,
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。 否则结束 。
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
26
改进 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
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
27
算法步骤 为：
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。 否则结束 。
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
28
改进 2：用 2e△ x来替换 e
e初 =-△ x，
每走一步有 e=e+2△ y。
if (e>0) then e=e-2△ x
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
29
算法步骤,
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。 否则结束 。
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
30
余 敦 辉湖北大学 数计学院计算机图形学
2
第五章 基本图形生成算法光栅扫描图形系统的结构光柵扫描特点：
* 数据量大 － 快的要求
* 显示的离散化 － 准的要求
* 独立的图形显示处理器 － 快速，实时硬件处理的扫描转换
CP
U
系统总线显示处理器 系统存储器显示处理器存储器帧缓存视频控制器
I/O设备监视器
3
第五章 基本图形生成算法图形显示处理器 (加速引擎 )
任务,进行扫描转换 (Scan Conversion)
扫描转换,将应用程序给出的图形定义数字化为一组像素强度值,并放到帧缓存器扫描转换的工作内容：
－基本图形的生成
－字符的生成
－填充,裁剪
－线型的处理
－彩色处理
－某些变换和管理
4
第五章 基本图形生成算法坐标系统为描述对象、构造场景或完成图形变换，需要不同的坐标系！
1,建模坐标系 － 定义对象
2,世界坐标系 － 定义对象与外界环境的关系
3,设备坐标系 － 定义图形显示的位置、大小
4,规范化坐标 － 为保证互换性（与设备无关）
而定义的辅助坐标
5
第五章 基本图形生成算法坐标系统建模坐标
Modeling CoordinateLocal Coordinate
Master Coordinate
世界坐标
World Coordinate
绘图仪其它输出设备设备坐标
Device Coordinate
Screen Coordinate
1
1
1
规范化坐标
NormalizedCoordinate
6
第五章 基本图形生成算法
5.1 直线的扫描转换光栅扫描显示下画直线存在的问题：
(1) 显示速度问题：
例：分辨率,1024× 768,24Bit 彩色,
帧存容量,1024× 768× 3＝ 2,359,296 Byte
刷新率 85Hz,85× 2,359,296 ＝ 200,540,160 (Byte / S)
存储器读出时间,~5nS
(2) 显示质量问题：
阶梯状
线的粗细不一
线的亮度差异
7
第五章 基本图形生成算法
5.1 直线的扫描转换直线的绘制要求：
1.直线要直
2.直线的端点要准确,即无定向性和断裂情况
3.直线的亮度,色泽要均匀
4.画线的速度要快
5.要求直线具有不同的色泽,亮度,线型等解决的问题：
给定直线两端点 P0(x0,y0)和 P1(x1,y1),画出该直线 。
8
5.1.1 数值微分法 (DDA法 )
直线的微分方程：
1)-(5
01
01 kxx yyxydxdy
第五章 基本图形生成算法
5.1 直线的扫描转换
DDA算法原理：
2)-(5 1
1
yyy
xxx
ii
ii
ε=1/max(|△ x|,|△ y|)
ε △xx i
y
x
y i
x i +1
y i +1
ε △y
图5 - 2 D D A 算法原理
9
第五章 基本图形生成算法
5.1 直线的扫描转换
max(|△ x|,|△ y|)=|△ x|,即 |k|≤1的情况：
max(|△ x|,|△ y|)=|△ y|,此时 |k|≥1：
4)-(5 1
1
11
1
1
iiii
iiii
yy
y
yyyy
k
xx
y
xxxx
3)-(5
1
1
1
1
1
kyy
x
yyyy
xx
x
xxxx
iiii
iiii
10
第五章 基本图形生成算法
5.1 直线的扫描转换注意,round(x)=(int)(x+0.5)
图5- 3 D DA 算法生成直线段
(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 )
11
第五章 基本图形生成算法
5.1 直线的扫描转换
Void DDAline(int x0,int y0,int x1,int y1)
{
int dx,dy,eps1,k;
float x,y,xIncre,yIncre;
dx=x1-x0; dy=y1-y0;
x=x0; y=y0;
If (abs(dx)>abs(dy)) eps1=abs(dx);
else eps1=abs(dy);
xIncre=(float)dy/(float)eps1;
yIncre=(float)dy/(float)eps1;
for (k=0;k<=eps1;k++) {
putpixel((int)(x+0.5),(int)(y+0.5));
x+=xIncre;
y+=yIncre;
}
}
12
第五章 基本图形生成算法
5.1 直线的扫描转换特点：
增量算法直观,易实现缺点：
浮点运算、取整－－,废时，且不利于硬件实现。
不利于用硬件实现
13
14
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
其中
5.1 直线的扫描转换
15
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
16
基本原理,
假定 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
17
判别式,
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
18
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(
19
误差项的递推
d≥0：
d > = 0
(x i,y i )
(x i+1,y i+0.5 )
(x i+2,y i+0.5 )
kd
kbxky
bxky
yxFd
ii
ii
ii
)1(5.0
)2(5.0
)5.0,2(
20
初始值 d的计算
k
kbkxy
bxky
yxFd
5.0
5.0
)1(5.0
)5.0,1(
00
00
000
21
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。 否则结束 。
5.1.2 中点 Bresenham算法
5.1 直线的扫描转换
22
改进,用 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。
当直线没有画完时,重复步骤 。 否则结束 。
5.1.2 中点 Bresenham算法
5.1 直线的扫描转换
23
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
5.1 直线的扫描转换
24
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
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
25
算法步骤,
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。 否则结束 。
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
26
改进 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
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
27
算法步骤 为：
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。 否则结束 。
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
28
改进 2：用 2e△ x来替换 e
e初 =-△ x，
每走一步有 e=e+2△ y。
if (e>0) then e=e-2△ x
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
29
算法步骤,
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。 否则结束 。
5.1.3 改进的 Bresenham算法
5.1 直线的扫描转换
30
