home | news | contact | about
Drawing Circle Explained
13 October 2007, 05:57 AM
Before anything else examine the circles below. What is the characteristic?

circle-img001.pngcircle-img002.png

They are obviously round, which we describe a shape that is highly symmetrical and unchanging. The fact that a circle is symmetrical makes it very fitting for optimization. We can take advantage of this symmetry to implement fast circle plotter by calculating only the points in the first octant and copying those points to all other remaining octants. This is like cloning the first octant to produce the remaining seven while maintaining symmetry. The picture above-right can help to visualize this idea further. Examine each octant and we can immediately tell that they are all similar to each other. Finding the first octant is actually similar to finding all of the others. Because of this, the article will concentrate on the method of determining only the pixels in the first octant and replicating and mirroring it to get a full circle.

We will begin with a make it work first kind of implementation. A slow, crunchy, unoptimized code that work just fine, all in the name of simplicty and understanding. But first let us revise the good ol circle function we can find in our text book:

circle-equ001.gif

For practical reason we will assume both x0 and y0 as zero to make our circle centered at location (0,0) and of course to make it simpler and easier to implement. Now arrange the equation further to get,

circle-equ002.gif

a function of x because we know r (radius) will always be constant. Let us now look at the unoptimized implementation of above equation. The following image after the code shows an actual plotting of nine circles with increasing radius, plotted using the code.

public void circle(int x,int y,int radius,int color) {
    int i = 0, j = radius ;
    while (i<=j) {
        putpixel(x+i,y-j,color) ;
        putpixel(x+j,y-i,color) ;
        putpixel(x+i,y+j,color) ;
        putpixel(x+j,y+i,color) ;
        putpixel(x-i,y-j,color) ;
        putpixel(x-j,y-i,color) ;
        putpixel(x-i,y+j,color) ;
        putpixel(x-j,y+i,color) ;
        i++ ;
        j = (int)(Math.sqrt(radius*radius - i*i) + 0.5) ;
    }
}

circle-img003.png

As we can see from the code there are eight instances of putpixel suggesting each calculated point is plotted eight times at different locations. The observant reader may notice that weird +0.5, wondering what the hell is it for? The extra addition is to avoid early rounding of variable j which causes a somewhat pointy version of the plotted circle, if not ugly. Actually it is just a matter of preference, try removing that +0.5 and see for yourself - who knows we might just have different definition for the word ugly circle.

While the above implementation will work just fine, the presence of that expensive sqrt just made it tasteless. So the next thing we will do is to see how this costly calculation can be avoided by the use of discriminant equation. To explain this, lets get back to the drawing board and rearrange the circle equation,

circle-equ003.gif

Here the f(x,y) is a concept very useful in graphics programming called the discriminant function. It is used to partition or categorize f(x,y) based on the parameter x and y into, in our case, location of that point. If f(x,y) equals to zero, it means the point (x,y) is located on the right circle trajectory, a perfect pixel plot. If f(x,y) is below zero, the point (x,y) is inside the circle, while f(x,y) greater than zero would mean the point (x,y) is outside the circle. That may be a bit difficult to follow, but hopefully the diagram below will help give a better picture.

circle-img004.png

To draw our circle, we will be using x as the incrementing variable and y will be guessed for every x. The initial value for x will be zero, and y equals to radius, satisfying the condition f(0,r) = 0. Now the term guessing y for every x goes like this, keep incrementing x until f(x,y) suggest that the point (x,y) is starting to move outside the circle. If a point is outside the circle, f(x,y) > 0, we can bring it back inside by decreasing y by one.

circle-equ004.gif

The equation above shows that if we increase x by one, the next discriminant will be equal to the previous discriminant + 2x + 1. We can use this equation to find the new discriminant for every x for unchanging y. If y changes, as in condition f(x,y) > 0, update the discriminant with,

circle-equ005.gif

Now there is still one more thing to consider, remember that +0.5 mentioned earlier? If we want to take that into consideration f(x,y) must not start at f(0,r)=0, but at f(1,r-0.5),

circle-equ006.gif

Once we have determined how to calculate f(x,y), f(x+1,y), f(x+1,y-1), and f(1,r-0.5) for all x, we can start implementing a fully optimized circle function. Notice that operator shift right >>, and shift left << are used to represent division and multiplication respectively.

Here is the full implementation of a circle function,

public void circle(int x,int y,int radius,int color) {
    int discriminant = (5 - radius<<2)>>2 ;
    int i = 0, j = radius ;
    while (i<=j) {
        putpixel(x+i,y-j,color) ;
        putpixel(x+j,y-i,color) ;
        putpixel(x+i,y+j,color) ;
        putpixel(x+j,y+i,color) ;
        putpixel(x-i,y-j,color) ;
        putpixel(x-j,y-i,color) ;
        putpixel(x-i,y+j,color) ;
        putpixel(x-j,y+i,color) ;
        i++ ;
        if (discriminant<0) {                
            discriminant += (i<<1) + 1 ;
        } else {
            j-- ;
            discriminant += (1 + i - j)<<1 ;
        }
    }
}


[edit] should be (1 + i - j)<<1 not 1+ (i - j)<<1
Last edited on 16 May 2008

Comments

~what, 31 August 2014, 03:33 PM
I get an error message saying that putpixel isn\'t a method?
~Nikhil, 6 September 2014, 09:26 AM
Excellent Tutorials Keep it up...
~narf, 10 November 2014, 08:53 AM
This is awesome! It helped me a lot!

Thanks, it is really appreciated!
Post a comment~
Name*
1+3+4 is?*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.