Implementation of the 'Hierarchical Hash Grids' coarse collision detection algorithm.
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 uniquesized cells. Spatial partitioning is achieved by assigning every rigid body to exactly one cell in exactly one grid  that is the grid with the smallest cells that are larger than the rigid body (more precisely cells that are larger than the longest edge of the rigid body's axisaligned bounding box). As a consequence, the collision detection is reduced to only checking body's that are assigned to spatially directly adjacent cells.
Key features of this implementation are not only an averagecase 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 bodies of the underlying simulation. Also, arbitrary bodies can be added and removed in constant time, O(1). Consequently, the coarse collision detection algorithm based on these hierarchical hash grids is especially wellsuited for largescale simulations involving very large numbers of bodies.
For further information and a much more detailed explanation of this algorithm see http://www10.informatik.unierlangen.de/Publications/Theses/2009/Schornbaum_SA09.pdf
#include <HashGrids.h>
Classes  
class  HashGrid 
Implementation of the hash grid data structure. More...  
Public Member Functions  
Constructor  
HashGrids (BodyStorage &globalStorage, BodyStorage &bodystorage, BodyStorage &bodystorageShadowCopies)  
Constructor for the HashGrids class. More...  
Destructor  
~HashGrids ()  
Destructor for the HashGrids class. More...  
Add/remove functions  
void  add (BodyID body) 
Registering a rigid body with the coarse collision detector. More...  
void  remove (BodyID body) 
Deregistering a rigid body from the coarse collision detector. More...  
int  getObservedBodyCount () const 
Public Member Functions inherited from walberla::pe::ccd::ICCD  
virtual  ~ICCD () 
PossibleContacts &  getPossibleContacts () 
Static Public Attributes  
static const size_t  xCellCount = 16 
The initial number of cells in xdirection of a newly created hash grid. More...  
static const size_t  yCellCount = 16 
The initial number of cells in ydirection of a newly created hash grid. More...  
static const size_t  zCellCount = 16 
The initial number of cells in zdirection of a newly created hash grid. More...  
static const size_t  cellVectorSize = 16 
The initial storage capaciy of a newly created grid cell body container. More...  
static const size_t  occupiedCellsVectorSize = 256 
The initial storage capacity of the gridglobal vector. More...  
static const size_t  minimalGridDensity = 8 
The minimal ratio of cells to bodies that must be maintained at any time. More...  
static const size_t  gridActivationThreshold = 32 
Activation threshold for the hierarchical hash grids coarse collision detection algorithm. More...  
static const real_t  hierarchyFactor = real_c(2) 
The constant factor by which the cell size of any two successive grids differs. More...  
static uint64_t  intersectionTestCount = 0 
Private Types  
typedef std::vector< BodyID >  BodyVector 
Vector for storing (handles to) rigid bodies. More...  
typedef std::list< HashGrid * >  GridList 
List for storing all the hash grids that are in use. More...  
Private Member Functions  
Add functions  
void  addGrid (BodyID body) 
Adds a body to the hierarchical hash grids data structure. More...  
void  addList (BodyID body) 
Adds a body to the data structure (the usage of hash grids is not yet activated!). More...  
Private Attributes  
Member variables  
BodyStorage &  globalStorage_ 
Reference to the global body storage. More...  
BodyStorage &  bodystorage_ 
Reference to the central body storage. More...  
BodyStorage &  bodystorageShadowCopies_ 
Reference to the body storage containing body shadow copies. More...  
BodyVector  bodiesToAdd_ 
Vector of all bodies to be added to the HHG data structure. More...  
BodyVector  nonGridBodies_ 
Vector of all unassigned rigid bodies. More...  
GridList  gridList_ 
List of all grids that form the hierarchy. More...  
bool  gridActive_ 
Grid activation flag. More...  
int  observedBodyCount_ 
Utility functions  
void  clear () 
Clears the coarse collision detector. More...  
void  reloadBodies () 
clears all bodies from the hash grid and reloads bodies from bodystorage and shadowbodystorage More...  
virtual PossibleContacts &  generatePossibleContacts (WcTimingTree *tt=NULL) 
Contact generation between colliding rigid bodies. More...  
void  update (WcTimingTree *tt=NULL) 
Updates all hash grids and reassigns bodies. More...  
bool  active () const 
template<typename BodyTuple >  
BodyID  getClosestBodyIntersectingWithRay (const raytracing::Ray &ray, const AABB &blockAABB, real_t &t, Vec3 &n, std::function< bool(const BodyID body)> isBodyVisibleFunc) const 
Determines the closest intersecting body in the underlying hash grids. More...  
template<typename Contacts >  
static void  collide (BodyID a, BodyID b, Contacts &contacts) 
Checks whether two bodies are colliding or not, and if so generates the related points of contact. More...  
static bool  powerOfTwo (size_t number) 
Checks whether a certain number is equal to a power of two. More...  
Additional Inherited Members  
Protected Attributes inherited from walberla::pe::ccd::ICCD  
PossibleContacts  contacts_ 

private 
Vector for storing (handles to) rigid bodies.

private 
List for storing all the hash grids that are in use.
This data structure is used to represent the grid hierarchy. All hash grids are stored in ascending order by the size of their cells.
walberla::pe::ccd::HashGrids::HashGrids  (  BodyStorage &  globalStorage, 
BodyStorage &  bodystorage,  
BodyStorage &  bodystorageShadowCopies  
) 
Constructor for the HashGrids class.
bodystorage  Reference to the general body storage. 
Note that all (local, global and remote) must be contained in the body storage.
Constructor for the HashGrids class.
bodystorage  Reference to the central body storage. 
bodystorageShadowCopies  Reference to the body storage containing all body shadow copies. 
walberla::pe::ccd::HashGrids::~HashGrids  (  ) 
Destructor for the HashGrids class.

inline 

inline 
Registering a rigid body with the coarse collision detector.
body  The body to be registered with the coarse collision detector. 
This function is a requirement for all coarse collision detectors. It is automatically called every time a new rigid body is added to the simulation world.

private 
Adds a body to the hierarchical hash grids data structure.
body  The body that is about to be added to the hierarchical hash grids data structure. 
If the usage of hierarchical hash grids is activated, this function is called every time a new rigid body is added to the data structure. It may also be called during the update phase.

private 
Adds a body to the data structure (the usage of hash grids is not yet activated!).
body  The body that is about to be added to the data structure. 
As long as the number of bodies is lessorequal than specified by gridActivationThreshold, this function is called every time a new rigid body is added to the data structure. The body then is stored in nonGridBodies_  so that later during the detection step pairwise collision checks for all bodies stored in nonGridBodies_ can be performed.
However, the moment the threshold is exceeded, all bodies are removed from the array and finally added to the grid hierarchy  thereby creating the initial set of hash grids which are adapted to the just inserted bodies. Once this has happened, the usage of the hierarchical hash grids is activated irrevocably, which means the coarse collision detection phase will continue to use the hierarchical hash grids, even if removing bodies from the simulation might cause the total number of bodies to again drop below the threshold.
void walberla::pe::ccd::HashGrids::clear  (  ) 
Clears the coarse collision detector.

inlinestaticprotected 
Checks whether two bodies are colliding or not, and if so generates the related points of contact.
a  The first body. 
b  The second body. 
contacts  Contact container for the generated contacts. 

virtual 
Contact generation between colliding rigid bodies.
This function generates all contacts between all registered rigid bodies. The contacts are added to the contact container which can be retrieved via getPossibleContacts().
Implements walberla::pe::ccd::ICCD.
BodyID walberla::pe::ccd::HashGrids::getClosestBodyIntersectingWithRay  (  const raytracing::Ray &  ray, 
const AABB &  blockAABB,  
real_t &  t,  
Vec3 &  n,  
std::function< bool(const BodyID body)>  isBodyVisibleFunc  
)  const 
Determines the closest intersecting body in the underlying hash grids.
ray  Ray getting shot through those grids. 
blockAABB  AABB of the block the grids correspond to. 
t  Reference for the distance. 
n  Reference for the intersetion normal. 

inlinevirtual 
Implements walberla::pe::ccd::ICCD.

inlinestaticprivate 
Checks whether a certain number is equal to a power of two.
number  The number that is about to be checked. 
This function is used to ensure that the number of cells in each coordinate dimension of a hash grid is equal to a power of two so that the modulo calculations required for the hash value computation can be replaced by bitwise AND operations.

virtual 
clears all bodies from the hash grid and reloads bodies from bodystorage and shadowbodystorage
Reimplemented from walberla::pe::ccd::ICCD.
void walberla::pe::ccd::HashGrids::remove  (  BodyID  body  ) 
Deregistering a rigid body from the coarse collision detector.
body  The body to be deregistered from the coarse collision detector. 
This function is a requirement for all coarse collision detectors. It is automatically called every time a rigid body is removed from the simulation world.
void walberla::pe::ccd::HashGrids::update  (  WcTimingTree *  tt = NULL  ) 
Updates all hash grids and reassigns bodies.

private 
Vector of all bodies to be added to the HHG data structure.
This vector contains all bodies that were registered with the coarse collision detector and have not yet been added to the hierarchical hash grids data structure.

private 
Reference to the central body storage.

private 
Reference to the body storage containing body shadow copies.

static 
The initial storage capaciy of a newly created grid cell body container.
This value specifies the initial storage capacity reserved for every grid cell body container, i.e., the number of bodies 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 body 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$

private 
Reference to the global body storage.

static 
Activation threshold for the hierarchical hash grids coarse collision detection algorithm.
If the simulation only consists of a very small number of bodies, simply checking each body against each other body proves to be faster than involving the far more complex mechanisms of the hierarchical hash grids. In other words, despite its quadratic complexity, as long as there are only a couple of bodies present in the simulation, the naive approach of conducting pairwise checks for all existing bodies will always result in the best runtime performance. As a consequence, a threshold is introduced, and as long as the number of bodies is lessorequal than specified by this threshold value, no hierarchy of hash grids is constructed and thus no detection algorithm based on grids is applied.
Possible settings: any integral value greaterorequal to 0.

private 
Grid activation flag.
This flag indicates whether the detection algorithm based on hierarchical hash grids is activated. If the simulation only consists of a very small number of bodies, each body is simply checked against every other body. This strategy proves to be faster than involving the far more complex mechanisms of the hierarchical hash grids.

private 
List of all grids that form the hierarchy.
The grids in this list are sorted in ascending order by the size of their cells.

static 
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 inbetween 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 bodies 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 bodies are assigned to one single cell, but overall more grids have to be created. Hence, the number of bodies that are stored in one single cell is inversely proportional to the number of grids which are in use. Unfortunately, minimizing the number of bodies 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.

static 

static 
The minimal ratio of cells to bodies that must be maintained at any time.
This minimalGridDensity specifies the minimal ratio of cells to bodies that is allowed before a grid grows.
In order to handle an initially unknown and ultimately arbitrary number of bodies, 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 bodies are inserted. Therefore, if by inserting a body into a hash grid the associated grid density  that is the ratio of cells to bodies  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.

private 
Vector of all unassigned rigid bodies.
This vector contains all bodies that are not assigned to any grid in the hierarchy. A body is not assigned to any grid if the body is infinite in size or if the detection algorithm based on hierarchical hash grids has not yet been activated (see gridActive_).

private 

static 
The initial storage capacity of the gridglobal vector.
This value specifies the initial storage capacity of the gridglobal vector that keeps track of all bodyoccupied cells. As long as at least one body is assigned to a certain cell, this cell is recored in a gridglobal list that keeps track of all bodyoccupied cells in order to avoid iterating through all grid cells whenever all bodies that are stored in the grid need to be addressed.

static 
The initial number of cells in xdirection of a newly created hash grid.
This value represents the initial number of cells of a newly created hash grid in xdirection. The larger the value (i.e. the greater the number of cells of every newly created hash grid), the more memory is required for the storage of the hash grid. Since the size of a hash grid is increased at runtime in order to adapt to the number of currently inserted bodies, 16x16x16 is a suitable choice for the initial size of a newly created hash grid  it already consists of four thousand cells, yet only requires a few hundred kilobytes of memory. Note that the initial number of cells must both be greaterorequal to 4 and equal to a power of two. Also note that the initial number of cells does not necessarily have to be equal for all three coordinate directions.

static 
The initial number of cells in ydirection of a newly created hash grid.
This value represents the initial number of cells of a newly created hash grid in ydirection. The larger the value (i.e. the greater the number of cells of every newly created hash grid), the more memory is required for the storage of the hash grid. Since the size of a hash grid is increased at runtime in order to adapt to the number of currently inserted bodies, 16x16x16 is a suitable choice for the initial size of a newly created hash grid  it already consists of four thousand cells, yet only requires a few hundred kilobytes of memory. Note that the initial number of cells must both be greaterorequal to 4 and equal to a power of two. Also note that the initial number of cells does not necessarily have to be equal for all three coordinate directions.

static 
The initial number of cells in zdirection of a newly created hash grid.
This value represents the initial number of cells of a newly created hash grid in zdirection. The larger the value (i.e. the greater the number of cells of every newly created hash grid), the more memory is required for the storage of the hash grid. Since the size of a hash grid is increased at runtime in order to adapt to the number of currently inserted bodies, 16x16x16 is a suitable choice for the initial size of a newly created hash grid  it already consists of four thousand cells, yet only requires a few hundred kilobytes of memory. Note that the initial number of cells must both be greaterorequal to 4 and equal to a power of two. Also note that the initial number of cells does not necessarily have to be equal for all three coordinate directions.