Xref: utzoo comp.graphics:4632 sci.math:5823 comp.sources.wanted:6526
Path: utzoo!attcan!uunet!ingr!dan
From: dan@ingr.com (Dan Webb)
Newsgroups: comp.graphics,sci.math,comp.sources.wanted
Subject: Re: looking for a fast ellipse algorithm
Message-ID: <4110@ingr.com>
Date: 25 Feb 89 20:34:19 GMT
References: <741@microsoft.UUCP>
Organization: Intergraph Corp. Huntsville, Al
Lines: 46

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