frank@cavebbs.gen.nz (Frank van der Hulst) (01/23/91)
I'm looking for a generalised ellipse-drawing routine, perhaps similar to Bresenham's circle-drawing algorithm. However, I also want to be able to draw only parts of an ellipse. Currently, I'm doing it via the x^2/a^2 + y^2/b^2 = 1 formula, and calculating the angle between the x-axis and the line to the point being generated to ensure the line is within range. However, all the FP maths is slowing down the drawing considerably. o -- Take a walk on the wild side, and I don't mean the Milford Track.
fleming@ (Dennis Fleming) (01/25/91)
In article <1991Jan23.095200.17536@cavebbs.gen.nz> frank@cavebbs.gen.nz (Frank van der Hulst) writes: >I'm looking for a generalised ellipse-drawing routine, perhaps similar to >Bresenham's circle-drawing algorithm. However, I also want to be able to >draw only parts of an ellipse. > >Currently, I'm doing it via the x^2/a^2 + y^2/b^2 = 1 formula, and calculating >the angle between the x-axis and the line to the point being generated to >ensure the line is within range. However, all the FP maths is slowing down the >drawing considerably. >o >-- Two ways to draw an ellipse which come to mind immediately are 1) use Bresenham's algorithm using the minor axis as the radius and scale the output along the major axis 2) Rederive the Bresenham algorithm for circles using the equation for an ellipse instead of a circle. Here's some code for number 2: /* The program draws an ellipse centered at 256x256 */ /* with a width of wd and a height of ht */ void plot_ellipse_points(int x, int y, int xc, int yc) { image[yc + y][xc + x] = 64; image[yc - y][xc + x] = 128; image[yc + y][xc - x] = 192; image[yc - y][xc - x] = 255; } /* Draws an ellipse using Bresenham's incremental techniques. This is the same code as for circles, but incorporating the fact that there are two axes instead of just a radius. A critical difference is that ellipses don't have eight-way symmetry, so it's not enough to plot only an eighth in which one coordinate can always be stepped a full pixel. We must use four-way symmetry and check for the point where the slope of the tangent indicates that one axis predominates over the other. Since both axes will be the driving axis at one time, we must have two steppers, on for each axis */ void bres_ellipse(int xc, int yc, int wd, int ht) { int x, y, d, t1, t2; int wd2, ht2; /* Compute squares of axes */ wd2 = wd*wd; ht2 = ht*ht; /* Initialize decision variable and coordinates for X stepper */ d = 2*ht2-2*ht*wd2+wd2; x = 0; y = ht; while (y>0) { plot_ellipse_points(x, y, xc, yc); if (d<0) d += 4*ht2*x+6*ht2; else { t1 = 4*ht2*x; t2 = 4*wd2*y; /* Quit when the slope changes over. This is easy to check because it is the point beyond which d always increases. Note that x is always increasing and y is always decreasing, so as soon as the x term overcomes the y term, d will always grow */ if (t1>t2) break; d += t1-t2+6*ht2+4*wd2; y--; } x++; } /* Initialize decision variable and coordinates for Y stepper */ /* This is the same code as above, but with x<->y and wd<->ht */ d = 2*wd2-2*wd*ht2+ht2; x = wd; y = 0; while (x>0) { plot_ellipse_points(x, y, xc, yc); if (d<0) d += 4*wd2*y+6*wd2; else { t1 = 4*wd2*y; t2 = 4*ht2*x; if (t1>t2) break; d += t1-t2+6*wd2+4*ht2; x--; } y++; } } If you want to do just part of the ellipse you can truncate the test and change the routine plot_ellipse_points. Pitteway has a routine for incrementally plotting arbitrary conic sections. That algorithm along with other similar curve drawing routines can be found in _Fundamental Algorithms for Computer Graphics_ ed. R.A. Earnshaw Springer-Verlag 1985. It is part of the NATO ASI series F volume 17. It is, however, probably overpriced Dennis Fleming Dept of Electrical and Computer Engineering University of California, Irvine
leech@homer.cs.unc.edu (Jonathan Leech) (01/25/91)
In article <279F954C.4186@orion.oac.uci.edu>, fleming@ (Dennis Fleming) writes: |>Pitteway has a routine for incrementally plotting arbitrary conic sections. |>That algorithm along with other similar curve drawing routines can be |>found in _Fundamental Algorithms for Computer Graphics_ ed. R.A. Earnshaw |>Springer-Verlag 1985. It is part of the NATO ASI series F volume 17. |>It is, however, probably overpriced And perhaps not needed, if you have access to a moderately well-stocked CS library. Look in _Computer Journal_, V10 (1967-68), pg. 282 for "Algorithm for drawing ellipses or hyperbolae with a digital plotter" by M. Pitteway. Jon (leech@cs.unc.edu) __@/