Bresenham line algorithm in Cocoa (Objective C)

Bresenham's line algorithm draws a line from (x1,y1) to (x2,y2) into our custom framebuffer MYDraw. The algorithm is used to draw the wireframe portion of your 3D objects and it replaces Cocoa's [NSBezierPath stroke].

The ideal line is infinitly thin, but on the screen, we need to approximate lines with a row of stair-stepping pixels. Obviously we are bound to lose some precision, which however is no big deal, since a 3D-game is not rocket science. The trick is to calculate which individual pixels have to be switched on or off to create the impression of a line on the screen. To do that, we need to know the exact angle of the line.

The Slope of a Line

The angle of a line is called the slope. The slope tells us how far the line from (x1,y1) to (x2,y2) moves vertically (in y) for every pixel it moves horizontally (in x).

Mathematically, we need the distance between the y coordinates (dy = y2 - y1) divided by the distance between the x coordinates (dx = x2 - x1). Here is the formula to calculate the slope:

dy = (y2 - y1)
dx = (x2 - x1)
slope = (dy / dx) = (y2 - y1) / (x2 - x1)

dy = 8-2 = 6
dx = 4-1 = 3
slope = 6/3 = 2

Here is a list of cases we have to consider.

• If the result is a real number (such as 0.3) you need to convert it into integer fractions: A slope of 0.3 can be expressed as 3/10, this means, for each 3 pixels that you move down, you move 10 pixel to the right. (Note that 6 / 20 = 0.3 would have worked just them same: For each 6 pixels that you move down, you'd move 20 pixel to the right. You'd end up drawing the exact same line.)
• A horizontal line from (0,10) to (10,10) has a slope of 10-10 / 10-0 = 0 / 10 = zero. (Makes sense, a horizontal line obviously has no slope: Even if it makes 10 steps to the right, it makes zero steps down.)
• A vertical line from (10,0) to (10,10) has a slope of 10-0 / 10-10 = 10 / 0 = NAN! You can't divide by zero! (Makes sense, something like a "vertical slope" doesn't exist: A vertical line never makes any steps to the right, it's infinitly steep.)
• A diagonal line from (0,0) to (10,10) has a slope of 10-0 / 10-0 = 10 / 10 = 1/1 = 1. (Makes sense, for each 1 step to the right, the line goes down 1, too.)
• If the slope turns out to be negative, it means the line does not go from top-left to bottom-right but from top-right to bottom left. For each x steps to the left, the line goes down y steps.

Keeping the Slope Under Control: The "Error Term"

Bresenham's clever solution of the line drawing problem consisted in using a variable as an error term. It also distinguishes two cases, lines that are more horizontal than vertical, and lines that are more vertical than horizontal. In the first case, the next pixel will always be plotted to somewhere the right side of the previous one, resulting in a rather flat line. In the second case, the next pixel is always plotted somewhere below the previous one, resulting in a steeply falling line (look at the steeply falling line in the example picture).

Each time we approximate the shape of the line by placing a pixel, we make a tiny error: Obviously, a plump square pixel can't get the slope of the ideal line perfectly right. Bresenham uses the error_term variable to keep track of these small errors, because as soon as they sum up, he knows he will have to correct them.

In our example line from (1,2) to (4,8), we know, for each 2 pixels the line moves down, it moves 1 pixel to the right; its dy = 3 and its dx = 6. Lets step through the algorithm.

1. The error_term is set to zero.
2. (Case: Our line is more vertical than horizontal)
3. We plot the first pixel at (1,2).
4. This causes an error of dx=3.
5. We add dx to the error_term, which is now 3.
6. We test whether the error is big enough to require correction: Is the error_term bigger than dy?
7. No, 3 is not bigger than 3, so...
8. ... we plot the second pixel at (1,3), one row below the first one.
9. This causes another error of dx=3.
10. We add dx to the error_term, which is now 6.
11. We test whether the error is big enough to require correction: Is the error_term bigger than dy?
12. Yes, 6 is bigger than 3, so...
13. ... we reset the error_term by substracting dy and...
14. ... we correct the dy error by plotting the third pixel not only below, but also one step to the right, at (2,4).
15. The new pixel again caused an error of dx=3
16. (etc)
17. We stop when we have reached (4,8)

The Bresenham line algorithm works similarly for a flat line that's more horizontal than vertical — the steps are just the other way round. In flat-line case, the next pixel is always plotted to the right side of the previous pixel. If the error caused by that approximation requires correction, the next pixel is additionally moved one step below the previous.

If you look closely you will see, that the algorithm also provides for dealing with negative slopes, by using the variables xDirection and yDirection, which can be negative or positive to make the steps go to the left or right, or up or down as needed. This way, the algorithm can even handle horizontal and vertical lines: It just sets xDirection and yDirection to zero. Another nice thing is that the algorithm never needs to calculate the actual slope; it works only with dx and dy. This is very efficient since it spares us several slow division operations.

Implementation

Bresenham's line algorithm draws a line from (x1,y1) to (x2,y2) into our custom (MYDraw*) framebuffer. It relies on the argument ppr (number of pixels per row in the framebuffer), and needs to know the line's color.

@implementation Bresenham

+ (void) drawLineX1:(short)x1 y1:(short)y1 x2:(short)x2 y2:(short)y2
             buffer:(MYDraw*) mybuffer ppr:(int)ppr color:(NSColor*)color
{
    int dx, dy, xDirection, yDirection, i;
    int rowOffset;
    int pixelOffset;
    int error_term;
    // the absolute x and y distances for this line
    dx = x2 - x1;
    if (dx < 0) dx = -dx;
    dy = y2 - y1;
    if (dy < 0) dy = -dy;
    // the horizontal direction of the line (moving left or right?)
    if (x2 - x1 < 0) {
        xDirection = -1;        /* Moving left */
    } else if (x2 - x1 > 0) {
        xDirection = 1;         /* Moving right */
    } else {
        xDirection = 0;         /* vertical line! */
    }
    /*  the vertical direction of the line (moving up or down?) */
    if (y2 - y1 < 0) {
        yDirection = -1;
        rowOffset = -ppr;       /* Subtract ppr to move up a line */
    } else if (y2 - y1 > 0) {
        yDirection = 1;
        rowOffset = ppr;        /* Add ppr to move down a line */
    } else {
        yDirection = 0;
        rowOffset = 0;          /* horizontal line! */
    }
    /* Initialize the error term */
    error_term = 0;
    /* Calculate where the first pixel will be placed */
    pixelOffset = (y1*ppr) + (x1);
    /* the drawing loop */
    if (dx > dy)
    {
        /* Line is more horizontal than vertical (x>y) */
        for (i = 0; i <= dx; i++)
        {
            // Draw this pixel 
            [mybuffer setPixel:pixelOffset to:color];
            // Move the pixelOffset 1 pixel left or right. (x)
            pixelOffset += xDirection;
            // Time to move pixelOffset up or down? (y)
            error_term += dy;
            if (error_term > dx) {
                /* Yes. Reset the error term */
                error_term -= dx;
                /* And move the pixelOffset 1 pixel up or down */
                pixelOffset += rowOffset;
            }
        }
    } else {
        // Line is more vertical than horizontal: (y>x).
        for (i = 0; i <= dy; i++) {
            // Draw this pixel
            [mybuffer setPixel:pixelOffset to:color];
            // Move pixelOffset up or down. (y)
            pixelOffset += rowOffset;
            // Time to move pixelOffset left or right? (x) 
            error_term += dx;
            if (error_term > dy) {        
                /* Yes. Reset the error term */
                error_term -= dy;
                /* And move the pixelOffset 1 pixel left or right */
                pixelOffset += xDirection;
            }
        }
    }
}

Call

- (void) drawWireframePolygon
{
    // Bresenham line drawing algorithm
    // call drawWireframePolygon after closePath
    int i, x1,y1,x2,y2;
    for( i = 0; i < vertexNum-1; i++)
    {
	    x1 = [[vertexListX objectAtIndex:i] intValue];
	    y1 = [[vertexListY objectAtIndex:i] intValue];
	    x2 = [[vertexListX objectAtIndex:i+1] intValue];
	    y2 = [[vertexListY objectAtIndex:i+1] intValue];
	    [Bresenham drawLineX1:x1 y1:y1 x2:x2 y2:y2
		    buffer:self ppr:ppr color:color];
    }
}