Problems implementing Bresenhams circle algorithm

plaguebump · January 24, 2025, 2:44pm

Hi, i have a problem with implementing bresenhams circle algorithm, this code, which should create circles creates something that looks like a throwing star. While this is most definitively a unique feature, its also quite useless and absolutely not a circle.

#define absolute(num) (((num) > 0.0) ? (num) : (num) * (-1.0))
void
circularMoveTo (stepper motors[NROFMOTORS], v3i vNewPos, v3i vCenterOffset,
                char bClockwise)
{
  v3i vCenter = v3iAdd (vPos, vCenterOffset);
  int dR = absolute (v3iLength (vCenterOffset));
  while (!circleFinishCheck (vCenter, vNewPos))
    {
      // vector which contains next step direction: -1 for backwards, 1 for
      // forwards, 0 for off
      v3i vDirection = getNextCircleStep (vCenter, dR);
      vPos = v3iAdd (vPos, vDirection);
      step (motors, vDirection);
    }
}

// Helper functions
v3i
getNextCircleStep (v3i vCenter, int dR)

{
  v3i vDirection = {};
  v3i vCenterToPos = v3iSub (vPos, vCenter);
  // set step direction based on current quadrant
  v3i vInc = { 1, 1, 1 };
  if (vCenterToPos.y > 0)
    {
      vInc.x = 1;
    }
  else if (vCenterToPos.y < 0)
    {
      vInc.x = -1;
    }
  else // if on axxis, decide on other axxis to see which direction is needed
    {
      if (vCenterToPos.x > 0)
        {
          vInc.x = -1;
        }
      else
        {
          vInc.x = 1;
        }
    }
  if (vCenterToPos.x > 0)
    {
      vInc.y = -1;
    }
  else if (vCenterToPos.x < 0)
    {
      vInc.y = 1;
    }
  else // if on axxis, decide on other axxis to see which direction is needed
    {
      if (vCenterToPos.y > 0)
        {
          vInc.y = -1;
        }
      else
        {
          vInc.y = 1;
        }
    }
  // decide on which octant by longer axxis
  if (absolute (vCenterToPos.x) >= absolute (vCenterToPos.y))
    {
      // if deviation fro m with secondary step is smaller than without
      if (absolute (pow (vCenterToPos.x + vInc.x, 2)
                    + pow (vCenterToPos.y + vInc.y, 2) - pow (dR, 2))
          < absolute (pow (vCenterToPos.x + vInc.x, 2)
                      + pow (vCenterToPos.y, 2) - pow (dR, 2)))
        {
          vDirection.y = vInc.y;
        };
      vDirection.x = vInc.x;
    }
  // if other octant
  else if (absolute (vCenterToPos.x) < absolute (vCenterToPos.y))
    {
      // if error with secondary step is smaller than without
      if (absolute (pow (vCenterToPos.x + vInc.x, 2)
                    + pow (vCenterToPos.y + vInc.y, 2) - pow (dR, 2))
          < absolute (pow (vCenterToPos.x, 2)
                      + pow (vCenterToPos.y + vInc.y, 2) - pow (dR, 2)))
        {
          vDirection.x = vInc.x;
        }
      vDirection.y = vInc.y;
    }
  return vDirection;
}

char
circleFinishCheck (v3i v1, v3i v2)
{
  if (((v1.x > 0 && v2.x > 0) || (v1.x < 0 && v2.x < 0))
      && ((v1.y > 0 && v2.y > 0) || (v1.y < 0 && v2.y < 0)))
    {
      if (absolute (v1.x) > absolute (v1.y))
        {
          if (v1.y == v2.y)
            {
              return 1;
            }
          else if (v1.x == v2.x)
            {
              return 1;
            }
        }
    }
  return 0;
}

