Meshless Deformations Based On Shape Matching

Meshless Deformations Based on Shape Matching
Matthias M¨uller
Bruno Heidelberger
Matthias Teschner
Markus Gross
NovodeX/AGEIA & ETH Z¨urich
ETH Z¨urich
University of Freiburg
ETH Z¨urich
Figure 1: The presented technique is stable under all circumstances and allows to simulate hundreds of deformable objects in real-time.
Abstract
many deformable models have been proposed. In general, these
approaches focus on an accurate material representation, on stabil-
ity aspects of the dynamic simulation and on versatility in terms of
We present a new approach for simulating deformable objects. The
advanced object characteristics that can be handled, e. g. plastic
underlying model is geometrically motivated. It handles point-
deformation or fracturing.
based objects and does not need connectivity information. The ap-
proach does not require any pre-processing, is simple to compute,
Despite the long history of deformable modeling in computer
and provides unconditionally stable dynamic simulations.
graphics, research results have rarely been applied in computer
games. Nowadays, deformable cloth models with simple geome-
The main idea of our deformable model is to replace energies by
tries can be found in a few games, but in general, games are
geometric constraints and forces by distances of current positions
dominated by rigid bodies. Although rigid bodies can be linked
to goal positions. These goal positions are determined via a gener-
with joints to represent articulated structures, there exist no practi-
alized shape matching of an undeformed rest state with the current
cal solution which allows to simulate elastically deformable three-
deformed state of the point cloud. Since points are always drawn to-
dimensional objects in a stable and efﬁcient way. There are several
wards well-deﬁned locations, the overshooting problem of explicit
reasons that prevent current deformable models from being used in
integration schemes is eliminated. The versatility of the approach
interactive applications.
in terms of object representations that can be handled, the efﬁciency
in terms of memory and computational complexity, and the uncon-
Efﬁciency. Existing deformable models based on complex mater-
ditional stability of the dynamic simulation make the approach par-
ial laws in conjunction with stable, implicit integration schemes are
ticularly interesting for games.
computationally expensive. Such approaches do not allow for in-
teractive simulations of objects with a reasonable geometrical com-
CR Categories:
I.3.5 [Computer Graphics]: Computational
plexity. Further, these approaches might require a speciﬁc object
Geometry and Object Modeling—Physically Based Modeling; I.3.7
representation and the algorithms can be hard to implement and de-
[Computer Graphics]: Three-Dimensional Graphics and Realism—
bug. In contrast, interactive applications such as games constitute
Animation and Virtual Reality
hard constraints on the computational efﬁciency of a deformable
modeling approach. The approach is only allowed to use a small
Keywords: deformable modeling, geometric deformation, shape
fraction of the available computing resources. Further, speciﬁc vol-
matching, real-time simulation
umetric representations of deformable objects are often not avail-
able since the geometries are typically represented by surfaces only.
Stability. In interactive applications, the simulation of deformable
1
Introduction
objects needs to remain stable under all circumstances. While so-
phisticated approaches allow for stable numerical integration of ve-
locities and positions, additional error sources such as degenerated
Since Terzopoulos’ pioneering work on simulating deformable ob-
geometries, physically incorrect states, or problematic situations
jects in the context of computer graphics [Terzopoulos et al. 1987],
with large object interpenetrations are not addressed by many ap-
proaches. A ﬁrst contribution to this research area has been pre-
sented in [Irving et al. 2004], where large deformations and the
inversion of elements in FE approaches can be handled in a robust
way. However, this approach is not intended to be used in interac-
tive applications.

