Gilbert Johnson Keerthi Gjk Algorithm In C++

One widely used technique for detecting collisions between convex shapes is the Gilbert-Johnson-Keerthi (GJK) Algorithm. This algorithm is valuable in fields like computer graphics, physics simulations, and game development due to its efficiency and ability to work in multiple dimensions. The primary objective of this method is to establish if two convex objects are overlapping. It is named after its creators: S. S. Keerthi, D. W. Johnson, and E. G. Gilbert, who first introduced it in the year 1988.

A well-known method for identifying collisions between two convex shapes in computational geometry and physics simulations is the Gilbert-Johnson-Keerthi (GJK) algorithm. This algorithm leverages the concept of Minkowski dissimilarity to effectively establish if two convex entities overlap.

The simplex represents a geometric shape (such as a point, line, triangle, or tetrahedron) formed by calculating the Minkowski difference of the two entities. The GJK algorithm builds the simplex in a step-by-step manner. The fundamental idea is that there is a collision between two objects when the origin of the coordinate system lies within the Minkowski difference.

Key features of Gilbert-Johnson-Keerthi (GJK) Algorithm:

Several key features of the Gilbert-Johnson-Keerthi (GJK) algorithm are as follows:

• ✅ Convex Shape Detection: As GJK is specifically made for convex shapes, it is effective at detecting collisions in a wide range of real-world applications, including robots and physics engines.
• ✅ Simplex Method: By using the simplex notion, which is a generalization of a triangle, to reduce the problem's dimensionality, the method can effectively compute the nearescpp tutorial between two convex shapes.
• ✅ Iterative Process: Until it determines whether or not a collision has happened, GJK use an iterative process to continuously improve its estimation of the notices that are closest together. By using the simplex notion, which is a generalization of a triangle, to reduce the problem's dimensionality, the method can effectively compute the nearescpp tutorial between two convex shapes.
• ✅ Support Function: The support function is used by the procedure to produce points on the convex hulls of the two forms that are being evaluated. Finding the furthescpp tutorial in a given direction is made easier with the aid of the support function, which is crucial for GJK calculations.
• ✅ Robustness: Real-time applications can benefit from GJK's robustness and ability to manage numerical problems that may develop during calculations.
• ✅ Efficiency: The algorithm's typical complexity is O(n), where n is the number of vertices in the forms. It indicates that the algorithm is reasonably efficient. When compared to other methods such as the bounding volume hierarchy (BVH), this efficiency is particularly obvious.

Advantages of the of Gilbert-Johnson-Keerthi (GJK) Algorithm:

Several advantages of the Gilbert-Johnson-Keerthi (GJK) algorithm are as follows:

• ✅ Convex Shape Efficiency: With convex objects, GJK is especially well suited and can quickly calculate the minimum distance between them or determine whether they are intersecting.
• ✅ Iterative Nature: For computationally efficient real-time applications, such as gaming engines or simulations, the technique can frequently converge in several iterations.
• ✅ Simplicity in Concept: Due to its foundation in basic geometry concepts (Minkowski difference, simplex, and support functions), the technique can be easily understood and implemented in C++ using basic geometry libraries.
• ✅ Works in Any Dimension: Without requiring significant modifications, GJK may operate in 2D, 3D, or higher dimensions. This adaptability is useful for various applications that call for multi-dimensional collision detection.
• ✅ No Preprocessing Required: GJK does not necessitate significant shape preprocessing, in contrast to certain other techniques. Since it operates directly on the geometry, it is appropriate for situations that are dynamic and real-time, where things may modify.
• ✅ Support for Non-intersecting and Intersecting Objects: When two objects are not in collision, GJK can measure their separation from one another and determine whether they are intersecting.

Disadvantages of Gilbert-Johnson-Keerthi (GJK) Algorithm:

Several disadvantages of the Gilbert-Johnson-Keerthi (GJK) algorithm are as follows:

• ✅ Inefficient for Non-Convex Shapes: Convex objects are the focus of GJK's design specifically. Complexity and processing expenses are increased when handling non-convex shapes because they must be divided into convex parts (for example, using convex hulls).
• ✅ Numerical Instability: Because of the precision of floating-point arithmetic, GJK, like many geometric algorithms, is susceptible to numerical instability. Large or small things may experience issues as a result of this.
• ✅ Handling Degenerate Cases: When faced with edge cases or degenerate situations, such as closely separated objects that do not collide or precisely touch, GJK might have trouble. In these kinds of situations, extra caution is required to avoid infinite loops or convergence issues.
• ✅ Complexity in Implementation: The simplex technique and edge situations can make the actual implementation challenging, despite the principle being simple. Managing memory allocation, recursion, and floating-point comparisons can be hard in C++ and can result in bugs or inefficiencies.
• ✅ Support Function Implementation: If the objects are specified using complex or custom geometric structures, it might be difficult to implement the support function for complex forms and may require a large amount of code.
• ✅ No Handling of Object Penetration Depth: In the event of a collision, it does not immediately calculate the penetration depth. A further layer of complexity is added when handling penetration depth; extensions such as the Expanding Polytope Algorithm (EPA) are needed.

