Eurographics/ ACM SIGGRAPH Symposium on Computer Animation (2007)

D. Metaxas and J. Popovic (Editors)

Harmonic Skeleton for Realistic Character Animation

Grégoire Aujay1 Franck Hétroy1 Francis Lazarus2 Christine Depraz1

1 EVASION - LJK (CNRS, INRIA and Univ. Grenoble)

2 GIPSA-Lab (CNRS and Univ. Grenoble)

Abstract
Current approaches to skeleton generation are based on topological and geometrical information only; this can
be insufficient for realistic character animation, since the location of the joints does not usually match the real
bone structure of the model. This paper proposes the use of anatomical information to enhance the skeleton. Using
a harmonic function, this information can be recovered from the skeleton itself, which is guaranteed not to have
undesired endpoints. The skeleton is computed as a Reeb graph of such a function over the surface of the model.
Starting from one point selected on the head of the character, the entire process is fast, automatic and robust; it
generates skeletons whose joints can be associated with the character’s anatomy. Results are provided, including
a quantitative validation of the generated skeletons.
Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensional
Graphics and Realism: Animation

1. Introduction back, while the corresponding axis in computer-generated

skeletons is usually centered within the body (see Figure 12).
A common technique for animating a 3D model consists of Moreover, animation skeletons may have some joints which
creating a hierarchical articulated structure, named skeleton do not match any anatomical part of the model but are useful
(or IK skeleton), whose deformation drives the deformation for animation purpose (e.g., on the head, see Figure 2).
of the associated model. The location and displacement of
the skeleton’s joints dictate how the model moves (see Fig-
ure 1 for an example). A skeleton attached to a 3D model
(usually represented as a mesh) can be either created by hand
or computed. In the case of the realistic animation of a char-
acter (be it a human, an animal or a made-up monster), the
first option is most often chosen by artists, although it is
a time-consuming task which needs a skilled user. Indeed,
professional artists may create an initial skeleton relatively
quickly, but often need to make many adjustments during
the rigging process because the skin is very sensitive to the
exact location of the skeleton’s joints: they often have to go
back and forth several times between skeleton skinning and
testing animation before getting it right. Automatic or semi-
automatic methods have several drawbacks: they often allow
little control over the result, they can produce noisy skele- Figure 1: Walking cat. These images are taken from an ani-
tons with unwanted joints, and most importantly they rely mation created using our harmonic skeleton (see the video):
on the topology and the geometry of the model only, which joints deformation drives the mesh deformation.
is not sufficient for realistic animation where the anatomy of
the model does not completely match its geometry. For in- This paper explains how to automatically, robustly and ef-
stance, in most cases the spine of a character is close to its ficiently compute skeletons adapted to realistic character an-

Copyright c 2007 by the Association for Computing Machinery, Inc.

Permission to make digital or hard copies of part or all of this work for personal or class-
room use is granted without fee provided that copies are not made or distributed for com-
mercial advantage and that copies bear this notice and the full citation on the first page.
Copyrights for components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers,
or to redistribute to lists, requires prior specific permission and/or a fee. Request per-
missions from Permissions Dept, ACM Inc., fax +1 (212) 869-0481 or e-mail permis-
[email protected].
SCA 2007, San Diego, California, August 04 - 05, 2007
c 2007 ACM 978-1-59593-624-4/07/0008 $ 5.00
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

Figure 2: From left to right: a cat model, the computed harmonic graph with its symmetry axis, the computed harmonic skeleton
compared to a previously handmade animation skeleton.

