CS计算机代考程序代写 ER Excel arm asp scheme chain algorithm cache interpreter INVERSE KINEMATICS AND GEOMETRIC CONSTRAINTS FOR ARTICULATED FIGURE MANIPULATION

INVERSE KINEMATICS AND GEOMETRIC CONSTRAINTS FOR ARTICULATED FIGURE MANIPULATION
by
Chris Welman
B􏰦Sc􏰦 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􏰦 T􏰦W􏰦 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 eci􏰬ed at each frame􏰦 Animation techniques range from simple interp olation b etween keyframed 􏰬gure p oses to higher􏰫level algorithmic mo dels of sp eci􏰬c movement patterns􏰦 The former provides the animator with complete control over the movement􏰭 whereas the latter may provide only limited control via some high􏰫level 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 eci􏰬cation 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 􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹 􏰮􏰰
􏰯 E􏰷cient Algorithms for Direct Manipulation 􏰮􏰲 􏰯􏰦􏰧 ASimpli􏰬edDynamicModel 􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹 􏰮􏰲
􏰪 Inverse Kinematics
􏰪􏰦􏰧 The Inverse Kinematic Problem
􏰪􏰦􏰮 Resolved Motion Rate Control
􏰪􏰦􏰮􏰦􏰧 Redundancy 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹
􏰹 􏰹 􏰹
􏰪􏰦􏰮􏰦􏰮 Singularities 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰪􏰦􏰪 Optimization􏰫Based Metho ds
􏰯􏰦􏰧􏰦􏰧 The Jacobian Transpose Method
􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹 􏰮􏰩
i

CONTENTS
ii
􏰯􏰦􏰧􏰦􏰮 ImplementationDetails 􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹 􏰪􏰳
􏰯􏰦􏰧􏰦􏰪 ComputingtheJacobian􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹 􏰪􏰳
􏰯􏰦􏰧􏰦􏰯 ScalingConsiderations􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹 􏰪􏰪
􏰯􏰦􏰧􏰦􏰰 Integration 􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹 􏰪􏰪
􏰯􏰦􏰧􏰦􏰱 JointLimits􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹 􏰯􏰦􏰮 A Complementary Heuristic Approach 􏰹 􏰹 􏰹 􏰹 􏰹
􏰯􏰦􏰮􏰦􏰧 The Cyclic􏰫Coordinate 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 CCD􏰫based 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 de􏰬ned in lo cal co ordinate systems􏰦 􏰴b􏰵 Lo cal
rotations
applied􏰦
Localtranslationsapplied􏰦􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹􏰹
􏰪􏰦􏰧 Three con􏰬gurations of a 􏰮D redundant manipulator
􏰪􏰦􏰮 A manipulator in a singular con􏰬guration 􏰹 􏰹 􏰹 􏰹 􏰹 􏰹
􏰯􏰦􏰧 Interactive control lo op mo del for Jacobian transp ose
􏰯􏰦􏰮 A case not handled well with the Jacobian transp ose metho d􏰦
􏰴c􏰫d􏰵
􏰹 􏰹 􏰹 􏰹 􏰰
􏰹 􏰹 􏰹 􏰹 􏰮􏰳
􏰹 􏰹 􏰹 􏰹 􏰮􏰧
􏰹 􏰹 􏰹 􏰹 􏰪􏰳 on the
tip of the manipulator on the left will not pro duce an exp ected con􏰬guration 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 end􏰫e􏰶ector 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 di􏰷cult􏰭 particularly as ob ject models grow increasingly complex􏰦 The speci􏰬cation 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 life􏰫like􏰭 p ossibly human􏰫like􏰭 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 computer􏰫generated characters roaming through arti􏰬cial 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 di􏰷cult 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 high􏰫level b ehavioural and motor control mo dels􏰦 However􏰭 these algorithms are often limited to generating sp eci􏰬c􏰭 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 e􏰶ective􏰭 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 di􏰶ering 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 life􏰫like 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 computer􏰫generated 􏰺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 erformer􏰸s
􏰪

􏰯
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 su􏰷ce􏰦 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 de􏰬ned 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 de􏰬ned in their own lo cal co ordinate systems􏰦
More complex skeletons can b e built up by arranging the segments in a tree􏰫structured hierarchy􏰦 Each no de in the tree maintains the rotations currently in e􏰶ect at the corresp onding joint􏰽 these joint rotations are o􏰶sets 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 eci􏰬ed 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 de􏰬ne a skeleton􏰭 and it is easy enough to de􏰬ne a simple grammar for sp ecifying skeletons 􏰾Zel􏰩􏰮b􏰿􏰦 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 de􏰬nition 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 de􏰬ned in lo cal co ordinate systems􏰦 􏰴b􏰵 Lo cal rotations applied􏰦 􏰴c􏰫d􏰵 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 eci􏰬cation 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 eci􏰬cation 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 eci􏰬c 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 eci􏰬ed at di􏰶erent 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 animator􏰸s 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 a􏰶ects the rate of change of the interp olated value around the keyframe􏰭 and thus provides some control over sp eed􏰦 Some traditional animation e􏰶ects such as action fol low􏰫through and exaggeration 􏰾Las􏰩􏰲􏰿 can be achieved with appropriate settings of these parameters􏰦 Unfortunately􏰭 since all three parameters in the spline formulation a􏰶ect 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 double􏰫interp olant metho d which do es separate timing control from the tra jectory itself􏰦 As b efore􏰭 a tra jectory is de􏰬ned 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
higher􏰫order
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 de􏰬ned􏰭 the quality of the movement can be further modi􏰬ed 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 non􏰫intuitive􏰭 requiring a trial􏰫and􏰫error pro cess on the part of the animator to achieve the desired velo city pro􏰬le 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 arc􏰫length􏰦 Arc􏰫length 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 jectory􏰸s arc􏰫length 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 arc􏰫length 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
Keyframe􏰫based 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􏰦 Computer􏰫based keyframing is intuitive􏰭 and the interp olation can usually b e p er􏰫 formed fast enough to provide near real􏰫time 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 technique􏰸s 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 di􏰷culty 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 error􏰫prone􏰦 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 di􏰷cult 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 X􏰭Y􏰭 and Z rotation directions at each joint

CHAPTER 􏰮􏰦 APPROACHES TO FIGURE ANIMATION 􏰩
b o dy segment􏰸s 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 di􏰷cult 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
frame􏰫by􏰫frame p ositioning of traditional stop􏰫action 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 frame􏰫by􏰫frame basis􏰦
While forward kinematics combined with a simple interp olation scheme may su􏰷ce 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
o􏰶ers an attractive alternative to explicitly rotating individual joints within a skeleton􏰦 An animator can instead directly sp ecify the p osition of an end􏰫e􏰶ector􏰭 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 end􏰫e􏰶ector 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􏰦
􏰨
Chadwick􏰸s Critter system
keyframes 􏰾CHP􏰩􏰨􏰿􏰦 Badler has
straints on multiple b o dy parts
range limits into the inverse kinematic solution 􏰾CP􏰨􏰳􏰭 ZB􏰩􏰨􏰿􏰦 Both Girard􏰸s PODA system 􏰾GM􏰩􏰰􏰿 and Sims􏰸 gait controller 􏰾SZ􏰩􏰩􏰿 provided high􏰫level 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 ot􏰫hold􏰦
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 higher􏰫level 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 e􏰶ort
on the animator􏰸s 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 di􏰷cult 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 di􏰷cult 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 time􏰫varying 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 ject􏰸s 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 O􏰴n􏰯 􏰵 complexity for n
recursive formulation which
of simple articulated structures to b e p erformed reasonably complex articulated skeletons cannot single􏰫pro 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 di􏰷cult􏰭 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􏰩􏰱􏰿􏰦 E􏰶orts 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 signi􏰬cantly a􏰶ects the cost for the matrix􏰫based Gibbs􏰫App ell formulation􏰭 for example􏰭 of freedom 􏰾Wil􏰩􏰲􏰿􏰦 Armstrong has proposed an alternative
􏰾AG􏰩􏰰􏰿􏰭 enabling dynamic simulations real􏰫time􏰦 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 ill􏰫conditioned􏰭 indep endent of their formulation 􏰾Mac􏰨􏰳􏰿􏰦 The
problem of numerical instabilities is the fact that the equations of motion for
ill􏰫conditioning arises
one degree of freedom pro duce large accelerations elsewhere􏰽 almost all numerical solution techniques have di􏰷culty handling such cases􏰦 Maciejewski contends that these situations o ccur frequently for articulated 􏰬gures􏰭 and are inherent in the structure of most skeletons􏰦 The ill􏰫conditioning 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 ill􏰫conditioning 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 eci􏰬ed at di􏰶erent times􏰽 cubic splines were then used to construct the force and torque pro􏰬les over the course of the entire motion sequence􏰦 During dynamic simulation􏰭 these force􏱂torque pro􏰬les 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 di􏰶erence
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 e􏰶orts to simulate skeleton motion using pure forward
􏰾WCH􏰩􏰩􏰿􏰦
􏰬gure di􏰷cult 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 initial􏰫value problems􏰦 That is􏰭 tasks for which initial p ositions and velo cities􏰭 and force􏱂torque pro􏰬les􏰭 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 eci􏰬c 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 force􏱂torque
of gravity􏰭 and reactions to collisions with the 􏰼o or􏰭 to generate
pro􏰬les
􏰮􏰦􏰪􏰦􏰮
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 di􏰷cult􏰽 land it in the cup is di􏰷cult 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 high􏰫level constraints or goals to b e necessary to meet the goals􏰦
Geometric Constraints
modelling were presented􏰭 including point􏰫to􏰫path constraints for moving control an ob ject􏰸s orientation􏰦 The forward dynamics simulation of the move the mo del towards a state in
sp eci􏰬ed􏰭 and which then compute the forces and torques
somewhat the distinction self􏰫assembling structures􏰽
the geometric constraints􏰭
the laws of Newtonian mechanics􏰦
mo del was de􏰬ned as simple constraints for point􏰫to􏰫point 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 prede􏰬ned 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 satis􏰬ed􏰦 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 Armstrong􏰸s recursive formu􏰫 lation for the equations of motion􏰦 A p ositional goal for a b o dy part could b e sp eci􏰬ed 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 arti􏰬cially 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 di􏰶erent p oints during the dynamic analysis􏰭 and later using these stored states as keyframes for kinematic interp olation􏰦
The penalty􏰫force 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 sti􏰶ness 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 e􏰷cients for the constraints is often a matter of trial􏰫and􏰫error􏰦
In contrast to the p enalty􏰫force 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􏰦
Non􏰫Geometric 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 non􏰫geometric constraints in the inverse dynamic solution􏰦 These approaches are based on well􏰫established 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 prede􏰬ned limb tra jectories for articulated 􏰬gures􏰦 Girard notes that the choice of optimization criteria has a signi􏰬cant e􏰶ect on the p erceived quality of motion􏰦 Solving for a velo city pro􏰬le 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 goal􏰫directed 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 side􏰫steps 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􏰭 physically􏰫correct 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 constraint􏰫based inverse dynamics to synthesize the tra􏰫 jectories of limbs charged with the task of moving a load b etween two di􏰶erent p ositions􏰦 The tra jectories are computed incrementally􏰭 and are constrained by measures of strength􏰭 comfort􏰭 and exertion􏰦 The iterative nature of the algorithm di􏰶ers 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 sub􏰫optimal􏰭 limb tra jectories which accomplish the task􏰦
􏰮􏰦􏰯 Control Issues
The research e􏰶orts 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 e􏰶orts􏰭 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 eci􏰬c for decomp osing high􏰫level task descriptions􏰭 such
into lower􏰫level 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 low􏰫level kinematic goals􏰭 forward dynamic
minimizing jerk reaching for an

