# Fast circle algorithm

3 messages
Open this post in threaded view
|

## 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.