A Fast Simulation Method Using Overlapping Grids
for Interactions between Smoke and Rigid Objects
 Computer Graphics Forum (Proceedings of EUROGRAPHICS 2008), Vol. 27, No. 6 , pp. 477-486

 Yoshinori Dobashi1,  Yasuhiro Matsuda2,  Tsuyoshi Yamamoto1,  Tomoyuki Nishita2
 1Hokkaido University,  2The University of Tokyo

         

Abstract
Recently, many techniques using computational fluid dynamics have been proposed for the simulation of natural phenomena such as smoke and fire. Traditionally, a single grid is used for computing the motion of fluids. When an object interacts with a fluid, the resolution of the grid must be sufficiently high because the shape of the object is represented by a shape sampled at the grid points. This increases the number of grid points that are required, and hence the computational cost is increased. To address this problem, we propose a method using multiple grids that overlap with each other. In addition to a large single grid (a global grid) that covers the whole of the simulation space, separate grids (local grids) are generated that surround each object. The resolution of a local grid is higher than that of the global grid. The local grids move according to the motion of the objects. Therefore, the process of resampling the shape of the object is unnecessary when the object moves. To accelerate the computation, appropriate resolutions are adaptively-determined for the local grids according to their distance from the viewpoint. Furthermore, since we use regular (orthogonal) lattices for the grids, the method is suitable for GPU implementation. This realizes the real-time simulation of interactions between objects and smoke.

Download
paper:[pdf] slide:[ppt]

Videos

Verification of Our Transfer Method between Grids

Animations corresponding to the examples shown in Section 4.3.3 are shown here. These demonstrates the validity of our method. These examples are calculated on the CPU. In the following examples, pressures are converted into pseudo colors after normalizing them so that the maximum pressure corresponds to 1.0, which corresponds to red color.


 This example shows the comparison of simulations using different sizes of boundary regions of local grids.
  • Outermost two grid points for the leftmost images.
  • Outermost four grid points for the center images.
  • The global grid only for the rightmost images (no local grids).
We consider the rightmost images as the reference solution. This animation demonstrates the following things:
  • In the leftmost images, there are discontinuities between the local grid and the global grid.
  • Oscillations in pressures are also observed in the leftmost images.
  • The oscillations are also observed in the reference solution (the rightmost images). This is due to the sampling errors of the object shape.
  • The dicontinuities and the oscillations disappear by using our method (the center images).

 This example shows the comparison of simulations using different resolutions of local grids. Compared to the resolution of the global grid, the resolutions of the local grids are:
  • twice finer in the leftmost images,
  • four times finer in the center images, and
  • eight times finer in the rightmost images.
The following features are observed in the animation.
  • In the case of the twice finer resolution (the leftmost images), no discontinuities are observed between the local and the global grids.
  • Slight discontinuities can be observed in the pressure distribution, when using the four times finer resolution (the center images). However, in the density distribution, we cannot distinguish the discontinuities.
  • When using the eight times finer resolution (the rightmost images), the apparent discontinuities appear in the pressure distribution. However, it is still difficult to distinguish them in the density distribution.


This example shows the validity of our transfer method between multiple grids. The two cross-shaped objects rotate around the large object. The resolutions of the local grids are chosen appropriately according to the size of the objects (see Section 4.3.3 for more detail). Our method works very well even if multiple grids overlap as shown in this example

Experimental Results

Animations corresponding to the examples shown in Section 7.1 are shown here. These examples are calculated on the CPU

This example shows the comparison of simulations with different configurations of grids.
  • The leftmost image shows the result using only the global grid with a low resolution.
  • The simulation shown in the center also uses the global grid only but the resolution is higher.
  • The rightmost image shows the results using the proposed method that uses the local grid and the global grid.
The animation demonstrates the ability of our method to reproduce the small-scale vortices

This example is to verify the effectiveness of the method for determining the resolution of the local grid. We used a simple three-dimensional simulation, in which a fighter plane rotates and descends. We compare two types of the simulations.
  • In the left image, high resolutions of the global grid and the local grid are used. We consider this simulation as a reference solution.
  • In the right image, a relatively lower resolution is used for the global grid and the resolution of the local grid is determined by the proposed method.
This animation demonstrates that :
  • the proposed method can generate images that are almost the same quality as the reference solution and
  • the computation process is 8 times faster.

This movie shows the effect of using a higher resolution local grid in three-dimensional simulation. In this movie, the left image show the result using the global grid only. The right image shows the result using our method. The resolution of the local grid is four times finer. As shown in this move, the motion of smoke becomes simpler without the local grid.
Note: this example is not included in the paper

Practical Examples

Animations corresponding to the examples in Section 7.2 + some additional examples are shown here.

This example shows a real-time simulation of the interactions between several objects and rising smoke in two dimensions. The shapes of the objects are determined by bitmap images of the letters, 'EUROGRAPHICS'. The resolution of the global grid is 512x512 and the resolution of the local grids for the letters is 128x128. The simulation runs at 10 fps on the GPU.

This example shows a real-time simulation of the interactions between a fighter plane and smoke in three dimensions. The resolution of the global grid is 128x128x128, and the resolution of the local grid of the fighter plane is 49x59x25. The simulation runs at 10 fps on the GPU.

This example shows an animation of dynamic smoke generated from 15 fighter planes under attack by missiles. In this example, we use the resolution determination method for the local grids of the fighters. A specific grid around the viewpoint is also generated in order to improve the visual quality. This example is calculated on the CPU. Both the simulation and the rednering took 10 sec./time-step. Note that this animation contains audio.

This example shows the interactive operation, where the user moves a sphere in fluids. Since only the local grid for the sphere is set to higher resolution, we can calculate the interaction between the sphere and the fluids very efficiently. The motion of fluid is visualized by either particles or volume rendering. The frame rate of the simulation is 10 fps. For the volume rendering, we used the advection texture technique developed by Max to visualize the velocity field

This animation shows a rotating parallelepiped interacting with rising smoke. This example shows the ability of the proposed method to capture the detailed flow around the objects. The motion of fluid is visualized by using the volume rendering combined with the advection texture technique. The frame rate of the simulation is 10 fps but the rendering took 0.6 sec./time-step in this case

Citation
@article{doba2008,
		    author  = {Yoshinori Dobashi and Yasuhiro Matsuda and Tsuyoshi Yamamoto and Tomoyuki Nishita},
		    title   = {A Fast Simulation Method Using Overlapping Grids for Interactions between Smoke and Rigid Objects},
		    journal = {Computer Graphics Forum (Proceedings of EUROGRAPHICS 2008)},
		    year    = {2008},
		    volume  = {23},
		    number  = {3},
		    pages = {539-546}
		}
Acknowledgement
This research is partly supported by the Strategic Information and Communications R&D Promotion Programme (SCOPE) from the Ministry of Internal Affairs and Communications of Japan.