class for GJK algorithm More...

#include <gjk.h>

Classes
struct	Simplex

struct	SimplexV

Public Types
enum	Status { Valid, Inside, Failed, EarlyStopped }
	Status of the GJK algorithm: Valid: GJK converged and the shapes are not in collision. Inside: 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 Vec3f &w, const FCL_REAL &rl, FCL_REAL &alpha, const FCL_REAL &omega)
	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 Vec3f &guess, const support_func_guess_t &supportHint=support_func_guess_t::Zero())
	GJK algorithm, given the initial value guess. More...

bool	getClosestPoints (const MinkowskiDiff &shape, Vec3f &w0, Vec3f &w1)

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

size_t	getIterations ()
	Get GJK number of iterations. More...

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

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

FCL_REAL	getTolerance ()
	Get GJK tolerance. More...

	GJK (unsigned int max_iterations_, FCL_REAL tolerance_)

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

bool	hasPenetrationInformation (const MinkowskiDiff &shape)

void	initialize ()

void	setDistanceEarlyBreak (const FCL_REAL &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

FCL_REAL	distance

GJKVariant	gjk_variant

Vec3f	ray

MinkowskiDiff const *	shape

Simplex	simplices [2]

support_func_guess_t	support_hint

Private Member Functions
void	appendVertex (Simplex &simplex, const Vec3f &v, bool isNormalized, support_func_guess_t &hint)
	append one vertex to the simplex 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. 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

FCL_REAL	distance_upper_bound

SimplexV *	free_v [4]

size_t	iterations

unsigned int	max_iterations

vertex_id_t	nfree

Simplex *	simplex

Status	status

SimplexV	store_v [4]

FCL_REAL	tolerance

Detailed Description

class for GJK algorithm

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

Definition at line 141 of file gjk.h.

Member Typedef Documentation

◆ vertex_id_t

typedef unsigned char hpp::fcl::details::GJK::vertex_id_t

Definition at line 150 of file gjk.h.

Member Enumeration Documentation

◆ Status

enum hpp::fcl::details::GJK::Status

Status of the GJK algorithm: Valid: GJK converged and the shapes are not in collision. Inside: GJK converged and the shapes are in collision. Failed: GJK did not converge.

Enumerator
Valid
Inside
Failed
EarlyStopped

Definition at line 165 of file gjk.h.

Constructor & Destructor Documentation

◆ GJK()

hpp::fcl::details::GJK::GJK	(	unsigned int	max_iterations_,
		FCL_REAL	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 196 of file gjk.h.

Member Function Documentation

◆ appendVertex()

void hpp::fcl::details::GJK::appendVertex	(	Simplex &	simplex,
		const Vec3f &	v,
		bool	isNormalized,
		support_func_guess_t &	hint
	)

inlineprivate

append one vertex to the simplex

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

◆ checkConvergence()

bool hpp::fcl::details::GJK::checkConvergence	(	const Vec3f &	w,
		const FCL_REAL &	rl,
		FCL_REAL &	alpha,
		const FCL_REAL &	omega
	)

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

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

◆ encloseOrigin()

bool hpp::fcl::details::GJK::encloseOrigin ( )

whether the simplex enclose the origin

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

◆ evaluate()

GJK::Status hpp::fcl::details::GJK::evaluate	(	const MinkowskiDiff &	shape,
		const Vec3f &	guess,
		const support_func_guess_t &	supportHint = `support_func_guess_t::Zero()`
	)

GJK algorithm, given the initial value guess.

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

◆ getClosestPoints()

bool hpp::fcl::details::GJK::getClosestPoints	(	const MinkowskiDiff &	shape,
		Vec3f &	w0,
		Vec3f &	w1
	)

Get the closest points on each object.

Returns: true on success

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

◆ getGuessFromSimplex()

Vec3f hpp::fcl::details::GJK::getGuessFromSimplex ( ) const

get the guess from current simplex

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

◆ getIterations()

size_t hpp::fcl::details::GJK::getIterations ( )

inline

Get GJK number of iterations.

Definition at line 255 of file gjk.h.

◆ getSimplex()

Simplex* hpp::fcl::details::GJK::getSimplex ( ) const

inline

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

Definition at line 221 of file gjk.h.

◆ getSupport()

void hpp::fcl::details::GJK::getSupport	(	const Vec3f &	d,
		bool	dIsNormalized,
		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 210 of file gjk.h.

◆ getTolerance()

FCL_REAL hpp::fcl::details::GJK::getTolerance ( )

inline

Get GJK tolerance.

Definition at line 258 of file gjk.h.

◆ hasClosestPoints()

bool hpp::fcl::details::GJK::hasClosestPoints ( )

inline

Tells whether the closest points are available.

Definition at line 224 of file gjk.h.

◆ hasPenetrationInformation()

bool hpp::fcl::details::GJK::hasPenetrationInformation ( const MinkowskiDiff & shape )

inline

Tells whether the penetration information.

In such case, most indepth points and penetration depth can be retrieved from GJK. Calling EPA has an undefined behaviour.

Definition at line 230 of file gjk.h.

◆ initialize()

void hpp::fcl::details::GJK::initialize ( )

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

◆ projectLineOrigin()

bool hpp::fcl::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.

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

◆ projectTetrahedraOrigin()

bool hpp::fcl::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 1044 of file src/narrowphase/gjk.cpp.

◆ projectTriangleOrigin()

bool hpp::fcl::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 1002 of file src/narrowphase/gjk.cpp.

◆ removeVertex()

void hpp::fcl::details::GJK::removeVertex ( Simplex & simplex )

inlineprivate

discard one vertex from the simplex

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

◆ setDistanceEarlyBreak()

void hpp::fcl::details::GJK::setDistanceEarlyBreak ( const FCL_REAL & 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 245 of file gjk.h.

Member Data Documentation

◆ convergence_criterion

GJKConvergenceCriterion hpp::fcl::details::GJK::convergence_criterion

Definition at line 170 of file gjk.h.

◆ convergence_criterion_type

GJKConvergenceCriterionType hpp::fcl::details::GJK::convergence_criterion_type

Definition at line 171 of file gjk.h.

◆ current

vertex_id_t hpp::fcl::details::GJK::current

private

Definition at line 264 of file gjk.h.

◆ distance

FCL_REAL hpp::fcl::details::GJK::distance

The distance computed by GJK. The possible values are

when a collision is detected and GJK cannot compute penetration informations.
$- R \le d \le 0$ when a collision is detected and GJK can compute penetration informations.
$0 < d \le d_{ub}$ when there is no collision and GJK can compute the closest points.
$d_{ub} < d$ when there is no collision and GJK cannot compute the closest points.

where $ d $ is the GJK::distance, $ R $ is the sum of the shape MinkowskiDiff::inflation and $d_{ub}$ is the GJK::distance_upper_bound.

Definition at line 186 of file gjk.h.

◆ distance_upper_bound

FCL_REAL hpp::fcl::details::GJK::distance_upper_bound

private

Definition at line 270 of file gjk.h.

◆ free_v

SimplexV* hpp::fcl::details::GJK::free_v[4]

private

Definition at line 262 of file gjk.h.

◆ gjk_variant

GJKVariant hpp::fcl::details::GJK::gjk_variant

Definition at line 169 of file gjk.h.

◆ iterations

size_t hpp::fcl::details::GJK::iterations

private

Definition at line 271 of file gjk.h.

◆ max_iterations

unsigned int hpp::fcl::details::GJK::max_iterations

private

Definition at line 268 of file gjk.h.

◆ nfree

vertex_id_t hpp::fcl::details::GJK::nfree

private

Definition at line 263 of file gjk.h.

◆ ray

Vec3f hpp::fcl::details::GJK::ray

Definition at line 168 of file gjk.h.

◆ shape

MinkowskiDiff const* hpp::fcl::details::GJK::shape

Definition at line 167 of file gjk.h.

◆ simplex

Simplex* hpp::fcl::details::GJK::simplex

private

Definition at line 265 of file gjk.h.

◆ simplices

Simplex hpp::fcl::details::GJK::simplices[2]

Definition at line 187 of file gjk.h.

◆ status

Status hpp::fcl::details::GJK::status

private

Definition at line 266 of file gjk.h.

◆ store_v

SimplexV hpp::fcl::details::GJK::store_v[4]

private

Definition at line 261 of file gjk.h.

◆ support_hint

support_func_guess_t hpp::fcl::details::GJK::support_hint

Definition at line 172 of file gjk.h.

◆ tolerance

FCL_REAL hpp::fcl::details::GJK::tolerance

private

Definition at line 269 of file 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()

◆ getClosestPoints()

◆ getGuessFromSimplex()

◆ getIterations()

◆ getSimplex()

◆ getSupport()

◆ getTolerance()

◆ hasClosestPoints()

◆ hasPenetrationInformation()

◆ initialize()

◆ projectLineOrigin()

◆ projectTetrahedraOrigin()

◆ projectTriangleOrigin()

◆ removeVertex()

◆ setDistanceEarlyBreak()

Member Data Documentation

◆ convergence_criterion

◆ convergence_criterion_type

◆ current

◆ distance

◆ distance_upper_bound

◆ free_v

◆ gjk_variant

◆ iterations

◆ max_iterations

◆ nfree

◆ ray

◆ shape

◆ simplex

◆ simplices

◆ status

◆ store_v

◆ support_hint

◆ tolerance