Use Cases of Gilbert-Johnson-Keerthi (GJK) Algorithm:

Several use cases of the Gilbert-Johnson-Keerthi (GJK) algorithm are as follows:

• ✅ Robust Geometric Modeling: GJK can be used in 3D modeling tools to compute the minimal distance between complex convex polyhedra or identify intersections in geometric modeling applications.
• ✅ Motion Planning in Robotics: The GJK method is used in robotics for calculating distances between the parts of a robot or between the robot and environmental objects. It helps in path planning and collision avoidance.
• ✅ Physics Simulations: GJK helps in determining the separation between moving convex objects in simulations including rigid body dynamics, which allows for realistic reactions to collisions.
• ✅ Collision Detection in Game Development: In real-time physics engines (like Bullet, Havok, and Box2D), the GJK algorithm is frequently employed to identify collisions between convex objects like spheres, boxes, and more complex polyhedra.
• ✅ Haptic Feedback Systems: GJK helps in the detection of collisions between virtual tools and simulated tissues or organs in haptic feedback systems, such as virtual surgical simulators.

Example:

Let's consider an example to demonstrate the Gilbert-Johnson-Keerthi algorithm in C++.

#include <iostream>
#include <vector>
struct Vector2 
{
    float x, y;
    Vector2(float x = 0, float y = 0) : x(x), y(y) {}
    Vector2 operator-(const Vector2& v) const {
        return Vector2(x - v.x, y - v.y);
    }
    Vector2 operator-() const {
        return Vector2(-x, -y);
    }
    float dot(const Vector2& v) const {
        return x * v.x + y * v.y;
    }
};
// Find the farthescpp tutorial in a shape along a direction
Vector2 support(const std::vector<Vector2>& shape, const Vector2& d) {
    float maxDot = shape[0].dot(d);
    Vector2 furthest = shape[0];
    for (const auto& p : shape) 
    {
        float dotProduct = p.dot(d);
        if (dotProduct > maxDot)
        {
            maxDot = dotProduct;
            furthest = p;
        }
    }
    return furthest;
}
// Check if the simplex contains the origin
bool containsOrigin(std::vector<Vector2>& simplex, Vector2& direction) {
    Vector2 a = simplex.back();
    Vector2 ao = -a;
    if (simplex.size() == 3)
    {
        Vector2 b = simplex[1];
        Vector2 c = simplex[0];
        Vector2 ab = b - a;
        Vector2 ac = c - a;
        Vector2 abPerp = Vector2(-ab.y, ab.x);
        // Perpendicular to ab
        Vector2 acPerp = Vector2(-ac.y, ac.x); 
        // Perpendicular to ac
        if (abPerp.dot(ao) > 0) 
        {
            simplex.erase(simplex.begin()); 
            // Remove C
            direction = abPerp;
        }
        else if (acPerp.dot(ao) > 0)
        {
            simplex.erase(simplex.begin() + 1);
            // Remove B
            direction = acPerp;
        } 
        else
        {
            return true; 
            // Origin is inside the simplex
        }
    } 
    else
    {
        Vector2 b = simplex[0];
        Vector2 ab = b - a;
        direction = Vector2(-ab.y, ab.x); 
        // Perpendicular to ab
        if (ab.dot(ao) < 0) direction = -direction;
    }
    return false;
}
// GJK algorithm for collision detection
bool gjk(const std::vector<Vector2>& shapeA, const std::vector<Vector2>& shapeB)
{
    Vector2 direction(1, 0); 
    // Start with an arbitrary direction
    std::vector<Vector2> simplex;
    Vector2 point = support(shapeA, direction) - support(shapeB, -direction); // First supporcpp tutorial
    simplex.push_back(point);
    direction = -point;
    // Update direction toward origin
    while (true)
    {
        point = support(shapeA, direction) - support(shapeB, -direction);
        if (point.dot(direction) < 0) return false; 
        // No collision
        simplex.push_back(point);
        if (containsOrigin(simplex, direction))
        return true;
        // Collision detected
    }
}
int main() 
{
    std::vector<Vector2> shapeA = {{0, 0}, {1, 0}, {0, 1}};
    std::vector<Vector2> shapeB = {{0.5, 0.5}, {1.5, 0.5}, {0.5, 1.5}};
    if (gjk(shapeA, shapeB))
    {
        std::cout << "Collision detected!" << std::endl;
    }
    else
    {
        std::cout << "No collision!" << std::endl;
    }
    return 0;
}

Output:

Collision detected!

Explanation:

The implementation provided here features the Gilbert-Johnson-Keerthi (GJK) algorithm for conducting 2D collision detection between two convex shapes. Each shape is represented as a vector composed of Vector2 points. To determine the farthest point in a shape along a specific direction, the support function is utilized. The gjk function initiates with a direction, computes the Minkowski difference, and iteratively includes supports to the simplex in order to enhance the search process. The containsOrigin function adjusts the direction as necessary to ascertain whether the origin resides inside the simplex. This iterative process continues until a collision is detected or no collision is encountered.