浙江大学信息学院 计算机图形学第三章 直线、圆、椭圆生成算法图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：
1、确定有关像素
2、用图形的颜色或其它属性，对像素进行写操作。
对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。
任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。
浙江大学信息学院 计算机图形学图形显示前需要：扫描转换 +裁剪
●裁剪 ---〉 扫描转换：最常用，节约计算时间。
●扫描转换 ---〉 裁剪：算法简单；
浙江大学信息学院 计算机图形学本章内容
？扫描转换直线段
DDA算法中点画线法
Bresenham画线算法
？圆弧、椭圆弧扫描转换中点算法内接正多边形迫近法等面积正多边形逼近法生成圆弧的正负法浙江大学信息学院 计算机图形学直线段的扫描转换算法
直线的扫描转换,确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。
三个常用算法：
数值微分法（ DDA）
中点画线法
Bresenham算法。
浙江大学信息学院 计算机图形学数值微分法（ＤＤＡ）
假定直线的起点、终点分别为：（ x0,y0),
(x1,y1)，且都为整数。
(X i+1,Yi + k)
(X i,Int(Yi +0.5))
(X i,Yi) 栅格交点表示象素点位置
。
。 。
。
浙江大学信息学院 计算机图形学数值微分 (DDA)法
基本思想已知过端点 P0 (x0,y0),P1(x1,y1)的直线段 L
y=kx+b
直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。
01
01
xx
yyk
)(,;
10
yr o u n dx
bkxy
s te p xxxxxx
令浙江大学信息学院 计算机图形学数值微分 (DDA)法计算 yi+1= kxi+1+b
= kxi+b+k?x
= yi+k?x
当?x =1; yi+1 = yi+k
即：当 x每递增 1,y递增 k(即直线斜率 )；
注意上述分析的算法仅适用于?k? ≤ 1的情形。
在这种情况下,x每增加 1,y最多增加 1。
当?k1时，必须把 x,y地位互换浙江大学信息学院 计算机图形学数值微分 (DDA)法
增量算法：在一个迭代算法中，如果每一步的 x,y值是用前一步的值加上一个增量来获得，则称为增量算法。
DDA算法就是一个增量算法。
浙江大学信息学院 计算机图形学数值微分 (DDA)法
void DDALine(int x0,int y0,int x1,int y1,int color)
int x；
float dx,dy,y,k;
dx = x1-x0; dy=y1-y0;
k=dy/dx; y=y0;
for (x=x0; x?x1,x++)
drawpixel (x,int(y+0.5),color);
y=y+k;
浙江大学信息学院 计算机图形学数值微分 (DDA)法
例：画直线段 P0(0,0)--P1(5,2)
x int(y+0.5) y+0.5
0 0 0+0.5
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
5 2 2.0+0.5
0 1 2 3 4 5
3
2
1
Line,P0(0,0)-- P1(5,2)
浙江大学信息学院 计算机图形学数值微分 (DDA)法
缺点,在此算法中,y,k必须是 float，且每一步都必须对 y进行舍入取整，不利于硬件实现。
浙江大学信息学院 计算机图形学中点画线法
原理：
假定直线斜率 0<K<1，且已确定点亮象素点 P（ Xp,Yp ）,
则下一个与直线最接近的像素只能是 P1点或 P2点。设 M
为中点,Q为交点现需确定下一个点亮的象素。
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法
– 当 M在 Q的下方 -> P2离直线更近更近 ->取 P2 。
– M在 Q的上方 -> P1离直线更近更近 ->取 P1
– M与 Q重合,P1,P2任取一点。
– 问题：如何判断 M与 Q点的关系？
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法假设直线方程为,ax+by+c=0
其中 a=y0-y1,b=x1-x0,c=x0y1-x1y0
由常识知：
∴ 欲判断 M点是在 Q点上方还是在 Q点下方,
只需把 M代入 F(x,y),并检查它的符号 。
点在直线下方点在直线上方点在直线上面
0,
0,
0,
yxF
yxF
yxF
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法构造判别式：
d=F(M)=F(xp+1,yp+0.5)
=a(xp+1)+b(yp+0.5)+c
当 d<0,M在直线 (Q点 )下方，取右上方 P2；
当 d>0,M在直线 (Q点 )上方，取右方 P1；
当 d=0，选 P1或 P2均可，
约定取 P1；
能否采用增量算法呢？
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法若 d?0->M在直线上方 ->取 P1;
此时再下一个象素的判别式为
d1=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；
增量为 a
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法
若 d<0->M在直线下方 ->取 P2;
此时再下一个象素的判别式为
d2= 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 ；
增量为 a＋ b
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法
画线从 (x0,y0)开始,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来摆脱小数，提高效率。
浙江大学信息学院 计算机图形学中点画线法
void Midpoint Line (int x0,int y0,int x1,int y1,int color)
{ int a,b,d1,d2,d,x,y;
a=y0-y1,b=x1-x0,d=2*a+b;
d1=2*a,d2=2* (a+b);
x=x0,y=y0;
drawpixel(x,y,color);
while (x<x1)
{ if (d<0) {x++; y++; d+=d2; }
else {x++; d+=d1;}
drawpixel (x,y,color);
} /* while */
} /* mid PointLine */
浙江大学信息学院 计算机图形学中点画线法
例：用中点画线法 P0(0,0) P1(5,2)
a=y0-y1=-2 b=x1-x0=5
d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6
i xi yi d
1 0 0 1
2 1 0 -3
3 2 1 3
4 3 1 -1
5 4 2 5
0 1 2 3 4 5
3
2
1
浙江大学信息学院 计算机图形学
Bresenham画线算法在直线生成的算法中 Bresenham算法是最有效的算法之一。令 k=Δy/Δx,就
0≤k≤1 的情况来说明 Bresenham算法。
由 DDA算法可知：
yi+1=yi+k (1)
由于 k不一定是整数，由此式求出的 yi也不一定是整数，因此要用坐标为（ xi,yir）
的象素来表示直线上的点，其中 yir表示最靠近 yi的整数。
浙江大学信息学院 计算机图形学
Bresenham画线算法设图中 xi列上已用（ xi,yir）作为表示直线的点，
又设 B点是直线上的点，其坐标为（ xi+1,yi+1），显然下一个表示直线的点（ xi+1,yi+1,r）只能从图中的 C
或者 D点中去选。设 A为 CD边的中点。 若 B在 A点上面则应取 D点作为（ xi+1,yi+1,r），否则应取 C点。
xi Xi+1
Yi,r
Yi+1,r
C
D
BA
ε(x) 的几何意义为能确定 B在 A点上面或下面，令
ε(x i+1)=yi+1-yir-0.5 (2)
若 B在 A的下面，则有 ε(x i+1)<0，反之，
则 ε(x i+1)>0。由图可知
yi+1,r=yir+1，若 ε(x i+1)≥0 (3)
yi+1,r=yir,若 ε(x i+1)≤0
浙江大学信息学院 计算机图形学
Bresenham画线算法由式（ 2）和式（ 3）可得到
ε(x i+2)=yi+2 - yi+1,r - 0.5
=yi+1 + k - yi+1,r - 0.5 （ 4）
yi+1 - yir -0.5 + k - 1,当 ε(x i+1)≥0
yi+1 - yir -0.5 + k,当 ε(x i+1)≤0
ε(x i+2)= ε(x i+1) + k -1,当 ε(x i+1)≥0
ε(x i+2)= ε(x i+1) + k,当 ε(x i+1)≤0
由式（ 1）和式（ 2）可得到
ε(x 2)= k - 0.5 (5)
浙江大学信息学院 计算机图形学程序如下,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画线算法浙江大学信息学院 计算机图形学圆的扫描转换算法下面仅以圆心在原点、半径 R为整数的圆为例，讨论圆的生成算法。
假设圆的方程为：
X2 + Y2 = R2
浙江大学信息学院 计算机图形学圆弧扫描算法
X2 + Y2 = R2
Y =?Sqrt(R2 - X2)
在一定范围内，每给定一
X值，可得一 Y值。
当 X取整数时,Y须取整。
缺点：浮点运算，开方，
取整，不均匀。
y
x
浙江大学信息学院 计算机图形学角度 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 + dx = x n - Rsin?d? =x n - (y n - y 0 )d?
y n+1 = y n + dy = y n + Rcos?d? =y n + (x n - x 0 )d?
显然，确定 x,y的初值及 d?值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。
但要采用浮点运算、乘法运算、取整运算。
浙江大学信息学院 计算机图形学中点画圆法利用圆的对称性，只须讨论 1/8圆。第二个 8分圆
P为当前点亮象素，那么，下一个点亮的象素可能是 P1（ Xp+1,Yp）或 P2（ Xp +1,Yp +1)。
M
P1
P2
P（ Xp,Yp ）
浙江大学信息学院 计算机图形学中点画圆法构造函数,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)
M
P1
P2
浙江大学信息学院 计算机图形学中点画圆法有如下结论：
F（ M） < 0 ->M在圆内 -> 取 P1
F（ M） >= 0 ->M在圆外 -> 取 P2
为此，可采用如下判别式：
M
P1
P2
浙江大学信息学院 计算机图形学中点画圆法
d = F(M) = F(xp + 1,yp - 0.5)
=(xp + 1)2 + (yp - 0.5) 2 - R2
若 d<0,则 P1 为下一个象素，那么再下一个象素的判别式为：
d1 = F(xp + 2,yp - 0.5)
= (xp + 2)2 + (yp - 0.5) 2 - R2
= d + 2xp +3
即 d 的增量为 2xp +3.
M
P1
P2
d
浙江大学信息学院 计算机图形学中点画圆法若 d>=0,则 P2 为下一个象素，那么再下一个象素的判别式为：
d1 = F(xp + 2,yp - 1.5)
= (xp + 2)2 + (yp - 1.5) 2 - R2
= d + （ 2xp + 3） +（ -2 yp + 2）
即 d 的增量为 2 (xp - yp) +5.
d的初值,
d0 = F(1,R-0.5)
= 1 + (R-0.5)2 - R2
= 1.25 - R
M
P1
P2
浙江大学信息学院 计算机图形学中点画圆法
MidpointCircle(int r,int 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--; }
}
}
浙江大学信息学院 计算机图形学中点画圆法
为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。
使用 e=d-0.25代替 d
e0=1-R
浙江大学信息学院 计算机图形学中点画圆法
上述算法能否再改进呢？
注意到 d的增量是 x,y的线性函数,
每当 x递增 1,则 d的增量递增 Δx=2
每当 y递减 1,则 d的增量递增 Δy=2
Δx初始值 =3； Δy初始值 =-2r+2
见 173页算法 。
浙江大学信息学院 计算机图形学
Bresenham画圆算法现在从 A点开始向右下方逐点来寻找弧 AB要用的点。如图中点 Pi-1是已选中的一个表示圆弧上的点，根据弧 AB的走向，下一个点应该从
Hi或者 Li中选择。显然应选离 AB最近的点作为显示弧 AB的点。
假设圆的半径为 R，显然，当
xhi2 + yhi2 -R2 ≥ R 2 - (xli2 +
yli2)时，应该取 Li。否则取 Hi。
令 di = xhi2 + yhi2 + xli2 +
yli2 - 2R2 显然，当 di ≥0 时应该取 Li。否则取 Hi。
Pi-1 Hi
Li
应取 Hi还是取 Li
浙江大学信息学院 计算机图形学
Bresenham画圆算法剩下的问题是如何快速的计算 di。设图中
Pi-1的坐标为 (xi-1,yi-1)，则 Hi和 Li的坐标为 (xi,yi-1)和 (xi,yi-1-1 )
di = xi2 + yi-12 + xi2 + (yi-1-1)2 - 2R2
=2xi2 + 2yi-12 - 2yi-1 - 2R2
di+1 = (xi + 1)2 + yi2 + (xi + 1)2 + (yi
- 1)2 - 2R2
=2xi2 + 4xi + 2yi2 - 2yi - 2R2 + 3
Pi-1 Hi
Li
应取 Hi还是取 Li
浙江大学信息学院 计算机图形学
Bresenham画圆算法当 di<0时 ->取 Hi -> yi=yi-1，则
di+1 = di + 4xi-1 + 6
当 di ≥ 0 时 ->取 Li -> yi=yi-1-1，则
di+1 = di + 4(xi-1-yi-1) + 10
易知 x0=0,y0=R,x1=x0+1
因此 d0=12 + y02 + 12 +(y0 - 1)2
- 2R2 = 3 - 2y0 = 3 - 2R
Pi-1 Hi
Li
应取 Hi还是取 Li
浙江大学信息学院 计算机图形学生成圆弧的正负法原理：
设圆的方程为 F(x,y)=X2 + Y2 - R2=0;
假设求得 Pi的坐标为 (xi,yi)；
则当 Pi在圆内时 -> F(xi,yi)<0 -> 向右 -> 向圆外
Pi在圆外时 -> F(xi,yi)>0 -> 向下 -> 向圆内浙江大学信息学院 计算机图形学生成圆弧的正负法即求得 Pi点后选择下一个象素点 Pi+1的规则为：
当 F(xi,yi) ≤0 取 xi+1 = xi+1,yi+1 = yi;
当 F(xi,yi) ＞ 0 取 xi+1 = xi,yi+1 = yi - 1;
这样用于表示圆弧的点均在圆弧附近，且使
F(xi,yi) 时正时负，故称正负法。
快速计算的关键是 F(xi,yi) 的计算，能否采用增量算法？
浙江大学信息学院 计算机图形学生成圆弧的正负法
若 F(xi,yi) 已知，计算 F(xi+1,yi+1) 可分两种情况：
1,F(xi,yi)≤0 -> xi+1 = xi+1,yi+1 = yi;
-> F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2
-> = (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi+1
2,F(xi,yi)＞ 0-> xi+1 = xi,yi+1 = yi -1;
-> F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2
-> = xi2+(yi –1)2-R2 = F(xi,yi) - 2yi+1
3、初始值：略浙江大学信息学院 计算机图形学生成圆弧的多边形逼近法圆的内接正多边形迫近法圆的等面积正多边形迫近法浙江大学信息学院 计算机图形学圆的内接正多边形逼近法
思想：当一个正多边形的边数足够多时，
该多边形可以和圆无限接近。即
因此，在允许的误差范围内，可以用正多边形代替圆。
设内接正 n边形的顶点为 Pi(xi,yi),Pi的幅角为?i,每一条边对应的圆心角为 a，则有
xi =Rcos?i
yi =Rsin?i
圆边正内接多边形） nn (lim
浙江大学信息学院 计算机图形学圆的内接正多边形逼近法内接正 n边形代替圆
计算多边形各顶点的递推公式
Xi+1 Rcos( a+?i)
=
Yi +1 Rsin (a+?i)
Xi+1 cos a - sin a Xi
=
Yi +1 sin a cosa Yi
因为,a是常数,sin a,cosa只在开始时计算一次所以，一个顶点只需 4次乘法，共 4n次乘法，外加直线段的中点算法的计算量。
浙江大学信息学院 计算机图形学圆的等面积正多边形逼近法
当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。
为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。
浙江大学信息学院 计算机图形学圆的等面积正多边形逼近法步骤：
求多边形径长，从而求所有顶点坐标值
由逼近误差值，确定边所对应的圆心角 α
浙江大学信息学院 计算机图形学椭圆的扫描转换
F(x,y)=b2x2+a2y2-a2b2=0
椭圆的对称性,只考虑第一象限椭圆弧生成,分上下两部分,以切线斜率为 -1
的点作为分界点 。
椭圆上一点处的法向：
N(x,y) = (F)' x i + (F)' y j
= 2b2 x i + 2a2 y j
浙江大学信息学院 计算机图形学在上半部分,法向量的 y分量大在下半部分,法向量的 x分量大上半部分下半部分法向量两分量相等M1
M2
在当前中点处，法向量（ 2b2 (Xp+1),2a2 (Yp-0.5))的 y分量比 x分量大,
即,b2 (Xp+1) < a2 (Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分浙江大学信息学院 计算机图形学椭圆的中点画法
与圆弧中点算法类似：确定一个象素后,接着在两个候选象素的中点计算一个判别式的值,
由判别式的符号确定更近的点先讨论椭圆弧的上部分设 (Xp,Yp)已确定,则下一待选像素的中点是
(Xp+1,Yp-0.5)
d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2
浙江大学信息学院 计算机图形学根据 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)
浙江大学信息学院 计算机图形学
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
浙江大学信息学院 计算机图形学程序,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); }
}
1、确定有关像素
2、用图形的颜色或其它属性，对像素进行写操作。
对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。
任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。
浙江大学信息学院 计算机图形学图形显示前需要：扫描转换 +裁剪
●裁剪 ---〉 扫描转换：最常用，节约计算时间。
●扫描转换 ---〉 裁剪：算法简单；
浙江大学信息学院 计算机图形学本章内容
？扫描转换直线段
DDA算法中点画线法
Bresenham画线算法
？圆弧、椭圆弧扫描转换中点算法内接正多边形迫近法等面积正多边形逼近法生成圆弧的正负法浙江大学信息学院 计算机图形学直线段的扫描转换算法
直线的扫描转换,确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。
三个常用算法：
数值微分法（ DDA）
中点画线法
Bresenham算法。
浙江大学信息学院 计算机图形学数值微分法（ＤＤＡ）
假定直线的起点、终点分别为：（ x0,y0),
(x1,y1)，且都为整数。
(X i+1,Yi + k)
(X i,Int(Yi +0.5))
(X i,Yi) 栅格交点表示象素点位置
。
。 。
。
浙江大学信息学院 计算机图形学数值微分 (DDA)法
基本思想已知过端点 P0 (x0,y0),P1(x1,y1)的直线段 L
y=kx+b
直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。
01
01
xx
yyk
)(,;
10
yr o u n dx
bkxy
s te p xxxxxx
令浙江大学信息学院 计算机图形学数值微分 (DDA)法计算 yi+1= kxi+1+b
= kxi+b+k?x
= yi+k?x
当?x =1; yi+1 = yi+k
即：当 x每递增 1,y递增 k(即直线斜率 )；
注意上述分析的算法仅适用于?k? ≤ 1的情形。
在这种情况下,x每增加 1,y最多增加 1。
当?k1时，必须把 x,y地位互换浙江大学信息学院 计算机图形学数值微分 (DDA)法
增量算法：在一个迭代算法中，如果每一步的 x,y值是用前一步的值加上一个增量来获得，则称为增量算法。
DDA算法就是一个增量算法。
浙江大学信息学院 计算机图形学数值微分 (DDA)法
void DDALine(int x0,int y0,int x1,int y1,int color)
int x；
float dx,dy,y,k;
dx = x1-x0; dy=y1-y0;
k=dy/dx; y=y0;
for (x=x0; x?x1,x++)
drawpixel (x,int(y+0.5),color);
y=y+k;
浙江大学信息学院 计算机图形学数值微分 (DDA)法
例：画直线段 P0(0,0)--P1(5,2)
x int(y+0.5) y+0.5
0 0 0+0.5
1 0 0.4+0.5
2 1 0.8+0.5
3 1 1.2+0.5
4 2 1.6+0.5
5 2 2.0+0.5
0 1 2 3 4 5
3
2
1
Line,P0(0,0)-- P1(5,2)
浙江大学信息学院 计算机图形学数值微分 (DDA)法
缺点,在此算法中,y,k必须是 float，且每一步都必须对 y进行舍入取整，不利于硬件实现。
浙江大学信息学院 计算机图形学中点画线法
原理：
假定直线斜率 0<K<1，且已确定点亮象素点 P（ Xp,Yp ）,
则下一个与直线最接近的像素只能是 P1点或 P2点。设 M
为中点,Q为交点现需确定下一个点亮的象素。
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法
– 当 M在 Q的下方 -> P2离直线更近更近 ->取 P2 。
– M在 Q的上方 -> P1离直线更近更近 ->取 P1
– M与 Q重合,P1,P2任取一点。
– 问题：如何判断 M与 Q点的关系？
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法假设直线方程为,ax+by+c=0
其中 a=y0-y1,b=x1-x0,c=x0y1-x1y0
由常识知：
∴ 欲判断 M点是在 Q点上方还是在 Q点下方,
只需把 M代入 F(x,y),并检查它的符号 。
点在直线下方点在直线上方点在直线上面
0,
0,
0,
yxF
yxF
yxF
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法构造判别式：
d=F(M)=F(xp+1,yp+0.5)
=a(xp+1)+b(yp+0.5)+c
当 d<0,M在直线 (Q点 )下方，取右上方 P2；
当 d>0,M在直线 (Q点 )上方，取右方 P1；
当 d=0，选 P1或 P2均可，
约定取 P1；
能否采用增量算法呢？
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法若 d?0->M在直线上方 ->取 P1;
此时再下一个象素的判别式为
d1=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；
增量为 a
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法
若 d<0->M在直线下方 ->取 P2;
此时再下一个象素的判别式为
d2= 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 ；
增量为 a＋ b
P=( x p,y p )
Q
P2
P1
浙江大学信息学院 计算机图形学中点画线法
画线从 (x0,y0)开始,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来摆脱小数，提高效率。
浙江大学信息学院 计算机图形学中点画线法
void Midpoint Line (int x0,int y0,int x1,int y1,int color)
{ int a,b,d1,d2,d,x,y;
a=y0-y1,b=x1-x0,d=2*a+b;
d1=2*a,d2=2* (a+b);
x=x0,y=y0;
drawpixel(x,y,color);
while (x<x1)
{ if (d<0) {x++; y++; d+=d2; }
else {x++; d+=d1;}
drawpixel (x,y,color);
} /* while */
} /* mid PointLine */
浙江大学信息学院 计算机图形学中点画线法
例：用中点画线法 P0(0,0) P1(5,2)
a=y0-y1=-2 b=x1-x0=5
d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6
i xi yi d
1 0 0 1
2 1 0 -3
3 2 1 3
4 3 1 -1
5 4 2 5
0 1 2 3 4 5
3
2
1
浙江大学信息学院 计算机图形学
Bresenham画线算法在直线生成的算法中 Bresenham算法是最有效的算法之一。令 k=Δy/Δx,就
0≤k≤1 的情况来说明 Bresenham算法。
由 DDA算法可知：
yi+1=yi+k (1)
由于 k不一定是整数，由此式求出的 yi也不一定是整数，因此要用坐标为（ xi,yir）
的象素来表示直线上的点，其中 yir表示最靠近 yi的整数。
浙江大学信息学院 计算机图形学
Bresenham画线算法设图中 xi列上已用（ xi,yir）作为表示直线的点，
又设 B点是直线上的点，其坐标为（ xi+1,yi+1），显然下一个表示直线的点（ xi+1,yi+1,r）只能从图中的 C
或者 D点中去选。设 A为 CD边的中点。 若 B在 A点上面则应取 D点作为（ xi+1,yi+1,r），否则应取 C点。
xi Xi+1
Yi,r
Yi+1,r
C
D
BA
ε(x) 的几何意义为能确定 B在 A点上面或下面，令
ε(x i+1)=yi+1-yir-0.5 (2)
若 B在 A的下面，则有 ε(x i+1)<0，反之，
则 ε(x i+1)>0。由图可知
yi+1,r=yir+1，若 ε(x i+1)≥0 (3)
yi+1,r=yir,若 ε(x i+1)≤0
浙江大学信息学院 计算机图形学
Bresenham画线算法由式（ 2）和式（ 3）可得到
ε(x i+2)=yi+2 - yi+1,r - 0.5
=yi+1 + k - yi+1,r - 0.5 （ 4）
yi+1 - yir -0.5 + k - 1,当 ε(x i+1)≥0
yi+1 - yir -0.5 + k,当 ε(x i+1)≤0
ε(x i+2)= ε(x i+1) + k -1,当 ε(x i+1)≥0
ε(x i+2)= ε(x i+1) + k,当 ε(x i+1)≤0
由式（ 1）和式（ 2）可得到
ε(x 2)= k - 0.5 (5)
浙江大学信息学院 计算机图形学程序如下,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画线算法浙江大学信息学院 计算机图形学圆的扫描转换算法下面仅以圆心在原点、半径 R为整数的圆为例，讨论圆的生成算法。
假设圆的方程为：
X2 + Y2 = R2
浙江大学信息学院 计算机图形学圆弧扫描算法
X2 + Y2 = R2
Y =?Sqrt(R2 - X2)
在一定范围内，每给定一
X值，可得一 Y值。
当 X取整数时,Y须取整。
缺点：浮点运算，开方，
取整，不均匀。
y
x
浙江大学信息学院 计算机图形学角度 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 + dx = x n - Rsin?d? =x n - (y n - y 0 )d?
y n+1 = y n + dy = y n + Rcos?d? =y n + (x n - x 0 )d?
显然，确定 x,y的初值及 d?值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。
但要采用浮点运算、乘法运算、取整运算。
浙江大学信息学院 计算机图形学中点画圆法利用圆的对称性，只须讨论 1/8圆。第二个 8分圆
P为当前点亮象素，那么，下一个点亮的象素可能是 P1（ Xp+1,Yp）或 P2（ Xp +1,Yp +1)。
M
P1
P2
P（ Xp,Yp ）
浙江大学信息学院 计算机图形学中点画圆法构造函数,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)
M
P1
P2
浙江大学信息学院 计算机图形学中点画圆法有如下结论：
F（ M） < 0 ->M在圆内 -> 取 P1
F（ M） >= 0 ->M在圆外 -> 取 P2
为此，可采用如下判别式：
M
P1
P2
浙江大学信息学院 计算机图形学中点画圆法
d = F(M) = F(xp + 1,yp - 0.5)
=(xp + 1)2 + (yp - 0.5) 2 - R2
若 d<0,则 P1 为下一个象素，那么再下一个象素的判别式为：
d1 = F(xp + 2,yp - 0.5)
= (xp + 2)2 + (yp - 0.5) 2 - R2
= d + 2xp +3
即 d 的增量为 2xp +3.
M
P1
P2
d
浙江大学信息学院 计算机图形学中点画圆法若 d>=0,则 P2 为下一个象素，那么再下一个象素的判别式为：
d1 = F(xp + 2,yp - 1.5)
= (xp + 2)2 + (yp - 1.5) 2 - R2
= d + （ 2xp + 3） +（ -2 yp + 2）
即 d 的增量为 2 (xp - yp) +5.
d的初值,
d0 = F(1,R-0.5)
= 1 + (R-0.5)2 - R2
= 1.25 - R
M
P1
P2
浙江大学信息学院 计算机图形学中点画圆法
MidpointCircle(int r,int 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--; }
}
}
浙江大学信息学院 计算机图形学中点画圆法
为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。
使用 e=d-0.25代替 d
e0=1-R
浙江大学信息学院 计算机图形学中点画圆法
上述算法能否再改进呢？
注意到 d的增量是 x,y的线性函数,
每当 x递增 1,则 d的增量递增 Δx=2
每当 y递减 1,则 d的增量递增 Δy=2
Δx初始值 =3； Δy初始值 =-2r+2
见 173页算法 。
浙江大学信息学院 计算机图形学
Bresenham画圆算法现在从 A点开始向右下方逐点来寻找弧 AB要用的点。如图中点 Pi-1是已选中的一个表示圆弧上的点，根据弧 AB的走向，下一个点应该从
Hi或者 Li中选择。显然应选离 AB最近的点作为显示弧 AB的点。
假设圆的半径为 R，显然，当
xhi2 + yhi2 -R2 ≥ R 2 - (xli2 +
yli2)时，应该取 Li。否则取 Hi。
令 di = xhi2 + yhi2 + xli2 +
yli2 - 2R2 显然，当 di ≥0 时应该取 Li。否则取 Hi。
Pi-1 Hi
Li
应取 Hi还是取 Li
浙江大学信息学院 计算机图形学
Bresenham画圆算法剩下的问题是如何快速的计算 di。设图中
Pi-1的坐标为 (xi-1,yi-1)，则 Hi和 Li的坐标为 (xi,yi-1)和 (xi,yi-1-1 )
di = xi2 + yi-12 + xi2 + (yi-1-1)2 - 2R2
=2xi2 + 2yi-12 - 2yi-1 - 2R2
di+1 = (xi + 1)2 + yi2 + (xi + 1)2 + (yi
- 1)2 - 2R2
=2xi2 + 4xi + 2yi2 - 2yi - 2R2 + 3
Pi-1 Hi
Li
应取 Hi还是取 Li
浙江大学信息学院 计算机图形学
Bresenham画圆算法当 di<0时 ->取 Hi -> yi=yi-1，则
di+1 = di + 4xi-1 + 6
当 di ≥ 0 时 ->取 Li -> yi=yi-1-1，则
di+1 = di + 4(xi-1-yi-1) + 10
易知 x0=0,y0=R,x1=x0+1
因此 d0=12 + y02 + 12 +(y0 - 1)2
- 2R2 = 3 - 2y0 = 3 - 2R
Pi-1 Hi
Li
应取 Hi还是取 Li
浙江大学信息学院 计算机图形学生成圆弧的正负法原理：
设圆的方程为 F(x,y)=X2 + Y2 - R2=0;
假设求得 Pi的坐标为 (xi,yi)；
则当 Pi在圆内时 -> F(xi,yi)<0 -> 向右 -> 向圆外
Pi在圆外时 -> F(xi,yi)>0 -> 向下 -> 向圆内浙江大学信息学院 计算机图形学生成圆弧的正负法即求得 Pi点后选择下一个象素点 Pi+1的规则为：
当 F(xi,yi) ≤0 取 xi+1 = xi+1,yi+1 = yi;
当 F(xi,yi) ＞ 0 取 xi+1 = xi,yi+1 = yi - 1;
这样用于表示圆弧的点均在圆弧附近，且使
F(xi,yi) 时正时负，故称正负法。
快速计算的关键是 F(xi,yi) 的计算，能否采用增量算法？
浙江大学信息学院 计算机图形学生成圆弧的正负法
若 F(xi,yi) 已知，计算 F(xi+1,yi+1) 可分两种情况：
1,F(xi,yi)≤0 -> xi+1 = xi+1,yi+1 = yi;
-> F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2
-> = (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi+1
2,F(xi,yi)＞ 0-> xi+1 = xi,yi+1 = yi -1;
-> F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2
-> = xi2+(yi –1)2-R2 = F(xi,yi) - 2yi+1
3、初始值：略浙江大学信息学院 计算机图形学生成圆弧的多边形逼近法圆的内接正多边形迫近法圆的等面积正多边形迫近法浙江大学信息学院 计算机图形学圆的内接正多边形逼近法
思想：当一个正多边形的边数足够多时，
该多边形可以和圆无限接近。即
因此，在允许的误差范围内，可以用正多边形代替圆。
设内接正 n边形的顶点为 Pi(xi,yi),Pi的幅角为?i,每一条边对应的圆心角为 a，则有
xi =Rcos?i
yi =Rsin?i
圆边正内接多边形） nn (lim
浙江大学信息学院 计算机图形学圆的内接正多边形逼近法内接正 n边形代替圆
计算多边形各顶点的递推公式
Xi+1 Rcos( a+?i)
=
Yi +1 Rsin (a+?i)
Xi+1 cos a - sin a Xi
=
Yi +1 sin a cosa Yi
因为,a是常数,sin a,cosa只在开始时计算一次所以，一个顶点只需 4次乘法，共 4n次乘法，外加直线段的中点算法的计算量。
浙江大学信息学院 计算机图形学圆的等面积正多边形逼近法
当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。
为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。
浙江大学信息学院 计算机图形学圆的等面积正多边形逼近法步骤：
求多边形径长，从而求所有顶点坐标值
由逼近误差值，确定边所对应的圆心角 α
浙江大学信息学院 计算机图形学椭圆的扫描转换
F(x,y)=b2x2+a2y2-a2b2=0
椭圆的对称性,只考虑第一象限椭圆弧生成,分上下两部分,以切线斜率为 -1
的点作为分界点 。
椭圆上一点处的法向：
N(x,y) = (F)' x i + (F)' y j
= 2b2 x i + 2a2 y j
浙江大学信息学院 计算机图形学在上半部分,法向量的 y分量大在下半部分,法向量的 x分量大上半部分下半部分法向量两分量相等M1
M2
在当前中点处，法向量（ 2b2 (Xp+1),2a2 (Yp-0.5))的 y分量比 x分量大,
即,b2 (Xp+1) < a2 (Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分浙江大学信息学院 计算机图形学椭圆的中点画法
与圆弧中点算法类似：确定一个象素后,接着在两个候选象素的中点计算一个判别式的值,
由判别式的符号确定更近的点先讨论椭圆弧的上部分设 (Xp,Yp)已确定,则下一待选像素的中点是
(Xp+1,Yp-0.5)
d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2
浙江大学信息学院 计算机图形学根据 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)
浙江大学信息学院 计算机图形学
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
浙江大学信息学院 计算机图形学程序,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); }
}
