Computer Graphics papers: Stream-Guided Smoke Simulations, by Sato et. al.

I have always found reading graduate-level computer science papers to be rather difficult. I would like to change this, and get really good at reading and understanding them. 

So, let's start with the one I have to present in CS 655, Stream-Guided Smoke Simulations by Sato et. al. 

First off, here is the main website for the paper.

The video on that website has no sound or explanation at all, so sadly we are stuck with the paper only. 

I guess I can embed it here, too. 

NOTE: Smoke is considered a fluid in this paper. Obviously it's a gas, but things such as smoke are considered to be fluids for the purposes of simulation. 

Basic Idea:

With any paper, we need to figure out the basic idea behind it before we do anything else. The idea is to boil down the text to the most basic concepts possible. We do this by skimming the abstract at the beginning (not labeled in this paper). 

The basic idea behind this paper? We are simulating smoke in 3D. 

Easy, right? Yeah. But that leads us to the next question. 

What problem are we solving?

Modern visual effects tools such as Houdini already have the functionality built within them to simulate smoke. So, what is this paper doing differently? More specifically, what problem is it solving? 

As with many things in computer graphics, we are effectively solving two problems:

1) Computational efficiency, and

2) Artistic quality. 

These two concepts are both extremely important, and are constantly at war with each other. This paper attempts to create smoke simulations that are both efficient and high-quality. First, a basic smoke simulation with hardly any details is created, and it is super smooth and boring. Why? Because it's faster to render! 

Now, the artistic quality part comes in. We use user input, plus some fancy math, in order to add detail to the smoke in post-processing. 

Post-processing generally means after the initial render has already been computed, mathematically speaking. This tends to save us time, overall. 

How are we solving this problem?

"We" technically refers to the authors of the paper, but by extent, it can also refer to us as computer scientists trying to understand their process. Anyway, semantics. 

We are solving this problem by a user-controlled method. This means that, as a part of this paper, the authors created a tool that users can control. This tool will allow the user to adjust the smoke simulation as they please, and it will only change a single parameter. 

Recap so far

Not bad, eh? We are simulating and rendering smoke in 3D. We are trying to do so in an efficient way which still maintains high artistic quality. Our method creates a simple smoke simulation, then adds detail to it in post-processing, using fancy math. And we are allowing the user to control how the smoke is rendered. 

The basic math

This is where it starts to get annoying. 

Because computer graphics papers always assume a lot about your mathematical background and acuity. 

This paper formulates fluid guidance -- 

-- or in other words, the user adjusting the smoke simulation -- 

-- as a minimization problem in stream function space. 

Looking at this, I'm not really sure what a minimization problem is, and I'm also not sure what stream function space is. However, I have learned one more thing: 

The focus of this paper is clearly on what the user is adjusting. What the user is adjusting is tied to this mathematical formula. 

However, we can derive additional meaning from looking deeper into the lexicon, and googling around. A minimization problem is simply a subset of an optimization problem, so we are just trying to optimize something. Which makes sense, since we want this to be an efficient simulation method. 

Stream function space -- I have no idea what this is. Hopefully, they will elaborate further into the paper. 

Now let's read further until we understand what they're talking about. 

Reading the Introduction

Okay, so the first thing I realize while reading the introduction is that the normal guide-based methods usually solve large minimization problems, which makes them quite computationally expensive. 

The paper is improving this by working with stream functions. It provides vector potentials as a synonym. I'm still not entirely sure what these are, but the benefits are clearly stated: The problem is much simpler and faster, but it remains high-quality. 

The second paragraph has some key stuff!

• First, arbitrary input velocities are converted into stream functions. 
• Then, these functions are used to guide the optimization of a higher-resolution stream. 
• We obtain the final velocity by taking the curl.
• And the final result is incompressible. 
• It's still a minimization problem, but it's the scalar product of the upsampled input stream function and a simple scaling function. 
• The goal is to obtain the optimal scaling field that generates a high-resolution turbulent flow that is similar to the input flow. 
• After that, it basically goes on about how efficient it is. Also, it's artsy and can work with user-inputted velocities. K, cool. 

So, a lot of that is still Greek to me. But, the goal is evident: generate a high-resolution turbulent flow that is similar to the input flow. 

Let's analyze this further, because we are determined computer scientists who push through difficult topics in order to gain a true, full understanding. 

I believe that the arbitrary input velocities are there to introduce randomness into the simulation. Somehow, these guide the optimization problem, which makes the smoke higher-res while also introducing randomness. 

All right, so that makes enough sense for now, I guess. Let's keep going. 

Reading the Related Work Section

This section essentially exists to give us a better understanding of the context of the problem. Spending too much time on this crap, though, is ultimately counterproductive, so let's breeze through it and just a general idea of what they did. We should also understand what they are lacking that this paper fulfills. 

• Stam introduced a solver for the Navier-Stokes equations. Okay, pretty much every fluid simulation paper mentions this lol. 
• Control methods: 
• Fattal/Lischinski -- They introduced additional external forces to control smoke simulations. 
• Thurey et. al. -- Used a control method that preserved details. 
• These produce good results, but they are SLOW. 
• Post-processing methods for enhancing detail:
• Low-resolution simulation using wavelet noise (Kim et. al.): This synthesizes plausible turbulent motion for low-res simulations. 
• Same thing using curl noise (Narain et al)
• Using existing high-resolution flow data for detail enhancement 
• Using CNNs to learn a relation between high and low res flows (Chu/Thuerey)
• Sato et. al.: Style transfer for fluid turbulence. LOL this was the last paper I had to present. Interesting stuff.  
• These methods work well, but are not as realistic and result in some data loss. 
• Guiding methods for velocity fields 
• Guided high-resolution flows using optimization (Nielsen et al) -- It involves a user-specified parameter. I'm pretty sure that I read about this one in the Sato paper. This is super computationally expensive. 
• Gregson et al: A guided simulation based on an ADMM framework. I have no idea what ADMM is. This is why these papers are so confusing aaaaaugh 
• Inglis et. al.: Optimizing using a primal-dual algorithm. Computationally expensive 
• Frequency-Domain guiding method (Forootaninia/Narain) -- Simple to implement, and efficient. But, the user has a difficult task to create a velocity field. 
• Ando: liquid solver in stream function space
• Sato: stream function for deforming fluid flow as a post-process
• For the above two approaches, the results always satisfy the incompressibility condition. 

