class for GJK algorithm More...

#include <coal/narrowphase/gjk.h>

Collaboration diagram for coal::details::GJK:

[legend]

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
	GJK (size_t max_iterations_, SolverScalar tolerance_)

void	reset (size_t max_iterations_, SolverScalar 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...

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

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

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

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

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

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

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

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

bool	checkConvergence (const Vec3ps &w, const SolverScalar &rl, SolverScalar &alpha, const SolverScalar &omega) const
	Convergence check used to stop GJK when shapes are not in collision. More...

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

SolverScalar	getTolerance () const
	Get the tolerance of GJK. 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...

Public Attributes
SolverScalar	distance_upper_bound

Status	status

GJKVariant	gjk_variant

GJKConvergenceCriterion	convergence_criterion

GJKConvergenceCriterionType	convergence_criterion_type

MinkowskiDiff const *	shape

Vec3ps	ray

support_func_guess_t	support_hint

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

Simplex *	simplex

Detailed Description

class for GJK algorithm

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

Member Typedef Documentation

◆ vertex_id_t

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

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

Constructor & Destructor Documentation

◆ GJK()

coal::details::GJK::GJK	(	size_t	max_iterations_,
		SolverScalar	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.

Member Function Documentation

◆ checkConvergence()

bool coal::details::GJK::checkConvergence	(	const Vec3ps &	w,
		const SolverScalar &	rl,
		SolverScalar &	alpha,
		const SolverScalar &	omega
	)		const

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

◆ encloseOrigin()

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

whether the simplex enclose the origin

◆ evaluate()

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

GJK algorithm, given the initial value guess.

◆ getGuessFromSimplex()

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

get the guess from current simplex

◆ getNumIterations()

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

inline

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

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

◆ getNumMaxIterations()

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

inline

Get the max number of iterations of GJK.

◆ getSimplex()

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

inline

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

◆ getSupport()

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

inline

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

◆ getTolerance()

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

inline

Get the tolerance of GJK.

◆ getWitnessPointsAndNormal()

void coal::details::GJK::getWitnessPointsAndNormal	(	const MinkowskiDiff &	shape,
		Vec3ps &	w0,
		Vec3ps &	w1,
		Vec3ps &	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.

◆ hasClosestPoints()

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

inline

Tells whether the closest points are available.

◆ reset()

void coal::details::GJK::reset	(	size_t	max_iterations_,
		SolverScalar	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.

◆ setDistanceEarlyBreak()

void coal::details::GJK::setDistanceEarlyBreak ( const SolverScalar & 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).

Member Data Documentation

◆ convergence_criterion

GJKConvergenceCriterion coal::details::GJK::convergence_criterion

◆ convergence_criterion_type

GJKConvergenceCriterionType coal::details::GJK::convergence_criterion_type

◆ distance

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

◆ distance_upper_bound

SolverScalar coal::details::GJK::distance_upper_bound

◆ gjk_variant

GJKVariant coal::details::GJK::gjk_variant

◆ ray

Vec3ps coal::details::GJK::ray

◆ shape

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

◆ simplex

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

◆ status

Status coal::details::GJK::status

◆ support_hint

support_func_guess_t coal::details::GJK::support_hint

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

include/coal/narrowphase/gjk.h

Classes

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ vertex_id_t

Member Enumeration Documentation

◆ Status

Constructor & Destructor Documentation

◆ GJK()

Member Function Documentation

◆ checkConvergence()

◆ encloseOrigin()

◆ evaluate()

◆ getGuessFromSimplex()

◆ getNumIterations()

◆ getNumIterationsMomentumStopped()

◆ getNumMaxIterations()

◆ getSimplex()

◆ getSupport()

◆ getTolerance()

◆ getWitnessPointsAndNormal()

◆ hasClosestPoints()

◆ reset()

◆ setDistanceEarlyBreak()

Member Data Documentation

◆ convergence_criterion

◆ convergence_criterion_type

◆ distance

◆ distance_upper_bound

◆ gjk_variant

◆ ray

◆ shape

◆ simplex

◆ status

◆ support_hint