计算机图像图形学-中点画线法.ppt

中点画线法,潘万鹏,3.1.2 中点画线法,这里先讨论直线斜率在0l之间。如图3.2所示，若直线在x方向上增加一个单位，则在y方向上的增量只能在01之间。假设直线上当前已确定的一个像素点坐标为(xp,yp)，用实心小圆表示。,图3.2 中点画线法示意图,那么，下一个与直线最近的像素只能是正右方的P1(xp+1、yp)或右上方的P2(xp+1、yp+1)两者之一，用空心小圆表示。,为了方便地确定出下一个像素是P1还是P2，设M为P1与P2的中点，即M=(xp+1,yp+0.5)。又设Q是理想直线与垂直线 x=xp+l的交点。显然，若M在Q的上方，则P1离直线近，应取为下一个像素；否则应取P2。这种以中点M作为判别标志的方法就是中点画线算法。,下面来讨论中点画线法的具体实现。,直线方程为：F(x,y)=ax+by+c 0假设直线的起点和终点分别为(x1,y1)和(x2,y2)，则上述参数：a=y1-y2，b=x2-x1，c=x1y2-x2y1。,对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)0；而对于直线下方的点，F(x，y)0。因此，欲判断前述Q在M的上方还是下方，只要把 M代入 F(x，y)，并判断它的符号。,构造判别式 dF(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c,当 d0时，M在直线上方（即在Q的上方），故应取右方的P1作为下一个像素。而当d0，则应取右上方的P2。当d=0时，约定取右方P1。,对每一个像素计算判别式d，根据它的符号确定下一像素。,由于d是xp和yp的线性函数，可采用增量计算，以便提高运算效率。,在d0的情况下，取正右方像素P1，欲判断再下一个像素应取那个，应计算 d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=(a(xp+1)+b(yp+0.5)+c)+a=d+a故d的增量为a。,在d0时，取右上方像素P2。要判断再下一个像素，应计算 d2=F(xp+2,yp+l.5)=a(xp+2)+b(yp+1.5)+c=(a(xp+1)+b(yp+0.5)+c)+a+b=d+a+b,再看d的初始值。直线的第一个像素为左端点(x1,y1)，所以相应的判别式值为 d0=F(x1+1,y1+0.5)=a(x1+1)+b(y1+0.5)+c=(ax1+by1+c)+a+0.5b=F(x1，y1)+a+0.5b 由于(x1,y1)在直线上，故F(x1,y1)=0。因此，d的初始值为d0=a0.5b。,由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，就可以写出仅包含整数运算的中点画线算法(斜率在0l)：,故d的增量为ab。,void MidpointLine(int x1,int y1,int x2,int y2,int color)int x,y,a,b,d1,d2,d;a=y1-y2;b=x2-x1;d=2*a+b;d1=2*a;d2=2*(a+b);x=x1;y=y1;putpixel(x,y,color);while(xx2)x=x+1;if(d0)y=y+1;d+=d2;else d+=d1;putpixel(x,y,color);,3.2 圆与椭圆的生成,3.2.1 圆的特性,由于圆是图形和图像中经常使用的元素，因此在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的绘图函数。,圆被定义为所有离一中心位置(xc，yc)距离为给定值r的点集，可用如下方程表示：(x xc)2+(y yc)2=r 2,利用这个方程，我们可以沿x轴从xcr到xc+r以单位步长计算对应的y值来得到圆周上每点的位置：y=yc,但这并非是生成圆的最好方法。这个方法的一个问题是每一步包含很大的计算量。而且所画像素位置间的间距是不一致的，在靠近x轴的0和180处像素点之间的间距越来越大。当然可以在圆斜率的绝对值大于1后，交换x和y（即步进y值，计算x值）来调整间距。但这样增加了算法所需的计算量和处理过程。,另一种消除不等间距的方法是使用极坐标r和计算沿圆周的点。以参数极坐标形式表示圆方程可得到方程组：x=xc+r cos y=yc+r sin,使用上述方法以固定角度为步长生成显示时，圆就可沿圆周等距点绘制出来。但这个方法使用了三角函数调用和浮点运算，运算速度太慢。,考虑到圆的对称性可以减少计算量。只要能生成8分圆，那么圆的其他部分可通过一系列的简单反射变换得到。,如图3.4所示，假设已知一个圆心在原点的圆上一点(x，y)，根据对称性可得另外七个8分圆上的对应点(y,x),(y,x),(x,y),(x,y),(y,x),(y,x),(x,y)。因此，只需讨论8分圆的生成算法。,另外，为了方便起见，我们只考虑中心在原点，半径为整数R的圆x2y2=R2。对于中心不在原点的圆，可先通过平移变换，化为中心在原点的圆，再进行扫描转换，把所得的像素坐标加上一个位移量即得所求像素坐标。,图3.4 圆的对称性,3.2.2 中点画圆法,由于圆的对称性，下面主要考虑中心在原点半径为r的圆的第二8分圆。若从圆的正上方开始讨论如何确定最佳逼近于该圆弧的像素序列。,图3.5 中点画圆法示意图,假定当前已确定了圆弧上的一个像素点为P(xp,yp)，那么，下一个像素只能是正右方的P1(xp+1,yp)或右下方的P2(xp+1,yp1)两者之一。如图3.5所示。,那么，当F(M)0时，M在圆外，这说明P2距离圆弧更近，应取P2作为下一像素。而当F(M)0时，P1离圆弧更近，应取P1。当F(M)=0时，在P1与P2之中随便取一个即可，约定取P2。,对于圆上的点，F(x,y)=0；对于圆外的点，F(x,y)0；而对于圆内的点，F(x,y)0。与中点画线法类似，设M是P1和P2的中点，即M=(xp+1，yp 0.5)。,构造函数：F(x,y)=x2y2 r2(35),若d0，则应取P1为下一像素，而且再下一个像素的判别式为 d=F(xp+2，yp 0.5)=(xp+2)2+(yp 0.5)2 R2=d+2xp+3所以，沿正右方向，d的增量为2xp+3。,与中点画线法一样，构造判别式 d=F(M)=F(xp+1，yp 0.5)=(xp+1)2+(yp 0.5)2 r2,而若d0，则P2是下一像素，而且下一像素的判别式为 d=F(xp+2,yp 1.5)=(xp+2)2+(yp 1.5)2 R2=d+(2xp+3)+(2yp+2)所以,沿右下方向,判别式d的增量为2(xpyp)+5。,再来看看d的初始值d0。由于我们从圆的正上方开始，因此第一像素是(0,r)，判别式d的初始值为：d0=F(l,r 0.5)=1+(r 0.5)2 r2=1.25 r,由于上述公式中只有d0包含小数，而它又仅仅作为一个判别式，因此可以做一些特殊处理来摆脱浮点数，在算法中全部使用整数。,若用e=d 0.25代替d，则d0=l.25 r 对应于e0=1 r。判别式d0对应于e 0.25。算法中其他与d有关的式子可把d直接换成e。这样，就可以写出完全用整数实现的中点画圆算法。算法中e仍用d来表示。,以下是中点画圆算法的C语言描述：,void MidpointCircle(int xc,int yc,int r,int color)int x=0,y=r,d=1 r；WholeCircle（xc，yc，x，y，color）；while（x=y）if（d0）d+=2*x+3；x+；else d+=2*（x y）+5；x+;y；WholeCircle（xc，yc，x，y，color）；,void WholeCircle(int xc,int yc,int x,int y,int color)putpixel(xc+x，yc+y，color)；putpixel(xc x，yc+y，color)；putpixel(xc+x，yc y，color)；putpixel(xc x，yc y，color)；putpixel(xc+y，yc+x，color)；putpixel(xc y，yc+x，color)；putpixel(xc+y，yc x，color)；putpixel(xc y，yc x，color)；,3.2.3 Bresenham画圆算法,考虑圆心在原点，半径为r的第一个8分圆。取(0,r)为起点，按顺时针方向生成圆。如图3.6所示。从这段圆弧的任意一点出发，按顺时针方向生成圆时。在这种情况下，x每步增加1，即：,图3.6 y的位置,xi+1=xi+1则相应的y有二种选择：yi+1=yi 或 yi+1=yi-1,Bresenham画圆算法采用一个决策值来确定到底是选择yi还是yi-1。在x=xi+1位置上，用d1和d2来标识两个候选像素的y值与圆弧上理想y值的差值，则：y2=r2-(xi+1)2 d1=yi2-y2=yi2-r2+(xi+1)2 d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2,令di=d1-d2，并代入d1、d2，则有：di=2(xi+1)2+yi2+(yi-1)2-2r2这里di就是Bresenham画圆算法的第i步决策值。如果di0，则yi+1=yi，否则yi+1=yi-1。若di=0，则可任选一个，我们约定yi+1=yi-1。,下面来推导di的递推公式。在i+1步，di+1为：di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2,若di0，取右方像素，yi+1=yi，则：di+1=2(xi+1+1)2+yi2+(yi-1)2-2r2=di+4xi+6,而决策值的初值d0由x=0,y=r代入前面公式，得：d0=2(0+1)2+r2+(r-1)2-2r2=3-2r,已知xi+1=xi+1，因而得到：di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2,若di=0，取右下方像素，yi+1=yi-1，则：di+1=2(xi+1+1)2+(yi-1)2+(yi-1-1)2-2r2=di+4(xi-yi)+10,由此，可写出Bresenham画圆算法的C程序：,void BresenhamCircle(int xc,int yc,int r,int color)int x=0,y=r,d=3-2*r;while(xy)WholeCircle(xc,yc,x,y,color);if(d0)d=d+4*x+6;else d=d+4*(x-y)+10;y-;x+;if(x=y)WholeCircle(xc,yc,x,y,color);,3.2.4 椭圆的生成算法,中点画圆法可以推广到一般二次曲线的生成。给定椭圆参数中心（xc，yc）、长半轴a和短半轴b，该椭圆的一般方程为：(x xc)2/a2+(y yc)2/b2=1,为此，可以先把中心平移到坐标原点，确定好中心在原点的标准位置的椭圆像素点集后，再平移到(xc,yc)位置。如果椭圆的长轴和短轴方向不与坐标轴x和y平行，可以先绕中心点进行旋转变换，确定变换矩阵，然后用本方法生成椭圆像素点集，再用变换矩阵乘以这些点集，就可绘出倾斜的椭圆。,以下我们先考虑标准位置的椭圆，即：x2/a2+y2/b2=1把上式改变为下面形式：F(x,y)=b2x2a2y2 a2b2=0(36),由于椭圆的对称性，我们只要讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一步把它分为两部分：上部分和下部分。,以弧上斜率为1的点作为分界，如图3.7(P83)所示。在上部分，在x方向取单位步长，确定下一像素的位置；在斜率小于1的下部分，在y方向取单位步长来确定下一像素的位置。,椭圆的斜率可从方程(36)中计算出：dy/dx=2b2x/2a2y,在上部分和下部分的交界处,斜率dy/dx=1,则上式变为：2b2x=2a2y 因此，从上部分变为下部分的条件是：2b2x=2a2y,与中点画圆算法类似，当我们确定一个像素之后，接着在两个候选像素的中点计算一个判别式的值。并根据判别式符号确定两个候选像素哪个离椭圆更近。下面讨论算法的具体步骤。先看椭圆弧的上部分。假设当前已确定的椭圆弧上的像素点为(xp,yp)，那么下一对候选像素的中点是(xp+l,yp 0.5)。,因此判别式为 dp=F(xp+1,yp0.5)=b2(xp+1)2+a2(yp0.5)2 a2b2它的符号将决定下一个像素是取正右方的那个，还是右下方的那个。,若dp0，中点在椭圆内，则应取正右方像素，且判别式应更新为 dp+1=F(xp+2,yp0.5)=b2(xp+2)2+a2(yp0.5)2 a2b2=(b2(xp+1)2+a2(yp0.5)2a2b2)+b2(2xp+1+1)=dp+b2(2xp+1+1)因此，往正右方向，判别式dl的增量为b2(2xp+1+1)。,而当dp0，中点在椭圆之外，这时应取右下方像素，并且更新判别式为,dp+1=F(xp+2,yp1.5)=b2(xp+2)2+a2(yp1.5)2 a2b2=(b2(xp+1)2+a2(yp0.5)2a2b2)+b2(2xp+1+1)2a2yp+1=dp+b2(2xp+1+1)2a2yp+1,所以，沿右下方向，判别式d的增量为：b2(2xp+1+1)2a2yp+1,接下来，我们来看判别式dp的初始条件。由于弧起点为(0,b)，因此，第一个中点是(1,b0.5)，对应的判别式是dp0=F(1,b0.5)=b2+a2(b0.5)2a2b2=b2+a2(b+0.25),在生成椭圆弧的上部分时，在每步迭代中，必须随时计算和比较从上部分转入下部分的条件是否成立，这是由于在下一部分步进方向由x改为y，因此算法也就不同。在下部分，应改为从正下方和右下方两个像素中选择下一像素。,在刚转入下一部分之时，必须对下部分的中点判别式d2进行初始化。具体地说，如果在上部分所选择的最后一像素是(xp,yp)，则下部分的中点判别式d2在(xp+0.5,yp1)处计算。d2在正下方向与右下方向的增量计算与上部分类似，这里不再赘述。下部分弧的终止条件是y=0。至此，可写出完整的中点画椭圆的算法如下：,void MidpointEllipse(int xc,int yc,int a,int b,int color)int aa=a*a,bb=b*b;int twoaa=2*aa,twobb=2*bb;int x=0,y=b;int dx=0,dy=twoaa*y;int d=(int)(bb+aa*(b+0.25)+0.5);WholeEllipse(xc,yc,x,y,color);while(dx dy)x+;dx+=twobb;if(d 0)d+=bb+dx;else y;dy=twoaa;d+=bb+dx dy;WholeEllipse(xc,yc,x,y,color);,void WholeEllipse(xc,yc,x,y,color)int xc,yc,x,y,color;putpixel(xc+x,yc+y,color);putpixel(xc+x,yc y,color);putpixel(xc x,yc+y,color);putpixel(xc x,yc y,color);,d=(int)(bb*(x+0.5)*(x+0.5)+aa*(y1)*(y1)aa*bb+0.5);while(y 0)y;dy=twoaa;if(d 0)d+=aa dy;else x+;dx+=twobb;d+=aa dy+dx;WholeEllipse(xc,yc,x,y,color);,