Sunday, December 4, 2011

Profiling the CPU fluid simulation

The suspended particle explosion simulation doesn't actually require a very high resolution fluid grid: while a higher resolution one will allow for slightly nicer detailed particle behaviour, much of the detail of the simulation is in the movement of the fuel/soot particles.

I had originally thought that the most critical thing to optimize would be the conjugate gradient solver in the projection step, since it may take many steps to converge, and each loop of it is doing a pretty decent exponent on the number of grid cells. I believe that part of the reason why projection isn't the most expensive step is a result of the high tolerance we use to make sure that the solver doesn't freak out, as previously mentioned.

Roughly profiling a CPU-based update step, the pieces of the update step rank in the following way:
- vorticity confinement
- velocity advection
- density advection
- temperature advection
- buoyancy
- projection
- update constant sources

There are three particle update steps that don't generally fit nicely in that list:
- particle position update
- heat transfer to particles
- burning particles

The particle position update is flatly O(N), but eventually the number of particles in the simulation can be a few orders of magnitude larger than the total number of grid cells used to simulate the fluid, and once that happens this update becomes more expensive than the advection steps (naturally). Perhaps the most surprising one is the vorticity confinement step: it is regularly an order of magnitude slower than the next slowest step, whether the total number of grid cells is in the 100s or 10,000s, and this can probably be attributed to the fact that it does 7 square root operations per grid cell, even though it is an O(N) function. It's difficult to improve on this operation on a CPU-based implementation.

Thankfully, we have a GPU, but let's save that post for later.

Tuesday, November 29, 2011

Testing testing 1,2,3...

Testing the publishing...

The new hotness

Decided to render a particle set inside the volumetric particle system.
Currently only the soot particles are being used in this render, with a single non-dynamic light.

Smoky backroom dealing

One of the dirty little secrets of our old smoke simulation is that in spite of being implemented in what was originally an incompressible fluid solver, the various pokes and prods that we do to the divergences and pressures can cause the simulation to break. As a result, it's necessary to set some starting parameters in the fluid grid so that the sudden injection of stuff from the explosion doesn't cause the solver to freak out.

One of the little problems of this is that after several months pass, it can be easy to forget just what all the little constant tweaks were in order to get particular explosions. Alas.

Here are some pictures of explosions that Steve Lovejoy and I simulated from the past project:

Saturday, November 19, 2011

So a funny thing happened on the way to the linker

A few days after getting flabbergasted by the nvutd.lib problem, I figured it out: the library files provided in that sample don't actually match with the library files provided in the other samples!

That and choosing to go with VS 2008 because of its more understandable handling of the custom build rules have helped get this up and running.

Hooray, that only took how many days to figure out? :(

Link to Hell

Compiling the sample code for this project has been quite a trip in solving linker errors. After a bunch of false starts, I've gotten it down to a bizarre link error with nvutd.lib:

1>nvutd.lib(nvutmedia.obj) : error LNK2001: unresolved external symbol "unsigned int (__stdcall* ATL::g_pfnGetThreadACP)(void)" (?g_pfnGetThreadACP@ATL@@3P6GIXZA)

Advice on this issue ranges from including certain header files in the precompiled header to recompiling the library file so that it links to something else entirely because that call it says is missing is missing because it's a deprecated function. Fun.

MSBuild hooray

MSBuild is a frazzling good/bad time.

When bringing an old project that contains a custom build rule into VS 2010, VS 2010 creates 3 files that ostensibly duplicate the functionality of the old .rules file. However, VS 2010 does not allow you to modify parts of the custom build step inside VS; you have to open up the files in a text editor, make the changes, close the project in VS, then re-open the project in VS and then inspect the command line and see if you did it right.

Some of the script variables also behave weirdly, likely a result of the importing process.

A Microsoft blog post that contains a lot of advice about this:

Here's a quote that made my day:
"One major change is that there is no more UI support in VS2010 to help you create custom build rule, although all your previous custom build rules from VS2005 and VS2008 can be converted to the VS2010 format. "
that sure sounds wonderful

Link to the Past

One of the problems with the codebase from the GPU Gems 3 smoke sample is that it's designed for an older version of Direct3D, an older version of Visual Studio, and an older version of the DirectX FX Compiler. What that translates to is a mess of path and link problems when trying to get it to compile.

Hopefully this won't take too long to resolve, although having to constantly pester people for an admin login to install SDKs is a bit of a nuisance.

Fancier GPU-powered dust

I like explosions.

The goal of my project is to combine an implementation of Animating Suspended Particle Explosions (Arikan, Feldman, O’Brien, 2003) with a GPU-accelerated fluid simulation, and the results of that into a GPU-accelerated volumetric renderer.

The implementation of the 2003 paper written by Arikan et al was previously implemented by myself and Steve Lovejoy in CIS 563. The method modifies incompressible semi-Lagrangian flow by allowing discrete quantities of simulated fuel to locally inject non-zero divergence into the fluid grid, with the evolution of the explosion visualized by particles representing these fuel quantities. Our simulation included one-way interaction with solid obstacles; i.e. the obstacles restrict the explosion, but the explosion does not push or otherwise cause physical effects on the obstacles.

However, our implementation was slow and kind of ugly: the fluid simulator ran at a single-digit framerate, and the fact that the elements of the fire and soot were represented by relatively small amounts of 2D particles greatly limited the visual quality of the results. The particles moved in nice explosion-y ways, but they didn't really capture the volumetric appearance of what they were supposed to represent.

GPU Gems 3 describes a shader-based implementation of incompressible Navier Stokes fluid, illustrated in a video from one of the authors:
I will be modifying their implementation to allow for tracking of particles in the fluid grid, and so that their solver handles injected divergence/temperature/velocity caused by the burning particles.

A second work that I will be drawing on to improve the rendering quality is Simon Green's Volumetric Particle Shadows:
This implementation allows for user-controlled real-time volumetric rendering of a set of particles. However, in order for it to be applied to the results of the fluid solver, it will have to be modified in a variety of ways: it needs to be able to handle input particle positions, the light source will have to be dynamically adjusted, a reversed accumulation method will need to be added for the burning particles, and a color mapping from the temperature needs to be implemented.

Monday, October 17, 2011

Pardon our dust will soon be replaced with much fancier, GPU-powered dust.