基本图形生成算法直线圆弧PPT讲稿.ppt

《基本图形生成算法直线圆弧PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《基本图形生成算法直线圆弧PPT讲稿.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基本图形生成算法直线圆弧第1页，共58页，编辑于2022年，星期六 通常认为，基本二维图形包括点、直线、圆、椭圆、多边形域通常认为，基本二维图形包括点、直线、圆、椭圆、多边形域和字符串等。复杂曲线及各种复杂图形均可由直线段和圆弧来拟合，和字符串等。复杂曲线及各种复杂图形均可由直线段和圆弧来拟合，因此研究直线和圆弧的生成算法是二维图形生成技术的基础。因此研究直线和圆弧的生成算法是二维图形生成技术的基础。第2页，共58页，编辑于2022年，星期六在光栅显示器生成一个对象，实质上是往帧缓冲区的相应单元在光栅显示器生成一个对象，实质上是往帧缓冲区的相应单元中写入数据；如画一条直线，实质上是发现最佳逼近

2、直线的像中写入数据；如画一条直线，实质上是发现最佳逼近直线的像素序列、并填入相应颜色的过程，这个过程称为直线的光栅化，素序列、并填入相应颜色的过程，这个过程称为直线的光栅化，或者称为直线的扫描转换。或者称为直线的扫描转换。第3页，共58页，编辑于2022年，星期六“发现最佳逼近直线的像素序列发现最佳逼近直线的像素序列”就是发现直线生成的算就是发现直线生成的算法。不同的算法有不同的效率，但各种算法的法。不同的算法有不同的效率，但各种算法的核心都是围绕核心都是围绕着判别和生成着判别和生成x、y增量的过程和方法（走笔规则）增量的过程和方法（走笔规则）展开研究的。展开研究的。第4页，共58页，编辑于2

3、022年，星期六通常从以下四方面评价直线扫描转换算法的质量：通常从以下四方面评价直线扫描转换算法的质量：一、显示像素点应尽量靠近理想直线，直线要直，走样小；一、显示像素点应尽量靠近理想直线，直线要直，走样小；二、直线端点准确，且绘制无定向性，即以哪一个端点为绘制起点得到的线二、直线端点准确，且绘制无定向性，即以哪一个端点为绘制起点得到的线段应重合；段应重合；三、直线的亮度和色泽要均匀，避免造成视觉上一段亮一段暗的感三、直线的亮度和色泽要均匀，避免造成视觉上一段亮一段暗的感觉。这通过所绘制的像素点密度保持均匀来实现；觉。这通过所绘制的像素点密度保持均匀来实现；四、画线速度尽可能快，即算法效率要高

4、。四、画线速度尽可能快，即算法效率要高。第5页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换常用的直线生成算法有逐点比较法、正负法、数值微分法和常用的直线生成算法有逐点比较法、正负法、数值微分法和Bresenham算法等。算法等。简介简介逐点比较法逐点比较法详细介绍详细介绍数值微分法数值微分法和和Bresenham算法算法。第6页，共58页，编辑于2022年，星期六算法的判断规则算法的判断规则在绘图过程中，画笔每走一步，就要与理想图形进行在绘图过程中，画笔每走一步，就要与理想图形进行比较，然后决定下一步的走向，用步步逼近的方法画出指定起止点间的直比较，然后决定下一步的走向，用

5、步步逼近的方法画出指定起止点间的直线段。线段。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第7页，共58页，编辑于2022年，星期六走笔约定走笔约定以第一象限为例。当以第一象限为例。当画笔（光标当前位置）位于理想直画笔（光标当前位置）位于理想直线上方，则横向走笔，即画笔沿线上方，则横向走笔，即画笔沿x x方向移动一个单位；当画笔位方向移动一个单位；当画笔位于理想直线下方时，则纵向走于理想直线下方时，则纵向走笔，即画笔沿笔，即画笔沿y y方向移动一个单方向移动一个单位。位。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第8页，共58页，编辑于2022年，星期六要确定画线时光标移动的方向，必

