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

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)= b2x2＋a2y2 – a2b2 = 0 (3–6) 则该式可作为中点算法的判别式： 0 说明(x，y)在椭圆边界内 F (x, y) = 0 说明(x，y)在椭圆边界上 0 说明(x, y)在椭圆边界外 由于椭圆的对称性，我们只要讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一步把它分为两部分：上部分和下部分。 以弧上斜率为–1的点作为分界，如图3.7(P83)所示。在上部分，在x方向取单位步长，确定下一像素的位置；在斜率小于–1的下部分，在y方向取单位步长来确定下一像素的位置。 椭圆的斜率可从方程(3–6)中计算出： dy / dx = – 2b2x / 2a2y 在上部分和下部分的交界处, 斜率dy/dx= –1, 则上式变为： 2b2x = 2a2y 因此，从上部分变为下部分的条件是： 2b2x = 2a2y 与中点画圆算法类似，当我们确定一个像素之后，接着在两个候选像素的中点计算一个判别式的值。并根据判别式符号确定两个候选像素哪个离椭圆更近。下面讨论算法的具体步骤。先看椭圆弧的上部分。假设当前已确定的椭圆弧上的像素点为(xp,yp)，那么下一对候选像素的中点是(xp+l,yp – 0.5)。 因此判别式为 dp = F(xp+1, yp–0.5)= b2(xp+1)2 + a2(yp–0.5)2 – a2b2 它的符号将决定下一个像素是取正右方的那个，还是右下方的那个。 若dp0，中点在椭圆内，则应取正右方像素，且判别式应更新为 dp+1=F(xp+2, yp–0.5)=b2(xp+2)2 +a2(yp–0.5)2 –a2b2 = (b2(xp+1)2 +a2(yp–0.5)2–a2b2) +b2(2xp+1+1) = dp + b2(2xp+1 +1) 因此，往正右方向，判别式dl的增量为b2(2xp+1+1)。 而当dp≥0，中点在椭圆之外，这时应取右下方像素，并且更新判别式为 dp+1 =F(xp+2, yp–1.5)=b2(xp+2)2 +a2(yp–1.5)2 – a2b2 =(b2(xp+1)2+a2(yp–0.5)2–a2b2)+b2(2xp+1+1)–2a2yp+1 = dp+b2(2xp+1+1)–2a2yp+1 所以，沿右下方向，判别式d的增量为： b2(2xp+1+1)– 2a2yp+1 接下来，我们来看判别式dp的初始条件。由于弧起点为(0, b)，因此，第一个中点是(1, b–0.5)，对应的判别式是 dp0=F(1, b–0.5)=b2+a2(b–0.5)2–a2b2=b2+a2(–b+0.25) 在生成椭圆弧的上部分时，在每步迭代中，必须随时计算和比较从上部分转入下部分的条件是否成立，这是由于在下一部分步进方向由