Learning and Applying Mathematics using Computing

On paper, drawing a straight line between two points is easy: Put your ruler down on the page, and run your pencil across. In contrast, drawing a straight line on a computer screen is a matter of deciding which pixels to colour in (known as rasterization). It can be thought of as drawing a pencil line on squared graph paper, and colouring in any squares which the line passes through:

But how do you practically do this? One way is to move along the line in small increments, and colour the square you are in after each movement. But if your increment isn’t small enough you can miss some squares which the line barely touches — and if your increment is too small, it can be quite an inefficient exercise.

This post will explain how to draw a line on a computer screen. There are several fast line-drawing algorithms: Bresenham is quite famous, and Wu can do anti-aliasing. I’m going to explain an equivalent to Wu’s algorithm, but without the anti-aliasing.

The Algorithm

Every two-dimensional line can be put into one of three categories:

  1. It’s longer in the Y dimension than in X.
  2. It’s the same length in X and Y (and thus is at 45 degrees).
  3. It’s longer in the X dimension than in Y.

Thus we can always pick the longest dimension and call it the major axis, with the other axis being the minor axis. (In the middle case, you can pick X or Y for the major axis, it won’t matter.) Here’s the first part of our key insight for our line-drawing algorithm: by definition, if you move 1 pixel on the major axis, you’ll move at most 1 pixel in the minor axis. After all, if you moved further in the minor axis than major, you have labelled them wrong. Here’s some diagrams to illustrate:

The major axis is red, the minor axis is blue. In the bottom-right picture, we could have chosen either X or Y to be the major axis.

And here’s the second part of our insight: if you move 1 pixel in the major axis, and thus at most 1 pixel in the minor axis, you will always touch at most two pixels on the minor axis. You can see this in the diagram above. Trace one pixel in the major axis. To touch three pixels, you would need to begin in pixel A, then move into pixel B, out of pixel B and into pixel C. That would require moving more than one pixel in the minor axis, which we’ve already seen would mean you’ve labelled them wrong.

So we can write our line-drawing algorithm so that it advances 1 pixel in the major axis, and then just works out which 1 or 2 pixels it touched on the minor axis, then go again.

Specific Case

To begin with, here’s the code for the case when the X axis is the major axis, and the start point is to the left of the end point. We fill the start and end pixels as a special case, because we know straight away that the line must pass through them:

        fillPixel(lineStartX, lineStartY);
        
        if (lineStartX == lineEndX && lineStartY == lineEndY)
            return;
        
        double slope = (double)(lineEndY - lineStartY) / (double)(lineEndX - lineStartX);
        fillPixelsLine(lineStartX, lineEndX, lineStartY, slope);
        
        fillPixel(lineEndX, lineEndY);

All the other pixels in the line are filled by the fillPixelsLine function:

    private void fillPixelsLine(int startX, int endX, int startY, double slope)
    {
        double curY = startY + 0.5 + (0.5 * slope);
        for (int curX = startX + 1; curX != endX; curX++)
        {
            fillPixel(curX, (int)Math.floor(curY));

            double newY = curY + slope;            
            if (Math.floor(newY) != Math.floor(curY))
            {
                fillPixel(curX, (int)Math.floor(newY));
            }
            curY = newY;
        }
    }

The above function is passed the coordinates of the starting pixel, but actually begins on the next pixel. This is effectively the top-left corner of a pixel, but the line starts in the middle. So the “+ 0.5 + 0.5 * slope” for curY starts the Y coordinate in the middle of the pixel (the “+ 0.5”), then works out how much it would be at the end of the pixel:

The loop begins by filling a pixel (using the Y at the start, or left-hand edge, of the current column). Then it advances the Y to its next value (the Y at the end, or right-hand edge of the current column) — if this is a different pixel from the earlier one, it is also filled:

We tell if the pixel is the same by looking at the integer part using Math.floor: In the above diagram, Math.floor(10.7) is 10, and Math.floor(11.3) is 11, so because those are not equal, we can tell that we have crossed the pixel boundary (located at 11.00).

Generalising

The above code is specialised for the case that the X axis is the major axis, and the line heads in the positive X direction. To generalise the code to handle all cases, we need to add a bit of extra parameterisation to the code:

    private void drawLine(int lineStartX, int lineStartY, int lineEndX, int lineEndY)
    {
        fillPixel(lineStartX, lineStartY, true);
        
        if (lineStartX == lineEndX && lineStartY == lineEndY)
            return;
            
        fillPixel(lineEndX, lineEndY, true);
        
        if (Math.abs(lineEndX - lineStartX) >= Math.abs(lineEndY - lineStartY))
            fillPixels(lineStartX, lineEndX, lineStartY, (double)(lineEndY - lineStartY) / (double)(lineEndX - lineStartX), true);
        else
            fillPixels(lineStartY, lineEndY, lineStartX, (double)(lineEndX - lineStartX) / (double)(lineEndY - lineStartY), false);
    }
    
    private void fillPixels(int start, int end, int startMinor, double slope, boolean horizontal)
    {
        int advance = end > start ? 1 : -1;
        double curMinor = startMinor + 0.5 + (0.5 * advance * slope);
        for (int curMajor = start + advance; curMajor != end; curMajor += advance)
        {
            fillPixel(curMajor, (int)Math.floor(curMinor), horizontal);

            double newMinor = curMinor + (advance * slope);            
            if (Math.floor(newMinor) != Math.floor(curMinor))
                fillPixel(curMajor, (int)Math.floor(newMinor), horizontal);
            curMinor = newMinor;
        }
    }
    
    private void fillPixel(int major, int minor, boolean horizontal)
    {
        if (horizontal) // X is major
            addObject(new Box(), major, minor);
        else // Y is major
            addObject(new Box(), minor, major);
    }

The two added parameters are the horizontal boolean, which indicates whether major is X or Y, and the advance constant, which allows you to go in a negative direction along the major axis. The principle of the code is exactly the same.

Summary

You can see the line-drawing in action — left-click to set the start point, and right-click to set the end point.

Our line-drawing algorithm is perhaps a bit unusual, because it colours in any pixel the line touches, which Bresenham does not. (Wu does, but draws in different transparencies, to implement anti-aliasing.) However, in the next few posts I’m going to show you other uses of this algorithm, besides line-drawing, which require this behaviour.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s