INVERSE KINEMATICS AND GEOMETRIC CONSTRAINTS FOR ARTICULATED FIGURE MANIPULATION
by
Chris Welman
BSc Simon Fraser University
a thesis of the
submitted in partial fulfillment requirements for the degree of
Master of Science in the Scho ol
of Computing Science
All
repro duced
or other means
reserved This in whole or in
work may not b e part by photo copy
c Chris Welman SIMON FRASER UNIVERSITY Septemb er
rights
without the p ermission of the author
Name
Degree
Title of
Examining
APPROVAL
Chris Welman Master of Science
Inverse Kinematics and Geometric Constraints for Articulated Fig ure Manipulation
Dr L Hafer Chair
Dr TW Calvert Senior Sup ervisor
Dr J Dill
Dr D Forsey External Examiner
thesis
Committee
Date Approved
ii
Abstract
Computer animation of articulated gures can b e tedious largely due to the amount of data which must b e sp ecied at each frame Animation techniques range from simple interp olation b etween keyframed gure p oses to higherlevel algorithmic mo dels of sp ecic movement patterns The former provides the animator with complete control over the movement whereas the latter may provide only limited control via some highlevel parameters incorp orated into the mo del Inverse kinematic techniques adopted from the rob otics literature have the p otential to relieve the animator of detailed
sp ecication of every motion parameter within a gure while retaining complete control movement if desired
over the
This work investigates the use of inverse kinematics and simple geometric constraints as to ols for the animator Previous applications of inverse kinematic algorithms to computer animation are reviewed A pair of alternative algorithms suitable for a direct manipulation interface are presented and qualitatively compared Application of these algorithms to enforce simple geometric constraints on a gure during interactive manipulation is discussed An implementation of one of these algo rithms within an existing gure animation editor is describ ed which provides constrained inverse kinematic gure manipulation for the creation of keyframes
Contents
Intro duction Organization
Approaches to Figure Animation
BodyModels Scope
Skeleton Mo delling
Kinematic Methods
Forward Kinematics
Inverse Kinematics
Dynamic Methods
Forward Dynamics
Inverse Dynamics
ControlIssues
Summary
Evaluation ApplicationstoComputerGraphics
Ecient Algorithms for Direct Manipulation ASimpliedDynamicModel
Inverse Kinematics
The Inverse Kinematic Problem
Resolved Motion Rate Control
Redundancy
Singularities OptimizationBased Metho ds
The Jacobian Transpose Method
i
CONTENTS
ii
ImplementationDetails
ComputingtheJacobian
ScalingConsiderations
Integration
JointLimits A Complementary Heuristic Approach
The CyclicCoordinate Descent Method
Overview Comparison
Incorp orating Constraints
ConstraintSatisfaction
MaintainingConstraints
TheConstraintCondition
ComputingtheConstraintJacobianMatrix
ComputingtheConstraintForce
SolvingforLagrangeMultipliers
Feedback
Overview
Implementation Issues
Skeletons as Ob jects
Handles on Skeletons
Constraints on Handles
The Global Picture
Summary
A CCDbased Penalty Metho d
Skeletons
An
ASystemOverview
Interactive Editor
The Sequence
The Editor
Direct Manipulation
Constraints
Conclusion Summary Results
CONTENTS iii
Comments about Constraints Directions
Bibliography
List of Figures
a ob jects dened in lo cal co ordinate systems b Lo cal
rotations
applied
Localtranslationsapplied
Three congurations of a D redundant manipulator
A manipulator in a singular conguration
Interactive control lo op mo del for Jacobian transp ose
A case not handled well with the Jacobian transp ose metho d
cd
on the
tip of the manipulator on the left will not pro duce an exp ected conguration like the
oneshownontheright
ExampleCCDiterationstepforrotationjointi
A force applied to a point constrained to lie within a plane A constraining force normal to the plane is added to the applied force to obtain a legal force tangential to
theplane
Iteration steps for maintaining constraints
Agenericfunctionblock
Examplenetwork
A branching chain with two endeector constraints
Sampleskeletondescription
Sequenceeditorscreen
Plan view of goal determination in a an orthographic view
view
A gure b eing p ositioned by rst tilting then twisting the p elvis
a First keyframe p ose b Interp olated p ose c Second keyframe p ose
iv
metho d
Pulling inwards
p ersp ective
and b a
Chapter
Intro duction
Computer graphics has advanced to a p oint where generating images of striking realism and com plexity has become almost commonplace However making ob jects move convincingly within these pictures remains dicult particularly as ob ject models grow increasingly complex The specication and control of motion for computer animation has emerged as one of the principal areas of research within the computer graphics community
One area in particular which continues to receive attention is that of gure animation The goal of work in this area is to provide a means of generating lifelike p ossibly humanlike articulated gures and to design and control their actions within simulated environments Animated human gures could for example b e placed in simulated environments for ergonomic evaluation or simply to provide some aesthetic qualities to a presentation In the arts and entertainment area the concept of computergenerated characters roaming through articial worlds seems universally app ealing
Although gure animation raises technical challenges in b oth mo delling and rendering the fun damental problem of designing and controlling movement for these gures remains a particularly dicult one Part of the problem lies in deciding from which level of detail to approach the task
At one end of the scale the movements of individual parts of the b o dy
instant in time At the other end of the scale co ordinating movements
b etween gures and with the environment may require algorithms based on b ehavioural rules and knowledge bases Many of the most impressive examples of gure animation by computer have b een the result of algorithms implementing highlevel b ehavioural and motor control mo dels However these algorithms are often limited to generating sp ecic usually rep etitive movement patterns such as walking and running For the animator who wishes to create new movements there is little al ternative to painstakingly constructing the movement by hand Given the complex structure of a typical articulated gure this can involve an inordinate amount of work
must b e known for each and handling interaction
CHAPTER INTRODUCTION
The motivation b ehind this work is a desire to improve the animation capabilities of an existing interactive articulated gure animation package which is currently used to create movements for b oth dance and animation It is shown how inverse kinematic techniques for controlling rob otic manipulators can b e adopted to relieve the animator of some of the more tedious asp ects of creating new movements by hand After reviewing the inverse kinematic problem and solutions that have previously b een applied to gure animation a pair of alternative solution algorithms are presented and qualitatively compared These algorithms are simple yet eective and can supp ort b oth direct manipulation of articulated gures as well as the imp osition of simple geometric constraints up on a gure Implementations of these algorithms are presented and are applied to develop a basic set of interactive to ols for gure manipulation and animation
Organization
Chapter reviews computer animation techniques in general and discusses their applicability in the context of gure animation In Chapter the inverse kinematic problem is stated and com mon approaches to solving the problem are reviewed In Chapter a pair of fast reliable inverse kinematic algorithms are describ ed suitable for interactive manipulation tasks and diering from previous algorithms adopted for computer graphics In Chapter pro cedures for satisfying simple geometric constraints using these algorithms are considered Chapter intro duces an interactive gure animation editor and discusses implementation of the algorithms as p ositioning aids
Chapter
Approaches to Figure Animation
Placing this work in context requires some understanding of computer animation techniques in general and of how they may b e applied to gure animation in particular This chapter provides an overview of the advantages and disadvantages of basic motion control techniques for gure animation
The emphasis here is on metho ds to create and control the movements of articulated gures
rather than simply replaying digitized
itizing or rotoscoping the movements
convincing lifelike motion Rotoscoping can
graphic images to prerecorded video fo otage to attaching some
b o dy whose p ositions can b e tracked by computer and stored for later playback Neither of these are particularly attractive options the former b eing quite tedious and the latter relying on the availability of reliable unobtrusive instrumentation for the b o dy and sophisticated software to re construct the original motion from the sensor data neither of which are readily available yet A further limitation of rotoscoping is that a gure animated in this way is limited to those movements actually p erformed by a live sub ject Computer animation techniques can b e applied to animate gures in situations for which rotoscoping is neither a viable nor practical solution
Bo dy Mo dels
Scop e
First we must decide exactly what we are trying to animate Although the ideal computergenerated character would include muscle and tissue that deforms during movement skin and clothing that wrinkles and stretches hair that ows and expressive facial features the accurate mo delling ani mation and rendering of these attributes are research topics in their own right and work in these
movement It is
of real
fair to say that for many pro ductions dig remains the method of choice for obtaining
subjects
refer to techniques
ranging from visually matching sort of sensors to a p erformers
areas is still at the exp erimental stage For the time b eing we
animating simple approximations to real b o dies It is useful to
as a skeletal layer up on which muscle tissue and skin can later
is that any b o dy mo del can b e animated by moving an underlying skeletal approximation which need not b ear any resemblance to the nal rendered app earance of the character Thus the motion control problem for gures reduces to that of controlling the movement of an abstract articulated skeleton
Skeleton Mo delling
A skeleton can b e represented by a collection of simple rigid ob jects connected together by joints The joints are usually rotational but may also b e sliding or prismatic Each rotary joint may allow rotation in or orthogonal directions these are the degrees of freedom DOF of the joint A detailed approximation to the human skeleton may have as many as degrees of freedom although often fewer suce Restrictions on the allowable range of movements for a joint can b e approximated by limiting the rotation angle in each of the rotation directions at each joint
The individual ob jects comprising the skeleton are each dened in their own local coordinate
CHAPTER APPROACHES TO FIGURE ANIMATION
systems and are assembled into a
nested series of transformations In Figure a simple articulated limb is built up by applying lo cal rotations and translations to blo cks dened in their own lo cal co ordinate systems
More complex skeletons can b e built up by arranging the segments in a treestructured hierarchy Each no de in the tree maintains the rotations currently in eect at the corresp onding joint these joint rotations are osets from the orientation of the parent segment in the tree These nested transformations in the hierarchy ensure that segments inherit the rotations applied to joints higher in the tree a rotation applied at say the shoulder joint causes the entire arm to rotate and not just the upp er arm segment One joint in the skeleton needs to b e sp ecied as the ro ot of the tree
will have to restrict our attention to think of these simple approximations b e layered The imp ortant p oint here
recognizable gure in a global world co ordinate system by a
transformations applied to this
choice of which joint is to serve
an existing hierarchy around a new ro ot joint at any time The global transformations applied to any particular ob ject within the skeleton can be computed by traversing the hierarchy from the root to the segment and concatenating the lo cal transformations at each joint visited by the traversal
Most animation systems provide a means of building up the transformation hierarchy needed to dene a skeleton and it is easy enough to dene a simple grammar for sp ecifying skeletons Zelb Sims SZ has describ ed an interactive editor for designing new skeletons which applies some simple heuristics to streamline the pro cess Regardless of how it is created a skeleton denition will
joint move the entire skeleton in the world co ordinate system The as the ro ot is irrelevant and it is convenient to b e able to restructure
CHAPTER APPROACHES TO FIGURE ANIMATION
(a)
(b)
(c)
(d)
Figure a ob jects dened in lo cal co ordinate systems b Lo cal rotations applied cd Lo cal translations applied
minimally sp ecify the individual b o dy segment lengths the joint degrees of freedom and the overall hierarchy of the structure
A skeleton can b e animated by varying the lo cal rotations applied at each joint over time as well as the global translation applied at the ro ot joint The motion sp ecication and control problem is that of managing the way in which these transformations change over time In general there are two fundamental approaches to this problem kinematic and dynamic The following sections review b oth kinematic and dynamic metho ds for motion sp ecication in general the typ es of control available for each and applications of these to gure animation in particular
Kinematic Metho ds
Forward Kinematics
Forward kinematics involves explicitly setting the p osition and orientation of ob jects at sp ecic frame
times For skeletons this means directly setting the rotations
global translation applied to the ro ot joint to create a pose
of an animation a series of keyframe p oses can b e sp ecied at dierent frames with intermediate
at selected joints and p ossibly the To avoid doing this for each frame
CHAPTER APPROACHES TO FIGURE ANIMATION
p oses calculated
b e animated by displaying each intermediate p ose
by interp olating the joint parameters b etween the keyframes The gure can then
While linear
mediate p oses the resulting motion is usually unsatisfactory Discontinuous rst derivatives
inter in the use of
Interp olation often pro duces intermediate values that do not quite meet the animators requirements some control over the interp olation pro cess is crucial Las The interp olated values for a single DOF over the course of an animation form a trajectory curve which usually passes through the keyframe values The shap e of the tra jectory and hence the motion of the ob ject is dep endant on b oth the keyframed values and the typ e of interp olating spline used An interactive editor which
allows the
tra jectory
which the tra jectory
proposed which provide varying degrees of control over both the shape of a tra jectory and variations in sp eed along the tra jectory
Ko chanek KB describ es an interp olation technique based on a generalized form of piecewise cubic Hermite splines Three parameters continuity tension and bias are provided to control the length and direction of vectors tangent to the tra jectory at the keyframes Mo difying the direction of the tangent vectors gives lo cal control over the shap e of the curve as it passes through a keyframe Changing the length of the tangent vectors aects the rate of change of the interp olated value around the keyframe and thus provides some control over sp eed Some traditional animation eects such as action fol lowthrough and exaggeration Las can be achieved with appropriate settings of these parameters Unfortunately since all three parameters in the spline formulation aect the shap e of the curve the metho d provides no means for mo difying sp eed along a tra jectory without mo difying the tra jectory itself
Steketee and Badler SB advo cate a doubleinterp olant metho d which do es separate timing control from the tra jectory itself As b efore a tra jectory is dened as a piecewise cubic spline passing through a series of keyframed values An additional spline curve is also intro duced to control the
interp olation b etween keyframes is the simplest metho d for generating these
interp olated
higherorder
acceleration
p olation is well established Ste Gom HS Sho Stu and is invariably provided in commercial animation systems
Controlling interp olation
joint angles at the keyframes lend a jerky rob otic quality to the motion The
interp olation metho ds such as and hence smo other transitions
piecewise splines can provide continuous velo city and b etween and through the keyframes Keyframe inter
animator
is dened the quality of the movement can be further modied by varying the rate at
to view and mo dify the shap e of a tra jectory can b e a useful to ol Once a
is traversed A numb er of parameterized interp olation metho ds
have b een
CHAPTER APPROACHES TO FIGURE ANIMATION
parameter with which the tra jectory curve is sampled This provides control over the parametric sp eed at which the tra jectory curve is traversed However there is often no meaningful relationship b etween parametric sp eed and actual sp eed in the geometric sense sampling a curve at uniformly spaced parametric p oints will not necessarily yield uniformly spaced p oints in space This approach to timing adjustment therefore is somewhat ad hoc and nonintuitive requiring a trialanderror pro cess on the part of the animator to achieve the desired velo city prole along the tra jectory
More intuitive control over sp eed along a tra jectory can b e obtained by reparameterizing the tra jectory curve by arclength Arclength parameterization provides a direct relationship between parametric sp eed and geometric sp eed along a tra jectory the distance d travelled along a tra jectory is proportional to the increment s of the tra jectorys arclength parameter s Allowing the animator to sketch a curve representing s over time provides an intuitive mechanism for varying sp eed along the tra jectory BH However although theoretically a reparameterization by arclength exists for any curve it is often not p ossible to nd an analytic solution for arbitrary curves and one must resort to numerical approximation metho ds Gir GP
Evaluation
Keyframebased computer animation has a direct analogy in traditional animation where key ani mation cels are drawn by senior animators while less exp erienced animators draw the action in the intermediate cels Computerbased keyframing is intuitive and the interp olation can usually b e p er formed fast enough to provide near realtime feedback For skeleton animation however keyframe interp olation do es not work well the few go o d examples of keyframed gure animation are more a tribute to the skill and patience of the animator than to the techniques suitability for the task
of freedom problem for interesting skeletons many DOFs for which values must b e provided the level of detail required
One ma jor diculty can b e lab elled the degrees
there are simply to o
from the animator to sp ecify even a single key p ose
is excessive Trying to control the interp olated modifying possibly hundreds of tra jectory curves can be tedious frustrating and errorprone While it is essential that the animator have some control at the joint level higher
motion by manually
levels of control are desirable for sp ecifying the co ordinated movements of groups of joints
Even supp osing that the numb er of degrees of freedom within a gure is manageable the common practice of displaying interpolated joint angles as a set of three splined tra jectory curves is rarely helpful Unlike translations an ordered series of rotations do not combine intuitively making it dicult to predict the consequences of editing a single rotation tra jectory and almost imp ossible to decide on the appropriate changes to all three curves which will pro duce a desired change in a single
one each for the XY and Z rotation directions at each joint
CHAPTER APPROACHES TO FIGURE ANIMATION
b o dy segments motion
The hierarchical structure of the skeleton also causes problems The only joint which an animator
can explicitly position is the root joint in the hierarchy the positions of all
skeleton dep end on the rotations at ancestor joints This makes it dicult to enforce p ositional
constraints when creating a keyframe p ose For example if
the hierarchy ro ot
The same b oth feet are interp olating
problem crops up during interp olation Even if an
p ositioned correctly in a series of keyframe p oses there is no guarantee that simply joint rotations will maintain the correct fo ot p ositions at the intermediate frames
for a bip ed is at the is troublesome if the fo ot is already in at the knee will move the fo ot which must then b e rep ositioned by mo difying
p elvis then placing
place then a b end
the rotation at the
marginally useful
allow a knee b end which leaves the fo ot in place However this will also move the
which may move another previously p ositioned b o dy segment such as the other fo ot This enforcing multiple p ositional constraints a frustrating pro cess
a fo ot
on the o or and keeping it there
hip joint The ability to rearrange the hierarchy ab out a new In our example making the supp ort fo ot the new ro ot of the
ro ot joint is only
would b o dy makes
It is quite common to see interp olated keyframed sequences for gures in which the feet seem to p enetrate through or slide around on the o or While this can b e remedied by sp ecifying additional
keyframes as the keyframe
framebyframe p ositioning of traditional stopaction animation claymation for example This defeats the whole purp ose of interp olation which is intended to relieve the animator from the tedium of sp ecifying the motion on a framebyframe basis
While forward kinematics combined with a simple interp olation scheme may suce for animating simple ob jects it is not really up to the task of animating articulated gures
Inverse Kinematics
Using forward kinematics the position of any ob ject within a skeleton can only be indirectly con
spacing b ecomes smaller the animation pro cess b egins to resemble the
trolled
inverse
the end
desired
oers an attractive alternative to explicitly rotating individual joints within a skeleton An animator can instead directly sp ecify the p osition of an endeector while the system automatically computes the joint angles needed to place the part Not surprisingly the inverse kinematic problem has b een studied extensively in the rob otics eld although it is only fairly recently that the techniques have
by specifying rotations at the joints between the root and the
kinematic techniques provide direct control over the placement of an endeector ob ject at
of a kinematic chain of joints solving for the joint rotations which place the ob ject at the lo cation In light of the preceeding discussion it should b e apparent that inverse kinematics
other ob jects in the
hierarchy rest of the
animator has made sure that
ob ject itself In contrast
CHAPTER APPROACHES TO FIGURE ANIMATION
b een adopted for computer animation
Chadwicks Critter system
keyframes CHP Badler has
straints on multiple b o dy parts
range limits into the inverse kinematic solution CP ZB Both Girards PODA system GM and Sims gait controller SZ provided highlevel lo comotion mo dels for skeletons using inverse
p ermits inverse kinematic manipulation of prop osed an inverse kinematic algorithm to
a skeleton for creating enforce p ositional con during skeleton manipulation BMW and has incorp orated joint
kinematics to generate
ments and tra jectories
joint angles as the feet are moved along tra jectories b etween each fo othold
the leg motion In these systems a planning stage determines fo ot place while the inverse kinematic algorithm is responsible for generating the leg
Inverse kinematics provides higherlevel control over joint hierarchies than simple forward kine matics moving the limbs of a skeleton b ecomes much more manageable However often the un derlying metho d for generating motion still relies on strictly kinematic metho ds Unfortunately kinematic metho ds do not pro duce convincing movement without a considerable amount of eort
on the animators part Often the motion exhibits a weightless quality
by editing the tra jectories and timing for individual forward and inverse do not pro duce movement with exp ect from our exp erience with the physical laws of
Dynamic Metho ds
which is dicult to disp el Kinematic metho ds b oth integrity we have come to
Animation based on dynamic simulation is attractive
ical laws providing a level of realism that is extremely dicult to duplicate with kinematic metho ds For dynamic analysis ob ject descriptions must include such physical attributes as the center of mass the total mass and the moments and pro ducts of inertia Although there are many formulations for the equations of motion they are all essentially equivalent to the familiar F ma which relates the
acceleration a an ob ject
of mass The motion
and torques which may vary over time Techniques for dynamic motion control can b e categorized as either forward dynamic metho ds or inverse dynamic metho ds The essential distinction b etween the two is in the way that the basic forces and torques driving the motion are arrived at
Forward Dynamics
Forward dynamics involves explicit application of timevarying forces and torques to ob jects Some forces such as those due to gravity and collisions between ob jects may be handled automatically
degrees
the sort
the real world
b ecause
the generated motion adheres to phys
of freedom of dynamic
of mass m undergo es in resp onse to a force F applied at the ob jects center generated by physical simulation is controlled by the application of forces
a similar equation relates angular acceleration to applied torques
CHAPTER APPROACHES TO FIGURE ANIMATION
by the animation system other forces are applied directly by the animator to ob jects in the scene The motion is approximated by taking a series of discrete steps in time and at each step solving the equations of motion for the acceleration an ob ject undergo es in resp onse to the applied forces Given the position and velocity of an ob ject from the previous time step the acceleration a can be twice
integrated to determine a new velo city and
intro duction and overview of the basics of forward dynamic simulation
can b e found in Wil A comprehensive
ob jects accounting for collisions is presented by Hahn Hah
of the solution metho d A
has On complexity for n
recursive formulation which
of simple articulated structures to b e p erformed reasonably complex articulated skeletons cannot singlepro cessor machines although the recursive
solution degrees
reduces
the complexity to O n in close to in general
p osition resp ectively for the
current time step A go o d for animating rigid b o dies approach to simulating the motion of rigid p olyhedral
Extending this approach to the simulation of articulated skeletons is challenging In general there will b e one equation of motion for each degree of freedom in the skeleton This leads to a large
system of equations which must b e exp ense The formulation adopted to
Complicating matters is the fact that the equations of motion for articulated skeletons are con siderably more complex than those for simple ob jects since they must include terms to model the interactions b etween connected b o dy parts This coupling of the dynamics equations makes control extrememly dicult since movement of one segment of the skeleton will exert forces and torques on adjacent segments the notion that the motion of the skeleton can b e adequately controlled by applying joint torques individually is incorrect Wil Eorts to counteract this unwanted prop agation of torques usually involve placing springs and damp ers at each joint to maintain a desired orientation Unfortunately this typ e of control invariably leads to a sti set of equations which causes severe instability in most numerical solution techniques A summary of numerical stability and control issues that must b e addressed during dynamic simulation is presented in Gir
solved by numerical metho ds at considerable computational represent the equations of motion signicantly aects the cost for the matrixbased GibbsApp ell formulation for example of freedom Wil Armstrong has proposed an alternative
AG enabling dynamic simulations realtime But dynamic simulation of b e p erformed at interactive sp eeds on
formulation may b e fast enough to b e tolerable
Comp ounding the
articulated skeletons are inherently illconditioned indep endent of their formulation Mac The
problem of numerical instabilities is the fact that the equations of motion for
illconditioning arises
one degree of freedom pro duce large accelerations elsewhere almost all numerical solution techniques have diculty handling such cases Maciejewski contends that these situations o ccur frequently for articulated gures and are inherent in the structure of most skeletons The illconditioning of the
when the skeleton assumes a p osture in which small incremental changes in
CHAPTER APPROACHES TO FIGURE ANIMATION
equations has implications not only for dynamic analysis but inverse kinematic algorithms as well Mac gives a lucid description of the problem and discusses metho ds for detecting and handling the illconditioning in b oth cases
One of the earliest attempts to control an articulated gure purely through forward dynamic simulation was Wilhelms V ir y a system Wil V ir y a p ermitted the interactive design of force or torque versus time functions for individual degrees of freedom Force and torque keyframes could b e sp ecied at dierent times cubic splines were then used to construct the force and torque proles over the course of the entire motion sequence During dynamic simulation these forcetorque proles were sampled and combined with forces due to collisions and gravity to determine instantaneous force and torque measurements for the current time step The use of interp olating curves is conceptually similar to the direct kinematic keyframe interp olation approach describ ed previously The dierence
is that the motion is driven not directly
equations of motion V ir y a exhibited most of the problems outlined ab ove In particular Wilhelms
by the interp olated curves but indirectly through the
equations made control of the eorts to simulate skeleton motion using pure forward
WCH
gure dicult and non dynamics rep ort similar
rep orts that the coupling of the dynamic
intuitive Other problems AG
Even supp osing that a reliable and fast numerical solution technique is available the lack of intuitive control remains the principal problem in using forward dynamics for animation In fact forward dynamic simulation is b est suited for tasks which can b e p osed as initialvalue problems That is tasks for which initial p ositions and velo cities and forcetorque proles are known a priori and the goal is to generate the resulting motion This formulation may b e satisfactory for animating scenes of simple inanimate ob jects realistically tumbling and b ouncing through an environment but
do es not apply for the animation of sp ecic tasks For example simulating a ball b ouncing
o or is simple to do given an initial height and velo city the simulation need only consider the force
on a
convincing motion However if the
goal is to have the ball b ounce three times and land in
the exact initial p osition and release velo city of the ball which will
determine Yet this is precisely the sort of problem that app ears in animation the animator knows what motion should o ccur but do es not know in advance the initial conditions and forcetorque
of gravity and reactions to collisions with the o or to generate
proles
needed to pro duce the desired result
Inverse Dynamics
dynamic metho ds automatically determine the force and torque functions needed to accom
Inverse
plish a stated goal In the degenerate case the stated goal is a complete description of the motion
a cup the
problem is much more dicult land it in the cup is dicult to
CHAPTER APPROACHES TO FIGURE ANIMATION
and the aim is to determine the forces and torques which repro duce the motion under forward dy namic simulation While this case is of interest in rob otics its application is of little use in an animation system after all if the motion tra jectories and timing are known beforehand the expense of the physical simulation is unnecessary More interesting are recent metho ds which allow rela
tively highlevel constraints or goals to b e necessary to meet the goals
Geometric Constraints
modelling were presented including pointtopath constraints for moving control an ob jects orientation The forward dynamics simulation of the move the mo del towards a state in
sp ecied and which then compute the forces and torques
somewhat the distinction selfassembling structures
the geometric constraints
the laws of Newtonian mechanics
mo del was dened as simple constraints for pointtopoint constraints for attaching two ob jects together
Barzel and Barr BB made early use of
a collection of ob jects related by geometric constraints A number of useful
inverse dynamics for mo delling A
an ob ject along a predened path
and twist constraints to forces and torques into a mo del These constraint forces and torques act in concert to which all the constraints are satised This approach blurs b etween mo delling and motion control as it allows for the animation of if the constituent parts of the mo del initially are in a state which violates turning on dynamic simulation results in the mo del assembling itself using
constraints were used to intro duce
Forsey and Wilhelms have used inverse dynamics to manipulate an articulated skeleton into keyframe p ositions for a traditional kinematic interp olation system FW The Manikin system p erformed dynamic analysis during interaction with the gure using Armstrongs recursive formu lation for the equations of motion A p ositional goal for a b o dy part could b e sp ecied interactively with M anik in computing the forces to push the part towards the goal This allowed manipulation of the gure in a manner similar to inverse kinematic manipulation The imp osition of p ositional con straints up on b o dy parts was accomplished by articially increasing the mass of constrained parts with the system constantly computing additional forces necessary to keep the part in place as other parts were moved Motion sequences could b e generated by storing the state of the b o dy at dierent p oints during the dynamic analysis and later using these stored states as keyframes for kinematic interp olation
The penaltyforce approach taken here of converting all constraints into forces and torques which steer the motion during dynamic analysis has its limitations The p enalty forces are often mo delled
as simulated springs and damp ers which deliver This metho d of control is vulnerable to stiness sirable oscillations ab out constraint satisfaction
a force prop ortional to the velo city of the motion in the resulting system of equations and by unde p oints Cho osing appropriate spring and damping
CHAPTER APPROACHES TO FIGURE ANIMATION
co ecients for the constraints is often a matter of trialanderror
In contrast to the p enaltyforce approach a numb er of formulations for the dynamic equations of motion can include explicit constraint equations Isaacs Dynamo system IC IC combines keyframed kinematic constraints with inverse dynamics Rather than causing the intro duction of additional forces into the simulation the kinematic constraints are instead used to remove degrees
of freedom from the system
The remaining accelerations
ensures that reactant forces due to the keyframe constraints are
the unconstrained DOFs This allows the kinematic constraints
of a skeleton while the other unconstrained parts react realistically to the prescrib ed motion In cases where all parts are constrained the technique reduces to a simple keyframing approach This approach illustrates an interesting mixture of dynamic simulation with kinematic control However Isaacs most ambitious attempt at skeleton animation is the simulation of a traditional marionette controlled by ro ds and strings attached to the limbs While technically impressive this example p oints out the need for b etter metho ds of control over dynamically simulated skeleton motion
NonGeometric Constraints
Consider the inverse dynamic problem of moving a p oint mass from p osition A to p osition B in a given time interval t There is no unique force function over the interval t which will accomplish this the system must cho ose b etween applying a large force for a short p erio d of time or applying
since they implicitly sp ecify some of for unconstrained DOFs can then b e
the accelerations in the system solved for The solution metho d
a smaller force over a
p osition B at time t
moving from A to B but also how the motion is to o ccur A numb er of metho ds have b een prop osed which attempt to describ e the quality of motion by considering nongeometric constraints in the inverse dynamic solution These approaches are based on wellestablished techniques for optimizing functions sub ject to a set of constraints
Brotman and Netravali BN prop ose an inverse dynamic approach to motion interp olation which uses p enalty forces to enforce keyframed kinematic constraints However the solution in
longer p erio d b oth metho ds may achieve the goal of reaching the keyframed This problem is one of determining not only what is to o ccur in this case
corp orates an
formulated as that of solving for the set of constraint forces which
p enalty forces The problem is minimizes the energy exp ended
in meeting the
constraints imp osed by kinematic keyframe values
additional constraint on the energy exerted by these
Girard Gir has applied constrained optimization techniques
along predened limb tra jectories for articulated gures Girard notes that the choice of optimization criteria has a signicant eect on the p erceived quality of motion Solving for a velo city prole which
intro duced into the to sp ecify motion for
solution for some parts
to determine sp eed distribution
minimizes energy exp enditure yields a relaxed swinging motion for the limb while
ab out the end of the limb yields movement suggestive of such goaldirected tasks as
ob ject The establishment of additional correspondences between optimization criteria and expressive
CHAPTER APPROACHES TO FIGURE ANIMATION
qualities of movement remains an op en area
These constrained optimization metho ds
limbs are known in advance and attempt to derive the b est set of forces and torques which move the limb along the path This sidesteps the fundamental problem of synthesizing the limb tra jectories for coordinated movement in the rst place Witkin and Kass WK have proposed an intriguing metho d of motion synthesis they call Spacetime Constraints which they demonstrated to b e capable of synthesizing b oth the tra jectories and the timing of movements for simple articulated gures This use of constrained optimization seems particularly promising as it seems capable
of pro ducing
However the
b e considered
limitations of the metho d Coh
of research
assume that the complete or partial motion paths for
complex co ordinated physicallycorrect motion with very little input from a user approach results in very large systems of equations which must b e solved and cannot useful for interactive gure animation Ongoing research is addressing the interactivity
Badler LWZB has used a form of constraintbased inverse dynamics to synthesize the tra jectories of limbs charged with the task of moving a load b etween two dierent p ositions The tra jectories are computed incrementally and are constrained by measures of strength comfort and exertion The iterative nature of the algorithm diers fundamentally from the global solution found by optimization metho ds Instead a set of biomechanical heuristics which are intended to mimic the pro cess by which p eople move loads are used to guide the solution pro cess The metho d successfully produces feasible albeit suboptimal limb tra jectories which accomplish the task
Control Issues
The research eorts outlined ab ove are attempts to provide higher levels of control over b oth kine matic and dynamic motion The goal is to b e able to sp ecify movements at the task level and to
have the system take care of the underlying details of pro ducing state of these eorts it seems that it will b e some time b efore the
synthesizing motion to accomplish arbitrary tasks oping sp ecial purp ose control strategies for sp ecic for decomp osing highlevel task descriptions such
into lowerlevel movement
primitives may consist of
simulations constrained inverse dynamic goals or a mixture of all these approaches
primitives and for the
keyframes for interp olation inverse
the motion Given the current emergence of systems capable of However there has b een some success in devel typ es of movements The system is resp onsible
as walk to co ordination
the do or or reach of these primitives
for the cup The lowlevel kinematic goals forward dynamic
minimizing jerk reaching for an
CHAPTER APPROACHES TO FIGURE ANIMATION
Zeltzer was an early prop onent of the need for highlevel control over articulated gures Zela He describ es a control strategy for synthesizing walking sequences for a skeleton Highlevel walking instructions are decomp osed into a set of motor control programs MCP which drive the motions of individual limbs or joints The control stategy is based on a nitestate machine resp onsible for activating and deactivating the appropriate MCPs at the appropriate times Zeltzers MCPs consisted of kinematic joint values obtained from rotoscop ed human walks and thus were purely
kinematic Nevertheless the system demonstrated
the usefulness of the concept
Building on Zeltzers work Bruderlin BC develop ed a similar hierarchical control strategy for generating bip ed walking sequences but incorp orated dynamic simulation to derive leg motion rather than relying on rotoscop ed data The user is able to instruct a skeleton to walk at a particular sp eed and is able to sp ecify b oth desired step frequency and step length These instructions are decomp osed into dynamicallybased lowlevel MCPs which drive the motion of an abstract kneeless pair of legs The MCPs essentially p erform dynamic interp olation of a set of kinematic keyframes for the leg movements during the walk cycle The kinematic keyframe values and spacing are derived from the input parameters combined with knowledge ab out human lo comotion patterns gleaned from the biomechanics literature The forces and torques driving the motion of the simplied walking mechanism are iteratively adjusted until the keyframed joint angles are achieved at the correct times A purely kinematic overlay of the skeletons jointed legs onto the underlying mechanism is then p erformed The algorithm is able to pro duce a wide range of realistic walking sequences and is a true hybrid of b oth dynamic and kinematic motion control The decision to use a simplied dynamic mo del sp ecically tuned for walking seems sound the resulting system of equations is small relatively stable and inexp ensive to solve A similar approach has b een used by this author to build a jumping algorithm based on the simulation of a simple underlying massandspring mo del
Unfortunately the highlevel control provided by algorithms of this nature come at the exp ense of generality each control strategy must b e tuned for a sp ecic movement But developing such a control strategy is dicult Deriving the equations for simulating the dynamics of the underlying mechanism requires some mathematical sophistication In the absence of an inverse kinematic algo rithm Bruderlins metho d of mapping the motion of the underlying dynamic mo del to the motion of the skeleton can p ose problems to the implementor To a large extent the success of the ab ove control strategies is due to the predictable rep etitive nature of lo comotion Developing highlevel control strategies for arbitrary movement sequences still seems a distant goal
CHAPTER APPROACHES TO FIGURE ANIMATION
Summary
What has hop efully emerged from the discussion so far is that no one technique has emerged as
a clear winner A successful gure animation system is
discussed ab ove to some degree Pure dynamics applied
problems as it addresses unless it is conned to sp ecic
into automatic motion synthesis from highlevel constraints while promising is still at to o early a stage to b e considered useful For the time b eing designing arbitrary movement sequences remains in the hands of the animator
A simple interactive keyframe editor in the hands of a user who understands how the b o dy moves and has some patience can pro duce some surprisingly go o d animation sequences even for gures as complex as the human form Dynamic simulation or algorithmic motion mo dels while useful in some contexts will only b e appreciated if they can alleviate some of the work involved in interactively handcrafting new movement sequences and it can b e argued that given the current state of research in these areas this is not generally the case The most promising interactive techniques reviewed in this chapter are those based on the use of inverse kinematics which provide a level of control higher than simple forward kinematics yet still leave the user with complete control over the animation
In the remaining chapters the use of inverse kinematics to complement an existing interactive keyframe editor is explored The goal is to address the limitations of a simple forward kinematic approach by providing a set of to ols which supp ort direct manipulation of kinematic chains within a gure and the imp osition of simple geometric constraints which are maintained during keyframe creation and interp olation Along the way we identify two inverse kinematic algorithms which dier from those previously adopted for computer graphics and describ e their suitability to the problem
likely to incorp orate all of the
to gure animation seems to raise as many movement control strategies The research
techniques
Chapter
Inverse Kinematics
The inverse kinematic problem has b een studied extensively in the rob otics literature which remains the b est source of information on the sub ject In this chapter we formally state the problem and review the most common approaches to solving it Previous applications of these approaches to computer graphics are also describ ed
The Inverse Kinematic Problem
Section showed that a skeleton can be modelled as a hierarchical collection of rigid ob jects connected by joints We will refer to a kinematic chain of segments within a skeleton as a manipulator and will assume that the joints connecting segments within this chain are revolute joints rotating ab out a single axis One end of the manipulator the base is xed and cannot move the distal end of the chain is free to move The endeector is emb edded in the co ordinate frame of the most distal joint in the chain the endeector p osition is a p oint within this frame and the endeector orientation refers to the orientation of the frame itself
At each joint in the chain a joint variable determines a transformation M b etween the two adjacent
co ordinate frames sharing the joint The transformation Mi at of a translation and a rotation b oth of which are relative to the That is
Mi Txi yi ziRi
a rotation joint i is a concatenation co ordinate frame of joint is parent
where Txi yi zi is the matrix that translates by the oset of joint i from its parent joint i and Ri is the matrix that rotates by i ab out joint is rotation axis
CHAPTER INVERSE KINEMATICS
The relationship b etween any two co ordinate systems i and j in the chain is found by concate nating the transformations at the joints encountered during a traversal from joint i to joint j
j
nonlinear equations to b e do es not exist instead the
Mi
Mi Mi Mj Mj
So the p osition and orientation of the
concatenating the transformations at each joint in the manipulator
Given a vector q of known joint variables then the forward kinematic problem of computing the p osition and orientation vector x of the endeector is a simple matter of matrix concatenation and has the form
x fq
But if the goal is to place the endeector at a sp ecied p osition and orientation x then determining the appropriate joint variable vector q to achieve the goal requires a solution to the inverse of
q f x
Solving this inverse kinematic problem is not so simple The function f is nonlinear and while there is a unique mapping from q to x in equation the same cannot b e said for the inverse mapping of there may b e many qs for a particular x The most direct approach for solving the problem would be to obtain a closedform solution to But closedform solutions can only be derived
solvedPau
Resolved Motion Rate Control
Since the nonlinear nature of equation makes it dicult to solve a natural approach is to
linearize the problem ab out the current manipulator conguration
then
the
relationship
b etween
joint velo cities and the
velo city of the
endeector is
x Jqq
Jacobian matrix
The linear relationship is given by the
endeector
with resp ect to the base frame is found by simply
sp ecic characteristics and even these result in a set of A general analytic solution for arbitrary manipulators problem must b e solved with numerical metho ds for solving systems of nonlinear equations The most common solution metho ds are based on either matrix inversion or
optimization techniques
for a restricted set of manipulators with
J
f q
p osition and orientation is the dimension of the endeector vector x which is usually either for a simple p ositioning task or for a more general p ositionandorientation task The ith column of J represents the incremental change in the p osition
and orientation of the endeector resulting from an incremental change in the joint variable qi
Inverting the relationship of provides the basis for resolved motion rate control
q J q x
If the inverse of J is known we can compute incremental changes in the joint variables which pro duce a desired incremental change in the endeector p osition and orientation
CHAPTER INVERSE KINEMATICS
which maps changes in the joint variables q to changes in the endeector
x J is an m n matrix where n is the
numb er of joint variables and m
A simple iterative scheme for solving
At each iteration a desired x can
p ositions The joint velo cities q can then
once to nd a new joint state vector q The
the desired goal Note that since the linear relationship represented by J is only valid for small p erturbations in the manipulator conguration Jq must b e recomputed at each iteration A pro cedure for eciently computing the Jacobian is presented in Section
Of course this scheme assumes that the Jacobian matrix is invertible that J is b oth square and nonsingular This assumption is not in general a valid one Diculties arise when a manipulator is redundant or when it passes through or near a singular conguration
Redundancy
A manipulator is considered kinematical ly redundant when it p ossesses more degrees of freedom than
at some p oint x y
of the congurations
redundant for this D p ositioning task
the b e b e
inverse kinematic problem can b e based on equation
computed computed
from the current and desired endeector using the Jacobian inverse and integrated rep eats until the endeector has reached
pro cedure
are required to sp ecify a goal for the endeector
Figure The manipulator p ossesses degrees of freedom the rotation angles at each joint For a simple p ositioning task the goal is to place the endeector the tip of the distal link of the chain
For example consider the simple D case in
As the gure shows for a given goal x y there is no unique solution each shown will place the tip at the goal p osition The manipulator is therefore
In general p ositioning an ob ject in Cartesian space requires the sp ecication of six co ordinates three for lo cation and three for orientation Therefore any manipulator p ossessing more than six degrees of freedom is redundant for the general Dspace p ositioning task and there is no unique
CHAPTER
INVERSE KINEMATICS
(x,y)
θ3
θ2
θ1
Figure Three congurations
of a D redundant
manipulator
set of joint values solving the inverse kinematic problem
For a redundant manipulator the Jacobian matrix has fewer rows than columns and cannot inverted In this case equation is underdetermined and there are an innite numb er of
b e
solutions from
useful solution
Mo orePenrose
optimal in the sense that it yields solutions with a minimum Euclidean norm for cases in which is underdetermined m n and that in cases in which the system is overdetermined m n a leastsquares solution is obtained In practice these prop erties ensure that joints move as little as p ossible to match the desired endeector velo city as closely as p ossible
Exploiting Redundancy
Since a redundant manipulator can satisfy a p ositioning task in any numb er of ways it is often useful to consider exploiting the redundancy in an attempt to satisfy some secondary criteria This can be accomplished by incorp orating an additional term into equation
which to choose If J in is replaced by some generalized inverse Jy then a to the underdetermined problem can b e found One such generalized inverse is the pseudoinverse Gre GM It can b e shown KH that this pseudoinverse is
q J y x I J y J r H q
minimized sub ject to satisfying the
The function H q is a measure of some criterion to b e
primary positioning task The other component I Jy J
those components of the gradient vector rH q which lie in the set of homogeneous solutions to A homogeneous solution to is a set of joint velo cities q which do es not change the endeector
is a pro jection operator
which selects
CHAPTER INVERSE KINEMATICS
y
singular direction
x
Figure A manipulator in a singular conguration
p osition ie for which x In eect then the rst term of the general equation
joint velo city vector which pro duces the desired change in the endeector p osition while the second term exploits the redundancy of the manipulator by varying these joint velo cities in such a way that H q is minimized without disturbing the endeector position By exploiting redundancy in this manner secondary goals have b een created to avoid collisions with obstacles Bai to exploit joint range availability GM KH and even to maintain manipulator dexterity by avoiding kinematic singularities SS
Singularities
The pseudoinverse metho d outlined ab ove provides useful solutions to when the Jacobian matrix J is rectangular and therefore not invertible But we must also consider the case where J is not invertible b ecause it is singular A matrix is said to singular when two or more rows are linearly dep endent and a manipulator is said to b e in a singular conguration when the Jacobian b ecomes singular Figure depicts a simple example of a jointed manipulator in a singular conguration In this example an incremental change to any of the joint angles will result in approximately the same movement of the endeector in the y direction no combination of joint velo cities will pro duce an endeector velo city in the singular ie x direction The Jacobian matrix computed for this conguration will contain zero es in the rst row and is therefore singular and cannot b e inverted
The pseudoinverse can still b e applied to obtain a useful solution when J is singular However as a manipulator passes through a singular conguration there are discontinuities in elements of
Although intuitively it might seem obvious that a rotation at any joint will result in at least some movement in the x direction recall that equation deals with instantaneous quantities
selects a
CHAPTER INVERSE KINEMATICS
the computed pseudoinverse due to the change in rank of J at the singular conguration Mac Furthermore as the manipulator approaches this conguration the pseudoinverse tends to pro duce large joint velo cities Numerical integration techniques typically do not handle such derivative spikes well The problem manifests itself as a tendency of the manipulator to oscillate wildly around the singular conguration So while the pseudoinverse is able to provide a usable solution at a singular conguration its principal drawback is that it do es not provide a continuous stable solution around singularities While industrial rob otic manipulators may b e programmed to follow tra jectories which explicitly avoid singular congurations for just this reason this is not really an option for an algorithm to b e used for computer animation
The Singular Value Decomp osition
Numerical instabilities near singular congurations are a ma jor problem which raises the question of whether there is a means of detecting and correcting the problem Probably the most useful to ol for analyzing the Jacobian matrix is the singular value decomposition SVD PFTV The SVD theorem states that any matrix can b e written as the pro duct of three nonunique matrices
The pro cedure for computing the SVD of a matrix is b eyond well known and describ ed elsewhere PFTV MK The interpretation of each of the three matrices U D and V
J UDV
T
the scop e of this discussion but is signicance of the SVD lies in the
For an m n matrix J D is an n n diagonal matrix with nonnegative diagonal elements known as singular values If one or more of these diagonal elements is zero then the original matrix is itself singular Even b etter the ratio of the largest singular value to the smallest one the condition number of the matrix is a measure of how il lconditioned the matrix J is When the condition number is too large then the matrix is illconditioned It is this illconditioning that is responsible for the large joint velo cities generated by the pseudoinverse near a singular conguration Mac
The other matrices U and V are orthonormal bases for the range and nul l space respectively of J For any zero singular values in D the corresp onding columns in V form a set of orthogonal vectors which span the space of homogeneous solutions to equation ie the set of joint velo cities which will not move the endeector Likewise the nonzero singular values have corresp onding columns in U which span the space of solutions which wil l move the endeector We will refer to these basis matrices again when discussing constraints in Chapter
While the SVD provides a means for detecting illconditioning in the Jacobian matrix it do es ie its recipro cal approaches machine precision limits
CHAPTER INVERSE KINEMATICS
not in itself provide a way for dealing with the illconditioning Nevertheless it is useful as an analytical to ol Klein and Huang KH have used singular value analysis to demonstrate the optimal prop erties of the Mo orePenrose pseudoinverse Maciejewski Mac has used the SVD to illustrate the discontinuity that o ccurs in the pseudoinverse at a singularity and to develop a strategy for damping the high velo cities which o ccur near singular congurations But the cost of computing the SVD O n l og n for an n n matrix adds signicantly to the p eriteration cost of any control
algorithm so it is often not feasible to incorp orate it into online control schemes
MK do es describ e a metho d of incrementally up dating the SVD from one iteration to the next which reduces the cost to On per iteration but this requires careful implementation to reduce cumulative errors and the cost is still high enough to deter its use
OptimizationBased Metho ds
A fundamentally dierent approach to solving the inverse kinematic problem avoids the matrix inversion step altogether The idea is to cast the basic problem of equation as a minimization problem then apply standard iterative nonlinear optimization techniques to obtain a solution
As an example consider the problem of p ositioning the endeector
x at a goal p osition p The
distance from the current p osition xq to the goal p osition p serves
as
an
error
measurement
E q p xq
By varying the joint angle vector q the endeector either moves away from p increasing the error measure or towards p decreasing the error Clearly the intent is to nd a joint vector q which minimizes the error measure Limits on the joint ranges of motion provide additional constraints on
the individual joint values qi Formally we
minimize subject to
need to nd a vector q which solves the problem
E q
li qi ui i n
where li and ui are the lower and upp er b ounds resp ectively on the value of joint variable qi For this example the error measure E is just the distance formula but the approach generalizes to more complex goals for the endeector since E q can be any arbitrary function of the joint vector q
This formulation is a classic nonlinear constrained optimization problem which can b e solved by
a numb er of standard numerical metho ds A go o d intro duction to the
issues to consider in selecting a solution metho d is presented by Press et al PFTV Gill et al survey a numb er of practical optimization techniques GMW The eectiveness of any particular
metho d is usually determined by the characteristics of the ob jective
function in this case E and
topic of optimization and the
Maciejewski
CHAPTER INVERSE KINEMATICS
of the constraints For our example a solver for minimizing smooth quadratic functions sub ject to linear inequality constraints would b e an appropriate choice
A typical solver will iteratively converge from an initial state towards a solution state at each step perturbing the state variables slightly and reevaluating the ob jective function to evaluate its progress Some solvers may make use of the gradient of the ob jective function rE to suggest new directions in which to p erturb the state vector This may increase the computation p er iteration but pay o in an improved rate of convergence toward a solution
Once selected the optimizer can b e thought of as a black b ox which
current joint vector q a function for evaluating the ob jective function E and possibly a function to
evaluate rE as well The output from the black b ox is a new joint vector error measure E and therefore solves the inverse kinematic problem
which minimizes the
Evaluation
While conceptually simple there are some practical diculties in implementing this approach Con
Furthermore there is no guarantee that a solver will nd the true global minimum for a con strained optimization problem Since most solvers converge on a solution by iteratively moving downhill along the ob jective function surface they cannot distinguish between a true global min imum and merely a lo cal minimum of the surface In practical terms this implies that the solver may return a joint vector q which do es not provide the b est solution and the user may have to somehow suggest a more appropriate conguration from which to restart the iterative search for a b etter solution
For interactive computer graphics the demands of interactivity place some additional demands on the solver Interactive dragging of a manipulator involves rep eatedly sampling the cursor lo cation onscreen to determine a goal p osition for the endeector then invoking the solver with the current manipulator state as the initial guess at a solution To maintain the illusion of continuous interactive control during dragging the screen needs to be updated at a reasonable refresh rate If the solver black b ox cannot pro duce a solution quickly enough to provide go o d feedback to a user dragging
strained optimization of
pro duced a collection of
Selecting an appropriate
dicult A solver may work well for one particular typ e of problem but fail miserably on others
arbitrary nonlinear functions is numerical metho ds which may or solver and determining what the
is fed as inputs the
still an op en research area which has may not work for a particular problem problem is when it fails to work can b e
each step should decrease or increase when maximizing the ob jective function framessec for example is a minimal goal to aim for during interaction
CHAPTER INVERSE KINEMATICS
a manipulator onscreen then the interface will feel sluggish and unresp onsive
that optimizers typically work b est when the initial state is close to the nal
interactive dragging the cursor may get ahead of the solver so that on the next invo cation of the solver the state of the manipulator b eing dragged is not close to the next solution As a result the solver may drastically alter the state while solving for the next solution the result is that the manipulator will seem to suddenly jump to a completely dierent conguration in order to satisfy the goal This is of course quite disconcerting to a user One option is to interrupt the solver and obtain its current state in order to refresh the screen However since the solver is free to try dierent paths as it feels its way towards the closest minimum there is no guarantee that intermediate solutions will be suitable for refreshing the screen
Applications to Computer Graphics
Each of the approaches ab ove have previously b een adopted for computer graphics The pseudoin verse metho d was intro duced to the computer graphics community by Girard in GM for his PODA gait generator Girard exploited the redundancy of animal limbs in an attempt to minimize joint limit violations using the pro jection op erator metho d of Section The inverse kinematic capabilities of Sims gait controller SZ and Chadwicks Critter system are also based on the tech nique None of these eorts suggest sp ecic solutions to the problems the metho d exhibits around singularities so it seems reasonable to assume that each of these systems will not p erform well near singular congurations
Badler and Zhao CP ZB have adopted the second approach for the Jack system applying
a variablemetric optimization pro cedure to
posture Joint range limits are presented as
functions for simple geometric constraints are develop ed These include for example p ointto p oint constraints p ointtoplane constraints orientation constraints and others of a similar nature Simultaneous constraints on multiple b o dy parts can b e imp osed by simply summing the individual ob jective functions for each constrained part into an aggregate ob jective function to b e minimized This p ermits inverse kinematic manipulation of a gure while maintaining a set of constraints on the b o dy which is a useful interactive to ol Phillips PB even describ es an ob jective function which attempts to balance the Jack gure providing a go o d example of how the metho d can b e extended to handle arbitrarily complex nongeometric goals While Jacks capabilities are impressive and do
provide interactive control over an articulated gures
constraints to the optimizer and a
number of ob jective
on highp erformance graphics workstations noticeably degrades the resp onse time of the screen with intermediate solutions from the
p erform at interactive sp eeds it works b est
then the imp osition of just a few constraints
Badler admits to p erio dically refreshing the
to retain interactivity even after stating CP that only the nal solution is useful and that the
A related solution
problem is But during
and even interface optimizer
CHAPTER INVERSE KINEMATICS
intermediate solutions should not b e considered motion
A simpler conjugategradient minimization technique is also used by Alt and Nicolas AN providing inverse kinematic manipulation and animation of limbs by animating p osition goals over time In constrast to Badlers approach they p erform unconstrained minimization electing to enforce joint limits by simply clamping solution values to the joint variable b ounding values
It is also worth noting that some early attempts by Badler to solve the inverse kinematic problem were based on simple heuristic algorithms KB BMW These metho ds do not app ear to have gained wide acceptance Badler has since abandoned these approaches in favour of the optimization metho d describ ed ab ove
Chapter
Ecient Algorithms for Direct Manipulation
One of our goals is to provide direct manipulation of an articulated gure and for this the metho ds of the previous chapter have some shortcomings The pseudoinverse is exp ensive to compute and is sub ject to numerical instabilities around singular congurations Badlers optimization metho d is considerably more p owerful but its p erformance leaves something to b e desired and it may b e more suitable for solving problems oline than for interactive manipulation The continuing app earance of inverse kinematic pap ers in the rob otics literature seems to suggest that neither of these metho ds is entirely satisfactory
In this chapter a pair of simple inverse kinematic algorithms are presented as alternatives to those adopted for computer graphics in the past Both are relatively simple to implement are numerically stable and are ecient enough to provide reasonable interactive p erformance on even lowp erformance machines Each metho d exhibits a dierent b ehaviour than the other and it is suggested that they might work well together as complementary manipulation to ols
A Simplied Dynamic Mo del
The rst metho d b elongs to a class of solutions to
on the transp ose of the Jacobian matrix Like the
relies on the linear relationship b etween endeector and joint velo cities Unlike this other approach however no inversion of the Jacobian matrix is required which signicantly reduces the cost of each iteration Consequently the metho d has b een advo cated for the online dynamic control of rob otic manipulators
the inverse kinematic problem that are based resolvedmotion rate control of section it
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
The metho d was intro duced in by Wolovich and Elliot WE who describ ed a dynamic control scheme based on the use of the Jacobian transp ose and showed that it could provide stable tracking of an arbitrary endeector tra jectory Sciavicco and Siciliano SS applied the method to redundant manipulators and showed that the redundant degrees of freedom could b e used to satisfy b oth obstacle avoidance constraints and constraints on joint ranges of motion Das et al DSS develop a more general technique for satisfying secondary criteria similar to the pseudoinversebased metho d discussed in section and compare the metho d to a minimization algorithm based on Newtons metho d Novakovic and Nemec NN show that the metho d can b e used to generate either joint velo cities or joint accelerations We are interested here in pro ducing joint velo cities to
drive the
joint parameters
The Jacobian Transp ose Metho d
Consider a comp osite force F applied to the tip of a real manipulator consisting in some direction and a twist torque m ab out some axis
T F fx fy fz mx my mz
of b oth
a pull f
This external force F applied to the endeector will result in internal torques and forces at the manipulator joints Under the simplifying assumption of the principle of virtual work Pau the relationship b etween F and the vector of internal generalized forces is
JTF
This suggests a rather simple iterative metho d for forcing an tra jectory xd t If the current endeector p osition is given by
et xd t xc t
can be thought of as a force f pulling the endeector toward
Equation can then be used to transform this external force to a generalized force on each of the joint variables If we are interested in the dynamic b ehaviour of the manipulator in reaction to the applied force then can b e considered the vector of joint variable accelerations q Since we are not particularly interested in accurate dynamic simulation of the manipulator it suces to think of as the vector of joint displacements velo cities so that
q J T F
Once q is computed a single integration step yields a new vector q which moves the endeector towards xd t This pro cedure rep eats until the endeector reaches the desired p osition or some other stopping criterion is met
endeector to track
a timevarying measure
xc t then the
error
the desired tra jectory point xd t
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
In eect at each iteration we treat the vector e as an elastic force pulling on the end of a dy namically simple manipulator and adopt a heuristic simulation mo del in which force is prop ortional
to velo city rather than acceleration Using f mv as
the eects of inertia things stop moving as so on as the applied external force disapp ears Gleicher GW has used the relationship combined with this simple equation of motion to provide direct manipulation over a variety of geometric ob jects The term dierential manipulation has been coined to describ e this and the discussion ab ove shows that we can add articulated structures to the set of ob jects amenable to direct manipulation of this typ e
Equation is in fact equivalent to the wellknown steepest descent metho d of minimization which is generally regarded as having p o or convergence prop erties PFTV This raises the question
of why one would adopt this
prop erties The intent here is to provide direct manipulation of articulated gures in an interac tive setting rather than to solve inverse kinematic problems oline and for this typ e of online application the Jacobian transp ose metho d has some app ealing characteristics
The rst of these is that no matrix inversion is required Using the transp ose of the Jacobian not only avoids problems with matrix singularities but also means that at each iteration only forward kinematic calculations are required Since these can be computed quickly a tra jectory which is being sp ecied interactively can b e sampled frequently providing resp onsive feedback to the user
More imp ortantly
solutions obtained in successive
tor will resp ond as though the user were in fact pulling on the endeector contrast other minimization techniques may generate successive solutions
redundant and there
One drawback is that since the metho d is based
kinematic singularities since the matrix will b e inherently illconditioned Near a singularity high joint velo cities can result in oscillations ab out the singular conguration This typically o ccurs only when trying to fully extend the manipulator The problem can b e overcome by either using a smaller integration stepsize using an integration metho d with an adaptive stepsize or by clamping joint velo cities to some maximum b ounds b efore integrating Since the basic solution step is so quick
from each other particularly when the manipulator is acceptable solutions When using a physicallybased constrained to b e close to each other the pulling
p o or convergence prop erties of the metho d
the governing equation of motion eliminates
approach over other minimization metho ds with sup erior convergence
since the solution is based on a physical mo del alb eit a simplied one the iterations are b oth predictable and intuitive That is the manipula with an elastic band In which are quite dierent are an innite numb er of mo del successive congurations are implicitly metaphor uniquely sp ecies a path from one solution to the next For interactive applications this advantage arguably outweighs the p otentially
on the Jacobian it is not entirely immune to
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
F q’ q
x− d
x c
Figure Interactive
to compute often it is interactive p erformance
control
simply
lo op mo del for Jacobian transp ose
use a smaller integration stepsize
metho d
while retaining
go o d
T J
Implementation Details
p ossible to
In comparison with the metho ds of the previous chapter implementation of the Jacobian transp ose metho d is relatively simple Each iteration involves computing a force applied to the endeector computing the Jacobian matrix for the current conguration and computing the resulting joint
velo cities
Figure depicts the basic control lo op
The joint velo cities are integrated once to obtain a new conguration for the manipulator
Forces
in Chapter For now we assume that the applied force is known and concentrate on the other asp ects of the metho d
Computing the Jacobian
At each iteration we need to compute the Jacobian matrix J whose columns convey how the end eector frame moves in the world frame as the individual joint variables change Given a vector of joint variables q the endeector frame is sp ecied by a p osition Pq and orientation Oq The
applied to the endeector are a result of interaction with the user and will b e discussed
∫
f(q)
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT
MANIPULATION
Jacobian column entry for the ith
joint is
Ox i
derivative world frame
op erator is with
or may b e computed in the
ui in the lo cal joint frame At each joint Mi is the matrix which to the world frame Supp ose that axisi represents the normalized
transforms the transformation of
axis in the
world co ordinate frame
Then for
a translating
axisi ui Mi
joint the corresp onding Jacobian
T axisi
J
entry
is
and for a rotating joint the Jacobian entry is
where
p denotes the
p osition of the endeector and ji is
the p osition
of
joint
i
in the
world
Lo cal vs World Frame
Ji
T p ji axisi
T axisi
Px
P y
J P z
Oy Oz
qi These
lo cal joint
for eciently computing the full Jacobian matrix
Each joint i in the manipulator either translates along or rotates ab out one of the principal axes
where the
resp ect to
entries frame
can
b efore b eing
in the
world
for a manipulator
frame Here we describ e b oth pro cedures
i
In practice it is exp ected that the
eral transformation hierarchy within an animation system This subtree may contain arbitrary transformation no des in addition to those corresp onding to the manipulator joints These additional transformation no des do not constitute degrees of freedom and are not sub ject to up dates by inverse kinematic manipulation But since they transform some of the lo cal joint frames of the manipulator
manipulator itself
will b e a subtree emb edded within a
gen
either
b e
computed transformed to the
lo cal joint frame
the
lo cal
joint
directly
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
they must b e considered The signicance of this is that the typ es of no de present in the hierarchy determine whether the Jacobian entries can b e computed in the global world frame or whether they must b e computed in the lo cal joint frames at a slightly higher cost
If the transformation hierarchy in which the manipulator is emb edded consists only of trans
lations and rotations then the Jacobian entries concatenation of only rotations and translations transformation Mi at a joint will b e orthogonal
can b e computed directly in the world frame A guarantees that the upp erleft p ortion of the This implies that the rst three rows of Mi are the
transformed principal axes of
Similarly the joint position ji can be extracted from the fourth row of Mi Since the transformation matrices M need to b e computed to display the structure caching them at each joint during display reduces the calculation of each Jacobian entry Ji to just a vector subtraction and a cross pro duct op eration
If scaling transformations are permitted in the hierarchy then there is no guarantee that Mi is orthogonal Arbitrary nonuniform scaling transformations within the manipulator may result in an upp erleft p ortion of Mi which do es not represent a pure rotation In this case axisi cannot b e extracted from Mi Instead the vector quantities in and must b e computed in the lo cal joint frame then transformed to the world frame by Mi To compute in the lo cal frame the endeector p osition p needs to b e transformed from the world frame to the joint frame and so
the inverse transformation Mi is required
For eciency Mi matrix identity
can b e computed incrementally
while
traversing the
hierarchy
Using the
the joints local frame and so axisi can be extracted directly from Mi
AB B A
and the fact that the inverse transformation for a single joint is simple to determine the matrix inversion step at a joint can b e replaced with a cheap er matrix multiplication Further simplications
result from noting that the world frame joint frame and that the joint axis is simply one trivial
p osition ji corresp onds to the of the principal axes making
origin of the lo cal joint the cross pro duct step
The Jacobian
the hierarchy At
calculations may b e p erformed either in the global frame or the lo cal joint frame
matrix for the endeector
each joint i either or is computed to obtain the column Ji and these
frame then can b e assembled
by a single traversal of
as they are likely to b e in any computer animation system
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
Scaling Considerations
In practice the simple mo del expressed in equation do es not work well for the general case One problem is that the resp onse of the manipulator to an applied force dep ends on the choice of scale for the joint variables If rotation joint values represent degrees for example a given applied force will result in a dierent resp onse than if the rotations were measured in radians The overall scale of the world must also b e considered since this will govern the magnitude of the vector quantities in These factors must b e taken into account if the technique is to provide uniform b ehaviour over a range of scales
To provide stable scaleinvariant b ehaviour we can mo dify equation to comp ensate for these factors
q KJT F
where K is simply a constant scaling matrix whose ith diagonal entry Ki acts as a weighting factor for the computed joint velocity qi The following term is suggested
Ki
where the wi term is prop ortional to the
wi i
length of link i and is intended to oset the eects of
world
b e thought of of the joint to an applied force This parameter might
the overall scale of the
as a parameter controlling the
b e made available to the user to allow editing of a joints p erceived stiness
The i term is a weighting factor for joint i which can
resp onsiveness
Although K is sp ecied here to b e a constant gain matrix it is p ossible to compute a timevarying gain matrix Kt so as to control the rate of convergence of a tracking algorithm based on WE NN However given that the additional computation required is considerable relative to the basic iteration cost of there is some incentive to just consider K constant
Integration
Once the joint velo cities q are known a single integration step is required to generate the new state of the manipulator q for the next iteration The simplest metho d is to take a single Euler integration step
q q h q
for some integration stepsize h This metho d is
velo city across the step interval As the interval
but overall p erformance suers Nevertheless the Euler metho d with a small h may b e adequate for manipulators with just a few joints
notoriously width h is
inaccurate
made smaller the
accuracy improves
since it assumes constant
The Euler metho d can b e replaced with a more robust metho d An adaptive stepsize
Kutta metho d can improve p erformance taking small steps when required but allowing the
h to increase when small steps are unnecessary Adaptive integration implementations are available
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
in the public domain PFTV and their use is
Joint Limits
Since the formulation do es not explicitly include are enforced by clamping qi to upp er and lower not recommended in most optimization texts in
force
recommended
constraints on the joint variable values joint limits b ounds after the integration step Although this is
practice it app ears to b e adequate
goal
Runge stepsize
Figure A case not handled well with the Jacobian transp ose metho d Pulling inwards on the tip of the manipulator on the left will not pro duce an exp ected conguration like the one shown on the right
A Complementary Heuristic Approach
The forcebased approach of the preceding metho d has some app ealing characteristics for interactive manipulation There are some cases however for which the metho d do es not p erform well Figure illustrates one such case On the left is a manipulator in a singular conguration with a new desired p osition for the tip shown as a black dot The conguration on the right shows a reasonable solution to this inverse kinematic problem and probably reects what a user exp ects to get by dragging the tip in towards the goal However as the user attempts to drag the tip inwards the applied force exerted on the tip p oints straight down the singular direction it is in eect cancelled
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
out and the tip will not move This b ehaviour is reasonable given the physical analogy of the Jacobian transp ose metho d but may not really match the users exp ectation
An alternative inverse kinematic algorithm is presented here suitable for interactive p ositioning and capable of providing reasonable b ehaviour in cases such as that in Figure It is based on a heuristic metho d which has b een prop osed to quickly nd an initial feasible solution for a standard minimizationbased algorithm WC However it can stand on its own as an inverse kinematic p ositioning to ol Like the Jacobian transp ose metho d the technique is ecient simple and immune to problems with singularities However its b ehaviour is quite dierent from that exhibited by the previous algorithm and it is suggested here as a complement to rather than a replacement for the Jacobian transp ose metho d
The CyclicCo ordinate Descent
The cycliccoordinate descent CCD metho d is an
tempts to minimize p osition and orientation errors by varying one joint variable at a time Each iteration involves a single traversal of the manipulator from the most distal link inward towards the manipulator base Each joint variable qi is mo died in turn to minimize an ob jective function The minimization problem at each joint is simple enough that an analytic solution can b e formulated so each iteration can b e p erformed quickly
As a solution is obtained at each joint the endeector p osition and orientation are up dated immediately to reect the change Thus the minimization problem to b e solved at any particular joint incorp orates the changes made to more distal joints during the current iteration This diers from the previously describ ed metho d which in eect determines the changes to each joint simultaneously
Supp ose that the current endeector p osition is
Pc xc yc zc
and that the current orientation of the endeector is sp ecied
by the three orthonormal rows of the
rotation matrix Oc
uc Oc uc
uc
Metho d
iterative heuristic search technique which at
ie although the changes are computed sequentially the state of the manipulator remains constant during the iteration
CHAPTER
EFFICIENT
ALGORITHMS FOR
P ic
DIRECT
MANIPULATION
u 2d
u 3d
φP d
P id
Example CCD iteration step for
u 1d
j i
Figure
rotation joint i
The endeector
by nding a joint vector
which is just the sum of
and an orientation error
placed as close as p ossible to some
q which minimizes the error measure
E q Ep q Eo q a p ositional error measure
orientation Od
can b e
desired
p osition
Pd
and
measure
Eo q
X
j
uj d uj c
Ep q kPd Pc k
The metho d pro ceeds by considering one joint at a time from the
qi is mo died to minimize equation b efore pro ceeding to
minimizing b ecomes a simple onedimensional optimization problem since only qi is allowed to change while the other elements of q are xed Since joint i is either a rotation or a translation joint there are two cases to b e considered
Rotation Joint
Figure illustrates the situation for rotation joint i during an iteration The vector Pic is the vector from the joint p osition ji to the current endeector p osition and Pid is the vector from ji to the desired endeector p osition We are free to rotate the vector Pic ab out the world space joint axis axisi by some amount This rotated vector is
Pic Raxis Pic
i
tip the
to
next joint i
the
base
Each
At each joint
joint variable
CHAPTER
EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
As varies
position Pd
by varying joint variable seek a value for which
closest to the desired so the best we can do Pic and Pid This implies that we
following ad hoc
values for these factors are suggested WC
wo
wp
Pic sweeps out a circle centered at ji The p oint on this circle
is the point at which the circle would intersect the line along Pid
Reasoning along similar maximizes the expression
lines an orientation error
Combining both
Here wp and wo
duced to play a role similar to that of the
ji alone is to align the two maximizes the expression
vectors
corrected
g Pid Pic
also
joint i intro
g
X
j
and gives an aggregate ob jective g wp g wo g
function
to be
maximized for
is b est
uj d uj c
by making
sure
that
are arbitrary p osition and orientation weighting factors
gain matrix K of the Jacobian transp ose
Here is a scaling factor inversely prop ortional to the overall world scale W kW
and is required to make the algorithms b ehaviour scaleinvariant The factor is an arbitrary weight which dep ends on the conguration of the manipulator Wang WC suggests without justication that
minkPid k kPick
maxkPid k kPick
which seems to be adequate in practice
With some algebraic manipulation the ob jective function to reduced to
be maximized at
joint
i
can be
resp ectively
and are metho d The
with the constant
g k cos kcos k sin co ecients k k and k given by
k wp Pid axisi Pic axisi wo
X j
uj d axisi uj c axisi
CHAPTER
EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
implies that
determines
a candidate
value
candidate values to consider c
k
k
X
wp Pid Pic wo uj d uj c
j X
j
axisi wp Pic Pid wo
uj c uj d
From elementary calculus we know that the ob jective function is maximized over
when its rst derivative is zero and its second derivative is negative The rst condition
k ksin k cos
Translation Joint
If joint i is a translation joint then it can only reduce the p osition error
It error is to
is not dicult to change the joint
show WC that the b est that can b e done to minimize displacement by
the p osition
tan
k
k k
c in the range
the
interval
which
there are p otentially two other
values those which lie in the interval x and which pass the second derivative test are maximizing values for the ob jective function If there is more than one of these the ob jective
c
However
is candidate
since tan and c Of these
p erio dic
function is evaluated with each to determine
uniquely determined in this way it is added
introduce an arbitrary weighting factor wi wi which controls the perceived stiness of the joint so that the up date b ecomes
qi qi wi
The endeector frame is then rotated to reect this change and the iteration continues on to the next joint i using the up dated endeector
which yields the true maximum Once has b een to the current joint value qi At this p oint we can
Pid Pic axisi
This is weighted by wi as before and added to the current value of joint variable qi The endeector
p osition is up dated b efore continuing
Overview
on to the next joint
A single iteration of the CCD metho d for an njointed manipulator visits joints n through in turn At each joint the original ndimensional optimization problem is reduced to a onedimensional
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
problem involving just the joint variable qi which admits to an analytic solution An incremental change to qi is computed with either if the joint rotates or with if the joint translates The variable qi is then incremented and clamp ed to upp er and lower b ounds The current endeector frame Pc and Oc is up dated to reect the change b efore pro ceeding to the next joint
The algorithm behaves well around singular congurations and since the value of the ob jective function is reduced with each step the metho d is guaranteed to converge But the heuristic nature of the metho d makes the rate of convergence somewhat dicult to quantify since it is de
p endent on the structure of the manipulator itself In
only a few iterations although there are situations for
In terms of b ehaviour the heuristic implies that distal
the base if the endeector goal can b e reached by moving only the nal link of the chain then only that link will move
Comparison
the metho ds describ ed ab ove is suitable for interactive direct manipulation with
Each of
caveats
dragging
singularities although the CCD metho d has an edge in this regard since it is completely immune to diculties near singularities Where neither metho d particularly excels is in the rate at which they converge toward a solution b oth can exhibit p o or convergence rates particularly if high accuracy is required
The p eriteration cost for each is minimal so reasonably complex manipulators Each can
some that b oth can provide go o d feedback when b e made numerically stable near kinematic
Figures and compare the p erformance of each algorithm for solving a pair of inverse kinematic problems The manipulator has degrees of freedom ab out the same complexity as a simple approximation to a limb although for this example there are no limits on the range of movement for each joint In each case a p osition goal is sp ecied for the endeector and the inverse kinematic problem is solved to varying degrees of accuracy Each gure shows the initial conguration and the nal solution obtained with each metho d In addition the time to achieve the solution is plotted with resp ect to the degree of accuracy requested In the rst case of Figure the endeector goal is well within reach and b oth metho ds are able to solve the problem reasonably quickly However it is already apparant that the Jacobian tranp ose converges slowly when it is close to a solution there is a marked decrease in p erformance for each additional digit of accuracy requested
In the second case of Figure the goal is close to the edge of the reach space of the limb
practice most problems can b e solved with which the metho d can converge very slowly links move more readily than links closer to
CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION
which must
to solve the goal the CCD
approach a singular conguration to achieve the goal Although b oth metho ds are able metho d clearly outp erforms the other particularly as the accuracy of
the solution
small applied force which is
progress towards the goal is very slow example
increases As it
approaches the goal the Jacobian transp ose metho d is hamp ered by a
pulling
in a direction which do esnt aect most of the joints so the The heuristic approach of the CCD fares much b etter in this
The nal congurations
moving distal links in contrast with the other metho ds tendency to distribute joint changes more equally along the chain This dierence in b ehaviour is quite noticeable during interactive dragging Manipulating a chain with the Jacobian transp ose metho d tends to feel like playing a exible elastic ro d while the CCD metho d imparts a feel more akin to pulling on a chain of lo osely connected links While the nal solutions for the CCD metho d might lo ok inferior to those obtained with the Jacobian tranp ose keep in mind that these solutions were obtained noninteractively ie they were computed oline When dragging interactively using the CCD metho d it is usually not dicult to
shown in the gures also illustrate the CCD metho ds preference for
gain control over the nal p osition by moving the cursor
a means of controlling joint resp onsiveness by sp ecifying an appropriate weighting factor wi at each joint In particular this parameter can b e useful to oset the default b ehaviour of the CCD metho d
These examples illustrate the main advantages and disadvantages of each metho d Both are quick and therefore worth considering if direct manipulation is required even on machines with mo dest p erformance The Jacobian metho d has the advantage of resp onding in an intuitive fashion to pushes and pulls on the endeector the CCD metho d is not as intuitive in this regard The CCD metho d exhibits more stability around singular congurations and although its rate of convergence slows it is not nearly to the extent that the Jacobians do es Moreover it can b e argued that direct manipulation do es not necessarily require a high degree of accuracy Certainly while a user is sweeping a cursor across the screen it is not critical that the endeector track it to six decimal places of precision one or two decimal places of accuracy probably suces When accurate p ositioning is required particularly near singularities the CCD metho d would b e the appropriate metho d to use In general the two metho ds complement each other nicely providing alternate interaction mo dels to oer the user
appropriately Also b oth metho ds supp ort
CHAPTER EFFICIENT
ALGORITHMS FOR DIRECT MANIPULATION
(a) Initial
200
Time (milliseconds)
100
(b) Jacobian transpose
(c) CCD
X
O
X
O
O
X
X
X
XO O
O
X − Jacobian O − CCD
1e−1
1e−2 1e−3 1e−4 Convergence Criteria
Figure
1e−5 1e−6
CHAPTER EFFICIENT
ALGORITHMS FOR DIRECT MANIPULATION
(a) Initial
2750
2000
Time (milliseconds)
1000
X − Jacobian O − CCD
(b) Jacobian transpose
(c) CCD
X
X
XO O
X
X XO
O
O
1e−1 1e−2
Convergence Criteria
Figure
O
1e−5
1e−3 1e−4
1e−6
Chapter
Incorp orating Constraints
Inverse kinematic manipulation is a useful shortcut but do es not in itself provide any more function ality than simple forward kinematics Creating a p ose for a skeleton can b e less tedious but there are still problems in trying to edit the p ose without moving previously p ositioned b o dy parts It would b e useful for example to b e able to sp ecify that parts of the b o dy should not move no matter how we manipulate the skeleton Badlers recent work CP has shown the usefulness of b eing able
to imp ose
with Jack
sp ecied
PB this capability has not b een exploited The basic set of constraints available within Jack are almost all simple geometric constraints on p ositions and orientations of b o dy parts It would seem that even this limited set of constraints is enough to greatly improve interaction with a gure
In this chapter we consider how each of the manipulation techniques describ ed in the previous chapter can b e used to satisfy multiple simple geometric constraints on the p ositions and orientations of endeectors within a skeleton and discuss some of the p erformance and implementation issues that arise
Constraint Satisfaction
A manipulator or a skeleton can b e considered a system describ ed by a set of state variables for our purp oses joint rotations Solving the inverse kinematic problem is essentially one of solving a nonlinear system of equations for these state variables and there are a numb er of approaches one can take to incorp orate constraints in the solution pro cess We have already seen that constrained optimization is one p ossibility but there are other p ossibilities for the manipulation metho ds of the previous chapter
constraints on a gure during editing The constrained optimization metho d employed
p ermits any constraint which can b e expressed as a function of the skeleton state to b e However with the exception of the exp erimental balance constraint describ ed by Phillips
CHAPTER INCORPORATING CONSTRAINTS
The simplest approach is to use some variant of the penalty method This metho d can b e used with any iterative technique and the essential idea is that when a constraint is violated a restoring force is intro duced to push the system back into a legal state in which all constraints are satised A feedback control lo op monitors the state of the system and applies the appropriate p enalty forces as it detects constraint violations An advantage of this approach is that if the constraints are not initially met the restoring forces pull the system towards a legal state A disadvantage is that the constraints cannot b e enforced exactly since the restoring force only comes into play after a constraint has already b een violated Thus two p oints constrained to b e coincident will app ear to pull apart slightly b efore the constraining force can pull them back together For metho ds based on physical simulation the restoring forces are usually springbased If the springs are made suciently sti then the constraint violations may b e small enough to b e unnoticeable But this causes problems when trying to simulate the system requiring tiny integration steps to retain numerical stability PFTV
Both the Jacobian transp ose metho d and the CCD metho d could b e used within a control lo op to provide this sort of constraint satisfaction In fact due to the heuristic nature of the CCD metho d and its reliance on strictly geometric information this is the only option op en Before describing a p enaltymetho d approach based on the CCD metho d we consider rst a more comprehensive solution which is a generalization of the Jacobian transp ose metho d
Maintaining Constraints
The approach taken is to consider the problem of maintaining a set of constraints which are already satised rather than trying to satisfy constraints that have b een violated By assuming that the system is already in a legal state the problem is reduced to one of ensuring that changes to the system never violate the constraints The technique is based on wellknown metho ds for implementing constrained dynamics within physical simulations Sur AW using the same sort of simplied rstorder equations of motion describ ed in Section and by Gleicher GW The essential idea is that geometric constraints on an ob ject are treated as mechanical connections which introduce constraining forces into the system b eing simulated When an external force is applied to the system some comp onents of the applied force may b e counteracted by these constraining forces so that the net force acting on the system do es not violate the constraints The nub of the problem is to determine what these constraining forces are given a set of geometric constraints which must b e satised
Figure illustrates the concept for the simplest p ossible system a p oint The systems state q is simply the p oints lo cation in space A single constraint is imp osed on the system stating that the
CHAPTER INCORPORATING CONSTRAINTS
force force only
those
not change so the derivatives of C must always b e zero In particular this
imp oses the
condition
F a
F t
F c
Figure A force applied to a p oint constrained to lie within a plane A constraining force normal to the plane is added to the applied force to obtain a legal force tangential to the plane
lie within a plane This constraint condition can b e written as a function of the system Now supp ose a force Fa is applied to the p oint If the p oint is to remain in the the constraint must intro duce a counteracting force Fc which removes from the applied comp onents which would move the p oint away from the plane Summing the applied with this constraint force yields a net force acting on the p oint which ensures that the p oint moves in a legal direction Although simple this example illustrates two imp ortant p oints which apply to more complicated systems the net force lies in a plane tangent to the constraint surface cq while the constraining force points in a direction normal to this tangent plane We now describ e a pro cedure for computing the appropriate constraint forces for arbitrarily complex
systems
The Constraint Condition
Supp ose we write the constraints on a system as a vector function of the system state
C fq
If the constraints are initially satised then C In order to maintain the constraints C must
p oint must state cq plane then
C
C q
q
In Chapter equation dened the simplied equations of motion for a system which had the form
q Kg in fact for this trivial example the tangent plane is the constraint surface
CHAPTER INCORPORATING CONSTRAINTS
for some generalized force g acting on the system state Substituting this equation into and
denoting the constraint Jacobian matrix by Jc c the constraint condition becomes q
C J c K g
Any generalized force g acting on the system which satises this condition will not violate the constraints
Computing the Constraint
Jacobian Matrix
how the individual constraints change as the state
of m is an
In practice constraints are not sp ecied on q directly but rather on more meaningful geometric entities such as p oints or orientations which are themselves functions of the state q For example supp ose we wish to imp ose a constraint that the tip of a limb on an articulated skeleton denoted Pq should remain xed at some lo cation R An appropriate constraint condition for this example would b e
The constraint Jacobian matrix Jc describ es
variables vary The section ab ove intro duced the constraint vector Cq which is made up scalar constraint functions c q cm q If there are n state variables q qn then Jc m n matrix Typically there are more state variables than there are constraints
In this case the constraint
vector C
R Pq
consists of scalar constraints one on
each of the x y
Jacobian
contributes a blo ck of r rows to the matrix where r is the dimension of the geometric quantity eg r for a p oint constraint Since geometric constraints are expressed in terms of functions of q the chain rule is applied to calculate the Jacobian entries In the case
comp onents of
P
Each scalar each geometric
constraint constraint
ci contributes a single row ci to the constraint qj
matrix Thus
ab ove for example
Cq
xyz
c P q c P q c P q
Rx Px Ry Py Rz Pz
and z
ci qj
ci Pk Pk qj
Typically a single constraint will dep end left fo ot of the sample skeleton of Figure
on only a few of the is constrained to some
system state lo cation for
variables If the example the arm
CHAPTER INCORPORATING CONSTRAINTS
joint variables have no eect on this
constraint Thus the ith row of Jc
constraint ci usually contains Jc b e exploited and preserved naive implementation
Computing the
corresponding to the that this sparsity in matrix techniques oer substantial p erformance gains over a
Jc while the net force g must lie in its null space This is a presented in Figure
If the constraint force is in the range of Jc then gc Jc can b e written as
T
generalization of the specic example
just a few nonzero elements sparse
It is important
Constraint Force
In Chapter it was shown that an external force applied to a p oint on an articulated skeleton could b e converted to a generalized force g on the skeleton state by the Jacobian transp ose metho d However the g of equation is the net generalized force on the system As such it may include the sum of multiple forces applied to various p oints on a skeleton More to the p oint it must also include some unknown constraining forces which prevent the applied forces from violating the constraints imp osed on the system In general the net force is considered to b e a sum of known applied forces and of unknown constraint forces g ga gc Substituting this into the constraint condition yields the linear system of equations
Jc Kgc Jc Kga in which only the constraining generalized force vector gc is unknown
Equation simply states that an appropriate constraining force is one which when added to the applied forces causes the constraint derivatives to b e zero But this is to o ambiguous since the system is usually underconstrained and there may b e many constraining forces gc which satisfy equation One approach to removing this ambiguity is to insist that the constraint force must lie in a direction in which the system may not move just as the constraining force of Figure do es Recalling the discussion in Chapter ab out the Singular Value Decomp osition SVD this implies that the constraint force must lie within the range of the constraint Jacobian matrix Jc Thus for constrained systems in general the constraint force gc is restricted to lie in the range of
Jc KJc
Jc Kga
and solved for the vector of Lagrange multipliers Once the Lagrange multipliers are known the constraint force which removes the illegal comp onents of the applied force is computed as
gc Jc
this restriction follows from the principle of virtual work Pau
for some vector
Therefore equation
CHAPTER INCORPORATING CONSTRAINTS
Note that computing gc requires the solution to a linear system of equations even though the constraints themselves may b e nonlinear
Solving for Lagrange Multipliers
The linear system must b e solved to nd the Lagrange multiplier vector
m
Note that the numb er of equations in the system is equal to the dimension of the constraint vector C Any metho d for solving sets of linear equations can b e applied here
A metho d recommended here to solve the system emphasizes robustness over sp eed Due
to the
structure of most articulated skeletons it is imp ossible to avoid illconditioning in all of the
time Mac To cop e with this the system is solved using the truncated SVD of the lefthand
T
m m matrix Jc KJc
is formed from the original SVD by zeroing any small singular values which eectively throws
This term eectively the magnitude of the
adds a p enalty spring to the system the constraint deviation C
strength
of which is
Overview
combined with a backsubstition algorithm PFTV The truncated SVD
away any illconditioned comp onents of the matrix PFTV MK This
not take advantage of any sparsity in the matrix but has the advantage of b eing robust in cases where illconditioning o ccurs
Feedback
The discussion so far has b een based on the assumption that the constraints are initially satised and that they remain so To handle cases in which the initial state violates some constraints or where numerical inaccuracies cause constraint violations an additional feedback term is added to the basic equation of motion
q Kga gc kCJc
T
prop ortional to
Equation is the complete simplied equation of motion for a constrained system Constraints are maintained by evaluating the right hand side of the equation using the metho ds outlined in the sections ab ove to nd the state variable velo cities q A single integration step then yields a new state q which resp ects any constraints imp osed on the system In an interactive setting the pro cedure iterates as the user applies changes to the system state through the user interface Screen up dates o ccur after each iteration to provide feedback Figure provides an overview of the pro cedure
solution metho d do es
CHAPTER INCORPORATING CONSTRAINTS
for a single iteration Note that equation is a generalization of the Jacobian transp ose metho d of chapter in the absence of any constraints on the system the equation reduces to the simple formula intro duced earlier
Implementation Issues
The basic constrained equation of motion has a regular structure which lends itself to an ob ject oriented implementation A solver for the equation only needs to know a few things the length and value of a global state vector q how to evaluate a numb er of functions of q and how to evaluate a matrix of partial derivatives with resp ect to q for each of these functions
Using software ob jects which resp ond to sp ecic requests to provide these pieces of information a generic constraint solver can b e written which is insulated from the sp ecic details of articulated skeletons The solver queries these ob jects to obtain the information it needs to assemble a global system of constrained equations of motion solves the system and then communicates the results back to some of the ob jects Implementing this metho d of maintaining constraints requires three dierent typ es of these ob jects skeletons hand les and constraints
Skeletons as Ob jects
Each skeleton is considered a single ob ject which contributes variables to the solvers global vector q Each skeleton must b e able to resp ond to requests for sp ecic pieces of information that the solver requires In addition a metho d must b e provided by which the solver can communicate a solution back to the skeleton If each skeleton provides these capabilities the solver do es not need
to know anything ab out the internal structure of the skeleton itself The
state
solver must b e able to
query a
query a
query a
send a skeleton a new state vector
skeleton skeleton skeleton
for the length of its state vector for its state variable vector
for its scaling matrix K
reecting the solution
A hand le is an abstraction representing a geometric quantity associated with a skeleton whose value
Handles on Skeletons
dep ends on the skeletons internal state
of a joint within the skeleton or as complex as the lo cation of the skeletons center of mass Handles are the geometric entities up on which constraints may later b e imp osed and to which forces may b e applied
A handle can refer to something as simple as the p osition
CHAPTER
INCORPORATING
Manipulate skeleton
g a
CONSTRAINTS
Specify constraints
Compute constraint
Jacobian
J c
Solve for
Lagrange multipliers λ
Compute constraint force
g c
+
q ́
∫
q
Compute feedback term
Figure
Iteration
steps for maintaining constraints
CHAPTER INCORPORATING CONSTRAINTS
Each handle attached to a skeleton knows how to compute a function of the skeletons state hq sk eleton A numb er of handle typ es can b e dened each computing a dierent quantity These might include
A point hand le which computes the global position of some point dened within a local joint co ordinate system eg a p oint on the left shin inches b elow the knee
An orientation handle which computes the global orientation of a local joint coordinate system
A centerofmass hand le which computes the global position of a skeletons center of mass computed as a weighted average of each b o dy parts center of mass
Usually a single handle will dep end on only a subset of the joints within a skeleton When queried for its state vector a skeleton should return only those elements of q skeleton which are referenced by a handle This will keep the total numb er of variables in the constrained system to a minimum
In addition to the function hq sk eleton each handle must also know how to compute the Jacobian
matrix Jh
Constraints on Handles
Constraints can b e applied to the quantities computed by a handle The simplest constraints are those that constrain a handle to a geometric constant Useful examples of this include
matrix J qskeleton h
h qskeleton
The constraint solver will query each handle for this information when assembling the global constraint Jacobian matrix Jc Implementing a new handle typ e is straightforward requiring only handlesp ecic routines to b e co ded These routines are resp onsible for initializing the handle computing the handle function h and computing the handles Jacobian
constraining a
constraining a
constraining a
constraining an orientation handle to a given orientation
can b e also b e clasp ed b etween
environment For o or or the hand constraints could created b etween two handles For example a gures hands could b e constrained to stay together by creating a p oint handle on each hand then sp ecifying an equality constraint
p oint handle p oint handle p oint handle
to a given lo cation to a plane
to a line
These simple constraints would b e useful for sp ecifying interactions with a static example the feet of a gure can b e constrained to lie in the plane dened by the
constrained to the rung of a ladder To sp ecify more complex b ehaviours
these two handles
CHAPTER INCORPORATING CONSTRAINTS
Each constraint computes a function ch hn where the input values are the outputs of one or more handles These constraint functions are usually quite simple often reducing to just a variation of the distance formula In addition each constraint must b e able to compute its Jacobian matrix with resp ect to its inputs c Adding a new constraint is just a matter of writing co de to
h
evaluate these two items Geometric constraints are for the most part simple enough that this is a
minor amount of work
The Global Picture
An application sets up constraint problems by creating handles on skeletons imp osing constraints on these handles and applying forces to them b efore invoking a solver to evaluate equation But adding the constraint enforcement scheme of Section to an interactive program is not quite straightforward A user should b e able to interactively imp ose temp orary constraints on a gure while editing its p osture Over the course of a normal work session numerous constraints may b e created and deleted as the work pro ceeds So the system b eing simulated by equation is
constantly changing each time a constraint is added new handles may b e referenced and new variables intro duced It is not p ossible to determine b eforehand the correct set of equations to b e simulated and to simply hardwire the co de to do so Instead some sort of mechanism must exist for assembling and evaluating the system of equations on the y based on the current set of active
constraints The constraint solver
ow network which represents the
are completely determined by the networks conguration The dataow network scheme has b een describ ed by Witkin AW and explored more fully by Kass Kas
itself can b e made resp onsible for this It will maintain a data system b eing simulated the equations of motion for the system
The solver is resp onsible for assembling and solving the global constrained system of equations taking an integration step and communicating new state information back to each skeleton ob ject It also handles any b o okkeeping required to map lo cal skeleton variable indices to global indices As an application adds constraints to the system the dataow network within the solver is up dated The network consists of a set of function blocks with outputs of some blo cks feeding into the inputs
of others
Jacobian
the result of multiplying the lo cal Jacobian matrix by an incoming Jacobian matrix thus applying
Each blo ck computes two items a function of the blo cks inputs f x and the lo cal
matrix of that function with respect to its inputs f The block outputs f x as well as x
state
the chain
rule Figure depicts a typical function blo ck
constraint and each handle within the system contribute a single function blo ck to the At the top level the inputs of a constraint blo ck are wired to the outputs of one or more handle blo cks or in the case of simple constraints directly to constant values At the b ottom level the inputs to each handle blo ck are connected directly to elements in the global state vector q As
Each network
CHAPTER INCORPORATING CONSTRAINTS
f(x)
∂f ∂q
∂x ∂q
f
x
Figure A generic function blo ck
constraints are created and destroyed no des are added to and deleted from the network which is rewired to reect the change
When the solver is invoked it consults the top level of the network to determine the global constraint vector C as well as the constraint Jacobian matrix Jc The constraint vector C is formed by simply instructing each top level no de to evaluate its function and concatenating the results Each no de recursively instructs its inputs to evaluate themselves b efore computing its own function The recursion b ottoms out at the lowest level when it reaches the state variable values q Each no de caches its last computed value in case it is needed again
A similar recursive scheme is used to compute the global constraint Jacobian matrix Jc Each top level constraint no de computes its own lo cal Jacobian matrix with resp ect to its inputs then applies the chain rule by multiplying this against the Jacobian matrix of each of its inputs with resp ect to the state variables see Figure The solvers recursion scheme takes care of the mapping b etween lo cal and global indices as well as the allo cation of temp orary memory for intermediate matrices Matrix sparsity is preserved and exploited to reduce computation and caching is again used to avoid duplicate computations
The dataow network provides the exibility required to supp ort the interactive restructuring of a simulated system One attractive feature of this organization is that implementing new classes of handles and constraints is particularly simple All that is required is to implement the two routines required by a function blo ck since this is all the solver needs as it traverses the network
CHAPTER INCORPORATING CONSTRAINTS
An Example
Consider the problem of constraining the tips of a gures hands to its hips This can be accomplished
by rst creating
four p oint handles on the gure
handle
handle
handle
handle
h on the h on the h on the h on the
tip of the right hand right hip
tip of the left hand left hip
To x the hands to the hips two equality constraints on these handles are created
c h h
c h h
Figure shows the resulting dataow network constructed by the constraint solver Each handle references a few variables within the skeletons state vector these variables are concatenated to
form the
and feed the results to the constraint function blo cks These compute the distances b etween the
global state vector q The handle function blo cks compute their resp ective p oint lo cations
p oints and the blo ck function outputs are concatenated to form the element global
incoming
constraint vector C Each blo ck also computes its own lo cal Jacobian matrix with resp ect to its inputs multiplies it with an incoming matrix and passes the result along The matrix outputs of
the constraint blo cks contribute sparse rectangular blo cks to the global constraint
Jacobian Jc
Any time an element of q changes value a disable cache signal is triggered on any handle blo ck connected to the element This signal p ercolates up through the network forcing any blo ck that is encountered to discard its cached data The next time the solver evaluates the network only these blo cks will recompute their outputs When the network has b een reevaluated the solver has all the information it needs to evaluate equation
Summary
pro cedure has some attractive characteristics
maintained exactly since any forces acting on
are removed The pro cedure is quite general as well constraints and
for this example two sets of x y and z scalar constraints
This constraint enforcement
straints can theoretically b e
cause a constraint violation
handles can be arbitrarily complex functions and are therefore not restricted to referring to geomet ric quantities alone The dataow network architecture is extensible since adding new handle and constraint typ es is simply a matter of writing a handful of functions
Most imp ortantly con the system which would
CHAPTER INCORPORATING CONSTRAINTS
C
Jc
c1
c2
h1
h2
h3
h4
q
Figure Example network
CHAPTER INCORPORATING CONSTRAINTS
The main drawback to the approach is that the solution cost is dominated by the On cost of solving a linear system for the Lagrange multipliers of which there is one for each of n scalar constraints in the system b eing simulated For even a few simple geometric constraints the solution time at this b ottleneck quickly degrades to the p oint where interaction b ecomes dicult But Surles Sur has shown that when constraints are applied to articulated structures with sp ecic charac teristics the resulting system of equations can b e solved in linear time under certain conditions This result is promising but is recent enough that it has not b een pursued for this thesis
A sample implementation of the metho d outlined ab ove b oth conrms its p otential as well as the limitations imp osed by the b ottleneck Retaining interactive up date rates for any reasonably complex skeleton with just a few p osition and orientation constraints applied is dicult given current CPU p erformance Simple Euler integration not surprisingly intro duces numerical instabilities due to cumulative errors when the integration stepsize is large enough to provide reasonable interactive
either since it to feel implies that some steps will b e thrown away entirely retain accuracy As a result one iteration may take much longer to complete than another so screen up dates o ccur at irregular intervals and consequently the interface is p erceived as b eing jerky and unresp onsive However these are problems which will disapp ear as CPU p erformance improves to the p oint where accuracy in the solution can b e
maintained at interactive up date rates
Another source of p otential stability problems is the feedback term of equation This term
feedback Adopting more robust adaptive integration metho ds is not
These metho ds typically require multiple evaluations of equation p er iteration and
is so exp ensive to compute the refresh rate unresp onsive In addition adaptive stepsizing when the stepsize must b e reduced in order to
drops dramatically and the interface tends
suers from the usual
constant k leads to a
noticeable constraint
currently done purely
ie k is small with the assumption that as CPU p erformance improves it will b e p ossible to p erform enough iterations b etween screen up dates to eliminate any noticeable constraint violations Trying to eliminate the inevitable drifting of a system away from its constraints a result of numerical inaccuracies by using a high spring constant is almost sure to intro duce severe stability problems
problems asso ciated with springbased constraint enforcement a high spring sti set of equations which are unstable while a low value for k p ermits violations Cho osing a go o d spring constant value can b e dicult and is on a trialanderror basis Ideally the feedback spring should b e a lo ose one
Given current CPU sp eeds this technique seems b etter suited to solving constraint problems oline than in an interactive setting Our goal is to develop immediately useful interactive to ols for working with nontrivial skeletons and this metho d cannot b e considered practical yet for this
necessarily helpful
CHAPTER INCORPORATING CONSTRAINTS
purp ose on mo destly p owered workstations Instead we will consider a p enaltyforce metho d based
on the CCD algorithm as a substitute with which we can exp eriment
A CCDbased Penalty Metho d
in an interactive editor
The previous metho d is capable of handling multiple constraints imp osed on dierent parts of a skeleton To accomplish the same with the CCD metho d requires some slight mo dications to the basic algorithm presented in Chapter Whereas the basic algorithm considered just a serial chain of links and a single goal solving for multiple constraints means we must also consider branches in the manipulator and more than one goal as shown in Figure
The scheme of Chapter solved the problem for a serial chain by traversing from the endeector in towards the base at each joint adjusting the joint parameter to minimize an error measure derived from the current endeector p osition and a known goal In a branching chain with multiple end eectors and multiple goals a joint may contribute to the p osition of more than one endeector so p otentially more than one goal must b e considered when varying the joint variable Also the
algorithm dep ends on the inward proximal one can b e considered
traversal scheme distal This precludes treating
solved sequentially
A recursive traversal of the
problems at a joint are solved
children to solve for any constraints that may b e applied to endeectors in their subtree Then the joint variable which minimizes the summed error measure from each child subtree can b e computed The only change from the previous CCD algorithm is that the traversal must now consider branches
A
B
Figure A branching chain with two endeector constraints
singlegoal problems which can
b e
joints must b e solved rst b efore a more the multiplegoal problem as a series of
hierarchy from the leaves in towards the ro ot ensures that all sub b efore the joint itself is considered Each joint instructs all of its
CHAPTER INCORPORATING CONSTRAINTS
in a chain and that the error measure equation of Chapter Xn
b ecomes
a summation
E q
Ep i q Eo i q
i
over the n constraints which are distal to the current joint The net eect of this change is that the coecients k k and k must be computed by summing equations over each distal
computed The constraints have b een satised or until successive iterations pro duce negligible changes indicating that the constraints are conicting and cannot b e
simultaneously satised
This recursive scheme resembles Badlers early heuristic approach BMW for p ositioning a gure with multiple constraints although the CCD metho d for computing a minimizing change in a joint variable app ears to dier from the one used there
This p enalty metho d approach is arguably inferior to the more comprehensive scheme outlined previously Constraints are only approximately enforced so we can exp ect to see some drift on segments that are constrained to stay in place Also we are restricted to geometric constraints due to the CCD metho ds reliance on geometric relationships alone Nevertheless the metho d is
endeector goal b efore a minimizing change in the current joint variable can b e
pro cedure must iterate until either all endeector
usually stable
exp erimenting
instabilities do o ccur when p osition and orientation constraints conict with each other but this can b e alleviated with appropriate weighting factors on the individual constraints
enough to p erform adequately at interactive up date rates and gives us a means of with constraints within our interactive editor In our prototyp e implementation
Chapter
An Interactive Editor
To place the discussion of the preceding chapters in context an interactive program for animating articulated gures is intro duced here The program is designed to create keyframed motion sequences
for arbitrary skeletons
in this thesis Both the Jacobian transp ose and the CCD metho ds have b een implemented and
and has b een b oth a motivation and a testb ed
for the ideas develop ed
the application interface mo died to accomo date direct inverse kinematic
constrained manipulation This chapter briey describ es the program and the manipulation interface
A System Overview
The Sequence Editor is an interactive to ol for creating and editing keyframed movement sequences for a single arbitrary skeletal gure Its primary function has b een to act as the movement creation window of a motion planning package CWGL for choreographers whose needs are quite dierent from those of computer animators To a typical user planning the movement of multiple gures in a work space a rough approximation of a movement that can b e created quickly can b e more valuable
than a more realistic
has favoured ease of use over functionality The hop e is that direct manipulation and constraint satisfaction based on the metho ds of the previous chapters can improve the quality of movement created with the editor while retaining a simple and intuitive user interface
Before describing the interface itself some of the terminology warrants a brief explanation
Skeletons
The program itself knows nothing ab out skeletons sp ecically a skeleton app ears as an abstract data typ e supp orted by a to olkit library of routines The to olkit supp orts the creation manipulation and
animation that would take hours to p erfect Consequently the programs design
manipulation as well as
CHAPTER AN INTERACTIVE EDITOR
animation of skeletons dened by a simple ASCI I le format Figure shows a sample description
for a simple approximation to a human gure Any editor and animated
valid skeleton description can b e read in to the
As the example shows each skeleton is simply a collection of named joints arranged in a hierarchy The joints are either rotary or prismatic each with a single degree of freedom Comp ound joints with
multiple degrees of freedom eg ballandso cket
joints sharing
the joint typ e
of movement
These rigid ob jects comprise the appearance of the skeleton and are drawn as they are encountered during a display traversal of the hierarchy
A skeleton maintains an internal state vector q consisting of all the joint variable values as well as a translation vector for the skeleton as a whole This information is enough to completely dene the lo cation and shap e of the skeleton for a single frame An application can animate a skeleton by
the same lo cation Asso ciated with
each joint are a numb er of attributes
axes of freedom and lo cal limits on the range
rotary or prismatic the lo cal axis of the joint Polygonal ob jects may
be attached to any joint node in the
hierarchy
rep eatedly loading the skeleton state q and instructing
The to olkit now supp orts inverse kinematic control
to identify b oth a base and an endeector within the joint hierarchy A desired p osition andor
orientation for the endeector may then b e sp ecied and the skeleton
inverse kinematic problem using either of the metho ds of the previous chapter The internal state q
is automatically up dated to reect
the details of the inverse kinematic algorithms
can b e mo delled as a series of these single DOF
the skeleton to display itself
over a skeleton by allowing the application
the solution to the problem This isolates the application from
The Sequence
A sequence is an abstract data typ e
of a skeleton over some p erio d of
skeleton state at any frame of the animation Although a sequence could
motion mo del for this discussion a sequence will b e dened as a series of keyframed p oses each of which sp ecies the state vector q at a particular frame When a sequence is queried for the skeleton state at a frame b etween key frames an interp olated state is computed onthey and returned For each rotating joint either linear or splined quaternion interp olation Sho may b e p erformed For each translating joint either linear interp olation or generalized CatmullRom spline interp olation KB may b e used Currently no further control over the interp olation pro cess is provided other
for storing skeleton animation data it represents the movements time An application may query a sequence to determine the encapsulate a pro cedural
instructed to solve the
including
courtesy of Phil Peterson
a quaternion is a compact representation for rotations with some app ealing prop erties
CHAPTER AN INTERACTIVE EDITOR
# Example .scr file for a stick figure.
define skeleton “stickman” joint “pelvis”
group “Upper body” joint “torso”
group “Right Arm” joint “right arm” joint “right hand”
end group
group “Left arm”
joint “left arm”
joint “left hand” end group
joint “head” # “head” is a child of “torso” end group
group “Right leg” joint “right leg” joint “right foot”
end group
group “Left leg”
joint “left leg”
joint “left foot” end group
end skeleton
right arm
right hand
right leg
right foot
head
torso
pelvis
left arm
left hand
left leg
left foot
define joint “right leg” object “r_lleg.pol” offset 0 −0.32 0 hinge x 0 170
mass 1 orientation 0 0 0 mirror “left leg”
end joint
Figure Sample skeleton description
CHAPTER AN INTERACTIVE EDITOR
than that aorded by changing the keyframe spacing or the key p oses
A numb er of simple editing op erations are dened for keyframe sequences Ranges of keyframe p oses may b e copied inserted andor deleted Keyframe spacing may also b e adjusted by stretching shrinking or sliding moving a range within the sequence This provides some crude control over timing
The Editor
An interactive editor for creating and editing animation sequences for arbitrary skeletons is shown
in Figure The current skeleton is displayed in
view Each of these views may o ccupy the large
manipulated Existing sequences are group ed into menus and displayed in iconic form to the right
three orthogonal views and a
main work area in which the skeleton may b e
single p ersp ective
Figure Sequence editor screen
of the screen Each sequence
a simple ipb o ok preview of the movement as a memory aid A sequence
icon can cycle through all of the keyframe p oses on request generating can b e named and added menu item can later b e reloaded for editing A small display b eneath
to one of these menus and a
the main viewp ort shows the keyframe p oses within the loaded sequence
These are laid out along
CHAPTER AN INTERACTIVE EDITOR
a timeline to indicate the keyframe spacing A set of VCRlike transp ort controls are provided for playing back the animated sequence in the main display area
The small timeline provides a convenient interface for copying cutting and pasting ranges of keyframes within a sequence as well as mo difying the keyframe spacing But the key p oses them selves must b e created or mo died by adjusting the skeleton displayed in the main window For manipulating the skeleton forward kinematic controls are provided in the form of sliders for adjust ing individual joints within the skeleton one at a time In addition the interface has b een mo died to p ermit inverse kinematic manipulation of the skeleton In this mo de the user may use the metho ds
presented in the previous chapter to up date multiple joints
implementation of this interface for direct manipulation is briey describ ed b elow
Direct Manipulation
With direct manipulation the user adjusts the skeleton by selecting and dragging a b o dy part rather than adjusting individual joints A dragging session b egins when a b o dy part is selected with the mouse and ends when the mouse button is released Dragging is a p ositioning mechanism only it do es not directly control the orientation of the selected part To supp ort dragging the interface must provide a way of identifying a serial chain of joints within the skeleton which will b e considered
a manipulator as
well as
a way of unambiguously sp ecifying endeector goals for the chain
Identifying the Chain
A chain of joints
b oth a base joint
hierarchy is traversed backwards from the selected part towards the ro ot Three mo des control how far up the tree this traversal pro ceeds b efore stopping at a
within the skeleton is dened when a b o dy part is rst selected at which time
and an
endeector must b e determined To determine a base joint the skeleton separate interaction joint which b ecomes
the base of the chain The
stop
stop
stop
The rst of these
equivalent of p ositioning the part using the forward kinematic slider controls The second results in a chain which extends from the nearest branch in the hierarchy and is therefore a useful default to use when dragging limbs Selecting and dragging a hand for example would move the entire arm without disturbing the torso The third interaction mo de p ermits the user to override these default
when the parent
when the parent
when a named joint is reached
stopping criteria corresp onding to each of the three joint has a b o dy part attached to it
joint has multiple children
dragging mo des are
results in only the selected b o dy part b eing dragged and is the direct manipulation
by dragging one b o dy part around The
CHAPTER AN INTERACTIVE EDITOR
b ehaviours by explicitly naming a joint from which the chain extends
torso of the
In p oint
a user
p oint on the b o dy segment underneath the cursor by casting a ray and intersecting it with the ob ject The alternative is to predene lo cations within the skeleton which may b e selected for dragging the lo cations of the joints themselves for example This requires either that the lo cations b e displayed in some iconic form so the user can select one or that the cursor warp to the nearest one when the
joint as the chain base for example in which spine
case pulling on the
addition to the base of the chain the endeector p osition must
b eing dragged There are two p ossible approaches to determing the endeector lo cation when
p oints at a b o dy segment and presses the mouse button The rst is to explicitly compute the
mouse button is pressed
a point on the surface of the ob ject and making that point the location of the endeector frame This gave mixed results On one hand it allowed the user to click anywhere on the ob ject for dragging without any disconcerting cursor warping On the other hand having the endeector frame located on the ob ject surface often resulted in unexpected twisting of the segment especially
must resolve the ambiguity in here is to cast a ray through is closest to the endeector technique provides reasonable
mapping a the cursor This p oint
b ehaviour
D screen lo cation to a D lo cation The solution adopted into the world and to nd the p oint on this line which b ecomes the goal p osition for the current iteration This
in b oth orthographic and p ersp ective views
The initial decision was to cho ose the former metho d explicitly computing
with the Jacobian metho d As a compromise the current implementation halfway along the segments axis of selfrotation warping the cursor to the lo cation Lo cating the endeector along the segment axis eliminates the twisting
places the endeector corresp onding onscreen problem of unexp ected
Determining an EndEector Goal
To compute new goal p ositions for the endeector as the cursor moves around on the screen we
With an orthographic pro jection the cast ray is parallel to the line of sight and the closest point
on the line will lie in the plane p erp endicular to the ray and
the endeector is constrained to lie within the plane while
pro jection view the cast ray may diverge from the line of
endeector to the ray is no longer constrained to lie parallel to the image plane The endeector is therefore free to move in any direction and may even b e pushed and pulled towards and away from the viewer with a little practice Figure illustrates the case for b oth p ersp ective and orthographic pro jections
Thus the user can
arm would result in a b end
b e known since that is the
containing the endeector In this case it is dragged around In a p ersp ective sight and the shortest path from the
sp ecify a
CHAPTER AN INTERACTIVE EDITOR
goal
goal
(a)
(b)
Figure Plan view of goal determination in a an orthographic view and b a p ersp ective view
Once the new goal p osition for the endeector has b een computed the skeleton is instructed to solve the inverse kinematic problem the user can select the solution metho d to use by setting
a program option The screen is refreshed and the cursor lo cation resampled after
to provide resp onsive feedback Of course when a single iteration is insucient to solve the most recent problem the movement of the skeleton lags b ehind the cursor In practice this small tracking delay has not b een a problem
To provide some control over the resp onsive b ehaviour of the skeleton the user can interactively
mo dify metho d of a set
weighting parameters at each individual joint This is particularly useful when the CCD is used allowing a the resp onsiveness of a chain to b e varied from that of a sti ro d to that of lo osely coupled links
Constraints
As an
apply
in place while the p ose is b eing edited Currently constraints are enforced by iteratively
set of p ersistent inverse kinematic goals using the CCD metho d This restricts us to a set of simple geometric goals
Lo cking an endeector p osition
Lo cking an endeector orientation This can b e a partial lo ck of only one or two directions
eg lo ck Y orientation only
additional p ositioning aid a small set of constraints have b een dened which the user may to any segment of a skeleton The most useful of these are intended to lo ck limb extremities solving a
each iteration
CHAPTER AN INTERACTIVE EDITOR
A weighted combination of b oth of these
Constraining an endeector to lie within a plane
To apply a lo ck the user selects a segment then makes a lo ck selection from a menu Once created
a lo ck remains in place until it is explicitly deleted A lo ck can b e edited to change either its imp ortance weighting or the joints which can contribute to maintaining the lo ck The lo ck or orientation can also b e mo died by either dragging the lo ck or twisting the endeector a set of sliders
typ e its lo cation through
The intent is that lo cks represent constraints which are to b e maintained during any subsequent p ositioning of the gure To achieve this after each editing op eration of a gure whether through direct manipulation or the forward kinematic slider controls a numb er of iterations of the multiple goal CCD solver are p erformed prior to each screen refresh When the numb er of iterations p erformed is insucient to satisfy any constraints violated by the editing op eration some drifting from the lo ck
constraint p ositions is unavoidable
all constraints are met to the users
p erformed b etween screen refreshes
minimize visible constraint violations on a lowp erformance the resp onsiveness of the interface at the cost of constraint
Lo cking constraints are particularly useful when applied
the example of Figure the gures feet are
p osition and orientation The rst image shows
second image the p elvis has b een tilted to lean the gure and
applied to the p elvis In all three images the fo ot p ositions and orientations are maintained and the CCD solver is fast enough that the p elvis can b e tilted and twisted interactively without noticeable sliding of the feet For this example iterations b etween screen refreshes were sucient to maintain the constraints with negligible drift and provide an up date rate of frames p er second on a Silicon Graphics R Entry Level Indigo workstation This up date rate is inadequate for animation but quite sucient for interactive p ositioning
While lo cking endeectors in p osition is useful for creating a series of consistent keyframe p oses there still remains the problem of maintaining the constraints at the interp olated inb etween frames
But a button is provided for invoking the solver explicitly until satisfaction The user may also change the numb er of iterations
On a highp erformance
machine this numb er can b e set high to machine a smaller numb er can improve violations b ecoming more noticeable
in the third image a twist has b een
constrained the p osition
to the supp orting limbs of a gure In to stay in place by lo cking b oth their at which the lo cks are created In the
There is no guarantee that an endeector lo cked to some p osition
remain in that p osition if joint angles are merely interp olated b etween
the problem The rst and last images are keyframes in which the
the same p osition and orientation The image in the middle is the result of interp olating joint
in two adjacent keyframes will the p oses Figure illustrates feet have b een constrained to
CHAPTER AN INTERACTIVE EDITOR
Figure A gure b eing p ositioned by rst tilting then twisting the p elvis
angles b etween the two p oses
the keyframes The problem
relationship b etween the rate
at which the leg joint angles
rearrange the hierarchy to ro ot it at one of the feet but this would only alleviate the problem for that fo ot rearranging the hierarchy is not helpful when multiple endeectors are constrained
the feet clearly move through the o or during the transition b etween is that the gures hierarchy is ro oted at the p elvis and there is no at the which the p elvic translation is b eing interp olated and the rate need to change to maintain the fo ot p ositions Of course we could
In the current implementation the only attempt made to address this problem is to provide an option to enable constraint satisfaction during interp olation Each frame is computed as usual by interp olating joint angles then the CCD solver is invoked until any violated constraints have b een resatised In essence a series of singleframe constraint problems are solved This approach is admittedly ad hoc and it is not clear yet how well it will work it app ears adequate for the few situations tested so far although interp olation can no longer b e p erformed onthey
Initial feedback suggests that even this simple approach to enforcing geometric constraints com bined with direct inverse kinematic manipulation is a signicant improvement to the keyframe editor
CHAPTER AN INTERACTIVE EDITOR
Figure a First keyframe p ose b Interp olated p ose c Second keyframe p ose
Chapter
Conclusion
Summary
We have examined solutions to the inverse kinematic problem applied to manipulating articulated skeletons in an interactive keyframe animation editor As alternatives to previously published algo rithms in the graphics literature a pair of simple algorithms have b een describ ed which can provide relatively inexp ensive direct manipulation of a gure The rst of these is really just an application of a simple minimization metho d but its application to inverse kinematics has not previously b een made explicit The second is a new heuristic algorithm adopted and mo died from the rob otics liter ature The advantages and disadvantages of each have b een discussed and their relative p erformances gauged
Metho ds by which each algorithm can b e used to
b een develop ed and their resp ective advantages and disadvantages discussed An implementation of the simpler approach has b een incorp orated into a keyframe editor and the interface briey describ ed
As a bypro duct a to olkit library for dening and manipulating skeletons has b een implemented which insulates an application from the details of creating editing drawing and animating a gure A skeleton is also able to solve inverse kinematic problems p osed by the application allowing the application to deal with interface issues rather than dealing explicitly with inverse kinematic algo rithms This also allows new inverse kinematic solution metho ds to b e implemented and added to the to olkit without requiring mo dications to the application
satisfy constraints during manipulation have
CHAPTER CONCLUSION
Results
exp erimenting with several inverse kinematic metho ds in the course of this work some things
After
have
typ e or another no one approach seems uniformly sup erior
should not necessarily b e considered any b etter than other approaches but rather provide alternative approaches which may b e suitable in some applications
b ecome apparant The rst is that inverse kinematic
algorithms all exhibit problems
to others The metho ds presented here
The second p oint is that inverse kinematics as a p ositioning to ol is a useful complement to but not a replacement for simple forward kinematic p ositioning In particular for direct manipulation inverse kinematics is really only useful for chains with relatively few degrees of freedom single limbs for example In fact an interesting observation is that even with the ability to drag multiple jointed chains around many users of the editor describ ed in Chapter seem quite content with the default dragging mo de which drags just a single b o dy part Informal feedback from users suggests that while direct manipulation is a huge improvement to the interface over the previous sliderbased p ositioning the value of multiplejoint p ositioning is not quite so clear In fact trying to p osition a chain with many degrees of freedom with direct manipulation is often likely to cause unwanted changes to the skeleton For example trying to b end the spine of a gure by pulling on its ngers is probably asking to o much in the absence of additional constraints sp ecifying how changes should b e distributed among the joints any metho d is likely to give unnatural results Joint limits provide some constraints as do the weighting parameters at each joint but these do not seem to b e adequate particularly for manipulating recognizable b o dies Inverse kinematic metho ds which
p erform quite acceptably for disemb o died
chains or mechanical rob ots do not necessarily often app ear unnatural This problem is that
translate
well to animate gures
unnatural is sub jective and dicult to
result from considering these factors more carefully
the results can
the term quantify More p owerful p ositioning to ols are likely to
Either of the inverse kinematic algorithms presented in Chapter is adequate for interactive direct manipulation They are b oth simple to implement and are fast enough to provide go o d feedback
for gross p ositioning tasks However if high accuracy is a requirement and interactive not so much of a concern then other solution metho ds may oer b etter p erformance
Comments ab out Constraints
resp onse time
In Chapter the choice of the CCDbased p enalty metho d for implementation within the gure animation editor was largely based on p erformance issues the alternative Lagrange multiplierbased approach was deemed to o demanding for interactive use on a typical workstation This problem is temp orary however and it is worth reconsidering the decision in light of continuing increases in
of one
CHAPTER CONCLUSION
CPU p ower At the same time we can sp eculate a little useful to develop and how constraints might b e used for
ab out what typ es of constraints might b e
Given sucient CPU sp eed to retain numerical stability the Lagrange multiplier approach is the more general of the two The CCDbased metho d is fast b ecause it reduces a dicult problem to a series of simpler ones which can b e solved analytically using only simple geometric quantities But for problems more complicated than solving p osition and orientation constraints the reduction to analytical form is not always p ossible so the approach is limited to these typ es of constraints In contrast the Lagrange multiplier metho d could b e used to enforce many dierent typ es of constraints
including nongeometric ones the only requirement is that the constraints b e joint variables within a gure
Lo oking Ahead
some function of the
useful for gure ma the animation editor To o often a solution correct in the sense that all geometric constraints are satised seems incorrect b ecause it gure into an awkward lo oking p ose Think for example of a p erson going from a standing into a crouch The natural tendency is for the knees to move apart as the p erson crouches that is the comfortable way to crouch To manipulate a standing gure in the editor into a crouch one might lo ck the to es of each fo ot in place and then pull the p elvis down to make the gure crouch But without any other information ab out how the legs should move one is just as likely to see the knees move together as the gure crouches as to see them move together Perhaps this could b e rectied by sp ecifying additional geometric constraints on the knees but cho osing and sp ecifying these auxiliary constraints would probably b e dicult and timeconsuming A useful alternative
would b e a standard set of constraints which applied to the gure at all times
constraints to avoid uncomfortable p ostures or p ostures which would place a p erson obalance The latter can b e implemented as a constraint on a gures centerofmass a computable quantity given a set of joint angles while the former would require some function which measured comfort or naturalness given the same set of variables
In addition to manipulation constraints could also b e useful in animating a gure A natural place to start would b e to consider animating the constraint values Animating a p osition constraint for example might dene a tra jectory for some limb extremity to follow A simultaneous animated orientation constraint would control the orientation of the extremity as it traversed the tra jectory
What sorts of constraints other than the obvious geometric ones might b e nipulation Initial exp erimentation with the constraint solver implemented in indicates that geometric constraints alone while useful are not always enough
which is puts the p osition b ecause
But for complex motions constraints will probably b e more helpful in describing a desired
with some sort of scripting approach For example the movements of the supp ort fo ot of a walking
animation as
well as manipulation
These might include
movement
CHAPTER CONCLUSION
bip ed might b e describ ed in terms similar to the following
After heel strike the heel of the fo ot maintains its
touches the ground For a short p erio d the entire fo ot
b o dy moves forward Toward the end of the step the heel of the fo ot breaks contact with the ground rst followed shortly after by the ball of the fo ot
A description
movement If the description were more sp ecic ab out the time intervals and lo cations involved we
such as this identies a numb er of simple constraints which are in eect during the
would have a
language could b e implemented which would allow movements such as this to b e describ ed textu ally A script would need to sp ecify a set of constraints to b e imp osed and provide some way of activating and deactivating these constraints over the course of a movement An interpreter for such a descriptive scripting language would b e a useful to ol for gure animation
Directions
There are plenty of problems still to b e addressed At a low level of detail it is worth determining whether the p erformance of the Lagrange multiplier constraint satiser can b e improved up on First Surles has shown that some constraint problems for articulated gures can b e solved in linear time Sur He lists a numb er of prerequisites for this but in the context of chemical protein mo delling which is his application area An analysis of these prerequisites and what they mean in the context
fairly detailed script for animating the stance fo ot during a walk A simple scripting
of articulated skeleton manipulation would
sp eed up the solution pro cess is to consider
SVD MK the referenced pap ers on this
approaches to the inverse kinematic problem in general
p osition until the ball of the fo ot
remains lo cked in
place while the
b e useful A second area which could b e explored to Maciejewskis incremental algorithm for computing the topic are interesting reading and may suggest alternate
Designing interactive interfaces which make eective use of constraints is challenging and deserves
some
when
time What ab out constraints involving multiple gures
attention How should constraints b e represented Selected Edited What should happ en constraints conict with each other How should constraints b e animated and controlled over
And nally do inverse kinematics and constraints provide a convenient layer up on which higher level pro cedural motion mo dels can b e built An interesting exercise would b e to extend Bruderlins walking algorithm to handling uneven terrain making use of the basic techniques describ ed in this thesis to achieve and maintain fo otholds
Biblio graphy
AG W Armstrong and M Green The dynamics of articulated rigid b o dies for purp oses of animation The Visual Computer
AN L Alt and A Nicolas Animating articulated structures with multiple goals In Proceed ings of Computer Graphics pages
AW W Welch A Witkin M Gleicher Interactive dynamics Computer Graphics March
Bai J Bailleiul Avoiding obstacles and resolving kinematic redundancy In Proc Int Conf on Robotics and Automation April
BB R Barzel and A Barr Mo deling with dynamic constraints In SIGGRAPH Course Notes Topics in Physical lyBased Model ling
BC A Bruderlin and T Calvert Goaldirected dynamic animation of human walking Com puter Graphics July
BH R Bartels and I Hardtke Sp eed adjustment for keyframe interp olation In Proceedings
of Graphics Interface pages
BMW N Badler K Mano o chehri constraints IEEE Computer
and G Walters Articulated gure p ositioning by multiple Graphics and Applications June
BN L Brotman and A Netravali Motion interp olation by optimal control Computer Graph ics August
CHP J Chadwick D Haumann and R Parent Layered construction for deformable animated characters Computer Graphics July
Coh MF Cohen Interactive spacetime control for animation Computer Graphics July
BIBLIOGRAPHY
CP N Badler C Phillips J Zhao Interactive realtime articulated gure using multiple kinematic constraints In Proceedings Symposium on Graphics pages
manipulation Interactive D
CWGL TW Calvert C Welman S Gaudet and C Lee Comp osition of multiple gure sequences for dance and animation In Proceedings of CG International
DSS H Das JJ Slotine and TB Sheridan Inverse kinematic algorithms for redundant systems In Proceedings IEEE Intl Conference on Robotics and Automation pages
FW D Forsey and J Wilhelms Techniques for interactive manipulation of articulated b o dies using dynamic analysis In Proceedings of Graphics Interface pages
Gir M Girard Interactive design of d computeranimated legged animal motion In Pro ceedings Workshop on Interactive D Graphics pages
Gir M Girard Constrained optimization of articulated animal movement in computer ani mation In N Badler B Barsky and D Zeltzer editors Making Them Move Mechan ics Control and Animation of Articulated Figures chapter pages Morgan Kaufmann PublishersInc San Mateo Ca
GM M Girard and A Maciejewski Computational modeling for the computer animation of legged gures Computers Graphics July
GMW P Gill W Murray and M Wright Practical Optimization Academic Press New York NY
Gom J Gomez Twixt A d animation system Computers and Graphics March
GP B Guenter and R Parent Computing the arc length of parametric curves IEEE Computer Graphics and Applications May
Gre TNE Greville The pseudoinverse of a rectangular or singular matrix and its application to the solution of systems of linear equations SIAM Review January
GW M Gleicher and A Witkin Dierential manipulation In Proceedings of Graphics Inter face
Hah JK Hahn Realistic animation of rigid b o dies Computer Graphics August
BIBLIOGRAPHY
HS P Hanrahan and D Sturman Interactive animation of parametric mo dels The Visual Computer
IC P Isaacs and M Cohen Controlling dynamic simulation with kinematic constraints b ehaviour functions and inverse dynamics Computer Graphics July
IC P Isaacs and M Cohen Mixed metho ds for complex kinematic constraints in dynamic gure animation The Visual Computer
Kas M Kass Condor Constraintbased dataow Computer Graphics July
KB J Korein and N Badler Techniques for goaldirected motion IEEE Computer Graphics and Applications
KB D Ko chanek and R Bartels Interp olating splines with lo cal tension continuity and bias control Computer Graphics July
KH CA Klein and CH Huang Review of pseudoinverse control for use with kinemati cally redundant manipulators IEEE Transactions on Systems Man and Cybernetics MarchApril
Las J Lasseter Principals of traditional animation applied to d computer animation Com puter Graphics July
LWZB P Lee S Wei J Zhao and N Badler Strength guided motion Computer Graphics
Mac A A Maciejewski Dealing with the illconditioned equations of motion for articulated gures IEEE Computer Graphics and Applications May
MK AA Maciejewski and CA Klein The singular value decomp osition Computation and applications to rob otics International Journal of Robotics Research Decemb er
NN ZR Novakovic and B Nemec A solution of the inverse kinematics problem using the sliding mo de IEEE Transactions on Robotics and Automation April
Pau RP Paul Robot Manipulators Mathematics Programming and Control MIT Press Cambridge MA
PB C Phillips and N Badler Interactive b ehaviours for bip edal articulated gures Com puter Graphics July
BIBLIOGRAPHY
PFTV WH Press BP Flannery SA Teukolsky and WT Vetterling Numerical Recipes in C The Art of Scientic Computing Cambridge University Press Cambridge MA
SB S Steketee and N Badler Parametric keyframe interp olation incorp orating kinetic
adjustment and
phrasing control Computer Graphics July
Sho K Sho emake July
Animating rotation with quaternion curves Computer Graphics
SS L Sciavicco and B Siciliano A dynamic solution to the inverse kinematic problem of redundant manipulators In IEEE Intl Conference on Robotics and Automation pages March
Ste G Stern Bb op a program for dimensional pages
animation In Nicograph Proceedings
Stu D Sturman Interactive keyframe animation of d articulated mo dels In SIGGRAPH
Course Notes Computer Animation D Motion
Specication and Control pages
Sur MC Surles An algorithm with linear complexity for interactive physicallybased mo d eling of large proteins Computer Graphics July
SZ K Sims and D Zeltzer A gure editor and gait controller for task level animation In SIGGRAPH Course Notes Synthetic Actors The Impact of Articial Intel ligence and Robotics on Animation
WC LCT Wang and CC Chen A combined optimization metho d for solving the inverse kinematics problem of mechanical manipulators IEEE Transactions on Robotics and Automation August
WCH B Wyvill M Chmilar and C Herr A simple mo del of human animation In SIGGRAPH Course Notes Synthetic Actors The Impact of Articial Intel ligence and Robotics on Animation
WE WA Wolovich and H Elliot A computational technique for inverse kinematics In Proceedings of rd Conference on Decision and Control pages Decemb er
Wil J Wilhelms Virya a motion control editor for kinematic and dynamic animation In Proceedings of Graphics Interface pages
BIBLIOGRAPHY
Wil J Wilhelms Using dynamic analysis for realistic animation of articulated b o dies IEEE Computer Graphics and Applications June
Wil J Wilhelms Dynamic exp eriences In N Badler B Barsky and D Zeltzer editors Mak ing Them Move Mechanics Control and Animation of Articulated Figures chapter pages Morgan Kaufmann PublishersInc San Mateo Ca
WK A Witkin and M Kass Spacetime constraints Computer Graphics August
ZB J Zhao and N Badler Real time inverse kinematics with joint limits and spatial con straints Technical Rep ort Technical Rep ort MSCIS University of Pennsylvania
Zela D Zeltzer Motor control techniques for gure animation IEEE Computer Graphics and Applications
Zelb D Zeltzer Representation of complex animated gures In Proceedings of Graphics Interface pages