Coordinate Systems, Vectors, Planes FAQ
=======================================

Version 1.4  28th December 2001
-------------------------------

This FAQ is now maintained by "andreas@(no-spam)cs.ualberta.ca".
Any additional suggestions or related questions are welcome.
Just send E-mail to the above address.

The latest copy of this FAQ can be found at the following web page:

    
http://www.cs.ualberta.ca/~andreas/math/vectfaq_latest.html

Feel free to distribute or copy this FAQ as you please.

Contributions
-------------

  Appearance: Cleaned out some of the empty lines, made the header like the
matrfaq:  Andreas Junghanns


History
-------

I (Andreas) received this FAQ from "Sylvain Carette" by email.
I tried to find "hexapod@(no-spam)netcom.com" who seemed to have maintained
this (as others) for a while, but the site at netcom.com doesn't exist anymore,
emails bounce.  Since I (and colleques) wasted quite some time figuring out
what was wrong with some of the algorithms given in the earlier versions of
this document, I decided to correct it and put it back on the web.

The formerly given sites for the location of these documents do
not exist anymore:
  ftp://ftp.netcom.com/pub/he/hexapod/index.html
  http://www.glue.umd.edu/~rsrodger


Versions, dates and links to local copies (so you can compare):
vectfaq_1.03.html: Version 1.3  17th March 1998
vectfaq_1.04.html: Version 1.4  28th December 2001

Please refrain from asking me math questions. I am only maintaining this FAQ
and have very little knowledge about the subject. But, if you have a
question that is not answered by this FAQ and later happen to find the
answer and believe it to be relevant for this FAQ (or its readers), please
send all relevant information, hopefully in a pre-digested form, to me to
be included here. Thanks!
If you prefer to appear as "anonymous" in the contributions list, let me
know, otherwise I'll just put you down with whatever name I can gather from
your email header.



Questions
---------


COORDINATE SYSTEMS
==================

Q1.  What is a coordinate system?
Q2.  What is a point?
Q3.  What is a origin?
Q4.  What is a vector?
Q5.  What is a column vector?
Q6.  What is a row vector?
Q7.  What is a vertex?
Q8.  What are homogeneous coordinates?
Q9.  What is the Euclidean coordinate system?
Q10. What is the Polar coordinate system?
Q11. How do I display Polar coordinates?
Q12. What are right-handed and left-handed coordinate systems?
Q13. Which is the best coordinate system to use?
Q14. How do rotation angles relate to coordinate systems?
Q15. What is a global coordinate system?
Q16. What is a local coordinate system?
Q17. How do I convert Euclidean to Polar coordinates?
Q18. How do I convert Polar to Euclidean coordinates?
Q19. How do I convert between rotation systems?


VECTORS
=======

Q20. How do I represent a vector using the C/C++ programming languages?
Q21. How do I calculate the length of a vector?
Q22. What is the magnitude of a vector?
Q23. What is a normalised vector?
Q24. How do I normalise a vector?
Q25. What is an unit vector?
Q26. What is a direction vector?
Q27. What is an outward normal?
Q28. What is a dot product?
Q29. How do I determine the angle between two vectors?
Q30. What is a cross product?
Q31. How do I add two vectors?
Q32. How do I subtract two vectors?
Q33. How do I scale a vector?
Q34. How do I perform linear interpolation between two vectors?
Q35. How do I perform cubic interpolation between four vectors?


PLANES
======

Q36. What is a plane equation?
Q37. How do I evaluate a point relative to a plane?
Q38. How do I find the point of intersection with a between and a plane?
Q39. How do I calculate the reflection of a vector from a plane equation?
Q40. How is the reflection of a vector equation derived?
Q41. How do I calculate the acceleration of an object on a sloping surface?


DEFORMATION PATCHES
===================

Q42. What are deformation patches?
Q43. What are linear deformation patches?
Q44. How do I perform linear deformation?
Q45. How do I implement a linear deformation system?
Q46. How do I define a cubic deformation patch?
Q47. How do I evaluate a deformation patch?
Q48. How do I implement a deformation patch system?
Q49. How can I use keyframe animation with deformation patches?


Answers
-------

COORDINATE SYSTEMS
==================

Q1.  What is a coordinate system?
---------------------------------

  A coordinate system is a way of defining multi-dimensional space so that
  every individual point in space can be referenced uniquely.

  Several types of coordinate systems exist. These include the following:

    o Euclidean coordinate system

    o Polar coordinate system

  A coordinate system may exist in one, two, three or more dimensions.

  A one dimensional coordinate system defines a set of coordinates along
  a single straight line.

  A two dimensional coordinate system defines a flat rectangular space.
  This requires a pair of coordinates.

  A three dimensional coordinate system defines a solid box. This requires
  a triplet of coordinates.

  A coordinate system using four or more dimensions requires some
  imagination in order to be visualised. Several method exist to handle
  this situation.

  With four to six dimensions, the first three coordinates can be used to
  define standard 3D Euclidean space. The remaining three coordinates
  can be converted into a set of RGB color values. This system is used
  in CAT or NMR scanners. The first three dimensions are the position of
  the patients body. The fourth dimension defines the signal intensity
  for an individual voxel or point in the patients body.


Q2.  What is a point?
---------------------

  A point is an absolute position in space. It measures the displacement
  of the point along each axis or dimension of the coordinate system.


Q3.  What is a origin?
----------------------

  The origin is the point within the coordinate system, where the
  displacement along each axis or dimension is equal to zero.

  For example, with the Euclidean coordinate system, the point (0,0,0)
  is the origin.


Q4.  What is a vector?
----------------------

  Mathematically speaking, a vector differs from a point in that it
  defines the displacement between two points rather than the
  physical location of an actual point in space.

  A point does not define a direction, while a vector does.

  However, a vector between the origin and a point in space, has exactly
  the same coordinates.


Q5.  What is a column vector?
------------------------------

  By convention, two dimensional and three dimensional vectors are
  represented as a single vertical column of numeric values ie:


        | x |                   | x |
    V = |   |               V = | y |
        | y |                   | z |

  Two dimensions            Three dimensions

  A list of vectors (eg. the geometry of a 3D model) is represented
  simply by adding additional columns ie.

        | x1 x2 x3 ... xN |
    V = | y1 y2 y4 ... yN |
        | z1 z2 z4 ... zN |

Q6.  What is row vector?
------------------------

  For problem-solving, a vector may be described as V = (x,y,z) during
  the specification of a problem.

  This is a row vector. However, row-vectors should not really be used
  with any mathematical descriptions.


Q7.  What is a vertex?
----------------------

  A vertex is another name for a point. However, it used specifically
  when referring to a group of points arranged into a geometric shape.


