Shadow Blade
Morrowland Presents Apron Tutorials
game - design - multimedia - web - programming - tutorials - There are currently viewers visiting Apron Tutorials.







  visual basic










  draw sketch


  3d studio


  shadow blade

  game environment

  virtual 3d guide

  billy blue flame


  win32 api





  about us



The Character Animation FAQ 





Q1.  What is character animation?
Q2.  What are skeletons?
Q3.  What are chains and anchors?

Q4.  What are joints?
Q5.  What are revolute joints?
Q6.  What are prismatic joints?
Q7.  What are helical joints?
Q8.  What are cylindrical joints?
Q9.  What are spherical joints?
Q10. What are planar joints?


Q11. How do I define a skeleton?
Q12. How do I move a skeleton?
Q13. How do I constrain a skeleton?
Q14. How do I evaluate a skeleton?


Q15. What are keyframes?
Q16. What is  keyframe animation?
Q17. What is  keyframe Interpolation?
Q18. What is motion capture?
Q19. What are state machines?

Q20. What is digital skin?
Q21. How do I define digital skin?
Q22. How do I evaluate digital skin?
Q23. How do I render digital skin?

Q24. What are expressions?
Q25. What are inverse kinematics?
Q26. How do I implement an IK system?


Q27. How do I render a skeleton as a set of lines?
Q28. How do I render a skeleton as a set of tetrahedrons?
Q29. How do I render a skeleton as a texture-mapped model?


Q30. How do I perform collision detection?
Q31. How do I perform intersection tests between coordinates and a plane?
Q32. How do I perform intersection tests between a line and a sphere?
Q33. How do I perform intersection tests between two spheres?


   Applying a single mesh skin to a skeleton.


Q1.  What is Character Animation?

  Character animation can be defined as the expression of emotion or
  behaviour of a live or inanimate object through the use of motion.
  A good guide to the artistic side of this topic is the book titled
  "Disney's - The Art of Animation".

  There are ten main ways of giving a character expressive behaviour.
  These can be summarised briefly as follows:

  o Squash and Stretch

    The change in shape of a character when a part of its body moves eg.
    head stretching and squashing as a character eats some food.
    Or a character's stomach enlarging and shrinking as he pants after

  o Anticipation

    The positioning of a character before he performs an act eg. making
    his hand reach the sky before digging into his pocket.

  o Staging

    Positioning of the camera, so that the viewer can see what the
    character is doing. This may also include selecting the correct
    background scenery in order to get the message across eg. Standing
    in front of a hot-dog stand while eating a hot-dog which flies across
    the screen when bitten.

  o Straight Ahead Action and Pose to Pose

    Straight Ahead Action simply involves running one animation sequence
    after another without any pre-planning of animation sequences.

    Pose to Pose is exactly the opposite. All the animation sequences are
    planned ahead of time. This allows the camera positions to be planned
    so that everything is in proportion.

  o Follow Through and Overlapping Action

    This involves parts of a character to continue moving from a previous
    animation sequence while the character starts a new sequence.

    eg. A character comes to a sudden stop, while his coat-tails continue
        moving forward.

  o Slow In and Slow Out

    Accelarating and deaccelarating the motion of a character between
    animation sequences.

  o Arcs

    Modelling the motion of every part of a character's body as he moves.
    eg. Making the head bob up and down as the character walks along

  o Secondary Action

    Adding other smaller movements to emphasise any animation sequence eg.
    A character shaking his head after being hit by a falling object.

  o Timing

    The number of frames required to complete a single animation sequence.

  o Exaggeration

    Making the motion of a character more dramatic

  o Solid Drawing

    Making a character appear solid and 3-dimensional. Avoiding "twinning"
    where two limbs of a character will have mirror symmetry.

  o Appeal

    Making a character attract the viewers attention. This includes getting
    the colors right, avoiding clumsy shapes, awkward motion, and distorting
    the shape of the character.

    Other attributes can include the behaviour of the character and the
    manner in which he/she speaks.

Q2.  What are Skeletons?

  To represent the motion of a living creature such as a human, animal or
  arthropod (insect),   it is convenient to store the relationships between
  each movable part of the creature eg. Head is attached to the neck,
  left foot is attached to the lower left leg and so on.

  Taking a cue from biology, each movable part is referred to as a bone,
  the attachments between each bone are called joints and the entire
  collection of bones is referred to as a skeleton.

  The connections between individual bones are referred to as "joints".

  For example, a basic mammal (without fingers or toes) would take around
  20 bones:

    |                                                           |
    |                          o                                |
    |                          | Head                           |
    |        Right.shoulder    |   Left.shoulder                |
    |                  o-------o-------o                        |
    |  Right.upperarm  |       |Upper- | Left.upperarm          |
    |                  |       |back   |                        |
    |                  o       |       o                        |
    |  Right.lowerarm  |       |       | Left.lowerarm          |
    |                  |       oLower- |                        |
    |                  o       |back   o                        |
    |  Right.hand      |       |       | Left.hand              |
    |                          |                                |
    |               Right.butt | Left.butt                      |
    |                       o--o--o                             |
    |                       |     |                             |
    |                       |     |                             |
    |       Right.upperleg  |     | Left.upperleg               |
    |                       |     |                             |
    |                       o     o                             |
    |                       |     |                             |
    |                       |     |                             |
    |       Right.lowerleg  |     | Left.lowerleg               |
    |                       o     o                             |
    |       Right.foot     /     /  Left.foot                   |
    |                                                           |
    |                                                           |

  A hand might be represented with 16 bones as follows:

    |                  thumbend                                      |
    |                o----                                           |
    |               /                                                |
    |    thumbbase /    o---o---o----  ringbase ringmid ringend      |
    |             /     |                                            |
    |            /      o----o----o---- indexbase indexmid indexend  |
    |   o-------o-------o                                            |
    |   lowerarm  palm  o---o---o---  midbase midmid midend          |
    |                   |                                            |
    |                   o--o--o--- littlebase littlemid littleend    |
    |                                                                |
    |                                                                |

  For an anatomically correct skeleton of a human, over 300 bones would
  be required.

Q3.  What are Chains and Anchors?

  "Chains" are a more generic name for skeletons. The latter term really
  only makes sense when applied to living creatures. Other applications
  for inverse kinematics include simulating flexible objects such as
  ropes, string and ship anchor chains.

  Each of these objects can be modelled using a set of single "bones" or

  Taking a cue from nautical terms, the "anchor" or "anchor point" is one
  end of the chain which always has a fixed or known position - much like
  a ships anchor limits the positions that a ship can be in.

    |                         |
    |      +----+             |
    |      |    |             |
    |  o---+----+----o        |
    |  \           O/         |
    |  +|          |          |
    |   o---------o| link1    |
    |              o          |
    |              |          |
    |              | link2    |
    |              o          |
    |              |          |
    |              | link3    |
    |              @          |
    |              Anchor     |
    |                         |

  For animation purposes, each part of the chain has a single object
  attached to it ie. a chain link.


Q4.  What are joints?

  In the field of robotics (or cybernetics), six basic types of joint
  have been defined. These can be summarised as follows:

  | Name               | Symbol | DOF |
  |                    |        |     |
  | Revolute joints    |   R    |  1  |
  |                    |        |     |
  | Prismatic joints   |   P    |  1  |
  |                    |        |     |
  | Helical joints     |   -    |  1  |
  |                    |     ~~ |     |
  | Cylindrical joints | RP  RP |  2  |
  |                    |        |     |
  | Spherical joints   | 3R RRR |  3  |
  |                    |        |     |
  | Planar joints      | RRP    |  3  |

  In the field of character animation, only three types of joint need
  to be considered. These are the "revolute" and "prismatic" joints.
  All other types can be based on these two.

  The symbols "R" annd P" are used when describing combined rotation
  and prismatic joints. The number of symbols liked together indicates
  the number of degrees of freedom.

Q5.  What are revolute joints?

  Revolute joints are the most commonly used joint. The term "revolute"
  comes from the fact that the endpoint of one bone rotates around the
  endpoint of another.
  Revolute joints are represented by the symbol R.

  Because revolute joints only rotate in a single axis, they only have
  one degree of freedom.

  Three types of "revolute" joint exist:

  +----------+    +----------+   +--------------+
  |R1        |    |R2  a     |   |R3   a        |
  |          |    |    .     |   |     .        |
  |          |    |    .     |   |     .        |
  |    @     |    |    @     |   |     .        |
  |    |B    |    |    |B    |   |     .        |
  |    |     |    |    |     |   |     .        |
  |    |     |    |    |     |   |     .  B     |
  | ...o...a |    |    o     |   |     o----@   |
  |    |     |    |    |     |   |     |        |
  |    |     |    |    |     |   |     |        |
  |    |A    |    |    |A    |   |     |A       |
  |    |     |    |    |     |   |     |        |
  | ---O---  |    | ---O---  |   |  ---O---     |
  |          |    |          |   |              |
  +----------+    +----------+   +--------------+

  R1 is the simplest of the three types - it is most comonly known as
  the "simple hinge". Bone B rotates in an axis perpendicular to both
  bone A. The far endpoint of bone B rotates in a circle centred on the
  endpoint of bone B.

  Examples in nature include the human knee and elbow joints.

  R2 differs from R1 in that the rotation axis is parallel to both
  bones B and A. The far endpoint of bone B cannot change location but
  can rotate in place.

  Examples in nature include the human wrist.

  R3 is a variation on R2. While the rotation axis remains the same, bone
  B has been repositioned so that it is perpendicular to bone A. This
  allows for the far endpoint of bone B to rotate in a circle around the
  endpoint of bone A.

Q6.  What are prismatic joints?

  Prismatic joints are joint in which the motion of the bone is purely
  translational. The name "prismatic" is derived from the implementation
  of such joints in industry by using triangular bars (prisms) sliding
  into a matching holder.

  Prismatic joints are represented by the symbol P.

  Because prismatic joints are constrained to move in a single axis,
  only one degree of freedom exists.

  |P   .      |
  |    .      |
  |    .      |
  |    @      |
  |    |      |
  |    |B     |
  |    |      |
  |   +|+     |
  |   |||     |
  |   |o|     |
  |   |.|     |
  |   |.|     |
  |   |.|A    |
  |   o-o     |
  |           |

Q7.  What are helical joints?

  Helical joints combine a rotation motion with a matching translation.
  The main industrial application is in the drive systems for lathes and

  As bone A rotates, bone B experiences a translational movement parallel
  to axis of bone A.

  Because the amount of translation is directly related to the amount of
  rotation, only one degree of freedom exists.

  As a consequence, helical joints are rarely used in the field of

  |H1         |
  |           |
  |           |
  |   @       |
  |   /A      |
  |   \       |
  |   /       |
  |   \  B    |
  |   /o----@ |
  |   \       |
  |   /       |
  |   \       |
  |   /       |
  |   \       |
  |   o       |
  |           |

Q8.  What are cylindrical joints?

  Cylindrical joints combine an coaxial rotation (R3) along with a
  translational movement. Since both movements are independent
  of each other, two degrees of freedom exist.

  Because cylindrical joints are a combination of rotation (R) and
  translation (P), they are represented by the symbol RP.

  If both movements share the same axis, then the symbol RP is used.

  The two types of cylindrical joint are as follows:

  +-----------+       +-----------+
  |           |       |~~         |
  |RP .       |       |RP         |
  |   .       |       |   @.@     |
  |   .       |       |   |.|     |
  |   o       |       |   |o|     |
  |   |       |       |   |||B    |
  |   |       |       |   |||     |
  |  ||| B    |       |   |||     |
  |  ||o----@ |       |   |||     |
  |  |||      |       |   |||     |
  |   |       |       |   o|o     |
  |  A|       |       |    |      |
  |   |       |       |   A|      |
  |   o       |       |    o      |
  |   .       |       |    .      |
  |   .       |       |    .      |
  |   .       |       |    .      |
  |           |       |           |
  +-----------+       +-----------+

