class for GJK algorithm More...

#include <gjk.h>

Classes
struct	Simplex
	A simplex is a set of up to 4 vertices. Its rank is the number of vertices it contains. More...

struct	SimplexV

Public Types
enum	Status { DidNotRun, Failed, NoCollisionEarlyStopped, NoCollision, CollisionWithPenetrationInformation, Collision }
	Status of the GJK algorithm: DidNotRun: GJK has not been run. Failed: GJK did not converge (it exceeded the maximum number of iterations). NoCollisionEarlyStopped: GJK found a separating hyperplane and exited before converting. The shapes are not in collision. NoCollision: GJK converged and the shapes are not in collision. Collision: GJK converged and the shapes are in collision. Failed: GJK did not converge. More...

typedef unsigned char	vertex_id_t

Public Member Functions
bool	checkConvergence (const Vec3s &w, const CoalScalar &rl, CoalScalar &alpha, const CoalScalar &omega) const
	Convergence check used to stop GJK when shapes are not in collision. More...

bool	encloseOrigin ()
	whether the simplex enclose the origin More...

Status	evaluate (const MinkowskiDiff &shape, const Vec3s &guess, const support_func_guess_t &supportHint=support_func_guess_t::Zero())
	GJK algorithm, given the initial value guess. More...

Vec3s	getGuessFromSimplex () const
	get the guess from current simplex More...

size_t	getNumIterations () const
	Get the number of iterations of the last run of GJK. More...

size_t	getNumIterationsMomentumStopped () const
	Get GJK number of iterations before momentum stops. Only usefull if the Nesterov or Polyak acceleration activated. More...

size_t	getNumMaxIterations () const
	Get the max number of iterations of GJK. More...

Simplex *	getSimplex () const
	get the underlying simplex using in GJK, can be used for cache in next iteration More...

void	getSupport (const Vec3s &d, SimplexV &sv, support_func_guess_t &hint) const
	apply the support function along a direction, the result is return in sv More...

CoalScalar	getTolerance () const
	Get the tolerance of GJK. More...

void	getWitnessPointsAndNormal (const MinkowskiDiff &shape, Vec3s &w0, Vec3s &w1, Vec3s &normal) const

	GJK (size_t max_iterations_, CoalScalar tolerance_)

bool	hasClosestPoints () const
	Tells whether the closest points are available. More...

void	reset (size_t max_iterations_, CoalScalar tolerance_)
	resets the GJK algorithm, preparing it for a new run. Other than the maximum number of iterations and the tolerance, this function does not modify the parameters of the GJK algorithm. More...

void	setDistanceEarlyBreak (const CoalScalar &dup)
	Distance threshold for early break. GJK stops when it proved the distance is more than this threshold. More...

Public Attributes
GJKConvergenceCriterion	convergence_criterion

GJKConvergenceCriterionType	convergence_criterion_type

CoalScalar	distance
	The distance between the two shapes, computed by GJK. If the distance is below GJK's threshold, the shapes are in collision in the eyes of GJK. If `distance_upper_bound` is set to a value lower than infinity, GJK will early stop as soon as it finds `distance` to be greater than `distance_upper_bound`. More...

CoalScalar	distance_upper_bound

GJKVariant	gjk_variant

Vec3s	ray

MinkowskiDiff const *	shape

Simplex *	simplex

Status	status

support_func_guess_t	support_hint

Private Member Functions
void	appendVertex (Simplex &simplex, const Vec3s &v, support_func_guess_t &hint)
	append one vertex to the simplex More...

void	initialize ()
	Initializes the GJK algorithm. This function should only be called by the constructor. Otherwise use reset. More...

bool	projectLineOrigin (const Simplex &current, Simplex &next)
	Project origin (0) onto line a-b For a detailed explanation of how to efficiently project onto a simplex, check out Ericson's book, page 403: https://realtimecollisiondetection.net/ To sum up, a simplex has a voronoi region for each feature it has (vertex, edge, face). We find the voronoi region in which the origin lies and stop as soon as we find it; we then project onto it and return the result. We start by voronoi regions generated by vertices then move on to edges then faces. Checking voronoi regions is done using simple dot products. Moreover, edges voronoi checks reuse computations of vertices voronoi checks. The same goes for faces which reuse checks from edges. Finally, in addition to the voronoi procedure, checks relying on the order of construction of the simplex are added. To know more about these, visit https://caseymuratori.com/blog_0003. More...

bool	projectTetrahedraOrigin (const Simplex &current, Simplex &next)
	Project origin (0) onto tetrahedron a-b-c-d See projectLineOrigin for an explanation on simplex projections. More...

bool	projectTriangleOrigin (const Simplex &current, Simplex &next)
	Project origin (0) onto triangle a-b-c See projectLineOrigin for an explanation on simplex projections. More...

void	removeVertex (Simplex &simplex)
	discard one vertex from the simplex More...

Private Attributes
vertex_id_t	current

SimplexV *	free_v [4]

size_t	iterations

size_t	iterations_momentum_stop

size_t	max_iterations

vertex_id_t	nfree

Simplex	simplices [2]

SimplexV	store_v [4]

CoalScalar	tolerance

Detailed Description

class for GJK algorithm

Note: The computations are performed in the frame of the first shape.

Definition at line 53 of file coal/narrowphase/gjk.h.

Member Typedef Documentation

◆ vertex_id_t

typedef unsigned char coal::details::GJK::vertex_id_t

Definition at line 62 of file coal/narrowphase/gjk.h.

Member Enumeration Documentation

◆ Status

enum coal::details::GJK::Status

Status of the GJK algorithm: DidNotRun: GJK has not been run. Failed: GJK did not converge (it exceeded the maximum number of iterations). NoCollisionEarlyStopped: GJK found a separating hyperplane and exited before converting. The shapes are not in collision. NoCollision: GJK converged and the shapes are not in collision. Collision: GJK converged and the shapes are in collision. Failed: GJK did not converge.

Enumerator
DidNotRun
Failed
NoCollisionEarlyStopped
NoCollision
CollisionWithPenetrationInformation
Collision

Definition at line 94 of file coal/narrowphase/gjk.h.

Constructor & Destructor Documentation

◆ GJK()

coal::details::GJK::GJK	(	size_t	max_iterations_,
		CoalScalar	tolerance_
	)

inline

Parameters

max_iterations_	number of iteration before GJK returns failure.
tolerance_	precision of the algorithm.

The tolerance argument is useful for continuous shapes and for polyhedron with some vertices closer than this threshold.

Suggested values are 100 iterations and a tolerance of 1e-6.

Definition at line 143 of file coal/narrowphase/gjk.h.

Member Function Documentation

◆ appendVertex()

void coal::details::GJK::appendVertex	(	Simplex &	simplex,
		const Vec3s &	v,
		support_func_guess_t &	hint
	)

inlineprivate

append one vertex to the simplex

Definition at line 432 of file src/narrowphase/gjk.cpp.

◆ checkConvergence()

bool coal::details::GJK::checkConvergence	(	const Vec3s &	w,
		const CoalScalar &	rl,
		CoalScalar &	alpha,
		const CoalScalar &	omega
	)		const

Convergence check used to stop GJK when shapes are not in collision.

Definition at line 373 of file src/narrowphase/gjk.cpp.

◆ encloseOrigin()

bool coal::details::GJK::encloseOrigin ( )

whether the simplex enclose the origin

Definition at line 438 of file src/narrowphase/gjk.cpp.

◆ evaluate()

GJK::Status coal::details::GJK::evaluate	(	const MinkowskiDiff &	shape,
		const Vec3s &	guess,
		const support_func_guess_t &	supportHint = `support_func_guess_t::Zero()`
	)

GJK algorithm, given the initial value guess.

Definition at line 187 of file src/narrowphase/gjk.cpp.

◆ getGuessFromSimplex()

Vec3s coal::details::GJK::getGuessFromSimplex ( ) const

get the guess from current simplex

Definition at line 70 of file src/narrowphase/gjk.cpp.

◆ getNumIterations()

size_t coal::details::GJK::getNumIterations ( ) const

inline

Get the number of iterations of the last run of GJK.

Definition at line 210 of file coal/narrowphase/gjk.h.

◆ getNumIterationsMomentumStopped()

size_t coal::details::GJK::getNumIterationsMomentumStopped ( ) const

inline

Get GJK number of iterations before momentum stops. Only usefull if the Nesterov or Polyak acceleration activated.

Definition at line 214 of file coal/narrowphase/gjk.h.

◆ getNumMaxIterations()

size_t coal::details::GJK::getNumMaxIterations ( ) const

inline

Get the max number of iterations of GJK.

Definition at line 204 of file coal/narrowphase/gjk.h.

◆ getSimplex()

Simplex* coal::details::GJK::getSimplex ( ) const

inline

get the underlying simplex using in GJK, can be used for cache in next iteration

Definition at line 173 of file coal/narrowphase/gjk.h.

◆ getSupport()

void coal::details::GJK::getSupport	(	const Vec3s &	d,
		SimplexV &	sv,
		support_func_guess_t &	hint
	)		const

inline

apply the support function along a direction, the result is return in sv

Definition at line 162 of file coal/narrowphase/gjk.h.

◆ getTolerance()

CoalScalar coal::details::GJK::getTolerance ( ) const

inline

Get the tolerance of GJK.

Definition at line 207 of file coal/narrowphase/gjk.h.

◆ getWitnessPointsAndNormal()

void coal::details::GJK::getWitnessPointsAndNormal	(	const MinkowskiDiff &	shape,
		Vec3s &	w0,
		Vec3s &	w1,
		Vec3s &	normal
	)		const

Get the witness points on each object, and the corresponding normal.

Parameters

[in]	shape	is the Minkowski difference of the two shapes.
[out]	w0	is the witness point on shape0.
[out]	w1	is the witness point on shape1.
[out]	normal	is the normal of the separating plane found by GJK. It points from shape0 to shape1.

Definition at line 176 of file src/narrowphase/gjk.cpp.

◆ hasClosestPoints()

bool coal::details::GJK::hasClosestPoints ( ) const

inline

Tells whether the closest points are available.

Definition at line 176 of file coal/narrowphase/gjk.h.

◆ initialize()

void coal::details::GJK::initialize ( )

private

Initializes the GJK algorithm. This function should only be called by the constructor. Otherwise use reset.

Definition at line 50 of file src/narrowphase/gjk.cpp.

◆ projectLineOrigin()

bool coal::details::GJK::projectLineOrigin	(	const Simplex &	current,
		Simplex &	next
	)

private

Project origin (0) onto line a-b For a detailed explanation of how to efficiently project onto a simplex, check out Ericson's book, page 403: https://realtimecollisiondetection.net/ To sum up, a simplex has a voronoi region for each feature it has (vertex, edge, face). We find the voronoi region in which the origin lies and stop as soon as we find it; we then project onto it and return the result. We start by voronoi regions generated by vertices then move on to edges then faces. Checking voronoi regions is done using simple dot products. Moreover, edges voronoi checks reuse computations of vertices voronoi checks. The same goes for faces which reuse checks from edges. Finally, in addition to the voronoi procedure, checks relying on the order of construction of the simplex are added. To know more about these, visit https://caseymuratori.com/blog_0003.

Definition at line 544 of file src/narrowphase/gjk.cpp.

◆ projectTetrahedraOrigin()

bool coal::details::GJK::projectTetrahedraOrigin	(	const Simplex &	current,
		Simplex &	next
	)

private

Project origin (0) onto tetrahedron a-b-c-d See projectLineOrigin for an explanation on simplex projections.

Definition at line 614 of file src/narrowphase/gjk.cpp.

◆ projectTriangleOrigin()

bool coal::details::GJK::projectTriangleOrigin	(	const Simplex &	current,
		Simplex &	next
	)

private

Project origin (0) onto triangle a-b-c See projectLineOrigin for an explanation on simplex projections.

Definition at line 572 of file src/narrowphase/gjk.cpp.

◆ removeVertex()

void coal::details::GJK::removeVertex ( Simplex & simplex )

inlineprivate

discard one vertex from the simplex

Definition at line 428 of file src/narrowphase/gjk.cpp.

◆ reset()

void coal::details::GJK::reset	(	size_t	max_iterations_,
		CoalScalar	tolerance_
	)

resets the GJK algorithm, preparing it for a new run. Other than the maximum number of iterations and the tolerance, this function does not modify the parameters of the GJK algorithm.

Definition at line 58 of file src/narrowphase/gjk.cpp.

◆ setDistanceEarlyBreak()

void coal::details::GJK::setDistanceEarlyBreak ( const CoalScalar & dup )

inline

Distance threshold for early break. GJK stops when it proved the distance is more than this threshold.

Note: The closest points will be erroneous in this case. If you want the closest points, set this to infinity (the default).

Definition at line 194 of file coal/narrowphase/gjk.h.

Member Data Documentation

◆ convergence_criterion

GJKConvergenceCriterion coal::details::GJK::convergence_criterion

Definition at line 107 of file coal/narrowphase/gjk.h.

◆ convergence_criterion_type

GJKConvergenceCriterionType coal::details::GJK::convergence_criterion_type

Definition at line 108 of file coal/narrowphase/gjk.h.

◆ current

vertex_id_t coal::details::GJK::current

private

Definition at line 130 of file coal/narrowphase/gjk.h.

◆ distance

CoalScalar coal::details::GJK::distance

The distance between the two shapes, computed by GJK. If the distance is below GJK's threshold, the shapes are in collision in the eyes of GJK. If distance_upper_bound is set to a value lower than infinity, GJK will early stop as soon as it finds distance to be greater than distance_upper_bound.

Definition at line 118 of file coal/narrowphase/gjk.h.

◆ distance_upper_bound

CoalScalar coal::details::GJK::distance_upper_bound

Definition at line 104 of file coal/narrowphase/gjk.h.

◆ free_v

SimplexV* coal::details::GJK::free_v[4]

private

Definition at line 128 of file coal/narrowphase/gjk.h.

◆ gjk_variant

GJKVariant coal::details::GJK::gjk_variant

Definition at line 106 of file coal/narrowphase/gjk.h.

◆ iterations

size_t coal::details::GJK::iterations

private

Definition at line 132 of file coal/narrowphase/gjk.h.

◆ iterations_momentum_stop

size_t coal::details::GJK::iterations_momentum_stop

private

Definition at line 133 of file coal/narrowphase/gjk.h.

◆ max_iterations

size_t coal::details::GJK::max_iterations

private

Definition at line 124 of file coal/narrowphase/gjk.h.

◆ nfree

vertex_id_t coal::details::GJK::nfree

private

Definition at line 129 of file coal/narrowphase/gjk.h.

◆ ray

Vec3s coal::details::GJK::ray

Definition at line 111 of file coal/narrowphase/gjk.h.

◆ shape

MinkowskiDiff const* coal::details::GJK::shape

Definition at line 110 of file coal/narrowphase/gjk.h.

◆ simplex

Simplex* coal::details::GJK::simplex

Definition at line 119 of file coal/narrowphase/gjk.h.

◆ simplices

Simplex coal::details::GJK::simplices[2]

private

Definition at line 131 of file coal/narrowphase/gjk.h.

◆ status

Status coal::details::GJK::status

Definition at line 105 of file coal/narrowphase/gjk.h.

◆ store_v

SimplexV coal::details::GJK::store_v[4]

private

Definition at line 127 of file coal/narrowphase/gjk.h.

◆ support_hint

support_func_guess_t coal::details::GJK::support_hint

Definition at line 112 of file coal/narrowphase/gjk.h.

◆ tolerance

CoalScalar coal::details::GJK::tolerance

private

Definition at line 125 of file coal/narrowphase/gjk.h.

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

Classes

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ vertex_id_t

Member Enumeration Documentation

◆ Status

Constructor & Destructor Documentation

◆ GJK()

Member Function Documentation

◆ appendVertex()

◆ checkConvergence()

◆ encloseOrigin()

◆ evaluate()

◆ getGuessFromSimplex()

◆ getNumIterations()

◆ getNumIterationsMomentumStopped()

◆ getNumMaxIterations()

◆ getSimplex()

◆ getSupport()

◆ getTolerance()

◆ getWitnessPointsAndNormal()

◆ hasClosestPoints()

◆ initialize()

◆ projectLineOrigin()

◆ projectTetrahedraOrigin()

◆ projectTriangleOrigin()

◆ removeVertex()

◆ reset()

◆ setDistanceEarlyBreak()

Member Data Documentation

◆ convergence_criterion

◆ convergence_criterion_type

◆ current

◆ distance

◆ distance_upper_bound

◆ free_v

◆ gjk_variant

◆ iterations

◆ iterations_momentum_stop

◆ max_iterations

◆ nfree

◆ ray

◆ shape

◆ simplex

◆ simplices

◆ status

◆ store_v

◆ support_hint

◆ tolerance