Inverse kinematics

Introduction

Inverse kinematics (IK) is a very powerful tool in game development. Its origins come from Robotics, but it’s found a place in many computer and science fields. The basic concept behind IK, which we’ll go over in more depth later, is to calculate positions for a joint system so that it will reach a certain end goal. This has immense use in things such as animation, body rigging, and so forth.

There are many ways to calculate inverse kinematics, but in order to keep things simple, this article focuses on a method known as FABRIK because it's relatively easy to use and implement compared to other IK methods.

Prerequisites

  • Vector math is a must!
  • Dot product is used extensively for constraints

Forward Kinematics

Before we start talking about inverse kinematics, it’s first important that we define forward kinematics (FK). The good news is that FK is pretty simple and intuitive to get a basic understanding of. Let’s use an example of a robot arm. If I have some starting point (for example, the equivalent of your shoulder on your arm), the length of all the parts on the robot, and the angles between those parts, then I should be able to calculate the end position with some mathematical function.

InverseKinematics1.png

For our purposes knowing the exact mathematical formula doesn’t really matter. What matters is that we understand that given the right information and a start point we can calculate the end effector of our joint system with some equation and we call this "forward kinematics".

Inverse Kinematics

Inverse kinematics on the other hand isn’t a focus on getting the end effector, rather it’s about having the end effector and finding a configuration for the joint system so that it will reach said end effector from the origin.

InverseKinematics2.png

As it turns out, this can be quite difficult and resource intensive. Furthermore, most explanations regarding inverse kinematics are filled with Robotics jargon which may make it somewhat difficult for the average user to pick up.

FABRIK

For the rest of this article we're going to focus on learning how we can use a method (FABRIK) to solve inverse kinematic problems.

Forward And Backward Reaching inverse kinematics (FABRIK) is an IK method that seems to be the easiest not only to understand, but also to implement. It supports systems with multiple targets for different chains and is relatively low cost resource wise because it's heuristic. What’s important to realize about most multi-joint inverse kinematic problems is that they’re usually heuristic solutions, meaning they’re practical methods, but they might not give a 100% perfect answer, rather they give a very good guess. This is okay for our case because if the position is off by a few decimals worth of units it’s not going to make a huge difference visually.

The concept behind FABRIK relies on using the previous position of the joints to create a problem where you simply have to find a point on a line as opposed to going through complex math to find angle rotations. This of course allows you to cut out a lot of tough math and keep everything relatively simple (minus constraints).

Analysis of the algorithm

To start off let’s define our situation with a picture:

InverseKinematics3.png

From said picture we can assume we have a few pieces of input. We have the position of each joint (P1, P2, P3 ...) we have the lengths between each joint (d1, d2 ...) and we have a target (our goal for the end effector). We can also assume that P1 is the origin and does not move. Realistically we can do IK without the distances pre-defined because we can just get the initial distances between the joints via vector subtraction and use that. So with all that covered here's our class

-- table sum function
function sum(t)
	local s = 0;
	for _, value in ipairs(t) do
		s = s + value;
	end;
	return s;
end;
 
-- FABRIK chain class
local chain = {};
 
function chain.new(joints, target)
	local self = setmetatable({}, {__index = chain});
 
	-- get the distances between the joints
	local lengths = {};
	for i = 1, #joints - 1 do
		lengths[i] = (joints[i] - joints[i+1]).magnitude;
	end;	
 
	self.n = #joints;
	self.tolerance = 0.1; -- heuristic method so this is our error margin
	self.target = target; -- goal for the end effector
	self.joints = joints;
	self.lengths = lengths;
	self.origin = CFrame.new(joints[1]);
	self.totallength = sum(lengths);
 
	-- rotation constraints (covered below)
	self.constrained = false;
	self.left = math.rad(89);
	self.right = math.rad(89);
	self.up = math.rad(89);
	self.down = math.rad(89);
 
	return self;
end;


Now that we've got some inputs we can work with the first step towards solving our system of joints for IK is going to be to see if our target is reachable! This is a pretty simple test. If the distance between the start and target is greater than the length of all our distances combined we know the target is unreachable. As such we know the closest point to our target is achieved by fully elongating our system.

