

CS 6665.001 "Character Animation" Projects, Fall 2014by Ian Mallett (ian AT geometrian.com)This is my project 1 for the course CS 6665.001, being taught at the University of Utah in Fall 2014 by Adam Bargteil. Project 1 is to implement an inverse kinematics solver. TheoryThe inverse kinematics algorithm essentially casts the degrees of freedom for each joint as being "directions" one can go toward a solution. Formally, each degree of freedom works out to be an element of a Jacobian matrix describing how much some feature on the linkage moves toward the goal. A simple example could be an arm with one hinge joint (so it can swing around in a circle) and you're trying to move one endpoint to a point on that circle. The Jacobian in this case describes how much moving the joint \(\Delta\theta_0\) radians moves you toward/away the point in each of \(\vec{i}\), \(\vec{j}\), and \(\vec{k}\). The Jacobian forms a system that looks like this:\[ \mathbf{J} \cdot \Delta\vec{\Theta} = \Delta\vec{x} \]In the above, \(\mathbf{J}\) is the Jacobian, \(\Delta\vec{\Theta}=\{\Delta\theta_0,\Delta\theta_1,\cdots,\Delta\theta_{n1}\}\) is a list of changes to parameters of the joints (usually angles, but possibly, for example, scalar translations), and \(\Delta\vec{x}\) is the difference between the feature's current value (for example, its current position) and the feature's goal value. The system is solved by using SVD to compute the pseudoinverse, thus obtaining \(\Delta\vec{\Theta}\). These changes are made to all the joints and the process is repeated. Hopefully, it converges to a configuration where the linkage satisfies the features. If you want to keep some particular parameter \(\theta_i\) as close to some value \(\hat{\theta}_i\) as possible (relative to the nullspace) while still solving the system, you can instead use the difference \(\Delta\theta_i+(\mathbf{J}^T\mathbf{J}I)\hat{\theta}_i\) instead of \(\Delta\theta_i\). ImplementationMy inverse kinematics solver implements arbitrary rigid bodies with up to two connections. Bodies have an arbitrary center of mass (which for my solver is, unfortunately, meaningless) and can have arbitrary joints attached at any location. To make things simpler though, my examples below keep joint locations axisaligned. All joints have degrees of freedom of rotation around their local axes as well as a sliding translational value. However, all joints have at least one degree of freedom disabled. Disabled degrees of freedom are excluded from the calculations above. To enforce joint constraints, the values are clamped after each step in the iteration. The algorithm proceeds until a certain tolerance is reached. I had a lot of trouble with the SVD implementation. Everywhere I looked, I saw claims that the algorithm was "wellknown". However, if you Google for it, you'll find about a dozen papers talking about ludicrously intricate techniques. One paper I found spent eleven pages discussing previous work. If you look for code, you'll find a few libraries, like LAPACK, GLS, and Eigen, and not much else. I did find a small Python script ported directly from ALGOL which gets kindof the right answers, sortof, for a subset of the problem. My math degree is in abstract math, not applied. Ask me about fundamental group of the octonions, analytic continuations, operatorvalued Banach algebras, sheesh whatever. But ask me about factoring a matrix? No. This became one of the very rare occasions when I defer implementation to the experts; I gave up and used Eigen. The inverse kinematics problem can not have a solution in particular cases (for example if the linkage tries to overextend itself), but sometimes the iteration can get caught in local minima, in the sense that a solution is possible but the algorithm is trying to converge to it in a manner that is "through" a constraint. My solver implements a basic global algorithm (which can be disabled): if convergence is not reached after a given number of iterations, the joint parameters are randomized and the solver tries again. This repeats indefinitely. In practice this helps resolve most of these cases. My implementation is quite configurable. In the examples below, \(10\) iterations are done perframe until the solution reaches a tolerance of a Euclidean, world space distance of \(\frac{1}{1000}\)th unit. If the global solver is enabled, the global randomization kicks in after \(100\) iterations without a solution being reached. ExamplesIn the following examples, the images are the expected result when the provided (below) binaries are run. The images have been resized here to better fit on the screen; view them individually to get the full effect. The white points are the centers of mass of the rigid bodies (cyan). Rigid bodies are connected by joints (red points) and are constrained (lying within green portions of red gimbals or else inside red cones). The effector (yellow) tries to reach the goal (orange). The controls are left mouse to drag the goal around (hold shift to raise it up), right click and drag and scrollwheel to move the camera. I apologize that the binaries are Windowsonly. Mac makes it literally impossible to write GUI programs in C++ without horrific compiling cruft, and Linux platforms vary too much. Requires GL 4.0 or higher and support for 32x multisampling FBOs. No installation or DLL horror required. These are standalone, statically linked applications. The only known problem is that the orange point may slowly drift when holding shift. I know why this happens, and I don't care about fixing it. Example 1: Simple Arm Example 2: Translational Arm Example 3: Complex Arm Video Binaries


