dig@peritek.UUCP (David Gotwisner) (02/14/89)
I am looking for an algorithm (or code) which will allow circle generation onto a graphics device which drives a monitor with non-square pixels. If any of you know of anything that may help me, please let me know. I think that an efficient ellipse algorithm would work also. Also, if you could refer me to some literature, this would also help. Thanks in advance. Dave Gotwisner -- ------------------------------------------------------------------------------ Dave Gotwisner UUCP: ...!unisoft!peritek!dig Peritek Corporation ...!vsi1!peritek!dig 5550 Redwood Road Oakland, CA 94619 Phone: 1-415-531-6500
krueger@ndmath.UUCP (Andreas Krueger) (02/15/89)
In article <399@peritek.UUCP>, dig@peritek.UUCP (David Gotwisner) writes: > > I am looking for an algorithm (or code) which will allow circle > generation onto a graphics device which drives a monitor with non-square > pixels. Drawing a circle on a device with non-square pixels is equivalent to drawing an ellipse on a monitor with square pixels. From any third-semester calculus book ("calculus with analytic geometry") you can find the formula of an ellipse: x^2 y^2 --- + --- = 1 a^2 b^2 This is the formula of an ellipse with center (0,0), the "diameter" in direction of the x-axis is 2a, the "diameter" in direction of the y axis is 2b. The points (a,0), (-a,0), (0,b), (0,-b) are the four vertices of the ellipse (i.e., the points where the two symmetry axes hit through the ellipse). I've just been teaching this stuff in a third semester calculus course (off semester), so this is actually a nice homework exercise for me. Here is how I would go about implementing this: If you want to draw a circle, proceed as follows: You'll have a radius "r". Let "a" denote the number of pixels on a horizontal line of length "r", and "b" denote the number of pixels on a vertical line length "r". Now let x run from 0 to a^2/sqrt(a^2+b^2) in steps of 1 (pixel). For each such x, compute y by the above formula, which when solved for y yields y = (b/a)*sqrt(a^2 - x^2). (You'll want to put those numbers b/a and a^2 into temporary variables so the computer doesn't compute them anew each time.) Round y to the nearest integer. If (x0,y0) are the pixel coordinates of the intended center of your circle, set the four pixels (x+x0,y+y0), (-x+x0,y+y0), (x+x0,-y+y0), (-x+x0,-y+y0). (For efficiency, see to it that the program computes x+x0, -x+x0, y+y0, -y+y0 only once each, rather than twice. Just use some more temporary variables.) Now you let y run from 0 to b^2/sqrt(a^2+b^2) in steps of 1 (pixel). For each such y, compute x by the above formula, which when solved for x yields x = (a/b)*sqrt(b^2 - y^2). Set the four pixels (same as above). From this, you can write the code yourself, I'd say. I don't know for what kind of computer you'll need this. If it turns out that the arthmetic is too slow, you'll have to increase your steps from 1 to some larger number and draw connecting lines rather than just blacking individual pixels. The coding would become slightly more messy, for you'll need to keep track of four unfinished lines at one time. Hope that's what you needed! krueger@ndmath.math.nd.edu gl5r7n@irishmvs.cc.nd.edu gl5r7n@irishmvs.bitnet
jgary@ms.uky.edu (James E. Gary) (02/15/89)
In article <1311@ndmath.UUCP> krueger@ndmath.UUCP (Andreas Krueger) writes: >In article <399@peritek.UUCP>, dig@peritek.UUCP (David Gotwisner) writes: >> >> I am looking for an algorithm (or code) which will allow circle >> generation onto a graphics device which drives a monitor with non-square >> pixels. > [ lots of calculus stuff deleted ] That is perfectly fine, but the title said he wanted a _FAST_ ellipse algorithm. Almost any computer graphics book will contain Bresenham's circle drawing algorithm which is very fast. It requires no trig function evaluation, only addition, subtraction, and multiplication by 2 and 4, which can be accomplished quickly by shifts. Uses only integer variables also. It also takes advantage of the symmetry of the problem. I don't think it gets no faster than that. If you can't find the algorithm in a book somewhere, let me know and I'll post it. It is quite short.
leech@zeta.cs.unc.edu (Jonathan Leech) (02/15/89)
In article <399@peritek.UUCP>, dig@peritek.UUCP (David Gotwisner) writes: > > I am looking for an algorithm (or code) which will allow circle > generation onto a graphics device which drives a monitor with non-square > pixels. Two related papers: _An Improved Algorithm for the Generation of Nonparametric Curves_, Bernard Jordan et al., IEEE TOC Vol. C-22, #12, Dec. 1973 _Algorithm for drawing ellipses or hyperbolae with a digital plotter_, M. Pitteway, Computer Journal, V. 10 (1967-68), p. 282 -- Jon Leech (leech@cs.unc.edu) __@/ ``You're everything I ever wanted in a human AND an extraterrestrial.'' - Dr. Steve Mills in _My Stepmother is an Alien_
rhbartels@watcgl.waterloo.edu (Richard Bartels) (02/15/89)
> I am looking for an algorithm (or code) which will allow circle > generation onto a graphics device which drives a monitor with non-square > pixels. Just for the reference, since I have not seen it mentioned yet in response: "How Many Ways Can You Draw a Circle?" Jim Blinn IEEE Computer Graphics and Applications August, 1987 It is not quite what is wanted, but a good collateral reference. (Jim Blinn's articles in each issue of this journal are absolutely required reading.) -Richard ---------------------------------------------------------------------------- The opinions expressed are my own. Don't you wish you had them, too?
dmt@mtunb.ATT.COM (Dave Tutelman) (02/16/89)
>In article <399@peritek.UUCP>, dig@peritek.UUCP (David Gotwisner) writes: >> >> I am looking for an algorithm (or code) which will allow circle >> generation onto a graphics device which drives a monitor with non-square >> pixels. >> ...... < gotta' be FAST > ........ In article <1311@ndmath.UUCP> krueger@ndmath.UUCP (Andreas Krueger) writes: >From any third-semester calculus book ("calculus with analytic >geometry") you can find the formula of an ellipse: > > x^2 y^2 > --- + --- = 1 > a^2 b^2 True enough! >... < lots of stuff about stepping pixels deleted > >For each such y, compute x by the above formula, which when >solved for x yields x = (a/b)*sqrt(b^2 - y^2). Set the four >pixels (same as above). > >From this, you can write the code yourself, I'd say. >I don't know for what kind of computer you'll need this. If it >turns out that the arthmetic is too slow..... This is a straightforward approach, but naive about practice in graphics programming. For instance, it requires floating point arithmetic and the taking of square roots for each pixel (well, each 4 pixels anyway). Look at the way fast line-drawing algorithms work (Bresenham's algorithm). Once you understand how it works, it's not all that arcane to work from the math of an ellipse (as Andreas posts) to come up with a modified Bresenham's for ellipses. Hint: compare the formula above with a straight line: x y - + - = 1 a b I did this a few years back in Turbo Pascal. All integer arithmetic. Only 2 multiplies (and a bunch of adds and compares) per pixel. If folks are interested, I'll exhume the code, clean it up, and post it. Please express interest by Email. +---------------------------------------------------------------+ | Dave Tutelman | | Physical - AT&T Bell Labs - Lincroft, NJ | | Logical - ...att!mtunb!dmt | | Audible - (201) 576 2442 | +---------------------------------------------------------------+
krueger@ndmath.UUCP (Andreas Krueger) (02/16/89)
Yes, I see he did say FAST. Sorry, somehow I must have overlooked that. (Seriously. Didn't get enough sleep the night before I posted or something.) I only write humble programs to figure xyz out for my dissertation. Those get some 3 or 4 runs, some only one, so for me the concern is "quickly coded, easily debugged". Runtime is rarely an issue for that kind of software. So thanks for anyone who reminded me there is a real world out there! Greetings from the ivory tower! :-) krueger@ndmath.math.nd.edu gl5r7n@irishmvs.cc.nd.edu
klee@daisy.UUCP (Ken Lee) (02/16/89)
If anyone's interested, Bresenham's circle generation algorithm is presented in Chapter 11.4.2 of *Fundamentals of Interactive Computer Graphics* by Foley & Van Dam. It's all integer with about 3 adds and 1 multiply per pixel, i.e., about as fast as you can get in software on raster displays. Ken Lee -- klee@daisy.uucp Daisy Systems Corp., Interactive Graphics Tools Dept.
chasm@killer.DALLAS.TX.US (Charles Marslett) (02/16/89)
In article <399@peritek.UUCP>, dig@peritek.UUCP (David Gotwisner) writes: > > I am looking for an algorithm (or code) which will allow circle > generation onto a graphics device which drives a monitor with non-square > pixels. If any of you know of anything that may help me, please let me > know. I think that an efficient ellipse algorithm would work also. The Demo program provided with STB VGA cards has an ellipse subroutine that is derived from an article in Dr. Dobbs Journal perhaps 2 or 3 years ago -- the article described the extension of the standard straight line Bresenham (sp?) alogorithm to arbitrary conic sections. I think the original NASA paper describing the algorithm described this extension, but having never seen it, I do not know for sure. > Also, if you could refer me to some literature, this would also help. > > Thanks in advance. > > Dave Gotwisener =========================================================================== Charles Marslett STB Systems, Inc. <== Apply all standard disclaimers Wordmark Systems <== No disclaimers required -- that's just me chasm@killer.dallas.tx.us
smith@joshua.math.ucla.edu (02/17/89)
In article <399@peritek.UUCP> dig@peritek.UUCP (David Gotwisner) writes:
I am looking for an algorithm (or code) which will allow
circle generation onto a graphics device which drives a
monitor with non-square pixels . . .
What is needed is a fast way of computing x[n] = r*cos [nu] and
y[n] = r*sin [nu] for n = 0, 1, 2, . . . where u is a small angle.
Let a be chosen so that a = 2*cos u. Then one can verify immediately
that
x[n] = a*x[n-1] - x[n-2] and y[n] = a*y[n-1] - y[n-2],
for n = 2, 3, 4, . . . It is easy to check that this recurrence is
stable and accurate. Thus, with the starting values x[0], x[1], y[0],
y[1], a one can compute the coordinates of each point (x[n], y[n])
with two multiplications and two subtractions (if the circle is not
centered at the origin, then two more additions are necessary). By
appropriate scaling, integer arithmetic may be used.
If one uses differences, then more accuracy is obtainable and one can
replace the multiplcation by a right shift. Put
e = 2 - 2*cos u = 2 - a.
In most applications e will be quite small. Put
dx[n] = x[n] - x[n-1] and dy[n] = y[n] - y[n-1].
Then one obtains the recurrences
dx[n] = dx[n-1] - e*x[n-1] x[n] = x[n-1] + dx[n-1],
dy[n] = dy[n-1] - e*y[n-1] y[n] = y[n-1] + dy[n-1].
This can be very attractive if the original angle u is chosen so that
e is a negative power of 2. For then multiplication by e amounts
to a right shift. Here the required starting values are x[0], dx[0],
y[0], dy[0], e. Care should be used in computing these.
smitty
Douglas Smythe
Internet: smith@math.ucla.edu
UUCP: ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!smithstevens@hsi.UUCP (Richard Stevens) (02/17/89)
/*
* Draw an ellipse.
*
* The algorithm is from "An Efficient Ellipse-Drawing Algorithm" by
* Jerry R. Van Aken, IEEE CG&A, September 1984, pp. 24-35,
* specifically, Figure 10 on page 32.
*/
#include "plot.h" /* need definition of PLOT() */
ellipse(centerx, centery, a, b)
int centerx, centery; /* center of ellipse, in device coordinates */
int a, b; /* a = "radius" in x, b = "radius" in y */
{
register long d1, d2;
register short x, y;
register long t1, t2, t3, t4, t5, t6, t7, t8, t9;
/* intermediate terms to speed up loop */
t1 = a * a; t2 = t1 << 1; t3 = t2 << 1;
t4 = b * b; t5 = t4 << 1; t6 = t5 << 1;
t7 = a * t5; t8 = t7 << 1; t9 = 0L;
d1 = t2 - t7 + (t4 >> 1); /* error terms */
d2 = (t1 >> 1) - t8 + t5;
x = a;
y = 0;
while (d2 < 0) { /* region 1 of ellipse */
/* draw 4 points using symmetry */
PLOT(centerx + x, centery + y);
PLOT(centerx + x, centery - y);
PLOT(centerx - x, centery + y);
PLOT(centerx - x, centery - y);
y++; /* always move up here */
t9 += t3;
if (d1 < 0) { /* move straight up */
d1 += t9 + t2;
d2 += t9;
} else { /* move up and left */
x--;
t8 -= t6;
d1 += t9 + t2 - t8;
d2 += t9 + t5 - t8;
}
}
do { /* region 2 of ellipse */
/* draw 4 points using symmetry */
PLOT(centerx + x, centery + y);
PLOT(centerx + x, centery - y);
PLOT(centerx - x, centery + y);
PLOT(centerx - x, centery - y);
x--; /* always move left here */
t8 -= t6;
if (d2 < 0) { /* move up and left */
y++;
t9 += t3;
d2 += t9 + t5 - t8;
} else /* move straight left */
d2 += t5 - t8;
} while (x >= 0);
}
-------------------------------------------------------------
Richard Stevens
Health Systems International, New Haven, CT
stevens@hsi.com
... { uunet | yale } ! hsi ! stevensjfh@brunix (John Forbes Hughes) (02/18/89)
In article <1311@ndmath.UUCP> krueger@ndmath.UUCP (Andreas Krueger) writes: >In article <399@peritek.UUCP>, dig@peritek.UUCP (David Gotwisner) writes: >> >> I am looking for an algorithm (or code) which will allow circle >> generation onto a graphics device which drives a monitor with non-square >> pixels. > >Drawing a circle on a device with non-square pixels is >equivalent to drawing an ellipse on a monitor with square pixels. > [Analytic geometry deleted] >I've just been teaching this stuff in a third semester calculus course > [...] >Now let x run from 0 to a^2/sqrt(a^2+b^2) in steps of 1 (pixel). >For each such x, compute y by the above formula, which >when solved for y yields y = (b/a)*sqrt(a^2 - x^2). > [More deletion] >From this, you can write the code yourself, I'd say. [...] If it >turns out that the arthmetic is too slow, you'll have to increase >your steps from 1 to some larger number and draw connecting lines ... Well, I've just been writing a book (Foley, van Dam, Feiner and Hughes) about this, and the method above is not too clever. It uses floating point arithmetic, sqrt, and doesn't handle the case of non-integer center/radius properly. Here's a different solution: Assumptions: Your ellipse is aligned vertically (i.e. not rotated), and the center (h, k) is given in rational numbers with denominator d. Also, the eccentricity is small (since you say it's for a raster device, I assume the pixel aspect ratio (length/width) is near one). I also assume that the major and minor radii (a and b) are rational with denominator d. (1) Write eqn for the ellipse: (b(x - h))^2 + (a(y - k))^2 - (abR)^2 = S(x, y) = 0 (2) Multiply through by 4d^2 and expand out to a form like this S(x, y) = Ax^2 + Cy^2 + Dx + Ey + F = 0; (3) Observe that A...E are all integers divisible by 4. F is not, so round it off. Important observation: if S(x, y) > 0 at an integer (or half-integer) point (x, y), it will still be >0 after rounding F, since rounding changes the value by less than one. Henceforth F refers to the rounded value of F. (4) Start at the pixel (x, y) = (ROUND(h), ROUND(k + b)), draw this pixel. Compute S(x+1, y - 1/2). If this is > 0, then move from (x, y) to (x+1, y-1) and draw. If it is < 0, then move from (x, y) to (x + 1, y) and draw. Continue this process until you reach the point where 2Ax + D > 2Cy + E. You have drawn one eighth of your ellipse. The other 7 octants are a (very tedious) exercise. IMPORTANT NOTE: recomputing S(x + 1, y - 1/2) for each (x, y) is expensive! You can save a lot of time as follows: Note that you currently know either S(x, y - 1/2) or S(x, y+1/2). TO compute S(x + 1, y - 1/2), in the first case you just add dE = 2Ax + D; in the second case you add dSE = 2Ax + D + 2Cy - E; A rough approximation of the correct loop now looks like this: INITIALIZE EVERYTHING IN SIGHT, and then... while (gradX < gradY) plot(x, y) dE = dE + 2A /* compute new value of dE from previous one */ gradX = gradX + 2 /* compute new gradient values */ if (last_move == E) /* Same for dSE */ dSE = dSE + 2A else dSE = dSE + 2A - 2C gradY = gradY - 2 /* moved SE, so gradY changes, too */ if (last_move == E) S = S + dE else S = S + dSE x = x + 1 /* move to correct new point */ if (S > 0) y = y-1 last_move = SE /* moved to southeast */ else last_move = E /* moved east -- no change in y */ end-while Note that for each pixel, we do about 3 additions (the numbers 2A, 2C, etc should all be precomputed) and a few compares. This should run about a billion :-) times faster than any routine calling for square roots. Also note that if your center is at an integer point, then you can actually draw only 1/4 of the ellipse and use reflections to draw the other points.If it's not at an integer center, this doesn't work. All of this is a fairly trivial extension of the Midpoint Algorithm for scan-converting circles. Foley and van Dam (1st edition) give a description of another scan converter for circles which can be adapted in the same way. Now, would you like antialiasing too??? -John Hughes, "the 4th author"
dan@ingr.com (Dan Webb) (02/24/89)
After skimming through all the replies to the question of a fast ellipse algorithm, I have yet to see the algorithm used by the Macintosh, which happens to be very fast and mathematically perfect. Why doesn't anyone seem to know what it is? Is it proprietary? Apple? R. Dan Webb UUNET: uunet!ingr!dan INET: dan@ingr.com
jurjen@cwi.nl (Jurjen N.E. Bos) (02/24/89)
In article <4070@ingr.com> dan@ingr.com (Dan Webb) writes: >After skimming through all the replies to the question of a fast ellipse >algorithm, I have yet to see the algorithm used by the Macintosh, which >happens to be very fast and mathematically perfect. Why doesn't anyone >seem to know what it is? Is it proprietary? Apple? I'm sorry to correct you, but the (very fast) algorithm by the Mac is not mathematically perfect. You'll find out by drawing a very slim ellipse (say 5 pixels times 200 pixels): You get an ellipse with holes in it. I am a little bit disappointed by this fact; the routines are for the rest nearly perfect and very powerful. By the way, I also like to know how the routines used by the Mac. -- -- Jurjen N.E. Bos (jurjen@cwi.nl)
earleh@eleazar.dartmouth.edu (Earle R. Horton) (02/25/89)
In article <4070@ingr.com> dan@ingr.com (Dan Webb) writes: >After skimming through all the replies to the question of a fast ellipse >algorithm, I have yet to see the algorithm used by the Macintosh, which >happens to be very fast and mathematically perfect. Why doesn't anyone >seem to know what it is? Is it proprietary? Apple? This is a just a wild guess, but the Macintosh ellipse algorithm is probably just a hand-optimized variant of one of the algorithms posted here. Probably not extremely useful unless your CPU is a 68000-series. I would like to see an ellipse algorithm which allows me to specify the axes of the ellipse as something other than horizontal and vertical. Something like this: - __/ - / /\ -/ / / / / /- \_/_/ - / - / minor axis major axis Anybody got one? Earle R. Horton. 23 Fletcher Circle, Hanover, NH 03755--Graduate student. He who puts his hand to the plow and looks back is not fit for the kingdom of winners. In any case, 'BACK' doesn't work.
w-colinp@microsoft.UUCP (Colin Plumb) (02/25/89)
dan@ingr.com (Dan Webb) wrote: > After skimming through all the replies to the question of a fast ellipse > algorithm, I have yet to see the algorithm used by the Macintosh, which > happens to be very fast and mathematically perfect. Why doesn't anyone > seem to know what it is? Is it proprietary? Apple? I don't know what it is, but it's not perfect. Very extreme ellipses have holes in them. At least, that's the case with the 64K ROMs. I don't know about the more recent ones. There are plenty of disassemblied of the Mac ROMs floating around, although Apple gets mad if they're too prominent. -- -Colin (uunet!microsoft!w-colinp) "Don't listen to me. I never do."
chas@gtss.gatech.edu (Charles Cleveland) (02/25/89)
In article <4070@ingr.com> dan@ingr.com (Dan Webb) writes:
)After skimming through all the replies to the question of a fast ellipse
)algorithm, I have yet to see the algorithm used by the Macintosh, which
)happens to be very fast and mathematically perfect. Why doesn't anyone
)seem to know what it is? Is it proprietary? Apple?
)
) R. Dan Webb
) UUNET: uunet!ingr!dan
) INET: dan@ingr.com
When reading in BYTE, back in the days when it wasn't just a PC-clone
magazine with an occasional crust thrown to the Mac as an alternative
approach, someone claimed that the ellipse algorithm on the Mac was
deficient in that a subsequent area fill on the interior could leak out
to the exterior. The author stated that he could not understand why, when
other fast algorithms were available without this problem, Apple chose
to use the one they did.
Whether this is true or not (is it?), I have not seen the issue addressed in
the recent discussion of ellipse algorithms and would like to hear about it.
--
- It is better for civilization to be going down the drain than to be -
- coming up it. -- Henry Allen -
Charles Cleveland Georgia Tech School of Physics Atlanta, GA 30332-0430
UUCP: ...!gatech!gtss!chas INTERNET: chas@gtss.gatech.edudan@ingr.com (Dan Webb) (02/26/89)
in article <741@microsoft.UUCP>, w-colinp@microsoft.UUCP (Colin Plumb) says: > > dan@ingr.com (Dan Webb) wrote: >> After skimming through all the replies to the question of a fast ellipse >> algorithm, I have yet to see the algorithm used by the Macintosh, which >> happens to be very fast and mathematically perfect. Why doesn't anyone >> seem to know what it is? Is it proprietary? Apple? > > I don't know what it is, but it's not perfect. Very extreme ellipses have > holes in them. At least, that's the case with the 64K ROMs. I don't > know about the more recent ones. You have a different definition of the word "perfect." I'll explain what I mean by "mathematically perfect." The coordinate system on the Mac is a REAL Cartesian coordinate system, not the system of numbering individual pixels like most (all?) other computers do. (You may know this already.) A point is infinitely small, a line is infinitely thin, etc. So, all graphics concepts and primitives can be precisely defined. QuickDraw in general is one of the best graphics systems I've seen mainly because it is based on precise mathematical principles. Here's how you draw a perfect circle: Take a sheet a graph paper and draw a circle. Draw a another circle inside the first one, one "pixel" smaller. Fill in all pixels between the 2 circles that are at least 50% enclosed. These are the exact pixels the Mac's algorithm will draw. Of course, you can do the same for any ellipse. Drawing 2 concentric ellipses will leave no empty pixels between them and draw no pixel twice. Drawing an ellipse with a relatively large eccentricity will naturally leave gaps, which is what some people don't like about the algorithm. However, if this algorithm were implemented on a system with several shades of gray, you would get automatic anti-aliasing. Simply make the intensity of each pixel proportional to the percent of coverage. The gaps are there on a 2-color system because you're drawing the closest thing to the true ellipse. Filling in the gaps will theoretically cause the ellipse to look too thick in some places (but since it is so thin anyway, it may not be noticeable). I've seen the output of several other circle algorithms, and they all seem to appear deficient in one way or another. And the Mac's algorithm IS fast. I single-stepped through it on my Mac one time, and I saw only one initial multiply and divide (I may be wrong). - R. Dan Webb uunet!ingr!dan dan@ingr.com