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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
直线的微分方程：
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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
注意,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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
特点：
增量算法直观,易实现缺点：
浮点运算、取整－－,废时，且不利于硬件实现。
不利于用硬件实现
。
13
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
5.1.2 中点画线法算法原理：
假定直线斜率 K<1，且已确定点亮象素点 P（ Xp,Yp ）
M为中点,Q为交点现需确定下一个点亮的象素 。
显然可得出如下结论：若 M在 Q的下方，选 Pu，否则选 Pd
14
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法算法实现：
假设直线的起点、终点分别为：（ X0,Y0),(X1,Y1)
该直线方程可表示为：
F(x,y)=a*x+b*y+c （ 1）
其中,a=Y0-Y1,b=X1-X0,c=X0*Y1-X1*Y0
当,F(Xt,Yt) = 0 → (Xt,Yt) 在直线上
F(Xt,Yt) < 0 → (Xt,Yt) 在直线下方
F(Xt,Yt) > 0 → (Xt,Yt) 在直线上方
15
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
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
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法因此：将中点 M坐标代入（
1）式，并判断其符号即可确定象素点的选取。构造如下判别式：
d = F(M)
=F(Xp+1,Yp+0.5)
=a(Xp+1)+b(Yp+0.5)+c
由上式可看出,d是 x,y线性函数，可推导 d的增量公式
)0(
)0( 1
dy
dy
y
17
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法当 d < 0 时,取象素 Pu，此时再下一个象素的判别式为：
d’= F(Xp+2,Yp+1.5)
= a(Xp+2)+b(Yp+1.5)+c
= a(Xp+1)+b(Yp+0.5)+c +a +b
= d + a + b;
误差项的递推
d<0：
18
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法当 d>= 0时，取象素 Pd，此时再下一个象素的判别式为：
d’= F(Xp+2,Yp+0.5)
= a(Xp+2)+b(Yp+0.5)+c
= a(Xp+1)+b(Yp+0.5)+c +a
= d + a;
误差项的递推
d≥0：
19
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
d的初始值可按下式计算：
d0 = F(X0+1,Y0+0.5)
= a(X0+1)+b(Y0+0.5)+c
= F(X0,Y0)+a+0.5b
= a+0.5b
由于只用 d 的符号作判断，为了只包含整数运算,
可取 2d代替 d，这样可得如下中点算法程序：
20
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
MidpointLine(X0,Y0,X1,Y1,Color)
int X0,Y0,X1,Y1,Color;
{
int a,b,d1,d2,d,x,y;
a=Y0-Y1; b=X1-X0;
d=a+a+b;
d1=a+a;
d2=a+b+a+b;
x=X0; y=Y0;
drawpixle(x,y,Color);
while(x<X1){
if(d<0){
x++; y++;
d+=d2;
}
21
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
else{
x++;
d += d1;
}
drawpixle(x,y,Color);
}/*while*/
}/*MidPointLine*/
习题：
按照中点划线算法，确定直线（ 0,0）（ 5,3）的点亮象素。列出计算过程，并列出所选象素坐标。
22
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法
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
23
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法假定直线斜率,0<k<1,起点坐标为 (x,y);
下一个点亮象素可能是：
(x+1,y) 或 (x+1,y+1)。这可通过 d值的大小来确定,
d = d+k,当 d>1 时 d=d-1 ;
当 d<0.5取 (x+1,y)，否则取
(x+1,y+1)。
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
24
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法算法步骤：
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。 否则结束 。
25
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法改进 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
26
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法算法步骤为：
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。 否则结束 。
27
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法改进 2,用 2e△ x来替换 e
e初 = -△ x，
每走一步有 e=e+2△ y。
if (e>0) then e=e-2△ x
28
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法算法步骤：
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。 否则结束 。
程序如下,BresenhamLine(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int x,y,dx,dy;
float k,e; int e;
dx = x1-x0;
dy = y1-y0;
k = dy/dx;
e = -0.5; x=x0; y=y0; e = -dx;
for( i=0; i<=dx; i++){
drawpixel(x,y,color);
x++; e=e+k; e1=e-0.5; e=e+2*dy; e1= e-dx;
if(e1 > 0) e = e - 1; e = e - 2*dx;
if(e >=0) y++;
}
}
Bresenham 画线例直线端点为 (20,10)和 （ 30,18),用 Bresenham 法画线解,?x＝ 10,?y ＝ 8,k =?y /?x = 0.8,2?y ＝ 16,2?x ＝ 20
e0 ＝ －?x ＝ － 10
画初始点 (20,10),并根据判别式确定沿线段路径的后续像素位置如下表：
i e’
i
(x
i +1
,y
i +1
)
0 6 (21,1 1)
1 2 (22,12)
2 -2 (23,12)
3 14 (24,13)
4 10 (25,14)
5 6 (26,15)
6 2 (27,16)
7 -2 (28,16)
8 14 (29,17)
9 10 (20,18)
2921 22 23 24 25 2620 2827
10
18
17
16
15
13
14
12
11
19
30
31
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.1 圆的对称性利用八分圆的对称性特点
，可以简化圆的扫描转换算法。
如果圆的圆心在原点，则可以由其中某个八分圆的圆周上的某点（ x,y
）计算出其他七个八分圆圆周上对应的点的坐标。
由此可构造相应算法，由图中阴影的圆周复制生成整个圆周。
32
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.1 圆的对称性算法如下：
int Circle_Points(x,y,value)
int x,y,value;
{ drawpixel(x,y,value);
drawpixel(x,-y,value);
drawpixel(-x,y,value);
drawpixel(-x,-y,value);
drawpixel(y,x,value);
drawpixel(-y,x,value);
drawpixel(y,-x,value);
drawpixel(-y,-x,value);
}
33
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.2 角度 DDA画圆算法
1,角度 DDA法若已知圆的方程：
x = x0 + Rcos?
y = y0 + Rsin?
dx =- Rsin?d?
dy = Rcos?d?
xn+1 =x n + dx
y n+1 =y n + dy
xn+1 =x n - (y n - y 0 )d?
y n+1 =y n + (x n - x 0 )d?
34
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.2 角度 DDA画圆算法角增量?(弧度 )的选取,d?＝?/(n-1)
n越大，点越多，速度越慢。所以在不同的精度下，对于不同的半径给定不同的 d?：
使 max(|Δx|,|Δy|) ≤ 1
因,Δx = - ( yn – y0) d?
Δy = ( xn – x0) d?
即 max(| ( yn – y0) d? |,| ( xn – x0) d?|) ≤ 1
又因为 | yn – y0 |,| xn – x0 | 最大是 R
所以,R| d? | ≤ 1 | d? | ≤ 1/R
绝对值表示画圆弧有顺时针和逆时针之别，
为精度计，取 | d? | ＝ 1/(R+1)
35
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.2 角度 DDA画圆算法算法：
Arc－ dda（ xc,yc,r,a1,a2,color）
int xc,yc,r,color；
double a1,a2；
{ int i,steps,x,y；
double da,radin;
da = 1/(r＋ 1）；
radin ＝ a2 - a1; steps = radin/da;
x = r*cos(a1); y = r * Sin(a1);
for(i = 0;i ≤ steps;i++)
{ drawpixel( x+xc,y+ yc,color );
x = x – y*da ; y = y+ x*da ;
}
}
36
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法利用圆的对称性，只须讨论 1/8圆 (第一象限中的第二个八分圆 )。
解决问题：
y
y = x
图5 - 1 0 1 / 8 圆弧
x
R
37
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法基本原理,假设 P（ Xp+1,Yp）为当前点亮象素，那么，下一个点亮的象素可能是 P1
（ Xp+1,Yp）或 P2（ Xp +1,Yp +1)。
38
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
2)推导过程：
① 构造一函数：
F（ X,Y） =X2 + Y2 - R2
F（ X,Y） = 0 （ X,Y）在圆上；
F（ X,Y） < 0 （ X,Y）在圆内；
F（ X,Y） > 0 （ X,Y）在圆外。
M为 P1,P2间的中点,M=(Xp+1,Yp-0.5)
有如下结论：
F（ M） < 0 取 P1
F（ M） >= 0 取 P2
39
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
② 构造判别式 d = F(M)= F(xp + 1,yp - 0.5)
=(xp + 1)2 + (yp - 0.5) 2 - R2
若 d<0,则 P1 为下一个象素，那么再下一个象素的判别式为：
d = F(xp + 2,yp - 0.5)
= (xp + 2)2 + (yp - 0.5) 2 - R2
= d + 2xp +3
即 d 的增量为 2xp +3.
40
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
③ 计算 d的初值,
d0 = F(1,R-0.5)
= 1 + (R-0.5)2 - R2
= 1.25 - R
若 d>=0,则 P2 为下一个象素，那么再下一个象素的判别式为：
d = F(xp + 2,yp - 1.5)
= (xp + 2)2 + (yp - 1.5) 2 - R2
= d + 2(xp - yp) + 5
即 d 的增量为 2 (xp - yp) +5.
41
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法算法步骤：
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。 否则结束 。
42
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
MidpointCircle(r,color)
int r,color;
{
int x,y;
float d;
x=0; y=r; d=1.25-r;
drawpixel(x,y,color);
while(x<y)
{
if(d<0)
{
d+ = 2*x+3; x++；
}
else
{
d+ = 2*(x-y) + 5;
x++;y--;
}
}
}
43
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法改进 1：用 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。 否则结束 。
令 e＝ d－ 0.25 e＝ 1－ R
则 d < 0 e<－ 0.25
而 e为整数，则 e<－ 0.25等价于 e < 0。再将 e仍用 d来表示
44
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法改进 2,因判别式 d的增量是 x,y的线性函数。
每当 x递增 1,d递增 Δx ＝ 2；
每当 y递增 1,d递减 Δy ＝ 2；
由于初始象素为（ 0,r），所以 Δx 的初值为 3,Δy 的初值为－ 2r＋ 2。再注意到乘 2运算可以改用加法实现，至此我们可写出不含乘法，仅用整数实现的中点画圆算法。
45
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
MidpointCircle(r,color)
int r,color;
{
int x,y,deltax,deltay,d;
x=0; y=r; d=1-r;
deltax=3; deltay=2-r-r;
drawpixel(x,y,color);
while(x<y)
{
if(d<0)
{
d+ = deltax;
deltax+=2; x++；
}
else
{
d+ = (deltax+deltay);
deltax+=2;deltay+=2;
x++; y--;
}
}
}
46
例题,画第一象限中，半径 R＝ 10,圆心在原点的圆弧解,起点为 (x0,y0) ＝ (0,10)
e0 ＝ 1－ R ＝ － 9； (x1,y1)＝ (1,10)
e1 ＝ e0 ＋ 2x0 +3 ＝ － 6； (x2,y2)＝ (2,10)
e2 ＝ e1 ＋ 2x1 +3 ＝ － 1； (x3,y3)＝ (3,10)
e3 ＝ e2 ＋ 2x2 +3 ＝ 6； (x4,y4)＝ (4,9)
e4 ＝ e3 ＋ 2(x3－ y3 ) + 5 ＝－ 3； (x5,y5)＝ (5,9)
e5 ＝ e4 ＋ 2x4 + 3 ＝ 8； (x6,y6)＝ (6,8)
e6 ＝ e5 ＋ 2(x5－ y5 ) + 5 ＝ 5； (x7,y7)＝ (7,7)
91 2 3 4 5 60 87
1
9
8
7
6
4
5
3
2
10
10
若 ei<0,－ > ei＋ 1 ＝ ei + 2xi + 3
ei>=0,－ > ei＋ 1 ＝ ei + 2(xi － yi ) + 5
47
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法
5.2.3,Bresenham画圆算法为讨论方便，仅考虑圆心在原点，半径为 R的第一象限上的一段圆弧。且取（ 0,R） 为起点，按顺时针方向绘制该 1/4圆弧。
48
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法原理,
如图 1-3所示，从当前点亮象素出发，按顺时针方向生成圆时，最佳逼近该圆的下一个象素只可能为 H,D,V三象素之一。 H,D,V中距圆周边界距离最小者，即为所求的象素点。
49
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法算法：
H,D,V三点到圆心的距离平方与圆的半径平方差，即为 H,D,V到圆弧距离的一种度量：
H = (x+1)2 + y2 - R2;
D = (x+1)2 + (y-1)2 - R2;
V = x2 + (y-1)2 - R2;
50
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法为了根据这些度量值可确定最佳象素点，首先，将 H,D,V与理想圆弧的关系进行分类。
存在以下五种情况：
1） H,D,V全在圆内；
2） H在圆外,D,V在圆内；
3） D在圆上,H在圆外,V在圆内；
4） H,D在圆外,V在圆内；
5） H,D,V全在圆外。
与 Bresenham画线算法一样，按照上述不同类型
，找出误差度量的递推公式，然后判别它的正、
负性即可确定最佳逼近的象素点。
51
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法当?D < 0,只可能为 1或 2种情况。为了确定是 H
还是 D，可用如下判别式：
δHD = |?H | - |?D |
δHD ≤ 0 则应选 H，否则选 D。
52
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法对于第 2种情况：
δHD =?H +?D
= (x+1)2 + y2 - R2 + (x+1)2 + (y-1)2 - R2
=2?D + 2y - 1
对于第 1种情况：
∵ y是 x的单调递减函数
∴ H为下一点亮象素。
另，此时?H < 0 和?D < 0
H +?D = 2?D + 2y - 1 < 0
综上两种情况可得如下结论：
在?D＜ 0时，若 2（?D +y) - 1 ≤0，则取 H，
否则取 D
53
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法当?D ＞ 0,只可能有 4,5两种情况。且最佳象素点为 D或 V，可用如下判别式：
δDV = |?D |- |?V |
δDV ≤ 0 则应选 D，否则选 V。
对于第 4种情况：
δDV =?D +?V （?D ＞ 0,?V＜ 0）
= (x+1)2 + (y-1)2 - R2 + (x)2 + (y-1)2 - R2
= 2(?D - x) - 1
对于第 5种情况：
D,V都在圆外，显然 V为所选象素。
注意,∵?D ＞ 0,?V＞ 0
∴?D +?V = 2(?D - x) - 1 ＞ 0
54
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法综上两种情况可得如下结论：
在?D＞ 0时，若 2（?D -x) - 1 ≤0，则取 D，
否则取 V
当?D = 0 此时 D是最佳象素 。
总结上述分析结果：
当?D ＞ 0,若 2(?D - x) - 1 ＞ 0，取 V，否则取 D
当?D ＜ 0，若 2 (?D +y) - 1 ≤0，取 H，否则取 D
当?D = 0,取 D。
55
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法关键的问题就是计算? D （ 见? D的计算公式 ）
采用增量法，获得?D的计算公式。
分三种情况：
下一象素为 H时,则
H=(x’,y’)=(x+1,y)
D ’=((x+1)+1)2 +(y-1)2 - R2
=(x+1)2 + (y-1)2 -R2 + 2(x+1) + 1
=?D +2(x+1) + 1
=?D +2 x’ + 1
56
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法下一象素为 D时
D=(x’,y’)=(x+1,y-1)
D=((x+1)+1)2 +((y-1)-1)2 - R2
=(x+1)2 + (y-1)2 -R2 + 2(x+1) - 2(y-1) + 1
=?D +2(x+1) - 2(y-1) + 2
下一象素为 V时
V=(x’,y’)=(x,y-1)
D=(x+1)2 +((y-1)-1)2 - R2
=(x+1)2 + (y-1)2 -R2 - 2(y-1) + 1
=?D - 2(y-1) + 1
57
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法有了上述?D的递推计算公式，还需计算出?D的初值。
∵ 圆弧的起点为（ 0,R）
∴?D的初值为：
D = (0+1)2 +(R-1)2-R2
= 2 (1-R)
BresenhamCircle(r,color)
int r,color;
{
int x,y,delta,d1,d2,dir
x=0; y=r;
delta = 2*(1-r)
while(y>=0){
drawpixel(x,y,color);
if(delta < 0){
d1 = 2* (delta + y) -1;
if(d1 <=0) dir = 1;
else dir = 2;
}
else if( delta > 0){
d2 = 2*(delta-x)-1;
if(d2 <= 0) dir = 2;
else dir = 3;
}
else dir = 2;
switch(dir){
case 1:
x++;
delta+=2*x + 1;
break;
case 2:
x++; Y--;
delta+=2*(x-y+1) + 1;
break;
case 3:
y--;
delta+=-2*y + 1;
break;
}/*end of switch*/
}/*end of while*/
}/*end of BresenhamCircle*/
60
第五章 基本图形生成算法
5.3 椭圆的扫描转换
b
a x
y
图5 - 1 4 长半轴为a,短半轴为b 的标准椭圆
( x,y )
( x,- y )( - x,- y )
( - x,y )
0),( 222222 bayaxbyxF
对于椭圆上的点，有 F(x,y)=0；
对于椭圆外的点,F(x,y)>0；
对于椭圆内的点,F(x,y)<0。
61
第五章 基本图形生成算法
5.3 椭圆的扫描转换解决问题,y
x
( x,y )
y
y = - x y = x
y
y =x
图5-10 1/8圆弧
x
R
62
第五章 基本图形生成算法
5.3 椭圆的扫描转换上半部分下半部分二分量相等的法向量图5- 15 第一象限的椭圆弧
y
x
法向量
yjaxibjyFixFyxN 22 22),(
y分量 > x分量
y分量 < x分量
y分量 = x分量
0),( 222222 bayaxbyxF
椭圆方程分界点：法向量两分量相等的点，以弧上斜率为－ 1的点
63
第五章 基本图形生成算法
5.3 椭圆的扫描转换引理 5-1：若在当前中点，法向量的 y分量比 x分量大，即
)5.0()1( 22 ii yaxb
而在下一个中点,不等号改变方向,则说明椭圆弧从上部分转入下部分 。
当前点 P(xi,yi)
候选点 Pu(xi+1,yi)
Pd(xi+1,yi-1)
中 点 (xi+1,yi-0.5)
上半部分下半部分二分量相等的法向量图5- 15 第一象限的椭圆弧
y
x
64
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法
5.3.1 椭圆的中点 Bresenham算法先推导上半部分的椭圆绘制公式再推导下半部分的椭圆绘制公式
65
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法先推导上半部分的椭圆绘制公式判别式 误差项的递推 判别式的初值
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 上半部分椭圆弧的绘制原理
66
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法判别式
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 上半部分椭圆弧的绘制原理
67
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
( 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
2222221 )5.0()1()5.0,1( bayaxbyxFd iiii
情况一：
d1≤0,
68
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
)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
2222221 )5.0()1()5.0,1( bayaxbyxFd iiii
情况二：
d1>0：
69
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法上半部判别式的初始值：
)25.0(
)5.0()5.0,1(
22
22222
10
bab
bababbFd
初始点 （ 0,b）
候选点 （ 1,b-1） （ 1,b）
中 点 （ 1,b-0.5）
70
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法再来推导椭圆弧下半部分的绘制公式判别式 误差项的递推 判别式的初值
71
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法判别式
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii
若 d2>0,取 Pl(xi,yi-1)
若 d2≤ 0,取 Pr(xi+1,yi-1)
72
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
)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
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii
第一种情况：
d2>0：
73
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
)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
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii
第二种情况：
d2≤0,
74
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法注意：
上半部分的终止判别下半部分误差项的初值
75
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法算法步骤：
1.输入椭圆的长半轴 a和短半轴 b。
2.计算初始值 d=b2+a2(-b+0.25),x=0,y=b。
3.绘制点 (x,y)及其在四分象限上的另外三个对称点。
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。
76
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法
6.用上半部分计算的最后点 (x,y)来计算下半部分中 d的初值
：
222222 )1()5.0( bayaxbd
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。 否则结束 。
MidpointEllipse (a,b,color)
int a,b,color;
{
int x,y；
float d1,d2；
x=0; y=b;
d1＝ b*b+a*(-b+0.25);
drawpixel(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--;
}
drawpixel(x,y,color);
}
d2＝ sqr(b*(x+5)+a*(y-1)-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--;
}
drawpixel(x,y,color);
}
}
79习题
1,将中点画线方法推广，使之能画出任意斜率的直线
2,用 DDA法，中点画线法和 Bresenham 算法画从 (0,0)到 (-10,-5)
间的直线段
3.写一个利用 BRESENHAM算法，画 任意斜率 的直线段的程序。
4,编写按逆时针方向生成中心在原点的第一个 8分圆的中点画圆算法，导出递 推公式
5,推导用中点画圆算法画中心在原点的第一象限椭圆弧的递推算法
余 敦 辉湖北大学 数计学院计算机图形学
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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
直线的微分方程：
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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
注意,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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
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 直线的扫描转换
5.1.1 数值微分法 (DDA法 )
特点：
增量算法直观,易实现缺点：
浮点运算、取整－－,废时，且不利于硬件实现。
不利于用硬件实现
。
13
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
5.1.2 中点画线法算法原理：
假定直线斜率 K<1，且已确定点亮象素点 P（ Xp,Yp ）
M为中点,Q为交点现需确定下一个点亮的象素 。
显然可得出如下结论：若 M在 Q的下方，选 Pu，否则选 Pd
14
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法算法实现：
假设直线的起点、终点分别为：（ X0,Y0),(X1,Y1)
该直线方程可表示为：
F(x,y)=a*x+b*y+c （ 1）
其中,a=Y0-Y1,b=X1-X0,c=X0*Y1-X1*Y0
当,F(Xt,Yt) = 0 → (Xt,Yt) 在直线上
F(Xt,Yt) < 0 → (Xt,Yt) 在直线下方
F(Xt,Yt) > 0 → (Xt,Yt) 在直线上方
15
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
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
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法因此：将中点 M坐标代入（
1）式，并判断其符号即可确定象素点的选取。构造如下判别式：
d = F(M)
=F(Xp+1,Yp+0.5)
=a(Xp+1)+b(Yp+0.5)+c
由上式可看出,d是 x,y线性函数，可推导 d的增量公式
)0(
)0( 1
dy
dy
y
17
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法当 d < 0 时,取象素 Pu，此时再下一个象素的判别式为：
d’= F(Xp+2,Yp+1.5)
= a(Xp+2)+b(Yp+1.5)+c
= a(Xp+1)+b(Yp+0.5)+c +a +b
= d + a + b;
误差项的递推
d<0：
18
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法当 d>= 0时，取象素 Pd，此时再下一个象素的判别式为：
d’= F(Xp+2,Yp+0.5)
= a(Xp+2)+b(Yp+0.5)+c
= a(Xp+1)+b(Yp+0.5)+c +a
= d + a;
误差项的递推
d≥0：
19
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
d的初始值可按下式计算：
d0 = F(X0+1,Y0+0.5)
= a(X0+1)+b(Y0+0.5)+c
= F(X0,Y0)+a+0.5b
= a+0.5b
由于只用 d 的符号作判断，为了只包含整数运算,
可取 2d代替 d，这样可得如下中点算法程序：
20
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
MidpointLine(X0,Y0,X1,Y1,Color)
int X0,Y0,X1,Y1,Color;
{
int a,b,d1,d2,d,x,y;
a=Y0-Y1; b=X1-X0;
d=a+a+b;
d1=a+a;
d2=a+b+a+b;
x=X0; y=Y0;
drawpixle(x,y,Color);
while(x<X1){
if(d<0){
x++; y++;
d+=d2;
}
21
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.2 中点画线法算法
else{
x++;
d += d1;
}
drawpixle(x,y,Color);
}/*while*/
}/*MidPointLine*/
习题：
按照中点划线算法，确定直线（ 0,0）（ 5,3）的点亮象素。列出计算过程，并列出所选象素坐标。
22
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法
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
23
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法假定直线斜率,0<k<1,起点坐标为 (x,y);
下一个点亮象素可能是：
(x+1,y) 或 (x+1,y+1)。这可通过 d值的大小来确定,
d = d+k,当 d>1 时 d=d-1 ;
当 d<0.5取 (x+1,y)，否则取
(x+1,y+1)。
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
24
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法算法步骤：
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。 否则结束 。
25
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法改进 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
26
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法算法步骤为：
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。 否则结束 。
27
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法改进 2,用 2e△ x来替换 e
e初 = -△ x，
每走一步有 e=e+2△ y。
if (e>0) then e=e-2△ x
28
第五章 基本图形生成算法
5.1 直线的扫描转换
5.1.3 Bresenham画线算法算法步骤：
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。 否则结束 。
程序如下,BresenhamLine(x0,y0,x1,y1,color)
int x0,y0,x1,y1,color;
{
int x,y,dx,dy;
float k,e; int e;
dx = x1-x0;
dy = y1-y0;
k = dy/dx;
e = -0.5; x=x0; y=y0; e = -dx;
for( i=0; i<=dx; i++){
drawpixel(x,y,color);
x++; e=e+k; e1=e-0.5; e=e+2*dy; e1= e-dx;
if(e1 > 0) e = e - 1; e = e - 2*dx;
if(e >=0) y++;
}
}
Bresenham 画线例直线端点为 (20,10)和 （ 30,18),用 Bresenham 法画线解,?x＝ 10,?y ＝ 8,k =?y /?x = 0.8,2?y ＝ 16,2?x ＝ 20
e0 ＝ －?x ＝ － 10
画初始点 (20,10),并根据判别式确定沿线段路径的后续像素位置如下表：
i e’
i
(x
i +1
,y
i +1
)
0 6 (21,1 1)
1 2 (22,12)
2 -2 (23,12)
3 14 (24,13)
4 10 (25,14)
5 6 (26,15)
6 2 (27,16)
7 -2 (28,16)
8 14 (29,17)
9 10 (20,18)
2921 22 23 24 25 2620 2827
10
18
17
16
15
13
14
12
11
19
30
31
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.1 圆的对称性利用八分圆的对称性特点
，可以简化圆的扫描转换算法。
如果圆的圆心在原点，则可以由其中某个八分圆的圆周上的某点（ x,y
）计算出其他七个八分圆圆周上对应的点的坐标。
由此可构造相应算法，由图中阴影的圆周复制生成整个圆周。
32
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.1 圆的对称性算法如下：
int Circle_Points(x,y,value)
int x,y,value;
{ drawpixel(x,y,value);
drawpixel(x,-y,value);
drawpixel(-x,y,value);
drawpixel(-x,-y,value);
drawpixel(y,x,value);
drawpixel(-y,x,value);
drawpixel(y,-x,value);
drawpixel(-y,-x,value);
}
33
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.2 角度 DDA画圆算法
1,角度 DDA法若已知圆的方程：
x = x0 + Rcos?
y = y0 + Rsin?
dx =- Rsin?d?
dy = Rcos?d?
xn+1 =x n + dx
y n+1 =y n + dy
xn+1 =x n - (y n - y 0 )d?
y n+1 =y n + (x n - x 0 )d?
34
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.2 角度 DDA画圆算法角增量?(弧度 )的选取,d?＝?/(n-1)
n越大，点越多，速度越慢。所以在不同的精度下，对于不同的半径给定不同的 d?：
使 max(|Δx|,|Δy|) ≤ 1
因,Δx = - ( yn – y0) d?
Δy = ( xn – x0) d?
即 max(| ( yn – y0) d? |,| ( xn – x0) d?|) ≤ 1
又因为 | yn – y0 |,| xn – x0 | 最大是 R
所以,R| d? | ≤ 1 | d? | ≤ 1/R
绝对值表示画圆弧有顺时针和逆时针之别，
为精度计，取 | d? | ＝ 1/(R+1)
35
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.2 角度 DDA画圆算法算法：
Arc－ dda（ xc,yc,r,a1,a2,color）
int xc,yc,r,color；
double a1,a2；
{ int i,steps,x,y；
double da,radin;
da = 1/(r＋ 1）；
radin ＝ a2 - a1; steps = radin/da;
x = r*cos(a1); y = r * Sin(a1);
for(i = 0;i ≤ steps;i++)
{ drawpixel( x+xc,y+ yc,color );
x = x – y*da ; y = y+ x*da ;
}
}
36
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法利用圆的对称性，只须讨论 1/8圆 (第一象限中的第二个八分圆 )。
解决问题：
y
y = x
图5 - 1 0 1 / 8 圆弧
x
R
37
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法基本原理,假设 P（ Xp+1,Yp）为当前点亮象素，那么，下一个点亮的象素可能是 P1
（ Xp+1,Yp）或 P2（ Xp +1,Yp +1)。
38
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
2)推导过程：
① 构造一函数：
F（ X,Y） =X2 + Y2 - R2
F（ X,Y） = 0 （ X,Y）在圆上；
F（ X,Y） < 0 （ X,Y）在圆内；
F（ X,Y） > 0 （ X,Y）在圆外。
M为 P1,P2间的中点,M=(Xp+1,Yp-0.5)
有如下结论：
F（ M） < 0 取 P1
F（ M） >= 0 取 P2
39
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
② 构造判别式 d = F(M)= F(xp + 1,yp - 0.5)
=(xp + 1)2 + (yp - 0.5) 2 - R2
若 d<0,则 P1 为下一个象素，那么再下一个象素的判别式为：
d = F(xp + 2,yp - 0.5)
= (xp + 2)2 + (yp - 0.5) 2 - R2
= d + 2xp +3
即 d 的增量为 2xp +3.
40
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
③ 计算 d的初值,
d0 = F(1,R-0.5)
= 1 + (R-0.5)2 - R2
= 1.25 - R
若 d>=0,则 P2 为下一个象素，那么再下一个象素的判别式为：
d = F(xp + 2,yp - 1.5)
= (xp + 2)2 + (yp - 1.5) 2 - R2
= d + 2(xp - yp) + 5
即 d 的增量为 2 (xp - yp) +5.
41
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法算法步骤：
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。 否则结束 。
42
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
MidpointCircle(r,color)
int r,color;
{
int x,y;
float d;
x=0; y=r; d=1.25-r;
drawpixel(x,y,color);
while(x<y)
{
if(d<0)
{
d+ = 2*x+3; x++；
}
else
{
d+ = 2*(x-y) + 5;
x++;y--;
}
}
}
43
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法改进 1：用 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。 否则结束 。
令 e＝ d－ 0.25 e＝ 1－ R
则 d < 0 e<－ 0.25
而 e为整数，则 e<－ 0.25等价于 e < 0。再将 e仍用 d来表示
44
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法改进 2,因判别式 d的增量是 x,y的线性函数。
每当 x递增 1,d递增 Δx ＝ 2；
每当 y递增 1,d递减 Δy ＝ 2；
由于初始象素为（ 0,r），所以 Δx 的初值为 3,Δy 的初值为－ 2r＋ 2。再注意到乘 2运算可以改用加法实现，至此我们可写出不含乘法，仅用整数实现的中点画圆算法。
45
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 中点 画圆法
MidpointCircle(r,color)
int r,color;
{
int x,y,deltax,deltay,d;
x=0; y=r; d=1-r;
deltax=3; deltay=2-r-r;
drawpixel(x,y,color);
while(x<y)
{
if(d<0)
{
d+ = deltax;
deltax+=2; x++；
}
else
{
d+ = (deltax+deltay);
deltax+=2;deltay+=2;
x++; y--;
}
}
}
46
例题,画第一象限中，半径 R＝ 10,圆心在原点的圆弧解,起点为 (x0,y0) ＝ (0,10)
e0 ＝ 1－ R ＝ － 9； (x1,y1)＝ (1,10)
e1 ＝ e0 ＋ 2x0 +3 ＝ － 6； (x2,y2)＝ (2,10)
e2 ＝ e1 ＋ 2x1 +3 ＝ － 1； (x3,y3)＝ (3,10)
e3 ＝ e2 ＋ 2x2 +3 ＝ 6； (x4,y4)＝ (4,9)
e4 ＝ e3 ＋ 2(x3－ y3 ) + 5 ＝－ 3； (x5,y5)＝ (5,9)
e5 ＝ e4 ＋ 2x4 + 3 ＝ 8； (x6,y6)＝ (6,8)
e6 ＝ e5 ＋ 2(x5－ y5 ) + 5 ＝ 5； (x7,y7)＝ (7,7)
91 2 3 4 5 60 87
1
9
8
7
6
4
5
3
2
10
10
若 ei<0,－ > ei＋ 1 ＝ ei + 2xi + 3
ei>=0,－ > ei＋ 1 ＝ ei + 2(xi － yi ) + 5
47
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法
5.2.3,Bresenham画圆算法为讨论方便，仅考虑圆心在原点，半径为 R的第一象限上的一段圆弧。且取（ 0,R） 为起点，按顺时针方向绘制该 1/4圆弧。
48
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法原理,
如图 1-3所示，从当前点亮象素出发，按顺时针方向生成圆时，最佳逼近该圆的下一个象素只可能为 H,D,V三象素之一。 H,D,V中距圆周边界距离最小者，即为所求的象素点。
49
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法算法：
H,D,V三点到圆心的距离平方与圆的半径平方差，即为 H,D,V到圆弧距离的一种度量：
H = (x+1)2 + y2 - R2;
D = (x+1)2 + (y-1)2 - R2;
V = x2 + (y-1)2 - R2;
50
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法为了根据这些度量值可确定最佳象素点，首先，将 H,D,V与理想圆弧的关系进行分类。
存在以下五种情况：
1） H,D,V全在圆内；
2） H在圆外,D,V在圆内；
3） D在圆上,H在圆外,V在圆内；
4） H,D在圆外,V在圆内；
5） H,D,V全在圆外。
与 Bresenham画线算法一样，按照上述不同类型
，找出误差度量的递推公式，然后判别它的正、
负性即可确定最佳逼近的象素点。
51
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法当?D < 0,只可能为 1或 2种情况。为了确定是 H
还是 D，可用如下判别式：
δHD = |?H | - |?D |
δHD ≤ 0 则应选 H，否则选 D。
52
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法对于第 2种情况：
δHD =?H +?D
= (x+1)2 + y2 - R2 + (x+1)2 + (y-1)2 - R2
=2?D + 2y - 1
对于第 1种情况：
∵ y是 x的单调递减函数
∴ H为下一点亮象素。
另，此时?H < 0 和?D < 0
H +?D = 2?D + 2y - 1 < 0
综上两种情况可得如下结论：
在?D＜ 0时，若 2（?D +y) - 1 ≤0，则取 H，
否则取 D
53
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法当?D ＞ 0,只可能有 4,5两种情况。且最佳象素点为 D或 V，可用如下判别式：
δDV = |?D |- |?V |
δDV ≤ 0 则应选 D，否则选 V。
对于第 4种情况：
δDV =?D +?V （?D ＞ 0,?V＜ 0）
= (x+1)2 + (y-1)2 - R2 + (x)2 + (y-1)2 - R2
= 2(?D - x) - 1
对于第 5种情况：
D,V都在圆外，显然 V为所选象素。
注意,∵?D ＞ 0,?V＞ 0
∴?D +?V = 2(?D - x) - 1 ＞ 0
54
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法综上两种情况可得如下结论：
在?D＞ 0时，若 2（?D -x) - 1 ≤0，则取 D，
否则取 V
当?D = 0 此时 D是最佳象素 。
总结上述分析结果：
当?D ＞ 0,若 2(?D - x) - 1 ＞ 0，取 V，否则取 D
当?D ＜ 0，若 2 (?D +y) - 1 ≤0，取 H，否则取 D
当?D = 0,取 D。
55
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法关键的问题就是计算? D （ 见? D的计算公式 ）
采用增量法，获得?D的计算公式。
分三种情况：
下一象素为 H时,则
H=(x’,y’)=(x+1,y)
D ’=((x+1)+1)2 +(y-1)2 - R2
=(x+1)2 + (y-1)2 -R2 + 2(x+1) + 1
=?D +2(x+1) + 1
=?D +2 x’ + 1
56
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法下一象素为 D时
D=(x’,y’)=(x+1,y-1)
D=((x+1)+1)2 +((y-1)-1)2 - R2
=(x+1)2 + (y-1)2 -R2 + 2(x+1) - 2(y-1) + 1
=?D +2(x+1) - 2(y-1) + 2
下一象素为 V时
V=(x’,y’)=(x,y-1)
D=(x+1)2 +((y-1)-1)2 - R2
=(x+1)2 + (y-1)2 -R2 - 2(y-1) + 1
=?D - 2(y-1) + 1
57
第五章 基本图形生成算法
5.2 圆的扫描转换
5.2.3 Bresenham画圆法有了上述?D的递推计算公式，还需计算出?D的初值。
∵ 圆弧的起点为（ 0,R）
∴?D的初值为：
D = (0+1)2 +(R-1)2-R2
= 2 (1-R)
BresenhamCircle(r,color)
int r,color;
{
int x,y,delta,d1,d2,dir
x=0; y=r;
delta = 2*(1-r)
while(y>=0){
drawpixel(x,y,color);
if(delta < 0){
d1 = 2* (delta + y) -1;
if(d1 <=0) dir = 1;
else dir = 2;
}
else if( delta > 0){
d2 = 2*(delta-x)-1;
if(d2 <= 0) dir = 2;
else dir = 3;
}
else dir = 2;
switch(dir){
case 1:
x++;
delta+=2*x + 1;
break;
case 2:
x++; Y--;
delta+=2*(x-y+1) + 1;
break;
case 3:
y--;
delta+=-2*y + 1;
break;
}/*end of switch*/
}/*end of while*/
}/*end of BresenhamCircle*/
60
第五章 基本图形生成算法
5.3 椭圆的扫描转换
b
a x
y
图5 - 1 4 长半轴为a,短半轴为b 的标准椭圆
( x,y )
( x,- y )( - x,- y )
( - x,y )
0),( 222222 bayaxbyxF
对于椭圆上的点，有 F(x,y)=0；
对于椭圆外的点,F(x,y)>0；
对于椭圆内的点,F(x,y)<0。
61
第五章 基本图形生成算法
5.3 椭圆的扫描转换解决问题,y
x
( x,y )
y
y = - x y = x
y
y =x
图5-10 1/8圆弧
x
R
62
第五章 基本图形生成算法
5.3 椭圆的扫描转换上半部分下半部分二分量相等的法向量图5- 15 第一象限的椭圆弧
y
x
法向量
yjaxibjyFixFyxN 22 22),(
y分量 > x分量
y分量 < x分量
y分量 = x分量
0),( 222222 bayaxbyxF
椭圆方程分界点：法向量两分量相等的点，以弧上斜率为－ 1的点
63
第五章 基本图形生成算法
5.3 椭圆的扫描转换引理 5-1：若在当前中点，法向量的 y分量比 x分量大，即
)5.0()1( 22 ii yaxb
而在下一个中点,不等号改变方向,则说明椭圆弧从上部分转入下部分 。
当前点 P(xi,yi)
候选点 Pu(xi+1,yi)
Pd(xi+1,yi-1)
中 点 (xi+1,yi-0.5)
上半部分下半部分二分量相等的法向量图5- 15 第一象限的椭圆弧
y
x
64
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法
5.3.1 椭圆的中点 Bresenham算法先推导上半部分的椭圆绘制公式再推导下半部分的椭圆绘制公式
65
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法先推导上半部分的椭圆绘制公式判别式 误差项的递推 判别式的初值
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 上半部分椭圆弧的绘制原理
66
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法判别式
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 上半部分椭圆弧的绘制原理
67
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
( 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
2222221 )5.0()1()5.0,1( bayaxbyxFd iiii
情况一：
d1≤0,
68
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
)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
2222221 )5.0()1()5.0,1( bayaxbyxFd iiii
情况二：
d1>0：
69
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法上半部判别式的初始值：
)25.0(
)5.0()5.0,1(
22
22222
10
bab
bababbFd
初始点 （ 0,b）
候选点 （ 1,b-1） （ 1,b）
中 点 （ 1,b-0.5）
70
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法再来推导椭圆弧下半部分的绘制公式判别式 误差项的递推 判别式的初值
71
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法判别式
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii
若 d2>0,取 Pl(xi,yi-1)
若 d2≤ 0,取 Pr(xi+1,yi-1)
72
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
)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
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii
第一种情况：
d2>0：
73
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法误差项的递推
)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
2222222 )1()5.0()1,5.0( bayaxbyxFd iiii
第二种情况：
d2≤0,
74
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法注意：
上半部分的终止判别下半部分误差项的初值
75
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法算法步骤：
1.输入椭圆的长半轴 a和短半轴 b。
2.计算初始值 d=b2+a2(-b+0.25),x=0,y=b。
3.绘制点 (x,y)及其在四分象限上的另外三个对称点。
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。
76
第五章 基本图形生成算法
5.3 椭圆的扫描转换
5.3.1 椭圆的中点 Bresenham算法
6.用上半部分计算的最后点 (x,y)来计算下半部分中 d的初值
：
222222 )1()5.0( bayaxbd
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。 否则结束 。
MidpointEllipse (a,b,color)
int a,b,color;
{
int x,y；
float d1,d2；
x=0; y=b;
d1＝ b*b+a*(-b+0.25);
drawpixel(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--;
}
drawpixel(x,y,color);
}
d2＝ sqr(b*(x+5)+a*(y-1)-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--;
}
drawpixel(x,y,color);
}
}
79习题
1,将中点画线方法推广，使之能画出任意斜率的直线
2,用 DDA法，中点画线法和 Bresenham 算法画从 (0,0)到 (-10,-5)
间的直线段
3.写一个利用 BRESENHAM算法，画 任意斜率 的直线段的程序。
4,编写按逆时针方向生成中心在原点的第一个 8分圆的中点画圆算法，导出递 推公式
5,推导用中点画圆算法画中心在原点的第一象限椭圆弧的递推算法
