josephc@nntp-server.caltech.edu (Joseph I. Chiu) (01/25/91)
The discussion of ellipse drawing prompted me to write the article because
I had a hard time coming up with a fast circle-drawing routine when I needed
it for a programming class last year. I hope someone can use this...
Okay, here it goes (I'm going to go through the process from the start
because I need to jog my memory...)
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.
But, computing the sines and cosines of each point take a ridiculous part
of our drawing routine if we use the sine/cosine math library functions...
So we use a little bit of math...
We know, from our high-school math that:
sin (a+b) = sin (a) cos (b) + sin (b) cos (a)
cos (a+b) = cos (a) cos (b) - sin (a) sin (b)
So, let's say we start our circle at theta = 0; Well, the sin/cos values
for angle 0 is simply:
sin (0) = 0 cos (0) = 1
Now, to find the sin/cos values of the next point of interest, say at angle
theta(2), where theta(2) = theta + delta. By using the identities above,
sin (theta(2)) = sin (theta)*cos (delta) + sin(delta)*cos(theta)
cos (theta(2)) = cos (theta)*cos (delta) - sin(theta)*sin(delta)
By using the method again, we can find the values for sin/cos for the angle
theta(3) where theta(3) = theta + 2*delta = theta(2) + delta by:
sin (theta(3)) = sin (theta(2))*cos (delta) + sin (delta)*cos (theta(2))
cos (theta(3)) = cos (theta(2))*cos (delta) - sin (theta(2))*sin (delta)
And we can repeat the process for successive angles by repeating the process.
Note that in all cases, cos(delta) and sin(delta) are constant.
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;
}
Hope this helps...
-- Joseph
--
--
josephc@coil.caltech.edu ...Just another lost soul in the universebrandis@inf.ethz.ch (Marc Brandis) (01/25/91)
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
suhonen@kunto.jyu.fi (Timo Suhonen) (01/25/91)
In article <1991Jan25.055135.4172@nntp-server.caltech.edu> josephc@nntp-server.caltech.edu (Joseph I. Chiu) writes:
The discussion of ellipse drawing prompted me to write the article because
I had a hard time coming up with a fast circle-drawing routine when I needed
it for a programming class last year. I hope someone can use this...
[stuff about sin & cos removed]
You can't do anything _fast_ with sin and cos. The are too slow...
Find Bresenhams circle algorithm. You can code it with integers (ex. use
pixels as coordinates and convert your problem coordinats to screen
coordinates). I a PC (or Mac, Atari, Amiga, you name it) you can do the
whole thing into video memory to increase speed. The algorithm should be
found from any computer graphics book.
--
Timo Suhonen I am logged in, therefore I am suhonen@nic.funet.fi
suhonen@kunto.jyu.fi
Moderator for ftp site nic.funet.fi (128.214.6.100) Atari ST dir
Opinions(?) are mine (if not stolen), NOT those of Univ. of Jyvaskyla.