# 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

BSc Simon Fraser University

a thesis of the

submitted in partial fulfillment requirements for the degree of

Master of Science in the Scho ol

of Computing Science

All

repro duced

or other means

reserved This in whole or in

work may not b e part by photo copy

c Chris Welman SIMON FRASER UNIVERSITY Septemb er

rights

without the p ermission of the author

Name

Degree

Title of

Examining

APPROVAL

Chris Welman Master of Science

Inverse Kinematics and Geometric Constraints for Articulated Fig ure Manipulation

Dr L Hafer Chair

Dr TW Calvert Senior Sup ervisor

Dr J Dill

Dr D Forsey External Examiner

thesis

Committee

Date Approved

ii

Abstract

Computer animation of articulated gures can b e tedious largely due to the amount of data which must b e sp ecied at each frame Animation techniques range from simple interp olation b etween keyframed gure p oses to higherlevel algorithmic mo dels of sp ecic movement patterns The former provides the animator with complete control over the movement whereas the latter may provide only limited control via some highlevel parameters incorp orated into the mo del Inverse kinematic techniques adopted from the rob otics literature have the p otential to relieve the animator of detailed

sp ecication of every motion parameter within a gure while retaining complete control movement if desired

over the

This work investigates the use of inverse kinematics and simple geometric constraints as to ols for the animator Previous applications of inverse kinematic algorithms to computer animation are reviewed A pair of alternative algorithms suitable for a direct manipulation interface are presented and qualitatively compared Application of these algorithms to enforce simple geometric constraints on a gure during interactive manipulation is discussed An implementation of one of these algo rithms within an existing gure animation editor is describ ed which provides constrained inverse kinematic gure manipulation for the creation of keyframes

Contents

Intro duction Organization

Approaches to Figure Animation

BodyModels Scope

Skeleton Mo delling

Kinematic Methods

Forward Kinematics

Inverse Kinematics

Dynamic Methods

Forward Dynamics

Inverse Dynamics

ControlIssues

Summary

Evaluation ApplicationstoComputerGraphics

Ecient Algorithms for Direct Manipulation ASimpliedDynamicModel

Inverse Kinematics

The Inverse Kinematic Problem

Resolved Motion Rate Control

Redundancy

Singularities OptimizationBased Metho ds

The Jacobian Transpose Method

i

CONTENTS

ii

ImplementationDetails

ComputingtheJacobian

ScalingConsiderations

Integration

JointLimits A Complementary Heuristic Approach

The CyclicCoordinate Descent Method

Overview Comparison

Incorp orating Constraints

ConstraintSatisfaction

MaintainingConstraints

TheConstraintCondition

ComputingtheConstraintJacobianMatrix

ComputingtheConstraintForce

SolvingforLagrangeMultipliers

Feedback

Overview

Implementation Issues

Skeletons as Ob jects

Handles on Skeletons

Constraints on Handles

The Global Picture

Summary

A CCDbased Penalty Metho d

Skeletons

An

ASystemOverview

Interactive Editor

The Sequence

The Editor

Direct Manipulation

Constraints

Conclusion Summary Results

CONTENTS iii

Comments about Constraints Directions

Bibliography

List of Figures

a ob jects dened in lo cal co ordinate systems b Lo cal

rotations

applied

Localtranslationsapplied

Three congurations of a D redundant manipulator

A manipulator in a singular conguration

Interactive control lo op mo del for Jacobian transp ose

A case not handled well with the Jacobian transp ose metho d

cd

on the

tip of the manipulator on the left will not pro duce an exp ected conguration like the

oneshownontheright

ExampleCCDiterationstepforrotationjointi

A force applied to a point constrained to lie within a plane A constraining force normal to the plane is added to the applied force to obtain a legal force tangential to

theplane

Iteration steps for maintaining constraints

Agenericfunctionblock

Examplenetwork

A branching chain with two endeector constraints

Sampleskeletondescription

Sequenceeditorscreen

Plan view of goal determination in a an orthographic view

view

A gure b eing p ositioned by rst tilting then twisting the p elvis

a First keyframe p ose b Interp olated p ose c Second keyframe p ose

iv

metho d

Pulling inwards

p ersp ective

and b a

Chapter

Intro duction

Computer graphics has advanced to a p oint where generating images of striking realism and com plexity has become almost commonplace However making ob jects move convincingly within these pictures remains dicult particularly as ob ject models grow increasingly complex The specication and control of motion for computer animation has emerged as one of the principal areas of research within the computer graphics community

One area in particular which continues to receive attention is that of gure animation The goal of work in this area is to provide a means of generating lifelike p ossibly humanlike articulated gures and to design and control their actions within simulated environments Animated human gures could for example b e placed in simulated environments for ergonomic evaluation or simply to provide some aesthetic qualities to a presentation In the arts and entertainment area the concept of computergenerated characters roaming through articial worlds seems universally app ealing

Although gure animation raises technical challenges in b oth mo delling and rendering the fun damental problem of designing and controlling movement for these gures remains a particularly dicult one Part of the problem lies in deciding from which level of detail to approach the task

At one end of the scale the movements of individual parts of the b o dy

instant in time At the other end of the scale co ordinating movements

b etween gures and with the environment may require algorithms based on b ehavioural rules and knowledge bases Many of the most impressive examples of gure animation by computer have b een the result of algorithms implementing highlevel b ehavioural and motor control mo dels However these algorithms are often limited to generating sp ecic usually rep etitive movement patterns such as walking and running For the animator who wishes to create new movements there is little al ternative to painstakingly constructing the movement by hand Given the complex structure of a typical articulated gure this can involve an inordinate amount of work

must b e known for each and handling interaction

CHAPTER INTRODUCTION

The motivation b ehind this work is a desire to improve the animation capabilities of an existing interactive articulated gure animation package which is currently used to create movements for b oth dance and animation It is shown how inverse kinematic techniques for controlling rob otic manipulators can b e adopted to relieve the animator of some of the more tedious asp ects of creating new movements by hand After reviewing the inverse kinematic problem and solutions that have previously b een applied to gure animation a pair of alternative solution algorithms are presented and qualitatively compared These algorithms are simple yet eective and can supp ort b oth direct manipulation of articulated gures as well as the imp osition of simple geometric constraints up on a gure Implementations of these algorithms are presented and are applied to develop a basic set of interactive to ols for gure manipulation and animation

Organization

Chapter reviews computer animation techniques in general and discusses their applicability in the context of gure animation In Chapter the inverse kinematic problem is stated and com mon approaches to solving the problem are reviewed In Chapter a pair of fast reliable inverse kinematic algorithms are describ ed suitable for interactive manipulation tasks and diering from previous algorithms adopted for computer graphics In Chapter pro cedures for satisfying simple geometric constraints using these algorithms are considered Chapter intro duces an interactive gure animation editor and discusses implementation of the algorithms as p ositioning aids

Chapter

Approaches to Figure Animation

Placing this work in context requires some understanding of computer animation techniques in general and of how they may b e applied to gure animation in particular This chapter provides an overview of the advantages and disadvantages of basic motion control techniques for gure animation

The emphasis here is on metho ds to create and control the movements of articulated gures

rather than simply replaying digitized

itizing or rotoscoping the movements

convincing lifelike motion Rotoscoping can

graphic images to prerecorded video fo otage to attaching some

b o dy whose p ositions can b e tracked by computer and stored for later playback Neither of these are particularly attractive options the former b eing quite tedious and the latter relying on the availability of reliable unobtrusive instrumentation for the b o dy and sophisticated software to re construct the original motion from the sensor data neither of which are readily available yet A further limitation of rotoscoping is that a gure animated in this way is limited to those movements actually p erformed by a live sub ject Computer animation techniques can b e applied to animate gures in situations for which rotoscoping is neither a viable nor practical solution

Bo dy Mo dels

Scop e

First we must decide exactly what we are trying to animate Although the ideal computergenerated character would include muscle and tissue that deforms during movement skin and clothing that wrinkles and stretches hair that ows and expressive facial features the accurate mo delling ani mation and rendering of these attributes are research topics in their own right and work in these

movement It is

of real

fair to say that for many pro ductions dig remains the method of choice for obtaining

subjects

refer to techniques

ranging from visually matching sort of sensors to a p erformers

areas is still at the exp erimental stage For the time b eing we

animating simple approximations to real b o dies It is useful to

as a skeletal layer up on which muscle tissue and skin can later

is that any b o dy mo del can b e animated by moving an underlying skeletal approximation which need not b ear any resemblance to the nal rendered app earance of the character Thus the motion control problem for gures reduces to that of controlling the movement of an abstract articulated skeleton

Skeleton Mo delling

A skeleton can b e represented by a collection of simple rigid ob jects connected together by joints The joints are usually rotational but may also b e sliding or prismatic Each rotary joint may allow rotation in or orthogonal directions these are the degrees of freedom DOF of the joint A detailed approximation to the human skeleton may have as many as degrees of freedom although often fewer suce Restrictions on the allowable range of movements for a joint can b e approximated by limiting the rotation angle in each of the rotation directions at each joint

The individual ob jects comprising the skeleton are each dened in their own local coordinate

CHAPTER APPROACHES TO FIGURE ANIMATION

systems and are assembled into a

nested series of transformations In Figure a simple articulated limb is built up by applying lo cal rotations and translations to blo cks dened in their own lo cal co ordinate systems

More complex skeletons can b e built up by arranging the segments in a treestructured hierarchy Each no de in the tree maintains the rotations currently in eect at the corresp onding joint these joint rotations are osets from the orientation of the parent segment in the tree These nested transformations in the hierarchy ensure that segments inherit the rotations applied to joints higher in the tree a rotation applied at say the shoulder joint causes the entire arm to rotate and not just the upp er arm segment One joint in the skeleton needs to b e sp ecied as the ro ot of the tree

will have to restrict our attention to think of these simple approximations b e layered The imp ortant p oint here

recognizable gure in a global world co ordinate system by a

transformations applied to this

choice of which joint is to serve

an existing hierarchy around a new ro ot joint at any time The global transformations applied to any particular ob ject within the skeleton can be computed by traversing the hierarchy from the root to the segment and concatenating the lo cal transformations at each joint visited by the traversal

Most animation systems provide a means of building up the transformation hierarchy needed to dene a skeleton and it is easy enough to dene a simple grammar for sp ecifying skeletons Zelb Sims SZ has describ ed an interactive editor for designing new skeletons which applies some simple heuristics to streamline the pro cess Regardless of how it is created a skeleton denition will

joint move the entire skeleton in the world co ordinate system The as the ro ot is irrelevant and it is convenient to b e able to restructure

CHAPTER APPROACHES TO FIGURE ANIMATION

(a)

(b)

(c)

(d)

Figure a ob jects dened in lo cal co ordinate systems b Lo cal rotations applied cd Lo cal translations applied

minimally sp ecify the individual b o dy segment lengths the joint degrees of freedom and the overall hierarchy of the structure

A skeleton can b e animated by varying the lo cal rotations applied at each joint over time as well as the global translation applied at the ro ot joint The motion sp ecication and control problem is that of managing the way in which these transformations change over time In general there are two fundamental approaches to this problem kinematic and dynamic The following sections review b oth kinematic and dynamic metho ds for motion sp ecication in general the typ es of control available for each and applications of these to gure animation in particular

Kinematic Metho ds

Forward Kinematics

Forward kinematics involves explicitly setting the p osition and orientation of ob jects at sp ecic frame

times For skeletons this means directly setting the rotations

global translation applied to the ro ot joint to create a pose

of an animation a series of keyframe p oses can b e sp ecied at dierent frames with intermediate

at selected joints and p ossibly the To avoid doing this for each frame

CHAPTER APPROACHES TO FIGURE ANIMATION

p oses calculated

b e animated by displaying each intermediate p ose

by interp olating the joint parameters b etween the keyframes The gure can then

While linear

mediate p oses the resulting motion is usually unsatisfactory Discontinuous rst derivatives

inter in the use of

Interp olation often pro duces intermediate values that do not quite meet the animators requirements some control over the interp olation pro cess is crucial Las The interp olated values for a single DOF over the course of an animation form a trajectory curve which usually passes through the keyframe values The shap e of the tra jectory and hence the motion of the ob ject is dep endant on b oth the keyframed values and the typ e of interp olating spline used An interactive editor which

allows the

tra jectory

which the tra jectory

proposed which provide varying degrees of control over both the shape of a tra jectory and variations in sp eed along the tra jectory

Ko chanek KB describ es an interp olation technique based on a generalized form of piecewise cubic Hermite splines Three parameters continuity tension and bias are provided to control the length and direction of vectors tangent to the tra jectory at the keyframes Mo difying the direction of the tangent vectors gives lo cal control over the shap e of the curve as it passes through a keyframe Changing the length of the tangent vectors aects the rate of change of the interp olated value around the keyframe and thus provides some control over sp eed Some traditional animation eects such as action fol lowthrough and exaggeration Las can be achieved with appropriate settings of these parameters Unfortunately since all three parameters in the spline formulation aect the shap e of the curve the metho d provides no means for mo difying sp eed along a tra jectory without mo difying the tra jectory itself

Steketee and Badler SB advo cate a doubleinterp olant metho d which do es separate timing control from the tra jectory itself As b efore a tra jectory is dened as a piecewise cubic spline passing through a series of keyframed values An additional spline curve is also intro duced to control the

interp olation b etween keyframes is the simplest metho d for generating these

interp olated

higherorder

acceleration

p olation is well established Ste Gom HS Sho Stu and is invariably provided in commercial animation systems

Controlling interp olation

joint angles at the keyframes lend a jerky rob otic quality to the motion The

interp olation metho ds such as and hence smo other transitions

piecewise splines can provide continuous velo city and b etween and through the keyframes Keyframe inter

animator

is dened the quality of the movement can be further modied by varying the rate at

to view and mo dify the shap e of a tra jectory can b e a useful to ol Once a

is traversed A numb er of parameterized interp olation metho ds

have b een

CHAPTER APPROACHES TO FIGURE ANIMATION

parameter with which the tra jectory curve is sampled This provides control over the parametric sp eed at which the tra jectory curve is traversed However there is often no meaningful relationship b etween parametric sp eed and actual sp eed in the geometric sense sampling a curve at uniformly spaced parametric p oints will not necessarily yield uniformly spaced p oints in space This approach to timing adjustment therefore is somewhat ad hoc and nonintuitive requiring a trialanderror pro cess on the part of the animator to achieve the desired velo city prole along the tra jectory

More intuitive control over sp eed along a tra jectory can b e obtained by reparameterizing the tra jectory curve by arclength Arclength parameterization provides a direct relationship between parametric sp eed and geometric sp eed along a tra jectory the distance d travelled along a tra jectory is proportional to the increment s of the tra jectorys arclength parameter s Allowing the animator to sketch a curve representing s over time provides an intuitive mechanism for varying sp eed along the tra jectory BH However although theoretically a reparameterization by arclength exists for any curve it is often not p ossible to nd an analytic solution for arbitrary curves and one must resort to numerical approximation metho ds Gir GP

Evaluation

Keyframebased computer animation has a direct analogy in traditional animation where key ani mation cels are drawn by senior animators while less exp erienced animators draw the action in the intermediate cels Computerbased keyframing is intuitive and the interp olation can usually b e p er formed fast enough to provide near realtime feedback For skeleton animation however keyframe interp olation do es not work well the few go o d examples of keyframed gure animation are more a tribute to the skill and patience of the animator than to the techniques suitability for the task

of freedom problem for interesting skeletons many DOFs for which values must b e provided the level of detail required

One ma jor diculty can b e lab elled the degrees

there are simply to o

from the animator to sp ecify even a single key p ose

is excessive Trying to control the interp olated modifying possibly hundreds of tra jectory curves can be tedious frustrating and errorprone While it is essential that the animator have some control at the joint level higher

motion by manually

levels of control are desirable for sp ecifying the co ordinated movements of groups of joints

Even supp osing that the numb er of degrees of freedom within a gure is manageable the common practice of displaying interpolated joint angles as a set of three splined tra jectory curves is rarely helpful Unlike translations an ordered series of rotations do not combine intuitively making it dicult to predict the consequences of editing a single rotation tra jectory and almost imp ossible to decide on the appropriate changes to all three curves which will pro duce a desired change in a single

one each for the XY and Z rotation directions at each joint

CHAPTER APPROACHES TO FIGURE ANIMATION

b o dy segments motion

The hierarchical structure of the skeleton also causes problems The only joint which an animator

