http://www.andreasaristidou.com/publications/papers/FABRIK.pdf http://andreasaristidou.com/publications/papers/Extending_FABRIK_with_Model_Cοnstraints.pdf
Above are links to both the FABRIK papers.
As a brief summary, the FABRIK algorithm solves the IK problem by taking advantage of some geometry, namely, the fact that the sum lengths of 2 sides of a triangle is always greater than the third.
At each propagation step(joint position update) if we can prove that d_t' will always be less than d_t by taking advantage of the above mentioned fact, we can prove that the end effector gets closer and closer to the target.
That's a brief synopsis of the algorithm, and I am intentionally leaving out some details because the paper does a good job of explaining it, but the above is the central idea.
In section 4.1 - Multiple End Effectors. They highlight the fact that you can have two kinematic chains meeting at a joint (they call this a "sub-base") each with an end effector. For example the legs of a stickman meeting at one point(which is the sub-base) and then a line representing the torso of the stickman going up from there. In such a case, when it comes time to update the sub-base joint, there will be as many new positions for that joint as there are kinematic chains meeting there. They propose a solution where you take the centroid or average of those positions to be the new position of the sub-base.
So, it is not immediately clear to me that taking the centroid still allows both end effectors to converge towards their targets. I would appreciate any sort of explanation on the matter! Thanks in advance.
I have begun to try to prove it at least, but I haven't arrived at an answer though!
So basically, you have 2 end effectors, both trying to reach their own respective targets going through the regular FABRIK algo, when you get to the sub-base, each link meeting at the sub-base will produce a new position for the sub-base joint. And so there idea was to take the centroid of those position to be the new position of the sub-base.
I would need to explain the FABRIK algo itself in the simple case for what I'm saying to make sense, but essentially, in the simple case you prove that the end effector converges towards the target by proving that at each joint update, the distance between the current joint position and the new position for that joint, gets smaller and smaller.
let's call this distance d_t
so for the sub-base, since 2 new positions get generated for it, you have d1_t and d2_t, let's say
depiction of what I'm saying
so as an illustration. The red is the CURRENT position of the sub-base the green is the potential new position calculated by the green chain meeting at the sub-base. The blue is the potential new position calculated by the blue chain meeting at the sub-base and their respective distances portrayed by the dashed lines.
OK. now, the authors propose that we take the centroid of the green and blue joints(the potential new positions calculated by each chain)
depiction with centroid
so now I've created a joint that is the midpoint of the green and blue and a distance to that midpoint joint from the current position of the sub-base, d3_t.
now the algorithm will take that black joint to be the new position of the sub-base, and propagate further up the chain, what I mean is
depiction with joint further past sub-base
and I wont draw it, but you can imagine when we update that dark blue joint, the distance from its current position to the new position, will be less than d3_t, because we said that each time we propagate and update a joint it's d_t distance will be less than the previous!
when we get all the way to the root joint, we repeat the same sort of propagation, but this time going forward, but this same property is maintained.
So all we have to prove to ensure our initial property is maintained is that d3_t gets smaller and smaller each time we get to the sub-base during the backpropagation step, this will prove the general algorithm converges.
A triangle is formed
Look at d1_t, d2_t, and the line going from the green to the blue joint. What you find is a triangle.
Now, there's a very special triangle theorem.
Taken from this website: https://byjus.com/jee/relation-between-median-and-sides-of-a-triangle/
"A line segment that joins any vertex of the triangle and the mid-point of its opposite side is called a median."
"The sum of two sides of a triangle is greater than the median drawn from the vertex, which is common."
What does this mean?
well it means
d3_t1 < (d1_t1 + d2_t1)
I use the extra 1 at the end of variable to mean the first iteration.
during the second iteration, what do we know? we know
d1_t2 < d3_t1
d2_t2 < d3_t1
and
d3_t2 < (d1_t2 + d2_t2)
this is not enough to prove that it converges, there will be spikes in the graph, but I cannot say whether or not these spikes get smaller and smaller. Perhaps I am missing an additional constraint or there is an error in how I'm posing this. Hopefully someone can chime in!