Slashdot Mirror
Making Animated Fluids Look More Realistic
brunascle writes "Technology Review has an article about recent advances in animated fluid dynamics made by Mathieu Desbrun, a computer science professor at Caltech. 'He and his team are developing an entirely new approach to fluid motion, based on new mathematics called discrete differential geometry, that use equations designed specifically to be solved by computers rather than people.' Desbrun explains that the currently in-use equations for animating fluid dynamics were not developed with computers in mind, and were simply reworkings of older equations. He claims that his new equations use about the same amount of computer resources, but with much better results. The article includes a 5 minute (flash) video demonstrating various results using his equations, ending with 2 fascinating and vivid displays: the first of a snowglobe, and the second of a cloud of smoke filling a volume in the shape of a bunny."
If you ever want to see some cool simulations of water and other particles, there are some folks in the POVRay animation usenet newsgroup (on news.povray.org) that have been experimenting around with fluids over the past year. They are actually pretty neat animations that simulate fluids pretty well.
That's the Stanford Bunny.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
hmm... the video i was talking about is gone, replaced by the 2nd one under "Multimedia." sorry about that. the other 2 are still good though. the smoke is in the first one. too bad, though, the snowglobe was great.
Ron Fedkiw at Stanford also has a lot of very impressive demonstrations of liquids, smoke, fire, cloth, rigid bodies, elasticity, and fracturing. The videos are definitely worth checking out: http://graphics.stanford.edu/~fedkiw/ I especially like the water being poured into the glass. It's nearly photo realistic.
http://www.technologyreview.com/player/07/01/Smoki ngBunny/1.aspxr eteFluids/1.aspx
http://www.technologyreview.com/player/07/01/Disc
Seems to check referer, so reload once.
Hey! That's my sig you're smoking there!
The "breaking problems into smaller pieces" here is simply the spatial descritization. In this case, tets in 3D or triangles in 2D. They are partitioning the physical domain into a set of small regions, basically like finite elements or finite volume methods. The divergence free constraint and viscous terms still result in a global linear algebra problem to be solved at each time step. So, in this case, it doesn't really have anything to do with multi-core processors. It isn't any more (or less) amenable to parallel computation than most other methods.
No, it has nothing to do with the finite element/difference methods at all.
In fact, it's a fundamentally different approach from both of those methods. Finite element/difference means that you think of the problem as a continuous, smooth manifold. Then, you break the manifold into chunks (discretize) it, and you apply the "natural laws" like they would work on a smooth surface to the discretized approximation. The idea is that, the smaller the chunks, the errors becomes too small to notice.
However, in some cases the discretization process causes quantities (like total energy of the system) to not be conserved. The little errors add up to a lot. In fluid dynamics, non-conserved quantities cause solutions to the systems that just look wrong to the casual observer.
This team's approach is fundamentally different. Instead of discretizing a continuous problem involving a smooth manifold and continuous operators, they think of the problem as discrete to begin with and define operators on the discrete geometry. They don't say "apply the derivative to an approximation of a smooth surface", they say "apply this discrete derivative-like operator to this discrete surface". It turns out that if you define your discrete operators correctly, you can focus on conserving quantities (such as total system energy) that the normal approximation to the derivative won't.
It offers no speedup in computation time, and probably has no parallelization opportunities beyond those normally there in fluid dynamics. However, it *does* produce better-looking solutions as all of the conservation laws are met.
Very interesting research.
It is similar. They use what is referred to as a consistent or mimetic discretization where the discrete operators have some of the same properties as the continuous operators, i.e. div curl v = 0 in the continuous case becomes DIV CURL v = 0 where DIV and CURL are the discrete version of the divergence and curl (i.e. matrices). It makes it easier to get local conservation. In this case, they focus on conserving circulation which is an integral of the vorticity in the fluid.
Full water is a ways off since it requires a large area to be simulated (well, you can simulate puddles, but not anything you can swim through). However real smoke animates are on their way since you can easily confine smoke to a reasonably small area. Nvidia's smokebox demo was created to show off the 8800's processing power with realistic smoke rendering, and the results of that demo are already being integrated into games. Movies more information are on the creator's website:t _fluid.htmly pe=mov&pl=game
http://graphics.cs.uiuc.edu/svn/kcrane/web/projec
http://www.gametrailers.com/player.php?id=15381&t
What the CFD-literate Slashdotters will want to read is the actual paper (warning, pdf) that the article is based upon.
It's a neat method, but it's nothing revolutionary. The upshot is that their method tries to conserve vorticity (fluid spin) better than the other methods currently used for graphics, with the aim of getting rid of hacks that are now necessary to Make Things Look Good. The entire spin (no pun intended) in the article about "equations for computers, not for people" is journalistic sensationalism.
All told, it's a vorticity-based Finite Element Method, which is solved as a sparse linear system. Cool pictures, though.
"Evil company X is threatening to restrict our rights! Let's all get together to stop--OOOH! SHINEY!!!" -- AC
Bump mapping was invented in 1978 by James Blinn and has been available in non-realtime rendering ever since. By 1996 it was a reasonably common effect in realtime software renderers (as in, everybody who wanted to show off their coding skillz had to have bump mapping in their rendering engine). But it was not easy to do bump mapping with the first-generation consumer-level 3D accelerators like 3dfx voodoo so people basically forgot about it as they moved onto hardware accelerated graphics... Until pixel shaders reintroduced the programmable pixel pipeline.
Having a "discrete derivative-like operator" was just an example of what one might do along these lines.
They're not the only people to do this sort of research. I remember a (Los Alamos, I think) physics research team doing a similar thing with some of Einstein's equations. By taking a different approach, they got some of the conserved quantities to stay conserved in solutions.
Not all approximations to the derivative are created equal. In fact, for smooth functions, the finite difference method is a poor solution, as its error is going to be O(h^2), where h is the step size. So, if you discretize the problem with the traditional central differnce, set it up as a matrix problem and solve the matrix with *no error at all* (and there will be error, as you're doing numerics on a computer), your solution is going to have O(h^2) error.
On the other hand, if you approximate the derivative using sinc methods, the error is O(2^h). This means that your numerical solution is going to be a much better approximation to the true solution.
Moral of the story? Even though, in the limit as h -> 0, or as your discrete geometry approaches a continuous one, how you get there is going to make a huge difference in what your solution is going to be.
The research group's publications might shed a bit more light on how this works.
There are four sorts of people in the world: fools, lunatics, idiots and morons. - Umberto Eco, Foucaut's pendulum.
I bleed easily. And I tend to pee myself in court.
- None can love freedom heartily, but good men; the rest love not freedom, but license. -- John Milton
I've never understood why more attention isn't given to Lattice-Boltzmann methods of CFD. The algorithm is less costly, and as accurate as NS along with being highly parallelizable. PowerFLOW uses an integer based LBM, and has had great success. The conceptual problem seems to lie in centuries of continuous domain equations, which computers simply aren't designed to implement natively. People are too married to calculus.
Jos Stam's stable fluids (SIGGRAPH 99) was one instance of a technique that looked better but wasn't exactly more accurate (specifically, Stam presented an unconditionally stable solver based on the Hodge-Helmholtz decomposition principle. Great for graphics, horrible numerical dissipation). Desbrun et al are solving Euler's equations for inviscid flow. The new thing is that their formulation of the equation on a discrete setting (solving it on a simplicial mesh instead of on a continuous field) provably conserves vorticity exactly, without numerical dissipation. The paper is available on their Caltech page, just google for it.
In fact, just the opposite. The entertainment industry (e.g. animation/vfx) wants fluids that will obey a director rather than the laws of physics, while remaining as credible as possible.
I have read the SIGGRAPH course notes. They are indeed solving the Navier-Stokes equations. Because this is for the entertainment business, they want to retain as much visual detail as possible while keeping the time step as large as possible.
Previous approaches are based on techniques developed for astrophysics, meteorology and oceanography, where you don't care so much about the small-scale detail. To overcome this, previous approaches either modelled more viscous fluids, such as melting wax (see House of Wax for onex example) where there fine-scale detail dissipates quickly anyway, or went to some trouble to mimic the propagation of the detail. One common approach, for example, is to take the curl of the velocity field ("vorticity"), advect it, then add a bit back. Yeah, it looks pretty good.
The main advances of this approach are two-fold. One is that instead of using Lagrangian particles or an Eulerian grid, they're using a simplicial grid which matches exactly the geometry of the environment, which means that interactions with the environment are exact.
Secondly, and this is the key bit, rather than separate "a bit" of the vorticity, they treat it as a completely separate variable. The advantage is that the vorticity field, being the curl of a vector field, is inherently divergence-free. Previous techniques had to manually zero-out the divergence in a separate step, which was usually the expensive part.
OK, if you didn't understand that, think about what's happening physically. The fluids that you generally care about in visual effects/animation are incompressible at the scales that you care about. Think of a glass of water, for example. Water in a glass isn't really incompressible, but it is close enough because the "speed of sound" in water is huge, when you consider the size of a glass and the length of a single frame of film.
So the water is effectively incompressible, which means it has an effectively infinite spend of sound. That means that if you "push" it in one place, then for the water to conserve its volume/mass (volume is proportional to mass in an incompressible fluid, remember), displacement elsewhere will have to happen instantaneously. That means that in general, you can't just make decisions locally; there needs to be a step in the solver which propagates these pressure effects over the whole fluid in one step.
The advance of this new method is hard to explain, but it uses a formulation that avoids this error-prone step completely. It's not free, since it requires that you convert between vorticity and flux. And it's hard to see how you'd model some of the more difficult forces like surface tension. But it's pretty impressive nonetheless.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});