Module org.dyn4j

Class Gjk

• java.lang.Object
• org.dyn4j.collision.narrowphase.Gjk
• All Implemented Interfaces:
`DistanceDetector`, `NarrowphaseDetector`, `RaycastDetector`

```public class Gjk
extends java.lang.Object
implements NarrowphaseDetector, DistanceDetector, RaycastDetector```
Implementation of the Gilbert-Johnson-Keerthi (GJK) algorithm for collision detection.

`Gjk` is an algorithm used to find minimum distance from one `Convex` `Shape` to another, but can also be used to determine whether or not they intersect.

`Gjk` uses a specific mathematical construct called the `MinkowskiSum`. The `MinkowskiSum` of two `Convex` `Shape`s create another `Convex` `Shape`. If the shapes are labeled A and B, the `MinkowskiSum` is the convex hull of adding every point in A to every point in B.

Now, if we subtract every point in A and every point in B, we still end up with a `Convex` `Shape`, but we also get another interesting property. If the two `Convex` `Shape`s are penetrating one another (overlapping) then the `MinkowskiSum`, using the difference operator, will contain the origin.

Computing the `MinkowskiSum` directly would not be very efficient and performance would be directly linked to the number of vertices each shape contained (n*m subtractions). In addition, curved shapes have an infinite number of vertices.

That said, it's not necessary to compute the `MinkowskiSum`. Instead, to determine whether the origin is contained in the `MinkowskiSum` we iteratively create a `Shape` inside the `MinkowskiSum` that encloses the origin. This is called the simplex and for 2D it will be a triangle. If we can enclose the origin using a shape contained within the `MinkowskiSum`, then we can conclude that the origin is contained within the `MinkowskiSum`, and that the two shapes are penetrating. If we cannot, then the shapes are separated.

To create a shape inside the `MinkowskiSum`, we use what is called a support function. The support function returns a point on the edge of the `MinkowskiSum` farthest in a given direction. This can be obtained by taking the farthest point in shape A minus the farthest point in shape B in the opposite direction.

If the `MinkowskiSum` is:

``` A - B
```
then the support function would be:
``` (farthest point in direction D in A) - (farthest point in direction -D in B)
```
With this we can obtain a point which is on the edge of the `MinkowskiSum` shape in any direction. Next we iteratively create these points so that we create a shape (triangle in the 2d case) that encloses the origin.

Algorithm psuedo-code:

``` // get a point farthest in the direction
// choose some random direction (selection of the initial direction can
// determine the speed at which the algorithm terminates)
Point p = support(A, B, direction);
// add it to the simplex
// negate the direction
direction = -direction;
// make sure the point we are about to add is actually past the origin
// if its not past the origin then that means we can never enclose the origin
// therefore its not in the Minkowski sum and therefore there is no penetration.
while (p = support(A, B, direction).dot(direction) > 0) {
// if the point is past the origin then add it to the simplex
// then check to see if the simplex contains the origin
// passing back a new search direction if it does not
if (check(simplex, direction)) {
return true;
}
}
return false;
```
The last method to discuss is the check method. This method can be implemented in any fashion, however, if the simplex points are stored in a way that we always know what point was added last, many optimizations can be done. For these optimizations please refer to the source documentation on `checkSimplex(List, Vector2)`.

Once `Gjk` has found that the two `Collidable`s are penetrating it will exit and hand off the resulting simplex to a `MinkowskiPenetrationSolver` to find the collision depth and normal.

The `Gjk` algorithm's original intent was to find the minimum distance between two `Convex` `Shape`s. Refer to `distance(Convex, Transform, Convex, Transform, Separation)` for details on the implementation.

Since:
1.0.0
Version:
3.3.0
Author:
William Bittle
`Epa`, GJK (Gilbert-Johnson-Keerthi), GJK - Distance & Closest Points
• Field Summary

Fields
Modifier and Type Field Description
`static double` `DEFAULT_DETECT_EPSILON`
The default epsilon in meters for collision detection
`static double` `DEFAULT_DISTANCE_EPSILON`
The default epsilon in meters for distance checks
`static int` `DEFAULT_MAX_ITERATIONS`
The default `Gjk` maximum iterations
`static double` `DEFAULT_RAYCAST_EPSILON`
The default epsilon in meters for raycast checks
• Constructor Summary

