Bug with the Bresenham's line drawing algorithm?

Question

I know how to draw lines with DDA, but I want to learn a more efficient way and Google suggests Bresenham's line drawing algorithm is better than DDA.

Here is my implementation:

int x0 = Math.round(m_start.getPosition().getX());
int y0 = Math.round(m_start.getPosition().getY());
int x1 = Math.round(m_end.getPosition().getX());
int y1 = Math.round(m_end.getPosition().getY());

int dx = x1 - x0;
int dy = y1 - y0;

int parameter = 2 * dy -  dx;

Point k = new Point(new Vector2D(x0, y0), m_display, PixelData.white());
k.DrawPoint();

for(int i = x0 + 1; i < x1; i++){
   if(parameter < 0){
       y0 += 1;
       Point p = new Point(new Vector2D(i, y0), m_display, PixelData.white());
       p.DrawPoint();

       parameter += 2 * dy;
   }
   else{
       y0 += 1;
       Point p = new Point(new Vector2D(i, y0 + 1), m_display, PixelData.white());
       p.DrawPoint();

       parameter += 2 * dy - 2 * dx;
   }
}

And here is the output:

As you can see, the line is not ending at the desired coordinate. That small dot is where it should end.

I checked the slope, dx and dy.

System.out.println(dx + " " + dy + " " + (dy/(float)dx));

Output:

100 50 0.5

The slope is below tan (pi/4).

How do I find the bug?

Answer 1

Note that the approach you appear to be taking will only work for lines with a slope in a single octant. For the other seven octants the algorithm requires changing the approach, for example by changing the roles of x and y. Wikipedia gives a table of cases that can be used for this conversion.

For this answer I will assume you are simply trying to get the code working for the first octant.

---

int parameter = 2 * dy -  dx;

parameter starts off negative only if dx > 2 * dy.

In this case the total horizontal distance to be covered by the line is more* than twice the vertical distance, which means the first step should be purely horizontal. So if parameter is negative then y0 should not change.

Here is the source of the problem:

if(parameter < 0){
           y0 += 1;

y0 should only be incremented if parameter is not negative. This y0 += 1 is causing vertical movement even if the first step should be purely horizontal.

The same problem applies on later steps too. The code causes parameter to switch back and for between negative and non-negative in proportion to the ratio between 2 * dx and dy. y0 must only be incremented when parameter is non-negative. That additional occurrence of y0 += 1 prevents y0 from ever staying still, causing a slope of 1 regardless of the inputs. Simply remove that line and it should work correctly.

---

*If you are wondering why the algorithm only steps purely horizontally when the parameter is less than zero, rather than less than or equal to zero, bear in mind that the horizontal distance to be covered is one less than the number of pixel columns displayed. If x0 is 0 and x1 is 3, then dx is 3, but 4 columns of pixels will be displayed. So a line 4 pixels across and 2 pixels down actually has xd as 3 and yd as 1. In this case the number of pixels across is exactly twice the number of pixels down, but xd is more than twice yd, so this still results in the parameter being negative and the line moving purely horizontally on the first step.

Answer 2

Frankly, your implementation doesn't make much sense. It basically iterates x coordinate through i variable and increments y variable at each step. Since the parameter doesn't cross the 0 boundary, it generates the diagonal points you can see on your picture.

You also compute and update the parameter variable somehow, but don't use it anywhere.