The step function steps one step in a given direction(a vector with -1, 1 or 0) and waits some miliseconds, depending on speed. It works perfectly fine in linear movement, so there is no issue there. The stepper type just contains the pins the motor is connencted to the arduino uno.The v3i type is a struct containing 3 integer elements, named x y and z.
Thanks for any help getting this to work.

alto777 · January 24, 2025, 3:13pm

We could guess, and maybe some of us fairly well, but it would be nice to see this in the context of a full sketch, and also see any libraries and other stuff you are needing to build it.

Or… you could take the maths out and present it in the absence of any application.

I don't see that you've use any serial.printing in there to confirm the values of the variabkes and that those values are properly informing the flow through your code.

a7

jremington · January 24, 2025, 4:16pm

Why bother with Breseham's algorithm? It was designed in 1962, when computers were as slow as plotters. You can afford to do trigonometry and floating point math on any modern MCU, and the code to draw a close approximation to a circle is trivial.

bobcousins · January 24, 2025, 4:16pm

It's pretty but not circular.

bobcousins · January 24, 2025, 4:59pm

I've achieved a better looking plot , which may be correct.

I hard-coded it to work for first quadrant.

The two issues appear to be

calculating the right increments for each quadrant.

I can;t see why you split it further into octants; I think one case is enough.

FWIW here's my version:

v3i
getNextCircleStep(v3i vCenter, int dR)

{
    v3i vDirection = {};
    v3i vCenterToPos = v3iSub(vPos, vCenter);
    // set step direction based on current quadrant
    v3i vInc = { 0, 0, 0 };

    if (vCenterToPos.y > 0)
    {
        vInc.x = -1;
    }
    else if (vCenterToPos.y < 0)
    {
        vInc.x = 1;
    }
    else // if on axxis, decide on other axxis to see which direction is needed
    {
        if (vCenterToPos.x > 0)
        {
            vInc.x = -1;
        }
        else
        {
            vInc.x = 1;
        }
    }

    if (vCenterToPos.x > 0)
    {
        vInc.y = -1;
    }
    else if (vCenterToPos.x < 0)
    {
        vInc.y = 1;
    }
    else // if on axxis, decide on other axxis to see which direction is needed
    {
        if (vCenterToPos.y > 0)
        {
            vInc.y = -1;
        }
        else
        {
            vInc.y = 1;
        }
    }

    vInc = { -1, 1, 0 }; // only works for first quadrant

    int errorX = absolute(pow(vCenterToPos.x + vInc.x, 2)
        + pow(vCenterToPos.y, 2)
        - pow(dR, 2));

    int errorY = absolute(pow(vCenterToPos.x, 2)
        + pow(vCenterToPos.y + vInc.y, 2)
        - pow(dR, 2));

    if (errorX < errorY)
    {
        vDirection.x = vInc.x;
    }
    else
    {
        vDirection.y = vInc.y;
    }

    // decide on which octant by longer axxis
#if 0
    if (absolute(vCenterToPos.x) >= absolute(vCenterToPos.y))
    {
    }
    // if other octant
    else if (absolute(vCenterToPos.x) < absolute(vCenterToPos.y))
    {
        // if error with secondary step is smaller than without
        if (absolute( pow(vCenterToPos.x , 2)
                    + pow(vCenterToPos.y + vInc.y, 2) - pow(dR, 2))
           < absolute(  pow(vCenterToPos.x, 2)
                      + pow(vCenterToPos.y + vInc.y, 2) - pow(dR, 2)))
        {
            vDirection.x = vInc.x;
        }
        vDirection.y = vInc.y;
    }
    #endif
    return vDirection;
}

DaveX · January 24, 2025, 5:11pm

Where did you get the algorithm? The pow()s don't seem very Bresenham-like.

jremington · January 24, 2025, 5:25pm

Bresenham-like circle algorithm (for point plotters)

