Improved Semi-Lagrangian Algorithm For Smoke Simulation

Fluid simulation is widely used in movie animation effects, industrial design and other fields. Physics-based simulation method is becoming increasingly common in fluid simulation. The most common applications of fluid simulation in computer graphics are the liquids, smoke, flame and explosions. Fluid simulation schemes can be used in other applications such as reproducting hair, clothes and facial expressions.In this thesis, we present an introduction to Navier-Stokes fluid simulation in computer graphics and we also present the details and comparison of three different methods for solving the advection equation: the popular semi-Lagrangian method, two order accuracy order BFECC method and MacCormack method. Through these advection scheme comparisons, we propose a new scheme that based on the simple semi-Lagrangian method to simulate fully three dimensional smoke scenes in real time. The main idea of the new method is using semi-Lagrangian method to structure a set of approximate straight lines of characteristic line for the partial differential equation. The new scheme is completely dependent on the semi-Lagrangian method, so it is unconditionally numerical stable with arbitrary large time steps. The new scheme has two order accuracy and can reduce dissipation largely compare to the semi-Lagrangian method. Both BFECC and MacCormack improve the accuracy to second order both in time and space by error correction step which can introduce a new extrema into results and eventually lead to divergence so when we use these schemes, we need a limiters to filter the new extrema values. Unlike BFECC or MacCormack method, the new scheme uses semi-Lagrangian method repeatedly rather than error correction, so the minimum and the maximum is bounded. Furthermore, we can get a series of numbers that approximate the exact values in an arbitrary order accuracy.