Detailed Description

Implementation of the hash grid data structure.

Classes
struct	Cell
	Data structure for representing a cell in the hash grid (used by the 'Hierarchical Hash Grids' coarse collision detection algorithm). More...

Public Member Functions
Constructor
	HashGrid (real_t cellSpan)
	Constructor for the HashGrid class. More...

Destructor
	~HashGrid ()
	Destructor for the HashGrid class. More...

Add/remove functions
void	add (BodyID body)
	Adds a body to this hash grid. More...

void	remove (BodyID body)
	Removes a body from this hash grid. More...

Private Types
using	offset_t = long
	The signed integer type that is used for storing offsets to neighboring cells. More...

using	CellVector = std::vector< Cell * >
	Vector for storing pointers to (body-occupied) cells. More...

Utility functions
static const int	BLOCKCELL_NORMAL_INDETERMINATE = 3

void	update (BodyID body)
	Updates the cell association of a body that is assigned to this grid. More...

template<typename Contacts >
size_t	process (BodyID **gridBodies, Contacts &contacts) const
	Processes this hash grid for colliding bodies. More...

template<typename Contacts >
void	processBodies (BodyID *bodies, size_t bodyCount, Contacts &contacts) const
	Checks all the bodies that are stored in bodies for collisions with the bodies that are stored in this grid. More...

template<typename BodyTuple >
BodyID	getRayIntersectingBody (const raytracing::Ray &ray, const AABB &blockAABB, real_t &t, Vec3 &n, std::function< bool(const BodyID body)> isBodyVisibleFunc) const
	Calculates ray-cell intersections and determines the closest body to the ray origin. More...

template<typename BodyTuple >
BodyID	getBodyIntersectionForBlockCell (const Vector3< int32_t > &blockCell, const int8_t cellNormalAxis, const int8_t cellNormalDir, const raytracing::Ray &ray, real_t &t_closest, Vec3 &n_closest, std::function< bool(const BodyID body)> isBodyVisibleFunc) const
	Computes closest ray-body intersection of cell with center at point x,y,z and neighboring ones. More...

void	clear ()
	Clears the hash grid. More...

void	initializeNeighborOffsets ()
	Sets up the neighborhood relationships for all grid cells. More...

size_t	hash (BodyID body) const
	Computes the hash value (= cell association) of a given rigid body. More...

size_t	hashPoint (real_t x, real_t y, real_t z) const
	Computes the hash for a given point. More...

void	add (BodyID body, Cell *cell)
	Adds a body to a specific cell in this hash grid. More...

void	remove (BodyID body, Cell *cell)
	Removes a body from a specific cell in this hash grid. More...

void	enlarge ()
	Increases the number of cells used by this hash grid. More...

Member variables
Cell *	cell_
	Linear array of cells representing the three-dimensional hash grid. More...

size_t	xCellCount_
	Number of cells allocated in x-axis direction. More...

size_t	yCellCount_
	Number of cells allocated in y-axis direction. More...

size_t	zCellCount_
	Number of cells allocated in z-axis direction. More...

size_t	xHashMask_
	Bit-mask required for the hash calculation in x-axis direction (xCellCount_ - 1). More...

size_t	yHashMask_
	Bit-mask required for the hash calculation in y-axis direction (yCellCount_ - 1). More...

size_t	zHashMask_
	Bit-mask required for the hash calculation in z-axis direction (zCellCount_ - 1). More...

size_t	xyCellCount_
	Number of cells allocated in x-axis direction multiplied by the number of cells allocated in y-axis direction. More...

size_t	xyzCellCount_
	Total number of allocated cells. More...

size_t	enlargementThreshold_
	The enlargement threshold - the moment the number of assigned bodies exceeds this threshold, the size of this hash grid is increased. More...

real_t	cellSpan_
	The grid's cell size (edge length of the underlying cubic grid cells). More...

real_t	inverseCellSpan_
	The inverse cell size. More...

CellVector	occupiedCells_
	A grid-global list that keeps track of all body-occupied cells. More...

size_t	bodyCount_
	Number of bodies assigned to this hash grid. More...

offset_t	stdNeighborOffset_ [27]
	Array of offsets to the neighboring cells (valid for all the inner cells of the hash grid). More...

Member Typedef Documentation

◆ CellVector

using walberla::pe::ccd::HashGrids::HashGrid::CellVector = std::vector<Cell *>

private

Vector for storing pointers to (body-occupied) cells.

◆ offset_t

using walberla::pe::ccd::HashGrids::HashGrid::offset_t = long

private

The signed integer type that is used for storing offsets to neighboring cells.

Constructor & Destructor Documentation

◆ HashGrid()

walberla::pe::ccd::HashGrids::HashGrid::HashGrid ( real_t cellSpan )

explicit

Constructor for the HashGrid class.

◆ ~HashGrid()

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

Destructor for the HashGrid class.

Member Function Documentation

◆ add() [1/2]

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

inline

Adds a body to this hash grid.

Parameters

body	The body that is about to be added to this hash grid.

Returns: void

This function is called every time a new rigid body is added to this grid. If adding the body will cause the total number of bodies assigned to this grid to exceed the enlargement threshold, the size of this hash grid is increased in order to maintain a fixed minimal grid density (= ratio of cells to bodies). This function may also be called during the update phase.

◆ add() [2/2]

void walberla::pe::ccd::HashGrids::HashGrid::add	(	BodyID	body,
		Cell *	cell
	)

private

Adds a body to a specific cell in this hash grid.

Parameters

body	The body that is about to be added to this hash grid.
cell	The cell the body is assigned to.

Returns: void

◆ clear()

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

Clears the hash grid.

Returns: void

This function removes all (the handles to) the bodies that are assigned to this hash grid from the body containers of the grid's cells.

◆ enlarge()

void walberla::pe::ccd::HashGrids::HashGrid::enlarge ( )

private

Increases the number of cells used by this hash grid.

Returns: void

In order to handle an initially unknown and ultimately arbitrary number of bodies, the 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 this hash grid the associated grid density - that is the ratio of cells to bodies - drops below the threshold specified by minimalGridDensity, or in other words, if the number of bodies grows larger than specified by enlargementThreshold_, the number of cells in each coordinate direction is doubled (thus the total number of grid cells is increased by a factor of 8).

◆ getBodyIntersectionForBlockCell()

template<typename BodyTuple >

BodyID walberla::pe::ccd::HashGrids::HashGrid::getBodyIntersectionForBlockCell	(	const Vector3< int32_t > &	blockCell,
		const int8_t	cellNormalAxis,
		const int8_t	cellNormalDir,
		const raytracing::Ray &	ray,
		real_t &	t_closest,
		Vec3 &	n_closest,
		std::function< bool(const BodyID body)>	isBodyVisibleFunc
	)		const

Computes closest ray-body intersection of cell with center at point x,y,z and neighboring ones.

Parameters

blockCell	index of cell within block grid.
ray	Ray being casted trough grid.
t_closest	Distance of closest object from ray origin. Will be updated if closer body found.
n_closest	Normal of intersection point.

Returns: BodyID of intersected body, NULL if no intersection found.

Inserts bodies of specified cell into bodiesContainer and additionally considers bodies in neighboring cells in all negative coordinate direction to take bodies in consideration, which protrude from their cell into the intersected cell (and thus, possibly intersect with the ray as well).

◆ getRayIntersectingBody()

template<typename BodyTuple >

BodyID walberla::pe::ccd::HashGrids::HashGrid::getRayIntersectingBody	(	const raytracing::Ray &	ray,
		const AABB &	blockAABB,
		real_t &	t_closest,
		Vec3 &	n_closest,
		std::function< bool(const BodyID body)>	isBodyVisibleFunc
	)		const

Calculates ray-cell intersections and determines the closest body to the ray origin.

Parameters

ray	Ray getting shot through this grid.
blockAABB	AABB of the block this grid corresponds to.
t_closest	Reference for the distance.
n_closest	Reference for the intersection normal.

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

