Description

Utilities for Chrono multicore collision detection.

Functions
Hashing functions
template<class T >
vec3	HashMin (const T &A, const real3 &inv_bin_size_vec)
	Convert a position into bin coordinates ("lower" corner).

template<class T >
vec3	HashMax (const T &A, const real3 &inv_bin_size_vec)
	Convert a position into bin coordinates ("upper" corner).

uint	Hash_Index (const vec3 &A, const vec3 &bins_per_axis)
	Convert bin coordinates into a unique bin index value.

vec3	Hash_Decode (uint hash, const vec3 &bins_per_axis)
	Decode a bin index into its associated bin coordinates.

AABB collision functions
bool	collide (const short2 &fam_data_A, const short2 &fam_data_B)
	Check if two bodies interact using their collision family data.

bool	overlap (const real3 &Amin, const real3 &Amax, const real3 &Bmin, const real3 &Bmax)
	Check if two AABBs overlap using their min/max corners.

bool	current_bin (const real3 &Amin, const real3 &Amax, const real3 &Bmin, const real3 &Bmax, const real3 &inv_bin_size_vec, const vec3 &bins_per_axis, uint bin)

Utility functions for broadphase
ChApi vec3	Compute_Grid_Resolution (uint num_aabb, const real3 &d, real k)
	Compute broadphase grid resolution, given the total number of AABBs, the grid dimension (diagonal), and the desired density.

ChApi void	f_Count_AABB_BIN_Intersection (const uint index, const real3 &inv_bin_size, const std::vector< real3 > &aabb_min, const std::vector< real3 > &aabb_max, std::vector< uint > &bins_intersected)
	Function to Count AABB-Bin intersections.

ChApi void	f_Store_AABB_BIN_Intersection (const uint index, const vec3 &bins_per_axis, const real3 &inv_bin_size, const std::vector< real3 > &aabb_min_data, const std::vector< real3 > &aabb_max_data, const std::vector< uint > &bins_intersected, std::vector< uint > &bin_number, std::vector< uint > &aabb_number)
	Function to Store AABB-Bin Intersections.

ChApi void	f_Count_AABB_AABB_Intersection (const uint index, const real3 inv_bin_size_vec, const vec3 bins_per_axis, const std::vector< real3 > &aabb_min_data, const std::vector< real3 > &aabb_max_data, const std::vector< uint > &bin_number, const std::vector< uint > &aabb_number, const std::vector< uint > &bin_start_index, const std::vector< short2 > &fam_data, const std::vector< char > &body_active, const std::vector< char > &body_collide, const std::vector< uint > &body_id, std::vector< uint > &num_contact)
	Function to count AABB-AABB intersection.

ChApi void	f_Store_AABB_AABB_Intersection (const uint index, const real3 inv_bin_size_vec, const vec3 bins_per_axis, const std::vector< real3 > &aabb_min_data, const std::vector< real3 > &aabb_max_data, const std::vector< uint > &bin_number, const std::vector< uint > &aabb_number, const std::vector< uint > &bin_start_index, const std::vector< uint > &num_contact, const std::vector< short2 > &fam_data, const std::vector< char > &body_active, const std::vector< char > &body_collide, const std::vector< uint > &body_id, std::vector< long long > &potential_contacts)
	Function to store AABB-AABB intersections.

Utility functions for MPR narrowphase
real3	GetSupportPoint_Sphere (const real radius, const real3 &n)
	Support point for a sphere (for GJK and MPR).

real3	GetSupportPoint_Triangle (const real3 *t, const real3 &n)
	Support point for a triangle (for GJK and MPR).

real3	GetSupportPoint_Box (const real3 &B, const real3 &n)
	Support point for a box (for GJK and MPR).

real3	GetSupportPoint_Ellipsoid (const real3 &B, const real3 &n)
	Support point for an ellipsoid (for GJK and MPR).

real3	GetSupportPoint_Cylinder (const real3 &B, const real3 &n)
	Support point for a cylinder (for GJK and MPR). More...

real3	GetSupportPoint_Plane (const real3 &B, const real3 &n)
	Support point for a plane (for GJK and MPR).

real3	GetSupportPoint_Cone (const real3 &B, const real3 &n)
	Support point for a cone (for GJK and MPR). More...

real3	GetSupportPoint_Seg (const real B, const real3 &n)
	Support point for a line segment (for GJK and MPR).

