# Fast circle algorithm

3 messages
Open this post in threaded view
|
Report Content as Inappropriate

## Fast circle algorithm

 I found a nice algorithm for drawing circles that avoids all math operations apart from addition and subtraction. The resulting speed up is pretty impressive. function void drawCircle(int x, int y, int r) {         var int i, j;         var int counter;         let i = 0;         let j = r;         let counter = 3 - (r + r);         do Screen.drawHorizLineSegment(x - r, x + r, y);         while (j > i) {             if (counter < 0) {                 let counter = counter + 6 + i + i + i + i;                 let i = i + 1;             } else {                 if ((counter > 0) & (j > i)) {                         let j = j - 1;                         let counter = (counter + 4) - (j + j + j + j);                 }             }             do Screen.drawHorizLineSegment(x - i, x + i, y + j);             do Screen.drawHorizLineSegment(x - i, x + i, y - j);             do Screen.drawHorizLineSegment(x - j, x + j, y + i);             do Screen.drawHorizLineSegment(x - j, x + j, y - i);         }         return;     } The algorithm is due to Brasenham: https://en.wikipedia.org/wiki/Midpoint_circle_algorithmThe "fudge factors" in the version I used seem to give a slight improvement to the shape when using integers instead of floating points. This makes a rough approximation of 1/8th of the circle by tracking its gradient. It uses symmetry to complete the rest. It's surprisingly accurate for circles of radius between 5 and 80 pixels. For an unfilled circle you can just plot the end-points. For a filled circle, you will need to implement a fast horizontal line-drawing routine, but the Hack screen layout makes it easy to draw 16 pixels at a time and only the first and last words need to be masked.
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Fast circle algorithm

 Administrator This post was updated on . Here is a paper that describes this algorithm and includes a much more readable derivation than the Wikipedia page. A Fast Bresenham Type Algorithm For Drawing Circles, John KennedyThere is also a variant for ellipses. A Fast Bresenham Type Algorithm For Drawing Ellipses, John KennedyThere is the potential for a line drawing optimization in your routine, but it makes the code much uglier and you must be careful that it doesn't slow down small circles too much. On larger circles you draw the upper and lower lines multiple times when j doesn't change, each time drawing it 2 pixels wider. With the ever popular "flag and a kludge" you can delay drawing the outer lines until j changes and draw the lines once at their final width. --Mark