Keyframe Animation of Implicit Models

by
David I. White
[Link]., The University of Western Ontario, 2004
A THESIS SUBMITTED IN PARTIAL FULFILMENT OF
THE REQUIREMENTS FOR THE DEGREE OF
Master of Science
in
The Faculty of Graduate Studies
(Computer Science)
The University Of British Columbia
August 2006
c David I. White, 2006
ii
Abstract
We present an approach that automatically constructs physically plausible in-
between frames, given keyframes of arbitrary implicit surface geometry and
feature points registered between adjacent keyframes. This extends to usable
keyframe control of computer animated uid-like materials. Most current im-
plicit surface morphs do not allow feature point tracking and none guarantee
physically plausible in-between frames of arbitrary motion. Standard triangle
surface mesh morphing techniques do not guarantee physically plausible in-
betweens either, nor can they handle topological changes. Current uid control
approaches do not respect keyframes nor track feature points.
Our variational approach nds a volume mapping between keyframes
which minimizes a physics-based objective function using Gauss-Newton modi-
ed to handle linear constraints. We then create as-rigid-as-possible trajectories
of the volume respecting this map, which we use to create physically plausible
in-between frames.
iii
Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Image Morphing . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Morphing with Tetrahedral Meshes . . . . . . . . . . . . . 3
1.2.3 Implicit Surface Morphing . . . . . . . . . . . . . . . . . . 3
1.2.4 Fluid Simulation for Computer Animation . . . . . . . . . 4
1.2.5 Controllable Fluid Simulations . . . . . . . . . . . . . . . 4
1.3 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Mapping Adjacent Keyframes . . . . . . . . . . . . . . . . . . . . 8
2.1 Keyframe Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . 9
Contents iv
2.3 Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Modied Gauss-Newton Optimization . . . . . . . . . . . . . . . 14
3 Computing In-between Frames . . . . . . . . . . . . . . . . . . . . 18
3.1 Rigid Trajectories . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Level Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1 Rigid Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Topological Changes . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.3 Articulated Motion . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4 Splash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . 27
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2.1 Cartoony Fluids . . . . . . . . . . . . . . . . . . . . . . . 28
5.2.2 Hands-on Control . . . . . . . . . . . . . . . . . . . . . . 28
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
A Optimal Rotation in Two Dimensions . . . . . . . . . . . . . . . 36
v
List of Tables
4.1 Number of feature points in presented simulations. . . . . . . . . 21
vi
List of Figures
1.1 An example of input to our system: initial (a) and nal (b) im-
plicit surfaces, and their respective feature points (c) and (d). . . 5
1.2 Our computed mapping from the initial keyframe (a) to the nal
keyframe (b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 The as-rigid-as-possible trajectories from our initial keyframe to
the nal keyframe. . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 The output of our system: in-between frames that correspond to
the input keyframes. . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Nave (a) and subdivided (b) discretization of a two-dimensional
grid cell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Nave (a) and subdivided (b) discretization of a three-dimensional
grid cell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Barycentric weights, t
i
, of y

i
in the grid dened by x
1
, x
2
, x
3
,
and x
4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.1 A Cartesian grid representation of three-dimensional rigid ex-
amples: rotation (top row), translation (middle row), and both
translation and rotation (bottom row). . . . . . . . . . . . . . . . 23
4.2 Two-dimensional merging example, with the rst and last images
as keyframes. The level sets are displayed, as are the feature points. 24
List of Figures vii
4.3 Two-dimensional bending example, with the rst and last images
as keyframes. The level sets are displayed, as are the feature points. 25
4.4 Two-dimensional splashing example with the level set and feature
points shown. The rst, third, fth and seventh images represent
keyframes. The initial grid points, warped to their intermediate
or nal positions are also shown. . . . . . . . . . . . . . . . . . . 26
viii
Acknowledgements
This thesis would not have been possible without the insight and guidance of my
supervisor, Robert Bridson. First and foremost I am grateful to him. Secondly,
thanks to my second reader Michiel van de Panne for his helpful comments. He
and Kevin Loken were incredible research collaborators as well.
Thanks also to Scott Singer, who provided motivation and advice during
SIGGRAPH this summer.
For a fun, yet productive work environment I thank the crew from Imager;
there are too many individuals to mention by name, but how can I forget Bi?
Dima, Scott, Dustin, Dan, Greg, Thomas, Bram and Christopher, thanks
for making the Orphanage a great place to live.
Thanks to my family especially my sister and parents, without whom I might
still think dogs run on batteries or worse yet, have never questioned it.
DAVID I. WHITE
The University of British Columbia
August 2006
1
Chapter 1
Introduction
What the animator does on each frame of lm is not as important
as what he or she does in between.
- Norman McLaren
Keyframe-based animation of general shapes is dicult on the computer. We
provide a solution that can automatically construct physically plausible in-
between frames given implicit surface keyframes of arbitrary geometry. Implicit
surfaces are an attractive representation for general shapes that may undergo
extreme deformation or topological changes during animation. There are many
approaches to modeling objects with implicit surfaces, but there is little work
on animating them. Techniques for animating xed topology triangle meshes,
which do not undergo large deformation, based on morphing are becoming ma-
ture. The current state of morphing for implicit surfaces is comparatively more
primitive.
Our strategy is to nd a mapping between Cartesian grid points of adja-
cent implicit surface keyframes (Chapter 2), then estimate as-rigid-as-possible
trajectories of mapped points (Section 3.1), which are used to create implicit
surfaces for the in-between frames (Section 3.2).
Chapter 1. Introduction 2
1.1 Motivation
The inspiration for this work comes from the tradeo between physical realism
and directability in computer animated uids. Fluid simulations based on the
Navier-Stokes equations accurately represent the physical properties of uids,
but are computationally time consuming, dicult to create from scratch and
most importantly they oer no user-control of the uid. In practice, computer
animation studios generally use uid systems that are set up to be highly user-
intensive so that artists have control over the motion of the uid. However,
this can be time consuming and may lead to uid that does not move in a
physical manner. Our system allows full control of the uid through user-
dened keyframes and a minimal number of feature points, which we use to
create in-between frames that are physically plausible.
1.2 Previous Work
Considerable work has been done on morphing, which is analogous to creating
in-betweens for a given pair of keyframes. This work began with image morphing
techniques in the early 1990s.
1.2.1 Image Morphing
Image morphing techniques began with [3], which uses feature mapping to con-
trol the morph between two images. While this works well for its intended
purpose of simply blending two images, the created morph is non-physical. The
work of [37] produces a three-dimensional view morph from two-dimensional
images. It can produce physically consistent morphs, but not for arbitrary ob-
jects nor arbitrary motion. Image representations tend to lose or obscure detail.
For a more accurate representation of objects, we need to consider morphing of
Chapter 1. Introduction 3
geometric models.
1.2.2 Morphing with Tetrahedral Meshes
Standard morphing techniques based on triangle surface meshes [19, 29, 48]
generally preserve ne details well, but do not provide any guarantees of vol-
ume conservation nor do they handle topological changes. Least-distorting vol-
ume morphing techniques [1, 24] preserve volume but do not handle topological
changes. Topological changes are trivial if we consider implicit surfaces.
1.2.3 Implicit Surface Morphing
Current implicit surface morphing techniques [11, 47] successfully morph be-
tween given surfaces; however in-between surfaces are generally not physically
realistic. They do not guarantee preservation of volume, nor do they accurately
provide rigid motion. For static model morphing this is reasonable, but physical
in-between frames are crucial for keyframed animation. For example, [47] can-
not match a simple rigid rotation. The approach of [7] works well for globally
rigid movement, but will not hold for articulated motion. The volume morph
technique in [28] is still non-physical because it merely blends the two models,
which will not work for rigid motions. A novel, but non-physical, technique of
morphing by expansion and contraction of shapes is presented in [4]. A keyframe
technique is presented in [2], but it is contingent on an underlying skeletal struc-
ture and also is unproven for topological changes. In most of the aforementioned
approaches, it is not guaranteed that feature points will map as expected. For
example, the nose in an initial model may inadvertently map to an ear in the
nal model. With our user-dened feature points, we can guarantee a mapping
to the users specications.
Chapter 1. Introduction 4
1.2.4 Fluid Simulation for Computer Animation
Fluid simulation techniques for computer animation were rst presented in [34],
where particles were used to represent clouds, smoke, water and re. Later
on, [25] provided a model for animating propagations along water surfaces that
relied on solving the wave equation. The introduction of Navier-Stokes to com-
puter graphics, for modeling the full body of uid, came in [15]. A higher-level
look at this same method is [17], which also explains how it was used to animated
uids in the lm Antz the rst computer animated lm containing uids. A
few years later, this approach was extended to be unconditionally stable in [42],
which also introduced the semi-Lagrangian method. This was later rened for
inviscid uids, such as smoke, in [13] and liquids in [14]. The latter also intro-
duced level sets to the computer graphics community. Photorealistic computer
animated uids were rst shown in [10] by introducing, among other things, the
particle level set. More recent advances include: using the octree data struc-
ture [30], introducing vortices for more interesting motion [38], animating uids
on meshes [26], and multiple uids of dierent densities interacting [31]. For a
detailed introduction to uid simulation, see [5].
1.2.5 Controllable Fluid Simulations
Controllable uids for computer animation were introduced in [16], where the
user could change parameters to alter the uid motion. More recent work in
uid control can be split into two categories: target matching [12, 20, 39, 40, 41,
45, 46] and user-dened control points [32, 33, 43, 51]. The former have diculty
perfectly matching uid to the specied targets, and the latter use highly user-
intensive control methods. Our approach guarantees that we exactly match
the specied keyframes while keeping the number of user-dened control points
reasonable.
Chapter 1. Introduction 5
1.3 Algorithm Overview
Our system takes as input a series of keyframes and feature points. We compute
in-between frames for each pair of keyframes, and , and their corresponding
feature points, x

and y

(shown in Figure 1.1). Using this information we create

Figure 1.1: An example of input to our system: initial (a) and nal (b) implicit
surfaces, and their respective feature points (c) and (d).
a map, y, of each object point in our initial keyframe to a corresponding point
in the nal keyframe (shown in Figure 1.2). Initially we do this using Radial
Basis Functions built on the feature points, and then we use optimization to
modify the map to t several physical properties, such as volume conservation.
From the map we create trajectories for each point (shown in Figure 1.3). In
Figure 1.2: Our computed mapping from the initial keyframe (a) to the nal
keyframe (b).
Chapter 1. Introduction 6
order to capture rigid motions, such as rotations, these trajectories are as-rigid-
as-possible, and are computed locally to match articulated motion.
Figure 1.3: The as-rigid-as-possible trajectories from our initial keyframe to the
nal keyframe.
By sampling these trajectories, we create new implicit surfaces for in-between
frames (shown in Figure 1.4).
Figure 1.4: The output of our system: in-between frames that correspond to
the input keyframes.
Our approach is outlined in Algorithm 1.
Chapter 1. Introduction 7
Algorithm 1 System Overview
1: Input: keyframes (as implicit surfaces) and feature points mapped between
adjacent keyframes
2: for each pair of keyframes do
3: map grid points from the initial keyframe to the nal keyframe using
Radial Basis Functions based on the feature points
4: optimize this map using our physically based objective function and
Gauss-Newton modied to handle linear constraints
5: for each mapped point do
6: create a trajectory between the keyframes that is as-rigid-as-possible
7: end for
8: for each in-between frame do
9: create a level set based on the keyframe(s) and the trajectories
10: end for
11: Output: in-between frames
12: end for
8
Chapter 2
Mapping Adjacent
Keyframes
Given a series of keyframes represented as implicit surfaces and selected feature
points on adjacent keyframes, we nd a mapping of all the material points in
the initial frame to the material points in the nal frame. Using Radial Basis
Functions and the given feature points we obtain an initial guess for this map.
Then we optimize this map for physically realistic movement by minimizing
an objective function of physical properties. For this optimization we use the
Gauss-Newton method modied to include linear constraints. These constraints
ensure the feature points are mapped correctly, whether they lie on grid points,
or not.
2.1 Keyframe Input
The inputs to our system are keyframes, represented as implicit surfaces sampled
on regular Cartesian grids, and sets of selected feature points mapped between
adjacent keyframes. We compute intermediate frames between each pair of
adjacent keyframe surfaces, (x) and (y), and their corresponding feature
points, x

and y

. Feature points can be sparse, and can dier for each pairing
of keyframes. It is important to note that the feature points are not required to
align with the grid points as our optimizer is more general. Also they are not
Chapter 2. Mapping Adjacent Keyframes 9
conned to the material boundary - they can enter the interior of our material
as specied by the user.
2.2 Radial Basis Functions
Using the initial feature points, x

, and their nal positions, y

, we map the nal

positions of all the material points in our initial keyframe. This map, y(x), is
one-to-one and we present scenarios in
2
and
3
. It is used as an initial guess
for the optimization outlined in Section 2.3 and Section 2.5. Using the Radial
Basis Function formulation outlined in [6], we obtain our initial map in each
dimension from:
y(x) = x +p(x) +
N

i=1

i
R
B
(x (y

i
x

i
)
2
), (2.1)
ensuring that y(x

i
) = y

i
(2.2)
where R
B
is the Radial Basis Function, N is the number of feature points,
p(x) is a (dimension-1)-degree polynomial with M coecients c, and
i
are the
coecients of the Radial Basis Functions. Notice that we use the RBF to get a
mapping of displacements, so we convert it to nal values by adding the initial
locations of each point, x. This is dierent than the standard RBF formulation.
For two dimensions we use the thin-plate spline:
R
B
(r) = r
2
log r, (2.3)
and in three dimensions we use the triharmonic spline:
R
B
(r) = r
3
. (2.4)
Chapter 2. Mapping Adjacent Keyframes 10
To obtain and c, we solve:
_

_
A P
P
T
0
_

_
_

c
_

_ =
_

_
f
0
_

_, (2.5)
where
A
i,j
= R
B
(x
i
(y

j
x

j
)
2
), i, j = 1, ..., N
P
i,j
= p
j
(x
i
), i = 1, ..., N, j = 1, ..., M
f
i
= y(x

i
), i, j = 1, ..., N.
Given initial keyframes containing multiple objects, we perform the Radial
Basis Function step separately on each object.
2.3 Objective Function
At the heart of our system lies an objective function, f, that ensures the mapping
from initial to nal grid points, y(x), preserves certain physical properties. This
objective function is:
f(y) =
_
| det(
y
x
) 1|
2
+
_

y
x
T
y
x
I
2
F
(2.6)
+
_
H((x)) H((y(x)))
2
2
,
Chapter 2. Mapping Adjacent Keyframes 11
where and are the initial and nal keyframes, and H is the Heaviside
function:
H((x
ij
)) =
_

_
0 if (x
ij
) < ,
1
2
+
(xij)
2
+
1
2
sin
_
(xij)

_
if (x
ij
) ,
1 if < (x
ij
),
(2.7)
with =
3x
2
to numerically smear over several grid cells to permit gradient
estimates.
It is crucial that our feature points map properly, so this objective function
is subject to the constraints:
y(x

) = y

. (2.8)
In our objective function, the rst term resists volume change in the material
by ensuring that det
_
y
x
_
, the ratio of the approximated nal volume to the
actual initial volume of a grid cell, is close to one. The second term avoids
unnecessary deformation within the material, so for example we match rigid
body motions exactly. This is done by enforcing that the partial derivative with
respect to each point is dependent only on its nal position, and not that of
any of the other points. Meanwhile the third term matches the initial level set
surface to the mapped image on the nal level set surface by comparing the
Heaviside function at each initial grid point with the Heaviside function of the
corresponding nal mapped position. To account for additional criteria, more
terms could be added to this objective function. Prioritizing certain terms could
also be accomplished by adding scaling factors to the terms. We minimize this
objective function using the approach outlined in Section 2.5.
Chapter 2. Mapping Adjacent Keyframes 12
2.4 Discretization
Since our map is sampled on a Cartesian grid,
y
x
is computed in two dimensions
using the nave discretization:
y
x
=
_

_
u
1
u
2
v
1
v
2
_

_, (2.9)
where
u
1
=
(x
(1)
i+1,j+1
+x
(1)
i+1,j
)(x
(1)
i,j+1
+x
(1)
i,j
)
2u
,
u
2
=
(x
(1)
i+1,j+1
+x
(1)
i,j+1
)(x
(1)
i+1,j
+x
(1)
i,j
)
2u
,
v
1
=
(x
(2)
i+1,j+1
+x
(2)
i+1,j
)(x
(2)
i,j+1
+x
(2)
i,j
)
2v
,
v
2
=
(x
(2)
i+1,j+1
+x
(2)
i,j+1
)(x
(2)
i+1,j
+x
(2)
i,j
)
2v
.
Note: the superscript represents the dimension; it is not an exponent. Un-
fortunately this discretization (shown in Figure 2.1a) allows the emergence of
hour-glassing unwanted null-space modes where cells badly deform into
equal area trapezoids. So we further subdivide each grid cell into four parts
(shown in Figure 2.1b) and compute
y
x
for each of them.
The extension of this subdivision to three dimensions is shown in Figure 2.2,
Chapter 2. Mapping Adjacent Keyframes 13
and the discretization is:
y
x
=
_

_
u
1
u
2
u
3
v
1
v
2
v
3
w
1
w
2
w
3
_

_
, (2.10)
where
u
1
=
(x
(1)
i+1,j+1,k
+x
(1)
i+1,j,k
)(x
(1)
i,j+1,k
+x
(1)
i,j,k
)+(x
(1)
i+1,j+1,k+1
+x
(1)
i+1,j,k+1
)(x
(1)
i,j+1,k+1
+x
(1)
i,j,k+1
)
4u
,
u
2
=
(x
(1)
i+1,j+1,k
+x
(1)
i+1,j,k
)(x
(1)
i+1,j+1,k+1
+x
(1)
i+1,j,k+1
)+(x
(1)
i,j+1,k
+x
(1)
i,j,k
)(x
(1)
i,j+1,k+1
+x
(1)
i,j,k+1
)
4u
,
u
3
=
(x
(1)
i+1,j,k
+x
(1)
i,j,k
)(x
(1)
i+1,j,k+1
+x
(1)
i,j,k+1
)+(x
(1)
i+1,j+1,k
+x
(1)
i,j+1,k
)(x
(1)
i+1,j+1,k+1
+x
(1)
i+1,j,k+1
)
4u
,
v
1
=
(x
(2)
i+1,j+1,k
+x
(2)
i+1,j,k
)(x
(2)
i,j+1,k
+x
(2)
i,j,k
)+(x
(2)
i+1,j+1,k+1
+x
(2)
i+1,j,k+1
)(x
(2)
i,j+1,k+1
+x
(2)
i,j,k+1
)
4v
,
v
2
=
(x
(2)
i+1,j+1,k
+x
(2)
i+1,j,k
)(x
(2)
i+1,j+1,k+1
+x
(2)
i+1,j,k+1
)+(x
(2)
i,j+1,k
+x
(2)
i,j,k
)(x
(2)
i,j+1,k+1
+x
(2)
i,j,k+1
)
4v
,
v
3
=
(x
(2)
i+1,j,k
+x
(2)
i,j,k
)(x
(2)
i+1,j,k+1
+x
(2)
i,j,k+1
)+(x
(2)
i+1,j+1,k
+x
(2)
i,j+1,k
)(x
(2)
i+1,j+1,k+1
+x
(2)
i+1,j,k+1
)
4v
,
w
1
=
(x
(3)
i+1,j+1,k
+x
(3)
i+1,j,k
)(x
(3)
i,j+1,k
+x
(3)
i,j,k
)+(x
(3)
i+1,j+1,k+1
+x
(3)
i+1,j,k+1
)(x
(3)
i,j+1,k+1
+x
(3)
i,j,k+1
)
4w
,
w
2
=
(x
(3)
i+1,j+1,k
+x
(3)
i+1,j,k
)(x
(3)
i+1,j+1,k+1
+x
(3)
i+1,j,k+1
)+(x
(3)
i,j+1,k
+x
(3)
i,j,k
)(x
(3)
i,j+1,k+1
+x
(3)
i,j,k+1
)
4w
,
w
3
=
(x
(3)
i+1,j,k
+x
(3)
i,j,k
)(x
(3)
i+1,j,k+1
+x
(3)
i,j,k+1
)+(x
(3)
i+1,j+1,k
+x
(3)
i,j+1,k
)(x
(3)
i+1,j+1,k+1
+x
(3)
i+1,j,k+1
)
4w
.
Chapter 2. Mapping Adjacent Keyframes 14
Figure 2.1: Nave (a) and subdivided (b) discretization of a two-dimensional
grid cell.
2.5 Modied Gauss-Newton Optimization
To solve the objective function we use Gauss-Newton optimization. However,
since the optimal map must match the selected feature points, we have lin-
ear constraints. To perform this optimization we modify the standard Gauss-
Newton approach of:
min
y(x)
p(y)
2
, (2.11)
which updates each step, y
k
, by
J
T
k
J
k
y
k
= J
T
k
p(y
k
), (2.12)
where
J
k
=
p
y

y
k
. (2.13)
Chapter 2. Mapping Adjacent Keyframes 15
Figure 2.2: Nave (a) and subdivided (b) discretization of a three-dimensional
grid cell.
Our modied approach that satises linear constraints is:
min
y(x)
p(y)
2
, (2.14)
subject to Cy

= d, (2.15)
and y
k
is obtained from
_

_
J
T
k
J
k
C
T
C 0
_

_
_

_
y
k

_ =
_

_
J
T
k
p(y
k
)
0
_

_. (2.16)
Our initial map from the Radial Basis Functions matches the feature points
exactly, so the constraints are satised when the optimization begins. The
update steps, y
k
, then just have to maintain these constraints.
When the feature points lie along Cartesian grid points, our constraints are
Chapter 2. Mapping Adjacent Keyframes 16
simply:
C
ij
=
_

_
1 if y

i
is on grid point j,
0 otherwise,
(2.17)
d
i
= x

i
. (2.18)
For feature points that are not aligned with the grid points we use barycentric
weights, t
i
, to guarantee that the optimal map meets these constraints (Fig-
ure 2.3). Our constraints then become:
C
ij
=
_

_
t
i
if j is a grid point on the grid cell of y

i
,
0 otherwise,
(2.19)
d
i
= (t
1
+ t
2
+ t
3
+ t
4
)x

i
. (2.20)
Chapter 2. Mapping Adjacent Keyframes 17
Figure 2.3: Barycentric weights, t
i
, of y

i
in the grid dened by x
1
, x
2
, x
3
, and
x
4
.
18
Chapter 3
Computing In-between
Frames
Once we have obtained the optimal mapping from the initial keyframe to the
nal keyframe, we still need to compute the corresponding in-between frames.
In the traditional morphing sense, this is done simply by blending between the
initial and nal keyframes, with perhaps a small warp to help them match up.
We also take a warp and blend approach, though our warp does everything up to
truncation error in matching the implicit surfaces of the keyframes. The third
term of our objective function (Equation 2.3) corrects this (tiny) truncation
error. More sophisticated methods, [4], could be used if desired.
Our warping is carried out by creating as-rigid-as-possible trajectories for
each mapped point. We then create a level set at each intermediate time step by
blending the initial and nal implicit surfaces advected along these trajectories.
3.1 Rigid Trajectories
After we have computed the optimal map, we then create trajectories which are
the basis for the in-between frames. An obvious choice would be to move each
point along a straight line towards its nal location, however this fails to match
rigid rotations. Since we want the local neighbourhood of a point to be mapped
in a rigid manner, the trajectory should be the source of this rigidity. This
Chapter 3. Computing In-between Frames 19
gives a natural arc, instead of a straight line, for rotations. We generalize this
to as-rigid-as-possible by nding the rigid body motion as close as possible to
the deformation of the points neighbourhood. We use the following formulation
to compute the trajectory of an initial grid point, x
ij
, at the t
th
intermediate
frame:
x
(t)
ij
= x
ij
+ (x
ij
x)R

(x
ij
, t) +
_
t1
n1
_
( y x) (3.1)
+
_
t1
n1
_
(1
tn
)
_
y
ij
x
(n)
ij
_
,
where x is the mean of x, y is the mean of y, n is the total number of frames,
is the Kronecker Delta, x
(n)
ij
is the nal position of x
ij
, and R

(x
ij
, t) is the
optimal rotation of x
ij
and its grid neighbours at the t
th
frame.
For each mapped point we compute the translation and rotation component
of it and its nearest grid neighbours using the closed-form solution presented
in [21, 22]. For two dimensions we reduce this approach, shown in Appendix A.
We linearly interpolate the residual deformation to ensure our trajectories match
the nal keyframe. For components of the model that move rigidly this approach
yields the exact solution. Since we compute this locally, if dierent parts of a
body move with dierent rigid motions, we still get the correct trajectories.
3.2 Level Sets
Given our initial and nal implicit surfaces, and respectively, we compute
intermediate surfaces based on the as-rigid-as-possible trajectories. To generate
intermediate implicit surfaces we advect the initial level set along these trajec-
Chapter 3. Computing In-between Frames 20
tories using weighted averages:
(x
ij
) =
_

p
w(x
ij
x
p
)
_
/
_

p
w(x
ij
x
p
)
_
(3.2)
where
w(x
ij
) =
1
||x
ij
||
2
+
2
. (3.3)
For higher accuracy, we could blend it with the nal level set advected back
along the same trajectories, computing the intermediate level set for the t
th
frame,
(t)
, from:

(t)
(x
(t)
ij
) = (n t) (x
(t)
ij
) + t (y(x
(t)
ij
)). (3.4)
Since we have an explicit map, we can not only blend the level set values,
but also colour and texture coordinate information, for example. If these are
only dened on the surface of the initial and nal frames, we extend them into
the volume by taking the same value as the closest point on the surface.
To resample the level set or other values onto regular grids at intermediate
frames, if desired, we use scattered data interpolation. Currently our imple-
mentation simply uses weighted averages, but this is easily extended to more
accurate Moving-Least Squares estimates [8].
21
Chapter 4
Results
Our system strives to animate materials in a physically reasonable manner given
a set of keyframes. We also automatically allow for topological changes, and
allow the user to guide the motion by identifying a sparse set of feature points.
The number of feature points must be large enough for the Radial Basis Function
to build an initial map. Similar methods, [32, 33] use hundreds of thousands of
control points, but as shown in Table 4.1 the number of feature points in our
examples are reasonable for manual manipulation.
Simulation Number of Feature Points
Merge 8
Bend 6
Splash 10,14,12
Table 4.1: Number of feature points in presented simulations.
4.1 Rigid Motion
We begin with a simple example that demonstrates the rigid-motion-preservation
of our technique. As mentioned in Section 3.1, rigid motion, such as rotation
or translation, is matched exactly by our system. Since the second term of our
objective function (Equation 2.6) preserves rigid-body motions, as does the ini-
tial guess obtained from the Radial Basis Functions, the optimal map from our
optimization is completely rigid. This leaves no residual deformation for our as-
Chapter 4. Results 22
rigid-as-possible-trajectories, thus providing rigid in-between trajectories. Some
examples of rigid motion are shown in Figure 4.1.
4.2 Topological Changes
Our system automatically handles the merging of components, as shown in
Figure 4.2. In the future we would like to extend this to topological splitting of
components, based on a fracture-like criterion.
4.3 Articulated Motion
To show that our system works for movement that is rigid in its components, but
not as a whole, we provide the case of an articulated rod bending in Figure 4.3.
There are currently bugs in the level set code that cause unexpected surface
artifacts to appear in some of the in-between frames here and in the following
example.
4.4 Splash
In Figure 4.4 we present a simulation of a droplet splashing into a pool of uid.
Note, we are using our current system that does not include the additional
inertial term for uid-like movement.
Chapter 4. Results 23
F
i
g
u
r
e
4
.
1
:
A
C
a
r
t
e
s
i
a
n
g
r
i
d
r
e
p
r
e
s
e
n
t
a
t
i
o
n
o
f
t
h
r
e
e
-
d
i
m
e
n
s
i
o
n
a
l
r
i
g
i
d
e
x
a
m
p
l
e
s
:
r
o
t
a
t
i
o
n
(
t
o
p
r
o
w
)
,
t
r
a
n
s
l
a
t
i
o
n
(
m
i
d
d
l
e
r
o
w
)
,
a
n
d
b
o
t
h
t
r
a
n
s
l
a
t
i
o
n
a
n
d
r
o
t
a
t
i
o
n
(
b
o
t
t
o
m
r
o
w
)
.
Chapter 4. Results 24
F
i
g
u
r
e
4
.
2
:
T
w
o
-
d
i
m
e
n
s
i
o
n
a
l
m
e
r
g
i
n
g
e
x
a
m
p
l
e
,
w
i
t
h
t
h
e

r
s
t
a
n
d
l
a
s
t
i
m
a
g
e
s
a
s
k
e
y
f
r
a
m
e
s
.
T
h
e
l
e
v
e
l
s
e
t
s
a
r
e
d
i
s
p
l
a
y
e
d
,
a
s
a
r
e
t
h
e
f
e
a
t
u
r
e
p
o
i
n
t
s
.
Chapter 4. Results 25
F
i
g
u
r
e
4
.
3
:
T
w
o
-
d
i
m
e
n
s
i
o
n
a
l
b
e
n
d
i
n
g
e
x
a
m
p
l
e
,
w
i
t
h
t
h
e

r
s
t
a
n
d
l
a
s
t
i
m
a
g
e
s
a
s
k
e
y
f
r
a
m
e
s
.
T
h
e
l
e
v
e
l
s
e
t
s
a
r
e
d
i
s
p
l
a
y
e
d
,
a
s
a
r
e
t
h
e
f
e
a
t
u
r
e
p
o
i
n
t
s
.
Chapter 4. Results 26
F
i
g
u
r
e
4
.
4
:
T
w
o
-
d
i
m
e
n
s
i
o
n
a
l
s
p
l
a
s
h
i
n
g
e
x
a
m
p
l
e
w
i
t
h
t
h
e
l
e
v
e
l
s
e
t
a
n
d
f
e
a
t
u
r
e
p
o
i
n
t
s
s
h
o
w
n
.
T
h
e

r
s
t
,
t
h
i
r
d
,

f
t
h
a
n
d
s
e
v
e
n
t
h
i
m
a
g
e
s
r
e
p
r
e
s
e
n
t
k
e
y
f
r
a
m
e
s
.
T
h
e
i
n
i
t
i
a
l
g
r
i
d
p
o
i
n
t
s
,
w
a
r
p
e
d
t
o
t
h
e
i
r
i
n
t
e
r
m
e
d
i
a
t
e
o
r

n
a
l
p
o
s
i
t
i
o
n
s
a
r
e
a
l
s
o
s
h
o
w
n
.
27
Chapter 5
Conclusion and Future
Work
5.1 Conclusion
We present a method to create physically plausible in-between frames, given
arbitrary implicit models as keyframes. Our variational approach nds a volume
mapping between keyframes which minimizes a physics-based objective function,
and then creates as-rigid-as-possible trajectories of the volume respecting this
map, which we use to create physically plausible in-between frames.
5.2 Future Work
Currently we animate objects in a rigid manner, however this method could be
extended to animate uid-like materials by adding a parameter that controls
sloppy liquid-like motion of the uid. One application of this would be for
animating liquid characters, which are currently animated in an ad hoc and
highly artist-intensive manner to ensure absolute control of the uid and uid-
like motion [33, 51].
We believe the addition of an inertial term to our objective function would
provide an automated solution to this problem. This term would penalize ac-
celerations, by accounting for the dierence between predicted position, based
Chapter 5. Conclusion and Future Work 28
on given initial velocities, and the corresponding mapped nal position. We in
essence would provide a variational form for continuum dynamics, with addi-
tional control terms or constraints for feature point and level set matching. For
trajectory estimation we also need to take into account initial velocities, as the
nal velocity dictated by the computed trajectory should match the velocity at
the start of the following keyframe. We also plan to add the capability to split
topologies, by providing a fracture-like criterion.
5.2.1 Cartoony Fluids
Inspired by the work of [9], which creates cartoony uids in an artist-intensive
approach, we would like to extend our system to provide a more automated solu-
tion. Our approach would be to combine our system, including the inertial term
for uid-like motion, with cartoon animation lters, [49, 50], that automatically
apply well-known animation principles [27, 44].
5.2.2 Hands-on Control
We would also like to extend this work to include a hands-on approach to mod-
eling keyframes for animation. The idea is to have a user create the keyframes
using modeling clay, and then scan the three-dimensional model with a handheld
camera. Relevant research include the areas of mosaicing, [18, 23] and model
acquisition [35, 36].
29
Bibliography
[1] Marc Alexa, Daniel Cohen-Or, and David Levin. As-rigid-as-possible shape
interpolation. In SIGGRAPH 00: Proceedings of the 27th annual confer-
ence on Computer graphics and interactive techniques, pages 157164, New
York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.
[2] Aurelien Barbier, Eric Galin, and Samir Akkouche. A framework for mod-
eling, animating, and morphing textured implicit models. Graph. Models,
67(3):166188, 2005.
[3] Thaddeus Beier and Shawn Neely. Feature-based image metamorphosis. In
SIGGRAPH 92: Proceedings of the 19th annual conference on Computer
graphics and interactive techniques, pages 3542, New York, NY, USA,
1992. ACM Press.
[4] David E. Breen and Ross T. Whitaker. A level-set approach for the meta-
morphosis of solid models. IEEE Transactions on Visualization and Com-
puter Graphics, 7(2):173192, 2001.
[5] Robert Bridson, Matthias M uller-Fischer, Eran Guendelman, and Ronald
Fedkiw. Fluid simulation. In SIGGRAPH 2006 Course Notes, 2006.
[6] J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright,
B. C. McCallum, and T. R. Evans. Reconstruction and representation of 3d
objects with radial basis functions. In SIGGRAPH 01: Proceedings of the
Bibliography 30
28th annual conference on Computer graphics and interactive techniques,
pages 6776, New York, NY, USA, 2001. ACM Press.
[7] Daniel Cohen-Or, Amira Solomovic, and David Levin. Three-dimensional
distance eld metamorphosis. ACM Trans. Graph., 17(2):116141, 1998.
[8] Richard Corbett. Point-based level sets and progress towards unorganized
particle based uids. Masters thesis, University of British Columbia, 2005.
[9] Peter DeMund. Cartoony uid animation. In Proceedings of SIGGRAPH
2005, Sketches & Applications. ACM Press, 2005.
[10] Douglas Enright, Stephen Marschner, and Ronald Fedkiw. Animation and
rendering of complex water surfaces. In SIGGRAPH 02: Proceedings of the
29th annual conference on Computer graphics and interactive techniques,
pages 736744, New York, NY, USA, 2002. ACM Press.
[11] Xiang Fang, Hujun Bao, Pheng Ann Heng, TienTsin Wong, and Qunsheng
Peng. Continuous eld based free-form surface modeling and morphing.
Computers and Graphics, 25(2):235243, April 2001.
[12] Raanan Fattal and Dani Lischinski. Target-driven smoke animation. ACM
Trans. Graph., 23(3):441448, 2004.
[13] Ronald Fedkiw, Jos Stam, and Henrik Wann Jensen. Visual simulation of
smoke. In SIGGRAPH 01: Proceedings of the 28th annual conference on
Computer graphics and interactive techniques, pages 1522, New York, NY,
USA, 2001. ACM Press.
[14] Nick Foster and Ronald Fedkiw. Practical animation of liquids. In SIG-
GRAPH 01: Proceedings of the 28th annual conference on Computer
graphics and interactive techniques, pages 2330, New York, NY, USA,
2001. ACM Press.
Bibliography 31
[15] Nick Foster and Dimitri Metaxas. Realistic animation of liquids. Graphical
models and image processing: GMIP, 58(5):471483, 1996.
[16] Nick Foster and Dimitris Metaxas. Controlling uid animation. In CGI 97:
Proceedings of the 1997 Conference on Computer Graphics International,
page 178, Washington, DC, USA, 1997. IEEE Computer Society.
[17] Nick Foster and Dimitris Metaxas. Modeling water for computer animation.
Commun. ACM, 43(7):6067, 2000.
[18] Paolo Grattoni and Massimiliano Spertino. A mosaicing approach for the
acquisition and representation of 3d painted surfaces for conservation and
restoration purposes. Mach. Vision Appl., 15(1):110, 2003.
[19] Arthur D. Gregory, Andrei State, Ming C. Lin, Dinesh Manocha, and
Mark A. Livingston. Feature-based surface decomposition for correspon-
dence and morphing between polyhedra. In Computer Animation 98, pages
6471, 1998.
[20] Jeong-Mo Hong and Chang-Hun Kim. Controlling uid animation with
geometric potential: Research articles. Comput. Animat. Virtual Worlds,
15(3-4):147157, 2004.
[21] Berthold K.P. Horn. Closed form solution of absolute orientation using
unit quaternions. Journal of the Optical Society A, 4:629642, 1987.
[22] Berthold K.P. Horn, Hugh M. Hilden, and Shahriar Negahdaripour. Closed
form solution of absolute orientation using orthonormal matrices. Journal
of the Optical Society A, 5:11271135, 1988.
[23] Chiou-Ting Hsu, Tzu-Hung Cheng, Rob A. Beuker, and Jyh-Kuen Horng.
Feature-based video mosaic. In ICIP, 2000.
Bibliography 32
[24] Takeo Igarashi, Tomer Moscovich, and John F. Hughes. As-rigid-as-possible
shape manipulation. ACM Trans. Graph., 24(3):11341141, 2005.
[25] Michael Kass and Gavin Miller. Rapid, stable uid dynamics for computer
graphics. In SIGGRAPH 90: Proceedings of the 17th annual conference
on Computer graphics and interactive techniques, pages 4957, New York,
NY, USA, 1990. ACM Press.
[26] Bryan M. Klingner, Bryan E. Feldman, Nuttapong Chentanez, and
James F. OBrien. Fluid animation with dynamic meshes. ACM Trans.
Graph., 25(3):820825, 2006.
[27] John Lasseter. Principles of traditional animation applied to 3d computer
animation. In SIGGRAPH 87: Proceedings of the 14th annual conference
on Computer graphics and interactive techniques, pages 3544, New York,
NY, USA, 1987. ACM Press.
[28] Apostolos Lerios, Chase D. Garnkle, and Marc Levoy. Feature-based vol-
ume metamorphosis. In SIGGRAPH 95: Proceedings of the 22nd annual
conference on Computer graphics and interactive techniques, pages 449
456, New York, NY, USA, 1995. ACM Press.
[29] Yaron Lipman, Olga Sorkine, David Levin, and Daniel Cohen-Or. Linear
rotation-invariant coordinates for meshes. ACM Trans. Graph., 24(3):479
487, 2005.
[30] Frank Losasso, Frederic Gibou, and Ron Fedkiw. Simulating water and
smoke with an octree data structure. ACM Trans. Graph., 23(3):457462,
2004.
[31] Frank Losasso, Tamar Shinar, Andrew Selle, and Ronald Fedkiw. Multiple
interacting liquids. In SIGGRAPH 06: Proceedings of the 33rd annual
Bibliography 33
conference on Computer graphics and interactive techniques, New York,
NY, USA, 2006. ACM Press.
[32] Antoine McNamara, Adrien Treuille, Zoran Popovic, and Jos Stam. Fluid
control using the adjoint method. ACM Trans. Graph., 23(3):449456,
2004.
[33] N. Rasmussen, D. Enright, D. Nguyen, S. Marino, N. Sumner, W. Geiger,
S. Hoon, and R. Fedkiw. Directable photorealistic liquids. In SCA 04:
Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on
Computer animation, pages 193202, New York, NY, USA, 2004. ACM
Press.
[34] William T. Reeves. Particle systems - a technique for modeling a class of
fuzzy objects. In SIGGRAPH 83: Proceedings of the 10th annual confer-
ence on Computer graphics and interactive techniques, pages 359375, New
York, NY, USA, 1983. ACM Press.
[35] Szymon Rusinkiewicz, Olaf Hall-Holt, and Marc Levoy. Real-time 3d model
acquisition. In SIGGRAPH 02: Proceedings of the 29th annual confer-
ence on Computer graphics and interactive techniques, pages 438446, New
York, NY, USA, 2002. ACM Press.
[36] Tomokazu Sato, Masayuki Kanbara, Naokazu Yokoya, and Haruo Take-
mura. Dense 3-d reconstruction of an outdoor scene by hundreds-baseline
stereo using a hand-held video camera. Int. J. Comput. Vision, 47(1-3):119
129, 2002.
[37] Steven M. Seitz and Charles R. Dyer. View morphing. Computer Graphics,
30(Annual Conference Series):2130, 1996.
Bibliography 34
[38] Andrew Selle, Nick Rasmussen, and Ronald Fedkiw. A vortex particle
method for smoke, water and explosions. ACM Trans. Graph., 24(3):910
914, 2005.
[39] Lin Shi and Yizhou Yu. Controllable smoke animation with guiding objects.
ACM Trans. Graph., 24(1):140164, 2005.
[40] Lin Shi and Yizhou Yu. Taming liquids for rapidly changing targets. In SCA
05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium
on Computer animation, pages 229236, New York, NY, USA, 2005. ACM
Press.
[41] Seung-Ho Shin, Jung Lee, Sun-Jeong Kim, and Chang-Hun Kim. Con-
trolling liquids using pressure jump. In Proceedings of SIGGRAPH 2006,
Sketches & Applications. ACM Press, 2006.
[42] Jos Stam. Stable uids. In SIGGRAPH 99: Proceedings of the 26th annual
conference on Computer graphics and interactive techniques, pages 121
128, New York, NY, USA, 1999. ACM Press/Addison-Wesley Publishing
Co.
[43] Nigel Sumner, Samir Hoon, Willi Geiger, Sebastien Marino, Nick Ras-
mussen, and Ron Fedkiw. Melting a terminatrix. In Proceedings of SIG-
GRAPH 2003, Sketches & Applications. ACM Press, 2003.
[44] Frank Thomas and Ollie Johnston. The Illusion of Life. Disney Editions,
pp. 62., 1981.
[45] Nils Th urey, Richard Keiser, Ulrich R ude, and Mark Pauly. Detail-
preserving uid control. In SCA 06: Proceedings of the 2005 ACM SIG-
GRAPH/Eurographics symposium on Computer animation, New York, NY,
USA, 2006. ACM Press.
Bibliography 35
[46] Adrien Treuille, Antoine McNamara, Zoran Popovic, and Jos Stam.
Keyframe control of smoke simulations. ACM Trans. Graph., 22(3):716
723, 2003.
[47] Greg Turk and James F. OBrien. Shape transformation using variational
implicit functions. In SIGGRAPH 99: Proceedings of the 26th annual
conference on Computer graphics and interactive techniques, pages 335
342, New York, NY, USA, 1999. ACM Press/Addison-Wesley Publishing
Co.
[48] Wolfram von Funck, Holger Theisel, and Hans-Peter Seidel. Vector eld
based shape deformations. In SIGGRAPH 06: Proceedings of the 33rd
annual conference on Computer graphics and interactive techniques, New
York, NY, USA, 2006. ACM Press.
[49] Jue Wang, Stephen M. Drucker, Maneesh Agrawala, and Michael F. Cohen.
Cartoon animation lter. In In SIGGRAPH 06: Proceedings of the 33rd
annual conference on Computer graphics and interactive techniques, New
York, NY, USA, 2006. ACM Press.
[50] David White, Kevin Loken, and Michiel van de Panne. Slow in and slow
out cartoon animation lter. In Proceedings of SIGGRAPH 2006, Research
Posters. ACM Press, 2006.
[51] Mark Wiebe and Ben Houston. The tar monster: Creating a character
with uid simulation. In Proceedings of SIGGRAPH 2004, Sketches &
Applications. ACM Press, 2004.
36
Appendix A
Optimal Rotation in Two
Dimensions
In [21] and [22], a closed form solution for computing the optimal rotation of a
set of points is derived for three dimensions. We use this for three-dimensional
simulations and our two-dimensional examples use a reduced formulation out-
lined below. Note that translation, regardless of the dimensionality, is simply
y x, the dierence between nal and initial center points.
We begin by stating that we seek a rotation, R, such that
y
i
= R x
i
, (A.1)
where
y
i
= (y
i
y),
x
i
= (x
i
x),
i = 1, ..., N.
Given that we are not necessarily dealing with absolute rigidity, we use a least-
Appendix A. Optimal Rotation in Two Dimensions 37
squares error metric, given by:
min
R

i
y
i
R x
i

2
, (A.2)
subject to det (R) = 1. (A.3)
This expands to

i
(| y|
2
+| x|
2
2 y
T
i
R x
i
), (A.4)
and since | y|
2
and | x|
2
are independent of R, we reduce the error term to

i
( y
T
i
R x
i
) (A.5)
=

i
( y
(1)
i
y
(2)
i
)
_
_
_
cos() sin()
sin() cos()
_
_
_
_
_
_
x
(1)
i
x
(1)
i
_
_
_
=

i
( y
(1)
i
y
(2)
i
)
_
_
_
x
(1)
i
cos() + x
(2)
i
sin()
x
(1)
i
sin() + x
(2)
i
cos()
_
_
_
=

i

_
y
(1)
i
x
(1)
i
cos() + y
(1)
i
x
(2)
i
sin() y
(2)
i
x
(1)
i
sin() + y
(2)
i
x
(2)
i
cos()
_
= cos()
_

i
_
y
(1)
i
x
(1)
i
+ y
(2)
i
x
(2)
i
__
+sin()
_

i
( y
(2)
i
x
(1)
i
y
(1)
i
x
(2)
i
)
_
= Acos() + B sin(). (A.6)
where
Appendix A. Optimal Rotation in Two Dimensions 38
A =

i
_
y
(1)
i
x
(1)
i
+ y
(2)
i
x
(2)
i
_
, (A.7)
B =

i
( y
(2)
i
x
(1)
i
y
(1)
i
x
(2)
i
). (A.8)
Our constraint (Equation A.3) is now cos
2
() +sin
2
() = 1, which combines
with A.6 to yield:
cos() =
A

A
2
+B
2
, (A.9)
sin() =
B

A
2
+B
2
, (A.10)