Realistic Smoke Simulation Using A Frustum Aligned Grid by Alan Wai L u n Woo B . S c , U n i v e r s i t y of B r i t i s h C o l u m b i a , 2002 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T O F THE REQUIREMENTS FOR THEDEGREE OF MASTER OF SCIENCE in T H E F A C U L T Y O F G R A D U A T E STUDIES ( C o m p u t e r Science) The University of British Columbia A p r i l 2006 © A l a n W a i L u n W o o , 2006 Abstract Realistic s i m u l a t i o n of smoke is used i n the special effects i n d u s t r y to produce smoke i n b o t h feature films a n d video games. T r a d i t i o n a l simulations utilize u n i f o r m l y spaced rectangular c o m p u t a t i o n a l grids to perform the smoke s i m u l a t i o n . V a r i o u s changes h a d been proposed to improve different aspects of the s i m u l a t i o n , i n c l u d i n g level of details, m e m o r y usage a n d s i m u l a t i o n speed. I n this thesis, I propose a novel c o m p u t a t i o n a l grid that improves u p o n the level of details as well as m e m o r y usage. I propose a frustum aligned grid t h a t takes advantage of the viewi n g camera because details are most i m p o r t a n t i n the area close to the camera. A frustum aligned grid reduces the amount of g r i d points necessary to cover the whole d o m a i n b y placing a h i g h concentration of grid points near the camera while h a v i n g sparse grid points away from the camera. B y using a larger number of g r i d lines i n the direction parallel to the camera a n d fewer grid lines i n the direction perpendicular to the camera, h i g h level of details using a smaller amount of m e m o r y can be achieved. T h e g r i d is logically rectangular a n d a perspective transformation can m a p the g r i d into a spatially rectangular one. These properties enable the use of existing s i m u l a t i o n tools w i t h some modifications, thus m a i n t a i n i n g the level of speed. E x p e r i m e n t a l results a n d comparison w i t h a s t a n d a r d uniform grid demonstrate the p r a c t i c a l i t y a n d effectiveness of the proposed m e t h o d . n Contents Abstract ii Contents iii L i s t of Tables v L i s t of F i g u r e s vi Acknowledgements vii 1 Introduction 1 2 T r a d i t i o n a l Smoke S i m u l a t i o n 4 3 2.1 Governing Equations 4 2.2 The Grid 5 2.3 Simulation Loop 5 2.4 Advection 8 2.5 V o r t i c i t y Confinement 9 Frustum Aligned Grid Method 11 3.1 Frustum Aligned G r i d 11 3.2 Simulation Loop 14 iii 4 5 3.3 Divergence 14 3.4 Advection 19 3.5 Pressure solve 20 3.6 Vorticity 21 E x p e r i m e n t a l results 24 4.1 Source location 25 4.2 G r i d size 27 4.3 Vorticity 29 4.4 Comparison with traditional simulation 30 Conclusion 36 Bibliography Appendix A 37 L a p l a c i a n Coefficients 38 iv List of Tables 4.1 Parameters for s i m u l a t i o n 25 4.2 R u n time of sample simulations w i t h different grid sizes i n seconds per frame and file size of one frame of smoke d a t a i n kilobytes. . . . 4.3 e a n d M I N C U R L used i n figure 4.4 4.4 R u n time a n d m e m o r y usage comparison of frustum aligned g r i d m e t h o d and t r a d i t i o n a l m e t h o d 4.5 28 30 32 C o m p a r i s o n of s i m u l a t i o n time used i n subroutines between frustum aligned grid m e t h o d a n d t r a d i t i o n a l m e t h o d using a 64 b y 64 by 64 grid 32 4.6 G r i d spacing of varies grid sizes 32 4.7 Statistics for figure 4.6 33 v List of Figures 2.1 C o m p u t a t i o n a l d o m a i n a n d staggered g r i d alignment 5 3.1 F r u s t u m parameters 12 3.2 F r u s t u m aligned grid 13 3.3 A x i s configuration for 4.1 Images obtained from different smoke simulations. X? Y% jk 17 k T o p : a pulse, Second: two sources, T h i r d : m o v i n g source, B o t t o m : approaching source 4.2 26 Simulations w i t h different source locations. T o p : back half of frust u m , M i d d l e : m i d d l e of frustum, B o t t o m : front half of frustum. . . . 4.3 27 C o m p a r i s o n between frustum aligned g r i d a n d rectangular g r i d . T o p : g r i d spacing m a t c h back of frustum, B o t t o m : grid spacing m a t c h front of frustum 29 4.4 Simulations w i t h different e a n d M I N C U R L 31 4.5 C o m p a r i s o n of simulations w i t h different number of grid lines i n the C. direction 4.6 33 C o m p a r i s o n of t r a d i t i o n a l m e t h o d a n d frustum aligned grid m e t h o d . vi 34 Acknowledgements I ' d like to acknowledge m y very understanding supervisor R o b e r t B r i d s o n , for a l l his help a n d advice. ALAN WAI L U N WOO The University of British Columbia April 2006 vn Chapter 1 Introduction Smoke s i m u l a t i o n techniques have made various advancements i n recent years to a point where high-quality realistic smoke can be simulated i n reasonable time. T h e major breakthroughs come from the i n t r o d u c t i o n of the semi-lagrangian m e t h o d b y S t a m [8] a n d v o r t i c i t y confinement by F e d k i w et al[l]. Together, they form the basic backbone of s i m u l a t i o n methods that are u t i l i z e d today. T h e m e m o r y requirement is h i g h t r a d i t i o n a l l y and various techniques have been developed to address this p r o b l e m . Rasmussen [6] developed a technique to reduce the m e m o r y usage by using interpolated two dimensional flow fields instead of a full three dimensional one. T h e two dimensional flow fields are combined w i t h a t i l e d K o l m o g o r o v velocity field to produce large-scale phenomena such as nuclear explosions. T h i s m e t h o d is inherently l i m i t e d b y its interpolative nature, thus missi n g s m a l l scale details t h a t reside i n the physical space between the two dimensional flow fields. T h e octree d a t a structure i n t r o d u c e d b y Losasso [5] uses large g r i d cells i n area of low activities a n d smaller g r i d cells i n areas w i t h interesting flow, reduci n g the overall number of cells used to d i v i d e the c o m p u t a t i o n a l d o m a i n . However, the definition of interesting flow a n d c r i t e r i a for refinement are difficult to define 1 accurately to capture the required details. Recently, Selle [7] combined the vortex particle m e t h o d w i t h an E u l e r i a n g r i d to produce h i g h l y turbulent effects. T h e v o r t i c i t y form of the Navier-Stokes equations is solved to o b t a i n velocity for advection and v o r t i c i t y particles are used to conserve the v o r t i c i t y of the flow. A v o r t i c i t y conserving force is used to drive the g r i d v o r t i c i t y to m a t c h the particles. F e l d m a n [2] introduces fluid s i m u l a t i o n using u n s t r u c t u r e d tetrahedral grid a n d i n c o m b i n a t i o n w i t h regular hexahedral g r i d . T h i s m e t h o d allows for s i m u l a t i o n i n irregular domains that are difficult w i t h t r a d i t i o n a l grids. W e introduce a novel c o m p u t a t i o n a l grid that addresses the m e m o r y issue as well as level of details. A frustum aligned grid is used to take advantage of the v i e w i n g camera. U n l i k e octree, our g r i d has a defined area of interest, the front of the frustum, where we place h i g h concentration of s m a l l g r i d cells to capture the details. Progressively larger g r i d cells are placed towards the back of the frustum to reduce the number of cells necessary to d i v i d e the c o m p u t a t i o n a l d o m a i n . However, the structure of the grid does impose a d d i t i o n a l overheads i n the c o m p u t a t i o n , but they can be compromised b y c u t t i n g back the grid dimension perpendicular to the camera. Since the g r i d is aligned w i t h the camera, the dimensions parallel to the camera play a more v i t a l role i n m a i n t a i n i n g the level of details a n d c u t t i n g back the g r i d dimension perpendicular to the camera has m i n i m a l i m p a c t o n the q u a l i t y of the images. Divergence a n d gradient operators on the frustum aligned g r i d are developed based on the orthogonal decomposition theorems by H y m a n a n d Shashkov [4]C h a p t e r 2 w i l l define the t r a d i t i o n a l simulation m e t h o d , chapter 3 w i l l outline the details of the frustum aligned g r i d method, chapter 4 w i l l present some 2 e x p e r i m e n t a l results a n d chapter 5 w i l l conclude a n d discuss some future work. 3 Chapter 2 T r a d i t i o n a l Smoke S i m u l a t i o n Smoke simulations have been used to produce realistic looking smoke for m a n y years a n d they a l l generally follow the framework discussed i n this chapter. 2.1 Governing Equations Smoke is composed of t i n y soot particles suspended i n air, w h i c h behaves according to a set of governing equations k n o w n as the Navier-Stokes equations. VP fV-r) V + (V • V ) V + — = ^ — ^ + f P P t where p denotes density a n d r denotes viscous stress tensors. V i s c o s i t y a n d compressibility are negligible i n smoke and density can be assumed to be constant; therefore the equation can be simplified into the i n c o m pressible E u l e r equations t h a t conserve b o t h mass and m o m e n t u m . V + (V- V ) V + V P = / t V-v =o where V = (u, v, w) denotes the velocity, P denotes rescaled pressure a n d f denotes any external forces such as buoyancy. 4 F i g u r e 2.1: 2.2 C o m p u t a t i o n a l d o m a i n a n d staggered g r i d alignment. The Grid T r a d i t i o n a l simulations d i v i d e the c o m p u t a t i o n a l d o m a i n into equal v o l u m e cells. Velocity a n d pressure are arranged i n a staggered grid alignment or M A C g r i d [3] where velocities lie perpendicular to the faces of a cell a n d pressures lie at cell centers. See figure 2.1. T h i s arrangement ensures the correct q u a n t i t y w i l l be at the correct l o c a t i o n d u r i n g the c o m p u t a t i o n . Average velocity a n d divergence of velocity w i l l be collocated w i t h pressure, a n d gradient of pressure w i l l be collocated w i t h components of velocity. 2.3 Simulation Loop S i m u l a t i n g smoke requires solving the incompressible E u l e r equations for each frame of the s i m u l a t i o n . T h e t y p i c a l frame rate of an a n i m a t i o n is 24 frames per second. T o solve the E u l e r equations, a projection m e t h o d is used. T h e equations are broken 5 u p into parts a n d solved i n a few steps. V = V - {V • V)VAt 1 n V* = V + fAt 1 V P * = V • V* 2 T/ra+1 _ y* _ y p * T h e first step is to advect the velocity u s i n g the semi-lagrangian m e t h o d discussed i n the next section. B y i g n o r i n g the pressure t e r m , we can reduce the E u l e r equations into V* — V n - _ - + (V-V)V = / a n d rearrange to get V* = V n - (V • V ) V A i + fAt w h i c h can be broken u p into V = V - (V • V)VAt 1 n V* = V + fAt 1 A n intermediate velocity field V 1 added to i t . is found t h r o u g h advection a n d external forces are E x t e r n a l forces usually include buoyancy a n d v o r t i c i t y confinement, w h i c h w i l l be discussed i n section 2.5. B o u n d a r y conditions are t h e n applied to the velocity a n d pressure. Types of b o u n d a r y conditions include D i r i c h l e t , where values are specified, a n d N e u m a n n , where the n o r m a l derivative is specified. I n a smoke s i m u l a t i o n , t y p i c a l b o u n d a r y c o n d i t i o n used for pressure is | ^ = 0 for a l l boundaries a n d t y p i c a l b o u n d a r y conditions used for velocities are | ^ = 0 for open boundaries a n d velocity =• 0 for the g r o u n d . 6 A f t e r b o u n d a r y conditions are a p p l i e d , the correct pressure to force a divergence free velocity is c o m p u t e d . yn+l_y* + V P = At yn+1 _ y* T/n+1 + V 0 P A i = 0 V P A i = V* + B y t a k i n g the divergence of the e q u a t i o n V .V + V P A i = V • V* n+1 a n d using the fact that V 2 should be divergence free, n+1 =0 V •V n+1 we can derive the P o i s s o n equation required to solve for the pressure. V P A t = V • V* 2 A t i m e scaled pressure P * = P A t is u s u a l l y used to simplify the c o m p u t a t i o n . T h e divergence of a cell can be c o m p u t e d as / 1 dx \ d_ dy \ / U \ V dz J = Ui+ljk - Uijk + Vij ik — Vijk + Wijk+l - Wijk + a n d the L a p l a c i a n of pressure can be c o m p u t e d as V P * = 6POA. R. ijk - fi—ljk 2 Pi fij—lk Pi+ljk -fij+lk Pi ik. — 1 fijk—1 Pi.'. ^ijk+l T h e pressure is then defined by _ V • V*j + Pi-ijk "ijk — k + Pi+ljk + Pij-lk 7. 7 + Pij+lk + Pijk-l + Pijk+1 T h e Poisson equation can be solved using methods such as Gauss-Seidel relaxation, m u l t i g r i d or conjugate gradient. T h e final step i n the s i m u l a t i o n is to update the velocity b y s u b t r a c t i n g the pressure gradient. yn+l 2.4 = y* _ V P A i Advection A d v e c t i o n of quantities such as velocity a n d smoke density are carried out using the semi-lagrangian m e t h o d introduced b y S t a m . Semi-lagrangian m e t h o d is a blend between E u l e r i a n methods, w h i c h keep track of quantities at fixed g r i d points, a n d L a g r a n g i a n methods, w h i c h keep track of the location of the quantities over time. T h i s m e t h o d aims to eliminate the i n s t a b i l i t y a n d time step restriction i n the comp u t a t i o n . I n explicit E u l e r i a n methods, the t i m e step is restricted b y the spacing of the g r i d nodes. L a g r a n g i a n methods have no time step restriction b u t the lack of a regularly sampled g r i d poses other challenges. B y using fixed g r i d nodes as i n E u l e r i a n methods a n d t r a c i n g the quantity b a c k w a r d similar to L a g r a n g i a n methods, the semi-lagrangian m e t h o d is able t o combine the best of b o t h classes of methods into a stable a n d efficient package. Some disadvantages of the m e t h o d include numerical dissipation from interpolation a n d failure t o conserve mass a n d energy. T o advect a quantity, the velocity field at the specific l o c a t i o n has to be c o m p u t e d . Since smoke densities are located at the cell centers, averaged cell center velocities need to be derived. \ ( "i.jfc+»i+1.7fc 2 Vi ijk 2 Wj.7fc+ i.7fc+1 W \ This velocity is used to trace back to where the quantity is coming from. X* = X{jk — VijkAt Interpolation of the eight neighboring values is used to update the current value of the quantity. Trilinear or cubic spline interpolations are normally used but any higher degree interpolation can be used to increase the accuracy of the simulation. Advection of velocities is performed in a similar fashion with averaged velocity field defined at the appropriate cell faces. For example, the velocity field at the location of L 7 i + l j f c is defined as ^ i 2 Ui+ljk / ^ .. Ui+ljk \ Viik+ i-i+lk+Vi+ljk+Vj+lj+lk v = 4 'U>iik+1>>iik+\+'U>i+\ik+'U>i+lik+l V 2.5 w i + h k + \ 4 j Vorticity Confinement Vorticity confinement is introduced by Fedkiw et al. in 2000 to attack the problem of small scale details. Since the computation involves a fair amount of averaging or interpolating of quantities, small scale details are lost in the numerical dissipation. Vorticity confinement is an effort to reintroduce the lost details by applying a confinement force to areas of high vorticity. The force is proportional to the grid spacing and disappears as the spacing decreases due to increased grid size. This property is consistent with the Euler equations. Thefirststep is to compute the vorticity of each cell using cell center velocity averaged from the faces. ^ Uijk V%jk Vijk \ W ijk J / LO ^ij+lk— ij-lk W —Vjjk+1 +Vj jk-1 2 Uj j k+1 — Ujj k -1 ~ W j +1 j k + i 2 W = S/ XV = V \ -1 j k Vi+ljk—Vj-ljk — Uij + lk+Uij-lk 2 J T h e n v o r t i c i t y l o c a t i o n vectors that point toward higher v o r t i c i t y concentration are computed. VH n = IVIwI F i n a l l y , a confinement force is c o m p u t e d as / = eh(Q x u) where h is the g r i d spacing. T h e force is then a p p l i e d to the velocities. ( \ ,fV 2 \ w 2 fV + = At V ijk j fjjk+fi-l.jk fjjk+fjjk-1 2 T h e parameter e controls the amount of confinement force a n d i t can have significant influence o n the resulting smoke appearance. A s e increases the amount of a c t i v i t y i n the smoke increases a n d the smoke appears to be more alive. B u t i f e is set t o o high, it w i l l dominate the other quantities a n d causes the smoke to appear unrealistic or even uncharacteristic. 10 Chapter 3 Frustum Aligned Grid Method L i k e v o r t i c i t y confinement discussed i n the last chapter, m a n y other methods exist that t r y to improve the realism or efficiency of a smoke s i m u l a t i o n . E x a m p l e s of such methods include the vortex particle m e t h o d , octree d a t a structure a n d u n s t r u c t u r e d grids, a m o n g others. T h e F r u s t u m A l i g n e d G r i d m e t h o d is a m e t h o d that takes advantage of the v i e w i n g camera and tries to improve on b o t h realism and efficiency. 3.1 Frustum Aligned Grid Since the v i e w i n g camera can o n l y see so m u c h at a p a r t i c u l a r instance, we can concentrate our s i m u l a t i o n w i t h i n the area of interest: the frustum. T h e frustum can be described using four parameters: field of view, aspect ratio, near c l i p p i n g plane a n d far c l i p p i n g plane. F i e l d of view defines the angle to the left and right of vertical t h a t the camera is capable of c a p t u r i n g . T y p i c a l cameras have a field of view of 30 degrees or less. A s p e c t ratio defines the ratio of w i d t h to height. C o m m o n aspect ratios are 4:3 for television a n d 16:9 for widescreen display. N e a r a n d far c l i p p i n g planes defines the closest a n d farthest distance the camera could 11 Nearplnne Field of View F i g u r e 3.1: F r u s t u m parameters see. See figure 3.1. In computer graphics, a perspective transformation is used to transform a frustum into a rectangular d o m a i n . Generally, the rectangular d o m a i n w i l l have dimension of -1 to 1 i n a l l directions. T h e perspective transformation can be defined as t a n fov perspective 0 —aspect t a n fov 0 0 0 0 — V 0 0 0 0 — (farplane+nearplane) farplane—nearplane 2(farplane)(nearplane) farplane—nearplane a n d its inverse can be defined as - l — t a n fov 0 0 0 0 — t a n fov aspect 0 0 0 0 0 0 0 perspective farplane—nearplane 2(farplane){nearplane) — (farplane+nearplane) 2(f arplane)(nearplane) / These two matrices are used to convert position between g r i d space a n d real space. A s i n t r a d i t i o n a l simulations, the c o m p u t a t i o n a l d o m a i n is d i v i d e d into cells. 12 F i g u r e 3.2: F r u s t u m aligned grid We d i v i d e the d o m a i n using g r i d lines t h a t w i l l transform to equally spaced grid lines i n the rectangular g r i d space. T h e g r i d spacing i n a l l directions w i l l increase g r a d u a l l y from the front to the back of the d o m a i n . T h i s produces cells w i t h smaller volume near the camera a n d cells w i t h larger volume away from the camera. T h i s also produces denser g r i d nodes near the camera and sparser g r i d nodes away from the camera. Velocities and pressure are s t i l l arranged i n a staggered grid alignment but velocities lay along the g r i d lines a n d pressure resides at the g r i d nodes. See figure 3.2. T h i s can be view as a shifted version of the standard M A C g r i d . If a cell is placed a r o u n d the node, the pressure w i l l lay i n the center a n d velocities at the faces. I n t r a d i t i o n a l m e t h o d , this shift w o u l d not cause any change i n the s i m u l a t i o n process. Since the grid lines are not orthogonal, velocities values are the projection of the real w o r l d values onto the directions of the grid lines. T h e axes for any g r i d nodes are £ = ( 1 , 0 , 0 ) , r\ — (0,1,0) a n d ( = (x,y,z), where x, y a n d z varies depending on the location of the g r i d node. T h e relationship between velocities and 13 real world values can be described as 1 0 0 v„ 0 1 0 \ x z j y and more usefully ( Vy 1 0 0 0 1 0 -x -y 1 since we will need these conversions when performing later computations. 3.2 Simulation Loop The structure of the simulation loop of the frustum aligned grid method is identical to traditional methods. Essentially, it is still solving the incompressible Euler equations using the projection method. But since the physical domain and the computational grid is different, computations such as advection, vorticity, divergence and pressure solve need to be redefined. The following sections describe each in detail. 3.3 Divergence Divergence is the rate of change of a control volume. In a frustum aligned grid, the control volume is the volume around a grid node and the flux is related to the velocities on the grid lines. The divergence operator using the frustum align grid is 14 defined as L\\ V •V = d_d_d_ dx dy dz -N- -N'^LV 1 L\2 Liz L21 L22 \ L31 L 3 2 L23 J L33 where TV is t h e volume of the node, T is the transpose a n d L is a 3 b y 3 m a t r i x that relates the formal a n d n a t u r a l inner p r o d u c t of velocities. T o compute L, we must first define the n a t u r a l a n d formal inner p r o d u c t of the d o m a i n . T h e first step i n d e r i v i n g the n a t u r a l inner product of two velocities X a n d Y is to convert t h e m into real w o r l d values X and Y r using t h e m a t r i x r defined i n t h e section 3.1. \ X,, and x„ v ( / y r \ 1 Y„ v -X (x)-X (y)+X XT. J u v \ v -Y (x)-Y (y)+Y u u V v w J V where £ = (x, y, z) is the u n i t vector of t h e direction of the grid line. W e c a n then take t h e inner p r o d u c t o f t h e two values to get Y u (X r • Y) r = ( X u X v ^ -Xu(x)-X (y)+X w v Y v -Y (x)-Y (y)+Y z u — ( l + f?) X Y U ^(X Y U V U + ^1 + XY + V U U W W w J -pX Y + V w w + X Y ) + -^{X Y + X Y ) + ^(X Y V v U V W + X Y) W V T h i s defines t h e n a t u r a l inner p r o d u c t at a specific g r i d node a n d axis alignment. T o compute t h e n a t u r a l inner p r o d u c t o f a cell, the n a t u r a l inner p r o d u c t o f t h e eight corners o f the cell are weighted b y the volume i t occupies a n d then s u m m e d . T h e n a t u r a l inner p r o d u c t of the d o m a i n is obtained b y s u m m i n g t h e n a t u r a l inner p r o d u c t o f a l l t h e cells i n the d o m a i n . 15 T h e formal inner p r o d u c t of the d o m a i n is defined as [X • Y ] = YJ Y1 YJ (X Y v U W U + XY U V w h i c h sums the inner p r o d u c t over the d o m a i n . + V XY) W W T h e formal a n d n a t u r a l inner p r o d u c t of the d o m a i n is related b y {X R • Y ) = [LX • Y ] R R R A p p l y i n g the m a t r i x L a n d e x p a n d i n g t h e equation, we get (( L\2 L13 L u [LX • r Y r ] = L21 L22 \ V L31 — T, E 'E (LiiX Y u v w u V V U W f \ X u L23 X L33 ) \X ) ) + L\2X Y u L23X Y + L,3\X Y W L32 \ U T 1 Yv v \ w + L\3X Y W \ Yu U J Yyj + L2\X Y U V + L22X Y + V V + L,32X Y + L33X Y ) V W W W T h e explicit formulas for L can be derived b y comparing the n a t u r a l a n d form a l inner p r o d u c t s . T o derive L u , we need to calculate the equivalent of T, T, T, LuX Y u v w i n terms of the n a t u r a l inner products. W e need to look at the eight axis configurations of n a t u r a l inner products that contain the same X Y U according t o their volume w i t h i n the cell. F o r X^ Y^ , k are 16 k U t e r m a n d weight t h e m the eight axis configurations u u (0, i . i i ! (O'jivQ} (0.1,0) (1.0,0) (1.0.0) (-1.0.0) (-1.0,0) ;(6Wi.;b.)--. !<». -1.0) (<i-#>oj (0.-1.0) Figure 3.3: Axis configuration for i c (1,0,0) (0,1,0) (1,0,0) (0,1,0) (1,0,0) (0,-1,0) (1,0,0) (0,-1,0) (-1,0,0) (0,1,0) (-1,0,0) (0,1,0) (-1,0,0) (0,-1,0) (-1,0,0) (0,-1,0) X^ Y^ . k k V Viji (Xiji Zij) x 2 Vol 1 ( Viji ij) z (%ij, Diji (—Xij, ( i+lj x (—Xi+lj, V o l —ytj, i Vi+lj — JJi+lj, (xi+ij,Vi+ij, (—Xi+lj,—Vi+lj, ^ + k ,2.) ~Zij) i z i+lj) —Zi+lj) Zi+ij) ™ * - l ™* u u 1 w , i+y) 1 w —Zi+lj) where Vol and VoZjJ. are the volumes of the front and back half of cells with index k k, respectively, and Volk is the volume of cells with index k. See figure 3.3. The rightmost column represents the volume weighted coefficient of the corresponding 17 n a t u r a l inner p r o d u c t . B y c o m b i n i n g t h e eight terms, we get the explicit formula for L \ \ . n ijk - L X L 2 Vol 2H I 2 + — ijfc A 2,i+ij ) W e c a n derive the other terms i n the m a t r i x L i n similar fashion. 'Voll + V ^ r J l ^ ^ p ( ^ y f c + ij-lk) + T yw _ o / -J--J.7 / ~ ^ \ V o l z 2 ( l-l Vol 21 ijk L ^V^IT X ^ ijk L + X fc-i 0 I Z$ ijk L X £31** Z X yu> k , - i i J k - l , [ i+ljk + i+lj-lk) X +l ( + J k z —Xj+ij V l k - i o ^VoZ f c X _L Y W _! , V ^ J Z'^ijy<7 ^ i j f c + i - l j f c J + z | (yu ' /" , yA a "\ , Xij+lVij+l V o ^ Voi I " y-k yw Volk^ijkJ \ ~ y i . 7 + i / • " " f c - i yw Vij+i I "'l l y u ^ J ^ - ^Vo/fc.i^-ij+lfc-l I : \^ijk -A-i-ljk) Vo/fcfc 2 y w k VoZ , y uX k ^i+ljfc + i+lj+lk) (^-^J (^F^t ( X ^ f c + Vol' _ i _ V {^ijk+l Vol k + "'t y i o Voi ^ii+lfe v f c ^i-ljfc+lj ( ij'fc+1 + ij-lk+l) X ij-\k) + V ^ t X X ^ Tjk = ^ Tjk L x x tj T o compute the divergence, the first step is t o compute the t e m p o r a r y values of LV. I temp ( \ u L , .temp l l U + temp L 1 2 V+ L l 3 \ W L \u + L22V + L23W y Lu + L32V + L33W 2 W 3i j T h e n t h e transpose of gradient is a p p l i e d a n d finally m u l t i p l i e d b y the inverse of the nodes volume. V-V = VNode L k AX, temp temp i-\jk Hjk -1 \ "\ ijk fc ~^'.7 / ^ ° ^ f e - i y i o 2. ^VoJfc-i^-ijfc-l 2. l + + VoZ° =2 2 yu> \ -r Vol ^ijk z ^ ijk - L 1 *. X ijk ' AX temp temp ij-lk ~ ijk V V A T T - AY k k temp ijk-\ W <^ temp • ijk A % _ i AZ ijk J AY a n d AZ are the g r i d spacing i n X , Y a n d Z respectively. T h e grid spacing i n the X a n d Y directions are constant w i t h i n the same k index while the grid spacing i n t h e Z direction varies. 18 3.4 Advection A d v e c t i o n is performed using the semi-lagrangian m e t h o d as before, b u t a few changes need to be made i n order to accommodate the frustum aligned g r i d . T o advect the smoke density at the g r i d nodes, the first step is to convert the g r i d l o c a t i o n into a physical location using the inverse of the perspective m a t r i x . T h e next step is to define a velocity field at the g r i d nodes b y averaging the velocities along the g r i d lines. Since the velocities are located i n the m i d p o i n t between grid nodes a n d the g r i d nodes are not equally spaced i n the £ direction, we need to do a weighted average instead. Ujjk+Uj-ljk \ 2 Vjjk+Vij-ik V^k V w ijk 2 j ™iik^Zijk-\+Wiik-\&Ziik &Ziik+&Zijk-\ . / T h e node velocity is then converted t o real w o r l d values and used to trace the smoke density b a c k w a r d . T h e calculated p h y s i c a l location is converted back into a g r i d location using the perspective m a t r i x . T r i l i n e a r interpolation is then carried out using the g r i d l o c a t i o n i n g r i d space. Special treatment is needed for the interpolation i n the £ direction because the perspective transformation is not affine i n that direct i o n . T h e g r i d location is used to locate w h i c h cell the smoke is from. T h e physical location of the cell's corners a n d the calculated physical location of the smoke i n the C. direction are used t o compute a weighting factor for the interpolation. T h e g r i d location is sufficient t o compute the weighting factor for interpolation i n the £ a n d rj directions. Higher degree interpolation schemes c a n be used to o b t a i n more accurate results. U n l i k e t r a d i t i o n a l methods where the velocities are advected i n d i v i d u a l l y , the averaged node velocity is advected instead. 19 T h e process is identical to advecting smoke described above. T h e advected node velocity is then averaged back to the g r i d lines using the usual m e t h o d . / Uiik+Uj+ljk \ 2 Uijk Vjjk+Vjj+lk 2 V ijk w 3.5 2 J Pressure solve T o solve for the pressure, we need t o solve the Poisson equation defined as VP =V• 2 V T h e divergence is defined i n section 3.3 a n d we still need t o define the L a p l a c i a n of the pressure. W e can rewrite the L a p l a c i a n as the divergence of the gradient a n d a p p l y the definition of divergence from above. Since the divergence operator is not as compact as o n a regular grid, the L a p l a c i a n operator involves 18 of the 26 neighboring g r i d nodes. V P = V • VP = - A T ^ L V P 2 20 E x p a n d i n g the equation we get L12 Lis Ln L21 L22 \ M J _ P L23 ^ V P , L33 J L32 L31 V W V P Z _ AL \7P +L 2VPy+L VP ) _^ 1 11 x 1 13 z i AX k k (.L VP +L22VPy+L 3VPz) _ 21 (LiiVPx+LizVPy+^iaVfz),^ _ k AX V V x 2 i:j {L lVP +L VPy+L VP ) _ lk 2 x 22 23 z i;jk AY k (L3lVP +L 2VP x 3 y + + (L X7P +L 2VPy+L33VP ) + L33VF2)..fc_1 31 x 3 z ijk AZ, ijk _ - \ {L11VP^j-xjk-jL^VP ) M J ( V x ^ (L VP ) _ -(L VP ) ijk 12 i ljk l2 y J 3 AX k , 7 _ (Li VPz)i-iik-(.L VP ) ijk AX k ( L2lVPx)i,-lfc-(^2lVPx)i fc (^lVPx)ijt-l y AX (£ lVP*)ijfc (I-22VP»)i. --lfc-(I-22VP»)ijfc 7 , 3 (^32VPy)ijfc-l _ , y VPyfc yp?.. ijk \ / (LssVPzhjk-l iik Pj+ijk-Pjjk _ (L VPz)i k-} 33 \ Pji + lk—Pjjk = V Pjjk + l—Pjjk AZ. ijk w h i c h defines the gradient of pressure along the g r i d lines, we can derive the coefficient of the g r i d node a n d its 18 neighbors. T h e derivation of the coefficients is i n c l u d e d i n the appendix. T h e pressure can then be solved using the standard Gauss-Seidel relaxation or conjugate gradient. 3.6 Vorticity T o increase the realism of the s i m u l a t i o n , a force similar to voriticity confinement is used. T h e idea is t o m a i n t a i n the level of c u r l w i t h i n the system, thus m a i n t a i n i n g 21 i:jk "I" F u r t h e r e x p a n d i n g the above equation b y replacing the pressure gradient w i t h / z (J-23 V P z ) i j - I f c ~(I<23 V P ^ i j f c , (L VP ) 32 13 f c j the s m a l l scale details that would have otherwise be d a m p e d out. T h e first step is to calculate the c u r l for each face of the cells. c u r l V XV ijk j ijk j ik A r e a 'i+\ik&Zi+\jk—Uiik+\&X -L-W j &Z jk+Uiik& k = X k+ c u r l i k i ijk Area y u 3 Tjk V i + \ j k & j curl Y k - U i i + \ k & X K - V i i k k & Y k + u Areaf i : j k & X K J T h e n i f the magnitude of the c u r l of any face is less then a predefined m i n i m u m , a force is applied to increase the c u r l of the face. T h e curl is always perpendicular to the face a n d the faces along the same g r i d lines lay o n the same plane. T h e two dimensional confinement force can be calculated for each plane using the normalized gradient of c u r l as a weighting t e r m . V x V% : k A Y weightij = k + A Y k + r l 1 k 9ht V w e i g n t l j k - l w wei e i g h t . . . z k ijk c u r l i i k + i - \ l -e(curl? )(weightl )AY /2 /y+ifc = e(curlf )(weight )AZ /2 Pijk = f? 3k = jk jk k+1 y jk ijk ij+lk -e(curl? )(weight )AY /2 z jk ijk k e{cuTl^ ){weight )AZ /2 y k ljk 22 u i i k - i &-Zijk+&Zij+\k = fijk+i c ijk V x V? : jk . w e i 9 h t i j k= H h+z wpinht-, weignt -- ^ .' , ljk wei9ht k lweight jkl fr+ijk = -e(curlV )(weigh% )AZ /2 f? = e(curl- ){weightl )AX /2 f»ijk = -e{curl\ ){weight )AZ /2 jk+1 fijk = jk jk jk i+ljk jk k+1 x jk ijk ijk e(curlv )(weightf )AX /2 jk jk k V x V* : k { weightij , -r. \ weightf jk I » w e i i • 9 t ij h V k , .. w — curl \ ..-curl T ik- Tj-ik k • curl™ / \ curl j+ J \ J weightnk wghtijk = \ ei W 9 h t : 3 k \ fi+ijk = e{curl% ){weight* )AY /2 k fij+ik = fijk f? = jk jk k -e(curlf ){weightl )AX /2 jk k k = e{curiy ){weight* )AYk/2 3k jk -e(curl? )(weightyAX /2 jk k Both e and the minimum curl can be used to control the amount of force applied and the activities within the smoke. They have similar effect as the e used in vorticity confinement where values too large can have negative overall effects. 23 Chapter 4 E x p e r i m e n t a l results T h e experimental simulations are implemented using V i s u a l C + + a n d O p e n G L . T h e y are r u n on a laptop w i t h 1.5Ghz P e n t i u m M processor and 5 1 2 M B of memory. T h e s i m u l a t i o n requires a few parameters i n c l u d i n g field of view, aspect ratio, near plane, far plane, number of g r i d lines i n the x, y, and z direction, number of iterations for the Gauss-Seidel pressure solver, number of seconds to simulate, buoyancy, e for vorticity, r for opacity a n d m i n i m u m c u r l . T y p i c a l values used i n experimental simulations are s u m m a r i z e d i n table 4.1. Pressure at boundaries are set to zero and N e u m a n n conditions are used for velocities. E x p e r i m e n t s are conducted to investigate the effects of various parameters have on the simulation, and a comparison w i t h t r a d i t i o n a l simulation is also carried out. A h y p o t h e t i c a l m u s h r o o m c l o u d where the smoke originate from a s m a l l opening i n the g r o u n d i n the center of the d o m a i n is used to perform the testing, but i n practice, there can be more t h a n one source a n d they can be located anywhere w i t h i n the d o m a i n . T h e images are rendered using a ray m a r c h i n g technique w h i c h s i m p l y accumulates the luminance along the £ d i r e c t i o n . T w o light sources are used to i l l u m i n a t e 24 Parameter fov aspect near plane far plane XMAX YMAX ZMAX iterations seconds buoyancy e T MINCURL Value 15° 1.0 5.0 10.0 128 128 64 10 20 5.0 2.0 0.1 5.0 Table 4.1: Parameters for simulation. the smoke, one from overhead a n d one from the left h a n d side. M o r e advanced techniques such as p h o t o n m a p p i n g can be used to create higher q u a l i t y images. F i g u r e 4.1 shows several sample images obtained from different styles of smoke. Some artifacts are visible due to aliasing from the g r i d . 4.1 Source location Since the configuration of the frustum aligned grid places emphasis more on the space at the front of the frustum t h a n the back, the location of the source s h o u l d be an i m p o r t a n t factor i n the appearance of the resultant smoke. F i g u r e 4.2 compares the simulations of three different source locations. These simulations use the t y p i c a l values found i n the beginning of the chapter except the value of e is set to zero. T h i s effectively turns v o r t i c i t y confinement off a n d allows the smoke to rise under buoyancy alone. T h e sizes of the source i n a l l s i m u l a t i o n are the same a n d they are i n the shape of a square. T h e first sequence is generated w i t h a source located 25 26 F i g u r e 4.2: Simulations w i t h different source locations. T o p : back half of frustum, M i d d l e : m i d d l e of frustum, B o t t o m : front half of frustum. at the back half of the frustum, the second sequence is generated w i t h a source located at the m i d d l e of the frustum a n d the last is generated w i t h a source located at the front half of the frustum. Since the size of the source is identical, as it moves further away from the camera, it w i l l appear smaller. T h e level of details w i l l also be lowered as less g r i d nodes are located at the back of the frustum, b u t coupled w i t h the reduction i n the apparent size, the resulting image still maintains a comparable level of details. 4.2 G r i d size T h e grid size is a c r u c i a l factor i n the smoke s i m u l a t i o n . T o increase the realism of a s i m u l a t i o n , the t r i v i a l s o l u t i o n is to increase the resolution of the grid since the smaller the g r i d spacing, the better the a b i l i t y to capture the details. T h e drawback 27 G r i d Size R u n Time(s/frame) F i l e Size(kb) 64 b y 64 b y 32 0.461 1.342 517 2057 64 by 64 by 64 2.874 4113 32 b y 32 by 32 128 b y 128 by 32 5.448 8209 128 b y 128 by 128 256 b y 256 by 32 20.920 41.309 32833 32801 T a b l e 4.2: R u n time of sample simulations w i t h different grid sizes i n seconds per frame a n d file size of one frame of smoke d a t a i n kilobytes. of such approach includes the increase i n s i m u l a t i o n time and m e m o r y requirement. T y p i c a l l y , the s i m u l a t i o n time varies d i r e c t l y w i t h the grid size; d o u b l i n g the grid dimension i n a l l directions transforms to eight times the original s i m u l a t i o n time. Table 4.2 lists the s i m u l a t i o n time for several sample g r i d sizes as well as the file size for one frame of smoke data. T h e frustum aligned g r i d m e t h o d is aimed to increase the realism while addressing the t i m e a n d m e m o r y issue. E a c h grid lines i n the direction perpendicular to the camera is projected into a single p o i n t at the front of the camera. The dimension parallel to the camera can be viewed as the resolution of the image where each p i x e l is a projected grid line. U s i n g this arrangement, a l l g r i d nodes are located at a relevant p o s i t i o n w i t h respect to the camera and no grid nodes are wasted or overlapping. I n t r a d i t i o n a l rectangular c o m p u t a t i o n a l grids, when rendering the resulting image, usually m a n y different g r i d nodes w i l l be m a p p e d to the same pixel, thus wasting the c o m p u t a t i o n a l time a n d m e m o r y space for these redundant values. T h e g r i d spacing i n a frustum aligned grid is not uniform. T h e spacing at the back of the frustum can be couple times larger than the ones at the front. Y e t , the details are not lost from the sparse spacing because the frustum aligned grid accounted for what could and couldn't be seen by the camera. T o cover the same 28 F i g u r e 4.3: C o m p a r i s o n between frustum aligned g r i d and rectangular grid. T o p : g r i d spacing m a t c h back of frustum, B o t t o m : grid spacing match front of frustum. volume occupied by the frustum using a t r a d i t i o n a l grid, considerably more g r i d nodes are needed since i n order to o b t a i n the same level of details, the g r i d spacing of the whole d o m a i n should m a t c h the g r i d spacing at the front and e x t r a g r i d nodes are needed outside the frustum to get a rectangular g r i d . See figure 4.3. T o cover the 64 b y 64 b y 64 grid of the frustum described by the parameters at the beginning of the chapter, a 128 by 128 b y 128 u n i f o r m g r i d w i l l be needed. T h e amount of e x t r a g r i d nodes required is m a i n l y depended u p o n the near and far c l i p p i n g planes of the frustum. 4.3 Vorticity T h e realism of the smoke s i m u l a t i o n is enhanced b y the i n t r o d u c t i o n of v o r t i c i t y force. T h e force is controlled using two parameters: e a n d M I N C U R L . T h e M I N C U R L controls the m i n i m u m c u r l desirable. 29 A n y face w i t h a c u r l smaller t h a n e MINCURL 1 2 3 4 1 2 5 5 5 5 10 10 T a b l e 4.3: e a n d M I N C U R L used i n figure 4.4 M I N C U R L w i l l have a force applied to it a n d that force is p r o p o r t i o n a l to the c u r l itself, e controls the amount of force that w i l l be applied. F i g u r e 4.4 shows several simulations w i t h different setting of e a n d M I N C U R L and table 4.3 lists the values used i n the simulations. T h e t y p i c a l values at the beginning of the chapter are used for the other parameters. T h e ideal value of e a n d M I N C U R L depends u p o n the scene a n d varies greatly. T r i a l and error may be required to determine the ideal value but i n most case, the ideal value is not required to produce a realistic and interesting s i m u l a t i o n . 4.4 Comparison with traditional simulation A similar i m p l e m e n t a t i o n to the frustum aligned g r i d m e t h o d of the t r a d i t i o n a l g r i d m e t h o d is used for the comparison. T a b l e 4.4 compares the r u n time a n d m e m o r y usage of the two methods for several different g r i d sizes a n d table 4.5 compares the s i m u l a t i o n time used i n the subroutines of the two methods. A s seen from the d a t a that the frustum aligned grid m e t h o d is on average half as fast as the t r a d i t i o n a l m e t h o d . T h e e x t r a c o m p u t a t i o n time is used m a i n l y i n the divergence a n d pressure solver as expected. T o b r i n g the frustum aligned m e t h o d on par w i t h the t r a d i t i o n a l m e t h o d i n t e r m of c o m p u t a t i o n time, we can 30 F i g u r e 4.4: Simulations w i t h different e a n d M I N C U R L . 31 Frustum G r i d Size Traditional Run Time 32 by 32 by 32 Memory Run Time 4124 0.260 0.982 0.461 1.342 64 by 64 by 32 64 b y 64 by 64 13812 2.874 128 b y 128 by 32 3972 12132 1.903 26500 52104 5.448 Memory 23456 46120 3.876 Table 4.4: R u n time a n d m e m o r y usage comparison of frustum aligned g r i d m e t h o d and traditional method. Subroutine Frustum Traditional 0.160 0.280 0.170 0.160 1.502 0.010 1.472 0.160 0.010 0.100 0.010 Initalization Advection Vorticity Divergence Pressure Solve Gradient 0.010 Table 4.5: C o m p a r i s o n of s i m u l a t i o n t i m e used i n subroutines between frustum aligned grid m e t h o d a n d t r a d i t i o n a l m e t h o d using a 64 by 64 by 64 g r i d . reduce the n u m b e r of g r i d lines i n the direction perpendicular to the camera b y a factor of two. Since the grid lines are concentrated at the front of the frustum a n d they are not equally spaced, decreasing the number of grid lines w i l l have a smaller effect on the s a m p l i n g at the front of the frustum where details are most i m p o r t a n t . T a b l e 4.6 shows the g r i d spacing of the first few grid lines of varies g r i d sizes a n d figure 4.5 compares the resulting images from the different simulations. T h e result indicates that the reduction of grid lines produces comparable Szi G r i d Size 128 b y 128 b y 32 128 by 128 b y 64 128 b y 128 by 128 0.0820 0.0400 0.0198 5Z2 0.0847 0.0406 0.0199 5zz 5z4 0.0875 0.0414 0.0201 0.0906 0.0419 0.0202 5z 5 0.0938 0.0427 0.0204 Table 4.6: G r i d spacing of varies grid sizes. 32 0.3125 0.1563 0.0781 F i g u r e 4.5: C o m p a r i s o n of simulations w i t h different number of grid lines i n the ( direction. Figure a b c d Method G r i d Spacing G r i d Size Simulation T i m e 0.0419 0.0425 0.0211 0.0211 128 b y 128 b y 128 64 by 64 by 64 14.221 Traditional Frustum Frustum Frustum 128 by 128 by 64 128 b y 128 b y 128 2.874 9.684 20.920 T a b l e 4.7: Statistics for figure 4.6. images that suffer slight detail lost and it also leads t o lower m e m o r y requirement. F i g u r e 4.6 compares the images obtained from t r a d i t i o n a l methods a n d frust u m aligned grid m e t h o d . T h r e e different c r i t e r i a are used for comparison i n c l u d i n g equal grid spacing, equal grid size and equal c o m p u t a t i o n time. Table 4.7 lists the statistics for the simulations. W i t h equal grid spacing at the front of the frustum, the t r a d i t i o n a l s i m u l a t i o n produces better result t h a n frustum aligned m e t h o d but the simulation t i m e a n d 33 F i g u r e 4.6: C o m p a r i s o n of t r a d i t i o n a l m e t h o d and frustum aligned grid method. 34 m e m o r y usage are b o t h five times more. Increasing the grid size by a factor of two i n the x a n d y direction produces comparable result. T h e m e m o r y usage is half of the traditional's a n d the s i m u l a t i o n time is about 30% less. W i t h equal grid size, the frustum aligned m e t h o d produces superior s i m u l a t i o n than t r a d i t i o n a l m e t h o d at a cost of increased s i m u l a t i o n time. These results confirm the performance of the frustum aligned grid m e t h o d i n terms of m e m o r y usage and level of details. 35 Chapter 5 Conclusion We presented a frustum aligned grid for realistic smoke simulation that benefits from knowledge of the viewing camera. The novel computation grid addressed the problem of memory usage and level of details by utilizing non uniform frustum aligned grid cells. Significantly less grid nodes are required to cover the computation domain, thus reducing the memory usage and computation time. The grid lines in the direction perpendicular to the camera can be reduced without suffering detail lost. The reduction further reduces the memory usage and they can translate to increased grid lines in other directions, thus increasing the level of details. Comparison with traditional simulation proved the validity and effectiveness of the method. The currently fixed frustum is a limitation and a topic for future work. The current configuration can realistically simulate a large scale phenomenon at a fixed viewpoint but afly-byscenario with a moving camera will require additional modification, possibly in the form of particles. 36 Bibliography [1] R . F e d k i w , J . S t a m , and H . W . Jensen. V i s u a l s i m u l a t i o n of smoke. I n Proc. of SIGGRAPH 2001, pages 15-22, 2001. [2] B . E . F e l d m a n , J . F . O B r i e n , and B . M . K l i n g n e r . A n i m a t i n g gases w i t h h y b r i d meshes. I n Proc. of SIGGRAPH 2005, 2005. [3] F . H a r l o w a n d J . W e l c h . N u m e r i c a l calculation of time-dependent viscous i n - compressible flow of fluid w i t h a free surface. I n The Physics of Fluids 8, pages 2182-2189, 1965. [4] J . M . H y m a n a n d M . Shashkov. T h e orthogonal decomposition theorems for m i m e t i c finite difference methods. SIAM Journal on Numberical Analysis, 36(3):788-818, 1999. [5] F . Losasso, F . G i b o u , and R . F e d k i w . S i m u l a t i n g water a n d smoke w i t h an octree d a t a structure. I n Proc. of SIGGRAPH 2004, pages ? ? - ? ? , 2004. [6] N . Rasmussen, D . N g u y e n , W . Geiger, a n d R . F e d k i w . Smoke s i m u l a t i o n for large scale phenomena. I n Proc. of SIGGRAPH 2003, pages 703-707, 2003. [7] A . Selle, N . Rasmussen, a n d R . F e d k i w . A vortex particle method for smoke, water a n d explosions. In Proc. of SIGGRAPH 2005, pages 910-914, 2005. [8] J . S t a m . Stable fluid. I n Proc. of SIGGRAPH 1999, pages 121-128, 1999. 37 Appendix A L a p l a c i a n Coefficients = (2( £ f e ^i2vpy_ ljfc +f + ^)(2 -^i2vpy- + AA- ")17 fe)( Pi? fc AX FC i r l-i Vol i A X f c A Y f c V y o / f c . ! "I" I 1 ( l-i , 1 f k-\ , Vol Vol Y£H\i i-yyi-^\p. x Voi A f c 2 2 _ ^ jn-lj-lfe ^ W ^ + l ^ i + l ^ p Vo^wZj+ijyj+ijN 38 p ^3V^Ll, 7 2 -^3V^- f c ( - X i - i j f c M - i V c - i j - i A / M - n p 2 AX AZ ^ k 2 / - i i - i - u " ' M ^~zrT7^Vol ijk Ax AZ _i k V % o ^ P ^ .. p 0 zf . ijk )\Vol +1 ( i-i Vol 1 fc-i i ' AX AZ \ - V o i ("^7r )(y 2fc_i ) - i + i i f c - i iik k ^i-lj'fe+l k 2_/Z*!±liW + p y 1 AX AZ k i i V o l f c - i J-n-ljfc-1 V ijk i V-oiS k , K w % - i i i . j - n p XJ — 1 zj — 1 ^AXkAYkWol^^ Vol >y l t 2 2 y ^ A r y ^ + fc 2 + A ^3VP-_ y2( -^23VP/, Ay l f c 2. + i J-H-lj+lfc t VoZ _i A z k ^22v/^._ -L vp*;. Vol° Vol V k < + Vol + Vol° Vol k ^ + fl±l)p ) ( 2 + ij ) ( 4 + ^ k + | t - i r f c f c A Y k l ^ I 7 n f-Vij-i 2 ijk -yii-^s 2 f c f c f c o l _i ) i j - l k - l ,Vol° , Avoi i iJ-l)!+l r f c r k _2 Ay AZ VoifcA^-fc^U+lfc / - V i j + i,Voll_ u^'t-nn 2 f c i 3 f c _ x v - i j r ^ - n vrffc-! ^ i j + i f c - i / -yij+i' ijk k-i\p V^T/Ayo/^iAZyfc.! " Ay Az f c V z .. , ^Ay AZi,- V Ay \( k ^l£T"A V o / AY AZ ^ k Vol AZ )^3-lk ^ k - i A Z i j t - i ,voi°. i J f c 39 ^ 2 j ^ AX / - Z i j w 2 A2 f c + 1 o p f c - i \ i / -Xjj x / V o ^ \ p I "IF A y / J-^i-lj i 3 fc A X ^ zl + V 0 fc+1 fc Vol AZ >^+W JWolk^AZijk..-, k ijk ,Voll "AJ t ( ^ ) ( v^) i+ljfc+l P iAZ + l j &Zijk-\ k &Zijk __2_ zm ( Y<=i )( v A y ^ ^ A V o l ^ A ^ . ! 2 {-yij\/ V o l < ) P 1 t l/o/fcA^-fc^U-lfc k-i\ p Ayifc.jAz^fc.^^Ai/oifc-i^y-ifc-i + Ay i Az f c + 1 : ( ^ )(vot'> ^z i 3 r-ynr 2 L P ^- V o ~ AY \~z^~)Wol . AZ '-ijk-. k k 1 l A Y A Y k . k + 1 1 A Z A Z AZijk-l i i j j k . 1 -V; i j k ^ . k Voll Vo£_i p r +P:(A^? . , ijk—1 1 1 ! + 1 AzT7^ H ijk P 40 P , Vol AZ l^3+^k 1 } k 1 p A2?..2? y' + 1 i &-Z<ijk 1 + 1 r + l k k k ) P ij+lk-l ijk
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Realistic smoke simulation using a frustum aligned...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Realistic smoke simulation using a frustum aligned grid Woo, Alan Wai Lun 2006
pdf
Page Metadata
Item Metadata
Title | Realistic smoke simulation using a frustum aligned grid |
Creator |
Woo, Alan Wai Lun |
Date Issued | 2006 |
Description | Realistic simulation of smoke is used in the special effects industry to produce smoke in both feature films and video games. Traditional simulations utilize uniformly spaced rectangular computational grids to perform the smoke simulation. Various changes had been proposed to improve different aspects of the simulation, including level of details, memory usage and simulation speed. In this thesis, I propose a novel computational grid that improves upon the level of details as well as memory usage. I propose a frustum aligned grid that takes advantage of the viewing camera because details are most important in the area close to the camera. A frustum aligned grid reduces the amount of grid points necessary to cover the whole domain by placing a high concentration of grid points near the camera while having sparse grid points away from the camera. By using a larger number of grid lines in the direction parallel to the camera and fewer grid lines in the direction perpendicular to the camera, high level of details using a smaller amount of memory can be achieved. The grid is logically rectangular and a perspective transformation can map the grid into a spatially rectangular one. These properties enable the use of existing simulation tools with some modifications, thus maintaining the level of speed. Experimental results and comparison with a standard uniform grid demonstrate the practicality and effectiveness of the proposed method. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-08 |
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.0051580 |
URI | http://hdl.handle.net/2429/17818 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2006-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2006-0348.pdf [ 3.58MB ]
- Metadata
- JSON: 831-1.0051580.json
- JSON-LD: 831-1.0051580-ld.json
- RDF/XML (Pretty): 831-1.0051580-rdf.xml
- RDF/JSON: 831-1.0051580-rdf.json
- Turtle: 831-1.0051580-turtle.txt
- N-Triples: 831-1.0051580-rdf-ntriples.txt
- Original Record: 831-1.0051580-source.json
- Full Text
- 831-1.0051580-fulltext.txt
- Citation
- 831-1.0051580.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}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051580/manifest