CHAPTER 􏰮􏰦 APPROACHES TO FIGURE ANIMATION 􏰧􏰰
Zeltzer was an early prop onent of the need for high􏰫level control over articulated 􏰬gures 􏰾Zel􏰩􏰮a􏰿􏰦 He describ es a control strategy for synthesizing walking sequences for a skeleton􏰦 High􏰫level 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 􏰬nite􏰫state machine resp onsible for activating and deactivating the appropriate MCPs at the appropriate times􏰦 Zeltzer􏰸s 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 Zeltzer􏰸s 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 dynamically􏰫based low􏰫level 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 simpli􏰬ed walking mechanism are iteratively adjusted until the keyframed joint angles are achieved at the correct times􏰦 A purely kinematic overlay of the skeleton􏰸s 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 simpli􏰬ed dynamic mo del sp eci􏰬cally 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 mass􏰫and􏰫spring mo del􏰦
Unfortunately􏰭 the high􏰫level control provided by algorithms of this nature come at the exp ense of generality􏰽 each control strategy must b e tuned for a sp eci􏰬c movement􏰦 But developing such a control strategy is di􏰷cult􏰦 Deriving the equations for simulating the dynamics of the underlying mechanism requires some mathematical sophistication􏰦 In the absence of an inverse kinematic algo􏰫 rithm􏰭 Bruderlin􏰸s 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 high􏰫level 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 con􏰬ned to sp eci􏰬c
into automatic motion synthesis from high􏰫level 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 hand􏰫crafting 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 di􏰶er 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 end􏰫e􏰶ector is emb edded in the co ordinate frame of the most distal joint in the chain􏰽 the end􏰫e􏰶ector p osition is a p oint within this frame and the end􏰫e􏰶ector 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 􏱁 T􏰴xi 􏰽 yi 􏰽 zi􏰵R􏰴􏱌i 􏰵
a rotation joint i is a concatenation co ordinate frame of joint i􏰸s parent􏰦
􏰴􏰪􏰦􏰧􏰵
where T􏰴xi 􏰽 yi 􏰽 zi􏰵 is the matrix that translates by the o􏰶set of joint i from its parent joint i 􏱇 􏰧􏰭 and R􏰴􏱌i 􏰵 is the matrix that rotates by 􏱌i ab out joint i􏰸s 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
non􏰫linear 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 end􏰫e􏰶ector􏰭 is a simple matter of matrix concatenation􏰭 and has the form
x 􏱁 f􏰴q􏰵 􏰴􏰪􏰦􏰪􏰵
But if the goal is to place the end􏰫e􏰶ector at a sp eci􏰬ed 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 q􏰸s for a particular x􏰦 The most direct approach for solving the problem would be to obtain a closed􏰫form solution to 􏰴􏰪􏰦􏰯􏰵􏰦 But closed􏰫form solutions can only be derived
solved􏰾Pau􏰩􏰧􏰿􏰦
􏰪􏰦􏰮 Resolved Motion Rate Control
Since the non􏰫linear nature of equation 􏰴􏰪􏰦􏰯􏰵 makes it di􏰷cult to solve􏰭 a natural approach is to
linearize the problem ab out the current manipulator con􏰬guration
􏰫
then
the
relationship
b etween
􏰴􏰪􏰦􏰰􏰵
􏰴􏰪􏰦􏰱􏰵
joint velo cities and the
velo city of the
end􏰫e􏰶ector is
x􏱃 􏱁 J􏰴q􏰵q􏱃
Jacobian matrix
The linear relationship is given by the
end􏰫e􏰶ector
with resp ect to the base frame is found by simply
sp eci􏰬c 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 non􏰫linear 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 end􏰫e􏰶ector vector x􏰭 which is usually either 􏰪 for a simple p ositioning task􏰭 or 􏰱 for a more general p osition􏰫and􏰫orientation task􏰦 The ith column of J represents the incremental change in the p osition
􏰴and orientation􏰵 of the end􏰫e􏰶ector 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 end􏰫e􏰶ector p osition and orientation􏰦
CHAPTER 􏰪􏰦 INVERSE KINEMATICS
which maps changes in the joint variables q to changes in the end􏰫e􏰶ector
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 con􏰬guration􏰭 J􏰴q􏰵 must b e recomputed at each iteration􏰦 A pro cedure for e􏰷ciently 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 non􏰫singular􏰦 This assumption is not􏰭 in general􏰭 a valid one􏰦 Di􏰷culties arise when a manipulator is redundant􏰭 or when it passes through or near a singular con􏰬guration􏰦
􏰪􏰦􏰮􏰦􏰧 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 con􏰬gurations
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 end􏰫e􏰶ector using the Jacobian inverse􏰭 and integrated rep eats until the end􏰫e􏰶ector has reached
pro cedure
are required to sp ecify a goal for the end􏰫e􏰶ector􏰦
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 end􏰫e􏰶ector 􏰴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 eci􏰬cation 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 􏰪D􏰫space p ositioning task􏰭 and there is no unique

CHAPTER 􏰪􏰦
INVERSE KINEMATICS
􏰮􏰳
(x,y)
θ3
θ2
θ1
Figure 􏰪􏰦􏰧􏰹 Three con􏰬gurations
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 under􏰫determined􏰭 and there are an in􏰬nite numb er of
b e
solutions from
useful solution
Mo ore􏰫Penrose
optimal in the sense that it yields solutions with a minimum Euclidean norm for cases in which 􏰴􏰪􏰦􏰲􏰵 is under􏰫determined 􏰴m 􏱎 n􏰵􏰭 and that in cases in which the system is over􏰫determined 􏰴m 􏱏 n􏰵 a least􏰫squares solution is obtained􏰦 In practice􏰭 these prop erties ensure that joints move as little as p ossible to match the desired end􏰫e􏰶ector 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 under􏰫determined 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 end􏰫e􏰶ector
is a pro jection operator
which selects

CHAPTER 􏰪􏰦 INVERSE KINEMATICS
􏰮􏰧
y
singular direction
x
Figure 􏰪􏰦􏰮􏰹 A manipulator in a singular con􏰬guration
p osition 􏰴i􏰦e􏰦 for which x􏱃 􏱁 􏰳􏰵􏰦 In e􏰶ect􏰭 then􏰭 the 􏰬rst term of the general equation
joint velo city vector which pro duces the desired change in the end􏰫e􏰶ector 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 end􏰫e􏰶ector 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 con􏰬guration when the Jacobian b ecomes singular􏰦 Figure 􏰪􏰦􏰮 depicts a simple example of a 􏰪􏰫jointed manipulator in a singular con􏰬guration􏰦 In this example􏰭 an incremental change to any of the joint angles will result in approximately the same movement of the end􏰫e􏰶ector in the y direction􏰽 no combination of joint velo cities will pro duce an end􏰫e􏰶ector velo city in the singular 􏰴i􏰦e􏰦 x􏰵 direction􏰦 􏰧 The Jacobian matrix computed for this con􏰬guration 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 con􏰬guration 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 con􏰬guration 􏰾Mac􏰨􏰳􏰿􏰦 Furthermore􏰭 as the manipulator approaches this con􏰬guration 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 con􏰬guration􏰦 So􏰭 while the pseudoinverse is able to provide a usable solution at a singular con􏰬guration􏰭 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 con􏰬gurations 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 con􏰬gurations 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 􏰴non􏰫unique􏰵 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 signi􏰬cance of the SVD lies in the
For an m 􏱈 n matrix J􏰭 D is an n 􏱈 n diagonal matrix with non􏰫negative 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 l􏰫conditioned the matrix J is􏰦 When the condition number is too large 􏰮􏰭 then the matrix is ill􏰫conditioned􏰦 It is this ill􏰫conditioning that is responsible for the large joint velo cities generated by the pseudoinverse near a singular con􏰬guration 􏰾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 􏰴􏰪􏰦􏰲􏰵 􏰴i􏰦e􏰦 the set of joint velo cities which will not move the end􏰫e􏰶ector􏰵􏰦 Likewise􏰭 the non􏰫zero singular values have corresp onding columns in U which span the space of solutions which wil l move the end􏰫e􏰶ector􏰦 We will refer to these basis matrices again when discussing constraints in Chapter 􏰰􏰦
While the SVD provides a means for detecting ill􏰫conditioning in the Jacobian matrix􏰭 it do es i􏰦e􏰦 its recipro cal approaches machine precision limits
􏰮