real3	GetSupportPoint_Capsule (const real2 &B, const real3 &n)
	Support point for a capsule (for GJK and MPR). More...

real3	GetSupportPoint_Disk (const real B, const real3 &n)
	Support point for a disk (for GJK and MPR).

real3	GetSupportPoint_Rect (const real3 &B, const real3 &n)
	Support point for a rectangle (for GJK and MPR).

real3	GetSupportPoint_RoundedBox (const real4 &B, const real3 &n)
	Support point for a rounded box, i.e. a sphere-swept box (for GJK and MPR).

real3	GetSupportPoint_RoundedCylinder (const real4 &B, const real3 &n)
	Support point for a rounded cylinder, i.e. More...

real3	GetSupportPoint_CylindricalShell (const real3 &B, const real3 &n)
	Support point for a cylindrical shell (for GJK and MPR). More...

real3	GetSupportPoint_Convex (const int size, const real3 *convex_data, const real3 &n)
	Support point for a generic convex shape (for GJK and MPR).

real3	GetSupportPoint_Tetrahedron (const uvec4 &indices, const real3 *nodes, const real3 &n)
	Support point for a tetrahedron (for GJK and MPR).

real3	GetCenter_Sphere ()

real3	GetCenter_Triangle (const real3 *t)

real3	GetCenter_Box ()

real3	GetCenter_Ellipsoid ()

real3	GetCenter_Cylinder ()

real3	GetCenter_Plane ()

real3	GetCenter_Cone (const real3 &B)

real3	GetCenter_Convex (const int size, const real3 *convex_data)

real3	GetCenter_Tetrahedron (const uvec4 &indices, const real3 *nodes)

ChApi real3	SupportVertNoMargin (const chrono::ConvexBase *Shape, const real3 &nv, const real &envelope)

ChApi real3	LocalSupportVert (const chrono::ConvexBase *Shape, const real3 &n, const real &envelope)

ChApi real3	TransformSupportVert (const chrono::ConvexBase *Shape, const real3 &n, const real &envelope)

ChApi bool	snap_to_triangle_bary (const real3 &A, const real3 &B, const real3 &C, const real3 &P, real3 &res, real3 &barycentric)
	This utility function takes the location 'P' and snaps it to the closest point on the triangular face with given vertices (A, B, and C). More...

ChApi void	FindTriIndex (const real3 &P, const uvec4 &T, const real3 *pos_node, int &face, real3 &cb)
	Given a contact point P and a tetrahedron T compute the closest triangle to that point.

Utility functions for PRIMS narrowphase.
real3	triangle_normal (const real3 &A, const real3 &B, const real3 &C)
	This utility function returns the normal to the triangular face defined by the vertices A, B, and C. More...

ChApi bool	snap_to_triangle (const real3 &A, const real3 &B, const real3 &C, const real3 &P, real3 &res)
	This utility function takes the location 'P' and snaps it to the closest point on the triangular face with given vertices (A, B, and C). More...

ChApi bool	point_in_triangle (const real3 &A, const real3 &B, const real3 &C, const real3 &loc)
	This utility function returns a boolean indicating whether or not the specified 'loc' is inside the given triangle (with vertices A, B, C and outwards 'normal'). More...

uint	snap_to_cylinder (const real &rad, const real &hlen, real3 &loc)
	This utility function snaps the specified location to a point on a cylinder with given radius and half-length. More...

uint	box_closest_feature (const real3 &dir, const real3 &hdims)
	This utility function returns a code that indicates the closest feature of a box in the specified direction. More...

uint	snap_to_box (const real3 &hdims, real3 &loc)
	This utility function snaps the specified location to a point on a box with given half-dimensions. More...

real3	snap_to_box_face (const real3 &hdims, const real3 &pt_on_box, uint code, const real3 &pt_to_snap)
	This utility function snaps the location 'pt_to_snap' to a location on the face of this box identified by the specified 'code' and 'pt_on_box'. More...

real3	snap_to_box_edge (const real3 &hdims, const real3 &pt_on_box, uint code, const real3 &pt_to_snap)
	This utility function snaps the location 'pt_to_snap' to a location on the edge of this box identified by the specified 'code' and 'pt_on_box'. More...

void	get_edge_corners (const real3 &pt_on_edge, uint code, real3 *corners)
	This utility function fill out 'corners' with the corners of the box edge specified by 'code' and 'pt_on_edge'. More...

