Accommodating Chains of Greater Degrees of Freedom
“When the number of links in a joint chain becomes greater than three, analytical methods usually become complex and difficult to implement.” (Mukundan, 2009, p. 1)The function of a Cyclic Coordinate Descent (CCD) algorithm allows for control of highly articulated systems, well beyond 3 degrees of freedom which my current analytical solution limits me to.
As explored in my earlier inverse kinematics approaches blog, a heuristic iterative search aims to place the end effector as close to the target position as possible by performing a series of one-bone corrections in turn, along the length of the limb.
The ability to solve chain configurations regardless of segment length and efficiency of CCD algorithms makes it an ideal choice for my solution as this “technique for generating IK solutions that can run at interactive frame-reates” (Kenwright, 2013, p. 56).
The IK Problem
As my solution aims to reproduce natural human motion I will only need to consider revolute joints. These can be solved with: |
 |
| Figure 1: Revolute joint, corrective angle and rotation axis calculation (Kenwright, 2013, p. 56) |
The cross product “returns a vector that is perpendicular to both of the vectors being multiplied together” (Lengyel, 2012, p. 19). This defines the axis about which the corrective rotation must be applied.
Implementing CCD solution
As discussed by Kenwright (2013, p. 55) CCD is an iterative step-by-step approach. I began by creating a for loop which will iterate through an array containing all the joints in the kinematic chain, from the end effector to the root joint. |
| Figure 2: heuristic iterative search criteria |
On each pass of the for loop, a vector is created between the current joint and the end effector and another between the current joint and the target.
The values are normalized so that the cross and dot product may be calculated correctly.
As “‘Solving’ means minimizing some error” (Bergen, 2014) a check was needed to compare the end effector position to the target position. If this error value is below a certain threshold, the process is completed.
 |
| Figure 3: Configuration target error |
Alternately, the solution may manipulate the chain so that it “Converges to the nearest local minimum, which may not be a proper solution (should one exist)” (Bergen, 2014). To allow for this circumstance, each time a joint in the chain is adjusted by the solution a count in incremented. If this count reaches a maximum attempt threshold value, the process is considered complete.
As the solution is intended for dynamic environments, every time the target is moved the number of attempts is set to 0 and the iterative search begins again.
 |
| Figure 4: Setting current attempt to 0 if the target is updated |
The result was this behaviour:
 |
| Figure 5: Floating errors present in calculation of joint configurations |
Using the lessons learnt from improving my previous analytical solution, clamping the corrective rotation between -1 and 1 prevents any floating errors (shown in figure 6). This results in less erratic deviation from the current chain position to the next viable solution, as shown in figure 7.
 |
| Figure 6: Clamped corrective rotation calculation to eliminate floating errors |
 |
| Figure 7: No floating errors present in calculation of joint configurations |
The script has been purposefully written to accommodate 3D joint chains. When applied to a model which has been set up with an appropriate hierarchy to produce forward kinematics, the solution functions as intended (3D biped model sourced from mixamo.com).
 |
| Figure 8: Unconstrained CCD manipulating 3D biped model |
Next Objective
Now I can manipulate a 3D chain to accommodate the rotations of all joints to place the end effector at the target location, modifying the solution behaviour to mimic natural actions through constraining the rotation of the joints to prevent overextension/twisting of the joints, stopping unnatural or impossible chain configurations, and dampening the movement of the joints to new postures to give more believable motion.References
Bergen, G. (2014). Math for Game Programmers: Inverse Kinematics. Available at: https://www.gdcvault.com/play/1020056/Math-for-Game-Programmers-Inverse [Accessed 1 Mar. 2019]
Kenwright, B. (2013). Game Inverse Kinematics. [Place of publication not identified]: CreatSpace, pp.9, 20-23, 31-37, 55-59.
Lengyel, E. (2012). Mathematics for 3D Game Programming and Computer Graphics. 3rd ed. pp.15-16, 19-21, 29, 82-86.
Mukundan, R. (2009). A robust inverse kinematics algorithm for animating a joint chain. International Journal of Computer Applications in Technology, 34(4), p.303-308. Available at: https://www.researchgate.net/publication/220171083_A_robust_inverse_kinematics_algorithm_for_animating_a_joint_chain [Accessed 1 Mar. 2019]
Bibliography
Gürbüzbalaban, M., Ozdaglar, A., Parrilo, P. and Vanli, N. (2017). When Cyclic Coordinate Descent OutperformsRandomized Coordinate Descent. NIPS 2017, [online] pp.1-9. Available at: https://papers.nips.cc/paper/7275-when-cyclic-coordinate-descent-outperforms-randomized-coordinate-descent.pdf [Accessed 5 Mar. 2019].
Kenwright, B. (2012). Game Physics. pp.14-40, 188, 263.
Kenwright, B. (2012). Inverse Kinematics – Cyclic Coordinate Descent (CCD). Journal of Graphics Tools, 16(4), pp.177-217. Available at: https://www.researchgate.net/publication/263226178_Inverse_Kinematics_-_Cyclic_Coordinate_Descent_CCD [Accessed 1 Mar. 2019]
Lander, J. (1998). Making Kine More Flexible. GRAPHIC CONTENT, [online] pp.15-22. Available at: http://www.darwin3d.com/gamedev/articles/col1198.pdf [Accessed 5 Mar. 2019].
