PhysX provides methods in PxScene to perform collision queries against actors and attached shapes in the scene. There are three types of queries: raycasts, sweeps and overlaps, and each can return either a single result, or multiple results. Broadly speaking, each query traverses a culling structure containing the scene objects, performs a precise test using the GeometryQuery functions (see Geometry Queries), and accumulates the results. Filtering may occur before or after precise testing.
The scene uses two different query structures, one for PxRigidStatic actors, and the other for PxRigidBody actors (PxRigidDynamic and PxArticulationLink). The two structures may be configured to use different culling implementations depending on the desired speed/space characteristics (see PxPruningStructure.)
A PxScene::raycast() query intersects a user-defined ray with the whole scene. The simplest use case for a raycast() query is to find the closest hit along a given ray as follows:
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);
if (status)
applyDamage(hit.block.position, hit.block.normal);
In this code snippet a PxRaycastBuffer object is used to receive results from the raycast query. A call to raycast() returns true if there was a hit. hit.hadBlock is also set to true if there was a hit. The distance for raycasts has to be in the [0, inf) range.
Raycasts results include position, normal, hit distance, shape and actor, and a face index with UV coordinates for triangle meshes and heightfields. Before using query results check PxHitFlag::ePOSITION, eNORMAL, eDISTANCE, eUV flags first, as in some cases they are not set.
A PxScene::sweep() query is geometrically similar to a raycast(): a PxGeometry shape is swept from a specified initial pose in a direction unitDir with specified maximum length, to find the points of impacts of the geometry with scene objects. The maximum distance for sweeps has to be in the [0, inf) range, and will be clamped by to PX_MAX_SWEEP_DISTANCE, defined in file PxScene.h.
Allowed shapes are box, sphere, capsule and convex.
A PxSweepBuffer object is used to receive results from sweep() queries:
PxSweepBuffer hit; // [out] Sweep results
PxGeometry sweepShape = ...; // [in] swept shape
PxTransform initialPose = ...; // [in] initial shape pose (at distance=0)
PxVec3 sweepDirection = ...; // [in] normalized sweep direction
bool status = scene->sweep(sweepShape, initialPose, sweepDirection, sweepDistance, hit);
Sweeps results include position, normal, hit distance, shape and actor, and a face index for triangle meshes and heightfields.
PxScene::overlap() query searches a region enclosed by a specified shape for any overlapping objects in the scene. The region is specified as a transformed box, sphere, capsule or convex geometry.
A PxOverlapBuffer object is used to receive results from overlap() queries:
PxOverlapBuffer hit; // [out] Overlap results
PxGeometry overlapShape = ...; // [in] shape to test for overlaps
PxTransform shapePose = ...; // [in] initial shape pose (at distance=0)
PxOverlapBuffer hit;
bool status = scene->overlap(overlapShape, shapePose, hit);
Overlaps results only include actor/shape and faceIndex since there is no single point of intersection.
For queries with multiple results we distinguish between touching and blocking hits. The choice of whether a hit is touching or blocking is made by the user-implemented filtering logic. Intuitively a blocking hit prevents further progress of a raycast or a sweep along its path, and a touching hit is recorded but allows the ray or sweep to continue. So a multiple-hit query will return the closest blocking hit if one exists, together with any touching hits that are closer. If there are no blocking hits, all touching hits will be returned.
See the Filtering section for details.
The default mode of operation for all three query types is "closest hit". The query looks for all blocking hits, picks the one with the minimum distance and reports it in the PxHitBuffer::block member.
All three query types can operate in "any hit" mode. This is a performance hint to the query system indicating that there is no need to look for the closest hit - any hit encountered will do. This mode is most often used for boolean blocking/non-blocking queries. Performance improvement may be a factor of 3 or more, depending on scenario. To activate this mode use PxQueryFlag::eANY_HIT filter data flag and set it in PxQueryFilterData object, for instance:
PxQueryFilterData fd;
fd.flags |= PxQueryFlag::eANY_HIT; // note the OR with the default value
bool status = scene->raycast(origin, unitDir, maxDistance, hit,
PxHitFlags(PxHitFlag::eDEFAULT), fdAny);
All three query types (raycast, overlap, sweep) can also report multiple hits with objects in the scene.
For instance:
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 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'
scene->raycast(origin, unitDir, maxDistance, buf);
for (PxU32 i = 0; i < buf.nbTouches; i++)
animateLeaves(buf.touches[i]);
The same mechanism is used for overlaps (use PxOverlapBuffer with PxOverlapHit[]) and sweeps (PxSweepBuffer with PxSweepHit[]).
In the snippet for multiple hits above we only expected touching hits. If a blocking hit was encountered along with touching hits, it will be reported in PxHitBuffer::block member, and the touch buffer will contain only touching hits which are closer. This combination is useful in scenarios such as bullets going through windows (breaking them on their way) or leaves of a tree (making them rustle) until they hit a blocking object (a concrete wall):
// same initialization code as in the snippet for multiple hits
bool hadBlockingHit = scene->raycast(origin, unitDir, maxDistance, buf);
if (hadBlockingHit)
drawWallDecal(buf.block);
for (PxU32 i = 0; i < buf.nbTouches; i++)
{
assert(buf.touches[i].distance <= buf.block.distance);
animateLeaves(buf.touches[i]);
}
Filtering controls how shapes are excluded from scene query results and how results are reported. All three query types support the following filtering parameters:
PxQueryFlag::eSTATIC and PxQueryFlag::eDYNAMIC flags control whether the query should include shapes from the static and/or dynamic query structures. This is the most efficient way to filter out all static/dynamic shapes. For example an explosion effect that applies forces to all dynamics in a region could use a spherical overlap query, and only the PxQueryFlag::eDYNAMIC flag to exclude all statics since forces cannot be applied to static objects. By default both statics and dynamics are included in query results.
For instance:
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);
Scene queries are performed in three phases: broad phase, midphase and narrow phase.
To implement custom filtering in queries, set the PxQueryFlag::ePREFILTER and/or PxQueryFlag::ePOSTFILTER flags and subclass PxQueryFilterCallback with the required filtering logic.
The implementation of a filtering callback returns a PxQueryHitType result.
Whenever a raycast(), sweep() or overlap() query was called with non-zero PxHitCallback::nbTouches and PxHitCallback::touches parameters, eTOUCH type hits that are no further (touchDistance <= blockDistance) than the closest eBLOCK type hit, will be reported. For example, to record all hits from a raycast query, always return eTOUCH.
..note:: Returning eTOUCH from a filter callback requires the hit buffer query parameter to have a non-zero ::touches array, otherwise PhysX will generate an error in checked builds and discard any touching hits. .. note:: eBLOCK should not be returned from user filters for overlap(). Doing so will result in undefined behavior, and a warning will be issued. If the PxQueryFlag::eNO_BLOCK flag is set, the eBLOCK will instead be automatically converted to an eTOUCH and the warning suppressed.
Use this flag to force the query to report the first encountered hit (which may not be the closest) as a blocking hit. Performance may be more than three times faster, depending on the scenario. Best gains can be expected for long raycasts/sweeps with a nearby intersecting object, or overlaps with multiple intersecting objects.
Use this flag when you want to override the eBLOCK value returned from filters to eTOUCH or in cases when no blocking hits are expected (in this case this flag serves as a performance hint). All hits will then be reported as touching regardless of the filter callback return value. The hit callback/buffer object provided to the query is required to have a non-zero PxHitBuffer::touches buffer when this flag is used. Significant performance gains should only be expected for scenarios where the touching hit buffer overflows.
Note
this flag overrides the return value from pre and post-filter functions, so hits that were previously returned as blocking will instead be returned as touching.
A fast, fixed-function filter is provided by PxFilterData, a 4*32-bit bitmask used by the built-in filtering equation. Each shape has a bitmask (set via 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 unbatched queries, the following rules are applied:
Or in other words:
PxU32 keep = (query.word0 & object.word0)
| (query.word1 & object.word1)
| (query.word2 & object.word2)
| (query.word3 & object.word3);
This hardcoded equation can provide simple filtering while avoiding the function call overhead of the filtering callback. For example, to emulate the behavior of PhysX 2 active groups, define the groups as follows:
enum ActiveGroup
{
GROUP1 = (1<<0),
GROUP2 = (1<<1),
GROUP3 = (1<<2),
GROUP4 = (1<<3),
...
};
When shapes are created, they can be assigned to the a group, for example GROUP1:
PxShape* shape; // Previously created shape
PxFilterData filterData;
filterData.word0 = GROUP1;
shape->setQueryFilterData(filterData);
Or to multiple groups, for example GROUP1 and GROUP3:
PxShape* shape; // Previously created shape
PxFilterData filterData;
filterData.word0 = GROUP1|GROUP3;
shape->setQueryFilterData(filterData);
When performing a scene query, select which groups are active for the query - for example GROUP2 and GROUP3 - as follows:
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::ePOSITION | 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);
Queries can sometimes return a very large number of results (for example, queries with very large objects or in areas with high object density), and it can be prohibitively expensive to reserve a sufficiently large memory buffer. The classes PxRaycastCallback, PxSweepCallback and PxOverlapCallback provide efficient callback based solutions for such scenarios. For instance a raycast query with a PxRaycastCallback callback will return all touch hits via multiple virtual PxHitCallback::processTouches() callbacks:
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
In this code snippet the raycast() query will potentially invoke processTouches multiple times, with all touching hits already clipped to the globally nearest blocking hit.
PhysX supports batching of scene queries via the PxBatchQuery interface. Using this API may provide a speedup on PS3 (only batched queries are SPU-accelerated) or simplify multi-threaded implementations on other platforms.
For SPU specific limitations and filter shader guide refer to the User's PS3 Guide sections "SPU Simulation Restrictions" and "SPU Query Filter Shaders".
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 for executing raycasts, overlaps, and sweeps. PxVolumeCache can provide a performance boost when objects within the same localized region of space are queried multiple times, either within the same simulation frame or on a later frame.
Some expected use cases for PxVolumeCache are:
The cache has a maximum capacity, specified separately for dynamic and static objects, in PxScene::createVolumeCache().
For purposes of multithreaded access, any operation on the cache counts as a read call on the scene.
To fill the cache, call PxVolumeCache::fill(). This will query the scene for objects overlapping with the volume defined by the geometry and transform and store the results in an internal buffer up to the maximum sizes for static and dynamic objects. Only PxBoxGeometry, PxSphereGeometry and PxCapsuleGeometry are supported for cacheVolume. The call will always refill both the static and dynamic internal caches, even if the new volume lies entirely within the previous cached volume. It returns a result of type PxVolumeCache::FillStatus.
Subsequent queries against the cache (raycasts, overlaps, sweeps, forEach) will refill the cache automatically using the same volume if the scene query subsystem has been updated since the last fill. The update status is tracked independently for statics and dynamics, so a query might only refill the cache for dynamics while reusing valid cached results for statics. If any attempt to fill or refill fails, the cache is invalid, and any subsequent query will attempt to fill it.
PxVolumeCache provides an API for raycasts, sweeps and overlaps that is similar to the scene query API. The main difference in signatures is that Single Object Caching is not supported for PxVolumeCache queries. Query results are reported via the PxVolumeCache::Iterator::shapes() callback, and the query may invoke the callback multiple times to deliver multiple batches of results.
Since the cache refills automatically on any query where the scene has changed, these two conditions guarantee that a query against the cache that lies entirely within the cache volume will always return exactly the same shapes as querying the scene. If the query does not lie entirely within the cache volume (and the cache is valid) only those shapes which overlap the cache volume will be returned. If a query is issued against a cache on which fill() has never been called, an error is reported.
The cache also provides a low-level forEach() mechanism that iterates over the cached objects. If forEach() is executed on a cache for which fill() has never been called, it will return without reporting an error. If the cache is invalid, forEach() will retrieve the shapes that overlap the cached volume directly from the scene. This process involves the allocation of a temporary buffer, and if the allocation fails, forEach() will emit an error message and return.
This code snippet shows how to use 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 until invalidated by object movement,
// insertion or deletion
PxVolumeCache* cache = scene->createVolumeCache(maxStatics, maxDynamics);
cache->setMaxNbStaticShapes(64); cache->setMaxNbDynamicShapes(16);
// fill the cache using a box geometry centered around the point of interest
cache->fill(PxBoxGeometry(PxVec3(1.0f)), PxTransform(position));
...
// 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);
Another special case mechanism for accelerating scene queries is single-object caching, using PxQueryCache.
For example there is a good chance that an AI visibility query will return the same line-of-sight blocking shape for several frames. Using a raycast query with a properly filled PxQueryCache object will allow PhysX to test a single shape - before traversing the internal spatial partitioning structures, and in case of a "cache hit" the traversal can be bypassed entirely. For instance:
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 blocking hit or when using the eANY_HIT flag. In this case, testing the previously closest object first can allow PhysX to shorten the query distance very early, leading to fewer total narrow phase collision tests and early out from the traversal.
Note
PhysX does not detect stale pointers, so the application is responsible for cached object validity when shapes are deleted.
Note
Overlaps do not support single hit blocking caches.
PhysX SDK offers different pruning structures which are used to accelerate the scene queries. This paragraph describes the differences between them.
The Scene Query system uses two different acceleration structures, a hierarchical grid and an AABB tree.
The grid builds quickly, in O(n) time, with queries executing in between O(1) and O(N) time depending on how uniformly the objects are distributed in space, with pathological worst case performance of O(N) when all objects are clustered in the same grid cell.
The tree builds in O(n log(n)) time, but queries with a single result typically run in O(log(n)) time. Queries returning multiple results will traverse more of the tree, the worst case being a query returning all of the objects in the scene in O(n) time. The tree is vulnerable to degeneration when the same topology is maintained too long as object positions change, and in pathological cases query performance may degrade to O(n) time.
Acceleration structures must be continually modified in accordance with objects being added or removed, or object AABB updates due to changes in position or geometry. To minimize the cost, modifications are deferred for as long as possible. Thus adding or removing objects or updating AABBs occurs in amortized constant time, with the cost of modifications deferred until the changes 'commit'. This happens on the next subsequent query or the next fetchResults(). To force an immediate commit, call the PxScene::flushQueryUpdates() function.
The exact details of the commit process depend on the values of staticStructure and dynamicStructure specified in PxSceneDesc.
To avoid automatic resizing triggered by insertions into internal scene query data structures, reserve the space in advance. See PxSceneDesc::maxNbStaticShapes and PxSceneDesc::maxNbDynamicShapes.
The acceleration structure is similar to a hierarchical grid. Committing changes requires a full rebuild. This is a good choice if you expect to rarely or never update the objects in this structure.
The acceleration structure is a tree. Committing changes requires a full rebuild. It is not generally recommended, but can be a good choice for staticStructure if the static actors in your scene are created on initialization, and not modified thereafter. If you frequently add or remove static geometry, the default eDYNAMIC_AABB_TREE setting is usually a better choice, although it has a higher memory footprint than that of eSTATIC_AABB_TREE.
In this case, both the tree and the grid are used, and each query searches both the tree and the grid.
The tree is initially built by the first commit. Once a tree is built, committing changes proceeds as follows:: * the tree is refitted in accordance with updates and removals of object it contains. * added objects are inserted into the grid. Such additions, or removals of objects currently in the grid, or changes to AABBs of objects in the grid, cause it to be rebuilt.
In addition, a new tree is incrementally built during fetchResults(), over a number of frames controlled by PxScene's dynamicTreeRebuildRateHint attribute. When the build starts, it includes all of the objects in the current tree and grid. When it finishes, some frames later, the new tree is refitted in accordance with any AABB changes or removals since the build started, and then replaces the current tree. Any objects that were added since the start of the build remain in the grid.
To force a full immediate rebuild, call PxScene::forceDynamicTreeRebuild(). This can be useful in cases such as the following: