walberla::pe::ccd::HashGrids Class Reference

## Detailed Description

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 unique-sized 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 axis-aligned 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 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 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 well-suited for large-scale simulations involving very large numbers of bodies.

For further information and a much more detailed explanation of this algorithm see http://www10.informatik.uni-erlangen.de/Publications/Theses/2009/Schornbaum_SA09.pdf

#include <HashGrids.h>

Inheritance diagram for walberla::pe::ccd::HashGrids:

## 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...

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 ()

PossibleContactsgetPossibleContacts ()

## Static Public Attributes

static const size_t xCellCount = 16
The initial number of cells in x-direction of a newly created hash grid. More...

static const size_t yCellCount = 16
The initial number of cells in y-direction of a newly created hash grid. More...

static const size_t zCellCount = 16
The initial number of cells in z-direction 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 grid-global 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< BodyIDBodyVector
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

Adds a body to the hierarchical hash grids data structure. More...

Adds a body to the data structure (the usage of hash grids is not yet activated!). More...

## Private Attributes

Member variables
BodyStorageglobalStorage_
Reference to the global body storage. More...

BodyStoragebodystorage_
Reference to the central body storage. More...

Reference to the body storage containing body shadow copies. More...

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...

clears all bodies from the hash grid and reloads bodies from bodystorage and shadowbodystorage More...

virtual PossibleContactsgeneratePossibleContacts (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...

Protected Attributes inherited from walberla::pe::ccd::ICCD
PossibleContacts contacts_

## ◆ BodyVector

 typedef std::vector walberla::pe::ccd::HashGrids::BodyVector
private

Vector for storing (handles to) rigid bodies.

## ◆ GridList

 typedef std::list walberla::pe::ccd::HashGrids::GridList
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.

## ◆ HashGrids()

 walberla::pe::ccd::HashGrids::HashGrids ( BodyStorage & globalStorage, BodyStorage & bodystorage, BodyStorage & bodystorageShadowCopies )

Constructor for the HashGrids class.

Parameters
 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.

Parameters
 bodystorage Reference to the central body storage. bodystorageShadowCopies Reference to the body storage containing all body shadow copies.

## ◆ ~HashGrids()

 walberla::pe::ccd::HashGrids::~HashGrids ( )

Destructor for the HashGrids class.

## ◆ active()

 bool walberla::pe::ccd::HashGrids::active ( ) const
inline

 void walberla::pe::ccd::HashGrids::add ( BodyID body )
inline

Registering a rigid body with the coarse collision detector.

Parameters
 body The body to be registered with the coarse collision detector.
Returns
void

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.

 void walberla::pe::ccd::HashGrids::addGrid ( BodyID body )
private

Adds a body to the hierarchical hash grids data structure.

Parameters
 body The body that is about to be added to the hierarchical hash grids data structure.
Returns
void

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.

 void walberla::pe::ccd::HashGrids::addList ( BodyID body )
private

Adds a body to the data structure (the usage of hash grids is not yet activated!).

Parameters
 body The body that is about to be added to the data structure.
Returns
void

As long as the number of bodies is less-or-equal 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.

## ◆ clear()

 void walberla::pe::ccd::HashGrids::clear ( )

Clears the coarse collision detector.

Returns
void

## ◆ collide()

template<typename Contacts >
 void walberla::pe::ccd::HashGrids::collide ( BodyID a, BodyID b, Contacts & contacts )
inlinestaticprotected

Checks whether two bodies are colliding or not, and if so generates the related points of contact.

Parameters
 a The first body. b The second body. contacts Contact container for the generated contacts.
Returns
void

## ◆ generatePossibleContacts()

 PossibleContacts & walberla::pe::ccd::HashGrids::generatePossibleContacts ( WcTimingTree * tt = NULL )
virtual

Contact generation between colliding rigid bodies.

Returns
Vector of possible contacts.

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.

## ◆ getClosestBodyIntersectingWithRay()

template<typename BodyTuple >
 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.

Parameters
 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.
Returns
BodyID of closest body, NULL if none found.

## ◆ getObservedBodyCount()

 int walberla::pe::ccd::HashGrids::getObservedBodyCount ( ) const
inlinevirtual

## ◆ powerOfTwo()

 bool walberla::pe::ccd::HashGrids::powerOfTwo ( size_t number )
inlinestaticprivate

Checks whether a certain number is equal to a power of two.

Parameters
 number The number that is about to be checked.
Returns
true if the number is equal to a power of two, false if not.

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

Returns
void

Reimplemented from walberla::pe::ccd::ICCD.

## ◆ remove()

 void walberla::pe::ccd::HashGrids::remove ( BodyID body )

Deregistering a rigid body from the coarse collision detector.

Parameters
 body The body to be deregistered from the coarse collision detector.
Returns
void

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.

## ◆ update()

 void walberla::pe::ccd::HashGrids::update ( WcTimingTree * tt = NULL )

Updates all hash grids and reassigns bodies.

## Member Data Documentation

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.

## ◆ bodystorage_

 BodyStorage& walberla::pe::ccd::HashGrids::bodystorage_
private

Reference to the central body storage.

private

Reference to the body storage containing body shadow copies.

## ◆ cellVectorSize

 const size_t walberla::pe::ccd::HashGrids::cellVectorSize = 16
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$


## ◆ globalStorage_

 BodyStorage& walberla::pe::ccd::HashGrids::globalStorage_
private

Reference to the global body storage.

## ◆ gridActivationThreshold

 const size_t walberla::pe::ccd::HashGrids::gridActivationThreshold = 32
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 less-or-equal 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 greater-or-equal to 0.

## ◆ gridActive_

 bool walberla::pe::ccd::HashGrids::gridActive_
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.

## ◆ gridList_

 GridList walberla::pe::ccd::HashGrids::gridList_
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.

## ◆ hierarchyFactor

 const real_t walberla::pe::ccd::HashGrids::hierarchyFactor = real_c(2)
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 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 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.

## ◆ intersectionTestCount

 uint64_t walberla::pe::ccd::HashGrids::intersectionTestCount = 0
static

## ◆ minimalGridDensity

 const size_t walberla::pe::ccd::HashGrids::minimalGridDensity = 8
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.

## ◆ nonGridBodies_

 BodyVector walberla::pe::ccd::HashGrids::nonGridBodies_
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_).

## ◆ observedBodyCount_

 int walberla::pe::ccd::HashGrids::observedBodyCount_
private

## ◆ occupiedCellsVectorSize

 const size_t walberla::pe::ccd::HashGrids::occupiedCellsVectorSize = 256
static

The initial storage capacity of the grid-global vector.

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

## ◆ xCellCount

 const size_t walberla::pe::ccd::HashGrids::xCellCount = 16
static

The initial number of cells in x-direction of a newly created hash grid.

This value represents the initial number of cells of a newly created hash grid in x-direction. 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 greater-or-equal 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.

## ◆ yCellCount

 const size_t walberla::pe::ccd::HashGrids::yCellCount = 16
static

The initial number of cells in y-direction of a newly created hash grid.

This value represents the initial number of cells of a newly created hash grid in y-direction. 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 greater-or-equal 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.

## ◆ zCellCount

 const size_t walberla::pe::ccd::HashGrids::zCellCount = 16
static

The initial number of cells in z-direction of a newly created hash grid.

This value represents the initial number of cells of a newly created hash grid in z-direction. 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 greater-or-equal 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.

The documentation for this class was generated from the following files: