Keyframe Animation of Implicit Models by David I. White B.Sc, The University of Western Ontario, 2004 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Maste r of Science i n The Faculty of Graduate Studies (Computer Science) The Univers i ty O f B r i t i s h C o l u m b i a August 2006 © 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 fluid-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 fluid control approaches do not respect keyframes nor track feature points. Our variational approach finds a volume mapping between keyframes which minimizes a physics-based objective function using Gauss-Newton modi-fied 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. Contents Abs t rac t ii Contents iii Lis t of Tables v Lis t of Figures vi Acknowledgements viii 1 In t roduct ion 1 1.1 Motivation 2 1.2 Previous Work 2 1.2.1 Image Morphing 2 1.2.2 Morphing with Tetrahedra! 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 M a p p i n g 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 Modified Gauss-Newton Optimization 14 3 C o m p u t i n g 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 Conclus ion and Future W o r k 27 5.1 Conclusion 27 5.2 Future Work 27 5.2.1 Cartoony Fluids 28 5.2.2 Hands-on Control 28 Bibl iography 29 A O p t i m a l Ro ta t ion in T w o Dimensions 36 L i s t o f T a b l e s 4.1 Number of feature points in presented simulations vi Lis t of Figures 1.1 An example of input to our system: initial (a) and final (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 final keyframe (b) 5 1.3 The as-rigid-as-possible trajectories from our initial keyframe to the final keyframe 6 1.4 The output of our system: in-between frames that correspond to the input keyframes 6 2.1 Naive (a) and subdivided (b) discretization of a two-dimensional grid cell 14 2.2 Naive (a) and subdivided (b) discretization of a three-dimensional grid cell 15 2.3 Barycentric weights, tit of y[ in the grid defined by x\, x-2, x3, and X4 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 first 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 first 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 first, third, fifth and seventh images represent keyframes. The initial grid points, warped to their intermediate or final 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 Biff? 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 clogs run on batteries - or worse yet, have never questioned it. DAVID I. WHITE The University of British Columbia August 2006 C h a p t e r 1 i Introduct ion "Wh.al the animator does on each frame of film, is not as important as what he or she does in between." - Norman McLaren Keyframe-based animation of general shapes is difficult 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 fixed 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 find a mapping between Cartesian grid points of adja-cent implicit sui'face 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 tradeoff between physical realism and directability in computer animated fluids. Fluid simulations based on the Navier-Stokes equations accurately represent the physical properties of fluids, but are computationally time consuming, difficult to create from scratch and most importantly they offer no user-control of the fluid. In practice, computer animation studios generally use fluid systems that are set up to be highly user-intensive so that artists have control over the motion of the fluid. However, this can be time consuming and may lead to fluid that does not move in a physical manner. Our system allows full control of the fluid through user-defined 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 1990's. 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 fine 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, ln 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 final model. With our user-defined feature points, we can guarantee a mapping to the user's specifications. Chapter 1. Introduction 1.2.4 Fluid Simulation for Computer Animation Fluid simulation techniques for computer animation were first presented in [34], where particles were used to represent clouds, smoke, water and fire. 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 fluid, came in [15]. A higher-level look at this same method is [17], which also explains how it was used to animated fluids in the film Antz - the first computer animated film containing fluids. A few years later, this approach was extended to be unconditionally stable in [42], which also introduced the serni-Lagrangian method. This was later refined for inviscid fluids, such as smoke, in [13] and liquids in [14]. The latter also intro-duced level sets to the computer graphics community. Photorealistic computer animated fluids were first 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 fluids on meshes [26], and multiple fluids of different densities interacting [31]. For a detailed introduction to fluid simulation, see [5]. 1.2.5 Controllable Fluid Simulations Controllable fluids for computer animation were introduced in [16], where the user could change parameters to alter the fluid motion. More recent work in fluid control can be split into two categories: target matching [12, 20, 39, 40, 41, 45, 46] and user-defined control points [32, 33, 43, 51]. The former have difficulty perfectly matching fluid to the specified targets, and the latter use highly user-intensive control methods. Our approach guarantees that; we exactly match the specified keyframes while keeping the number of user-defined 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, <f> and \&, and their corresponding feature points, x ' and y'(shown in Figure 1.1). Using this information we create Figure 1.1: A n example of input to our system: ini t ia l (a) and final (b) implici t surfaces, and their respective feature points (c) and (d). a map, y , of each object point in our in i t ia l keyframe to a corresponding point in the final keyframe (shown in Figure 1.2). Ini t ial ly we do this using Rad ia l Basis Functions buil t on the feature points, and then we use opt imizat ion to modify the map to fit several physical properties, such as volume conservation. From the map we create trajectories for each point (shown in Figure 1.3). In (a) (b) Figure 1.2: Our computed mapping from the ini t ia l keyframe (a) to the final 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. o - o - o - o - o - o ^ o ^ » < » * » * » o o o o o tt-e K.»t»t»<»<»o O O O 0 o o »c»o»ofcofco»o o - o - o - o - « - o ^ , * t * t * * ; ^ * e Figure 1.3: The as-rigid-as-possible trajectories from our initial keyframe to the final 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 A l g o r i t h m 1 System Overview l: Input: keyframes (as implicit surfaces) and feature points mapped between adjacent keyframes 2: for each pair of keyframes d o 3: map grid points from the initial keyframe to the final keyframe using Radial Basis Functions based on the feature points 4: optimize this map using our physically based objective function and Gauss-Newton modified to handle linear constraints 5: for each mapped point d o 6: create a trajectory between the keyframes that is as-rigid-as-possible 7: e n d for 8: for each in-between frame d o 9: create a level set based on the keyframe(s) and the trajectories 10: e n d for 11: Output: in-between frames 12: e n d for 8 C h a p t e r 2 Mapping Adjacent Keyframes Given a series of keyframes represented as implicit surfaces and selected feature points on adjacent keyframes, we find a mapping of all the material points in the initial frame to the material points in the final 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 modified 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, cf>(x) and v]>(y), and their corresponding feature points, x ' and y' . Feature points can be sparse, and can differ 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 confined to the material boundary - they can enter the interior of our material as specified by the user. 2.2 Radial Basis Functions Using the initial feature points, x', and their final positions, y', we map the final positions of all the material points in our initial keyframe. This map, y(x), is one-to-one and we present scenarios in 5ft2 and 5R3. 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: N y(x) = x -1- p(x) + ^ B ( | | X " (v'i ~ X'M2), (2.1) ensuring that y(x'i) = y\ (2.2) where RB is the Radial Basis Function, ./V is the number of feature points, p(x) is a (dimension-l)-degree polynomial with M coefficients c, and A, are the coefficients of the Radial Basis Functions. Notice that we use the RBF to get a mapping of displacements, so we convert it to final values by adding the initial locations of each point, x. This is different than the standard RBF formulation. For two dimensions we use the thin-plate spline: RB(r) = r2logr, (2.3) and in three dimensions we use the triharmonic spline: RB(r) = ra. (2.4) Chapter 2. Mapping Adjacent Keyframes 10 To obtain A and c, we solve: A P A f PT 0 c 0 where Aij = RB(\\xi-(y':i-x')h), i,j = l,...,N Pij=Pj{xi), i=l,...,N,j = l,...,M fi=y{x'A, '-7 - 1 V 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, /, that ensures the mapping from initial to final grid points, y(x), preserves certain physical properties. This objective function is: /(y)= i ' | d e t ( ^ ) - l | 2 + / I l i * r i £ - / | | 2 F (2.6) + J||J-J($(x))-//(vP(y(x)))|||, Chapter 2. Mapping Adjacent Keyframes 11 where <J> and $ are the initial and final keyframes, and H is the Heavisicle function: 0 if <5>(xij) < -e, H($(Xij)) = <j i + + s i n ( I ^ ) if 6 < < e, 1 ife<$(.Ty), (2.7) with £ = 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 first term resists volume change in the material by ensuring that det ( § j ) > t n e ratio of the approximated final 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 final 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 final level set surface by comparing the Heavisicle function at each initial grid point with the Heavisicle function of the corresponding final 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, |^ is computed in two dimensions using the naive discretization: where dy II. [ Uo (2.9) Ul u2 V2 (x(1) +x(1) )- x ( 1 ) + X5'j) 2Au Cx(1) +x(1) )-2Au l X i + l , . j + l + X i + l , J . ' x ( 2 ) i , . 7 + l + X0) 2Av (x<2) +x<2) )- ("ft, +X^) 2Au 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 |^ 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: dy 5x U 2 U3 Vl V2 V3 Wi W2 W3 (2.10) where Ul — ' 1 4-^ <" 1 f x ( l ) l + rx '" +X U ) W x ' " +X ( 1 > ) fx"> 4-x(1> 1 fx' 1 ' +x ( 1 ) W x ( 1 ) +x ( 1 > ) - f x ( 1 ) '"'3 = ' ' 4A^ +x ( 1 ) ) - l . k + l ^ X i + l . : i : k + l ) , 1 2 ) (2) . , (2) (2) , , (2) (2) W x ( 2 ) + x ( 2 > } _ ( x i + l . i + l , k + x i + l o , k ) - ( x i , i + l , k + x i . j , k ) + \ x i + l.j + l . k + i + x i + l , 3 , k + l ) l x i , j+l .*+l + x i , j , , (2) (2) , , (2) (2) > + fx ( 2 ) +x < 2 ) W x < 2 ) +X ( 2 ' ) (xl4-l.Hl,t+xHI,<,t)~txHl-<+^HI+xHI,<.M-lW'i<.Wl.ttxi.<." y x i , : i + l , k + l + x i . : j . k + l l y2 = , j ^ -_ (xi + - i . i . k + x i , : i , k ) txi+l..-j.fc + l+xi..j,t- + lJ + ' . x i+l. j+l,t + x i . j + l.fc^ lxi+l,j+n.-+l+xi+l..j.t-+l ^ 1 ;3 — 4At> fv(3> 4-x ( 3 ) ^ lV ( 3 ) -l-x ( 3 ) W x ( 3 ) -t-X(3) Wx ( ' ' ' +X l J ) 1 _ (xi+i.,-+l>+xi+L.j,t-J~Cxi,> + l,),-+xi.7.t^ + t x i + lr) + i.t'+i+xi+l-7.''- + '' ) • '•x<..j+l,t+l+xi..i,H-^ '(/J2 _ \ x i + \ . j + \ , k + x ; + \ . : l . k l l x i+ l . : j+ l ,k + l + x i + l . - j , k + l> + \ x i . i + i . k + x i . : i , k > y x i . : i + l , k + l + x i . j . k + \ ) — 4Alu ' W3 ^<3> x^<3> \ (-x(3) J - X < 3 ) u r v ( 3 ) +x l 3 ) +x < 3 ) ) _ (x<+t.j.fc+xi,i.t>~Cxn.l,J.fc+l+xi.i.fc4-^+tx<H-l.j+l.t^xi.i+l.fcJ vxi+l,j+l.fc+l+xi+l..7.fc+w — 4Atu Chapter 2. Mapping Adjacent Keyframes 14 v 1+1/2J+1/2 X. X i+ l j + l i+ l j+ i / X. , . X . . X i + . / 2 J X i + l j (b) Figure 2.1: Naive (a) and subdivided (b) discretization of a two-dimensional grid cell. 2.5 Modified 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|kp(y)||2, (2.11) y(x) which updates each step, Ayk, by jTjkAyk = -ATP(y,= ), (2.12) where Chapter 2. Mapping Adjacent Keyframes 15 (a) (b) Figure 2.2: Naive (a) and subdivided (b) discretization of a three-dimensional grid cell. Our modified approach that satisfies linear constraints is: min||p(y)||2, y(x) subject to Cy' = d, (2.14) (2.15) and Ayfc is obtained from JTJ, CT Ay f c = (2.16) C 0 A 0 from the Radial Basis Functions matches the feature points exactly, so the constraints are satisfied when the optimization begins. The update steps, Ay/:, 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: ( 1 if y'j is on grid point j , (2.17) 0 otherwise, </, ••:>•[. (2.18) For feature points that are not aligned with the grid points we use barycentric weights, ti, to guarantee that the optimal map meets these constraints (Fig-ure 2.3). Our constraints then become: Li if j is a grid point on the grid cell of y!-, 0 otherwise, C ; , • { ' ' (2.19) <k = (ti +t2+t3 + t4)x'i. (2.20) Chapter 2. Mapping Adjacent Keyframes 17 x i i> t 2 X 2 X 3 X Figure 2.3: Barycentric weights, ti, of y.- in the grid defined by x\, xo, %3, and x4. IS C h a p t e r 3 Computing In-between Frames Once we have obtained the optimal mapping from the initial keyframe to the final keyframe, we still need to compute the corresponding in-between frames. In the traditional morphing sense, this is clone simply by blending between the initial and final 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 final 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 it's final location, however this fails to match rigid rotations. Since we want the local neighbourhood of a point to be mapped in a l'igid 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 finding the rigid body motion as close as possible to the deformation of the point's neighbourhood. We use the following formulation to compute the trajectory of an ini t ial grid point, X ; J , at the tth intermediate frame: xi? = x y + - W i * ! , t) + (&)(v - S) (3-1) + ( ^ ) ( i - < W ( y i ; - x i ; 0 ) , where x is the mean of x, y is the mean of y, n is the total number of frames, 5 is the Kronecker Delta, x.-^ is the final position of x.^ , and /?.* ( X ; J ,/;) is the opt imal rotation of and its grid neighbours at the ttk 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 final keyframe. For components of the model that move rigidly this approach yields the exact solution. Since we compute this locally, if different parts of a body move with different rigid motions, we sti l l get the correct trajectories. 3.2 Level Sets Given our ini t ia l and final implici t surfaces, <3> and \f/ respectively, we compute intermediate surfaces based on the as-rigid-as-possible trajectories. To generate intermediate implici t surfaces we advect the ini t ial level set along these trajec-Chapter 3. Computing In-between Frames 20 tories using weighted averages: <I>(a ^wixij - xp) where w(Xij) = (3.2) (3-3) For higher accuracy, we could blend it with the final level set a.dvectecl back along the same trajectories, computing the intermediate level set for the /,''' frame. <I>(t), from: # W ( x i ; . ) ) = (n - t)*( a; i* ) ) -rt*(y(^ ) ) ) . (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 defined on the surface of the initial and final 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 C h a p t e r 4 R e s u l t s 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. Simulat ion N u m b e r 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 fluid. Note, we are using our current system that does not include the additional inertial term for fluid-like movement. Figure 4.1: A Cartesian grid representation of three-dimensional rigid examples: rotation (top row), translation (middle row), and both translation and rotation (bottom row). Figure 4.2: Two-dimensional merging example, with the first and last images as keyframes. The level sets are displayed, as are the feature points. to Figure 4.3: Two-dimensional bending example, with the first and last images as keyframes. The level sets are displayed, as are the feature points. < O Q O O > o o n n < Of'OOOOO o o o o o o o o V 1 OOOOOOOOOOOOO' o^o o o o o o o o o o o o ojo o 0~< -O 0'( O OOOOOOOO' i ^ a o o o c o c o o o o i j c o o o o o o o c o c i o o o o o o o c o o c o c ^ c > g~n-o o~c~S~c o a 5 o i_Q O q O Of^O 0 * 0 0 0 * 0 0 0*0 o OO o"^ o| 0 0 0 0 0 o o o o o o c o p j o a . o o a ^ o o c 0J0 O O O O C 0 0_l -0000 0~~0 O 9 •a o s» o o o o" o U"~cJ 0 0 0 oAo O 0 / 0 0 o o o o o o o o o o 0^0 o>. o o o o o o o o o 0 0 0 0 J 0 o S S^t*- ° o 0^0 5 0/0 O o 0 0 0 0 0 0 8 t ^ s T S T O W * ^ ? c o f ° O o o o o o o o ° ° j > o o o o o o ° 0 0 ° J o ~ o fa Co c Figure 4.4: Two-dimensional splashing example with the level set and feature points shown. The first, third, fifth and seventh images represent keyframes. The initial grid points, warped to their intermediate or final positions are also shown. to 27 C h a p t e r 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 finds 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 fluid-like materials by adding a parameter that controls sloppy liquid-like motion of the fluid. 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 fluid and fluid-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 difference between predicted position, based Chapter 5. Conclusion and Future Work 28 on given initial velocities, and the corresponding mapped final 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 final 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 fluids 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 fluid-like motion, with cartoon animation filters, [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-rigicl-as-possible shape interpolation. In SIGGRAPH '00: Proceedings of the 27th annual confer-ence on Computer graphics and interactive techniques, pages 157-164, 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):166-188, 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 35-42, 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): 173-192, 2001. [5] Robert Bridson, Matthias Midler-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 67-76, New York, NY, USA, 2001. ACM Press. [7] Daniel Cohen-Or, Amira Solornovic, and David Levin. Three-dimensional distance field metamorphosis. ACM Trans. Graph., 17(2):116-141, 1998. [8] Richard Corbett. Point-based level sets and progress towards unorganized particle based fluids. Master's thesis, University of British Columbia, 2005. [9] Peter DeMund. Cartoony fluid 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 736-744, New York, NY, USA, 2002. ACM Press. [11] Xiang Fang, Hujun Bao, Pheng Ann Heng, TienTsin Wong, and Qunsheng Peng. Continuous field based free-form surface modeling and morphing. Computers and Graphics, 25(2):235-243, April 2001. [12] Raanan Fattal and Dani Lischinski. Target-driven smoke animation. ACM Trans. Graph., 23(3):441-448, 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 15-22, New York, NY, USA, 2001. ACM Press. [ 1 4 ] 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 23-30, 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):471-483, 1996. [16] Nick Foster and Dimitris Metaxas. Controlling fluid 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. Comrnun. ACM, 43(7):60-67, 2000. [18] Paolo Grattoni and Mas.sirniliano Spertino. A mosaicing approach for the acquisition and representation of 3d painted surfaces for conservation and restoration purposes. Mach. Vision Appl, 15(1):1—10, 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 64-71, 1998. [20] .Jeong-Mo Hong and Chang-Hun Kim. Controlling fluid animation with geometric potential: Research articles. Comput. Anvmat. Virtual Worlds, 15(3-4).T47-157, 2004. [21] Berthold K.P. Horn. Closed form solution of absolute orientation using unit quaternions. Journal of the Optical Society A, 4:629-642, 19S7. [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:1127-1135, 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):1134-1141, 2005. [25] Michael Kass and Gavin Miller. Rapid, stable fluid dynamics for computer graphics. In SIGGRAPH '90: Proceedings of the 17th annual conference on Computer graphics and interactive techniques, pages 49-57, New York, NY, USA, 1990. ACM Press. [26] Bryan M. Klingner, Bryan E. Feldman, Nuttapong Chentanez, and James F. O'Brien. Fluid animation with dynamic meshes. ACM Trans. Graph., 25(3):820-825, 2006. [27] John Lasseter. Principles of traditional animation applied to 3d computer animation. In SIGGRAPH '87: Proceedings of the l^th annual conference on Computer graphics and interactive techniques, pages 35-44, New York, NY, USA, 1987. ACM Press. [28] Apostolos Lerios, Chase D. Garfinkle, 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):457-462, 2004. [31] Frank Losasso, Tamar Shinar, Andrew Selle, and Ronald Fedkiw. Multiple interacting liquids. In SIGGRAPH '06: Proceedings of the 33rd annual Bibliography conference on Computer graphics and interactive techniques, New York, NY, USA, 2006. ACM Press. [32] Antoine McNamara, Adrien Treuille, Zoran Popovic, and Jos Stain. Fluid control using the adjoint method. ACM Trans. Graph., 23(3):449-456, 2004. [33] N. Rasinussen, 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 193-202, 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 359-375, 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 438-446, New York, NY, USA, 2002. ACM Press. [36] Toniokazu 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. Corn-put. Vision, 47(1-3):119-129, 2002. [37] Steven M. Seitz and Charles R. Dyer. View morphing. Computer Graphics, 30(Annual Conference Series):21-30, 1996. Bibliography 34 [38] Andrew Selle, Nick Rasmussen, and Ronald Fedkiw. A vortex particle method lor 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):140-164, 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 229-236, 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 fluids. 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 Thiirey, Richard Keiser, Ulrich Riide, and Mark Pauly. Detail-preserving fluid 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 Ti'euille, Antoine McNamara, Zoran Popovic, and Jos'Stain. Keyframe control of smoke simulations. ACM Trans. Graph., 22(3):716-723, 2003. [47] Greg Turk and James F. O'Brien. 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 field 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 filter. 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 filter. In Proceedings of SIGGRAPH 2006, Research Posters. ACM Press, 2006. [51) Mark Wiebe and Ben Houston. The tar monster: Creating a character with fluid simulation. In Proceedings of SIGGRAPH 2004, Sketch.es & 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 difference between final and initial center points. We begin by stating that we seek a rotation, R, such that •Tji = RXi, (A.1) where Vi = (Vi ~ V), Xi = {Xi 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: subject to det (R) = 1. (A.2) (A .3) This expands to Y^(\y\2 + \x\2-2yTRxi), ( A . 4 ) i and since \y\2 and \x\2 are independent of R, we reduce the error term to E i ( » 1 , » i a ) ) cos(6») sin(6>) ( A . 5 ) •sin(0) cos(0) J ( cos(0) + xf] sin(0) \ \ -if 's in^) +xii)cos(9) J E , - [v^iP cos(0) + yf*j 2> sin(0) - j)fx|') sin(0) + y™4» cos(0)] = cos(fl) [-E, ( y i 1 ) i i 1 , +y ( ( 2 , 5 ! 2 ) ) ] + sin(fl) [E»(2/. = 4cos(0) + £siri(0). ( A . 6 ) where Appendix A. Optimal Rotation in Two Dimensions 38 ^ = - E . i ( ^ 1 ) + ^ M 2 ) ) . (A.7) B ^ i v ^ - y ^ ) . (A.8) Our constraint (Equation A.3) is now cos2(£>) + sin2(6>) = 1, which combines with A.G to yield:
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Keyframe animation of implicit models
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Keyframe animation of implicit models White, David I. 2006
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Keyframe animation of implicit models |
Creator |
White, David I. |
Publisher | University of British Columbia |
Date Issued | 2006 |
Description | 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 fluid-like materials. Most current implicit 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 fluid control approaches do not respect keyframes nor track feature points. Our variational approach finds a volume mapping between keyframes which minimizes a physics-based objective function using Gauss-Newton modified 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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051751 |
URI | http://hdl.handle.net/2429/18380 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2006-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2006-0706.pdf [ 1.23MB ]
- Metadata
- JSON: 831-1.0051751.json
- JSON-LD: 831-1.0051751-ld.json
- RDF/XML (Pretty): 831-1.0051751-rdf.xml
- RDF/JSON: 831-1.0051751-rdf.json
- Turtle: 831-1.0051751-turtle.txt
- N-Triples: 831-1.0051751-rdf-ntriples.txt
- Original Record: 831-1.0051751-source.json
- Full Text
- 831-1.0051751-fulltext.txt
- Citation
- 831-1.0051751.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051751/manifest