Jan 9, 2018 2d, Algorithm, Javascript

FABRIK Algorithm (2D)

FABRIK stands for Forward-and-Backward Reaching Inverse Kinematics, and it’s a very simple, fast, and clever solution to the inverse kinematics problem.

Let’s inspect this interesting algorithm in 2D.

Problem

First of all, what is Inverse Kinematics (IK)?

Suppose you have a robotic arm with three joints, whose job is to point to a location:

Simplified Robot Arm

How do you calculate the correct angle of each joint in order to hit the target?

This seems stupid at first – we solve this problem all day long, inside our bodies, as we reach for objects and navigate the world. But there is surprising complexity in this problem.

In order to appreciate the FABRIK solution, watch the following video as different algorithms attempt to solve IK in 3D:

FABRIK Demonstration Video

Iterative Reaching

FABRIK’s solution to this problem is to iteratively reach for a target location.

Let’s start with the most basic setup.

Suppose there aren’t any joints, and you simply want a line of a fixed length to follow your mouse cursor:

Use Mouse to Pull Line

Reaching, according to FABRIK, consists of:

Given a line and a target…
Set the line’s head point to the target, stretching the line
Slide the line’s tail point along the new stretched line to fix the length

Let’s look at this visually.

Given a line and a target:

Set the line’s head to the target:

Notice that this stretches the line. We fix that by sliding the tail along the new line:

Let’s look at some code:

function reach(head, tail, tgt){
  // returns new head and tail in the format of:
  //   [new_head, new_tail]
  // where `new_head` has been moved to `tgt`

  // calculate the current length
  // (in practice, this should be calculated once and saved,
  //  not re-calculated every time `reach` is called)
  var c_dx = tail.x - head.x;
  var c_dy = tail.y - head.y;
  var c_dist = Math.sqrt(c_dx * c_dx + c_dy * c_dy);

  // calculate the stretched length
  var s_dx = tail.x - tgt.x;
  var s_dy = tail.y - tgt.y;
  var s_dist = Math.sqrt(s_dx * s_dx + s_dy * s_dy);

  // calculate how much to scale the stretched line
  var scale = c_dist / s_dist;

  // return the result
  return [
    // copy the target for the new head
    { x: tgt.x, y: tgt.y },

    // scale the new tail based on distance from target
    { x: tgt.x + s_dx * scale, y: tgt.y + s_dy * scale }
  ];
}

This should be fairly straight-forward, but there is one important property to notice:

This function always succeeds. The line will always be moved so that it touches the target.

Making it Iterative

How can we make the process iterative? I.e., instead of pulling around a single line, how can we pull along a chain of lines?

Use Mouse to Pull Chain

It’s quite ingenious:

The act of sliding the tail along the line can itself be a reach.

Think about it. We have all the ingredients.

To perform a reach, we need a line (head + tail), and a target location. Well, in a chain, the tail of one segment is the head of another segment. For each segment, we simply perform a reach with the new target, until we run out of segments – then we slide the final tail to the target:

// initialize target
var tgt = mousePosition();

// for each segment (except the last one)
for (var i = 0; i < segments.length - 1; i++){
  // perform a reach for this segment
  var r = reach(segments[i], segments[i + 1], tgt);

  // update this node
  // (`r[0]` is guaranteed to be the same point as `tgt`)
  segments[i] = r[0];

  // update the target, so the next segment's head
  // targets this segments new tail
  tgt = r[1];
}

// for the last segment, move it to the target
segments[segments.length - 1] = tgt;

Forward and Backward

We haven’t quite made a robot arm though, have we?

A robot arm doesn’t move around freely like a chain – it’s fixed at the base.

The last insight of FABRIK is that since we are guaranteed the head of the chain will always reach its target, we can perform the iterative reach in reverse to ensure that the base of the arm will always stay fixed.

Said another way:

First we perform the iterative reach like normal, so the head is guaranteed to be touching the target. Then we perform the iterative reach in reverse, so that the tail is guaranteed to be touching the base.

And that gives us an arm:

Working Robot Arm

Here’s the code:

// save the fixed base location
var base = segments[segments.length - 1];

// perform the iterative reach in the forward direction
// (same as before)
var tgt = mousePosition();
for (var i = 0; i < segments.length - 1; i++){
  var r = reach(segments[i], segments[i + 1], tgt);
  segments[i] = r[0];
  tgt = r[1];
}
segments[segments.length - 1] = tgt;

// at this point, our base has moved from its original
// location... so perform the iterative reach in reverse,
// with the target set to the initial base location
tgt = base;
for (var i = segments.length - 1; i > 0; i--){
  var r = reach(segments[i], segments[i - 1], tgt);
  segments[i] = r[0];
  tgt = r[1];
}
segments[0] = tgt;

Conclusion

It’s quite amazing that such a simple concept – a stretched reach – has turned into solving the complex and puzzling inverse kinematics problem.

There are a lot of ways to extend this algorithm too.

Moving into 3D complicates it because orientation of the segments matter, but by tweaking the reach function, it can be made to work.

Adding constraints like fixed range of motion over a joint is possible too, but requires thought about where to enforce the constraints during the iterative process.

Moving objects other than lines is possible too (i.e., rigid triangles), if you can break down the objects into lines, and traverse the heirarchy correctly while iterating.

The important part is understanding the core idea, which I hope is clear now. Go forth, experiment, and have fun!