Inverse Kinematics (part 1)CSE169: Computer AnimationInstructor: Steve RotenbergUCSD, Winter 2008Welman, 1993 “Inverse Kinematics and Geometric Constraints for Articulated Figure Manipulation”, Chris Welman, 1993 Masters thesis on IK algorithms Examines Jacobian methods and Cyclic Coordinate Descent (CCD) Please read sections 1-4 (about 40 pages)Forward Kinematics The local and world matrix construction within the skeleton is an implementation of forward kinematics Forward kinematics refers to the process of computing world space geometric descriptions (matrices…) based on joint DOF values (usually rotation angles and/or translations)Kinematic Chains For today, we will limit our study to linear kinematic chains, rather than the more general hierarchies (i.e., stick with individual arms & legs rather than an entire body with multiple branching chains)End Effector The joint at the root of the chain is sometimes called the base The joint (bone) at the leaf end of the chain is called the end effector Sometimes, we will refer to the end effector as being a bone with position and orientation, while other times, we might just consider a point on the tip of the bone and only think about it’s positionForward Kinematics We will use the vector:to represent the array of M joint DOF values We will also use the vector:to represent an array of N DOFs that describe the end effector in world space. For example, if our end effector is a full joint with orientation, e would contain 6 DOFs: 3 translations and 3 rotations. If we were only concerned with the end effector position, e would just contain the 3 translations.[]Mφφφ...21=Φ[]Neee ...21=eForward Kinematics The forward kinematic function f() computes the world space end effector DOFs from the joint DOFs:()Φe f=Inverse Kinematics The goal of inverse kinematics is to compute the vector of joint DOFs that will cause the end effector to reach some desired goal state In other words, it is the inverse of the forward kinematics problem()eΦ1−= fInverse Kinematics Issues IK is challenging because while f() may be relatively easy to evaluate, f-1() usually isn’t For one thing, there may be several possible solutions for Φ, or there may be no solutions Even if there is a solution, it may require complex and expensive computations to find it As a result, there are many different approaches to solving IK problemsAnalytical vs. Numerical Solutions One major way to classify IK solutions is into analytical and numerical methods Analytical methods attempt to mathematically solve an exact solution by directly inverting the forward kinematics equations. This is only possible on relatively simple chains. Numerical methods use approximation and iteration to converge on a solution. They tend to be more expensive, but far more general purpose. Today, we will examine a numerical IK technique based on Jacobian matricesCalculus ReviewDerivative of a Scalar Function If we have a scalar function f of a single variable x, we can write it as f(x) The derivative of the function with respect to x is df/dx The derivative is defined as:()()xxfxxfxfdxdfxxΔ−Δ+=ΔΔ=→Δ→Δ 00limlimDerivative of a Scalar Functionf-axisx-axis xf(x)Slope=df/dxDerivative of f(x)=x2()()()()xxxxxxxxxxxxxxxxxdxdfxxfxxxx22lim2lim2limlim :exampleFor 02022202202=Δ+=ΔΔ+Δ=Δ−Δ+Δ+=Δ−Δ+==→Δ→Δ→Δ→Δ()()xxfxxfxΔ−Δ+=→Δ 0limExact vs. Approximate Many algorithms require the computation of derivatives Sometimes, we can compute analytical derivatives. For example: Other times, we have a function that’s too complex, and we can’t compute an exact derivative As long as we can evaluate the function, we can always approximate a derivative()xdxdfxxf 2 2==()()xxxfxxfdxdfΔΔ−Δ+≈ smallforApproximate Derivativef-axisx-axis Δxf(x)f(x+Δx)Slope=Δf/ΔxNearby Function Values If we know the value of a function and its derivative at some x, we can estimate what the value of the function is at other points near x()()dxdfxxfxxfdxdfxfdxdfxfΔ+≈Δ+Δ≈Δ≈ΔΔFinding Solutions to f(x)=0 There are many mathematical and computational approaches to finding values of x for which f(x)=0 One such way is the gradient descentmethod If we can evaluate f(x) and df/dx for any value of x, we can always follow the gradient (slope) in the direction towards 0Gradient Descent We want to find the value of x that causes f(x) to equal 0 We will start at some value x0and keep taking small steps:xi+1= xi+ Δxuntil we find a value xNthat satisfies f(xN)=0 For each step, we try to choose a value of Δxthat will bring us closer to our goal We can use the derivative as an approximation to the slope of the function and use this information to move ‘downhill’ towards zeroGradient Descentf-axisx-axisxif(xi)df/dxMinimization If f(xi) is not 0, the value of f(xi) can be thought of as an error. The goal of gradient descent is to minimize this error, and so we can refer to it as a minimizationalgorithm Each step Δx we take results in the function changing its value. We will call this change Δf. Ideally, we could have Δf = -f(xi). In other words, we want to take a step Δx that causes Δf to cancel out the error More realistically, we will just hope that each step will bring us closer, and we can eventually stop when we get ‘close enough’ This iterative process involving approximations is consistent with many numerical algorithmsChoosing Δx Step If we have a function that varies heavily, we will be safest taking small steps If we have a relatively smooth function, we could try stepping directly to where the linear approximation passes through 0Choosing Δx Step If we want to choose Δx to bring us to the value where the slope passes through 0, we can use:()dxdfxxfdxdfxfdxdfxfiΔ≈−Δ≈Δ≈ΔΔ()1−⎟⎠⎞⎜⎝⎛−=ΔdxdfxfxiGradient Descentf-axisx-axisxif(xi)df/dxxi+1Solving f(x)=g If we don’t want to find where a function equals some value ‘g’ other than zero, we can simply think of it as minimizing f(x)-g and just step towards g:()()1−⎟⎠⎞⎜⎝⎛−=ΔdxdfxfgxiGradient Descent for f(x)=gf-axisx-axisxif(xi)df/dxgxi+1Taking Safer Steps Sometimes, we are dealing with non-smooth functions with varying derivatives Therefore, our simple linear approximation is not very reliable for large values of Δx There are