Xref: utzoo comp.graphics:4479 sci.math:5702 comp.sources.wanted:6373
Path: utzoo!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!wasatch!cs.utexas.edu!rutgers!att!mtunb!dmt
From: dmt@mtunb.ATT.COM (Dave Tutelman)
Newsgroups: comp.graphics,sci.math,comp.sources.wanted
Subject: Re: looking for a fast ellipse algorithm
Keywords: ellipse, graphics, circle
Message-ID: <1403@mtunb.ATT.COM>
Date: 15 Feb 89 18:42:53 GMT
References: <399@peritek.UUCP> <1311@ndmath.UUCP>
Reply-To: dmt@mtunb.UUCP (Dave Tutelman)
Organization: AT&T Bell Labs - Lincroft, NJ
Lines: 51

>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					|
+---------------------------------------------------------------+