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

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

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

3、位置）位于理想直线上方，则横向走笔，即画笔沿x方向移动一个单位；当画笔位于理想直线下方时，则纵向走笔，即画笔沿y方向移动一个单位。,直线的扫描转换逐点比较法,要确定画线时光标移动的方向，必须要知道当前光标点与理想直线的位置关系。位置关系通过坐标的偏差来决定。 以第一象限为例分析逐点比较法的偏差计算过程。,直线的扫描转换逐点比较法,设要绘制的直线为OA（即理想直线），当前点为M，当前点与理想直线的相对位置（即点M在OA的上方或下方）用偏差值 的正负来判断。 的计算公式为：,直线的扫描转换逐点比较法,tan函数在是单调递增函数，因此 的正负体现b 和a 的大小。,偏差与走笔的关系分析： 当 0时，

4、角b a，点M在理想直线下方，按约定，画笔应向上（+y）走一步； 当P0时，角bPa ，点M在理想直线上方或在直线上，按约定，画笔应向右（+x）走一步。,直线的扫描转换逐点比较法,从计算偏差值的公式,可知，分子的正负决定 的正负，因此将公式简化如下：,直线的扫描转换逐点比较法,设当前位置为Mi（xi，yi），则计算偏差的函数为,从偏差函数可知，光标每移动一个点，就要与理想直线的终点坐标进行计算、比较，然后确定下一步走笔的方向和步长的增量，这样绘制直线效率必然会很低，因此要对偏差函数进行简化。 有效的方法是利用前一个点的偏差来推算下一个点的偏差值，这种方法称为递推法。,直线的扫描转换逐点比较法,

5、例如已知前一个点的偏差值FiP0，说明点在理想直线的上方，画笔应该沿+x方向移动一个步长；反之，则应该沿+y向移动一个步长。 开始绘制直线时，光标位于理想直线的起点，因此始终有F0=0。,直线的扫描转换逐点比较法,若FiP0，表示第i点在直线上方， 则有xi+1 xi1（其中1为步长） yi+1 yi， 第i+1点的偏差判别式为：,将递推法用数学的方法表示为： 设当前位置为Mi（xi，yi）， 下一个点位置为Mi+1（xi+1，yi+1）,直线的扫描转换逐点比较法,求偏差的基本公式：,将递推法用数学的方法表示为： 若Fi0，表示第i点在直线下方， 则有xi+1 xi yi+1 yi 1 （其中

6、1为步长）， 即第i+1点的偏差判别式为：,直线的扫描转换逐点比较法,求偏差的基本公式：,各象限的判别式,直线的扫描转换逐点比较法,逐点比较法绘制直线.doc,【注】递推公式的作用： 意义：简化计算过程，提高效率。 原则：尽可能以加减法代替乘除法。 方法：用当前点的偏差推算出走笔方向，并计算出下一步的偏差；再以画笔的当前位置重复上述过程，推算出画笔下一步的动作。,数值微分法（Digital Differential Analyzer） 简称DDA法，利用直线的微分方程生成直线的方法。,设直线的端点坐标为（X0，Y0）和（X1，Y1），直线的参数方程为：,直线的扫描转换数值微分法,直线的扫描转换

7、数值微分法,DDA算法的原理：由于直线的一阶导数是连续的，且x和y是成比例的，因此可以通过在当前位置( xi , yi)分别加上两个小增量 Hx 和 H y（其中为无穷小的正数）来求出下一个点( xi+1, yi+1)的坐标。,式中，i=0, 1, 2 , n-1，,直线的扫描转换数值微分法,当精度无限高的情况下，绘制出的直线无限接近理想直线。这种理想情况不可能出现（因为设备的精度有限）也没必要追求，因此通常增量系数的取值为：,绘制直线时，要确定一个方向的增量为单位增量，即确定画线的基本步进方向，另一个方向的增量由直线的斜率决定。确定基本步进方向的依据是理想直线的斜率k。 通常设： 当直线斜率

