Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Bresenhams Circle Algorithm

Posted on 1997-07-02
1
3,223 Views
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?

//THE CODE

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 */
    dx++;
    n+=invradius;
    dy = (radius * SIN_ACOS[n>>6]) >>16;
  }
}

void main()
{
  int i;
  setvmode(0x13);

  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);

  setvmode(0x03);
}
//

THANK YOU VERY MUCH... THIS IS VERY IMPORTANT!!!
0
Comment
Question by:kane020397
1 Comment
 
LVL 4

Accepted Solution

by:
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)

and

  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 jos@and.nl



0

Featured Post

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

861 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