Q9.  What are spherical joints?

  Spherical joints implement the "ball-and-socket" concept of a joint,
  where a ball is free to rotate in any direction while being held by
  a socket.

  Since the only way to prevent the ball from popping out of
  the socket is to use a volume slightly larger than a hemisphere, this
  restricts motion in two axii to less than 180 degrees.

  However, the remaining third axis which is parallel to bone B is free
  to move about unrestricted.

  Because it is practically impossible to drive "ball-and-socket"
  mechanisms in the real world, spherical motion is usually implemented
  through the use of three revolute joints.

  Thus, a spherical joint is represented by the symbol 3R or RRR

  |RRR         |
  |            |
  |    ...     |
  |   .   .    |
  |  o     .   |
  | . \B    .  |
  | .  \    .  |
  | .   @   .  |
  |  .  |  .   |
  |   . | .    |
  |    .|.     |
  |     |      |
  |    A|      |
  |     |      |
  |     o      |
  |            |

Q10. What are planar joints?

  Planar joints combine prismatic motion in two axii, along with rotation
  in the axis perpendicular to the other two planes. This can be
  visualised as the motion of a book held flat against a desk.

  Thus, planar joints can be represented by the symbols RRP, RPR or PRR.

  |PRR         |
  |     .      |
  |     .      |
  |     .      |
  |     .      |
  |   +---+    |
  |   |   |    |
  | ..|   |..  |
  |   |   |    |
  |   +---+    |
  |     .      |
  |     .      |
  |     .      |
  |            |


Q11. How do I define a skeleton?

  A skeleton can be defined as an array of bones. Each bone is defined
  in terms of a length, a default direction vector, a name and the name
  of the parent.

  The parent of a bone is the bone which is attached to that bone and will
  cause that bone to move if it moves. eg. If you turn your neck, your
  head will also turn. If you bend your back, your neck and head will also
  both move forwards.

  The only bone which does not have a parent is the root node. It is not
  really a bone in a physical sense but rather it is used as a convenient
  way of moving the entire skeleton with a single translation or rotation.

  So, for the example above, the list would be as follows:

    Bone            Parent            Length        Direction

    Root            ---               -             -  -  -

    Head            Upperback         3             0  1  0
    Upperback       Lowerback         5             0  1  0
    Lowerback       Root              5             0  1  0

    Left.shoulder   Upperback         8             1  0  0
    Left.upperarm   Right.shoulder    3             0 -1  0
    Left.lowerarm   Right.upperarm    3             0 -1  0
    Left.hand       Right.lowerarm    2             0 -1  0

    Right.shoulder  Upperback         8            -1  0  0
    Right.upperarm  Right.shoulder    3             0 -1  0
    Right.lowerarm  Right.upperarm    3             0 -1  0
    Right.hand      Right.lowerarm    2             0 -1  0

    Left.butt       Root              3             1  0  0
    Left.upperleg   Left.butt         5             1  0  0
    Left.lowerleg   Left.upperleg     4             1  0  0
    Left.foot       Left.lowerleg     2             0  0  1

    Right.butt      Root              3            -1  0  0
    Right.upperleg  Right.butt        5             1  0  0
    Right.lowerleg  Right.upperleg    4             1  0  0
    Right.foot      Right.lowerleg    2             0  0  1

Q12. How do I move a skeleton?

  Since each bone has a direction vector and a length, it is possible
  to use rotation matrices to transform each bone to a new position.

  Generation of the rotation matrix can be performed by the mathematical
  concatenation the XYZ rotation matrices or by using quaternions.

  For most applications, translating the position of each bone will not be
  needed.  However, for special effects such as a body being dismembered,
  translation operations can be used.

  Other uses may be for the barrel of a gun which can recoil after
  launching a round of ammunition.

  For other special effects such as pair of extra arms sprouting out of
  nowhere, it can be convenient to set the bone lengths to zero.
  The lengths can then be gradually incremented until they are at
  full length. This is one way of modelling the growth of a tree.

Q13. How do I constrain a skeleton?

  With the skeleton defined above, there is no way of determining
  whether a particular configuration of joints rotations is valid or
  not. For example, the rotation data may have come from external input
  such as a trackball or motion capture sensors.

  In order to ensure that the skeleton is always in a valid position,
  constraints are placed onto the position of each joint.

  The simplest way to implement a constraint based system is to place
  maximum and minimum limits on each rotation and translation axis.

  For example you can twist your thigh sideways around +/- 45 degrees.
  For the model this would correspond to minimum/maximum rotations in
  the Y-axis. Since you cannot detach your leg without some difficulty,
  the constraints for translation are all zero.

  In this case, these would be defined as follows:

    #name          rotation min max        translation min max

    Left.upperleg  0 -45 0   0 45 0        0 0 0      0 0 0

  However, this method requires that the user has to consider and
  visualise the limits of rotation for each joint in the skeleton.

  A more sophisticated method is to classify each type of joint according
  to the type of motion expected. A considerable amount of research in
  this area has been performed in the field of robotics.

Q14. How do I evaluate a skeleton?

  This is fairly easy to perform. Every bone has the following set of
  local information:

    Start-point     - The end attached to the parent
    End-point       - The end where children are attached
    Relative matrix - Matrix generated from local rotation/translation values
    Absolute matrix - Matrix generated from local matrix and parent matrix

  The first stage performed is to evaluate the root node. This will
  involve setting the start-point, end-point and the "relative" (R)
  matrix. Since this is the root node, the "absolute" (A) matrix is
  identical to this.

  The second stage involves the generation of the A-matrix for each
  bone in the model. For each bone in the model, the following steps
  are performed:

    [1] The parent bone is determined. Only if this bone has already
        been evaluated, can the following steps can be performed. The
        ID of the parent bone can be represented either by a name-tag
        or by an index value.

    [2] The end-point of the parent bone is used as the start-point of
        the current bone.

    [3] The R-matrix is calculated (if this has not already been done).

    [4] The R-matrix is combined with the parent's A-matrix to
        generate a new A-matrix.

    [5] The direction vector is combined with the A-matrix to determine
        the current orientation of the bone.

    [6] The current orientation of the bone is added to the start-point
        in order to generate the end-point.

  This process is repeated until all bones have been evaluated.

  Once every bone in the skeleton has been evaluated, the next stage is to
  transform all geometry (polygons, lines, particle systems etc...)
  associated with each bone.

  For each piece of geometry, the associated bone is identified, and the
  following steps are performed:

  For each piece of geometry, the A-matrix is used to rotate the
  coordinates then they are translated by the start-point of the bone.