Okay, that was exhausting lol. I won't pretend to understand all of that, but I should probably look up the incompressibility condition. 

Here we go

Still kind of confusing. Let's keep looking. 

Maybe this?

I think I get it? The rate of change of the density of the fluid should remain constant. OK, not too bad. Well, it either means that or the density itself is remaining constant. Um. I guess it depends on the context. OK, whatever, something is remaining constant. 

KK, that's good enough for now. Let's take a break, get some water, weep for all of humanity, fold some laundry, etc. 

Reading the Proposed Method section

Ah, it's about to get super gross now. Because this is where we actually dive into the math. For the presentation, it's most important to just understand what each individual variable is representing. Furthermore, you don't need to do any sort of full derivation or anything; just understand the gist of what the equation is outputting. 

But yeah it's still gonna be gross. Fat and juicy, just like those grubs from Lion King 1 1/2. Like, eww. 

First off, we see that we have both low- and high-resolution grids, which will be notated as lowercase/uppercase accordingly. The grids are probably going to be vector fields, or some other sort of way of finitely discretizing what is in reality a continuous function representing the smoke. 

The method is explained as follows: 

• It executes for each frame of our animation.
• The INPUT is a low-resolution guiding field. So in other words, it's a super low-res smoke simulation, which is easy and fast to compute, that follows the general path we want. Note that this is a vector field. 
• The algorithm starts by upsampling this to a higher resolution. This creates a new vector field. 
• This vector field is then converted into a stream function. 
• Then, the algorithm solves an optimization problem to generate a guided stream function (not sure if this is the same one from the above bullet point or not, or if it's related or not).
• The final velocity field is taken by computing the curl of the above guided stream function. 
• Then, we must advect the velocity field. (I don't know what advecting means.) It is advected using the Navier-Stokes equations. 
• This result is then used to solve the optimization problem for the next frame. Interesting...
• Additional parameters can be adjusted if desired, such as turbulence. 
• The degree of guidance can be adjusted by the user using the parameter alpha. 

So, after Googling around it looks like advection is a way to describe fluid transfer. Considering that this is essentially what the Navier-Stokes equations exist to model, we don't need to worry too much about it. 

The next sections simply provide further mathematical elaboration. 

Computing the Stream Function

This section basically describes how we compute our stream function, given our upsampled velocity field. 

Upon writing this, I spent all day doing 650 and now I have to do this stuff and I am super exhausted, so unfortunately the cohesiveness is probably gonna go waaaaay down as I attempt to finish this before too late at night. 

The variables should be explained pretty quickly. P is a scalar function, and H is a harmonic vector field. Some fancy mathematical properties give us the final result. 

I am not sure what delta is. 

Regardless, this is based on the Helmholtz-Hodge decomposition. It is definitely beyond the scope of any math I have taken up to this point, but here you go eh. 

The solver used to compute the resultant formula is the conjugate gradient method. It doesn't matter, though, what matters is that the result is the stream function. 

Guiding Formulation

First, the guided stream function is described as the sum of an upsampled stream function, and any stream function from the previous section. The variable x is a grid function. 

We optimize the stream function at x in order to generate the turbulent details. (I think when I make these slides, I will try and put an image here)

We then optimize the scaling function. Some user input comes into play here. 

Then, we define the optimization problem. We solve for the optimal scaling function subject to a minimization problem at each frame of the animation. In other words, equation 7 in the paper is solved at each frame. The variable alpha controls the degree of guiding. Vt(x) is obtained by advecting the guided velocity field from the previous frame. An equation is given for that, and some more math is used to simplify it. 

Delta-T is a time step, and f is external forces such as vorticity confinement and smoke sources. 

The equation 9 is a Navier-Stokes momentum equation. 

Some more math crap

And then we get equation 11 which is the final optimization problem, I think. Then we walk about how to get the final velocity field. 

I will need to explain how those photos work...

Using Control Parameter Alpha

The user can paint alpha onto their screen (digitally, obviously) in order to control the turbulence. Otherwise, they assigned smaller alpha to the smoke region, and larger alpha to other regions. 

Results

This section is important because it is related quite a bit to the video. They show a LOT of cases in which their method is clearly superior to related methods. They basically explain in each one why the other methods suck. 

Figure 6 shows what happens when you modify alpha. 

Figure 7 shows manual input flow, and how the algorithm adds realistic motion to it. 

Figure 8 is a smoke plume sim

Discussion

The guidance algorithm fails when the user-provided stream function isn't good. The value can't be 0, 1, or a simple addition of a constant, or else it will not work. Only the method from section 3.1 works. 

Incompressibility is satisfied because the optimization is solved in stream function space. 

Conclusions

Ok so the guiding method works with stream functions, plus there is a scaling function which formulates a minimization problem, which speeds things up. The final velocity is incompressible (density remains constant). The authors hope to apply this method in the future to other fluids. 

Okay, so I'm pretty exhausted, and unfortunately the last parts will probably seem hazy. Hopefully, I will be able to refine and iterate on this more in the future. For now, let's see what we can do about a presentation. 

Presentation

Surprisingly, it actually went pretty well, all things considered. Here are my slides.