diff options
Diffstat (limited to 'PhysX_3.4/Source/SceneQuery/src/SqAABBPruner.h')
| -rw-r--r-- | PhysX_3.4/Source/SceneQuery/src/SqAABBPruner.h | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/PhysX_3.4/Source/SceneQuery/src/SqAABBPruner.h b/PhysX_3.4/Source/SceneQuery/src/SqAABBPruner.h new file mode 100644 index 00000000..c5e96aa6 --- /dev/null +++ b/PhysX_3.4/Source/SceneQuery/src/SqAABBPruner.h @@ -0,0 +1,268 @@ +// This code contains NVIDIA Confidential Information and is disclosed to you +// under a form of NVIDIA software license agreement provided separately to you. +// +// Notice +// NVIDIA Corporation and its licensors retain all intellectual property and +// proprietary rights in and to this software and related documentation and +// any modifications thereto. Any use, reproduction, disclosure, or +// distribution of this software and related documentation without an express +// license agreement from NVIDIA Corporation is strictly prohibited. +// +// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES +// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO +// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, +// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. +// +// Information and code furnished is believed to be accurate and reliable. +// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such +// information or for any infringement of patents or other rights of third parties that may +// result from its use. No license is granted by implication or otherwise under any patent +// or patent rights of NVIDIA Corporation. Details are subject to change without notice. +// This code supersedes and replaces all information previously supplied. +// NVIDIA Corporation products are not authorized for use as critical +// components in life support devices or systems without express written approval of +// NVIDIA Corporation. +// +// Copyright (c) 2008-2016 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 = 1, bool hasPruningStructure = false); + virtual void removeObjects(const PrunerHandle* handles, PxU32 count = 1); + virtual void updateObjects(const PrunerHandle* handles, const PxBounds3* newBounds, PxU32 count = 1); + virtual void updateObjects(const PrunerHandle* handles, const PxU32* indices, const PxBounds3* newBounds, PxU32 count = 1); + 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(); // returns true if finished + //~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 + Sq::AABBTreeBuildParams mBuilder; // this class deals with the details of the actual tree building + 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 |