Computer graphics processing and selective visual display system – Computer graphics processing – Animation
Reexamination Certificate
1998-11-20
2001-07-24
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Animation
Reexamination Certificate
active
06266071
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer graphic animation, and more particularly to computer graphic simulation of fluid flow.
2. Related Art
One of the most intriguing problems in computer graphics is the simulation of fluid like behavior. Fluid mechanics is used as the standard mat hematical framework on which many existing simulations are based. There is a consensus among scientists that the Navier-Stokes equations are a very good model for fluid flow. Thousands of books and articles have been published in various areas on how to compute these equations numerically. Which solver to use depends largely on the problem at hand and on the computing power available. Most engineering tasks require that the simulation provide accurate bounds on the physical quantities involved, to answer questions such as “will the plane fly?” or “will the heat cause a fire?” The exact shape of the flow is of secondary importance. In computer graphics, on the other hand, attributes such as the shape and the behavior of the fluid are of primary interest, while physical accuracy is secondary or in some cases irrelevant. Fluid solvers, for computer graphics, should ideally provide a user with a tool that achieves fluid-like effects in real-time.
In fact, most previous fluid models in computer graphics are driven by visual appearance and not by physical accuracy. A good example is the cloud model of Gardner (Gardner, G. Y., “Visual Simulation of Clouds”,
ACM Computer Graphics
(
SIGGRAPH
'85) 19(3):297-384 (July 1985)). More generally, researchers in computer graphics have used solid textures to model various fluid-like phenomena. This type of research was pioneered by Perlin (Perlin, K., “An Image Synthesizer”,
ACM Computer Graphics
(
SIGGRAPH
'85) 19(3):287-296 (July 1985)) and later extended by Ebert and Parent to include motion (Ebert, D. S. and Parent, R. E., “Rendering and Animation of Gaseous Phenomena by Combining Fast Volume and Scanline A-buffer Techniques”,
ACM Computer Graphics
(
SIGGRAPH
'90) 24(4):357-366 (August 1990)). A very good exposition of this approach and a comprehensive account of related models is given in the book on solid texturing by Ebert, Musgrave and Peachy (Ebert, D., et al.,
Texturing and Modeling: A Procedural Approach
, AP Professional (1994)). Another approach to the modeling of fluids is the use of particle systems as initiated by Reeves (Reeves, W. T., “Particle Systems. A Technique for Modeling a Class of Fuzzy Objects”,
ACM Computer Graphics
(
SIGGRAPH
'83) 17(3):359-376 (July 1983)) and refined by Sims (Sims, K., “Particle Animation and Rendering Using Data Parallel Computation”,
ACM Computer Graphics
(
SIGGRAPH
'90) 24(4):405-413 (August 1990)). Using variants of these techniques, visual simulations have been designed for various phenomena such as smoke (Sakas, G., “Modeling and Animating Turbulent Gaseous Phenomena Using Spectral Synthesis”,
The Visual Computer
9:200-212 (1993); Stam, J. and Fiume, E., “Turbulent Wind Fields for Gaseous Phenomena”, in:
Proceedings of SIGGRAPH
'93, pages 369-376, Addison-Wesley Publishing Company (August 1993)), water (Chiba, N., et al., “Visual Simulation of Water Currents Using a Particle-based Behavioural Model”,
The Journal of Visualization and Computer Animation
6:155-171 (1995)) and fire (Chiba, N., et al., “Two-dimensional Visual Simulation of Flames, Smoke and the Sprad of Fire”,
The Journal of Visualization and Computer Animation
5:37-53 (1994); Stam, J. and Fiume, E., “Depicting Fire and Other Gaseous Phenomena Using Diffusion Processes”, in:
Proceedings of SIGGRAPH
'95, pages 129-136, Addison-Wesley Publishing Company (August 1995)). To obtain convincing fluid motions with these techniques usually requires considerable user expertise and trial and error. On the other hand, methods based on the Navier-Stokes equations should necessarily produce fluid-like results, since the underlying physics of fluids is properly modeled by these equations.
Until recently, it was believed that the full Navier-Stokes equations were too difficult to be solved in practice for computer graphical applications. However, Foster and Metaxas have shown that the full solution of the Navier-Stokes even on coarse grids can be used to create very nice simulations of gases and water (Foster, N. and Metaxas, D., “Modeling the Motion of a Hot, Turbulent Gas”, in:
Computer Graphics Proceedings, Annual Conference Series
1997, pages 181-188 (August 1997); Foster, N. and Metaxas, D., “Realistics Animation of Liquids”,
Graphical Models and Image Processing
58(5):471-483 (1996)). Before that, the Navier-Stokes equations had only been computed by supercomputers to animate two-dimensional fluids, such as Jupiter's atmosphere (Yaeger, L. and Upson, C., “Combining Physical and Visual Simulation. Creation of the Planet Jupiter for the film 2010
”, ACM Computer Graphics
(
SIGGRAPH '
86) 20(4):85-93 (August 1986)). Also, a linearized version of the Navier-Stokes equations was used by Kass and Miller to derive a stable solver (Kass, M. and Miller, G., “Rapid, Stable Fluid Dynamics for Computer Graphics”,
ACM Computer Graphics
(
SIGGRAPH
'90) 24(4):49-57 (August 1990)), but the linearization removes most of the fluid-like behavior, such as swirling and turbulence. Foster and Metaxas' work on the other hand clearly shows the advantages of using the full Navier-Stokes equations. Many effects which are hard to key frame manually such as swirling motion and flows past objects are obtained. Their algorithm is based mainly on the work of Harlow and Welch in computational fluid dynamics, which dates back to 1965 (Harlow, F. H. and Welch, J. E., “Numerical Calculation of Time-Dependent Viscous Incompressible Flow of Fluid with Free Surface”,
The Physics of Fluids
8:2182-2189 (December 1965)). Since then many other techniques have been developed which Foster and Metaxas could have used. However, their model has the advantage of being simple to code, since it is based on a straightforward finite differencing of the Navier-Stokes equations and an explicit time solver.
The main problem with their approach is that the numerical scheme can become unstable for large time-steps or very viscous fluids. Instability leads to numerical simulations that yield numerically unbounded results, and therefore have to be restarted with a smaller time-step. The instability of their algorithm sets serious limits on the interactivity of their model. Ideally, a user should be able to interact in real-time with a fluid solver without having to worry about possible instability. Hence there is a need for a method of simulating fluid-like behavior based on the Navier Stokes equations, where solution of the equations is stable.
SUMMARY OF THE INVENTION
The present invention is a method for performing computer graphic simulation of a fluid in motion. The method takes input data and calculates the velocity of the fluid at a plurality of points at successive time intervals. The velocity values are sent to an animator module which produces a geometrical description of the scene. This geometrical description is then sent to a renderer module, which calculates an image using the geometrical description. The animation is then displayed on an output device. In an embodiment of the invention, scalar quantities such as temperature and density are calculated as well and sent to the renderer module, where they are used in calculating the image.
The process of calculating velocity and scalar fields comprises solution of the Navier-Stokes equations, is easy to implement, and allows a user to interact in real-time with three-dimensional fluids on a graphics workstation. The invention achieves this by using time-steps much larger than the ones used by Foster and Metaxas. To obtain a stable solver for these equations, the invention radically departs from Foster and Metaxas' method of solution. Instead of their explicit Eulerian schemes, Lagrangi
Brinsmead Duncan
Stam Jos
Nguyen Phu K.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
Method of producing fluid-like animations using a rapid and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of producing fluid-like animations using a rapid and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of producing fluid-like animations using a rapid and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2537810