Some Cool Stuff

In the department of the new and cool, you should check out the videos of John Grden’s FITC presentation (otherwise known as all the justification you ever need to attend a conference where John is one of the speakers).

Keith Peters just released a copy of his presentation on Apollo – it’s the best introduction to Apollo I’ve seen. Excellent work.

Finally, check out this cool scientific graphing calculator done in Flex. Nice stuff.

References for FITC Presentation

Well, FITC is over and I have to give the conference high marks overall. I only had two battles. One was with the rental computer (screensaver from hell) and the other was reducing the slide count in the presentation to ensure I finished in the alloted time frame. Fortunately, I made it with just under a minute to spare, but one of the slides that got ‘cut’ was the references. So, here is the list.

Denavit, J. and Hartenberg, R., “A Kinematic Notation for a Lower-Pair Mechanism Based on Matrices,” Journal of Applied Mechanism, Vol. 1, 1955.

Eberly, D., “3D Game Engine Design,” Morgan Kauffman, San Francisco, CA, 1999.

Landers, I., “Skin Them Bones: Game Programming for the Web Generation,” Game Developer Magazine, Miller Freeman, May 1998.

Manseur, R. and Solari, L., “A Software Package for Kinematic Analysis of General Robot Manipulators,” Proceedings of the Florida Conference on Recent Advances in Robotics, FCRAR 2005, Gainsville, FL.

Manseur, R., “Robot Modeling and Kinematics”, DaVinci Engineering Press, Boston, MA, 2006.

Welman, C., “Inverse Kinematics and Geometric Constraints for Articulated Figures,” Masters Thesis, Simon Frasier University.

Thanks to everyone who attended. I was pretty shocked at the attendance level for the first presentation in the morning after two nights of parties 🙂

FITC Preview, Drawing Bones

Continuing the preview of my FITC Toronto presentation, bones are generally used in 3D applications to deform character meshes. For characters with segmented limbs, bones themselves may be used to draw the character. This technique is used more often for 2D characters. The current rigging classes use a Template system to draw bones. Templates are symmetric about the bone’s axis and may be uniformly or non-uniformly scaled.

For bones with an assigned Template, the control points may be connected with lines (simple point-to-point drawing) or interpolated with a cubic Bezier spline. For more information on the composite Bezier curve, read this TechNote.

The screen shots above illustrate a bone chain drawn with standard bones and a Template. In the presentation, I will give a demo showing how you may toggle back and forth between different drawing methods for the bones.

For segmented 2D characters, bones may be used as a skeleton rig and a visual representation for the character.  In a future release of the AS 3 rigging classes, the rig will be able to deform a continuous character whose outline is represented by a piecewise cubic curve.

See you in Toronto!

FITC Preview, Mixed IK and FK

Continuing the preview of my FITC Toronto presentation, the following screenshot is taken from the AS3/Flex 2-link IK demo. When IK is applied to limbs in a rig, it is generally the case that a bone chain is linked forward of the chain whose IK solution is currently sought.

The leftmost image indicates the default position of the rig, consisting of a two-bone arm chain and a Hand connector. The Hand is linked to the arm chain. The colored wedges illustrate the lower and upper rotational limits of each bone. As the target is moved, the visual representation of the second bone’s limits are updated (the root bone is oriented to the positive x-axis).

Notice that the Hand connector maintains proper orientation throughout the solution. At the end of each solution step, the Chain class invalidate() method is called. This tells the Chain instance that the position and orientation of the end effector has changed, meaning that the position and orientation of all Chains/Connectors linked forward are no longer valid. The invalidate() method makes the appropriate adjustments.

In addition to an alpha version of the AS 3 rigging classes, all Flex demos (MXML files) are provided with the code distribution for this talk. See you in Toronto!

FITC Preview – IK With Joint Limits

Continuing the preview of my FITC talk, joint limits are an important part of any IK solver. They may be implemented by modifying the math for the solution or post-solution adjustment via angle offsets. The latter approach is less elegant but conceptually simpler. I will illustrate a simple implementation for the two-bone (in-plane) solver with lower joint limits in the range [0,-pi] and upper limits in the range [0,pi]. If the root bone requires more flexibility, it is likely that it will be completely unconstrained. This is more flexibility than would probably be required in most production rigs.