procedure PlotCircle(CX, CY, R : longint);
begin
var X, Y : longint;
XChange, YChange : longint;
RadiusError : longint;
X := R;
Y := 0;
XChange := 1-2*R;
YChange := 1;
RadiusError := 0;
while ( X >= Y ) do
begin
Plot8CirclePoints(X,Y);
inc(Y);
inc(RadiusError, YChange);
inc(YChange,2);
if ( 2*RadiusError + XChange > 0 ) then
begin
dec(X);
inc(RadiusError, XChange);
inc(XChange,2)
end
end
end; {procedure PlotCircle}

procedure Plot8CirclePoints(X,Y : longint);
begin
PutPixel(CX+X, CY+Y); {point in octant 1}
PutPixel(CX-X, CY+Y); {point in octant 4}
PutPixel(CX-X, CY-Y); {point in octant 5}
PutPixel(CX+X, CY-Y); {point in octant 8}
PutPixel(CX+Y, CY+X); {point in octant 2}
PutPixel(CX-Y, CY+X); {point in octant 3}
PutPixel(CX-Y, CY-X); {point in octant 6}
PutPixel(CX+Y, CY-X) {point in octant 7}
end; {procedure Plot8CirclePoints}

bobcousins · January 24, 2025, 5:31pm

I think I have something working for all quadrants :

//
// bresenham.cpp 
//

#include <stdio.h>
#include <math.h>

#define absolute(num) (((num) > 0.0) ? (num) : (num) * (-1.0))

const int NROFMOTORS = 2;

typedef int stepper;

typedef struct {
    int x;
    int y;
    int z;
} v3i;

v3i vPos = { 0,0,0 };

v3i v3iAdd(v3i a, v3i b)
{
    a.x += b.x;
    a.y += b.y;
    return a;
}

v3i v3iSub(v3i a, v3i b)
{
    a.x -= b.x;
    a.y -= b.y;
    return a;
}

int v3iLength (v3i a)
{
    int len = sqrt(a.x * a.x + a.y * a.y);
    return len;
}

void step (stepper motors[NROFMOTORS], v3i vDirection)
{
    printf("pos %d, %d   step %d,%d\n", vPos.x, vPos.y, vDirection.x, vDirection.y);
}

bool circleFinishCheck(v3i v1, v3i v2)
{
    return (v1.x == v2.x) && (v1.y == v2.y);
}


// Helper functions
v3i
getNextCircleStep(v3i vCenter, int dR)

{
    v3i vDirection = {};
    v3i vCenterToPos = v3iSub(vPos, vCenter);
    // set step direction based on current quadrant
    v3i vInc = { 0, 0, 0 };

    if (vCenterToPos.x >= 0)
    {
        if (vCenterToPos.y >= 0)
        {
            // Q1
            printf("Q1 ");
            vInc.x = -1;
            vInc.y = 1;
        }
        else if (vCenterToPos.y < 0)
        {
            // Q4
            printf("Q4 ");
            vInc.x = 1;
            vInc.y = 1;
        }
    }
    else
    {
        if (vCenterToPos.y > 0)
        {
            // Q2
            printf("Q2 ");
            vInc.x = -1;
            vInc.y = -1;
        }
        else
        {
            // Q3
            printf("Q3 ");
            vInc.x = 1;
            vInc.y = -1;
        }
    }

    int errorX = absolute(pow(vCenterToPos.x + vInc.x, 2)
        + pow(vCenterToPos.y, 2)
        - pow(dR, 2));

    int errorY = absolute(pow(vCenterToPos.x, 2)
        + pow(vCenterToPos.y + vInc.y, 2)
        - pow(dR, 2));

    if (errorX < errorY)
    {
        vDirection.x = vInc.x;
    }
    else
    {
        vDirection.y = vInc.y;
    }
    return vDirection;
}