CHAPTER 􏰪􏰦 INVERSE KINEMATICS 􏰮􏰪
not in itself provide a way for dealing with the ill􏰫conditioning􏰦 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 ore􏰫Penrose 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 con􏰬gurations􏰦 But the cost of computing the SVD􏰭 O 􏰴n􏰮 l og n􏰵 for an n 􏱈 n matrix􏰭 adds signi􏰬cantly to the p er􏰫iteration cost of any control
algorithm􏰭 so it is often not feasible to incorp orate it into on􏰫line 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 O􏰴n􏰮 􏰵 per iteration􏰭 but this requires careful implementation to reduce cumulative errors and the cost is still high enough to deter its use􏰦
􏰪􏰦􏰪 Optimization􏰫Based Metho ds
A fundamentally di􏰶erent 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 non􏰫linear optimization techniques to obtain a solution􏰦
As an example􏰭 consider the problem of p ositioning the end􏰫e􏰶ector
x at a goal p osition p􏰦 The
distance from the current p osition x􏰴q􏰵 to the goal p osition p serves
as
an
error
measurement􏰹
􏰴􏰪􏰦􏰧􏰳􏰵
E 􏰴q􏰵 􏱁 􏰴p 􏱇 x􏰴q􏰵􏰵
􏰮
By varying the joint angle vector q the end􏰫e􏰶ector 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 end􏰫e􏰶ector since E 􏰴q􏰵 can be any arbitrary function of the joint vector q􏰦
This formulation is a classic non􏰫linear 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 e􏰶ectiveness 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 di􏰷culties 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 con􏰬guration 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 end􏰫e􏰶ector􏰭 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
di􏰷cult􏰦 A solver may work well for one particular typ e of problem􏰭 but fail miserably on others􏰦
arbitrary non􏰫linear 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 􏰧􏰳 frames􏱂sec􏰭 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 di􏰶erent con􏰬guration 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 di􏰶erent 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 Chadwick􏰸s Critter system are also based on the tech􏰫 nique􏰦 None of these e􏰶orts suggest sp eci􏰬c 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 con􏰬gurations􏰦
Badler and Zhao 􏰾CP􏰨􏰳􏰭 ZB􏰩􏰨􏰿 have adopted the second approach for the Jack system􏰭 applying
a variable􏰫metric optimization pro cedure to
posture􏰦 Joint range limits are presented as
functions for simple geometric constraints are develop ed􏰦 These include􏰭 for example􏰭 p oint􏰫to􏰫 p oint constraints􏰭 p oint􏰫to􏰫plane 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 non􏰫geometric goals􏰦 While Jack􏰸s capabilities are impressive􏰭 and do
provide interactive control over an articulated 􏰬gure􏰸s
constraints to the optimizer􏰭 and a
number of ob jective
on high􏰫p 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 conjugate􏰫gradient 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 Badler􏰸s 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 􏰯
E􏰷cient 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 con􏰬gurations􏰦 Badler􏰸s 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 o􏰶􏰫line 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 e􏰷cient enough to provide reasonable interactive p erformance on even low􏰫p erformance machines􏰦 Each metho d exhibits a di􏰶erent b ehaviour than the other􏰭 and it is suggested that they might work well together as complementary manipulation to ols􏰦
􏰯􏰦􏰧 A Simpli􏰬ed 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 end􏰫e􏰶ector and joint velo cities􏰦 Unlike this other approach􏰭 however􏰭 no inversion of the Jacobian matrix is required􏰭 which signi􏰬cantly reduces the cost of each iteration􏰦 Consequently􏰭 the metho d has b een advo cated for the on􏰫line􏰭 dynamic control of rob otic manipulators􏰦
􏰮􏰲
the inverse kinematic problem that are based resolved􏰫motion 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 end􏰫e􏰶ector 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 pseudoinverse􏰫based metho d discussed in section 􏰴􏰪􏰦􏰮􏰦􏰧􏰵􏰭 and compare the metho d to a minimization algorithm based on Newton􏰸s 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 end􏰫e􏰶ector 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 end􏰫e􏰶ector p osition is given by
e􏰴t􏰵 􏱁 xd 􏰴t􏰵 􏱇 xc 􏰴t􏰵
can be thought of as a force f pulling the end􏰫e􏰶ector 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 su􏰷ces 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 end􏰫e􏰶ector towards xd 􏰴t􏰵􏰦 This pro cedure rep eats until the end􏰫e􏰶ector reaches the desired p osition􏰭 or some other stopping criterion is met􏰦
end􏰫e􏰶ector to track
􏰴􏰯􏰦􏰮􏰵
a time􏰫varying measure
􏰴􏰯􏰦􏰪􏰵
xc 􏰴t􏰵􏰭 then the
error
the desired tra jectory point xd 􏰴t􏰵􏰦

