Bresenhams Circle Algorithm

Posted on 1997-07-02
Last Modified: 2008-02-26
This is problem I understand his line algorithm but not his circle.  This is the one I have got can some one explain what he does with these variables and why he does it.  I mean actually explain line by line what he does and why?


typedef long           fixed16_16;
fixed16_16 SIN_ACOS[1024];

 *  circle_fast                                                           *
 *    Draws a circle by using fixed point numbers and a trigonometry      *
 *    table.                                                              *

void circle(int x,int y, int radius, byte color)
  fixed16_16 n=0,invradius=(1/(float)radius)*0x10000L;
  int dx=0,dy=radius-1;
  word dxoffset,dyoffset,offset = (y<<8)+(y<<6)+x;

  while (dx<=dy)
    dxoffset = (dx<<8) + (dx<<6);
    dyoffset = (dy<<8) + (dy<<6);
    VGA[offset+dy-dxoffset] = color;  /* octant 0 */
    VGA[offset+dx-dyoffset] = color;  /* octant 1 */
    VGA[offset-dx-dyoffset] = color;  /* octant 2 */
    VGA[offset-dy-dxoffset] = color;  /* octant 3 */
    VGA[offset-dy+dxoffset] = color;  /* octant 4 */
    VGA[offset-dx+dyoffset] = color;  /* octant 5 */
    VGA[offset+dx+dyoffset] = color;  /* octant 6 */
    VGA[offset+dy+dxoffset] = color;  /* octant 7 */
    dy = (radius * SIN_ACOS[n>>6]) >>16;

void main()
  int i;

  for(i=0;i<1024;i++)                 /* create the sin(arccos(x)) table. */
    SIN_ACOS[i]=sin(acos((float)i/1024)) * 0x10000L;

  circle(160, 100, 50, 7);


Question by:kane020397
1 Comment

Accepted Solution

jos010697 earned 100 total points
ID: 1164233
Have a look at it this way:

The x,y coordinates of a circle are:

   x= r*cos(n)
   y= r*sin(n)

where n is the angle and r the radius (I stick to the variable
naming given in your code); so

   n= acos(x/r)


  y=  r*sin(acos(x/r)

This is basically what happens in function 'circle'. The
angle 'n' is incremented by 1/r (i.e. 'invradius') at every
iteration of the loop. Variable 'x' is adjusted directly 'dx++'
and variable 'dy' is adjusted by looking up the appropriate
sin(acos(x/r)) value in the table.

FYI, this is not a very efficient circle drawing algorithm
(and it has nothing to do with Bresenham either).
The original Bresenham alogirhm just needs a couple
of additions and a few shifts per iteration; no precomputed
table of arccosines and sines is needed ...

kind regards,

Jos aka


Featured Post

Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

813 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now