void	get_face_corners (const real3 &pt_on_face, uint code, real3 *corners)
	This utility function fill out 'corners' with the corners of the face specified by 'code' and 'pt_on_face'. More...

real3	get_face_normal (const real3 &pt_on_face, uint code)
	This utility function returns the box face normal (expressed in the box local frame) for the face specified by 'code' and 'pt_on_face'. More...

ChApi bool	point_vs_face (const real3 &hdims, const real3 &pt_on_face, uint code, const real3 &point, const real &separation, real3 &result, real3 &normal, real &dist)
	This utility function returns true if 'point' is no farther than 'separation' from the face of this box identified by 'pt_on_face' and 'code'; and returns false otherwise. More...

ChApi bool	segment_vs_edge (const real3 &hdims, const real3 &pt_on_edge, uint code, const real3 &pt1, const real3 &pt2, real3 &locE, real3 &locS)
	This utility function calculates the closest points between the box edge identified by 'pt_on_edge' and 'code' and a line segment between 'pt1' and 'pt2'. More...

real3	box_farthest_corner (const real3 &hdims, const real3 &dir)
	This utility function returns the corner of a box of given dimensions that is farthest in the direction 'dir', which is assumed to be given in the frame of the box.

real3	box_closest_corner (const real3 &hdims, const real3 &dir)
	This utility function returns the corner of a box of given dimensions that is closest in the direction 'dir', which is assumed to be given in the frame of the box.

ChApi int	box_intersects_box (const real3 &hdims1, const real3 &hdims2, const real3 &pos, const quaternion &rot, real separation, real3 &dir)
	This function returns an integer indicating whether or not a box1 with dimensions hdims1 intersects (or is close enough to) a second box with dimensions hdims2. More...

ChApi int	box_intersects_triangle (const real3 &hdims, const real3 &v0, const real3 &v1, const real3 &v2, real separation)
	This function returns an integer indicating whether or not a box with dimensions hdims intersects (or is close enough to) a triangle given by its vertices v0, v1, v2. More...

Function Documentation

◆ box_closest_feature()

uint chrono::ch_utils::box_closest_feature	(	const real3 &	dir,
		const real3 &	hdims
	)

inline

This utility function returns a code that indicates the closest feature of a box in the specified direction.

The direction 'dir' is assumed to be given in the frame of the box. The return code encodes the box axes that define the closest feature:

first bit (least significant) corresponds to x-axis
second bit corresponds to y-axis
third bit corresponds to z-axis

Therefore:

code = 0 indicates a degenerate direction (within a threshold)
code = 1 or code = 2 or code = 4 indicates a face
code = 3 or code = 5 or code = 6 indicates an edge
code = 7 indicates a corner

◆ box_intersects_box()

int chrono::ch_utils::box_intersects_box	(	const real3 &	hdims1,
		const real3 &	hdims2,
		const real3 &	pos,
		const quaternion &	rot,
		real	separation,
		real3 &	dir
	)

This function returns an integer indicating whether or not a box1 with dimensions hdims1 intersects (or is close enough to) a second box with dimensions hdims2.

The check is performed in the local frame of box1. The transform from the other box is given through 'pos' and 'rot'.

The return value is -1 if the two boxes overlap, +1 if they are within a distance of 'separation' from each other, and 0 if they are "far" from each other. If returning -1 or +1, 'dir' contains the direction of smallest intersection (or closest separation).

This check is performed by testing 15 possible separating planes between the two boxes (Gottschalk, Lin, Manocha - Siggraph96).

If not considering a separation value, the 15 tests use an overlap of the form: overlap = r1 + r2 - D, where r1 and r2 are the half-projections of the two boxes on the current direction and D is the projected distance between the box centers. If there's no overlap (overlap <= 0) in any direction, then the boxes do not intersect. Otherwise, we keep track of the direction of minimum overlap.

If considering a separation > 0, we simply use an overlap of the form: overlap = r1 + r2 - D + separation and use the exact same checks.

◆ box_intersects_triangle()

int chrono::ch_utils::box_intersects_triangle	(	const real3 &	hdims,
		const real3 &	v0,
		const real3 &	v1,
		const real3 &	v2,
		real	separation
	)

This function returns an integer indicating whether or not a box with dimensions hdims intersects (or is close enough to) a triangle given by its vertices v0, v1, v2.

The check is performed in the box frame and it is assumed that the triangle vertices are expressed in the box frame.

