Gjk Queries

Introduction

This section describes the special set of query functions operating on GJK Support Mappings.

GJK (Gilbert-Johnson-Keerthi) is an algorithm determining the minimum distance between two convex shapes. Unlike many other distance algorithms, it does not require the geometry data to be stored in any specific format, but instead relies solely on support mappings.

Support Mapping of a convex shape is a function that takes direction as an argument and returns the point on the shape’s surface farthest in a given direction.

Support Mapping Interface

Every function in this API expects a pair of support mapping objects. Each support mapping should implement the PxGjkQuery::Support interface, which has the following functions:

PxGjkQuery::Support::supportLocal() defining the shape’s core, and
PxGjkQuery::Support::getMargin() returning the shape’s margin.

The core of a shape is a convex hull of an arbitrary set of points. The supportLocal() function of the shape’s support mapping should be able to return the farthest point on the hull surface in any given direction.

The margin of a shape is the distance from the shape’s core where all points still belong to the shape.

For example, this code defines the support mapping of a sphere shape:

struct SphereSupport : PxGjkQuery::Support
{
    PxReal radius;
    virtual PxReal getMargin() const { return radius; }
    virtual PxVec3 supportLocal(const PxVec3& dir) const
        { return PxVec3(0, 0, 0); }
};

Here the sphere’s core is a single point - [0 0 0], and the sphere’s margin is its radius.

A slightly more complex example is the support mapping of a capsule shape:

struct CapsuleSupport : PxGjkQuery::Support
{
    PxReal radius, halfHeight;
    virtual PxReal getMargin() const { return radius; }
    virtual PxVec3 supportLocal(const PxVec3& dir) const
        { return PxVec3((dir.x > 0 ? halfHeight : -halfHeight), 0, 0); }
};

The capsule’s core is a line segment, thus, depending on the direction, the supportLocal() function returns one of the two end points of this segment, either [halfHeight 0 0] or [-halfHeight 0 0]. The margin of a capsule is its radius, same as for a sphere.

Queries

Queries are simple tests for two shapes located in space.

PxGjkQuery::overlap()

bool PxGjkQuery::overlap(const Support& a, const Support& b,
        const PxTransform& poseA, const PxTransform& poseB);

PxGjkQuery::overlap() query tests if two shapes intersect. It returns true if they do.

PxGjkQuery::sweep()

bool PxGjkQuery::sweep(const Support& a, const Support& b,
        const PxTransform& poseA, const PxTransform& poseB,
        const PxVec3& unitDir, PxReal maxDist,
        PxReal& t, PxVec3& n, PxVec3& p);

PxGjkQuery::sweep() query tests if one moving shape B hits the other stationary shape A. It returns true if the hit occurs, and computes the hit distance, hit normal, and hit point.

PxGjkQuery::raycast()

bool PxGjkQuery::raycast(const Support& shape, const PxTransform& pose,
        const PxVec3& rayStart, const PxVec3& unitDir, PxReal maxDist,
        PxReal& t, PxVec3& n, PxVec3& p);

PxGjkQuery::raycast() query tests a ray against a shape. It returns true if the ray hits the shape, and computes the hit distance, hit normal, and hit point. Internally a raycast is a sweep of a point (or a sphere with zero radius) against a shape.

PxGjkQuery::proximityInfo()

bool PxGjkQuery::proximityInfo(const Support& a, const Support& b,
        const PxTransform& poseA, const PxTransform& poseB,
        PxReal contactDistance, PxReal toleranceLength,
        PxVec3& pointA, PxVec3& pointB, PxVec3& separatingAxis,
        PxReal& separation);

PxGjkQuery::proximityInfo() query returns true if the distance between two shapes is smaller than the provided contact distance. It also computes such proximity information as the closest/deepest points on the shapes’ surfaces, the axis separating two shapes (the separating plane normal), and the separation/penetration distance.

Extensions

PhysXExtensions module’s PxGjkQueryExt API provides several auxiliary classes and functions for PxGjkQuery API. This includes 5 pre-made support mappings and a contact generation helper function.

Pre-made support mappings

There are 4 support mappings for convex geometry types:

And a universal support mapping which automatically detects any of the four types above and internally creates the corresponding support mapping.

PxGjkQueryExt::ConvexGeomSupport

PxGjkQueryExt::generateContacts()

bool PxGjkQueryExt::generateContacts(
        const PxGjkQuery::Support& a, const PxGjkQuery::Support& b,
        const PxTransform& poseA, const PxTransform& poseB,
        PxReal contactDistance, PxReal toleranceLength,
        PxContactBuffer& contactBuffer);

PxGjkQueryExt::generateContacts() function internally uses PxGjkQuery::proximityInfo() query and then writes its result as a contact to the provided contact buffer.