CHAPTER 􏰯􏰦 EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION 􏰮􏰨
In e􏰶ect􏰭 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 e􏰶ects 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 di􏰶erential 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 well􏰫known 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 o􏰶􏰫line􏰭 and for this typ e of on􏰫line 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 eci􏰬ed 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 end􏰫e􏰶ector 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 ill􏰫conditioned􏰦 Near a singularity high joint velo cities can result in oscillations ab out the singular con􏰬guration􏰦 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 physically􏰫based 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 simpli􏰬ed one􏰭 the iterations are b oth predictable and intuitive􏰦 That is􏰭 the manipula􏰫 with an elastic band􏰦 In which are quite di􏰶erent are an in􏰬nite numb er of mo del􏰭 successive con􏰬gurations are implicitly metaphor uniquely sp eci􏰬es 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 end􏰫e􏰶ector􏰭 computing the Jacobian matrix for the current con􏰬guration􏰭 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 con􏰬guration 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􏰫 e􏰶ector frame moves in the world frame as the individual joint variables change􏰦 Given a vector of joint variables q􏰭 the end􏰫e􏰶ector frame is sp eci􏰬ed by a p osition P􏰴q􏰵 and orientation O􏰴q􏰵􏰦 The
applied to the end􏰫e􏰶ector 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 i􏰸th
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 end􏰫e􏰶ector􏰭 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 e􏰷ciently 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 sub􏰫tree 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 sub􏰫tree 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 signi􏰬cance 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 er􏰫left 􏰪 􏱈 􏰪 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􏰭 non􏰫uniform scaling transformations within the manipulator may result in an upp er􏰫left 􏰪 􏱈 􏰪 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 end􏰫e􏰶ector 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 e􏰷ciency􏰭 Mi matrix identity
can b e computed incrementally
while
traversing the
hierarchy􏰦
Using the
􏰴􏰯􏰦􏰨􏰵
the joint􏰸s 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 simpli􏰬cations
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 end􏰫e􏰶ector
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 di􏰶erent 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 scale􏰫invariant 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 i􏰸th 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 o􏰶set the e􏰶ects 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 joint􏰸s p erceived 􏰺sti􏰶ness􏰻􏰦
The 􏰶i term is a weighting factor for joint i􏰭 which can
resp onsiveness
Although K is sp eci􏰬ed here to b e a constant gain matrix􏰭 it is p ossible to compute a time􏰫varying gain matrix K􏰴t􏰵 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 su􏰶ers􏰦 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 con􏰬guration like the one shown on the right􏰦
􏰯􏰦􏰮 A Complementary Heuristic Approach
The force􏰫based 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 con􏰬guration􏰭 with a new􏰭 desired p osition for the tip shown as a black dot􏰦 The con􏰬guration on the right shows a reasonable solution to this inverse kinematic problem􏰭 and probably re􏰼ects 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 e􏰶ect 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 user􏰸s 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 minimization􏰫based 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 e􏰷cient􏰭 simple􏰭 and immune to problems with singularities􏰦 However its b ehaviour is quite di􏰶erent 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 Cyclic􏰫Co ordinate Descent
The cyclic􏰫coordinate 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 di􏰬ed 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 end􏰫e􏰶ector p osition and orientation are up dated immediately to re􏰼ect 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 di􏰶ers from the previously describ ed metho d􏰭 which in e􏰶ect determines the changes to each joint simultaneously 􏰮􏰦
Supp ose that the current end􏰫e􏰶ector p osition is
Pc 􏱁 􏰴xc 􏰽 yc 􏰽 zc􏰵
and that the current orientation of the end􏰫e􏰶ector is sp eci􏰬ed
by the three orthonormal rows of the
rotation matrix Oc
􏰮
􏰮􏰪
􏰱􏰱 u􏰧c 􏰲􏰲 Oc 􏱁 􏰯 u􏰮c 􏰰
u􏰪c
Metho d
iterative heuristic search technique which at􏰫
i􏰦e􏰦 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 end􏰫e􏰶ector
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􏰵 􏱁 k􏰴Pd 􏱇 Pc 􏰵k
The metho d pro ceeds by considering one joint at a time􏰭 from the
qi is mo di􏰬ed to minimize equation 􏰴􏰯􏰦􏰧􏰪􏰵􏰭 b efore pro ceeding to
minimizing 􏰴􏰯􏰦􏰧􏰪􏰵 b ecomes a simple one􏰫dimensional 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 end􏰫e􏰶ector p osition􏰭 and Pid is the vector from ji to the desired end􏰫e􏰶ector 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 􏰶 􏱁 k􏱁W
and is required to make the algorithm􏰸s b ehaviour scale􏰫invariant􏰦 The factor 􏱒 is an arbitrary weight which dep ends on the con􏰬guration of the manipulator􏰽 Wang 􏰾WC􏰨􏰧􏰿 suggests􏰭 without justi􏰬cation􏰭 that
min􏰴kPid k􏰽 kPick􏰵 􏱒􏱁
max􏰴kPid 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􏱑􏰵 􏱄 k􏰮cos􏱑 􏱄 k􏰪 sin􏱑 co e􏰷cients 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􏰧 􏱇 k􏰮􏰵sin􏱑 􏱄 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 di􏰷cult 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 􏰺sti􏰶ness􏰻 of the joint􏰭 so that the up date b ecomes
qi 􏱁 qi 􏱄 wi􏱑
The end􏰫e􏰶ector frame is then rotated to re􏰼ect this change􏰭 and the iteration continues on to the next joint i 􏱇 􏰧 using the up dated end􏰫e􏰶ector􏰦
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 end􏰫e􏰶ector
p osition is up dated b efore continuing
􏰯􏰦􏰮􏰦􏰮 Overview
on to the next joint􏰦
A single iteration of the CCD metho d for an n􏰫jointed manipulator visits joints n through 􏰧 in turn􏰦 At each joint􏰭 the original n􏰫dimensional optimization problem is reduced to a one􏰫dimensional
􏰴􏰯􏰦􏰮􏰯􏰵

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 end􏰫e􏰶ector frame 􏰴Pc and Oc 􏰵 is up dated to re􏰼ect the change b efore pro ceeding to the next joint􏰦
The algorithm behaves well around singular con􏰬gurations􏰭 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 di􏰷cult 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 end􏰫e􏰶ector 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 di􏰷culties 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 er􏰫iteration 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 eci􏰬ed for the end􏰫e􏰶ector􏰭 and the inverse kinematic problem is solved to varying degrees of accuracy􏰦 Each 􏰬gure shows the initial con􏰬guration􏰭 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 end􏰫e􏰶ector 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 con􏰬guration 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 esn􏰸t a􏰶ect most of the joints􏰭 so the The heuristic approach of the CCD fares much b etter in this
The 􏰬nal con􏰬gurations
moving distal links􏰭 in contrast with the other metho d􏰸s tendency to distribute joint changes more equally along the chain􏰦 This di􏰶erence 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 non􏰫interactively 􏰫 i􏰦e􏰦 they were computed o􏰶􏰫line􏰦 When dragging interactively using the CCD metho d it is usually not di􏰷cult to
shown in the 􏰬gures also illustrate the CCD metho d􏰸s 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 o􏰶set 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 end􏰫e􏰶ector􏰽 the CCD metho d is not as intuitive in this regard􏰦 The CCD metho d exhibits more stability around singular con􏰬gurations􏰭 and although its rate of convergence slows􏰭 it is not nearly to the extent that the Jacobian􏰸s 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 end􏰫e􏰶ector track it to six decimal places of precision􏰽 one or two decimal places of accuracy probably su􏰷ces􏰦 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 o􏰶er 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􏰦 Badler􏰸s recent work 􏰾CP􏰨􏰳􏰿 has shown the usefulness of b eing able
to imp ose
with Jack
sp eci􏰬ed􏰦
􏰾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 end􏰫e􏰶ectors 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 non􏰫linear 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 satis􏰬ed􏰦 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 spring􏰫based􏰦 If the springs are made su􏰷ciently 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 enalty􏰫metho 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 satis􏰬ed􏰭 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 well􏰫known metho ds for implementing constrained dynamics within physical simulations 􏰾Sur􏰨􏰮􏰭 AW􏰨􏰳􏰿􏰭 using the same sort of simpli􏰬ed 􏰬rst􏰫order 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 satis􏰬ed􏰦
Figure 􏰰􏰦􏰧 illustrates the concept for the simplest p ossible system􏰭 a p oint􏰦 The system􏰸s state q is simply the p oint􏰸s 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 c􏰴q􏰵 􏱁 􏰳 􏰧􏰭 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 􏱁 f􏰴q􏰵
If the constraints are initially satis􏰬ed􏰭 then C 􏱁 􏰳􏰦 In order to maintain the constraints􏰭 C must
p oint must state􏰭 c􏰴q􏰵 plane􏰭 then
C􏱃 􏱁
􏱍C 􏱍q
q􏱃 􏱁 􏰳
In Chapter 􏰯􏰭 equation 􏰴􏰯􏰦􏰧􏰳􏰵 de􏰬ned the simpli􏰬ed 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 satis􏰬es 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 eci􏰬ed 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 P􏰴q􏰵􏰭 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 C􏰴q􏰵􏰭 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 􏱇 P􏰴q􏰵􏰵 􏱁 􏰳
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 􏰴e􏰦g􏰦 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􏰭
C􏰴q􏰵 􏱁 􏱁
􏰾 􏱈􏰧x􏰮y􏰪z􏱖
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 e􏰶ect on this
constraint􏰦 Thus the i􏰸th 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 o􏰶er 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 speci􏰬c example
just a few non􏰫zero 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 under􏰫constrained 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 non􏰫linear􏰦
􏰰􏰦􏰮􏰦􏰯 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 ill􏰫conditioning in 􏰴􏰰􏰦􏰰􏰵 all of the
time 􏰾Mac􏰨􏰳􏰿􏰦 To cop e with this􏰭 the system is solved using the truncated SVD of the left􏰫hand
T
m 􏱈 m matrix Jc KJc
is formed from the original SVD by zeroing any 􏰺small􏰻 singular values􏰭 which e􏰶ectively throws
This term e􏰶ectively 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 ill􏰫conditioned 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 ill􏰫conditioning o ccurs􏰦
􏰰􏰦􏰮􏰦􏰰 Feedback
The discussion so far has b een based on the assumption that the constraints are initially satis􏰬ed􏰭 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􏱃 􏱁 K􏰴ga 􏱄 gc 􏰵 􏱇 kCJc
T
􏰴􏰰􏰦􏰲􏰵 prop ortional to
Equation 􏰴􏰰􏰦􏰲􏰵 is the complete simpli􏰬ed 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 eci􏰬c requests to provide these pieces of information􏰭 a generic constraint solver can b e written which is insulated from the sp eci􏰬c 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 di􏰶erent 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 solver􏰸s global vector q􏰦 Each skeleton must b e able to resp ond to requests for sp eci􏰬c 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
re􏰼ecting 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 skeleton􏰸s internal state􏰦
of a joint within the skeleton􏰭 or as complex as the lo cation of the skeleton􏰸s 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 skeleton􏰸s state􏰭 h􏰴q sk eleton􏰵􏰦 A numb er of handle typ es can b e de􏰬ned􏰭 each computing a di􏰶erent quantity􏰦 These might include
􏱊 A point hand le which computes the global position of some point de􏰬ned within a local joint co ordinate system􏰦 􏰴e􏰦g􏰦 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 center􏰫of􏰫mass hand le which computes the global position of a skeleton􏰸s center of mass􏰭 computed as a weighted average of each b o dy part􏰸s 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 h􏰴q 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 􏰪 handle􏰫sp eci􏰬c routines to b e co ded􏰦 These routines are resp onsible for initializing the handle􏰭 computing the handle function h􏰭 and computing the handle􏰸s 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 􏰬gure􏰸s 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 de􏰬ned 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 c􏰴h􏰧 􏰽 􏱀 􏱀 􏱀 􏰽 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 􏰺hard􏰫wire􏰻 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 network􏰸s con􏰬guration􏰦 The data􏰫􏰼ow 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 data􏰫􏰼ow 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 ck􏰸s 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 re􏰼ect 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 solver􏰸s 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 data􏰫􏰼ow 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 􏰬gure􏰸s 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 data􏰫􏰼ow network constructed by the constraint solver􏰦 Each handle references a few variables within the skeleton􏰸s 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 re􏰫evaluated􏰭 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 data􏰫􏰼ow 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 O􏰴n􏰪 􏰵 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 di􏰷cult􏰦 But Surles 􏰾Sur􏰨􏰮􏰿 has shown that when constraints are applied to articulated structures with sp eci􏰬c 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 con􏰬rms 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 di􏰷cult 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
su􏰶ers from the usual
constant k leads to a
noticeable constraint
currently done purely
􏰴i􏰦e􏰦 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 spring􏰫based 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 di􏰷cult􏰭 and is on a trial􏰫and􏰫error 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 o􏰶􏰫line than in an interactive setting􏰦 Our goal is to develop immediately useful interactive to ols for working with non􏰫trivial 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 enalty􏰫force metho d based
on the CCD algorithm as a substitute with which we can exp eriment
􏰰􏰦􏰯 A CCD􏰫based Penalty Metho d
in an interactive editor􏰦
The previous metho d is capable of handling multiple constraints imp osed on di􏰶erent parts of a skeleton􏰦 To accomplish the same with the CCD metho d requires some slight mo di􏰬cations 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 end􏰫e􏰶ector in towards the base􏰭 at each joint adjusting the joint parameter to minimize an error measure derived from the current end􏰫e􏰶ector p osition and a known goal􏰦 In a branching chain with multiple end􏰫 e􏰶ectors and multiple goals􏰭 a joint may contribute to the p osition of more than one end􏰫e􏰶ector􏰭 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 end􏰫e􏰶ectors in their sub􏰫tree􏰦 Then the joint variable which minimizes the summed error measure from each child sub􏰫tree 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 end􏰫e􏰶ector constraints
single􏰫goal problems which can
b e
joints must b e solved 􏰬rst b efore a more the multiple􏰫goal 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 e􏰶ect of this change is that the coe􏰷cients k􏰧 􏰭 k􏰮􏰭 and k􏰪 must be computed by summing equations 􏰴􏰯􏰦􏰮􏰳􏰵􏰫􏰴􏰯􏰦􏰮􏰮􏰵 over each distal
computed􏰦 The constraints have b een satis􏰬ed􏰭 or until successive iterations pro duce negligible changes􏰭 indicating that the constraints are con􏰼icting and cannot b e
simultaneously satis􏰬ed􏰦
This recursive scheme resembles Badler􏰸s 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 di􏰶er 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 d􏰸s reliance on geometric relationships alone􏰦 Nevertheless the metho d is
end􏰫e􏰶ector goal􏰭 b efore a minimizing change in the current joint variable can b e
pro cedure must iterate until either all end􏰫e􏰶ector
usually stable
exp erimenting
instabilities do o ccur when p osition and orientation constraints con􏰼ict 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 di􏰬ed to accomo date direct inverse kinematic
constrained manipulation􏰦 This chapter brie􏰼y 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 di􏰶erent 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 eci􏰬cally􏰽 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 program􏰸s design
􏰰􏰨
manipulation􏰭 as well as