can explicitly position is the root joint in the hierarchy the positions of all

skeleton dep end on the rotations at ancestor joints This makes it dicult to enforce p ositional

constraints when creating a keyframe p ose For example if

the hierarchy ro ot

The same b oth feet are interp olating

problem crops up during interp olation Even if an

p ositioned correctly in a series of keyframe p oses there is no guarantee that simply joint rotations will maintain the correct fo ot p ositions at the intermediate frames

for a bip ed is at the is troublesome if the fo ot is already in at the knee will move the fo ot which must then b e rep ositioned by mo difying

p elvis then placing

place then a b end

the rotation at the

marginally useful

allow a knee b end which leaves the fo ot in place However this will also move the

which may move another previously p ositioned b o dy segment such as the other fo ot This enforcing multiple p ositional constraints a frustrating pro cess

a fo ot

on the o or and keeping it there

hip joint The ability to rearrange the hierarchy ab out a new In our example making the supp ort fo ot the new ro ot of the

ro ot joint is only

would b o dy makes

It is quite common to see interp olated keyframed sequences for gures in which the feet seem to p enetrate through or slide around on the o or While this can b e remedied by sp ecifying additional

keyframes as the keyframe

framebyframe p ositioning of traditional stopaction animation claymation for example This defeats the whole purp ose of interp olation which is intended to relieve the animator from the tedium of sp ecifying the motion on a framebyframe basis

While forward kinematics combined with a simple interp olation scheme may suce for animating simple ob jects it is not really up to the task of animating articulated gures

Inverse Kinematics

Using forward kinematics the position of any ob ject within a skeleton can only be indirectly con

spacing b ecomes smaller the animation pro cess b egins to resemble the

trolled

inverse

the end

desired

oers an attractive alternative to explicitly rotating individual joints within a skeleton An animator can instead directly sp ecify the p osition of an endeector while the system automatically computes the joint angles needed to place the part Not surprisingly the inverse kinematic problem has b een studied extensively in the rob otics eld although it is only fairly recently that the techniques have

by specifying rotations at the joints between the root and the

kinematic techniques provide direct control over the placement of an endeector ob ject at

of a kinematic chain of joints solving for the joint rotations which place the ob ject at the lo cation In light of the preceeding discussion it should b e apparent that inverse kinematics

other ob jects in the

hierarchy rest of the

animator has made sure that

ob ject itself In contrast

CHAPTER APPROACHES TO FIGURE ANIMATION

b een adopted for computer animation

Chadwicks Critter system

keyframes CHP Badler has

straints on multiple b o dy parts

range limits into the inverse kinematic solution CP ZB Both Girards PODA system GM and Sims gait controller SZ provided highlevel lo comotion mo dels for skeletons using inverse

p ermits inverse kinematic manipulation of prop osed an inverse kinematic algorithm to

a skeleton for creating enforce p ositional con during skeleton manipulation BMW and has incorp orated joint

kinematics to generate

ments and tra jectories

joint angles as the feet are moved along tra jectories b etween each fo othold

the leg motion In these systems a planning stage determines fo ot place while the inverse kinematic algorithm is responsible for generating the leg

Inverse kinematics provides higherlevel control over joint hierarchies than simple forward kine matics moving the limbs of a skeleton b ecomes much more manageable However often the un derlying metho d for generating motion still relies on strictly kinematic metho ds Unfortunately kinematic metho ds do not pro duce convincing movement without a considerable amount of eort

on the animators part Often the motion exhibits a weightless quality

by editing the tra jectories and timing for individual forward and inverse do not pro duce movement with exp ect from our exp erience with the physical laws of

Dynamic Metho ds

which is dicult to disp el Kinematic metho ds b oth integrity we have come to

Animation based on dynamic simulation is attractive

ical laws providing a level of realism that is extremely dicult to duplicate with kinematic metho ds For dynamic analysis ob ject descriptions must include such physical attributes as the center of mass the total mass and the moments and pro ducts of inertia Although there are many formulations for the equations of motion they are all essentially equivalent to the familiar F ma which relates the

acceleration a an ob ject

of mass The motion

and torques which may vary over time Techniques for dynamic motion control can b e categorized as either forward dynamic metho ds or inverse dynamic metho ds The essential distinction b etween the two is in the way that the basic forces and torques driving the motion are arrived at

Forward Dynamics

Forward dynamics involves explicit application of timevarying forces and torques to ob jects Some forces such as those due to gravity and collisions between ob jects may be handled automatically

degrees

the sort

the real world

b ecause

the generated motion adheres to phys

of freedom of dynamic

of mass m undergo es in resp onse to a force F applied at the ob jects center generated by physical simulation is controlled by the application of forces

a similar equation relates angular acceleration to applied torques

CHAPTER APPROACHES TO FIGURE ANIMATION

by the animation system other forces are applied directly by the animator to ob jects in the scene The motion is approximated by taking a series of discrete steps in time and at each step solving the equations of motion for the acceleration an ob ject undergo es in resp onse to the applied forces Given the position and velocity of an ob ject from the previous time step the acceleration a can be twice

integrated to determine a new velo city and

intro duction and overview of the basics of forward dynamic simulation

can b e found in Wil A comprehensive

ob jects accounting for collisions is presented by Hahn Hah

of the solution metho d A

has On complexity for n

recursive formulation which

of simple articulated structures to b e p erformed reasonably complex articulated skeletons cannot singlepro cessor machines although the recursive

solution degrees

reduces

the complexity to O n in close to in general

p osition resp ectively for the

current time step A go o d for animating rigid b o dies approach to simulating the motion of rigid p olyhedral

Extending this approach to the simulation of articulated skeletons is challenging In general there will b e one equation of motion for each degree of freedom in the skeleton This leads to a large

system of equations which must b e exp ense The formulation adopted to

Complicating matters is the fact that the equations of motion for articulated skeletons are con siderably more complex than those for simple ob jects since they must include terms to model the interactions b etween connected b o dy parts This coupling of the dynamics equations makes control extrememly dicult since movement of one segment of the skeleton will exert forces and torques on adjacent segments the notion that the motion of the skeleton can b e adequately controlled by applying joint torques individually is incorrect Wil Eorts to counteract this unwanted prop agation of torques usually involve placing springs and damp ers at each joint to maintain a desired orientation Unfortunately this typ e of control invariably leads to a sti set of equations which causes severe instability in most numerical solution techniques A summary of numerical stability and control issues that must b e addressed during dynamic simulation is presented in Gir

solved by numerical metho ds at considerable computational represent the equations of motion signicantly aects the cost for the matrixbased GibbsApp ell formulation for example of freedom Wil Armstrong has proposed an alternative

AG enabling dynamic simulations realtime But dynamic simulation of b e p erformed at interactive sp eeds on

formulation may b e fast enough to b e tolerable

Comp ounding the

articulated skeletons are inherently illconditioned indep endent of their formulation Mac The

problem of numerical instabilities is the fact that the equations of motion for

illconditioning arises

one degree of freedom pro duce large accelerations elsewhere almost all numerical solution techniques have diculty handling such cases Maciejewski contends that these situations o ccur frequently for articulated gures and are inherent in the structure of most skeletons The illconditioning of the

when the skeleton assumes a p osture in which small incremental changes in

CHAPTER APPROACHES TO FIGURE ANIMATION

equations has implications not only for dynamic analysis but inverse kinematic algorithms as well Mac gives a lucid description of the problem and discusses metho ds for detecting and handling the illconditioning in b oth cases

One of the earliest attempts to control an articulated gure purely through forward dynamic simulation was Wilhelms V ir y a system Wil V ir y a p ermitted the interactive design of force or torque versus time functions for individual degrees of freedom Force and torque keyframes could b e sp ecied at dierent times cubic splines were then used to construct the force and torque proles over the course of the entire motion sequence During dynamic simulation these forcetorque proles were sampled and combined with forces due to collisions and gravity to determine instantaneous force and torque measurements for the current time step The use of interp olating curves is conceptually similar to the direct kinematic keyframe interp olation approach describ ed previously The dierence

is that the motion is driven not directly

equations of motion V ir y a exhibited most of the problems outlined ab ove In particular Wilhelms

by the interp olated curves but indirectly through the

equations made control of the eorts to simulate skeleton motion using pure forward

WCH

gure dicult and non dynamics rep ort similar

rep orts that the coupling of the dynamic

intuitive Other problems AG

Even supp osing that a reliable and fast numerical solution technique is available the lack of intuitive control remains the principal problem in using forward dynamics for animation In fact forward dynamic simulation is b est suited for tasks which can b e p osed as initialvalue problems That is tasks for which initial p ositions and velo cities and forcetorque proles are known a priori and the goal is to generate the resulting motion This formulation may b e satisfactory for animating scenes of simple inanimate ob jects realistically tumbling and b ouncing through an environment but

do es not apply for the animation of sp ecic tasks For example simulating a ball b ouncing

o or is simple to do given an initial height and velo city the simulation need only consider the force

on a

convincing motion However if the

goal is to have the ball b ounce three times and land in

the exact initial p osition and release velo city of the ball which will

determine Yet this is precisely the sort of problem that app ears in animation the animator knows what motion should o ccur but do es not know in advance the initial conditions and forcetorque

of gravity and reactions to collisions with the o or to generate

proles

needed to pro duce the desired result

Inverse Dynamics

dynamic metho ds automatically determine the force and torque functions needed to accom

Inverse

plish a stated goal In the degenerate case the stated goal is a complete description of the motion

a cup the

problem is much more dicult land it in the cup is dicult to

CHAPTER APPROACHES TO FIGURE ANIMATION

and the aim is to determine the forces and torques which repro duce the motion under forward dy namic simulation While this case is of interest in rob otics its application is of little use in an animation system after all if the motion tra jectories and timing are known beforehand the expense of the physical simulation is unnecessary More interesting are recent metho ds which allow rela

tively highlevel constraints or goals to b e necessary to meet the goals

Geometric Constraints

modelling were presented including pointtopath constraints for moving control an ob jects orientation The forward dynamics simulation of the move the mo del towards a state in

sp ecied and which then compute the forces and torques

somewhat the distinction selfassembling structures

the geometric constraints

the laws of Newtonian mechanics

mo del was dened as simple constraints for pointtopoint constraints for attaching two ob jects together

Barzel and Barr BB made early use of

a collection of ob jects related by geometric constraints A number of useful

inverse dynamics for mo delling A

an ob ject along a predened path

and twist constraints to forces and torques into a mo del These constraint forces and torques act in concert to which all the constraints are satised This approach blurs b etween mo delling and motion control as it allows for the animation of if the constituent parts of the mo del initially are in a state which violates turning on dynamic simulation results in the mo del assembling itself using

constraints were used to intro duce

Forsey and Wilhelms have used inverse dynamics to manipulate an articulated skeleton into keyframe p ositions for a traditional kinematic interp olation system FW The Manikin system p erformed dynamic analysis during interaction with the gure using Armstrongs recursive formu lation for the equations of motion A p ositional goal for a b o dy part could b e sp ecied interactively with M anik in computing the forces to push the part towards the goal This allowed manipulation of the gure in a manner similar to inverse kinematic manipulation The imp osition of p ositional con straints up on b o dy parts was accomplished by articially increasing the mass of constrained parts with the system constantly computing additional forces necessary to keep the part in place as other parts were moved Motion sequences could b e generated by storing the state of the b o dy at dierent p oints during the dynamic analysis and later using these stored states as keyframes for kinematic interp olation

The penaltyforce approach taken here of converting all constraints into forces and torques which steer the motion during dynamic analysis has its limitations The p enalty forces are often mo delled

as simulated springs and damp ers which deliver This metho d of control is vulnerable to stiness sirable oscillations ab out constraint satisfaction

a force prop ortional to the velo city of the motion in the resulting system of equations and by unde p oints Cho osing appropriate spring and damping

CHAPTER APPROACHES TO FIGURE ANIMATION

co ecients for the constraints is often a matter of trialanderror

In contrast to the p enaltyforce approach a numb er of formulations for the dynamic equations of motion can include explicit constraint equations Isaacs Dynamo system IC IC combines keyframed kinematic constraints with inverse dynamics Rather than causing the intro duction of additional forces into the simulation the kinematic constraints are instead used to remove degrees

of freedom from the system

The remaining accelerations

ensures that reactant forces due to the keyframe constraints are

the unconstrained DOFs This allows the kinematic constraints

of a skeleton while the other unconstrained parts react realistically to the prescrib ed motion In cases where all parts are constrained the technique reduces to a simple keyframing approach This approach illustrates an interesting mixture of dynamic simulation with kinematic control However Isaacs most ambitious attempt at skeleton animation is the simulation of a traditional marionette controlled by ro ds and strings attached to the limbs While technically impressive this example p oints out the need for b etter metho ds of control over dynamically simulated skeleton motion

NonGeometric Constraints

Consider the inverse dynamic problem of moving a p oint mass from p osition A to p osition B in a given time interval t There is no unique force function over the interval t which will accomplish this the system must cho ose b etween applying a large force for a short p erio d of time or applying

since they implicitly sp ecify some of for unconstrained DOFs can then b e

the accelerations in the system solved for The solution metho d

a smaller force over a

p osition B at time t

moving from A to B but also how the motion is to o ccur A numb er of metho ds have b een prop osed which attempt to describ e the quality of motion by considering nongeometric constraints in the inverse dynamic solution These approaches are based on wellestablished techniques for optimizing functions sub ject to a set of constraints

Brotman and Netravali BN prop ose an inverse dynamic approach to motion interp olation which uses p enalty forces to enforce keyframed kinematic constraints However the solution in

longer p erio d b oth metho ds may achieve the goal of reaching the keyframed This problem is one of determining not only what is to o ccur in this case

corp orates an

formulated as that of solving for the set of constraint forces which

p enalty forces The problem is minimizes the energy exp ended

in meeting the

constraints imp osed by kinematic keyframe values

additional constraint on the energy exerted by these

Girard Gir has applied constrained optimization techniques

along predened limb tra jectories for articulated gures Girard notes that the choice of optimization criteria has a signicant eect on the p erceived quality of motion Solving for a velo city prole which

intro duced into the to sp ecify motion for

solution for some parts

to determine sp eed distribution

minimizes energy exp enditure yields a relaxed swinging motion for the limb while

ab out the end of the limb yields movement suggestive of such goaldirected tasks as

ob ject The establishment of additional correspondences between optimization criteria and expressive

CHAPTER APPROACHES TO FIGURE ANIMATION

qualities of movement remains an op en area

These constrained optimization metho ds

limbs are known in advance and attempt to derive the b est set of forces and torques which move the limb along the path This sidesteps the fundamental problem of synthesizing the limb tra jectories for coordinated movement in the rst place Witkin and Kass WK have proposed an intriguing metho d of motion synthesis they call Spacetime Constraints which they demonstrated to b e capable of synthesizing b oth the tra jectories and the timing of movements for simple articulated gures This use of constrained optimization seems particularly promising as it seems capable

of pro ducing

However the

b e considered

limitations of the metho d Coh

of research

assume that the complete or partial motion paths for

complex co ordinated physicallycorrect motion with very little input from a user approach results in very large systems of equations which must b e solved and cannot useful for interactive gure animation Ongoing research is addressing the interactivity

Badler LWZB has used a form of constraintbased inverse dynamics to synthesize the tra jectories of limbs charged with the task of moving a load b etween two dierent p ositions The tra jectories are computed incrementally and are constrained by measures of strength comfort and exertion The iterative nature of the algorithm diers fundamentally from the global solution found by optimization metho ds Instead a set of biomechanical heuristics which are intended to mimic the pro cess by which p eople move loads are used to guide the solution pro cess The metho d successfully produces feasible albeit suboptimal limb tra jectories which accomplish the task

Control Issues

The research eorts outlined ab ove are attempts to provide higher levels of control over b oth kine matic and dynamic motion The goal is to b e able to sp ecify movements at the task level and to

have the system take care of the underlying details of pro ducing state of these eorts it seems that it will b e some time b efore the

synthesizing motion to accomplish arbitrary tasks oping sp ecial purp ose control strategies for sp ecic for decomp osing highlevel task descriptions such

into lowerlevel movement

primitives may consist of

simulations constrained inverse dynamic goals or a mixture of all these approaches

primitives and for the

keyframes for interp olation inverse

the motion Given the current emergence of systems capable of However there has b een some success in devel typ es of movements The system is resp onsible

as walk to co ordination

