Fast circle algorithm

[jamesleibert]

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_algorithm
The "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.

[cadet1620]

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 Kennedy

There is also a variant for ellipses.

A Fast Bresenham Type Algorithm For Drawing Ellipses, John Kennedy


There 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

[jamesleibert]

Definitely true. For large circles, surely it must be worthwhile, if only to avoid the additional function calls.

At some point, I did write a version that checked for this, but it ended up being awkward having one set of code for four octants and another for the other four, and different code for filled circles vs empty circles. I'll redo it and post it at some point if I can make it neat.

I can't find a good paper explaining the origin and rationale for the fudges in the integer version.