Back to #amycoders Homepage
|Here comes the logical predecessor of the
Linedrawing-Compo: The Circledrawing-compo. The mission was to create a routine
drawing a circle with variable radius to a chunky-screen. There were both a fastest
and shortest compo again. The choice of the algorithm was free.
The deadline was: sunday, october 12st, 1997 at 21.00 CET
|The Results (shortest):|
|Nine people competed in this compo. The
routines were quite interesting and different. A lot of different ideas were involved. One
idea was the "bruteforce" approach - scanning the whole screen for the circle
with a pythagoras distance formula. These routines got incredible slow. The slowest
routine is more than 11,000 times slower, than the fastest one in this compo :)
But Trover whose routine won, did show that it is possible to do both a (relatively) fast and shor routine. He also contributed with a 36 bytes version, which needs only 40 rasterlines to draw the testcircles.
The routines in the "shortest" compo had to draw three circles. Two with a radius of 32 and one with a radius of 64. The testroutine is included in the contribution package, which can be downloaded at the bottom of this page.
|6.||R.A.Y & Sniper||44||23320 !||Bruteforce Pythagoras/sqrt|
*1 Routine was moved down a place due to its inaccuracy.
|The Results (fastest):|
|Also 9 routines were contributed here. The
circleroutines had to draw 504 Circles with 63 different radii, so always 8 circle with
the same radius. This lead to a problem with some routines using a kind of
"Bruteforce" approach again, by either using a very huge table or generating 128
subroutines, one for each radius. Since these routines speed depended a lot on the memory
usage their speed was dependant of the order, in which the circles were drawn. I did a
best case and a worst case timing for these routines. (written in parenthesis)
Using the best-case timing only would have been pretty unfair towards the other routines, since no everyday-application would sort the circles by size before drawing. So I used the average value of best and worst time to compare these special routines with the others.
This competition was won by Piru. His routine is generating subroutines for every radius, cleverly gathering pixels to .l and .w writes. Due to this it is very cache dependant. So the very clean and short routine by Blueberry, who became second, is faster in a lot of cases.
|1.||Piru||436||av. 492 (547/437)||One routine per radius|
|6.||Raylight||162||av. 564 (636/492)||One routine per radius|
|8.||Piru, second entry||292||av. 662 (723/601)||Big table|
*1 Please note, that I didnt take a too close look to the routines.
So routines marked as using Bresenham might also use a similar algorithm instead.
|How does it work ?|
|I am only describing the best two routines
of the "shortest-circleroutine" compo here. Download the whole package of
This routine is using the parametric equation of a circle: X=r*cos(t) ,Y=r*sin(t). The sinus and cosinus function is calculated by a recursive formula with a stepwidth of 1/256. So a full circle takes 2*pi*256 steps, which is enough to draw a closed circle. Read the Sinustable Generation Tutorial for further info. ("Another Algebraic Approach")
It is using a kind of "bruteforce" approach. It is stepping through the whole 256x256 array of the chunky buffer and calculating the distance from the midpoint of the circle for each pixel with the pythagoras formula. If the distance is between r+1 and r, the pixel is considered to be on the circle. (A rasterized circle has an area in fact.. :) )
Since a squareroot-routine , which would be needed for the formula d=sqrt(x^2+y^2), is extremly slow and not that short Piru used another trick. He divided d^2 by r. And checked for the range [r-1;r] r e Z then. This is mathematically not entirely correct (figure that out byself.. :) ) but it seems to be accurate enough, since the circles drawn with this routine are looking ok.
|In case you want to see the contributions code. Download the package here Please remember that, even if you can download these routines, they are still not public domain. Ask before using any of these routines, or give credits at least.|
Last change: 16.01.2001