the do or or reach of these primitives

for the cup The lowlevel kinematic goals forward dynamic

minimizing jerk reaching for an

CHAPTER APPROACHES TO FIGURE ANIMATION

Zeltzer was an early prop onent of the need for highlevel control over articulated gures Zela He describ es a control strategy for synthesizing walking sequences for a skeleton Highlevel walking instructions are decomp osed into a set of motor control programs MCP which drive the motions of individual limbs or joints The control stategy is based on a nitestate machine resp onsible for activating and deactivating the appropriate MCPs at the appropriate times Zeltzers MCPs consisted of kinematic joint values obtained from rotoscop ed human walks and thus were purely

kinematic Nevertheless the system demonstrated

the usefulness of the concept

Building on Zeltzers work Bruderlin BC develop ed a similar hierarchical control strategy for generating bip ed walking sequences but incorp orated dynamic simulation to derive leg motion rather than relying on rotoscop ed data The user is able to instruct a skeleton to walk at a particular sp eed and is able to sp ecify b oth desired step frequency and step length These instructions are decomp osed into dynamicallybased lowlevel MCPs which drive the motion of an abstract kneeless pair of legs The MCPs essentially p erform dynamic interp olation of a set of kinematic keyframes for the leg movements during the walk cycle The kinematic keyframe values and spacing are derived from the input parameters combined with knowledge ab out human lo comotion patterns gleaned from the biomechanics literature The forces and torques driving the motion of the simplied walking mechanism are iteratively adjusted until the keyframed joint angles are achieved at the correct times A purely kinematic overlay of the skeletons jointed legs onto the underlying mechanism is then p erformed The algorithm is able to pro duce a wide range of realistic walking sequences and is a true hybrid of b oth dynamic and kinematic motion control The decision to use a simplied dynamic mo del sp ecically tuned for walking seems sound the resulting system of equations is small relatively stable and inexp ensive to solve A similar approach has b een used by this author to build a jumping algorithm based on the simulation of a simple underlying massandspring mo del

Unfortunately the highlevel control provided by algorithms of this nature come at the exp ense of generality each control strategy must b e tuned for a sp ecic movement But developing such a control strategy is dicult Deriving the equations for simulating the dynamics of the underlying mechanism requires some mathematical sophistication In the absence of an inverse kinematic algo rithm Bruderlins metho d of mapping the motion of the underlying dynamic mo del to the motion of the skeleton can p ose problems to the implementor To a large extent the success of the ab ove control strategies is due to the predictable rep etitive nature of lo comotion Developing highlevel control strategies for arbitrary movement sequences still seems a distant goal

CHAPTER APPROACHES TO FIGURE ANIMATION

Summary

What has hop efully emerged from the discussion so far is that no one technique has emerged as

a clear winner A successful gure animation system is

discussed ab ove to some degree Pure dynamics applied

problems as it addresses unless it is conned to sp ecic

into automatic motion synthesis from highlevel constraints while promising is still at to o early a stage to b e considered useful For the time b eing designing arbitrary movement sequences remains in the hands of the animator

A simple interactive keyframe editor in the hands of a user who understands how the b o dy moves and has some patience can pro duce some surprisingly go o d animation sequences even for gures as complex as the human form Dynamic simulation or algorithmic motion mo dels while useful in some contexts will only b e appreciated if they can alleviate some of the work involved in interactively handcrafting new movement sequences and it can b e argued that given the current state of research in these areas this is not generally the case The most promising interactive techniques reviewed in this chapter are those based on the use of inverse kinematics which provide a level of control higher than simple forward kinematics yet still leave the user with complete control over the animation

In the remaining chapters the use of inverse kinematics to complement an existing interactive keyframe editor is explored The goal is to address the limitations of a simple forward kinematic approach by providing a set of to ols which supp ort direct manipulation of kinematic chains within a gure and the imp osition of simple geometric constraints which are maintained during keyframe creation and interp olation Along the way we identify two inverse kinematic algorithms which dier from those previously adopted for computer graphics and describ e their suitability to the problem

likely to incorp orate all of the

to gure animation seems to raise as many movement control strategies The research

techniques

Chapter

Inverse Kinematics

The inverse kinematic problem has b een studied extensively in the rob otics literature which remains the b est source of information on the sub ject In this chapter we formally state the problem and review the most common approaches to solving it Previous applications of these approaches to computer graphics are also describ ed

The Inverse Kinematic Problem

Section showed that a skeleton can be modelled as a hierarchical collection of rigid ob jects connected by joints We will refer to a kinematic chain of segments within a skeleton as a manipulator and will assume that the joints connecting segments within this chain are revolute joints rotating ab out a single axis One end of the manipulator the base is xed and cannot move the distal end of the chain is free to move The endeector is emb edded in the co ordinate frame of the most distal joint in the chain the endeector p osition is a p oint within this frame and the endeector orientation refers to the orientation of the frame itself

At each joint in the chain a joint variable determines a transformation M b etween the two adjacent

co ordinate frames sharing the joint The transformation Mi at of a translation and a rotation b oth of which are relative to the That is

Mi Txi yi ziRi

a rotation joint i is a concatenation co ordinate frame of joint is parent

where Txi yi zi is the matrix that translates by the oset of joint i from its parent joint i and Ri is the matrix that rotates by i ab out joint is rotation axis

CHAPTER INVERSE KINEMATICS

The relationship b etween any two co ordinate systems i and j in the chain is found by concate nating the transformations at the joints encountered during a traversal from joint i to joint j

j

nonlinear equations to b e do es not exist instead the

Mi

Mi Mi Mj Mj

So the p osition and orientation of the

concatenating the transformations at each joint in the manipulator

Given a vector q of known joint variables then the forward kinematic problem of computing the p osition and orientation vector x of the endeector is a simple matter of matrix concatenation and has the form

x fq

But if the goal is to place the endeector at a sp ecied p osition and orientation x then determining the appropriate joint variable vector q to achieve the goal requires a solution to the inverse of

q f x

Solving this inverse kinematic problem is not so simple The function f is nonlinear and while there is a unique mapping from q to x in equation the same cannot b e said for the inverse mapping of there may b e many qs for a particular x The most direct approach for solving the problem would be to obtain a closedform solution to But closedform solutions can only be derived

solvedPau

Resolved Motion Rate Control

Since the nonlinear nature of equation makes it dicult to solve a natural approach is to

linearize the problem ab out the current manipulator conguration

then

the

relationship

b etween

joint velo cities and the

velo city of the

endeector is

x Jqq

Jacobian matrix

The linear relationship is given by the

endeector

with resp ect to the base frame is found by simply

sp ecic characteristics and even these result in a set of A general analytic solution for arbitrary manipulators problem must b e solved with numerical metho ds for solving systems of nonlinear equations The most common solution metho ds are based on either matrix inversion or

optimization techniques

for a restricted set of manipulators with

J

f q

p osition and orientation is the dimension of the endeector vector x which is usually either for a simple p ositioning task or for a more general p ositionandorientation task The ith column of J represents the incremental change in the p osition

and orientation of the endeector resulting from an incremental change in the joint variable qi

Inverting the relationship of provides the basis for resolved motion rate control

q J q x

If the inverse of J is known we can compute incremental changes in the joint variables which pro duce a desired incremental change in the endeector p osition and orientation

CHAPTER INVERSE KINEMATICS

which maps changes in the joint variables q to changes in the endeector

x J is an m n matrix where n is the

numb er of joint variables and m

A simple iterative scheme for solving

At each iteration a desired x can

p ositions The joint velo cities q can then

once to nd a new joint state vector q The

the desired goal Note that since the linear relationship represented by J is only valid for small p erturbations in the manipulator conguration Jq must b e recomputed at each iteration A pro cedure for eciently computing the Jacobian is presented in Section

Of course this scheme assumes that the Jacobian matrix is invertible that J is b oth square and nonsingular This assumption is not in general a valid one Diculties arise when a manipulator is redundant or when it passes through or near a singular conguration

Redundancy

A manipulator is considered kinematical ly redundant when it p ossesses more degrees of freedom than

at some p oint x y

of the congurations

redundant for this D p ositioning task

the b e b e

inverse kinematic problem can b e based on equation

computed computed

from the current and desired endeector using the Jacobian inverse and integrated rep eats until the endeector has reached

pro cedure

are required to sp ecify a goal for the endeector

Figure The manipulator p ossesses degrees of freedom the rotation angles at each joint For a simple p ositioning task the goal is to place the endeector the tip of the distal link of the chain

For example consider the simple D case in

As the gure shows for a given goal x y there is no unique solution each shown will place the tip at the goal p osition The manipulator is therefore

In general p ositioning an ob ject in Cartesian space requires the sp ecication of six co ordinates three for lo cation and three for orientation Therefore any manipulator p ossessing more than six degrees of freedom is redundant for the general Dspace p ositioning task and there is no unique

CHAPTER

INVERSE KINEMATICS

(x,y)

θ3

θ2

θ1

Figure Three congurations

of a D redundant

manipulator

set of joint values solving the inverse kinematic problem

For a redundant manipulator the Jacobian matrix has fewer rows than columns and cannot inverted In this case equation is underdetermined and there are an innite numb er of

b e

solutions from

useful solution

Mo orePenrose

optimal in the sense that it yields solutions with a minimum Euclidean norm for cases in which is underdetermined m n and that in cases in which the system is overdetermined m n a leastsquares solution is obtained In practice these prop erties ensure that joints move as little as p ossible to match the desired endeector velo city as closely as p ossible

Exploiting Redundancy

Since a redundant manipulator can satisfy a p ositioning task in any numb er of ways it is often useful to consider exploiting the redundancy in an attempt to satisfy some secondary criteria This can be accomplished by incorp orating an additional term into equation

which to choose If J in is replaced by some generalized inverse Jy then a to the underdetermined problem can b e found One such generalized inverse is the pseudoinverse Gre GM It can b e shown KH that this pseudoinverse is

q J y x I J y J r H q

minimized sub ject to satisfying the

The function H q is a measure of some criterion to b e

primary positioning task The other component I Jy J

those components of the gradient vector rH q which lie in the set of homogeneous solutions to A homogeneous solution to is a set of joint velo cities q which do es not change the endeector

is a pro jection operator

which selects

CHAPTER INVERSE KINEMATICS

y

singular direction

x

Figure A manipulator in a singular conguration

p osition ie for which x In eect then the rst term of the general equation

joint velo city vector which pro duces the desired change in the endeector p osition while the second term exploits the redundancy of the manipulator by varying these joint velo cities in such a way that H q is minimized without disturbing the endeector position By exploiting redundancy in this manner secondary goals have b een created to avoid collisions with obstacles Bai to exploit joint range availability GM KH and even to maintain manipulator dexterity by avoiding kinematic singularities SS

Singularities

The pseudoinverse metho d outlined ab ove provides useful solutions to when the Jacobian matrix J is rectangular and therefore not invertible But we must also consider the case where J is not invertible b ecause it is singular A matrix is said to singular when two or more rows are linearly dep endent and a manipulator is said to b e in a singular conguration when the Jacobian b ecomes singular Figure depicts a simple example of a jointed manipulator in a singular conguration In this example an incremental change to any of the joint angles will result in approximately the same movement of the endeector in the y direction no combination of joint velo cities will pro duce an endeector velo city in the singular ie x direction The Jacobian matrix computed for this conguration will contain zero es in the rst row and is therefore singular and cannot b e inverted

The pseudoinverse can still b e applied to obtain a useful solution when J is singular However as a manipulator passes through a singular conguration there are discontinuities in elements of

Although intuitively it might seem obvious that a rotation at any joint will result in at least some movement in the x direction recall that equation deals with instantaneous quantities

selects a

CHAPTER INVERSE KINEMATICS

the computed pseudoinverse due to the change in rank of J at the singular conguration Mac Furthermore as the manipulator approaches this conguration the pseudoinverse tends to pro duce large joint velo cities Numerical integration techniques typically do not handle such derivative spikes well The problem manifests itself as a tendency of the manipulator to oscillate wildly around the singular conguration So while the pseudoinverse is able to provide a usable solution at a singular conguration its principal drawback is that it do es not provide a continuous stable solution around singularities While industrial rob otic manipulators may b e programmed to follow tra jectories which explicitly avoid singular congurations for just this reason this is not really an option for an algorithm to b e used for computer animation

The Singular Value Decomp osition

Numerical instabilities near singular congurations are a ma jor problem which raises the question of whether there is a means of detecting and correcting the problem Probably the most useful to ol for analyzing the Jacobian matrix is the singular value decomposition SVD PFTV The SVD theorem states that any matrix can b e written as the pro duct of three nonunique matrices

The pro cedure for computing the SVD of a matrix is b eyond well known and describ ed elsewhere PFTV MK The interpretation of each of the three matrices U D and V

J UDV

T

the scop e of this discussion but is signicance of the SVD lies in the

For an m n matrix J D is an n n diagonal matrix with nonnegative diagonal elements known as singular values If one or more of these diagonal elements is zero then the original matrix is itself singular Even b etter the ratio of the largest singular value to the smallest one the condition number of the matrix is a measure of how il lconditioned the matrix J is When the condition number is too large then the matrix is illconditioned It is this illconditioning that is responsible for the large joint velo cities generated by the pseudoinverse near a singular conguration Mac

The other matrices U and V are orthonormal bases for the range and nul l space respectively of J For any zero singular values in D the corresp onding columns in V form a set of orthogonal vectors which span the space of homogeneous solutions to equation ie the set of joint velo cities which will not move the endeector Likewise the nonzero singular values have corresp onding columns in U which span the space of solutions which wil l move the endeector We will refer to these basis matrices again when discussing constraints in Chapter

While the SVD provides a means for detecting illconditioning in the Jacobian matrix it do es ie its recipro cal approaches machine precision limits

CHAPTER INVERSE KINEMATICS

not in itself provide a way for dealing with the illconditioning Nevertheless it is useful as an analytical to ol Klein and Huang KH have used singular value analysis to demonstrate the optimal prop erties of the Mo orePenrose pseudoinverse Maciejewski Mac has used the SVD to illustrate the discontinuity that o ccurs in the pseudoinverse at a singularity and to develop a strategy for damping the high velo cities which o ccur near singular congurations But the cost of computing the SVD O n l og n for an n n matrix adds signicantly to the p eriteration cost of any control

algorithm so it is often not feasible to incorp orate it into online control schemes

MK do es describ e a metho d of incrementally up dating the SVD from one iteration to the next which reduces the cost to On per iteration but this requires careful implementation to reduce cumulative errors and the cost is still high enough to deter its use

OptimizationBased Metho ds

A fundamentally dierent approach to solving the inverse kinematic problem avoids the matrix inversion step altogether The idea is to cast the basic problem of equation as a minimization problem then apply standard iterative nonlinear optimization techniques to obtain a solution

As an example consider the problem of p ositioning the endeector

x at a goal p osition p The

distance from the current p osition xq to the goal p osition p serves

as

an

error

measurement

E q p xq

By varying the joint angle vector q the endeector either moves away from p increasing the error measure or towards p decreasing the error Clearly the intent is to nd a joint vector q which minimizes the error measure Limits on the joint ranges of motion provide additional constraints on

the individual joint values qi Formally we

minimize subject to

need to nd a vector q which solves the problem

E q

li qi ui i n

where li and ui are the lower and upp er b ounds resp ectively on the value of joint variable qi For this example the error measure E is just the distance formula but the approach generalizes to more complex goals for the endeector since E q can be any arbitrary function of the joint vector q

This formulation is a classic nonlinear constrained optimization problem which can b e solved by

a numb er of standard numerical metho ds A go o d intro duction to the

issues to consider in selecting a solution metho d is presented by Press et al PFTV Gill et al survey a numb er of practical optimization techniques GMW The eectiveness of any particular

metho d is usually determined by the characteristics of the ob jective

function in this case E and

topic of optimization and the

Maciejewski

CHAPTER INVERSE KINEMATICS

of the constraints For our example a solver for minimizing smooth quadratic functions sub ject to linear inequality constraints would b e an appropriate choice

A typical solver will iteratively converge from an initial state towards a solution state at each step perturbing the state variables slightly and reevaluating the ob jective function to evaluate its progress Some solvers may make use of the gradient of the ob jective function rE to suggest new directions in which to p erturb the state vector This may increase the computation p er iteration but pay o in an improved rate of convergence toward a solution

Once selected the optimizer can b e thought of as a black b ox which

current joint vector q a function for evaluating the ob jective function E and possibly a function to

evaluate rE as well The output from the black b ox is a new joint vector error measure E and therefore solves the inverse kinematic problem

which minimizes the

Evaluation

While conceptually simple there are some practical diculties in implementing this approach Con

Furthermore there is no guarantee that a solver will nd the true global minimum for a con strained optimization problem Since most solvers converge on a solution by iteratively moving downhill along the ob jective function surface they cannot distinguish between a true global min imum and merely a lo cal minimum of the surface In practical terms this implies that the solver may return a joint vector q which do es not provide the b est solution and the user may have to somehow suggest a more appropriate conguration from which to restart the iterative search for a b etter solution

For interactive computer graphics the demands of interactivity place some additional demands on the solver Interactive dragging of a manipulator involves rep eatedly sampling the cursor lo cation onscreen to determine a goal p osition for the endeector then invoking the solver with the current manipulator state as the initial guess at a solution To maintain the illusion of continuous interactive control during dragging the screen needs to be updated at a reasonable refresh rate If the solver black b ox cannot pro duce a solution quickly enough to provide go o d feedback to a user dragging

strained optimization of

pro duced a collection of

Selecting an appropriate

dicult A solver may work well for one particular typ e of problem but fail miserably on others

arbitrary nonlinear functions is numerical metho ds which may or solver and determining what the

is fed as inputs the

still an op en research area which has may not work for a particular problem problem is when it fails to work can b e

each step should decrease or increase when maximizing the ob jective function framessec for example is a minimal goal to aim for during interaction

CHAPTER INVERSE KINEMATICS

a manipulator onscreen then the interface will feel sluggish and unresp onsive

that optimizers typically work b est when the initial state is close to the nal

interactive dragging the cursor may get ahead of the solver so that on the next invo cation of the solver the state of the manipulator b eing dragged is not close to the next solution As a result the solver may drastically alter the state while solving for the next solution the result is that the manipulator will seem to suddenly jump to a completely dierent conguration in order to satisfy the goal This is of course quite disconcerting to a user One option is to interrupt the solver and obtain its current state in order to refresh the screen However since the solver is free to try dierent paths as it feels its way towards the closest minimum there is no guarantee that intermediate solutions will be suitable for refreshing the screen

Applications to Computer Graphics

Each of the approaches ab ove have previously b een adopted for computer graphics The pseudoin verse metho d was intro duced to the computer graphics community by Girard in GM for his PODA gait generator Girard exploited the redundancy of animal limbs in an attempt to minimize joint limit violations using the pro jection op erator metho d of Section The inverse kinematic capabilities of Sims gait controller SZ and Chadwicks Critter system are also based on the tech nique None of these eorts suggest sp ecic solutions to the problems the metho d exhibits around singularities so it seems reasonable to assume that each of these systems will not p erform well near singular congurations

Badler and Zhao CP ZB have adopted the second approach for the Jack system applying

a variablemetric optimization pro cedure to

posture Joint range limits are presented as

functions for simple geometric constraints are develop ed These include for example p ointto p oint constraints p ointtoplane constraints orientation constraints and others of a similar nature Simultaneous constraints on multiple b o dy parts can b e imp osed by simply summing the individual ob jective functions for each constrained part into an aggregate ob jective function to b e minimized This p ermits inverse kinematic manipulation of a gure while maintaining a set of constraints on the b o dy which is a useful interactive to ol Phillips PB even describ es an ob jective function which attempts to balance the Jack gure providing a go o d example of how the metho d can b e extended to handle arbitrarily complex nongeometric goals While Jacks capabilities are impressive and do

provide interactive control over an articulated gures

constraints to the optimizer and a

number of ob jective

on highp erformance graphics workstations noticeably degrades the resp onse time of the screen with intermediate solutions from the

p erform at interactive sp eeds it works b est

then the imp osition of just a few constraints

Badler admits to p erio dically refreshing the

to retain interactivity even after stating CP that only the nal solution is useful and that the

A related solution

problem is But during

and even interface optimizer

CHAPTER INVERSE KINEMATICS

intermediate solutions should not b e considered motion

A simpler conjugategradient minimization technique is also used by Alt and Nicolas AN providing inverse kinematic manipulation and animation of limbs by animating p osition goals over time In constrast to Badlers approach they p erform unconstrained minimization electing to enforce joint limits by simply clamping solution values to the joint variable b ounding values

It is also worth noting that some early attempts by Badler to solve the inverse kinematic problem were based on simple heuristic algorithms KB BMW These metho ds do not app ear to have gained wide acceptance Badler has since abandoned these approaches in favour of the optimization metho d describ ed ab ove

Chapter

Ecient Algorithms for Direct Manipulation

One of our goals is to provide direct manipulation of an articulated gure and for this the metho ds of the previous chapter have some shortcomings The pseudoinverse is exp ensive to compute and is sub ject to numerical instabilities around singular congurations Badlers optimization metho d is considerably more p owerful but its p erformance leaves something to b e desired and it may b e more suitable for solving problems oline than for interactive manipulation The continuing app earance of inverse kinematic pap ers in the rob otics literature seems to suggest that neither of these metho ds is entirely satisfactory

In this chapter a pair of simple inverse kinematic algorithms are presented as alternatives to those adopted for computer graphics in the past Both are relatively simple to implement are numerically stable and are ecient enough to provide reasonable interactive p erformance on even lowp erformance machines Each metho d exhibits a dierent b ehaviour than the other and it is suggested that they might work well together as complementary manipulation to ols

A Simplied Dynamic Mo del

The rst metho d b elongs to a class of solutions to

on the transp ose of the Jacobian matrix Like the

relies on the linear relationship b etween endeector and joint velo cities Unlike this other approach however no inversion of the Jacobian matrix is required which signicantly reduces the cost of each iteration Consequently the metho d has b een advo cated for the online dynamic control of rob otic manipulators

the inverse kinematic problem that are based resolvedmotion rate control of section it

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

The metho d was intro duced in by Wolovich and Elliot WE who describ ed a dynamic control scheme based on the use of the Jacobian transp ose and showed that it could provide stable tracking of an arbitrary endeector tra jectory Sciavicco and Siciliano SS applied the method to redundant manipulators and showed that the redundant degrees of freedom could b e used to satisfy b oth obstacle avoidance constraints and constraints on joint ranges of motion Das et al DSS develop a more general technique for satisfying secondary criteria similar to the pseudoinversebased metho d discussed in section and compare the metho d to a minimization algorithm based on Newtons metho d Novakovic and Nemec NN show that the metho d can b e used to generate either joint velo cities or joint accelerations We are interested here in pro ducing joint velo cities to

drive the

joint parameters

The Jacobian Transp ose Metho d

Consider a comp osite force F applied to the tip of a real manipulator consisting in some direction and a twist torque m ab out some axis

T F fx fy fz mx my mz

of b oth

a pull f

This external force F applied to the endeector will result in internal torques and forces at the manipulator joints Under the simplifying assumption of the principle of virtual work Pau the relationship b etween F and the vector of internal generalized forces is

JTF

This suggests a rather simple iterative metho d for forcing an tra jectory xd t If the current endeector p osition is given by

et xd t xc t

can be thought of as a force f pulling the endeector toward

Equation can then be used to transform this external force to a generalized force on each of the joint variables If we are interested in the dynamic b ehaviour of the manipulator in reaction to the applied force then can b e considered the vector of joint variable accelerations q Since we are not particularly interested in accurate dynamic simulation of the manipulator it suces to think of as the vector of joint displacements velo cities so that

q J T F

Once q is computed a single integration step yields a new vector q which moves the endeector towards xd t This pro cedure rep eats until the endeector reaches the desired p osition or some other stopping criterion is met

endeector to track

a timevarying measure

xc t then the

error

the desired tra jectory point xd t

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

In eect at each iteration we treat the vector e as an elastic force pulling on the end of a dy namically simple manipulator and adopt a heuristic simulation mo del in which force is prop ortional

to velo city rather than acceleration Using f mv as

the eects of inertia things stop moving as so on as the applied external force disapp ears Gleicher GW has used the relationship combined with this simple equation of motion to provide direct manipulation over a variety of geometric ob jects The term dierential manipulation has been coined to describ e this and the discussion ab ove shows that we can add articulated structures to the set of ob jects amenable to direct manipulation of this typ e

Equation is in fact equivalent to the wellknown steepest descent metho d of minimization which is generally regarded as having p o or convergence prop erties PFTV This raises the question

of why one would adopt this

prop erties The intent here is to provide direct manipulation of articulated gures in an interac tive setting rather than to solve inverse kinematic problems oline and for this typ e of online application the Jacobian transp ose metho d has some app ealing characteristics

The rst of these is that no matrix inversion is required Using the transp ose of the Jacobian not only avoids problems with matrix singularities but also means that at each iteration only forward kinematic calculations are required Since these can be computed quickly a tra jectory which is being sp ecied interactively can b e sampled frequently providing resp onsive feedback to the user

More imp ortantly

solutions obtained in successive

tor will resp ond as though the user were in fact pulling on the endeector contrast other minimization techniques may generate successive solutions

redundant and there

One drawback is that since the metho d is based

kinematic singularities since the matrix will b e inherently illconditioned Near a singularity high joint velo cities can result in oscillations ab out the singular conguration This typically o ccurs only when trying to fully extend the manipulator The problem can b e overcome by either using a smaller integration stepsize using an integration metho d with an adaptive stepsize or by clamping joint velo cities to some maximum b ounds b efore integrating Since the basic solution step is so quick

from each other particularly when the manipulator is acceptable solutions When using a physicallybased constrained to b e close to each other the pulling

p o or convergence prop erties of the metho d

the governing equation of motion eliminates

approach over other minimization metho ds with sup erior convergence

since the solution is based on a physical mo del alb eit a simplied one the iterations are b oth predictable and intuitive That is the manipula with an elastic band In which are quite dierent are an innite numb er of mo del successive congurations are implicitly metaphor uniquely sp ecies a path from one solution to the next For interactive applications this advantage arguably outweighs the p otentially

on the Jacobian it is not entirely immune to

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

F q’ q

x− d

x c

Figure Interactive

to compute often it is interactive p erformance

control

simply

lo op mo del for Jacobian transp ose

use a smaller integration stepsize

metho d

while retaining

go o d

T J

Implementation Details

p ossible to

In comparison with the metho ds of the previous chapter implementation of the Jacobian transp ose metho d is relatively simple Each iteration involves computing a force applied to the endeector computing the Jacobian matrix for the current conguration and computing the resulting joint

velo cities

Figure depicts the basic control lo op

The joint velo cities are integrated once to obtain a new conguration for the manipulator

Forces

in Chapter For now we assume that the applied force is known and concentrate on the other asp ects of the metho d

Computing the Jacobian

At each iteration we need to compute the Jacobian matrix J whose columns convey how the end eector frame moves in the world frame as the individual joint variables change Given a vector of joint variables q the endeector frame is sp ecied by a p osition Pq and orientation Oq The

applied to the endeector are a result of interaction with the user and will b e discussed

∫

f(q)

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT

MANIPULATION

Jacobian column entry for the ith

joint is

Ox i

derivative world frame

op erator is with

or may b e computed in the

ui in the lo cal joint frame At each joint Mi is the matrix which to the world frame Supp ose that axisi represents the normalized

transforms the transformation of

axis in the

world co ordinate frame

Then for

a translating

axisi ui Mi

joint the corresp onding Jacobian

T axisi

J

entry

is

and for a rotating joint the Jacobian entry is

where

p denotes the

p osition of the endeector and ji is

the p osition

of

joint

i

in the

world

Lo cal vs World Frame

Ji

T p ji axisi

T axisi

Px

P y

J P z

Oy Oz

qi These

lo cal joint

for eciently computing the full Jacobian matrix

Each joint i in the manipulator either translates along or rotates ab out one of the principal axes

where the

resp ect to

entries frame

can

b efore b eing

in the

world

for a manipulator

frame Here we describ e b oth pro cedures

i

In practice it is exp ected that the

eral transformation hierarchy within an animation system This subtree may contain arbitrary transformation no des in addition to those corresp onding to the manipulator joints These additional transformation no des do not constitute degrees of freedom and are not sub ject to up dates by inverse kinematic manipulation But since they transform some of the lo cal joint frames of the manipulator

manipulator itself

will b e a subtree emb edded within a

gen

either

b e

computed transformed to the

lo cal joint frame

the

lo cal

joint

directly

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

they must b e considered The signicance of this is that the typ es of no de present in the hierarchy determine whether the Jacobian entries can b e computed in the global world frame or whether they must b e computed in the lo cal joint frames at a slightly higher cost

If the transformation hierarchy in which the manipulator is emb edded consists only of trans

lations and rotations then the Jacobian entries concatenation of only rotations and translations transformation Mi at a joint will b e orthogonal

can b e computed directly in the world frame A guarantees that the upp erleft p ortion of the This implies that the rst three rows of Mi are the

transformed principal axes of

Similarly the joint position ji can be extracted from the fourth row of Mi Since the transformation matrices M need to b e computed to display the structure caching them at each joint during display reduces the calculation of each Jacobian entry Ji to just a vector subtraction and a cross pro duct op eration

If scaling transformations are permitted in the hierarchy then there is no guarantee that Mi is orthogonal Arbitrary nonuniform scaling transformations within the manipulator may result in an upp erleft p ortion of Mi which do es not represent a pure rotation In this case axisi cannot b e extracted from Mi Instead the vector quantities in and must b e computed in the lo cal joint frame then transformed to the world frame by Mi To compute in the lo cal frame the endeector p osition p needs to b e transformed from the world frame to the joint frame and so

the inverse transformation Mi is required

For eciency Mi matrix identity

can b e computed incrementally

while

traversing the

hierarchy

Using the

the joints local frame and so axisi can be extracted directly from Mi

AB B A

and the fact that the inverse transformation for a single joint is simple to determine the matrix inversion step at a joint can b e replaced with a cheap er matrix multiplication Further simplications

result from noting that the world frame joint frame and that the joint axis is simply one trivial

p osition ji corresp onds to the of the principal axes making

origin of the lo cal joint the cross pro duct step

The Jacobian

the hierarchy At

calculations may b e p erformed either in the global frame or the lo cal joint frame

matrix for the endeector

each joint i either or is computed to obtain the column Ji and these

frame then can b e assembled

by a single traversal of

as they are likely to b e in any computer animation system

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

Scaling Considerations

In practice the simple mo del expressed in equation do es not work well for the general case One problem is that the resp onse of the manipulator to an applied force dep ends on the choice of scale for the joint variables If rotation joint values represent degrees for example a given applied force will result in a dierent resp onse than if the rotations were measured in radians The overall scale of the world must also b e considered since this will govern the magnitude of the vector quantities in These factors must b e taken into account if the technique is to provide uniform b ehaviour over a range of scales

To provide stable scaleinvariant b ehaviour we can mo dify equation to comp ensate for these factors

q KJT F

where K is simply a constant scaling matrix whose ith diagonal entry Ki acts as a weighting factor for the computed joint velocity qi The following term is suggested

Ki

where the wi term is prop ortional to the

wi i

length of link i and is intended to oset the eects of

world

b e thought of of the joint to an applied force This parameter might

the overall scale of the

as a parameter controlling the

b e made available to the user to allow editing of a joints p erceived stiness

The i term is a weighting factor for joint i which can

resp onsiveness

Although K is sp ecied here to b e a constant gain matrix it is p ossible to compute a timevarying gain matrix Kt so as to control the rate of convergence of a tracking algorithm based on WE NN However given that the additional computation required is considerable relative to the basic iteration cost of there is some incentive to just consider K constant

Integration

Once the joint velo cities q are known a single integration step is required to generate the new state of the manipulator q for the next iteration The simplest metho d is to take a single Euler integration step

q q h q

for some integration stepsize h This metho d is

velo city across the step interval As the interval

but overall p erformance suers Nevertheless the Euler metho d with a small h may b e adequate for manipulators with just a few joints

notoriously width h is

inaccurate

made smaller the

accuracy improves

since it assumes constant

The Euler metho d can b e replaced with a more robust metho d An adaptive stepsize

Kutta metho d can improve p erformance taking small steps when required but allowing the

h to increase when small steps are unnecessary Adaptive integration implementations are available

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

in the public domain PFTV and their use is

Joint Limits

Since the formulation do es not explicitly include are enforced by clamping qi to upp er and lower not recommended in most optimization texts in

force

