文档介绍：基本图形生成算法直线圆弧
第1页，本讲稿共58页
通常认为，基本二维图形包括点、直线、圆、椭圆、多边形域和字符串等。复杂曲线及各种复杂图形均可由直线段和圆弧来拟合，因此研究直线和圆弧的生成算法是二维图形生成技术的基础。
第2页Y
第二象限
走笔 +Y
Fk+1=Fk-|xA |
走笔 -X
Fk+1=Fk+|yA |
第四象限
走笔 -Y
走笔 +X
各象限的判别式
直线的扫描转换——逐点比较法
第17页，本讲稿共58页
【注】递推公式的作用：
意义：简化计算过程，提高效率。
原则：尽可能以加减法代替乘除法。
方法：用当前点的偏差推算出走笔方向，并计算出下一步的偏差；再以画笔的当前位置重复上述过程，推算出画笔下一步的动作。
第18页，本讲稿共58页
数值微分法（Digital Differential Analyzer）
简称DDA法，利用直线的微分方程生成直线的方法。
设直线的端点坐标为（X0，Y0）和（X1，Y1），直线的参数方程为：
直线的扫描转换——数值微分法
第19页，本讲稿共58页
直线的扫描转换——数值微分法
DDA算法的原理：由于直线的一阶导数是连续的，且x和y是成比例的，因此可以通过在当前位置( xi , yi)分别加上两个小增量 Hx 和 H y（其中为无穷小的正数）来求出下一个点( xi+1, yi+1)的坐标。
式中，i=0, 1, 2 … , n-1，
第20页，本讲稿共58页
直线的扫描转换——数值微分法
当精度无限高的情况下，绘制出的直线无限接近理想直线。这种理想情况不可能出现（因为设备的精度有限）也没必要追求，因此通常增量系数的取值为：
第21页，本讲稿共58页
绘制直线时，要确定一个方向的增量为单位增量，即确定画线的基本步进方向，另一个方向的增量由直线的斜率决定。确定基本步进方向的依据是理想直线的斜率k。
通常设：
当直线斜率小于或等于1，x方向为基本步进方向，即x=1，y的值由直线的斜率决定。
当直线斜率大于1，y为基本步进方向，即y=1，x的值由直线的斜率决定。
直线的扫描转换——数值微分法
第22页，本讲稿共58页
DDA算法的坐标迭代公式：
情况一：当 ， 即 时，有：
直线的扫描转换——数值微分法
第23页，本讲稿共58页
情况二：当 ，即 时，有：
直线的扫描转换——数值微分法
第24页，本讲稿共58页
直线的扫描转换——数值微分法
需要注意的是：由于在光栅化过程中，绘制点的最小单位是1，因此对求出的xi+1和yi+1的值需要进行四舍五入。
DDA算法是一种增量算法，优点是直观、易于实现；
缺点是要做浮点运算和舍入取整，不利于硬件实现。
第25页，本讲稿共58页
直线的扫描转换——数值微分法
斜率<=1时，以x为基本步进方向，x方向每次步进增量为1。
斜率>1时，以y为基本步进方向，y方向每次步进增量为1。
第26页，本讲稿共58页
直线的扫描转换——数值微分法
void dda_line(float x0,float y0,float x1,float y1)
{
int i,epsl;
float xincre,yincre,x,y;
epsl=max(abs(x1-x0),abs(y1-y0));
xincre=(x1-x0)/epsl;
yincre=(y1-y0)/epsl;
x=x0;
y=y0;
for(i=1;i<=epsl;i++)
{
drawPoint(int(x+),int(y+)); //四舍五入取整
x=x+xincre;
y=y+yincre;
}
}
第27页，本讲稿共58页
直线的扫描转换——Bresenham算法
Bresenham提出的直线生成算法基本原理为：在某一计长方向上，每次变化一个单位步长或一个象素单位，另一个方向上是否走步取决于误差项。
计长方向由直线的斜率k决定。当0<=k<=1时，x为计长方向；当k>1时，y为计长方向。
关键问题是如何生成误差项判断条件。
第28页，本讲稿共58页
直线的扫描转换——中点Bresenham算法
中点Bresenham算法依据直线的斜率截距方程。设直线的斜率为k，截距为b；直线的斜率、截距方程为：
F(x, y) =y- kx – b=0
当直线经过端点P0(