Q8.  What are homogeneous coordinates?
--------------------------------------

  Homogenous coordinates are used in order to implement perspective depth
  projection operations using matrices. With ordinary matrix multiplication
  it is not possible to divide columns of a matrix by the value of a
  particular element ie. Dividing X and Y by Z.

  Homogeneous coordinates get around this problem by defining an additional
  coordinate W. When vectors are normally defined, this value is always
  set to 1.0. Because, of this, it is not usually necessary to store this
  value with 3D coordinates and vectors.

  The use of this coordinate is the reason why all projection matrices are
  4x4 in size.

  When a 3D vector is multiplied with a projection matrix, the W
  coordinate gets multiplied alongside XYZ. The resulting value is
  then used to divide each of X,Y and Z.

  A simple perspective matrix will set the value of W to Z.


Q9.  What is the Euclidean coordinate system?
---------------------------------------------

  Euclidean coordinates can range from 1 to N dimension. Each dimension
  is always perpendicular to all the others. Two and three dimensions
  are most commonly used by game systems.

  In a two dimensional system, each position is defined by two coordinates
  X and Y. A two-dimensional system is as follows:

    +-------------------+
    |                   |
    |       +Y          |
    |                   |
    |        o          |
    |        |          |
    |        |          |
    |        |          |
    |        |          |
    |    ....o----o +X  |
    |        .          |
    |        .          |
    |        .          |
    |        .          |
    |                   |
    +-------------------+

  In a three dimensional system, an additional Z coordinate is added.

    +-------------------+
    |                   |
    |       +Y          |
    |                   |
    |        o          |
    |        |          |
    |        |          |
    |        |          |
    |        |          |
    |    ....o----o +X  |
    |       /.          |
    |      / .          |
    |     /  .          |
    | +Z o   .          |
    |                   |
    +-------------------+

  For example, a football field can be represented as a coordinate system.
  The  centre point is the origin. The X axis is the centre line, the Z
  axis is the direction from one goal to another and the Y axis is the
  height of the football from the ground.

  The Euclidean coordinate system can also be extended into four or more
  dimensions.

  For example, in a flight simulator game, it may be useful to keep track
  of the flight path of an aeroplane. In this case, the fourth dimension
  actually defines time.


Q10. What is the Polar coordinate system?
-----------------------------------------

  The Polar coordinate system differs from the Euclidean coordinate system
  in that each point in space is defined in terms of its position and
  distance from a sphere with unit radius.

  The centre of the sphere is the origin . The first two coordinates
  define longitude and latitude on the sphere. In effect they wrap a two
  dimensional coordinate system onto the surface of the sphere.

  The third coordinate defines the distance of the point from the centre
  of the sphere.

  Each point defines a triplet of values (latitude, longitude and height).
  Latitude ranges from +90 to -90. Longitude ranges from  -180 to +180, and
  height range from 0 to infinity. Height can be negative.

  ie. ( +90, --, +r ) defines the North Pole.

      ( -90, --, -r ) defines the South Pole.

      (   0,  0,  r ) is a point on the equator.


Q11. How do I display Polar coordinates?
----------------------------------------

  Longitude and Latitude can be displayed as floating point values or
  as degrees, minutes and seconds (and even arc-seconds).

  These angles are represented in the format

       o
     dd  mm' ss"

  where dd ranges from -180 to 180,
        mm ranges from 0 to 59,
    and ss ranges from 0 to 59.

  dd defines the integer number of degrees, while mm and ss take the
  fractional part and scale it into two other integers ie:

    ----------------------------------

    frac = modf( angle, &dd ) * 3600.0

    ss   = frac % 60

    mm   = frac - ss

    ----------------------------------


Q12.  What are right-handed and left-handed coordinate systems?
---------------------------------------------------------------

  When working with coordinates in the Euclidean coordinate system
  there are two possible ways of arranging the three XYZ coordinate
  axii.

  One way is to have the positive Z-axis point outwards of the screen.
  This is referred to as the "right-handed coordinate system" and is
  the system preferred by mathematicians.

  The more negative a coordinate is, the further back into the screen it
  appears. Coordinates with positive values are behind the observer.

  Alternatively, the positive Z-axis can be made to point into the
  screen. This is referred to as the "left-handed coordinate system".

  This is opposite to the right-handed coordinate system. The more
  positive a coordinate is, the further back into the screen it appears.
  Coordinates with positive values are behind the observer.

   Left-handed coordinate system    Right-handed coordinate system   
  +-----------------------------+   +------------------------------+  
  |                             |   |                              |  
  |             +Y              |   |           +Y                 |  
  |              ^              |   |            ^                 |  
  |              |      +Z      |   |            |                 |  
  |              |   -o         |   |            |    .            |  
  |              |   /|         |   |            |   .             |  
  |              |  /           |   |            |  .              |  
  |              | /            |   |            | .               |
  |              |/             |   |            |.                |  
  |       .......o-------> +X   |   |     .......o-------> +X      |  
  |             ..              |   |           /.                 |  
  |            . .              |   |          / .                 |  
  |           .  .              |   |         /  .                 |  
  |          .   .              |   |       |/   .                 |  
  |         .    .              |   |       o-   .                 |  
  |              .              |   |            .                 |  
  |              .              |   |     +Z     .                 |  
  |                             |   |                              |
  +-----------------------------+   +------------------------------+  

  If the direction of the Y-axis is reversed, then whichever coordinate
  system is currently in use becomes the direct opposite.

  OpenGl and XGL use the right-handed coordinate system. Direct3D uses
  the left-handed coordinate system.

  The terms "left-handed" and "right-handed" are 
  derived from the way you can use your thumb, index and middle fingers 
  to model the
  selected coordinate systems.

  If you point the index finger of your right hand in the direction of
  the Z-axis, then your right thumb points in the direction of the Y-axis
  and your right middle finger points in the direction of the X-axis.

  If the direction of the Z-axis is reversed (ie. pointing into the
  screen) then this is defined as a "left-handed" coordinate system.
  This is because your left thumb now points in the direction of the
  Y-axis and your left middle finger nows points in the direction of
  the X-axis.