recommended

constraints on the joint variable values joint limits b ounds after the integration step Although this is

practice it app ears to b e adequate

goal

Runge stepsize

Figure A case not handled well with the Jacobian transp ose metho d Pulling inwards on the tip of the manipulator on the left will not pro duce an exp ected conguration like the one shown on the right

A Complementary Heuristic Approach

The forcebased approach of the preceding metho d has some app ealing characteristics for interactive manipulation There are some cases however for which the metho d do es not p erform well Figure illustrates one such case On the left is a manipulator in a singular conguration with a new desired p osition for the tip shown as a black dot The conguration on the right shows a reasonable solution to this inverse kinematic problem and probably reects what a user exp ects to get by dragging the tip in towards the goal However as the user attempts to drag the tip inwards the applied force exerted on the tip p oints straight down the singular direction it is in eect cancelled

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

out and the tip will not move This b ehaviour is reasonable given the physical analogy of the Jacobian transp ose metho d but may not really match the users exp ectation

An alternative inverse kinematic algorithm is presented here suitable for interactive p ositioning and capable of providing reasonable b ehaviour in cases such as that in Figure It is based on a heuristic metho d which has b een prop osed to quickly nd an initial feasible solution for a standard minimizationbased algorithm WC However it can stand on its own as an inverse kinematic p ositioning to ol Like the Jacobian transp ose metho d the technique is ecient simple and immune to problems with singularities However its b ehaviour is quite dierent from that exhibited by the previous algorithm and it is suggested here as a complement to rather than a replacement for the Jacobian transp ose metho d

The CyclicCo ordinate Descent

The cycliccoordinate descent CCD metho d is an

tempts to minimize p osition and orientation errors by varying one joint variable at a time Each iteration involves a single traversal of the manipulator from the most distal link inward towards the manipulator base Each joint variable qi is mo died in turn to minimize an ob jective function The minimization problem at each joint is simple enough that an analytic solution can b e formulated so each iteration can b e p erformed quickly

As a solution is obtained at each joint the endeector p osition and orientation are up dated immediately to reect the change Thus the minimization problem to b e solved at any particular joint incorp orates the changes made to more distal joints during the current iteration This diers from the previously describ ed metho d which in eect determines the changes to each joint simultaneously

Supp ose that the current endeector p osition is

Pc xc yc zc

and that the current orientation of the endeector is sp ecied

by the three orthonormal rows of the

rotation matrix Oc

uc Oc uc

uc

Metho d

iterative heuristic search technique which at

ie although the changes are computed sequentially the state of the manipulator remains constant during the iteration

CHAPTER

EFFICIENT

ALGORITHMS FOR

P ic

DIRECT

MANIPULATION

u 2d

u 3d

φP d

P id

Example CCD iteration step for

u 1d

j i

Figure

rotation joint i

The endeector

by nding a joint vector

which is just the sum of

and an orientation error

placed as close as p ossible to some

q which minimizes the error measure

E q Ep q Eo q a p ositional error measure

orientation Od

can b e

desired

p osition

Pd

and

measure

Eo q

X

j

uj d uj c

Ep q kPd Pc k

The metho d pro ceeds by considering one joint at a time from the

qi is mo died to minimize equation b efore pro ceeding to

minimizing b ecomes a simple onedimensional optimization problem since only qi is allowed to change while the other elements of q are xed Since joint i is either a rotation or a translation joint there are two cases to b e considered

Rotation Joint

Figure illustrates the situation for rotation joint i during an iteration The vector Pic is the vector from the joint p osition ji to the current endeector p osition and Pid is the vector from ji to the desired endeector p osition We are free to rotate the vector Pic ab out the world space joint axis axisi by some amount This rotated vector is

Pic Raxis Pic

i

tip the

to

next joint i

the

base

Each

At each joint

joint variable

CHAPTER

EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

As varies

position Pd

by varying joint variable seek a value for which

closest to the desired so the best we can do Pic and Pid This implies that we

following ad hoc

values for these factors are suggested WC

wo

wp

Pic sweeps out a circle centered at ji The p oint on this circle

is the point at which the circle would intersect the line along Pid

Reasoning along similar maximizes the expression

lines an orientation error

Combining both

Here wp and wo

duced to play a role similar to that of the

ji alone is to align the two maximizes the expression

vectors

corrected

g Pid Pic

also

joint i intro

g

X

j

and gives an aggregate ob jective g wp g wo g

function

to be

maximized for

is b est

uj d uj c

by making

sure

that

are arbitrary p osition and orientation weighting factors

gain matrix K of the Jacobian transp ose

Here is a scaling factor inversely prop ortional to the overall world scale W kW

and is required to make the algorithms b ehaviour scaleinvariant The factor is an arbitrary weight which dep ends on the conguration of the manipulator Wang WC suggests without justication that

minkPid k kPick

maxkPid k kPick

which seems to be adequate in practice

With some algebraic manipulation the ob jective function to reduced to

be maximized at

joint

i

can be

resp ectively

and are metho d The

with the constant

g k cos kcos k sin co ecients k k and k given by

k wp Pid axisi Pic axisi wo

X j

uj d axisi uj c axisi

CHAPTER

EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

implies that

determines

a candidate

value

candidate values to consider c

k

k

X

wp Pid Pic wo uj d uj c

j X

j

axisi wp Pic Pid wo

uj c uj d

From elementary calculus we know that the ob jective function is maximized over

when its rst derivative is zero and its second derivative is negative The rst condition

k ksin k cos

Translation Joint

If joint i is a translation joint then it can only reduce the p osition error

It error is to

is not dicult to change the joint

show WC that the b est that can b e done to minimize displacement by

the p osition

tan

k

k k

c in the range

the

interval

which

there are p otentially two other

values those which lie in the interval x and which pass the second derivative test are maximizing values for the ob jective function If there is more than one of these the ob jective

c

However

is candidate

since tan and c Of these

p erio dic

function is evaluated with each to determine

uniquely determined in this way it is added

introduce an arbitrary weighting factor wi wi which controls the perceived stiness of the joint so that the up date b ecomes

qi qi wi

The endeector frame is then rotated to reect this change and the iteration continues on to the next joint i using the up dated endeector

which yields the true maximum Once has b een to the current joint value qi At this p oint we can

Pid Pic axisi

This is weighted by wi as before and added to the current value of joint variable qi The endeector

p osition is up dated b efore continuing

Overview

on to the next joint

A single iteration of the CCD metho d for an njointed manipulator visits joints n through in turn At each joint the original ndimensional optimization problem is reduced to a onedimensional

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

problem involving just the joint variable qi which admits to an analytic solution An incremental change to qi is computed with either if the joint rotates or with if the joint translates The variable qi is then incremented and clamp ed to upp er and lower b ounds The current endeector frame Pc and Oc is up dated to reect the change b efore pro ceeding to the next joint

The algorithm behaves well around singular congurations and since the value of the ob jective function is reduced with each step the metho d is guaranteed to converge But the heuristic nature of the metho d makes the rate of convergence somewhat dicult to quantify since it is de

p endent on the structure of the manipulator itself In

only a few iterations although there are situations for

In terms of b ehaviour the heuristic implies that distal

the base if the endeector goal can b e reached by moving only the nal link of the chain then only that link will move

Comparison

the metho ds describ ed ab ove is suitable for interactive direct manipulation with

Each of

caveats

dragging

singularities although the CCD metho d has an edge in this regard since it is completely immune to diculties near singularities Where neither metho d particularly excels is in the rate at which they converge toward a solution b oth can exhibit p o or convergence rates particularly if high accuracy is required

The p eriteration cost for each is minimal so reasonably complex manipulators Each can

some that b oth can provide go o d feedback when b e made numerically stable near kinematic

Figures and compare the p erformance of each algorithm for solving a pair of inverse kinematic problems The manipulator has degrees of freedom ab out the same complexity as a simple approximation to a limb although for this example there are no limits on the range of movement for each joint In each case a p osition goal is sp ecied for the endeector and the inverse kinematic problem is solved to varying degrees of accuracy Each gure shows the initial conguration and the nal solution obtained with each metho d In addition the time to achieve the solution is plotted with resp ect to the degree of accuracy requested In the rst case of Figure the endeector goal is well within reach and b oth metho ds are able to solve the problem reasonably quickly However it is already apparant that the Jacobian tranp ose converges slowly when it is close to a solution there is a marked decrease in p erformance for each additional digit of accuracy requested

In the second case of Figure the goal is close to the edge of the reach space of the limb

practice most problems can b e solved with which the metho d can converge very slowly links move more readily than links closer to

CHAPTER EFFICIENT ALGORITHMS FOR DIRECT MANIPULATION

which must

to solve the goal the CCD

approach a singular conguration to achieve the goal Although b oth metho ds are able metho d clearly outp erforms the other particularly as the accuracy of

the solution

small applied force which is

progress towards the goal is very slow example

increases As it

approaches the goal the Jacobian transp ose metho d is hamp ered by a

pulling

in a direction which do esnt aect most of the joints so the The heuristic approach of the CCD fares much b etter in this

The nal congurations

moving distal links in contrast with the other metho ds tendency to distribute joint changes more equally along the chain This dierence in b ehaviour is quite noticeable during interactive dragging Manipulating a chain with the Jacobian transp ose metho d tends to feel like playing a exible elastic ro d while the CCD metho d imparts a feel more akin to pulling on a chain of lo osely connected links While the nal solutions for the CCD metho d might lo ok inferior to those obtained with the Jacobian tranp ose keep in mind that these solutions were obtained noninteractively ie they were computed oline When dragging interactively using the CCD metho d it is usually not dicult to

shown in the gures also illustrate the CCD metho ds preference for

gain control over the nal p osition by moving the cursor

a means of controlling joint resp onsiveness by sp ecifying an appropriate weighting factor wi at each joint In particular this parameter can b e useful to oset the default b ehaviour of the CCD metho d

These examples illustrate the main advantages and disadvantages of each metho d Both are quick and therefore worth considering if direct manipulation is required even on machines with mo dest p erformance The Jacobian metho d has the advantage of resp onding in an intuitive fashion to pushes and pulls on the endeector the CCD metho d is not as intuitive in this regard The CCD metho d exhibits more stability around singular congurations and although its rate of convergence slows it is not nearly to the extent that the Jacobians do es Moreover it can b e argued that direct manipulation do es not necessarily require a high degree of accuracy Certainly while a user is sweeping a cursor across the screen it is not critical that the endeector track it to six decimal places of precision one or two decimal places of accuracy probably suces When accurate p ositioning is required particularly near singularities the CCD metho d would b e the appropriate metho d to use In general the two metho ds complement each other nicely providing alternate interaction mo dels to oer the user

appropriately Also b oth metho ds supp ort

CHAPTER EFFICIENT

ALGORITHMS FOR DIRECT MANIPULATION

(a) Initial

200

Time (milliseconds)

100

(b) Jacobian transpose

(c) CCD

X

O

X

O

O

X

X

X

XO O

O

X − Jacobian O − CCD

1e−1

1e−2 1e−3 1e−4 Convergence Criteria

Figure

1e−5 1e−6

CHAPTER EFFICIENT

ALGORITHMS FOR DIRECT MANIPULATION

(a) Initial

2750

2000

Time (milliseconds)

1000

X − Jacobian O − CCD

(b) Jacobian transpose

(c) CCD

X

X

XO O

X

X XO

O

O

1e−1 1e−2

Convergence Criteria

Figure

O

1e−5

1e−3 1e−4

1e−6

Chapter

Incorp orating Constraints

Inverse kinematic manipulation is a useful shortcut but do es not in itself provide any more function ality than simple forward kinematics Creating a p ose for a skeleton can b e less tedious but there are still problems in trying to edit the p ose without moving previously p ositioned b o dy parts It would b e useful for example to b e able to sp ecify that parts of the b o dy should not move no matter how we manipulate the skeleton Badlers recent work CP has shown the usefulness of b eing able

to imp ose

with Jack

sp ecied

PB this capability has not b een exploited The basic set of constraints available within Jack are almost all simple geometric constraints on p ositions and orientations of b o dy parts It would seem that even this limited set of constraints is enough to greatly improve interaction with a gure

In this chapter we consider how each of the manipulation techniques describ ed in the previous chapter can b e used to satisfy multiple simple geometric constraints on the p ositions and orientations of endeectors within a skeleton and discuss some of the p erformance and implementation issues that arise

Constraint Satisfaction

A manipulator or a skeleton can b e considered a system describ ed by a set of state variables for our purp oses joint rotations Solving the inverse kinematic problem is essentially one of solving a nonlinear system of equations for these state variables and there are a numb er of approaches one can take to incorp orate constraints in the solution pro cess We have already seen that constrained optimization is one p ossibility but there are other p ossibilities for the manipulation metho ds of the previous chapter

constraints on a gure during editing The constrained optimization metho d employed

p ermits any constraint which can b e expressed as a function of the skeleton state to b e However with the exception of the exp erimental balance constraint describ ed by Phillips

CHAPTER INCORPORATING CONSTRAINTS

The simplest approach is to use some variant of the penalty method This metho d can b e used with any iterative technique and the essential idea is that when a constraint is violated a restoring force is intro duced to push the system back into a legal state in which all constraints are satised A feedback control lo op monitors the state of the system and applies the appropriate p enalty forces as it detects constraint violations An advantage of this approach is that if the constraints are not initially met the restoring forces pull the system towards a legal state A disadvantage is that the constraints cannot b e enforced exactly since the restoring force only comes into play after a constraint has already b een violated Thus two p oints constrained to b e coincident will app ear to pull apart slightly b efore the constraining force can pull them back together For metho ds based on physical simulation the restoring forces are usually springbased If the springs are made suciently sti then the constraint violations may b e small enough to b e unnoticeable But this causes problems when trying to simulate the system requiring tiny integration steps to retain numerical stability PFTV

Both the Jacobian transp ose metho d and the CCD metho d could b e used within a control lo op to provide this sort of constraint satisfaction In fact due to the heuristic nature of the CCD metho d and its reliance on strictly geometric information this is the only option op en Before describing a p enaltymetho d approach based on the CCD metho d we consider rst a more comprehensive solution which is a generalization of the Jacobian transp ose metho d

Maintaining Constraints

The approach taken is to consider the problem of maintaining a set of constraints which are already satised rather than trying to satisfy constraints that have b een violated By assuming that the system is already in a legal state the problem is reduced to one of ensuring that changes to the system never violate the constraints The technique is based on wellknown metho ds for implementing constrained dynamics within physical simulations Sur AW using the same sort of simplied rstorder equations of motion describ ed in Section and by Gleicher GW The essential idea is that geometric constraints on an ob ject are treated as mechanical connections which introduce constraining forces into the system b eing simulated When an external force is applied to the system some comp onents of the applied force may b e counteracted by these constraining forces so that the net force acting on the system do es not violate the constraints The nub of the problem is to determine what these constraining forces are given a set of geometric constraints which must b e satised

Figure illustrates the concept for the simplest p ossible system a p oint The systems state q is simply the p oints lo cation in space A single constraint is imp osed on the system stating that the

CHAPTER INCORPORATING CONSTRAINTS

force force only

those

not change so the derivatives of C must always b e zero In particular this

imp oses the

condition

F a

F t

F c

Figure A force applied to a p oint constrained to lie within a plane A constraining force normal to the plane is added to the applied force to obtain a legal force tangential to the plane

lie within a plane This constraint condition can b e written as a function of the system Now supp ose a force Fa is applied to the p oint If the p oint is to remain in the the constraint must intro duce a counteracting force Fc which removes from the applied comp onents which would move the p oint away from the plane Summing the applied with this constraint force yields a net force acting on the p oint which ensures that the p oint moves in a legal direction Although simple this example illustrates two imp ortant p oints which apply to more complicated systems the net force lies in a plane tangent to the constraint surface cq while the constraining force points in a direction normal to this tangent plane We now describ e a pro cedure for computing the appropriate constraint forces for arbitrarily complex

systems

The Constraint Condition

Supp ose we write the constraints on a system as a vector function of the system state

C fq

If the constraints are initially satised then C In order to maintain the constraints C must

p oint must state cq plane then

C

C q

q

In Chapter equation dened the simplied equations of motion for a system which had the form

q Kg in fact for this trivial example the tangent plane is the constraint surface

CHAPTER INCORPORATING CONSTRAINTS

for some generalized force g acting on the system state Substituting this equation into and

denoting the constraint Jacobian matrix by Jc c the constraint condition becomes q

