广工数媒计算机图形学之5基本图形生成算法-直线圆弧

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时，以y为基本步进方向，y

9、方向每次步进增量为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;i0，即点M在直线上方； F(xM, yM)=0时，xi+1=xi+1; yi+1=yi+1; 有,直线的扫描转换Bresenham算法,当di1时，该变量取值1；当斜率=1时，该变量取

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

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

12、awPoint(xc-x,yc-y); /画点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。,圆的扫描转换中点Bres

13、enham算法,设当前点为P(xi, yi)，则有点M(xi+1, yi-0.5)。 构造误差项判别式：,若di0，下一个点为Pu(xi+1, yi)； 否则下一个点为Pd(xi+1, yi-1)；,圆的扫描转换中点Bresenham算法,误差项判别式的递推公式： 当di=0时，此时有xi+1=xi+1，yi+1=yi-1,圆的扫描转换中点Bresenham算法,误差项的初值： 开始绘制圆弧的第一个为理想圆弧上的P0(0, R)点，因此有判别项的初值为：,为避免做浮点运算，用1取代1.25。造成误差项的初值有0.25的误差。因为绘制圆弧以一个像素为基本单位，0.25的舍去不会影响下一个点误差项

14、的计算，因此初值为：,圆的扫描转换中点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+; ,圆的扫描转换中点Bresenham算法,在第一象限y=x到y=0区域，以y为基本走步方向，即yi+1=yi-1，x坐标根据中点与理想圆弧的位置关系，或加1或加0。,圆的扫描转换中点Bresenham算法,决定x坐标增量的原则是：当下一步的中点M(xi+0.5, yi-1)在圆周上或在圆外，即误差项 则x坐标增量为0，下一个点的坐标为(xi, yi-1)； 否则x坐标增量为1，下一个点坐标为(xi+1, yi-1)。,圆的扫描转换中点Bresenham算法,绘制整圆的方法通常可利用中点Bresenham画圆算法结合八分法实现。利用中点Bresenham画圆算法求出第一象限x=y到x=0八分之一区域内的点，利用八分法求出其余区域内的点。 例：brescircle.cpp,直线及圆弧的扫描转换实验要求,一、分别利用D