8、小于或等于1，x方向为基本步进方向，即x=1，y的值由直线的斜率决定。 当直线斜率大于1，y为基本步进方向，即y=1，x的值由直线的斜率决定。,直线的扫描转换数值微分法,DDA算法的坐标迭代公式： 情况一：当 ， 即 时，有：,直线的扫描转换数值微分法,情况二：当 ，即 时，有：,直线的扫描转换数值微分法,直线的扫描转换数值微分法,需要注意的是：由于在光栅化过程中，绘制点的最小单位是1，因此对求出的xi+1和yi+1的值需要进行四舍五入。,DDA算法是一种增量算法，优点是直观、易于实现； 缺点是要做浮点运算和舍入取整，不利于硬件实现。,直线的扫描转换数值微分法,斜率=1时，以x为基本步进方向，

9、x方向每次步进增量为1。,斜率1时，以y为基本步进方向，y方向每次步进增量为1。,直线的扫描转换数值微分法,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+0.5),int(y+0.5); /四舍五入取整 x=x+xincre;

10、y=y+yincre; ,直线的扫描转换Bresenham算法,Bresenham提出的直线生成算法基本原理为：在某一计长方向上，每次变化一个单位步长或一个象素单位，另一个方向上是否走步取决于误差项。 计长方向由直线的斜率k决定。当01时，y为计长方向。 关键问题是如何生成误差项判断条件。,直线的扫描转换中点Bresenham算法,中点Bresenham算法依据直线的斜率截距方程。设直线的斜率为k，截距为b；直线的斜率、截距方程为：,F(x, y) =y- kx b=0,当直线经过端点P0(X0, Y0) 和P1(X1, Y1)时,直线的扫描转换中点Bresenham算法,符号说明： P当前点

11、； M中点； Pd和Pu下一步可能位置； Q理想直线在x=xi+1位置上的点；,直线的扫描转换中点Bresenham算法,算法说明： 设直线斜率在01之间，且位于第一象限。光标走步规则为：每次在x方向上加1，y方向根据误差项判断，或加1或加0。,直线的扫描转换中点Bresenham算法,误差项判别式构造： 当前点P，下一个点可能为Pd (即yi+1=yi点) ，可能为Pu (即yi+1=yi+1点)。M为Pd 与Pu的中点。 若M在Q点下方，说明Pu点离直线近，则有yi+1=yi+1; 若M在Q点上方，说明Pd点离直线近，则有yi+1=yi;,直线的扫描转换中点Bresenham算法,直线方程

12、为： 要判断点M与直线的位置关系，只需要把M的坐标代入直线方程，若： F(xM, yM)=0，即点M在直线上； F(xM, yM)0，即点M在直线上方； F(xM, yM)0，即点M在直线下方；,直线的扫描转换中点Bresenham算法,点M与点Q误差项d判别式推导：,当di=0时，M在直线上方或在直线上，Pd (即yi+1=yi点)为下一个点。 根据递推思想，推导出di与di+1的关系。,直线的扫描转换中点Bresenham算法,当di0时，xi+1=xi+1; yi+1=yi+1; 则有：,直线的扫描转换中点Bresenham算法,当di=0时，xi+1=xi+1; yi+1=yi; 则有

13、,d的初值：绘制直线时，光点最初在直线的起点P0(x0, y0)处，可推导出：d0=0.5-k,直线的扫描转换中点Bresenham算法,直线的斜率k=dy/dx，将斜率带入判别式：,当di0时，则有,当di=0时，则有,d的初值：,di的正负决定下一个点的位置，与di 的具体数值无关，因此，统一以2dxHdi替代di，以简化判别式。,直线的扫描转换中点Bresenham算法,当di0时，则有,当di=0时，则有,d的初值：,因此在代码中最终用到的判别式为：,直线的扫描转换中点Bresenham算法,绘制点(x, y),yes,no,直线的扫描转换中点Bresenham算法,上述推导的中点Br

