Circle Drawing




Intro


Many would think that rendering circles would be a pretty trivial task. In most cases it is, making pie charts or drawing a couple of circles isn't that big of a problem. The underlying problem rears its head when we try to do it quickly. Following is two routines to draw a circle. The first will do fine when we just need to draw a couple of circles. The second will be usefull when we need to do it lightning fast!


Good Ole Sin-Cos


This method is really easy to use, you probably remember it from geometry in High School. Here's the code! 

void se::SlowCircle(long xcenter,long ycenter, long radius)
{ long x,y;
 for(float theta=0;theta < (2*M_PI);theta+=.01)
  { x=xcenter+(long)(radius*sin(theta));
    y=ycenter+(long)(radius*cos(theta));
    video->quickpixel(x,y,15);
  }
}

This routine is pretty simple. We use the old sin and cos and inrement theta from 0 to 2 PI. We can then make our circle a known radius by multiplying each sin and cos by the radius variable. The problem with this routine is that it uses the sin and cos functions. These are very slow and simply will not work for our uses. Also, we increment theta by 1/100ths every itteration until we reach 2PI. At best we will make a solid circle, but some points will be written multiple times. Even worse, with larger circles we will skip pixels. We made a circle, but at a very high cost. The next function will do things a lot better, please read on.

Better Methods


We can do a lot better than the first algorythm above. Firstly we can try to exploit the symmetry that the circle has inherit to it. Let's consider the equation to the right that we learned in school. We can use the positive and negative values of the square root to come up with a faster answer, but with a couple of complications. 
void se::SlowCircle(long xcenter,long ycenter, long radius)
{ long x,y,r2=radius*radius;
  for(long x=-radius;x<=radius;x++)
   { y=(short)sqrt(r2-(x*x));
     video->quickpixel(xcenter+x,ycenter+y,15);
     video->quickpixel(xcenter+x,ycenter-y,15);
   }
}

As we said, we know that at the very least, the top and bottom will mirror each other. Knowing that we can use the positive and negative values of the square root to plot our pixels. Notice that where the slope is greater than one, the circle is discontinuous. Before tackling this problem directly, we will take a slight stray from the norm and try optimizing this routine so that we can fully utilize its symmetry.

Firstly, lets make use of 4 way symmetry by using making a slight adjustment to the code.

void se::SlowCircle(long xcenter,long ycenter, long radius)
{ long x,y,r2=radius*radius;
  for(long x=0;x<=radius;x++)
   { y=(short)sqrt(r2-(x*x));
     video->quickpixel(xcenter+x,ycenter+y,15);
     video->quickpixel(xcenter+x,ycenter-y,15);
     video->quickpixel(xcenter-x,ycenter+y,15);
     video->quickpixel(xcenter-x,ycenter-y,15);
   }
}

We can mirror the circle by splitting it up into 4 quadrants. Our x will go from 0 to the radius and we will mirror the other 3 halves. Realize that even though we have cut down our computations, we still have the same problems inherint in the previous routine. Let's take it one step further!

void se::SlowCircle(long xcenter,long ycenter, long radius)
{ long x,y,r2=radius*radius;
  for(long x=0;x<=radius;x++)
   { y=(short)sqrt(r2-(x*x));
     video->quickpixel(xcenter+x,ycenter+y,15);
     video->quickpixel(xcenter+x,ycenter-y,15);
     video->quickpixel(xcenter-x,ycenter+y,15);
     video->quickpixel(xcenter-x,ycenter-y,15);
     video->quickpixel(xcenter+y,ycenter+x,15);
     video->quickpixel(xcenter+y,ycenter-x,15);
     video->quickpixel(xcenter-y,ycenter+x,15);
     video->quickpixel(xcenter-y,ycenter-x,15);
   }
}

This routine takes into account 8 way symmetry in the circle by taking all possible combinations of x and y
(+x,+y)(+x,-y)(-x,+y)(-x,-y)(+y,+x)(+y,-x)(-y,+x)(-y,-x)
Suddenly, the circle is complete!! By using the symmetry inherent in the circle we have made a routine that will always create a complete circle no matter what the radius is! The only big problem is that it uses the sqrt function which is really a cycle sucker! Luckily we DO have other methods at our disposal! 

void Circle(long xcenter,long ycenter,long radius)
{ long x=0;
  long y=radius;
  long p=(5-radius*4)/4;
  CirclePoint(xcenter,ycenter,x,y,4);
  while(x<y)
  { x++;
    if(p<0)
     {p+=2*x+1;
     }
    else{y--;p+=2*(x-y)+1;}
    CirclePoint(xcenter,ycenter,x,y,x);
  }
}

void CirclePoint(long cx,long cy,long x,long y,char c)
{ if(x==0)
  { video->quickpixel(cx,cy+y,c);
  video->quickpixel(cx,cy-y,c);
  video->quickpixel(cx+y,cy,c);
  video->quickpixel(cx-y,cy,c);
  }
else if(x==y)
 {video->quickpixel(cx+x,cy+y,c);
 video->quickpixel(cx-x,cy+y,c);
 video->quickpixel(cx+x,cy-y,c);
 video->quickpixel(cx-x,cy-y,c);
 }
else if(x<y)
 {video->quickpixel(cx+x,cy+y,c);
 video->quickpixel(cx-x,cy+y,c);
 video->quickpixel(cx+x,cy-y,c);
 video->quickpixel(cx-x,cy-y,c);
 video->quickpixel(cx+y,cy+x,c);
 video->quickpixel(cx-y,cy+x,c);
 video->quickpixel(cx+y,cy-x,c);
 video->quickpixel(cx-y,cy-x,c);
 }
}

This routine actually transforms the circle routine into a discriminating function. We can rewrite the normal equation for a circle as f(x,y)=x^2+y^2+r^2. When f(x,y)=0 we are on our circle. When it is greater than 0, we are outside our circle, and a negative result means we are inside the circle. Knowing this behavior we do some substitutions and voila! I'm not going into too much detail here because I haven't taken the time to fully realize the behavior of this routine (thank MIT). If you have any question, comments, complaints, whatever! send me some Feedback.