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

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
BodyStorageglobalStorage_
 Reference to the global body storage. More...
 
BodyStoragebodystorage_
 Reference to the central body storage. More...
 
BodyStoragebodystorageShadowCopies_
 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 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...
 

Additional Inherited Members

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

Member Typedef Documentation

◆ BodyVector

typedef std::vector<BodyID> walberla::pe::ccd::HashGrids::BodyVector
private

Vector for storing (handles to) rigid bodies.

◆ GridList

typedef std::list<HashGrid*> 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.

Constructor & Destructor Documentation

◆ HashGrids()

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

Constructor for the HashGrids class.

Parameters
bodystorageReference 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
bodystorageReference to the central body storage.
bodystorageShadowCopiesReference to the body storage containing all body shadow copies.

◆ ~HashGrids()

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

Destructor for the HashGrids class.

Member Function Documentation

◆ active()

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

◆ add()

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

Registering a rigid body with the coarse collision detector.

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

◆ addGrid()

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

Adds a body to the hierarchical hash grids data structure.

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

◆ addList()

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
bodyThe 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
aThe first body.
bThe second body.
contactsContact 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
rayRay getting shot through those grids.
blockAABBAABB of the block the grids correspond to.
tReference for the distance.
nReference 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
numberThe 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.

◆ reloadBodies()

void walberla::pe::ccd::HashGrids::reloadBodies ( )
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
bodyThe 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

◆ bodiesToAdd_

BodyVector walberla::pe::ccd::HashGrids::bodiesToAdd_
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.

◆ bodystorageShadowCopies_

BodyStorage& walberla::pe::ccd::HashGrids::bodystorageShadowCopies_
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: