资源描述
中点画线法,潘万鹏,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); ,
展开阅读全文