Bresenham’s line algorithm

The algorithm can be extended to cover gradients between 0 and -1 by checking whether y needs to increase or decrease (i.e. dy < 0)

plotLineLow(x0,y0, x1,y1)
  dx = x1 - x0
  dy = y1 - y0
  yi = 1
  if dy < 0
    yi = -1
    dy = -dy
  end if
  D = 2*dy - dx
  y = y0

for x from x0 to x1
  plot(x,y)
  if D > 0
    y = y + yi
    D = D - 2*dx
  end if
  D = D + 2*dy

By switching the x and y axis an implementation for positive or negative steep gradients can be written as

plotLineHigh(x0,y0, x1,y1)
  dx = x1 - x0
  dy = y1 - y0
  xi = 1
  if dx < 0
    xi = -1
    dx = -dx
  end if
  D = 2*dx - dy
  x = x0

for y from y0 to y1
  plot(x,y)
  if D > 0
    x = x + xi
    D = D - 2*dy
  end if
  D = D + 2*dx

A complete solution would need to detect whether x1 > x0 or y1 > y0 and reverse the input coordinates before drawing, thus

plotLine(x0,y0, x1,y1)
  if abs(y1 - y0) < abs(x1 - x0)
    if x0 > x1
      plotLineLow(x1, y1, x0, y0)
    else
      plotLineLow(x0, y0, x1, y1)
    end if
  else
    if y0 > y1
      plotLineHigh(x1, y1, x0, y0)
    else
      plotLineHigh(x0, y0, x1, y1)
    end if
  end if

Reference:

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

C语言版本

// 交换整数 a 、b 的值
inline void swap_int(int *a, int *b) 
{
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}
 
// Bresenham's line algorithm
void draw_line(IMAGE *img, int x1, int y1, int x2, int y2, unsigned long c) 
{
  // 参数 c 为颜色值
  int dx = abs(x2 - x1),
  dy = abs(y2 - y1),
  yy = 0;
 
  if (dx < dy) 
  {
    yy = 1;
    swap_int(&x1, &y1);
    swap_int(&x2, &y2);
    swap_int(&dx, &dy);
  }
 
  int ix = (x2 - x1) > 0 ? 1 : -1,
  iy = (y2 - y1) > 0 ? 1 : -1,
  cx = x1,
  cy = y1,
  n2dy = dy * 2,
  n2dydx = (dy - dx) * 2,
  d = dy * 2 - dx;
 
  if (yy) 
  { // 如果直线与 x 轴的夹角大于 45 度
    while (cx != x2) 
    {
      if (d < 0) 
      {
        d += n2dy;
      }
      else 
      {
        cy += iy;
        d += n2dydx;
      }
      putpixel(img, cy, cx, c);
      cx += ix;
    }
  } 
  else 
  { // 如果直线与 x 轴的夹角小于 45 度
    while (cx != x2)
    {
      if (d < 0) 
      {
        d += n2dy;
      }
      else
      {
        cy += iy;
        d += n2dydx;
      }
      putpixel(img, cx, cy, c);
      cx += ix;
    }
  }
}

Python Implementation

def draw_line(self, p1, p2, c):
    """draws a line from point p1 to p2 with color c. p1 and p2 can be
       outside of the cube, but it will only draw the line that fall inside
       the cube"""
    current_point = Vertex(p1.x, p1.y, p1.z)
    dx = p2.x - p1.x
    dy = p2.y - p1.y
    dz = p2.z - p1.z
    x_inc = -1 if dx < 0 else 1
    l = abs(dx)
    y_inc = -1 if dy < 0 else 1
    m = abs(dy)
    z_inc = -1 if dz < 0 else 1
    n = abs(dz)
    dx2 = l * 2
    dy2 = m * 2
    dz2 = n * 2

    if (l >= m) and (l >= n):
        err_1 = dy2 - l
        err_2 = dz2 - l
        for i in range(0, l):
            self.set_pixel(current_point, c)
            if err_1 > 0:
                current_point.y = current_point.y + y_inc
                err_1 = err_1 - dx2
            if err_2 > 0:
                current_point.z = current_point.z + z_inc
                err_2 = err_2 - dx2
            err_1 = err_1 + dy2
            err_2 = err_2 + dz2
            current_point.x = current_point.x + x_inc
    elif m >= l and m >= n:
        err_1 = dx2 - m
        err_2 = dz2 - m
        for i in range(0, m):
            self.set_pixel(current_point, c)
            if err_1 > 0:
                current_point.x = current_point.x + x_inc
                err_1 = err_1 - dy2
            if err_2 > 0:
                current_point.z = current_point.z + z_inc
                err_2 = err_2 - dy2
            err_1 = err_1 + dx2
            err_2 = err_2 + dz2
            current_point.y = current_point.y + y_inc
    else:
        err_1 = dy2 - n
        err_2 = dx2 - n
        for i in range(0,n):
            self.set_pixel(current_point, c)
            if err_1 > 0:
                current_point.y = current_point.y + y_inc
                err_1 = err_1 - dz2
            if err_2 > 0:
                current_point.x = current_point.x + x_inc
                err_2 = err_2 - dz2
            err_1 = err_1 + dy2
            err_2 = err_2 + dx2
            current_point.z = current_point.z + z_inc
    self.set_pixel(current_point, c)

 

The algorithm can be extended to cover gradients betwee […]