next »

[Evan Balster]

Hello, all.

I've got a peculiar little problem in a system I'm writing which models the morphology, positioning and behavior of a kinematic body in three-dimensional space.

I have a Skeleton, composed of Bones which are connected with Joints.  A Bone contains details on mass distribution, and a Joint defines the range of possible relative positions for two conjoined Bones.  A Skeleton is an assembly of Bones and Joints which defines the rough physical morphology of a creature.

I have a separate object called Posture which models a body's positioning.  It is composed of Parts, which cache temporary data and expose algorithms useful in IK solving, and Bends (for lack of a better term) which model the state of a Joint's degrees of freedom.

This separated model/state scheme has some pleasant advantages and some woeful problems which I will list:

Advantages:
- Pure prototyping:  Skeleton is stateless and doesn't require a "resting" position.
- Non-redundancy:  I can have multiple Postures in existence for the same Skeleton, without duplicating data.  This is useful for predictive motion planning.

Disadvantages:
- Structural dependency:  The Skeleton cannot be structurally changed while a Posture exists which is based on it.  By the same token a serialized Posture will be dependent upon a compatible skeleton when deserialized.
- Awkward naming:  An issue which is often symptomatic of an underlying problem in data representation.  "Part" is a vague alias for a Bone, and "Bend" a vague alias for a Joint.

I'm a bit bothered by all this, and I'm inclined to weigh the upsides and downsides of this scheme, Model and State, versus Unified and Prototype and Object models.  In the second, I would merge Skeleton/Bone/Joint with Posture/Part/Bend, doing away with the separation.  In the last, I would keep the original Skeleton and use the Unified object type to represent state, retaining separation and ensuring integrity at the cost of redundancy.

I could program my system using any of these approaches and it would do its job.  But it's an interesting philosophical problem, and lately I've found myself in search of elegant solutions to the practical challenges I encounter in programming.  So I'm interested in a few opinions from my esteemed colleagues here. 

[ThemsAllTook]

I've developed a habit of separating these things, too. It takes a bit more work up front to get it right, but ultimately the rewards are totally worth it.

- Structural dependency:  The Skeleton cannot be structurally changed while a Posture exists which is based on it.  By the same token a serialized Posture will be dependent upon a compatible skeleton when deserialized.

Seems to me like this should be solvable. Is the Posture object replicating some of the structural data from Skeleton which could be avoided? What causes a Posture to become invalid when the Skeleton is changed? Serialization could get a bit tricky, but it should be workable to, say, have your Posture refer symbolically to the parts of the Skeleton it affects. If a Posture stores orientations bone1 and bone2, and is then applied to a Skeleton that contains only bone1 and bone3, the bone2 Part would have no effect, and bone3 would remain in the identity orientation.

- Awkward naming:  An issue which is often symptomatic of an underlying problem in data representation.  "Part" is a vague alias for a Bone, and "Bend" a vague alias for a Joint.

My naming conventions for this would go something like SkeletonModel, BoneModel, JointModel, SkeletonStateModel, BoneStateModel, and JointStateModel. Can still get awkward in places, but it might be a bit more straightforward than looking for loose synonyms.

[Evan Balster]

I try to avoid long names where I can.  Hrmmmm.

So the structural dependency right now is a result of the Parts/Bends having the same tree-structure as the Bones/Joints, and referring to those Bones and Joints by pointers.  A simpler mapping where the Posture object stores all data within itself would destroy some useful abstractions I use for caching absolute locations and grouping degrees of freedom by joint.

Switching to a looser mapping (sans pointers) where missing and deleted posture parameters would behave like that would have some clear benefits, but could be a bit challenging with the current tree-structure, hrm.  The use-case is when editing the skeleton in a body-maker tool.

[ThemsAllTook]

So the structural dependency right now is a result of the Parts/Bends having the same tree-structure as the Bones/Joints, and referring to those Bones and Joints by pointers.  A simpler mapping where the Posture object stores all data within itself would destroy some useful abstractions I use for caching absolute locations and grouping degrees of freedom by joint.

That's what I figured. Hmm, maybe you could do both? Skeletons would be hierarchical, Postures would refer to them symbolically, and a PostureCache could be used to do both at runtime if there's some structural or performance benefit. Your Posture could potentially be updated from PostureCache, and the PostureCache would be rebuilt if the Skeleton structure ever changed. This might be getting overly complicated, though...

