Struct GJK

Nested Relationships

Nested Types

Struct Documentation

struct GJK

class for GJK algorithm

Note

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

Public Types

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

Values:

enumerator DidNotRun
enumerator Failed
enumerator NoCollisionEarlyStopped
enumerator NoCollision
enumerator CollisionWithPenetrationInformation
enumerator Collision
typedef unsigned char vertex_id_t

Public Functions

inline GJK(size_t max_iterations_, CoalScalar tolerance_)

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.

Parameters:

  • max_iterations_ – number of iteration before GJK returns failure.

  • tolerance_ – precision of the algorithm.

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.

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.

inline 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

bool encloseOrigin()

whether the simplex enclose the origin

inline Simplex *getSimplex() const

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

inline bool hasClosestPoints() const

Tells whether the closest points are available.

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

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

Parameters:

  • shape – [in] is the Minkowski difference of the two shapes.

  • w0 – [out] is the witness point on shape0.

  • w1 – [out] is the witness point on shape1.

  • normal – [out] is the normal of the separating plane found by GJK. It points from shape0 to shape1.

Vec3s getGuessFromSimplex() const

get the guess from current simplex

inline void setDistanceEarlyBreak(const CoalScalar &dup)

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

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.

inline size_t getNumMaxIterations() const

Get the max number of iterations of GJK.

inline CoalScalar getTolerance() const

Get the tolerance of GJK.

inline size_t getNumIterations() const

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

inline size_t getNumIterationsMomentumStopped() const

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

Public Members

CoalScalar distance_upper_bound
Status status
GJKVariant gjk_variant
GJKConvergenceCriterion convergence_criterion
GJKConvergenceCriterionType convergence_criterion_type
MinkowskiDiff const *shape
Vec3s ray
support_func_guess_t support_hint
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.

Simplex *simplex
struct Simplex

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

Note

This data structure does not own the vertices it refers to. To be efficient, the constructor of GJK creates storage for 4 vertices. Since GJK does not need any more storage, it reuses these vertices throughout the algorithm by using multiple instance of this Simplex class.

Public Functions

inline Simplex()
inline void reset()

Public Members

SimplexV *vertex[4]

simplex vertex

vertex_id_t rank

size of simplex (number of vertices)

struct SimplexV

Public Members

Vec3s w0

support vector for shape 0 and 1.

Vec3s w1
Vec3s w

support vector (i.e., the furthest point on the shape along the support direction)