The algorithm, or "I just swapped the X and Y axes and called it a day."

With the background and the current state-of-the-art algorithm established in the previous post, it's time to take a look at my ultra sleek revolutionary new algorithm. Spoiler alert: it's pretty simple.

First of all, let's take a look at a simple scenario from the perspective of a single pixel in the scene. For each pixel, we're interested in being able to store a representation of the smoke's density along the view vector of that pixel. In other words, the entire problem boils down to creating a nice way of storing the mathematical function for density of the smoke over distance from the camera for each pixel.

In our little test scenario, we have a single, thick smoke cloud at a fairly high distance from the camera. The particular pixel we're looking at therefore has a zero density for a long distance, followed by a rapid increase in density. Instead of plotting the density directly, I'll be plotting the visibility of the smoke at a certain distance. Essentially, the visibility at a certain depth from the camera depends on how much smoke was between that point and the camera; the more smoke, the lower visibility. This is a bit more intuitive than plotting density, and will help with the visualization I want to make.

Here's the visibility curve. The x-axis plots depth, while the y-axis plots visibility.

As you can see, the visibility starts at 1.0 (100%) and remains at that level for half the view range. Then comes a rapid drop caused by the mentioned smoke cloud, causing the visibility to quickly approach zero, but never actually reach there (the visibility is equal to exp(-distance*density), meaning the value never reaches zero no matter how much smoke we have).

The approach that the algorithm mentioned in the previous blog post takes is that it simply samples this function at certain fixed depths, computes the visibility there and essentially interpolates the rest.

The red line is a pretty bad approximation of the original green curve. The sample points are simply spaced too far away. Even worse, this representation would be even worse if the depth complexity of the scene increased. In this case, the samples would need to be distributed over a bigger depth range, reducing the accuracy of the representation even further. Of course, this example only uses 8 samples, but it's clear that the sample count would need to be increased vastly to be able to accurately represent this function. Although the samples does not have to be evenly spaced, modifying the distribution of the samples can merely help in specific cases, and will be a trade-off regardless (for example having more samples closer to the camera and fewer farther away).

Something that I mentioned in the previous blog post was also the inefficiencies in lighting this representation. The lighting would be computed by looping over different points and computing lighting at those points. However, a vast majority of these points either have no smoke (meaning they won't reflect light) or have zero visibility (so any reflected light would be invisible). A lighting algorithm running on a GPU would not be able to efficiently branch to avoid unnecessary work, meaning that a huge amount of work will go wasted, while not enough lighting samples will be taken where it really matters (high density areas).

Looking at this, I made an observation on the similarities between this problem and the problem of order-independent transparency. That problems also essentially boils down to the problem of efficiently computing a visibility function for each pixel so that blending can be done by computing a weighted sum using the visibility function. An example of this is Adaptive OIT, which can efficiently compute a step curve which is an extremely good representation of a visibility function that is completely independent of scene depth complexity. This got me thinking on a different approach.

The froxel algorithm essentially works by quantizing the depth of the function into discrete values while keeping the visibility/density at a high precision. What if we quantized the visibility/density instead and kept the depth at a high precision? In other words, instead of storing the visibility at certain predefined depths, we store the high precision depth values of certain predefined visibility values! How would such a scheme do at representing the above curve?

Well, well, well, would you look at that? That is actually an extremely good representation of the original function with the same number of samples! There are no samples wasted on the vast empty space in front of the smoke cloud and no samples wasted behind it either. All the samples are put to excellent use!

This kind of representation has a large number of advantages compared to quantizing depth. In the previous algorithm, aside from the problems with depth complexity if the smoke cloud was translated towards or away from the camera, the result will wobble and flicker as the smoke cloud travels over the quantization points. This can result in inconsistent sorting of smoke and cause lots of unwanted lighting artifacts, which the Frostbite paper needed heavy temporal filtering to fix. This quantization is completely unaffected by both the depth complexity of the scene and translation of the smoke clouds. However, the greatest advantage of this scheme stems from the fact that this kind of representation also gives optimal lighting sample points. By properly choosing the predefined visibility values to quantize to, simply calculating the lighting at the sample points (and possibly points interpolated between these points), the lighting samples will be perfectly distributed to have the same contribution to the final scene. This is a huge advantage that can be abused to get away with much lower sample counts that are traditionally needed to light smoke, as every single sample will have maximum contribution to the final scene!

The algorithm seems to have lots of potential! Of course, there's just one minor detail left... Implementing the sucker on modern GPUs! Oh, what could possibly go wrong? Stay tuned for the next episode: The implementation, or "I hate GPUs."!