Bresenham Algorithms in C

README

Some possible implementations of the Bresenham Algorithms in C.

The Bresenham line algorithm is an algorithm which determines which points in an
n-dimensional raster should be plotted in order to form a close approximation
to a straight line between two given points.
It is commonly used to draw lines on a computer screen, as it uses only integer
addition, subtraction and bit shifting, all of which are very cheap operations
in standard computer architectures.
It is one of the earliest algorithms developed in the field of computer graphics.
A minor extension to the original algorithm also deals with drawing circles.

While algorithms such as Wu's algorithm are also frequently used in modern
computer graphics because they can support antialiasing, the speed and simplicity
of Bresenham's line algorithm mean that it is still important.
The algorithm is used in hardware such as plotters and in the graphics chips of
modern graphics cards.
It can also be found in many software graphics libraries.
Because the algorithm is very simple, it is often implemented in either the
firmware or the hardware of modern graphics cards.

The label "Bresenham" is used today for a whole family of algorithms extending
or modifying Bresenham's original algorithm.


# EOF #

circle.c

// 'cx' and 'cy' denote the offset of the circle centre from the origin.
void
circle (int cx, int cy, int radius)
{
  int error = -radius;
  int x = radius;
  int y = 0;
 
  // The following while loop may altered to 'while (x > y)' for a
  // performance benefit, as long as a call to 'plot4points' follows
  // the body of the loop. This allows for the elimination of the
  // '(x != y') test in 'plot8points', providing a further benefit.
  //
  // For the sake of clarity, this is not shown here.
  while (x >= y)
  {
    plot8points (cx, cy, x, y);
    error += y;
    ++y;
    error += y;
    // The following test may be implemented in assembly language in
    // most machines by testing the carry flag after adding 'y' to
    // the value of 'error' in the previous step, since 'error'
    // nominally has a negative value.
    if (error >= 0)
    {
      --x;
      error -= x;
      error -= x;
    }
  }
}


void
plot8points (int cx, int cy, int x, int y)
{
  plot4points (cx, cy, x, y);
  if (x != y) plot4points (cx, cy, y, x);
}
 
// The '(x != 0 && y != 0)' test in the last line of this function
// may be omitted for a performance benefit if the radius of the
// circle is known to be non-zero.
void
plot4points (int cx, int cy, int x, int y)
{
  setPixel (cx + x, cy + y);
  if (x != 0) setPixel (cx - x, cy + y);
  if (y != 0) setPixel (cx + x, cy - y);
  if (x != 0 && y != 0) setPixel (cx - x, cy - y);
}


/* EOF */

plot_basic_bezier.c

void
plot_basic_bezier (int x0, int y0, int x1, int y1, int x2, int y2)
{                            
  int sx = x0 < x2 ? 1 : -1;
  int sy = y0 < y2 ? 1 : -1; /* step direction */
  int cur = sx * sy *((x0 - x1) * (y2 - y1) - (x2 - x1) * (y0 - y1)); /* curvature */
  int x = x0 - 2 * x1 + x2, y = y0 - 2 * y1 +y2, xy = 2 * x * y * sx * sy;
                                /* compute error increments of P0 */
  long dx = (1 - 2 * abs (x0 - x1)) * y * y + abs (y0 - y1) * xy - 2 * cur * abs (y0 - y2);
  long dy = (1 - 2 * abs (y0 - y1)) * x * x + abs (x0 - x1) * xy + 2 * cur * abs (x0 - x2);
                                /* compute error increments of P2 */
  long ex = (1 - 2 * abs (x2 - x1)) * y * y + abs (y2 - y1) * xy + 2 * cur * abs (y0 - y2);
  long ey = (1 - 2 * abs (y2 - y1)) * x * x + abs (x2 - x1) * xy - 2 * cur * abs (x0 - x2);
                              /* sign of gradient must not change */
  assert ((x0 - x1) * (x2 - x1) <= 0 && (y0 - y1) * (y2 - y1) <= 0); 
  if (cur == 0)
  { /* straight line */
    plotLine (x0, y0, x2, y2);
    return;
  }
  x *= 2 * x;
  y *= 2 * y;
  if (cur < 0)
  { /* negated curvature */
    x = -x;
    dx = -dx;
    ex = -ex;
    xy = -xy;
    y = -y;
    dy = -dy;
    ey = -ey;
  }
  /* algorithm fails for almost straight line, check error values */
  if (dx >= -y || dy <= -x || ex <= -y || ey >= -x)
  {        
    plotLine (x0, y0, x1, y1); /* simple approximation */
    plotLine (x1, y1, x2, y2);
    return;
  }
  dx -= xy;
  ex = dx + dy;
  dy -= xy; /* error of 1.step */
  for (;;)
  { /* plot curve */
    setPixel (x0, y0);
    ey = 2 * ex - dy; /* save value for test of y step */
    if (2 * ex >= dx)
    { /* x step */
      if (x0 == x2) break;
      x0 += sx;
      dy -= xy;
      ex += dx += y; 
    }
    if (ey <= 0)
    { /* y step */
      if (y0 == y2) break;
      y0 += sy;
      dx -= xy;
      ex += dy += x; 
    }
  }
}  
  