imation, starting from a single point selected by the user on Following Shinagawa et al. [SKK91], several authors have
the model. Generated skeletons match the ones that are cre- proposed to use a mathematical tool called the Reeb graph
ated by hand by professionals in most biped and quadruped to capture the model’s topology, before possible refinements
cases. Moreover, they carry anatomical information (that is to capture its geometry. A Reeb graph is defined with respect
to say, we know which joint corresponds to which part of to a mathematical function, and the result highly depends on
the model), allowing a semantic decomposition of the input the choice of this function. In the next section, we precisely
meshes. define the Reeb graph and then list some existing methods
using this mathematical notion.
1.1. Related work
The algorithm we propose takes as input a triangle mesh.
Numerous algorithms have been proposed to compute skele- It first computes a Reeb graph of this mesh, in a fast and
tons of 3D shapes from their geometry. Bloomenthal and robust way (that is to say, the graph’s leaves are only the de-
Lim [BL99] were among the first ones to point out that these sired ones). This abstract graph is then refined and embed-
geometric skeletons can be converted to IK skeletons and ded in the 3D space in order to be useful for realistic char-
then used for animation purposes. However, to be useful for acter animation; this is made possible thanks to a semantic
animation, skeletons should be structured as graphs, whose decomposition of the model, given by the graph. Our algo-
nodes correspond to the joints and whose edges correspond rithm computes the skeleton of a model with several hundred
to their hierarchy. This discards two-dimensional skeletons of thousand faces in no longer than a few seconds on a low-
such as the Medial Axis [Blu67]. end computer.
Graph-like skeleton generation algorithms start either 1.2. Mathematical background
from the boundary surface [KT03, LWM∗ 03, DS06, LKA06,
Let f : M → R be a function defined over a 2-manifold M
TVD06] of the input model, or from its inner volume [GS01,
with or without boundary (that is to say, a surface for which
WP02, CSYB05]. Methods working on a volumetric repre-
each point has a neighboorhood homeomorphic to a disk
sentation of a model have a major drawback: only features
or half-disk). Level sets of f are the sets f −1 (u) = {x ∈
with a size greater than the voxel size can be taken into ac-
M, f (x) = u}. Each of these sets, if it exists, can be con-
count. This often leads to computationally expensive algo-
nected or not. For instance, on Figure 3, where f is a height
rithms.
function, f −1 (u) is connected for low and high values of
Katz and Tal [KT03] extract a skeleton from a meshed u, but is made of several connected components for values
model using a hierarchical decomposition of this mesh into around −0.7, 0 and 0.7. For some special values, the number
meaningful parts. Generated skeletons are star-shaped (they of connected components of the level set changes: these val-
contain a root joint, located in the center of mass of the ues are called critical values, and the corresponding points
model, from which all other joints derive) and thus are not x on the surface are called critical points. The Reeb graph
suited for realistic animation. Lien et al. [LKA06] gener- of f [Ree46] is a graph whose nodes correspond to these
ate shape decomposition and skeleton simultaneously; the critical points, and which encodes the connectivity between
skeleton is computed using centroids and principal axes of them (see Figure 3). In particular, notice that the leaves of
the shape’s components, which gives a skeleton with geo- the Reeb graph exactly match the local maxima and min-
metrically but not necessarily anatomically meaningful po- ima of f . Mathematically speaking, the Reeb graph of f is
sitions. The same problem appears with Dey and Sun’s ro- defined as the quotient space M/ ∼, with ∼ the following
bust skeleton computation from the Medial Axis [DS06]. Liu equivalence relation on M:
et al. [LWM∗ 03] propose to use a repulsive force field to 
position the joints. This method is quite slow (as reported  f (x1 ) = f (x2 )
x1 ∼ x2 ⇐⇒ and x1 and x2 belong to the same
in the paper, it takes several minutes to compute the skele-
connected component of f −1 ( f (x1 ))

ton for a model containing about 10,000 triangles), and does
not guarantee that the result will capture all desired features. More details about these notions can be found in e.g. [FK97].

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

will refer to the graph while joint will refer to the skeleton
and vertex to the mesh.
Our algorithm runs in seven successive stages:
1. the endpoints of the desired skeleton are chosen by the
user or computed (however at least one of them, called
f the source node/joint, must be manually chosen on the
head of the character);
Figure 3: From left to right: a surface, some level sets of f , 2. the harmonic function f solving Laplace’s equation with
the Reeb graph of f . non-homogeneous Dirichlet boundary conditions is com-
puted;
3. the Reeb graph of f is computed with the algorithm de-
scribed in [CMEH∗ 03];
A Reeb graph w.r.t. a triangulated surface with n edges
4. this graph, which we call a harmonic graph since f is
can be computed in O(n log n) time [CMEH∗ 03]. However,
a harmonic function, is subsequently filtered to recover
the choice of the function f is a key issue in revealing infor-
the symmetry of the character’s morphology (i.e., overall
mation about the surface, and several proposals have been
structure);
made in order to obtain a relevant graph: the distance on the
5. starting from the source node, the symmetry axis of the
mesh to a source point [LV99], the integral over the mesh to
graph is detected;
such a distance (in order to avoid the choice of the source
6. the harmonic graph is refined by inserting regular nodes
point) [HSKK01], a mapping function that highlights the
and embedded in R3 : this gives us the harmonic skele-
relevant features [TVD06], etc. Following an idea proposed
ton, which carries anatomical information about the input
by Ni et al. [NGH04], we choose to find a “fair” function
model (such as “this joint corresponds to the tail”);
f , whose extrema will be anatomically significant, by solv-
7. additional heuristics are used in case the model is de-
ing Laplace’s equation 4 f = 0. Steiner and Fischer did the
tected to be a biped or quadruped with sagittally oriented
same [SF01], but their Reeb graph captured neither geomet-
legs (this excludes amphibians, but includes most mam-
rical nor anatomical features, only the topology of the model.
mals), in order to fit the IK skeleton that would be manu-
The main property of such functions f , called har- ally created by an expert. Although not presented in this
monic functions, is their lack of extrema except at boundary paper, equivalent heuristics can be defined for other kinds
points [NGH04]. They also have the following property: of characters, such as birds or insects.
let M be a compact surface, BM its boundary and g : M → R The contributions of this paper are the following:
a function; there exists a unique solution f : M → R to
the following system, called Laplace’s equation with non- • the computed skeleton is robust: endpoints are exactly the
homogeneous Dirichlet boundary conditions: ones that have been chosen, and two meshes represent-
 ing the same model under two different postures generate