Constructors
Constructor Description
`Gjk​()`
Default constructor.
`Gjk​(MinkowskiPenetrationSolver minkowskiPenetrationSolver)`
Optional constructor.
• Method Summary

All Methods
Modifier and Type Method Description
`boolean` ```detect​(Convex convex1, Transform transform1, Convex convex2, Transform transform2)```
Returns true if the two `Convex` `Shape`s intersect.
`boolean` ```detect​(Convex convex1, Transform transform1, Convex convex2, Transform transform2, Penetration penetration)```
Returns true if the two `Convex` `Shape`s intersect and fills the `Penetration` object with the penetration vector and depth.
`boolean` ```distance​(Convex convex1, Transform transform1, Convex convex2, Transform transform2, Separation separation)```
Returns true if the two `Convex` `Shape`s are separated and fills the given `Separation` object with the minimum distance vector, distance, and closest points.
`double` `getDetectEpsilon​()`
Returns the `Gjk` detect epsilon.
`double` `getDistanceEpsilon​()`
Returns the `Gjk` distance epsilon.
`int` `getMaxDetectIterations​()`
Returns the maximum number of iterations the `Gjk` collision detection algorithm will perform before returning that two convex shapes are not overlapping.
`int` `getMaxDistanceIterations​()`
Returns the maximum number of iterations the `Gjk` distance algorithm will perform before returning the distance between two separated convex shapes.
`int` `getMaxIterations​()`
Deprecated.
`int` `getMaxRaycastIterations​()`
Returns the maximum number of iterations the `Gjk` raycast algorithm will perform before returning that the ray and the convex are not overlapping.
`MinkowskiPenetrationSolver` `getMinkowskiPenetrationSolver​()`
Returns the `MinkowskiPenetrationSolver` used to obtain the penetration vector and depth.
`double` `getRaycastEpsilon​()`
Returns the `Gjk` raycast epsilon.
`boolean` ```raycast​(Ray ray, double maxLength, Convex convex, Transform transform, Raycast raycast)```
Performs a ray cast given a `Ray` and a `Convex` `Shape` returning true if the ray passes through the convex shape.
`void` `setDetectEpsilon​(double detectEpsilon)`
The minimum distance to determine that two shapes are not colliding.
`void` `setDistanceEpsilon​(double distanceEpsilon)`
The minimum distance between two iterations of the `Gjk` distance algorithm.
`void` `setMaxDetectIterations​(int maxIterations)`
Sets the maximum number of iterations the `Gjk` collision detection algorithm will perform when before return that two convex shapes are not overlapping.
`void` `setMaxDistanceIterations​(int maxIterations)`
Sets the maximum number of iterations the `Gjk` distance algorithm will perform when determining the distance between two convex shapes.
`void` `setMaxIterations​(int maxIterations)`
Deprecated.
`void` `setMaxRaycastIterations​(int maxIterations)`
Sets the maximum number of iterations the `Gjk` raycast algorithm will perform when checking whether the ray intersects the convex.
`void` `setMinkowskiPenetrationSolver​(MinkowskiPenetrationSolver minkowskiPenetrationSolver)`
Sets the `MinkowskiPenetrationSolver` used to obtain the penetration vector and depth.
`void` `setRaycastEpsilon​(double raycastEpsilon)`
The minimum distance between the ray and convex for the `Gjk` raycast algorithm.
• Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• Field Detail

• DEFAULT_DETECT_EPSILON

`public static final double DEFAULT_DETECT_EPSILON`
The default epsilon in meters for collision detection
Constant Field Values
• DEFAULT_DISTANCE_EPSILON

`public static final double DEFAULT_DISTANCE_EPSILON`
The default epsilon in meters for distance checks
• DEFAULT_RAYCAST_EPSILON

`public static final double DEFAULT_RAYCAST_EPSILON`
The default epsilon in meters for raycast checks
• Constructor Detail

• Gjk

`public Gjk​()`
Default constructor.
• Gjk

`public Gjk​(MinkowskiPenetrationSolver minkowskiPenetrationSolver)`
Optional constructor.
Parameters:
`minkowskiPenetrationSolver` - the `MinkowskiPenetrationSolver` to use
Throws:
`java.lang.NullPointerException` - if minkowskiPenetrationSolver is null
• Method Detail

• getMaxDetectIterations