Q13. Which is the best coordinate system to use?
------------------------------------------------

  In practical use, there is no particular advantage that either the
  left-handed or right-hand coordinatee systems has over the other.
  The main reason for choosing one system over the other is purely
  a matter of convenience.

  Such reasons might include maintaining compatability with the
  underlying 3D API or geographical coordinate system. For example
  OpenGL uses a right-handed coordinate system, while Direct 3D uses
  a left-handed coordinate system.

  For an aircraft simulator, it is convenient to "map" the geographical
  longitude with the X-axis, geographical latitude with the Y-axis and
  height (or depth) with the Z-axis. When combined together, all three
  coordinate axii form the right-handed coordinate system, albeit rotated
  -90 degrees in the X-axis.

      Right-handed coordinate system
      for aircraft simulator
     +------------------------------+
     |                              |
     |           +Z                 |
     |            ^      +Y         |
     |            |    -o           |
     |            |    /|           |
     |            |   /             |
     |            |  /              |
     |            | /               |
     |            |/                |
     |     .......o-------> +X      |
     |           ..                 |
     |          . .                 |
     |         .  .                 |
     |        .   .                 |
     |       .    .                 |
     |            .                 |
     |            .                 |
     |                              |
     +------------------------------+

  In the case of a submarine simulator, the Z-axis actually has polarity
  reversed, so that positive values of Z represents increasing depth,
  while the X and Y still represent longitude and latitude respectively.
  Thus, all three coordinate axii form the left-handed coordinate system,
  albeit rotated +90 degrees in the X-axis.


      Left-handed coordinate system
      for submarine simulator
     +-----------------------------+
     |                             |
     |              .              |
     |              .      +Y      |
     |              .   -o         |
     |              .   /|         |
     |              .  /           |
     |              . /            |
     |              ./             |
     |       .......o-------> +X   |
     |             .|              |
     |            . |              |
     |           .  |              |
     |          .   |              |
     |         .    |              |
     |              |              |
     |              V              |
     |             +Z              |
     |                             |
     +-----------------------------+

  For the aircraft simulator, converting coordinates to OpenGL is simply
  a matter of performing a +90 degree rotation in the X-axis.

  Likewise, for the submatine simulator, the conversion to OpeGL is
  simply a matter of performing a -90 degree rotation in the X-axis.



Q14. How do rotation angles relate to coordinate systems?
---------------------------------------------------------

  By mathematical convention, a positive rotation angle generates a
  clockwise rotation when looking from the origin towards the positive
  end of the selected rotation axis.

  Given this relationship between rotation angles and coordinate
  systems, it is possible to derive the rotation matrices for each
  rotation axis.


Q15. What is a global coordinate system?
----------------------------------------

  Global coordinate system are used to assign the coordinates of all
  points relative to a single common origin.

  For example, when tracking the positions of players in a 3D maze, it
  is convenient to have all players and obstacles assign coordinates
  relative to a single common origin eg. The entrance/exit of the maze.


Q16. What is a local coordinate system?
---------------------------------------

  Local coordinate systems are used to assign the coordinates of all
  points relative to one or more origins.

  For example, using the Euclidean coordinate system to animate the
  movement of a multi-jointed robot arm, it is convenient to assign
  each joint separate local coordinate systems.

  The point of rotation of each joint actually becomes the origin of
  the related geometry.

  This allows for the surface geometry of each joint to be transformed
  by the current position of that joint.

  The coordinate system need not always Euclidean. In the case of
  astronomy and tracking the positions of features on the moon or
  other planets, it is necessary to give each planet its own local
  polar coordinates system.

  However, the position of all planets can be defined using a global
  coordinate system, with the Sun being placed at the origin.


Q17. How do I convert Euclidean to Polar coordinates?
-----------------------------------------------------

  With a Euclidean coordinate (x y z), the goal is to convert it into a
  Polar coordinate (latitude, longitude, distance).

  The conversion is as follows:

    -----------------------------------------
    distance  = sqrt( x*x + y*y + z*z )

    x        /= distance;
    y        /= distance;
    z        /= distance;

    xz_dist   = sqrt( x*x + z*z )
    latitude  = atan2( xz_dist, y ) * RADIANS
    longitude = atan2( x,       z ) * RADIANS
    -----------------------------------------


Q18. How do I convert Polar to Euclidean coordinates?
-----------------------------------------------------

  With a Polar coordinate (latitude, longitude, distance), the goal is to
  convert it into a Euclidean coordinate (x y z).

  The conversion is as follows:

    -----------------------------------------
    x = cos( latitude ) . sin( longitude )
    y = sin( latitude )
    z = cos( latitude ) . cos( longitude )
    -----------------------------------------


Q19. How do I convert between rotation systems?
-----------------------------------------------

  Altogether, there are around five different ways in which a rotation
  in three dimensions can be represented:

  These include:

    Euler angles
    Matrices
    Quaternions
    Rotation Axis/Angle
    Spherical Rotation Angles

  Euler angles define each rotation as a combination of rotations in
  each of the three main X, Y and Z axii. Euler angles must be converted
  to matrices before any vertex transformations can be performed.

  Matrices define each rotation as an 2D array of values which are
  multiplied with an array of vertices. They can either be 3x3 or 4x4
  in size.

  Quaternions define each rotation in 4 dimension instead of three. As a
  result they require four floating point values. Quaternions must be
  connverted to matrices before any vertex transformation can be
  performed.

  Rotation Axis/Angles define each rotation as a unit vector along with
  a specifiede rotation angle along that axis. Rotation Axis/Angle pairs
  must be converted into Quaternions before finally being converted into
  a rotation matrix.

  Spherical angles define each rotation in terms of latitude/longitude
  and a rotation angle. They must be converted into a rotation matrix
  through the use of AxisAngle and Quaternion coordinates.


  The conversion paths are as follows:

         +--------------+     +--------------+     +--------------+
         |    Matrix    |<===>|  Quaternion  |<===>|   AxisAngle  |
         +--------------+     +--------------+     +--------------+
                /\                                        /\
                ||                                        ||
                \/                                        \/
         +--------------+                          +--------------+
         | Euler angles |                          |  Spherical   |
         +--------------+                          +--------------+

  A comparision of the various representations is presented below:

    +--------------+------------+---------------------------------------+
    | Data type    | Size       | Usage                                 |
    +--------------+------------+---------------------------------------+
    | Euler Angles | FLOAT * 3  | Must be converted to a matrix         |
    |              |            | Gimbal lock can occur                 |
    +--------------+------------+---------------------------------------+
    | Matrix       | FLOAT * 9  | Can be used directly for vertex       |
    |              | FLOAT * 16 | transformation                        |
    |              |            | 3x3 matrices can be used for rotation |
    |              |            | and scaling only.                     |
    |              |            | 4x4 matrices can be used for both     |
    |              |            | translation and perspective           |
    +--------------+------------+---------------------------------------+
    | Quaternion   | FLOAT * 4  | Must be converted to a matrix         |
    |              |            | No danger of Gimbal lock              |
    +--------------+------------+---------------------------------------+
    | Axis Angle   | FLOAT * 4  | Must be converted to a matrix through |
    |              |            | the use of Quaternions.               |
    |              |            | No danger of Gimbal lock              |
    +--------------+------------+---------------------------------------+
    | Spherical    | FLOAT * 3  | Must be converted to a matrix through |
    |              |            | the use of AxisAngle and Quaternion   |
    |              |            | representations.                      |
    |              |            | No danger of Gimbal lock              |
    +--------------+------------+---------------------------------------+


VECTORS
=======