Q15. What are keyframes?

  As mentioned above, each bone in a skeleton can be assigned a particular
  orientation. In order to represent a particular pose (eg. a single frame
  in a walk cycle), it is necessary to store the rotation/translation values
  for every bone. There are several ways of specifying the keyframe data.
  One way is to store the rotations and translations as vectors eg.

    #rotate    Left.upperleg 0 10  0
    #translate Left.upperleg 0 0.3 0
    #length    Left.upperleg 3

  This method saves space, however it requires the rotation matrix to be
  calculated every time, plus a translation operation.

  Another way is to evaluate and combine the rotation and translation
  operations into a single 4x4 matrix.

    #matrix Left.upperleg

    1 0 0  0
    0 1 0  0.3
    0 0 0  0
    0 0 0  1

  This method avoids having to calculate the rotation matrix every time,
  but it does require the storage of sixteen data values instead of six.

Q16. What is keyframe animation?

  In a method similar to pencil drawn flip-books, keyframe animation
  gives the appearance of motion through the continuous presentation
  of different positions of a character.

  For example, a simple walk cycle may require 8 keyframes. The first
  four frames will have the left leg and right arm swinging forward
  and backwards to rest, then the last four frames will be when the
  right leg and left arm swing forward, and the cycle will continue
  from the beginning again.

Q17. What is keyframe interpolation?

  Unless there are a large number of keyframes, any motion using
  keyframe animation will appear jerky. For example, assuming a
  screen is being updated at 60 frames/second and a character takes
  1 second to complete one walk cycle, then this animation will
  require 60 frames of animation.

  However, there may not be memory space for 60 frames of animation
  (especially for game console systems), so that only 30 or even 15
  frames can be stored.

  The solution to this problem is to perform keyframe interpolation.

  As the name suggests, keyframe interpolation attempts to generate new
  frames by interpolating values between two existing frames.

  To implement this, each keyframe must store the XYZ rotations and
  translations of every bone, regardless of whether it has moved or not.

  The simplest method of interpolation is "linear interpolation". Here,
  the individual values of two frames are combined using a weighting
  function ie.

    Pnew =  Pold[frame] * (1.0-frac) + Pold[frame+1] * frac;

  where Pnew is the new value,
        Pold[frame] is the position for the current frame,
        Pold[frame+1] is the position for the next frame,
    and frac is the fraction of time between the two frames

  This calculation would be performed for each field in the XYZ rotation,
  translation and scaling data.

  More complex motion paths can also be specified - for example, three
  or more frames can be used to implement B-spline interpolation.
  If the frames are not at consecutive intervals of time, Non-Uniform
  Rational B-splines can be used.

  Even more complex methods can use quaternions to interpolate between
  the actual R-matrices.

