We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you a podcast all about Citrix Workspace, moving to the cloud, and analytics & intelligence. Episode 2 coming soon!Listen Now

x

# Bresenhams Circle Algorithm

on
Medium Priority
3,289 Views
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)
{
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++;
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!!!
Comment
Watch Question

## View Solution Only

Commented:
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

Not the solution you were looking for? Getting a personalized solution is easy.

##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile