Spatial Queries

Applications commonly need to efficiently query volumes in space or trace rays or moving objects through space to determine what might be there. PhysX supports two interfaces for this, one for objects already in a scene, and one for querying against sets of arbitrary AABBs. The scene query system is discussed in Scene Queries.

PxSpatialIndex

PxSpatialIndex is a BVH data structure that allows spatial queries to be performed without the need to instantiate a PxScene. It supports insertion, removal and updating of any objects defining a bounding box, and raycasts, sweeps, and overlap queries against those bounds.

SnippetSpatialIndex shows an example of how to use this class.

PxSpatialIndex has no internal locking, and there are special considerations when using it from multiple threads. Query operations (marked const in the interface) must not be issued in parallel with update (non-const) operations, or update operations in parallel with each other. When issuing query operations in parallel, it is important to be aware that PxSpatialIndex defers some updates to its internal data structures until a query is issued. In a single-threaded context this does not affect correctness or safety, but when querying from multiple threads simultaneously the internal updates may cause data hazards. In order to avoid these, call the flush() method to force the updates to be processed immediately. Between a call to flushUpdates() and any subsequent update operation, queries may be safely issued in parallel.

A query against a PxSpatialIndex structure will result in a callback for each AABB hit by the query, allowing filtering or precise intersection as desired. The methods in the PxGeometryQuery class can be used to perform these intersection tests. Results will typically be in approximately sorted order, and when looking for the closest object in a raycast or sweep query against PxSpatialIndex, a useful optimization is to clip the length of the query inside the callback. For example, in SnippetSpatialIndex:

PxAgain onHit(PxSpatialIndexItem& item, PxReal distance, PxReal& shrunkDistance)
{
    PX_UNUSED(distance);

    Sphere& s = static_cast<Sphere&>(item);
    PxRaycastHit hitData;

    // the ray hit the sphere's AABB, now we do a ray-sphere intersection test to find out if
    // the ray hit the sphere

    PxU32 hit = PxGeometryQuery::raycast(position, direction,
                                         PxSphereGeometry(s.radius), PxTransform(s.position),
                                         1e6, PxHitFlag::eDEFAULT,
                                         1, &hitData);

    // if the raycast hit and it's closer than what we had before, shrink the maximum length
    // of the raycast

    if(hit && hitData.distance < closest)
    {
        closest = hitData.distance;
        hitSphere = &s;
        shrunkDistance = hitData.distance;
    }

    // and continue the query

    return true;
}

Note

Methods in PxGeometryQuery may report positive results when shapes are within a numerical tolerance of intersection or impact. To obtain results that are identical when using PxSpatialIndex and when not using a culling hierarchy, the bounding boxes must be slightly padded. PxGeometryQuery::getWorldBounds adds this padding by default.

PxSpatialIndex has the same performance characteristics as the scene query system using the PxPruningStructure::eDYNAMIC_AABB_TREE option. If the AABBs correspond to moving objects, or there are many insertions and deletions, the quality of the tree may degrade over time. In order to prevent this, the tree may be rebuilt entirely using the function rebuildFull(). Alternatively, a second tree may be built incrementally in the background over many small steps, using the function rebuildStep() to performs the same incremental rebuild step as performed by the scene's dynamic pruning structure during fetchResults(). See PxPruningStructure for details.