Xref: utzoo comp.graphics:4531 sci.math:5739 comp.sources.wanted:6424
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!oberon!sm.unisys.com!ucla-cs!math.ucla.edu!smith
From: smith@joshua.math.ucla.edu
Newsgroups: comp.graphics,sci.math,comp.sources.wanted
Subject: Re: looking for a fast ellipse algorithm
Keywords: ellipse, graphics, circle
Message-ID: <474@sunset.MATH.UCLA.EDU>
Date: 16 Feb 89 19:08:45 GMT
References: <399@peritek.UUCP>
Sender: news@MATH.UCLA.EDU
Reply-To: smith@MATH.UCLA.EDU ()
Organization: UCLA Mathematics Department
Lines: 45

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