The following screen shot illustrates an example where the root bone is constrained between -3*pi/5 and pi/2. The second bone is constrained between -pi/2 and 3*pi/4. Note that all constraints are relative to the parent orientation. If the root bone is not connected to any other part of a rig, its orientation is relative to the positive x-axis.

The target can not be reached with this configuration, so the solver attempts to rotate the root bone in the direction of the target, then rotate the second bone by pi to point as near as possible to the target. The root bone, however, can not be rotated beyond its upper limit of pi/2. The solver then attempts to rotate the second bone in the direction of the target, but can not exceed the upper limit of 3*pi/4, so this is as close at the solver can resolve the end effector to the target with the current joint limits.

There are more issues to discuss. It is possible to keep moving the target upwards until it crosses the negative x-axis at which point the solver ‘flips’ the orientation. The root bone points upwards and to the left, based on its lower limit. This behavior is due to the solver being ‘history independent.’ The solver has no visibility to prior solutions when attempting the current solution.

I will discuss history-independent vs. history-dependent solvers and how the ‘flip’ could be avoided. It is also the case that any feasible solution has an alternate solution. A typical solution to this particular problem causes the chain to always be oriented clockwise or counter-clockwise when there are ‘bends’ in the chain. With history-independent solvers for unconstrained problems, there is no reason to prefer one solution over the other.

In my talk, I will provide some indications where one solution might be preferred over the other in the case of joint limits. Details, details, details … it’s all in the details 🙂

See you in Toronto.

FITC Preview, Improved 2-link IK

Continuing the preview of my FITC Toronto presentation, I alluded yesterday to a hybrid algebraic/geometric algorithm for solving the in-plane, 2-link IK problem. Other solutions presented in the Flash community tend to use bones of equal length, hiding issues with infeasible solutions. The previous post illustrated one such problem from the code in the book, ‘Making Things Move.’ The following screen shot illustrates the hybrid solver with two bones of different length and a minimal-error orientation for an infeasible solution.

An additional feature of the algorithm is that it produces a solution with less computation. A typical geometric solution (i.e. MTM) involves two inverse cosines and an inverse tangent along with some supplemental computations and sin, cos operations to position the second bone. The hybrid approach requires a single inverse cosine and inverse tangent.

The computational savings are not overwhelming, but in a game engine, every cycle saved in IK is a cycle available for rendering, AI, etc. A typical bipedal character has two arms and two legs, so animating that character in a game engine generally involves solutions across multiple chains. Those savings add up 🙂

Another feature is that the second bone’s orientation relative to the parent is directly computed, making it easy to test for joint limits. In a production rig, an IK solver that does not take joint limits into account is practically worthless.

See you in Toronto.

FITC Preview, 2-link IK

Following is a continuing preview of my talk, ‘Dynamic Skeletal Animation’ to be presented at FITC Toronto.

The two-link chain is both an important starting point for general IK solutions as well as an important optimization for game engines. Many game characters can be constructed entirely from hierarchies of single or compound two-link chains.

Analytic solutions are possible for 2D rigs as there is a single degree of freedom at each joint. The two methods for solving the 2-link IK problem are algebraic and geometric. Algebraic methods work from the analytic formula for the FK problem (attempting to derive the inverse function). Geometric methods are more intuitive and treat the problem as one from plane geometry.

In the Flash community, geometric methods have been discussed in books such as ‘Making Things Move’ or at this link. Actually, the code from both of these sources is nearly identical. In ‘Making Things Move,’ Keith does a good job of illustrating dual solutions to the 2-link, in-plane IK problem and showing how to alter the code to generate each solution.

Both examples use bones with identical lengths, which is rare in production rigs. When bones are of different lengths, it is necessary to take into account all possible regions of infeasible solutions. For example, take the MTM two-link example code and replace the ‘chain link’ bones with rectangles of lengths 100 and 50. The crosshairs in the following screen shot illustrate the initial coordinates of the root bone. The square illustrates the target. Notice the wild orientation of the bones.

This is a result of invalid arguments passed to an acos() function. In addition to showing how to compensate for infeasible solutions, I hope to illustrate a hybrid algebraic/geometric solution to the two-link problem (if time allows).

See you in Toronto.