Solved

Bresenhams Circle Algorithm

Posted on 1997-07-02
1
3,204 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
Comment Utility
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

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

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…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
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 be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

763 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

7 Experts available now in Live!

Get 1:1 Help Now