计算机图形学基本光栅图形算法

《计算机图形学基本光栅图形算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章内容13.1用Java语言绘图23.2直线的扫描转换33.3圆的扫描转换43.4多边形的扫描转换53.5区域填充63.6字符的生成73.7光栅图形的反走样算法3.2直线的扫描转换⊙图形图像是由屏幕上不同亮度不同颜色的光点（像素）组成。在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。所以⊙对直线进行光栅化的时候，只能在显示器所给定的有限个像素组成的点阵中确定最佳逼近于该直线的一组像素，用这些像素表示该直线。所以⊙生成直线的主要工作是：快速找出距离直线最近的网格点

2、，用这些网格点对应的像素表示该直线。3像素逼近直线示意图图像元素可寻址点43.2.1基本3增.量2.算1法基(DD本A-增dig量it算al法differentialanalyzer)1、基本思想：设直线ymxb满足0m1，由于直线的斜率小于等于1，所以，该直线的扫描转换可从最左端开始，x每次递增一个单位，对每个xi，相应的有ymxb，则iiymxbm(x1)bymi1i1ii所以，x每增加一个单位，y只需加上一个m，这样就去掉了乘法运算，提高了算法效率。在该算法中

3、，直线上的所有点的x和y值可由前一点的值加一个基本增量得到，所以该算法称为基本增量算法。53.2.1基本增量算法上述讨论只适合

4、m

5、1的情况，当

6、m

7、时1，注：只需将和x的角y色互换，即每次y增加一个单位，每次x增加1。/m基本增量算法也叫数字微分分析器算法（DigitalDifferentialAnalyzer，DDA）。DDA是用数值方法求解微分方程的一种设备，即根据11x1和y的一阶导数，在x和y方向上渐进地以小步长移动，由此产生连续的像素坐标(x,y)。ii62、直线的表示：设直线的

8、起点坐标为(xs，ys)，终点坐标为(xe,ye)，令Δx＝xe-xs，Δy＝ye-ys，则直线参数方程为xxxts0t1yyyts第i步时xixsxti(3.1)yyytisiv目标：能快速地求出能很好地表示直线的像素73、提高速度的方法：乘法用加法实现，每一个点坐标都可以由前一个坐标变化一个增量得到。设(xi,yi)是第i步得的直线上的点，则直线上第个i+1点是(xi+1,yi+1)，其中xxx(tt)xxti1sii(3.2)

9、yyy(tt)yyti1sii当Δx>Δy>0，即直线斜率小于1，应使x方向每次增加1，y方向最多增加1，此时取Δt=1/Δx；同理,当Δy>Δx>0,直线斜率大于1，取Δt=1/Δy，所以令nmax{

10、x

11、,

12、y

13、}，将参数区间[0，1]分为n等份，即t每次的增量为t1/n。8下图中，用公式（3.2）求得的直线PsPe上的点用空心圆表示，但显示时要用像素来表示，即采用四舍五入的办法得到最靠近空心圆点的像素，用这些像素（下图中的实心圆点）来表示直线。PePs图中实心

14、圆点表示用DDA方法生成的直线94、直线的DDA算法程序voiddda(Graphicsg,intx1,intx2,inty1,inty2){intk;floatx,y,dx,dy;k=Math.abs(x2-x1);if(Math.abs(y2-y1)>k)k=Math.abs(y2-y1);dx=(float)(x2-x1)/k;dy=(float)(y2-y1)/k;//变化的增量x=(float)(x1);y=(float)(y1);图中黑点表示用DDAfor(inti=0;i

15、+){法生成的直线g.drawLine((int)(x+.5f),(int)(y+.5f),(int)(x+.5f),(int)(y+.5f));x=x+dx;y=y+dy;}}//endDDA完成四舍五入10设给定直线的起点坐标为(0，0)，实例终点坐标为(9，6)，则上述DDA算法画出的直线如下图所示。DDA算法缺点：需要进行浮点数运算，产生一个像素要做两次加法和两次取整运算，运行效率低且取整运算不利于硬件实现。DDA方法所画直线图113.2.2Bresenham算法设直线的起点坐标为(xs

16、,ys)，斜率为m。下面就0m1的情况来说算法背景明该算法。取xi为像素所在点的横坐标（整数），令(x,y)(x,y)，11ss直线上相邻两点的坐标满足关系yi1yim(3.3)一般来说，m不一定是整数，所以yi也不一定是整数，因此要用靠近该点最近的网格点(x,int(y0.5))来近似。由ii于取整计算量较大，为了提高效率，Bresenham算法用下面的方法来避免使用取整运算。12算法思想：Dy1设图3.4中已得到第i个显示的点i,r(x,y)，B点是直线与第i1列Aii,r