[BleakProspects]

In robotics, we refer to the state of a kinematic body as its "configuration". Technically, configurations are separated from the kinematic structure of the body, but the kinematic structure implies the existence of what's called the "configuration space" of the body (ie, the set of all valid configurations). For most robotics applications, a configuration is just an indexed vector where each index is a degree of freedom. This allows us to do very fast operations over thousands upon thousands of configurations. Typically, a robotics package will have a seperate "kinematic model" of the robot, and this model has something along the lines of a "SetConfig(vector)" function which sets the configuration of the model.

If you lose joints or change joint limits, obviously the configuration space becomes totally invalid, and you would need to modify your representation.

What I see you doing here is just inventing a (rather bloated) book-keeping system on top of configurations to make it easier to create a new configuration space every time the robot is changed. This is fine, but you're going to have a ridiculous amount of overhead. What parts of the configuration of a kinematic body can you not represent simply as an indexed vector? What sorts of operations does this extra structure give you that you couldn't get through an indexed vector?

[Evan Balster]

For whatever relevance it might have, I'm doing this for animation rather than robotics.

The Posture (configuration) lists degree-of-freedom values for each joint, which are implemented as objects (bends) that provide some information on their relevance in the least-squares solver.  (I use virtual functions and type-checking to compute the function values and jacobians)  It also contains a listing of objects (parts) which cache useful information (absolute positions) which saves CPU time during those operations.

Using a vector would definitely reduce construction and copy overhead for these objects, though.  The tree structure has been a pain.  And since structural change to the skeleton is uncommon I could implement an expensive operation to "transplant" relevant posture data from one structural version of a skeleton to the next.

Hmmmm....

[BleakProspects]

For whatever relevance it might have, I'm doing this for animation rather than robotics.

Right, I can see why you might have different needs. In robotics we often need very very fast calculations running in 500hz control loops to get things moving. Or else we need to test 1000 IKs for some objective function. In animation you don't have those needs, as at most you'd need to run things at 60hz and do 1 or 10 IKs. Though I should mention that robotics and graphics have a lot in common -- the literature is full of re-implementations of old algorithms in the other field.

The Posture (configuration) lists degree-of-freedom values for each joint, which are implemented as objects (bends) that provide some information on their relevance in the least-squares solver.

Why is this information stored in the "posture" rather than the kinematic object?

(I use virtual functions and type-checking to compute the function values and jacobians)

Okay, that is one way to do it without a lot of programming hassle. In my lab we just store the type of joint as an enum, and typically there are only two (revolute and prismatic) for speed. Ball and socket is just 3 revolute. Other joints can be represented as combinations of several revolute/prismatic joints.

 It also contains a listing of objects (parts) which cache useful information (absolute positions) which saves CPU time during those operations.

I see. So your use case is to do some kind of metric over a whole bunch of different poses? FK isn't a *huge* part of processing time, but I can see why that would be useful. In our implementation, "SetConfig" of the kinematic object caches all the forward kinematics stuff for later use in the kinematic object, but we lose that data when we call "SetConfig" again with a different configuration.

Using a vector would definitely reduce construction and copy overhead for these objects, though.  The tree structure has been a pain.  And since structural change to the skeleton is uncommon I could implement an expensive operation to "transplant" relevant posture data from one structural version of a skeleton to the next.

So using a vector also makes it very natural to just apply global operations to the entire pose very easily. For instance, cartesian velocity control, torque control, planning, interpolation, joint control -- all of that becomes trivial when you can just say (in pseudocode):

Code:

Config currentConfig = Body.GetConfig();
Vector3D endVelocity = GetDesiredEndVelocity();
Matrix Jacobian = Body.ComputeEndJacobian(currentConfig);
Config jointSpeed = Jacobian.PseudoInverse() * endVelocity;
Body.SetJointVelocity(jointSpeed);

Of course, you could accomplish the same thing by just making your own operators and functions over "Bends" or whatever, but it's much more natural for me to think of things in terms of vector spaces than as arbitrary values applied to some kinematic tree.

[Evan Balster]

I like keeping the kinematic object separate from state data because it's useful to be able to store different configurations of that object.  As an example I might want multiple instances of a body in action, or I might want to compute hypothetical positions as part of a planning algorithm.

