Saturday, April 3, 2010

Closed for Non-Iterative Inverse Kinematics

Last year I submitted an article to the Game Programming Gems people on IK.

The article titled 'Non-Iterative, Closed Form, Inverse Kinematic Solver' ( a mouthful I apologize ), was published in Game Programming Gems 8 that was released in March. I just received my copy, and it is very satisfying to see the article in print in a well respected hard cover volume, and that the article is highlighted in the preface is especially gratifying. Getting the article written up and polished was not an insignificant amount of work.

The algorithm presented in the article has been through many stages of evolution starting out as a much simpler, limited solution in CAT1. It was developed considerably for CAT2 , and for the article it was overhauled once again to improve the behavior.

My personal perspective is that this algorithm renders solvers such as CCD redundant especially in the field of game development, and I build a case for this in introduction section of the article. However, I hope that this will spur people on to refine and develop the solver further based on particular requirements in their project.

I was rebuilding the solver recently (after the article submitted for publishing), and I think I may have found a way to develop the idea even further, simplifying even more the basic concept, and providing greater level of control.

The idea in the solver is that for every bone in a chain hierarchy, you can identify 2 important values that can be used to drive the solution.
The algorithm assumes a hierarchical solve, calculated either from the base of the chain to the tip, or vice versa. As each bone in the chain is solved, the resulting solution will have an effect on the children bones as they will need to solve according to the results of their parents. Basically, for the overall solution to be valid, each bone must be solved such that they allow the remaining bones in the chain to be solved.

This introduces the first condition, that each bone must be solved such that the distance from the tip of the bone to the goal allows the rest of the chain to reach the goal if possible.
The resulting pose of the bone must allow the children to reach the goal if possible. This gives us a maximum allowable angle for the bone relative to the vector between the bone and the goal.

The other key concept of the solver is the the FK pose of the chain prior to solving gives us what we might consider a 'model' answer. The concept being that IK applies a minimal change in pose to the chain thereby preserving the pose of the character, and also allowing FK animation to drive the shape of the chain over time.

We de-construct the model pose to a 'desired angle' for each bone at a given distance from the goal.

In the article, I go into detail including diagrams, and example code on how to derive a solution for a chain in a single pass of the hierarchy by comparing the 2 angles, and using them to infer a new angle for the exact context the chain is actually being solved in. This is achieved by linearly interpolating the 2 values according to a parameter extracted from the context of the solve. The actual distance to the IK goal.

The algorithm works very well, and I think that they accompanying code should demonstrate this. However, there is one weakness to the solver that bugs me.

For long chains, where the length of the chain is far greater than the distance to the goal, the solution, while technically correct, may produce results that are undesirable. Bones in the chains may bend too far or too little for the character they are solving for. Now, I am really splitting hairs, and I would actually like to see a character who which I predict the problems might occur.

This motivated me to think a bit more about the problem, and I decided that what would be prefect would be some very specific way of describing the angles of the bones for the range of possible contexts. This description would need to satisfy at least the first condition mentioned above, but I think both would be important. I think that a parametric function curve could be defined that would give artists very explicit control over the solving, while always producing a valid result that respected the FK pose of the chain prior to solving. I have started prototyping this new curve based method, and although my initial results are really a step down from the solver presented in the book, I do have confidence that there is a new, simpler, clearer version of the solver on the horizon.

=Data Size=
With the ability to specify a curve which defines the angles for the bones for a range of contexts, this would also give the engineers the option of eliminating all the FK animation data on limb bones where IK would be solved. Effectively, instead of specifying a pose for the limb at every frame of every animation, you provide a set of curves, which describes the ideal pose of the limb under all possible conditions. These curves could be extracted from reference animation for example, giving the artists the ability to say, 'this is how this leg should always be solved'.

The position of the tip of the chain would need to be extracted prior to this step and stored because no doubt you will need this data later, but many engines, including the Unreal Engine already do this. The other channel that you would need to keep somehow would be possibly the root bone orientation. This is because it will contain some twist information that cannot be derived at runtime. I believe this twist information could be reduced to a single float channel.

For complex creatures with many chains with many bones each, this would remove a big chunk of your data without affecting the quality of the animation at all. This is just an idea.

If you are interested in the problem of IK, or looking for a solution, then I would recommend that you check out the book.

I find the domain of IK interesting, and I plan to keep working on variations of this solution until every possible avenue has been explored. If anyone has any questions/comments, please send them my way.

Friday, October 16, 2009

Why did you do that?

I have had my fair share of strife when managing teams of people. I have attended various training courses etc... and the one thing that they never explain is how to tell people what not to do.

Its easy enough to tell people what to do. You have a project with some goals, and requirements, and so you start by reviewing the goals and requirements with the team. In your head everything is crystal clear, and after the 1-2 hour discussion, it seems that the team members are content with the project definition. Then, everyone smiles, nods and agrees that this project, is simple, clear, and will easily be accomplished within the given time frame.

3 weeks later its a mess...

Why didn't you tell the programmer not to write that huge new data structure to mirror the existing perfectly useful structure.
Why didn't you tell the artist not to put all the assets in one monolithic file.
Why didn't you tell the engineer not to fragment that 1 page C++ function into multiple micro functions distributed across multiple source files, all relying on scary side effects and carefully organised calling sequence.

I realize this is all simply about communication, and experience. Something that I believed was obvious, and didn't need to be said, wasn't obvious to the team members. The solution isn't to micro-manage and tell people exactly what to do and exactly how to do it. Everybody wants to contribute to the project, and add something of themselves.