C J c K g

Any generalized force g acting on the system which satises this condition will not violate the constraints

Computing the Constraint

Jacobian Matrix

how the individual constraints change as the state

of m is an

In practice constraints are not sp ecied on q directly but rather on more meaningful geometric entities such as p oints or orientations which are themselves functions of the state q For example supp ose we wish to imp ose a constraint that the tip of a limb on an articulated skeleton denoted Pq should remain xed at some lo cation R An appropriate constraint condition for this example would b e

The constraint Jacobian matrix Jc describ es

variables vary The section ab ove intro duced the constraint vector Cq which is made up scalar constraint functions c q cm q If there are n state variables q qn then Jc m n matrix Typically there are more state variables than there are constraints

In this case the constraint

vector C

R Pq

consists of scalar constraints one on

each of the x y

Jacobian

contributes a blo ck of r rows to the matrix where r is the dimension of the geometric quantity eg r for a p oint constraint Since geometric constraints are expressed in terms of functions of q the chain rule is applied to calculate the Jacobian entries In the case

comp onents of

P

Each scalar each geometric

constraint constraint

ci contributes a single row ci to the constraint qj

matrix Thus

ab ove for example

Cq

xyz

c P q c P q c P q

Rx Px Ry Py Rz Pz

and z

ci qj

ci Pk Pk qj

Typically a single constraint will dep end left fo ot of the sample skeleton of Figure

on only a few of the is constrained to some

system state lo cation for

variables If the example the arm

CHAPTER INCORPORATING CONSTRAINTS

joint variables have no eect on this

constraint Thus the ith row of Jc

constraint ci usually contains Jc b e exploited and preserved naive implementation

Computing the

corresponding to the that this sparsity in matrix techniques oer substantial p erformance gains over a

Jc while the net force g must lie in its null space This is a presented in Figure

If the constraint force is in the range of Jc then gc Jc can b e written as

T

generalization of the specic example

just a few nonzero elements sparse

It is important

Constraint Force

In Chapter it was shown that an external force applied to a p oint on an articulated skeleton could b e converted to a generalized force g on the skeleton state by the Jacobian transp ose metho d However the g of equation is the net generalized force on the system As such it may include the sum of multiple forces applied to various p oints on a skeleton More to the p oint it must also include some unknown constraining forces which prevent the applied forces from violating the constraints imp osed on the system In general the net force is considered to b e a sum of known applied forces and of unknown constraint forces g ga gc Substituting this into the constraint condition yields the linear system of equations

Jc Kgc Jc Kga in which only the constraining generalized force vector gc is unknown

Equation simply states that an appropriate constraining force is one which when added to the applied forces causes the constraint derivatives to b e zero But this is to o ambiguous since the system is usually underconstrained and there may b e many constraining forces gc which satisfy equation One approach to removing this ambiguity is to insist that the constraint force must lie in a direction in which the system may not move just as the constraining force of Figure do es Recalling the discussion in Chapter ab out the Singular Value Decomp osition SVD this implies that the constraint force must lie within the range of the constraint Jacobian matrix Jc Thus for constrained systems in general the constraint force gc is restricted to lie in the range of

Jc KJc

Jc Kga

and solved for the vector of Lagrange multipliers Once the Lagrange multipliers are known the constraint force which removes the illegal comp onents of the applied force is computed as

gc Jc

this restriction follows from the principle of virtual work Pau

for some vector

Therefore equation

CHAPTER INCORPORATING CONSTRAINTS

Note that computing gc requires the solution to a linear system of equations even though the constraints themselves may b e nonlinear

Solving for Lagrange Multipliers

The linear system must b e solved to nd the Lagrange multiplier vector

m

Note that the numb er of equations in the system is equal to the dimension of the constraint vector C Any metho d for solving sets of linear equations can b e applied here

A metho d recommended here to solve the system emphasizes robustness over sp eed Due

to the

structure of most articulated skeletons it is imp ossible to avoid illconditioning in all of the

time Mac To cop e with this the system is solved using the truncated SVD of the lefthand

T

m m matrix Jc KJc

is formed from the original SVD by zeroing any small singular values which eectively throws

This term eectively the magnitude of the

adds a p enalty spring to the system the constraint deviation C

strength

of which is

Overview

combined with a backsubstition algorithm PFTV The truncated SVD

away any illconditioned comp onents of the matrix PFTV MK This

not take advantage of any sparsity in the matrix but has the advantage of b eing robust in cases where illconditioning o ccurs

Feedback

The discussion so far has b een based on the assumption that the constraints are initially satised and that they remain so To handle cases in which the initial state violates some constraints or where numerical inaccuracies cause constraint violations an additional feedback term is added to the basic equation of motion

q Kga gc kCJc

T

prop ortional to

Equation is the complete simplied equation of motion for a constrained system Constraints are maintained by evaluating the right hand side of the equation using the metho ds outlined in the sections ab ove to nd the state variable velo cities q A single integration step then yields a new state q which resp ects any constraints imp osed on the system In an interactive setting the pro cedure iterates as the user applies changes to the system state through the user interface Screen up dates o ccur after each iteration to provide feedback Figure provides an overview of the pro cedure

solution metho d do es

CHAPTER INCORPORATING CONSTRAINTS

for a single iteration Note that equation is a generalization of the Jacobian transp ose metho d of chapter in the absence of any constraints on the system the equation reduces to the simple formula intro duced earlier

Implementation Issues

The basic constrained equation of motion has a regular structure which lends itself to an ob ject oriented implementation A solver for the equation only needs to know a few things the length and value of a global state vector q how to evaluate a numb er of functions of q and how to evaluate a matrix of partial derivatives with resp ect to q for each of these functions

Using software ob jects which resp ond to sp ecic requests to provide these pieces of information a generic constraint solver can b e written which is insulated from the sp ecic details of articulated skeletons The solver queries these ob jects to obtain the information it needs to assemble a global system of constrained equations of motion solves the system and then communicates the results back to some of the ob jects Implementing this metho d of maintaining constraints requires three dierent typ es of these ob jects skeletons hand les and constraints

Skeletons as Ob jects

Each skeleton is considered a single ob ject which contributes variables to the solvers global vector q Each skeleton must b e able to resp ond to requests for sp ecic pieces of information that the solver requires In addition a metho d must b e provided by which the solver can communicate a solution back to the skeleton If each skeleton provides these capabilities the solver do es not need

to know anything ab out the internal structure of the skeleton itself The

state

solver must b e able to

query a

query a

query a

send a skeleton a new state vector

skeleton skeleton skeleton

for the length of its state vector for its state variable vector

for its scaling matrix K

reecting the solution

A hand le is an abstraction representing a geometric quantity associated with a skeleton whose value

Handles on Skeletons

dep ends on the skeletons internal state

of a joint within the skeleton or as complex as the lo cation of the skeletons center of mass Handles are the geometric entities up on which constraints may later b e imp osed and to which forces may b e applied

A handle can refer to something as simple as the p osition

CHAPTER

INCORPORATING

Manipulate skeleton

g a

CONSTRAINTS

Specify constraints

Compute constraint

Jacobian

J c

Solve for

Lagrange multipliers λ

Compute constraint force

g c

+

q ́

∫

q

Compute feedback term

Figure

Iteration

steps for maintaining constraints

CHAPTER INCORPORATING CONSTRAINTS

Each handle attached to a skeleton knows how to compute a function of the skeletons state hq sk eleton A numb er of handle typ es can b e dened each computing a dierent quantity These might include

A point hand le which computes the global position of some point dened within a local joint co ordinate system eg a p oint on the left shin inches b elow the knee

An orientation handle which computes the global orientation of a local joint coordinate system

A centerofmass hand le which computes the global position of a skeletons center of mass computed as a weighted average of each b o dy parts center of mass

Usually a single handle will dep end on only a subset of the joints within a skeleton When queried for its state vector a skeleton should return only those elements of q skeleton which are referenced by a handle This will keep the total numb er of variables in the constrained system to a minimum

In addition to the function hq sk eleton each handle must also know how to compute the Jacobian

matrix Jh

Constraints on Handles

Constraints can b e applied to the quantities computed by a handle The simplest constraints are those that constrain a handle to a geometric constant Useful examples of this include

matrix J qskeleton h

h qskeleton

The constraint solver will query each handle for this information when assembling the global constraint Jacobian matrix Jc Implementing a new handle typ e is straightforward requiring only handlesp ecic routines to b e co ded These routines are resp onsible for initializing the handle computing the handle function h and computing the handles Jacobian

constraining a

constraining a

constraining a

constraining an orientation handle to a given orientation

can b e also b e clasp ed b etween

environment For o or or the hand constraints could created b etween two handles For example a gures hands could b e constrained to stay together by creating a p oint handle on each hand then sp ecifying an equality constraint

p oint handle p oint handle p oint handle

to a given lo cation to a plane

to a line

These simple constraints would b e useful for sp ecifying interactions with a static example the feet of a gure can b e constrained to lie in the plane dened by the

constrained to the rung of a ladder To sp ecify more complex b ehaviours

these two handles

CHAPTER INCORPORATING CONSTRAINTS

Each constraint computes a function ch hn where the input values are the outputs of one or more handles These constraint functions are usually quite simple often reducing to just a variation of the distance formula In addition each constraint must b e able to compute its Jacobian matrix with resp ect to its inputs c Adding a new constraint is just a matter of writing co de to

h

evaluate these two items Geometric constraints are for the most part simple enough that this is a

minor amount of work

The Global Picture

An application sets up constraint problems by creating handles on skeletons imp osing constraints on these handles and applying forces to them b efore invoking a solver to evaluate equation But adding the constraint enforcement scheme of Section to an interactive program is not quite straightforward A user should b e able to interactively imp ose temp orary constraints on a gure while editing its p osture Over the course of a normal work session numerous constraints may b e created and deleted as the work pro ceeds So the system b eing simulated by equation is

constantly changing each time a constraint is added new handles may b e referenced and new variables intro duced It is not p ossible to determine b eforehand the correct set of equations to b e simulated and to simply hardwire the co de to do so Instead some sort of mechanism must exist for assembling and evaluating the system of equations on the y based on the current set of active

constraints The constraint solver

ow network which represents the

are completely determined by the networks conguration The dataow network scheme has b een describ ed by Witkin AW and explored more fully by Kass Kas

itself can b e made resp onsible for this It will maintain a data system b eing simulated the equations of motion for the system

The solver is resp onsible for assembling and solving the global constrained system of equations taking an integration step and communicating new state information back to each skeleton ob ject It also handles any b o okkeeping required to map lo cal skeleton variable indices to global indices As an application adds constraints to the system the dataow network within the solver is up dated The network consists of a set of function blocks with outputs of some blo cks feeding into the inputs

of others

Jacobian

the result of multiplying the lo cal Jacobian matrix by an incoming Jacobian matrix thus applying

Each blo ck computes two items a function of the blo cks inputs f x and the lo cal

matrix of that function with respect to its inputs f The block outputs f x as well as x

state

the chain

rule Figure depicts a typical function blo ck

constraint and each handle within the system contribute a single function blo ck to the At the top level the inputs of a constraint blo ck are wired to the outputs of one or more handle blo cks or in the case of simple constraints directly to constant values At the b ottom level the inputs to each handle blo ck are connected directly to elements in the global state vector q As

Each network

CHAPTER INCORPORATING CONSTRAINTS

f(x)

∂f ∂q

∂x ∂q

f

x

Figure A generic function blo ck

constraints are created and destroyed no des are added to and deleted from the network which is rewired to reect the change

When the solver is invoked it consults the top level of the network to determine the global constraint vector C as well as the constraint Jacobian matrix Jc The constraint vector C is formed by simply instructing each top level no de to evaluate its function and concatenating the results Each no de recursively instructs its inputs to evaluate themselves b efore computing its own function The recursion b ottoms out at the lowest level when it reaches the state variable values q Each no de caches its last computed value in case it is needed again

A similar recursive scheme is used to compute the global constraint Jacobian matrix Jc Each top level constraint no de computes its own lo cal Jacobian matrix with resp ect to its inputs then applies the chain rule by multiplying this against the Jacobian matrix of each of its inputs with resp ect to the state variables see Figure The solvers recursion scheme takes care of the mapping b etween lo cal and global indices as well as the allo cation of temp orary memory for intermediate matrices Matrix sparsity is preserved and exploited to reduce computation and caching is again used to avoid duplicate computations

The dataow network provides the exibility required to supp ort the interactive restructuring of a simulated system One attractive feature of this organization is that implementing new classes of handles and constraints is particularly simple All that is required is to implement the two routines required by a function blo ck since this is all the solver needs as it traverses the network

CHAPTER INCORPORATING CONSTRAINTS

An Example

Consider the problem of constraining the tips of a gures hands to its hips This can be accomplished

by rst creating

four p oint handles on the gure

handle

handle

handle

handle

h on the h on the h on the h on the

tip of the right hand right hip

tip of the left hand left hip

To x the hands to the hips two equality constraints on these handles are created

c h h

c h h

Figure shows the resulting dataow network constructed by the constraint solver Each handle references a few variables within the skeletons state vector these variables are concatenated to

form the

and feed the results to the constraint function blo cks These compute the distances b etween the

global state vector q The handle function blo cks compute their resp ective p oint lo cations

p oints and the blo ck function outputs are concatenated to form the element global

incoming

constraint vector C Each blo ck also computes its own lo cal Jacobian matrix with resp ect to its inputs multiplies it with an incoming matrix and passes the result along The matrix outputs of

the constraint blo cks contribute sparse rectangular blo cks to the global constraint

Jacobian Jc

Any time an element of q changes value a disable cache signal is triggered on any handle blo ck connected to the element This signal p ercolates up through the network forcing any blo ck that is encountered to discard its cached data The next time the solver evaluates the network only these blo cks will recompute their outputs When the network has b een reevaluated the solver has all the information it needs to evaluate equation

Summary

pro cedure has some attractive characteristics

maintained exactly since any forces acting on

are removed The pro cedure is quite general as well constraints and

for this example two sets of x y and z scalar constraints

This constraint enforcement

straints can theoretically b e

cause a constraint violation

handles can be arbitrarily complex functions and are therefore not restricted to referring to geomet ric quantities alone The dataow network architecture is extensible since adding new handle and constraint typ es is simply a matter of writing a handful of functions

Most imp ortantly con the system which would

CHAPTER INCORPORATING CONSTRAINTS

C

Jc

c1

c2

h1

h2

h3

h4

q

Figure Example network

CHAPTER INCORPORATING CONSTRAINTS

The main drawback to the approach is that the solution cost is dominated by the On cost of solving a linear system for the Lagrange multipliers of which there is one for each of n scalar constraints in the system b eing simulated For even a few simple geometric constraints the solution time at this b ottleneck quickly degrades to the p oint where interaction b ecomes dicult But Surles Sur has shown that when constraints are applied to articulated structures with sp ecic charac teristics the resulting system of equations can b e solved in linear time under certain conditions This result is promising but is recent enough that it has not b een pursued for this thesis

A sample implementation of the metho d outlined ab ove b oth conrms its p otential as well as the limitations imp osed by the b ottleneck Retaining interactive up date rates for any reasonably complex skeleton with just a few p osition and orientation constraints applied is dicult given current CPU p erformance Simple Euler integration not surprisingly intro duces numerical instabilities due to cumulative errors when the integration stepsize is large enough to provide reasonable interactive

either since it to feel implies that some steps will b e thrown away entirely retain accuracy As a result one iteration may take much longer to complete than another so screen up dates o ccur at irregular intervals and consequently the interface is p erceived as b eing jerky and unresp onsive However these are problems which will disapp ear as CPU p erformance improves to the p oint where accuracy in the solution can b e

maintained at interactive up date rates

Another source of p otential stability problems is the feedback term of equation This term

feedback Adopting more robust adaptive integration metho ds is not

These metho ds typically require multiple evaluations of equation p er iteration and

is so exp ensive to compute the refresh rate unresp onsive In addition adaptive stepsizing when the stepsize must b e reduced in order to

drops dramatically and the interface tends

suers from the usual

constant k leads to a

noticeable constraint

currently done purely

ie k is small with the assumption that as CPU p erformance improves it will b e p ossible to p erform enough iterations b etween screen up dates to eliminate any noticeable constraint violations Trying to eliminate the inevitable drifting of a system away from its constraints a result of numerical inaccuracies by using a high spring constant is almost sure to intro duce severe stability problems

