EPAPenetrationDepth Class Reference

#include <EPAPenetrationDepth.h>

Public Types
enum class	EStatus { NotColliding , Colliding , Indeterminate }
	Return code for GetPenetrationDepthStepGJK. More...

Public Member Functions
template<typename AE , typename BE >
EStatus	GetPenetrationDepthStepGJK (const AE &inAExcludingConvexRadius, float inConvexRadiusA, const BE &inBExcludingConvexRadius, float inConvexRadiusB, float inTolerance, Vec3 &ioV, Vec3 &outPointA, Vec3 &outPointB)
template<typename AI , typename BI >
bool	GetPenetrationDepthStepEPA (const AI &inAIncludingConvexRadius, const BI &inBIncludingConvexRadius, float inTolerance, Vec3 &outV, Vec3 &outPointA, Vec3 &outPointB)
template<typename AE , typename AI , typename BE , typename BI >
bool	GetPenetrationDepth (const AE &inAExcludingConvexRadius, const AI &inAIncludingConvexRadius, float inConvexRadiusA, const BE &inBExcludingConvexRadius, const BI &inBIncludingConvexRadius, float inConvexRadiusB, float inCollisionToleranceSq, float inPenetrationTolerance, Vec3 &ioV, Vec3 &outPointA, Vec3 &outPointB)
template<typename A , typename B >
bool	CastShape (Mat44Arg inStart, Vec3Arg inDirection, float inCollisionTolerance, float inPenetrationTolerance, const A &inA, const B &inB, float inConvexRadiusA, float inConvexRadiusB, bool inReturnDeepestPoint, float &ioLambda, Vec3 &outPointA, Vec3 &outPointB, Vec3 &outContactNormal)

Detailed Description

Implementation of Expanding Polytope Algorithm as described in:

Proximity Queries and Penetration Depth Computation on 3D Game Objects - Gino van den Bergen

The implementation of this algorithm does not completely follow the article, instead of splitting triangles at each edge as in fig. 7 in the article, we build a convex hull (removing any triangles that are facing the new point, thereby avoiding the problem of getting really oblong triangles as mentioned in the article).

The algorithm roughly works like:

• Start with a simplex of the Minkowski sum (difference) of two objects that was calculated by GJK
• This simplex should contain the origin (or else GJK would have reported: no collision)
• In cases where the simplex consists of 1 - 3 points, find some extra support points (of the Minkowski sum) to get to at least 4 points
• Convert this into a convex hull with non-zero volume (which includes the origin)
• A: Calculate the closest point to the origin for all triangles of the hull and take the closest one
• Calculate a new support point (of the Minkowski sum) in this direction and add this point to the convex hull
• This will remove all faces that are facing the new point and will create new triangles to fill up the hole
• Loop to A until no closer point found
• The closest point indicates the position / direction of least penetration

Member Enumeration Documentation

EStatus

enum class EPAPenetrationDepth::EStatus

strong

Return code for GetPenetrationDepthStepGJK.

Enumerator
NotColliding	Returned if the objects don't collide, in this case outPointA/outPointB are invalid.
Colliding	Returned if the objects penetrate.
Indeterminate	Returned if the objects penetrate further than the convex radius. In this case you need to call GetPenetrationDepthStepEPA to get the actual penetration depth.

Member Function Documentation

CastShape()

template<typename A , typename B >

bool EPAPenetrationDepth::CastShape ( Mat44Arg  inStart, Vec3Arg  inDirection, float  inCollisionTolerance, float  inPenetrationTolerance, const A &  inA, const B &  inB, float  inConvexRadiusA, float  inConvexRadiusB, bool  inReturnDeepestPoint, float &  ioLambda, Vec3 &  outPointA, Vec3 &  outPointB, Vec3 &  outContactNormal  )

inline