Q20. How do I represent a vector using the C/C++ programming languages?
-----------------------------------------------------------------------

  The most convenient way of representing a vector using the C/C++
  programming languages is through the use of a data structure:

    typedef float VFLOAT;

    typedef vector3_st
      {
      VFLOAT vx;
      VFLOAT vy;
      VFLOAT vz;
      } VECTOR3;

  or through the use of arrays:

    typedef VFLOAT VECTOR3[3];


  For convenience and modularity, it is always a good idea to define
  labels for commonly used data types that may vary from system to system.
  Thus floating point values are given the label "VFLOAT".


Q21. How do I calculate the length of a vector?
-----------------------------------------------

  The length of a vector is calculated by taking the square root of
  the sum of the squares of each coordinate ie.

  If the vector is defined as (x,y,z) then the length of the vector is
  calculated from:


           ----------------
          /  2    2    2
    L = \/  x  + y  + z


Q22. What is the magnitude of a vector?
---------------------------------------

  This is equivalent to the length of a vector.

  Placing a pair of vertical lines around a vector indicates the
  magnitude of the vector.

  eg. If the variable V is used to represent a vector, then the
  expression |V| indicates the magnitude of a vector.


Q23. What is a normalised vector?
---------------------------------

  A normalised vector is a vector where the sum of the squares of all
  coordinates is equal to one.

  For example, the vector ( 2, 2, 0 ) is not normalised, while the
  vectors ( 0.707, 0.707, 0.0) and ( 1.0, 0.0, 0.0 ) are normalised.


Q24. How do I normalise a vector?
---------------------------------

  A vector can be normalised by calculating the magnitude or length of
  the vector and dividing each coordinate by this value.

  For example, consider the vector

        | 3.0 |
    V = | 4.0 |
        | 0.0 |

  The length of this vector is 5.0

    |V| = 5.0

  Then the value of the normalised vector is given by:

     V    | 3.0 |   1   | 0.6 |
    --- = | 4.0 | . - = | 0.8 |
    |V|   | 0.0 |   5   | 0.0 |


  If the vector is already normalised, then the value of |V| will be
  equal to one, and after division, the vector will remain as before.


Q25. What is an unit vector?
----------------------------

  A unit vector is another name for a normalised vector. The sum of the
  squares of all coordinates is equal to one.


Q26. What is a direction vector?
--------------------------------

  A direction vector is another name for a vector, but which is
  specifically used for the purpose of determining the direction that
  a polygon surface or vertex is facing.

  However, direction vectors are not necessarily always normalised.

  For example, a direction vector may be used to represent wind direction
  of points within a landscape. The magnitude of the vector is used to
  represent wind speed combined with the direction of the wind.


Q27. What is an outward normal?
-------------------------------

  An outward normal is another name for a normalised vector. Similar
  in purpose to a direction vector, an outward normal are used
  specifically for representing the direction that a polygon surface or
  vertex is facing.


Q28. What is a dot product?
---------------------------

  The dot product is used to calculate the angle between two vectors.

  If v1 and v2 are two normalised vectors, then the dot product is given
  by the expression:

    v1.v2

  For a pair of three dimension vectors this expression is evaluated
  using the equation:

    d =     v1 . v2

        | x1 |   | x2 |
    d = | y1 | . | y2 |
        | z1 |   | z2 |

    d = x1.x2 + y1.y2 + z1.z2


  This can be represented using the C/C++ programming languages as:

    d = v1.x * v2.x + v1.y * v2.y + v1.z * v2.z

  where * is the standard multiplication operation.

  For efficiency, this function can represented as C #define macros or
  C++ inline class functions.


Q29. How do I determine the angle between two vectors?
------------------------------------------------------

  The angle between two normalised vectors can be calculated from the
  mathematical expression:

    cos A = v1.v2

            | x1 |   | x2 |
          = | y1 | . | y2 |
            | z1 |   | z2 |

  where cos is the cosine function,
          A is the angle between the two vectors,
         v1 is the first vector and
         v2 is the second vector

  The expression v1.v2 is the actual dot product

  If the two vectors are not normalised, then the following expression
  can be used:

              v1.v2
    cos A = ---------
             v1 . v2
             --   --

  where -- is the magnitude or length of the vector.

  This takes the dot product of the two vectors, and divides the result
  by the product of the lengths of both vectors.


Q30. What is a cross product?
-----------------------------

  The cross product between two normalised vectors is used to determine
  the vector which perpendicular to both the vectors. This is expressed
  as the mathematical expression:

    v3 = v1 x v2

         | x1 |   | x2 |
    v3 = | y1 | x | y2 |
         | z1 |   | z2 |

         | y1.z2 + z1.y2 |
    v3 = | z1.x2 + x1.z2 |
         | x1.y2 + y1.x2 |

  This can be represented using the C/C++ programming languages as:

    v3.vx = v1.y * v2.z + v1.z * v2.y
    v3.vy = v1.z * v2.x + v1.x * v2.z
    v3.vz = v1.x * v2.y + v1.y * v2.x

  For efficiency, this function can represented as C #define macros or
  C++ inline class functions.


Q31. How do I add two vectors?
------------------------------

  Adding two vectors together is very simple to perform. This is achieved
  by adding together the individual coordinates of each vector. The
  operation is defined by the following mathematical expression:

    v3 = v1 + v2

         | x1 |   | x2 |
    v3 = | y1 | + | y2 |
         | z1 |   | z2 |

         | x1 + x2 |
    v3 = | y1 + y2 |
         | z1 + z2 |

  This can be represented using the C/C++ programming languages as:

    v3.vx = v1.vx + v2.vx
    v3.vy = v1.vy + v2.vy
    v3.vz = v1.vz + v2.vz

  For efficiency, this function can represented as C #define macros or
  C++ inline class functions.


Q32. How do I subtract two vectors?
-----------------------------------

  Subtraction is performed in the same way as addition. This is achieved
  by subtracting the individual coordinates of each vector. The
  operation is defined by the following mathematical expression:

    v3 = v1 - v2

         | x1 |   | x2 |
    v3 = | y1 | - | y2 |
         | z1 |   | z2 |

         | x1 - x2 |
    v3 = | y1 - y2 |
         | z1 - z2 |

  This can be represented using the C/C++ programming languages as:

    v3.vx = v1.vx - v2.vx
    v3.vy = v1.vy - v2.vy
    v3.vz = v1.vz - v2.vz

  For efficiency, this function can represented as C #define macros or
  C++ inline class functions.


Q33. How do I scale a vector?
-----------------------------

  A vector can be scaled (enlarged or reduced) in a way similar to
  multiplication. This is achieved by multiplying each coordinate by the
  same scaling factor. The mathematical expression for this is as follows:

    v2 = v1 . S

         | x1 |
    v3 = | y1 | . S
         | z1 |

         | x1.S |
    v3 = | y1.S |
         | z1.S |

  This can be represented using the C/C++ programming languages as:

    v3.vx = v1.vx * S
    v3.vy = v1.vy * S
    v3.vz = v1.vz * S

  For efficiency, this function can represented as C #define macros or
  C++ inline class functions.


