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.

FITC Preview, Simple IK

Continuing the preview of some of the topics I’ll discuss at FITC Toronto, several IK solvers will be covered. I will start with what is probably the simplest and most intuitive algorithm which was once jokingly called “Reverse Forward Kinematics” by my robotics professor in 1981. It seems RFK dates back to at least 1972, although I have been able to uncover an original attribution.

Some Flashers may recognize RFK as the algorithm discussed in the book Making Things Move. In reality, it is a variant of Cyclic Coordinate Descent [Wang and Chen, "A Combined Optimization Method for Solving the Inverse Kinematics Problem of Mechanical Manipulators," IEEE Transactions on Robotics and Automation, Vol. 7, No. 4, August 1991, pp. 489-499]. Both RFK and traditional CCD treat the IK problem as a sequence of one-bone optimizations. Start at the end of the chain and perform a one-bone correction. Begin a new IK problem with a chain having one fewer links. Repeat the process until reaching the root bone of the chain. RFK uses different targets at each step, while traditional CCD uses a fixed target. RFK requires a second forward
pass to adjust each bone to its new orientation.

At the end of one full sweep, the end-effector should be closer to the target. In a production solver, a distance metric and iteration limit are used as stopping criteria for the process.

In MTM, the iterative nature of the process is hidden inside an onEnterFrame handler that is constantly trying to resolve the chain’s end-effector towards the mouse position. The actual iterations are easier to observe by using a fixed target such as a static MovieClip. Allow the chain to move from its initial (arbitrary) orientation to the fixed MC position.

Referring to the ch14_07 example, replace the onEnterFrame handler with a fixed iteration loop.

Following is a diagram showing the chain orientation after one, four, and ten iterations. After a small fraction of a second to settle ‘close’ to the mouse position, it takes fewer and fewer iterations to resolve the end effector exactly to the mouse position (providing such a solution exists).

The next diagram was created from one of the demos I will go through step by step in the talk,

The original chain orientation is shown at the top. The orange markers are generated one at a time showing the required orientation of each bone to orient its terminal point to the (virtual) initial point of the next bone in the chain. The end bone is oriented to exactly match the target. The forward sweep (hence the RFK designtation) moves each bone to match the generated orientation keeping the root bone pinned at all iterations. This is shown in the bottom part of the diagram.

The RFK algorithm is fast compared to most IK approaches, but has very strong bias towards the latter bones in the chain. It is also highly prone to ‘kinking’ in the chain. I will discuss damping and a couple other approaches that compensate for these tendencies, producing more realistic motion from the solution.

I will also discuss analytic solutions to the classic two-link chain (which is important in many Biped rigs) and practical issues such as joint limits, effector pinning, and dealing with other chains in a rig that are linked forward of the chain whose IK solution is sought.

Hope to see you in Toronto. If you have not already purchased tickets, use the code 2112fx to obtain a 10% discount on checkout.

Joint Limits in Bone Chains

This image illustrates the application of joint rotational limits in a bone chain and across chains. In this case, a single hand connector is linked to a three-bone chain. The second bone in the chain is selected and two pie-shaped wedges illustrate the rotational limits (relative to the parent orientation) for that bone (yes, that’s where the AS 3 Wedge class comes into play). The bone is rotated towards its lower limit and is not allowed to exceed that limit as shown in the leftmost image.

Next, the third bone in the chain is selected and rotated towards, but not past its upper limit. Notice that in all cases, the motion is propagated to the next chain in the hierarchy (the hand connector). Finally, the hand connector is selected. Bones in a chain know their parents, so it’s easy to query the parent orientation. Anything connected to a chain (another chain or connector, for example) must implement the IChain interface. This interface ensures that it is always possible for the current item to query who it is linked to and obtain the parent’s orientation.

As can be seen from the diagram, it is not possible to rotate the hand connector beyond its outer limit. The implementation is general-purpose and multi-chain, so joint limits can be applied to Biped, Quadruped, and custom rigs with the same code base.

New Papervision 3D Developments

I wanted to draw attention to some recent P3D developments. The work done by Den Ivanov on terrain mapping is absolutely astounding. Check out the Musicscape demo here and then download the source. Major props to Den for releasing the source.

I’ve always liked cartoon shaders and enjoyed my work of years ago with the Swift 3D plugin for 3ds max. I might never use the plugin again after seeing the work done on the RC2 cell shader by Ralph Hauert. This is just the first attempt at the new shaders — imagine what the future might be!