This function calculates ray-cell intersections and the closest body in those cells. Also, neighboring cells in all negative coordinate directions are regarded to take bodies in consideration, which protrude from their cell into the intersected cell (and thus, possibly intersect with the ray as well).

◆ hash()

size_t walberla::pe::ccd::HashGrids::HashGrid::hash ( BodyID body ) const

private

Computes the hash value (= cell association) of a given rigid body.

Parameters

body	The body whose hash value is about to be calculated.

Returns: The hash value (=cell association) of the body.

◆ hashPoint()

size_t walberla::pe::ccd::HashGrids::HashGrid::hashPoint	(	real_t	x,
		real_t	y,
		real_t	z
	)		const

private

Computes the hash for a given point.

Parameters

x	X value of the point.
y	Y value of the point.
z	Z value of the point.

Returns: The hash value (=cell association) of the point.

The hash calculation uses modulo operations in order to spatially map entire blocks of connected cells to the origin of the coordinate system. This block of cells at the origin of the coordinate system that is filled with all the bodies of the simulation is referred to as the hash grid. The key feature, and ultimately the advantage, of hash grids is the fact that two adjacent cells that are located anywhere in the simulation space are mapped to two cells that are still adjacent in the hashed storage structure.

Note that the modulo calculations are replaced with fast bitwise AND operations - hence, the spatial dimensions of the hash grid must be restricted to powers of two!

◆ initializeNeighborOffsets()

void walberla::pe::ccd::HashGrids::HashGrid::initializeNeighborOffsets ( )

private

Sets up the neighborhood relationships for all grid cells.

Returns: void

This function is used to initialize the offset arrays of all grid cells. The offsets are required for ensuring fast direct access to all directly adjacent cells for each cell in the hash grid.

◆ process()

template<typename Contacts >

size_t walberla::pe::ccd::HashGrids::HashGrid::process	(	BodyID **	gridBodies,
		Contacts &	contacts
	)		const

Processes this hash grid for colliding bodies.

Parameters

gridBodies	Linear array of (handles to) all the bodies stored in this hash grid.
contacts	Contact container for the generated contacts.

Returns: The number of bodies stored in this grid - which is the number of bodies stored in gridBodies.

This function generates all contacts between all rigid bodies that are assigned to this grid. The contacts are added to the contact container contacts. Moreover, a linear array that contains (handles to) all bodies that are stored in this grid is returned in order to being able to check these bodies against other bodies that are stored in grids with larger sized cells.

◆ processBodies()

template<typename Contacts >

void walberla::pe::ccd::HashGrids::HashGrid::processBodies	(	BodyID *	bodies,
		size_t	bodyCount,
		Contacts &	contacts
	)		const

Checks all the bodies that are stored in bodies for collisions with the bodies that are stored in this grid.

Parameters

bodies	Linear array of (handles to) all the bodies that are about to be checked for collisions with the bodies that are stored in this grid.
bodyCount	The number of bodies that are stored in bodies.
contacts	Contact container for the generated contacts.

Returns: void

This function generates all contacts between the rigid bodies that are stored in bodies and all the rigid bodies that are assigned to this grid. The contacts are added to the contact container contacts.

◆ remove() [1/2]

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

inline

Removes a body from this hash grid.

Parameters

body	The body that is about to be removed from this hash grid.

Returns: void

This function is called every time a rigid body is removed from this grid. It may also be called during the update phase.

◆ remove() [2/2]

void walberla::pe::ccd::HashGrids::HashGrid::remove	(	BodyID	body,
		Cell *	cell
	)

private

Removes a body from a specific cell in this hash grid.

Parameters

body	The body that is about to be removed from this hash grid.
cell	The cell the body is removed from.

Returns: void

◆ update()

void walberla::pe::ccd::HashGrids::HashGrid::update ( BodyID body )

Updates the cell association of a body that is assigned to this grid.

Parameters

body	The body whose cell association is being updated.

Returns: void

