Bresenham's Line Algorithm

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
 
Previous article deleted due to crappiness. Here's an improved C++ version (as in the previous article plot() draws a pixel at (x, y):
 
Previous article deleted due to crappiness. Here's an improved C++ version (as in the previous article plot() draws a pixel at (x, y):
  
#ifndef ABS
+
#ifndef ABS
#  define ABS(x) ((x)>0?(x):-(x))
+
#  define ABS(x) ((x)>0?(x):-(x))
#endif
+
#endif
 
+
////////////////////////////////////////////////////////////////////////////////
+
////////////////////////////////////////////////////////////////////////////////
void Bresenham(unsigned x1,
+
void Bresenham(unsigned x1,
    unsigned y1,
+
    unsigned y1,
    unsigned x2,
+
    unsigned x2,
    unsigned y2)
+
    unsigned y2)
{
+
{
    unsigned delta_x = ABS(x2 - x1) << 1;
+
    unsigned delta_x = ABS(x2 - x1) << 1;
    unsigned delta_y = ABS(y2 - y1) << 1;
+
    unsigned delta_y = ABS(y2 - y1) << 1;
 
+
    // if x1 == x2 or y1 == y2, then it does not matter what we set here
+
    // if x1 == x2 or y1 == y2, then it does not matter what we set here
    char ix = x2 > x1?1:-1;
+
    char ix = x2 > x1?1:-1;
    char iy = y2 > y1?1:-1;
+
    char iy = y2 > y1?1:-1;
 
+
    plot(x1, y1);
+
    plot(x1, y1);
 
+
    if (delta_x >= delta_y)
+
    if (delta_x >= delta_y)
    {
+
    {
        // error may go below zero
+
        // error may go below zero
        int error = delta_y - (delta_x >> 1);
+
        int error = delta_y - (delta_x >> 1);
 
+
        while (x1 != x2)
+
        while (x1 != x2)
        {
+
        {
            if (error >= 0)
+
            if (error >= 0)
            {
+
            {
                if (error || (ix > 0))
+
                if (error || (ix > 0))
                {
+
                {
                    y1 += iy;
+
                    y1 += iy;
                    error -= delta_x;
+
                    error -= delta_x;
                }
+
                }
                // else do nothing
+
                // else do nothing
            }
+
            }
            // else do nothing
+
            // else do nothing
 
+
            x1 += ix;
+
            x1 += ix;
            error += delta_y;
+
            error += delta_y;
 
+
            plot(x1, y1);
+
            plot(x1, y1);
        }
+
        }
    }
+
    }
    else
+
    else
    {
+
    {
        // error may go below zero
+
        // error may go below zero
        int error = delta_x - (delta_y >> 1);
+
        int error = delta_x - (delta_y >> 1);
 
+
        while (y1 != y2)
+
        while (y1 != y2)
        {
+
        {
            if (error >= 0)
+
            if (error >= 0)
            {
+
            {
                if (error || (iy > 0))
+
                if (error || (iy > 0))
                {
+
                {
                    x1 += ix;
+
                    x1 += ix;
                    error -= delta_y;
+
                    error -= delta_y;
                }
+
                }
                // else do nothing
+
                // else do nothing
            }
+
            }
            // else do nothing
+
            // else do nothing
 
+
            y1 += iy;
+
            y1 += iy;
            error += delta_x;
+
            error += delta_x;
 
+
            plot(x1, y1);
+
            plot(x1, y1);
        }
+
        }
    }
+
    }
}
+
}
  
 
[[Category:Algorithms]]
 
[[Category:Algorithms]]

Revision as of 14:09, 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):

#ifndef ABS
#   define ABS(x) ((x)>0?(x):-(x))
#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