problems asso ciated with springbased constraint enforcement a high spring sti set of equations which are unstable while a low value for k p ermits violations Cho osing a go o d spring constant value can b e dicult and is on a trialanderror basis Ideally the feedback spring should b e a lo ose one

Given current CPU sp eeds this technique seems b etter suited to solving constraint problems oline than in an interactive setting Our goal is to develop immediately useful interactive to ols for working with nontrivial skeletons and this metho d cannot b e considered practical yet for this

necessarily helpful

CHAPTER INCORPORATING CONSTRAINTS

purp ose on mo destly p owered workstations Instead we will consider a p enaltyforce metho d based

on the CCD algorithm as a substitute with which we can exp eriment

A CCDbased Penalty Metho d

in an interactive editor

The previous metho d is capable of handling multiple constraints imp osed on dierent parts of a skeleton To accomplish the same with the CCD metho d requires some slight mo dications to the basic algorithm presented in Chapter Whereas the basic algorithm considered just a serial chain of links and a single goal solving for multiple constraints means we must also consider branches in the manipulator and more than one goal as shown in Figure

The scheme of Chapter solved the problem for a serial chain by traversing from the endeector in towards the base at each joint adjusting the joint parameter to minimize an error measure derived from the current endeector p osition and a known goal In a branching chain with multiple end eectors and multiple goals a joint may contribute to the p osition of more than one endeector so p otentially more than one goal must b e considered when varying the joint variable Also the

algorithm dep ends on the inward proximal one can b e considered

traversal scheme distal This precludes treating

solved sequentially

A recursive traversal of the

problems at a joint are solved

children to solve for any constraints that may b e applied to endeectors in their subtree Then the joint variable which minimizes the summed error measure from each child subtree can b e computed The only change from the previous CCD algorithm is that the traversal must now consider branches

A

B

Figure A branching chain with two endeector constraints

singlegoal problems which can

b e

joints must b e solved rst b efore a more the multiplegoal problem as a series of

hierarchy from the leaves in towards the ro ot ensures that all sub b efore the joint itself is considered Each joint instructs all of its

CHAPTER INCORPORATING CONSTRAINTS

in a chain and that the error measure equation of Chapter Xn

b ecomes

a summation

E q

Ep i q Eo i q

i

over the n constraints which are distal to the current joint The net eect of this change is that the coecients k k and k must be computed by summing equations over each distal

computed The constraints have b een satised or until successive iterations pro duce negligible changes indicating that the constraints are conicting and cannot b e

simultaneously satised

This recursive scheme resembles Badlers early heuristic approach BMW for p ositioning a gure with multiple constraints although the CCD metho d for computing a minimizing change in a joint variable app ears to dier from the one used there

This p enalty metho d approach is arguably inferior to the more comprehensive scheme outlined previously Constraints are only approximately enforced so we can exp ect to see some drift on segments that are constrained to stay in place Also we are restricted to geometric constraints due to the CCD metho ds reliance on geometric relationships alone Nevertheless the metho d is

endeector goal b efore a minimizing change in the current joint variable can b e

pro cedure must iterate until either all endeector

usually stable

exp erimenting

instabilities do o ccur when p osition and orientation constraints conict with each other but this can b e alleviated with appropriate weighting factors on the individual constraints

enough to p erform adequately at interactive up date rates and gives us a means of with constraints within our interactive editor In our prototyp e implementation

Chapter

An Interactive Editor

To place the discussion of the preceding chapters in context an interactive program for animating articulated gures is intro duced here The program is designed to create keyframed motion sequences

for arbitrary skeletons

in this thesis Both the Jacobian transp ose and the CCD metho ds have b een implemented and

and has b een b oth a motivation and a testb ed

for the ideas develop ed

the application interface mo died to accomo date direct inverse kinematic

constrained manipulation This chapter briey describ es the program and the manipulation interface

A System Overview

The Sequence Editor is an interactive to ol for creating and editing keyframed movement sequences for a single arbitrary skeletal gure Its primary function has b een to act as the movement creation window of a motion planning package CWGL for choreographers whose needs are quite dierent from those of computer animators To a typical user planning the movement of multiple gures in a work space a rough approximation of a movement that can b e created quickly can b e more valuable

than a more realistic

has favoured ease of use over functionality The hop e is that direct manipulation and constraint satisfaction based on the metho ds of the previous chapters can improve the quality of movement created with the editor while retaining a simple and intuitive user interface

Before describing the interface itself some of the terminology warrants a brief explanation

Skeletons

The program itself knows nothing ab out skeletons sp ecically a skeleton app ears as an abstract data typ e supp orted by a to olkit library of routines The to olkit supp orts the creation manipulation and

animation that would take hours to p erfect Consequently the programs design

manipulation as well as

CHAPTER AN INTERACTIVE EDITOR

animation of skeletons dened by a simple ASCI I le format Figure shows a sample description

for a simple approximation to a human gure Any editor and animated

valid skeleton description can b e read in to the

As the example shows each skeleton is simply a collection of named joints arranged in a hierarchy The joints are either rotary or prismatic each with a single degree of freedom Comp ound joints with

multiple degrees of freedom eg ballandso cket

joints sharing

the joint typ e

of movement

These rigid ob jects comprise the appearance of the skeleton and are drawn as they are encountered during a display traversal of the hierarchy

A skeleton maintains an internal state vector q consisting of all the joint variable values as well as a translation vector for the skeleton as a whole This information is enough to completely dene the lo cation and shap e of the skeleton for a single frame An application can animate a skeleton by

the same lo cation Asso ciated with

each joint are a numb er of attributes

axes of freedom and lo cal limits on the range

rotary or prismatic the lo cal axis of the joint Polygonal ob jects may

be attached to any joint node in the

hierarchy

rep eatedly loading the skeleton state q and instructing

The to olkit now supp orts inverse kinematic control

to identify b oth a base and an endeector within the joint hierarchy A desired p osition andor

orientation for the endeector may then b e sp ecied and the skeleton

inverse kinematic problem using either of the metho ds of the previous chapter The internal state q

is automatically up dated to reect

the details of the inverse kinematic algorithms

can b e mo delled as a series of these single DOF

the skeleton to display itself

over a skeleton by allowing the application

the solution to the problem This isolates the application from

The Sequence

A sequence is an abstract data typ e

of a skeleton over some p erio d of

skeleton state at any frame of the animation Although a sequence could

motion mo del for this discussion a sequence will b e dened as a series of keyframed p oses each of which sp ecies the state vector q at a particular frame When a sequence is queried for the skeleton state at a frame b etween key frames an interp olated state is computed onthey and returned For each rotating joint either linear or splined quaternion interp olation Sho may b e p erformed For each translating joint either linear interp olation or generalized CatmullRom spline interp olation KB may b e used Currently no further control over the interp olation pro cess is provided other

for storing skeleton animation data it represents the movements time An application may query a sequence to determine the encapsulate a pro cedural

instructed to solve the

including

courtesy of Phil Peterson

a quaternion is a compact representation for rotations with some app ealing prop erties

CHAPTER AN INTERACTIVE EDITOR

# Example .scr file for a stick figure.

define skeleton “stickman” joint “pelvis”

group “Upper body” joint “torso”

group “Right Arm” joint “right arm” joint “right hand”

end group

group “Left arm”

joint “left arm”

joint “left hand” end group

joint “head” # “head” is a child of “torso” end group

group “Right leg” joint “right leg” joint “right foot”

end group

group “Left leg”

joint “left leg”

joint “left foot” end group

end skeleton

right arm

right hand

right leg

right foot

head

torso

pelvis

left arm

left hand

left leg

left foot

define joint “right leg” object “r_lleg.pol” offset 0 −0.32 0 hinge x 0 170

mass 1 orientation 0 0 0 mirror “left leg”

end joint

Figure Sample skeleton description

CHAPTER AN INTERACTIVE EDITOR

than that aorded by changing the keyframe spacing or the key p oses

A numb er of simple editing op erations are dened for keyframe sequences Ranges of keyframe p oses may b e copied inserted andor deleted Keyframe spacing may also b e adjusted by stretching shrinking or sliding moving a range within the sequence This provides some crude control over timing

The Editor

An interactive editor for creating and editing animation sequences for arbitrary skeletons is shown

in Figure The current skeleton is displayed in

view Each of these views may o ccupy the large

manipulated Existing sequences are group ed into menus and displayed in iconic form to the right

three orthogonal views and a

main work area in which the skeleton may b e

single p ersp ective

Figure Sequence editor screen

of the screen Each sequence

a simple ipb o ok preview of the movement as a memory aid A sequence

icon can cycle through all of the keyframe p oses on request generating can b e named and added menu item can later b e reloaded for editing A small display b eneath

to one of these menus and a

the main viewp ort shows the keyframe p oses within the loaded sequence

These are laid out along

CHAPTER AN INTERACTIVE EDITOR

a timeline to indicate the keyframe spacing A set of VCRlike transp ort controls are provided for playing back the animated sequence in the main display area

The small timeline provides a convenient interface for copying cutting and pasting ranges of keyframes within a sequence as well as mo difying the keyframe spacing But the key p oses them selves must b e created or mo died by adjusting the skeleton displayed in the main window For manipulating the skeleton forward kinematic controls are provided in the form of sliders for adjust ing individual joints within the skeleton one at a time In addition the interface has b een mo died to p ermit inverse kinematic manipulation of the skeleton In this mo de the user may use the metho ds

presented in the previous chapter to up date multiple joints

implementation of this interface for direct manipulation is briey describ ed b elow

Direct Manipulation

With direct manipulation the user adjusts the skeleton by selecting and dragging a b o dy part rather than adjusting individual joints A dragging session b egins when a b o dy part is selected with the mouse and ends when the mouse button is released Dragging is a p ositioning mechanism only it do es not directly control the orientation of the selected part To supp ort dragging the interface must provide a way of identifying a serial chain of joints within the skeleton which will b e considered

a manipulator as

well as

a way of unambiguously sp ecifying endeector goals for the chain

Identifying the Chain

A chain of joints

b oth a base joint

hierarchy is traversed backwards from the selected part towards the ro ot Three mo des control how far up the tree this traversal pro ceeds b efore stopping at a

within the skeleton is dened when a b o dy part is rst selected at which time

and an

endeector must b e determined To determine a base joint the skeleton separate interaction joint which b ecomes

the base of the chain The

stop

stop

stop

The rst of these

equivalent of p ositioning the part using the forward kinematic slider controls The second results in a chain which extends from the nearest branch in the hierarchy and is therefore a useful default to use when dragging limbs Selecting and dragging a hand for example would move the entire arm without disturbing the torso The third interaction mo de p ermits the user to override these default

when the parent

when the parent

when a named joint is reached

stopping criteria corresp onding to each of the three joint has a b o dy part attached to it

joint has multiple children

dragging mo des are

results in only the selected b o dy part b eing dragged and is the direct manipulation

by dragging one b o dy part around The

CHAPTER AN INTERACTIVE EDITOR

b ehaviours by explicitly naming a joint from which the chain extends

torso of the

In p oint

a user

p oint on the b o dy segment underneath the cursor by casting a ray and intersecting it with the ob ject The alternative is to predene lo cations within the skeleton which may b e selected for dragging the lo cations of the joints themselves for example This requires either that the lo cations b e displayed in some iconic form so the user can select one or that the cursor warp to the nearest one when the

joint as the chain base for example in which spine

case pulling on the

addition to the base of the chain the endeector p osition must

b eing dragged There are two p ossible approaches to determing the endeector lo cation when

p oints at a b o dy segment and presses the mouse button The rst is to explicitly compute the

mouse button is pressed

a point on the surface of the ob ject and making that point the location of the endeector frame This gave mixed results On one hand it allowed the user to click anywhere on the ob ject for dragging without any disconcerting cursor warping On the other hand having the endeector frame located on the ob ject surface often resulted in unexpected twisting of the segment especially

must resolve the ambiguity in here is to cast a ray through is closest to the endeector technique provides reasonable

mapping a the cursor This p oint

b ehaviour

D screen lo cation to a D lo cation The solution adopted into the world and to nd the p oint on this line which b ecomes the goal p osition for the current iteration This

in b oth orthographic and p ersp ective views

The initial decision was to cho ose the former metho d explicitly computing

with the Jacobian metho d As a compromise the current implementation halfway along the segments axis of selfrotation warping the cursor to the lo cation Lo cating the endeector along the segment axis eliminates the twisting

places the endeector corresp onding onscreen problem of unexp ected

Determining an EndEector Goal

To compute new goal p ositions for the endeector as the cursor moves around on the screen we

With an orthographic pro jection the cast ray is parallel to the line of sight and the closest point

on the line will lie in the plane p erp endicular to the ray and

the endeector is constrained to lie within the plane while

pro jection view the cast ray may diverge from the line of

endeector to the ray is no longer constrained to lie parallel to the image plane The endeector is therefore free to move in any direction and may even b e pushed and pulled towards and away from the viewer with a little practice Figure illustrates the case for b oth p ersp ective and orthographic pro jections

Thus the user can

arm would result in a b end

b e known since that is the

containing the endeector In this case it is dragged around In a p ersp ective sight and the shortest path from the

sp ecify a

CHAPTER AN INTERACTIVE EDITOR

goal

goal

(a)

(b)

Figure Plan view of goal determination in a an orthographic view and b a p ersp ective view

Once the new goal p osition for the endeector has b een computed the skeleton is instructed to solve the inverse kinematic problem the user can select the solution metho d to use by setting

a program option The screen is refreshed and the cursor lo cation resampled after

to provide resp onsive feedback Of course when a single iteration is insucient to solve the most recent problem the movement of the skeleton lags b ehind the cursor In practice this small tracking delay has not b een a problem

To provide some control over the resp onsive b ehaviour of the skeleton the user can interactively

mo dify metho d of a set

weighting parameters at each individual joint This is particularly useful when the CCD is used allowing a the resp onsiveness of a chain to b e varied from that of a sti ro d to that of lo osely coupled links

Constraints

As an

apply

in place while the p ose is b eing edited Currently constraints are enforced by iteratively

set of p ersistent inverse kinematic goals using the CCD metho d This restricts us to a set of simple geometric goals

Lo cking an endeector p osition

Lo cking an endeector orientation This can b e a partial lo ck of only one or two directions

eg lo ck Y orientation only

additional p ositioning aid a small set of constraints have b een dened which the user may to any segment of a skeleton The most useful of these are intended to lo ck limb extremities solving a

each iteration

CHAPTER AN INTERACTIVE EDITOR

A weighted combination of b oth of these

Constraining an endeector to lie within a plane

To apply a lo ck the user selects a segment then makes a lo ck selection from a menu Once created

a lo ck remains in place until it is explicitly deleted A lo ck can b e edited to change either its imp ortance weighting or the joints which can contribute to maintaining the lo ck The lo ck or orientation can also b e mo died by either dragging the lo ck or twisting the endeector a set of sliders

typ e its lo cation through

The intent is that lo cks represent constraints which are to b e maintained during any subsequent p ositioning of the gure To achieve this after each editing op eration of a gure whether through direct manipulation or the forward kinematic slider controls a numb er of iterations of the multiple goal CCD solver are p erformed prior to each screen refresh When the numb er of iterations p erformed is insucient to satisfy any constraints violated by the editing op eration some drifting from the lo ck

constraint p ositions is unavoidable

all constraints are met to the users

p erformed b etween screen refreshes

minimize visible constraint violations on a lowp erformance the resp onsiveness of the interface at the cost of constraint

Lo cking constraints are particularly useful when applied

the example of Figure the gures feet are

p osition and orientation The rst image shows

second image the p elvis has b een tilted to lean the gure and

applied to the p elvis In all three images the fo ot p ositions and orientations are maintained and the CCD solver is fast enough that the p elvis can b e tilted and twisted interactively without noticeable sliding of the feet For this example iterations b etween screen refreshes were sucient to maintain the constraints with negligible drift and provide an up date rate of frames p er second on a Silicon Graphics R Entry Level Indigo workstation This up date rate is inadequate for animation but quite sucient for interactive p ositioning

While lo cking endeectors in p osition is useful for creating a series of consistent keyframe p oses there still remains the problem of maintaining the constraints at the interp olated inb etween frames

But a button is provided for invoking the solver explicitly until satisfaction The user may also change the numb er of iterations

On a highp erformance

machine this numb er can b e set high to machine a smaller numb er can improve violations b ecoming more noticeable

in the third image a twist has b een