Checks if a given rigid body can remain stored in its currently assigned cell - and if not, removes the body from this cell and reassigns it to another cell (which is identified by re-evaluating the body's hash value).

Member Data Documentation

◆ BLOCKCELL_NORMAL_INDETERMINATE

const int walberla::pe::ccd::HashGrids::HashGrid::BLOCKCELL_NORMAL_INDETERMINATE = 3

static

◆ bodyCount_

size_t walberla::pe::ccd::HashGrids::HashGrid::bodyCount_

Number of bodies assigned to this hash grid.

◆ cell_

Cell* walberla::pe::ccd::HashGrids::HashGrid::cell_

private

Linear array of cells representing the three-dimensional hash grid.

◆ cellSpan_

real_t walberla::pe::ccd::HashGrids::HashGrid::cellSpan_

The grid's cell size (edge length of the underlying cubic grid cells).

◆ enlargementThreshold_

size_t walberla::pe::ccd::HashGrids::HashGrid::enlargementThreshold_

The enlargement threshold - the moment the number of assigned bodies exceeds this threshold, the size of this hash grid is increased.

◆ inverseCellSpan_

real_t walberla::pe::ccd::HashGrids::HashGrid::inverseCellSpan_

The inverse cell size.

Required for replacing floating point divisions with multiplications during the hash computation.

◆ occupiedCells_

CellVector walberla::pe::ccd::HashGrids::HashGrid::occupiedCells_

A grid-global list that keeps track of all body-occupied cells.

The list is required in order to avoid iterating through all grid cells whenever all bodies that are stored in the grid need to be addressed.

◆ stdNeighborOffset_

offset_t walberla::pe::ccd::HashGrids::HashGrid::stdNeighborOffset_[27]

Array of offsets to the neighboring cells (valid for all the inner cells of the hash grid).

◆ xCellCount_

size_t walberla::pe::ccd::HashGrids::HashGrid::xCellCount_

private

Number of cells allocated in x-axis direction.

◆ xHashMask_

size_t walberla::pe::ccd::HashGrids::HashGrid::xHashMask_

private

Bit-mask required for the hash calculation in x-axis direction (xCellCount_ - 1).

◆ xyCellCount_

size_t walberla::pe::ccd::HashGrids::HashGrid::xyCellCount_

private

Number of cells allocated in x-axis direction multiplied by the number of cells allocated in y-axis direction.

◆ xyzCellCount_

size_t walberla::pe::ccd::HashGrids::HashGrid::xyzCellCount_

Total number of allocated cells.

◆ yCellCount_

size_t walberla::pe::ccd::HashGrids::HashGrid::yCellCount_

private

Number of cells allocated in y-axis direction.

◆ yHashMask_

size_t walberla::pe::ccd::HashGrids::HashGrid::yHashMask_

private

Bit-mask required for the hash calculation in y-axis direction (yCellCount_ - 1).

◆ zCellCount_

size_t walberla::pe::ccd::HashGrids::HashGrid::zCellCount_

private

Number of cells allocated in z-axis direction.

◆ zHashMask_

size_t walberla::pe::ccd::HashGrids::HashGrid::zHashMask_

private

Bit-mask required for the hash calculation in z-axis direction (zCellCount_ - 1).

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

Private Types

Utility functions

Member variables

Member Typedef Documentation

◆ CellVector

◆ offset_t

Constructor & Destructor Documentation

◆ HashGrid()

◆ ~HashGrid()

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ clear()

◆ enlarge()

◆ getBodyIntersectionForBlockCell()

◆ getRayIntersectingBody()

◆ hash()

◆ hashPoint()

◆ initializeNeighborOffsets()

◆ process()

◆ processBodies()

◆ remove() [1/2]

◆ remove() [2/2]

◆ update()

Member Data Documentation

◆ BLOCKCELL_NORMAL_INDETERMINATE

◆ bodyCount_

◆ cell_

◆ cellSpan_

◆ enlargementThreshold_

◆ inverseCellSpan_

◆ occupiedCells_

◆ stdNeighborOffset_

◆ xCellCount_

◆ xHashMask_

◆ xyCellCount_

◆ xyzCellCount_

◆ yCellCount_

◆ yHashMask_

◆ zCellCount_

◆ zHashMask_