function chain:solve()
	local distance = (self.joints[1] - self.target).magnitude;
	if distance > self.totallength then
		-- target is out of reach
		for i = 1, self.n - 1 do
			-- create direct line to target and travel join distance across it
			local r = (self.target - self.joints[i]).magnitude;
			local l = self.lengths[i] / r;
			-- find new joint position
			self.joints[i+1] = (1 - l) * self.joints[i] + l * self.target;
		end;
	end;
end;


That was simple enough, but I think most people could figure that out with a few minutes of focus on the problem. The real difficultly lies within how we solve if the target is reachable? This is where FABRIK comes into play.

FABRIK has two stages to a single iteration. The first stage takes a best guess at where each joint should be by first setting the end position at the target and then working backwards to the beginning. The process of working backwards is done by finding the line between the most recently updated point and the next point backwards in the chain and then moving along that line by the respective fixed distance between those two joints. The process looks like this:

InverseKinematics5.png

As you may have already noticed from the above picture that when we do this calculation we’re left with a gap between the start and our new calculated position. That’s not good at all! As such we’re going to perform the same operation, but this time we’re going to do it by setting ONLY P1 back to the original start and now working forward up the chain.

InverseKinematics6.png

Once again you can see that we’re not quite at the target, but if you scroll back up and look at the difference between the original P4 and where it is after a full iteration, you’ll notice it is way closer! If we keep running this FABRIK iteration we’ll get closer and closer to having our system solved.

The question now is when do we stop solving? One might naively say when P4 is perfectly aligned with the target. However, if you remember I mentioned this is a heuristic solution and since that’s the case we can expect some margin of error. So instead of being perfect we’ll just stop running iterations once P4 gets within a certain range (margin of error). However if for whatever reason FABRIK can’t get to the solution within a few iterations we want to stop trying to solve else we freeze our computer.

This is our final code for our basic solver:

function chain:backward()
	-- backward reaching; set end effector as target
	self.joints[self.n] = self.target;
	for i = self.n - 1, 1, -1 do
		local r = (self.joints[i+1] - self.joints[i]);
		local l = self.lengths[i] / r.magnitude;
		-- find new joint position
		local pos = (1 - l) * self.joints[i+1] + l * self.joints[i];
		self.joints[i] = pos;
	end;
end;
 
function chain:forward()
	-- forward reaching; set root at initial position
	self.joints[1] = self.origin.p;
	for i = 1, self.n - 1 do
		local r = (self.joints[i+1] - self.joints[i]);
		local l = self.lengths[i] / r.magnitude;
		-- find new joint position
		local pos = (1 - l) * self.joints[i] + l * self.joints[i+1];
		self.joints[i+1] = pos;
	end;
end;
 
function chain:solve()
	local distance = (self.joints[1] - self.target).magnitude;
	if distance > self.totallength then
		-- target is out of reach
		for i = 1, self.n - 1 do
			local r = (self.target - self.joints[i]).magnitude;
			local l = self.lengths[i] / r;
			-- find new joint position
			self.joints[i+1] = (1 - l) * self.joints[i] + l * self.target;
		end;
	else
		-- target is in reach
		local bcount = 0;
		local dif = (self.joints[self.n] - self.target).magnitude;
		while dif > self.tolerance do -- check if within error margin
			self:backward();
			self:forward();
			dif = (self.joints[self.n] - self.target).magnitude;
			-- break if it's taking too long so the game doesn't freeze
			bcount = bcount + 1;
			if bcount > 10 then break; end;
		end;
	end;
end;


Multiple end effectors

Alright, we built a simple IK system, surprisingly wasn’t that hard, was it? The problem with our algorithm in its current form is that it’s still very limited regarding what it can represent. As is we can only handle chains with only one end, but that’s not very useful if we want to represent things like hands or bodies, or most things in real life that are connected to multiple things. Luckily for us changing our algorithm to support having multiple targets is a pretty smooth process. We just need to take a few extra things into account.