6、须要知道当前光标要确定画线时光标移动的方向，必须要知道当前光标点与理想直线的位置关系。位置关系通过坐标的偏差点与理想直线的位置关系。位置关系通过坐标的偏差来决定。来决定。以第一象限为例分析逐点比较法的偏差计算过程。以第一象限为例分析逐点比较法的偏差计算过程。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第9页，共58页，编辑于2022年，星期六设要绘制的直线为设要绘制的直线为OA（即理想直线），当（即理想直线），当前点为前点为M，当前点与理想直线的相对位置，当前点与理想直线的相对位置（即点（即点M在在OA的上方或下方）用偏差值的上方或下方）用偏差值 的的正负来判断。正负来判断。的计算公式为：

7、的计算公式为：直线的扫描转换直线的扫描转换逐点比较法逐点比较法tan函数在是单调递增函数，因此函数在是单调递增函数，因此 的正负体现的正负体现b b 和和a a 的大小。的大小。第10页，共58页，编辑于2022年，星期六偏差与走笔的关系分析：偏差与走笔的关系分析：当当 0时，角时，角b b a a，点，点M在理想直线下在理想直线下方，按约定，画笔应向上（方，按约定，画笔应向上（+y）走一步；）走一步；当当 P0时，角时，角b bPa a，点，点M在理想直线上方在理想直线上方或在直线上，按约定，画笔应向右（或在直线上，按约定，画笔应向右（+x）走一步。走一步。直线的扫描转换直线的扫描转换逐点比

8、较法逐点比较法第11页，共58页，编辑于2022年，星期六从计算偏差值的公式从计算偏差值的公式可知，分子的正负决定可知，分子的正负决定 的正负，因的正负，因此将公式简化如下：此将公式简化如下：直线的扫描转换直线的扫描转换逐点比较法逐点比较法第12页，共58页，编辑于2022年，星期六设当前位置为设当前位置为Mi（xi，yi），则计算偏差的函数为），则计算偏差的函数为从偏差函数可知，光标每移动一个点，就要与理想直线的终点坐标进行计算、从偏差函数可知，光标每移动一个点，就要与理想直线的终点坐标进行计算、比较，然后确定下一步走笔的方向和步长的增量，这样绘制直线效率必然会比较，然后确定下一步走笔的方向

9、和步长的增量，这样绘制直线效率必然会很低，因此要对偏差函数进行简化。很低，因此要对偏差函数进行简化。有效的方法是利用前一个点的偏差来推算下一个点的偏差值，这种方法称为有效的方法是利用前一个点的偏差来推算下一个点的偏差值，这种方法称为递推法递推法。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第13页，共58页，编辑于2022年，星期六例如已知前一个点的偏差值例如已知前一个点的偏差值FiP0，说明点在理想直线的上方，说明点在理想直线的上方，画笔应该沿画笔应该沿+x方向移动一个步长；反之，则应该沿方向移动一个步长；反之，则应该沿+y向移动一个步向移动一个步长。长。开始绘制直线时，光标位于理想直线

10、的起点，因此始终有开始绘制直线时，光标位于理想直线的起点，因此始终有F0=0。直线的扫描转换直线的扫描转换逐点比较法逐点比较法第14页，共58页，编辑于2022年，星期六u 若若FiP0，表示第，表示第i点在直线上方，点在直线上方，则有则有xi+1 xi1（其中（其中1为步长）为步长）yi+1 yi，第第i+1点的偏差判别式为：点的偏差判别式为：将递推法用数学的方法表示为：将递推法用数学的方法表示为：设当前位置为设当前位置为Mi（xi，yi），），下一个点位置为下一个点位置为Mi+1（xi+1，yi+1）直线的扫描转换直线的扫描转换逐点比较法逐点比较法求偏差的基本公式：求偏差的基本公式：第15

