[comp.sources.wanted] looking for a fast ellipse algorithm

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!smith

stevens@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 ! stevens

jfh@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.edu

dan@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