constrained the p osition

to the supp orting limbs of a gure In to stay in place by lo cking b oth their at which the lo cks are created In the

There is no guarantee that an endeector lo cked to some p osition

remain in that p osition if joint angles are merely interp olated b etween

the problem The rst and last images are keyframes in which the

the same p osition and orientation The image in the middle is the result of interp olating joint

in two adjacent keyframes will the p oses Figure illustrates feet have b een constrained to

CHAPTER AN INTERACTIVE EDITOR

Figure A gure b eing p ositioned by rst tilting then twisting the p elvis

angles b etween the two p oses

the keyframes The problem

relationship b etween the rate

at which the leg joint angles

rearrange the hierarchy to ro ot it at one of the feet but this would only alleviate the problem for that fo ot rearranging the hierarchy is not helpful when multiple endeectors are constrained

the feet clearly move through the o or during the transition b etween is that the gures hierarchy is ro oted at the p elvis and there is no at the which the p elvic translation is b eing interp olated and the rate need to change to maintain the fo ot p ositions Of course we could

In the current implementation the only attempt made to address this problem is to provide an option to enable constraint satisfaction during interp olation Each frame is computed as usual by interp olating joint angles then the CCD solver is invoked until any violated constraints have b een resatised In essence a series of singleframe constraint problems are solved This approach is admittedly ad hoc and it is not clear yet how well it will work it app ears adequate for the few situations tested so far although interp olation can no longer b e p erformed onthey

Initial feedback suggests that even this simple approach to enforcing geometric constraints com bined with direct inverse kinematic manipulation is a signicant improvement to the keyframe editor

CHAPTER AN INTERACTIVE EDITOR

Figure a First keyframe p ose b Interp olated p ose c Second keyframe p ose

Chapter

Conclusion

Summary

We have examined solutions to the inverse kinematic problem applied to manipulating articulated skeletons in an interactive keyframe animation editor As alternatives to previously published algo rithms in the graphics literature a pair of simple algorithms have b een describ ed which can provide relatively inexp ensive direct manipulation of a gure The rst of these is really just an application of a simple minimization metho d but its application to inverse kinematics has not previously b een made explicit The second is a new heuristic algorithm adopted and mo died from the rob otics liter ature The advantages and disadvantages of each have b een discussed and their relative p erformances gauged

Metho ds by which each algorithm can b e used to

b een develop ed and their resp ective advantages and disadvantages discussed An implementation of the simpler approach has b een incorp orated into a keyframe editor and the interface briey describ ed

As a bypro duct a to olkit library for dening and manipulating skeletons has b een implemented which insulates an application from the details of creating editing drawing and animating a gure A skeleton is also able to solve inverse kinematic problems p osed by the application allowing the application to deal with interface issues rather than dealing explicitly with inverse kinematic algo rithms This also allows new inverse kinematic solution metho ds to b e implemented and added to the to olkit without requiring mo dications to the application

satisfy constraints during manipulation have

CHAPTER CONCLUSION

Results

exp erimenting with several inverse kinematic metho ds in the course of this work some things

After

have

typ e or another no one approach seems uniformly sup erior

should not necessarily b e considered any b etter than other approaches but rather provide alternative approaches which may b e suitable in some applications

b ecome apparant The rst is that inverse kinematic

algorithms all exhibit problems

to others The metho ds presented here

The second p oint is that inverse kinematics as a p ositioning to ol is a useful complement to but not a replacement for simple forward kinematic p ositioning In particular for direct manipulation inverse kinematics is really only useful for chains with relatively few degrees of freedom single limbs for example In fact an interesting observation is that even with the ability to drag multiple jointed chains around many users of the editor describ ed in Chapter seem quite content with the default dragging mo de which drags just a single b o dy part Informal feedback from users suggests that while direct manipulation is a huge improvement to the interface over the previous sliderbased p ositioning the value of multiplejoint p ositioning is not quite so clear In fact trying to p osition a chain with many degrees of freedom with direct manipulation is often likely to cause unwanted changes to the skeleton For example trying to b end the spine of a gure by pulling on its ngers is probably asking to o much in the absence of additional constraints sp ecifying how changes should b e distributed among the joints any metho d is likely to give unnatural results Joint limits provide some constraints as do the weighting parameters at each joint but these do not seem to b e adequate particularly for manipulating recognizable b o dies Inverse kinematic metho ds which

p erform quite acceptably for disemb o died

chains or mechanical rob ots do not necessarily often app ear unnatural This problem is that

translate

well to animate gures

unnatural is sub jective and dicult to

result from considering these factors more carefully

the results can

the term quantify More p owerful p ositioning to ols are likely to

Either of the inverse kinematic algorithms presented in Chapter is adequate for interactive direct manipulation They are b oth simple to implement and are fast enough to provide go o d feedback

for gross p ositioning tasks However if high accuracy is a requirement and interactive not so much of a concern then other solution metho ds may oer b etter p erformance

Comments ab out Constraints

resp onse time

In Chapter the choice of the CCDbased p enalty metho d for implementation within the gure animation editor was largely based on p erformance issues the alternative Lagrange multiplierbased approach was deemed to o demanding for interactive use on a typical workstation This problem is temp orary however and it is worth reconsidering the decision in light of continuing increases in

of one

CHAPTER CONCLUSION

CPU p ower At the same time we can sp eculate a little useful to develop and how constraints might b e used for

ab out what typ es of constraints might b e

Given sucient CPU sp eed to retain numerical stability the Lagrange multiplier approach is the more general of the two The CCDbased metho d is fast b ecause it reduces a dicult problem to a series of simpler ones which can b e solved analytically using only simple geometric quantities But for problems more complicated than solving p osition and orientation constraints the reduction to analytical form is not always p ossible so the approach is limited to these typ es of constraints In contrast the Lagrange multiplier metho d could b e used to enforce many dierent typ es of constraints

including nongeometric ones the only requirement is that the constraints b e joint variables within a gure

Lo oking Ahead

some function of the

useful for gure ma the animation editor To o often a solution correct in the sense that all geometric constraints are satised seems incorrect b ecause it gure into an awkward lo oking p ose Think for example of a p erson going from a standing into a crouch The natural tendency is for the knees to move apart as the p erson crouches that is the comfortable way to crouch To manipulate a standing gure in the editor into a crouch one might lo ck the to es of each fo ot in place and then pull the p elvis down to make the gure crouch But without any other information ab out how the legs should move one is just as likely to see the knees move together as the gure crouches as to see them move together Perhaps this could b e rectied by sp ecifying additional geometric constraints on the knees but cho osing and sp ecifying these auxiliary constraints would probably b e dicult and timeconsuming A useful alternative

would b e a standard set of constraints which applied to the gure at all times

constraints to avoid uncomfortable p ostures or p ostures which would place a p erson obalance The latter can b e implemented as a constraint on a gures centerofmass a computable quantity given a set of joint angles while the former would require some function which measured comfort or naturalness given the same set of variables

In addition to manipulation constraints could also b e useful in animating a gure A natural place to start would b e to consider animating the constraint values Animating a p osition constraint for example might dene a tra jectory for some limb extremity to follow A simultaneous animated orientation constraint would control the orientation of the extremity as it traversed the tra jectory

What sorts of constraints other than the obvious geometric ones might b e nipulation Initial exp erimentation with the constraint solver implemented in indicates that geometric constraints alone while useful are not always enough

which is puts the p osition b ecause

But for complex motions constraints will probably b e more helpful in describing a desired

with some sort of scripting approach For example the movements of the supp ort fo ot of a walking

animation as

well as manipulation

These might include

movement

CHAPTER CONCLUSION

bip ed might b e describ ed in terms similar to the following

After heel strike the heel of the fo ot maintains its

touches the ground For a short p erio d the entire fo ot

b o dy moves forward Toward the end of the step the heel of the fo ot breaks contact with the ground rst followed shortly after by the ball of the fo ot

A description

movement If the description were more sp ecic ab out the time intervals and lo cations involved we

such as this identies a numb er of simple constraints which are in eect during the

would have a

language could b e implemented which would allow movements such as this to b e describ ed textu ally A script would need to sp ecify a set of constraints to b e imp osed and provide some way of activating and deactivating these constraints over the course of a movement An interpreter for such a descriptive scripting language would b e a useful to ol for gure animation

Directions

There are plenty of problems still to b e addressed At a low level of detail it is worth determining whether the p erformance of the Lagrange multiplier constraint satiser can b e improved up on First Surles has shown that some constraint problems for articulated gures can b e solved in linear time Sur He lists a numb er of prerequisites for this but in the context of chemical protein mo delling which is his application area An analysis of these prerequisites and what they mean in the context

fairly detailed script for animating the stance fo ot during a walk A simple scripting

of articulated skeleton manipulation would

sp eed up the solution pro cess is to consider

SVD MK the referenced pap ers on this

approaches to the inverse kinematic problem in general

p osition until the ball of the fo ot

remains lo cked in

place while the

b e useful A second area which could b e explored to Maciejewskis incremental algorithm for computing the topic are interesting reading and may suggest alternate

Designing interactive interfaces which make eective use of constraints is challenging and deserves

some

when

time What ab out constraints involving multiple gures

attention How should constraints b e represented Selected Edited What should happ en constraints conict with each other How should constraints b e animated and controlled over

And nally do inverse kinematics and constraints provide a convenient layer up on which higher level pro cedural motion mo dels can b e built An interesting exercise would b e to extend Bruderlins walking algorithm to handling uneven terrain making use of the basic techniques describ ed in this thesis to achieve and maintain fo otholds

Biblio graphy

AG W Armstrong and M Green The dynamics of articulated rigid b o dies for purp oses of animation The Visual Computer

AN L Alt and A Nicolas Animating articulated structures with multiple goals In Proceed ings of Computer Graphics pages

AW W Welch A Witkin M Gleicher Interactive dynamics Computer Graphics March

Bai J Bailleiul Avoiding obstacles and resolving kinematic redundancy In Proc Int Conf on Robotics and Automation April

BB R Barzel and A Barr Mo deling with dynamic constraints In SIGGRAPH Course Notes Topics in Physical lyBased Model ling

BC A Bruderlin and T Calvert Goaldirected dynamic animation of human walking Com puter Graphics July

BH R Bartels and I Hardtke Sp eed adjustment for keyframe interp olation In Proceedings

of Graphics Interface pages

BMW N Badler K Mano o chehri constraints IEEE Computer

and G Walters Articulated gure p ositioning by multiple Graphics and Applications June

BN L Brotman and A Netravali Motion interp olation by optimal control Computer Graph ics August

CHP J Chadwick D Haumann and R Parent Layered construction for deformable animated characters Computer Graphics July

Coh MF Cohen Interactive spacetime control for animation Computer Graphics July

BIBLIOGRAPHY

CP N Badler C Phillips J Zhao Interactive realtime articulated gure using multiple kinematic constraints In Proceedings Symposium on Graphics pages

manipulation Interactive D

CWGL TW Calvert C Welman S Gaudet and C Lee Comp osition of multiple gure sequences for dance and animation In Proceedings of CG International

DSS H Das JJ Slotine and TB Sheridan Inverse kinematic algorithms for redundant systems In Proceedings IEEE Intl Conference on Robotics and Automation pages

FW D Forsey and J Wilhelms Techniques for interactive manipulation of articulated b o dies using dynamic analysis In Proceedings of Graphics Interface pages

Gir M Girard Interactive design of d computeranimated legged animal motion In Pro ceedings Workshop on Interactive D Graphics pages

Gir M Girard Constrained optimization of articulated animal movement in computer ani mation In N Badler B Barsky and D Zeltzer editors Making Them Move Mechan ics Control and Animation of Articulated Figures chapter pages Morgan Kaufmann PublishersInc San Mateo Ca

GM M Girard and A Maciejewski Computational modeling for the computer animation of legged gures Computers Graphics July

GMW P Gill W Murray and M Wright Practical Optimization Academic Press New York NY

Gom J Gomez Twixt A d animation system Computers and Graphics March

GP B Guenter and R Parent Computing the arc length of parametric curves IEEE Computer Graphics and Applications May

Gre TNE Greville The pseudoinverse of a rectangular or singular matrix and its application to the solution of systems of linear equations SIAM Review January

GW M Gleicher and A Witkin Dierential manipulation In Proceedings of Graphics Inter face

Hah JK Hahn Realistic animation of rigid b o dies Computer Graphics August

BIBLIOGRAPHY

HS P Hanrahan and D Sturman Interactive animation of parametric mo dels The Visual Computer

IC P Isaacs and M Cohen Controlling dynamic simulation with kinematic constraints b ehaviour functions and inverse dynamics Computer Graphics July

IC P Isaacs and M Cohen Mixed metho ds for complex kinematic constraints in dynamic gure animation The Visual Computer

Kas M Kass Condor Constraintbased dataow Computer Graphics July

KB J Korein and N Badler Techniques for goaldirected motion IEEE Computer Graphics and Applications

KB D Ko chanek and R Bartels Interp olating splines with lo cal tension continuity and bias control Computer Graphics July

KH CA Klein and CH Huang Review of pseudoinverse control for use with kinemati cally redundant manipulators IEEE Transactions on Systems Man and Cybernetics MarchApril

Las J Lasseter Principals of traditional animation applied to d computer animation Com puter Graphics July

LWZB P Lee S Wei J Zhao and N Badler Strength guided motion Computer Graphics

Mac A A Maciejewski Dealing with the illconditioned equations of motion for articulated gures IEEE Computer Graphics and Applications May

MK AA Maciejewski and CA Klein The singular value decomp osition Computation and applications to rob otics International Journal of Robotics Research Decemb er

NN ZR Novakovic and B Nemec A solution of the inverse kinematics problem using the sliding mo de IEEE Transactions on Robotics and Automation April

Pau RP Paul Robot Manipulators Mathematics Programming and Control MIT Press Cambridge MA

PB C Phillips and N Badler Interactive b ehaviours for bip edal articulated gures Com puter Graphics July

BIBLIOGRAPHY

PFTV WH Press BP Flannery SA Teukolsky and WT Vetterling Numerical Recipes in C The Art of Scientic Computing Cambridge University Press Cambridge MA

SB S Steketee and N Badler Parametric keyframe interp olation incorp orating kinetic

adjustment and

phrasing control Computer Graphics July

Sho K Sho emake July

Animating rotation with quaternion curves Computer Graphics

SS L Sciavicco and B Siciliano A dynamic solution to the inverse kinematic problem of redundant manipulators In IEEE Intl Conference on Robotics and Automation pages March

Ste G Stern Bb op a program for dimensional pages

animation In Nicograph Proceedings

Stu D Sturman Interactive keyframe animation of d articulated mo dels In SIGGRAPH

Course Notes Computer Animation D Motion

Specication and Control pages

Sur MC Surles An algorithm with linear complexity for interactive physicallybased mo d eling of large proteins Computer Graphics July

SZ K Sims and D Zeltzer A gure editor and gait controller for task level animation In SIGGRAPH Course Notes Synthetic Actors The Impact of Articial Intel ligence and Robotics on Animation

WC LCT Wang and CC Chen A combined optimization metho d for solving the inverse kinematics problem of mechanical manipulators IEEE Transactions on Robotics and Automation August

WCH B Wyvill M Chmilar and C Herr A simple mo del of human animation In SIGGRAPH Course Notes Synthetic Actors The Impact of Articial Intel ligence and Robotics on Animation

WE WA Wolovich and H Elliot A computational technique for inverse kinematics In Proceedings of rd Conference on Decision and Control pages Decemb er

Wil J Wilhelms Virya a motion control editor for kinematic and dynamic animation In Proceedings of Graphics Interface pages

BIBLIOGRAPHY

Wil J Wilhelms Using dynamic analysis for realistic animation of articulated b o dies IEEE Computer Graphics and Applications June

Wil J Wilhelms Dynamic exp eriences In N Badler B Barsky and D Zeltzer editors Mak ing Them Move Mechanics Control and Animation of Articulated Figures chapter pages Morgan Kaufmann PublishersInc San Mateo Ca

WK A Witkin and M Kass Spacetime constraints Computer Graphics August

ZB J Zhao and N Badler Real time inverse kinematics with joint limits and spatial con straints Technical Rep ort Technical Rep ort MSCIS University of Pennsylvania

Zela D Zeltzer Motor control techniques for gure animation IEEE Computer Graphics and Applications

Zelb D Zeltzer Representation of complex animated gures In Proceedings of Graphics Interface pages