基本图形生成算法-直线圆弧

《基本图形生成算法-直线圆弧》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、通常认为，基本二维图形包括点、直线、圆、椭圆、多边形域和字符串等。复杂曲线及各种复杂图形均可由直线段和圆弧来拟合，因此研究直线和圆弧的生成算法是二维图形生成技术的基础。在光栅显示器生成一个对象，实质上是往帧缓冲区的相应单元中写入数据；如画一条直线，实质上是发现最佳逼近直线的像素序列、并填入相应颜色的过程，这个过程称为直线的光栅化，或者称为直线的扫描转换。“发现最佳逼近直线的像素序列”就是发现直线生成的算法。不同的算法有不同的效率，但各种算法的核心都是围绕着判别和生成x、y增量的过程和方法（走笔规则）展开研究的。通常从

2、以下四方面评价直线扫描转换算法的质量：一、显示像素点应尽量靠近理想直线，直线要直，走样小；二、直线端点准确，且绘制无定向性，即以哪一个端点为绘制起点得到的线段应重合；三、直线的亮度和色泽要均匀，避免造成视觉上一段亮一段暗的感觉。这通过所绘制的像素点密度保持均匀来实现；四、画线速度尽可能快，即算法效率要高。直线的扫描转换常用的直线生成算法有逐点比较法、正负法、数值微分法和Bresenham算法等。简介逐点比较法详细介绍数值微分法和Bresenham算法。算法的判断规则——在绘图过程中，画笔每走一步，就要与理想图形进行比

3、较，然后决定下一步的走向，用步步逼近的方法画出指定起止点间的直线段。直线的扫描转换——逐点比较法走笔约定——以第一象限为例。当画笔（光标当前位置）位于理想直线上方，则横向走笔，即画笔沿x方向移动一个单位；当画笔位于理想直线下方时，则纵向走笔，即画笔沿y方向移动一个单位。直线的扫描转换——逐点比较法要确定画线时光标移动的方向，必须要知道当前光标点与理想直线的位置关系。位置关系通过坐标的偏差来决定。以第一象限为例分析逐点比较法的偏差计算过程。直线的扫描转换——逐点比较法设要绘制的直线为OA（即理想直线），当前点为M，当前

4、点与理想直线的相对位置（即点M在OA的上方或下方）用偏差值的正负来判断。的计算公式为：直线的扫描转换——逐点比较法tan函数在是单调递增函数，因此的正负体现b和a的大小。偏差与走笔的关系分析：当<0时，角b

5、偏差的函数为从偏差函数可知，光标每移动一个点，就要与理想直线的终点坐标进行计算、比较，然后确定下一步走笔的方向和步长的增量，这样绘制直线效率必然会很低，因此要对偏差函数进行简化。有效的方法是利用前一个点的偏差来推算下一个点的偏差值，这种方法称为递推法。直线的扫描转换——逐点比较法例如已知前一个点的偏差值FiP0，说明点在理想直线的上方，画笔应该沿+x方向移动一个步长；反之，则应该沿+y向移动一个步长。开始绘制直线时，光标位于理想直线的起点，因此始终有F0=0。直线的扫描转换——逐点比较法若FiP0，表示第i点在直线上

6、方，则有xi+1＝xi＋1（其中1为步长）yi+1＝yi，第i+1点的偏差判别式为：将递推法用数学的方法表示为：设当前位置为Mi（xi，yi），下一个点位置为Mi+1（xi+1，yi+1）直线的扫描转换——逐点比较法求偏差的基本公式：将递推法用数学的方法表示为：若Fi<0，表示第i点在直线下方，则有xi+1＝xiyi+1＝yi＋1（其中1为步长），即第i+1点的偏差判别式为：直线的扫描转换——逐点比较法求偏差的基本公式：直线段位置偏差值FkP0偏差值Fk<0第一象限走笔+XFk+1=Fk-

7、yA

8、走笔+YFk+1=F

9、k+

10、xA

11、第三象限走笔-X走笔-Y第二象限走笔+YFk+1=Fk-

12、xA

13、走笔-XFk+1=Fk+

14、yA

15、第四象限走笔-Y走笔+X各象限的判别式直线的扫描转换——逐点比较法逐点比较法绘制直线.doc【注】递推公式的作用：意义：简化计算过程，提高效率。原则：尽可能以加减法代替乘除法。方法：用当前点的偏差推算出走笔方向，并计算出下一步的偏差；再以画笔的当前位置重复上述过程，推算出画笔下一步的动作。数值微分法（DigitalDifferentialAnalyzer）简称DDA法，利用直线的微分方程生成直线的方法。设直线的

16、端点坐标为（X0，Y0）和（X1，Y1），直线的参数方程为：直线的扫描转换——数值微分法直线的扫描转换——数值微分法DDA算法的原理：由于直线的一阶导数是连续的，且x和y是成比例的，因此可以通过在当前位置(xi,yi)分别加上两个小增量Hx和Hy（其中为无穷小的正数）来求出下一个点(xi+1,yi+1)的坐标。式中，i=0,1,2