Sunday, May 18, 2014

Waterfloo and ramblings about fluid simulation

As it is usually the case, a strong resolution to update the blog regularly clashed with the dull reality and lost in shame. As did a plan to write and publish a game in six months.

Well, it's been only fourteen months since I announced that plan. I was doing various things during that time, but only recently I managed to finish something and it's not a game. It's another entertainment app / live wallpaper for Android - Waterfloo. The previous one, Magic Fluids, was actually quite successful (over million downloads of the free version, and a reasonable amount of purchases of the paid version too), so it seemed promising to further explore the visually pleasing side of fluid simulation.

As it happens, fluid simulation was a topic of my Masters thesis. Back when I knew nothing about fluids (I don't know much now, either), I stared in awe at the videos on Ron Fedkiw's academic webpage and decided I want to at least touch this subject. I was very glad to find out that fluid simulation is a favourite hobby-topic of my advisor. We decided that I'll be exploring simulating liquids using level-set techniques.

Fluid simulation is actually a beautiful subject, not only for it's visual attractiveness. The physical derivations are mostly analysis and they lead to partial differential equations. Then, when you try to solve them on a computer, it turns out that many other areas of mathematics are useful - mostly linear algebra (because usually the slowest part of the simulation is solving a big system of linear equations), but there are also approaches based on variational calculus or Fourier transform. Lots of math, especially if you want to understand it well! Coders usually have rather limited understanding of the math behind the problems they solve. It really bothers me and I am planning on teaching myself math on a deeper level. If something comes out of it, I'll probably write about it in the future.

Magic Fluids was actually a very simple Jos-Stam-like simulation, so not much learning was needed. My new app on the other hand uses more advanced techniques. A good starting point for learning them is Fluid Simulation for Computer Graphics. I actually haven't read the whole book, only the first few chapters covered most of what I needed. However, this isn't a book that you can simply hold next to the keyboard and write code. I doesn't hold your hand and you need to fill out lots of details by yourself. I had to read many research papers and look inside lots of source code to finally get something working. One problem is the lack of readable, complete, contained and approachable code samples. There are a few small and clean codes for 2D simulations, but none of them covers the level set method. Mostly they are implementations of particle methods, optionally with a generation of a level set function from the particles (note that when I say particles, I don't mean SPH, these are all Eulerian techniques).

You could argue that going from a particle-based liquid simulation to level set-based one shouldn't be that hard, but unfortunately there are lots of small things that are really difficult to get right - mostly boundary conditions. Unlike some other problems in graphics, where wrong boundary condition gives you incorrect behaviour visible only at the boundary, in fluid simulation anything can happen: liquid leaking through a solid wall and disappearing from the screen in the blink of an eye is just one (and common) example.

I have found only one complete level set simulation with source code: But I only found it after I already had most of the work done. :)

Eulerian liquid simulation is surprisingly hard to get right for one more reason. A simulation constitutes of a couple of procedures, running sequentially, each solving a different part of the differential equation (or doing something else, like redistancing, which AFAIR is still a PDE, but not the main one that governs the fluid motion). Unless you're a mathematician (and a very good one) or you've been working on the subject for years, you probably understand each of the algorithms on the intuitive level only (which sometimes is enough, but often it isn't).

The problem is, trying to isolate one of the algorithms and visualizing the effects is usually hopeless, because the results are meaningless to an untrained eye. Only when running eveything together, you can (more or less) tell if you got it right. But then again, isolating procedures one by one is usually necessary to pin down a bug. I blame myself for not taking time to write some additional code or more complex visualization tools that would allow to run an algorithm solving a single part of the equation and compare the results with data obtained elsewhere (e.g. math software). If you're about to take on doing fluid simulation, I strongly advise this.

Back to the matters at hand: somehow I managed to complete both my thesis and Waterfloo. It uses a pure level set simulation, without any particle-based enhancements (something to explore in the future). It looks pretty great with some simply rendering on top (rather ordinary 2D version of refraction). Entire simulation is done on CPU and all time-consuming (and easily parallelizable :)) procedures are multithreaded.

Besides pouring water, in Waterfloo you can put some paint (dye) into the water. Paint densities need to be simulated in a grid that is four times bigger in both directions than the velocity and level set function grid (so 16 times more cells), otherwise the paint is too blocky. The velocity field is linearly interpolated when advecting paint values.

While paint and velocities are advected in the simplest manner possible, level set function advection is more complex. Spatial interpolation is cubic and instead of simple Euler (semi-Lagrangian) time integration, second-order Runge-Kutta is used. As is turns out, both are really important to the quality of the simulation.

I also experimented with cubic interpolation while rendering the distance field in a shader, but full version that takes 16 samples was really slow on some devices. I know there is an optimization described in GPU Gems that allows to do it using just four samples, but I didn't do that. I did something else though that gave similar effect, but I think I'll write it up another time. Eventually, since the optimized version was still too slow on some devices, I decided to stick with linear interpolation. Full 16-tap cubic interpolation is used when taking screenshots from the simulation though, because speed isn't important then.

I thought about at least leaving cubic interpolation as an option (I have some speed/quality tradeoff options in the app after all), but I decided against it for the following reason: even when the GPU is a little underutilised and giving it some more work wouldn't lower the FPS, you may want to keep it that way to keep latency on as low level as possible. Even without adding cubic interpolation on top, I can already see with a naked eye an increase in latency in Waterfloo compared to Magic Fluids (which was rather light on GPU, unless a lot of big particles were on the screen). Responsiveness is critically important for this kind of apps - it may look great, but only when it feels great, it leaves a good impression.

Now for some links and screenshots:

I don't know what I'll be doing in months to come. Hopefully both apps will keep me independent while I'm figuring it out. :) I have some ideas for Magic Fluids 2 and I still really want to make and publish a game by myself, but I don't fool myself anymore that I could manage to do that in less than a year. My NIH syndrome will make sure of that!