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