Skip to navigation

BBC Micro Elite

Back-face culling

How Elite draws solid-looking 3D ships by only drawing visible faces
--------------------------------------------------------------------
References: LL9 (Part 5 of 11)
  One of the reasons that Elite's 3D wireframe ships look so good is because
  you can't see through them - they look genuinely solid. This is down to a
  process called "back-face culling", a mathematical process that works out
  which faces of the ship are visible to the viewer and which ones aren't. It
  then discards (or "culls") any faces that aren't visible and only draws those
  that we can actually see. This prevents the wireframes from being see-through,
  and this gives the ships a real sense of solidity.
  
  The main principle behind back-face culling is the dot product. This simple
  mathematical operation takes two vectors and produces a scalar value that is
  in essence a kind of mathematical application of one vector to the other, of
  taking the "essence" of one vector and applying it to another. For the
  purposes of back-face culling in Elite, we use the dot product in two distinct
  ways.
  
  Direction of the face normal
  ----------------------------
  The first use is to calculate whether a face is pointing towards us or away
  from us, so we can decide whether to draw it. For this we use a property of
  the dot product that's almost tailor-made for solving this problem: if the dot
  product of two vectors is negative, then the angle between them is greater
  than 90 degrees (and by extension, if it is positive then the angle is less
  than 90 degrees, while a dot product of 0 means they are at exactly 90 degrees
  to each other).
  
  Now, consider a face of one of our ships, and take the surface normal vector
  of that face. This is the vector that sticks out of the surface of the face at
  90 degrees to the surface (so a ship with its face normals attached would look
  like a strange, space-faring hedgehog). Now think about rotating that face in
  space, and you can see that if that face normal is pointing towards us - in
  other words if the spike is pointing in our general direction, more towards us
  than away from us - then we can see the front of the face, while if the face
  normal (the spike) is pointing away from us, then the face is also pointing
  away from us and we can't see it.
  
  The normal is effectively pointing in the direction of the face, so if it is
  pointing in our general direction, then the face is pointing towards us and we
  can see it; similarly, if the normal is pointing away from us, then the face
  is also pointing away from us, and we can't see it. Finally, if the face is
  exactly side on to us, it's on the cusp of being visible and invisible to us.
  
  It looks like this (though you'll have to imagine that the normals are at
  90 degrees, as that's pretty difficult to do in ASCII):
  
                                 /                        `.   /   normal points
                                /      normal points        `./    towards us,
    line of sight ----->       /`.     away, face            /     face visible
                              /   `.   not visible          /
  
  The solid lines represent the faces, while the dotted lines represent the
  normals. On the left the normal is pointing away from us and the face is
  turned away from us, so it's not visible, while on the right the normal is
  pointing towards us and so is the face, so it's visible.
  
  So, when the face normal is pointing away from us, the face is hidden from us.
  To put this another way, when the angle between the face normal and our line
  of sight is greater than 90 degrees, then the face normal is pointing away
  from us and the face is not visible. Similarly, when the angle is less than 90
  degrees, the normal is pointing towards us, so the face is visible.
  
  This means that we can calculate the visibility of a face by calculating the
  following dot product:
  
    line of sight vector . face normal vector
  
  If the result of this dot product is negative, then the face is visible; if
  it's positive, it isn't visible; and if it's zero it's edge on to us.
  
  Line of sight vector
  --------------------
  We already have the face normal vector, as that's how faces are stored in the
  memory (see the ship blueprints documentation at XX21 for more information on
  this). So how can we calculate the line of sight vector?
  
  The first solution that springs to mind is to use the vector from our position
  to the ship we are trying to draw. Our ship is always at the origin (0, 0, 0),
  so this would mean the line of sight vector would be the vector from the
  origin to the ship at (x, y, z), or [x y z]. This is close, but it isn't quite
  right as the line of sight we are interested in is towards the face, not the
  centre of the ship.
  
  Luckily, any point on the face will do for our calculation, so we just need to
  find the vector from our position to any point on the face, and the dot
  product will work fine. Indeed, we can extend that to say that any point on
  the plane containing the face will suffice; if you think about it, extending
  the face in all directions wouldn't change its visibility to us, so it won't
  change the calculation if we pick a point that is outside the limits of the
  actual face we want to draw. It just has to be in the same plane as the face
  for this to work.
  
  Given this, perhaps we can get hold of a vector that goes from the ship's
  centre to a point on the extended face plane? As then we could define our line
  of sight vector by adding the vector to the ship's centre, and the vector from
  the ship's centre to the extended face plane.
  
  Luckily - well, it isn't luck, it's by design, but it feels lucky - this is
  exactly how faces are stored in Elite. Each face is stored as a face normal
  vector, but that normal is specifically designed to be the vector from the
  centre of the ship to the nearest point on the extended face plane. The
  direction of the vector stored in the ship's blueprint is parallel to the
  face normal (the hedgehog spike), but its magnitude (i.e. the vector's length)
  is set to the distance from the ship's centre to the extended face plane. So,
  by design, we can add this vector to the ship's position in space to get the
  line of sight vector from our ship to a point on the face plane, like so:
  
    line of sight vector = [x y z] + face normal vector
  
  and we can then calculate the dot product of this vector with the face normal
  vector to get our positive or negative result, which determines whether this
  face is hidden or visible.
  
  (Incidentally, the face normal vector that's stored in the ship's blueprint
  goes from the ship's centre to the nearest point on the extended face plane,
  as the vector is a normal, though we don't need to use this fact, it's just
  an interesting consequence of how this is all set up.)
  
  Projecting onto the orientation vector space
  --------------------------------------------
  So are we done? Not quite. The maths is all good, but the way the coordinates
  and vectors are stored means we have to do a bit more geometry before we can
  plug the values into our dot product equation.
  
  The problem is that the vector from our position to the ship we're displaying
  uses a different set of axes to the ship's blueprint. As we cavort through
  space, pitching and rolling away, the x-axis is always pointing to the right
  on screen, the y-axis always points up, and the z-axis always points into the
  screen. This is always the case, even if we switch views (this is where the
  PLUT routine comes in, as it switches the axes around to maintain this
  relationship between the screen and the axes). When we roll, pitch and travel
  through space, we don't actually roll or pitch, but instead we rotate the
  universe around us (this is done in the MVEIT routine). On top of this, each
  ship has its own set of orientation vectors - nosev, roofv and sidev - that
  determine the direction that the ship is pointing.
  
  The problem is that the face normal vector in the ship's blueprint is stored
  in terms of an unrotated ship. Ship coordinates are stored with the x, y and
  z axes along the orientation vectors, so if we were sitting in the ship,
  the x-coordinate of the face normal vector would be pointing to our right, the
  y-coordinate would be pointing up, and the z-coordinate would be pointing
  forward, because that's how the coordinates are stored. This intentionally
  coincides with the way the orientation vectors point; from the perspective of
  the pilot of the other ship, sidev is the x-axis going off to the right, roofv
  is the y-axis going up, and the z-axis is nosev, heading forward. The face
  normal vectors are stored with reference to these orientation vectors as axes;
  mathematically speaking, the ship's orientation vectors form an orthonormal
  basis for the Euclidean space in which the face normals are expressed.
  
  So somehow we need to merge these two coordinate systems - the orientation of
  the universe from the perspective of our ship vs the orientation of the
  universe from the perspective of the other ship. Luckily there's an easy
  solution, and again it involves the dot product.
  
  The feature of the dot product that we use to merge the coordinate systems is
  called "scalar projection". This says that given a vector and a unit vector,
  we can calculate the projection of the vector onto the unit vector by simply
  calculating the dot product. If we do this with a vector and three unit
  vectors, then the dot product gives us that vector, expressed in terms of the
  three unit vectors - in other words, this is how we convert coordinates from
  one set of axes to another.
  
  In our case, we have the following equation to calculate:
  
    line of sight vector . face normal vector
  
  where:
  
    line of sight vector = [x y z] + face normal vector
  
  so if we can convert [x y z] to use the same axes as the face normal vector,
  then we can do our calculation. As discussed above, the face normal vector
  uses the ship's orientation vectors as its axes, and we know that the
  orientation vectors are unit vectors because they are orthonormal (and we
  keep calling the TIDY routine to ensure that they stay this way). So we can
  project the [x y z] vector onto each of the orientation vectors in turn, like
  this:
  
    [x y z] projected onto sidev = [x y z] . sidev
    [x y z] projected onto roofv = [x y z] . roofv
    [x y z] projected onto nosev = [x y z] . nosev
  
  and because the orientation vectors are effectively the x, y and z axes for
  the ship's space, we can combine them into our projected line of sight vector
  like this:
  
                               [ [x y z] . sidev ]
    projected [x y z] vector = [ [x y z] . roofv ]
                               [ [x y z] . nosev ]
  
  The final step is to combine all of the above into our final equation. This is
  the value we want to calculate:
  
    line of sight vector . face normal vector
  
  and we know that:
  
    line of sight vector = [x y z] + face normal vector
  
  so if we now project the [x y z] vector into the same space as the face
  normals so we can combine them properly, we get:
  
    line of sight vector = projected [x y z] vector + face normal vector
  
                           [ [x y z] . sidev ]   [ normal_x ]
                         = [ [x y z] . roofv ] + [ normal_y ]
                           [ [x y z] . nosev ]   [ normal_z ]
  
                           [ [x y z] . sidev + normal_x ]
                         = [ [x y z] . roofv + normal_y ]
                           [ [x y z] . nosev + normal_z ]
  
  and if we substitute this into our final calculation, we can calculate the dot
  product as follows:
  
                 [ [x y z] . sidev + normal_x ]   [ normal_x ]
    visibility = [ [x y z] . roofv + normal_y ] . [ normal_y ]
                 [ [x y z] . nosev + normal_z ]   [ normal_z ]
  
  If the result is negative the face is visible, otherwise it is not visible.
  
  This is exactly what happens in part 5 of the LL9 routine. We set the block of
  memory at XX15 to the left-hand side of the final calculation and the block at
  XX12 block to the right-hand side, and calculate the dot product XX12 . XX15
  to tell us whether or not this face is visible, which we store in the table at
  XX2. This gets repeated for all the faces until XX2 contains the visibilities
  of all the faces for this ship.