void
circularMoveTo(stepper motors[NROFMOTORS], v3i vNewPos, v3i vCenterOffset, bool bClockwise)
{
    v3i vCenter = v3iAdd(vPos, vCenterOffset);
    int dR = absolute(v3iLength(vCenterOffset));
    do 
    {
        // vector which contains next step direction: -1 for backwards, 1 for
        // forwards, 0 for off
        v3i vDirection = getNextCircleStep(vCenter, dR);
        vPos = v3iAdd(vPos, vDirection);
        step(motors, vDirection);
    } while (!circleFinishCheck(vPos, vNewPos));
}


int main()
{
    stepper motors[2];

    vPos = { 10,0,0 };
    v3i vCenterOffset = { -10,0,0 };
    v3i vNewPos = { 10,0,0 };

    circularMoveTo(motors, vNewPos, vCenterOffset, true);
}

Sample output :

Q1 pos 10, 1   step 0,1
Q1 pos 10, 2   step 0,1
Q1 pos 10, 3   step 0,1
Q1 pos 9, 3   step -1,0
Q1 pos 9, 4   step 0,1
Q1 pos 9, 5   step 0,1
Q1 pos 8, 5   step -1,0
Q1 pos 8, 6   step 0,1
Q1 pos 8, 7   step 0,1
Q1 pos 7, 7   step -1,0
Q1 pos 7, 8   step 0,1
Q1 pos 6, 8   step -1,0
Q1 pos 5, 8   step -1,0
Q1 pos 5, 9   step 0,1
Q1 pos 4, 9   step -1,0
Q1 pos 3, 9   step -1,0
Q1 pos 3, 10   step 0,1
Q1 pos 2, 10   step -1,0
Q1 pos 1, 10   step -1,0
Q1 pos 0, 10   step -1,0
Q1 pos -1, 10   step -1,0
Q2 pos -2, 10   step -1,0
Q2 pos -3, 10   step -1,0
Q2 pos -3, 9   step 0,-1
Q2 pos -4, 9   step -1,0
Q2 pos -5, 9   step -1,0
Q2 pos -5, 8   step 0,-1
Q2 pos -6, 8   step -1,0
Q2 pos -7, 8   step -1,0
Q2 pos -7, 7   step 0,-1
Q2 pos -8, 7   step -1,0
Q2 pos -8, 6   step 0,-1
Q2 pos -8, 5   step 0,-1
Q2 pos -9, 5   step -1,0
Q2 pos -9, 4   step 0,-1
Q2 pos -9, 3   step 0,-1
Q2 pos -10, 3   step -1,0
Q2 pos -10, 2   step 0,-1
Q2 pos -10, 1   step 0,-1
Q2 pos -10, 0   step 0,-1
Q3 pos -10, -1   step 0,-1
Q3 pos -10, -2   step 0,-1
Q3 pos -10, -3   step 0,-1
Q3 pos -9, -3   step 1,0
Q3 pos -9, -4   step 0,-1
Q3 pos -9, -5   step 0,-1
Q3 pos -8, -5   step 1,0
Q3 pos -8, -6   step 0,-1
Q3 pos -8, -7   step 0,-1
Q3 pos -7, -7   step 1,0
Q3 pos -7, -8   step 0,-1
Q3 pos -6, -8   step 1,0
Q3 pos -5, -8   step 1,0
Q3 pos -5, -9   step 0,-1
Q3 pos -4, -9   step 1,0
Q3 pos -3, -9   step 1,0
Q3 pos -3, -10   step 0,-1
Q3 pos -2, -10   step 1,0
Q3 pos -1, -10   step 1,0
Q3 pos 0, -10   step 1,0
Q4 pos 1, -10   step 1,0
Q4 pos 2, -10   step 1,0
Q4 pos 3, -10   step 1,0
Q4 pos 3, -9   step 0,1
Q4 pos 4, -9   step 1,0
Q4 pos 5, -9   step 1,0
Q4 pos 5, -8   step 0,1
Q4 pos 6, -8   step 1,0
Q4 pos 7, -8   step 1,0
Q4 pos 7, -7   step 0,1
Q4 pos 8, -7   step 1,0
Q4 pos 8, -6   step 0,1
Q4 pos 8, -5   step 0,1
Q4 pos 9, -5   step 1,0
Q4 pos 9, -4   step 0,1
Q4 pos 9, -3   step 0,1
Q4 pos 10, -3   step 1,0
Q4 pos 10, -2   step 0,1
Q4 pos 10, -1   step 0,1
Q4 pos 10, 0   step 0,1

