Classes | Public Types | Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | List of all members
hpp::fcl::details::GJK Struct Reference

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...
 
SimplexgetSimplex () 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
 
SimplexVfree_v [4]
 
size_t iterations
 
unsigned int max_iterations
 
vertex_id_t nfree
 
Simplexsimplex
 
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

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

  • $ d = - R - 1 $ 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:


hpp-fcl
Author(s):
autogenerated on Fri Jun 2 2023 02:39:03