The first thing we will need is knowledge of what we’ll call “sub-bases”. Simply put these are any point that acts as a fork in the road of our chain:

InverseKinematics8.png

In order to run our algorithm with multiple targets we need to know which points are sub bases, which are end points, and so forth. This shouldn’t be a big deal, it’s not really requiring much more information that you already knew; you just need to better organize things.

Once we have the sub-bases the algorithm works as follows. We have two stages. The first stage has us iterate through the sub-bases that are the closest linked to end effectors. We START from the end effectors and solve inwards to their respective closest linked sub-base. If we have multiple end effectors connected to a single sub-base this will leave us with multiple points for the sub base. We take all those points and get the centroid between them. That is our new sub-base position. If that sub-base is connected to another sub-base we repeat the process mentioned above. If the sub-base is connected to the start we solve from the sub-base to the start. In the second stage we use simply solve forward from the start and treating any branch offs at sub-bases as individual chains! That’s it!

We aren't really adding anything to our inverse kinematic solver's process, we're simply using it slightly differently. Here's an example of it in use:

local ik = require(game.Workspace.FABRIK);
 
local start = game.Workspace.Start;
local subb = game.Workspace.SubBase;
local finish1 = game.Workspace.Finish1;
local finish2 = game.Workspace.Finish2;
 
-- build our chains
local A = buildChain(start.Position, subb.Position, 5);
local chainA = ik.new(A, subb.Position);
local A1 = buildChain(subb.Position, finish1.Position, 5);
local chainA1 = ik.new(A1, finish1.Position);
local A2 = buildChain(subb.Position, finish1.Position, 5);
local chainA2 = ik.new(A2, finish2.Position);
 
function update()
	-- update the targets
	chainA.origin = CFrame.new(start.Position);
	chainA.joints[1] = start.Position;
	chainA1.target = finish1.Position;
	chainA2.target = finish2.Position;
 
	-- work backwards to the subb
	chainA1:backward();
	chainA2:backward();
 
	-- get the centroid, set as next part of chain's target and solve 
	-- (we're going backwards, then forwards by using solve for chainA)
	local centroid = (chainA1.joints[1] + chainA2.joints[2])/2;
	chainA.target = centroid;
	chainA:solve();
 
	-- set origins to end of chainA
	chainA1.origin = CFrame.new(chainA.joints[chainA.n]);
	chainA2.origin = CFrame.new(chainA.joints[chainA.n]);
 
	-- now we're working forwards for the things we previously went backwards on
	chainA1:forward();
	chainA2:forward();
 
	-- from here you'd draw the chain...
end
 
game:GetService("RunService").RenderStepped:connect(function()
	update();
end);

Joint constraints

Alright, if there was a time in this article where things are going to get mathematically hairy, this is going to be it! FABRIK is a documented way to do inverse kinematics, meaning everything in this article so far is based off of descriptions of the algorithm you can easily find by searching. What is not as easy to find is a good description or example of constraints. As such this constraint method was an attempt at piecing together the broad explanations of FABRIK's constraint method and what's being explained here is the solution discovered.

Constraints in an IK system are essentially rules that joints have to follow. In our current IK system so far our joint system has been free to move in whichever way it wants. This might be useful in some cases, but you also might want to represent something more ridged like an elbow or hand where some joints can’t bend backwards in. In this section we'll go over a way that you can constrain the angle at which joints bend and in what direction.

The basic idea behind this constraint method is to take a 3D problem, convert it into a 2D problem, solve the 2D problem, and then bring it back into 3D space. Unfortunately this is a bit of a mathematical process, but hopefully we can push through it.

First, let’s start with visualizing the 3D problem on a simple chain. At every joint we are going to define the constraint by a cone. This cone will be used to represent the range of movement in multiple directions. Once we have found a way that can properly and accurately represent said cone we are going to calculate our system like normal. If the proposed solution is inside the cone’s range of movement then we don’t need to change anything. If the solution is outside of the cone’s range of movement we know we need to adjust.

InverseKinematics10.png

Now we may want our constraints to favour different directions of movement. So instead of defining a cone that has an equal radius all the way around it's base we are going to define our cone by four separate angles so that we can create a wide variety of ellipse type shapes to define our range of movement. Take note we can also use these angles in addition to some height to get the different distances to the edge of a cross section of the cone. This will come into play later.

InverseKinematics11.png

Now that we have our cone defined we can now focus on making this a two dimensional problem as opposed to a 3D one. Our first step is going to be defining what is up and what is down. To do this we’re going to build a matrix with the CFrame.new constructor. The matrix will represent the rotation facing direction between the two previous points.

local cf = CFrame.new(joint[i], joint[i+1]);


We can then use vectorToWorldSpace on that cframe to get the up, down, left, right, etc. vectors relative to its rotation. We are going to pick two vectors which we will use to build our axis (which will use to make things 2D). We want a vector going up or down and left or right. The key word there is “or”. We need to be specific which one we pick otherwise out of bound vectors might get flipped. The way we will pick our two vectors is by comparing the up against the down and the left against the right to see which is closer to our unchanged calculated point.

local ups = {cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Top)), cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Bottom))};
local rights = {cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Right)),  cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Left))};
table.sort(ups, function(a, b) return (a - calc).magnitude < (b - calc).magnitude end);
table.sort(rights, function(a, b) return (a - calc).magnitude < (b - calc).magnitude end);
 
