UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Animating sand as a fluid Zhu, Yongning 2006

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2006-0142.pdf [ 3.82MB ]
Metadata
JSON: 831-1.0051582.json
JSON-LD: 831-1.0051582-ld.json
RDF/XML (Pretty): 831-1.0051582-rdf.xml
RDF/JSON: 831-1.0051582-rdf.json
Turtle: 831-1.0051582-turtle.txt
N-Triples: 831-1.0051582-rdf-ntriples.txt
Original Record: 831-1.0051582-source.json
Full Text
831-1.0051582-fulltext.txt
Citation
831-1.0051582.ris

Full Text

Animating Sand as a Fluid by Yongning Zhu B.Sc, Peking University, 2003 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Computer Science) The University of British Columbia November 2005 © Yongning Zhu, 2005 Abst rac t My thesis presents a physics-based simulation method for animating sand. To allow for efficiently scaling up to large volumes of sand, we abstract away the individual grains and think of the sand as a continuum. In particular we show that an existing water simulator can-be turned into a sand simulator within frictional regime with only a lew small additions to account for inter-grain and boundary friction, yet with visually acceptable result. We also propose an alternative method for simulating fluids. Our core rep-resentation is a cloud of particles, which allows for accurate and flexible surface tracking and advection. but we use an auxiliary grid to efficiently enforce boundary conditions and incompressibility. We further address the issue of reconstructing a surface from particle data to render each frame. n Table of Contents Abstract ii Table of Contents iii List of Figures v Acknowledgements vii 1 Introduction 1 1.1 Basic assumption 2 1.1.1 Continuum Assumption 2 1.1.2 Frictional flow 3 1.2 Related works 4 1.2.1 Sand in Graphics 4 1.2.2 Sand grains as rigid bodies 5 1.2.3 Particle-based Water Simulation . 5 1.2.4 Grid-based Water Simulation 6 1.2.5 Plastic Flow 7 1.2.6 Scientific Work on Granular Materials . . 7 1.2.7 Scientific Work on Fluid Flow 8 1.3 Overview of the Thesis 8 i i i 2 S a n d M o d e l i n g 10 2.1 Fluid dynamics 11 2.2 Frictional Plasticity 13 2.3 A Simplified Model 14 2.3.1 Assumptions for simplification 14 2.3.2 Mohr-Coulomb law . . 15 2.3.3 Algorithm 16 2.3.4 Sand rigidification 17 2.4 Frictional Boundary Conditions 18 2.5 Cohesion 20 3 F l u i d S i m u l a t i o n R e v i s i t e d 21 3.1 Grids and Particles 21 3.2 Particle-in-Cell Methods 23 3.2.1 Error analysis 29 4 S u r f a c e R e c o n s t r u c t i o n f r o m P a r t i c l e s ' 31 5 R e s u l t s 3 6 6 F u t u r e W o r k a n d C o n c l u s i o n s 3 9 B i b l i o g r a p h y 4 0 iv List of Figures 2.1 Solidification of non-yielding grid cells 18 2.2 The sand bunny with a boundary friction coefficient i/, = 0.6: compare to figure 5.1 where zero boundary friction was used 19 3.1 PIC and FLIP Method, (a) Algorithm starts with particles carry-ing their velocities, (b) Transfer velocities from particles to grid.(c) Resolve forces on grid, including external forces like gravity, resolv-ing boundary conditions and projecting velocity back to be incom-pressible, (d) Update particle velocities.(e) Update particle position carrying velocities with them (advection) 24 3.2 Velocity interpolation between particles and grid cells ' 26 3.3 FLIP vs. PIC velocity update for the same simulation. Notice the small-scale velocities preserved by FLIP but smoothed away by PIC. 28 4.1 Comparison of our implicit function and blobbies for matching a per-fect circle defined by the points inside. The blobby is the outer curve, ours is the inner curve 32 4.2 A column of regular liquid is released 33 4.3 A column of sand is released. 34 5.1 Low friction sand bunny 37 v Water bunny Acknowledgements I would like to express my gratitude to all those who gave me the possibility to complete this thesis. Especially. I want to thank my supervisor Robert Briclson for introducing me into computer graphics area, and always encouraging me to go ahead. And I want to thank Professor Ian Mitchel who has carefully read the thesis, and proposed valued suggestions. I would like to thank all the members in Imager lab that have been with me for these two years. Without them, I wouldn't be able to finish this work. And I would like to thank all my friends both in the University of British Columbia and back in China who have always been supporting me and caring about me. This work was in part supported by a grant from the Natural Sciences and Engineering Research Council of Canada. And we would like to thank Dr. Dawn Shuttle for her help with granular constitutive models. Y O N G N I N G Z H U The, University of British Columbia November 2005 vn Chapte r 1 Introduct ion The motion of sand—how it flows and also how it stabilizes—has transfixed countless children at the beach or playground. More generally, granular materials such as sand, gravel, grains, soil, rubble, flour, sugar, and many more play an important role in the world. There is an increasing interest in both physics and engineering research in studying and simulating granular materials too. Thus we are interested in animating them. People have studied animating sand using a variety of different methods. More efficient techniques still need to be developed. This thesis considers an efficient way of simulating slow flow of sand, and improvements in corresponding high quality rendering . In this section, we will clarify the basic assumption and regime in our sim-ulation, with a brief introduction to related works people have been doing in both computer' graphics and physics. We will also give an overview of contributions of this thesis. • 1 1.1 Basic assumption 1.1.1 Continuum Assumption Granular material consists of so many grains that it also shows a collective behaviour. This dual property introduces special difficulties and interesting phenomena, and attracted a lot of physicists. From the numerical simulation point of view, there could be both discrete and continuous descriptions and approaches. The discrete approach, like molecular dynamics methods, is the most direct one. It captures the behaviour of every individual particle. It plays an important role for studying the macroscopic properties of granular material. Weber, Hoffman and Hrenya[57] have performed simulations of rapid shear flow with low-to-meclium volume fraction consisting of 2292 particles. They used hard-sphere collisions with cohesive forces incorporated via a square-well potential. Silbert et al[49] have done simulations of 1000-20000 particles with a soft-sphere model. Discrete models are widely used in simulation for physics. However, this kind of approach takes too much computation as the number of particles increases. Scaling this up to just a handful of sand is clearly infeasible; a sand dune containing trillions of grains is out of the question. In this sense, discrete models aren't a good approach for animation. From a macroscopic point of view, we cannot distinguish separate grains. Instead, we see the sand as a continuous material, behaving like a kind of fluid. More precisely, although each particle has its own velocity, we only consider their average velocity over a volume element small enough in a macroscopic view. Similarly, an averaged stress tensor will decide the behaviour of this granular material instead of particle-particle interaction. Our simulation will be based on a collective behaviour of the sand particles instead of only considering each particle. So we refer to pressure, density, viscosity . etc. in a similar sense. 2 Here we introduce the concept granular How as a continuous description for granular material. Generally, a granular flow is a multiphase (i.e., solid and fluid) flow consisting of macroscopic solid particulates and an interstitial fluid. When sheared, the particulates may either flow in a manner similar to a fluid, or resist the shearing like a solid. This includes both dry and wet sand, but in this thesis, we only consider the flow of dry sand grains. Therefore we will describe the sand flow with such quantities: p(x:t) ' density (kg/m*) p(x:t) pressure [N/m?) u(x;t) velocity (m/s) o~(x;t) stress tensor (N/m2) f(x:t) body forces density(iV/m'3) D(x:t) rate of strain(l/.s) 1.1.2 Frictional flow Granular material's behaviour could be divided into three fundamental regimes. At low concentration and high shear rates, friction between grains can be neglected compared to collisional force. This case is called the rapid (or collisional) granular flow regime. Similar concepts and analysis from molecular kinetics are proposed, and hydrodynamic equations are derived with constitutive equations for the density, velocity and granular temperature. [19] Another mechanism, kinetic-collisional stress has been introduced for the constitutive law. [9] When the granular flow is moving slowly, i.e. with low rate-of-strain and high concentration, it is called frictional regime, since frictional stress dominates in the interaction of grains. The flow behaves like a rigid-plastic flow. Schaeffer first introduced the incompressible granular flow.model for the frictional case, and 3 discussed its ill-posedness in 1987[47]. Between these two cases, is the intermediate regime where both collisional and ii'ictional inteactions must be considered. In this thesis, we will only consider the frictional regime, and assume it to be perfect rigid-plastic flow. For simplicity, when we refer to sand behaviour in this thesis, we are mostly talking about this frictional regime. 1.2 Related works 1.2.1 Sand in Graphics Several authors have worked on sand animation, beginning with Miller and Pearce[36] They presented a method for animating viscous fluids by simulating the forces of such particles interacting with each other, and demonstrated a simple particle system model with short-range interaction forces which could be tuned to achieve (amongst other things) powder-like behaviour. Later Luciani et al.[33] developed-a similar multi-scale particle system model specifically for granular materials using damped nonlinear springs at a coarse length scale and a faster linear model at a fine length scale. L i and JVIoshell[31] presented a dynamic height-field simulation of soil based on the standard engineering Mob.r-Cou.lomb constitutive model of granular mate-rials. They used a dynamic model for soil slippage and soil manipulations under the constraint of volume conservation, and developed a numerical algorithm of lin-ear time and space complexities to meet the need of realtime computer simulation. Sumner et al.[53] took a similar heightfield approach with simple displacement and erosion rules to model footprints, tracks, etc. Onoue and Nishita[42] recently ex-tended this to multi-valued heightfields, allowing for some 3D effects. And recently, Bell[3] simulated granular material with discrete elements represented by particles to handle difficult topology evolved. 4 1.2.2 Sand grains as rigid bodies As we mentioned above, one approach to granular materials is directly simulating the grains as rigid bodies. Milenkovic[34] demonstrated a simulation of 1000 rigid spheres falling through an hour-glass using optimization methods for resolving con-tact. Milenkovic and Schmidl[35] improved the capability of this algorithm by using quadratic programming (QP) to increase the integration time steps, and Guendel-nian et al.[20] further accelerated rigid body simulation, showing 500 nonconvex rigid bodies falling through a funnel. 1.2.3 Particle-based Water Simulation Particles have been a popular technique in graphics for water simulation. Smoothed Particle Hydrodynamics(SPH) was introduced for computational fluid dynamics, by representing the fluid with a set of particles. These particles work as matter elements or sample points of the values or derivatives of physics quantities. SPH has an obvious advantage that pure advection is treated exactly in SPH, while for finite difference schemes, numerical error will smooth out details in advections. The SPH method has been applied widely including diffusion problems, turbulence and multiphase flow problems. See Monaghan[37] for the standard review of SPH. Desbrun and Cani[10] introduced SPH to the animation literature, demon-strating a viscous fluid flow simulation using particles alone. JVIiiller et al.[39] developed SPH further for water simulation, achieving im-pressive interactive results. Premoze et al.[44] used a variation on SPH with an approximate projection solve for their water simulations, but generated the final rendering geometry with a grid-based level set. 5 1.2.4 G r i d - b a s e d W a t e r S i m u l a t i o n Particle-based simulation can suffer from high computational costs and'stability problems. There has been more work on animating water with grids for efficient simulation with better stability. Foster and Metaxas[15] developed the first grid-based fully 3D water simulation in graphics. They were using a staggered grid for solving the Navier-Stokes equation, and marker particles to track the fluid position. Velocity advection is treated with forward integration. Stam[51] provided the semi-Lagrangian advection method which is unconditionally stable, and thus allows time steps large enough for interactive animation. The excessive numerical dissipation in that work was later mitigated by Fedkiw et al[14] with higher order interpolation and vorticity confinement. One of the problems in grid-based algorithms is volume loss. To avoid volume loss for pure level set advection and the poor artifacts of the surface directly gen-erated from particles, Foster and Fedkiw[16] incorporated former work into a water solver, where particles are combined with a level set function to express the fluid dis-tribution. To this model Genevaux et al.[17] added two-way fluid-solid interaction forces. The interaction between fluid and solid is introduced by a clamped spring between each marker particle near solid object and each nodal mass of the solid. Carlson et al.[7] added variable viscosity to a water solver, providing beautiful simu-lations of wet sand dripping, which is achieved simply by increased viscosity. Enright et al.[13] extended the Foster and Fedkiw approach with particles on both sides of the interface and velocity extrapolation into the air. Losasso et al.[32] extended this to dynamically adapted octree grids, providing much enhanced resolution, and Rasmussen et al.[45] improved the boundary conditions and velocity extrapolation while adding several other features important for visual effects production. Carlson et al.[8] added better coupling between fluid and rigid body simulations—which we 6 parenthetically note had its origins in scientific work on fluid flow with sand grains. Hong and Kim[25] and Takahashi et al.[55] introduced volume-of-fluid algorithms for animating multi-phase flow (water and air, as opposed to just the water of the free-surface flows animated above). 1.2.5 Plastic Flow For more general plastic flow, most of the graphics work has dealt with meshes. Terzopoulos and Fleischer[56] first introduced plasticity to physics-based animation, with a simple ID model applied to their springs. O'Brien et al.[41] added plasticity to a fracture-capable tetrahedral-mesh finite element/simulation to support ductile fracture. Irving et al.[26] introduced a more sophisticated plasticity model along with their invertible finite elements, also for tetrahedral meshes. Real-time elas-tic simulation including plasticity has been the focus of several papers (e.g. [38]). Closest in spirit to the current paper. Goktekin et al.[18] added elastic forces and associated plastic flow to a water solver, enabling animation of a wide variety of non-Newtonian fluids. 1.2.6 Scientific Work on Granular Materials For a scientific description of the physics of granular materials, we refer the reader to Jaeger et al.[27]. In the soil mechanics literature there is a long history of numeri-cally simulating granular materials using an elasto-plastic finite element formulation, with Mohr-Coulomb or Drucker-Prager yield conditions and various non-associated plastic flow rules. We highlight the standard work of Nayak and Zienkiewicz[40], and the book by Smith and Griffiths[50] which contains code and detailed com-ments on F E M simulation of granular materials. Landslides and avalanches are two granular phenomena of particular interest, and generally have been studied using depth-averaged 2D equations introduced by Savage and Hutter[46]. For alternatives 7 that", simulate the material at the level of individual grains. Herrmann and Luding's review[24] is a good place to start. 1.2.7 Scient i f ic W o r k on F l u i d F l o w Our new fluid code traces its history back to the early particle-in-cell (PIC) work of Harlow[23] for compressible flow. Shortly thereafter Harlow and Welch[22] in-vented the marker-ancl-cell method for incompressible flow, with its characteristic staggered grid discretization and marker particles for tracking a free surface—the other fundamental elements of our algorithm. PIC suffered from excessive numerical dissipation, which was cured by the Fluid-Implicit-Particle (FLIP) method[5]: Kothe and Brackbill[29] later worked on adapting FLIP to incompressible flow. Compress-ible FLIP was also extended to an elasto-plastic finite element formulation, the Material Point Method[52]. which has been used to model granular materials at the level of individual grains[2] amongst other things. M P M was used by Konagai and Johansson[28] for simulating large-scale (continuum) granular materials, though only in 2D and at considerable computational expense. 1.3 Overview of the Thesis In Chapter 2, we explain our sand modelling. Our constitutive law is based on a continuous description about granular flow, and assuming our frictional sand flow to be perfectly rigid-plastic. Frictional boundary conditions are applied and details about the numerical implementation is discussed. In Chapter 3. we also present a new fluid simulation method. As previous papers on simulating fluids have noted, grids and particles have complementary strengths and weaknesses. Here we combine the two approaches, using particles for our basic representation and for advection, but auxiliary grids to compute all 8 the spatial interactions including boundary conditions, incompressibility, and in the case of sand, friction forces. Our simulations only output particles that indicate where the fluid (or sand flow) is. To actually render the result, we need to reconstruct a smooth surface that wraps around these particles. In Chapter 4 we explain our improvement for the level set reconstruction, and the advantages this framework has over existing approaches. 9 Chapter 2 Sand Model ing A s we assumed, we consider sand as a k i n d of con t inuous m a t e r i a l , a n d a p p l y fluid d y n a m i c s expressions to descr ibe the behav io r of sand . In th i s chapter , we w i l l first r ev iew the general f l u id d y n a m i c s concepts and d e s c r i p t i o n of f lu id s i m u l a t i o n to c la r i fy concepts . T h e d y n a m i c s of g ranu la r mate r ia l s have been s t ud i ed ex tens ive ly i n the field of so i l mechanics . T h e r e have been over one h u n d r e d k i n d s of different mode ls abou t cons t i t u t i ve r e l a t i onsh ip of g ranu la r flow. W e will i n t roduce our m o d e l i n g of sand , or cons t i t u t i ve l aw. a s suming tha t s and flow is per fec t ly r i g i d - p l a s t i c w i t h the M o h r - C o u l o m b p l a s t i c i t y law. W e w i l l discusfs i n d e t a i l abou t f r i c t i ona l stress w h i c h makes sand different f rom rea l fluid. T o achieve efficient s imula t ions for a n i m a t i o n purposes , we m a d e some s i m -plified a s sumpt ions for the sand m o d e l i n g . These a s sumpt ions a l low us to express our sand s i m u l a t i o n as an ex tens ion of a fluid s i m u l a t i o n process . T h e cond i t ions for these a s sumpt ions as w e l l as the i r advantages a n d disadvantages w i l l also be c lar i f ied . De t a i l s of our s and s i m u l a t i o n a l g o r i t h m , as we l l as some i m p l e m e n t a t i o n issues will also be discussed in the last par t . 10 2.1 F l u i d dynamics In the field of hydrodynamics, there are two ways to describe fluid properties. L a -grangian framework is more natural from kinetic theory of molecules. In the L a -grangian framework, a fluid is considered to be a collection of a lot of abstract moving particles, each particle's behavior is described by the state and position as functions of time. In many cases, the initial position of that particle is used for reference. In the Eulerian approach, all fluid properties, including velocity and pressure, are considered as a function of space and time. For any physics property in Table 1.1.1.the material time derivative D/Dt measures how the quantity at a point in space changes as the material flows past as well as changes. For example, using the chain rule with the density p illustrates the material time derivative: §-fp(t;p) = ^-fp{x{t:,p).t) + ~x(t:p) • Vp(x{typ).t) = p(x,t)t + u{x,t) • Vp{x.t). This also explains derivative relationship between Eulerian and Lagrangian descrip-tion I n c o m p r e s s i b l e fluid For incompressible fluids, the density remains constant in time as it is acl-vected with the flow. i.e. the material derivative of density is zero: ~p(t;p) = P(*,t)t + u(x,t) • Vp(x,t) = 0 Vp s.t. x(0;p) £ fi(0). In this thesis, we wil l only consider the simple case of p being constant, which is a sufficient but not necessary condition for incompressibility. M a s s c o n s e r v a t i o n a n d M o m e n t u m c o n s e r v a t i o n Mass conservation and momentum conservation can easily be derived by taking the time derivative of 11 the mass or momentum integrated over a volume element(see [21] for example): pL + (u-V)p = 0 (2.1) put+u- Vf>t) =pf + S7-a ' (2.2) where a is the stress tensor. In a Cartesian coordinate system, we know that the three columns of a are actually interaction tractions over the three coordinate planes of a cubic volume element, a must always be a symmetric tensor, so cr,;^  is actually the stress on the i-plane in j direction. • Conventionally, the isotropic part of sigma is separated from the rest of the stress tensor, corresponding to the fluid pressure p: a = r — pi N a v i e r - S t o k e s E q u a t i o n For Newtonian fluids, like water and thin mineral oils, where rj is the dynamic viscosity, 77 •'= pv. In this thesis, we ignore difference in the temperature for the fluids, and take viscosity // to be constant, so puL + u • V(pu) = pf + r/V • V u - V • pi V p ut + u • V u = / + / / V • Vu -P This equation, in combination with mass conservation equation for incompressible fluid forms the basic Navier-Stokes equation : . V -u =. 0 u,, + u • V u = / + ; / V • V u - ^ T o w a r d s s a n d •12 Newtonian flow is quite different from plastic flow which occurs only when a finite minimum force is exceeded. Sand is usually modeled as elasto-plastic flow or rigid-plastic flow. Then the major problem is how to decide stress a, or rather the shearing part of it r. 2 . 2 Frictional Plasticity The standard approach to defining the continuum behavior of sand and other gran-ular (or '''frictional") materials is in terms of plastic yielding. Suppose the stress tensor a has mean stress crm = tr{a)/'i and Von Mises equivalent shear stress a = |<7 — arn5\p/\/2 (where | • \p is the Frobenius norm). The Mohr-Coulomb 1 law says the material will not yield as long as \/3a < sin (j)am (2.3) where 4> is the friction angle. Heuristically, this is just the classic Coulomb static friction law generalized to tensors: the shear stress a — am5 that tries to force particles to slide against one another is annulled by friction if the pressure o~rn forcing the particles against each other is proportionally strong enough. The coefficient of friction /./, commonly used in Coulomb friction is replaced here by sin0. If the yield condition is met and the sand can start to flow, a flow rule is' required. The simplest reasonable flow direction is a — am5. Heuristically this means the sand is allowed to slide against itself in the direction that the shearing force is pushing. Note that this is nonassociated. i.e. not equal to the gradient of the yield condition. While associated flow rules are simpler and are usually assumed for plastic materials (and have been used exclusively before in graphics[41. 18. 26]), they are impossible here. The Mohr-Coulomb law compares the shear part of the ' T e c h n i c a l l y M o h r - C o u l o m b uses the T r e s c a d e f i n i t i o n of e q u i v a l e n t s h e a r s tress , b u t s ince it is no t s m o o t h a n d poses n u m e r i c a l d i f f icul t ies , m o s t p e o p l e use V o n M i s e s . 13 stress to the dilatational part, unlike normal plastic materials which ignore the dilation part. Thus an associated flow rule would allow the material to shear if and only if it dilates proportionally—the more the sand flows, the more it expands. Technically sand does dilate a little when it begins to flow—the particles need some elbow room to move past each other—but this dilation stops as soon as the sand is freely flowing. This is a fairly subtle effect that is very difficult to observe with the eye, so we confidently ignore it for animation. Once plasticity has been defined, the standard soil mechanics approach to simulation would be to add a simple elasticity relation, and use a finite element solver to simulate the sand. However, we would prefer to avoid the additional complexity and expense of F E M (which would require numerical quadrature, an implicit solver to avoid stiff time step restrictions due to elasticity, return mapping" for plasticity, etc.). For the purposes of plausible animation we will make some further simplifying assumptions so we can retrofit sand modeling into an existing water solver. 2.3 A Simplified Model 2.3.1 A s s u m p t i o n s for s impl i f i ca t ion We first ignore the nearly imperceptible elastic deformation regime when there is no yielding, as the elasticity in rock is so small. And we also ignore the tiny volume changes that sand undergoes as it starts and stops flowing. This is correct only for the frictional flow regime which is what we are concentrating on. Thus our domain, can be decomposed into regions which are rigidly moving (where the Mohr-Coulomb yield condition has not been met) and the rest where we have an incompressible shearing flow. We then further assume that the pressure required to make the entire velocity field incompressible will be similar to the true pressure in the sand. This is certainly 14 false: for example, it is well known that a column of sand in a silo has a maximum pressure independent of the height of the column2 whereas in.a column of water the pressure increases linearly with height. However, we can only think of one case where this might be implausible in animation: the pressure limit means sand in an hour glass flows at a constant rate independent of the amount of sand remaining (which is the reason hour glasses work). We suggest our inaccurate results will still be plausible in most other cases. A more accurate model was given by Schaeffer[47]. They discussed a rigid-perfectly plastic, incompressible, cohesionless Coulomb granular flow. But they didn't make the pressure assumption, instead, they solve pressure directly. Since pressure appears not only in making the velocity incompressible, but also in stress tensor term, this will introduce a lot more work in Finite Element solving. 2.3 .2 M o h r - C o u l o m b l a w The constitutive law has two parts: the yield condition and the flow rule. Since we are neglecting elastic effects, we assume that where the sand is flowing the frictional stress is simply where D = (Vr/.+ S7uT)/2 is the strain rate. That is, the frictional stress is the point on the yield surface that most directly resists the sliding. Although this is frictional stress only for yielding region, we compute it for all fluid cells for yield condition. In fact , this value recognizes the maximum frictional force under current normal , pressure to resist relative movement between grid cells . The real frictional stress could be either equal to that on yielding or smaller than that when smaller static friction could afford the resisting of yielding. 2This is due to the force that resists the weight of the sand above being transferred to the walls of the silo by friction—sometimes causing silos to unexpectedly collapse as a result. a [ = — sin (pp D (2-4) 15 In fact, since the stress tensor has a linear relationship with the direction of rate of strain instead of rate of strain itself, such modification might be affecting the incompressibility in velocity. By the numerical result, such incompressibility is vis u ally accep t ab le. We finally need a way of determining the yield condition without tracking elastic stress and strain, i.e. when the sand should be rigidified. Consider one grid cell, of side length Ax. The relative sliding velocities between opposite faces in the cell are Vr = AxD. The mass of the cell is M = pAx*. Ignoring other cells, the forces required to stop all sliding motion in a time step A t are F — -VrM/ At = — (AxD)(pAxA)/At, derived from integrating Newton's law to get the update formula V"'ew — V + AtF/M. Dividing F by the cross-sectional area Ax2 to get the stress gives: Vrigid = ^ . l^-Oj This is actually the minimum stress required for rigidifying sand between two grid cells. And we can compare this with the maximum frictional stress that could be afforded corresponding to current normal pressure aj, and check if this satisfies our yield inequality: if it does, i.e. if the required friction for resisting movement is small enough to be afforded with current pressure, and hence the sand can resist forces and inertia trying to make it slide, then it could be kept static with a static friction, and the material in that cell should be rigid at the end of the time step. Otherwise, when the required friction for resisting movement is bigger than maximum friction stress, then the real friction stress is just this maximum friction stress. And the sand starts to slide. 2.3.3 Algorithm This gives us the following algorithm for sand simulation. 16 • For every time o Apply advection • Apply gravity and boundary conditions, solve for pressure to enforce incornpressibility, and subtracting A t / p V p from the intermediate velocity held to make it incompressible. • Evaluate the strain rate tensor D in each grid cell with standard central differences, and decide,yielding condition for each grid cell: • If the resulting arigid from equation 2.5 satisfies the yield condition with the pressure we computed for incornpressibility, we mark the grid cell as rigid and store (Trigi(i at that cell. • Otherwise, we store the sliding frictional stress a, from equation 2.4, • Treat the two regions differently: • Find all connected groups of rigid cells, and project the velocity field in each separate group to the space of rigid body motions. • For all the yielding cells, we update with the frictional stress, using standard central differences for u+ = A t / p V • 07. • EndFor 2.3.4 S a n d r ig id i f i ca t ion For rigid cells, we will.project the velocity field in each separate group to the space of a corresponding rigid body movement velocity. Similar to the rigid fluid work by Carlson et. al.[7], recall that rigid body motion is determined entirely by the mass center velocity v and angular velocity tu. These can be easily calculated, via velocity 17 / / \ V I \ / ***] ! Figure 2.1: Solidification of non-yielding grid cells. and angular momentum conservation (Fig 2.1) Yl m « v i = grid cells to be rigidilied ^ m,n x V ; = grid cells to be rigidified ( ^2  m i ) v grid cells to be rigidified ( 22  mi)& grid cells to (2.6) (2.7) be rigidified where r is the position of each cell. The projected rigid velocity in this region is v(x) = v + (x - x) x m e r e x = ( m < x i ) / ( Yl m i ) grid cells to grid cells to be rigidilied be rigidified 2.4 Frict ional Boundary Conditions So far we have covered the friction within the sand, but there is also the friction between the sand and other objects (e.g. the solid wall boundaries) to worry about. Our simple solution is to use the friction formula of Bridson et al.[6] when we enforce the t/. • n > 0 boundary condition on the grid. When we project out the normal com-ponent of velocity, we reduce the tangential component of velocity proportionately, IS F i g u r e 2 . 2 : T h e s a n d b u n n y w i t h a b o u n d a r y f r i c t i o n c o e f f i c i e n t \x = 0 . 6 : c o m p a r e t o f i g u r e 5 . 1 w h e r e z e r o b o u n d a r y f r i c t i o n w a s u s e d . 1 9 c l a m p i n g i t t o z e r o f o r t h e c a s e o f s t a t i c f r i c t i o n : uT = m a x ^ 0 , 1 - ^ 7 p ) U T ( 2 - 8 ) w h e r e /./, i s t h e C o u l o m b f r i c t i o n c o e f f i c i e n t b e t w e e n t h e s a n d a n d t h e w a l l . T h i s i s a c r u c i a l a d d i t i o n t o a f l u i d s o l v e r , s i n c e t h e b o u n d a r y c o n d i t i o n s p r e v i o u s l y d i s c u s s e d i n t h e a n i m a t i o n l i t e r a t u r e e i t h e r d o n ' t p e r m i t a n y k i n d o f s l i d i n g (M = 0 ) w h i c h m e a n s s a n d s t i c k s e v e n t o v e r t i c a l s u r f a c e s , o r a l w a y s a l l o w s l i d i n g (u • 77, > 0 , p o s s i b l y w i t h a v i s c o u s r e d u c t i o n o f t a n g e n t i a l v e l o c i t y ) w h i c h m e a n s s a n d p i l e s w i l l n e v e r b e s t a b l e . C o m p a r e f i g u r e 2 . 2 , w h i c h i n c l u d e s f r i c t i o n , t o f i g u r e 5 . 1 w h i c h d o e s n ' t . 2.5 Cohesion A c o m m o n e n h a n c e m e n t t o t h e b a s i c M o h r - C o u l o m b c o n d i t i o n i s t h e a d d i t i o n o f c o h e s i o n : \/3(7 < s i n g e r , , , , + c ( 2 . 9 ) w h e r e c > 0 i s t h e c o h e s i o n c o e f f i c i e n t . T h i s i s a p p r o p r i a t e f o r s o i l s o r o t h e r s l i g h t l y s t i c k y m a t e r i a l s t h a t c a n s u p p o r t , s o m e t e n s i o n b e f o r e y i e l d i n g . W e h a v e f o u n d t h a t i n c l u d i n g a v e r y s m a l l a m o u n t o f c o h e s i o n i m p r o v e s o u r r e s u l t s f o r s u p p o s e d l y c o h e s i o n - l e s s m a t e r i a l s l i k e s a n d . I n w h a t s h o u l d b e a s t a b l e s a n d p i l e , s m a l l n u m e r i c a l e r r o r s c a n a l l o w s o m e s l i p p a g e ; a t i n y a m o u n t o f c o h e s i o n c o u n t e r s t h i s e r r o r a n d m a k e s t h e s a n d s t a b l e a g a i n , w i t h o u t , v i s i b l y e f f e c t i n g t h e f l o w w h e n t h e s a n d s h o u l d b e m o v i n g . F o r m o d e l i n g s o i l s w i t h t h e i r t r u e c o h e s i o n c o e f f i c i e n t , o u r m e t h o d i s t o o s t a b l e : o b v i o u s l y u n s t a b l e s t r u c t u r e s a r e i m p l a u s i b l y h e l d r i g i d . W e w i l l i n v e s t i g a t e t h i s i s s u e i n t h e f u t u r e . H o w e v e r , f o r m o d e l i n g s a n d w i t h l o w c o h e s i o n , i n t r o d u c i n g a l i t t l e c o h e s i o n w i l l h e l p i n s t a b l i z a t i o n . 2 0 Chapter 3 Fluid Simulation Revisited 3.1 Gr ids and Particles T h e r e a r e c u r r e n t l y t w o m a i n a p p r o a c h e s t o s i m u l a t i n g f u l l y t h r e e - d i m e n s i o n a l w a t e r -i n c o m p u t e r g r a p h i c s : E u l e r i a n g r i d s a n d L a g r a n g i a n p a r t i c l e s . G r i d - b a s e d m e t h o d s ( r e c e n t p a p e r s i n c l u d e [8, 18. 3 2 ] ) s t o r e v e l o c i t y , p r e s s u r e , s o m e s o r t o f i n d i c a t o r o f w h e r e t h e f l u i d i s o r i s n ' t , a n d a n y a d d i t i o n a l v a r i a b l e s o n a fixed g r i d . U s u a l l y a s t a g g e r e d " ' M A C " g r i d i s u s e d , a l l o w i n g s i m p l e a n d s t a b l e p r e s s u r e s o l v e s . P a r t i c l e -b a s e d m e t h o d s , e x e m p l i f i e d b y S m o o t h e d P a r t i c l e H y d r o d y n a m i c s ( s e e [ 3 7 . . 3 9 , 4 4 ] f o r e x a m p l e ) , d i s p e n s e w i t h g r i d s e x c e p t p e r h a p s f o r a c c e l e r a t i n g g e o m e t r i c s e a r c h e s . I n s t e a d f l u i d v a r i a b l e s a r e s t o r e d o n p a r t i c l e s w h i c h r e p r e s e n t a c t u a l c h u n k s o f f l u i d , a n d t h e m o t i o n o f t h e f l u i d i s a c h i e v e d s i m p l y b y m o v i n g t h e p a r t i c l e s t h e m s e l v e s . T h e L a g r a n g i a n f o r m o f t h e N a v i e r - S t o k e s e q u a t i o n s ( s o m e t i m e s u s i n g a c o m p r e s s -i b l e f o r m u l a t i o n w i t h a f i c t i t i o u s e q u a t i o n o f s t a t e ) i s u s e d t o c a l c u l a t e t h e i n t e r a c t i o n f o r c e s o n t h e p a r t i c l e s . T h e p r i m a r y s t r e n g t h o f t h e g r i d - b a s e d m e t h o d s i s t h e s i m p l i c i t y o f t h e d i s -c r e t i z a t i o n a n d s o l u t i o n o f t h e i n c o r n p r e s s i b i l i t y c o n d i t i o n , w h i c h f o r m s t h e c o r e o f t h e f l u i d s o l v e r . U n f o r t u n a t e l y , g r i d - b a s e d m e t h o d s h a v e d i f f i c u l t i e s w i t h t h e 2 1 a d v e c t i o n p a r t o f t h e e q u a t i o n s . T h e c u r r e n t l y f a v o r e d a p p r o a c h i n g r a p h i c s , s e m i -L a g r a n g i a n a d v e c t i o n , s u f f e r s f r o m e x c e s s i v e n u m e r i c a l d i s s i p a t i o n d u e t o a c c u m u -l a t e d i n t e r p o l a t i o n e r r o r s . T o c o u n t e r t h i s n o n p h y s i c a l e f f e c t , a n o n p h y s i c a l t e r m s u c h a s v o r t i c i t y c o n f i n e m e n t m u s t b e a d d e d ( a t t h e e x p e n s e o f c o n s e r v i n g a n g u l a r o r e v e n l i n e a r m o m e n t u m ) . W h i l e h i g h r e s o l u t i o n m e t h o d s f r o m . s c i e n t i f i c c o m p u t i n g c a n a c c u r a t e l y s o l v e f o r t h e a d v e c t i o n o f a w e l l - r e s o l v e d v e l o c i t y f i e l d t h r o u g h t h e f l u i d , t h e i r i m p l e m e n t a t i o n i s n ' t e n t i r e l y s t r a i g h t f o r w a r d : t h e i r w i d e s t e n c i l s m a k e l i f e d i f f i c u l t o n c o a r s e a n i m a t i o n g r i d s t h a t r o u t i n e l y r e p r e s e n t f e a t u r e s o n l y o n e o r t w o g r i d c e l l s t h i c k . M o r e o v e r , e v e n f i f t h - o r d e r a c c u r a t e m e t h o d s f a i l t o a c c u r a t e l y a d v e c t l e v e l s e t s f l l ] a s a r e c o m m o n l y u s e d t o r e p r e s e n t t h e w a t e r s u r f a c e , quickly r o u n d i n g o f f a n y s m a l l f e a t u r e s . T h e m o s t a t t r a c t i v e a l t e r n a t i v e t o l e v e l s e t s i s v o l u m e - o f - f l u i d ( V O F ) , w h i c h c o n s e r v e s w a t e r u p t o f l o a t i n g - p o i n t p r e c i s i o n : h o w -e v e r i t h a s d i f f i c u l t i e s m a i n t a i n i n g a n a c c u r a t e b u t s h a r p l y - d e f i n e d s u r f a c e . C o u p l i n g l e v e l s e t s w i t h V O F i s p o s s i b l e [ 5 4 ] b u t a t a s i g n i f i c a n t i m p l e m e n t a t i o n a n d c o m p u -t a t i o n a l c o s t . O n t h e o t h e r h a n d , p a r t i c l e s t r i v i a l l y h a n d l e a d v e c t i o n w i t h e x c e l l e n t a c c u r a c y — s i m p l y b y l e t t i n g t h e m flow t h r o u g h t h e v e l o c i t y f i e l d u s i n g O D E s o l v e r s — b u t h a v e d i f f i c u l t i e s w i t h p r e s s u r e a n d t h e i n c o m p r e s s i b i l i t y c o n d i t i o n , o f t e n n e c e s s i t a t i n g s m a l l e r t h a n d e s i r e d t i m e s t e p s f o r s t a b i l i t y . SPH m e t h o d s i n p a r t i c u l a r c a n ' t t o l -e r a t e n o n u n i f o r m p a r t i c l e s p a c i n g , w h i c h c a n b e d i f f i c u l t t o e n f o r c e t h r o u g h o u t t h e e n t i r e l e n g t h o f a s i m u l a t i o n . R e a l i z i n g t h e s t r e n g t h s a n d w e a k n e s s e s o f t h e t w o a p p r o a c h e s c o m p l e m e n t e a c h o t h e r F o s t e r a n d F e d k i w [ 1 6 ] a n d l a t e r E n r i g h t e t a l . [ 1 3 ] a u g m e n t e d ' a g r i d -b a s e d m e t h o d w i t h m a r k e r p a r t i c l e s t o c o r r e c t t h e e r r o r s i n t h e g r i d - b a s e d l e v e l s e t a d v e c t i o n . T h i s p a r t i c l e - l e v e l s e t m e t h o d , m o s t r e c e n t l y i m p l e m e n t e d o n a n a d a p t i v e o c t r e e [ 3 2 ] , h a s p r o d u c e d t h e h i g h e s t f i d e l i t y w a t e r a n i m a t i o n s i n t h e f i e l d . H o w e v e r , w e b e l i e v e p a r t i c l e s c a n b e e x p l o i t e d e v e n f u r t h e r , s i m p l i f y i n g a n d a c c e l e r a t i n g t h e i m p l e m e n t a t i o n , a n d a f f o r d i n g s o m e n e w b e n e f i t s i n f l e x i b i l i t y . 3.2 Particle-in-Cell Methods C o n t i n u i n g t h e g r a p h i c s t r a d i t i o n o f r e c a l l i n g e a r l y c o m p u t a t i o n a l f l u i d d y n a m i c s r e s e a r c h , w e r e t u r n t o t h e P a r t i c l e - i n - C e l l ( P I C ) m e t h o d o f Harlow[23]. T h i s w a s a n e a r l y a p p r o a c h t o s i m u l a t i n g c o m p r e s s i b l e f l o w t h a t h a n d l e d a d v e c t i o n w i t h p a r -t i c l e s , b u t e v e r y t h i n g e l s e o n a g r i d . A t e a c h t i m e s t e p , t h e f l u i d v a r i a b l e s a t a g r i d p o i n t w e r e i n i t i a l i z e d a s a w e i g h t e d a v e r a g e o f n e a r b y p a r t i c l e v a l u e s , t h e n u p d a t e d o n t h e g r i d w i t h t h e n o n - a c l v e c t i o n p a r t o f t h e e q u a t i o n s . T h e n e w p a r t i c l e v a l u e s w e r e t h e n i n t e r p o l a t e d f r o m t h e u p d a t e d g r i d v a l u e s , a n d finally t h e p a r t i c l e s m o v e d a c c o r d i n g t o t h e g r i d v e l o c i t y f i e l d . T h e m a j o r p r o b l e m w i t h P I C w a s t h e e x c e s s i v e n u m e r i c a l d i f f u s i o n c a u s e d b y r e p e a t e d l y a v e r a g i n g a n d i n t e r p o l a t i n g t h e f l u i d v a r i a b l e s . B r a c k b i l l a n d R . u p p e l [ 5 ] c u r e d t h i s w i t h t h e F l u i d - I m p l i c i t - P a r t i c l e ( F L I P ) m e t h o d , w h i c h a c h i e v e d " a n a l -m o s t t o t a l a b s e n c e o f n u m e r i c a l d i s s i p a t i o n a n d t h e a b i l i t y t o r e p r e s e n t l a r g e v a r i -a t i o n s i n d a t a . " T h e c r u c i a l c h a n g e w a s t o m a k e t h e p a r t i c l e s t h e f u n d a m e n t a l r e p r e s e n t a t i o n o f t h e f l u i d , a n d u s e t h e a u x i l i a r y g r i d s i m p l y t o i n c r e m e n t t h e p a r t i c l e v a r i a b l e s a c c o r d i n g t o t h e c h a n g e c o m p u t e d o n t h e g r i d . W e h a v e a d a p t e d P I C a n d F L I P t o i n c o m p r e s s i b l e flow1 a s f o l l o w s : • I n i t i a l i z e p a r t i c l e p o s i t i o n s a n d v e l o c i t i e s ( F i g 3 . 1 ( a ) ) • F o r e a c h t i m e s t e p : • A t e a c h s t a g g e r e d M A C g r i d n o d e , c o m p u t e a w e i g h t e d a v e r a g e o f t h e n e a r b y p a r t i c l e v e l o c i t i e s ( F i g 3 . 1 ( b ) ) • F o r F L I P : S a v e t h e g r i d v e l o c i t i e s . ' The one precedent for this that we could find is a reference to an unpublished manuscript[29]. 23 1 n _ t t • i t • — , I #-* • — • (o) F i g u r e 3 . 1 : P I C a n d F L I P M e t h o d , ( a ) A l g o r i t h m s t a r t s w i t h p a r t i c l e s c a r r y i n g t h e i r v e l o c i t i e s , ( b ) T r a n s f e r v e l o c i t i e s f r o m p a r t i c l e s t o g r i d . ( c ) R e s o l v e f o r c e s o n g r i d , i n c l u d i n g e x t e r n a l f o r c e s l i k e g r a v i t y , r e s o l v i n g b o u n d a r y c o n d i t i o n s a n d p r o j e c t i n g v e l o c i t y b a c k t o b e i n c o m p r e s s i b l e . ( d ) U p d a t e p a r t i c l e v e l o c i t i e s , ( e ) U p d a t e p a r t i c l e p o s i t i o n c a r r y i n g v e l o c i t i e s w i t h t h e m ( a d v e c t i o n ) . 24 « D o a l l t h e n o n - a d v e c t i o n s t e p s o f a s t a n d a r d w a t e r s i m u l a t o r o n t h e g r i d . ( F i g 3 . 1 ( c ) , 3 . 1 ( d ) ) o F o r F L I P : S u b t r a c t t h e n e w g r i d v e l o c i t i e s f r o m t h e s a v e d v e l o c i t i e s , t h e n a d d t h e i n t e r p o l a t e d d i f f e r e n c e t o e a c h p a r t i c l e . • F o r P I C : I n t e r p o l a t e t h e n e w g r i d v e l o c i t y t o t h e p a r t i c l e s , o M o v e p a r t i c l e s t h r o u g h t h e g r i d v e l o c i t y f i e l d w i t h a n O D E s o l v e r , m a k i n g s u r e t o p u s h t h e m o u t s i d e o f s o l i d w a l l b o u n d a r i e s . ( F i g 3 . 1 ( e ) ) o W r i t e t h e p a r t i c l e p o s i t i o n s t o o u t p u t . O b s e r v e t h e r e i s n o l o n g e r a n y n e e d t o i m p l e m e n t g r i d - b a s e d a d v e c t i o n , o r t h e m a t c h i n g s c h e m e s s u c h a s v o r t i c i t y c o n f i n e m e n t a n d p a r t i c l e - l e v e l s e t t o c o u n t e r n u m e r i c a l d i s s i p a t i o n . I n i t i a l i z i n g P a r t i c l e s W e h a v e f o u n d a r e a s o n a b l e e f f e c t i v e p r a c t i c e i s t o c r e a t e 8 p a r t i c l e s i n e v e r y g r i d c e l l , r a n d o m l y j i t t e r e d f r o m t h e i r 2 x 2 x 2 s u b g r i d p o s i t i o n s t o a v o i d a l i a s i n g w h e n t h e f l o w i s u n d e r r e s o l v e d a t t h e s i m u l a t i o n r e s o l u t i o n . W i t h f e w e r p a r t i c l e s p e r g r i d c e l l , w e t e n d t o r u n i n t o o c c a s i o n a l " g a p s " i n t h e f l o w , a n d m o r e p a r t i c l e s w i l l b e i n t r o d u c i n g m u c h m o r e c o m p u t a t i o n . T o h e l p w i t h s u r f a c e r e c o n s t r u c t i o n l a t e r ( s e c t i o n 4) w e r e p o s i t i o n p a r t i c l e s t h a t l i e n e a r t h e i n i t i a l w a t e r s u r f a c e ( s a y w i t h i n o n e g r i d c e l l w i d t h ) t o b e e x a c t l y h a l f a g r i d c e l l a w a y f r o m t h e s u r f a c e . T r a n s f e r r i n g to the G r i d E a c h g r i d p o i n t t a k e s a w e i g h t e d a v e r a g e o f t h e n e a r b y p a r t i c l e s . W e d e f i n e ' ' ' n e a r " a s b e i n g c o n t a i n e d i n t h e c u b e o f t w i c e t h e g r i d c e l l w i d t h c e n t e r e d o n t h e g r i d p o i n t . ( N o t e t h a t o n a s t a g g e r e d M A C g r i d , t h e d i f f e r e n t c o m p o n e n t s o f v e l o c i t y w i l l h a v e 25 particle to grid Accumulation Weighted average: grid to particle U2 • A3- • At- V2 1 Bi Bo A2 Ao, U1 U3 B3 B2 vo V1 v = i?, )v0 + 5 1 v i ;+5 ,v J + 5 3 v ; j F i g u r e 3 . 2 : V e l o c i t y i n t e r p o l a t i o n b e t w e e n p a r t i c l e s a n d g r i d c e l l s . 2 6 o f f s e t n e i g h b o r h o o d s . ) T h e w e i g h t o f a p a r t i c l e i n t h i s c u b e i s t h e s t a n d a r d t r i l i n e a r w e i g h t i n g . W e a l s o m a r k t h e g r i d c e l l s t h a t c o n t a i n a t l e a s t o n e particle (Fig 3 . 2 ) . I n f u t u r e w o r k w e w i l l i n v e s t i g a t e u s i n g a m o r e a c c u r a t e i n d i c a t o r , e . g . r e c o n s t r u c t i n g a s i g n e d d i s t a n c e h e l d o n t h e g r i d f r o m d i s t a n c e v a l u e s s t o r e d o n t h e p a r t i c l e s . T h i s w o u l d a l l o w u s t o e a s i l y i m p l e m e n t a s e c o n d - o r d e r a c c u r a t e f r e e s u r f a c e b o u n d a r y c o h d i t i o n [ 1 2 ] w h i c h s i g n i f i c a n t l y r e d u c e s g r i d a r t i f a c t s . W e a l s o n o t e t h a t t h e g r i d i n o u r s i m u l a t i o n i s p u r e l y a n a u x i l i a r y s t r u c t u r e t o t h e f u n d a m e n t a l p a r t i c l e r e p r e s e n t a t i o n . I n p a r t i c u l a r , w e a r e n o t r e q u i r e d t o u s e t h e s a m e g r i d e v e r y t i m e s t e p . A n o b v i o u s o p t i m i z a t i o n w h i c h w e h a v e n o t y e t i m p l e m e n t e d — r e n d e r i n g i s c u r r e n t l y o u r b o t t l e n e c k — i s t o d e h n e t h e g r i d a c c o r d i n g t o t h e b o u n d i n g b o x o f t h e p a r t i c l e s e v e r y t i m e s t e p . T h i s a l s o m e a n s w e h a v e n o a p r i o r i l i m i t s o n t h e s i m u l a t i o n d o m a i n . W e p l a n i n t h e f u t u r e t o d e t e c t w h e n c l u s t e r s o f p a r t i c l e s h a v e s e p a r a t e d a n d u s e s e p a r a t e b o u n d i n g g r i d s f o r t h e m , f o r s i g n i f i c a n t l y i m p r o v e d e f f i c i e n c y . S o l v i n g o n the G r i d W e f i r s t a d d t h e a c c e l e r a t i o n d u e t o g r a v i t y t o t h e g r i d v e l o c i t i e s . W e t h e n c o n -s t r u c t a d i s t a n c e h e l d <p(x) i n t h e u n m a r k e d ( n o n - f l u i d ) p a r t o f t h e g r i d u s i n g f a s t s w e e p i n g [ 5 8 ] a n d u s e t h a t t o e x t e n d t h e v e l o c i t y f i e l d o u t s i d e t h e f l u i d w i t h t h e P D E V w • V r / > = 0 ( a l s o s o l v e d w i t h f a s t s w e e p i n g ) . W e e n f o r c e b o u n d a r y c o n d i t i o n s a n d i n c o r n p r e s s i b i l i t y a s i n E n r i g h t e t a l . [ 1 3 ] . t h e n e x t e n d t h e n e w v e l o c i t y f i e l d a g a i n u s i n g f a s t s w e e p i n g ( a s w e f o u n d i t t o b e m a r g i n a l l y f a s t e r a n d s i m p l e r t o i m p l e m e n t t h a n f a s t r n a r c h i n g [ l ] ) . U p d a t i n g P a r t i c l e V e l o c i t i e s A t e a c h p a r t i c l e , w e t r i l i n e a r l y i n t e r p o l a t e e i t h e r t h e v e l o c i t y ( P I C ) o r t h e c h a n g e i n v e l o c i t y ( F L I P ) r e c o r d e d a t t h e s u r r o u n d i n g e i g h t g r i d p o i n t s ( F i g 3 . 2 ) . F o r v i s c o u s 2 7 F i g u r e 3 . 3 : F L I P v s . P I C v e l o c i t y u p d a t e f o r t h e s a m e s i m u l a t i o n . N o t i c e t h e s m a l l - s c a l e v e l o c i t i e s p r e s e r v e d b y F L I P b u t s m o o t h e d a w a y b y P I C . f l o w s , s u c h a s s a n d , t h e a d d i t i o n a l n u m e r i c a l v i s c o s i t y o f P I C i s b e n e f i c i a l . I n t h e P I C m e t h o d , t h e v e l o c i t y i s s m o o t h e d o u t b y c o n s t a n t l y a v e r a g i n g a n d i n t e r p o l a t i n g a t e a c h t i m e s t e p w h i c h i n t r o d u c e s o b v i o u s n u m e r i c a l v i s c o s i t y . F o r i n v i s c i d f l o w s , s u c h a s w a t e r : F L I P i s p r e f e r a b l e . I n f a c t , i n t h e F L I P m e t h o d , o n l y v e l o c i t y i n c r e m e n t i s i n t e r p o l a t e d o n c e f o r e a c h t i m e s t e p . S e e figure 3 . 3 f o r a 2 D v i e w o f t h e d i f f e r e n c e s b e t w e e n P I C a n d F L I P . A w e i g h t e d a v e r a g e o f t h e t w o c a n b e u s e d t o t u n e j u s t h o w m u c h n u m e r i c a l v i s c o s i t y i s d e s i r e d . F o r e x a m p l e , a v i s c o s i t y s t e p o n t h e g r i d i n c o n c e r t w i t h P I C w o u l d b e r e q u i r e d f o r h i g h l y v i s c o u s fluids. M o v i n g P a r t i c l e s O n c e w e h a v e a v e l o c i t y f i e l d d e f i n e d o n t h e g r i d ( e x t r a p o l a t e d t o e x i s t e v e r y w h e r e ) w e c a n m o v e t h e p a r t i c l e s a r o u n d i n i t . W e u s e a s i m p l e RK2 O D E s o l v e r w i t h f i v e s u b s t e p s e a c h . o f w h i c h i s l i m i t e d b y t h e C F L c o n d i t i o n ( s o t h a t a p a r t i c l e m o v e s l e s s t h a n o n e g r i d c e l l i n e a c h s u b s t e p ) , s i m i l a r t o E n r i g h t e t a l . [ 1 3 ] . W e a d d i t i o n a l l y d e t e c t w h e n p a r t i c l e s p e n e t r a t e s o l i d w a l l b o u n d a r i e s d u e s i m p l y t o t r u n c a t i o n e r r o r i n R K 2 a n d t h e g r i d - b a s e d v e l o c i t y f i e l d , a n d m o v e t h e m i n t h e n o r m a l d i r e c t i o n b a c k t o j u s t o u t s i d e t h e s o l i d , t o a v o i d t h e o c c a s i o n a l s t u c k - p a r t i c l e a r t i f a c t t h i s w o u l d o t h e r w i s e c a u s e . T h i s w i l l i n t r o d u c e l o s s o f i n c o m p r e s s i b i l i t y , h e n c e , w e u s e d b e t t e r p r e s s u r e s o l v e r a n d m o r e a c c u r a t e b o u n d a r y c o n d i t i o n t o a v o i d i t . 2 8 3.2.1 E r r o r analysis E r r o r i s i n t r o d u c e d d u r i n g t h e p r o c e s s o f t r a n s f e r i n g v e l o c i t y b a c k a n d f o r t h b e t w e e n g r i d a n d p a r t i c l e s . F o r a s i m p l e a n a l y s i s , w e c o n s i d e r t h e 1 - d i m e n s i o n a l c a s e , a n d c o n s i d e r t h e v a l u e o f a f u n c t i o n / w i t h i n t w o g r i d c e l l s : [ . x ' _ i , x o ] ; [ x o i ^ ' i ] . Transfer from grid to particles W h e n w e c o m p u t e / o n c e r t a i n p o s i t i o n . 1 ; b e t w e e n xo a n d x\, t h e i n t e r p o l a t e d v a l u e / ( n ; ) c o u l d b e a p p r o x i m a t e d b y T a y l o r e x p a n s i o n : / O o ) = f(x) + ( x 0 - x ) f ' ( x ) + { x o ~ x ) 2 f " ( X ) ( 3 . 1 ) / ( ' f i ) = f(x) + (xl-x)f'(x)+{Xl~x)2r(x) ( 3 . 2 ) / ( , ; ) = ( l - t ) / O o ) + * / O i ) ( 3 - 3 ) w i t h / . - " " " . I - - / . , , X i ' : ' ; ( 3 . 4 ) Xi - XQ ' X\ - XQ ."./>) = f ( x ) - ^ ( x 0 - x ) ( x 1 - x ) ( 3 . 5 ) Transfer from particles to grid W i t h o u t l o s s o f g e n e r a l i t y , w e a s s u m e x\ — XQ = x§ — %-\ = Ax. A n d w e a s s u m e t h a t t h e p a r t i c l e s a p p e a r w i t h u n i f o r m p r o b a b i l i t y o v e r e a c h s e c t i o n , w i t h i n t e r p o l a t i o n e r r o r f r o m 3 . 1 , t h e n t h e e x p e c t a t i o n o f n e w v a l u e o f / , f(x) t r a n s f e r r e d f r o m p a r t i c l e s ' v a l u e s b a c k t o g r i d i s . A - f + x n w(x)f(x) dx /(*o) = — 1 ^ ( 3 - 6 ) . / . x _ f + R C 0 W ( X ) C L X , X - X < X(j w(x) = { ( 3 . 7 ) X \ — X X > XQ f(xQ) = f(x0) + ^f(x0)Ax2 + O(Axi) ( 3 . 8 ) 2 9 S o i g n o r i n g a d v e c t i o n c a s e t h e e r r o r i n t r o d u c e d b y i n t e r p o l a t i n g t o p a r t i c l e s a n d t h e n a v e r a g e d b a c k t o g r i d i s 0(Ax2). 30 Chapter 4 Surface Reconstruction from Particles O u r s i m u l a t i o n s o u t p u t t h e p o s i t i o n s o f t h e p a r t i c l e s t h a t d e f i n e t h e l o c a t i o n o f t h e f l u i d . F o r h i g h q u a l i t y r e n d e r i n g w e n e e d t o r e c o n s t r u c t a s u r f a c e t h a t w r a p s a r o u n d t h e p a r t i c l e s . O f c o u r s e w e c a n g i v e u p o n d i r e c t r e c o n s t r u c t i o n , e . g . r u n n i n g a l e v e l s e t s i m u l a t i o n g u i d e d b y t h e p a r t i c l e s [ 4 4 ] . W h i l e t h i s i s a n e f f e c t i v e s o l u t i o n , w e b e l i e v e a f u l l y p a r t i c l e - b a s e d r e c o n s t r u c t i o n c a n h a v e s i g n i f i c a n t a d v a n t a g e s . N a t u r a l l y t h e first a p p r o a c h t h a t c o m e s t o m i n d i s b l o b b i e s [ 4 ] . F o r i r r e g u l a r l y s h a p e d b l o b s c o n t a i n i n g o n l y a f e w p a r t i c l e s , t h i s w o r k s b e a u t i f u l l y . U n f o r t u n a t e l y , i t s e e m s u n a b l e t o m a t c h a s u r f a c e s u c h a s a f l a t p l a n e , a c o n e , o r a l a r g e s p h e r e f r o m a l a r g e q u a n t i t y o f i r r e g u l a r l y s p a c e d p a r t i c l e s — a s w e m i g h t w e l l s e e i n a t l e a s t t h e i n i t i a l c o n d i t i o n s o f a s i m u l a t i o n . Bumps r e l a t i n g t o t h e p a r t i c l e d i s t r i b u t i o n a r e a l w a y s v i s i b l e . A s m a l l i m p r o v e m e n t t o t h i s w a s s u g g e s t e d i n [ 3 9 ] , w h e r e t h e c o n t r i b u t i o n f r o m a p a r t i c l e w a s d i v i d e d b y t h e S P H e s t i m a t e o f d e n s i t y . T h i s o v e r c o m e s s o m e s c a l i n g i s s u e s b u t d o e s n o t s i g n i f i c a n t l y r e d u c e t h e b u m p s o n w h a t s h o u l d b e flat s u r f a c e s . W e t h u s t a k e a d i f f e r e n t a p p r o a c h , g u i d e d b y t h e p r i n c i p l e t h a t w e s h o u l d 3 1 F i g u r e 4 . 1 : C o m p a r i s o n o f o u r i m p l i c i t f u n c t i o n a n d b l o b b i e s f o r m a t c h i n g a p e r f e c t c i r c l e d e f i n e d b y t h e p o i n t s i n s i d e . T h e b l o b b y i s t h e o u t e r c u r v e , o u r s i s t h e i n n e r c u r v e . e x a c t l y r e c o n s t r u c t t h e s i g n e d d i s t a n c e f i e l d o f a n i s o l a t e d p a r t i c l e : f o r a s i n g l e p a r t i c l e XQ w i t h r a d i u s ? t j , o u r i m p l i c i t f u n c t i o n m u s t b e : <p(x) = \x - .r 01 - r 0 ( 4 . 1 ) T o g e n e r a l i z e t h i s , w e u s e t h e s a m e f o r m u l a w i t h XQ r e p l a c e d b y a w e i g h t e d a v e r a g e o f t h e n e a r b y p a r t i c l e p o s i t i o n s a n d VQ r e p l a c e d a w e i g h t e d a v e r a g e o f t h e i r r a d i i : (j){x) = \x - x\ - f . ( 4 . 2 ) X = ^ ir,:r; ( 4 . 3 ) i r = Y \ „ , r . ^ (4.4) , , = ( 4 , , w h e r e k. i s a s u i t a b l e k e r n e l f u n c t i o n t h a t s m o o t h l y d r o p s t o z e r o — w e u s e d k(s) — m a x ( 0 , ( 1 — s2)A) s i n c e i t a v o i d s t h e n e e d f o r square r o o t s a n d i s r e a s o n a b l y w e l l -s h a p e d — a n d w h e r e R i s t h e r a d i u s o f t h e n e i g h b o r h o o d w e c o n s i d e r a r o u n d x. T y p i c a l l y w e c h o o s e R t o b e t w i c e t h e a v e r a g e p a r t i c l e s p a c i n g . A s l o n g a s t h e p a r t i c l e r a d i i a r e b o u n d e d a w a y f r o m z e r o ( s a y a t l e a s t 1 / 2 t h e p a r t i c l e s p a c i n g ) w e h a v e f o u n d t h i s f o r m u l a g i v e s e x c e l l e n t a g r e e m e n t w i t h f i a t o r s m o o t h s u r f a c e s . S e e figure 4 . 1 f o r a c o m p a r i s o n w i t h b l o b b i e s u s i n g t h e s a m e k e r n e l f u n c t i o n . 3 2 F i g u r e 4.2: A c o l u m n o f r e g u l a r l i q u i d i s r e l e a s e d . T h e m o s t s i g n i f i c a n t p r o b l e m w i t h t h i s d e f i n i t i o n i s a r t i f a c t s i n c o n c a v e r e -g i o n s : s p u r i o u s b l o b s o f s u r f a c e c a n a p p e a r , s i n c e x m a y e r r o n e o u s l y e n d u p o u t s i d e t h e s u r f a c e i n c o n c a v i t i e s . H o w e v e r , s i n c e t h e s e a r t i f a c t s a r e s i g n i f i c a n t l y s m a l l e r t h a n t h e p a r t i c l e r a d i i w e c a n e a s i l y r e m o v e t h e m w i t h o u t d e s t r o y i n g t r u e f e a t u r e s b y s a m p l i n g 4>(x) o n a h i g h e r r e s o l u t i o n g r i d a n d t h e n d o i n g a s i m p l e s m o o t h i n g p a s s . A s e c o n d a r y p r o b l e m i s t h a t w e r e q u i r e t h e r a d i i t o b e a c c u r a t e e s t i m a t e s o f d i s t a n c e t o t h e s u r f a c e . T h i s i s n o n t r i v i a l a f t e r t h e f i r s t f r a m e ; i n t h e a b s e n c e o f a f a s t m e t h o d o f c o m p u t i n g t h e s e t o t h e d e s i r e d p r e c i s i o n , w e c u r r e n t l y fix a l l t h e p a r t i c l e r a d i i t o t h e c o n s t a n t a v e r a g e p a r t i c l e s p a c i n g a n d s i m p l y a d j u s t o u r i n i t i a l p o s i t i o n s s o t h a t t h e s u r f a c e p a r t i c l e s a r e e x a c t l y t h i s d i s t a n c e f r o m t h e s u r f a c e . A s m a l l a m o u n t o f a d d i t i o n a l g r i d s m o o t h i n g , r e s t r i c t e d t o d e c r e a s i n g <p t o a v o i d d e s t r o y i n g f e a t u r e s , r e d u c e s b u m p a r t i f a c t s a t l a t e r f r a m e s . O n t h e o t h e r h a n d , w e d o e n j o y s i g n i f i c a n t a d v a n t a g e s o v e r r e c o n s t r u c t i o n 33 m e t h o d s t h a t a r e t i e d t o l e v e l s e t s i m u l a t i o n s . T h e c o s t p e r f r a m e i s q u i t e l o w — e v e n i n o u r u n o p t i r n i z e d v e r s i o n w h i c h c a l c u l a t e s a n d w r i t e s o u t a f u l l 2 5 0 3 g r i d , w e a v e r a g e 4 0 - 5 0 s e c o n d s a f r a m e o n a 2 G H z G 5 , w i t h t h e b u l k o f t h e t i m e s p e n t o n I / O . M o r e o v e r , e v e r y f r a m e i s i n d e p e n d e n t , s o t h i s i s e a s i l y f a r m e d o u t . t o m u l t i p l e C P U ' s a n d m a c h i n e s r u n n i n g i n p a r a l l e l . I f w e c a n e l i m i n a t e t h e n e e d f o r g r i d - b a s e d s m o o t h i n g i n t h e f u t u r e , p e r h a p s a d a p t i n g a n M L S a p p r o a c h s u c h a s i n S h e n e t a l . [ 4 8 ] , w e c o u l d d o t h e s u r f a c e r e c o n s t r u c t i o n o n t h e fly d u r i n g r e n d e r i n g . A p a r t f r o m s p e e d , t h e b i g g e s t a d v a n t a g e t h i s w o u l d b r i n g w o u l d b e a c c u r a t e m o t i o n b l u r f o r fluids. T h e c u r r e n t t e c h n i q u e f o r g e n e r a t i n g i n t e r m e d i a t e s u r f a c e s b e t w e e n f r a m e s ( f o r a M o n t e C a r l o m o t i o n b l u r s o l u t i o n ) i s t o s i m p l y i n t e r p o l a t e b e t w e e n l e v e l s e t g r i d v a l u e s [ 1 3 ] . H o w e v e r , t h i s a p p r o a c h d e s t r o y s s m a l l f e a t u r e s t h a t m o v e f u r t h e r t h a n t h e i r w i d t h i n o n e f r a m e : t h e i n t e r p o l a t e d v a l u e s m a y a l l b e p o s i t i v e . U n f o r t u n a t e l y i t ' s e x a c t l y t h e s e s m a l l a n d f a s t - m o v i n g f e a t u r e s t h a t m o s t d e m a n d m o t i o n b l u r . W i t h p a r t i c l e - b a s e d s u r f a c e r e c o n s t r u c t i o n , t h e p o s i t i o n s o f t h e p a r t i c l e s c a n b e i n t e r p o l a t e d i n s t e a d , s o t h a t f e a t u r e s a r e p r e s e r v e d a t i n t e r m e d i a t e t i m e s . 3 5 Chapter 5 Results W e u s e d p b r t [ 4 3 ] f o r r e n d e r i n g . F o r t h e m a t t e s a n d s h a d i n g , w e b l e n d e d t o g e t h e r a v o l u m e t r i c t e x t u r e a d v e c t e d a r o u n d b y t h e s i m u l a t i o n p a r t i c l e s , s i m i l a r t o t h e a p p r o a c h o f L a m o r l e t t e [ 3 0 ] f o r f i r e b a l l s . T h e b u n n y e x a m p l e i n f i g u r e s 5 . 1 a n d 2 . 2 w e r e s i m u l a t e d w i t h 2 6 9 , 3 2 2 p a r -t i c l e s o n a 100'3 g r i d , t a k i n g a p p r o x i m a t e l y 6 s e c o n d s p e r f r a m e o n a 2 G h z G5 w o r k s t a t i o n . W e b e l i e v e o p t i m i z i n g t h e p a r t i c l e t r a n s f e r c o d e a n d u s i n g B L A S r o u -t i n e s f o r t h e l i n e a r s o l v e w o u l d s u b s t a n t i a l l y i m p r o v e t h i s p e r f o r m a n c e . U n o p t i m i z e d s m o o t h i n g a n d t e x t I / O c a u s e t h e s u r f a c e r e c o n s t r u c t i o n o n a 2 5 0 3 g r i d t o t a k e 4 0 - 5 0 s e c o n d s p e r f r a m e . T h e c o l u m n t e s t i n f i g u r e s 4 . 3 a n d 4 w a s s i m u l a t e d w i t h 4 3 3 , 4 7 9 p a r t i c l e s o n a 1 0 0 x 6 0 x 6 0 g r i d , t a k i n g a p p r o x i m a t e l y 12 s e c o n d s p e r f r a m e . O u r c o s t i s e s s e n t i a l l y l i n e a r l y p r o p o r t i o n a l t o t h e n u m b e r o f p a r t i c l e s ( o r e q u i v a l e n t l y , o c c u p i e d g r i d c e l l s ) . 3 6 Figure 5.1: Low friction sand bunny. 37 Chapte r 6 Future Work and Conclusions We have presented a method for converting an existing fluid solver into one capable of plausibly animating granular materials such as sand. In addition, we implemented a new fluid solver that combines the strengths of both particles and grids, offering enhanced flexibility and efficiency. We developed a new idea for reconstructing implicit surfaces from particles. Looking toward the future, we plan to more ag-gressively exploit the optimizations available with P I C / F L I P (e.g. using multiple bounding grids), increase the accuracy of our boundary conditions, and implement motion blur of the reconstructed surface. 39 Bibliography [I] D. Adalsteinsson and J . Sethian. The fast construction of extension velocities in level set methods. J. Comput. Phys., 148:2-22, 1999. [2j S. G. Bardenhagen. J. U . Brackbill. and D. Sulsky. The material-point method for granular materials. Comput. Methods Appl. Mech. Engrg., 187:529-541, 2000. [3] Nathan Bell, Yizhou Yu, and Peter J. Mucha. Particle-based simulation of granular materials. In SCA '05: Proceedings of the 2005 ACM SIG-GRAPH/'Eurographics symposium on Computer animation, pages 77-86, New York, NY, USA, 2005. A C M Press. [4] J. Blinn. A generalization of algebraic surface drawing. ACM Trans. Graph., l(3):235-256, 1982. [5] .1. U . Brackbill and H. M . R.uppel. FLIP: a method for adaptively zoned, pa,rticle-in-cell calculuations of fluid flows in two dimensions. ./. Comp. Phys., 65:314-343, 1986. [6] R.. Bridson, R.. Feclkiw, and J . Anderson. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. (Proc. SIGGRAPH). 21:594-603, 2002. [7] Mark Carlson, Peter Mucha, R, Van Horn III, and Greg Turk. Melting and flowing. In Proc. ACM SIGGRAPH'/Eurographics Symp. Comp. Anim., pages 167-174, 2002. [8] Mark Carlson, Peter J. Mucha, and Greg Turk. Rigid fluid: animating the inter-play between rigid bodies and fluid. ACM Trans. Graph. (Proc. SIGGRAPH), 23:377-384, 2004. [9] Sebastien Dartevelle. Numerical and granulometric approaches to geophysical, granular flows. PhD thesis, Michigan Technological University, 2003. [10] M . Desbrun and M.-P. Cani. Smoothed particles: A new paradigm for animat-ing highly deformable bodies. In R. Boulic and G. Hegron, editors, Comput. 40 Anvni,. and Sim. '96 (Proc. of EG Workshop on Anim. and Sim,.), pages 61-76. Springer-Verlag, Aug 1996. Published under the name JVIarie-Paule Gascuel. [11] D. Enright, R. Fedkiw, .1. Ferziger, and I. Mitchell. A hybrid particle level set method for improved interface capturing. J. Com,p. Phys., 183:83-116, 2002. [12] Doug Enright, Due Nguyen, Frederic Gibou, and Ron Fedkiw. Using the particle level set method and a second order accurate pressure boundary condition for free surface flows. In Proc. J,.th ASME-.JSME Joint Fluids Eng. Conj., number FEDSM2003-45144. A S M E , 2003. [13] Douglas Enright, Stephen Marschner, and R.onald Fedkiw. Animation and rendering of complex water surfaces. ACM Trans. Graph. (Proc. SIGGRAPH). 21(3):736-744, 2002. [14] R,. Fedkiw, .1. Stam, and H. Jensen. Visual simulation of smoke. In ACM Trans. Graph. (Proc. SIGGRAPH), pages 15-22, 2001. [15] N . Foster and D. Metaxas. R.ealistic animation of liquids. Graph. Models and Image Processing, 58:471-483, 1996. [16] Nick Foster and R.onald Fedkiw. Practical animation of liquids. In ACM Trans. Graph. (Proc. SIGGRAPH), pages 23-30, 2001. [17] Olivier Genevaux, Arash Habibi, and Jean-Michel Dischler. Simulating fluid-solid interaction. In Graphics Interface, pages 31-38, 2003. [18] Tolga G. Goktekin, Adam W. Bargteil, and James F. O'Brien. A method for animating viscoelastic fluids. ACM Trans. Graph. (Proc. SIGGRAPH), 23:463-468, 2004. [19] I. Goldhirsch. Rapid granular flows. Annu. Rev. Fluid Mech., 35, 2003. [20] Eran Guendelman, Robert Bridson, and Ronald Fedkiw. Nonconvex rigid bod-ies with stacking. ACM Trans. Graph. (Proc. SIGGRAPH), 22(3):871-878, 2003. [21] VV. Malalasekra H. Versteeg. An Introduction to Computational Fluid Dynam-ics: The Finite Volume Method Approach. Prentice Hall, 1996. [22] F. Harlow and J. Welch. Numerical Calculation of Time-Dependent Viscous Incompressible Flow of Fluid with Free Surface. Phys. Fluids, 8:2182-2189, 1965. [23] F. H. Harlow. The particle-in-cell method for numerical solution of problems in fluid dynamics. In Experimental arithmetic, high-speed, computations and mathematics, 1963. 41 [24] H. J. Herrmann and S. Luding. Modeling granular media on the computer. Continuum Mech. Therm., 10:189-231, 1998. [25] .leong-Mo Hong and Chang-Hun Kim. Animation of bubbles in liquid. Comp. Graph. Forum (Eurographics Proc), 22(3):253-262, 2003. [26] G. Irving, J. Teran, and R. Fedkiw. Invertible finite elements for robust sim-ulation of large deformation. In Proc. ACM SIGGRAPH'/Eurographics Symp. Comp. Aram., pages 1.31-140, 2004. [27] H. M . Jaeger, S. R. Nagel, and R. P. Behringer. Granular solids, liquids, and gases. Rev. Mod. Phys., 68(4):1259-1273, 1996. [28] Kazuo Konagai and J. Johansson. Two dimensional Lagrangian particle finite-difference method for modeling large soil deformations. Structural Eng./Earthquake Eng., JSCE, 18(2):105s-110s, 2001. [29] D. B. Kothe and J. U . Brackbill. FLIP-INC: a particle-in-cell method for incompressible flows. Unpublished, manuscript, 1992. [30] Arnauld Lamorlette. Shrek effects—flames and dragon fireballs. SIGGRAPH Course Notes, Course 19, pages 55-66, 2001. [31] Xin L i and J. Michael Moshell. Modeling soil: Realtime dynamic models for soil slippage and manipulation. In ACM Trans. Graph. (Proc. SIGGRAPH), pages 361-368, 1993. [32] F. Losasso, F. Gibou, and R. Fedkiw. Simulating water and smoke with an octree data structure. ACM Trans. Graph. (Proc. SIGGRAPH), 23:457-462, 2004. [33] A. Luciani, A. Habibi, and E. Manzotti. A multi-scale physical model of gran-ular materials. In Graphics Interface, pages 136-146, 1995. [34] Victor J. Milenkovic. Position-based physics: simulating the motion of many highly interacting spheres and polyhedra. In ACM Trans. Graph. (Proc. SIG-GRAPH), pages 129-136, 1996. [35] Victor J. Milenkovic and Haralcl Schmidl. Optimization-based animation. In ACM Trans. Graph. (Proc. SIGGRAPH), pages 37-46, 2001. [36] G. Miller and A. Pearce. Globular dynamics: a connected particle system for animating viscous fluids. In Comput. & Graphics, volume 13, pages 305-309, 1989. [37] J. J. Monaghan. Smoothed particle hydrodynamics. Annu. Rev. Astron. As-trophys., 30:543-574, 1992. 42 [38] JVI. Miiller and M . Gross. Interactive virtual materials. In Graphics Interface, 2004. [39] Matthias Miiller, David Charypar, and Markus Gross. Particle-based fluid sim-ulation for interactive applications. In Proc. ACM SIGGRAPH/Eurographics Syrup. Comp. Ani.m., pages 154-159, 2003. [40] G. C. Nayak and O. C. Zienkiewicz. Elasto-plastic stress analysis. A generaliza-tion for various constitutive relations including strain softening. Int. J. Num. Meth. Eng., 5:113-135, 1972. [41] .1. O'Brien, A . Bargteil, and J. Hodgins. Graphical modeling of ductile fracture. ACM Trans. Graph. (Proc. SIGGRAPH), 21:291-294, 2002. [42] K. Onoue and T. Nishita. Virtual sandbox. In Pacific Graphics, pages 252-262, 2003. [43] Matt Pharr and Greg Humphreys. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann, 2004. [44] Simon Prernoze, Tolga Tasdizen, James Bigler, Aaron Lefohn, and Ross Whitaker. Particle-based simulation of fluids. In Com.p. Graph. Forum (Euro-graphics Proc.), volume 22, pages 401-410, 2003. [45] N . Rasmussen. D. Enright. D. Nguyen, S. Marino. N . Sumner, W. Geiger, S. Hoon. and R.. Fedkiw. Directible photorealistic liquids. In Proc. ACM SIG-GRAPH/Eurographics Symp. Comp. Amm., pages 193-202, 2004. [46] S. B. Savage and K . Hutter. The motion of a finite mass of granular material down a rough incline. J. Fluid Mech., 199:177-215, 1989. [47] D. G. Schaeffer. Instability in the evolution equations describing incompressible granular flow. Journal of Differential Equations, 66, 1987. [48] C. Shen, J. F. O'Brien, and J. R„ Shewchuk. Interpolating and approximating implicit surfaces from polygon soup.- ACM Trans. Graph. (Proc. SIGGRAPH), 23:896-904, 2004. [49] L .E . Silbert, D. Ertas, G. S. Grest. and et. al. Granular flow down an inclined plane: Bagnold scalling and rheology. Physical Review E, 64, 2001. [50] I. M . Smith and D. V . Griffiths. Programming the Finite Element Method. J. Wiley & Sons, 1998. [51] Jos Stam. Stable fluids. In ACM Trans. Graph. (Proc. SIGGRAPH), pages 121-128, 1999. 43 [52] Deborah Sulsky, Shi-.Iian Zhou, and Howard L. Schreyer. Application of particle-in-cell method to solid mechanics. Comp. Phys. Comm.. 87:236-252. 1995. [53] R. W. Sumner. J. F. O'Brien, and J. K. Hodgins. Animating sand, mud, and snow. In Graphics Interface, pages 125-132, 1998. [54] Mark Sussman. A second order coupled level set and volume-of-fluid method for computing growth and collapse of vapor bubbles. .7. Comp. Phys., 187:110-136, • 2003. [55] Tsunemi Takahashi, Hiroko Fujii. Atsushu Kunimatsu, Kazuhiro Hiwada, Takahiro Saito, Ken Tanaka, and Heihachi Ueki. Realistic animation of fluid with splash and foam.' Comp. Graph. Forum (Eurographics Proc.), 22(3) :391-400, 2003. [56] D. Terzopoulos and K. Fleischer. Modeling inelastic deformation: viscoelastic-ity, plasticity, fracture. ACM Trans. Graph. (Proc. SIGGRAPH), pages 269-278, 1988. [57] M . VV. Weber, D. K . Hoffman, and C. M . Hrenya. Discrete-particle simulation-sof cohesive granular flow using a square-well potential. Granular Matter, 6, 2004. [58] Hongkai Zhao. A fast sweeping method for Eikonal equations. Math. Com,p., 74:603-627, 2005. 44 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo 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-0051582/manifest

Comment

Related Items