Q34. How do I perform linear interpolation between two vectors?
---------------------------------------------------------------

  For many 3D applications, it is sometimes necessary to perform linear
  interpolation between two vectors. Such applications can include view
  frustum clipping and morphing.

  Linear interpolation is implemented by taking the coordinates of two
  known points and scaling them in such a way as to generate a series
  of points that forms a straight line between them.

  This equation is sometimes referred to as a blending function. For
  linear interpolation this equations is as follows:

    V' = (1-t).Va + t.Vb

    V' = Va + t.(Vb-Va)

  The second form is more commonly used as it only requires a single
  multiplication operation.

  This is implemented using the following set of vector operations:

  Using the C programming language:

  void v3_linear( VECTOR3 *vr, VECTOR3 *va, VECTOR3 *vb, VFLOAT t )
    {
    v3_sub(    &vtemp,   vb, va    );
    v3_scalef( &vtemp,  &vtemp, t  );
    v3_add(    &vr,     &vtemp, va );
    }

Q35. How do I perform cubic interpolation between four vectors?
---------------------------------------------------------------

  Given four vectors, the problem is to find a way  of determining
  intermediate positions specified by a parametric variable t.

  This can be achieved by making use of cubic interpolation. The set
  of four vectors is combined into a single geometry vector G.
  Through the use of spline mathematics, this geometry vector is
  converted into an interpolation matrix M.

  If the geometry vector is defined as:

         | x1 x2 x3 x4 |
     G = | y1 y2 y3 y4 |
         | z1 z2 z3 z4 |

  Then multiplication by the base matrix:

         |  -4.5    9.0  -5.5  1.0  |
    Mb = |  13.5  -22.5   9.0  0.0  |
         | -13.5   18.0  -4.5  0.0  |
         |   4.5   -4.5   1.0  0.0  |

  will generate the 3x4 interpolation matrix Mi:

    Mi = G .Mb

  This can be implemented through a modified matrix-vector multiplication:

    m4_multspline( m_cubic, v_geom, v_source );

  Interpolation can then be performed by the use of the parametric
  variable t:

        R  = Mi . t

                           |t^3|
    | xr |   | A B C D |   |t^2|
    | yr | = | E F G H | . |t  |
    | zr |   | I J K L |   |1  |

  This can be implemented through a modified cubic interpolation
  algorithm:

    v3_cubic( vr, v_geom, t );

  The resulting vector can then be used as required.

  The function m4_multspline is implemented as follows:

    -------------------------

    void m4_multspline( MATRIX4 mat, VECTOR3 *vsrc, VECTOR3 *vdst )
      {
      VFLOAT tx, ty, tz;
      int    n;

      for ( n = 0; n < 4; n++ )
        {
        vdst[n].vx = vsrc[0].vx * mat[n]
                   + vsrc[1].vx * mat[n+4]
                   + vsrc[2].vx * mat[n+8]
                   + vsrc[3].vx * mat[n+12];

        vdst[n].vy = vsrc[0].vy * mat[n]
                   + vsrc[1].vy * mat[n+4]
                   + vsrc[2].vy * mat[n+8]
                   + vsrc[3].vy * mat[n+12];

        vdst[n].vz = vsrc[0].vz * mat[n]
                   + vsrc[1].vz * mat[n+4]
                   + vsrc[2].vz * mat[n+8]
                   + vsrc[3].vz * mat[n+12];
        }
      }

    -------------------------

  The function v3_cubic is implemented as follows:

    -------------------------

    void v3_cubic( VECTOR3 *vpos, VECTOR3 *vdst, VFLOAT t )
      {
      vpos -> vx = ((vdst[0].vx*t+vdst[1].vx)*t+vdst[2].vx)*t+vdst[3].vx;
      vpos -> vy = ((vdst[0].vy*t+vdst[1].vy)*t+vdst[2].vy)*t+vdst[3].vy;
      vpos -> vz = ((vdst[0].vz*t+vdst[1].vz)*t+vdst[2].vz)*t+vdst[3].vz;
      }

    -------------------------

  In fact, a cubic spline surface can be generated from the combination
  of these two algorithms:

    -------------------------

    void cubic_patch( VECTOR3 *vlist, VECTOR3 *vsurf, int hdiv, int vdiv )
      {
      MATRIX4 mh_geom[4];
      VECTOR3 mv_geom[4], mv_interp[4];
      VFLOAT  du, dv;
      int     n, u, v;

      if ( hdiv < 1 || vdiv < 1 )             /* Not enough subdivisions? */
        return;                               /* No, so return            */

      for ( n = 0; n < 4; n++ )                        /* Horiz. interp   */
        m4_multspline( m_cubic, vsurf+n*4,mh_geom[n]); /* Make I-matrix   */

      for ( u = 0; u <= hdiv; u++ )                    /* For each column */
        {
        for ( n = 0; n < 4; n++ )
          v3_cubic( mv_geom+n, mh_geom[n], (VFLOAT) u/hdiv );

        m4_multspline( m_cubic, mv_geom, mv_interp );  /* Make I-matrix   */

        for ( v = 0; v <= vdiv; v++, vlist++ )         /* For each row    */
          v3_cubic( vlist,mv_interp,(VFLOAT) v/vdiv ); /* Save vertex     */
        }
      }

    -------------------------


PLANES
======

Q36. What is a plane equation?
------------------------------

  Plane equations are widely used in the field of 3D animation to
  define and manipulate polygon surfaces. Plane equations are used to
  implement back face culling, view frustum culling, clipping and
  collision detection.

  The plane equation or "equation of the plane" is a mathematical
  expression as follows:

    Ax + By + Cz + D = 0

  where A, B, C and D are known constants and (x,y,z) specifies any
  point in three-dimensional space.


Q37. How do I evaluate a point relative to a plane?
---------------------------------------------------

  The position of a point relative to a plane is determined by
  evaluating the plane equation ie. Multiplying each coordinate (x,y,z)
  with the associated parameters (A,B,C) and adding D.

  If the evaluation of a point with the plane equation generates a
  positive value then the point is said to be "in front of the plane".

  If the evaluation generates a result which is negative, then the point
  is said to be "behind the plane".

  Otherwise, if the evaluation generates a result which is exactly
  zero, then the point is said to be "on the plane".

  The values of A,B and C actually define the outward normal of the
  surface. As such, the sum of the squares of these values will always
  add up to one ie.

     2    2    2
    A  + B  + C  - 1 = 0

  In fact, the evaluation of a point relative to the plane is actually
  a dot product calculation.


Q38. How do I find the point of intersection with a line and a plane?
------------------------------------------------------------------------

  For computer animation purpose, it is often convenient to determine
  where a straight 3D line intersects a polygon surface. The polygon
  surface is represented as a plane equation.


  The 3D line may be specified in two possible ways:

    o starting and finishing points ( Vs, Vf )

    o starting point and direction vector ( Vs, Vd )

  If only a starting point and a direction vector are known, then
  a dummy end point is calculated by adding the direction vector to
  the starting point ie:

    Vf = Vs + Vd

  This parameter can then be used in the algorithm defined as follows:

  In the case that both starting and finishing points are known, it is
  possible to determine the point of intersection by evaluating both
  points relative to the plane equation and interpolating ie.

    Es = P( Vs )
    Ef = P( Vf )

  Using these two values as weighting factors, it is possible to
  interpolate between the two endpoints.

  The weighting factor for the two points is evaluated as follows:

          Es             Ef
    Ws = -----     Wf = -----
         Ef-Es          Ef-Es


  Then the point of intersection is calculated as follows:

    Vp = Ws.Vs + Wf.Vf


Q39. How do I calculate the reflection of a vector from a plane equation?
-------------------------------------------------------------------------

  In order to perform calculations such as a light reflecting off a
  reflective surface, it is necessary to be able to calculate the
  reflection of a vector off a plane.

  The plane is represented as an outward normal.

  The mathematical expression for the reflection of a vector is
  given by:

    V' = 2N.(V.N) - V

  where the known (and unknown) parameters are as follows:

    N  = outward normal for the plane
    V  = unit vector of light ray
    V' = unknown unit vector of reflected light ray


Q40. How is the reflection of a vector equation derived?
--------------------------------------------------------

  The reflection of a vector is visualised by the following drawing:

               N
               ^
          V    |    V'
           |-  |  -|
           |\  |  /|
             \ | /
              \|/
         ------o-------

  where:

    V  is the original direction vector

    V' is the reflection direction vector, and

    N  is the outward normal of the plane

  The angle between the vector V and N is given by the dot product ie.

    cos(angle) = V.N

  So the expression must have a component V.N within it

  Then the following angles are known:

    At V.N =  0, V' = -V

    At V.N =  1, V' =  N

    At V.N = -1, V' = -N

  Since V.N = 1 gives N and V.N = -1, gives -N, this indicates that the
  component V.N is multiplied by N, ie.

    V' = f( N.(V.N) )

  where f() is the evalation function (not completely known).

  However, if V.N=0 then a result of -V is given.
  Therefore, there must also be a -V component ie.

    V' = f( N.(V.N) - V )

  But, since at V=N, V.N=1, this equation would cancel out completely.
  Thus, one of the parameters must be scaled by a factor of two.

  Then, the final equation is given by:

    V' = 2N.(V.N) - V

  This can be implemented using the vector library as follows:

    ----------------------

    void v3_reflect( VECTOR3 *vreflect, VECTOR3 *vdir, VECTOR3 *vnormal )
      {
      VFLOAT  angle;
      VECTOR3 vtemp;

      angle = v3_dot( vreflect, vnormal ) * 2;

      v3_scale( &vreflect,  vnormal,  angle   );
      v3_sub(   &vreflect, &vreflect, vnormal );
      }

    ----------------------


Q41. How do I calculate the acceleration of an object on a sloping surface?
---------------------------------------------------------------------------

  In the real world, when an object moves onto a sloping surface, it
  experiences acceleration forces due to gravity. However, because of the
  existence of the sloping surface, the acceleration will not be directly
  in the direction towards the gravitational source. Examples include a
  football rolling down a hill and a person sliding down a mudslide.

  In a virtual 3D environment, the position of an object is represented
  as a vector coordinate, the sloping surface as a plane equation and
  gravity is as a direction vector.

  The problem can then be defined as combining these parameters together
  in order to determine the acceleration force, which is represented as a
  direction vector.

  The following parameters are known:

    Vo = Position vector of the object

    Vg = Direction vector of gravity

    Vp = Outward normal of the current slope polygon


  Only the following parameter is unknown:

    Va = Direction vector of acceleration forces


  This can be visualised as follows:

    -----------------------------------------------

                    Vp = Outward normal of polygon
                 --
          \      /|
           \    /
            \  /
             \O
              |\
              |\\
              | \\| Va = Acceleration force
              |  \-
              V   \

       Vg = Gravity

    -----------------------------------------------

  Then the calculation is as follows:

    Axis of rotation of a rolling object is given by:

      Vt = Vg x Vp

    Then the direction vector representing the acceleration force is
    given by:

      Va = Vt x Vp


  This can be implemented using the 3D vector library as follows:

    -------------------------------

     void v3_slope( VECTOR3 *va, VECTOR3 *vr, VECTOR3 *vg, VECTOR3 *vp )
       {
       v3_cross( &vr, vg, vp );
       v3_cross( &va, vt, vp );
       }

    -------------------------------


DEFORMATION PATCHES
===================

Q42. What are deformation patches?
----------------------------------

  Deformation patches are a means of modifying the shape of an object
  while preserving the connectivity of all the geometry. They attempt
  to warp the local coordinate system of an object so that straight
  lines can become curved lines and vice versa.

  Applications of deformation patches includes special effects and
  character animation. An inanimate object can be made to twist around,
  shrink away from a threatening object and even shuffle or tip-toe
  about. For a really trippy effect, a camera can be made to move
  through an architectural model, while the geometry of the model is
  warped using a deformation patch.

  In the real world (using stop-go animation and clay), deformation of
  an object can be implemented through the use of reshaping, adding or
  removing clay.

  However, when animating by computer, using clay is not an option.
  Instead, surface are modelled using either polygons defined from
  vertices or surfaces defined using spline curves and control points.

  By warping the positions of these vertices and control points, it is
  possible to deform the shape of the object by modifying the local
  coordinate system, while still preserving the connectivity of the
  geometry.

  Warping or "deforming" of the geometry can be implemented using either
  linear or cubic interpolation. Linear interpolation offers considerable
  performance advantages over cubic interpolation, at the sacrifice of
  control over the way the geometry deforms.


Q43. What are linear deformation patches?
-----------------------------------------

  Linear deformation patches are a low-budget version of cubic
  deformation patches. Instead of using cubic interpolation, linear
  interpolation only makes use of linear interpolation of vectors.

  As a result, only eight control points are required, instead of the
  full complement of sixty-four. However, the control points are still
  arranged in the shape of a cube.


