资源描述:
《《图形显示算法基础》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、所谓图元的生成,是指完成图元的参数表示形式(由图形软件包的使用者指定)到点阵表示形式(光栅显示系统刷新时所需的表示形式)的转换。通常也称扫描转换图元。第7章 图形显示算法基础13.1直线的生成算法3.1.1基本知识只有画水平线,垂直线,及正方形对角线时,象素点集的位置才是准确的。显示一条直线,实际上是用最靠近这条直线的象素点集来近似地表示这条直线.有限的象素矩阵画点设备光栅显示器:缓冲存储器,显示控制器,数/模转换器,阴级射线管(CRT)A(x1,y1)、B(x2,y2)、在纸上画一条直线和在计算机屏幕上画一条直线有什么本质的区别?
2、2生成直线的一般要求是:1.DDA算法(数值微分法)2.直线的Bresenham算法确定象素最佳逼近某图形的过程通常称为光栅化。图形生成算法的工作:在显示器所给定的有限个象素组成的矩阵中,确定最佳逼近于图形的象素点集.1.象素是均匀分布的2.所画的线应是直的,且有精确的起点和终点4.最后直线的生成速度要快3.所显示的亮度应沿直线不变,且与直线的长度和方向无关。3.1.2直线光栅化的方法3已知端点A(x1,y1)、B(x2,y2),直线的微分方程:dy/dx=(y2-y1)/(x2-x1)=常数=myi+1=yi+(y2-y1)/(x
3、2-x1)*Δx=yi+m*Δxyi=mxi+Byi+1=mxi+1+B=m(xi+Δx)+BA(x1,y1)B(x2,y2)Pi(xi,yi)Pi+1(xi+1,yi+1)dy=k·dxdx3.1.3DDA算法(DigitalDifferentialAlgorithm)通过同时对x,y各增加一个小的增量,计算下一步的x,y值。在一个迭代算法中,如果每一步的x,y值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。4光栅中Δx=1直线的递推公式yi+1=yi+(y2-y1)/(x2-x1)xi+1=xi+1doublex=
4、x1,y=y1;m=(y2-y1)/(x2-x1);intk=abs(x2-x1);for(inti=0;ix1≥0,y2>y1≥05oxyk>1讨论:oxyk<1xi+1=xi+1yi+1=yi+kyi+1=yi+1xi+1=xi+1/k(xi,yi)(xi+1,yi+1)(xi,yi)(xi+1,yi+1)因而造成隔行显示解决办法:将y看作自变量6结论:第一象限的直线DDA算法:(round(xi+1),yi+1)yi+1=yi+1xi+1=xi+1/kk>1(xi+1,rou
5、nd(yi+1))xi+1=xi+1yi+1=yi+kk<1逼近直线的象素点的坐标直线上点的坐标递推公式直线的斜率起点(x1,y1),终点(x2,y2)(x2>x1,y2>y1)以(x1,y1)为起点7DDA算法的优、缺点DDA算法的本质:效率低,不利于硬件实现直观可行DDA算法也是一个增量算法。缺陷:做除法;须采用浮点数据计算要取整数->算法效率不高算法程序实现k=abs(x2-x1);if(abs(y2-y1)>k)doubledeltx=(x2-x1)/k;doubledelty=(y2-y1)/k;for(inti=0;i<
6、=k;i++){x+=deltx;//x=x+deltx;y+=delty;//y=y+delty;}k=abs(y2-y1);putpixel((int)x,(int)y,2);用数值方法解微分方程(数值微分法)81.问题的提出2.基本思想a.效率的意义b.希望找到一个简单的判决条件,迅速确定直线上的点。借助于一个决策变量d的正负符号,来确定下一个该点亮的象素点。最逼近Pi+1点的象素点是Ti+1点还是Si+1点?由ti+1与si+1二者的相对大小决定。若ti+1si+1,则
7、取Si点(xi+1,yi)ti+1与si+1二者的大小可以由si+1-ti+1的正负来判定。stTiSi(r,q)3.1.4直线的Bresenham算法9为讨论方便,假定:直线斜率k在0,1之间起点坐标A(x1,y1)终点坐标B(x2,y2)将直线平移到原点则起点坐标(0,0),终点坐标B(dx,dy)dx=x2-x1dy=y2-y1其中直线方程为:且其中r=xi-1,q=yi-1stTiSi(r,q)所以定义di=dx(s-t)为决策变量10经推导di+1=di+2dy-2dx*(yi-yi-1)如果1)当di0,即s-t
8、0,st,则点亮Ti,2)当di0,即s-t0,s<t,则点亮Si,di+1=di+2(dy-dx)下一个决策变量stTiSi(r,q)下一个决策变量yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1