How to use Bresenham's line drawing algorithm with clipping?

Question

When drawing a line with Bresenham line drawing algorithm, where the line may not be within the bounds of the bitmap being written to - it would be useful to clip the results so they fit within the axis aligned bounds of the image being written to.

While its possible to first clip the line to the rectangle, then draw the line. This isn't ideal since it often gives a slightly different slant to the line (assuming int coords are being used).

Since this is such a primitive operation, are there established methods for clipping the line while maintaining the same shape?

In case it helps, here is a reference implementation of the algorithm - it uses int coords, which avoids int/float conversion while drawing the line.

---

I spent some time looking into this:

• Problem is described in detail on virtual-dub's web page.
• Possible solution from Alan Tiedemann
  ... though I'd need to implement code based on the text - to see how well it works.
• Bresenham's Line Generation Algorithm with Built-in Clipping
  (paper from 1995, couldn't find the entire document? - PDF is a single page without the C code it references, looks like its pay-walled).

Answer 1

Let's reframe the problem so we can see how Bresenham's algorithm really works...

Lets say you are drawing a mostly horizontal line (the method is the same for mostly vertical, but with the axes switched) from (x0,y0) to (x1,y1):

The full line can be described as a function of y in terms of x (all integers):

y = y0 + round( (x-x0) * (y1-y0) / (x1-x0) )

This describes precisely each pixel you will paint when drawing the full line, and when you clip the line consistently, it still describes precisely each pixel you will paint -- you just apply it to a smaller range of x values.

We can evaluate this function using all integer math, by calculating the divisor and remainder separately. For x1 >= x0 and y1 >= y0 (do the normal transformations otherwise):

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}

Bresenham's algorithm is a just a fast way to update the result of this formula incrementally as you update x.

Here's how we can make use of incremental updates to draw the portion of the very same line from x=xs to x=xe:

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= remlimit)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}

If you want do to your remainder comparisons against 0, you can just offset it at the beginning:

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = ( (x-x0) * dy % dx ) - remlimit;
y = y0 + (x-x0) * dy / dx;
if (rem >= 0)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= 0)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}