基本图形生成算法直线圆弧优秀课件.ppt

基本图形生成算法直线圆弧第1页，本讲稿共58页 通常认为，基本二维图形包括点、直线、圆、椭圆、多边形域和字符串等。复杂曲线及各种复杂图形均可由直线段和圆弧来拟合，因此研究直线和圆弧的生成算法是二维图形生成技术的基础。第2页，本讲稿共58页在光栅显示器生成一个对象，实质上是往帧缓冲区的相应单元中写入数据；如画一条直线，实质上是发现最佳逼近直线的像素序列、并填入相应颜色的过程，这个过程称为直线的光栅化，或者称为直线的扫描转换。第3页，本讲稿共58页“发现最佳逼近直线的像素序列发现最佳逼近直线的像素序列”就是发现直线生成的算法就是发现直线生成的算法。不同的算法有不同的效率，但各种算法的。不同的算法有不同的效率，但各种算法的核心都是围绕着核心都是围绕着判别和生成判别和生成x、y增量的过程和方法（走笔规则）增量的过程和方法（走笔规则）展开研究的。展开研究的。第4页，本讲稿共58页通常从以下四方面评价直线扫描转换算法的质量：一、显示像素点应尽量靠近理想直线，直线要直，走样小；二、直线端点准确，且绘制无定向性，即以哪一个端点为绘制起点得到的线段应重合；三、直线的亮度和色泽要均匀，避免造成视觉上一段亮一段暗的感觉。这通过所绘制的像素点密度保持均匀来实现；四、画线速度尽可能快，即算法效率要高。第5页，本讲稿共58页直线的扫描转换常用的直线生成算法有逐点比较法、正负法、数值微分法和Bresenham算法等。简介逐点比较法详细介绍数值微分法和Bresenham算法。第6页，本讲稿共58页算法的判断规则算法的判断规则在绘图过程中，画笔每走一步，就要与理想图在绘图过程中，画笔每走一步，就要与理想图形进行比较，然后决定下一步的走向，用步步逼近的方法画出指定形进行比较，然后决定下一步的走向，用步步逼近的方法画出指定起止点间的直线段。起止点间的直线段。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第7页，本讲稿共58页走笔约定走笔约定以第一象限为例。以第一象限为例。当画笔（光标当前位置）位于当画笔（光标当前位置）位于理想直线上方，则横向走笔，理想直线上方，则横向走笔，即画笔沿即画笔沿x x方向移动一个单位；方向移动一个单位；当画笔位于理想直线下方时，当画笔位于理想直线下方时，则纵向走笔，即画笔沿则纵向走笔，即画笔沿y y方向方向移动一个单位。移动一个单位。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第8页，本讲稿共58页要确定画线时光标移动的方向，必须要知道当前光标点与理想直线的位置关系。位置关系通过坐标的偏差来决定。以第一象限为例分析逐点比较法的偏差计算过程。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第9页，本讲稿共58页设要绘制的直线为OA（即理想直线），当前点为M，当前点与理想直线的相对位置（即点M在OA的上方或下方）用偏差值 的正负来判断。的计算公式为：直线的扫描转换直线的扫描转换逐点比较法逐点比较法tan函数在是单调递增函数，因此 的正负体现b 和a 的大小。第10页，本讲稿共58页偏差与走笔的关系分析：当 0时，角b a，点M在理想直线下方，按约定，画笔应向上（+y）走一步；当P0时，角bPa，点M在理想直线上方或在直线上，按约定，画笔应向右（+x）走一步。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第11页，本讲稿共58页从计算偏差值的公式可知，分子的正负决定 的正负，因此将公式简化如下：直线的扫描转换直线的扫描转换逐点比较法逐点比较法第12页，本讲稿共58页设当前位置为Mi（xi，yi），则计算偏差的函数为从偏差函数可知，光标每移动一个点，就要与理想直线的终点坐标进行计算、比较，然后确定下一步走笔的方向和步长的增量，这样绘制直线效率必然会很低，因此要对偏差函数进行简化。有效的方法是利用前一个点的偏差来推算下一个点的偏差值，这种方法称为递推法。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第13页，本讲稿共58页例如已知前一个点的偏差值FiP0，说明点在理想直线的上方，画笔应该沿+x方向移动一个步长；反之，则应该沿+y向移动一个步长。开始绘制直线时，光标位于理想直线的起点，因此始终有F0=0。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第14页，本讲稿共58页u 若FiP0，表示第i点在直线上方，则有xi+1 xi1（其中1为步长）yi+1 yi，第i+1点的偏差判别式为：将递推法用数学的方法表示为：设当前位置为Mi（xi，yi），下一个点位置为Mi+1（xi+1，yi+1）直线的扫描转换直线的扫描转换逐点比较法逐点比较法求偏差的基本公式：第15页，本讲稿共58页将递推法用数学的方法表示为：u 若Fi0，表示第i点在直线下方，则有xi+1 xi yi+1 yi 1（其中1为步长），即第i+1点的偏差判别式为：直线的扫描转换直线的扫描转换逐点比较法逐点比较法求偏差的基本公式：第16页，本讲稿共58页直线段位置偏差值FkP0偏差值Fk0第一象限走笔+XFk+1=Fk-|yA|走笔+YFk+1=Fk+|xA|第三象限走笔-X走笔-Y第二象限走笔+YFk+1=Fk-|xA|走笔-XFk+1=Fk+|yA|第四象限走笔-Y走笔+X各象限的判别式直线的扫描转换直线的扫描转换逐点比较法逐点比较法逐点比较法绘制直线.doc第17页，本讲稿共58页【注】递推公式的作用：意义：简化计算过程，提高效率。原则：尽可能以加减法代替乘除法。方法：用当前点的偏差推算出走笔方向，并计算出下一步的偏差；再以画笔的当前位置重复上述过程，推算出画笔下一步的动作。第18页，本讲稿共58页数值微分法（Digital Differential Analyzer）简称DDA法，利用直线的微分方程生成直线的方法。设直线的端点坐标为（X0，Y0）和（X1，Y1），直线的参数方程为：直线的扫描转换直线的扫描转换数值微分法数值微分法第19页，本讲稿共58页直线的扫描转换直线的扫描转换数值微分法数值微分法DDA算法的原理：由于直线的一阶导数是连续的，且x和y是成比例的，因此可以通过在当前位置(xi,yi)分别加上两个小增量 Hx 和 H y（其中为无穷小的正数）来求出下一个点(xi+1,yi+1)的坐标。式中，式中，i=0,1,2 ,n-1，第20页，本讲稿共58页直线的扫描转换直线的扫描转换数值微分法数值微分法当精度无限高的情况下，绘制出的直线无限接近理想直线。这种理想情况不可能出现（因为设备的精度有限）也没必要追求，因此通常增量系数的取值为：第21页，本讲稿共58页绘制直线时，要确定一个方向的增量为单位增量，即确定画线的基本步进方向，另一个方向的增量由直线的斜率决定。确定基本步进方向的依据是理想直线的斜率k。通常设：当直线斜率小于或等于1，x方向为基本步进方向，即x=1，y的值由直线的斜率决定。当直线斜率大于1，y为基本步进方向，即y=1，x的值由直线的斜率决定。直线的扫描转换直线的扫描转换数值微分法数值微分法第22页，本讲稿共58页DDA算法的坐标迭代公式：情况一：当 ，即 时，有：直线的扫描转换直线的扫描转换数值微分法数值微分法第23页，本讲稿共58页情况二：当 ，即 时，有：直线的扫描转换直线的扫描转换数值微分法数值微分法第24页，本讲稿共58页直线的扫描转换直线的扫描转换数值微分法数值微分法需要注意的是：由于在光栅化过程中，绘制点的最小单位是1，因此对求出的xi+1和yi+1的值需要进行四舍五入。DDA算法是一种增量算法，优点是直观、易于实现；缺点是要做浮点运算和舍入取整，不利于硬件实现。第25页，本讲稿共58页直线的扫描转换直线的扫描转换数值微分法数值微分法斜率1时，以y为基本步进方向，y方向每次步进增量为1。第26页，本讲稿共58页直线的扫描转换直线的扫描转换数值微分法数值微分法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;y=y+yincre;第27页，本讲稿共58页直线的扫描转换直线的扫描转换Bresenham算法算法Bresenham提出的直线生成算法基本原理为：在某一计长方向上，每次变化一个单位步长或一个象素单位，另一个方向上是否走步取决于误差项。计长方向由直线的斜率k决定。当0=k1时，y为计长方向。关键问题是如何生成误差项判断条件。第28页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法中点Bresenham算法依据直线的斜率截距方程。设直线的斜率为k，截距为b；直线的斜率、截距方程为：F(x,y)=y-kx b=0当直线经过端点P0(X0,Y0)和P1(X1,Y1)时第29页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法符号说明：符号说明：P当前点；当前点；M中点；中点；Pd和和Pu下一步可能位下一步可能位置；置；Q理想直线在理想直线在x=xi+1位置上的点；位置上的点；第30页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法算法说明：设直线斜率在01之间，且位于第一象限。光标走步规则为：每次在x方向上加1，y方向根据误差项判断，或加1或加0。第31页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点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;第32页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法直线方程为：要判断点M与直线的位置关系，只需要把M的坐标代入直线方程，若：F(xM,yM)=0，即点M在直线上；F(xM,yM)0，即点M在直线上方；F(xM,yM)0，即点M在直线下方；第33页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法点M与点Q误差项d判别式推导：当di=0时，M在直线上方或在直线上，Pd(即yi+1=yi点)为下一个点。根据递推思想，推导出di与di+1的关系。第34页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法当di=0时，xi+1=xi+1;yi+1=yi;则有d的初值：绘制直线时，光点最初在直线的起点P0(x0,y0)处，可推导出：d0=0.5-k第36页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法直线的斜率k=dy/dx，将斜率带入判别式：当di=0时，则有d的初值：di的正负决定下一个点的位置，与di 的具体数值无关，因此，统一以2dxHdi替代di，以简化判别式。第37页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法当di=0时，则有d的初值：因此在代码中最终用到的判别式为：第38页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法绘制点(x,y)yesno第39页，本讲稿共58页直线的扫描转换直线的扫描转换中点中点Bresenham算法算法上述推导的中点Bresenham算法绘制直线的判别式适用于直线斜率在01之间的情况。观察例mid_bresenham.cpp绘制斜率在01之间的直线和斜率大于1的直线。当直线大于1时，可不必重新推导判别式，只需交换x和y的规则。bresenham.cpp第40页，本讲稿共58页直线的扫描转换直线的扫描转换Bresenham算法算法中点Bresenham算法的误差项判别式需要用到直线斜率，改进后的Bresenham算法，思路保持不变，对误差项判别式进行简化。Bresenham算法直接比较距离t和s的大小，来确定下一个绘制的像素。第41页，本讲稿共58页推导、简化后得到的误差项判别式为：当di=0时，xi+1=xi+1;yi+1=yi+1;有直线的扫描转换直线的扫描转换Bresenham算法算法当di1时，时，该变量取值该变量取值1；当斜率；当斜率=1时，该变量取值时，该变量取值0。直线的扫描转换直线的扫描转换Bresenham算法算法第44页，本讲稿共58页圆的扫描转换给出圆心(xc,yc)和半径r，逐点绘制圆的方式有：一、利用直角坐标方程利用直角坐标方程绘制圆弧思路清楚，但计算涉及开方运算，计算量大。更大的缺点是，由于y不是x的线性函数，因此，当x取值从0到r均匀递增时，y的值变化极不均匀，尤其当x接近r时，绘制出来的圆会出现较大的间断。第45页，本讲稿共58页圆的扫描转换二、利用圆的参数方程利用参数方程绘制圆弧可以克服直角坐标方程画圆的弊端。参数为圆周角，当圆周角按固定增量变化时，能获得均匀分布在圆周上的点。第46页，本讲稿共58页圆的扫描转换但是，利用圆的参数方程绘制圆弧有两个严重缺陷：但是，利用圆的参数方程绘制圆弧有两个严重缺陷：一、每次求点坐标都需要计算三角函数，计算量大，效率低。一、每次求点坐标都需要计算三角函数，计算量大，效率低。二、二、t 增量的大小与半径相关。如，若增量的大小与半径相关。如，若t 取某一定值，当半径很小时，取某一定值，当半径很小时，计算出来的像素可能会重叠（相邻像素的计算出来的像素可能会重叠（相邻像素的x和和y的增量都不于的增量都不于1）；而当半）；而当半径较大时，有可能会造成圆弧出现断开现象（相邻像素的径较大时，有可能会造成圆弧出现断开现象（相邻像素的x和和y的增量过大）的增量过大）。观察例程观察例程“参数方程画圆参数方程画圆”第47页，本讲稿共58页圆的扫描转换圆的扫描转换八分法画圆八分法画圆圆心位于原点的圆有四条对称轴线：若已知圆周上任意一点，可以利用圆的对称性得到另外七个点的坐标，从而得到整个圆的转换扫描像素集。第48页，本讲稿共58页圆的扫描转换圆的扫描转换八分法画圆八分法画圆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第49页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法中点Bresenham法求圆弧上的点思路与直线绘制相同。考虑圆心在原点，位于图示区域的八分之一圆弧。中点Bresenham画圆算法按照从点(0,0)到点顺时针确定最佳逼近理想圆弧的像素序列。第50页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法算法基本原理：x为基本步进方向。每一次沿x方向走一步，y方向坐标或减1，或减0。当前点为P，下一步的中点为M。如果点M在圆内，则Pu为下一个点，即y方向坐标减0；如果点M在圆外，则Pd为下一个点，即y方向坐标减1。第51页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法设当前点为P(xi,yi)，则有点M(xi+1,yi-0.5)。构造误差项判别式：若di0，下一个点为Pu(xi+1,yi)；否则下一个点为Pd(xi+1,yi-1)；第52页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法误差项判别式的递推公式：当di=0时，此时有xi+1=xi+1，yi+1=yi-1第53页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法误差项的初值：开始绘制圆弧的第一个为理想圆弧上的P0(0,R)点，因此有判别项的初值为：为避免做浮点运算，用1取代1.25。造成误差项的初值有0.25的误差。因为绘制圆弧以一个像素为基本单位，0.25的舍去不会影响下一个点误差项的计算，因此初值为：第54页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法void bresenham_circle(int xc,int yc,int r)int x=0,y=r,d;d=1-r;while(x=y)drawPoint(xc+x,yc+y);if(d0)d+=2*x+3;else d+=2*(x-y)+5;y-;x+;第55页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法在第一象限y=x到y=0区域，以y为基本走步方向，即yi+1=yi-1，x坐标根据中点与理想圆弧的位置关系，或加1或加0。第56页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法决定x坐标增量的原则是：当下一步的中点M(xi+0.5,yi-1)在圆周上或在圆外，即误差项则x坐标增量为0，下一个点的坐标为(xi,yi-1)；否则x坐标增量为1，下一个点坐标为(xi+1,yi-1)。第57页，本讲稿共58页圆的扫描转换圆的扫描转换中点中点Bresenham算法算法绘制整圆的方法通常可利用中点Bresenham画圆算法结合八分法实现。利用中点Bresenham画圆算法求出第一象限x=y到x=0八分之一区域内的点，利用八分法求出其余区域内的点。例：brescircle.cpp第58页，本讲稿共58页