14、esenham算法绘制直线的判别式适用于直线斜率在01之间的情况。 观察例mid_bresenham.cpp绘制斜率在01之间的直线和斜率大于1的直线。 当直线大于1时，可不必重新推导判别式，只需交换x和y的规则。bresenham.cpp,直线的扫描转换Bresenham算法,中点Bresenham算法的误差项判别式需要用到直线斜率，改进后的Bresenham算法，思路保持不变，对误差项判别式进行简化。,Bresenham算法直接比较距离t和s的大小，来确定下一个绘制的像素。,推导、简化后得到的误差项判别式为： 当di=0时，xi+1=xi+1; yi+1=yi+1; 有,直线的扫描转换Br

15、esenham算法,当di0时，xi+1=xi+1; yi+1=yi; 则有,从推导得出的确定画笔下一步位置的公式可以看出，Bresenham算法中只包括加法、减法和乘2的操作，所需要的计算量很小。 Bresenham算法不仅用于绘制直线，也可用于显示圆和其他曲线的整数增量计算，应用很广泛。,直线的扫描转换Bresenham算法,例程分析：bresenham.cpp 几个重要变量说明： dt误差项，对应判别式d; tx、tyx、y方向的增量，取值可为-1、0、1; interchange记录直线斜率情况。当斜率1时，该变量取值1；当斜率=1时，该变量取值0。,直线的扫描转换Bresenham算

16、法,圆的扫描转换,给出圆心(xc , yc)和半径r，逐点绘制圆的方式有： 一、利用直角坐标方程,利用直角坐标方程绘制圆弧思路清楚，但计算涉及开方运算，计算量大。更大的缺点是，由于y不是x的线性函数，因此，当x取值从0到r均匀递增时，y的值变化极不均匀，尤其当x接近r时，绘制出来的圆会出现较大的间断。,圆的扫描转换,二、利用圆的参数方程,利用参数方程绘制圆弧可以克服直角坐标方程画圆的弊端。参数为圆周角，当圆周角按固定增量变化时，能获得均匀分布在圆周上的点。,圆的扫描转换,但是，利用圆的参数方程绘制圆弧有两个严重缺陷： 一、每次求点坐标都需要计算三角函数，计算量大，效率低。 二、t 增量的大小与

17、半径相关。如，若t 取某一定值，当半径很小时，计算出来的像素可能会重叠（相邻像素的x和y的增量都不于1）；而当半径较大时，有可能会造成圆弧出现断开现象（相邻像素的x和y的增量过大） 。 观察例程“参数方程画圆”,圆的扫描转换八分法画圆,圆心位于原点的圆有四条对称轴线：,若已知圆周上任意一点，可以利用圆的对称性得到另外七个点的坐标，从而得到整个圆的转换扫描像素集。,圆的扫描转换八分法画圆,drawPoint(xc+x,yc+y); /画点A drawPoint(xc-x,yc+y); /画点A7 drawPoint(xc+x,yc-y); /画点A3 drawPoint(xc-x,yc-y);

18、/画点A4 drawPoint(xc+y,yc+x); /画点A1 drawPoint(xc-y,yc+x); /画点A2 drawPoint(xc+y,yc-x); /画点A6 drawPoint(xc-y,yc-x); /画点A5,圆的扫描转换中点Bresenham算法,圆的扫描转换中点Bresenham算法,算法基本原理： x为基本步进方向。每一次沿x方向走一步，y方向坐标或减1，或减0。 当前点为P，下一步的中点为M。如果点M在圆内，则Pu为下一个点，即y方向坐标减0；如果点M在圆外，则Pd为下一个点，即y方向坐标减1。,圆的扫描转换中点Bresenham算法,设当前点为P(xi, yi)，则有点M(xi+1, yi-0.5)。 构造误差项判别式：,若di0，下一个点为Pu(xi+1, yi)； 否则下一个点为Pd(xi+1, yi-1)；,圆的扫描转换中点Bresenham算法,误差项判别式的递推公式： 当di0时，此时有xi+1=xi+1，yi+1=yi,当di=0时，此时有xi+1=xi+1，yi+1=yi-1,圆的扫描转换中点Bresenham算法,误差项的初值：