Project: Rendering a fountain - Vilhelm Hedberg

Simulating and rendering water

Background

Water simulation has been used in a lot of films over the years, where it has been practically impossible or to expensive to film using real water. Traditionally water has been simulated in the field of computational physics but but in recent years a number of techniques has been proposed to simulate water for special effects. The problem is that when simulating water for rendering, it is not only the movement of the water in a closed container that is interesting, but rather the interface (water surface) between the water and air, that is important to render realistically.

The Navier-Stokes equations are used to describe incompressible flow of a fluid.
The equations can be discretised and evaluated using a number of methods: those who are gridbased, particled based, or a combintation.
One well-known water simulation technique is called "Smooth particle hydrodynamics", or SPH.
When rendering the water, the particle or grid densities has to somehow be converted into a water volume. One way of doing it is do describe the surface through an implicit function, which is evolved through time. This is the main idea behind the Level set method.

Overview

My goal was to create a water simulation of a fountain, and to be able to use that data in the ray-tracer PBRT. The reason for not using any already available commercial or open source software was purely educational so that I could learn more about particle simulations.

Technical contribution

All code for the simulation is available here: Water_Simulation.zip, which includes both a makefile and an xcode-project
A c++ program was written to simulate a number of particles using the SPH-method, that is described in Water.
For flexibility, and debugging help, I added the possibility to visualize the simulation as it was running using OpenGL. I made this optional since of the flexibility to be able to run on simulation on the Amazon EC2 cloud computing service, that has more power than my macbook laptop.
Something that can be observed in particle based water simulation movies is that they often start with a splash. This has to do with the initial conditions set in the simulation. It is hard to initiate a body of water in a steady state using particles, so a "trick" which I used in the simulation was to initiate the particles in a regular pattern, and run the simulation but with the viscosity of the water set really high, causing very high damping. This will lead to the water stabilizing quickly to a fixed state, and from there a lower viscosity can be set.

The initial placement of the particles in this simulation looked something like this:

attachment:initialPlacement.png

When doing a simulation of Navier-Stokes equations, usually there is some kind of timestep restriction, to guarantee stability and convergence. The time-step restriction used in this simulation was based on the Courant–Friedrichs–Lewy condition which is shown below:
- $\delta t = min(0.25*min_a(\frac{h}{\bf{f_a}}), 0.4*\frac{h}{c_s*(1+0.6\alpha)})$ , more details in "Weakly compressible SPH for free surface flows"
After the fluid has damped out it will look something like this:

attachment:sim_screen.png

In the article about Water the technique used to simulate the water is described in more detail. But how to handle boundary conditions?
The approach I used was to treat the water particles colliding as an elastic collision, where the coefficient of restitution orthogonal to a plane or a cylinder was set to a low number (.3) and the coefficient parallell to the plane or cylinder to a relatively high number (0.9).
Thus particles colliding with a plane would bounce of it but still continue to move along it in the same direction.
For this implementation, only support for arbitrary planes was added. Plans existed to add support for arbitrary cylinders, but in the current version only a cylinder centered on the y-axis can be used as a boundary.

A picture of the simulation run after a short period of time after the viscosity has been lowered is shown below:

attachment:random.png

In the first version of the program I used brute force O(n^2) to search for a particles nearest neighbors, but this was obviously very very slow as soon as the number of particles increase.
To optimize this I implemented a basic version of a KD-tree.
The KD-tree performs a split on the median position of all the particles, thus half of the particles in a node will be in each child node. This is done alternating the x, y and z axis.
This speeds up the simulation significantly
Even with the KD-tree my simulation was relatively slow with a computation time of a couple of hundreds of seconds for each second of simulation when the number of particles exceeded 10000. Due to lack of time, no further optimizations were made, and the simulation was run on the Amazon EC2 computing service to speed up the time for a simulation.

Rendering

The rendering of the particle data was performed using a raytracing system called PBRT. The simulation wrote data files that was parsable by prbt and thus the data could be rendered.

The SPH algorithm can compute the density at any point in space using interpolation by nearby particles, which was exploited in the raytracer.
An adaptive raymarching algorithm was used to walk along the ray, until a threshold density level was crossed, then the ray direction was reversed and the step size halfed. This procedure was repeated until the stepsize was small and the density was close enough to the threshold density. The ray was then reflected and refracted accordning to Snell's law.
This is the final rendered result of the simulation:

attachment:final_46.png

Since the simulation wrote the particle data every n:th of a second, it was also possible to render a sequence of images and create a movie. The result is shown in this video: http://www.youtube.com/watch?v=A4FTCIe8sck

Project proposal

This project will be done for both this class and the class "Image synthesis" (CS348b), where the contribution in this class will be the simulation of the water, the contribution to CS348b will be the rendering of the water in a realistic way.
The goal of the project is to simulate and render a water fountain realistically. The goal is to render something in the style of this image: http://www.flickr.com/photos/jaybeespics/4356155745/. The movie "Bolt" (2008) contains a sequence of the fountains outside the Bellagio hotel in Las Vegas, which also serves as a source of inspiration for the project.
I will write about the use of water in feature films, and the different techniques that has been used throughout the years.
The project will also contain more of in-depth technical details of the technique used for the rendering of the fountain.
Since the water in a fountain is largely non-bounded, a particle based implementation is proposed.
Pbrt will be used to render the water through an implicit function.