Q44. How do I perform linear deformation?
-----------------------------------------

  Once the bounding volume and control points have been defined, the
  next stage is to evaluate the new coordinates of each vertex.

  Each coordinate of the original object is converted into a parametric
  form based on the limits of the bounding volume.

  If the limits of the bounding volume are defined by:

          | Xlo |                 | Xhi |
    Min = | Ylo |    and    Max = | Yhi |
          | Zlo |                 | Zhi |

  Then a point P can be converted to parametric form:

        | X |
    P = | Y |
        | Z |

  Then the parameteric version of P can be calculated from:

         |  X - Xlo  |
         | --------- |
         | Xhi - Xlo |
         |           |
         |  Y - Ylo  |
    P' = | --------- |
         | Yhi - Ylo |
         |           |
         |  Z - Zlo  |
         | --------- |
         | Zhi - Zlo |

  This parametric coordinate can then be used as input to the evaluation
  stage.

  Because the deformation patch exists in three dimensions, this requires
  interpolation through three levels of spline curves:

  +---------------------------------------------------------------------+
  |                                                                     |
  |     Level 1              Level 2             Level 3                |
  |                                                                     |
  |   O------O               ..O..                                      |
  |   ..     ..                |.                                       |
  |   . .    . .               | .                .                     |
  |   .  .   .  .              |  .               .              .      |
  |   .   O------O   P'.X      | ..O..  P'.Y      O     P'.Z      .     |
  |   .   .  .   .   =====>    |   |    =====>    .\    =====>     O    |
  |   .   .  .   .             |   |              . \ .             .   |
  |   .   .  .   .             |   |                 \.              .  |
  |   O---.--O   .           ..O.. |                  O                 |
  |    .  .   .  .              .  |                  .                 |
  |     . .    . .               . |                  .                 |
  |      ..     ..                .|                                    |
  |       O------O               ..O..                                  |
  |                                                                     |
  +---------------------------------------------------------------------+

  The first level is defined from four interpolation lines, each of
  which is defined from pair of control points in the X-axis.

  Substituting in the X-axis parametric coordinate from P' generates
  a new set of 4 control points.

  These are used to generate two interpolation lines in the Y-axis.

  Substituting in the Y-axis parameteric coordinate from P' generates
  a new set of 2 control points.

  These are used to generate a single interpolation line in the Z-axis.

  Substituting in the Z-axis parametric coordinate from P' generates
  a single coordinate.

  This coordinate is in fact the final warped position of the point P.

  Each vertex or control point of the model is processed in this manner
  until all every coordinate has been processed.


Q45. How do I implement a linear deformation system?
----------------------------------------------------

  Implementation of a deformation patch system requires three sets of
  input parameters. These include the following:

    o Model geometry

    o Original bounding cube

    o Deformation patch (8 control points)

  The evaluation function, must then accept a set of vertex data as
  input (these might even be control points of a NURBS mesh!), and
  produce a modified set of vertex data as output.

  For efficiency, the default ordering of the control points of the
  deformation patch is X-minor, Z-major, ie. Vertices on the same
  X-axis row are placed next to each other in memory ie.

              | X1 X2 X1 X2 X1 X2 X1 X2 |
    Mdeform = | Y1 Y1 Y2 Y2 Y1 Y1 Y2 Y2 |
              | Z1 Z1 Z1 Z1 Z2 Z2 Z2 Z2 |

  The first stage of linear interpolation will convert each pair of
  control points into a single coordinate.

  By substituting in the parametric X coordinate and evaluating, a set
  of four coordinates are generated:

          | Xp Xp Xp Xp |
    Mdx = | Y1 Y2 Y1 Y2 |
          | Z1 Z1 Z2 Z2 |

  As with the first stage, the parametric Y coordinate is substituted
  and evaluated. This generates a pair of coordinates.

          | Xp Xp |
    Mdy = | Yp Yp |
          | Z1 Z2 |

  Finally, these are converted into a interpolation matrix, and the
  parametric Z coordinate is substituted and evaluated. This generates
  a single coordinate

          | Xp |
    Mdz = | Yp |
          | Zp |

  This is the final processed coordinate.

  A complete routine to perform this is as follows:

  The following parameters are used:

    vnum    - number of vertices to be processed
    vsrc    - source vertex data
    vdst    - processed vertex data
    vlimits - bounding volume for deformation patch
    vdeform - control points for deformation patch (64)

  ------------------------------------------------------

  void lpatch_evaluate( VECTOR3 *vdst, int vnum, VECTOR3 *vsrc,
                        VECTOR3 *vlimits,        VECTOR3 *vdeform )
    {
    VECTOR3  v_diff, vparam, v_ymesh[4], v_zmesh[2];
    int      n, m;

    v3_sub( &v_diff, vlimits+1, vlimits );             /* Scale for box   */

    for ( n = 0; n < vnum; n++ )                       /* For each vertex */
      {
      v3_sub( &vparam,  vsrc+n, vlimits );             /* Get parametric  */
      v3_div( &vparam, &vparam, &v_diff  );            /* coordinates     */

      for ( m = 0; m < 4; m++ )                        /* Get Y-axis mesh */
        v3_linear( v_ymesh+m, vdeform+m*2, vdeform+m*2+1, vparam.vx );

      for ( m = 0; m < 2; m++ )                        /* Get Z-axis mesh */
        v3_linear( v_zmesh+m, v_ymesh+m*2, v_ymesh+m*2+1, vparam.vy );

      v3_linear( vdst+n, v_zmesh, v_zmesh+1, vparam.vz ); /* Final coord. */
      }
    }

  ------------------------------------------------------

Q46. How do I define a cubic deformation patch?
-----------------------------------------------

  A cubic deformation patch is defined as a set of spline curve control
  points arranged in the shape of a cube. Modification of the cubic
  deformation patch is performed by repositioning groups of control points.

  Since a minimum of four points are required to define a spline curve,
  a cubic deformation patch requires at least sixty-four control points.
  Each control point is represented as a single 3D vector.

  It is also necessary to define a bounding volume which contains the
  area of coordinate space which is to be deformed.

  Thus, a single deformation patch can be defined from less than 70 3D
  vectors or less than 1K of memory.