11、页，共58页，编辑于2022年，星期六将递推法用数学的方法表示为：将递推法用数学的方法表示为：u 若若Fi0，表示第表示第i点在直线下方，点在直线下方，则有则有xi+1 xi yi+1 yi 1（其中（其中1为步长），为步长），即第即第i+1点的偏差判别式为：点的偏差判别式为：直线的扫描转换直线的扫描转换逐点比较法逐点比较法求偏差的基本公式：求偏差的基本公式：第16页，共58页，编辑于2022年，星期六直线段位置偏差值FkP0偏差值Fk0第一象限走笔+XFk+1=Fk-|yA|走笔+YFk+1=Fk+|xA|第三象限走笔-X走笔-Y第二象限走笔+YFk+1=Fk-|xA|走笔-XFk+1=Fk

12、+|yA|第四象限走笔-Y走笔+X各象限的判别式各象限的判别式直线的扫描转换直线的扫描转换逐点比较法逐点比较法逐点比较法绘制直线逐点比较法绘制直线.doc第17页，共58页，编辑于2022年，星期六【注注】递推公式的作用：递推公式的作用：意义：意义：简化计算过程，提高效率。简化计算过程，提高效率。原则：原则：尽可能以加减法代替乘除法。尽可能以加减法代替乘除法。方法：方法：用当前点的偏差推算出走笔方向，并计算出下一步的偏差；用当前点的偏差推算出走笔方向，并计算出下一步的偏差；再以画笔的当前位置重复上述过程，推算出画笔下一步的动作。再以画笔的当前位置重复上述过程，推算出画笔下一步的动作。第18页，

13、共58页，编辑于2022年，星期六数值微分法（数值微分法（Digital Differential Analyzer）简称简称DDA法，利用直线的微分方程生成直线的方法。法，利用直线的微分方程生成直线的方法。设直线的端点坐标为（设直线的端点坐标为（X0，Y0）和（）和（X1，Y1），直线的参数方程），直线的参数方程为：为：直线的扫描转换直线的扫描转换数值微分法数值微分法第19页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换数值微分法数值微分法DDA算法的原理：由于直线的一阶导数是连续的，且算法的原理：由于直线的一阶导数是连续的，且 x和和 y是成比例是成比例的，因此可以通过在

14、当前位置的，因此可以通过在当前位置(xi,yi)分别加上两个小增量分别加上两个小增量 H x 和和 H y（其中（其中 为无穷小的正数）来求出下一个点为无穷小的正数）来求出下一个点(xi+1,yi+1)的坐标。的坐标。式中，式中，i=0,1,2 ,n-1，第20页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换数值微分法数值微分法当精度无限高的情况下，绘制出的直线无限接近理想直线。当精度无限高的情况下，绘制出的直线无限接近理想直线。这种理想情况不可能出现（因为设备的精度有限）也没必这种理想情况不可能出现（因为设备的精度有限）也没必要追求，因此通常增量系数要追求，因此通常增量系数

15、 的取值为：的取值为：第21页，共58页，编辑于2022年，星期六绘制直线时，要确定一个方向的增量为单位增量，即绘制直线时，要确定一个方向的增量为单位增量，即确定画线的基本确定画线的基本步进方向步进方向，另一个方向的增量由直线的斜率决定。，另一个方向的增量由直线的斜率决定。确定基本步确定基本步进方向的依据是理想直线的斜率进方向的依据是理想直线的斜率k。通常设：通常设：当直线斜率小于或等于当直线斜率小于或等于1，x方向为基本步进方向，即方向为基本步进方向，即 x=1，y的值的值由直线的斜率决定。由直线的斜率决定。当直线斜率大于当直线斜率大于1，y为基本步进方向，即为基本步进方向，即 y=1，x的

16、值由直线的斜率的值由直线的斜率决定。决定。直线的扫描转换直线的扫描转换数值微分法数值微分法第22页，共58页，编辑于2022年，星期六DDA算法的坐标迭代公式：算法的坐标迭代公式：情况一：当情况一：当 ，即即 时，有：时，有：直线的扫描转换直线的扫描转换数值微分法数值微分法第23页，共58页，编辑于2022年，星期六情况二：当情况二：当 ，即，即 时，有：时，有：直线的扫描转换直线的扫描转换数值微分法数值微分法第24页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换数值微分法数值微分法需要注意的是：由于在光栅化过程中，绘制点的最小单位是需要注意的是：由于在光栅化过程中，绘制点的

