Line Drawing Algorithm not working properly

[Barry]

I have used Bresenham's line drawing algorithm to draw lines in my OS. I have encountered the problem of the algorithm not drawing vertical lines. The code does not produce vertical lines nor any lines of a similar angle, it stops after about 135 degrees from the top.

Here is the code:

Code: Select all

static void drawline(int x0, int y0, int x1, int y1, int colour) {
  int dx, dy, p, x, y, end;
  dx=abs(x1-x0);
  dy=abs(y1-y0);
  if (dy<dx) {p=2*dy-dx;} else {p=2*dx-dy;}
  if (x0>x1){
    x=x1;
    y=y1;
    end=x0;
  } else {
    x=x0;
    y=y0;
    end=x1;
  }
  putpixel(x,y,colour);
  while(x<=end) {
    if (p<0) {
      x++;
      if (dy<dx) {p=p+2*dy;} else {p=p+2*dx;}
    } else {
      x++;
      y++;
      if (dy<dx) {p=p+2*(dy-dx);} else {p=p+2*(dx-dy);}
    }
    putpixel(x,y,colour);
  }
}

Can anyone help me with this problem?

[quirck]

First of all, you seem to be drawing one pixel past the end due to "while(x<=end)" instead of strict inequality.
Then, if the line is closer to being vertical than horizontal (i.e. dy>dx), you should flip the roles of x and y, so that y is always incremented, and x is incremented only conditionally.
Finally, what about lines like (1, 10) to (10, 1)? Sometimes coordinates must be decremented rather than incremented.

I'd have completely separate branches for dy<dx and dy>=dx. That way there would be no need to test this condition inside the while loop. As for decrementing, I'd introduce another variable to store increment for less changing coordinate, and set it in the beginning to 1 or -1 depending on whether the coordinates must change in opposite directions.

[Combuster]

The while loop has only two possible cases: go right, and go down and right. If you sketch a few lines in a paint app you'll notice that such a condition only supports a very limited subset of lines.

The textbook explanation of Bresenham's often covers one example case, typically the X-dominant one. You will have to adapt such algorithms so that you transform each possible line into that 45' domain, which often means copying the algorithm several times until you cover the full 360' of cases, and perhaps intelligently merging out the duplicate parts until that very mess remains that you can't show to students. Effectively, your assumptions do not match the ones of "the algorithm"

A common balanced approach has two distinct loops, one for X-dominant and Y-dominant lines. The x++ and y++ inside those loops are then replaced by a x+=x_direction and y+=y_direction, after which you can actually do all 360 degrees.