Q47. How do I evaluate a cubic deformation patch?
-------------------------------------------------

  Once the bounding volume and control points have been defined, the
  next stage is to evaluate the new coordinates of each vertex.

  Each coordinate of the original object is converted into a
  parametric form based on the limits of the original bounding volume.

  If the limits of the bounding volume are defined by:

          | Xlo |                 | Xhi |
    Min = | Ylo |    and    Max = | Yhi |
          | Zlo |                 | Zhi |

  Then a point P can be converted to parametric form:

        | X |
    P = | Y |
        | Z |

  Then the parameteric version of P can be calculated from:

         |  X - Xlo  |
         | --------- |
         | Xhi - Xlo |
         |           |
         |  Y - Ylo  |
    P' = | --------- |
         | Yhi - Ylo |
         |           |
         |  Z - Zlo  |
         | --------- |
         | Zhi - Zlo |

  This parametric coordinate can then be used as input to the evaluation
  stage.

  Because the deformation patch exists in three dimensions, this requires
  interpolation through three levels of spline curves:

  +--------------------------------------------------------------------+
  |                                                                    |
  |        Level 1               Level 2      Level 3                  |
  |                                                                    |
  |   o---o---o---o                                                    |
  |   ..   .   .  ..                                                   |
  |   . o---o---o---o                                                  |
  |   .  .   .   ..  .           o                                     |
  |   .   o---o---o---o          |.                                    |
  |   .    .   .  ..   .         | o                                   |
  |   .     o---o---o---o        o |.          o            .          |
  |   .     .     .     .        |.| o          \            .         |
  |   o---o---o---o     .  P'.X  | o |.   P'.Y   o      P'.Z  .        |
  |   ..   ..  .  ..    .        o |.| o          \            .       |
  |   . o---o---o---o   .        |.| o |           o            o      |
  |   .  .  ..   ..  .  .  ===>  | o |.|  ===>      \   ===>     .     |
  |   .   o---o---o---o .        o |.| o             o            .    |
  |   .    ..  .  ..   ..         .| o |                               |
  |   .     o---o---o---o          o |.|                               |
  |   .     .     .     .           .| o                               |
  |   o---o---o---o     .            o |                               |
  |    .   ..  .   .    .             .|                               |
  |     o---o---o---o   .              o                               |
  |      .  ..   .   .  .                                              |
  |       o---o---o---o .                                              |
  |        ..  .   .   ..                                              |
  |         o---o---o---o                                              |
  |                                                                    |
  +--------------------------------------------------------------------+

  The first level is defined from sixteen spline curves, each of which
  is defined from a row of control points in the X-axis.

  Substituting in the X-axis parametric coordinate from P' generates
  a new set of 16 control points.

  These are used to generate four spline curves in the Y-axis.

  Substituting in the Y-axis parameteric coordinate from P' generates
  a new set of 4 control points.

  These are used to generate a single spline path in the Z-axis.

  Substituting in the Z-axis parametric coordinate from P' generates
  a single coordinate.

  This coordinate is in fact the final warped position of the point P.

  Each vertex or control point of the model is processed in this manner
  until all every coordinate has been processed.


Q48. How do I implement a cubic deformation patch system?
---------------------------------------------------------

  Implementation of a deformation patch system requires three sets of
  input parameters. These include the following:

    o Model geometry

    o Original bounding cube

    o Deformation patch (64 control points)

  The evaluation function, must then accept a set of vertex data as
  input (these might even be control points of a NURBS mesh!), and
  produce a modified set of vertex data as output.

  For efficiency, the default ordering of the control points of the
  deformation patch is X-minor, Z-major, ie. Vertices on the same
  X-axis row are placed next to each other in memory ie.

              | X1 X2 X3 X4 X1 X2 X3 X4 ... X4 |
    Mdeform = | Y1 Y1 Y1 Y1 Y2 Y2 Y2 Y2 ... Y4 |
              | Z1 Z1 Z1 Z1 Z1 Z1 Z1 Z1 ... Z4 |

  The first stage of cubic interpolation will convert each set of four
  control points into a cubic interpolation matrix.

  By substituting in the parametric X coordinate and evaluating, a set
  of 16 coordinates are generated:

          | X1 X1 X1 X1  X1 X1 X1 X1  X1 X1 X1 X1  X1 X1 X1 X1 |
    Mdx = | Y1 Y2 Y3 Y4  Y1 Y2 Y3 Y4  Y1 Y2 Y3 Y4  Y1 Y2 Y3 Y4 |
          | Z1 Z1 Z1 Z1  Z2 Z2 Z2 Z2  Z3 Z3 Z3 Z3  Z4 Z4 Z4 Z4 |

  As with the first stage, the parametric Y coordinate is substituted
  and evaluated. This generates a set of four coordinates:

          | X1 X1 X1 X1 |
    Mdy = | Y1 Y1 Y1 Y1 |
          | Z1 Z2 Z3 Z4 |

  Finally, these are converted into a interpolation matrix, and the
  parametric Z coordinate is substituted and evaluated. This generates
  a single coordinate

          | X1 |
    Mdz = | Y1 |
          | Z1 |

  This is the final processed coordinate.

  A complete routine to perform this is as follows:

  The following parameters are used:

    vnum    - number of vertices to be processed
    vsrc    - source vertex data
    vdst    - processed vertex data
    vlimits - bounding volume for deformation patch
    vdeform - control points for deformation patch (64)

  ------------------------------------------------------

  typedef VECTOR3 GVECTOR3[4];

  void dpatch_evaluate( VECTOR3 *vdst, int vnum, VECTOR3 *vsrc,
                        VECTOR3 *vlimits,        VECTOR3 *vdeform )
    {
    GVECTOR3 m_xgeom[16],    m_ygeom[4],  m_zgeom;
    VECTOR3  v_diff, vparam, v_ymesh[16], v_zmesh[4];
    int      n, m;

    v3_sub( &v_diff, vlimits+1, vlimits );               /* Scale for box   */

    for ( m = 0; m < 16; m++ )                           /* I-matrix X-axis */
      m4_multspline( m_cubic, vdeform+m*4, m_xgeom[m] );

    for ( n = 0; n < vnum; n++ )                         /* For each vertex */
      {
      v3_sub( &vparam,  vsrc+n, vlimits );               /* Get parametric  */
      v3_div( &vparam, &vparam, &v_diff  );              /* coordinates     */

      for ( m = 0; m < 16; m++ )                         /* Get Y-axis mesh */
        v3_cubic( v_ymesh+m, m_xgeom[m], vparam.vx );

      for ( m = 0; m < 4; m++ )
        {                                                /* I-matrix Y axis */
        m4_multspline( m_cubic, v_ymesh+m*4, m_ygeom[m] );

        v3_cubic( v_zmesh+m, m_ygeom[m], vparam.vy );    /* Get Z-axis mesh */
        }

      m4_multspline(    m_cubic, v_zmesh, m_zgeom );     /* I-matrix Z axis */

      v3_cubic( vdst+n, m_zgeom, vparam.vz );            /* New coordinate  */
      }
    }

  ------------------------------------------------------


Q49. How do I use keyframe animation with deformation patches?
--------------------------------------------------------------

  Using the algorithm described above, it is only possible to render
  a single rendered frame.

  In order to implement smooth and continuous animation, it is necessary
  to define more than one deformation patch.

  However, defining and positioning a single deformation patch for every
  keyframe is very time-consuming. The solution is to add another
  dimension to the deformation patch ie. time.

  For every two keyframes, it is possible to perform linear interpolation
  to generate each frame between the two keyframes.

  For every four keyframes, it is possible to perform cubic interpolation
  to generate each frame between the four keyframes.

  This allows for smooth animation along with efficient use of memory
  space.