Skip to content

A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.

11.2 KB
Raw Blame
// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
// SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0

#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 PX_OVERRIDE { return mIncrementalRebuild;	}
		//~Pruner

		// DynamicPruner
		virtual			void					setRebuildRateHint(PxU32 nbStepsForRebuild) PX_OVERRIDE;	// Besides the actual rebuild steps, 3 additional steps are needed.
		virtual			bool					buildStep(bool synchronousCall = true) PX_OVERRIDE;	// returns true if finished
		virtual			bool					prepareBuild() PX_OVERRIDE;	// 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