/* EOF */

plot_circle.c

void
plot_circle (int xm, int ym, int r)
{
   int x = -r, y = 0, err = 2-2*r; /* II. Quadrant */ 
   do {
      setPixel (xm-x, ym+y); /*   I. Quadrant */
      setPixel (xm-y, ym-x); /*  II. Quadrant */
      setPixel (xm+x, ym-y); /* III. Quadrant */
      setPixel (xm+y, ym+x); /*  IV. Quadrant */
      r = err;
      if (r >  x) err += ++x*2+1; /* e_xy+e_x > 0 */
      if (r <= y) err += ++y*2+1; /* e_xy+e_y < 0 */
   } while (x < 0);
}


/* EOF */

plot_ellipse_rect.c

void
plot_ellipse_rect (int x0, int y0, int x1, int y1)
{
   int a = abs (x1 - x0), b = abs (y1 - y0), b1 = b & 1; /* values of diameter */
   long dx = 4 * (1 - a) * b * b, dy = 4 * (b1 + 1) * a * a; /* error increment */
   long err = dx + dy + b1 * a * a, e2; /* error of 1.step */

   if (x0 > x1) { x0 = x1; x1 += a; } /* if called with swapped points */
   if (y0 > y1) y0 = y1; /* .. exchange them */
   y0 += (b + 1) / 2;
   y1 = y0-b1;   /* starting pixel */
   a *= 8 * a; b1 = 8 * b * b;
   do
   {
       setPixel (x1, y0); /*   I. Quadrant */
       setPixel (x0, y0); /*  II. Quadrant */
       setPixel (x0, y1); /* III. Quadrant */
       setPixel (x1, y1); /*  IV. Quadrant */
       e2 = 2 * err;
       if (e2 >= dx)
       {
          x0++;
          x1--;
          err += dx += b1;
       } /* x step */
       if (e2 <= dy)
       {
          y0++;
          y1--;
          err += dy += a;
       }  /* y step */ 
   } while (x0 <= x1);
   while (y0-y1 < b)
   {  /* too early stop of flat ellipses a=1 */
       setPixel (x0-1, y0); /* -> finish tip of ellipse */
       setPixel (x1+1, y0++); 
       setPixel (x0-1, y1);
       setPixel (x1+1, y1--); 
   }
}


/* EOF */

plot_line.c