4 f (x) = 0 ∀x ∈ M equivalent skeletons;
(1)
f (x) = g(x) ∀x ∈ BM • our algorithm is fast and does not need user intervention,
In our case, BM will be a (disjoint) set of vertices of the except for the selection of the source joint at the very be-
mesh, corresponding to anatomically significant parts of the ginning. However, controlling the skeleton generation is
model. We will compute the Reeb graph of the solution fBM ,g possible, by manually choosing its endpoints or tuning
to the previous system (1), for some function g which will some parameters;
be described in section 2.1.1; thanks to the property of har- • our method gives a semantic decomposition of the shape
monic functions, the leaves of this graph will exactly match (which is used for the embedding process): we know
the chosen vertices: in other words, the graph is guaranteed which part of the mesh corresponds to the head, the legs,
not to be noisy. the trunk and the tail of the character;
• we propose standard skeletons (graphs and their embed-
1.3. Algorithm overview dings) for bipeds and quadrupeds with sagittally oriented
limbs.
The Reeb graph of a function w.r.t. a surface is a pair (V, E)
with V a set of nodes and E ⊂ V ×V a set of edges between Moreover, in the case of quadrupeds, we have validated our
these nodes. It is minimal in the sense that there is no regular results not only visually but also by comparing parameters
node: each node has either one or at least 3 incident edges. with handmade animation skeletons. To our knowledge, this
Moreover, nodes do not have 3D coordinates. Thus, in order is the first time a quantitative validation is proposed.
to construct a skeleton which is suitable for animation from The organization of this paper is as follows: section 2 de-
such a graph, we must embed it in R3 , that is to say link each scribes stages 1 to 4 of our algorithm, that is to say the com-
node with 3D coordinates. Thus, our method first computes putation of the harmonic graph; section 3 explains the con-
a Reeb graph, then embeds it in R3 . In the following, node struction of the harmonic skeleton from the harmonic graph,

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

that is to say stages 5 and 6; in section 4, we detail the pro- neighboring critical points should have two different values
posed skeletons for bipeds and quadrupeds; we give results for f . To ensure this property, we check if all vertices on
and discuss them in section 5; finally, we conclude in sec- the mesh have different values. If several vertices x1 , . . . , xk
tion 6. have the same value f (x1 ) = . . . = f (xk ), we order them and
change their values slightly.
2. Harmonic graph
2.1. Graph computation 2.2. Graph filtering

2.1.1. Finding extrema 2.2.1. Recovering the shape’s symmetries

The first stage of our algorithm is to choose the endpoints of Even if the model is symmetric, Cole-McLaughlin’s algo-
the skeleton; they will correspond to extremal joints. The rithm may generate a non-symmetric graph, because the
user must select one source vertex xsource on the head of source vertex may not be located exactly on the symmetry
the character, which will give the source node of the graph. plane or axis. We propose here a simple way to recover these
We set f (xsource ) = 0. Other endpoints should match rele- symmetries.
vant anatomical features of the character that the user wants Each node n of the graph G is assigned with the value
to animate: hands, feet and possibly tail, ears, etc. These f (x), where x is the critical vertex on the surface correspond-
endpoints can be either selected manually, or computed. In ing to n. Now, let us give weights to the edges of G. Let
the latter case, we try to find vertices x such that the dis- (n1 , n2 ) be an edge of G. (n1 , n2 ) is balanced by the follow-
tance d(xsource , x) on the mesh is locally maximum. Several ing weight:
methods have been proposed to solve this problem: for in-
stance, Dong et al. [DKG05] choose to solve the Poisson | f (n1 ) − f (n2 )|
w(n1 , n2 ) = (2)
equation 4 f = −k4xk; the algorithm proposed by Tierny | max f (n) − min f (n)|
n∈G n∈G
et al. [TVD06] can also be applied, but it does not use the
Considering f as an approximated distance to the source ver-
source vertex, which should be selected afterwards among
tex over the mesh (see section 2.1.1), w(n1 , n2 ) represents
the detected feature vertices, hence it does not ensure this
the normalized difference between the distance to the source
vertex will be on the head of the character. The same prob-
vertex of two “topologically close” vertices. If w(n1 , n2 ) is
lem arises when computing the average geodesic distance
small, this means that the corresponding vertices x1 and x2
function over the mesh, as did Zhang et al. [ZMT05]. In our
are approximately at the same distance to the source vertex,
implementation, we use a fast and more straightforward so-
and are also located in the same topological area (they are
lution: g is defined as a geodesic distance to xsource ; we use
not necessarily geometrically close to each other). Thus, in
Dijkstra’s algorithm to compute shortest paths on the mesh
order to recover the shape’s symmetries, we propose to filter
from the source vertex to all other vertices, as proposed by
the graph by collapsing every internal edge with a weight
Lazarus and Verroust [LV99]. This method, as Dong’s, has
lower than a given threshold t1 . We do not collapse edges
one drawback: multiple neighboring local extrema can be
containing a leaf node, since this could remove small fea-
found in almost flat regions. We propose a solution to clus-
tures.
ter these extrema, which will be discussed in section 2.2.
For each extremum vertex x (be it manually or automatically Notice that we can recover not only geometrical symme-
chosen), the value f (x) is set to the length of the shortest tries of the model, but also morphological ones: for instance,
path from the source vertex, as computed by Dijkstra’s al- the octopus model of Figure 4 is not symmetric, geometri-
gorithm (it could also be set to the value given by Dong’s cally speaking, because its tentacles are not in the same po-
method when using this algorithm). Doing so, the harmonic sition; it can however be regarded as morphologically sym-
function f can be seen as a smooth approximated distance to metric, because these tentacles have the same size and are
the source vertex over the mesh. regularly placed around a symmetry axis. As shown on the
same model, we can recover not only symmetries w.r.t. a
2.1.2. Solving Laplace’s equation plane but also symmetries w.r.t. an axis.
Once the boundary conditions to Laplace’s equation are set,
the system (1) is solved using a classical finite elements 2.2.2. Removing irrelevant extrema
method of P1 type (the function f , defined for each vertex, is As explained in section 2.1.1, it may happen that too many
linearly interpolated inside each triangle). Since the assem- extremum vertices are computed. In order to remove irrel-
bled matrix is very sparse, computation can be done very evant extrema, since extrema correspond exactly to the leaf
efficiently (e.g. using the SuperLU solver [DEG∗ 99]). nodes of the graph, we propose to remove the external edges
(that is to say edges containing a leaf node) with a weight
2.1.3. Generating the graph lower than a given threshold t2 , together with their nodes.
The Reeb graph of f is then computed using Cole- However, these edges should be removed carefully (see Fig-
McLaughlin’s algorithm [CMEH∗ 03]. This algorithm re- ure 5): in order to avoid extra deletion of edges, they should
quires f to be a Morse function: this basically means that two first be ordered by increasing weight.

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

