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.4.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
`protected double` `detectEpsilon`
The collision detection epsilon in meters
`protected double` `distanceEpsilon`
The distance check epsilon in meters
`protected int` `maxDetectIterations`
The maximum number of collision detection iterations
`protected int` `maxDistanceIterations`
The maximum number of distance check iterations
`protected int` `maxRaycastIterations`
The maximum number of raycast iterations
`protected MinkowskiPenetrationSolver` `minkowskiPenetrationSolver`
The penetration solver; defaults to `Epa`
`protected double` `raycastEpsilon`
The raycast check epsilon in meters
• ### Constructor Summary

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

All Methods
Modifier and Type Method Description
`protected boolean` ```checkSimplex​(java.util.List<Vector2> simplex, Vector2 direction)```
Determines whether the given simplex contains the origin.
`protected boolean` ```containsOrigin​(Vector2 a, Vector2 b, Vector2 c)```
Returns true if the origin is within the triangle given by a, b, and c.
`protected boolean` ```detect​(MinkowskiSum ms, java.util.List<Vector2> simplex, Vector2 d)```
The main `Gjk` algorithm loop.
`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.
`protected void` ```findClosestPoints​(MinkowskiSumPoint a, MinkowskiSumPoint b, Separation separation)```
Finds the closest points on A and B given the termination simplex and places them into point1 and point2 of the given `Separation` object.
`double` `getDetectEpsilon()`
Returns the `Gjk` detect epsilon.
`double` `getDistanceEpsilon()`
Returns the `Gjk` distance epsilon.
`protected Vector2` ```getInitialDirection​(Convex convex1, Transform transform1, Convex convex2, Transform transform2)```
Returns a vector for the initial direction for the GJK algorithm in world coordinates.
`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

`clone, equals, finalize, 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
• #### minkowskiPenetrationSolver

`protected MinkowskiPenetrationSolver minkowskiPenetrationSolver`
The penetration solver; defaults to `Epa`
• #### maxDetectIterations

`protected int maxDetectIterations`
The maximum number of collision detection iterations
• #### maxDistanceIterations

`protected int maxDistanceIterations`
The maximum number of distance check iterations
• #### maxRaycastIterations

`protected int maxRaycastIterations`
The maximum number of raycast iterations
• #### detectEpsilon

`protected double detectEpsilon`
The collision detection epsilon in meters
• #### distanceEpsilon

`protected double distanceEpsilon`
The distance check epsilon in meters
• #### raycastEpsilon

`protected double raycastEpsilon`
The raycast check epsilon in meters
• ### 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

• #### getInitialDirection

```protected Vector2 getInitialDirection​(Convex convex1,
Transform transform1,
Convex convex2,
Transform transform2)```
Returns a vector for the initial direction for the GJK algorithm in world coordinates.

This implementation returns the vector from the center of the first convex to the center of the second.

Parameters:
`convex1` - the first convex
`transform1` - the first convex's transform
`convex2` - the second convex
`transform2` - the second convex's transform
Returns:
Vector2
• #### detect

```protected boolean detect​(MinkowskiSum ms,
java.util.List<Vector2> simplex,
Vector2 d)```
The main `Gjk` algorithm loop.

Returns true if a collision was detected and false otherwise.

The simplex and direction parameters will reflect the state of the algorithm at termination, whether a collision was found or not. This is useful for subsequent algorithms that use the GJK simplex to find the collision information (`Epa` for example).

Parameters:
`ms` - the `MinkowskiSum`
`simplex` - the simplex; should be an empty list
`d` - the initial direction
Returns:
boolean
• #### checkSimplex

```protected boolean checkSimplex​(java.util.List<Vector2> simplex,
Vector2 direction)```
Determines whether the given simplex contains the origin. If it does contain the origin, then this method will return true. If it does not, this method will update both the given simplex and also the given search direction.

This method only handles the line segment and triangle simplex cases, however, these two cases should be the only ones needed for 2 dimensional `Gjk`. The single point case is handled in `detect(MinkowskiSum, List, Vector2)`.

This method also assumes that the last point in the simplex is the most recently added point. This matters because optimizations are available when you know this information.

Parameters:
`simplex` - the simplex
`direction` - the search direction
Returns:
boolean true if the simplex contains the origin
• #### findClosestPoints

```protected void findClosestPoints​(MinkowskiSumPoint a,
MinkowskiSumPoint b,
Separation separation)```
Finds the closest points on A and B given the termination simplex and places them into point1 and point2 of the given `Separation` object.

The support points used to obtain a and b are not good enough since the support methods of `Convex` `Shape`s only return the farthest vertex, not necessarily the farthest point.

Parameters:
`a` - the first simplex point
`b` - the second simplex point
`separation` - the `Separation` object to populate
GJK - Distance & Closest Points
• #### containsOrigin

```protected boolean containsOrigin​(Vector2 a,
Vector2 b,
Vector2 c)```
Returns true if the origin is within the triangle given by a, b, and c.

If the origin lies on the same side of all the points then we know that the origin is in the triangle.

` sign(location(origin, a, b)) == sign(location(origin, b, c)) == sign(location(origin, c, a))`
The `Segment.getLocation(Vector2, Vector2, Vector2)` method can be simplified because we are using the origin as the search point:
``` = (b.x - a.x) * (origin.y - a.y) - (origin.x - a.x) * (b.y - a.y)
= (b.x - a.x) * (-a.y) - (-a.x) * (b.y - a.y)
= -a.y * b.x + a.y * a.x + a.x * b.y - a.x * a.y
= -a.y * b.x + a.x * b.y
= a.x * b.y - a.y * b.x
= a.cross(b)```
Parameters:
`a` - the first point
`b` - the second point
`c` - the third point
Returns:
boolean
• #### 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.
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