Simulating an Inverse Kinematics Chain

Inverse kinematics is a fun application of linear algebra and calculus that is extremely relevant in computer animation. Given a rigged skeleton, inverse kinematics can solve the joint angles (or similar parameters for other types of joints) necessary to minimize the distance between the end effector (i.e. joint at the end of the chain) and target. Solving this system essentially boils down to the following system of equations:

\vec{e}=J\vec{\Delta\theta}

where \vec{e} is called the “error vector,” and describes the velocity of the end effector necessary to converge on the target; \Delta\vec{\theta} is the vector of joint angle velocities that will result in the correct end effector velocity (this is the unknown part), and the Jacobian matrix J, that encodes the change of basis from joint angle space to Cartesian coordinate space for the partial derivatives. Alternatively, you can view this as a transformation matrix that takes the rate of change of the joint angles and relates it to the rate of change of the Cartesian coordinates of the end effector joint.

It is common to have more columns than rows in a system like this (especially in a chain), because the there will be few end effectors and many joints. Because the matrix is not invertible, our next best thing is the Moore-Penrose psuedoinverse which gives a least-squares solution to the problem. This is desirable because there are many cases where the chain cannot converge on the target, so we want the best possible attempt. The results in the following equation:

\Delta\vec{\theta}=J^T(JJ^T)^{-1}\vec{e}

This form of the psuedoinverse assumes that you have full row rank in your matrix J, otherwise JJ^T will be singular an non-invertible. This presents a problem because there do exist singularities in certain joint configurations. A common solution to this problem is to damp this matrix by a small factor to ensure invertibility. This method is called the Damped Least Squares method, and the requires only a simple change to the previous equation:

\Delta\vec{\theta}=J^T(JJ^T + \lambda I)^{-1}\vec{e}

Here, \lambda is just an arbitrarily chosen constant that keeps the matrix from every going singular. The bigger the constant, the less realistic the motion near singular configurations. On the other hand, a higher constant results in more numerical stability in the equations. The demo I wrote allows you to set an arbitrary \lambda value.

I also implemented two other solvers, a Jacobian Transpose solver and a Cyclic-Coordinate Decent solver. The former cheats by using the transpose of the Jacobian to solve the system rather than the psuedoinverse. It’s a simple solution but results in a lot of jittery motion and isn’t very realistic. CCD essentially loops through each joint multiple times and orients the child chain in the direction of the target. With enough iterations, this converges on a solution, but it only works in situations where joints are 1DOF. It is quite simple to understand and there are several articles online that explain it well.

Finally, the demo is written in Python using the pyglet library. User interactions is almost exclusively through a console interface (activated with ~). Included in the zip is a text file with the syntax for these commands.

Source Archive

For a more in-depth introduction to this topic, I found this paper extremely helpful.

Advertisements

Some Thoughts on Software Design

NOTE: This was taken from my blog on gamedev.net. I’m migrating things over slowly.

Software Engineering as I understand it involves the concept of software design. Anyone can program, and I would even venture to say that programming is the easy part. Good software design is where things get hairy. I consider myself a seasoned programmer, but a somewhat fledgling Software Engineer–a state that I think is fairly commonplace among academic or hobbyist developers. Bad habits done out ignorance can carry over into the industry and wreak havoc on bigger projects. I too am struggling when it comes to designing and implementing larger systems (like a game engine), although I am learning a lot. Though I am still inexperienced, I thought I might share some of my realizations so far. If you consider yourself a seasoned software engineer, feel free to comment/correct as you see fit.

Formulate Requirements

First of all, trying to design a system without knowing the requirements will drive you insane if you are expecting any semblance of quality in your architecture. I know this because I’ve tried. My previous attempt at creating a game engine went down in flaming glory because the end result wasn’t as flexible and usable as I had hoped. Before you write a single line of code, I implore you, write a design document for your project. Describe what the system needs to do in detail. Why is this so important? Without this step, you’re essentially flying blind. You will re-factor your code three times as often, bloat your code base including features you don’t need; and if you’re like me, you’ll agonize over finding the Right Way to do it–except you won’t, because you don’t know what you need.

Case in point: in my first engine, I rewrote my resource manager four times. Not a simple re-factor mind you; a complete rewrite. I included features like loading from a separate thread, which is a great feature, except that I didn’t really need it. I just thought it was cool and that every engine should use it. Granted, I learned a lot about what I did need during those four rewrites, but I would have been better off starting with the essentials and refactoring from there. I went into it without fleshing out how the end product would use the system; as a result, my design suffered from code bloat.

Build a (Good) Foundation

I’ve heard differing opinions on this, so take it with a grain of salt. I see a two specific mistakes that neophyte developers make (including myself) when they are just starting a big project. Either they try to sketch out the entire system (a large one, mind you) on paper, in detail, including every major class and how they’ll interact with other classes; or they don’t attempt to design anything and just start coding. The latter is just pure laziness in my opinion–the chances of designing a good system with that strategy are akin to winning the lottery (unless you’re John Carmack). The former, however, is just as destructive. From my experience, trying to build exclusive from the top down is paralyzing. You scrap design after design trying to find the perfect one (hint: it doesn’t exist).

As with all things in life, good design comes with moderation. Begin with your requirements and write some hypothetical sample code of how you will use the system. One good way I’ve found is to write a bogus program (or part of one) in pseudo code, testing out various interfaces and ideas. At the same time, begin building the foundation for your system. If it’s a game, start with the basics, like a basic map loader. Just get something working.

Break Down Work into Manageable Chunks

As you build the components of your system, not only will the next step become more clear, but so will the requirements. You’ll realize something you need but couldn’t have known early on in the process. This allows you to refine your requirements as well as your code. By starting simple, you will save time refactoring and gain momentum and efficiency. I see many developers who attempt to write hundreds of lines of code without ever compiling it. They proceed to spend hours trying to get it to even compile, and then twice as many working out the bugs. This is not good practice; a better method is to utilize unit testing. This is the process of writing small chunks of code and then rigorously testing it before moving on to another component. This gives you confidence in the components of your system as you build on them, and boosts your morale as you see small parts working independently. Furthermore, it simplifies bug fixing since you can focus on one part of the system exclusively.

Pick an Achievable Goal and Stick to It

This is probably the most important point. Avoid the pain and suffering of trying to design the perfect system for any product. It won’t happen. Always know your requirements and design for that only. This is especially true if you are trying something new. I don’t personally know how the guys at Epic designed Unreal 3 or their story, but I would imagine they built it up using the good parts of their games. Not only that, but the guys developing Unreal Engine 4 are probably the same ones who built the previous three engines (at least the lead developers). In short, defer your amazing do-it-all project for when you actually know what you’re doing (I say this to myself as well). Most of us started out wanting to develop the best MMO on the planet; we quickly realized this was foolish. However, some of us are repeating that foolishness on a smaller scale. We’re trying to build something we have little experience with, and make it better than everything else out there. That’s just my opinion.

How does this apply to me? Well, a lot. I’m trying to trim down my grandiose plans to something manageable. For instance, what are my goals? I’ve spoken about those in recent blog entries. If you go back to my first blog, you’ll find that I’ve trimmed it down a bit since then. I may trim it down even more. As a humble hobbyist with only 10 or so hours a week to devote to doing what I love, this has to be the way it is. It’s just reality.

Anyway, I hope this was helpful. Again, it’s just my opinion, and I’d love to hear your feedback if you agree or disagree. Thanks!