We propose here a heuristic to recover this symmetry axis

starting from the source node, which is located on this axis
since its corresponding vertex is supposed to be on the head
of the character.
Finding symmetries on a graph is a NP-complete prob-
lem; that is why we must make some hypotheses about the
graph to get an efficient algorithm. Several restrictions have
Figure 4: Left: non-symmetric graph obtained from a model been proposed in the graph theory community [DeF99]; we
containing a symmetry. Middle: the same graph after filter- describe here a simple iterative algorithm based on the 3 fol-
ing (t1 = 0.007). Right: refined harmonic skeleton. lowing assumptions:
1. the source node is located on the symmetry axis;
2. the harmonic graph is actually a tree, i.e. it does not con-
tain any cycle;
3. two subtrees are isomorphic if they have the same depth
and if their root nodes have the same degree (that is to
say, the same number of child nodes).
The two last hypotheses are relevant for our application,
Figure 5: Deletion of edges whose weight is lower than or since harmonic graphs are usually simple: they are made of
equal to t2 = 0.15. Top: without weight ordering. Bottom: one node for the head, one node for each leg, possibly one
with weight ordering. extremal node for the tail, for each ear and/or each wing
and/or each finger, and that is usually all.
We use n0 to denote the source node of the harmonic
graph, and (n0 , n1 ) = e0 as its incident edge: e0 is on the
Both thresholds t1 and t2 can be set by the user, but they
symmetry axis. n and n0 denote nodes of the harmonic graph,
can also be computed. Indeed, unwanted edges usually have
whereas e denotes an edge. Our algorithm proceeds as fol-
very small weights compared to the others’, since they can
lows:
be seen as noise while the others are associated with feature
sizes. Thus, a statistical analysis upon all the edge’s weights • e = (n, n0 ) ← e0 = (n0 , n1 )
can help to set these parameters. • while e 6= NULL loop

3. Harmonic skeleton – add e to the symmetry axis;

– let e1 = (n0 , n01 ), e2 = (n0 , n02 ), . . . , ek = (n0 , n0k ) be the
The harmonic graph gives the topological structure of the incident edges to n0 , excepting e;
model. This is not enough to get an animation skeleton: we – for each node n0j , let T j be the subtree of G whose root
need to add 3D coordinates to its nodes, which will repre-
node is n0j and which does not contain n0 ;
sent the joints of the skeleton; we may also need to refine
– store the T j into sets S1 , . . . , Sl of isomorphic trees,
the graph. Previous methods constructed the skeleton from
according to assumption number 3;
a Reeb graph using only topological and geometrical infor-
– if ∃!Si which contains only one tree Ti then e ← ei =
mation from the model, which is often not sufficient for real-
(n0 , n0i )
istic animation. We propose to take benefit from anatomical
– else e ← NULL
information to design the skeleton; this information will be
– end if
recovered from the harmonic graph, knowing that the source
vertex was chosen on the head of the character. In this sec- • end loop
tion, we explain how to detect symmetries of the model’s
Figure 6 shows the successive steps of the algorithm on
morphology on the graph and propose a skeleton in general
an example. It adds edges to the symmetry axis iteratively,
case. In the next section, we show how to improve this gen-
discarding subtrees of the harmonic graph that are symmet-
eral skeleton in the case of biped and quadruped characters.
ric w.r.t. the computed part of the axis. Note that if several
3.1. Symmetry axis detection sets Si containing one tree exist at the same time the algo-
rithm stops, because it cannot tell which tree has its root on
We suppose here that the character’s morphology is symmet- the axis. This algorithm can be applied not only to the har-
ric. This is often the case: typically, the model has two or monic graph G, but also to subtrees of G, in order to find
four legs, two ears, and the head and the tail (if it exists) are non-principal symmetries. We can thereby obtain a hierar-
centered with respect to the legs. Thus, the harmonic graph chy of symmetries, like [SKS06].
should also be symmetric with respect to an axis (or a node,
but a node can be considered as a degenerate case of an axis).

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

(a) (b) (c) (d)

Figure 6: Symmetry axis detection. (a) Initialization
(b) First step: T1 and T3 are isomorphic trees, and T2 is not
isomorphic to any other known tree: e2 = (n1 , n02 ) is on the (a) (b)
symmetry axis. (c) Second step: T1 and T2 are isomorphic, Figure 7: (a) Some nodes may have more than one corre-
there is no candidate tree to process further on, so the algo- sponding vertex on the mesh. (b) Added regular nodes and
rithm stops. (d) Detected symmetry axis. possible embedding for internal nodes with 3 incident edges.

3.2. Simple embedding • if there is none, embed n onto the center of mass of
Finding an appropriate embedding for each node of the har- the n0i ’s embeddings;
monic graph is not a trivial task: even if each extremal node • if there is one, embed n onto the embedding of this
can be embedded onto the corresponding vertex on the mesh, node n0k ;
this is not always possible for internal nodes, since they • if there are two (three or more is not possible), choose
may have more than one corresponding vertex (Figure 7 (a)). one of them, embed n onto its embedding and remove
Moreover, it is often more relevant to embed an internal node the other node from the graph;
inside the model than on the surface. Before giving details 5. finally, freeze the new edges (n, n0i ): this means that if one
about how internal nodes will be embedded in R3 , we should node’s embedding is subsequently modified, the other
explain how regular nodes (nodes with exactly two incident should be modified the same way.
edges) that will be inserted to the graph will be embedded.
Figure 7 (b) shows the possible embeddings for internal
Let u be a regular value of f (that is to say a non-critical nodes with 3 incident edges. Freezing edges has an impor-
value), let f −1 (u) be its level set, and let C be a connected tant meaning: some degrees of freedom are removed for
component of f −1 (u). C is a simple closed curve made of some joints of our animation skeleton, and freezing allows
segments whose endpoints p1 , p2 , . . . , pk , pk+1 = p1 inter- us to mirror the effect of bones such as the clavicle or the
sect the edges of the mesh. We define the center of C as the pelvis.
center of mass of these segments [LV99]:
k
3.3. Joint hierarchy
pi + pi+1
∑ kpi pi+1 k 2 Embedding the graph’s nodes in R3 is not sufficient to get an
i=1
center(C) = (3) applicable animation skeleton: we should also define a joint
k
hierarchy. This can easily be done using the detected sym-
∑ kpi pi+1 k metry axis on the harmonic graph: the base joint can corre-
i=1
spond to any node on this axis, then other joints recursively
We embed a regular node with value f (u) onto the center of
come from it. Common base joint choices include the head,
its associated connected component C. This choice is more
that is to say the source joint, a node on the symmetry axis
relevant that the center of mass of the points pi , since the
with a mean value for f , or the pelvis, which is the last node
result is less dependent on the surface’s discretization level.
on the symmetry axis with at least three incident edges.
Now, here is the algorithm we propose in order to embed
Once we have set up this hierarchy, we can use our embed-
an internal node n:
ded and augmented harmonic graph, which we call harmonic
1. split each incident edge (n, ni ) to n in two, by inserting a skeleton, as animation skeleton: nodes will be used as joints.
new node n0i ; The direction of the symmetry axis (or more precisely, of
2. assign the value f (n) + ε or f (n) − ε to each n0i , depend- its embedding) can be used to set up the initial orientation of
ing whether f (n) < f (ni ) or f (n) > f (ni ) (ε should be a each joint. Moreover, additional joints can be added in a very
small scalar value, lower than the lowest weight among simple way as regular nodes on the graph, with the embed-
the graph’s edges); ding described in section 3.2. The value for f corresponding
3. since each node n0i is a regular node, embed it as ex- to a new joint, and hence its exact location, can be either set
plained before; up by the user, or computed as the mean value between the
4. determine which nodes among these are on the symmetry two values of the edge’s nodes (this is our default choice), or
axis: even computed so that the joint fits some geometrical feature

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

(e.g. local minimum of the gaussian curvature, as proposed quadrupeds can be classified into two groups, according to
by [TVD06]). the orientation of their leg bones (see Figure 9): in the case
of amphibians these bones approximately lie in a transversal
4. Adapted embedding for bipeds and quadrupeds plane (plane with constant altitude), while in the case of
In this section, we explain how the previously computed most mammals they lie in a sagittal plane (orthogonal to
skeleton can be modified in order to better fit biped or S1 S2 and P1 P2 ). While our test is adequate for “sagitally
quadruped mammals. Equivalent heuristics can be devel- oriented” quadrupeds, it can fail for amphibians, for which
oped for other kinds of characters. These heuristics rely on the result can be the same than for bipeds: |Spine.NP | ≈ 0
semantic information about the model’s anatomy associated and |Spine.NS | ≈ 0.
to each joint of the skeleton, which can be recovered since
the source joint corresponds to the head of the character and
all skeleton extrema are known (see Figure 8 (a)). First, we
propose a heuristic to check if the skeleton corresponds to a
biped or a quadruped model.
(a) (b)
4.1. Biped/quadruped discrimination Figure 9: (a) Schematic skeleton of an amphibian: the leg
In the case of a biped or quadruped character, the computed bones are in a tranversal plane (z = cst). (b) Mammal case:
harmonic graph should be as described in Figure 8 (a): the they are in a sagittal plane (x = cst).
symmetry axis should have at least 2 nodes with at least 3
incident edges. The last of these nodes P matches the pelvis, 4.2. Biped embedding
and the previous one S matches the shoulders (we can have
others, matching for example the ears). Since P and S have 3 If the character has been detected as a biped, we propose a
or 4 incident edges, we know from section 3.2 that the ones special refinement of the harmonic skeleton. This refinement
not on the symmetry axis have been frozen: let P1 , P2 , S1 and starts with the addition of several nodes to the graph:
S2 be their other endpoints; these nodes correspond to the be- • the spine, that is to say the edge SP, is subdivided into 4;
ginning of the leg bones (when the subtree corresponding to • a new node N is inserted on the symmetry axis before S;
the tail is isomorphic to the back legs, P1 and P2 are cho- • a new node J is inserted before N, and a new edge JM is
sen among the three children of P so that |SP.(PP1 × PP2 )| added from J (M is a new extremum of the graph);
is maximum). We can now define 3 unit vectors: the spine • each arm and each leg is subdivided into 3 edges;
SP • if there is a tail, it is subdivided into 4 edges.
direction Spine = kSPk , a unit vector NP normal to the trian-
gle PP1 P2 and a unit vector NS normal to the triangle SS1 S2 . The goal of this refinement is to match what would have
Since edges PP1 , PP2 , SS1 and SS2 are frozen with f (P1 ) ≈ created an artist. The nodes added to each arm will match
f (P2 ) ≈ f (P) and f (S1 ) ≈ f (S2 ) ≈ f (S), we say that the elbows and wrists, while the nodes added to each leg will
model is a quadruped if |Spine.NP | ≈ 1 and |Spine.NS | ≈ 1, match knees and ankles; N will match the base of the neck, J
and a biped if |Spine.NP | ≈ 0 and |Spine.NS | ≈ 0 (see Fig- the jaw and M the mouth. Notice that the source node and M
ure 8 (b) and (c)). In the other cases, we cannot conclude. do not match any real joint: these are in fact useful to better
control the movement of the head and its size. We choose
not to add edges for the rib cage, as it is not usually modeled
for IK skeletons.
In order to shift some node embeddings and to embed the
newly inserted nodes, we first give a reference frame to the
model. This reference frame is defined by the previously in-
troduced unit vector Spine, the unit vector kPP1 PP2 k and the
1 2

