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

基本图形生成算法直线圆弧第一页，共五十八页，2022年，8月28日

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

的正负，因此将公式简化如下：直线的扫描转换——逐点比较法第十二页，共五十八页，2022年，8月28日设当前位置为Mi（xi，yi），则计算偏差的函数为从偏差函数可知，光标每移动一个点，就要与理想直线的终点坐标进行计算、比较，然后确定下一步走笔的方向和步长的增量，这样绘制直线效率必然会很低，因此要对偏差函数进行简化。有效的方法是利用前一个点的偏差来推算下一个点的偏差值，这种方法称为递推法。直线的扫描转换——逐点比较法第十三页，共五十八页，2022年，8月28日例如已知前一个点的偏差值FiP0，说明点在理想直线的上方，画笔应该沿+x方向移动一个步长；反之，则应该沿+y向移动一个步长。开始绘制直线时，光标位于理想直线的起点，因此始终有F0=0。直线的扫描转换——逐点比较法第十四页，共五十八页，2022年，8月28日

若FiP0，表示第i点在直线上方，则有xi+1＝xi＋1（其中1为步长）

yi+1＝yi，第i+1点的偏差判别式为：将递推法用数学的方法表示为：设当前位置为Mi（xi，yi），下一个点位置为Mi+1（xi+1，yi+1）直线的扫描转换——逐点比较法求偏差的基本公式：第十五页，共五十八页，2022年，8月28日将递推法用数学的方法表示为：若Fi<0，表示第i点在直线下方，则有xi+1＝xi

yi+1＝yi＋1

（其中1为步长），即第i+1点的偏差判别式为：直线的扫描转换——逐点比较法求偏差的基本公式：第十六页，共五十八页，2022年，8月28日直线段位置偏差值FkP0偏差值Fk<0第一象限走笔+XFk+1=Fk-|yA|走笔+YFk+1=Fk+|xA|第三象限走笔-X走笔-Y第二象限走笔+YFk+1=Fk-|xA|走笔-XFk+1=Fk+|yA|第四象限走笔-Y走笔+X各象限的判别式直线的扫描转换——逐点比较法逐点比较法绘制直线.doc第十七页，共五十八页，2022年，8月28日【注】递推公式的作用：

意义：简化计算过程，提高效率。

原则：尽可能以加减法代替乘除法。

方法：用当前点的偏差推算出走笔方向，并计算出下一步的偏差；再以画笔的当前位置重复上述过程，推算出画笔下一步的动作。第十八页，共五十八页，2022年，8月28日数值微分法（DigitalDifferentialAnalyzer）简称DDA法，利用直线的微分方程生成直线的方法。设直线的端点坐标为（X0，Y0）和（X1，Y1），直线的参数方程为：直线的扫描转换——数值微分法第十九页，共五十八页，2022年，8月28日直线的扫描转换——数值微分法DDA算法的原理：由于直线的一阶导数是连续的，且x和y是成比例的，因此可以通过在当前位置(xi,yi)分别加上两个小增量Hx

和H

y（其中为无穷小的正数）来求出下一个点(xi+1,yi+1)的坐标。式中，i=0,1,2