CHAPTER 􏰱􏰦 AN INTERACTIVE EDITOR 􏰱􏰳
animation of skeletons de􏰬ned 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 􏰴e􏰦g􏰦 ball􏰫and􏰫so 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 de􏰬ne 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 end􏰫e􏰶ector within the joint hierarchy􏰦 A desired p osition and􏱂or
orientation for the end􏰫e􏰶ector may then b e sp eci􏰬ed􏰭 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 re􏰼ect
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 de􏰬ned as a series of keyframed p oses􏰭 each of which sp eci􏰬es 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 on􏰫the􏰫􏰼y 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 Catmull􏰫Rom 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 a􏰶orded by changing the keyframe spacing or the key p oses􏰦
A numb er of simple editing op erations are de􏰬ned for keyframe sequences􏰦 Ranges of keyframe p oses may b e copied􏰭 inserted􏰭 and􏱂or 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 VCR􏰫like 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 di􏰬ed 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 di􏰬ed 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 brie􏰼y 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 end􏰫e􏰶ector 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 de􏰬ned when a b o dy part is 􏰬rst selected􏰭 at which time
and an
end􏰫e􏰶ector 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 pre􏰫de􏰬ne 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 end􏰫e􏰶ector p osition must
b eing dragged􏰦 There are two p ossible approaches to determing the end􏰫e􏰶ector 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 end􏰫e􏰶ector 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 end􏰫e􏰶ector 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 end􏰫e􏰶ector􏰦 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 self􏰫rotation􏰭 􏰺warping􏰻 the cursor to the lo cation􏰦 Lo cating the end􏰫e􏰶ector along the segment axis eliminates the twisting􏰦
places the end􏰫e􏰶ector corresp onding onscreen problem of unexp ected
Determining an End􏰫E􏰶ector Goal
To compute new goal p ositions for the end􏰫e􏰶ector 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 end􏰫e􏰶ector is constrained to lie within the plane while
pro jection view􏰭 the cast ray may diverge from the line of
end􏰫e􏰶ector to the ray is no longer constrained to lie parallel to the image plane􏰦 The end􏰫e􏰶ector 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 end􏰫e􏰶ector􏰦 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 end􏰫e􏰶ector 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 insu􏰷cient 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 end􏰫e􏰶ector p osition
􏱊 Lo cking an end􏰫e􏰶ector orientation􏰦 This can b e a partial lo ck of only one or two directions
􏰴e􏰦g􏰦 lo ck Y orientation only􏰵􏰦
additional p ositioning aid􏰭 a small set of constraints have b een de􏰬ned 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 end􏰫e􏰶ector 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 di􏰬ed by either dragging the lo ck􏰭 or twisting the end􏰫e􏰶ector 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 insu􏰷cient 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 user􏰸s
p erformed b etween screen refreshes􏰦
minimize visible constraint violations􏰽 on a low􏰫p 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 􏰬gure􏰸s 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 su􏰷cient 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 su􏰷cient for interactive p ositioning􏰦
While lo cking end􏰫e􏰶ectors 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 in􏰫b 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 high􏰫p 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 end􏰫e􏰶ector 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 end􏰫e􏰶ectors are constrained􏰦
the feet clearly move through the 􏰼o or during the transition b etween is that the 􏰬gure􏰸s 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 resatis􏰬ed􏰦 In essence a series of single􏰫frame 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 on􏰫the􏰫􏰼y􏰦
Initial feedback suggests that even this simple approach to enforcing geometric constraints􏰭 com􏰫 bined with direct inverse kinematic manipulation􏰭 is a signi􏰬cant 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 di􏰬ed 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 brie􏰼y describ ed􏰦
As a bypro duct􏰭 a to olkit library for de􏰬ning 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 di􏰬cations 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 slider􏰫based p ositioning􏰭 the value of multiple􏰫joint 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 di􏰷cult 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 o􏰶er b etter p erformance􏰦
􏰲􏰦􏰮􏰦􏰧 Comments ab out Constraints
resp onse time
In Chapter 􏰰􏰭 the choice of the CCD􏰫based p enalty metho d for implementation within the 􏰬gure animation editor was largely based on p erformance issues􏰽 the alternative Lagrange multiplier􏰫based 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 su􏰷cient CPU sp eed to retain numerical stability􏰭 the Lagrange multiplier approach is the more general of the two􏰦 The CCD􏰫based metho d is fast b ecause it reduces a di􏰷cult 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 di􏰶erent typ es of constraints􏰭
including non􏰫geometric 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 satis􏰬ed􏰭 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 recti􏰬ed by sp ecifying additional geometric constraints on the knees􏰭 but cho osing and sp ecifying these auxiliary constraints would probably b e di􏰷cult and time􏰫consuming􏰦 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 o􏰶􏰫balance􏰦 The latter can b e implemented as a constraint on a 􏰬gure􏰸s center􏰫of􏰫mass􏰭 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 de􏰬ne 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 eci􏰬c ab out the time intervals and lo cations involved we
such as this identi􏰬es a numb er of simple constraints which are in e􏰶ect 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 satis􏰬er 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 Maciejewski􏰸s incremental algorithm for computing the topic are interesting reading􏰭 and may suggest alternate
Designing interactive interfaces which make e􏰶ective 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 con􏰼ict 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 Bruderlin􏰸s 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 ly􏰫Based Model ling􏰭 􏰧􏰨􏰩􏰲􏰦
􏰾BC􏰩􏰨􏰿 A􏰦 Bruderlin and T􏰦 Calvert􏰦 Goal􏰫directed 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􏰨􏰮􏰿 M􏰦F􏰦 Cohen􏰦 Interactive spacetime control for animation􏰦 Computer Graphics􏰭 􏰮􏰱􏰴􏰮􏰵􏰭 July 􏰧􏰨􏰨􏰮􏰦
􏰲􏰪

