Surface Reconstruction of SPH Fluids
I have received several emails from people asking about surface reconstruction of Smoothed Particle Hydrodynamics. This is, of course, the current challenge :).
Currently, I know of several techniques which have been successfully applied to render surfaces from SPH particles:
1) Point Set surfaces
This was applied to an SPH fluid in GPU Gems 3. You can find the article here:
The technique uses a ‘repulsion’ method to avoid rendering interior particles, and computes surface normals for the surface particles. They achieve 16,000 particles at 40 fps.
2) Screen Space curvature
This technique was developed by NVidia. They use a screen-space
technique which projects all the particles onto the screen with some
gaussian filter, then blend them on the screen. They achieve 60,000 particles at 20 fps. You can find a demo video of this on youtube.
3) Raycasting of Metaballs
This method casts rays out on the GPU to intersect the metaball surface. They achieve 10,000 particles at 5 fps.
4) Image-Space 3D Metaballs
This method creates a 3D texture which represents a metaball isosurface, then uses a screen-space shader to raycast into this surface. They achieve 60,000 particles at 10 fps.
There is a group on Gamedev which is exploring this technique, and provides some code for download:
5) Sphere Scan Conversion
This is my own technique. It achieves 16,000 at 80 fps, and is the only method listed here which can render shadows, but it is only for vertical streams and not a general method.
6) Perspective Grid Raycasting (*NEW*)
This recent (2010) technique uses a perspective grid textures on the GPU to achieve efficient raycasting. Results are 2,575,500 particles at 6.57 fps.
To give a better overall picture of current progress in SPH surface methods, I’ve normalized the performance measures here and listed them in order of performance. Note that the units are in milliseconds per 10,000 particles (computed as = 10^7/( #particles * fps ).
As far as I know, this list represents the current state-of-the art in particle surface reconstruction, as of May 2010. I will update it regularly as new methods appear.
Currently, an SPH physics simulation can run on the GPU in real-time with 60,000 particles at 57 fps (Zhang 2007), which is 3 ms per 10k particles. This means that research in surface reconstruction is lagging behind simulation performance.
Although there are several successful methods above, none of them has achieved the frame rates that would be needed for an interactive game. In my view, both simulation and rendering need to total around 6 ms per 10k particles (30,000 particles at 60 fps) in order to be feasible for a commerical game, leaving enough time for rendering the rest of the game world and logic. Not to mention, to be useful in a game the fluid should interact with other objects and the world. The current bottleneck is the surface rendering (not simulation), and even the best generic methods are presently only at 8 ms/10k. In addition, none of the generic techniques above render shadows, and I’ve found shadows to be an important visual aspect to fluids.
The most obvious technique, in a classical graphics sense, is 3D Marching Cubes, which must first generate an implicit metaball function, and then construct a marching cubes surface from this function while performing each step in real-time per frame. Current best methods for real-time Marching Cubes achieve around 10 fps for at 64^3 grid (Real-Time Isosurface Extraction, Tatarchuk). The ideal methods for SPH fluids are those which could avoid processing the interior particles of the fluid, and only render or polygonize the surface particles. This would allow surface reconstruction to scale in the future as O(n^2) rather than O(n^3). Although the Point Set surfaces method above achieves this during rendering, it must process all particles in order to determine the surface set.
Although this is currently an open research problem, based on the interest and effort going into it, I imagine this problem will be solved within the next 3 years. Its just a guess though.
Feel free to comment or ask questions below.