local upvec = ups[1];
local rightvec = rights[1];


InverseKinematics12.png

Once we have those points we need to find out how to get our calculated point and our cone onto the 2D plane. The way we’re going to do this is by projecting the calculated point onto the cone’s center axis to find the shared height. We’re then going to get that projection in a vector form and subtract it from the calculated vector to get a vector that is on the same plane as the axis vectors we calculated above. From there we can project the point onto both axis to get a 2D point on a 2D plane. Next we’ll use the height we found earlier to get a cross section of our cone (using tan and the angle) that we can also use on our 2D plane. This might seem a bit confusing, and that’s partially because it is, but it’s also not exactly simple math.

function chain:constrain(calc, line, cf)
	local scalar = calc:Dot(line) / line.magnitude;
	local proj = scalar * line.unit;
 
	-- get the vector from the projection to the calculated vector
	local adjust = calc - proj;
 
	-- get the 2D components
	local xaspect = adjust:Dot(rightvec);
	local yaspect = adjust:Dot(upvec);
 
	-- get the cross section of the cone
	local left = -(proj.magnitude * math.tan(self.left));
	local right = proj.magnitude * math.tan(self.right);
	local up = proj.magnitude * math.tan(self.up);
	local down = -(proj.magnitude * math.tan(self.down));
 
	-- find the quadrant
	local xbound = xaspect >= 0 and right or left;
	local ybound = yaspect >= 0 and up or down;
 
	local f = calc;
	-- check if in 2D point lies in the ellipse 
	local ellipse = xaspect^2/xbound^2 + yaspect^2/ybound^2;
	local inbounds = ellipse <= 1;
 
	if not inbounds then
		-- ???
	end;
 
	-- return our final vector
	return f;
end;


InverseKinematics13.png

Now that we’ve converted everything into 2D our problem looks something like this visually:

InverseKinematics14.png

That looks a lot more reasonable doesn’t it? I’ve included two points (green and red) to show two possible outcomes. If we have a situation where our point is inside the ellipse (green) then we don’t need to adjust anything the calculation already abides by the constraint. If however we have a situation where the point is outside the ellipse (red) then we need to translate the point to the nearest point on the edge of the ellipse. One final thing, the above image uses a perfect ellipse, however that’s not always going to be the case based on the angles you choose to define the cone. In order to do the math below we need a perfect ellipse so what we’re going to do is find out what quadrant the point is in then use the two nearest points on both axis to create a perfect ellipse. This may change the shape as a whole, but it doesn’t matter because it retains the shape in the quadrant we’re going to get our calculations from.

To find out if we’re inside our ellipse we can use this simple equation (where x and y are the point’s coordinates):

InverseKinematics15.png

