Skip to navigation

BBC Micro Elite

Bresenham's line algorithm

The main line-drawing algorithm used to draw non-horizontal lines
-----------------------------------------------------------------
References: LOIN
  Most of what you see in the space view in Elite is composed of straight lines.
  The ships are drawn using wireframes that are made up of straight lines, the
  planets are made from circles and arcs that consist of lots of small, straight
  lines, and the sun is no more than a sequence of horizontal lines, drawn along
  a vertical axis. Having a fast line-drawing algorithm is essential in a game
  like Elite.
  
  Horizontal lines are a special case and have their own optimised routine at
  HLOIN, but all non-horizontal lines in Elite are drawn using Bresenham's line
  algorithm. Let's look at how that works.
  
  The core algorithm
  ------------------
  The basic idea is quite simple. Let's consider a line from (X1, Y1) to (X2,
  Y2), where that line slopes down and right at a reasonably shallow angle, like
  this:
  
    (X1, Y1) ''-..__
                    ''--..__
                            ''--..__
                                    ''--.._
                                            (X2, Y2)
  
  As we move along the line from (X1, Y1) to (X2, Y2), let's say that we move
  across by delta_x and down by delta_y, like this:
  
  
             <---------- delta_x --------->
  
    (X1, Y1) ''-..__                                    ^
                    ''--..__                            | delta_y
                            ''--..__                    |
                                    ''--.._             v
                                            (X2, Y2)
  
  So we have the following:
  
    * As we move along the line by delta_x in the x-direction, we move down by
      delta_y in the y-direction.
  
  If we divide each side of the triangle by delta_x, we also get the following:
  
    * As we move along the line by 1 in the x-direction, we move down by
      (delta_y / delta_x) in the y-direction.
  
  This is the core of the algorithm: if we step along the x-axis, 1 pixel at a
  time, then if we also move down by (delta_y / delta_x) in the y-direction and
  plot a point each time, we'll have our line. In pseudo-code, it looks like
  this:
  
    function line(x1, y1, x2, y2)
      delta_x = x2 - x1
      delta_y = y2 - y1
      y = y1
      for x from x1 to x2
        plot(x, y)
        y = y + (delta_y / delta_x)
  
  If our screen had an infinite resolution, then this would do nicely... but, of
  course, it doesn't, so we need to refine this idea. Internally we still do the
  same calculation for y, but when we come to plot the point with plot(x, y), we
  need to convert y into an integer. We could just convert y to the nearest
  integer each time, but working with floating point numbers is pretty slow, so
  the algorithm speeds things up by using the concept of a "slope error".
  
  We're drawing a pixel line, so each time we step along the x-axis by 1 pixel,
  we have a choice of either staying where we are in the y-axis, or moving down
  one line (i.e. incrementing y by 1). We can't increase y by fractions, so
  instead, each time we step along the x-axis, we keep a running total of how
  far we would step down in the y-axis if we weren't constrained by only being
  able to move down by 1. In other words, we keep a tally of the (delta_y /
  delta_x)'s that we would ideally be adding to y, until we know we've moved
  onto the next line, at which point we add 1 to y. This tally is known as the
  "slope error", as it's a running tally of the current error between our pixels
  and the real slope of the line.
  
  There's one final tweak, and that's starting our slope error tally at 0.5,
  which denotes the centre of the starting pixel. So the final algorithm looks
  like this:
  
    function line(x1, y1, x2, y2)
      delta_x = x2 - x1
      delta_y = y2 - y1
      slope_err = abs(delta_y / delta_x)
      error = 0.5
      y = y1
      for x from x1 to x2
        plot(x, y)
        error = error + slope_err
        if error >= 1.0 then
          y = y + 1
          error = error - 1.0
  
  Implementing Bresenham in 8-bit integers
  ----------------------------------------
  You may have noticed that the algorithm above still uses real numbers. When we
  actually use this approach in Elite, we multiply all the real numbers by 256,
  so that 256 is equivalent to 1.0. We can now initialise error to 128, and
  instead of checking whether error >= 1.0, we can check whether error is >=
  256, like this:
  
    function line(x1, y1, x2, y2)
      delta_x = x2 - x1
      delta_y = y2 - y1
      slope_err = abs(delta_y / delta_x)
      error = 128
      y = y1
      for x = x1 to x2
        plot(x, y)
        error = error + slope_err
        if error >= 256 then
          y = y + 1
          error = error - 256
  
  There is one final improvement. If we use a single byte to store the error,
  then error >= 256 is the same as saying "has the addition just overflowed", in
  which case we don't need to subtract 256 as the byte will already have rolled
  around to 0. So here is the final algorithm used in Elite:
  
    function line(x1, y1, x2, y2)
      delta_x = x2 - x1
      delta_y = y2 - y1
      slope_err = abs(delta_y / delta_x)
      error = 128
      y = y1
      for x = x1 to x2
        plot(x, y)
        error = error + slope_err
        if C flag is set then
          y = y + 1
  
  This is the algorithm that's implemented in part 4 of the LOIN routine, for
  gently sloping lines that go right and down. It uses Q, S, X and Y as follows:
  
    Q = |delta_y| / |delta_x|
    S = 128
    Y = Y1
    for X = X1 to X2
      plot(X, Y)
      S = S + Q
      if C flag set then
        inc Y
  
  The full LOIN routine implements the same basic algorithm multiple times,
  tweaked to cater for all the other variations of sloping line (such as more
  vertical lines that slope sharply up and to the left, for example). But the
  same principles apply, just with different signs.
  
  Also, it's worth noting that Elite doesn't plot the last pixel in any of its
  lines. This is to prevent corners from disappearing; if you imagine us drawing
  a triangle by drawing a line from point A to point B, then from B to C, and
  then from C to A again, then if we plotted the end points, each of the
  triangle's vertices (A, B and C) would be plotted twice, once as the start of
  a line, and again as the end of the line. Normally this wouldn't be a problem,
  but because Elite draws everything on-screen using EOR logic (so objects can
  be drawn and then erased by simply drawing them again), this would mean the
  corner points would disappear, and that would look very strange. So there is
  also logic in the following to omit the last pixel from the line, in the same
  way that HLOIN omits the final pixel from its lines too.
  
  Summary of the routine
  ----------------------
  To help with understanding the 7 parts of the line-drawing routine, here's a
  summary of what each part does.
  
    1. Calculate delta_x, delta_y
       Choose either parts 2-4 or parts 5-7
  
  If the line is closer to being horizontal than vertical, we step right along
  the x-axis:
  
    2. Potentially swap coordinates so X1 < X2
       Set up screen address variables
       Calculate |delta_y| / |delta_x|
       Choose either part 3 or part 4
  
    3. The line is going right and up (no swap) or left and down (swap)
       X1 < X2 and Y1-1 > Y2
       Draw from (X1, Y1) at bottom left to (X2, Y2) at top right
       If we swapped, don't plot (X1, Y1)
  
    4. The line is going right and down (no swap) or left and up (swap)
       X1 < X2 and Y1-1 <= Y2
       Draw from (X1, Y1) at top left to (X2, Y2) at bottom right
       If we didn't swap, skip plotting (X1, Y1)
  
  If the line is closer to being vertical than horizontal, we step up along
  the y-axis:
  
    5. Potentially swap coordinates so Y1 >= Y2
       Set up screen address variable
       Calculate |delta_x| / |delta_y|
       Choose either part 6 or part 7
  
    6. The line is going up and left (no swap) or down and right (swap)
       X1 < X2 and Y1 >= Y2
       Draw from (X1, Y1) at bottom right to (X2, Y2) at top left
       If we didn't swap, skip plotting (X1, Y1)
  
    7. The line is going up and right (no swap) or down and left (swap)
       X1 >= X2 and Y1 >= Y2
       Draw from (X1, Y1) at bottom left to (X2, Y2) at top right
       If we didn't swap, skip plotting (X1, Y1)