Animation of Deformable Models Using Implicit Surfaces.
AbstractThis paper presents a general approach for designing and animating complex deformable models with implicit surfaces. Implicit surfaces are introduced as an extra layer coating any kind of structure that moves and deforms over time. Offering a compact definition of a smooth surface around an object, they provide an efficient collision detection mechanism. The implicit layer deforms in order to generate exact contact surfaces between colliding bodies. A simple physically based model approximating elastic behavior is then used for computing collision response. The implicit formulation also eases the control of the object's volume with a new method based on local controllers.We present two different applications that illustrate the benefits of these techniques. First, the animation of simple characters made of articulated skeletons coated with implicit flesh exploits the compactness and enhanced control of the model. The second builds on the specific properties of implicit surfaces for modeling soft inelastic substances capable of separation and fusion that maintain a constant volume when animated.
Introduction
In traditional animation systems based on key-framing,
specifying the motion and the successive shapes of objects
interacting with a simulated world, requires a great amount
of specialized knowledge and intuition from the animator.
Models based on simplified physical laws have been proposed
for automating these tasks. They generate motion
and deformation from initial conditions and from a set
of externally applied forces over time, and automatically
detect and respond to collisions. These models are particularly
appropriate for facilitating the animation of deformable
objects. They can either be used alone for the
simulation of inanimate bodies, or be combined with user-controlled
structures as has been done for instance in character
animation [25], [7].
This paper shows that a number of problems that are
di#cult to solve with previous models can be easily handled
by combining them with an external deformable layer
based on implicit surfaces. Indeed, the implicit formulation
defines a smooth surface around the object that can
be used to perform e#cient collision detection, to enable
exact contact modeling, and to ease volume preservation.
This approach leads to a variety of applications such as
the animation of elastic bodies, the modeling of soft substances
that can separate or melt, or the animation of sim-
iMAGIS is a joint project of CNRS, INRIA, Institut National Polytechnique
de Grenoble and Universite Joseph Fourier.
ple characters made of articulated skeletons coated with an
implicitly specified volume.
A. Related work
Deformable models give a method for computing the alteration
of an object's shape due to a set of externally
applied forces. Deformations may be elastic or inelastic
depending on whether the original shape is restored when
external forces are removed. Most deformable models in
Computer Graphics result from "nodal approaches", in the
sense that they approximate deformations by the displacements
of elementary nodes inside a flexible body. Some of
them derive from the elasticity theory. Di#erential equations
of motion are discretized in space, and then integrated
over time by resolving a matrix equation at each time step.
This scheme has been used for modeling both elastic [37],
[39], [19] and inelastic [36] deformations. However, since
the topology of the network of nodes does not vary over
time, this approach is restricted to the animation of structured
objects. A solution for modeling soft inelastic bodies
that absorb deformations and may separate into pieces or
melt during an animation is a physically-based particle system
[26], [38], [40], [24]. In this case, a set of elementary
masses called "particles" interact by means of forces that
vary with the distance, such as Lennard-Jones forces that
combine short range repulsion with long range attraction.
Motion is computed by independentely solving the equations
of motion for each particle.
Nodal approaches are often compute intensive, since very
small integration steps may be required. Another class of
methods, called "global approaches", has been introduced
to reduce computational costs [33], [45], [2]. The idea is
to perform global shape transformations rather than simulating
deformations that progressively propagate over a
deformable body. However, this leads to a restricted range
of deformations, and can only be applied to the animation
of homogeneous visco-elastic material.
The way a deformable model detects and responds to collisions
with other objects is very important, since it influences
all subsequent motions and deformations. However,
collision between soft objects is a complex phenomenon
that has not been widely studied in physics 1 . Consequently,
1 Elasticity theory [18] studies small oscillations around equilibrium
states, but does not provide any model for collisions. Moreover, collisions
between flexible bodies have finite time duration and consume
some energy in deformations, so the solutions developed for rigid
solids [27], [1] cannot be applied.
most of the solutions used in computer graphics have been
especially designed for this application.
A first issue is the way interactions between deformable
bodies can be detected. Quite surprisingly, the surface that
is displayed to represent the object during an animation
is seldom used for collision detection. For instance, deformable
bodies have been represented by splines surfaces
controlled by mass-nodes located at control points [25],
[17], but no precise collision detection was performed. Soft
inelastic substances animated with a particle system have
been displayed with implicit surfaces [38], [40], but once
again, the implicit surface itself was not used to collision
detection. Besides being inaccurate, detecting collisions
with mass-nodes is expensive [28]. A better solution is
used by Pentland and Williams [32], who exploit the implicit
inside/outside function that defines the surfaces of
their models for precise and e#cient collision detection.
They test if the points that sample one object's surface are
inside or outside another one in linear time.
Secondly, a method for computing response to collisions
must be designed. Most of the models used so far 2 compute
response forces from penalty methods [28]. These
methods do not generate any contact surface between interacting
flexible bodies, but use instead the amount of
interpenetration for computing a force that pushes the objects
apart. A quite promising approach [2] extends the
analytical interaction processing used for rigid solids [1] to
a global deformable model [45]. However, contact surfaces
are approximated by discrete sets of contact points which,
as the authors emphasize, is somewhat unsatisfactory.
To conclude the review of related work, most previous
deformable models do not present a convincing way of processing
collision and contacts between objects. Exact contact
surfaces should be generated rather than local interpenetrations
or bouncing before visual contact. Moreover,
these problems may be exacerbated by the fact that soft
collisions can last for a finite time. The combination of
implicit surfaces and deformable models described in this
paper supplies a systematic approach to treating collisions
among deformable objects.
B.