If the inequality is satisfied then we know we’re inside the ellipse, otherwise we’re outside. That’s simple enough, but how do find the closest point along the ellipse if the above isn’t satisfied?

The answer is to get the angle between our point and the origin of the plane (0, 0). We can easily get this by using math.atan2. Once we have that angle we can easily find any point on the ellipse by inputting said angle into the following equation which simply gives traces the shape:

InverseKinematics16.png

Awesome we’ve got a way to calculate our fixed 2D point. Now the last thing we need to do is convert it back to 3D. Luckily for use this isn’t too bad because the x and y axis on our 2D plane represent two 3D vectors we already have. As such we just multiply the respective component to the respective 3D vector and add everything together. We also have to remember that the point we converted to 2D was relative to the projection and as such we need to add everything on top of that. Finally, we want to take that vector, normalize it, and then multiply it by the fixed length between our two joints to retain proper distance.

if not inbounds then
	-- get the angle of our out of ellipse point
	local a = math.atan2(yaspect, xaspect);
	-- find nearest point
	local x = xbound * math.cos(a);
	local y = ybound * math.sin(a);
	-- convert back to 3D
	f = (proj + rightvec * x + upvec * y).unit * calc.magnitude;
end;

Wow, that was a lot and for the most part the above works well, but there’s still one thing we didn’t take into account. What if the calculated vector and the cone vector have an angle difference greater than 90 degrees? If we start to draw it out we’ll notice right away that we are going to get a negative projection scalar on our cone vector which is going to mess up our above solution. As such we’re going to check if the scalar is negative and if it is we’re simply going to flip the projection vector and force the above algorithm to solve for the nearest point whether the calculated vector is technically in the ellipse or not.

InverseKinematics17.png

Our fixed code form:

function chain:constrain(calc, line, cf)
	local scalar = calc:Dot(line) / line.magnitude;
	local proj = scalar * line.unit;
 
	-- get axis that are closest
	local ups = {cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Top)), cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Bottom))};
	local rights = {cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Right)),  cf:vectorToWorldSpace(Vector3.FromNormalId(Enum.NormalId.Left))};
	table.sort(ups, function(a, b) return (a - calc).magnitude < (b - calc).magnitude end);
	table.sort(rights, function(a, b) return (a - calc).magnitude < (b - calc).magnitude end);
 
	local upvec = ups[1];
	local rightvec = rights[1];
 
	-- get the vector from the projection to the calculated vector
	local adjust = calc - proj;
	if scalar < 0 then
		-- if we're below the cone flip the projection vector
		proj = -proj;
	end;
 
	-- get the 2D components
	local xaspect = adjust:Dot(rightvec);
	local yaspect = adjust:Dot(upvec);
 
	-- get the cross section of the cone
	local left = -(proj.magnitude * math.tan(self.left));
	local right = proj.magnitude * math.tan(self.right);
	local up = proj.magnitude * math.tan(self.up);
	local down = -(proj.magnitude * math.tan(self.down));
 
	-- find the quadrant
	local xbound = xaspect >= 0 and right or left;
	local ybound = yaspect >= 0 and up or down;
 
	local f = calc;
	-- check if in 2D point lies in the ellipse 
	local ellipse = xaspect^2/xbound^2 + yaspect^2/ybound^2;
	local inbounds = ellipse <= 1 and scalar >= 0;
 
	if not inbounds then
		-- get the angle of our out of ellipse point
		local a = math.atan2(yaspect, xaspect);
		-- find nearest point
		local x = xbound * math.cos(a);
		local y = ybound * math.sin(a);
		-- convert back to 3D
		f = (proj + rightvec * x + upvec * y).unit * calc.magnitude;
	end;
 
	-- return our final vector
	return f;
end;


That’s it! If we put that all together we have a constraint system. We simply run our constraint during our forward cycle. Just keep in mind that when constraining points there might not always be a solution even though the target is in reach. As such this method will try to get as close as it can.

Conclusion

Hopefully this article has given you a good idea of how you can use IK in your own games. Good luck and here's a place file you can use as a reference:

https://www.roblox.com/games/405964460/FABRIKIKs-Place