But, how, oh how do you guide a project through and avoid the incredible tangents that junior members are guaranteed to do, just to inject a part of their inexperience into the project. In some cases, you just can't afford to let people learn the hard way.

I had a long day....

Tuesday, March 3, 2009

Proxy Manipulator - Update

I did a bit of an update to the ProxyManipulator. 

One of the key goals was to set up a nice fast foot pivot system that didn't require any fancy controllers actually installed on the foot object.

One of the weaknesses, is that although possible to manipulate an object in a perfect arc, the created keyframes will be linearly interpollated. 

I have added an option to create several keyframes on the time line at ouce, to create a better arc. If you wanted an object to move in a perfect circle, you just turn this value right up. 

I have also built Max 9, 2008,  2009 versions, and soon I'll compile a version for the next revision of Max. 

I have also uploaded the source code. This controller is fairly simple and the source code could become a template for your own project. 

Also, you coould take the code and re-compile it for whatever version of max you are using. 

Have fun.


Sunday, February 22, 2009

Proxy Manipulator

I had this idea for a simple controller that would filter manipulations and pass them on to other objects. 

It is based on the 'Gizmo Transform' controller that comes with CAT, but this one is a lot more sophisticated, and can do a few more tricks. 


3dsmax actually has a very flexible powerful animation system. the original designers of max made it possible to write plugins for virtually any area of the software, and a tool like this 'Proxy Manipulator' is really not a lot work to write. It took me only a few hours to have it up and running, and a few more hours to make it load and save and handle undos etc...

The 3dsmax SDK doesn't do a lot of the dirty work for you like other SDKs. It basically leaves it up to the coder to handle lots of little problems which can be seen as a headache. I actually think that its not all that bad, and for an experienced developer Max is very malleable to your needs. 

Proxy Manipulator. 

the idea is basically that often you want to easily manipulate one, or a group of objects quickly and easily. 

The proxy manipulator enables you to set up configurations where you can manipulate one object, which passes on those manipulations to target objects, which in turn get keyframed

In the video I show a couple of different configurations of how you can use the controller, but I am sure for an imaginative TD, there are loads of cases. 

I don't consider this project finished, and I may add another few ideas if they are good and add to the original concept. 

I will be posting the source code soon, but if anyone want to take a look, just send me an email. Its really not a complex controller, but it embodies everything that the 3dsmax SDK was designed for. 

I also have ideas for a few companion controllers that could work with this one to improve on the final playback. 


Tutorial Video

plugin : You can get the plugin here. 

Please let me know if you find it useful, and if you need it in another flavour ( e.g. 2008 ), I can arrange that. 


Post Autodesk

Ok, so I have left work at Autodesk now, and instead I'm working for a small games company called trapdoor entertainment here in Montreal. 

Things are good, and I'm getting hands on experience in game development which is exactly what I wanted. 

Sunday, December 7, 2008


Hello world.

This blog will eventually be filled with articles and links that I have gathered and have found interesting.

My Background...

I studied at Otago University in New Zealand where I earned a Bachelor in Computer Science. Uni life was fun and I didn't work all that hard on my courses. I was way to busy working on my animation demo reel in 3dsmax to care about my grades in engineering.

Ra Productions

I worked for a small local production company called Ra Productions where I was lead animator.
We worked on a bunch of smaller TV shows for Animal Planet, National Geographic, BBC, and smaller local productions also.
One show called 'The Most Extreme' heavily featured animation and went on to be nominated for an Emmy for its 2nd show, The Most Extreme : Jumpers.
Here is a sample of the show from a later season when I no longer worked on it. It still features all of my earlier work including the introduction sequence and countdowns.


I started up CAT with my boss at the time, Scott Pearson to commercialize some ideas I had been developing for a while. The ideas were mostly about procedural motion. I worked for roughly a year on CAT before we considered turning it into a product.
The background we came from was not big productions and we used ourselves as a customer template for development. CAT 1.0 was released in November 2003 after quite a short beta period. This turned out to be a little short sighted and so for CAT 2.0 the whole system was overhauled with bigger ideas in mind. 2005 

CAT was a very tough learning experience for me. I started out in a tiny little studio with a few ideas and soon I was in charge of a development team supporting a product used by a collection of high profile game studios. From a standing start I had to learn about pipelines, motion capture, batch process, etc... and present a solution to the world without any experience in it, or the resources to do any real research.

That said, I think I can safely say that CAT is a strong product that presents many many novel and inovative approaches to solving loads of tough problems in 3d animation. The many long nights at the office banging my head against problems were eventually fruitful.

Being lead developer, and demo guy is an interesting challenge. I was in front of customers as the demo either went well and everybody was impressed, or it crashed and burned in a humiliating reality check that sent me rushing back to the hotel to email 'the guys', or try and fix it myself before going to bed.

We went on for another year and started the CAT 3 beta cycle when we were eventually acquired by Softimage (Avid) in July 2006.


At Softimage, I found my biggest impact was taking a leading role in developing the workflow for ICE in XSI 7.0. Although in production I had used particles quite a lot(more than characters actually). this was back in 3dsmax 2.0 or 3.0 and so that experience wasn't much to lean on when it came to defining the workflow for one of the most impressive pieces of engineering to be developed in recent years.

One reason for posting this blog is to write some articles explaining some techniques when using ICE, and help people get to grips with this system faster.


This part of the story is still being written, but what I can say is that I have learned a lot more about the world of animation. Now I am head of animation at Softimage, and we have just been acquired by Autodesk.

The future looks bright for me, and especially good for the CAT product and therefore its loyal fans

Thanks for reading and hope to see you back