资源描述：
《实验三基本图形生成算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验三基本图形生成算法一.概述：本实验是根据光栅图形生成算法，以实现各种基本图形的绘制。因此，首先要熟悉各种基本图形的生成算法原理，然后根据算法原理，编写相应的绘图程序。下面仅对直线的DDA算法、Bresenham算法、圆的生成算法作简单介绍。1。数值微分(DDA)法给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为：画线过程从x的左端点x0开始，向x右端点步进，步长=1(个像素)，计算相应的y坐标：y=kx+b，取像素点(x,round(y))作为当前点的坐标。计算yi+1=kxi+1+b=k(xi+x)+b=kxi
2、+b+kx=yi+kx当x=1时yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)。上述采用的增量计算方法称为数值微分算法(DigitalDifferentialAnalyzer，简称DDA)。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。以下是适用于所有象限的DDA算法生成直线的C语言程序。图3-1DDA算法基本原理复杂度：加法+取整voidDDALine(intx0,inty0,intx1,inty1,intcolor)inti；floatdx,dy,length,x,y;
3、if(fabs(x1-x0)>=fabs(y1-y0))length=fabs(x1-x0);elselength=fabs(y1-y0);dx=(x1-x0)/length;dy=(y1-y0)/length;i=1;x=x0;y=y0;while(i<=length){SetPixel(int(x+0.5),int(y+0.5),color);x=x+dx;y=y+dy;i++;xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5图3-2直线段的DDA扫
4、描转换举例:线段P0(0,0)和P1(5,2)的DDA方法扫描转换。DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。2。Bresenham算法Bresenham算法1965年提出，基本原理是：借助于一个误差量(直线与当前实际绘制像素点的距离)，来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素位置。yi+1yyixixi+1d2d1图3-3根据误差量来确定理想的像素点假设
5、当前直线上的像素坐标为(xi,yi)，那么下一步需要在列xi+1上确定扫描线y的值。y值要么不变，要么递增1，可通过比较d1和d2来决定。如图3-3所示，对于直线斜率k在0~1之间的情况，从给定线段的左端点P0(x0,y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。根据误差项d的值来决定是否增1的过程如下：设Δy=y1－y0,Δx=x1－x0，则k=Δy/Δx，代入上式，得；是常量，与像素位置无关。则hi的计算仅包括整数运算，其符号与(d1-d2)的符号相同。当hi<0时，直线上理想位置与像素(xi＋1，yi
6、)更接近，应取右方像素；当hi>0时，像素(xi＋1，yi＋1)与直线上理想位置更接近；当hi=0时，两个像素与直线上理想位置一样接近，可约定取(xi＋1，yi＋1)。yi+1yyixixi+1d2d1图3-3根据误差量来确定像素点若令：对于i+1步，误差参数为：此时参数C已经消去，且xi+1=xi+1,得：②如果选择右方像素，即：，则：①如果选择右上方像素，即：，则：对于每个整数x，从线段的坐标端点开始，循环的进行误差量的计算。在起始像素(x0，y0)的第一个参数ho为：以下是当07、nham_Line(intx0,inty0,intx1,inty1,intcolor){intdx,dy,e,i,x,y;dx=x1-x0,dy=y1-y0,e=2*dy-dx;x=x0,y=y0;for(i=0;i<=dx;i++){SetPixel(x,y,color);x++;e=e+2*dy;if(e>=0){y++;e=e-2*dx;}}}3.圆的生成算法为了方便起见，可以只考虑中心在原点、半径为整数R的圆：圆上的点关于X轴、Y轴以及45º线对称，只要实现八分之一圆的扫描转换就可以利用对称性得到完整的圆。最容易想到的算法如下：根据圆的
8、基本方程，可以沿x轴，x从0到，以单位步长计算对应的y值来得到圆周上每点的位置：该算法每一步均包含浮点乘法和开方运算，且所绘制的像素间的间隔不一，随着
