Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!spool2.mu.edu!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!cernvax!chx400!bernina!neptune!inf.ethz.ch!brandis
From: brandis@inf.ethz.ch (Marc Brandis)
Newsgroups: comp.sys.ibm.pc.misc
Subject: Re: Fast circle drawing.
Message-ID: <22779@neptune.inf.ethz.ch>
Date: 25 Jan 91 08:15:03 GMT
References: <1991Jan25.055135.4172@nntp-server.caltech.edu>
Sender: news@neptune.inf.ethz.ch
Reply-To: brandis@inf.ethz.ch (Marc Brandis)
Organization: Departement Informatik, ETH, Zurich
Lines: 42

In article <1991Jan25.055135.4172@nntp-server.caltech.edu> josephc@nntp-server.caltech.edu (Joseph I. Chiu) writes:
>The traditional 'easy' way of drawing a circle is done by multiplying the
>'radius' of the circle with the sines and cosines of the loop (i.e., from
>zero to 360 degrees), and connecting the points.

OOOOhh, .... I think no serious programmer uses this. If you are right, this
would at least be a good explanation why some graphic programs are so slow ...
-:)

>Thus, to express the idea in C code:
>
>sine = 0; cosine = 1;    /* Starting sine/cosine values at theta = 0 */
>sine_delta = sin(delta_angle); cosine_delta = cos(delta_angle);
>
>for (i = 0; i < N; i++) {
>   new_sine = sine * cosine_delta + sine_delta * cosine;
>   new_cosine = cosine * cosine_delta - sine * sine_delta;
>   /* line drawing goes here */
>   sine = new_sine;  cosine = new_cosine;
>   }
>

While your reasoning is correct and the solution works (and certainly is much
faster than computing the sine and cosine in each step), this solution is far
from optimal. First, you need a lot of floating-point arithmetic, which is 
typically slow on CPUs used for graphics (I mean, if you have very fast FP,
it is also very likely that you have a specialized graphics processor, so you
do not need your routine). There is a well-known algorithm for drawing 
circles and ellipses by Bresenham (the same guy that first published a fast
way to draw lines on a raster display), and that one uses only integer
arithmetic and does have less operations than your loop.

Sorry, I do not have any english reference to it at hand. But I am sure you
can find it in good books on computer graphics.

-- Marc


Marc-Michael Brandis
Computer Systems Laboratory, ETH-Zentrum (Swiss Federal Institute of Technology)
CH-8092 Zurich, Switzerland
email: brandis@inf.ethz.ch