unit vector Spine × kPP1 PP2 k , which gives the front-to-back (or
1 2
back-to-front) direction. We can then embed newly inserted
(a) (b) (c) nodes, such as the nodes of the spine which can be slightly
moved backward. To mimick what an artist would do, we
Figure 8: (a) Minimal harmonic skeleton for a biped or a have also chosen to unfreeze the SS1 and SS2 edges,and to
quadruped model. The symmetry axis is colored in purple embed S1 and S2 ahead of the embedding of S, in order to
and frozen edges are colored in orange. (b,c) Spine, NP and match clavicles. Regular nodes can be embedded either us-
NS vectors for quadrupeds and bipeds. ing a mean Euclidean position or a mean value for f w.r.t. the
embeddings of their edge’s endpoints, or fitting some geo-
Actually, this heuristic is well-adapted for most metric criterion, such as proposed by [TVD06]. The last so-
quadrupeds, but not all. Indeed, vertebrate terrestrial lution can be particularly adapted for neck and wrists, which
match constrictions of the shape.

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

4.3. Quadruped embedding a close but regular value for f and the definition (3) of the
center of a connected component.
Automatic animation skeleton generation is much less de-
veloped for four-footed animals than for bipeds. In order Results on two quadruped models are shown on figures 2
to refine the harmonic skeleton for parasagittally oriented and 12. The cat’s tail is not considered as part of the sym-
quadrupeds, we based our work on the reference animation metry axis, since its corresponding subtree on the harmonic
skeletons proposed by [RFDC05]. These IK skeletons were graph is isomorphic to the back legs. Our algorithm provides
constructed by hand, from anatomical references [Cal75]. animation skeletons close to the model’s anatomy and to tra-
We add the same nodes to the harmonic graph as for bipeds, ditional IK skeletons. Nevertheless, some joints may need to
except that each front leg is subdivided into 5 edges, each be slightly displaced for better animation, particularly in the
back leg into 4 edges, and instead of having 2 edges between head. It is also noticeable that the very beginning of the tail
J and S (JN and NS), we have 5: the 4 added nodes will is actually included in a frozen edge; this is correct since it
match the first, the second, the fourth and the seventh (which corresponds to the first coccygeal vertebrae which are indeed
is the last) cervical vertebrae. We also subdivide the edge attached to the sacrum [Cal75].
starting from the source node in 3; the first inserted node J 0
Our harmonic skeletons have been used for animation, as
will match the jaw, while this time J will match the cranium.
can be seen on Figure 1 and on the accompanying video.
As for bipeds, M does not match any real joint and is useful
to control the head’s size and its movement. It will be put on 5.2. Robustness
top of the head of the character. We use the same reference
frame as for biped embedding; here is how some of the joints Figure 10 shows the robustness of the skeleton generation
are embedded: P is lifted up along the Spine × kPP1 PP2 k direc- w.r.t the pose, mesh deformation and source vertex location.
1 2
tion from the simple embedding position (the center of its Two different poses of the same character generate the
−1
connected component for f ( f (P))) in order to be close to same graph, with approximately the same values for f on
the back; nodes on SP are also lifted up, and so are S1 , S2 , P1 each node, as long as the model is not stretched from one
and P2 ; S is lifted up in order to match the pelvis’ height; the to the other. The reason is twofold: we are guaranteed that
first inserted nodes on each leg are moved along the −Spine the extremal nodes correspond to the selected or computed
direction. We found that the best choice to embed the node extremal vertices, and f can be approximated as a distance
J was near the neck constriction (actually a bit closer to the over the mesh to the source vertex. Then, the embedding is
source joint); its value for f and exact location depends on most often the same since it does not depend on the leg ori-
the neck length. Finally, a simple solution for J 0 is along the entation, for instance: it depends mostly on the computed
−Spine × kPP1 PP2 k direction from J, close to the chin. reference frame, which is the same except if the back has
1 2
been bended. It can also depends on the surface’s local ge-
5. Results and validation
ometry, if we use constrictions to fix some joints such as the
Figures 2 and 10 to 12 show harmonic skeletons computed neck and wrists.
with our method. In these cases extrema have been selected
If the pose deformation is not isometric, we cannot be sure
by hand, because automatic computation of the extremal fea-
to get the same harmonic graph, from a theoretical point of
tures can be quite slow. Thus, the threshold t2 has not been
view. However, stretching or shortening one leg in a homo-
used (it has been set to zero). No fine tuning of t1 has been
geneous way does not change neither the graph nor its em-
necessary: for almost all models, setting t1 between 0.001
bedding, since for instance the ratio forearm length over arm
and 0.150 is sufficient. Except the selection of the extrema
length is not modified.
and t1 , the entire process is automatic; no post-processing
has been applied.

