270 lines
14 KiB
C++
270 lines
14 KiB
C++
//
|
|
// Redistribution and use in source and binary forms, with or without
|
|
// modification, are permitted provided that the following conditions
|
|
// are met:
|
|
// * Redistributions of source code must retain the above copyright
|
|
// notice, this list of conditions and the following disclaimer.
|
|
// * Redistributions in binary form must reproduce the above copyright
|
|
// notice, this list of conditions and the following disclaimer in the
|
|
// documentation and/or other materials provided with the distribution.
|
|
// * Neither the name of NVIDIA CORPORATION nor the names of its
|
|
// contributors may be used to endorse or promote products derived
|
|
// from this software without specific prior written permission.
|
|
//
|
|
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
|
|
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
|
|
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
|
|
// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
//
|
|
// Copyright (c) 2008-2019 NVIDIA Corporation. All rights reserved.
|
|
// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
|
|
// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
|
|
|
|
#ifndef SQ_AABB_PRUNER_H
|
|
#define SQ_AABB_PRUNER_H
|
|
|
|
#include "SqPruningPool.h"
|
|
#include "SqExtendedBucketPruner.h"
|
|
#include "SqAABBTreeUpdateMap.h"
|
|
#include "SqAABBTree.h"
|
|
|
|
namespace physx
|
|
{
|
|
|
|
namespace Sq
|
|
{
|
|
// PT: we build the new tree over a number of frames/states, in order to limit perf spikes in 'updatePruningTrees'.
|
|
// The states are as follows:
|
|
//
|
|
// BUILD_NOT_STARTED (1 frame, AABBPruner):
|
|
//
|
|
// This is the initial state, before the new (AABBTree) build even starts. In this frame/state, we perform the AABBPruner-related
|
|
// memory allocations:
|
|
// - the new AABB tree is allocated
|
|
// - the array of cached bounding boxes is allocated and filled
|
|
//
|
|
// BUILD_INIT (1 frame, AABBTree):
|
|
//
|
|
// This is the first frame in which the new tree gets built. It deserves its own special state since various things happen in the
|
|
// first frame, that do no happen in subsequent frames. Basically most initial AABBTree-related allocations happen here (but no
|
|
// build step per se).
|
|
//
|
|
// BUILD_IN_PROGRESS (N frames, AABBTree):
|
|
//
|
|
// This is the core build function, actually building the tree. This should be mostly allocation-free, except here and there when
|
|
// building non-complete trees, and during the last call when the tree is finally built.
|
|
//
|
|
// BUILD_NEW_MAPPING (1 frame, AABBPruner):
|
|
//
|
|
// After the new AABBTree is built, we recreate an AABBTreeUpdateMap for the new tree, and use it to invalidate nodes whose objects
|
|
// have been removed during the build.
|
|
//
|
|
// We need to do that before doing a full refit in the next stage/frame. If we don't do that, the refit code will fetch a wrong box,
|
|
// that may very well belong to an entirely new object.
|
|
//
|
|
// Note that this mapping/update map (mNewTreeMap) is temporary, and only needed for the next stage.
|
|
//
|
|
// BUILD_FULL_REFIT (1 frame, AABBPruner):
|
|
//
|
|
// Once the new update map is available, we fully refit the new tree. AABBs of moved objects get updated. AABBs of removed objects
|
|
// become empty.
|
|
//
|
|
// BUILD_LAST_FRAME (1 frame, AABBPruner):
|
|
//
|
|
// This is an artificial frame used to delay the tree switching code. The switch happens as soon as we reach the BUILD_FINISHED
|
|
// state, but we don't want to execute BUILD_FULL_REFIT and the switch in the same frame. This extra BUILD_LAST_FRAME stage buys
|
|
// us one frame, i.e. we have one frame in which we do BUILD_FULL_REFIT, and in the next frame we'll do both BUILD_LAST_FRAME /
|
|
// BUILD_FINISHED / the switch.
|
|
//
|
|
// BUILD_FINISHED (1 frame, AABBPruner):
|
|
//
|
|
// Several things happen in this 'finalization' frame/stage:
|
|
// - We switch the trees (old one is deleted, cached boxes are deleted, new tree pointer is setup)
|
|
// - A new (final) update map is created (mTreeMap). The map is used to invalidate objects that may have been removed during
|
|
// the BUILD_NEW_MAPPING and BUILD_FULL_REFIT frames. The nodes containing these removed objects are marked for refit.
|
|
// - Nodes containing objects that have moved during the BUILD_NEW_MAPPING and BUILD_FULL_REFIT frames are marked for refit.
|
|
// - We do a partial refit on the new tree, to take these final changes into account. This small partial refit is usually much
|
|
// cheaper than the full refit we previously performed here.
|
|
// - We remove old objects from the bucket pruner
|
|
//
|
|
enum BuildStatus
|
|
{
|
|
BUILD_NOT_STARTED,
|
|
BUILD_INIT,
|
|
BUILD_IN_PROGRESS,
|
|
BUILD_NEW_MAPPING,
|
|
BUILD_FULL_REFIT,
|
|
BUILD_LAST_FRAME,
|
|
BUILD_FINISHED,
|
|
|
|
BUILD_FORCE_DWORD = 0xffffffff
|
|
};
|
|
|
|
// This class implements the Pruner interface for internal SQ use with some additional specialized functions
|
|
// The underlying data structure is a binary AABB tree
|
|
// AABBPruner supports insertions, removals and updates for dynamic objects
|
|
// The tree is either entirely rebuilt in a single frame (static pruner) or progressively rebuilt over multiple frames (dynamic pruner)
|
|
// The rebuild happens on a copy of the tree
|
|
// the copy is then swapped with current tree at the time commit() is called (only if mBuildState is BUILD_FINISHED),
|
|
// otherwise commit() will perform a refit operation applying any pending changes to the current tree
|
|
// While the tree is being rebuilt a temporary data structure (BucketPruner) is also kept in sync and used to speed up
|
|
// queries on updated objects that are not yet in either old or new tree.
|
|
// The requirements on the order of calls:
|
|
// commit() is required to be called before any queries to apply modifications
|
|
// queries can be issued on multiple threads after commit is called
|
|
// commit, buildStep, add/remove/update have to be called from the same thread or otherwise strictly serialized by external code
|
|
// and cannot be issued while a query is running
|
|
class AABBPruner : public IncrementalPruner
|
|
{
|
|
public:
|
|
AABBPruner(bool incrementalRebuild, PxU64 contextID); // true is equivalent to former dynamic pruner
|
|
virtual ~AABBPruner();
|
|
|
|
// Pruner
|
|
virtual bool addObjects(PrunerHandle* results, const PxBounds3* bounds, const PrunerPayload* userData, PxU32 count, bool hasPruningStructure);
|
|
virtual void removeObjects(const PrunerHandle* handles, PxU32 count);
|
|
virtual void updateObjectsAfterManualBoundsUpdates(const PrunerHandle* handles, PxU32 count);
|
|
virtual void updateObjectsAndInflateBounds(const PrunerHandle* handles, const PxU32* indices, const PxBounds3* newBounds, PxU32 count);
|
|
virtual void commit();
|
|
virtual PxAgain raycast(const PxVec3& origin, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&) const;
|
|
virtual PxAgain overlap(const Gu::ShapeData& queryVolume, PrunerCallback&) const;
|
|
virtual PxAgain sweep(const Gu::ShapeData& queryVolume, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&) const;
|
|
virtual const PrunerPayload& getPayload(PrunerHandle handle) const { return mPool.getPayload(handle); }
|
|
virtual const PrunerPayload& getPayload(PrunerHandle handle, PxBounds3*& bounds) const { return mPool.getPayload(handle, bounds); }
|
|
virtual void preallocate(PxU32 entries) { mPool.preallocate(entries); }
|
|
virtual void shiftOrigin(const PxVec3& shift);
|
|
virtual void visualize(Cm::RenderOutput& out, PxU32 color) const;
|
|
virtual void merge(const void* mergeParams);
|
|
//~Pruner
|
|
|
|
// IncrementalPruner
|
|
virtual void purge(); // gets rid of internal accel struct
|
|
virtual void setRebuildRateHint(PxU32 nbStepsForRebuild); // Besides the actual rebuild steps, 3 additional steps are needed.
|
|
virtual bool buildStep(bool synchronousCall = true); // returns true if finished
|
|
virtual bool prepareBuild(); // returns true if new tree is needed
|
|
//~IncrementalPruner
|
|
|
|
// direct access for test code
|
|
|
|
PX_FORCE_INLINE PxU32 getNbAddedObjects() const { return mBucketPruner.getNbObjects(); }
|
|
PX_FORCE_INLINE const Sq::AABBTree* getAABBTree() const { PX_ASSERT(!mUncommittedChanges); return mAABBTree; }
|
|
PX_FORCE_INLINE Sq::AABBTree* getAABBTree() { PX_ASSERT(!mUncommittedChanges); return mAABBTree; }
|
|
PX_FORCE_INLINE void setAABBTree(Sq::AABBTree* tree) { mAABBTree = tree; }
|
|
PX_FORCE_INLINE const Sq::AABBTree* hasAABBTree() const { return mAABBTree; }
|
|
PX_FORCE_INLINE BuildStatus getBuildStatus() const { return mProgress; }
|
|
|
|
// local functions
|
|
// private:
|
|
Sq::AABBTree* mAABBTree; // current active tree
|
|
Gu::AABBTreeBuildParams mBuilder; // this class deals with the details of the actual tree building
|
|
Gu::BuildStats mBuildStats;
|
|
|
|
// tree with build in progress, assigned to mAABBTree in commit, when mProgress is BUILD_FINISHED
|
|
// created in buildStep(), BUILD_NOT_STARTED
|
|
// This is non-null when there is a tree rebuild going on in progress
|
|
// and thus also indicates that we have to start saving the fixups
|
|
Sq::AABBTree* mNewTree;
|
|
|
|
// during rebuild the pool might change so we need a copy of boxes for the tree build
|
|
PxBounds3* mCachedBoxes;
|
|
PxU32 mNbCachedBoxes;
|
|
|
|
// incremented in commit(), serves as a progress counter for rebuild
|
|
PxU32 mNbCalls;
|
|
|
|
// PT: incremented each time we start building a new tree (i.e. effectively identifies a given tree)
|
|
// Timestamp is passed to bucket pruner to mark objects added there, linking them to a specific tree.
|
|
// When switching to the new tree, timestamp is used to remove old objects (now in the new tree) from
|
|
// the bucket pruner.
|
|
PxU32 mTimeStamp;
|
|
|
|
// this pruner is used for queries on objects that are not in the current tree yet
|
|
// includes both the objects in the tree being rebuilt and all the objects added later
|
|
ExtendedBucketPruner mBucketPruner;
|
|
|
|
BuildStatus mProgress; // current state of second tree build progress
|
|
|
|
// Fraction (as in 1/Nth) of the total number of primitives
|
|
// that should be processed per step by the AABB builder
|
|
// so if this value is 1, all primitives will be rebuilt, 2 => 1/2 of primitives per step etc.
|
|
// see also mNbCalls, mNbCalls varies from 0 to mRebuildRateHint-1
|
|
PxU32 mRebuildRateHint;
|
|
|
|
// Estimate for how much work has to be done to rebuild the tree.
|
|
PxU32 mTotalWorkUnits;
|
|
|
|
// Term to correct the work unit estimate if the rebuild rate is not matched
|
|
PxI32 mAdaptiveRebuildTerm;
|
|
|
|
PruningPool mPool; // Pool of AABBs
|
|
|
|
// maps pruning pool indices to aabb tree indices
|
|
// maps to INVALID_NODE_ID if the pool entry was removed or "pool index is outside input domain"
|
|
// The map is the inverse of the tree mapping: (node[map[poolID]].primitive == poolID)
|
|
// So:
|
|
// treeNodeIndex = mTreeMap.operator[](poolIndex)
|
|
// aabbTree->treeNodes[treeNodeIndex].primitives[0] == poolIndex
|
|
AABBTreeUpdateMap mTreeMap;
|
|
// Temporary update map, see BuildStatus notes above for details
|
|
AABBTreeUpdateMap mNewTreeMap;
|
|
|
|
// This is only set once in the constructor and is equivalent to isDynamicTree
|
|
// if it set to false then a 1-shot rebuild is performed in commit()
|
|
// bucket pruner is only used with incremental rebuild
|
|
bool mIncrementalRebuild;
|
|
|
|
// A rebuild can be triggered even when the Pruner is not dirty
|
|
// mUncommittedChanges is set to true in add, remove, update and buildStep
|
|
// mUncommittedChanges is set to false in commit
|
|
// mUncommittedChanges has to be false (commit() has to be called) in order to run a query as defined by the
|
|
// mUncommittedChanges is not set to true in add, when pruning structure is provided. Scene query shapes
|
|
// are merged to current AABB tree directly
|
|
// Pruner higher level API
|
|
bool mUncommittedChanges;
|
|
|
|
// A new AABB tree is built if an object was added, removed or updated
|
|
// Changing objects during a build will trigger another rebuild right afterwards
|
|
// this is set to true if a new tree has to be created again after the current rebuild is done
|
|
bool mNeedsNewTree;
|
|
|
|
// This struct is used to record modifications made to the pruner state
|
|
// while a tree is building in the background
|
|
// this is so we can apply the modifications to the tree at the time of completion
|
|
// the recorded fixup information is: removedIndex (in ::remove()) and
|
|
// lastIndexMoved which is the last index in the pruner array
|
|
// (since the way we remove from PruningPool is by swapping last into removed slot,
|
|
// we need to apply a fixup so that it syncs up that operation in the new tree)
|
|
struct NewTreeFixup
|
|
{
|
|
PX_FORCE_INLINE NewTreeFixup(PxU32 removedIndex_, PxU32 relocatedLastIndex_)
|
|
: removedIndex(removedIndex_), relocatedLastIndex(relocatedLastIndex_) {}
|
|
PxU32 removedIndex;
|
|
PxU32 relocatedLastIndex;
|
|
};
|
|
Ps::Array<NewTreeFixup> mNewTreeFixups;
|
|
|
|
Ps::Array<PoolIndex> mToRefit;
|
|
|
|
PxU64 mContextID;
|
|
|
|
// Internal methods
|
|
bool fullRebuildAABBTree(); // full rebuild function, used with static pruner mode
|
|
void release();
|
|
void refitUpdatedAndRemoved();
|
|
void updateBucketPruner();
|
|
PxBounds3 getAABB(PrunerHandle h);
|
|
};
|
|
|
|
} // namespace Sq
|
|
|
|
}
|
|
|
|
#endif // SQ_AABB_PRUNER_H
|