1. Come up with an algorithm that could calculate the depth values for when a smoke volume reaches certain visibility levels to calculate a visibility curve.
2. Come up with an algorithm that could take a pre-existing visibility curve and "add" another smoke volume to it, outputting a new visibility curve. The purpose of this algorithm is to allow me to compress multiple smoke clouds into a single visibility curve, so that lighting only has to be done once for the final curve.
3. Come up with a good GPU implementation of these algorithms.
I started out by writing a small visualization program to help me develop and test the initial algorithms. My first approach to the problem was to first integrate/raytrace through the smoke volume and generate a visibility curve, then merge that curve with the existing visibility curve for that pixel. This can then be done repeatedly to accumulate all smoke volumes into a single visibility curve.
Generating a visibility curve from a smoke volume
The solution to algorithm 1 that I came up with was:
1. Integrate through the smoke volume.
2. Whenever the visibility reaches the next threshold/milestone, calculate the exact depth and store that.
Simple enough. Here's an example of a generated visibility curve from a simple smoke volume that starts halfway into the scene.
Here's a second curve from a constant-density fog. For this curve, one can simply calculate the exact point the visibility drops to a certain value mathematically instead of integrating.
Merging two visibility curves into a single visibility curve
For algorithm 2, the algorithm for merging two visibility functions, I went with an exact mathematical solution. Given the input curves A and B:
1. For each point in curve A, find the corresponding visibility at that depth in curve B and multiply it together with its original visibility to calculate a new visibility for that point, storing the output in curve C. In the resulting curve, each point will NOT have a set visibility, so both depth and visibility will vary for these points.
2. Do the same for curve B, finding the corresponding visibility of each point in A and multiplying it together, storing the result in curve D.
3. Merge curve C and D into a single curve, curve E, sorting the nodes by visibility into a single curve.
4. Loop through all nodes in E to generate a new fixed-visibility curve. Whenever the visibility drops below the next threshold in visibility, store that depth into the next node.
The following is an example of a merge operation. Given the above two curves with blue and red nodes, the result of multiplying each curve by the point on the other curve and merging the two into one curve results in the following:
This curve has twice as many nodes as it should, and the nodes do not correspond to the fixed visibility values that we need. Hence, we continue with step 4 in the algorithm, compressing the curve to the correct number of nodes, where each node has a predetermined visibility, just like the original input curves.
This merging algorithm can then be performed again to add a third volume to the visibility curve.
The GPU implementation
The first GPU implementation revealed a number of problems that I had overlooked. The biggest one was how to deal with the case where the visibility never reaches all predefined values. For example, if the first visibility threshold is 0.95 and the visibility only ever drops to 0.96, the first threshold would never be reached, meaning that the smoke would simply never show up. Essentially, it meant that the visibility along a given curve was always rounded up to the closest threshold. This caused a kind of banding as the fog reached certain visibility levels.
The solution here was to adjust the visibility thresholds so that they went from 1.0 down to lowest visibility reached for each individual pixel. This redistributed the visibility levels dynamically based on the demands of each pixel so that all visibility levels were always reached, which lead to a huge increase in quality. When merging two visibility curves, the lowest visibility of the result is simply the lowest visibility of each of the curves multiplied together. This completely eliminated this issue.
There were however severe problems with the performance of the implementations. Generating a visibility curve during integration of a smoke volume requires dynamic writes and dynamic nested loops. This was a bad fit for GPUs.
The merge operation was even more inefficient. Step 1 and 2 each turned into O(n^2) operations, as each point in curve A needs a linear search through curve B and vice versa. In addition, the simple merging of two sorted lists turned into yet another nightmare, as that requires dynamic reads from the two arrays. Finally, the fourth step suffered from the same problem as the integration did, requiring dynamic writes and dynamic nested loops.
The future was looking grim...
No comments:
Post a Comment