直线的扫描转换.ppt

1、基本图形生成直线,内容安排,扫描转换的概念 直线的扫描转换算法,为什么需要扫描转换？,光栅显示器 画点设备 离散 近似表示 帧缓存,扫描转换的概念,扫描转换 确定一个像素集合并确定其颜色，用于显示一个图形的过程,扫描转换,第一步：确定有关像素 第二步：用图形的颜色或其他属性，对像素进行写操作。,扫描转换算法,必要性 每次生成或修改过程都需要调用扫描转换 要求 速度快 质量好,直线的扫描转换,如何确定直线段 直线段的起点和终点 端点坐标为整数 如何确定最佳逼近直线的像素点？ 线宽为1,直线的扫描转换,代数方程 y=mx+b F(x,y)=ax+by+c=0,直线的扫描转换,数值微分法DDA算法

2、Bresenham画线算法,基本观察,基本观察,斜率m在-1和1之间 x每次走一步 从x=x0到x=x1的每一列 P(xp,yp) 在x=xp+1的列上有一个像素,基本观察,斜率m在-1和1之外 y每次走一步 从y=y0到y=y1的每一列 P(xp,yp) 在y=yp+1的列上有一个像素,m =1,m =-1,最简单的策略,直线方程 y=mx+b xi+1=xi+1 yi+1=mxi+1+b y值是浮点数 四舍五入 效率太低 浮点乘法、加法,(xi+1 , round(yi+1),(xi , round(yi),(xi , yi),(xi+1 , yi+1),DDA算法,增量思想 xi+1=x

3、i+1 yi+1=mxi+1+b =m(xi+1)+b =mxi+b+m =yi+m 每一步的值都可以根 据前一步的值加上一 个增量得到 y值是浮点数 去掉了乘法,(xi+1 , round(yi+m),(xi , round(yi),(xi , yi),(xi+1 , yi+m),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

4、 y=y0; for (x=x0;x =x1;x+) dc.SetPixel( x,int(y+0.5), color); y+=m; ,算法演示,y,x,0,1,2,3,4,5,1,2,SetPixel(0,0) ,y=0.4,SetPixel(1,0) ，y=0.8,SetPixel(2,1) ，y=1.2,SetPixel(3,1) ，y=1.6,SetPixel(4,2) ，y=2,SetPixel(5,2) , y=2.4,算法演示,DDA算法特点,优点 算法简单 容易实现 缺点 浮点运算 四舍五入 误差积累,算法示例,斜率在0、1之间,k =0,k =1,探讨规律,斜率增量m 整数

5、增量0或1,(xi+1 , round(yi+m),(xi , round(yi),(xi , yi),(xi+1 , yi+m),1,E,NE,m=1,m=0,x=xi,x=xi+1,yiyi+1 yi+1,Round(yi+1)=Round(yi ) Round(yi+1)=Round(yi )+1,利用规律,选点规则 利用距离差 判定标准 dupper、dlower的大小 dlower dupper的符号,E,NE,P,L1,dupper,dlower,利用规律,p=dlower dupper p0 取NE p0 取E p=0 取NE,E,NE,P,L1,dupper,dlower,决策

6、参数值,已选点P(xk,yk) NE(xk+1,yk+1) E(xk+1,yk) dlower=y-yk dupper=yk+1-y pk= x(dlower dupper) pk=2y*xk-2x*yk+c,E,NE,P(xk,yk),L1,dupper,dlower,Bresenham算法,起始点 直线的左下端点 循环 x增1 根据判定变量的符号决定 y增1还是不增 斜率增量整数增量 更新判定变量的值 终止点 直线的右上端点,E,NE,dlower,P(xn , yn),Pnew(xn+1 , yn+1),NE,E,dlower,dupper,dupper,更新决策变量,pk=2y*xk-

7、2x*yk+c pk+1=2y*(xk+1)-2x*(yk+1)+c pk+1-pk=2y- 2x(yk+1-yk) 增量算法,E,NE,P(xk,yk),L1,dupper,dlower,更新决策变量,pk0 取NE点 Pnew(xk+1,yk+1) pk+1-pk=2y-2x,E,NE,P(xk,yk),L1,dupper,dlower,Pnew(xk+1,yk+1),dupper,dlower,E,NE,更新决策变量,pk0 取E点 Pnew(xk+1,yk) pk+1-pk=2y,E,NE,P(xk,yk),L1,dupper,dlower,Pnew(xk+1,yk),dupper,d

8、lower,E,NE,增量思想,去除了决策变量更新中的乘法运算,算法小结,起始点 直线的左下端点 循环 x增1 根据判定变量的符号决定下一个像素点位置 （y增1还是不增） 根据所选像素，用incrE或incrNE递增判定变量的值 终止点 直线的右上端点,初始化,已知：直线的两个端点坐标 初始决策变量 决策变量的两个增量incrE、incrNE 决策变量,初始化,选定点端点P0(x0,y0) 初始判定变量 p0=2y-x incrE= 2y incrNE= 2y-2x,dlower,P0(x0 , y0),E,NE,dupper,算法总结,void LineBres (int x0, int y

9、0, 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(xxEnd) x+; if(p0) p+=incrE; else y+; p+=incrNE; setPixel(x,y); ,算法演示,y,x,0,1,2,3,4,5,1,2,SetPixel(0,0)

10、,p=-1, incrE=4, incrNE=-6,d=-10, 取E点 p=p+incrE=3, SetPixel(1,0),p=30, 取NE点 p=p+ incrNE =-3, SetPixel(2,1),p=-30, 取E点 p=p+ incrE=1, SetPixel(3,1),p=10, 取NE点 p=p+incrNE=-5, SetPixel(4,2),p=-50, 取E点 p=p+incrE=-1, SetPixel(5,2),算法分析,速度快 没有浮点运算 没有函数调用运算 质量好 误差小 像素分布均匀,OpenGL 画线函数,#include void mydisplay(

11、) 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(); void main(int argc, char* argv) glutCreateWindow(简单示例); glutDisplayFunc(mydisplay);/ mydisplay是回调函数 glutMainLoop(); ,点的细节,控制点的大小 void glPointSize(GLfloat size) glPointSize(3.0); 默认状态下为1.0,直线的细节,指定线宽 void glLineWidth(GLfloat width) 默认状态下为1.0,线型,点画线 glLineStipple()定义点画模式 void glLineStipple(GLint factor,GLushort pattern); glEnabl