The return value is -1 if the box and triangle overlap, +1 if they are within a distance of 'separation' from each other, and 0 if they are "far" from each other.

This check is performed by testing 13 possible separating planes between the box and triangle (see Ericson).

◆ get_edge_corners()

void chrono::ch_utils::get_edge_corners	(	const real3 &	pt_on_edge,
		uint	code,
		real3 *	corners
	)

inline

This utility function fill out 'corners' with the corners of the box edge specified by 'code' and 'pt_on_edge'.

See box_closest_feature for definition of 'code.

◆ get_face_corners()

void chrono::ch_utils::get_face_corners	(	const real3 &	pt_on_face,
		uint	code,
		real3 *	corners
	)

inline

This utility function fill out 'corners' with the corners of the face specified by 'code' and 'pt_on_face'.

See box_closest_feature for definition of 'code.

◆ get_face_normal()

real3 chrono::ch_utils::get_face_normal	(	const real3 &	pt_on_face,
		uint	code
	)

inline

This utility function returns the box face normal (expressed in the box local frame) for the face specified by 'code' and 'pt_on_face'.

See box_closest_feature for definition of 'code.

◆ GetSupportPoint_Capsule()

real3 chrono::ch_utils::GetSupportPoint_Capsule	(	const real2 &	B,
		const real3 &	n
	)

inline

Support point for a capsule (for GJK and MPR).

Capsule assumed to be along Z axis with origin at center.

◆ GetSupportPoint_Cone()

real3 chrono::ch_utils::GetSupportPoint_Cone	(	const real3 &	B,
		const real3 &	n
	)

inline

Support point for a cone (for GJK and MPR).

Cone assumed to be along Z axis with origing at base center.

◆ GetSupportPoint_Cylinder()

real3 chrono::ch_utils::GetSupportPoint_Cylinder	(	const real3 &	B,
		const real3 &	n
	)

inline

Support point for a cylinder (for GJK and MPR).

Cylinder assumed to be along Z axis with origin at center.

◆ GetSupportPoint_CylindricalShell()

real3 chrono::ch_utils::GetSupportPoint_CylindricalShell	(	const real3 &	B,
		const real3 &	n
	)

inline

Support point for a cylindrical shell (for GJK and MPR).

Cylindrical shell assumed to be along Z axis with origin at center.

◆ GetSupportPoint_RoundedCylinder()

real3 chrono::ch_utils::GetSupportPoint_RoundedCylinder	(	const real4 &	B,
		const real3 &	n
	)

inline

Support point for a rounded cylinder, i.e.

a sphere-swept cylinder (for GJK and MPR). Rounded cylinder assumed to be along Z axis with origin at center.

◆ point_in_triangle()

bool chrono::ch_utils::point_in_triangle	(	const real3 &	A,
		const real3 &	B,
		const real3 &	C,
		const real3 &	loc
	)

This utility function returns a boolean indicating whether or not the specified 'loc' is inside the given triangle (with vertices A, B, C and outwards 'normal').

Locations on a triangle edge are considered to be inside.

◆ point_vs_face()

bool chrono::ch_utils::point_vs_face	(	const real3 &	hdims,
		const real3 &	pt_on_face,
		uint	code,
		const real3 &	point,
		const real &	separation,
		real3 &	result,
		real3 &	normal,
		real &	dist
	)

This utility function returns true if 'point' is no farther than 'separation' from the face of this box identified by 'pt_on_face' and 'code'; and returns false otherwise.

If the point is close enough, its projection onto the box face is returned in 'result' and the height of the point relative to the box face is returned in 'dist' (with a negative value indicating penetration, i.e. the point inside the box). 'normal' is set to the box face (pointing outwards). See box_closest_feature for definition of 'code.

◆ segment_vs_edge()

bool chrono::ch_utils::segment_vs_edge	(	const real3 &	hdims,
		const real3 &	pt_on_edge,
		uint	code,
		const real3 &	pt1,
		const real3 &	pt2,
		real3 &	locE,
		real3 &	locS
	)

This utility function calculates the closest points between the box edge identified by 'pt_on_edge' and 'code' and a line segment between 'pt1' and 'pt2'.

It returns true if the closest points are within the extent of the edge and the segment, respecively, and false otherwise. The closest points are returned in 'locE' and 'locS', respectively. This function uses the parametric solution of the two support lines to solve for the closest points, simplified as we work in the local frame of the box. See box_closest_feature for definition of 'code.

