Bresenham's Line Algorithm

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
m (adding wikipedia link to replace a link to a non-existent local page)
Line 1: Line 1:
Taken from wikipedia: (they will delete this code soon, I thought it might find a welcome home here)
+
Previous article deleted due to crappiness. Here's an improved C++ version (as in the previous article plot() draws a pixel at (x, y):
  
An implementation of [http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm Bresenham s line algorithm] in [[C_programming_language|C]] follows. The plot() function is not shown and is assumed to render a single point of the line in the chosen color.  This variation produces solid lines of a uniform color.
+
#ifndef ABS
 +
#  define ABS(x) ((x)>0?(x):-(x))
 +
#endif
  
void drawline2d(int x0, int y0, int x1, int y1, int color)
+
////////////////////////////////////////////////////////////////////////////////
{
+
void Bresenham(unsigned x1,
        int i;
+
    unsigned y1,
        int steep = 1;
+
    unsigned x2,
        int sx, sy;  /* step positive or negative (1 or -1) */
+
    unsigned y2)
        int dx, dy;  /* delta (difference in X and Y between points) */
+
{
        int e;
+
    unsigned delta_x = ABS(x2 - x1) << 1;
 
+
    unsigned delta_y = ABS(y2 - y1) << 1;
        /*
+
        * inline swap. On some architectures, the [http://en.wikipedia.org/wiki/Xor_swap_algorithm XOR trick] may be faster
+
        */
+
        int tmpswap;
+
#define SWAP(a,b) tmpswap = a; a = b; b = tmpswap;
+
 
+
        /*
+
        * optimize for vertical and horizontal lines here
+
        */
+
       
+
        dx = abs(x1 - x0);
+
        sx = ((x1 - x0) > 0) ? 1 : -1;
+
        dy = abs(y1 - y0);
+
        sy = ((y1 - y0) > 0) ? 1 : -1;
+
        if (dy > dx) {
+
                steep = 0;
+
                SWAP(x0, y0);
+
                SWAP(dx, dy);
+
                SWAP(sx, sy);
+
        }
+
        e = (dy << 1) - dx;
+
        for (i = 0; i < dx; i++) {
+
                if (steep) {
+
                        plot(x0,y0,color);
+
                } else {
+
                        plot(y0,x0,color);
+
                }
+
                while (e >= 0) {
+
                        y0 += sy;
+
                        e -= (dx << 1);
+
                }
+
                x0 += sx;
+
                e += (dy << 1);
+
        }
+
}
+
  
A slightly more optimized version of the above
+
    // if x1 == x2 or y1 == y2, then it does not matter what we set here
(might be a bit harder to read, though):
+
    char ix = x2 > x1?1:-1;
 +
    char iy = y2 > y1?1:-1;
  
void drawline2d(int x0, int y0, int x1, int y1, int color) {
+
    plot(x1, y1);
    int i;
+
 
     int sx, sy;  /* step positive or negative (1 or -1) */
+
     if (delta_x >= delta_y)
     int dx, dy;  /* delta (difference in X and Y between points) */
+
     {
    int dx2, dy2;
+
        // error may go below zero
    int e;
+
        int error = delta_y - (delta_x >> 1);
    int temp;
+
 
 
+
         while (x1 != x2)
    dx = x1 - x0;
+
         {
    sx = (dx > 0) ? 1 : -1;
+
            if (error >= 0)
    if (dx < 0)
+
             {
        dx = -dx;
+
                if (error || (ix > 0))
 
+
                 {
    dy = y1 - y0;
+
                    y1 += iy;
    sy = (dy > 0) ? 1 : -1;
+
                    error -= delta_x;
    if (dy < 0)
+
                }
         dy = -dy;
+
                // else do nothing
 
+
    dx2 = dx << 1; /* dx2 = 2 * dx */
+
    dy2 = dy << 1; /* dy2 = 2 * dy */
+
 
+
    if (dy <= dx) { /* steep */
+
         e = dy2 - dx;
+
 
+
        for (i = 0; i <= dx; ++i) {
+
             plot(x0, y0, color);
+
 
+
            while (e >= 0) {
+
                 y0 += sy;
+
                e -= dx2;
+
 
             }
 
             }
 
+
            // else do nothing
             x0 += sx;
+
 
             e += dy2;
+
             x1 += ix;
 +
             error += delta_y;
 +
 
 +
            plot(x1, y1);
 
         }
 
         }
     } else {
+
     }
         /* swap x0 <-> y0 */
+
    else
         temp = x0;
+
    {
        x0 = y0;
+
         // error may go below zero
        y0 = temp;
+
         int error = delta_x - (delta_y >> 1);
 
+
 
        /* swap dx <-> dy */
+
         while (y1 != y2)
        temp = dx;
+
         {
        dx = dy;
+
            if (error >= 0)
        dy = temp;
+
             {
 
+
                if (error || (iy > 0))
        /* swap dx2 <-> dy2 */
+
                {
        temp = dx2;
+
                    x1 += ix;
        dx2 = dy2;
+
                    error -= delta_y;
         dy2 = temp;
+
                }
 
+
                // else do nothing
         /* swap sx <-> sy */
+
        temp = sx;
+
        sx = sy;
+
        sy = temp;
+
 
+
        e = dy2 - dx;
+
 
+
        for (i = 0; i <= dx; ++i) {
+
             plot(y0, x0, color);
+
 
+
            while (e >= 0) {
+
                y0 += sy;
+
                e -= dx2;
+
 
             }
 
             }
 
+
            // else do nothing
             x0 += sx;
+
 
             e += dy2;
+
             y1 += iy;
 +
             error += delta_x;
 +
 
 +
            plot(x1, y1);
 
         }
 
         }
 
     }
 
     }
}
+
}
  
 
[[Category:Algorithms]]
 
[[Category:Algorithms]]

Revision as of 14:02, 3 March 2007

Previous article deleted due to crappiness. Here's an improved C++ version (as in the previous article plot() draws a pixel at (x, y):

  1. ifndef ABS
  2. define ABS(x) ((x)>0?(x):-(x))
  3. endif

//////////////////////////////////////////////////////////////////////////////// void Bresenham(unsigned x1,

   unsigned y1,
   unsigned x2,
   unsigned y2)

{

   unsigned delta_x = ABS(x2 - x1) << 1;
   unsigned delta_y = ABS(y2 - y1) << 1;
   // if x1 == x2 or y1 == y2, then it does not matter what we set here
   char ix = x2 > x1?1:-1;
   char iy = y2 > y1?1:-1;
   plot(x1, y1);
   if (delta_x >= delta_y)
   {
       // error may go below zero
       int error = delta_y - (delta_x >> 1);
       while (x1 != x2)
       {
           if (error >= 0)
           {
               if (error || (ix > 0))
               {
                   y1 += iy;
                   error -= delta_x;
               }
               // else do nothing
           }
           // else do nothing
           x1 += ix;
           error += delta_y;
           plot(x1, y1);
       }
   }
   else
   {
       // error may go below zero
       int error = delta_x - (delta_y >> 1);
       while (y1 != y2)
       {
           if (error >= 0)
           {
               if (error || (iy > 0))
               {
                   x1 += ix;
                   error -= delta_y;
               }
               // else do nothing
           }
           // else do nothing
           y1 += iy;
           error += delta_x;
           plot(x1, y1);
       }
   }

}

Personal tools