**Adapting the
Lattice-Boltzmann Model for Efficient Airflow Modeling
inside the View Frustum**

Independent Study Project by Leonid Velikovich

Advisor: Amitabh Varshney

ABSTRACT

This project proposes ways to improve the performance of
airflow modeling using the Lattice-Boltzmann Model
(LBM). LBM provides an efficient
means of simulating fluid flow; recent implementations run in real time on PC
hardware. However, LBM’s 3D data representation severely restricts the volume
and resolution of the modeled space due to computation and memory
requirements. These constraints
render LBM impractical in an open, freely-navigable 3D world. This project’s proposed solution is to
model over a *selective *volume using a
*selective *modeling resolution by
carrying LBM simulation inside a dynamic view frustum.

INTRODUCTION

There is a growing demand for realistic physical effects in
computer graphics. When it comes to
airflow effects such as blowing wind, billowing smoke, or air turbulence,
researchers seek behaviors that comply with the Navier-Stokes (NS) differential equations for incompressible
fluid flow. Derived by Claude Louis
M. H. Navier and Sir George Gabriel Stokes in the
19^{th} century, NS restates the Newtonian law of mass and momentum
conservation in the context of multidimensional liquid flow (Wolf-Gladrow 2000, 7).
NS is generally impervious to conventional analytical solution techniques
due to non-linearity. Numerical
methods can be used to find approximate solutions, but they are often
prohibitively expensive for real-time simulation.

While NS deals with macroscopic fluid flow, a microscopic approach is provided by the Boltzmann equation, derived in 1872 by Ludwig Boltzmann. The Boltzmann equation treats a dynamic fluid as a collection of microscopic particles which propagate and interact with each other. The Lattice-Boltzmann Model (LBM) simulates this behavior on a set of discrete points regularly spaced over the simulation volume. A simple local particle collision and propagation procedure is applied every time step in the simulation. As time and space resolution approach infinity, LBM approaches an NS solution (Wei et al. 2003). Due to LBM’s simplicity and data access locality, LBM has achieved real-time performance on modern PC hardware and benefited greatly from graphics hardware acceleration (Wei, Li, and Kaufman 2003).

Despite LBM’s promising results, it
has a serious weakness inadmissible in a freely-navigable 3D world. LBM represents the simulation volume as
a 3-dimensional grid, so its performance and memory footprint depend on the
volume and resolution of the modeled space. This is problematic in a
freely-navigable 3D world for two reasons.
First, the navigable volume may vastly exceed any affordable LBM grid
size (unless LBM resolution is reduced below any useful threshold). Second, LBM’s
fixed resolution is dismally maladaptive to the *viewer’s *position in a large world*.*
When perspective-projected onto screen space, faraway grid points become
wastefully close together, while nearby points are too far apart. Thus, small nearby objects will
experience no local airflow phenomena (unless LBM resolution is astronomically
high). At the same time, visible
faraway objects will have more airflow modeling precision than noticeable by the
viewer.

LBM’s resolution inefficiency is
particularly glaring in light of the increasing popularity of level-of-detail
(LOD) models, procedural geometry models, hierarchical object consolidation, and
size-based visibility culling. All
of these techniques adjust geometric detail in proportion to an object’s area on
the screen (e.g. they stabilize a scene’s resolution in *screen space*), with the goal providing
adequate detail up-close, while eliminating or merging excessive detail far
away. These techniques also make
fixed-resolution LBM grids very inefficient for faraway objects—the objects
become very large relative to the LBM grid.

This project modifies LBM’s volume
and resolution of simulation to achieve two goals in real time. The first is to extend the visibly
simulated airflow volume to an unlimited navigable world. The second is to adjust LBM resolution
to *screen space* resolution,
permitting efficient use of screen space and interaction with LOD and similar
objects.

The remaining paper is divided as follows. Previous Work describes prior approaches to gas and airflow modeling. The Lattice-Boltzmann Model explains the basics of the LBM simulation process. Approaches to Adaptive LBM details several ways to adjust LBM detail to viewer position, and explains the author’s choice. Implementation describes the demo that showcases frustum-mapped LBM simulation. Results and Discussion address the demo’s performance, limitations, and the possibility of acceleration on graphics hardware. Conclusion, Future Directions, References, and Demo Screenshots conclude the paper.

PREVIOUS WORK

Several approaches have been explored for simulating fluid dynamics on computer hardware. Procedural modeling was introduced by (Perlin 1985, 287-296) and uses parametric functions to describe fluid behaviors. This method is fast, but requires an unsystematic and difficult search for the right parameters to produce realistic results and has difficulties with environmental fluid interactions (Wei and Kaufman 2003, 6). Physically-based modeling has been proposed by (Wejchert and Haumann 1991, 19-22), and provides an analytical solution. Unfortunately, the computation time and memory requirements for 3D simulation are substantial (Wei and Kaufman 2003, 6). A method of finite differences in 3D was introduced by (Foster and Metaxas 1997, 181-188); however, finite differences are inherently unstable at large time steps and restrict the simulation speed.

More successful approaches ensued when (Stam 1999, 121-128) provided an unconditionally stable method using semi-Lagrangian advection and an implicit Navier-Stokes solver. This method is capable of simulating turbulent flows and can be executed in real time on a low-resolution grid. The method suffers from turbulence decay caused by numerical dissipation, but (Fedkiw, Stam, and Jensen 2001, 129-136) proposed using vortex confinement to avert such premature dissolution by feeding energy back into vortices.

The above methods are “top-down” approaches to approximating solutions to Navier-Stokes (NS) equations: they transform NS into discrete elements such as finite differences, finite volumes, finite elements, or spectral methods (Wolf-Gladrow 2000, 11). By contrast, Lattice-Gas Cellular Automata (LGCA) and the Lattice-Boltzmann Model (LBM) are “bottom-up” approaches; they simulate microscopic particle interactions modeled by the Boltzmann equation. Given sufficient numbers of particles and time-space resolution, they approach NS globally. The simplicity of modeling local interactions allows fast parallel implementations (such as on graphics hardware).

Cellular automata were introduced in 1950 and can be described as a collection of identical “cells” regularly distributed in space; each cell has an associated state, which changes during each time step depending on the states of its neighbors. The application to fluid dynamics was initially proposed by the HPP LGCA model (Hardy, de Pazzis, and Pomeau 1973). The HPP model used a “square tile” distribution, where binary on/off cells simulated the presence of gas particles moving in orthogonal directions. HPP failed to simulate Navier-Stokes because the square tiles’ inadequate 4-way symmetry produced results that were non-isotropic (inconsistent for different coordinate axis orientations). Subsequently, (Frisch, Hasslacher, and Pomeau 1986) produced a hexagonal FHP lattice and showed that 6-way symmetry was sufficient to yield the Navier-Stokes equation in the macroscopic limit. Used together with programming techniques such as multi-spin coding, HPP and FHP can be efficiently programmed for parallel computation on desktop PCs (Wolf-Gladrow 2000, 53).

The problem with LGCA is its binary nature: it attempts to simulate individual particles and consequently produces grainy “black and white” distributions. They can be smoothed by averaging over larger areas of the LGCA grid, but this makes for inefficient use of high grid resolution—performance is wasted.

LBM addresses the graininess problem (amongst others) by replacing the notion of individual on/off particles with continuously variable particle distributions. Thus LBM smoothes the range of possible gas pressure/velocity vectors at each cell in the grid. LBM has been shown to work in 2D as well as in 3D using square and cubic tiles, respectively, and a combination of orthogonal and diagonal interlinks. The simulation process is more complex than LGCA because collisions and boundary conditions are complicated by the non-discrete particle distribution values.

THE LATTICE-BOLTZMANN MODEL

The Lattice-Boltzmann Model (LBM) simulates the microscopic movement of fluid particles, which macroscopically obey the incompressible Navier-Stokes (NS) equations governing fluid motion. LBM subdivides space into a grid composed of regularly-spaced cells; the set of vectors connecting a cell to its immediate neighbors comprises a set of 4 discrete lattices shown in Figure 1 (Wei et al. 2003). These vectors represent fluid particle flow along those particular directions. Sub-lattice (a) is a zero vector representing stationary particles.

Figure 1: The four sub-lattices defined on a 3D gri;d taken from (Wei et al. 2003).

LBM simulation proceeds in a series of discrete time steps; each step consists of particle collision and propagation stages. The particle collision operation is computed locally for each cubic tile. A local collision is represented by displacing the velocities of colliding (opposite-facing) streams of fluid particles. The restriction is that after the collision step, the total mass and momentum must be preserved. This is accomplished by calculating an equilibrium velocity distribution based on the initial mass and momentum of fluid particles. The post-collision velocities are calculated as the pre-collision velocities plus a scaled difference with the equilibrium distribution. The propagation step simply moves the particle distributions one unit along their velocity vectors (e.g. to the neighboring cells).

The boundary conditions and object interactions are another source of concern. The simplest approach is to use periodic boundary conditions, e.g. to assume the LBM volume wraps around on itself. Objects can be assumed too light to affect airflow. In this ideal scenario, no special accommodations are needed. However, obstacles at the edges and heavy objects require special boundary treatment by using special semi-solid boundary tiles (Wei et al. 2003).

APPROACHES TO ADAPTIVE LBM

The goal of this project is to adapt LBM to permit unlimited modeling space and consistent screen space resolution. Many different approaches are possible, some of which are discussed here. For clarity, these approaches are categorized as preserving or distorting the LBM lattice shape. The distortion of lattice shape may cause undesired anisotropy, instability, or other deviations compared with a better-understood regularly-spaced cubic grid. However, distortion permits potentially higher LBM resolution efficiency, and its associated problems may be partially curable.

Amongst the distortion-free approaches to adaptive LBM modeling, Figure 2 shows the traditional fixed-resolution approach. The triangle represents the view frustum (2D projection from above; 90% horizontal field of view).

Figure 2: Conventional LBM Figure 3: Octtree World Space LBM Figure 4: Octtree Screen Space LBM

Conventional LBM resolution grid, world coordinates advantages:

- Preserves lattice symmetry
- No time scaling problems
- Completely viewpoint-independent

Disadvantages:

- Intractably inefficient for a large world volume
- Smallest phenomena scale determines global resolution

Figure 3 shows the concept of using octtrees to subdivide the world into a set of fixed-resolution subgrids. Advantages:

- Preserves lattice symmetry
- Addresses time scaling problems
- Palpably beneficient adaptive space scaling
- Simulation data is viewpoint-independent

Disadvantages:

- Visibility requires viewpoint-dependent calculations
- Introduces additional dimension to simulation
- Highly inefficient relative to view frustum volume

Figure 4 shows the possibility of transforming the octtree approach into the camera’s screen coordinates. Advantages:

- Preserves lattice symmetry
- Addresses time scaling problems
- Decent adaptive space scaling

Disadvantages:

- Requires viewpoint-tracking transformations
- Introduces additional dimension to simulation
- Inefficient relative to view frustum volume

Figure 5: Projection transformation LBM Figure 6: Geometric series LBM Figure 7: Spheric geo-series LBM

Figures 5-7 show how the LBM grid can be distorted to fit the
view frustum almost exactly. In
practice, it may be better to make the LBM grid a *subset* of the view frustum, ignoring
extreme far distances.

Figure 5 uses a projection transformation, which has the following advantages:

- Preserves vector linearity in all directions
- Every lattice in a slice has equal volume
- Efficiently covers view frustum volume

Disadvantages:

- Extreme front-back distortion of lattices
- Distortion causes extreme time scaling problems
- Lateral-direction lattice dissymmetry
- Requires viewpoint-tracking transformations

Figure 6 uses a geometric series to make all depth slices geometrically similar to each other, to minimize distortion. Advantages:

- All lateral slices are geometrically similar
- Lattice depth proportional to width (less distortion)
- Every lattice in a slice has equal volume
- Efficient view frustum volume coverage & distribution

Disadvantages:

- Skewed lattice dissymetry at edges of frustum
- Diagonal lattice vectors don't follow lines
- Gradual time-scaling problems
- Requires viewpoint-tracking transformations

Finally, Figure 7 is a modification that holds each vertex in a slice be equidistant from the viewer. Advantages:

- Minimized skew distortion of edge lattices
- All spherical slices are geometrically similar
- Lattice depth proportional to distance
- Fairly efficient view frustum coverage

Disadvantages:

- Narrowing/elongation of lattices at edges
- Diagonal lattice vectors severely curved
- Gradual time-scaling problems
- Expensive space and camera-tracking transformations

Due to its relatively small distortion combined with highly efficient space coverage, the geometric series approach was chosen for this project.

IMPLEMENTATION

The created demo emulates a level-of-detail world where
objects’ geometric detail varies with the distance from the camera. Leaves blow across the scene, blown by
the vectors in the LBM grid, with gravity effects and forces proportional to the
perpendicularly exposed leaf area.
A semi-realistic world environment was created from
procedurally-generated bushes, trees, and hills which are made of sphere,
cylinder, and plane primitives. The
view frustum contains the LBM simulation grid, which covers 100 % of the width,
66.7% of the height, and 12.5% of the depth of the view frustum. Because the LBM grid’s depth-wise
velocity vectors are collinear and converge at the camera’s origin, the grid
projects onto screen space with *constant
*spacing.

When using computer software, the LBM grid can be represented efficiently as a 1D array where X and Y dimensions are scaled up to nearest powers of 2. This way, the rightmost log2(X’) bits are reserved for the X address, the next log2(Y’) bits for the Y address, and the rest for Z; this makes addressing faster in many cases.

The process of mapping from world coordinates to LBM grid coordinates is fairly simple. World coordinates are linearly transformed into view coordinates (multiplication by a matrix). Then X and Y coordinates are divided by the Z (depth) coordinate. Finally, the logarithm of the Z coordinate is taken by using a fast floating-point logarithm function such as: extract the exponent part by bitshifting, then add a value from a lookup table indexed on the first 8-12 bits of the mantissa. When the Z logarithm is properly scaled, the return value would correspond to the LBM grid Z value. Trilinear filtering may have to be used to get the closest velocity vector to the desired world position.

Inverse mapping from LBM grid coordinates to world coordinates is even quicker. Use a lookup table to get the Z power of the geometric series factor; multiply grid X and Y by Z; reverse-transform from view to world coordinates.

The most serious performance-related problem of view frustum-mapped LBM is adapting to a changing camera position or orientation. A 3D transformation is needed to convert vectors into the corresponding newly positioned tiles. Additional tile information may have to be discarded. It is the presumption here that the addressing tricks permit to make such a transformation comparable in speed to advancing the simulation 1 time step.

Handling collisions is similar to the conventional LBM case. Handling propagation can be done via an addressing trick by adding an offset to the coordinates of grid lookups and modulating by X, Y, or Z. This removes the memory-intensive task of copying velocity distribution values over each time.

The numerical challenges of using a distorted LBM grid are based on the problem of mass and momentum conservation. Does particle mass K in the near depth plane correspond to the same mass in the far plane? One approach is to say Yes, and use the known asymmetry in velocity vectors to preserve momentum. Unfortunately, using this approach directly resulted in unstable simulation, where strong periodic gusts of wind developed in the front-to-back direction. The other approach is to say No, and to scale the momentum of faraway particles according to their distance. This approach produced more satisfactory results when using periodic boundary conditions.

It is undoubted that distortion of the LBM grid may produce at least some anisotropy and might not correctly approach the Navier-Stokes equation. The goal is merely to be sufficiently close, so that the visual appearance, performance, and freedom of movement make view frustum-mapped LBM a competitive choice for real-time navigable 3D worlds.

RESULTS AND DISCUSSION

The demo uses OpenGL and currently runs on the Windows platform using a Pentium 4 2.26GHz with ATI Radeon 9800 at a speed of 15FPS. Screenshots are included in the Screenshots section. Limitations of the demo implementation include a lack of flow interaction with the environment and using periodic boundary conditions.

One of the advantages of classic LBM is its adaptability to graphics hardware acceleration. The GPU has been shown to accelerate the performance by a factor of ~50 in some cases (Wei, Li, and Kaufman 2003). The view frustum-mapped LBM method should be amenable to similar enhancements. The differences from conventional LBM lie in distorted coordinate transformations and camera-related LBM grid recalculations. Coordinate transformations can be handled on GPU hardware by using 1D texture lookups for algorithm functions (for transforming from world to grid coordinates) and using GPU matrix multiplication. Camera-related transforms would be more complicated and may require two steps: going from old grid to world coordinates and then to new grid coordinates.

CONCLUSION

Due to its promising performance and realistic airflow effect appearance, view frustum-mapped LBM presents a promising alternative to conventional LBM for the purpose of airflow effects in an open, freely navigable 3D world. Furthermore, even disregarding absolute performance, frustum-mapped LBM allows for a greater range of resolution and simulation volume than conventional LBM.

FUTURE DIRECTIONS

The project can be improved as follows. Ways can be found to accelerate the camera movement/rotation-related LBM grid readjustment. Also, the LBM calculations can be moved to GPU hardware similarly to (Wei et al. 2003). This would provide a more realistic basis for comparing performance. Finally, simulation instabilities and ways to handle momentum vs. distance tradeoffs (time and space distortion) could be further explored.

REFERENCES

R. Fedkiw, J. Stam, and H. Jensen, 2001. Visual simulation of
smoke. *Proceedings of SIGGRAPH* 2001: 129–136.

N. Foster and D. Metaxas,
1997. Modeling
the motion of a hot, turbulent gas.
*Proceedings of SIGGRAPH* 1997:
181–188.

U. Frisch, B. Hasslacher, and Y. Pomeau, 1986. Lattice-gas automata for the Navier-Stokes Equation. Phys. Rev. Lett. 56(14): 1505-1508.

J. Hardy, Y. Pomeau, and O. de
Pazzis, 1973.
Time evolution of a two-dimensional model system: Invariant states and
time correlation functions. *J. Math. Phys.* 14(12): 1746-1759.

K. Perlin, 1985. An image
synthesizer. *Proceedings of SIGGRAPH* 19(3):
287–296.

D. H. Rothman and S. Zaleski, 1997.
*Lattice-gas cellular automata:
Simple models of complex hydrodynamics*.

J. Stam, 1999. Stable fluids.
*Proceedings of SIGGRAPH* 1999:
121–128.

Xiaoming Wei, Ye Zhao, Zhe Fan, Wei Li, Suzanne Yoakum-Stover and Arie Kaufman.
Blowing in the w*ACM SIGGRAPH/EUROGRAPHICS Symposium on
Computer Animation *2003: 75-85.

Xiaoming Wei, Wei Li, and Arie Kaufman, 2003. Implementing lattice boltzmann computation on graphics
hardware. *The Visual Computer *2003.

Xiaoming Wei, Wei Li, and Arie Kaufman, 2003. Interactive flowing of
highly viscous volumes in virtual environments. *IEEE Virtual Reality* 2003: 281-282.

Xiaoming Wei, Wei Li, and Arie Kaufman, 2003. Melting and flowing of viscous
volumes. *Computer Animation and Social Agents
2003*: 54-59.

Xiaoming Wei, Wei Li, Klaus Mueller, and
Arie Kaufman, 2003. The lattice-boltzmann method for gaseous phenomena. *IEEE Transactions on Visualization and
Computer Graphics*.

Xiaoming Wei, Wei Li, Klaus Mueller, and
Arie Kaufman, 2002. Simulating fire with
texture splats. *IEEE Visualization *2002: 227-237.

D. Weiskopf, M. Hopf, and T. Ertl, 2001. Hardware-accelerated visualization of
time-varying 2D and 3D vector fields by texture advection via programmable
per-pixel operations. *Workshop on Vision, Modeling, and
Visualization VMV* ’01: 439-446.

J. Wejchert and D. Haumann, 1991.
Animation aerodynamics. *Proceedings of SIGGRAPH* 25(4):
19–22.

Dieter A. Wolf-Gladrow, 2000. *Lattice-gas cellular automata and
lattice-boltzmann models, An
Introduction*. Springer-Verlag.

SCREENSHOTS

The world with leaves blowing. The LBM grid projected onto screen space.

An “outsider” view of the frustum-mapped LBM grid.

Wireframe view of the procedural world.