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 https://www10.cs.fau.de/publications/theses/2009/Schornbaum_SA_2009.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 () override
	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 override

Public Member Functions inherited from walberla::pe::ccd::ICCD
virtual	~ICCD ()=default

PossibleContacts &	getPossibleContacts ()

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 capacity 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
using	BodyVector = std::vector< BodyID >
	Vector for storing (handles to) rigid bodies. More...

using	GridList = std::list< HashGrid * >
	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 () override
	clears all bodies from the hash grid and reloads bodies from bodystorage and shadowbodystorage More...

PossibleContacts &	generatePossibleContacts (WcTimingTree *tt=nullptr) override
	Contact generation between colliding rigid bodies. More...

void	update (WcTimingTree *tt=nullptr)
	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

using walberla::pe::ccd::HashGrids::BodyVector = std::vector<BodyID>

private

Vector for storing (handles to) rigid bodies.

◆ GridList

using walberla::pe::ccd::HashGrids::GridList = std::list<HashGrid *>

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

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

◆ ~HashGrids()

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

override

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

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.

◆ addGrid()

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.

◆ 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

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 = nullptr )

overridevirtual

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

Returns: BodyID of closest body, NULL if none found.

◆ getObservedBodyCount()

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

inlineoverridevirtual

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

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

◆ reloadBodies()

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

overridevirtual

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 = nullptr )

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 capacity 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 recorded 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:

/builds/administration/walberla-website/walberla/src/pe/ccd/HashGrids.h
/builds/administration/walberla-website/walberla/src/pe/ccd/HashGrids.cpp

Detailed Description

Classes

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Utility functions

Additional Inherited Members

Member Typedef Documentation

◆ BodyVector

◆ GridList

Constructor & Destructor Documentation

◆ HashGrids()

◆ ~HashGrids()

Member Function Documentation

◆ active()

◆ add()

◆ addGrid()

◆ addList()

◆ clear()

◆ collide()

◆ generatePossibleContacts()

◆ getClosestBodyIntersectingWithRay()

◆ getObservedBodyCount()

◆ powerOfTwo()

◆ reloadBodies()

◆ remove()

◆ update()

Member Data Documentation

◆ bodiesToAdd_

◆ bodystorage_

◆ bodystorageShadowCopies_

◆ cellVectorSize

◆ globalStorage_

◆ gridActivationThreshold

◆ gridActive_

◆ gridList_

◆ hierarchyFactor

◆ intersectionTestCount

◆ minimalGridDensity

◆ nonGridBodies_

◆ observedBodyCount_

◆ occupiedCellsVectorSize

◆ xCellCount

◆ yCellCount

◆ zCellCount