5.1. Biped and quadruped embeddings

Figure 11 shows the harmonic skeleton computed from a
biped model, compared with a standard handmade skeleton
(from Autodesk’s Maya software). We have not modeled the
rib cage, as explained before. As for the other models, the
symmetry axis is colored in purple and frozen edges are col-
ored in orange. Even though the graph is more complex than
the minimal harmonic graph for a biped (Figure 8 (a)) be- Figure 10: Robustness of the skeleton generation w.r.t the
cause we decided to model the fingers, the symmetry axis pose (left), mesh deformation (middle) and the source vertex
has been correctly detected. Another biped skeleton is shown location (right). Compare to Figure 11.
on the right of the figure. We have chosen to embed extremal
nodes onto corresponding vertices on the mesh, but we could
have easily embedded them inside the model instead, using Our skeleton computation is also very robust w.r.t the

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

Figure 11: Comparison on a standard biped model, MayaHuman, between a standard IK skeleton (left) and our harmonic
skeleton (middle left). Middle right: hand close-up; right: harmonic skeleton for another biped model, MaleWB.

[Liu et al. 2003] [Lien et al. 2006] [Tierny et al. 2006] Our method Horse anatomy
Figure 12: Comparison on a horse model between several methods. Images are taken from the papers; the right image is taken
from Wikipedia.

source vertex location, as long as it is chosen on the head: graph computation is then done in O(n log n) time for a mesh
even if it is not on the character’s symmetry plane, the sym- with n faces [CMEH∗ 03], and embedding is done in nearly
metry axis of the harmonic graph is recovered; then, since linear time because we only compute ray/mesh intersections
the embedding we propose does not depend on the source for some joints in order to get their distance to the mesh, and
vertex location, it does not change. the number of joints does not depend on the mesh’s com-
plexity.
5.3. Quantitative validation
Mesh Back leg Front leg Neck
To prove that our approach is useful, we have carried out a Harmo. IK Harmo. IK Harmo. IK
quantitative validation of our results: since [RFDC05] intro- Cat 1.2 1.3 1.2 1.2 0.4 0.4
duced parameters to define quadruped’s skeletons (back and Cow 1.0 1.1 0.9 0.9 0.3 0.4
front leg height – or similarly spine tilt – and neck length, Dog 1.3 1.3 1.1 1.2 0.5 0.4
normalized by the spine length), we compared their values Elephant 1.4 1.6 1.4 1.4 0.3 0.3
between our skeletons and IK skeletons, handmade from Horse 1.3 1.7 1.4 1.6 0.7 1.0
anatomical reference. Results for 6 models are provided in Panther 1.0 1.1 0.9 1.0 0.4 0.5
Table 1; in most cases our embedding of nodes S and J is Table 1: Parameter comparison between our harmonic
correct, resulting in similar values between harmonic skele- skeletons and hand-built IK skeletons.
tons and IK skeletons for front leg height and neck length.
The location of the pelvis is sometimes low in our harmonic
skeletons, which explains the greater difference for back leg Mesh Nb. faces Graph Embedding Total
height. Cat 2,566 0.085 0.108 0.193
MayaHuman 14,118 0.634 0.139 0.773
5.4. Computation time Octopus 33,058 1.393 0.061 1.454
Horse 96,966 6.268 3.525 9.793
The Table 2 gives computation times for 5 models on a stan- MaleWB 296,272 30.816 5.230 36.046
dard PC with a 2.4 GHz Pentium 4 processor. Even for a
dense mesh, our algorithm generates the skeleton in less than Table 2: Computation time (in seconds) for some meshes.
1 minute. The memory requirement is also low: at most 350
6. Conclusion
MB for a model made of 300,000 faces, 1.5 MB for a model
with 15,000 faces (including the storage of the mesh). Most In this paper we have presented a fully automatic method to
of the time is spent on the harmonic function computation; compute an animation skeleton from a 3D meshed model in

c Association for Computing Machinery, Inc. 2007.
 G. Aujay, F. Hétroy, F. Lazarus & C. Depraz / Harmonic Skeleton for Realistic Character Animation

