Compressing Fluid Subspaces

In July 2016, I presented a piece of my ongoing research on data compression for subspace fluid re-simulation at the Symposium for Computer Animation in Zürich, Switzerland (for which we won a best paper award!). In general, high-quality physics-based fluid simulation can be extremely time-consuming, so previous research had focused on techniques of speeding things up. One particular scenario of “re-simulation” can occur when an animator is trying to subtly adjust parameters (such as the viscosity or the vorticity of the fluid) in a given scene to achieve just the right look. There is nothing more frustrating then choosing a few parameters, waiting forever for the scene to be simulated and rendered, and then discovering that the result would be perfect if only the viscosity were just a *teensy* bit increased! Morally speaking, it seems that there should be some way to leverage the data from the existing simulation toward re-simulating with a slightly higher viscosity, but without it, you have no choice but to start from scratch again. This is where subspace re-simulation comes to the rescue!

The basic idea is to render one full scene up front (think of it as a down payment of time). It is typical to simulate the fluid velocity field on a regular grid with \( N \) voxels, so mathematically, each time-step can be identified with an abstract vector living in \( \mathbb{R}^{3N} \). From the scene, which we regard as a sequence of vectors in \( \mathbb{R}^{3N} \) using an idea from linear algebra called the singular value decomposition (SVD), we discover a set of singular vectors—at most one per time-step. If there are \( r \) of these singular vectors, then we can identify the span of this set with \( \mathbb{R}^r \), which is a low-dimensional subspace of \( \mathbb{R}^{3N} \); hence, the name. An analogy for this might be something like the motion of a human hand—if we discretize the hand into millions of voxels, then in principle, there are many degrees of freedom in which a computer simulation could choose from. However, we know that in practice, there is a much smaller range of movements that are interesting or even physically possible. Theoretically then, there is some smaller subspace in which we can perform our calculations without sacrificing any quality!

As it turns out, however, this technique has some serious hidden drawbacks, primarily related to RAM limitations of typical computers (at least in the year 2016). In particular, for a reasonably high-detailed grid, the subspace re-simulation can require upwards of 90 GB RAM to be able to run! (Most typical laptops will have 4-16 GB RAM as of writing). Although the aptly-named “Kraken” machine in my lab does indeed have the requisite 96 GB RAM, for most people, this is an immediate dealbreaker. Hence the need for a data compression technique.

In my paper, we use a type of lossy compression similar to the pre-2000 JPEG algorithm which is based on the Discrete Cosine Transform (DCT). The basic premise of these types of compressions is to re-express the data in terms of a different basis, ideally one in which the representation is sparse (meaning that many of the coefficients are zero or at least very close to zero). As a basic example, if you wanted to encode the vector of all 1s in \( \mathbb{R}^n \), if you stick to using the standard ordered basis, each basis vector has a coefficient of 1, so in order to reconstruct it, you have to specify \( n \) numbers. However, using the discrete cosine basis instead, the representation for the very same vector would have every coefficient other than the first one would be 0, meaning only 1 number must be specified for the reconstruction to achieve the very same vector!

It turned out that the results from the DCT-based compression were reasonably promising in terms of the compression ratio obtained; however, the extra overhead required from decompressing and reconstructing the data initially proved extremely severe, increasing the previous runtime by a whole order of magnitude. Fortunately, we were able to use some simple mathematical trickery to evaluate the reconstruction phase sparsely inside the frequency domain before taking the inverse transform, using the fact that the DCT is a unitary transform (and thus preserves inner products).

The project page (linked at the beginning and again here) contains the full paper as well as some images and video results, so please check it out for a more thorough treatment!

Currently, I am experimenting with sonifying certain aspects of the subspace re-simulation, mapping the singular values into frequencies, and turning trajectories through the subspace into morphologies of chords and spectra.