Overview

This paper presents an integrated set of methods that
use implicit surfaces for animating a wide variety of deformable
models. Implicit surfaces will be used as an extra
layer that coats a base structure, deformable or not, with
some smooth elastic flesh. While the base structure controls
the large scale behavior, the implicit layer performs
collision processing and generates local deformations due
to contacts. It also handles constant volume deformations
and topological changes such as separation or fusion. This
allows simulation of behaviors that would be extremely difficult
to treat with other methods.
Section II presents the layered approach we use. Section
III details the collision processing method associated
2 As for instance Terzopoulos et al. models [37], [39], [36], and
Pentland's ``Thing World'' system [32], [35].
with the implicit layer. Section IV introduces volume
preservation to the model. Section V presents two di#er-
ent applications of this formalism: the design of simplified
characters made of articulated skeletons coated with elastic
flesh, and the animation of soft inelastic substances capable
of separation and fusion.
II. Building layered models using implicit
surfaces
A. Implicit surfaces generated by skeletons
Implicit isosurfaces such as "distance surfaces" [47], [5]
allow the design of free form shapes through the manipulation
of "skeletons" generating potential fields. Because
they are simple to define and to control, they constitute a
good alternative to traditional implicit surfaces defined by
analytical equations.
An implicit isopotential surface generated by a set of
skeletons s i n) with associated "field functions"
f i is defined, at the isovalue c, by 3 :
In this paper, f will be called the "field function", and
the f i will be designated as the "implicit contributions" of
the di#erent skeletons. The implicit surface surrounds a
solid whose points satisfy (f(P ) # c), which may have several
disconnected components. Normal vectors are directed
along the field's gradient.
The skeletons s i can be any geometric primitive admitting
a well defined distance function: points, curves, parametric
surfaces, simple volumes, etc. The field contributions
f i are decreasing functions of the distance to the associated
skeleton:
where d(., s i ) is the distance to s i , and F i can be defined for
instance by pieces of polynomials [47] or by more sophisticated
anisotropic functions [21], [3]. Most field functions
associate a restricted scope of influence to each skeleton in
order to provide local control of the surface and to optimize
the computations. In practice, we use piecewise polynomial
field contributions that are parametrized by three parameters
called respectively thickness, sti#ness
and radius of influence, as sketched in Figure 1.
B. Embedding implicit surfaces into a layered construction
As emphasized in [7], a layered construction is a very
e#cient tool for creating complex models for animation.
It often provides the user with parameters that are more
intuitive and easier to use. Implicit surfaces generated by
skeletons are especially well suited to this kind of approach.
In our framework, the user defines a deformable object
by specifying:
3 In the remainder of this paper, upper-case letters are used for
points and vectors, and lower-case letters for scalar values.
-k
F (P)
Fig. 1. A typical field contribution, with its three parameters t i , k i
and R i .
1. An internal physically-based model which will be used
as a base structure during the animation. This model
may be for instance a rigid solid defined by a mass
and an inertia tensor, an articulated structure made of
several such solids, a mass/spring network, a particle
system, or any other model.
2. An implicit layer, that "coats" the base structure.
This layer is built by defining skeletons that generate
the implicit surface in local coordinate systems animated
by the base structure. Skeletons may be points,
line segments, triangles, or any graphic primitives.
During animations, the implicit layer immediately follows
the motion and deformations generated by the base
structure, defining a smooth surface that can be used for
display. The topology of this surface may change over time,
since separation or blending may be produced by the relative
motion of skeletons.
C. Benefits of the approach
As stressed before, the coherence between the representation
of an object and the model used for collision processing
is very important for generating convincing motion. Using
an implicit representation of the surface brings several ben-
efits, such as a precise yet e#cient collision detection mech-
anism, and a solution to precise contact modeling between
deformable bodies.
Instead of using a purely geometric definition for the
implicit layer, we use the deformable implicit model first
introduced in [15]. This model, which will be reviewed in
the next section, defines a correspondence between applied
forces and deformations of the implicit surface that approximates
elastic behavior. The latter can therefore be used
for collision detection and response.
D. Animation algorithm
The general scheme for animating the resulting layered
model develops as follows:
1. Animate the base structure by integrating the equations
of motion according to the set of applied forces.
This computes new positions for the skeletons that
generate the implicit layer.
2. Process interactions between objects:
(a) Use the implicit layer for detecting interpenetrations

(b) Model contact by locally deforming the implicit
layer in order to generate exact contact surfaces between
colliding bodies.
(c) Integrate reaction and friction forces along contact
surfaces. Add them to the set of external actions
to be applied to the base structure at the next time
step.
Detailing dynamic equations and integration schemes usable
for the base structure is beyond the scope of this pa-
per. An overview can be found for instance in [42]. The
next section just presents the elastic model we use for the
implicit layer, and details the associated collision detection
and response algorithm.
III. Processing collisions with the implicit layer
In previous deformable models, when a collision is de-
tected, response forces are approximated first. These forces
are then used to compute subsequent deformation and motion
of the objects, without producing an exact contact
surface when collision endures in time. The implicit layer
defined in this section uses a di#erent approach. When a
collision is detected it first performs precise contact modeling
with the other object with local deformations. Compression
along contact surfaces is then used to compute
collision response.
A. Collision detection
Collision detection is performed between each pair of objects
by first testing interpenetration between axis-aligned
bounding boxes. When boxes intersect, the implicit representations
of the surfaces and a set of sample points on
them are used for a more precise detection: the surface
points of each object that lie within the bounding box of
the other object are evaluated by the implicit function of
the other object. When an interpenetration is detected, the
purely geometric contact modeling process described in the
following section is applied. Issues for maintaining samples
on the implicit surface will be discussed in Section III-D.
B. Modeling contact between objects
Once detected, an interpenetration must be avoided by
locally deforming the implicit layer of each object. Both
exact contact surfaces and deformations in propagation regions
that model the transverse propagation of deformation
must be generated (see Figure 2). We accomplish this by
adding new local terms, called "deformation terms", to the
field functions defining the implicit layers of each object.
. A negative field g modeling compression is added in the
interpenetration region in order to generate a contact
surface with the other object.
. A positive field p modeling the transverse propagation
of deformations is added in the propagation region.
B.1 Deformation in the interpenetration region
The deformation field terms g ji and g ij to be added to
the equations of the objects i and j should generate an
exact contact surface. Thus the two equations
Interpenetration region
Propagation region Solids after deformation
Object Object Object Objectf
Transverse
Propagation
Fig. 2. Modeling contact consists in applying di#erent deformation
fields in the interpenetration region and in the propagation regions
associated with each object (cross-sectional views).
must have a common solution. A simple and symmetric
solution is to define the compression field terms by:
This choice is appropriate since deformation field terms
are negative in the interpenetration region, and locally generate
in this region a contact surface defined by the set of
points such that:
We can remark at this point that an object can be defined
as rigid if no deformation term is added to its surface
equation. In that case, collision with a deformable implicit
object can easily be modeled. The compression field term
applied to the deformable object i is:
This makes the implicit layer of the deformable body exactly
fit with the rigid object in the whole interpenetration
region.
B.2 Deformation in the propagation areas
Our aim is to optimize the contact modeling process
by directly computing deformed shapes in contact situations
rather than simulating deformations that progressively
propagate over the implicit layer. The bulge generated
in the propagation region (see Figure 2) must be
computed such that there is a smooth junction between
the interpenetration region and the region where the object
remains undeformed.
The user controls s i 's propagation field term p ji (P ) (due
to the collision with s j ) through two additional parameters
in s i 's description:
. A value w i giving the o#set distance where deformations
propagate around the interpenetration region
(see

Figure

2). No deformations will be generated outside
this area.
. An "attenuation value" # i giving the ratio between the
maximal value desired for p ji and the current maximal
compression term in the interpenetration area.
We then define the propagation field term p ji to be applied
in the propagation zone of the object s i as:
where P 0 the closest point to s j in s j 's gradient direction
(see

Figure

is the maximal propagation
value equal to # i times the maximal compression
field value, and a k,a0 ,w (x) is a piecewise polynomial function
as depicted in Figure 3. P 0 is computed in practice
by iteratively performing small steps from P in the opposite
direction of the object j's gradient. Our choice for the
slope k ensures that the shape of the implicit object stays
C 1 at the border of the interpenetration zone. One can use
the following equation for a k,a0,w (x):
a k,a0 ,w
a (x)
Fig. 3. Attenuation function defining the field in propagation areas.
The slope at is k, the maximum is a 0 , and the function
has zero values and derivatives for x # w.
Fig. 4. (left) Contact between two colliding deformable objects.
Cross-sectional view showing the exact contact modeling.
A step-by-step description of this animation is described in Appendix

C. Response to collision
Now that correctly deformed shapes are generated beween
colliding objects as depicted in Figure 4, the deformation
of the implicit layer must be used to deduce response
forces. To achieve this, we describe in this section a model
designed to approximate elastic behavior, first introduced
in [15].
C.1 Modeling elasticity with implicit surfaces
A deformable model is defined by a given correspondence
between applied forces and deformations. Both linear [39],
[19], [45] and non-linear [37] elasticity have been used in
previous models. Linear elasticity states that sti#ness near
a given point P of a solid remains constant during defor-
mations. The displacement of P from an initial position
to a final position X(P
then a linear function of the applied force R(P
In non-linear models, the sti#ness k is not only a function
of the point P , but may also depend on its current location
inside the solid. The force applied during a displacement
of P from X
For generality, the implicit layer we are defining should be
able to exhibit both linear and non-linear behaviors.
Deformations of an implicit surface can be modeled by
variations in its field function f . To express non-linear
elasticity with this formalism, we let dR(Y ) be a infinitesimal
radial force and dY the resulting infinitesimal radial
displacement. From equation (12) they must satisfy:
We can then make the following observation: the set of
points P satisfying f(P is the field function,
is su#cient to define a surface. This set of points being
fixed, the variation of f around the isosurface can then
be used to model physical properties. Consequently, we
choose to model sti#ness with the field's gradient:
This choice simplifies equation (13), yielding:
be the deformation field term
associated at equilibrium with the radial force R. If the
normal vector N(P ) has remained constant during the deformation
(which is then said to be "radial"), the formula
giving the correspondence between applied forces and de-
formations, obtained by integrating equation (15), is:
In practice, we will use a rewritten version of this latter
The correspondence between applied forces and deformations
will only be used to integrate radial response forces
during collisions. It can be noted that this formulation only
approximates elastic behavior since only the radial component
of forces is computed.
C.2 Sti#ness control
As shown in [15], defining sti#ness with the field's gradient
has a simple geometric interpretation since field contributions
are decreasing functions of the distance to the
associated skeleton: the user defines local sti#ness as the
opposite of the slope of the field function. Both linear and
non-linear elastic behaviors are easily designed, as depicted
in

Figure

5.
-k
F (P)
F (P)
(a) (b)
Fig. 5. Examples of field functions for the implicit layer. (a) Linear
elasticity: sti#ness, represented by the opposite of the slope, is
constant during deformations. (b) Non-linear elasticity: sti#ness
increases during compressions.
In practice, the field's gradient also a#ects the object geometry
when contributions from di#erent skeletons blend
together (equation (1)). It is di#cult to specify the ob-
ject's shape and its dynamic behavior at the same time
by adjusting the di#erent field contributions. We partially
overcome this problem by introducing a scaling parameter
K relating the e#ective sti#ness and the field function's
This parameter K enables us to adjust the object sti#ness
according to its mass and inertia tensor without modifying
its geometry.
C.3 Radial response forces
We have defined a way to model contact and a correspondence
between deformations of the implicit layer and
radial applied forces. Thus evaluating the resulting normal
reaction force R(P ) at a point P on the contact surface
during collision is straightforward. Equations (6) and (17)
give us a value for the normal response force:
is the normal vector to the deformed surface
of object i at point P . Since g ji , which models local com-
pression, is negative, R i has the same orientation as the
normal vector, and models the internal force that tends to
restore the initial shape of the object.
An important remark is that our model is consistent with
the action/reaction principle: along contact surfaces, the
deformation terms applied to both objects are equal, since
while the normal vectors are opposite. Thus, opposite
reaction forces R i are generated.
C.4 Friction and damping forces
To model both tangential friction in contact areas and
damping due to the progressive compression of the solids,
Fig. 6. Flexible clover falling on a rigid staircase.
we include a friction coe#cient # i in the description of each
object. When a collision occurs, the friction and damping
force F i at a point P of the contact surface between two
objects i and j is expressed by:
is the speed of P , a point
on the surface of the object i (respectively j).
The sum of radial and frictional forces is transmitted to
the base structure of each object, and will be taken into
account in subsequent motion. An example of animation
using this technique is depicted on Figure 6.
D. Implementation
D.1 Sampling the isosurface
Sample points on the implicit surface are needed for both
collision detection and numerical integration of response
forces. Points that appear to be inside another object are
moved to the deformed isosurface (for instance by performing
search along the gradient direction), and the value of
the deformation field at each new location directly gives
the intensity of radial contact force along the small surface
area sampled. These forces are added to friction forces and
stored to be integrated by the base structure at the next
time step.
Any method could be used for generating sample points
on the implicit surface. The most widely used are spatial
partitioning techniques [47], [23], [4], [43], [29]. However,
approaches that take advantage of temporal coherence are
more e#cient for our application, since sample points do
not move much between two consecutive steps of an anima-
tion. One method of this kind [44] maintains sample points
called "floaters" on the isosurface, and ensures a good sampling
distribution by connecting them with repulsive inter-action
laws. During deformations, more floaters may be
automatically generated, or some of them may be removed,
according to the local sampling density. The method we
use, first introduced in [10], is slightly di#erent. We present
it briefly in the next paragraph since it has the advantage
of also being convenient for volume preservation, as will be
described below.
D.2 An adaptive sampling technique
The central idea is the following: each skeleton s i contributing
to the implicit layer emits a set of sample points in
directions that are fixed in its local coordinate system, and
are well distributed around it as illustrated in the stages 1
to 3 of

Figure

7. Those of the points that reach the iso-surface
without going through an area already sampled by
another skeleton are said to be "valid", and will be used as
samples on the isosurface at a current time step (see stage
4 in

Figure

7).
Stage 4
Stage 3
e
Fig. 7. Di#erent stages of sampling initialization
This process can be defined more formally by associating
a territory T i to each skeleton s
T i is the part of the implicit object where s i 's field contribution
is the highest. This is equivalent to splitting the
implicit volume into Vorono regions defined by the skele-
tons, the "distance" from a point P to a skeleton s i being
defined by the field function. Sample points sent from s i
stop at T i 's boundary, and are valid if they lie on the iso-surface

points then start from their previous position in
local coordinate system at each time step to meet the
surface again. Thus using temporal coherence increases
e#ciency. In addition, sample points that were located
between two territories at a given animation step may be
brought to the surface during later deformations. The sampling
of the isosurface automatically adapts to large deformations
and changes in topology.
D.3 Interactive visualization
A further benefit of the sampling method above is that
the implicit surface can be displayed, during an interactive
animation process, as a set of polygonal meshes built on
the sample points (valid or not) that belong to the same
skeleton. This provides a legible solid representation of
the surface with no extra cost [10] as depicted in Figure 8.
Note that we do not use the sample points for final high
quality rendering of an animation. Storing the parameters
of the isosurface such as the positions of the skeletons and
the lists of colliding objects o#ers a much more compact
representation that can then be used for computing direct
ray-tracing of the implicit surfaces [13].
Fig. 8. Left: visualization of sample points as scales on the surface.
Right: visualization of the same sampling but with a piecewise
polygonization.
IV. Controlling volume during animations
The preservation of constant volume of deformable objects
is desirable in animation [22]. Additionally, the user
may desire precise control over volume variation in order to
emphasize certain motion. The problem of volume preservation
has been solved by methods based on Lagrange multipliers
in the specific case of objects discretized into lattices
of fixed topology [33], [34]. We present in this section
the only solution to our knowledge that has been proposed
for controlling the volume of bodies that undergo large deformations
and topological changes such as separation and
fusion [9].
Unwanted volume variations are exacerbated in implicit
surface animation. They are produced by the field blending
process during the relative motion of the skeletons, and
they may be particularly annoying when the object undergoes
separation or fusion. Although the problem has
already been identified [47], [8], previous approaches only
provide partial solutions that ensure volume preservation
between an initial and a final state. But they do not
ensure volume preservation during intermediate deforma-
tions, while drastically restricting the range of field functions
that can be used.
This section presents a general method, applicable to
any field function and isovalue, for controlling the volume
of objects defined by implicit surfaces.
A. Local volume variations
The first problem is the detection of volume variation.
The volume of an implicitly-defined object is given by:
R R R f(P )#c
dx dy dz. This expression cannot be computed
analytically for most field functions. A simple method for
volume approximation consists of discretizing space into
voxels, and expressing the volume as the sum of voxels
that lie inside the object. However, this technique would
not provide a solution to the problem, since we also need
to know near which skeleton the volume is changing.
Suppose the volume has been modified, as in Figure 9
(a), by the relative motion of some skeletons of the implicit
layer. A solution for avoiding the variation consists
of adjusting the strength of the field functions so that the
(b)
step 1
(a)
Fig. 9. (a) Volume variations of an implicit surface generated by point
skeletons between two steps of animation. (b) Volume controlled
locally in step 2.
volume keeps its initial value. However, these adjustments
should not be done in areas where the object has not been
deformed. As a consequence, volume variations should be
detected and treated locally.
To define local volumes we use the notion of skeleton
already introduced in Section III-D.2: we define
the local volume V i associated with a skeleton s i as the
volume of its territory T i . The total volume of the implicit
object can then be expressed as the sum of local volumes.
approximation
Sampling Ti's boundaries
Skeleton Territories
Fig. 10. Particle territories and sample points used for volume approximation

Computing local volumes is straightforward when the
adaptive sampling method of Section III-D is used. As
shown in Figure 10, a local volume V i is approximated as
the sum of small pyramidal volumes defined around each
sample point sent by s
where P i is the set of sample points sent by a skeleton
is the distance, and b i only depends on the angular
distribution of samples for s i . In practice, the factor b i
can be omitted in volume computations, since controlling
the value of
su#cient for avoiding volume
variations.
B. Volume control
We control local volume variations by associating a
proportional-derivative controller to each skeleton. This
controller can be seen as a black box that, given the current
local volume V i,t and the value V i,0 to reach or to maintain,
outputs an adequate adjustment of the field function f i of
this particular skeleton.
For our application, the way to modify f i must be chosen
carefully since the norm of f i 's gradient gives the object
local sti#ness (see Section III-C.1). In order to adjust
the volume of skeleton territories without modifying the
object's physical properties, we combine the original field
function with a translation # i,t . At each time step, the field
originally defined by the decreasing function of the distance
replaced by:
Since we need regular shape variations, we control the time
derivative
# i,t of the translation parameter rather than its
value. The inputs of the controller are then the normalized
volume variation # i,t and its time derivative
Its output is:
where # and # are appropriately chosen parameters. A
simple example of volume control is given in Figure 11.
Fig. 11. Preserving volume during a blend between two point-
skeletons. The leftmost picture shows the initial configuration
and the speed vector. (a) shows the blending without any con-
trol, whereas (b) depicts a controlled blending ensuring constant
volume.
This method used for maintaining a constant volume
during an animation can be extended in order to impose
specific volume variations that may be locally specified by
the user: the target volumes V i,0 simply have to be changed
over time. These capabilities are useful in a broad range of
applications in the field of animation with implicit surfaces.
The next section presents two of them.
V. Applications
A very simple use of the implicit layer consists of combining
it with a rigid internal structure, as was done in [15].
This leads to animations of elastic objects that locally deform
during contacts, but return to their initial shape when
no external force is applied. Snapshots from such an animation
[12] are displayed in Figure 12.
This section presents two further applications of the
model. The first is an animation of simple characters made
of articulated skeletons coated with implicit flesh, which exploits
the compactness and enhanced control o#ered by a
layered structure. The second builds on the specific properties
of implicit surfaces for modeling soft inelastic substances
capable of separation and fusion, and that preserve
their volume during the animation.
A. Modeling simplified characters
Specifying complex motion is greatly simplified when the
animation system is able to abstract basic shapes from the
representation of an object. Motion can then be refined
with these shapes, and the animator only switches to the
Fig. 12. Four frames of the animation Simply Implicit.
detailed representation when necessary. This is particularly
true in character animation, where animators often spend
a lot of time specifying motion and deformations of an articulated
"skeleton" representing the character. Much less
time is spent on animating the skin deformations, which
may be generated automatically from the skeleton motion.
Layered models are particularly well adapted to this con-
text. Various approaches, either purely geometric [6], [11]
or physically-based [7], [17], [31], [41] have already been
proposed for the automatic animation of the skin from the
motion of the underlying skeleton.
This section explains how to adapt the implicit layer
model we have developed for this applications. One advantage
of using an implicit representation of the flesh and
skin is the compactness it o#ers: only skeletons and field
functions need to be specified since the field models geometric
and elastic properties. Another advantage is the ability
to automatically detect collisions and model contact with
other objects. This is particularly useful since characters
often need to interact with the simulated world. Moreover,
the volume control method we have developed can be used
for creating more lively animations, by animating muscles
for instance.
A.1 Structure used
In the terminology we have developed in Section II, a
character will be represented by:
. Base structure: an articulated structure composed
of a set of "links" connected by hinges. This structure
may be animated with key frames, inverse kinematics,
through the use of physically-based animation, or by
any other technique.
. Implicit layer: each skeleton contributing to the implicit
surface is defined in the local coordinate systems
of one of the links.
The animation of this model is straightforward in the general
framework we have defined: the general algorithm described
in Section II-D is used. However, two problems due
to the relative motion of skeletons inside the implicit layer
have to be discussed:
1. Unwanted blending e#ects must be avoided during deformations

2. Intercollisions should be detected between the di#er-
ent parts of a character.
The two next paragraphs explain how we deal with these
problems.
A.2 Avoiding unwanted blending e#ects
The unwanted blending case is a di#cult problem that
has been known for a long time [46]. When we implicitly
model characters for instance, we want their arms to blend
with their shoulders, but not with another part of the body,
as illustrated by Figure 13.
Fig. 13. The unwanted blending problem
A solution, first suggested in [46] and further developed
in [30], consists in defining a neighboring graph between
the di#erent skeletons, and stating that a skeleton's field
only blends with contributions from neighboring skeletons.
More precisely, the field function f is replaced by the following
procedure for computing the field value at a point
1. Compute all the field contributions at point P ,
2. Select the predominant contribution from those of
groups of skeletons that blend together,
3. Return this value without summing the other field
contributions.
This algorithm avoids surface discontinuity during the controlled
blending process, as explained in [20]. However, the
method can not guarantee C 1 continuity everywhere.
A.3 Processing intercollisions
Instead of processing collisions between pairs of objects,
we use the algorithm described in Section III-B for processing
collisions between pairs of skeleton territories that do
not blend. The sampling method described in Section III-D
provides us with a set of sample points, so we can easily
compute local bounding boxes from the position of valid
sample points and associate them with each skeleton ter-
ritory. These boxes (enlarged by the maximal distance
between sample points) cover the isosurface, allowing for
precise collision detection even when the surface separates
into several components.
When the underlying links are animated with a
physically-based approach, contact forces computed between
skeleton territories are transmitted to the reference
link of the skeletons, to be integrated at the next time step.
A.4 Results
An example of animation performed with this model is
depicted in Figure 14. A simulation method based on displacement
constraints [14] is used for animating the base
structure of the characters. We can observe several inter-
collisions as the character falls.
Fig. 14. Collisions with the ground and intercollisions of a simple
articulated implicit object falling on its side.
B. Animating soft substances
This section presents a quite di#erent application of the
techniques we have described. The soft substance model
we develop here, first introduced in [9], is particularly interesting
since it benefits from the specific capability of
implicit surfaces to model separation and fusion. The constant
volume deformations generated by our model are very
important in this case, otherwise an important increase of
volume would be produced during fusion.
B.1 Structure used
As emphasized in the introduction, a simple and unified
way of modeling a large variety of behaviors, including inelasticity
and fractures, is to use physically-based particle
systems. The main drawback of these systems, when used
alone, is the lack of a method for defining a smooth surface
for the objects. This is not a problem when several thousands
of particles are used for accurately simulating fluids
for instance. For animation purposes, the use of far fewer
particles is su#cient for producing su#cient deformations.
A surface, defined around the particles, should be used for
visualization and for processing contact with other objects.
The general framework we have defined provides a solution
to this problem since the implicit layer seems well adapted
for coating the particles. A piece of soft substance will then
be composed of:
. Base structure: a particle system, made of a few tens
of particles. Interactions between particles are modeled
by attraction/repulsion forces such as Lennard-Jones
forces, combined with friction forces that depend
on the local density of particles. In our implementa-
tion, we use the following expressions for the interaction
force and the friction force between two particles:
F int (P
r  8
r  4
is the sti#ness parameter,
stands for the speed vector of particle P i , and  is a
decreasing continous function with finite support.
. Implicit layer: an implicit surface defined by point
skeletons located on each particle. We use field contributions
with relatively large thickness and radius of
influence in order to give a smooth aspect to the simulated
material even if only a few particles are used. Local
volume controllers are associated with each skele-
ton, in order to prevent volume variations.
The general animation algorithm we have developed also
applies to this case. The next paragraphs explain how we
handle separation and fusion of the substance.
B.2 Modeling separation
When the particle system moves and deforms, a piece
of substance may separate into several components, due to
the relative motion of point skeletons defining the surface.
However, if these disconnected chunks come back close to
each other, they will blend as in Figure 11 rather than
collide, since they are considered to be parts of the same
This artifact is related to the unwanted blending problem
we have referred to in the previous section. However,
the problem is more complicated here since we cannot use
a predefined blending graph: the blending properties between
the set of point skeletons must change during the
animation, according to the separation that is detected.
As a consequence, our method is based on the computation
of a time varying blending graph. At each animation
step, the current blending graph is stored as a list of neigh-
bors, so called "blending list", associated with each point
skeleton. Processing unwanted blending is done by reducing
blending lists each time the implicit surface breaks into
disconnected components that must not blend any more.
The algorithm we use is the following:
. Before the animation, the blending graph is initialized
as a complete graph, where each skeleton is connected
to every other one. This corresponds to the standard
field function, computed as the sum of all the field
contributions.
. At each animation step:
1. For each pair of point skeletons that blend together,
we check if their spheres of influence, defined by the
radius of influence of their fields, intersect. This
relation defines an "influence graph". We then use
the transitive closure of this graph for computing
the blending graph we are looking for. For instance,
in

Figure

15, point A is detected to be in the same
components than point B, while the separation with
the other part is detected.
2. Collisions are detected between skeleton territories
not connected in the blending graph, as was done
in Section V-A.3. As a result, pieces of substance
that separate from the same body collide instead of
blending when they come back close to each other.
Note that intersection tests on spheres of influence do
not detect disconnections as soon as they appear, but when
there is no more implicit contribution between the discon-
AFig. 15. The influence graph and its connected components. Particles
A and B lie in the same component, and thus their fields will
blend if they come close to each other.
nected parts. However, we cannot reduce the blending list
earlier without a sudden alteration of the shape of the disconnected
components.
B.3 Modeling fusion under compression
Blocks of soft substance such as clay or dough merge
under compression forces that exceed a specified threshold.
This behavior can easily be simulated with our model.
A fusion threshold is associated with each substance.
Each time a collision is computed between two components
of the same substance, the compression force along the contact
surface between two skeleton territories is compared
with the fusion threshold. If the threshold is exceeded,
those skeleton that contribute to the contact surface for one
component are added to the blending list for those skeletons
contributing to the other component's contact surface.
At the next time step, fields from the two pieces will then
locally blend in this area, while collisions will still be computed
between the rest of the components as illustrated in

Figure

16. This merging will endure in time, unless the
two pieces happen to be disconnected again by subsequent
deformations. This method do not ensure, however, C
continuity everywhere, as observed in [20]: tangent discontinuities
may appear locally at some intermediate steps of
the fusion.
Fig. 16. Progressive fusion under compression of two soft substances.
Instant fusion can be handled even more easily. Figure
shows four steps of an animation where a piece of
soft substance is grabbed away by pliers and then released.
The substance is made of nine particles only, and the fusion
threshold has been set to zero, so that the substance
immediately merges back after a collision. Here, volume
preservation is essential. Otherwise, a very large and sudden
increase of volume would be produced between the two
last frames.

Figure

exhibits four frames from the animation
Kitchen Fiction [16]. It shows the application of all the
techniques detailed above to a more complex animation
where a set of rigid tools are manipulating three di#erent
soft substances.
Fig. 17. Soft substance grabbed away by pliers and released.
Fig. 18. Four frames of the animation Kitchen Fiction.
VI. Conclusion
This paper has presented a general framework for building
layered deformable models with implicit surfaces. The
implicit formulation is particularly well adapted to a layered
construction. It can be used for coating any reference
component as, for instance, a rigid solid, an articulated
structure, a mass-springs network, or a particle system. It
defines a smooth surface around the object that can be
used for rendering, and o#ers simple yet precise processing
of collisions and contacts. The implicit inside-outside function
faciliates collision detection, while the deformation of
the implicit layer generates exact contact surfaces between
colliding bodies. The physically-based model associated
with the implicit layer approximates elasticity and allows
the computation of response forces due to compression and
friction. Moreover, preservation of deformed objects' volume
is possible, even when the objects undergo significant
changes such as separation or fusion.
We have illustrated this framework by detailing two very
di#erent applications: the animation of rigid articulated
bodies coated with implicit flesh and the simulation of soft
substances performing separation and fusion. The first of
these applications should lead to interesting developments
in the character animation area. Our layered framework
would o#er a compact way of modeling both geometry and
the physical characteristics of simplified characters. Local
adjustments of volume through time could be used for generating
more expressive animations. Lastly, the capability
of processing collisions and contact between a character and
other objects of the scene would be an essential benefit of
our approach.

Acknowledgements

We wish to thank Jean-Dominique Gascuel and Nicolas
Tsingos for their contributions to the developement of the
animation software. Many thanks to Agata Opalach and
Jules Bloomenthal for fruitful discussions, to reviewers for
very helpful comments, and to Andrew Hanson and George
Drettakis for carefully rereading this paper.



--R

David Bara
David Bara
Extended field functions for soft objects.
Polygonisation of implicit surfaces.
Interactive techniques for implicit modeling.
Interactive skeleton technique for enhancing motion dynamics in key frame animation.

Highly deformable material for animation and collision processing.
Animating soft substances with implicit surfaces.
Adaptive sampling of implicit surfaces for interactive modeling and animation.
A surface model for skeleton-based character animation
Simply implicit.
Implicit patches: An optimized and powerful ray intersection algorithm for implicit surfaces.
Displacement constraints for interactive modeling and animation of articulated structures.
An implicit formulation for precise contact modeling between flexible solids.

A modeling system for complex deformable bodies suited to animation and collision processing.
Classical Mechanics.
Simulation of object and human skin deformations in a grasping task.
Controlled blending for implicit surfaces using a graph.
Controlled blending of procedural implicit surfaces.
Principles of traditional animation applied to 3d computer animation.
Marching cubes: a high resolution 3D surface construction algorithm.

The motion dynamics of snakes and worms.
Globular dynamics: A connected particle system for animating viscous fluids.
Impulse based simulation of rigid bodies.
Collision detection and response for computer animation.
An evaluation of implicit surface tilers.
Implicit surfaces: Appear- ance
High level control of implicit surfaces for character animation.
Good vibrations: Modal dynamics for graphics and animation.
Constraint methods for flexible mod- els
Alla She
Stan Sclaro
Modeling inelastic deformations: Viscoelasticity
Elastically deformable models.

Physically based model with rigid and deformable components.
Modeling liquids and solids using thermal par- ticles
A system for construsting and animating layered elastic characters.
Advanced Animation and Rendering Techniques.
Octree for faster isosurface generation.
Using particles to sample and control implicit surfaces.
Fast animation and control for non-rigid structures


--TR

--CTR
Daniel Nixon , Richard Lobb, A Fluid-Based Soft-Object Model, IEEE Computer Graphics and Applications, v.22 n.4, p.68-75, July 2002
Bryan E. Feldman , James F. O'Brien , Bryan M. Klingner , Tolga G. Goktekin, Fluids in deforming meshes, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California
Tolga G. Goktekin , Adam W. Bargteil , James F. O'Brien, A method for animating viscoelastic fluids, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
Bryan M. Klingner , Bryan E. Feldman , Nuttapong Chentanez , James F. O'Brien, Fluid animation with dynamic meshes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Bryan E. Feldman , James F. O'Brien , Bryan M. Klingner, Animating gases with hybrid meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
Guillaume Dewaele , Marie-Paule Cani, Interactive global and local deformations for virtual clay, Graphical Models, v.66 n.6, p.352-369, November 2004
Jing Hua , Hong Qin, Haptics-based volumetric modeling using dynamic spline-based implicit functions, Proceedings of the 2002 IEEE symposium on Volume visualization and graphics, October 28-29, 2002, Boston, Massachusetts
Victor B. Zordan , Bhrigu Celly , Bill Chiu , Paul C. DiLorenzo, Breathe easy: model and control of human respiration for computer animation, Graphical Models, v.68 n.2, p.113-132, March 2006
Capturing the complexity of hair motion, Graphical Models, v.64 n.1, p.40-58, January 2002
Victor Brian Zordan , Bhrigu Celly , Bill Chiu , Paul C. DiLorenzo, Breathe easy: model and control of simulated respiration for animation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
Adam W. Bargteil , Tolga G. Goktekin , James F. O'brien , John A. Strain, A semi-Lagrangian contouring method for fluid simulation, ACM Transactions on Graphics (TOG), v.25 n.1, p.19-38, January 2006
Alexis Angelidis , Marie-Paule Cani, Adaptive implicit modeling using subdivision curves and surfaces as skeletons, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Xiaogang Jin , Chiew-Lan Tai , Jieging Feng , Qunsheng Peng, Convolution surfaces for line skeletons with polynomial weight distributions, Journal of Graphics Tools, v.6 n.3, p.17-28, 2001
Marie-Paule Cani , Alexis Angelidis, Towards virtual clay, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
G. H. Bendels , R. Klein, Mesh forging: editing of 3D-meshes using implicitly defined occluders, Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
Hai-Yin Xu , Dan Li , Jian Wang, Implicit curve oriented inbetweening for motion animation, Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia, November 29-December 02, 2006, Kuala Lumpur, Malaysia
Daniel Nixon , Richard Lobb, A Fluid-Based Soft-Object Model, IEEE Computer Graphics and Applications, v.22 n.4, p.68-75, July 2002
Masatoshi Matsumiya , Haruo Takemura , Naokazu Yokoya, An immersive modeling system for 3D free-form design using implicit surfaces, Proceedings of the ACM symposium on Virtual reality software and technology, October 22-25, 2000, Seoul, Korea
Jing Hua , Hong Qin, Haptics-Based Dynamic Implicit Solid Modeling, IEEE Transactions on Visualization and Computer Graphics, v.10 n.5, p.574-586, September 2004
Allgre , Eric Galin , Raphalle Chaine , Samir Akkouche, The HybridTree: mixing skeletal implicit surfaces, triangle meshes, and point sets in a free-form modeling system, Graphical Models, v.68 n.1, p.42-64, January 2006
Mashhuda Glencross , Alan G. Chalmers , Ming C. Lin , Miguel A. Otaduy , Diego Gutierrez, Exploiting perception in high-fidelity virtual environmentsAdditional presentations from the 24th course are available on the citation page, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
inelasticity;animation;implicit surfaces;collision detection;collision response;deformable models