Bresenham's circle/ellipse drawing algorithm

Algorithm

  Here the general approach is based on lines drawing and sqrt function. Using Bresenham's approach we exclude sqrt function, only sum and multiplication. It is supposed we have next graphical primitive methods MoveTo(), LineTo() and DrawPixel().

Let us have a look at the result of general and Bresenham's algorithms for circles.

C-code for the sqrt-based procedure for circle
void DrawCircle (int x, int y, int radius)
{
    int sqrRoot, prevSR, r_2;
    int i;
    
    prevSR = sqrRoot = 0;
    r_2 = radius * radius;
    for (i = 1; i < 2 * radius + 1; i++)
    {
        sqrRoot = sqrt (r_2 - ((radius - i)*(radius - i)));

        MoveTo(i - 1, radius + prevSR);
        LineTo(i, radius + sqrRoot);

        MoveTo(i - 1, radius - prevSR);
        LineTo(i, radius - sqrRoot);

        prevSR = sqrRoot;
    }
}

C-code for the Bresenham's procedure
void DrawCircle (int xc, int yc, int radius)
{
    int x = 0;
    int y = radius;
    int delta = 2 - 2 * radius;
    int error = 0;

    while(y >= 0)
    {
        DrawPixel (xc + x, yc + y);
        DrawPixel (xc - x, yc + y);
        DrawPixel (xc + x, yc - y);
        DrawPixel (xc - x, yc - y);

        error = 2 * (delta + y) - 1;

        if(delta < 0 && error <= 0) {
            ++x;
            delta += 2 * x + 1;
            continue;
        }
        error = 2 * (delta - x) - 1;
        if(delta > 0 && error > 0) {
            --y;
            delta += 1 - 2 * y;
            continue;
        }
        ++x;
        delta += 2 * (x - y);
        --y;
    }
}

Bresenham's circle is on the right, the radius is 20 pixels for both of them. Could you find 10 differences?


Let us continue with ellipses. C-code for the sqrt-based procedure for ellipce

void DrawEllipse (int x, int y, int width, int height)
{
    int sqrRoot, prevSR;
    int h_2, w_2;
    int  i;
    prevSR = sqrRoot = 0u;
    h_2 = height * height;
    w_2 = width * width;
    for (i = 1; i < 2 * width; i++)
    {
        sqrRoot = sqrt (h_2 - (((h_2 * (width - i)) * (width - i)) / w_2));

        MoveTo (i - 1, height + prevSR);
        LineTo (i, height + sqrRoot);

        MoveTo (i - 1, height - prevSR);
        LineTo (i, height - sqrRoot);

        prevSR = sqrRoot;
    }
}

C-code for the Bresenham's procedure to draw an ellipse in two steps

void DrawEllipse (int xc, int yc, int width, int height)
{
    int a2 = width * width;
    int b2 = height * height;
    int fa2 = 4 * a2, fb2 = 4 * b2;
    int x, y, sigma;

    /* first half */
    for (x = 0, y = height, sigma = 2*b2+a2*(1-2*height); b2*x <= a2*y; x++)
    {
        DrawPixel (xc + x, yc + y);
        DrawPixel (xc - x, yc + y);
        DrawPixel (xc + x, yc - y);
        DrawPixel (xc - x, yc - y);
        if (sigma >= 0)
        {
            sigma += fa2 * (1 - y);
            y--;
        }
        sigma += b2 * ((4 * x) + 6);
    }

    /* second half */
    for (x = width, y = 0, sigma = 2*a2+b2*(1-2*width); a2*y <= b2*x; y++)
    {
        DrawPixel (xc + x, yc + y);
        DrawPixel (xc - x, yc + y);
        DrawPixel (xc + x, yc - y);
        DrawPixel (xc - x, yc - y);
        if (sigma >= 0)
        {
            sigma += fb2 * (1 - x);
            x--;
        }
        sigma += a2 * ((4 * y) + 6);
    }
}

Bresenham's ellipse is also on the right, w = 20, h = 15 for both of them.



Appendix

1. Graham Toal added the ellipse-drawing code to one of the Scratch projects (a graphical programming language for kids) - http://scratch.mit.edu/projects/50039326/
Thanks Graham! =)



2. Well known screen recorder CamStudio uses sqrt-approach to visualize circle/ellipse cursor view. I would not say that they are circle and ellipse:


3. IE also uses terrible sqrt-approach to portray its progress bar.
 
 
 
Comments