Controllability. Physically-based deformable models are intended
and Terzopoulos 1992], dynamic models have been derived from
to simulate the dynamic object behavior as realistically as possi-
global geometric deformations of solid primitives such as spheres,
ble. However, in games or entertainment technologies, the sim-
cylinders, cones, or superquadrics.
ulation, i. e. the magnitude and shape of a deformation need to
be controllable by the developer, tolerating a degradation of real-
Our approach uses deformation modes which are related to modal
ism as long as the result looks realistic. An early discussion of
analysis approaches [Pentland and Williams 1989], [Hauser et al.
physically-plausible simulations compared to accurate approaches
2003], [James and Pai 2004]. However, we do not approximate
can be found in [Barzel et al. 1996] and [Barzel 1997].
the deformation modes from elasto-mechanical object properties
which commonly requires the incorporation of additional auxiliary
Many available techniques for simulating deformable objects fail
object representations, such as tetrahedral meshes [James and Pai
with respect to one or more of these aspects. To overcome the
2002]. Instead, our deformation modes are geometrically motivated
existing restrictions we propose a technique which addresses the
which signiﬁcantly simpliﬁes the pre-processing stage. Although
aforementioned problems and contributes towards stable, interac-
the model is not physically motivated, we show that the approach
tive, and versatile deformable modeling. In particular, the contribu-
has similar capabilities in representing deformations compared to
tions of our deformable modeling approach are:
existing modal analysis models. In contrast to existing models,
•
no additional data structures for computing the deformation modes,
Elasticity is modeled by pulling a deformed geometry towards
no expensive modal decompositions, and no explicit representation
a well-deﬁned goal conﬁguration which is determined by an
and storage of modal vectors are required in our technique. Thus,
extended shape matching technique.
our approach is efﬁcient in terms of computational complexity and
• The degree of representable deformation details can be varied
memory.
using linear and quadratic deformation modes. Subdivisions
into clusters introduce further degrees of freedom.
Our approach draws from previous work in the ﬁeld of shape
matching [Shoemake and Duff 1992], [Alexa et al. 2000], [Kent
• A large variety of objects can be handled. Geometric defor-
et al. 1992]. While standard shape matching approaches are pri-
mations are just computed for points and connectivity infor-
marily concerned with establishing the correct correspondences
mation or speciﬁc representations are not required.
between two shape representations [Faugeras and Hebert 1983],
•
[Horn 1987], [Besl and McKay 1992], [Kazhdan et al. 2004], all
Our technique does not require any pre-processing or large
correspondences are a priori known in our case. The remaining
accompanying data structures. The conﬁguration of parame-
problem is that of ﬁnding least squares optimal rigid transforma-
ters is simple and intuitive. Thus, the technique is as simple
tions in 3D between the two point clouds with a priori known corre-
as ”plug and simulate” in terms of object handling.
spondences [Kanatani 1994], [Umeyama 1991] and [Lorusso et al.
• The dynamic simulation is stable under all circumstances and
1995]. In contrast to ﬁnding optimal rigid transformations, we ex-
for all deformed geometry conﬁgurations. The approach is not
tend these methods to compute optimal linear and quadratic trans-
exposed to problems such as ill-shaped or inverted elements.
formations.
Even non-manifold meshes with arbitrarily shaped triangles
can be handled.
• All components of the approach are simple to implement and
3
Meshless Animation
very efﬁcient in terms of memory requirements and run-time
performance.
Newton’s second law of motion is the common basis for many
physically-based simulation techniques including rigid body simu-
2
Related Work
lation, deformable modeling, and ﬂuid simulation. Deviations from
an equilibrium cause forces which accelerate the material back to an
equilibrium conﬁguration. In order to compute object locations, the
Many methods and models have been proposed in computer graph-
accelerations and velocities are numerically integrated over time.
ics to simulate deformable objects ranging from ﬁnite difference
approaches [Terzopoulos et al. 1987], mass-spring systems [Baraff
Stability and efﬁciency are major issues in numerical integration.
and Witkin 1998], [Desbrun et al. 1999], the Boundary Element
Implicit integration schemes guarantee stability independent of the
Method (BEM) [James and Pai 1999], the Finite Element Method
chosen time step. However, they require the solution of a system of
(FEM) [Debunne et al. 2001], [M¨uller et al. 2002], [M¨uller and
equations which is computationally expensive and potentially in-
Gross 2004], the Finite Volume Method (FVM) [Teran et al. 2003]
terferes with the constraints of interactive applications. In contrast,
to implicit surfaces [Desbrun and Cani 1995] and mesh-free par-
explicit integration schemes are much faster to compute. Unfor-
ticle systems [Desbrun and Cani 1996], [Tonnesen 1998], [M¨uller
tunately, this advantage comes with the loss of unconditional sta-
et al. 2004].
bility. A prominent example is the explicit Euler scheme which is
unconditionally unstable if applied to linear undamped mass-spring
In addition to approaches which mainly focus on the accurate simu-
systems [Eberly 2003].
lation of elasto-mechanical properties, there exist several accelera-
tion strategies. Robust integration schemes for large time steps have
In this section, we illustrate instability aspects of explicit integra-
been investigated [Baraff and Witkin 1998] and multi-resolution
tion schemes and we show how to obtain unconditional stability
models have been proposed [Debunne et al. 2001], [Capell et al.
using a purely geometric scheme. We point out, how the proposed
2002], [Grinspun et al. 2002]. To further improve the performance,
geometric scheme combines computational efﬁciency and uncondi-
modal analysis approaches have been employed which can trade
tional stability which makes the approach especially appropriate for
accuracy for efﬁciency [Pentland and Williams 1989], [Shen et al.
interactive deformable modeling applications. Although there exist
2002], [James and Pai 2002]. Further, data-driven methods have
many different explicit integration schemes, they all have the afore-
been presented where the pre-computed state space dynamics and
mentioned stability problem in common. Therefore, we exemplify
pre-computed impulse response functions are incorporated to im-
stability aspects using a modiﬁed Euler method from which we de-
prove the run-time performance [James and Pai 1999]. In [Metaxas
rive our unconditionally stable geometric scheme.

3.1
Explicit Numerical Integration
overall energy has erroneously increased. In subsequent steps the
problem gets worse because the restoring force will be even larger
We consider a linear undamped mass-spring system to illustrate the
than in earlier time steps.
instability of explicit methods. Fig. 2 shows a linear spring with
In general, the stability problem of explicit integration schemes can
resting length l0 and spring constant k. The spring connects two
be stated as follows: Elastic forces are the negative gradients of
points. One point is ﬁxed at the origin while the other point with
the elastic energy. As such, they always point towards an equilib-
mass m is free and located at x(t). The free point is pulled towards
rium conﬁguration. However, explicit schemes scale these forces
the equilibrium x(t) = l0 by the force f = −k(x(t) − l0).
blindly to compute displacements of points. Therefore, displace-
ments can overshoot the equilibrium by an amount which increases
f = −k(x(t) − l
the deformation and the energy of the system instead of preserving
0 )
m
m
or decreasing it which is required for stability.
One way to solve this problem would be to clamp the displacements
0
l0
x(t)
such that points do not overshoot the equilibrium or goal position.
In the simple one-dimensional spring example, the goal position
of the moving point is simply x(t) = l0. Unfortunately, in more
2
h k
general cases such as solid ﬁnite elements or geometrically complex
x
∆ = −
(x(t) − l0)
m
meshes, goal positions of individual points cannot be deﬁned easily.
Our new approach solves this problem.
0 x(t+h)
l0
x(t)
3.2
The Algorithm
Figure 2: A linear spring integrated with the explicit scheme as
shown in Eq. (1). If the time step is too large, internal forces erro-
g
0
g
0
x
x
3
3
4
3
x
neously increase the energy of the system.
x4
4
R
x
g
x
g
3
3
4
4
t
With the modiﬁed Euler integration scheme
x
x
1
g
1
g2
0
x
0
x
2
x
x
2
2
g
−
1
2
g
k(x(t) − l
1
1
v(t + h)
= v(t) + h
0)
m
Figure 3: First, the original shape x0 is matched to the deformed
x(t + h)
= x(t) + hv(t + h),
(1)
i
shape xi. Then, the deformed points xi are pulled towards the
matched shape g
the point velocity v is integrated with an explicit Euler step while
i.
the point position x is integrated with an implicit Euler step using
the predicted velocity. Considering the state vector [v x]T , Eq. (1)
The basic idea behind our geometric algorithm is simple. All we
results in the system matrix
need as input is a set of particles with masses mi and an initial con-
ﬁguration (i. e. the initial positions x0 of the particles). No connec-
i
1
− kh
tivity information or mesh is needed. The particles are simulated as
m
A =
(2)
a simple particle system without particle-particle interactions, but
h
1 − h2k
including response to collisions with the environment and including
m
external forces such as gravity. After each time step, each particle is
with eigenvalues
pulled towards its goal position gi. To compute the individual goal
positions, we match the original conﬁguration (or shape) deﬁned
e
by the x0 with the actual conﬁguration deﬁned by the actual posi-
0 = 1 − 1 (h2k −
−4mh2k + h4k2)
(3)
i
2m
tions of the particles xi (see Fig. 3). The next two sections describe
the shape matching process and how points are pulled towards goal
and
positions.
e1 = 1 − 1 (h2k +
−4mh2k + h4k2)
(4)
2m
Since A represents a discrete system, the spectral radius of A , i. e.
3.3
Shape Matching
the maximum magnitude of the eigenvalues e0 and e1, must not be
larger than one to ensure stability of the system. The magnitude of
In our approach, the shape matching problem with a priori known
eigenvalue e0 converges to 1 with |e0| < 1 for h2k → ∞. However,
correspondences can be stated as follows: Given two sets of points
it can be easily shown that the magnitude of e1 is only smaller than
x0 and x
one if h is smaller than 2
m . If a larger time step h is chosen the
i
i. Find the rotation matrix R and the translation vectors t
k
and t
system is unstable. Thus, the integration scheme is only condition-
0 which minimize
ally stable.
∑wi(R(x0 −
i
t0) + t − xi)2,
(5)
To further exemplify the instability of the system, we perform one
i
integration step assuming v(t) = 0. The step moves the free point
where the wi are weights of individual points. In our case, the nat-
by a distance ∆x = − h2k (x(t) − l
m
0). If either the time step h or
ural choice for the weights is wi = mi. The optimal translation vec-
the stiffness k are too large or the mass m is too small, the point
tors turn out to be the center of mass of the initial shape and the
not only overshoots the equilibrium position at l0 but is moved to a
center of mass of the actual shape, i. e.
position where the spring deformation |x(t)−l0| is larger than in the
previous time step (see Fig. 2 bottom). The potential energy of the
system has increased. Since we started with zero kinetic energy, the
t0 = x0 = ∑i mix0i ,
,
cm
t = x
(6)
∑
cm = ∑i mixi
i mi
∑i mi

Figure 4: The basic shape matching algorithm is well suited for nearly rigid objects (third cube). The linear and quadratic extensions (middle
and ﬁrst cube) allow large deviations form the rest shape.
which is physically plausible.
Finding the optimal rotation is
3.5
Discussion
slightly more involved. Let us deﬁne the relative locations qi =
x0 − x0
i
cm and pi = xi − xcm of points with respect to their center
The described algorithm can be implemented efﬁciently. Both, the
of mass and let us relax the problem of ﬁnding the optimal rota-
center of mass of the initial conﬁguration x0cm as well as all qi can be
tion matrix R to ﬁnding the optimal linear transformation A. Now,
pre-computed. At each time step, the 3 × 3 matrix Apq = ∑i mipiqT
the term to be minimized is ∑
i
i mi(Aqi − pi)2. Setting the deriva-
tives with respect to all coefﬁcients of A to zero yields the optimal
has to be assembled. To evaluate ( ATpqApq)−1, we diagonalize
transformation
the symmetric matrix ATpqApq using 5-10 Jacobi rotations, the com-
plexity of which is constant, i. e. independent of the number of
A = (∑mipiqT )(
)−1 =
i
∑miqiqTi
ApqAqq.
(7)
points. In contrast to most methods for simulating deformable ob-
i
i
jects, the approach described so far is well-suited for stiff or almost
The second term Aqq is a symmetric matrix and, thus, contains only
rigid objects. In this basic form, it is less suited for objects under-
scaling but no rotation. Therefore, the optimal rotation R is the
going large deformations, a limitation that is eliminated in Sections
rotational part of Apq which can be found via a polar decomposi-
4.2 and 4.3.
tion Apq = RS, where the symmetric part is S =
ATpqApq and the
The fact that the shapes are matched using their centers of mass
rotational part is R = A
ensures that all impulses applied in Eq. (9) sum up to zero and con-
pqS−1. Finally, the goal positions can be
computed as
serve linear momentum. By using the mi as the weights in shape
g
matching and the computation of A
i = R(x0 −
) +
pq conservation or angular mo-
i
x0cm
xcm.
(8)
mentum is enforced as well.
A problem with the velocity update in Eq. (9) is that the behavior of
3.4
Integration
the system depends on the time step, i. e. the velocity update is the
same for varying time steps. This problem can be solved by setting
The knowledge of the goal positions gi can now be used to construct
α = h/τ, where τ ≤ h is a time constant.
an integration scheme which does not overshoot:
vi(t + h)
= vi(t) + α gi(t) − xi(t) + h fext(t)/mi
(9)
4
Extensions
h
xi(t + h)
= xi(t) + hvi(t + h),
(10)
where α = [0 ... 1] is a parameter which simulates stiffness. The
4.1
Rigid Body Dynamics
only difference to the modiﬁed Euler scheme in Eq. (1) is the way
the internal elastic forces are treated. For α = 1, the term (g
The method can be used to imitate a rigid body simulator by setting
i(t) −
x
α = 1. In this case, the points are moved to the goal positions g
i(t))/h is added to the velocity and, thus, gi(t) − xi(t) is added to
i
the position in the second line moving the point directly to the goal
exactly at each time step. These positions represent a rotated and
position, or towards the goal position for α < 1.
translated version of the initial shape. Given an arbitrary surface
mesh, only a small subset of the vertices need to be animated as
For the one-dimensional spring example shown in Fig. 2, this itera-
particles. The remaining vertices can be transformed at each time
tive scheme yields the following update rule:
step using the computed transformation given by R and t. The same
holds for the methods described in the subsequent sections.
v(t + h)
v(t)
(11)
x(t + h)
=
1
−α/h
h
1 − α
x(t)
+ αl0/h
αl0
4.2
Linear Deformations
The ﬁrst term on the right hand side is the system matrix. Its eigen-
√
As mentioned before, the method described so far can only sim-
values are (1−α/2)±i 4α − α2/2. The magnitude of both eigen-
ulate small deviations from the rigid shape. To extend the range
values is 1, independent of α and the time step h. This shows that
of motion, we use the linear transformation matrix A computed in
the scheme is unconditionally stable and does not introduce damp-
Eq. (7). This matrix describes the best linear transformation of the
ing. This is also true for the general 3D case without external forces.
initial shape to match the actual shape in the least squares sense.
As long as the external forces are independent of the locations of
Instead of using R in Eq. (8) to compute the gi, we use the combi-
the points (such as gravitational forces) or applied only instanta-
nation β A + (1 − β )R, where β is an additional control parameter.
neous (such as collision response forces), the system matrix does
This way, the goal shape is allowed to undergo a linear transfor-
not change and the system remains stable.
mation. The presence of R in the sum ensures that there is still a

Figure 5: Visualization of all 3 × 9 modes deﬁned by the coefﬁcients of ˜
A = [A Q M] deﬁned in Eq. (12).
tendency towards the undeformed shape. To make sure that volume
to all the particle it contains, where gc(t) is the goal position of
i
is conserved, we divide A by 3 det(A) ensuring that det(A) = 1.
particle i with respect to cluster c.
For the standard approach we only need to compute Apq. Here, we
also need the matrix Aqq = (∑i miqiqT )−1
i
. Fortunately, this sym-
metric 3 × 3 matrix can be pre-computed.
4.5
Plasticity
4.3
Quadratic Deformations
Linear transformations can only represent shear and stretch. To
extend the range of motion by twist and bending modes, we move
from linear to quadratic transformations (see Fig. 4). We deﬁne a
quadratic transformation as follows:
gi = [A Q M] ˜
qi,
(12)
where gi ∈ R3, ˜q = [qx, qy, qz, q2,
, ,
x q2
y q2
z
qxqy, qyqz, qzqx]T ∈ R9,
A ∈ R3×3 contains the coefﬁcients for the linear terms, Q ∈ R3×3
the coefﬁcients for the purely quadratic terms and M ∈ R3×3 the co-
Figure 6: A cube deﬁned by 8 clusters undergoes plastic deforma-
efﬁcients for the mixed terms. With ˜
A = [A Q M] ∈ R3×9 we now
tions.
have to minimize ∑i mi( ˜A ˜
qi − pi)2. The optimal quadratic transfor-
mation turns out to be
The algorithm for linear deformations described in Section 4.2 can
˜
A = (∑m
˜
easily be extended to simulate plasticity. In Section 3.3, we ex-
ipi ˜
qT )(
)−1 = ˜
i
∑mi˜qi˜qTi
ApqAqq.
(13)
i
i
tracted the rotational part R of the linear transformation A using po-
lar decomposition. Therefore, A = RS, where the matrix S = RTA
Again, the symmetric ˜
Aqq ∈ R9×9 as well as the ˜qi can be pre-
represents pure deformation. Because S is post-multiplied with R,
computed. Analogous to the linear case, we use β ˜A + (1 − β ) ˜R to
it represents a deformation in the initial, unrotated reference frame.
compute the goal shape, where ˜
R ∈ R3×9 = [R 0 0]. The algorithm
Each cluster stores a plastic deformation state matrix Sp. This state
based on quadratic deformations is a computationally cheap imita-
matrix is initialized with the identity matrix I. At each time step, if
tion of methods using modal analysis. The linear shear and stretch
the actual deformation ||S − I||2 exceeds a threshold cyield, the state
modes and the additional bend and twist modes are shown in Fig. 5.
matrix is updated as
Sp ← [I + hccreep(S − I)]Sp,
(15)
4.4
Cluster Based Deformation
where h is the time step and cyield and ccreep are parameters to con-
To extend the range of motion even further, the set of particles
trol the plasticity [O’Brien et al. 2002]. The plasticity can be bound
can be divided into overlapping clusters. One way of doing this
by testing whether ||Sp − I||2 exceeds a threshold cmax. If this is the
would be to use a volumetric mesh and interpret the vertices as par-
case, the plastic deformation is set to I + cmax(Sp − I)/||Sp − I||2.
ticles and groups of vertices that are adjacent to the same element
To make sure that volume is conserved by plasticity, we divide Sp
(e. g. tetrahedron) as a cluster. To generate the results in this paper,
by 3 det(Sp) after it has been updated. Finally, the plastic state
we used an alternative method. We regularly subdivide the space
Sp is incorporated by replacing the deﬁnition of qi = x0 − x0
around a given surface mesh into overlapping cubical regions. For
i
cm in
Eq. (7) with
each region, we generate one cluster with all the vertices contained
in this region.
qi = Sp(x0 −
),
i
x0cm
(16)
At each integration step, the original shape of each cluster is
thereby deforming the original shape. Note that each time Sp is
matched with its actual shape. Then each cluster adds the term
updated, Aqq respectively ˜
Aqq have to be updated too. Fig. 6 shows
(t) − x
two different rest states after plastic deformation. To increase the
∆
i(t)
vi = α gci
(14)
level of detail, the cube is subdivided into 8 clusters.
h

5
Results
number of clusters requires more polar decompositions which re-
duces the performance. Also, the computation of the quadratic de-
formation model is more involved compared to the linear model.
We have integrated our method into a game-like simulation envi-
Still, 100 objects each containing 100 simulated points subdivided
ronment for deformable objects and various experiments have been
into 8 clusters can be animated with the quadratic approach at 50
carried out to analyze the characteristics and the performance of the
frames per second.
proposed method. All test scenarios presented in this section have
been performed on a PC Pentium 4, 3.2 GHz.
It is difﬁcult to compare our approach to the Finite Element Method
or mass-spring models in terms of performance. As Fig. 8 shows,
our technique depends on the deformation modes and the number
of clusters chosen with no analogy in FEM or mass-spring systems.
Complex simulation scenarios. Fig. 9 depicts a scene of 384 ob-
jects, 2, 448 clusters and 55, 200 points. The quadratic shape match-
ing in this case takes between 0.008 and 0.096 milliseconds per
frame and object depending on object complexity. In the teaser se-
quence Fig. 1 145 objects, 1, 728 clusters and 24, 618 points are
animated. The quadratic shape matching takes 0.12 milliseconds
per frame and object.
Figure 7: The ﬂexibility of the object is inﬂuenced by the number
Interactivity. Fig. 10 illustrates objects whose geometrical com-
of clusters. In this example, one, two, and ﬁve clusters are used
plexity can be considered typical for games: a head consisting of 8
from left to right, respectively.
clusters and 66 points, and some spheres consisting of 1 cluster and
13 points. To improve the visual impression, the objects are com-
bined with surface meshes, consisting of 6, 460 and 2, 000 faces,
Cluster based deformation. In Fig. 7, three quadratically de-
respectively. This environment can be handled at interactive frame
forming sticks with 60 points, but different numbers of clusters are
rates including user interaction with draggers, collision handling,
shown. From left to right, the sticks are subdivided into one, two,
and visualization.
and ﬁve clusters. In each ﬁgure, a spring forces is applied to the
same surface point and originating from the same location in space.
Stability. Fig. 11 demonstrates the fact that our approach can han-
The experiment shows, that with an increasing number of clusters,
dle degenerated geometries. In combination with the unconditional
the deformation gets more detailed and the physical plausibility is
stability of the numerical integration scheme, this allows for stable
improved. In general, the number of clusters is user deﬁned. For
animations independent of any user interaction.
simple, sphere-like objects, one cluster might me sufﬁcient while
for more complex geometries a subdivision might be necessary.
6
Conclusions and Future Work
5.0
linear_1
We have presented a new approach to geometric deformations.
4.0
linear_8
The underlying model is related to modal analysis approaches, but
linear_64
shows various differences. Our model does not require any pre-
) 3.0
quadratic_1
processing or auxiliary data structures, it is efﬁcient to compute,
(ms
quadratic_8
and provides unconditionally stable simulations. However, in con-
me
ti
quadratic_64
2.0
trast to modal analysis approaches our model is not physically mo-
tivated. While the accuracy of modal analysis methods can be ar-
bitrarily improved by just considering a larger number of deforma-
1.0
tion modes, our approach gets more involved if additional higher-
order deformation modes would be considered. Further, higher-
0.0
order modes do not necessarily improve the modeling accuracy in
0
2000
4000
6000
8000
10000
our approach, since they are not related to physical vibration modes.
number of points
Our approach can handle a reasonable number of deformable ob-
Figure 8: Time complexity of the presented methods in millisec-
jects in real-time. However, adequate collision handling is required.
onds per frame versus the number of points being simulated.
In order to illustrate our results, we have used an existing penalty-
based collision handling technique [Teschner et al. 2003], [Heidel-
berger et al. 2004], but found it to be a performance bottleneck.
Performance. The performance of our approach depends on the
Alternatively, the Bounded Deformation Tree [James and Pai 2004]
number of points that are used for the shape matching and on the
could be considered. Although the existing work is very promising,
number of clusters. In order to illustrate the scaling of the per-
further research in deformable collision handling is necessary to
formance with respect to these two criterions, we have performed
match the advances in deformable modeling [Teschner et al. 2005].
the following experiment. A number of points are placed at arbi-
trary positions and corresponding arbitrarily placed goal positions
The ”plug and simulate” handling of a large variety of objects, the
are deﬁned, resulting in a random initial displacement for each
efﬁciency in terms of memory and computational complexity, and
point. Based on this scenario, measurements have been performed
the unconditional stability of the dynamic simulation make the ap-
with varying numbers of points and clusters employing linear and
proach particularly interesting for games. While we have investi-
quadratic deformation models. Note, that the computational com-
gated plasticity as one of the ﬁrst model extensions, ongoing work
plexity of the rigid body case is equal to the linear deformation
focuses on further extensions such as fracture animation. Fractur-
model. Fig. 8 illustrates the results. It can be seen, that the perfor-
ing is particularly interesting since changing connectivity requires
mance scales linearly with the number of points. Further, a larger
only minor updates of data structures.

Figure 9: In this massive scene consisting of 384 objects, the computation of the dynamics is possible in real-time while collision detection
and collision response computations are not.
Figure 10: A head model simulated with 8 clusters reacts to user interaction or to collisions with other deformable objects.
Figure 11: Squeezing a duck model demonstrates the stability of the approach and the ability to recover from highly deformed or inverted
conﬁgurations.
7
Acknowledgements
BARZEL, R., HUGHES, J. F., AND WOOD, D. N. 1996. Plausible
motion simulation for computer graphics animation. Proceed-
ings of the Eurographics Workshop on Computer Animation and
The authors would like to thank Marco Heidelberger for the duck
Simulation, 183–197.
model. This project was funded by the Swiss National Commission
for Technology and Innovation (CTI) project no. 6310.1 KTS-ET.
BARZEL, R. 1997. Faking dynamics of ropes and springs. IEEE
Computer Graphics and Applications 17, 31–39.
References
BESL, P., AND MCKAY, N. 1992. A method for registration of 3-
d shapes. IEEE Transactions on Pattern Analysis and Machine
Intelligence 14, 2, 239–256.
ALEXA, M., COHEN-OR, D., AND LEVIN, D. 2000. As-rigid-
as-possible shape interpolation. In Computer Graphics Proceed-
ings, Annual Conference Series, ACM SIGGRAPH 2000, 157–
CAPELL, S., GREEN, S., CURLESS, B., DUCHAMP, T., AND
164.
POPOVIC, Z. 2002. Interactive skeleton-driven dynamic de-
formations. In Proceedings of SIGGRAPH 2002, ACM Press
BARAFF, D., AND WITKIN, A. 1998. Large steps in cloth simula-
/ ACM SIGGRAPH, Computer Graphics Proceedings, Annual
tion. In Proceedings of SIGGRAPH 1998, 43–54.
Conference Series, ACM, 586–593.

DEBUNNE, G., DESBRUN, M., CANI, M. P., AND BARR, A. H.
LORUSSO, A., EGGERT, D. W., AND FISHER, R. B. 1995. A
2001. Dynamic real-time deformations using space & time adap-
comparison of four algorithms for estimating 3-d rigid transfor-
tive sampling. In Computer Graphics Proceedings, Annual Con-
mations. In BMVC ’95: Proceedings of the 1995 British confer-
ference Series, ACM SIGGRAPH 2001, 31–36.
ence on Machine vision (Vol. 1), BMVA Press, 237–246.
DESBRUN, M., AND CANI, M.-P. 1995. Animating soft sub-
METAXAS, D., AND TERZOPOULOS, D. 1992. Dynamic defor-
stances with implicit surfaces. In Computer Graphics Proceed-
mation of solid primitives with constraints. In Computer Graph-
ings, ACM SIGGRAPH, 287–290.
ics Proceedings, Annual Conference Series, ACM SIGGRAPH
1992, 309–312.
DESBRUN, M., AND CANI, M.-P. 1996. Smoothed particles: A
new paradigm for animating highly deformable bodies. In 6th
M ¨ULLER, M., AND GROSS, M. 2004. Interactive virtual materials.
Eurographics Workshop on Computer Animation and Simulation
Proceedings of Graphics Interface (GI 2004), 239–246.
’96, 61–76.
M ¨ULLER, M., DORSEY, J., MCMILLAN, L., JAGNOW, R., AND
DESBRUN, M., SCHRODER, P., AND BARR, A. H. 1999. Inter-
CUTLER, B. 2002. Stable real-time deformations. Proceedings
active animation of structured deformable objects. In Graphics
of 2002 ACM SIGGRAPH Symposium on Computer Animation,
Interface, 1–8.
49–54.
E
M ¨
BERLY, D. H. 2003. Game Physics. Morgan Kaufmann.
ULLER, M., KEISER, R., NEALEN, A., PAULY, M., GROSS,
M., AND ALEXA, M. 2004. Point based animation of elas-
FAUGERAS, O. D., AND HEBERT, M. 1983. A 3-d recognition and
tic, plastic and melting objects. Proceedings of 2004 ACM SIG-
positioning algorithm using geometric matching between primi-
GRAPH Symposium on Computer Animation, 141–151.
tive surfaces. In Int. Joint Conference on Artiﬁcial Intelligence,
996–1002.
O’BRIEN, J. F., BARGTEIL, A. W., AND HODGINS, J. K. 2002.
Graphical modeling and animation of ductile fracture. In Pro-
GRINSPUN, E., KRYSL, P., AND SCHRODER, P. 2002. Charms:
ceedings of SIGGRAPH 2002, ACM Press / ACM SIGGRAPH,
A simple framework for adaptive simulation. In Proceedings of
Computer Graphics Proceedings, Annual Conference Series,
SIGGRAPH 2002, ACM Press / ACM SIGGRAPH, Computer
ACM, 291–294.
Graphics Proceedings, Annual Conference Series, ACM, 281–
PENTLAND, A., AND WILLIAMS, J.
1989.
Good vibrations:
290.
Modal dynamics for graphics and animation.
In Computer
HAUSER, K. K., SHEN, C., AND O’BRIEN, J. F. 2003. Interactive
Graphics Proceedings, Annual Conference Series, ACM SIG-
deformation using modal analysis with constraints. In Graph-
GRAPH, 215–222.
ics Interface, A K Peters, CIPS, Canadian Human-Computer
SHEN, C., HAUSER, K., GATCHALIAN, C., AND O’BRIEN, J.
Commnication Society, 247–256.
2002. Modal analysis for real-time viscoelastic deformation.
HEIDELBERGER, B., TESCHNER, M., KEISER, R., M ¨ULLER, M.,
ACM SIGGRAPH 2002 Conference Abstracts and Applications
AND GROSS, M. 2004. Consistent penetration depth estima-
(july).
tion for deformable collision response. In Proceedings of Vision,
SHOEMAKE, K., AND DUFF, T. 1992. Matrix animation and polar
Modeling, Visualization VMV’04, Stanford, USA, 339–346.
decomposition. In Graphics Interface, 258–264.
HORN, B. K. P. 1987. Closed-form solution of absolute orientation
TERAN, J., BLEMKER, S., HING, V. N. T., AND FEDKIW, R.
using unit quaternions. Journal of the Optical Society of America
2003. Finite volume methods for the simulation of skeletal mus-
A 4, 4, 629–642.
cle. Proceedings of 2003 ACM SIGGRAPH Symposium on Com-
I
puter Animation, 68–74.
RVING, G., TERAN, J., AND FEDKIW, R. 2004. Invertible ﬁnite
elements for robust simulation of large deformation. Eurograph-
TERZOPOULOS, D., PLATT, J., BARR, A., AND FLEISCHER, K.
ics (Sept.), 131–140.
1987. Elastically deformable models. In Computer Graphics
Proceedings, Annual Conference Series, ACM SIGGRAPH 87,
JAMES, D., AND PAI, D. K. 1999. Artdefo, accurate real time
205–214.
deformable objects. In Computer Graphics Proceedings, Annual
Conference Series, ACM SIGGRAPH 99, 65–72.
TESCHNER, M., HEIDELBERGER, B., M ¨ULLER, M., POMER-
ANETS, D., AND GROSS, M. 2003. Optimized spatial hashing
JAMES, D. L., AND PAI, D. K. 2002. Dyrt: Dynamic response
for collision detection of deformable objects. In Proceedings of
textures for real time deformation simulation with graphics hard-
Vision, Modeling, Visualization VMV’03, 47–54.
ware. In Computer Graphics Proceedings, Annual Conference
Series, ACM SIGGRAPH, 582–585.
TESCHNER, M., KIMMERLE, S., HEIDELBERGER, B., ZACH-
MANN, G., RAGHUPATHI, L., FUHRMANN, A., CANI, M.-
JAMES, D. L., AND PAI, D. K. 2004. Bd-tree: output-sensitive
P., FAURE, F., MAGNENAT-THALMANN, N., STRASSER, W.,
collision detection for reduced deformable models. ACM Trans.
AND VOLINO, P. 2005. Collision detection for deformable ob-
Graph. 23, 3, 393–398.
jects. Computer Graphics Forum 24, 1 (March), 61–81.
KANATANI, K. 1994. Analysis of 3-d rotation ﬁtting. IEEE Trans.
TONNESEN, D. 1998. Dynamically Coupled Particle Systems for
Pattern Anal. Mach. Intell. 16, 5, 543–549.
Geometric Modeling, Reconstruction, and Animation. PhD the-
K
sis, University of Toronto.
AZHDAN, M., FUNKHOUSER, T., AND RUSINKIEWICZ, S.
2004. Shape matching and anisotropy. ACM Trans. Graph. 23,
UMEYAMA, S. 1991. Least squares estimation of transformation
3, 623–629.
parameters between two point patterns. IEEE Transactions on
Pattern Analysis and Machine Intelligence 13, 4 (Apr.), 376–80.
KENT, J. R., CARLSON, W. E., AND PARENT, R. E. 1992. Shape
transformation for polyhedral objects. Computer Graphics 26,
47–54.