y
yk+1 y
P2
}d
2
}
yk
0
d1 x
P1 xk x k+ 1
Bresenham画线算法（2/7） Bresenham画线算法（2/7） 画线算法
为方便与0比较， e=d为方便与0比较，设e=d-0.5 e=e=初始 d=0 0.5 x++ d=d+k 0.5时 当d≥0.5时 e=e+k P 最接近P 最接近P2(xi+1,yi+1) 方向走一步, y方向走一步, y++ e>=0 同时作为下次计算的基点， 同时作为下次计算的基点，d-1 d<0.5时 当d<0.5时 最接近P 最接近P1(xi+1,yi) y方向不走步 e<0 P
P2
d’ d
P1
P2
d
P1
d’
Bresenham画线算法（3/7） Bresenham画线算法（3/7） 画线算法
BresenhamLine(x0,y0,x1,y1,color) /* 算法 2.3*/ { int x,y,dx,dy; float k,e; int e; x1y1dx = x1-x0; dy = y1-y0; dy/dx; k = dy/dx; 怎样避免程序中 的小数和除法？ 0.5; e = -0.5; x=x0; 的小数和除法？ y=y0; for( i=0; i<=dx; i++) { drawpixel(x,y,color); e=e+k; x++; e=e+k; if (e >=0) { y++; e = e - 1; }
中点画线法（7/7） 中点画线法（7/7）
例2.2：画直线段P0(0,0)--P1(5,2) 2.2：画直线段P (0,0)--P
a=y0-y1=-2, =5, b=x1-x0=5, d=a+0.5b=0.5 =a=d1=a=-2, d2=a+b=3 if (d<0)
d+=d2; } else {x++; d+=d1;}
0 0 1 1 2
x++; e=e+k; y e if (e >=0) { y++; - 1; } -0.5
e = e
Line: P0(0, 0)-- P1(5, 2)
-0.1 -0.7 -0.3 -0.9
3 2 1
0
1
2
3
4
5
Bresenham画线算法（5/7） Bresenham画线算法（5/7） 画线算法
。
(X 0 , Y0)
栅格交点表示象素点位置
当x每递增1，y递增k(即直线斜率) ,y最多增加1 每递增1 递增k(即直线斜率) ,y最多增加 k(即直线斜率 最多增加1 增量算法：在一个迭代算法中，如果每一步的x 增量算法：在一个迭代算法中，如果每一步的x、y 值是用前一步的值加上一个增量来获得，则称为增 值是用前一步的值加上一个增量来获得， 量算法。 量算法。 DDA算法就是一个增量算法 算法就是一个增量算法。 DDA算法就是一个增量算法。
在直线上， 因(X0,Y0)在直线上， 在直线上 所以F(X0,Y0)=0 所以
优点：
只有整数运算， 只有整数运算，不含乘除法 可用硬件实现
中点画线法（6/6） 中点画线法（6/6）
/* 算法2.2*/ 算法2.2*/
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 */
F ( x, y ) = 0 F ( x, y ) > 0 F ( x, y ) < 0 点在直线上面 点在直线上方
Q P2 M
点在直线下方
P=( p,yp) P1 x
中点画线法（3/6） 中点画线法（3/6）
构造判别式： 构造判别式： M(xp+1,yp+0.5) d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c =F(xp, yp)+a+0.5b= a+0.5b )+a+0.5b= d>0， 在直线(Q d>0，M在直线(Q点)上方，取右方P1； (Q点 上方，取右方P d<0，………………..下方，取右上方P ..下方 d<0，………………..下方，取右上方P2； d=0， 均可，约定取P d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？ 能否采用增量算法呢？
Line: P0(0, 0)-- P1(5, 2) 3 2 1
0
1
2
3
4
5
中点画线法（1/6） 中点画线法（1/6）
原理： 原理：
假定直线斜率0<K<1，且已确 ， 假定直线斜率 定点亮象素点P（ 定点亮象素点 （X ,Y ）,则 下一个与直线最接近的像素只 能是P 点或P 能是 1点或 2点。
p p
if (d<0) d+=d2; } else
3 2 1
d=2*a+b=1
{x++; y++; {x++; d+=d1;}
0 0 1 1 2
Line: P0(0, 0)-- P1(5, 2)
0
1
2
3
4
5
Bresenham画线算法（1/7） Bresenham画线算法（1/7） 画线算法
基本思想
比较从理想直线到位于直线上方的像素的距离d1 比较从理想直线到位于直线上方的像素的距离d1和 d1和 相邻的位于直线下方的像素的距离d2 相邻的位于直线下方的像素的距离d2 根据距离误差项的符号确定与理想直线最近的象素 起始点在像素中心，所以误差项d的初值d 起始点在像素中心，所以误差项d的初值d0=0
F((Xp+1)+1,Yp+0 )=a(Xp+2)+b(Yp+0 d’=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c =F(Xp,Yp)+a+0.5b+a= d+a =F(Xp,Yp)+a+0 d的增量为a 的增量为a 若d＜0，中点M在直线下方，取右上方象素P2 (Xp+1,Yp+1) 中点M在直线下方，取右上方象素P (Xp+1,Yp+1
中点画线法（2/6） 中点画线法（2/6）
问题：判断距离理想直线最近的下一个象素点 问题： 已知：线段两端点(x ,y0 (x0 (x1,y1 已知：线段两端点(x0,y0)，(x1,y1) 直线方程：F(x,y)=ax+by+c=0 a=y0 a=y0-y1 点上方还是下方？ 如何判断M点在Q点上方还是下方？ b=x1 b=x1-x0 ),并检查其符号 把M代入F(x,y),并检查其符号 c=x0 c=x0y1-x1y0
中点画线法（7/7） 中点画线法（7/7）
例2.2：画直线段P0(0,0)--P1(5,2) 2.2：画直线段P (0,0)--P
a=y0-y1=-2, =2*a=d1=2*a=-4, x 0 1 2 3 4 y d 1 -3 3 -1 5 b=x1-x0=5, =5, d2=2* (a+b)=6
直线的扫描转换
确定最佳逼近于该直线的一组象素 按扫描线顺序， 按扫描线顺序，对这些象素进行写操作
三个常用算法
1 数值微分法（DDA） 数值微分法（DDA） 2 中点画线法 Bresenham算法 3 Bresenham算法
数值微分(DDA) 数值微分(DDA)法（1/5） (DDA)法 1/5）
基本思想 已知过端点P 的直线段L 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L 直线斜率为 y1 − y0
P2 再下一个象素的判别式为 M(xp+2,yp+1.5) ： M =F(Xp,Yp)+a+0 =F(Xp,Yp)+a+0.5b+a+b =d+a+b d的增量为a+b 的增量为a+b P1 F((Xp+1)+1,(Yp+1)+0 a(Xp+2)+b(Yp+1 d’’=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c
第4章 扫描转换
鲁萍
扫描转换
4.1 4.2 4.3 4.4 4.6 4.7 直线段的扫描转换 圆弧的扫描转换 多边形的扫描转换与区域填充 字符 反走样 OpenGL程序设计 OpenGL程序设计
直线段扫描转换
假设
像素间均匀网格，整型坐标系，直线段斜率0<m<1 像素间均匀网格，整型坐标系，直线段斜率0<m<1 对m＞1，x、y互换