libccd

The Minkowski Portal Refinement (MPR) algorithm can be used for both intersection testing and penetration information.

Unlike GJK, MPR requires two additional functions for each object:

1. A support function (same as GJK).
2. A center function that returns the center (or any point near the center) of the object.

To use MPR:

• For intersection only: Use ccdMPRIntersect().
• For penetration info: Use ccdMPRPenetration().
• Set ccd.mpr_tolerance in the ccd_t structure.

#include <ccd/ccd.h>

// Support function
void support(const void *obj, const ccd_vec3_t *dir, ccd_vec3_t *vec) { /* ... */ }

// Center function
void center(const void *_obj, ccd_vec3_t *center) {
    obj_t *obj = (obj_t *)_obj;
    ccdVec3Copy(center, &obj->pos);
}

int main() {
    ccd_t ccd;
    CCD_INIT(&ccd);
    ccd.support1 = support;
    ccd.support2 = support;
    ccd.center1 = center;
    ccd.center2 = center;
    ccd.mpr_tolerance = 0.0001;

    // Intersection test
    int intersect = ccdMPRIntersect(obj1, obj2, &ccd);

    // Penetration test
    ccd_real_t depth;
    ccd_vec3_t dir, pos;
    int res = ccdMPRPenetration(obj1, obj2, &ccd, &depth, &dir, &pos);
}

The Gilbert-Johnson-Keerthi (GJK) algorithm is used to test if two convex objects intersect (a boolean 'yes/no' test).

To use GJK, you must:

1. Include <ccd/ccd.h>.
2. Implement a support function for your specific shapes. This function must return the furthest point from the object in a specified direction.
3. Initialize a ccd_t structure using the CCD_INIT(&ccd) macro.
4. Assign your support functions to ccd.support1 and ccd.support2.
5. Call ccdGJKIntersect(obj1, obj2, &ccd).

#include <ccd/ccd.h>

// User-defined support function
void support(const void *obj, const ccd_vec3_t *dir, ccd_vec3_t *vec) {
    // ... implementation ...
}

int main() {
    ccd_t ccd;
    CCD_INIT(&ccd);
    ccd.support1 = support;
    ccd.support2 = support;
    ccd.max_iterations = 100;

    int intersect = ccdGJKIntersect(obj1, obj2, &ccd);
    // intersect is true if objects intersect
}

If two objects intersect and you need to know how much they are penetrating, use the ccdGJKPenetration() function. This combines GJK with the Expanding Polytope Algorithm (EPA).

In addition to the support functions required for GJK, you should configure epa_tolerance in the ccd_t structure to control the precision of the EPA phase.

ccdGJKPenetration returns:

• An integer indicating if an intersection exists.
• depth: The penetration depth.
• dir: The direction of the separation vector.
• pos: The position in the global coordinate system.

#include <ccd/ccd.h>

int main(int argc, char *argv[])
{
    // ... setup objects ...

    ccd_t ccd;
    CCD_INIT(&ccd); // initialize ccd_t struct

    ccd.support1       = support; 
    ccd.support2       = support; 
    ccd.max_iterations = 100;     
    ccd.epa_tolerance  = 0.0001;  // maximal tolerance for EPA part

    ccd_real_t depth;
    ccd_vec3_t dir, pos;
    int intersect = ccdGJKPenetration(obj1, obj2, &ccd, &depth, &dir, &pos);
    // intersect holds true if obj1 and obj2 intersect
    // depth, dir, and pos store penetration depth, separation direction, and global position
}

Use the ccdMPRPenetration() function to obtain penetration information using the MPR algorithm.

Similar to the intersection test, you must provide support functions and center functions for both objects. You should also set mpr_tolerance in the ccd_t structure.

ccdMPRPenetration returns:

• An integer indicating if an intersection exists.
• depth: The penetration depth.
• dir: The direction of the separation vector.
• pos: The position in the global coordinate system.

#include <ccd/ccd.h>

int main(int argc, char *argv[])
{
    // ... setup objects ...

    ccd_t ccd;
    CCD_INIT(&ccd); // initialize ccd_t struct

    ccd.support1       = support; 
    ccd.support2       = support; 
    ccd.center1        = center; 
    ccd.center2        = center; 
    ccd.mpr_tolerance  = 0.0001; 

    ccd_real_t depth;
    ccd_vec3_t dir, pos;
    int intersect = ccdMPRPenetration(obj1, obj2, &ccd, &depth, &dir, &pos);
    // intersect holds true if obj1 and obj2 intersect
    // depth, dir, and pos store penetration depth, separation direction, and global position
}

The Minkowski Portal Refinement (MPR) algorithm can be used as an alternative to GJK for intersection testing.

To use MPR, you must implement two types of functions for each object:

1. A support function (same as GJK).
2. A center function that returns a point near the center of the object.

Configure the ccd_t structure with support1, support2, center1, center2, and mpr_tolerance. Then call ccdMPRIntersect(obj1, obj2, &ccd).

#include <ccd/ccd.h>

/** Center function - returns center of object */
void center(const void *_obj, ccd_vec3_t *center)
{
    obj_t *obj = (obj_t *)_obj;
    ccdVec3Copy(center, &obj->pos);
}

int main(int argc, char *argv[])
{
    // ... setup objects ...

    ccd_t ccd;
    CCD_INIT(&ccd); // initialize ccd_t struct

    ccd.support1       = support; 
    ccd.support2       = support; 
    ccd.center1        = center;  // center function for first object
    ccd.center2        = center;  // center function for second object
    ccd.mpr_tolerance  = 0.0001;  // maximal tolerance

    int intersect = ccdMPRIntersect(obj1, obj2, &ccd);
    // intersect holds true if obj1 and obj2 intersect
}

Use the Gilbert-Johnson-Keerthi (GJK) algorithm to perform a boolean 'yes/no' intersection test between two convex objects.

To use GJK, you must:

1. Include <ccd/ccd.h>.
2. Implement a support function for each shape. This function takes an object and a direction vector, and returns the furthest point from the object in that direction.
3. Initialize a ccd_t structure using CCD_INIT(&ccd).
4. Configure the ccd_t structure with your support functions and max_iterations.
5. Call ccdGJKIntersect(obj1, obj2, &ccd).

#include <ccd/ccd.h>

// ... implement support function ...

int main(int argc, char *argv[])
{
    // ... setup objects ...

    ccd_t ccd;
    CCD_INIT(&ccd); // initialize ccd_t struct

    // set up ccd_t struct
    ccd.support1       = support; // support function for first object
    ccd.support2       = support; // support function for second object
    ccd.max_iterations = 100;     // maximal number of iterations

    int intersect = ccdGJKIntersect(obj1, obj2, &ccd);
    // intersect holds true if obj1 and obj2 intersect, false otherwise
}