Difference between revisions of "Bresenham's Line Algorithm"

From RogueBasin
Jump to navigation Jump to 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
    // if x1 == x2 or y1 == y2, then it does not matter what we set here
        */
    char ix = x2 > x1?1:-1;
        int tmpswap;
    char iy = y2 > y1?1:-1;
#define SWAP(a,b) tmpswap = a; a = b; b = tmpswap;
 
 
    plot(x1, y1);
        /*
 
        * optimize for vertical and horizontal lines here
    if (delta_x >= delta_y)
        */
    {
       
         // error may go below zero
        dx = abs(x1 - x0);
         int error = delta_y - (delta_x >> 1);
        sx = ((x1 - x0) > 0) ? 1 : -1;
 
        dy = abs(y1 - y0);
         while (x1 != x2)
        sy = ((y1 - y0) > 0) ? 1 : -1;
        {
        if (dy > dx) {
            if (error >= 0)
                steep = 0;
            {
                SWAP(x0, y0);
                if (error || (ix > 0))
                SWAP(dx, dy);
                 {
                SWAP(sx, sy);
                    y1 += iy;
         }
                    error -= delta_x;
         e = (dy << 1) - dx;
         for (i = 0; i < dx; i++) {
                if (steep) {
                        plot(x0,y0,color);
                 } else {
                        plot(y0,x0,color);
                 }
                 }
                 while (e >= 0) {
                 // else do nothing
                        y0 += sy;
            }
                        e -= (dx << 1);
            // else do nothing
                }
                x0 += sx;
                e += (dy << 1);
        }
}


A slightly more optimized version of the above
            x1 += ix;
(might be a bit harder to read, though):
            error += delta_y;


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) */
    int dx, dy;  /* delta (difference in X and Y between points) */
    int dx2, dy2;
    int e;
    int temp;
 
    dx = x1 - x0;
    sx = (dx > 0) ? 1 : -1;
    if (dx < 0)
        dx = -dx;
 
    dy = y1 - y0;
    sy = (dy > 0) ? 1 : -1;
    if (dy < 0)
        dy = -dy;
 
    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;
            }
 
            x0 += sx;
            e += dy2;
         }
         }
     } 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 12: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);
       }
   }

}

Retrieved from "http://roguebasin.com/index.php?title=Bresenham%27s_Line_Algorithm&oldid=4714"