The main algorithm used to simulate fire are the Navier-Stokes (NS) equations which can simulate the flow of non-compressible (newtonian) fluids. These equations can model the chaotic and difficult natural phenomena turbulence. To find a smooth solution is possible in 2D, but has yet to be found for 3D simulations. Therefore, many alternative methods have been developed to try to accurately predict and simulate using NS equations or produce visually accurate results that may not be accurate to NS. Although NS equations are typically associated with fluid simulation, they can also be used for fire and smoke simulations as the underlying issue involves modeling the turbulence.
The computational complexity of NS equations are immense, with a recent fluid-solid coupling real-time simulation being able to run on a 64*64*64 grid using a Nvidia 2080ti GPU (4). A 3D simulation means that at minimum there is a n*n*n computational complexity since we must loop through x, y, and z coordinates. But this doesn't take into account solving NS which further increases the computational complexity. In the end, I used a 100*100 grid in Processing3 for my fire simulation with a linear solver iterating 10 times. An additional computational hurdle is how I blur my scene using a Gaussian blur effect within Processing's filter function. I do this to reduce the pixelation of my simulation due to the scaling effect I added in to make the window larger.
In order to scale my simulation 10x or even 100x, I think the limiting factor is the Processing framework that I am using. I would first migrate all my code to a faster C++ solution, perhaps using OpenGL. I would also need to create a shader that can blur my scene similar to the results that I am getting with the Gaussian filter, which can then be run on a GPU. Changing these two things would likely provide the largest computational improvement that would allow me to scale up my simulation.
During week 6, we began exploring fluid simulation and the methods that can be used to simulate fluids such as Eulerian shallow water, smooth particle hydrodynamics, and NS incompressible fluids. We delved further into NS incompressible fluids in week 11, in which we learned that NS does four key aspects: velocity pushes itself (advect function), velocity is pushed away from high pressure (project function), velocity diffuses along the gradient (diffuse function), and external forces affect the velocity (left mouse click and constant source for fire).
All of the current state of the art techniques try to either simulate real world fire dynamics more accurately or try to produce visually similar results to the real world while sacrificing NS accuracy. One method is by adding in more real world variables, such as the conversion of solid fuel to a gaseous fuel and the corresponding reaction zone where this occurs, as well as intermediate combustion products, blackbody radiation emittance, and even soot. Another utilizes lattice Boltzmann methods that doesn't solve NS directly but does create a more robust, accurate, and efficient fluid-solid coupling solver than previous attempts. They go so far to say that they can simulate in real-time a 64*64*64 3D grid, or 262,144 individual cells compared to my current 10,000.
Even though I am not able to implement the above state-of-the-art techniques, I similarly want to simulate fire in a more visually realistic way. To accomplish this, I really had to fine tune my parameters to my gaussian blur effect so that I could maximize the window size of my simulation while maintaining a smooth running simulation above 30 frames per second.
Feedback from my peers was positive and no real constructive criticism was given. I did have the problem that my simulation's window was too small because I couldn't run my simulation with 30 fps at anything higher than 200*200 pixels. There were suggestions from Professor Guy and TA Daniel that I try to scale up the simulation and/or blur the scene to dissipate the pixelation. I was able to add a scale factor to my simulation after many indexing errors. Next I tried to blur my scene with a shader, but the results just weren't blurred enough. Then I used the built-in filter function with parameter 1.65 that uses a Gaussian blur. This decreased my performance, but the visual result was much closer to what I wanted so I decided to reduce the complexity of my simulation by lowering the iteration of the solver to 10 and the grid size to 100*100 with a scale factor of 4.
As previously mentioned in Computational Bottlenecks, I would want to recreate my simulation in C++ and better utilize the GPU and shaders in order to create a larger fire simulation. Originally I wanted to create different coloring effects for the fire, but the optimization portions really took up most of my time. Tuning the parameters was also time intensive, but I am happy with the current settings and results. Additionally, I'd like to try and implement a lattice Boltzmann solver and compare the differences in the results compared to what I currently have.
(1) A model for physics‑based fire simulation and analysis, Zhou, X., Zhang, Y., Chen, G. et al., Virtual Reality, 2020.
(2) Physically based modeling and animation of fire, Duc Quang Nguyen, Ronald Fedkiw, and Henrik Wann Jensen, ACM Trans. Graph, 2002
(3) Local Bases for Model-reduced Smoke Simulations, Mercier, O. and Nowrouzezahrai, D., Computer Graphics Forum, 2020.
(4) Fast and Scalable Turbulent Flow Simulation with Two-Way Coupling, Wei Li, Yixin
(5) Fluid Simulation for Dummies. (2020). Retrieved 26, November 2020, from https://mikeash.com/pyblog/fluid-simulation-for-dummies.html