BIBLIOGRAPHY
􏰾CP􏰨􏰳􏰿 N􏰦 Badler C􏰦 Phillips􏰭 J􏰦 Zhao􏰦 Interactive real􏰫time articulated 􏰬gure using multiple kinematic constraints􏰦 In Proceedings􏰭 􏰧􏰨􏰨􏰳 Symposium on Graphics􏰭 pages 􏰮􏰯􏰰􏱆􏰮􏰰􏰳􏰭 􏰧􏰨􏰨􏰳􏰦
􏰲􏰯
manipulation Interactive 􏰪D
􏰾CWGL􏰩􏰨􏰿 T􏰦W􏰦 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􏰭 J􏰦J􏰦 Slotine􏰭 and T􏰦B􏰦 Sheridan􏰦 Inverse kinematic algorithms for redundant systems􏰦 In Proceedings IEEE Int􏰸l􏰦 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 computer􏰫animated 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 Publishers􏰭Inc􏰦􏰭 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􏰰􏰨􏰿 T􏰦N􏰦E􏰦 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􏰦 Di􏰶erential manipulation􏰦 In Proceedings of Graphics Inter􏰫 face 􏰸􏰨􏰧􏰭 􏰧􏰨􏰨􏰧􏰦
􏰾Hah􏰩􏰩􏰿 J􏰦K􏰦 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􏰹 Constraint􏰫based data􏰼ow􏰦 Computer Graphics􏰭 􏰮􏰱􏰴􏰮􏰵􏰭 July 􏰧􏰨􏰨􏰮􏰦
􏰾KB􏰩􏰮􏰿 J􏰦 Korein and N􏰦 Badler􏰦 Techniques for goal􏰫directed 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􏰩􏰪􏰿 C􏰦A􏰦 Klein and C􏰦H􏰦 Huang􏰦 Review of pseudoinverse control for use with kinemati􏰫 cally redundant manipulators􏰦 IEEE Transactions on Systems􏰭 Man􏰭 and Cybernetics􏰭 􏰧􏰪􏰴􏰪􏰵􏰹􏰮􏰯􏰰􏱆􏰮􏰰􏰳􏰭 March􏱂April 􏰧􏰨􏰩􏰪􏰦
􏰾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 ill􏰫conditioned equations of motion for articulated 􏰬gures􏰦 IEEE Computer Graphics and Applications􏰭 􏰧􏰳􏰴􏰪􏰵􏰹􏰮􏰪􏰪􏱆􏰮􏰯􏰮􏰭 May 􏰧􏰨􏰨􏰳􏰦
􏰾MK􏰩􏰨􏰿 A􏰦A􏰦 Maciejewski and C􏰦A􏰦 Klein􏰦 The singular value decomp osition􏰹 Computation and applications to rob otics􏰦 International Journal of Robotics Research􏰭 􏰩􏰴􏰱􏰵􏰭 Decemb er 􏰧􏰨􏰩􏰨􏰦
􏰾NN􏰨􏰳􏰿 Z􏰦R􏰦 Novakovic and B􏰦 Nemec􏰦 A solution of the inverse kinematics problem using the sliding mo de􏰦 IEEE Transactions on Robotics and Automation􏰭 􏰱􏰴􏰮􏰵􏰹􏰮􏰯􏰲􏱆􏰮􏰰􏰮􏰭 April 􏰧􏰨􏰨􏰳􏰦
􏰾Pau􏰩􏰧􏰿 R􏰦P􏰦 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􏰨􏰳􏰿 W􏰦H􏰦 Press􏰭 B􏰦P􏰦 Flannery􏰭 S􏰦A􏰦 Teukolsky􏰭 and W􏰦T􏰦 Vetterling􏰦 Numerical Recipes in C 􏰫 The Art of Scienti􏰬c 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 Int􏰸l 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 􏰧􏰨􏰩􏰲􏰦
Speci􏰬cation and Control􏰭 pages 􏰧􏰲􏱆􏰮􏰱􏰭
􏰾Sur􏰨􏰮􏰿 M􏰦C􏰦 Surles􏰦 An algorithm with linear complexity for interactive􏰭 physically􏰫based 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 Arti􏰬cial Intel ligence and Robotics on Animation􏰭 􏰧􏰨􏰩􏰩􏰦
􏰾WC􏰨􏰧􏰿 L􏰦C􏰦T􏰦 Wang and C􏰦C􏰦 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 Arti􏰬cial Intel ligence and Robotics on Animation􏰭 􏰧􏰨􏰩􏰩􏰦
􏰾WE􏰩􏰯􏰿 W􏰦A􏰦 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 Publishers􏰭Inc􏰦􏰭 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 MS􏰫CIS􏰫􏰩􏰨􏰫􏰳􏰨􏰭 University of Pennsylvania􏰭 􏰧􏰨􏰩􏰨􏰦
􏰾Zel􏰩􏰮a􏰿 D􏰦 Zeltzer􏰦 Motor control techniques for 􏰬gure animation􏰦 IEEE Computer Graphics and Applications􏰭 􏰮􏰴􏰨􏰵􏰹􏰰􏰪􏱆􏰰􏰨􏰭 􏰧􏰨􏰩􏰮􏰦
􏰾Zel􏰩􏰮b􏰿 D􏰦 Zeltzer􏰦 Representation of complex animated 􏰬gures􏰦 In Proceedings of Graphics Interface􏰭 pages 􏰮􏰳􏰰􏱆􏰮􏰧􏰧􏰭 􏰧􏰨􏰩􏰮􏰦