Scene Queries

PhysX provides methods in PxScene to perform collision queries against the actors in the scene. The queries come in three types: raycasts, sweeps and overlaps. Moreover, each query type has several variants. The API supports batching of queries via the PxBatchQuery interface, which may provide significant speedups for some platforms and scenarios. In particular, on PS3 only batched queries are SPU-accelerated.

Raycast queries

A raycast intersects a user-defined ray with the whole scene. PhysX raycasts can be viewed as having 4 different modes of operation:

  • raycast with PxRaycastBuffer buf; and PxQueryFlag::eANY_HIT parameter for any hit type query.
  • raycast with PxRaycastBuffer buf; parameter using default constructor for single closest blocking hit type query.
  • raycast with PxRaycastBuffer buf(hits, nbHits); parameter with touch hits constructor when multiple touching hits and a single blocking hit are needed.
  • raycast with a user custom callback deriving from PxRaycastCallback.

raycast with eANY_HIT returns a single boolean result. It is optimized for cases where the hit shape and impact point are not important. A typical use case would be AI line-of-sight queries:

PxScene* scene;
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance
PxRaycastBuffer hit;                 // [out] Raycast results

// Raycast against all static & dynamic objects (no filtering)
// The main result from this call is the boolean 'status'
PxQueryFilterData fd; fd.flags |= PxQueryFlag::eANY_HIT;
bool status = scene->raycast(origin, unitDir, maxDistance, hit, PxHitFlags(PxHitFlag::eDEFAULT), fdAny);

raycast with PxRaycastBuffer buf; returns a single result: the closest intersected blocking shape along the ray, if any, along with the exact hit information. This can be used for simple bullets, for example:

PxScene* scene;
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance
PxRaycastBuffer hit;                 // [out] Raycast results

// Raycast against all static & dynamic objects (no filtering)
// The main result from this call is the closest hit, stored in the 'hit.block' structure
bool status = scene->raycast(origin, unitDir, maxDistance, hit);

raycast with PxRaycastBuffer buf(hits, nbHits); finds all the objects touched by the ray, along with all the corresponding hits. The first blocking hit will be stored in the buffer.block member. For example this could be used to detect all the tree leaves hit along the way up until the bullet hits a solid wall:

PxScene* scene;
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance

const PxU32 bufferSize = 256;        // [in] size of 'hitBuffer'
PxRaycastHit hitBuffer[bufferSize];  // [out] User provided buffer for results
PxRaycastBuffer buf(hitBuffer, bufferSize); // [out] Blocking and touching hits will be stored here

// Raycast against all static & dynamic objects (no filtering)
// The main result from this call are all hits along the ray, stored in 'hitBuffer'
bool hadBlockingHit = scene->raycast(origin, unitDir, maxDistance, buf);
if (hadBlockingHit)
    drawWallDecal(buf.block);
for (PxU32 i = 0; i < buf.nbTouches; i++)
    animateLeaves(buf.touches[i]);

raycast with PxRaycastCallback user-derived callback will return multiple touch hits via a virtual PxHitCallback::processTouches() callback:

struct UserCallback : PxRaycastCallback
{
    UserData data;
    virtual PxAgain processTouches(const PxRaycastHit* buffer, PxU32 nbHits)
        // this callback can be issued multiple times and can be used to process an unbounded number of touching hits
        // each reported touching hit in buffer is guaranteed to be closer than the final block hit after the query has fully executed
    {
        for (PxU32 i = 0; i < nbHits; i++)
            animateLeaves(buffer[i], data);
    }
    virtual void finalizeQuery()
    {
        drawWallDecal(this->block, data);
    }
};

PxScene* scene;
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance

UserCallback cb; cb.data = ...;
scene->raycast(origin, unitDir, maxDistance, cb); // see UserCallback::processTouches

Notes:

  • Solid objects (sphere, capsule, box, convex) are defined as closed (i.e. they include their boundaries.)
  • A plane is a closed half-space

When raycasting against solid objects, the rays include their endpoints. Any intersection between a ray and a solid object results in a hit report.

For solid objects (sphere, capsule, box, convex) and heightfields PhysX will report a hit:

  1. if the start point or the end point is inside a solid object.
  2. if the start point or the end point is on the surface of a solid object.

In the case that the start point is inside a solid object:

  1. the reported hit distance is set to zero.
  2. the hit normal is in the opposite direction to the ray.
  3. the hit impact position is the start point of the ray.

For Planes: If the start point is behind the plane's surface, no hit will be reported even in the case that the ray intersects the plane. If the start point is on the plane, a hit with zero distance will be reported.

A mesh may be treated either as double-sided or single-sided (see below for how to specify this). Backface culling is enabled for single-sided meshes, disabled for double-sided ones.

If the start point is on the surface for both kinds of meshes, PhysX will not report a hit. If the end point is on the surface for both kinds of meshes, PhysX will report a hit. If the start point is on the back of a mesh triangle, and the ray intersects the triangle, PhysX will:

  1. report a hit for the double-sided mesh.
  2. report no hit for the single-sided mesh.

To summarize, here are the tables for the definition of raycast behavior.

Solid Shape

  Start Pt Inside Start Pt On the Surface Start Pt Outside
End Pt Inside HIT HIT HIT
End Pt On the Surface HIT HIT HIT
End Pt Outside HIT HIT MISS

Plane

  Start Pt Behind Start Pt On the Plane Start Pt in Front
End Pt Behind MISS HIT HIT
End Pt On the Plane MISS HIT HIT
End Pt in Front MISS HIT MISS

Double-Sided Mesh and HeightField

  Start Pt Behind Triangle Start Pt On the Triangle Start Pt in Front of Triangle
End Pt Behind Triangle MISS MISS HIT
End Pt On the Triangle HIT MISS HIT
End Pt in Front of Triangle HIT MISS MISS

Single-Sided Mesh and HeightField

  Start Pt Behind Triangle Start Pt On the Triangle Start Pt in Front of Triangle
End Pt Behind Triangle MISS MISS HIT
End Pt On the Triangle MISS MISS HIT
End Pt in Front of Triangle MISS MISS MISS

Sweep queries

Sweep API closely resembles raycast with a difference that a PxGeometry is swept starting at PxTransform pose initial pose in direction unitDir with specified maximum sweep length. Overlaps of swept geometry with scene objects are then reported. The distance of sweep must be larger than or equal to 0. It will be clamped to PX_MAX_SWEEP_DISTANCE which is defined in file PxScene.h. The currently supported input shapes are boxes, spheres, capsules and convex.

Notes:

  • By default initially overlapping sweeps are reported as hits with 0 distance. Internally this uses a specialized code path and incurs a performance penalty.
  • Specifying PxHitFlag::eINITIAL_OVERLAP_DISABLE parameter turns off this code path and boosts query performance in cases where it's known upfront that there is no initial overlap.
  • PxHitFlag::ePRECISE_SWEEP enables more accurate sweep code (by default a faster but less accurate solution is used).
  • Solid objects (sphere, capsule, box, convex) are defined as closed (i.e. they include their boundaries.)
  • A plane is a closed half-space.
  • Triangle Mesh is defined as thin triangle surface.
  • Heightfield is defined as thin triangle surface, the thickness of heightfield is ignored for sweeping test.
  • Sweeping volumes are defined as closed (i.e. they include their boundaries).
  • The inflation sweep() parameter can be used to inflate the swept geometry without modifying it.

Sweeps with Initial Intersection

The PxHitFlag::eINITIAL_OVERLAP_DISABLE flag is an optimization that can be enabled when it is guaranteed that the swept shape starts in a free volume of space, i.e. does not initially overlap any geometry. In that case, setting this flag will potentially make the sweep queries run faster.

By default however, PhysX properly detects these cases. If an initial overlap is found, the distance is set to zero, and the returned normal is set to the opposite of the sweep direction.

If the PxHitFlag::eINITIAL_OVERLAP_DISABLE flag is set even though the swept shape initially overlaps with some other shapes, then the behaviour is undefined.

If the sweep distance is exactly equal to 0, the sweep test is seen as an overlap test and the eINITIAL_OVERLAP_DISABLE flag can not be set. If the sweep distance is zero and the eINITIAL_OVERLAP_DISABLE flag is set, then a warning is generated and results are undefined.

Overlap Queries

In overlap queries, a shape is collided against the objects in the scene, and any touching object is reported. Otherwise the API is similar to raycast() and sweep() with some exceptions:

Overlaps do not support PxHitFlags since there's specific single point where overlap occurs. Overlaps do not currently support single hit blocking caches. Supported input shapes are box, spher, capsule and convex.

Notes:

  • Solid objects (sphere, capsule, box, convex) are defined as closed (i.e. they include their boundaries.)
  • A plane is a closed half-space
  • Triangle Mesh is defined as thin triangle surface.
  • Heightfield is defined as extruded triangle surface with thickness. Overlap geometries that do not intersect with heightfield surface but are within the extruded space also report a overlap hit.
  • Overlapping volumes are defined as closed.

PhysX does not use tolerance with overlap() queries. Instead, users can add their own tolerance to the overlapping volume by using a larger overlapping geometry before fill the query for PhysX. For example, use a large tolerance to get more broad results, use a small tolerance to get more accurate results.

Filtering

There are several ways to filter out undesired shapes from scene queries. Each scene query accepts the following filtering-related parameters:

  • a PxQueryFilterData structure, containing both PxQueryFlags and PxFilterData
  • an optional PxQueryFilterCallback

The first level of filtering is given by the PxQueryFlag::eSTATIC and PxQueryFlag::eDYNAMIC flags. These flags control whether the query takes static and/or dynamic shapes into account. This is the most efficient way to filter out all static shapes. For example an explosion effect which applies forces within a region could use the overlap query with a sphere shape, and the PxQueryFlag::eDYNAMIC flag to only consider dynamic objects, since it is useless to apply forces to static objects.

Returning to the initial raycast code snippets, a raycast call against static shapes only would be written like this:

PxScene* scene;
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance
PxRaycastBuffer hit;                 // [out] Raycast results

// [in] Define filter for static objects only
PxQueryFilterData filterData(PxQueryFlag::eSTATIC);

// Raycast against static objects only
// The main result from this call is the boolean 'status'
bool status = scene->raycast(origin, unitDir, maxDistance, hit, PxHitFlag::eDEFAULT, filterData);

In case of triangle meshes it is possible to receive multiple hits per mesh. To enable triangle mesh multiple hits set PxHitFlag::eMESH_MULTIPLE flag. This flag can be set in scene query flags and can be also set/cleared in pre-filter shader. SPU queries report at most 16 total hits per mesh, any hits after the 16th are discarded.

PxHitFlag::eMESH_ANY enables an optimized path for meshes - when this flag is used, any hit encountered with any of the mesh triangles will be returned as the hit.

It is also possible to generate hits for both front-facing and back-facing triangles of a mesh, using PxHitFlag::eMESH_BOTH_SIDES flag. A mesh is treated as double-sided if either PxHitFlag::eMESH_BOTH_SIDES or PxMeshGeometryFlag::eDOUBLE_SIDED is set, so a mesh with eDOUBLE_SIDED flag will always be treated as double-sided regardless of whether PxHitFlag::eMESH_BOTH_SIDES is set or not. If a mesh should sometimes be treated as single-sided and sometimes as double-sided, create it as single-sided and specify PxHitFlag::eMESH_BOTH_SIDES for the query, or set it in the hit filter callback.

The second level of filtering is controlled by PxFilterData, a 128-bit bitmask used by the built-in filtering equation. Each shape has a bitmask, set using PxShape::setQueryFilterData(), and the query also has a bitmask.

The query data is used differently by batched and unbatched queries (see below for batched queries.) For unbatcher queries, the following rules are applied:

  • If the query's bitmask is all zero, the shape is kept
  • Otherwise, if the bitwise-AND value of the query's bitmask and the shape's bitmask is zero, the shape is skipped

Or in other words:

PxU32 keep = (query.word0 & object.word0) | (query.word1 & object.word1) | (query.word2 & object.word2) | (query.word3 & object.word3);

The hardcoded filtering equation avoids the function call overhead of the filtering callback, while still providing reasonable filtering capabilities. This is similar to the "active groups" from previous versions of PhysX. For example, one can simply use the first word of filterData (word0) to emulate the behavior of previous PhysX versions. The active groups could be defined like this:

enum ActiveGroup
{
    GROUP1    = (1<<0),
    GROUP2    = (1<<1),
    GROUP3    = (1<<2),
    GROUP4    = (1<<3),
    ...
};

When shapes are created, they can be put in a single group, for example GROUP1:

PxShape* shape;                      // Previously created shape

PxFilterData filterData;
filterData.word0 = GROUP1;
shape->setQueryFilterData(filterData);

Or in several groups, for example GROUP1 and GROUP3:

PxShape* shape;                      // Previously created shape

PxFilterData filterData;
filterData.word0 = GROUP1|GROUP3;
shape->setQueryFilterData(filterData);

Then when performing a scene query, select which groups are active for the query - for example GROUP2 and GROUP3 here:

PxScene* scene;
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance
PxRaycastBuffer hit;                 // [out] Raycast results

// [in] Define what parts of PxRaycastHit we're interested in
const PxHitFlags outputFlags = PxHitFlag::eDISTANCE | PxHitFlag::eIMPACT | PxHitFlag::eNORMAL;

// [in] Raycast against GROUP2 and GROUP3
PxQueryFilterData filterData = PxQueryFilterData();
filterData.data.word0 = GROUP2|GROUP3;

bool status = scene->raycast(origin, unitDir, maxDistance, hit, outputFlags, filterData);

A built-in equation is never flexible enough, so the last level of filtering is provided by a filtering callback. The filtering callback must be passed to the query as a PxQueryFilterCallback. Set the PxQueryFlag::ePREFILTER and PxQueryFlag::ePOSTFILTER flags to determine whether to filter before accurate per-shape collision, afterward, or both. Filtering early allows shapes to be efficiently discarded before the potentially expensive collision test. On the other hand, the results of that test may be required in order to determine whether a shape should be discarded or not.

In some cases the built-in equation is not flexible enough, so the last level of filtering is provided by a filtering callback. The filtering callback must be passed to the query as a PxQueryFilterCallback. Set the PxQueryFlag::ePREFILTER and PxQueryFlag::ePOSTFILTER flags to determine whether to filter before accurate per-shape collision, afterward, or both. Filtering early allows shapes to be efficiently discarded before the potentially expensive collision test. On the other hand, the results of that test may be required in order to determine whether a shape should be discarded or not.

The implementation of the filtering callback must return a PxQueryHitType. These types define three different kinds of behavior:

  • eNONE indicates that the shape must simply be discarded from any further processing
  • eBLOCK indicates that the shape is a "blocking hit", and any shapes located further away can be ignored. Doesn't apply to overlap queries, overlap hits filtered with eBLOCK flag are treated as eTOUCH. The hit is still reported with eBLOCKING_HIT flag.
  • eTOUCH indicates that the shape is a "touching hit", and while this shape will be recorded and included in the query's report, the query will continue to seek hits further away

The eNONE and eBLOCK types correspond to the intuitive definition of a standard filtering mechanism: discard the shape (eNONE) or keep it (eBLOCK). eTOUCH provides support for scenarios such as bullets going through windows (breaking them on their way), or through the leaves of a tree (making them rustle). That is, cases where it is useful to apply various effects to touched objects, without actually blocking the bullet. Note that eTOUCH is only useful for scene queries reporting multiple hits. For queries returning a single result, touching hits are simply ignored (similar to eNONE).

To use filter-style querying in unbatched queries, similar to that performed by the simulation filter shader and for batched queries, add a filterData field to the query callback object and call your filter function there.

  • PxQueryFlag::eNO_BLOCK can be used to speed up query processing in cases where it's known upfront that no blocking hits should be expected. All hits will then be reported as touching.

Volume Caching

PxVolumeCache provides a mechanism for accelerating scene queries. This class implements caching for objects within a specified volume and provides an API similar to PxScene non-batched queries for executing raycasts, overlaps, and sweeps on cached objects. The only difference in signatures of raycast/sweep/overlap functions is that single object caching (PxQueryCache) is not supported for PxVolumeCache queries.

PxVolumeCache can provide a performance boost when multiple repeated queries are performed on objects within the same localized region of space, either on the same frame or on subsequent frames. One use case is a particle system with lots of raycasts performed for each particle from a spatially localized cloud, another is multiple short range character controller raycasts within the same area.

Another typical use case is caching across multiple frames, the cache can be filled using a larger volume on previous frame (possibly extruded in the anticipated direction of movement) and then queried with a smaller volume.

Maximum cache capacity for statics and dynamics is specified at creation time in PxScene::createVolumeCache call. PxVolumeCache::fill() function is then used to fill the cache. When fill() is executed, it will query the scene for objects overlapping with the provided volume geometry * transform and store the results in an internal buffer up to the maximum number of actors/shapes specified. Only PxBoxGeometry, PxSphereGeometry and PxCapsuleGeometry are supported for cacheVolume. Queries on cache (raycasts, overlaps, sweeps, forEach) will also refill the cache automatically (if within max specified capacity). Query results on PxVolumeCache are always complete within the last cached volume (but not necessarily outside), even if the number of actual objects within the volume is greater than the cache capacity. This means that if a raycast is performed on a cache and the same raycast is performed on a scene, the number of results from a scene raycast can be larger than the number of results from a raycast on the cache. In case of over max capacity, queries executed on the cache will fall back to scene queries and the cache will stay invalid, separately for statics and dynamics. A call to fill() currently does not perform a volume containment check and will always refill both the static and dynamic internal caches.

A fill() call returns a status (see PxVolumeCache::FillStatus). If returned status is not equal to PxVolumeCache::FILL_OK, the cache state is invalid. All subsequent queries on the cache will attempt to refill it and in case of repeated failure will redirect to a corresponding scene query call.

If a query (raycast, sweep or overlap) is executed on the cache without a prior fill() call or the number of objects within the cache volume is over the max count (either statics or dynamics), the cache query will fall back to a scene query call. In this case the list of returned objects can include objects outside of the cache volume. A forEach query executed on unfilled cache will return nothing without reporting an error.

forEach is a low level iterator that provides access to individual stored shapes/geometries for scenarios not covered by other queries (raycast/sweep/overlap).

Any operation on the cache counts as a read call on the scene for purposes of multithreaded access. The usual rules apply: overlapping writes to the scene are not allowed while the cache query is taking place.

forEach and raycast/sweep/overlap queries can invoke multiple PxVolumeCache::Iterator::shapes() callbacks, reporting multiple batches of results.

Objects cached across frames can become invalid due to any insertion or deletion from the scene or object movement. Internally the cache is invalidated independently for statics and dynamics, this means that a query might only refill the cache for dynamics while reusing valid cached results for statics.

This simple example shows the use of PxVolumeCache:

PxScene* scene;
PxVec3 poi = ...;                    // point of interest
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance
PxRaycastBuffer hit;                 // [out] Raycast results
const PxU32 maxStatics = 32, maxDynamics = 8;

// persistent cache, valid across frames unless invalidated due to object movement, insertion or deletion
PxVolumeCache* cache = scene->createVolumeCache(maxStatics, maxDynamics);
cache->setMaxNbStaticShapes(64); cache->setMaxNbDynamicShapes(16);

cache->fill(PxBoxGeometry(PxVec3(1.0f)), PxTransform(position)); // fill the cache using a box geometry centered around the point of interest

...

// Perform multiple raycast queries using the cache
PxRaycastBuffer hit;
const bool status = cache->raycast(origin, unitDir, maxDistance, hit);

// low level iterator for stored actor/shape pairs
struct UserIterator : PxVolumeCache::Iterator
{
    UserData userData;
    virtual void shapes(PxU32 count, const PxActorShape* actorShapePairs)
    {
            for (PxU32 i = 0; i < count; i++)
               doSomething(actorShapePairs[i].actor, actorShapePairs[i].shape, userData);
    }
} iter;

// invoke UserIterator::shapes() callback for all actor/shape pairs in the cache
cache->forEach(iter);

Single Object Caching

Another special case mechanism for accelerating scene queries is single-object cache, PxQueryCache. This can provide additional speedups and memory savings for raycast and sweep queries in any operation mode. Note that it is likely incorrect to use a past touching hit for caching since it will be interpreted as blocking and override any filtering. The cache object defines which shape - or even, in the case of triangle meshes, which triangle - should be tested first. For queries with high temporal coherence, this can provide significant performance gains. A good strategy to capture that coherence is simply to fill the cache object of a given query with the results (last touched shape, last touched triangle) from the previous frame.

For example there is a high probability that an AI visibility query will return the same vision-blocking shape for several frames. Using raycast with a properly filled PxQueryCache object will allow PhysX to test a single shape - or a single triangle! - before traversing internal pruning structures, and in the case of a "cache hit" the pruning structures can be bypassed entirely. Caching in such a scenario works like this:

PxScene* scene;
PxVec3 origin = ...;                 // [in] Ray origin
PxVec3 unitDir = ...;                // [in] Normalized ray direction
PxReal maxDistance = ...;            // [in] Raycast max distance
PxRaycastBuffer hit;                 // [out] Raycast results

// Per-raycast persistent cache, valid from one frame to the next
static PxQueryCache persistentCache;

// Define cache for current frame:
// - if there was a hit in the previous frame, use the cache.
// - otherwise do not (PhysX requires given cache has a valid shape pointer)
const PxQueryCache* cache = persistentCache.shape ? &persistentCache : NULL;

// Perform a raycast query using the cache
const bool status = scene->raycast(origin, unitDir, maxDistance, hit, PxHitFlags(PxHitFlag::eDEFAULT), PxQueryFilterData(), NULL, cache);
if(status)
{
    // We hit a shape. Cache it for next frame.
    persistentCache.shape = hit.block.shape;
    persistentCache.faceIndex = hit.block.faceIndex;
}
else
{
    // We did not hit anything. Reset the cache for next frame.
    persistentCache = PxQueryCache();
}

Caching can also be useful in queries looking for the "closest" hit. Here, testing the previously closest object first can allow PhysX to shorten the query distance very early, leading to fewer collision tests overall.

PhysX cannot detect stale pointers, so the application is responsible for updating caches when shapes are deleted.

Batched queries

PxBatchQuery interface facilitates batching queries together and executed all at once. PxBatchQuery buffers the raycast, overlap and sweep queries until PxBatchQuery::execute() is called.

Use PxScene::createBatchQuery(const PxBatchQueryDesc& desc) to create the PxBatchQuery object. PxBatchQuery buffers the raycast, overlap and sweep query, and does the query once when PxBatchQuery::execute() is called.

The hardcoded filtering equation is not used for batched queries. Instead it is replaced with two filter shaders, respectively running before (PxBatchQueryPreFilterShader) and after (PxBatchQueryPostFilterShader) the accurate collision tests. Set the preFilterShader and postFilterShader in PxBatchQueryDesc correspondingly.

The filterShaderData will be copied into PhysX and passed to the filter shader by the constantBlock parameter.

Results are written to the user-defined buffers PxBatchQueryMemory in PxBatchQueryDesc, in the same order the queries were given to the PxBatchQuery object. The results buffer and hits buffer for the needed query type must be set. The buffers can be re-set to the batch query before each execute to achieve better memory control. The SDK ignores batched queries with NULL results buffer or NULL hits buffer.

PS3 specific limitations and how to write an SPU Query Filter Shader are captured in the User's PS3 Guide "SPU Simulation Restrictions" and "SPU Query Filter Shaders" chapters respectively.

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 bounding box entries, and raycasts, sweeps, and overlap queries against those bounds. Similar to the PruningStructure::DYNAMIC_AABB_TREE option to PxScene, it allows for a new version of the data structure to be rebuilt incrementally in the background while the current version is used for raycasting, which prevents the quality of the hierarchy from decaying over time.

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) should 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 postpones some updates to its internal data structures until a query is issued. In a single-thread context this is not apparent, but when querying from multiple threads simultaneously the internal updates may cause data hazards. In order to avoid these, call the flushUpdates() 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 you to perform any filtering or precise intersection desired. The methods in the PxGeometryQuery class can be used to perform these tests using PxGeometry and PxTransform types. 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 bound 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;

        // do a precise query against 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 that results are identical when using PxSpatialIndex and when not using a culling hierarchy, you should slightly pad the bounding boxes. PxGeometryQuery::getWorldBounds adds this padding by default.

PxPruningStructure

General handling

The scene query system follows an update-commit-query paradigm.

The update step involves adding, updating and deleting objects that are subject in later queries.

The commit happens automatically when querying through PxBatchQuery or PxScene. The same is true for PxScene::fetchResults() which also triggers a commit because it is updating objects according to simulation results. For more control, use PxScene::flushQueryUpdates() to manually commit the changes.

Subsequent queries only search for objects and do not further alter the scene query representation.

To avoid automatic reallocation and copying of the necessary storage while adding more data to the scene query system, allocate the space in advance. This is performed by setting the scene limits maxNbStaticShapes and maxNbDynamicShapes.

PxPruningStructure::eSTATIC_AABB_TREE

As the name suggests, the static structure is not suited for representations that change often. Insertion, manipulation and removal of objects are therefore inexpensive, constant-time operations. That way a large collection of objects can be created quickly. Any change however will invalidate the existing acceleration structure. The expensive operation here is committing the changes, which implies constructing the volume hierarchy from scratch. This operation has a complexity in O(N*log(N)). Thus, it is not recommended to update only a small amount of objects at one time. Queries typically take O(log(N)) time when a single hit is searched for. In unfortunate cases however, the time complexity can grow up to O(N). So-called multiple queries collecting several hits at once will typically take some time between O(log(N)) when only one blocking hit is found rapidly and O(N) where all objects are touched and reported in the query process.

PxPruningStructure::eNONE

This structure is similar to PxPruningStructure::eSTATIC_AABB_TREE but uses a different representation. Here also, object manipulation is a cheap operation and any previously existing acceleration structure is destroyed. The cost of rebuilding the representation lies in O(N) for this structure. This cost applies in the commit step as explained above. On the other hand, queries also run in O(N), but distribution into grid cells during the build significantly reduces the constant factor for typical cases.

PxPruningStructure::eDYNAMIC_AABB_TREE

This structure combines both previously explained structures PxPruningStructure::eSTATIC_AABB_TREE and PxPruningStructure::eNONE and adds background building and current tree adjustments.

When the first set of objects is committed, an initial tree hierarchy is constructed as for PxPruningStructure::eSTATIC_AABB_TREE.

Insertion, manipulation and removal operations still complete in constant time. The tree hierarchy is not invalidated when updating this structure, but the grid representation can be destroyed. Adding objects will always destroy the grid representation. Added objects remain in the grid based subsystem until building a new tree is completed. Manipulating only objects in the tree will not affect the grid representation at all. Manipulating objects currently stored in the grid based subsystem destroys the grid representation.

Following commits only adjust the existing tree to reflect moved or deleted objects that were in the tree before. Note that these operations degenerate the tree and can have a negative impact on subsequent query performance. Adjusting the tree comes at O(log(N)) per updated object. If the grid representation was destroyed due to object manipulation, a new grid representation is also recreated at this moment. Although in this case, the cost of O(N) only applies for the N objects that are not in the tree yet.

Each call to PxScene::fetchResults() builds a portion of a new tree, which eventually contains the newly added objects so far stored in the grid structure. The amount of work executed in each step is controlled with dynamicTreeRebuildRateHint which sets the approximate number of steps a tree build takes to complete. The new tree is adjusted after the build completes according to manipulations of the objects in the meantime, possibly leading to tree degeneration. PxScene::forceDynamicTreeRebuild() requests building a new tree immediately, taking the full O(N*log(N)) cost. This operation moves all added objects to the tree and is not adjusted after the build.

Special care is needed when the number of objects in the grid structure objects becomes large and is changed often between queries. In this case the grid representation is built for every query. When this cost becomes prohibitive, consider forcing a rebuild instead or make sure the background build is stepped and finishes regularly.