Bresenham's Line Algorithm

From RogueBasin
Revision as of 14:02, 3 March 2007 by Johndoe (Talk | contribs)

Jump to: navigation, search

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