直线的扫描转换

点画线
小结
Bresenham画线法
距离差 NE 判定变量 符号判断 Pnew(xp+1 , yp+1) NE dupper 去除四舍五入运算 dlower dupper 增量算法 E dlower 去除乘法运算
P(xp , yp) E
增量思想 去除了决策变量更新中的乘法运算
pk incrNE pk 1 pk incrE
pk 0 取NE点 pn 0 取E点
算法小结
起始点
直线的左下端点
循环
x增 1 根据判定变量的符号决定下一个像素点位置 （y增1还是不增） 根据所选像素，用incrE或incrNE递增判定变量 的值
OpenGL 画线函数
#include <gl/glut.h> void mydisplay(){ glClearColor (1.0,1.0,0,0);//，设置背景色，默认为黑色 glClear(GL_COLOR_BUFFER_BIT);//清除帧缓存 glBegin(GL_LINE); glColor3f(1.0,0,0); glVertex2d(-0.5, -0.5); glVertex2d(-0.5, 0.5); glEnd(); glFlush(); }
(xi+1 , round(yi+m)) NE (xi , yi)
1 (xi+1 , yi+m) E (xi , round(yi)) m=0
利用规律
选点规则
利用距离差
判定标准
dupper、dlower的大小 dlower –dupper的符号
NE
dupper dlower
L1
P
E
利用规律
p=dlower –dupper p>0
取NE
L1
p<0
取E
NE
dupper
p=0
取NE
P
dlower
E
决策参数值
已选点P(xk,yk) NE(xk+1,yk+1) E(xk+1,yk) dlower=y-yk dupper=yk+1-y pk= △x(dlower –dupper) pk=2△y*xk-2△x*yk+c
数值微分法——DDA算法 Bresenham画线算法
基本观察
m =∞ m =1
m =0
m =-1
基本观察
斜率m在-1和1之间 x每次走一步
从x=x0到x=x1的每一列
m =1
P(xp,yp) 在x=xp+1的列上有一个像素
m =-1
基本观察
斜率m在-1和1之外 y每次走一步
GL_POLYGON
简单的凸多边形的边界
点的细节
控制点的大小
void glPointSize(GLfloat size) glPointSize(3.0); 默认状态下为1.0
直线的细节
指定线宽
void glLineWidth(GLfloat width) 默认状态下为1.0
void LineBres (int x0, int y0, int xEnd, int yEnd) { int dx=fabs(xEnd-x0),dy=fabs(yEnd-y0); int p=2*dy-dx; int incrE=2*dy; int incrNE=2*(dy-dx); int x,y; if(x0>xEnd) { x=xEnd;y=yEnd; xEnd=x0; } else { x=x0;y=y0; } setPixel(x,y); while(x<xEnd) { x++; if(p<0) p+=incrE; else {y++; p+=incrNE;} setPixel(x,y); } }
NE Pnew(xk+1,yk+1)
dupper dlower
NE
dupper dlower
L1
E
P(xk,yk)
E
更新决策变量
pk<0 取E点 Pnew(xk+1,yk) pk+1-pk=2△y
NE NE
dupper dlower dupper dlower L1
P(xk,yk)
E k) Pnew(xk+1,y E
终止点
直线的右上端点
初始化
已知：直线的两个端点坐标 初始决策变量 决策变量的两个增量incrE、incrNE 决策变量
初始化 选定点——端点P0(x0,y0) 初始判定变量
p0=2△y-△x
incrE= 2△y incrNE= 2△y-2△x
NE dupper dlower P0(x0 , y0) E
终止点
直线的右上端点
E
更新决策变量
pk=2△y*xk-2△x*yk+c pk+1=2△y*(xk+1)-2△x*(yk+1)+c pk+1-pk=2△y- 2△x(yk+1-yk) 增量算法
NE
dupper dlower
L1
P(xk,yk)
E
更新决策变量
pk≥0 取NE点 Pnew(xk+1,yk+1) pk+1-pk=2△y-2△x
4
5
x
p=p+ incrE=1, SetPixel(3,1)
p=1>0, 取NE点
p=-5<0, 取E点
p=p+incrE=-1, SetPixel(5,2)
p=p+incrNE=-5, SetPixel(4,2)
算法分析
速度快
没有浮点运算 没有函数调用运算
质量好
误差小 像素分布均匀
i i
m
DDA算法
void DDALine (int x0, int y0, int x1, int y1, COLORREF color) { CClientDC dc(this); int x; double dx = x1 –x0; double dy = y1-y0; double m= dy/dx; double y=y0; for (x=x0;x <=x1;x++) { dc.SetPixel( x,int(y+0.5), color); y+=m; } }
从y=y0到y=y1的每一列
m =1
P(xp,yp) 在y=yp+1的列上有一个像素
m =-1
最简单的策略
直线方程
y=mx+b
xi+1=xi+1 yi+1=mxi+1+b y值是浮点数 四舍五入 效率太低
(xi+1 , round(yi+1))
( x i , y i)
(xi+1 , yi+1)
L1
NE
dupper
dlower
P(xk,yk)
E
Bresenham算法
起始点
直线的左下端点
循环
x增1 根据判定变量的符号决定 y增1还是不增 Pnew(xn+1 , yn+1) NE 斜率增量——整数增量 更新判定变量的值 NE dupper dlower dupper dlower P(xn , yn) E
基本图形生成——直线
内容安排
扫描转换的概念 直线的扫描转换算法
为什么需要扫描转换？ 光栅显示器 画点设备
离散 近似表示 帧缓存
扫描转换的概念
扫描转换
确定一个像素集合 并确定其颜色，用 于显示一个图形的 过程
扫描转换 第一步：确定有关像素 第二步：用图形的颜色或其他属性，对像 素进行写操作。
扫描转换算法
必要性
每次生成或修改过程都需要调用扫描转换
要求
度快 质量好
直线的扫描转换
如何确定直线段
直线段的起点和终点 端点坐标为整数
如何确定最佳逼近直线的像素点？ 线宽为1
直线的扫描转换 代数方程
y=mx+b F(x,y)=ax+by+c=0
直线的扫描转换
浮点乘法、加法 (xi , round(yi))
DDA算法
增量思想
xi+1=xi+1 yi+1=mxi+1+b =m(xi+1)+b =mxi+b+m (xi+1 , round(yi+m)) =yi+m 每一步的值都可以根 据前一步的值加上一 (xi , yi) (xi+1 , yi+m) 个增量得到 y值是浮点数 去掉了乘法 (x , round(y ))
算法演示
SetPixel(0,0) ,y=0.4 y SetPixel(1,0) ，y=0.8
2 1
SetPixel(2,1) ，y=1.2
SetPixel(3,1) ，y=1.6
0
1
2
3
4
5
x SetPixel(4,2) ，y=2
SetPixel(5,2) , y=2.4
算法演示
DDA算法特点 优点
算法简单 容易实现
缺点
浮点运算 四舍五入 误差积累
算法示例
斜率在0、1之间
k =1
k =0
探讨规律
斜率增量m 整数增量0或1
x=xi x=xi+1 m=1
yi≤yi+1 ≤yi+1