Introduction
Inverse kinematics refers to the process of determining the orientations of joints in a limb system so as to reach a desired end position.
Invers kinematics can be approached both in a free-form “iterative” manner, or it can be approached with a much simpler geometric model. Being an absolute idiot blockehad, especially back whenever I played Garrys Mod and actually gave a hoot about inverse kinematics,
The inverse kinematics approach in this article approach is a relatively simple approach, which features a parameterized geometric model with all but one parameter pre-determined, and uses Newton iteration to solve for the missing parameter required to determine the angles of the entire system.
Before that, first I will explain inverse kinematics for 1 and 2 segments.
1-Segment IK
With 1-segment inverse kinematics, that is to say literally a single limb, it is a matter of orienting that limb towards the desired end position. Tough luck if it's not perfectly within range, however.
2-segment IK
With a situation such as 2-segment inverse kinematics, this situation becomes not as easy to calculate (only relative to 1-segment, which is not saying much at all), but with the extra limb there is an increased flexibility in the range of space that is accessible by the system.
The geometric picture that a 2-segment system makes is a simple triangle with lengths \(L_1\), \(L_2\), and \(D\) (D for the distance between the source of the system and its desired position to reach).
With three lengths of a triangle, we can use the Law of Cosines to solve for any particular angle of the triangle.
$$ m\angle{C} = cos^{-1}(\frac{a^2+b^2-c^2}{2ab}) $$
Plugging values in to find \(m\angle{BAC}\) we get:
$$ m\angle{BAC} = cos^{-1}(\frac{L_1^2 + D^2 - L_2^2}{2 \cdot L_1 \cdot D}) $$
This will give us the internal angle of the triangle that we will use to properly orient the system towards our end position. With A as the start of the system and C as the end of the system, the angles we would need to find in this setup are \(m\angle{BAC}\) and \(m\angle{ABC}\).
The Law of Cosines is perhaps the most handy tool to solving a system. At any point where you find the three lengths of a triangle inside a system, the law of cosines will give you the angles for it.
The particular challenge at hand
While a 1-segment and 2-segment system are easy to solve out, any more added joints to the system introduces ambiguity into finding a solution, there is more than just one single solution, and requires arbitrary constraints to simplify the system.
When I had originally attempted this problem in 2016, my small brain was not very capable, so on deciding the following constraints of letting \(L_1 = L_3\), which would allow \(L_2\) to directly bisect the line \(D\) while concurrently being bisected by \(D\), I had come up with an easy to work with model.
As can be seen, bisecting \(L_2\) and \(D\) and also having \(L_1 = L_3\) creates two congruent triangles. With the known triangle lengths of \(L_1\), \(\frac{L_2}{2}\), and \(\frac{D}{2}\), the Law of Cosines can be applied to solve for the angles required to orient the system.
An Analytic Approach for this System
Recently, I have taken another look into this setup, and have created a geometric model with equations that will make it possible to parameterize one aspect of the setup and find a solution for the other remaining aspect required to be found in order to have the lengths of the triangles in the setup.
I am using the variable \(k\) as a parameter which will represent how far along \(L_2\) will an intersection between it and \(D\) occur as a propotion from 0 to 1. In this system, \(k = 0\) would represent the left-most tip of \(L_2\) intersecting with the line \(D\) (making \(L_1\) directly parallel with D), while \(k = 1\) would represent the exact opposite situation with the right-most tip of \(L_2\) intersecting \(D\). The variable \(x\) represents the same idea as \(k\) of mapping a point along a line from 0 to 1 but with the line \(D\). It is \(x\) that we will solve for.
One property of geometry is that with intersecting straight lines, angles that are opposite each other are congruent. This means that in our system, the opposite angles \(A_1\) and \(A_2\) that are associated with the intersection of \(L_2\) and \(D\) for the triangles that are formed with \(L_1\) and \(L_3\) are congruent, despite the two triangles having different lengths.
For \(A_1\), the Law of Cosines shows that:
\begin{equation} cos(A_1) = \frac{(x \cdot D)^2 + (k \cdot L_2)^2 - L_1^2}{2 \cdot (x \cdot D) \cdot (k \cdot L_2)} \end{equation}
For \(A_2\):
\begin{equation} cos(A_2) = \frac{((1-x) \cdot D)^2 + ((1-k) \cdot L_2)^2 - L_3^2}{2 \cdot ((1-x) \cdot D) \cdot ((1-k) \cdot L_2)} \end{equation}
And because \(A_1 = A_2\), then \(cos(A_1) = cos(A_2)\). Therefore:
\begin{equation} \frac{(x \cdot D)^2 + (k \cdot L_2)^2 - L_1^2}{2 \cdot (x \cdot D) \cdot (k \cdot L_2)} = \frac{((1-x) \cdot D)^2 + ((1-k) \cdot L_2)^2 - L_3^2}{2 \cdot ((1-x) \cdot D) \cdot ((1-k) \cdot L_2)} \end{equation}
After rearranging the equation, distributing everything out, subtracting the two equations, simplifying, and refactoring, we have the following set to 0:
\begin{equation} \begin{aligned} L_1^2 \cdot (-(1-x)(1-k)) + L_2^2 \cdot (-k^3 + k^2 - xk + xk^2) \\ + L_3^2 \cdot (xk) + D^2 \cdot (-x^3 + x^2 - xk + x^2k) = 0 \end{aligned} \end{equation}
Testing and Usage
The aim is to, in having \(L_1\), \(L_2\), \(L_3\), and \(k\) be arbitrary variables and \(D\) dynamically changing, use that information to solve for an \(x\) that satisfies the equation. Solving for an \(x\) will allow for us to plug in \(k\) and \(x\) to the setup to have all the necessary lengths of the two triangles in the model, which will allow us to orient our system correctly.
Having plugged in the conditions that match the earlier simplified setup in Section 2, where \(L_1 = L_3\), \(x=\frac{1}{2}\), \(k=\frac{1}{2}\) (remember that \(L_2\) and \(D\) bisected each other; the intersection of \(L_2\) and \(D\) occur exactly halfway through each), the equation did indeed work out to equal 0, so we're on the right path.
Solving for \(x\)
Let E(x) be equal to our equation:
\begin{equation} \begin{aligned} E(x) = L_1^2 \cdot (-(1-x)(1-k)) + L_2^2 \cdot (-k^3 + k^2 - xk + xk^2) \\ + L_3^2 \cdot (xk) + D^2 \cdot (-x^3 + x^2 - xk + x^2k) \end{aligned} \end{equation}
So that whenever \(E(x) = 0\) in a proper setup and \(x\) is between 0 and 1, it means we have the proper \(x\) to plug in and solve for the angles of the system. We can find a zero for this equation with Newton's Method.
\begin{equation} E'(x) = L_1^2(-(k-1)) + L_2^2(k-1)k \\ + L_3^2k + D^2(k(2x-1) + (2-3x)x) \end{equation}
Newton's method says that with an initial value (in our case we can use \(x_i = 0.5\)), we can find the x-value of the intersection between the y-axis and a tangent line which touches where our initial guess is using:
\begin{equation} x' = x - \frac{E(x)}{E'(x)} \end{equation}
We can repeat this process on the \(x\) that we get multiple times to get a more and more accurate answer.
Here is a demo which shows the equation as a graph and shows the Newton iteration which gets it there. The demo compares against a ground truth determined by line intersections.
Once we have a sufficiently close x, we now have all the necessary measuresments for our triangles, and we may not use the law of cosines to calculate the angles for the inveres kinematics setup.
Aside: finding an intersection in two 2D line segments
Provided that there are 2 line segments \(\overline{P_1P_2}\) and \(\overline{P_3P_4}\) aren't parallel, then there is an intersection between them along the lines they segment (it may not be within the segment, but the intersection exists).
Framing the line segments as two rays which have a source point and a direction, we have a source \(P_1\) with a direction \(\vec{u} = P_2 - P_1\), and a source \(P_3\) with a direction \(\vec{v} = P_4 - P_3\). To get a point along the line segment, we can start at the source point and scale the direction by some value ranging from 0 to 1 (\(p = P_{source} + k \cdot \vec{u}\)). In the above setup, there is an intersection between the two line segments, which means that for both rays there are two values which we can scale each ray respectively to get the same point.
\begin{equation} P_1 + \vec{u} \cdot a = P_3 + \vec{v} \cdot b \end{equation}
We have a solution of \((a,b)\) (not a geometric point, just vector of values) that describe two particular linear combinations of two different vectors from two different points which will result in the same final point. Substituting and rearranging to seperate constants and variables:
\begin{equation} (P_2 - P_1) \cdot a + (P_3 - P_4) \cdot b = P_3 - P_1 \end{equation}
We can split this equation into two equations for each component in 2D space.
\begin{equation} (P_{2x} - P_{1x}) \cdot a + (P_{3x} - P_{4x}) \cdot b = P_{3x} - P_{1x} \end{equation}
\begin{equation} (P_{2y} - P_{1y}) \cdot a + (P_{3y} - P_{4y}) \cdot b = P_{3y} - P_{1y} \end{equation}
This gives us a set of linear equations with which we can solve for \(a\) and \(b\) using linear algebra.
\begin{equation} \begin{bmatrix} P_{2x} - P_{1x} & P_{3x} - P_{4x} \\ P_{2y} - P_{1y} & P_{3y} - P_{4y} \end{bmatrix} \cdot \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} P_{3x} - P_{1x} \\ P_{3y} - P_{1y} \end{bmatrix} \end{equation}
For line segments, as long as \(a\) and \(b\) are within 0 to 1, then the intersection lies inside the two segments.
What's good for our testing of our equation is the fact that the values \(a\) and \(b\) are conveniently the ground truth values for \(x\) and \(k\) in a setup of 4 arbitrary points.
Conclusion
Our function \(E(x)\) and the use of Newton's method to quickly iterate to a very accurate answer work exceptionally. In just three iterations, most typical looking cases set up in the testing demo easily iterated to a very small acceptable delta value.
Here is a working implementation of the parameterized inverse-kinematics setup to play with.
Properties of the equation—constraints, extraneous values, limitations
With some k-values that were above 1 or below 0, it was possible to iterate to valid solutions, however there exist some cases where an invalid solution is iterated to, so it's best to avoid any any such k-values.
Any x-values above 1 or below 0, on the other hand, are not particularly iterable to at all, since the initial guess is \(x_i = 0.5\), making it very likely that it will find another “solution” to the equation that happens to fall within the range (even if it's not the actual solution), but such a thing is not intended in the first place.
I simply cannot fathom configuring the setup such that the true x-value would fall out the range; it would likely require another setup, one that resembles more a trapezoid, which would be an entirely different approach to our Z-form.
It looks like any configurations where the solution is near the beginning or the end of \(D\) take more iterations to reach a sufficient accuracy, although I'm sure its neglibible.
The maximum length for the system is \(L_1 + L_2 + L_3\) while the minimum length will depend on which lenghths are larger and smaller. For a typical setup where both \(L_1\) and \(L_3\) are larger then \(L_2\), the minimum length is \(L_1 - L_2 + L_3\)
Special Thanks
to literally no one i did this myself