Skip to navigation

BBC Micro Elite

The ball line heap

How we remember the lines used to draw circles so they can be redrawn
---------------------------------------------------------------------
References: BLINE, LSX2, LSY2
  The planet, the sun and ships in our local bubble of universe are complicated
  things, and we have to use an awful lot of maths to calculate their shapes
  on-screen. Not surprisingly, all that maths takes up quite a bit of processor
  time. We can remove shapes from the screen by drawing the same shapes again in
  exactly the same place (which erases them because it's all done with EOR
  logic), so if we can avoid having to repeat all those intensive calculations
  for that second drawing, that would save a lot of time and effort.
  
  Not surprisingly, Elite has a solution - three of them, to be precise. Instead
  of repeating the calculations for the second drawing, Elite has a set of three
  "line heaps" where all the drawing information gets stored, so it's a simple
  process to redraw, and therefore erase, any shape on-screen.
  
  There are three types of line heap used in Elite:
  
    * The ball line heap, which is used by the BLINE routine when drawing
      circles (as well as polygonal rings like the launch and hyperspace tunnel)
  
    * The sun line heap, which is used by the SUN routine when drawing the sun
      (see the deep dive on "Drawing the sun" for details)
  
    * The ship line heap, one per ship in the local bubble of universe, which
      is used by the LL9 routine when drawing ships (see the deep dive on
      "Drawing ships" for details)
  
  Here we take a look at the ball line heap that's stored at LSX2 and LSY2, and
  with the pointer in LSP.
  
  Drawing and storing circles with BLINE
  --------------------------------------
  We draw a circle by repeated calls to BLINE, passing the next point around the
  circle with each subsequent call, until the circle (or half-circle) is drawn.
  
  Calling the routine with a value of &FF in FLAG initialises the line heap and
  stores the first point in memory rather than in the heap, so it's ready for
  the second call to BLINE, which is when we actually have a segment to draw
  and store in the line heap.
  
  The routine keeps a tally of the points passed to it on each call, storing
  them in the line heaps at LSX2 and LSY2, and using the line heap pointer
  in LSP (which points to the end of the heap). It also keeps the point from
  the previous call to BLINE in K5(3 2 1 0), so it can draw a segment between
  the last point and this one.
  
  If a line doesn't fit on-screen, then it isn't drawn or stored in the heap.
  Instead a &FF marker is inserted into the LSY2 entry at the current position,
  which indicates to the next call to BLINE that it should start a new segment.
  In this way broken, non-continuous lines can still be stored in the line
  heap.
  
  Keeping the points in the line heap lets us quickly redraw the circle without
  needing to regenerate all the points, so it is easy to remove the circle from
  the screen by simply redrawing all the segments stored in the line heaps. This
  is done in WPLS2.
  
  How the LSX2 and LSY2 heaps are structured
  ------------------------------------------
  The ball line heap is stored in 78 bytes at LSX2 and another 78 bytes at LSY2.
  The LSP variable points to the number of the first free entry at the end of
  the heap, so LSP = 1 indicates that the heap is empty.
  
  The first location at LSX2 has a special meaning:
  
    * LSX2 = 0 indicates the line heap contains data
    * LSX2 = &FF indicates the line heap is empty
  
  Meanwhile, if a y-coordinate in LSY2 is &FF, then this means the next point in
  the heap represents the start of a new segment, rather than a continuation
  of the previous one. Specifically, this is the layout in the heap:
  
    LSX2  ...      X1  X2 ...
    LSY2  ... &FF  Y1  Y2 ...
  
  The first entry in the table at LSY2 is always &FF, as the first point is
  always the start of a segment, so the start of a non-empty line heap looks
  like this:
  
    LSX2  0    X1  X2  X3 ...
    LSY2  &FF  Y1  Y2  Y3 ...
  
  When a planet is plotted for the second time to remove it from screen, the
  heaps are reset by setting LSP to 1 and inserting a &FF at the start of LSX2.
  See WPLS2 for details.