Q18. What is motion capture?

  There are two ways of generating keyframe data. One way is to get an
  animator, a suitable animation package, and get the animator to add
  the keyframe data to the model.

  For simple actions or for conveying action with exaggerated emotion,
  this is the most efficient way to go.

  However, for animation which requires a large amount of movement (say
  dancers on a stage), then motion capture can be used. There are two
  main methods of motion capture, magnetic and optical.

  In magnetic motion capture systems, a large coil magnet is placed at the
  centre of the stage, magnetic sensors are attached to the actor's body
  and readings are collected by the motion capture software to be
  converted into keyframe data.

  This method has the advantage of generating accurate data, however
  the disadvantages are that the actors are tethered by cables, are
  limited by the operating range of the magnetic coil. There is also the
  problem of callibrating and finding a non-metallic environment. Also,
  the data may require a large amount of signal processing in order to
  smooth out any any background noise that may appear (eg. A/C power

  In order for this type of motion capture to operate successfully, there
  must not be any metallic objects (eg. iron girders, power-cables, tables)
  within the operating range of the system. The most suitable environments
  are either aircraft hangers large warehouses or a farm field.

  In optical motion capture systems, a large number of reflective light
  markers are placed on the actor's body. Using the reflection of studio
  lights, a video camera will capture these reflections, pass the video
  data to a software package capable of converting the screen coordinates
  into three dimensional keyframe data.

  The advantage of this system is that actors are not tethered to any
  location, so long as they remain within visual range of the camera. The
  only disadvantage are that a user may have to callibrate the software
  in order to determine what exactly each point of light represents.

Q19. What are state machines?

  When used with character animation, state machines are a way of managing
  sequences of keyframe animation such that all animation remains smooth
  and continuous ie. there are no occasions where the character "jumps"
  from pose to pose.

  For example, a character in an adventure game may have the following
  actions modelled by keyframe animation:

    o Stationary    (STAT)
    o Start to walk (STWK)
    o Come to stop  (CSTP)
    o Walk          (WALK)
    o Turn left     (TLFT)
    o Turn right    (TRGT)
    o Jump          (JUMP)
    o Fly           (FLY)
    o Land          (LAND)
    o Crouch        (CRCH)
    o Stand up      (STUP)

  In this game, the character can only jump, turn left or right when
  walking. Also, the character can only fly after jumping and may only
  stand up after crouching. Landing is only possible after flying.

  During game development, without the use of state machines will lead to
  more and more code hacking in order to add new states (eg. run, fire,
  pick-up etc...)

  The solution is to use a state machine. First of all, all the possible
  states are drawn as boxes. Then these boxes are joined together by
  arrows which indicate the moves that are possibl.

  Each arrow defines a particular input event that occurs eg. control
  pad buttons pressed, monster-player collision etc...

    |                      +----+                     |
    |                         ^                 | 
    |                         |                       |
    |  +----+     +----+   +----+   |
    |  +----+          |   +----+     ^      +----+   |
    |                  |              |               |
    ^  +----+    |              |      +----+   |
    +<-|TLFT|----<-----+              |--<---|TLFT|<--+ 
    |  +----+          |              |      +----+   |
    |                  v              |               |
    |  +----+   |              |      +----+   |
    |<-|TRGT|----<-----+              +--<---|TRGT|<--+ 
    |  +----+          |                     +----+   |
    |                  |                              |
    |  +----+   +----+ | +----+   +----+     +----+   |
    +--|STUP|<--|CRCH|<+-|LAND|<--|FLY |<----|JUMP|<--+ 
       +----+   +----+   +----+   +----+     +----+

  This information can then be converted into a state table. This defines
  the current states as a column and the events as a row. Each entry
  defines the new state given the current state and incoming event. ie.

    |       |           Input event         |                |
    |Current+---------+------+-------+------+                |
    |state  | FORWARD | LEFT | RIGHT | STOP |                |
    |       |                               |                |
    | STAT  |   STWK    TLFG   TRGT    STAT |                |
    | STWK  |   WALK    WALK   WALK    CSTP |                |
    | WALK  |   WALK    TLFG   TRGT    CSTP |                |
    | CSTP  |   STAT    STAT   STAT    STAT |                |
    | TLFT  |   TLFT    TLFT   TLFT    CSTP |     New states |
    | TRGT  |   TRGT    TLFT   TRGY    CSTP |                |
    | JUMP  |   FLY     FLY    FLY     FLY  |                |
    | FLY   |   LAND    LAND   LAND    LAND |                |
    | LAND  |   CRCH    CRCH   CRCH    CRCH |                |
    | CRCH  |   STUP    STUP   STUP    STUP |                |
    | STUP  |   STAT    STAT   STAT    STAT |                |

  An optional feature is to have an output action associated with each
  state change eg. scheduling an audio scream if a player is killed, a
  coin being collected if a player-object collision is detected.



Q20. What is digital skin?

  Until recently, most character animation has been performed using
  simple geometry primitives eg. boxes, cylinders, spheres or NURBS
  patches, each of which would contain their own unique list of
  polygons and vertices.

  In this simple polgon model of a head, neck and torso, it can be seen
  that the character's neck extends into both the head and torso.
  Using Gouraud or flat-polygon shading with Z-buffering or polygon
  sorting, this is acceptable, since whenever the head is moved, the
  head will always appear attached to both the head and torso.

     Using individual polygon parts
    |                                                    |
    |      +-----+                                       |
    |      |     | Head                                  |
    |      | +-+ |               /- Seams -\             |
    |      +-|-|-+               |         |             |
    |        | |   Neck          v         v             |
    |  +-----|-|-----+  UpperArm              Hand       |
    |  |     | |     |/---------\/--------\/----\        |
    |  |     +-+    /|          /\        /\     \       |
    |  |            \|          \/        \/     /       |
    |  |   Torso     |\---------/\--------/\----/        |
    |                              LowerArm              |
    |                                                    |

  However, when texture-mapping is used, the textures on the neck will
  appear to sink into both the head and torso. Also, there is the problem
  of seams appearing between the different body parts whenever the
  character moves around.

  The solution is to use a technique known as digital skin. In the model
  above, each body part would be defined as a list of vertices and polygons.

  With digital skin, each body part still retains its own list of vertices.
  However, there is now a single global list of polygons. Polygons can now
  be defined which share vertices between different body parts (These are
  referred to as "glue" polygons. The following figure demonstrates this:

    |                                                    |
    |      +-----+                  Glue                 |
    |      |     | Head             Polygons             |
    |      |     |               /-       -\             |
    |      +-+-+-+               |         |             |
    |        | |   Neck          v         v             |
    |  +-----+-+-----+  UpperArm              Hand       |
    |  |             +-+-------+--+------+--+----\       |
    |  |             | |       |  |      |  |     \      |
    |  |             | |       |  |      |  |     /      |
    |  |   Torso     +-+-------+--+------+--+----/       |
    |  |             |^          ^           ^           |
    |                 |          |           |           |
    |                      Glue polygons                 |
    |                                                    |

  As the character moves a body part (say, twists an arm), then the "glue"
  polygons will stretch and contract between the two parts and give the
  appearance of skin.

  A more sophisticated use of digital skin is to make muscles appear to
  bulge whenever a joint is bent.


Q21. How do I define Digital Skin?

  Models which use digital skin are still defined in terms of polygons
  and vertices. However, as mentioned before, there is only a single
  polygon list, rather than individual lists for each bone in the skeleton.

  Vertices are defined in terms of XYZ coordinates.

  Polygons are defined in terms of their vertices (typically vertex ID's)
  and any other data eg. texture vertex ID's, outward normals

Q22. How do I evaluate Digital Skin?

  For most purposes, the only calculations required will be to calculate
  the new locations of each vertex based on the rotation matrix of the
  current bone.

  However, in order to implement more realistic effects such as bulging
  muscles, then it quite possible to use Expressions to determine the
  new position of a vertex.

  The method works as follows:

    [1] The rotation angle of the selected joint is read.

    [2] This value is translated using a cubic equation to determine
        the scale factor for the vertex.

    [3] This scale vactor is then used to adjust the position of the
        selected vertices.

Q23. How do I render digital skin?

  The digital skin can be rendered as any other type of polygon surface,
  mesh or NURBS Patch, and so no special calculations are required.


Q24. What are Expressions?

  In many animation scenes, it is often required that one or more 3D
  models are synchronised in the way they move. For example, consider
  the animation of a car gearbox with 15 or more gears. Using keyframes,
  this would require the animator to calculate and specify the position
  of all 15 gears per frame.

  Apart from running the risk of getting some of the calculations wrong,
  this also wastes time and memory space.

  An alternative method is to use arithmetic expressions (or "expressions"
  for short) to evaluate the movement of each gear. This method requires
  that arithmetic relationships between two moving objects are defined.

  Arithmetic expressions can include variables, constant values (eg. PI),
  trigonometric functions (eg. sin cos tan sqrt log exp ...)

  In the following model, A and B are two gears, each with radius
  Ra and Rb. C is a rack which moves up and down according to B
  (similar to car steering).

    |                              |
    |     A     | |      Y         |
    |    ---  B | |      |         |
    |   /   \/-\|C|      |         |
    |   | o ||o|| |      |         |
    |   \   /\-/| |      /---- X   |
    |    ---    | |     /          |
    |                  / Z         |
    |   | Ra||Rb|                  |
    |                              |

  Gear A is rotating at 10 degrees/frame. Gear B intersects Gear A.

  So the expressions for this system would be:


    radius_a = 10                # Define constants
    radius_b = 8
    pi       = 3.14159265

    gear_a.rotate_z = frameid    # Get frame ID

                                 # Calculate position of gear B
    gear_b.rotate_z = -(radius_a / radius_b) * gear_a.rotate_z

    rack_c.trans_y = -gear_b.rotate_z * 2 * pi


Q25. What are Inverse Kinematics?

  In the examples given above, it has always been assumed that the
  rotation angles and translation vectors for each bone are already
  known and only the end-points and rotation matrices for each bone
  have to be calculated.

  With inverse kinematics (or IK for short), only a limited set of
  endpoints and translation values are known, along with the set of
  constraints defining the freedom of movement of the skeleton. Other
  constraints that are known include the motion paths for each joint.

  For example, with motion capture, sensors will provide continuous
  data which will be interpolated into NURBS curves. For any instant
  of time, these will be translated into the endpoints of each bone
  in the skeleton. From these values, direction vectors can be
  generated for each bone.

  Once the direction vectors are known, rotation matrices for vertex
  data can be determined. These can then be used to transform the
  geometry of the model.

Q26. How do I implement an IK system?

  With IK systems, the goal is to determine the values of all unknown
  variables in the skeleton. As mentioned before, each bone data
  structure contains several pieces of data:

    | Name                  | Acronym  |    C flag     |
    | Euler rotation angles | RA       |   IK_ANGLES   |
    | Rotation matrix       | RM       |   IK_MATRIX   |
    | Start Point           | SP       |   IK_START    |
    | End   Points          | EP       |   IK_END      |
    | Translation           | TR       |               |
    | Direction vector      | DIR      |               |
    | Length                | LEN      |               |
    | ID of parent bone     |          |               |
    | Flag list             |          |               |

  The flag list contains a set of bit-values associated with each of the
  first four parameters (RA), (RM), (SP) and (EP). For each value which
  is known the appropriate flag bit is set.

  Since each of these values are related mathematically, data can be
  propagated both forwards and backwards.

  If the end-point of a parent bone is known, then the start-point of any
  child-bone is also known.  This is forward propagation.

  Similarly, if the start-point of a child bone is known, then the
  end-point of the parent is also known. This is backward propagation.

  If the start-point of the parent bone is known, and the end-point of
  the child bone is known, the location of the intermediate joint
  (end-point of the parent or start-point of the child) can also be

  Altogether, there are around 12+ rules which can be used to propagate
  data both backwards and forwards. These are as follows:

  |Rule  | Unknown |   Parent bone   |     Current bone            | Path   |
  |  #   | var.    | PSP | PRM | PEP | TR  | SP  | RA  | RM  | EP  | Vec PV |
  |  1 * | SP      | /// | ... | ### | ### | ??? | ... | ... | ... | ...    |
  |  2   | TR      | /// | ... | ### | ??? | ### | ... | ... | ... | ...    |
  |  3 % | EP      | ... | ... | ??? | ### | ### | ... | ... | ... | ...    |
  |  4 * | RM      | ... | ### | ... | ... | ... | ### | ??? | ... | ...    |
  |  5   | RA      | ... | ### | ... | ... | ... | ??? | ### | ... | ...    |
  |  6   | PRM     | ... | ??? | ... | ... | ... | ### | ### | ... | ...    |
  |  7 * | EP      | ... | ... | ... | ... | ### | ... | ### | ??? | ...    |
  |  8 % | RM      | ... | ### | ... | ... | ### | ... | ??? | ### | ...    |
  |  9   | SP      | ... | ... | ... | ... | ??? | ... | ### | ### | ...    |
  | 10   | EP      | ... | ... | ... | ... | ### | ... | ... | ??? | ###    |
  | 11   | PEP     | ### | ... | ??? | ... | ... | ... | ... | ... | ###    |
  | 12 % | PEP     | ### | ... | ??? | ... | ... | ... | ... | ### | ...    |

  ... - Not needed
  /// - Need not be known in certain cases
  ### - Known variable
  ??? - Unknown variable

    * - Standard character animation
    % - Can be used to implement motion capture

  It should be noted that Expressions can also be used by IK systems. In
  this case, the left hand side of the equation would be regarded as the
  unknown variable and any variables on the right hand side as known

  The operation of the IK system is fairly straightforward, and can be
  defined by the following sequence of actions:

  For each animation_frame do

    Mark all variables as unknown
    Set known variables and bit-flags
    Set progress_made flag

    While unknown_variables_exist and progress_made do
      Clear progress_made flag
      For each bone do
        For each rule do
          If LHS variable is unknown and
             all RHS variables are known then
            Evaluate_rule( rule, bone )
            Mark variable as known
            set progress_made flag
    Endwhile /* unknown_variables_exist */

  Endfor /* animation_frame */

  In certain situations, it may be impossible to find the values of some
  unknown variables. To detect this situation, it is necessary to maintain
  a progress made flag, which is set whenever the value of an unknown
  variable is determined. If no unknown variables can be determined then
  execution of the main loop is terminated, and the IK system returns the
  values of those variables which could be determined.

  Each of the above rules can be implemented using simple vector and matrix
  mathematics. A list of rules using the 3D API is as follows:

    Rule #

     1.  v3_sub( SP,  PEP, TR  )

     2.  v3_sub( TR,  SP,  PEP )

     3.  v3_sub( PEP, SP,  TR  )

     4.  m3_rotatexyz( m1, RA )
         m3_mult(      RM, PRM, m1 )

     5.  m3_transpose( m1, PRM )
         m3_mult     ( m2, m1, RM )
         m3_toeuler(   m2, RA )

     6.  m3_rotatexyz( m1, RA )
         m3_transpose( m2, m1 )
         m3_mult(      PRM, RM, m1 )

     7.  m3_multvector( RM, v1, DIR, 1 )
         v3_scalef(     v1, v1, LEN )
         v3_add(        EP, v1, SP )

     8.  findmatrix( RM, SP, EP )
         m3_toeuler(    RM, RA )

     9.  m3_multvector( MR, v1, DIR, 1 )
         v3_scalef(     v1, v1, LEN )
         v3_sub(        SP, EP, v1 )

     10. v3_sub( v1, PATHMAX, PATHMIN )
         v3_normalise( v1, v1 )
         v3_scale(     v1, v1, LEN )
         v3_add(       EP, SP, v1 )

     11. intersect sphere with line

     12. intersect sphere with sphere

  findmatrix - Function to determine the rotation matrix between the
               direction vector and the new position of a bone

    m3_multvector( PRM, v1, DIR )
    v3_sub( v2, PEP, SP )
    v3_normalise( v2, v2 )

    v3_cross( v3, v1, v2 )
    v3_norm( v3, v3 )

    lrot = v3_dot( v1, v2 )
    lrot = acos( lrot ) * RADIANS

    m3_fromquat(  RM, v3, lrot );
    m3_transpose( m1, RM )
    m3_mult(      m1, RM, PRM )
    m3_copy(      RM, m2 )


Q27. How do I render a skeleton as a set of lines?

  This is simplest and quickest way of rendering a skeleton.
  It is achieved simply by drawing a line from the start point to the
  end point of each bone.

  Joints can be highlighted by drawing circles at each joint.

Q28. How do I render a skeleton as a set of tetrahedrons?

  While drawing a skeleton as a series of lines is fast, it does not
  provide a clear view of the way in which each limb is moving.

  An alternative way is to represent each bone as an elongated
  tetrahedron. The base of the tetrahedron is placed at the start of
  the bone. The elongated end of the tetrahedron is positioned at the
  end of the bone.

  The coordinates of the tetrahedron can be stored as a single 4x4 matrix
  and scaled according to the dimensions of the bone.

  A unit tetrahedron has the following coordinates:

    |  0.000  0.353553   -0.176776   -0.176776  |
    |  0.000  0.000000    0.306186   -3.306186  |
    |  1.000  0.000000   -0.000000    0.000000  |

  with one end-point stored at (0,0,1). This coordinate will be scaled
  according to the length of the bone.

  To ensure that the tetrahedron rotates along with the model, each bone
  has an initial direction vector.

  Since the tetrahedron has a direction vector of ( 0,0,1 ), the base
  rotation matrix is derived from the matrix which rotates the direction
  vector of the tetrahedron to the direction vector of the bone.

  As the bone is rotated through keyframe animation or inverse kinematics
  the current rotation matrix of the bone is multiplied with the base
  rotation matrix. Applying this matrix to the vertices of the tetrahedron.

  The resulting set of vertices are used to render the tetrahedron.

  The tetrahedron can be rendered in wireframe, shaded or even texture
  mapped modes.

Q29. How do I render a skeleton as a texture mapped model?

See Q23. Rendering digital skin


Q30. How do I perform Collision Detection?

  This really depends on what kind of objects are colliding. For example,
  you may be attempting to determine whether a missile has collided with a
  character or whether the player has attempted to walk through a wall
  or has set off a trip-wire.

  The most commonly used collision detection methods are as follows:

    o Coordinate/Plane intersection test

      used for: trip-wire tests, character/wall collision, door activation

    o Sphere/Sphere intersection test

      used for: object pickup, character/character collision

    o Parametric line/Sphere intersection test

      used for: missile trajectory hits

Q31. How do I perform intersection tests between coordinates and a plane?

  For flat objects such as trip-fires or doors, plane-collision tests
  can be performed.

  A plane is defined by the equation:

    P = A.x + B.y + C.z + D

  where the constants A,B,C and D define the equation of the plane and
  (x,y,z) is a coordinate in Euclidean space.

  This calculation can also be considered to be a dot product between
  two homogenous coordinates.

  All points in front of the plane will generate positive value.
  All points behind the plane will generate negative values.
  All points which lie exactly on the plane will generate a value of zero.

  As a player or object moves around in world space, the current position
  is saved and the new position is calculated.

  For each new position, the new value of the plane equation is calculated.
  If the result changes sign, then a collision has occured.

  The point of intersection can be determined by the algorithm:

    ro = P . oldpos

    rn = P . newpos

  Then the point of intersection is given by:

            ro             rn
    Pi = --------- Po + ---------- Pn
         (rn - ro)      (rn - ro )

  This can be rearranged to give:

         ro.Po + rn.Pn
    Pi = -------------
           (rn - ro)

  where Po is the first point,
        Pn is the second point,
        ro is the evaluated plane equation for Po
        rn is the evaluated plane equation for Pn and
        Pi is the interpolated point

Q32. How do I perform intersection tests between a line and a sphere?

  For all cases, it is convenient to define a bounding sphere for the
  character. This allows for a simple distance check to determine
  whether a collision is likely to happen or not.

  The equation can be defined as follows:

                 2            2            2    2
    V = (Xp - Xm)  + (Yp - Ym)  + (Zp - Zm)  - R

  where (Xp,Yp,Zp) are the coordinates of the player,
        (Xm,Ym,Zm) are the coordinates of the missile  and
        R is the radius of the boundary sphere

  If V is less than zero, a "hit" has occurred, otherwise it is a "miss".

  If the missile is travelling so fast, as to appear instantaneous eg. high
  velocity rifle, then you are better off performing a line-sphere
  intersection test. In this case the trajectory of the missile is
  determined by a line equation:

    Pt = Ps + t . Pd

  Where Pt is the location of the missile at time t
        Ps is the initial location of the missile and
         t is the time

  This is substituted into the sphere equation above:

                 2            2            2    2
    V = (Xp - Xm)  + (Yp - Ym)  + (Zp - Zm)  - R

  Evaluating out, this forms a quadratic equation with the terms:

    A.t  + B.t + C = 0

  with the values of P, Q and R:

    A = Pdx + Pdy + Pdz

    B = -2.Xp.Pdx - 2.Yp.Pdy - 2.Zp.Pdz - 2.Psx.Pdx - 2.Psy.Pdy - 2.Psz.Pdz

          2     2     2                                     2
    C = Xp  + Yp  + Zp  - 2.Xp.Psx - 2.Yp.Psy - 2.Zp.Psz - R

  The roots of this quadratic equation define the values of the
  parametric variable t where the line intersects the sphere.

  The number of roots can be determined by calculated the "discriminant"
  D where:

    D = B  - 4AC

  If D is less than zero, no roots exist.
  If D is equal to zero, then one root exists.
  IF D is greater than zero, then two roots exist.

Q33. How do I perform intersection tests between two spheres?

  Given two spheres with Radii Ra and Rb and center points Pa and Pb, then
  the following test can be performed:

    D = | Pb - Pa | - Ra - Rb

  where D is the resulting test value.

  If D is less than zero, the spheres intersect
  If D is equal to zero, then the spheres just touch each other.
  If D is greater than zero, then the spheres do not intersect.

  The plane of intersection can be calculated as follows:

  The outward normal is the normalised direction vector of Pa to Pb.
    Pn = Pb - Pa

  This is equivalent to the values of A, B and C in the standard plane

  The point of intersection is derived by:

    Pi = Pa +  ------- . N

  The constant term of the plane equation can be evaluated by taking the
  negative dot product ie.

    D = -N.Pi


Q34. What are Flocks and Swarms?

  When animating animals, birds and insects, it is often required that
  two or more creatures are required to interact with each other. For
  example, a flock of geese will typically form a ^ formation when
  flying South or a swarm of bees will fly in a cluster towards a
  specific target.

  This behaviour can be modelled by a special kind of particle system
  (often referred to as Flocks). With traditional particle systems the
  motion of each particle is governed solely by the laws of Physics eg.
  gravity, velocity, wind, air-friction etc... No decision making ability
  is given to individual particles.

  Flocks attempt to give the particle system the appearance of cognitive
  thought, by allowing each particle to make decisions based on its
  position in the environment and relative to other particles.

  Certain constraints can be applied to the system. These include speed
  limits on velocity and accelaration. They may even include contraining
  the amount of angular vision on a particle ie. modelling the inability
  to see directly behind itself. This is required for modelling geese and
  insects. (Out of scientific curiosity, it is noted that Rabbits have 360
  degree vision).

  Usually, each particle will also be assigned a preferred distance from
  other particle. This is implemented using spherical force fields.

  For each particle, the distance to every other particle is determined
  using simple geometry. This value is then scaled using the inverse-square
  law and used to determine the resulting acceleration vector. These vectors
  are accumulated and used to move the particle. A maximum distance limit
  is usually set to discount particles that are far away.

  If two particles are closed together, they will attempt to move apart. If
  they are too far away, they will attempt to move together.

  To implement line-of-sight, the angular direction or direction vector is
  also determined. Using a suitable acceptance function eg. dot product or
  maximum/minimum limits, the visibility of other particles can be determined.
  If "out of sight", then these particles are ignored.

  To allow closer particles to obscure other further-away particles, only
  the nearest 3 or more particles need be considered to generate the
  acceleration vector.

  Particle may also be required to interect with an environment. In that
  case, collision detection and force fields may be implemented as
  described in 19].

Q35. What is Facial Animation?

  In the same way that Character Animation attempts to give life to
  inanimate objects, character animation attempts to bring to life a
  model of a face or an object which resembles a face.

  For example, the front of a car can be made to look like a face; the
  headlights are it's eyes, and the radiator is it's mouth.

  Another example is a stero system; the large speakers to each side are
  it's eyes and the buttons at the bottom are it's teeth/mouth.

  One way to implement facial animation is to model the way muscles move.
  With any living creature, movement of the skin surface is generated by
  movement of muscles underneath.

  Each patch of skin can be stretched by at least one or more muscles.
  However, while each muscle can only pull in one direction when it
  contracts, two or more muscles may be combined simultaneously to
  generate a new stretch direction.

  To represent this system using 3D mathematics, patches of skin are
  represented by 3D vertices, rendered either using NURBS or polygons.

  Each muscle is represented as a weighting factor from 0.0 (relaxed) to
  1.0 (fully contracted).

  Every vertex which is attached to that muscle has a cubic spline function
  weighted to model the way in which the skin is stretched. When the muscle
  contracts, the verex is displaced in a particular direction path.
  Since the polygonal geometry remains the same, the face produces a
  recognisable expression.

  Grouping together muscle movements develops various expressions eg.
  smiling grinning, surprise, frown, anger etc...

Q36. What is a good 3D mathematics library to build?

  If you are starting out in 3D and would like to experiment with vectors,
  matrices, outward normals and polygons, then you will need data structures
  to represent these. The first decision you will need to make is whether to
  use homogenous matrices (4x4) or standard (3x3) matrices.

  For most game applications 3x3 matrices require less calculations (ie. no
  need to maintain the W coordinate).

  For further details, see the Vectors and Matrices FAQ.


Thanks to Hexapod.


  morrowland home






  shadow blade

  game environment

  virtual 3d guide

  billy blue flame





  All rights reserved Morrowland © 2017  
Ronny André Reierstad