Graphical Models 73 (2011) 243–260

Contents lists available at ScienceDirect

Graphical Models
journal homepage: www.elsevier.com/locate/gmod

FABRIK: A fast, iterative solver for the Inverse Kinematics problem q
Andreas Aristidou ⇑, Joan Lasenby
Department of Engineering, University of Cambridge, Cambridge CB2 1PZ, UKa r t i c l e

i n f oArticle history:
Received 12 February 2010
Received in revised form 24 March 2011
Accepted 9 May 2011
Available online 15 May 2011
Keywords:
Human animation
Inverse Kinematics
Joint conﬁguration
Motion reconstructiona b s t r a c t
Inverse Kinematics is deﬁned as the problem of determining a set of appropriate joint conﬁgurations for which the end effectors move to desired positions as smoothly, rapidly, andas accurately as possible. However, many of the currently available methods suffer fromhigh computational cost and production of unrealistic poses. In this paper, a novel heuristic
method, called Forward And Backward Reaching Inverse Kinematics (FABRIK), is describedand compared with some of the most popular existing methods regarding reliability, computational cost and conversion criteria. FABRIK avoids the use of rotational angles or matrices, and instead ﬁnds each joint position via locating a point on a line. Thus, it converges in
few iterations, has low computational cost and produces visually realistic poses. Constraints can easily be incorporated within FABRIK and multiple chains with multiple end
effectors are also supported.
Ó 2011 Elsevier Inc. All rights reserved.

1. Introduction
This paper addresses the problem of manipulating articulated ﬁgures in an interactive and intuitive fashion for thedesign and control of their posture. This problem ﬁnds its
application in the areas of robotics, computer animation,
ergonomics and gaming. In computer graphics, articulated
ﬁgures are a convenient model for humans, animals orother virtual creatures from ﬁlms and video games. Inverse
Kinematics (IK) has also been used in rehabilitation medicine in order to observe asymmetries or abnormalities. The
most popular method for animating such models is motion-capture; however, despite the availability of highlysophisticated techniques and expensive tools, many problems appear when dealing with complex ﬁgures. Most virtual character models are very complex; they are made upof many joints giving a system with a large number of degrees of freedom, thus, it is often difﬁcult to produce a realistic character animation.

q

This paper has been recommended for acceptance by Jarek Rossignac.

⇑ Corresponding author. Fax: +44 1223332662.

E-mail address: aa462@cam.ac.uk (A. Aristidou).
1524-0703/$ - see front matter Ó 2011 Elsevier Inc. All rights reserved.
doi:10.1016/j.gmod.2011.05.003

Inverse Kinematics is a method for computing the posture via estimating each individual degree of freedom inorder to satisfy a given task that meets user constraints;
it plays an important role in the computer animation andsimulation of articulated ﬁgures. This paper presents a
new heuristic iterative method, Forward And Backward
Reaching Inverse Kinematics (FABRIK), for solving the IK
problem in different scenarios. FABRIK uses a forward
and backward iterative approach, ﬁnding each joint position via locating a point on line. FABRIK has been utilised
in highly complex systems with single and multiple targets, with and without joint restrictions. It can easily handle end effector orientations and support, to the best of ourknowledge, all chain classes. A reliable method for incorporating constraints is also presented and utilised within
FABRIK. The proposed method retains all the advantagesof FABRIK, producing visually smooth movements without
oscillations and discontinuities. Several experiments havebeen implemented for comparison purposes between themost popular manipulator solvers, including multiple end
effectors with multiple tasks, and highly constrained
joints. The proposed algorithm is very efﬁcient both insimple and complex problems resulting in similar or evenbetter poses than highly sophisticated methods, requiring

244

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

less processing time and fewer iterations to reach the target. Another important advantage of the proposed methodology is the simplicity of the algorithm, which enables easy
conﬁguration to any IK problem.

2. Background and motivation
The production of realistic and plausible motions remains an open challenge within the robotics and animation
communities.
Severalmodelshave
been
implemented for solving the IK problem from many different areas of study. Zhao and Badler [1] poses the IK task asa problem of ﬁnding a local minimum of a set of non-linear
equations, deﬁning Cartesian space constraints. However,
the most popular numerical approach is to use the Jacobianmatrix to ﬁnd a linear approximation to the IK problem.
The Jacobian solutions linearly model the end effectors’
movements relative to instantaneous system changes inlink translation and joint angle. Several different methodologies have been presented for calculating or approximating the Jacobian inverse, such as the Jacobian Transpose,
Damped Least Squares (DLS), Damped Least Squares with
Singular Value Decomposition (SVD-DLS), Selectively
Damped Least Squares (SDLS) and several extensions [2–7]. Jacobian inverse solutions produce smooth postures;
however most of these approaches suffer from high computational cost, complex matrix calculations and singularity problems. An alternative approach is given by Pechev in[8] where the Inverse Kinematics problem is solved from acontrol prospective. This approach is computationallymore efﬁcient than the pseudo-inverse based methods
and does not suffer from singularity problems.
The second family of IK solvers is based on Newton
methods. These algorithms seek target conﬁgurations
which are posed as solutions to a minimisation problem,
hence they return smooth motion without erratic discontinuities. The most well known methods are Broyden’s
method, Powell’s method and the Broyden, Fletcher, Goldfarb and Shanno (BFGS) method [9]. However, the Newton
methods are complex, difﬁcult to implement and have highcomputational cost per iteration.
A very popular IK method is the Cyclic Coordinate Descent (CCD) algorithm, which was ﬁrst introduced by Wang
and Chen [10] and then biomechanically constrained by
Welman [11]. CCD has been extensively used in the computer games industry [12] and has recently been adapted
for protein structure prediction [13]. CCD is a heuristic iterative method with low computational cost for each joint
per iteration, which can solve the IK problem without matrix manipulations; thus it formulates a solution very
quickly. However, CCD has some disadvantages; it can suffer from unrealistic animation, even if manipulator constraints have been added, and often produces motion
with erratic discontinuities. It is designed to handle serial
chains, thus, it is difﬁcult to extend to problems with multiple end effectors. Unzueta et al. [14] describes a Sequential IK (SIK) solver, and is a direct extension of Boulic et al.
[15], in that its inputs are end effector positions, such as
wrists, ankles, head and pelvis, which are used to ﬁnd
the human pose. The IK problem is then solved sequen-

tially using simple analytic-iterative IK algorithms (CCD),
in different parts of the body, in a speciﬁc order. Kulpa
and Multon [16] also adopted the CCD kinematic algorithm
and solved its crucial problem of resulting unnatural poses.
The proposed extension in [16] is able to solve problems
with humanoid hierarchy, dividing the whole body into
groups of joints near an end effector (typically head, trunk,arms and legs). In order to satisfy the desired centre ofmass, the lightest group moves ﬁrst, adjusting its centreof mass by changing the length of the limb and rotating
it (assuming it as a rigid body).
Recently, Courty and co-workers [17,18] proposed a
Sequential Monte Carlo Method (SMCM) and particle ﬁltering approach respectively. The proposed particle IK solver
treats the character skeleton as a set of 3 DoFs particles
having inter-length constraints. An iterative constrainer,
with various pre-conditions and parameters, is then applied over the particles, tuning its behaviour both staticallyand dynamically. The ﬁnal particle positions and the length
constraints are then used to reconstruct the resulting DoFs
of the body. Neither method suffers from matrix singularity problems and both perform reasonably well. However,these statistical methods have high computational cost.
Grochow et al. [19] presents a style-based IK method
which is based on a learned model of human poses. Givena set of constraints, the proposed system can produce, in
real-time, the most likely pose satisfying those constraints.
The model has been trained on different input data that
leads to different styles of IK; it can generate any pose,but poses are highly related to those which are most similar to the space of poses in the training data. Sumner andco-workers [20,21] used mesh-based IK techniques to conﬁgure the animated shapes. Mesh-based IK learns a spaceof natural deformations from example meshes. Using thelearned space, they generate new shapes that respect the
deformations exhibited by the examples, and satisfy vertex
constraints imposed by the user. However, these methods
require an off-line training procedure, their results arehighly dependent on the training data and limited only
to those models and movements on which the system
has been trained.
The Triangulation algorithm [22] is an IK solver thatuses the cosine rule to calculate each joint angle, startingat the root of the kinematic chain and moving outward towards the end effector. Although it can reach the target injust one iteration, having low computational cost, its results are often visually unnatural. The joints close to theend effector are usually in a straight line, emphasising
the rotation on the joints neighbouring the root. The Triangulation IK method can only be applied to problems with asingle end effector and does not support imposed joint limits. An improved version is given in [23] where the n-link
IK problem is reduced to a two-link problem in which eachlink is rotated at most once in an attempt to reach the target position.
Brown et al. [24] presents a real-time method whichuses a ‘Follow-the-Leader’ (FTL) non-iterative techniquewhich is similar to each individual iteration of FABRIK.
While FTL was speciﬁcally designed for rope simulation,
it can be applied to manipulate kinematic chains (balland-socket joints connected by rigid links). Since FTL does

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

