Implementation of the 'Hierarchical Hash Grids' coarse collision detection algorithm.
This is a port of the pe implementation (src/pe/ccd/HashGrids.h) for mesa_pd.
The 'Hierarchical Hash Grids' coarse collision detection algorithm is based on a spatial partitioning scheme that uses a hierarchy of uniform, hash storage based grids. Uniform grids subdivide the simulation space into cubic cells. A hierarchy of spatially superimposed grids provides a set of grids with each grid subdividing the very same space, however possessing different and thus unique-sized cells. Spatial partitioning is achieved by assigning every rigid particle to exactly one cell in exactly one grid - that is the grid with the smallest cells that are larger than the rigid particle (more precisely cells that are larger than the longest edge of the rigid particle's axis-aligned bounding box). As a consequence, the collision detection is reduced to only checking particle's that are assigned to spatially directly adjacent cells.
Key features of this implementation are not only an average-case computational complexity of order O(N) as well as a space complexity of order O(N), but also a short actual runtime combined with low memory consumption. Moreover, the data structure representing the hierarchy of grids has the ability to, at runtime, automatically and perfectly adapt to the particles of the underlying simulation. Also, arbitrary particles can be added and removed in constant time, O(1). Consequently, the coarse collision detection algorithm based on these hierarchical hash grids is especially well-suited for large-scale simulations involving very large numbers of particles.
For further information and a much more detailed explanation of this algorithm see https://www10.cs.fau.de/publications/theses/2009/Schornbaum_SA_2009.pdf
| constexpr size_t walberla::mesa_pd::data::HashGrids::cellVectorSize = 16 |
|
staticconstexpr |
The initial storage capacity of a newly created grid cell particle container.
This value specifies the initial storage capacity reserved for every grid cell particle container, i.e., the number of particles that can initially be assigned to a grid cell with the need to increase the storage capacity. The smaller this number, the more likely the storage capacity of a particle container must be increased, leading to potentially costly reallocation operations, which generally involve the entire storage space to be copied to a new location. The greater this number, the more memory is required. Rule of thumb:
\f$ cellVectorSize = 2 \cdot hierarchyFactor^3 \f$
| constexpr real_t walberla::mesa_pd::data::HashGrids::hierarchyFactor = real_t(2) |
|
staticconstexpr |
The constant factor by which the cell size of any two successive grids differs.
This factor specifies the size difference of two successive grid levels of the hierarchical hash grids. The grid hierarchy is constructed such that the cell size of any two successive grids differs by a constant factor - the hierarchy factor hierarchyFactor. As a result, the cell size \( c_k \) of grid \( k \) can be expressed as:
\f$ c_k = c_0 \cdot hierarchyFactor^k \f$.
Note that the hierarchy does not have to be dense, which means, if not every valid cell size that can be generated is required, some in-between grids are not created. Consequently, the cell size of two successive grids differs by a factor of \( hierarchyFactor^x \), with x being an integral value that is not necessarily equal to 1.
The larger the ratio between the cell size of two successive grids, the more particles are potentially assigned to one single cell, but overall fewer grids have to be used. On the other hand, the smaller the ratio between the cell size of two successive grids, the fewer particles are assigned to one single cell, but overall more grids have to be created. Hence, the number of particles that are stored in one single cell is inversely proportional to the number of grids which are in use. Unfortunately, minimizing the number of particles that are potentially assigned to the same cell and at the same time also minimizing the number of grids in the hierarchy are two opposing goals. In general - based on the evaluation of a number of different scenarios - the best choice seems to be a hierarchy factor that is equal to 2.0.
Possible settings: any floating point value that is greater than 1.0.
| constexpr size_t walberla::mesa_pd::data::HashGrids::minimalGridDensity = 8 |
|
staticconstexpr |
The minimal ratio of cells to particles that must be maintained at any time.
This minimalGridDensity specifies the minimal ratio of cells to particles that is allowed before a grid grows.
In order to handle an initially unknown and ultimately arbitrary number of particles, each hash grid, starting with a rather small number of cells at the time of its creation, must have the ability to grow as new particles are inserted. Therefore, if by inserting a particle into a hash grid the associated grid density - that is the ratio of cells to particles - drops below the threshold specified by minimalGridDensity, the number of cells in each coordinate direction is doubled (thus the total number of grid cells is increased by a factor of 8).
Possible settings: any integral value greater than 0.