GuAABBPruner.h

// 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-2022 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 GU_AABB_PRUNER_H
#define GU_AABB_PRUNER_H
 
#include "common/PxPhysXCommonConfig.h"
#include "GuExtendedBucketPruner.h"
#include "GuSqInternal.h"
#include "GuPruningPool.h"
#include "GuAABBTree.h"
#include "GuAABBTreeUpdateMap.h"
#include "GuAABBTreeBuildStats.h"
 
namespace physx
{
namespace Gu
{
    // 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 DynamicPruner
    {
                                                PX_NOCOPY(AABBPruner)
        public:
        PX_PHYSX_COMMON_API                     AABBPruner(bool incrementalRebuild, PxU64 contextID, CompanionPrunerType cpType, BVHBuildStrategy buildStrategy=BVH_SPLATTER_POINTS, PxU32 nbObjectsPerNode=4); // true is equivalent to former dynamic pruner
        virtual                                 ~AABBPruner();
 
        // BasePruner
                                                DECLARE_BASE_PRUNER_API
        //~BasePruner
 
        // Pruner
                                                DECLARE_PRUNER_API_COMMON
        virtual         bool                    isDynamic()         const       { return mIncrementalRebuild;   }
        //~Pruner
 
        // DynamicPruner
        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
        //~DynamicPruner
 
        // direct access for test code
 
        PX_FORCE_INLINE PxU32                   getNbAddedObjects() const       { return mBucketPruner.getNbObjects();                  }
        PX_FORCE_INLINE const AABBTree*         getAABBTree()       const       { PX_ASSERT(!mUncommittedChanges); return mAABBTree;    }
        PX_FORCE_INLINE AABBTree*               getAABBTree()                   { PX_ASSERT(!mUncommittedChanges); return mAABBTree;    }
        PX_FORCE_INLINE void                    setAABBTree(AABBTree* tree)     { mAABBTree = tree; }
        PX_FORCE_INLINE const AABBTree*         hasAABBTree()       const       { return mAABBTree; }
        PX_FORCE_INLINE BuildStatus             getBuildStatus()    const       { return mProgress; }
                
        // local functions
//      private:
                        NodeAllocator           mNodeAllocator;
 
                        AABBTree*               mAABBTree; // current active tree
                        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
                        AABBTree*               mNewTree;
 
        // during rebuild the pool might change so we need a copy of boxes for the tree build
                        AABBTreeBounds          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;
 
            const       PxU32                   mNbObjectsPerNode;
            const       BVHBuildStrategy        mBuildStrategy;
 
                        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
                const   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;
                        };
                        PxArray<NewTreeFixup>   mNewTreeFixups;
 
                        PxArray<PoolIndex>      mToRefit;
 
        // Internal methods
                        bool                    fullRebuildAABBTree(); // full rebuild function, used with static pruner mode
                        void                    release();
                        void                    refitUpdatedAndRemoved();
                        void                    updateBucketPruner();
    };
 
}
 
}
 
#endif