not work in an iterative fashion, the authors cope with
node constraints (for example the root position is ﬁxed,
as in the IK deﬁnition) by averaging the results of FTL(intermediate nodes) in each direction. However, the averaging of the results induces a variation of the segment
lengths and produces, in some cases, unnatural poses.
Although similar to FABRIK in its basic structure, the FTL
algorithm has not been extended to support joint constraints and orientations (these are largely superﬂuous inrope simulation), nor has it been applied to cases wheremultiple end effectors exist.
3. The articulated body model
A rigid multibody system consists of a set of rigid objects, called links, connected together by joints. A joint is
the component concerned with motion; it permits somedegree of relative motion between the connected segments. Virtual body modelling is important for human posture control. A well constrained model can restrict
postures to a feasible set, therefore allowing a more realistic motion. Most models assume that body parts are rigid,
although this is just an assumption approximating reality.
The skeletal structure is usually modeled as a hierarchy ofrigid segments connected by joints, each deﬁned by theirlength, shape, volume and mass properties.
A manipulator such as a robot arm or an animatedgraphics character is modelled as a chain composed of rigid
links connected at their ends by rotating joints. Any translation and/or rotation of the i-th joint affects the translation and rotation of any joint placed later in the chain.
The chains can be formalised as follows: All joints withno children are marked as end effectors; a chain can be built
for each end effector by moving back through the skeleton,going from parent to parent, until the root (the start of thechain) is reached. By deﬁnition, in the IK problem, the root
joint is assumed ﬁxed but methods can generally cope withtranslation of the root.
Algorithm 1. A full iteration of the FABRIK algorithm

1.1
1.2
1.3
1.4
1.5
1.6
1.7

1.8
1.9

Input: The joint positions pi for i = 1, . . . , n, thetargetposition t and the distances between eachjoint
di = jpi+1  pij for i = 1,. . .,n  1.
Output: The new joint positions pi for
i = 1, . . . , n.
% The distance between root and target
dist = jp1  tj
% Check whether the target is within reach
if dist > d1 + d2 +. . .+ dn1 then
% The target is unreachable
for i = 1, . . . , n  1 do
% Find the distance ri between the target t andthe joint
position pi
ri = jt  pij
ki = di/ri

1.10
1.11
1.12
1.13
1.14

1.15
1.16

1.17
1.18
1.19
1.20
1.21
1.22
1.23

1.24
1.25
1.26
1.27
1.28
1.29
1.30
1.31
1.32
1.33

1.34
1.35
1.36
1.37
1.38
1.39
1.40
1.41

245

% Find the new joint positions pi.
pi+1 = (1  ki) pi + kit
endelse% The target is reachable; thus, set as b the
initial position of thejoint p1
b = p1% Check whether the distance between the end
effector pn
and the target t is greater than a tolerance.
difA = jpn  tj
while difA > tol do% STAGE 1: FORWARD REACHING% Set the end effector pn as target t
pn = tfor i = n  1, . . . , 1 do
% Find the distance ri between the new joint
positionpi+1 and the joint pi
ri = jpi+1  pij
ki = di/ri% Find the new joint positions pi.
pi = (1  ki) pi+1 + kipi
end
% STAGE 2: BACKWARD REACHING% Set the root p1 its initial position.
p1 = bfor i = 1,. . .,n  1 do
% Find the distance ri between the new joint
position pi
and the joint pi+1
ri = jpi+1  pij
ki = di/ri% Find the new joint positions pi.
pi+1 = (1  ki)pi + kipi+1
end
difA = jpn  tj
end
end

4. FABRIK: a new heuristic IK solution
In this section, a new heuristic method for solving the IK
problem, FABRIK, is presented. It uses the previously calculated positions of the joints to ﬁnd the updates in a forward
and backward iterative mode. FABRIK involves minimising
the system error by adjusting each joint angle one at atime. The proposed method starts from the last joint of
the chain and works forwards, adjusting each joint along
the way. Thereafter, it works backward in the same way,in order to complete a full iteration. This method, insteadof using angle rotations, treats ﬁnding the joint locations
as a problem of ﬁnding a point on a line; hence, time andcomputation can be saved.
Assume p1, . . . , pn are the joint positions of a manipulator. Also, assume that p1 is the root joint and pn is the end

246

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

effector, for the simple case where only a single end effector exists. The target is symbolised as t and the initial baseposition by b. FABRIK is illustrated in pseudo-code in Algorithm 1 and a graphical representation of a full iteration
with a single target and 4 joints is presented and explainedin Fig. 1.
First calculate the distances between each joint
di = jpi+1  pij, for i = 1, . . . , n  1. Then, check whether thetarget is reachable or not; ﬁnd the distance between the

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 1. An example of a full iteration of FABRIK for the case of a single
target and 4 manipulator joints. (a) The initial position of the manipulator
and the target, (b) move the end effector p4 to the target, (c) ﬁnd the joint
p03 which lies on the line l3 that passes through the points p04 and p3, andhas distance d3 from the joint p04 , (d) continue the algorithm for the rest of
the joints, (e) the second stage of the algorithm: move the root joint p0 1 toits initial position, (f) repeat the same procedure but this time start fromthe base and move outwards to the end effector. The algorithm isrepeated until the position of the end effector reaches the target or gets
sufﬁciently close.

root and the target, dist, and if this distance is smaller thanP
the total sum of all the inter-joint distances, dist < n1
1 di ,
the target is within reach, otherwise, it is unreachable. If
the target is within reach, a full iteration is constitutedby two stages. In the ﬁrst stage, the algorithm estimateseach joint position starting from the end effector, pn, moving inwards to the manipulator base, p1. So, let the new position of the end effector be the target position, p0n ¼ t. Find
the line, ln1, which passes through the joint positions pn1
and p0n . The new position of the (n  1)th joint, p0n1 , lies onthat line with distance dn1 from p0n . Similarly, the new position of the (n  2)th joint, p0n2 , can be calculated using theline ln2, which passes through the pn2 and p0n1 , and has
distance dn2 from p0n1 . The algorithm continues until all
new joint positions are calculated, including the root, p01 .
Having in mind that the new position of the manipulator base, p01 , should not be different from its initial position,a second stage of the algorithm is needed. A full iteration iscompleted when the same procedure is repeated but thistime starting from the root joint and moving outwards tothe end effector. Thus, let the new position for the 1st joint,
p001 , be its initial position b. Then, using the line l1 thatpasses through the points p001 and p02 , we deﬁne the new position of the joint p002 as the point on that line with distanced1 from p001 . This procedure is repeated for all the remaining
joints, including the end effector. In cases where the root
joint has to be translated to a desired position, FABRIK
works as described with the difference that in the backward phase of the algorithm, the new position of the root
joint, p001 , will be the desired and not the initial position.
After one complete iteration, it is almost always the case(observed empirically) that the end effector is closer to thetarget. The procedure is then repeated, for as many iterations as needed, until the end effector is identical or close enough (to be deﬁned) to the desired target. The unconstrained
version of FABRIK converges to any given chains/goal positions, when the total length of serial links is greater thanthe distance to the target (the target is reachable). However,if the target is not within the reachable area, there is a termination condition which compares the previous and the current position of the end effector, and if this distance is lessthan an indicated tolerance, FABRIK terminates its operation. Also, in the extreme case where the number of iterations has exceeded an indicated value and the target has
not been reached, the algorithm is terminated (however,
we have never encountered such a situation).
Several optimisations can be achieved using Conformal
Geometric Algebra (CGA) [25,26] to produce faster results
and to converge to the ﬁnal answer in fewer iterations;
CGA has the advantage that basic entities, such as spheres,lines, planes and circles, are simply represented by algebraic objects. Therefore, a direct estimate of a missing joint,
when it is between 2 true positions, can be achieved byintersecting 2 spheres with centres the true joint positions
and radii the distances between the estimated and the true
joints respectively; the new joint position will be taken as
the point on the circle (created by the intersection of the 2
spheres) nearest to the previous joint position. Anothersimple optimisation is the direct construction of a line
pointing towards the target, when the latter isunreachable.

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

247

The proposed method has all the advantages of existing
iterative heuristic algorithms. The computational cost foreach joint per iteration is low, meaning the solution is arrived at very quickly. It is also easy to implement, since it
is simply a problem involving points, distances and lines
and always returns a solution when the target is in range.
It does not require complex calculations (e.g Jacobian or
Hessian matrix) or matrix manipulations (inversion or singular value decomposition), it does not suffer from singularity problems and returns smooth motion without
erratic discontinuities.
4.1. FABRIK with multiple end effectors
In reality, most of the multibody models, such as hands,
human or legged bodies etc, are comprised of several kinematic chains, and each chain generally has more than 1
end effector. Therefore, it is essential for an IK solver tobe able to solve problems with multiple end effectors
and targets. The proposed algorithm can be easily extended to process models with multiple end effectors.
However, prior knowledge of the model, such as the subbase1 joints, and the number and structure of chains isneeded.
The algorithm is divided into two stages, as in the single
end effector case. In the ﬁrst stage, the normal algorithm isapplied but this time starting from each end effector andmoving inwards to the parent sub-base. This will produce
as many different positions of the sub-base as the numberof end effectors connected with that speciﬁc sub-base. The
new position of the sub-base will then be the centroid of allthese positions. Thereafter, the normal algorithm should
be applied inwards starting from the sub-base to the
manipulator root. If there are more intermediate subbases, the same technique should be used. In the second
stage, the normal algorithm is applied starting now fromthe root and moving outwards to the sub-base. Then, thealgorithm should be applied separately for each chain until
the end effector is reached; if more sub-bases exist, thesame process is applied. The method is repeated until all
end effectors reach the targets or there is no signiﬁcantchange between their previous and their new positions.
An example of a model ﬁgure having multiple end effectors
and sub-bases is presented in Fig. 2.
More sophisticated (and complex) models can be also
tackled. Extending the proposed algorithm to take into account the ﬁgure’s shape, constraints and properties, will
reduce the number of iterations needed to reach the target
and will return more feasible postures. For example, FABRIK has been successfully applied to real-time hand tracking and reconstruction in motion capture [27,28].
4.2. FABRIK within closed loops
FABRIK can also cope with cases where the ‘‘end effector’’ is not positioned at the end of the chain (i.e. it is a leaf)in the same way as for the sub-bases described in Section
1
A sub-base joint is a joint which connects 2 or more chains. A preanalysis of the body can determine exactly where the sub-bases are located.

Fig. 2. An example of a model ﬁgure with multiple end effectors andmultiple sub-bases.

4.1. The whole model could be divided into groups of joints
near the end effectors (such as head, trunk, arms and legs)
and then the body postures can be sequentially adapted ina speciﬁc order, similarly to Unzueta et al. [14] and Kulpa
and Multon [16]. Obviously, the adaption hierarchy varies
between models. FABRIK has been successfully used withinclosed loops of a humanoid, achieving real-time centre ofrotation correction in motion capture, under marker occlusions [29].

4.3. Applying joint limits to FABRIK
Most legged body models are comprised of joints having biomechanical constraints, which provide natural
restrictions on their motion. Such constraints are essential
in physical simulations, IK techniques and tracking in motion capture systems to reduce visually unrealistic
movements.
Several biomechanically and anatomically correct models have been presented that formalise the range of motionof an articulated ﬁgure. These models are mainly characterised by the number of parameters which describe themotion space and are hierarchically structured. Becauseof their complex nature, most of the proposed models are
simpliﬁed or approximated by more than one joint. The
most well-known models are: the shoulder model, a complex model composed of 3 different joints [30–33]; thespine model, a complex arrangement of 24 vertebrae (usually, for simplicity, the spine is modelled as a simple chainof joints [34–37]); the hand model, this is the most versatilepart of the body comprising a large number of joints [38–40]; the strength model, which takes account of the forces
applied from the skeletal muscles to the bones [34].
A joint is deﬁned by its position and orientation and, inthe most general case, has 3 DoFs. A bone rotation can be
described by factoring it into two rotations: one ‘‘simple
rotation’’, termed here rotational (2 DoFs), that moves thebone to its ﬁnal direction vector, and another which we call

248

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

orientational (1 DoF), which represents the twist aroundthis ﬁnal vector. Thus, the range of movement of a bone
can be controlled by dividing the joint restriction procedure into two interconnected phases, a rotational and an
orientational phase, contributing equally to the joint
restrictions. The essential feature of a joint is that it permits a relative motion between the two limbs it connects.
Most of the existing structure models, such as those described above, use techniques which restrict the bone tolie within the rotational and orientational limits of thejoint. Blow [41] proposes a loop hung in space, limiting
the range of motion of the bone to ‘‘reach windows’’ described by star polygons. Wilhelms and Van Gelder [42]present a 3D ‘‘reach cone’’ methodology using planes,
treating the joint limits in the same way as [41]. Koreinand co-workers [36,43] parameterise realistic joint boundaries of the ball-and-socket joint by decomposing the arbitrary orientation into two components and controlling therotational joint limits so they do not exceed their bounds.
Once a proper parametrisation is deﬁned for each joint of
the articulated body, an animation engine is utilised.
Tolani et al. [44] presents analytical and numerical constraints suitable for anthropomorphic limbs; they treat thelimbs of 3D characters independently in closed forms
resulting in fast analytical solutions. However, analytic
solutions, in general, lack ﬂexibility for under-constrained
instances. A pin-and-drag interface for articulated characters is presented in [45], where multiple-priority-levels
architectures for combining end effector and centre ofmass position control is illustrated.
In this section, a reliable methodology for incorporatingmanipulator constraints is described using FABRIK. Since
FABRIK is iterative, the joint restrictions can be enforcedat each step just by taking the resultant orientation andforcing it to stay within the valid range. FABRIK’s ability
to converge on an answer, if the target is within reach, is
not affected by any imposed joint limits.
The main idea behind this methodology is the re-positioning and re-orientation of the target to be within the allowed range bounds; ensuring that these restrictions arealways satisﬁed means a more feasible posture can beachieved. This can be accomplished by checking if the target is within the valid bounds, at each step of FABRIK, andif it is not, to guarantee that it will be moved accordingly.
In contrast to most existing techniques for joint constraints, the proposed methodology simpliﬁes the 3D problem into a 2D problem, meaning that the complexity andthe required processing time is reduced. In this section, ajoint restriction methodology is presented for the generalcase of a ball and socket joint; this example should be considered as an illustration of how joint or model constraints
can be incorporated within FABRIK. Similar techniques canbe easily adopted to limit different joint models.
Assume we have a ball-and-socket joint with orientational limits described by the rotor R and rotational limits
described by the angles h1,. . .,h4. A graphical representationof a joint limit boundary could be an irregular cone which
is deﬁned by these angles. The rotational limits are enforced by re-positioning the target point as the nearest

(a)

(a)

(b)

(c)
Fig. 3. The target is re-positioned within the allowed range of motion
which is deﬁned by the conic section. There are 3 types of joint restriction,
as described by the angles h1,. . .,h4: (a) a circle, (b) an ellipsoidal shapeand (c) a parabolic shape.

(b)Fig. 4. (a) The ball-and-socket joint, pi, with its associated irregular cone
which deﬁnes the allowed range of motion. (b) Shows the composite
ellipsoidal shape created by the distances qj mapped from 3D to 2D.

249

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

point on a conic section from the target position; this procedure is described in detail later. There are 3 possible
conic sections, according to the angles deﬁning the irregular cone: if all hs are equal, the conic section is a circle; if all
hs are greater or smaller than 90° and are not equal, theconic section has an ellipsoidal shape; ﬁnally, if there arehs both greater and smaller than 90°, then the joint boundary limits are deﬁned by a parabolic shape, as illustrated inFig. 3. In subsequent analysis, the joint limits are assumed
to be deﬁned by an ellipsoidal shape, since this is the mostcommon case, but similar procedures apply for different
conic sections. Fig. 4 gives a graphical representation of
the implemented constraints and the irregular cone
describing the rotational motion bounds for the case ofan ellipsoidal shape.
The orientation of the joint can be assigned as follows:
Assume we are in the ﬁrst stage of the algorithm, i.e. wehave just calculated the new position of joint p0i , and wewant to ﬁnd the new position of the (i  1)th joint, p0i1 .
Find the rotor expressing the rotation between the orientation frames at joints p0i and pi1 and if this rotor represents
a rotation greater than a limit, reorient the joint pi1 insuch a way that the rotation will be within the limits. Repeat the procedure for all the joints on both stages of thealgorithm. The methodology is also described in pseudocode in Algorithm 2.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Algorithm 2. The orientational constraints

2.1

2.2
2.3
2.4
2.5

2.6

Input: The rotor R expressing the rotation
between theorientation frames at joints pi and pi1.
Output: The new re-oriented joint p0i1 .
Check whether the rotor R is within the motion
rangeboundsif within the bounds thendo nothing and exit
else
reorient the joint pi1 in such a way that therotor will
be within the limits
end

Once the joint orientation is established, the rotational(2 DoFs) limits, described by angles h1,. . .,h4, can be applied
as follows. Firstly, we ﬁnd the projection O of the target t online L1, where L1 is the line passing through the joint underconsideration, pi, and the previous joint of the chain, pi+1.
Then determine the distance S from the point O to the joint
position pi and calculate the distances qj = Stan(hj), forj = 1,. . .,4, as shown in Fig. 4. We then apply a rotationand translation which takes O to the origin and the axes
deﬁning the constraints to the x and y axes, as in Fig. 4(b).
Working in this 2D plane, we locate the target in a particular quadrant and ﬁnd the ellipse deﬁned on that quadrant
using the associated distances qj; for example, in Fig. 4(b)we are working with the ellipse which is deﬁned by the angles h2 and h3 (or the distances q2 and q3). Finally, ﬁnd thenearest point on that ellipse from the target, if the latter

Fig. 5. Incorporating rotational and orientational constraints within
FABRIK. (a) The initial conﬁguration of the manipulator and the target, (b)relocate and reorient joint p4 to target t, (c) move joint p3 to p03 , which lies on
the line that passes through the points p04 and p3 and has distance d3 fromp04 , (d) reorient joint p03 in such a way that the rotor expressing the rotation
between the orientation frames at joints p03 and p04 is within the motion
range bounds, (e) the rotational constraints: the allowed regions shown as ashaded composite ellipsoidal shape, (f) the joint position p2 is relocated to a
^ 2 , which is the nearest point on that composite ellipsoidal
new position, pshape from p2, ensuring that the new joint position p02 will be within the^ 2 to p02 , to conserve bone length, (h)allowed rotational range. (g) move p
reorient the joint p02 in order to satisfy the orientation limits. This procedure
is repeated for all the remaining joints in a forward and backward fashion.

250

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

is not in the allowed motion range. The nearest point on an
ellipse from a point can be found by simultaneously solving
the ellipse equation and the equation of the tangent line at
the orthogonal contacting point on the ellipse using the
Newton-Raphson method, as described in [46]. Obviously,
it is not necessary to calculate all the ellipses which deﬁne
the composite ellipsoidal shape of Fig. 4(b), but only the ellipse related to the quadrant in which the target is located.
It is important here to recall that, if the constraints which
deﬁne the allowed range of motion are described by a different conic section (circle or parabola), the target should
be re-positioned as the nearest point on that conic section,
similarly to the ellipsoidal case. The last step is to undo theinitial transformation which mapped O to the origin. This
procedure is illustrated in pseudo-code in Algorithm 3
and a demonstration of the process is given in Fig. 5.
Algorithm 3. The rotational constraints

3.1
3.2
3.3

3.4

3.5
3.6

3.7

3.8
3.9
3.10
3.11
3.12

3.13

3.14

Input The target position t and the angles
deﬁning therotation constraints hj for j = 1,. . .,4.
Output: The new target position t0 .
Find the line equation L1
Find the projection O of the target t on line L1
Find the distance between the point O and the
joint
position
Map the target (rotate and translate) in such a
way that O
is now located at the axis origin and oriented
accordingto the x and y-axis ) Now it is a 2D simpliﬁed
problemFind in which quadrant the target belongs
Find what conic section describes the allowed
range ofmotionFind the conic section which is associated withthat
quadrant using the distances qj = Stanhj, wherej = 1,..,4% Check whether the target is within the conic
section or not
if within the conic section thenuse the true target position t
else
Find the nearest point on that conic section
from thetargetMap (rotate and translate) that point on the
conic
section via reverse of 3.4 and use that point as
the new target position
endThis is a versatile, and easily visualisable, method of
restricting where the bone can go. Incorporating this methodology within an IK solver, such as FABRIK, will give us
the opportunity to reconstruct or track animated ﬁgureswith high accuracy. IK algorithms are generally more effective if the constraints are applied at each step (not at theend of the algorithm), ensuring that the rotational and orientational restrictions are satisﬁed at each iteration. Thus,
the proposed joint constraints can be applied within FABRIK by ensuring that the target, at each step, is moved to
be within the allowed orientational and rotational bounds.
Hence, assume that we are in the ﬁrst stage of the algorithm, and have just calculated the new positions of thejoints, p0iþ1 and p0i , and we want to ﬁnd the new positionof the (i  1)th joint, p0i1 . Check if the joint pi1 satisﬁes
the orientational limits and if so, check whether it is within
the composite ellipsoidal shape that describes the allowed
range bounds, as illustrated above. If it is not, then pi1should be re-oriented and/or re-positioned within the al^ i1 Þ. Thereafter, p0i1 can be deﬁned as
lowed bounds ðpthe point on the line li1, which passes through the joint^ i1 and p0i and has di1 distance from p0i , as is
positions p
illustrated in Fig. 5.
The same technique for constraining joints is applied in
the second stage of the algorithm and for each iteration until the target is reached or there is no signiﬁcant change inthe end effectors’ positions. The algorithm copes withjoints and limbs having 3 DoFs, and it can handle cases ofjoint and limb twist. It is important to recall here thatthe inter-joint lengths do not change over time since these
distances are implicity kept constant by FABRIK.
The proposed restriction methodology can be easily extended to manage joint limits greater than 180 degrees. For

(a)

(b)
Fig. 6. Solution for special joint restriction cases: (a) the original case andwhen the allowed range of motion is greater than 180 degrees, (b) when
the target is located on a different hemisphere than the irregular cone.

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

(a)

(b)

(c)

(d)

251

Fig. 7. Incorporating constraints for a hinge joint. (a) The initial conﬁguration of the manipulator and the target. U1 gives the plane of the allowed motion
and it is deﬁned by the hinge joint p2 (1 DoF). The root and the target, which is oriented, also deﬁne the plane U2. (b) Relocate and reorient joint p03 to target^ 2 , and ﬁnd the point p02 on line l2 that passes from the joint position p03 and the projected jointt. Then, project p2 onto the plane U2 to give a new point p^ 2 and has distance d2 from p03 . Reorient the new joint using the orientation constraints. (c) move and reorient joint p1 to p01 , which lies on the line
position pthat passes through the points p02 and p1 and has distance d1 from p02 , (d) The problem is now again a 2D problem and all joints lie on plane U2. Thus, FABRIK
can then be applied to of all the remaining joints in a forward and backward fashion.

instance, when the angle which deﬁnes the allowed rangeof motion is greater than 180 degrees, the associated irregular cone will deﬁne the area which is outside the limits. In
that case, the joint restriction methodology will work in areverse fashion; if the target is within the irregular conearea, meaning it is outside the limits, it will be projectedto the cone surface, as is demonstrated in Fig. 6(a). Anotherspecial case of joint restriction occurs when the target is located in such a position that is not in the same hemisphere(in Fig. 6(b), the upper hemisphere) as the irregular cone.
The limits of motion are deﬁned as the irregular cone in
the upper hemisphere and a reﬂection of the cone in thelower hemisphere; the target in the lower hemisphere is
projected onto the limit boundary by ﬁrst projecting its position onto the reﬂected cone and taking the associatedpoint on the regular cone, as shown in Fig. 6(b). Obviously,
the algorithm works in a similar way for different conic
sections.
One big advantage of the proposed methodology is thatno bone requires rotation to lie in any cone or polygon
window, such as those described in [41,42]; it is only nec-

essary to check whether the target is within the composite
ellipsoidal shape deﬁned by the restrictions on the motion.
It loses none of the advantages of the FABRIK algorithm,
incorporating joint limits via only points, lines and basic
2D entities; no rotational matrices need to be calculated,
resulting in large savings in computational time. If it isdesirable to retrieve the joint angles, all necessary information is of course available (position and orientation of eachjoint).
If more information about the allowed range of motion
is available, the proposed methodology can be extended toinclude increased sophistication, supporting more complex
joint types. Thus, instead of having an ellipsoidal entity todescribe the sub-area in which the target can be placed, apolygonal area can be implemented. If the target is out ofrange, we would look for the nearest point on the polygon.
The constraining methodology can also be modiﬁed tosupport other IK solvers. There are, however, some limitations on what joint types this prototype version can support, since it is assumed that the inter-joint distanceremains constant over time. Prismatic, slicing or shifting

252

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

Fig. 8. The structure of the models used in our experimental examples.
(a) A kinematic chain consisting of 10 joints and 1 end effector. There are
2 kinematic chain models, an unconstrained and a constrained version,(b) a kinematic model with 10 unconstrained joints and 2 end effectors,(c) a hand model with 26 unconstrained joints and 5 end effectors, (d) ahumanoid with 13 unconstrained joints and 5 end effectors. The target
positions (end effectors) are shown in red, while the joint positions areshown in green.

joints (joint types more usually discussed in robotics) are
not directly supported and more information about thejoint is required to attain a solution. Self-collisions can behandled using existing techniques, such as [47]; but morework is needed to ascertain if the FABRIK framework gives
any advantages when dealing with self occlusions.
The problem of limiting the joint movements for simple
2D joint models, such as the hinge joint, can be simpliﬁedusing alternative approaches. Since FABRIK operates on
the joint coordinates by adjusting the positions in an iterative fashion, the 2D restrictions can be enforced by projecting the joint onto the plane of orientation. That plane
is deﬁned by the root and the (oriented) target position.
An illustration showing how restrictions can be enforced
for a hinge manipulation is given in Fig. 7. Similar techniques can be applied to incorporate constraints for different types of joint, in a variety of motions.
The ability of the constrained version of the algorithm
to converge has not been reduced. If the target is within
the reachable area and there is a joint conﬁguration whichallows the chain to bend enough and reach the target, FABRIK will attain the solution. Obviously, since the chain is
not free from joint restrictions, there are instances where
the target is not reachable. For those instances, there is atermination condition, similar to the unconstrained version, which compares the previous and the current position of the end effector.
5. Experimental results
A target database has been created for the validationand testing of the IK methods. The database consists ofFig. 9. Experimental solutions using some of the most popular IK
methods. The kinematic chains consisted of 10 unconstrained joints,
allowing 3 DoFs on each joint. (a) Initial position, (b) FABRIK, (c) CCD, (d) J.
Transpose, (e) J. DLS, (f) J. SVD-DLS, (g) FTL, (h) Triangulation. Note thatthe link lengths of the resulting FTL posture are not equal to their initialsize.

reachable and unreachable targets, targets with different
distances from the end effectors and targets that movesmoothly in space with end effectors tracking their position. The tests also consist of reconstructing sequenceswith different classes of motion in order to process different swivel angles and axial orientations of the root joint.
The examples are demonstrated in 6 different kinematic
models; a chain with 10 unconstrained joints allowing 3
DoFs on each joint; a chain with 10 constrained joints
allowing limited angle rotations with 3 DoFs; a model containing a ‘Y-shape’ having 10 unconstrained joints and 2
end effectors; a fully unconstrained and un-modelled handwith 26 joints, 3 DoFs on each joint of which 5 are end
effectors and one the root; and a 13 joint humanoid model,

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

Fig. 10. A comparison between the FTL and the FABRIK approaches; the
FABRIK posture is shown in green and the FTL posture in orange. (a) The
FTL algorithm used fewer averaging iterations to calculated the ﬁnal pose,thus the resulting posture has more link length variations, (b) the link
length variation of the FTL algorithm was reduced over several iterations.
Nevertheless, the changes in link size is still signiﬁcant.

in a constrained and unconstrained version, with 3 DoFs oneach joint and 5 end effectors. The IK problem for the handand humanoid model is solved sequentially using closed
loops in a predeﬁned hierarchical order. Fig. 8 shows thedifferent kinematic models used within this work.
IK techniques will mostly work with speciﬁed positions
and orientations of speciﬁc joints, usually the end effectors,
since they are more easily speciﬁed by the animator andtracked by the motion capture system; thereby, they automatically conﬁgure the remaining joints according to different criteria that depend on the model variant and joint
restrictions.
Some of the most popular IK methods have been tested
against FABRIK, such as CCD, Jacobian Transpose, Jacobian
DLS, Jacobian pseudo-inverse DLS (SVD-DLS), FTL and Triangulation. In some of our experiments, we implemented
examples with large distances between target and end
effectors; hence, some methods tend to require more iterations to reach the target and thus the convergence differences are more obvious. The Jacobian and DLS parametervalues used in our experiments are the parameter values
suggested by Buss and Kim [7]; the damping constant
was set to k = 1.1. Several tests and comparisons have been
implemented between the proposed algorithms in respectof their computational cost, processing time, convergence,
the number of iterations needed to reach the target and thereconstruction quality.
5.1. A single end effector
In this section, the methods have been tested on problems with a single end effector and ﬁxed target positions.
These experiments did not include any joint constraints,
but all methods could be enhanced to enforce rotationaland orientational limits. An example with the resulting
postures for each methodology is presented in Fig. 9.
FABRIK produces results signiﬁcantly faster than all IK
methods tested. It is approximately 10 times faster thanthe CCD method and a thousand times faster than the Jacobian-based methods, for these examples with large end
effector movements. FABRIK has the lowest computational
cost and, at the same time, produces visually the smoothest and most natural movements. It needs the fewest iterations to reach the target, it converges faster to the desired

253

position and, when the target is unreachable, it keeps theend effector pointing to the target. On average, FABRIK
needs 15.4 iterations and just 13.2ms to attain a reachable
target and 67 iterations and 62ms for an unreachable target. When the target is unreachable, for this unconstrainedmodel, FABRIK converges to a ﬁnal answer in just 1 iteration and only 0.2ms.
CCD can also be applied in real-time. It is much fasterthan any Jacobian-based method; it needs, on average, 26
iterations and 123ms to reach the target when it is withinreach. On the other hand, when the target is not reachable,
it needs almost 400 iterations and 4sec to converge to its
ﬁnal solution (using the default algorithm without optimisations). However, CCD can often generate unrealistic postures since it can roll and unroll itself before reaching thetarget. CCD also tends to overemphasise the movementsof the joints closer to the end effector of the kinematic
chain.
The Jacobian methods return reasonable results; thereconstructed chain poses are visually more natural than
CCD. Nevertheless, the biggest advantage of the Jacobian
methods over all other methods is that, by default, they
can treat problems with multiple end effectors very easily.
Constraints can be applied within the Jacobian algorithms,
but the way in which these restrictions are incorporated is
not straightforward. Some Jacobian methods also sufferfrom singularity problems, since matrix inverses need tobe calculated. The Transpose and DLS methods do not suffer in this way since they do not use the matrix inverse.
The Jacobian methods also incur high computational cost
making this family of methods non-ideal for real-time
applications. The Jacobian methods generally converge
very slowly to their ﬁnal solutions since they use a linear
approximation with a small step. This is more obvious in
Fig. 11, where the number of iterations needed to reducethe distance between target and end effector as thischanges over time is presented for each methodology. In
this example, the original chain is 900mm long, the distance between target and end effector is 600mm, and thetermination tolerance is 1  103mm.
The FTL algorithm produces poses in real-time and its
resulting postures tend to resemble poses in the ﬁrst stepof the ﬁrst iteration of FABRIK (Fig. 10 and 11 shows a comparison between the FTL and FABRIK methods). However,
the averaging step of the algorithm induced a variation of
the link lengths compared to their initial size (this could
be considered as its major drawback). Even after a large
number of iterations, the length variations still exist. In
cases where the target is unreachable, FTL stretches thechain length in order to reach the target. In addition, theiterations needed to restore the link lengths to their initialsize (in some cases, FTL requires more than double thenumber of iterations of FABRIK) increase the computational cost and the processing time required to achieve a ﬁnal pose. Brown et al. [24] does not provide solutions forproblems with multiple end effectors and targets and, because of the averaging step, it is difﬁcult to incorporate
rotational and orientational constraints.
The Triangulation algorithm incurs a lower computational cost than the CCD algorithm and is substantially faster than the Jacobian methods. However, the resulting

254

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260
4

4

x 10

6

x 10

FABRIK
CCD

5Distance between target andend effector (mm)Distance between target andend effector (mm)

6

4
3
2
1
0

0

5

10

15

20

25

30

J.Transpose
J.DLS
J.SVD−DLS

5
4
3
2
1
0

0

200

400

600

800

1000

1200

Number of Iterations

Number of iterations

Fig. 11. The number of iterations needed to reach the target against the distance between target and end effector as this changes over time.

kinematic chain has a visually unrealistic shape; the joints
close to the end effector are usually in a straight line, withthe emphasis on rotation of the joints neighbouring theroot. Another important drawback of the Triangulation
algorithm is that it cannot be adapted for multiple end
effectors, thus it cannot be used for complex charactermodels. It also suffers from an inability to reach a feasible
solution when joint constraints are applied; the end effector often cannot reach the target, even if there is a solution,
since each joint position is calculated independently without considering the restrictions on the next joint.
Table 1 presents the average runtimes of each of themethods, as well as the number of iterations needed toreach the target, for both cases of a reachable and an
unreachable target. Runtimes are in seconds and were
measured with custom MATLAB code on a Pentium 2
Duo 2.2 GHz. No optimisations were used for any method
reported in the table. It also indicates the time needed
per iteration for each method and how many iterations
per second each methodology can support. An iterationof FABRIK has the lowest computational cost since, insteadof using angle rotations, it treats ﬁnding the joint locations
as a problem of ﬁnding a point on a line.
Fig. 9 compares the performance of each algorithm forsolving Inverse Kinematic problems; it shows the initial
conﬁguration and the goal solution obtained with eachmethodology. The manipulator is fully unconstrained andhas no limits on the range of allowed movement for eachjoint. In each case a position goal is speciﬁed for the end
effector and the Inverse Kinematic problem is solved tovarying degrees of accuracy. Fig. 12 plots the convergenceof each method, meaning the time taken to achieve thesolution with the requested degree of accuracy. It is clearlyobserved that FABRIK converges to the target faster thanany other implemented methodology. Also, Fig. 12 veriﬁes
that FABRIK always converges to the target, if the latter isreachable, in those cases tested.
The FABRIK, CCD, DLS and SVD-DLS methods have also
been tested when the targets are moving in a sinusoidal
trajectory and the end effectors are tracking their positions
when they are within reach, and keeping the end effectors
pointing at the targets when they are unreachable. The
accuracy of the tracking was measured over a period of athousand simulation steps. FABRIK tracks the target inreal-time producing smooth and visually natural motion
without erratic discontinuities. CCD produces reasonable
results within the real-time constraints; however there
are instances where the motion produced is not visuallyrealistic. It is important to mention that CCD’s performance
improves when the target is within a small distance fromthe end effector’s position or the frame rate is high. This
happens because the kinematic chain does not roll and unroll itself. On the other hand, the Jacobian-based methods
can produce oscillating motion with discontinuities. Their

Table 1
Average results (over 20 runs) for a single kinematic chain with 10 joints.
Reachable Target

FABRIK
CCD
Jacobian Transpose
Jacobian DLS
Jacobian SVD-DLS
FTLTriangulation

Unreachable Target

Number of
Iterations

Matlab exe.
time (sec)Time per iteration(in msec)

Iterations
per second

Number of
Iterations

Matlab exe.
time (sec)

15.46126.3081311.190
998.648808.79721.1251.000

0.013280.12356
12.98947
10.48051
9.296520.020450.05747

0.86
4.69
9.90
10.49
11.50
0.97
57.47

1164
213
101
95
87
1033
21

67.564390.135
6549.000
2881.667
2808.452
22.3251.000

0.062073.92869
33.90473
14.87918
15.97591
0.02526
0.06993

255

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

0.35

60
J. Transpose
J. DLS
J. SVD−DLSFABRIK
CCD

0.3

50

0.25

Time (sec)Time (sec)

40
0.2
0.15

30

20
0.1
10

0.05
0

5

1

0.5

0.1

0.05

0.01 0.005 0.001

Tolerance (x10−3 mm)

0

5

1

0.5

0.1

0.05

0.01 0.005 0.001

Tolerance (x10−3 mm)

Fig. 12. An example presenting the time needed for each methodology to achieve the solution with the degree of accuracy requested.

biggest drawback however is the time needed to track thetarget; only under some circumstances, eg using fast C++
matrix libraries, can these kinds of methods reach the goalof real-time application. Fig. 13 presents the performanceof each method on selected frames over time.
The FABRIK algorithm has been also implemented andtested within the Kine [12] application; Kine is a 2D realtime gaming application that initially has a kinematic
chain with six joints. Kine allows you to interact with the
IK solver; you click on the screen and the snake (the kinematic chain is drawn as a snake) moves to solve the IK
problem. There is also an option where you click and dragon the screen and the snake tracks the mouse. Fig. 14
shows examples of the FABRIK and CCD methods implemented within the Kine environment when the end effector moves through large distances. It is clearly observedthat FABRIK out-performs CCD in producing smootherposes.
5.2. Multiple end effectors
Most real models, such as the hand, legged bodies etc,
consist of multiple chains, each chain having at least one
end effector. Hence, it is essential to test our methodology
in cases where more than 1 end effector exists. To test FABRIK under these conditions, we implemented the ‘Yshaped’ multibody pictured in Fig. 15(a), also used in [7],and a hand multibody presented in Fig. 15(b). The ‘Yshape’ multibody has 10 joints with 2 end effectors. The
target positions (the red balls in the ﬁgures) moved insinusoidally varying curves in and out of reach of the multibody. The target positions moved in small increments
and in each time step the joint positions were updated.
The simulations were visually inspected for oscillations
and tracking quality. The end effectors can successfully
track the target positions when they are within reach,and remain pointing at the targets when these are out ofreach. Fig. 15(a) presents a simple example of how FABRIK
performs with multiple end effectors; although it is hard toshow in images, FABRIK can easily track both targets with asmooth motion and without oscillations, shaking or erratic
discontinuities.
Fig. 15(b) shows another example of implementing
FABRIK into a multiple end effector model. This is a fully
unconstrained hand example with 5 end effectors and 26
joints in total, allowing 3 DoFs on each joint. Incorporatinga highly constrained model that also considers the anatomically and physiologically properties of the hand, such as[40], the motion of each joint can be restricted to a feasible
set and the hand will have even more natural movements.
Fig. 16 shows an example of a tracking animation of ahumanoid with 13 joints, 5 of which are treated as end
effectors. In this demonstration, the frame rate was low(3 frames per second); the 3Hz frame rate selection increases the distance between target and end effector, thus
the performance of each method is more obvious. FABRIK
can easily track the animated humanoid in real-time, producing very reasonable results. Fig. 17 shows the reconstruction quality of different methodologies over thesame humanoid model. The differences between theimplemented methodologies, on these unconstrained
humanoid examples, are more obvious on shoulders, elbows and hips. FABRIK produces visually natural postures,
having the smaller reconstruction error compared to theoriginal sequences. These animations have been obtained
from an optical markered motion capture system and havenot been ﬁltered; thus, the algorithm is shown to be robustin noisy environments. Selected internal joints have been
artiﬁcially deleted in order to examine the reconstruction
quality of each methodology. These humanoids do nothave a mesh that deﬁnes their external shape, so self collisions are not considered within these reconstruction
examples.
Table 2 shows the performance (over 20 runs) of eachmethodology for the case of a dancing humanoid model.
The computational cost and the reconstruction quality for
tracking the animated model is also presented. FABRIK
gives the best results with respect to computational costand reconstruction quality; it requires the fewest iterations
to achieve the desired posture and produces visually the256

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

Fig. 14. FABRIK and CCD solution using the Kine application. (a) FABRIK
solution, (b) CCD solution.

Fig. 13. Selected frames during target tracking at 25Hz using different IK
solvers. (a) FABRIK, (b) CCD, (c) J. DLS, (d) J. SVD-DLS

smoothest poses. The median error presented in Table 2 refers to the difference between the estimated joint positions
and the true joint positions.
5.3. Applying restrictions
Most IK problems have rotational and orientational
restrictions since most real world joints have limitations
on their movements. The experimental dataset used to test
the reconstruction quality of the constrained FABRIK is
made up of 10 joints, each having angle rotational restrictions allowing movements only within a range. The same
humanoid model, as described in Section 5.2, is used to
examine the reconstruction quality of the proposed methodology with and without constraints.
FABRIK can be easily constrained producing visuallyrealistic postures without oscillations and discontinuities.

Fig. 15. An example of FABRIK implementation with multiple end
effectors over time; (a) a kinematic chain with 10 unconstrained joints,
2 end effectors and 2 targets, (b) A hand motion example using FABRIK;
this is a fully unconstrained hand example, allowing 3 DoFs on each joint.

The constrained version is slightly slower than its unconstrained counterpart, requiring now almost 3.0ms to reachthe target. Nevertheless, it is still much faster than other IK
methods and approximately 10 times faster than constrained CCD. The reconstruction quality is high, producing
postures with an average error of just over 30mm, almost
half the average error of the unconstrained version. On
the other hand, while it is not difﬁcult to apply manipulator constraints to CCD, the resulting animation often still
has unnatural movements, especially when the target is
at a signiﬁcant distance from the end effector. The unconstrained version of CCD produces different joint posescompared to its constrained version, even if the latter is
not violating the angle restrictions. It is interesting to notethat there are instances where the constrained version of
CCD needs fewer iterations and therefore performs slightly

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

257

Fig. 16. A low rate body tracking example. The joints in red are the known positions of the end effectors and those in blue are the estimated joint positions.
(a) shows the true body poses and (b) the estimated poses using FABRIK.

Fig. 17. Body reconstruction using different IK methodologies. The joints in red are the known positions of the end effectors and those in blue are theestimated joint positions. (a) shows the initial position and (b) the true ﬁnal position. (c) shows the FABRIK solution, (d) the CCD solution, (e) the J.
Transpose solution, (f) the J. DLS solution, (g) the J. SVD-DLS solution

faster than its unconstrained version. This happens because the constraints prevent the chain from rolling andunrolling itself before reaching the target. Fig. 18, shows
examples of FABRIK and CCD implementations with and258

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

Table 2
Reconstruction comparison. Average results (over 20 runs).

FABRIK
CCD
J.Transpose
J.DLS
J.SVD-DLS

Number of
Iterations

Mediantime

Time periterationMedian Error
(mm)

65
67
1352
804
723

1.6
20.5
1928.01533.01494.00.0246
0.30601.43341.90672.066458.68
69.99
137.42
84.84
83.73

This is a MATLAB executable time in msec

Fig. 19. An example of implementation. (a) The initial position, (b) thereal posture, (c) the solution using unconstrained FABRIK, (d) the solution
after incorporating joint restrictions.

Fig. 18. An example of FABRIK and CCD implementations with andwithout incorporating constraints. (a) presents the FABRIK unconstrained
solution and (b) the FABRIK constrained solution. (c) presents the CCD
unconstrained solution, and (d) is the CCD constrained solution.

without joint restrictions. On that example, rotational limits have been applied restricting the allowed bending ofeach joint angle to a maximum value (treated as ball andsocket joints). Fig. 19 shows the reconstruction improvement between an unconstrained and a constrained versionof FABRIK applied to the humanoid model; rotational andorientational constraints have been employed on eachjoint (including the hinge joint technique for elbows andknees) limiting the angle and the twist between limbs toa feasible set.
5.4. FABRIK limitations
During the implementations and testing of the algorithm, no signiﬁcant limitations have been encountered.
Some minor limitations on what joint types the algorithm
supports are mentioned in Section 4.3; however, these limitations can be coped with if more information is provided
about the joint. For instance, in the case of a prismatic joint,
FABRIK can obtain a solution if the ﬁnal inter-joint distanceor its minimum and maximum allowed length are known apriori. A breakdown of the algorithm (a singularity problem) has been also observed when the kinematic chain

was completely straight and the target was located exactly
on that alignment but between the two joints (on the line
which connects two joints). In that case, the chain would
be displaced towards the root but would still be straightafter the forward step of the process. And after the second
step (backward), it would be back at the original place, thus
entering to an inﬁnite loop (a similar problem is encountered in the CCD algorithm). However, this rare singularity
problem can be easily handled by allowing the chain tobend by a very small angle within the user constraints (byrepositioning the target during the ﬁrst backward stage
and then returning it to its original location).
6. Conclusions and future work
IK methods are used to control the postures of articulated bodies in frame animation production. However, mostof the currently available methods suffer from high computational cost and/or production of unrealistic poses. In thispaper, FABRIK, a simple, fast and reliable IK solver is presented. This is the ﬁrst algorithm to use an iterative methodwith points and lines to solve the IK problem. It divides the
problem into 2 phases, a forward and backward reachingapproach, and it supports (to the best of our knowledge)
all the rotational joint limits and joint orientations by repositioning and re-orienting the target at each step. It does not
suffer from singularity problems and it is fast and computationally efﬁcient. No pre-recorded motion database is necessary, thereby avoiding the need for extra memory. Also,a reliable methodology for applying joint restrictions,

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

which supports and utilises all the advantages of FABRIK, ispresented. Our experiments show that FABRIK requires on
average fewer iterations to reach the target than any other
IK method tested, both with constrained and unconstrained
kinematic chains. At the same time, it produces visuallysmooth postures, with and without constraints, reaching
the desired position with very low computational cost.
FABRIK can be also extended to a multiple end effector version supporting multiple kinematic chains. Future work
will see the introduction of the proposed algorithm within
analytically and anatomically correct models. A further
study of the collision problem, with simultaneous studyof more sophisticated joint types, is also essential for the
production of more natural movements.
Acknowledgments
The kine environment presented in Section 5.1 has been
adapted from the work of Jeff Lander [12]; we would like toexpress our enormous thanks to Jeff for giving us permission to use his code and application. We would also liketo thank Richard Wareham, Jonathan Cameron and Charles
Lee for their invaluable discussions and help with capturing data and producing video examples.
Appendix A. Supplementary data
Supplementary data associated with this article can befound, in the online version, at doi:10.1016/
j.gmod.2011.05.003.
References[1] Jianmin Zhao, Norman I. Badler, Inverse kinematics positioning using
nonlinear programming for highly articulated ﬁgures, ACM
Transactions on Graphics (TOG) 13 (4) (1994) 313–336.
[2] A. Balestrino, G. De Maria, L. Sciavicco, Robust control of robotic
manipulators, in: Proc. of the 9th IFAC World Congress, vol. 5, 1984,
pp. 2435–2440.
[3] W.A. Wolovich, H. Elliott, A computational technique for inverse
kinematics, in: The 23rd IEEE Conf. on Decision and Control, vol. 23,
1984, pp. 1359–1363.
[4] J. Baillieul, Kinematic programming alternatives for redundant
manipulators, in: Proc. of the IEEE International Conf. on Robotics
and Automation, vol. 2, March 1985, pp. 722–728.
[5] C.W. Wampler, Manipulator inverse kinematics solutions based on
vector formulations and damped least-squares methods, IEEE
Transactions on Systems, Man and Cybernetics 16 (1) (1986) 93–
101.
[6] Y. Nakamura, H. Hanafusa, Inverse kinematic solutions withsingularity robustness for robot manipulator control, Transactions
ASME, Journal of Dynamic Systems, Measurement, and Control 108(3) (1986) 163–171.
[7] Samuel R. Buss, Jin-Su Kim, Selectively damped least squares forinverse kinematics, Journal of Graphics Tools 10 (3) (2005) 37–49.
[8] Alexandre N. Pechev, Inverse kinematics without matrix invertion,
in: Proc. of the 2008 IEEE International Conf. on Robotics andAutomation, Pasadena, CA, USA, May 19–23 2008, pp. 2005–2012.
[9] Roger Fletcher, Practical Methods of Optimization, second ed., Wiley
Interscience, New York, NY, USA, 1987.
[10] Li-Chun Tommy Wang, Chih Cheng Chen, A combined optimization
method for solving the inverse kinematics problems of mechanicalmanipulators, IEEE Transactions on Robotics and Automation 7 (4)(1991) 489–499.
[11] Chris Welman, Inverse Kinematics and Geometric Constraints for
Articulated Figure Manipulation, Master Dissertation, Simon Fraser
University, Department of Computer Science, 1993.

259[12] Jeff Lander, Making kine more ﬂexible, Game Developer 5 (3) (1998)
15–22.
[13] Adrian A. Canutescu, Roland L. Dunbrack, Cyclic coordinate descent:a robotics algorithm for protein loop closure, Protein Science 12 (5)(2003) 963–972.
[14] Luis Unzueta, Manuel Peinado, Ronan Boulic, Ángel Suescun, Fullbody performance animation with sequential inverse kinematics,
Graphical Models 70 (5) (2008) 87–104.
[15] Ronan Boulic, Javier Varona, Luis Unzueta, Manuel Peinado, Angel
Suescun, Francisco Perales, Evaluation of on-line analytic andnumeric inverse kinematics approaches driven by partial vision
input, Virtual Reality 10 (1) (2006) 48–61.
[16] Richard Kulpa, Franck Multon, Fast inverse kinematics and kinetics
solver for human-like ﬁgures, in: International Conference on
Humanoid Robots, IEEE-RAS, December 2005, pp. 38–43.
[17] Nicolas Courty, Elise Arnaud, Inverse kinematics using sequential
monte carlo methods, in: Proc. of the V Conf. on Articulated Motion
and Deformable Objects, AMDO’08, LNCS, vol. 5098, Mallorca, Spain,
2008, pp. 1–10.
[18] Chris Hecker, Bernd Raabe, Ryan W. Enslow, John Deweese, Jordan
Maynard, Kees van Prooijen, Real-time motion retargeting to highly
varied user-created morphologies, ACM Transactions on Graphics(TOG) 27 (3) (2008) 1–11.
[19] Keith Grochow, Steven L. Martin, Aaron Hertzmann, Zoran Popović,Style-based inverse kinematics, in: SIGGRAPH ’04: ACM Trans. on
Graphics, ACM, New York, NY, USA, August 2004, pp. 522–531.
[20] Robert W. Sumner, Matthias Zwicker, Craig Gotsman, Jovan Popović,Mesh-based inverse kinematics, ACM Transactions of Graphics 24(3) (2005) 488–495.
[21] Kevin G. Der, Robert W. Sumner, Jovan Popović, Inverse kinematics
for reduced deformable models, in: ACM SIGGRAPH, ACM, New York,NY, USA, 2006, pp. 1174–1179.
[22] R. Mü ller-Cajar, R. Mukundan, Triangulation: a new algorithm forinverse kinematics, in: Proc. of the Image and Vision Computing
New Zealand 2007, New Zealand, December 2007, pp. 181–186.
[23] R. Mukundan, A robust inverse kinematics algorithm for animating a
joint chain, International Journal of Computer Applications inTechnology 34 (4) (2009) 303–308.
[24] Joel Brown, Jean-Claude Latombe, Kevin Montgomery, Real-timeknot-tying simulation, The Visual Computer: International Journal ofComputer Graphics 20 (2) (2004) 165–179.
[25] David Hestenes, Garret Sobczyk, Clifford Algebra to GeometricCalculus: A Uniﬁed Language for Mathematics and Physics, D.
Reidel, 1984.
[26] Chris Doran, Anthony Lasenby, Geometric Algebra for Physicists,
Cambridge University Press, Cambridge, UK, 2003.
[27] Andreas Aristidou, Joan Lasenby, Motion capture with constrained
inverse kinematics for real-time hand tracking, in: Proc. of theInternational Symposium on Communications, Control and Signal
Processing, Limassol, Cyprus, March 3–5 2010.
[28] Andreas Aristidou, Joan Lasenby, Inverse kinematics solutions using
conformal geometric algebra, in: L. Dorst, J. Lasenby (Eds.), Guide toGeometric Algebra in Practice, Springer Verlag, 2011.
[29] Andreas Aristidou, Tracking and Modelling Motion for
Biomechanical Analysis, PhD Thesis, University of Cambridge,
Cambridge, UK, October 2010.
[30] Walter Maurel, Daniel Thalmann, Human shoulder modelingincluding scapulo-thoracic constraint and joint sinus cones,
Computers & Graphics 24 (2) (2000) 203–218.
[31] Xuguang Wang, Jean Pierre Verriest, A geometric algorithm topredict the arm reach posture for computer-aided ergonomic
evaluation, Journal of Visualization and Computer Animation 9 (1)(1998) 33–47.
[32] N. Klopcar, M. Tomšič, J. Lenarčič, A kinematic model of the shoulder
complex to evaluate the arm-reachable workspace, Journal of
Biomechanics 40 (1) (2007) 86–91.
[33] Lorna Herda, Raquel Urtasun, Andrew Hanson, Pascal Fua, Automatic
determination of shoulder joint limits using experimentally
determined quaternion ﬁeld boundaries, International Journal of
Robotics Research 22 (6) (2003).
[34] Norman I. Badler, Cary B. Phillips, Bonnie Lynn Webber, Simulating
Humans: Computer Graphics Animation and Control, Oxford
University Press, New York, Oxford, 1993.
[35] Augustus A. White III, Manohar M. Panjabi, Clinical Biomechanics of
the Spine, second ed., J.B. Lippincott Company, 1990.
[36] James Urey Korein, A Geometric Investigation of Reach, MIT Press,
Cambridge, MA, USA, 1985.
[37] Gary Monheit, Norman I. Badler, A kinematic model of the human

260

A. Aristidou, J. Lasenby / Graphical Models 73 (2011) 243–260

spine and torso, IEEE Computer Graphics and Applications 11 (2)(1991) 29–38.
[38] Hans Rijpkema, Michael Girard, Computer animation of knowledgebased human grasping, in; SIGGRAPH ’91: Proc. of the 18th Annual
Conf. on Computer Graphics and Interactive Techniques, ACM, New
York, NY, USA, 1991, pp. 339–348.
[39] Richard M. Murray, S. Shankar Sastry, Li Zexiang, A Mathematical
Introduction to Robotic Manipulation, CRC Press, Inc., Boca Raton, FL,
USA, 1994.
[40] Paris Kaimakis, Joan Lasenby, Gradient-based hand tracking using
silhouette data, in: Proc.of the 3rd International Symposium on
Visual Computing (ISVC), vol. 1, Lake Tahoe, NV/CA, USA, November
26–28 2007, pp. 24–35.
[41] Jonathan Blow, Inverse Kinematics with Quaternion Joint Limits,
Game Developer, April 2002.
[42] Jane Wilhelms, Allen Van Gelder, Fast and easy reach-cone joint
limits, Journal of Graphic Tools 6 (2) (2001) 27–41.

[43] Paolo Baerlocher, Ronan Boulic, Parametrization and range of
motion of the ball-and-socket joint, in: Deformable Avatars,
Kluwer Academic Publishers, 2001. pp. 180–190.
[44] Deepak Tolani, Ambarish Goswami, Norman I. Badler, Real-timeinverse kinematics techniques for anthropomorphic limbs, GraphicalModels 62 (5) (2000) 353–388.
[45] Kiyomi Yamane, Yoshihiko Nakamura, Natural motion animation
through constraining and deconstraining at will, IEEE Transactions
on Visualization and Computer Graphics 9 (3) (2003) 352–360.
[46] Sung Joon Ahn, Wolfgang Rauh, Hans-Jnrgen Warnecke, Leastsquares orthogonal distances ﬁtting of circle, sphere, ellipse,
hyperbola, and parabola, Pattern Recognition 34 (12) (2001) 2283–
2303.
[47] Ming C. Lin, Stefan Gottschalk, Collision detection between
geometric models: a survey, in: Proc. of IMA Conf. on Mathematics
of Surfaces, 1998, pp. 37–56.