`public int getMaxDetectIterations​()`
Returns the maximum number of iterations the `Gjk` collision detection algorithm will perform before returning that two convex shapes are not overlapping.
Returns:
int the number of `Gjk` detect iterations
Since:
3.3.0
`setMaxDetectIterations(int)`
• setMaxDetectIterations

`public void setMaxDetectIterations​(int maxIterations)`
Sets the maximum number of iterations the `Gjk` collision detection algorithm will perform when before return that two convex shapes are not overlapping.

Valid values are in the range [5, ∞].

Parameters:
`maxIterations` - the maximum number of `Gjk` detect iterations
Throws:
`java.lang.IllegalArgumentException` - if maxIterations is less than 5
Since:
3.3.0
• getMaxDistanceIterations

`public int getMaxDistanceIterations​()`
Returns the maximum number of iterations the `Gjk` distance algorithm will perform before returning the distance between two separated convex shapes.
Returns:
int the number of `Gjk` distance iterations
Since:
3.3.0
`setMaxDistanceIterations(int)`
• setMaxDistanceIterations

`public void setMaxDistanceIterations​(int maxIterations)`
Sets the maximum number of iterations the `Gjk` distance algorithm will perform when determining the distance between two convex shapes.

Valid values are in the range [5, ∞].

Parameters:
`maxIterations` - the maximum number of `Gjk` distance iterations
Throws:
`java.lang.IllegalArgumentException` - if maxIterations is less than 5
Since:
3.3.0
• getMaxRaycastIterations

`public int getMaxRaycastIterations​()`
Returns the maximum number of iterations the `Gjk` raycast algorithm will perform before returning that the ray and the convex are not overlapping.
Returns:
int the number of `Gjk` raycast iterations
Since:
3.3.0
`setMaxRaycastIterations(int)`
• setMaxRaycastIterations

`public void setMaxRaycastIterations​(int maxIterations)`
Sets the maximum number of iterations the `Gjk` raycast algorithm will perform when checking whether the ray intersects the convex.

Valid values are in the range [5, ∞].

Parameters:
`maxIterations` - the maximum number of `Gjk` raycast iterations
Throws:
`java.lang.IllegalArgumentException` - if maxIterations is less than 5
Since:
3.3.0
• setDetectEpsilon

`public void setDetectEpsilon​(double detectEpsilon)`
The minimum distance to determine that two shapes are not colliding.

Valid values are in the range [0, ∞].

Parameters:
`detectEpsilon` - the `Gjk` detect epsilon
Throws:
`java.lang.IllegalArgumentException` - if detectEpsilon is less than zero
Since:
3.3.0
• setRaycastEpsilon

`public void setRaycastEpsilon​(double raycastEpsilon)`
The minimum distance between the ray and convex for the `Gjk` raycast algorithm.

Valid values are in the range (0, ∞].

Parameters:
`raycastEpsilon` - the `Gjk` raycast epsilon
Throws:
`java.lang.IllegalArgumentException` - if raycastEpsilon is less than or equal to zero
Since:
3.3.0
• setDistanceEpsilon

`public void setDistanceEpsilon​(double distanceEpsilon)`
The minimum distance between two iterations of the `Gjk` distance algorithm.

Valid values are in the range (0, ∞].

Parameters:
`distanceEpsilon` - the `Gjk` distance epsilon
Throws:
`java.lang.IllegalArgumentException` - if distanceEpsilon is less than or equal to zero
• setMinkowskiPenetrationSolver

`public void setMinkowskiPenetrationSolver​(MinkowskiPenetrationSolver minkowskiPenetrationSolver)`
Sets the `MinkowskiPenetrationSolver` used to obtain the penetration vector and depth.
Parameters:
`minkowskiPenetrationSolver` - the `MinkowskiPenetrationSolver`
Throws:
`java.lang.NullPointerException` - if minkowskiPenetrationSolver is null
• setMaxIterations

```@Deprecated
public void setMaxIterations​(int maxIterations)```
Deprecated. replaced with `setMaxDistanceIterations(int)` since 3.3.0
Sets the maximum number of iterations the `Gjk` algorithm will perform when computing the distance between two separated bodies.

Valid values are in the range [5, ∞].

Parameters:
`maxIterations` - the maximum number of `Gjk` iterations
Throws:
`java.lang.IllegalArgumentException` - if maxIterations is less than 5