void
plot_line (int x0, int y0, int x1, int y1)
{
  int dx =  abs (x1 - x0), sx = x0 < x1 ? 1 : -1;
  int dy = -abs (y1 - y0), sy = y0 < y1 ? 1 : -1; 
  int err = dx + dy, e2; /* error value e_xy */
 
  for (;;){  /* loop */
    setPixel (x0,y0);
    if (x0 == x1 && y0 == y1) break;
    e2 = 2 * err;
    if (e2 >= dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */
    if (e2 <= dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */
  }
}


/* EOF */

raster_circle.c

void
raster_circle (int x0, int y0, int radius)
{
  int f = 1 - radius;
  int ddF_x = 1;
  int ddF_y = -2 * radius;
  int x = 0;
  int y = radius;
 
  setPixel (x0, y0 + radius);
  setPixel (x0, y0 - radius);
  setPixel (x0 + radius, y0);
  setPixel (x0 - radius, y0);
  while (x < y)
  {
    // ddF_x == 2 * x + 1;
    // ddF_y == -2 * y;
    // f == x*x + y*y - radius*radius + 2*x - y + 1;
    if (f >= 0) 
    {
      y--;
      ddF_y += 2;
      f += ddF_y;
    }
    x++;
    ddF_x += 2;
    f += ddF_x;    
    setPixel (x0 + x, y0 + y);
    setPixel (x0 - x, y0 + y);
    setPixel (x0 + x, y0 - y);
    setPixel (x0 - x, y0 - y);
    setPixel (x0 + y, y0 + x);
    setPixel (x0 - y, y0 + x);
    setPixel (x0 + y, y0 - x);
    setPixel (x0 - y, y0 - x);
  }
}


/* EOF */

raster_circle.README

So.
 When we compare sum of N odd numbers to this algorithm we have.
 ddF_y = -2 * radius       is connected to last member of sum of N odd numbers.
                           This member has index equal to value of radius (integral). 
                           Since odd number is 2*n + 1 there is 1 handled elsewhere
                           or it should be -2*radius - 1
 ddF_x = 0                 should be 1. Because difference between two consecutive odd numbers is 2.
                           If so f += ddF_y + 1 is f+= ddF_y. Saving one operation.
 f = - radius + 1          Initial error equal to half of "bigger" step. 
                           In case of saving one addition it should be either -radius or -radius + 2.
 In any case there should be addition of 1 driven out of outer loop.
 So.
 f += ddF_y                Adding odd numbers from Nth to 1st. 
 f += ddF_x                Adding odd numbers from 1st to Nth. 1 is missing because it can be moved outside of loop.


# EOF #

Hello
Thanks for your work. I want to ask about how to transform rectangle box to circle box in darknet Yolo. image.c

void draw_box(image a, int x1, int y1, int x2, int y2, float r, float g, float b) {
//normalize_image(a);
int i;
if (x1 < 0) x1 = 0;
if (x1 >= a.w) x1 = a.w - 1;
if (x2 < 0) x2 = 0;
if (x2 >= a.w) x2 = a.w - 1;

if (y1 < 0) y1 = 0;
if (y1 >= a.h) y1 = a.h - 1;
if (y2 < 0) y2 = 0;
if (y2 >= a.h) y2 = a.h - 1;

for (i = x1; i <= x2; ++i) {
    a.data[i + y1*a.w + 0*a.w*a.h] = r;
    a.data[i + y2*a.w + 0*a.w*a.h] = r;

    a.data[i + y1*a.w + 1*a.w*a.h] = g;
    a.data[i + y2*a.w + 1*a.w*a.h] = g;

    a.data[i + y1*a.w + 2*a.w*a.h] = b;
    a.data[i + y2*a.w + 2*a.w*a.h] = b;
}
for(i = y1; i <= y2; ++i) {
    a.data[x1 + i*a.w + 0*a.w*a.h] = r;
    a.data[x2 + i*a.w + 0*a.w*a.h] = r;

    a.data[x1 + i*a.w + 1*a.w*a.h] = g;
    a.data[x2 + i*a.w + 1*a.w*a.h] = g;

    a.data[x1 + i*a.w + 2*a.w*a.h] = b;
    a.data[x2 + i*a.w + 2*a.w*a.h] = b;
}

}

void draw_box_width(image a, int x1, int y1, int x2, int y2, int w, float r, float g, float b) {
int i;
for (i = 0; i < w; ++i) {
draw_box(a, x1+i, y1+i, x2-i, y2-i, r, g, b);
}
}