Note that I ran the code on a PC, so ints are 4 bytes. pos() can be easily replaced with x * x construction. I guessed at the vector functions. printf() debugging can also be easily removed.

Porting to Arduino I leave as an exercise for the reader.

ETA: the bClockWise parameter is ignored, points are plotted CCW. I guess if you invert some things it will go the other way?

DaveX · January 24, 2025, 6:00pm

That's more bresenham-like. Taking advantage of circle symmetry was a big speed up for pixel coloring.

On the stepper CNC code I've worked with, breaking the arc up into short line segments was typical. Sometimes done inside the slicer/CAM program, and sometimes done in code (grbl, marlin)

Here's grbl's arc planning:

github.com/grbl/grbl

grbl/motion_control.c

9180094b7


      
          // Execute an arc in offset mode format. position == current xyz, target == target xyz, 
          // offset == offset from current xyz, axis_X defines circle plane in tool space, axis_linear is
          // the direction of helical travel, radius == circle radius, isclockwise boolean. Used
          // for vector transformation direction.
          // The arc is approximated by generating a huge number of tiny, linear segments. The chordal tolerance
          // of each segment is configured in settings.arc_tolerance, which is defined to be the maximum normal
          // distance from segment to the circle when the end points both lie on the circle.
          #ifdef USE_LINE_NUMBERS
            void mc_arc(float *position, float *target, float *offset, float radius, float feed_rate, 
              uint8_t invert_feed_rate, uint8_t axis_0, uint8_t axis_1, uint8_t axis_linear, uint8_t is_clockwise_arc, int32_t line_number)
          #else
            void mc_arc(float *position, float *target, float *offset, float radius, float feed_rate,
              uint8_t invert_feed_rate, uint8_t axis_0, uint8_t axis_1, uint8_t axis_linear, uint8_t is_clockwise_arc)
          #endif
          {
            float center_axis0 = position[axis_0] + offset[axis_0];
            float center_axis1 = position[axis_1] + offset[axis_1];
            float r_axis0 = -offset[axis_0];  // Radius vector from center to current location
            float r_axis1 = -offset[axis_1];
            float rt_axis0 = target[axis_0] - center_axis0;

This file has been truncated. show original

plaguebump · January 24, 2025, 7:11pm

I just figured out why my code doesnt work, it was just a most stupid typo:
if (absolute (vCenterToPos.x) <= absolute (vCenterToPos.y))
is the correct version, i wrote ">" instead. Damn, i feel really stupid now for bothering all of you, I searched for this the whole day.And i needed to adjust the end function.
Sorry for bothering you.

plaguebump · January 24, 2025, 7:16pm

Because they arent, the formulas i found for the original one didnt work, so i tried implementing something as close as possibile to the basic idea and nothing too optimized (first get something working at all before i start optimizing)

system · July 23, 2025, 7:16pm

This topic was automatically closed 180 days after the last reply. New replies are no longer allowed.

Topic		Replies	Views
CNC Easydriver stepper motor draw circle problem Motors, Mechanics, Power and CNC	20	11773	May 6, 2021
Any chance of a litle code help? Syntax & Programs	2	1039	May 6, 2021
multiple variables, simultaneous manipulation Programming	24	2982	May 5, 2021
circle code for Etch a sketch? Syntax & Programs	3	2344	May 6, 2021
Plotting Circles with Steppers Programming	10	7542	May 5, 2021

Problems implementing Bresenhams circle algorithm

Related topics