下面仅对直线的DDA算法.PPT

* * 实验三 基本图形生成算法 一. 概述： 本实验是根据光栅图形生成算法，以实现各种基本图形的绘制。 因此，首先要熟悉各种基本图形的生成算法原理，然后根据算法原理，编写相应的绘图程序。 下面仅对直线的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+b+k?x = yi+k?x 当?x =1时 yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)。 上述采用的增量计算方法称为数值微分算法(Digital Differential Analyzer，简称DDA)。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。 以下是适用于所有象限的DDA算法生成直线的C语言程序。 图3-1 DDA算法基本原理 复杂度：加法+取整 void DDALine(int x0,int y0,int x1,int y1,int color) ? int i； float dx, dy, length,x,y; if (fabs(x1-x0)=fabs(y1-y0)) length=fabs(x1-x0); else length=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++; ? ? x int(y+0.5) y+0.5 0 0 0+0.5 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 图3-2 直线段的DDA扫描转换 举例: 线段P0(0,0)和P1(5,2)的DDA方法扫描转换。 DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。 2。Bresenham算法 Bresenham算法1965年提出，基本原理是：借助于一个误差量(直线与当前实际绘制像素点的距离)，来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素位置。 yi+1 y yi xi xi+1 d2 d1 图3-3 根据误差量来确定理想的像素点 假设当前直线上的像素坐标为(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)的符号相同。 当hi0时，直线上理想位置与像素(xi＋1，yi)更接近，应取右方像素； 当hi0时，像素(xi＋1，yi＋1)与直线上理想位置更接近； 当hi=0时，两个像素与直线上理想位置一样接近，可约定取(xi＋1，yi＋1)。 yi+1 y yi xi xi+1 d2 d1 图3-3 根据误差量来确定像素点 若令： 对于i+1步，误差参数为： 此时参数C已经消去，且xi+1=xi+1,得： ②如果选择右方像素，即： ，则： ①如果选择右上方像素，即： ，则： 对于每个整数x，从线段的坐标端点开始，循环的进行误差量的计算。在起始像