17、最小单位是1，因，因此对求出的此对求出的xi+1和和yi+1的值需要进行四舍五入。的值需要进行四舍五入。DDA算法是一种增量算法，优点是直观、易于实现；算法是一种增量算法，优点是直观、易于实现；缺点是要做浮点运算和舍入取整，不利于硬件实现。缺点是要做浮点运算和舍入取整，不利于硬件实现。第25页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换数值微分法数值微分法斜率斜率1时，以时，以y为基本为基本步进方向，步进方向，y方向每次方向每次步进增量为步进增量为1。第26页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换数值微分法数值微分法void dda_line(fl

18、oat 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页，编辑于2022年，星期六直线的扫描转换直线的扫描转换Bresenham算法算法Bresenham提出的直线生

19、成算法基本原理为：在某一计长方向提出的直线生成算法基本原理为：在某一计长方向上，每次变化一个单位步长或一个象素单位，另一个方向上上，每次变化一个单位步长或一个象素单位，另一个方向上是否走步取决于误差项。是否走步取决于误差项。计长方向由直线的斜率计长方向由直线的斜率k决定。当决定。当0=k1时，时，y为计长方向。为计长方向。关键问题是如何生成误差项判断条件。关键问题是如何生成误差项判断条件。第28页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法中点中点Bresenham算法依据直线的斜率截距方程。算法依据直线的斜率截距方程。设直线的斜率为设直线

20、的斜率为k，截距为截距为b；直线的斜率、截距方程为：；直线的斜率、截距方程为：F(x,y)=y-kx b=0当直线经过端点当直线经过端点P0(X0,Y0)和和P1(X1,Y1)时时第29页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法符号说明：符号说明：P当前点；当前点；M中点；中点；Pd和和Pu下一步可能下一步可能位置；位置；Q理想直线在理想直线在x=xi+1位置上的点；位置上的点；第30页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法算法说明：算法说明：设直线斜率在设直线斜率在01之间，

21、且位于第一象限。光标走步规则为：每次在之间，且位于第一象限。光标走步规则为：每次在x方向上加方向上加1，y方向根据误差项判断，或加方向根据误差项判断，或加1或加或加0。第31页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法误差项判别式构造：误差项判别式构造：当前点当前点P，下一个点可能为，下一个点可能为Pd(即即yi+1=yi点点)，可能为，可能为Pu(即即yi+1=yi+1点点)。M为为Pd 与与Pu的中点。的中点。若若M在在Q点下方，说明点下方，说明Pu点离直线近，则有点离直线近，则有yi+1=yi+1;若若M在在Q点上方，说明点上方，说

22、明Pd点离直线近，则有点离直线近，则有yi+1=yi;第32页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法直线方程为：直线方程为：要判断点要判断点M与直线的位置关系，只需要把与直线的位置关系，只需要把M的坐标代入直线方程，的坐标代入直线方程，若：若：F(xM,yM)=0，即点，即点M在直线上；在直线上；F(xM,yM)0，即点，即点M在直线上方；在直线上方；F(xM,yM)0，即点，即点M在直线下方；在直线下方；第33页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法点点M与点与点Q误差项误

23、差项d判别式推导：判别式推导：当当di=0时，时，M在直线上方或在直线上，在直线上方或在直线上，Pd(即即yi+1=yi点点)为下一个点。为下一个点。根据递推思想，推导出根据递推思想，推导出di与与di+1的关系。的关系。第34页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法当当di=0时，时，xi+1=xi+1;yi+1=yi;则有则有d的初值：绘制直线时，光点最初在直线的起点的初值：绘制直线时，光点最初在直线的起点P0(x0,y0)处，可推导处，可推导出：出：d0=0.5-k第36页，共58页，编辑于2022年，星期六直线的扫描转换直线的

24、扫描转换中点中点Bresenham算法算法直线的斜率直线的斜率k=dy/dx，将斜率带入判别式：，将斜率带入判别式：当当di=0时，则有时，则有d的初值：的初值：di的正负决定下一个点的位置，与的正负决定下一个点的位置，与di 的具体数值无关，因此，统一的具体数值无关，因此，统一以以2dxHdi替代替代di，以简化判别式。，以简化判别式。第37页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法当当di=0时，则有时，则有d的初值：的初值：因此在代码中最终用到的判别式为：因此在代码中最终用到的判别式为：第38页，共58页，编辑于2022年，星期六

25、直线的扫描转换直线的扫描转换中点中点Bresenham算法算法绘制点绘制点(x,y)yesno第39页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换中点中点Bresenham算法算法上述推导的中点上述推导的中点Bresenham算法绘制直线的判别式适用于直算法绘制直线的判别式适用于直线斜率在线斜率在01之间的情况。之间的情况。观察例观察例mid_bresenham.cpp绘制斜率在绘制斜率在01之间的直线和斜率大之间的直线和斜率大于于1的直线。的直线。当直线大于当直线大于1时，可不必重新推导判别式，只需交换时，可不必重新推导判别式，只需交换x和和y的规则。的规则。bresen

26、ham.cpp第40页，共58页，编辑于2022年，星期六直线的扫描转换直线的扫描转换Bresenham算法算法中点中点Bresenham算法的误差项判别式需要用到直线斜率，改进算法的误差项判别式需要用到直线斜率，改进后的后的Bresenham算法，思路保持不变，对误差项判别式进行简化。算法，思路保持不变，对误差项判别式进行简化。Bresenham算法直接比较距离算法直接比较距离t和和s的大小，来确定下一个绘的大小，来确定下一个绘制的像素。制的像素。第41页，共58页，编辑于2022年，星期六推导、简化后得到的误差项判别式为：推导、简化后得到的误差项判别式为：当当di=0时，时，xi+1=xi

27、+1;yi+1=yi+1;有有直线的扫描转换直线的扫描转换Bresenham算法算法当当di1时，该变时，该变量取值量取值1；当斜率；当斜率=1时，该变量取值时，该变量取值0。直线的扫描转换直线的扫描转换Bresenham算法算法第44页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换给出圆心给出圆心(xc,yc)和半径和半径r，逐点绘制圆的方式有：，逐点绘制圆的方式有：一、利用直角坐标方程一、利用直角坐标方程利用直角坐标方程绘制圆弧思路清楚，但计算涉及开方运算，计算利用直角坐标方程绘制圆弧思路清楚，但计算涉及开方运算，计算量大。更大的缺点是，由于量大。更大的缺点是，由于y不是不是

28、x的线性函数，因此，当的线性函数，因此，当x取值从取值从0到到r均匀递增时，均匀递增时，y的值变化极不均匀，尤其当的值变化极不均匀，尤其当x接近接近r时，绘制出来的圆时，绘制出来的圆会出现较大的间断。会出现较大的间断。第45页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换二、利用圆的参数方程二、利用圆的参数方程利用参数方程绘制圆弧可以克服直角坐标方程画圆的弊端。参利用参数方程绘制圆弧可以克服直角坐标方程画圆的弊端。参数为圆周角，当圆周角按固定增量变化时，能获得均匀分布在数为圆周角，当圆周角按固定增量变化时，能获得均匀分布在圆周上的点。圆周上的点。第46页，共58页，编辑于2022

29、年，星期六圆的扫描转换圆的扫描转换但是，利用圆的参数方程绘制圆弧有两个严重缺陷：但是，利用圆的参数方程绘制圆弧有两个严重缺陷：一、每次求点坐标都需要计算三角函数，计算量大，效率低。一、每次求点坐标都需要计算三角函数，计算量大，效率低。二、二、t 增量的大小与半径相关。如，若增量的大小与半径相关。如，若t 取某一定值，当半径很小时，计取某一定值，当半径很小时，计算出来的像素可能会重叠（相邻像素的算出来的像素可能会重叠（相邻像素的x和和y的增量都不于的增量都不于1）；而当半径较）；而当半径较大时，有可能会造成圆弧出现断开现象（相邻像素的大时，有可能会造成圆弧出现断开现象（相邻像素的x和和y的增量过

30、大）的增量过大）。观察例程观察例程“参数方程画圆参数方程画圆”第47页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换八分法画圆八分法画圆圆心位于原点的圆有四条对圆心位于原点的圆有四条对称轴线：称轴线：若已知圆周上任意一点，可若已知圆周上任意一点，可以利用圆的对称性得到另外以利用圆的对称性得到另外七个点的坐标，从而得到整七个点的坐标，从而得到整个圆的转换扫描像素集。个圆的转换扫描像素集。第48页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换八分法画圆八分法画圆drawPoint(xc+x,yc+y);/画点画点AdrawPoint(xc-x,yc+y);/画点画点A7

31、drawPoint(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页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法中点中点Bresenham法求圆弧上法求圆弧上的点思路与直线绘制相同。的点思路与直线绘制相同。考虑圆心在原点，位于图示考虑圆心在原点，位于图示区域的八分之一圆弧。

32、区域的八分之一圆弧。中点中点Bresenham画圆算法按画圆算法按照从点照从点(0,0)到点到点顺时针确定最佳逼近理想圆顺时针确定最佳逼近理想圆弧的像素序列。弧的像素序列。第50页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法算法基本原理：算法基本原理：x为基本步进方向。每一次沿为基本步进方向。每一次沿x方向方向走一步，走一步，y方向坐标或减方向坐标或减1，或，或减减0。当前点为当前点为P，下一步的中点为，下一步的中点为M。如果点如果点M在圆内，则在圆内，则Pu为下一个为下一个点，即点，即y方向坐标减方向坐标减0；如果点；如果点M在圆外，则在圆外

33、，则Pd为下一个点，即为下一个点，即y方向坐标减方向坐标减1。第51页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法设当前点为设当前点为P(xi,yi)，则有点，则有点M(xi+1,yi-0.5)。构造误差项判别式：构造误差项判别式：若若di0，下一个点为，下一个点为Pu(xi+1,yi)；否则下一个点为否则下一个点为Pd(xi+1,yi-1)；第52页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法误差项判别式的递推公式：误差项判别式的递推公式：当当di=0时，此时有时，此时有xi+1=xi+1，y

34、i+1=yi-1第53页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法误差项的初值：误差项的初值：开始绘制圆弧的第一个为理想圆弧上的开始绘制圆弧的第一个为理想圆弧上的P0(0,R)点，因此有判别点，因此有判别项的初值为：项的初值为：为避免做浮点运算，用为避免做浮点运算，用1取代取代1.25。造成误差项的初值有。造成误差项的初值有0.25的误的误差。因为绘制圆弧以一个像素为基本单位，差。因为绘制圆弧以一个像素为基本单位，0.25的舍去不会的舍去不会影响下一个点误差项的计算，因此初值为：影响下一个点误差项的计算，因此初值为：第54页，共58页，编辑于

35、2022年，星期六圆的扫描转换圆的扫描转换中点中点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页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法在第一象限在第一象限y=x到到y=0区域，以区域，以y为基本走步方向，即为基本走步方向，即yi+1=yi-1，x坐标根据中点与理想圆弧的位坐标根据中点与理想圆

36、弧的位置关系，或加置关系，或加1或加或加0。第56页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法决定决定x坐标增量的原则是：当下一步坐标增量的原则是：当下一步的中点的中点M(xi+0.5,yi-1)在圆周上或在在圆周上或在圆外，即误差项圆外，即误差项则则x坐标增量为坐标增量为0，下一个点的坐，下一个点的坐标为标为(xi,yi-1)；否则否则x坐标增量为坐标增量为1，下一个点坐标，下一个点坐标为为(xi+1,yi-1)。第57页，共58页，编辑于2022年，星期六圆的扫描转换圆的扫描转换中点中点Bresenham算法算法绘制整圆的方法通常可利用中点绘制整圆的方法通常可利用中点Bresenham画圆算法结合八画圆算法结合八分法实现。利用中点分法实现。利用中点Bresenham画圆算法求出第一象限画圆算法求出第一象限x=y到到x=0八分之一区域内的点，利用八分法求出其余区域八分之一区域内的点，利用八分法求出其余区域内的点。内的点。例：例：brescircle.cpp第58页，共58页，编辑于2022年，星期六