Fast grid generation

Grid points of a computational domain used for Lattice Boltzmann CFD implementations can be of a variety of different kinds. Those points representing a fluid particle ensemble are considered fluid particles, whereas other points can represent a slip wall, a no-slip wall, an inflow boundary condition, or even moving bodies. Since the grid itself is static and does not change over time, it is the changing character of the points through which a moving body's motion is manifested. Figure 1 shows fluid particles as black circles and moving body particles as red dots. Black circles overlaid with red dots signify moving body particles from previous time steps, where a lighter shade of red indicates body particles from iterations further back in time.

The grid generation in elbe is based on an efficient point in polygon (ePiP) algorithm. The ePiP method is designed for execution on massively parallel processors such as GPUs. Each computational thread is assigned with a triangle. For each triangle a local region test within the triangle's bounding box then yields the identification of body particles. To define the region of valid inner points for the triangles, it is necessary to construct separation planes between adjacent triangles, i.e. for each edge of any given triangle. With this information it is possible to assign unique parts of the body domain to triangles. As an example, consider the 2D case depicted in figure 2. In the two-dimensional domain three-dimensional triangles and planes resemble edges or lines (3D bodies resemble 2D areas). The gray body consists of five corner points and edges. Assuming a symmetrical partition of the domain, at each of these corner points (points in 2D equal the triangle's edges in 3D) half-angles can be defined in such a way that the angle between an edge and the separation plane or two body edges (triangles) equals alpha or 2 alpha, respectively. For efficiency reasons and to better apply boundary conditions to the body's particles, it is desirable to identify the first inner layer of body particles only. In figure 2 the image on the lower left shows this first-layer region in blue, green, and pink colors. The detailed magnification of the blue-green corner depicts the half-angle definition. Red dots represent the body particles.


The development of the grid generator is part of Nils Koliha's Master thesis Computation and Real-Time Rendering of Complex Multiphase Flows on GPGPU Clusters. Nils graduated in Ocean Engineering at Hamburg University of Technology in late 2013. For more information, you can contact Nils at nils.koliha(at)

  • N. Koliha, "Computation and Real-Time Rendering of Complex Multiphase Flows on GPGPU Clusters", Master thesis, 2013.
  • N. Koliha, C. Jan├čen and T. Rung, "A fast and rigorously parallel surface voxelization technique for GPGPU-accelerated CFD simulations", submitted to Communications in Computational Physics.