Solved

Bresenhams Circle Algorithm

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
std::atomic with custom class 6 186
FMX StringGrid1->Canvas->FillRect Problem 3 127
Exception thrown at 0x00007FFD5BC81F28 7 38
sorting efficency of sorting algorithm 30 99
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…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
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.
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.

932 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