Test if a cast shape inA moving from inStart to lambda * inStart.GetTranslation() + inDirection where lambda e [0, ioLambda> intersects inB

Parameters

inStart	Start position and orientation of the convex object
inDirection	Direction of the sweep (ioLambda * inDirection determines length)
inCollisionTolerance	The minimal distance between A and B before they are considered colliding
inPenetrationTolerance	A factor that determines the accuracy of the result. If the change of the squared distance is less than inTolerance * current_penetration_depth^2 the algorithm will terminate. Should be bigger or equal to FLT_EPSILON.
inA	The convex object A, must support the GetSupport(Vec3) function.
inB	The convex object B, must support the GetSupport(Vec3) function.
inConvexRadiusA	The convex radius of A, this will be added on all sides to pad A.
inConvexRadiusB	The convex radius of B, this will be added on all sides to pad B.
inReturnDeepestPoint	If the shapes are initially intersecting this determines if the EPA algorithm will run to find the deepest point
ioLambda	The max fraction along the sweep, on output updated with the actual collision fraction.
outPointA	is the contact point on A
outPointB	is the contact point on B
outContactNormal	is either the contact normal when the objects are touching or the penetration axis when the objects are penetrating at the start of the sweep (pointing from A to B, length will not be 1)

Returns

true if the a hit was found, in which case ioLambda, outPointA, outPointB and outSurfaceNormal are updated.

GetPenetrationDepth()

template<typename AE , typename AI , typename BE , typename BI >

bool EPAPenetrationDepth::GetPenetrationDepth ( const AE &  inAExcludingConvexRadius, const AI &  inAIncludingConvexRadius, float  inConvexRadiusA, const BE &  inBExcludingConvexRadius, const BI &  inBIncludingConvexRadius, float  inConvexRadiusB, float  inCollisionToleranceSq, float  inPenetrationTolerance, Vec3 &  ioV, Vec3 &  outPointA, Vec3 &  outPointB  )

inline

This function combines the GJK and EPA steps and is provided as a convenience function. Note: less performant since you're providing all support functions in one go Note 2: You need to initialize ioV, see documentation at GetPenetrationDepthStepGJK!

GetPenetrationDepthStepEPA()

template<typename AI , typename BI >

bool EPAPenetrationDepth::GetPenetrationDepthStepEPA ( const AI &  inAIncludingConvexRadius, const BI &  inBIncludingConvexRadius, float  inTolerance, Vec3 &  outV, Vec3 &  outPointA, Vec3 &  outPointB  )

inline

Calculates penetration depth between two objects, second step (the EPA step)

Parameters

inAIncludingConvexRadius	Object A with convex radius
inBIncludingConvexRadius	Object B with convex radius
inTolerance	A factor that determines the accuracy of the result. If the change of the squared distance is less than inTolerance * current_penetration_depth^2 the algorithm will terminate. Should be bigger or equal to FLT_EPSILON.
outV	Direction to move B out of collision along the shortest path (magnitude is meaningless)
outPointA	Position on A that has the least amount of penetration
outPointB	Position on B that has the least amount of penetration Use |outPointB - outPointA| to get the distance of penetration

Returns

False if the objects don't collide, in this case outPointA/outPointB are invalid. True if the objects penetrate

GetPenetrationDepthStepGJK()

template<typename AE , typename BE >

EStatus EPAPenetrationDepth::GetPenetrationDepthStepGJK ( const AE &  inAExcludingConvexRadius, float  inConvexRadiusA, const BE &  inBExcludingConvexRadius, float  inConvexRadiusB, float  inTolerance, Vec3 &  ioV, Vec3 &  outPointA, Vec3 &  outPointB  )

inline

Calculates penetration depth between two objects, first step of two (the GJK step)

Parameters

inAExcludingConvexRadius	Object A without convex radius.
inBExcludingConvexRadius	Object B without convex radius.
inConvexRadiusA	Convex radius for A.
inConvexRadiusB	Convex radius for B.
ioV	Pass in previously returned value or (1, 0, 0). On return this value is changed to direction to move B out of collision along the shortest path (magnitude is meaningless).
inTolerance	Minimal distance before A and B are considered colliding.
outPointA	Position on A that has the least amount of penetration.
outPointB	Position on B that has the least amount of penetration. Use |outPointB - outPointA| to get the distance of penetration.

---

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

• Jolt/Geometry/EPAPenetrationDepth.h