…,n-1，第二十页，共五十八页，2022年，8月28日直线的扫描转换——数值微分法当精度无限高的情况下，绘制出的直线无限接近理想直线。这种理想情况不可能出现（因为设备的精度有限）也没必要追求，因此通常增量系数的取值为：第二十一页，共五十八页，2022年，8月28日绘制直线时，要确定一个方向的增量为单位增量，即确定画线的基本步进方向，另一个方向的增量由直线的斜率决定。确定基本步进方向的依据是理想直线的斜率k。通常设：当直线斜率小于或等于1，x方向为基本步进方向，即x=1，y的值由直线的斜率决定。当直线斜率大于1，y为基本步进方向，即y=1，x的值由直线的斜率决定。直线的扫描转换——数值微分法第二十二页，共五十八页，2022年，8月28日DDA算法的坐标迭代公式：情况一：当，即时，有：直线的扫描转换——数值微分法第二十三页，共五十八页，2022年，8月28日情况二：当，即时，有：直线的扫描转换——数值微分法第二十四页，共五十八页，2022年，8月28日直线的扫描转换——数值微分法需要注意的是：由于在光栅化过程中，绘制点的最小单位是1，因此对求出的xi+1和yi+1的值需要进行四舍五入。DDA算法是一种增量算法，优点是直观、易于实现；缺点是要做浮点运算和舍入取整，不利于硬件实现。第二十五页，共五十八页，2022年，8月28日直线的扫描转换——数值微分法斜率<=1时，以x为基本步进方向，x方向每次步进增量为1。斜率>1时，以y为基本步进方向，y方向每次步进增量为1。第二十六页，共五十八页，2022年，8月28日直线的扫描转换——数值微分法voiddda_line(floatx0,floaty0,floatx1,floaty1){inti,epsl;floatxincre,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;y=y+yincre;}}第二十七页，共五十八页，2022年，8月28日直线的扫描转换——Bresenham算法Bresenham提出的直线生成算法基本原理为：在某一计长方向上，每次变化一个单位步长或一个象素单位，另一个方向上是否走步取决于误差项。计长方向由直线的斜率k决定。当0<=k<=1时，x为计长方向；当k>1时，y为计长方向。关键问题是如何生成误差项判断条件。第二十八页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法中点Bresenham算法依据直线的斜率截距方程。设直线的斜率为k，截距为b；直线的斜率、截距方程为：F(x,y)=y-kx–b=0当直线经过端点P0(X0,Y0)和P1(X1,Y1)时第二十九页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法符号说明：P——当前点；M——中点；Pd和Pu——下一步可能位置；Q——理想直线在x=xi+1位置上的点；第三十页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法算法说明：设直线斜率在0~1之间，且位于第一象限。光标走步规则为：每次在x方向上加1，y方向根据误差项判断，或加1或加0。第三十一页，共五十八页，2022年，8月28日直线的扫描转换——中点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;第三十二页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法直线方程为：要判断点M与直线的位置关系，只需要把M的坐标代入直线方程，若：F(xM,yM)=0，即点M在直线上；F(xM,yM)>0，即点M在直线上方；F(xM,yM)<0，即点M在直线下方；第三十三页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法点M与点Q误差项d判别式推导：当di<0时，M在直线下方，Pu(即yi+1=yi+1点)为下一个点；当di>=0时，M在直线上方或在直线上，Pd(即yi+1=yi点)为下一个点。根据递推思想，推导出di与di+1的关系。第三十四页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法当di<0时，xi+1=xi+1;yi+1=yi+1;则有：第三十五页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法当di>=0时，xi+1=xi+1;yi+1=yi;则有d的初值：绘制直线时，光点最初在直线的起点P0(x0,y0)处，可推导出：d0=0.5-k第三十六页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法直线的斜率k=dy/dx，将斜率带入判别式：当di<0时，则有当di>=0时，则有d的初值：di的正负决定下一个点的位置，与di的具体数值无关，因此，统一以2dxHdi替代di，以简化判别式。第三十七页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法当di<0时，则有当di>=0时，则有d的初值：因此在代码中最终用到的判别式为：第三十八页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法绘制点(x,y)yesno第三十九页，共五十八页，2022年，8月28日直线的扫描转换——中点Bresenham算法上述推导的中点Bresenham算法绘制直线的判别式适用于直线斜率在0~1之间的情况。观察例mid_bresenham.cpp绘制斜率在0~1之间的直线和斜率大于1的直线。当直线大于1时，可不必重新推导判别式，只需交换x和y的规则。bresenham.cpp第四十页，共五十八页，2022年，8月28日直线的扫描转换——Bresenham算法中点Bresenham算法的误差项判别式需要用到直线斜率，改进后的Bresenham算法，思路保持不变，对误差项判别式进行简化。Bresenham算法直接比较距离t和s的大小，来确定下一个绘制的像素。第四十一页，共五十八页，2022年，8月28日推导、简化后得到的误差项判别式为：当di>=0时，xi+1=xi+1;yi+1=yi+1;有直线的扫描转换——Bresenham算法当di<0时，xi+1=xi+1;yi+1=yi;则有第四十二页，共五十八页，2022年，8月28日从推导得出的确定画笔下一步位置的公式可以看出，Bresenham算法中只包括加法、减法和乘2的操作，所需要的计算量很小。Bresenham算法不仅用于绘制直线，也可用于显示圆和其他曲线的整数增量计算，应用很广泛。直线的扫描转换——Bresenham算法第四十三页，共五十八页，2022年，8月28日例程分析：bresenham.cpp几个重要变量说明：dt——误差项，对应判别式d;tx、ty——x、y方向的增量，取值可为-1、0、1;interchange——记录直线斜率情况。当斜率>1时，该变量取值1；当斜率<=1时，该变量取值0。直线的扫描转换——Bresenham算法第四十四页，共五十八页，2022年，8月28日圆的扫描转换给出圆心(xc,yc)和半径r，逐点绘制圆的方式有：一、利用直角坐标方程利用直角坐标方程绘制圆弧思路清楚，但计算涉及开方运算，计算量大。更大的缺点是，由于y不是x的线性函数，因此，当x取值从0到r均匀递增时，y的值变化极不均匀，尤其当x接近r时，绘制出来的圆会出现较大的间断。第四十五页，共五十八页，2022年，8月28日圆的扫描转换二、利用圆的参数方程利用参数方程绘制圆弧可以克服直角坐标方程画圆的弊端。参数为圆周角，当圆周角按固定增量变化时，能获得均匀分布在圆周上的点。第四十六页，共五十八页，2022年，8月28日圆的扫描转换但是，利用圆的参数方程绘制圆弧有两个严重缺陷：一、每次求点坐标都需要计算三角函数，计算量大，效率低。二、t增量的大小与半径相关。如，若t取某一定值，当半径很小时，计算出来的像素可能会重叠（相邻像素的x和y的增量都不于1）；而当半径较大时，有可能会造成圆弧出现断开现象（相邻像素的x和y的增量过大）。观察例程“参数方程画圆”第四十七页，共五十八页，2022年，8月28日圆的扫描转换——八分法画圆圆心位于原点的圆有四条对称轴线：若已知圆周上任意一点，可以利用圆的对称性得到另外七个点的坐标，从而得到整个圆的转换扫描像素集。第四十八页，共五十八页，2022年，8月28日圆的扫描转换——八分法画圆drawPoint(xc+x,yc+y);//画点AdrawPoint(xc-x,yc+y);//画点A7drawPoint(xc+x,yc-y);//画点A3drawPoint(xc-x,yc-y);//画点A4drawPoint(xc+y,yc+x);//画点A1drawPoint(xc-y,yc+x);//画点A2drawPoint(xc+y,yc-x);//画点A6drawPoint(xc-y,yc-x);//画点A5第四十九页，共五十八页，2022年，8月28日圆的扫描转换——中点Bresenham算法中点Bresenham法求圆弧上的点思路与直线绘制相同。考虑圆心在原点，位于图示区域的八分之一圆弧。中点Bresenham画圆算法按照从点(0,0)到点顺时针确定最佳逼近理想圆弧的像素序列。第五十页，共五十八页，2022年，8月28日圆的扫描转换——中点Bresenham算法算法基本原理：x为基本步进方向。每一次沿x方向走一步，y方向坐标或减1，或减0。当前点为P，下一步的中点为M。如果点M在圆内，则Pu为下一个点，即y方向坐标减0；如果点M在圆外，则Pd为下一个点，即y方向坐标减1。第五十一页，共五十八页，2022年，8月28日圆的扫描转换——中点Bresenham算法设当前点为P(xi,yi)，则有点M(xi+1,yi-0.5)。构造误差项判别式：若di<0，下一个点为Pu(xi+1,yi)；否则下一个点为Pd(xi+1,yi-1)；第五十二页，共五十八页，2022年，8月28日圆的扫描转换——中点Bresenham算法误差项判别式的递推公式：当di<0时，此时有xi+1=xi+1，yi+1=yi当di>=0时，此时有xi+1=xi+1，yi+1=yi-1第五十三页，共五十八页，2022年，8月28日圆