文档介绍：基本图形生成算法直线圆弧
第一页，共58页
通常认为，基本二维图形包括点、直线、圆、椭圆、多边形域和字符串等。复杂曲线及各种复杂图形均可由直线段和圆弧来拟合，因此研究直线和圆弧的生成算法是二维图形生成技术的基础。
第二页，共58页
在光栅显示器生成一个对象，实质上是往帧缓冲区的相应单元中写入数据；如画一条直线，实质上是发现最佳逼近直线的像素序列、并填入相应颜色的过程，这个过程称为直线的光栅化，或者称为直线的扫描转换。
第三页，共58页
“发现最佳逼近直线的像素序列”就是发现直线生成的算法。不同的算法有不同的效率，但各种算法的核心都是围绕着判别和生成x、y增量的过程和方法（走笔规则）展开研究的。
第四页，共58页
通常从以下四方面评价直线扫描转换算法的质量：
一、显示像素点应尽量靠近理想直线，直线要直，走样小；
二、直线端点准确，且绘制无定向性，即以哪一个端点为绘制起点得到的线段应重合；
三、直线的亮度和色泽要均匀，避免造成视觉上一段亮一段暗的感觉。这通过所绘制的像素点密度保持均匀来实现；
四、画线速度尽可能快，即算法效率要高。
第五页，共58页
直线的扫描转换
常用的直线生成算法有逐点比较法、正负法、数值微分法和Bresenham算法等。
简介逐点比较法
详细介绍数值微分法和Bresenham算法。
第六页，共58页
算法的判断规则——在绘图过程中，画笔每走一步，就要与理想图形进行比较，然后决定下一步的走向，用步步逼近的方法画出指定起止点间的直线段。
直线的扫描转换——逐点比较法
第七页，共58页
走笔约定——以第一象限为例。当画笔（光标当前位置）位于理想直线上方，则横向走笔，即画笔沿x方向移动一个单位；当画笔位于理想直线下方时，则纵向走笔，即画笔沿y方向移动一个单位。
直线的扫描转换——逐点比较法
第八页，共58页
要确定画线时光标移动的方向，必须要知道当前光标点与理想直线的位置关系。位置关系通过坐标的偏差来决定。
以第一象限为例分析逐点比较法的偏差计算过程。
直线的扫描转换——逐点比较法
第九页，共58页
设要绘制的直线为OA（即理想直线），当前点为M，当前点与理想直线的相对位置（即点M在OA的上方或下方）用偏差值 的正负来判断。 的计算公式为：
直线的扫描转换——逐点比较法
tan函数在是单调递增函数，因此 的正负体现b 和a 的大小。
第十页，共58页