The heavy computations are for complex optimization functions which take many degrees of freedom as inputs.  These are used in an iterative least-squares algorithm and I need to be able to quickly compute the values and the many partial derivatives of functions of bone positions/orientations, which means evaluating the effect of every relevant degree of freedom.  Thus far I've implemented logic for optimizing mass-displacement (a weird metric nobody else seems to use) and minimizing distance between two end effectors, one of which might be in worldspace.

The partial derivative of "touch my hands together", for instance, is computed by evaluating the kinematic chain from one hand to the other and computing how one moves from the other's perspective for each degree that could possibly be adjusted.  I then find the dot product of the jacobian's translation-delta and the position of the second hand in the first's transform space; this produces the partial derivative of the latter's magnitude for a positive change to that degree's scalar value.

[BleakProspects]

I like keeping the kinematic object separate from state data because it's useful to be able to store different configurations of that object.

Yes, I can see how that would be useful.

The heavy computations are for complex optimization functions which take many degrees of freedom as inputs.  These are used in an iterative least-squares algorithm and I need to be able to quickly compute the values and the many partial derivatives of functions of bone positions/orientations, which means evaluating the effect of every relevant degree of freedom.  Thus far I've implemented logic for optimizing mass-displacement (a weird metric nobody else seems to use) and minimizing distance between two end effectors, one of which might be in worldspace.

Interesting. So you're computing these partial derivatives via finite differencing and performing nonlinear optimization via ILS? Sounds very familiar...

The partial derivative of "touch my hands together", for instance, is computed by evaluating the kinematic chain from one hand to the other and computing how one moves from the other's perspective for each degree that could possibly be adjusted.  I then find the dot product of the jacobian's translation-delta and the position of the second hand in the first's transform space; this produces the partial derivative of the latter's magnitude for a positive change to that degree's scalar value.

Okay, perhaps I'm being ignorant here, but couldn't you just do this iteratively in a control loop where you just compute workspace deltas between the end effectors for each kinematic chain alone, and then do Jacobian pseudo-inverse on each one? Do you need to optimize the entire body at once?

[Evan Balster]

I'm evaluating the jacobians, not approximating them.  When variables' effects are considered in isolation they produce a translational and rotational "velocity" I can evaluate.

Full-body solving, as I understand, is more effective than adjusting one segment at a time.  The latter technique is called cyclic coordinate descent and often requires multiple traversals of the complete kinematic chain.  It's poorly-suited to dealing with multiple goals, and it also gets characteristically "jittery".  My intention is to use my system to approximate physics integrations, among other things, so jitter is bad.

The involved matrix math (pseudo-inverses and such) are left to an opensource levenberg-marquardt algorithm I've wrapped in a little C++ systems solver library that facilitates the polymorphic behaviors and caching tricks I've mentioned.


But anyway.  I'm having some good thoughts.  This conversation has been stimulating so far, and my ears are open to any criticisms of this scheme...

[raigan]

(hi Evan!)

"evaluating the effect of every relevant degree of freedom"

This description definitely sounds like using finite-differences to calculate the jacobians, but correct me if I'm wrong: you have some objective function, you displace one of the degrees of freedom and measure the change in the objective function to "infer" what the jacobian of that degree of freedom is.

This approach can be considered a (numerical) approximation of the true jacobians since you're not calculating them directly/symbolically (i.e you don't have an explicit formula for the jacobian which you evaluate at the current system state).