◆ snap_to_box()

uint chrono::ch_utils::snap_to_box	(	const real3 &	hdims,
		real3 &	loc
	)

inline

This utility function snaps the specified location to a point on a box with given half-dimensions.

The in/out location is assumed to be specified in the frame of the box (which is therefore assumed to be an AABB centered at the origin). The return code indicates the box axes that caused snapping.

first bit (least significant) corresponds to x-axis
second bit corresponds to y-axis
third bit corresponds to z-axis

Therefore:

code = 0 indicates an interior point
code = 1 or code = 2 or code = 4 indicates snapping to a face
code = 3 or code = 5 or code = 6 indicates snapping to an edge
code = 7 indicates snapping to a corner

◆ snap_to_box_edge()

real3 chrono::ch_utils::snap_to_box_edge	(	const real3 &	hdims,
		const real3 &	pt_on_box,
		uint	code,
		const real3 &	pt_to_snap
	)

inline

This utility function snaps the location 'pt_to_snap' to a location on the edge of this box identified by the specified 'code' and 'pt_on_box'.

The resulting location is returned. See box_closest_feature for definition of 'code.

◆ snap_to_box_face()

real3 chrono::ch_utils::snap_to_box_face	(	const real3 &	hdims,
		const real3 &	pt_on_box,
		uint	code,
		const real3 &	pt_to_snap
	)

inline

This utility function snaps the location 'pt_to_snap' to a location on the face of this box identified by the specified 'code' and 'pt_on_box'.

The resulting location is returned. See box_closest_feature for definition of 'code.

◆ snap_to_cylinder()

uint chrono::ch_utils::snap_to_cylinder	(	const real &	rad,
		const real &	hlen,
		real3 &	loc
	)

inline

This utility function snaps the specified location to a point on a cylinder with given radius and half-length.

The in/out location is assumed to be specified in the frame of the cylinder (in this frame the cylinder is assumed to be centered at the origin and aligned with the Z axis). The return code indicates the feature of the cylinder that caused snapping.

code = 0 indicates and interior point
code = 1 indicates snapping to one of the cylinder caps
code = 2 indicates snapping to the cylinder side
code = 3 indicates snapping to one of the cylinder edges

◆ snap_to_triangle()

bool chrono::ch_utils::snap_to_triangle	(	const real3 &	A,
		const real3 &	B,
		const real3 &	C,
		const real3 &	P,
		real3 &	res
	)

This utility function takes the location 'P' and snaps it to the closest point on the triangular face with given vertices (A, B, and C).

The result is returned in 'res'. Both 'P' and 'res' are assumed to be specified in the same frame as the face vertices. This function returns 'true' if the result is on an edge of this face and 'false' if the result is inside the triangle. Code from Ericson, "Real-time collision detection", 2005, pp. 141

◆ snap_to_triangle_bary()

bool chrono::ch_utils::snap_to_triangle_bary	(	const real3 &	A,
		const real3 &	B,
		const real3 &	C,
		const real3 &	P,
		real3 &	res,
		real3 &	barycentric
	)

This utility function takes the location 'P' and snaps it to the closest point on the triangular face with given vertices (A, B, and C).

Additionally, it also returns the barycentric coordinates of the result point. See snap_to_triangle for additional details.

◆ triangle_normal()

real3 chrono::ch_utils::triangle_normal	(	const real3 &	A,
		const real3 &	B,
		const real3 &	C
	)

inline

This utility function returns the normal to the triangular face defined by the vertices A, B, and C.

The face is assumed to be non-degenerate. Note that order of vertices is important!

Description

Functions

Function Documentation

◆ box_closest_feature()

◆ box_intersects_box()

◆ box_intersects_triangle()

◆ get_edge_corners()

◆ get_face_corners()

◆ get_face_normal()

◆ GetSupportPoint_Capsule()

◆ GetSupportPoint_Cone()

◆ GetSupportPoint_Cylinder()

◆ GetSupportPoint_CylindricalShell()

◆ GetSupportPoint_RoundedCylinder()

◆ point_in_triangle()

◆ point_vs_face()

◆ segment_vs_edge()

◆ snap_to_box()

◆ snap_to_box_edge()

◆ snap_to_box_face()

◆ snap_to_cylinder()

◆ snap_to_triangle()

◆ snap_to_triangle_bary()

◆ triangle_normal()