a few seconds after the selection of an initial point. In the [DeF99] D E F RAYSSEIX H.: An heuristic for graph symmetry de-
case of most bipeds or quadrupeds, this skeleton fits the ani- tection. In Symposium on Graph Drawing (1999), pp. 276–285.
mation skeleton that would be hand-built by an expert start- [DEG∗ 99] D EMMEL J., E ISENSTAT S., G ILBERT J., L I X., L IU
ing from anatomical boards, and is thus adapted for realistic J.: A supernodal approach to sparse partial pivoting. SIAM Jour-
animation. The main idea is to construct the Reeb graph of nal on Matrix Analysis and Applications 20, 3 (1999), 720–755.
a harmonic function, which gives the overall morphological [DKG05] D ONG S., K IRCHNER S., G ARLAND M.: Harmonic
structure of the model (especially its symmetry axis), then to functions for quadrilateral remeshing of arbitrary manifolds.
refine and embed it using anatomical information. There are Computer Aided Geometric Design, Special issue on Geometry
two main restrictions on the input mesh: it should be a trian- Processing 22, 5 (2005), 392–423.
gulated 2-manifold (with or without boundary), and, in order [DS06] D EY T., S UN J.: Defining and computing curve-skeletons
to recover the symmetry axis of the shape’s morphology, it with medial geodesic function. In Symposium on Geometry Pro-
should not have handles (otherwise the Reeb graph contains cessing (2006), pp. 143–152.
cycles). Although the method is fully automatic, the user can [FK97] F OMENKO A., K UNII T.: Topological Modeling for Vi-
control the skeleton generation by tuning a few optional pa- sualization. Springer-Verlag, 1997.
rameters. This tool has been designed both to help artists and [GS01] G AGVANI N., S ILVER D.: Animating volumetric models.
to allow non-experts to quickly generate skeletons which can Graphical Models 63, 6 (2001), 443–458.
be used for realistic character animation. Computed skele- [HSKK01] H ILAGA M., S HINAGAWA Y., KOMURA T., K UNII
tons can be edited and refined, for instance to add joints that T.: Topology matching for fully automatic similarity estimation
correspond to wings or to the trunk of an elephant. of 3d shapes. In SIGGRAPH (2001), pp. 203–212.
Given this skeleton generation process, we see three [KT03] K ATZ S., TAL A.: Hierarchical mesh decomposition us-
promising research directions. First, each vertex of the mesh ing fuzzy clustering and cuts. In SIGGRAPH (2003).
is related to the joints of the skeleton, since we have given [LKA06] L IEN J., K EYSER J., , A MATO N.: Simultaneous shape
values for the harmonic function to the graph’s nodes, and decomposition and skeletonization. In ACM Symposium on Solid
hence the skeleton’s joints; these relations may be used to and Physical Modeling (2006), pp. 219–228.
enhance skinning weights. Second, our semantic decompo- [LV99] L AZARUS F., V ERROUST A.: Level set diagrams of poly-
sition of the graph may also be used to define heuristics that hedral objects. In ACM Symposium on Solid Modeling (1999).
give adapted skinning weights: weights may vary according [LWM∗ 03] L IU P., W U F., M A W., L IANG R., O UHYOUNG M.:
to the meaning of neighboring joints. It may also help for Automatic animation skeleton construction using repulsive force
automatic mesh segmentation into anatomically meaningful field. In Pacific Graphics (2003), pp. 409–413.
regions. Finally, even if not embedded to match the model’s [NGH04] N I X., G ARLAND M., H ART J.: Fair morse functions
anatomy, the harmonic graph may be useful for other appli- for extracting the topological structure of a surface mesh. In SIG-
cations (e.g. shape matching), since its construction is robust GRAPH (2004), pp. 613–622.
and does not create unnecessary nodes. [Ree46] R EEB G.: Sur les points singuliers d’une forme de pfaff
complètement intégrable ou d’une fonction numérique. Comptes-
Acknowledgments Rendus de l’Académie des Sciences 222 (1946), 847–849.
The authors would like to thank Lionel Revéret for interest- [RFDC05] R EVÉRET L., FAVREAU L., D EPRAZ C., C ANI M.:
ing discussions at the beginning of this work. The horse and Morphable model of quadruped skeletons for animating 3d ani-
MaleWB models are courtesy of Cyberware. The MayaHu- mals. In Symposium on Computer Animation (2005).
man model is courtesy of Autodesk. [SF01] S TEINER D., F ISCHER A.: Topology recognition of 3d
closed freeform objects based on topological graphs. In Pacific
References Graphics (2001), pp. 82–88.
[BL99] B LOOMENTHAL J., L IM C.: Skeletal methods of shape [SKK91] S HINAGAWA Y., K UNII T., K ERGOSIEN Y.: Surface
manipulation. In Shape Modeling International (1999). coding based on morse theory. IEEE Computer Graphics and
[Blu67] B LUM H.: A transformation for extracting new descrip- Applications 11, 5 (1991), 66–78.
tors of shape. In Symposium on Models for the Perception of [SKS06] S IMARI P., K ALOGERAKIS E., S INGH K.: Folding
Speech and Visual Form (1967), pp. 362–380. meshes: Hierarchical mesh segmentation based on planar sym-
[Cal75] C ALDERON W.: Animal Painting and Anatomy. Dover, metry. In Symposium on Geometry Processing (2006).
1975. [TVD06] T IERNY J., VANDEBORRE J., DAOUDI M.: 3d mesh
skeleton extraction using topological and geometrical analyses.
[CMEH∗ 03] C OLE -M C L AUGHLIN K., E DELSBRUNNER H.,
In Pacific Graphics (2006), pp. 409–413.
H ARER J., NATARAJAN V., PASCUCCI V.: Loops in reeb graphs
of 2-manifolds. In Symposium on Computational Geometry [WP02] WADE L., PARENT R.: Automated generation of control
(2003), pp. 344–350. skeletons for use in animation. The Visual Computer 18 (2002).
[CSYB05] C ORNEA N., S ILVER D., Y UAN X., BALASUBRA - [ZMT05] Z HANG E., M ISCHAIKOW K., T URK G.: Feature-
MANIAN R.: Computing hierarchical curve-skeletons of 3d ob- based surface parameterization and texture mapping. ACM
jects. The Visual Computer 21, 11 (2005), 945–955. Transactions on Graphics 24, 1 (2005), 1–27.

c Association for Computing Machinery, Inc. 2007.