This approach is the best I know of for ease-of-implementation (nothing is more annoying that trying to track down a typo or bug in your jacobian derivation or code) but it can be sensitive to e.g how big of a displacement you use to measure the change (and AFAICR there are algorithms/papers/etc. concerning different approaches to refining and adapting the size of the displacement in order to get a better approximation of the jacobian. The other downside is that it requires many evaluations of the objective function (i.e you have to recalculate a lot of transforms).

Of course, given how horrible the jacobians can be for even simple 2d constraints (4 degrees of freedom), finite differences might be the best approach for this problem in order to preserve programmer sanity

If you're not actually using what I'm describing above, it would be great to hear a more detailed description of your actual process since it sounds really interesting!

Actually I'd like to hear more either way, since this is something I've dabbled in (admittedly in a simpler 2d context).

Your talk of caching makes me think of Featherstone; I've honestly never managed to wrap my head around his generalized/reduced coordinates, but the idea (AFAIK) is that you can determine how parent and children's jacobians interact so that instead of having to fully recompute everything (calculating each jacobian in isolation), you can descend down the tree propagating the effect of parent on child and then ascend accumulating the effect of children on parents to calculate all the jacobians together. I might be way off on this though!

http://en.wikipedia.org/wiki/Featherstone's_algorithm
http://www.cimat.mx/~cesteves/cursos/animation/pdf/Featherstone_Orin.pdf
http://www.cs.ucla.edu/~forswg/files/sca10_si.pdf

[Evan Balster]

(Hi, Raigan!  Hit me up on Skype.)

I've been computing the jacobians directly rather than approximating them because I am a crazy person and don't want to bother with all the issues that can arise from numerical derivation.

Most jacobians in my IK system can be computed based on the derivative of a part's position relative to another part, with the variable being some degree of freedom.  I call this the "swing" and it is expressed as a "delta" consisting of a translation vector and a rotation vector as per our earlier conversation about orientations vs. rotations.

I haven't really looked into featherstone's algorithm, and the optimizations I mention are (1) a "relevance" matrix that identifies what jacobians are always zero and (2) caching logic for groups of variables that allows them to store useful data each time the system is adjusted, for cheaper computation of jacobians and objective functions.  In the case of IK I cache the absolute location and orientation of each Part.  This makes it so I don't have to do a transform tree traversal for every value computed, reducing those operations to constant time.

Proooobably gonna write up a blogpost about this stuff at some point as nobody else seems to be using SORA vectors in this way.

[gimymblert]

This thread looks to me so hi level it read like science fiction, following in case I learn something. I'm sure it's more simple that it sound, but i'm ignorant of most terms that fly and the stakes.

[Evan Balster]

I might write some articles in the future that serve as an introduction to all this stuff.  It's one of the first places in game programming where high-level mathematics are an absolute necessity, and it's made me handle math more intelligently elsewhere.

[raigan]

A blog post would be great! I'm especially interested in how you can avoid traversing the tree to update transforms.. actually all of that caching stuff sounds interesting

(I'm a bit skype-shy...)

[_Tommo_]

Thus far I've implemented logic for optimizing mass-displacement (a weird metric nobody else seems to use) and minimizing distance between two end effectors, one of which might be in worldspace.

This sounds like a problem I tried to solve...
I wanted to "guess" which position could an hand take given only the positions of the finger tips, but standard solvers (CCD, etc) result in very awkward poses for a real hand.
So, I used a "joint stress metric" that computes the cost of a pose as the the sum of the squares of each joint angle offset from the rest position, and it worked nicely
However I was unable to fit it into a CCD algorithm (not that good at maths) so I used an hashmap and tons of duct tape
How did you integrate a metric into the standard algorithms?

[Evan Balster]

I'm using least-squares solving, and it's painfully obvious you're also in possession of a Leap devkit, haha.  Multivariable optimization is definitely the easiest way to deal with a set of "loose" constraints like that.

I might just release my IK solver for the heck of it when I write an article about it.

[gimymblert]

I might write some articles in the future that serve as an introduction to all this stuff.  It's one of the first places in game programming where high-level mathematics are an absolute necessity, and it's made me handle math more intelligently elsewhere.

Oh cool thanks

[_Tommo_]

I'm using least-squares solving, and it's painfully obvious you're also in possession of a Leap devkit, haha.  Multivariable optimization is definitely the easiest way to deal with a set of "loose" constraints like that.

I might just release my IK solver for the heck of it when I write an article about it.

Yeah, I couldn't really wait for them to implement the same stuff :D
The article would be really interesting to read, even if I'm moving to Kinect, the algorithm could be adapted...
I'm thinking of switching because you can't still read point cloud data from the Leap, and the palm information is wildly incorrect when you rotate the hand, so there isn't enough data to always guess the hand position.
ie. when you do some complex movement like grabbing a virtual something and then flipping your hand from downward to upward to look better at it, you lose too many tips to follow the movement.

a little IT: even if I ended up not using real IKs, I used a model/state architecture similar to the one BleakProspects proposed: a skeleton has a setPose() method which takes a Pose object, that is a simple <DOF index, angle> map wrapper.

PS: do you solve the IK for all the hand at once, or per-finger? I didn't find any good resource that explained how to solve multiple effectors at once, so I did the latter, even if the former should be much more accurate.

[Evan Balster]

Least-squares systems solvers deal with all the variables they're given at once.  If the different variables being solved for have functions that they all affect, this technique has some very strong advantages.