Initial commit:

PhysX 3.4.0 Update @ 21294896
APEX 1.4.0 Update @ 21275617

[CL 21300167]

1 files changed, 279 insertions, 0 deletions

diff --git a/PhysX_3.4/Source/SceneQuery/src/SqBucketPruner.h b/PhysX_3.4/Source/SceneQuery/src/SqBucketPruner.h
new file mode 100644
index 00000000..dec62ccd
--- /dev/null
+++ b/PhysX_3.4/Source/SceneQuery/src/SqBucketPruner.h
@@ -0,0 +1,279 @@
+// 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_BUCKETPRUNER_H
+#define SQ_BUCKETPRUNER_H
+
+#include "SqTypedef.h"
+#include "SqPruningPool.h"
+#include "PsHash.h"
+
+#define FREE_PRUNER_SIZE	16
+//#define USE_REGULAR_HASH_MAP
+#ifdef USE_REGULAR_HASH_MAP
+	#include "PsHashMap.h"
+#endif
+
+namespace physx
+{
+namespace Sq
+{
+	typedef PxU32	BucketWord;
+	
+#if PX_VC 
+    #pragma warning(push)
+	#pragma warning( disable : 4324 ) // Padding was added at the end of a structure because of a __declspec(align) value.
+#endif
+
+	PX_ALIGN_PREFIX(16)	struct BucketBox
+	{
+		PxVec3	mCenter;
+		PxU32	mData0;		// Integer-encoded min value along sorting axis
+		PxVec3	mExtents;
+		PxU32	mData1;		// Integer-encoded max value along sorting axis
+
+	#ifdef _DEBUG
+		// PT: we need the original min value for debug checks. Using the center/extents version
+		// fails because recomputing the min from them introduces FPU accuracy errors in the values.
+		float	mDebugMin;
+	#endif
+
+		PX_FORCE_INLINE	PxVec3	getMin()	const
+		{
+			return mCenter - mExtents;
+		}
+
+		PX_FORCE_INLINE	PxVec3	getMax()	const
+		{
+			return mCenter + mExtents;
+		}
+
+		PX_FORCE_INLINE void	setEmpty()
+		{
+			mCenter = PxVec3(0.0f);
+			mExtents = PxVec3(-PX_MAX_BOUNDS_EXTENTS);
+
+	#ifdef _DEBUG
+			mDebugMin = PX_MAX_BOUNDS_EXTENTS;
+	#endif
+		}
+	}PX_ALIGN_SUFFIX(16);
+
+	PX_ALIGN_PREFIX(16) struct BucketPrunerNode
+	{
+					BucketPrunerNode();
+
+		void		classifyBoxes(	float limitX, float limitZ,
+									PxU32 nb,
+									BucketBox* PX_RESTRICT boxes,
+									const PrunerPayload* PX_RESTRICT objects,
+									BucketBox* PX_RESTRICT sortedBoxes,
+									PrunerPayload* PX_RESTRICT sortedObjects,
+									bool isCrossBucket, PxU32 sortAxis);
+
+		PX_FORCE_INLINE	void	initCounters()
+		{
+			for(PxU32 i=0;i<5;i++)
+				mCounters[i] = 0;
+			for(PxU32 i=0;i<5;i++)
+				mOffsets[i] = 0;
+		}
+
+		BucketWord	mCounters[5];	// Number of objects in each of the 5 children
+		BucketWord	mOffsets[5];	// Start index of objects for each of the 5 children
+		BucketBox	mBucketBox[5];	// AABBs around objects for each of the 5 children
+		PxU16		mOrder[8];		// PNS: 5 children => 3 bits/index => 3*5=15 bits total, for each of the 8 canonical directions
+	}PX_ALIGN_SUFFIX(16);
+
+	PX_FORCE_INLINE PxU32 hash(const PrunerPayload& payload)
+	{
+#if PX_P64_FAMILY
+//		const PxU32 h0 = Ps::hash((const void*)payload.data[0]);
+//		const PxU32 h1 = Ps::hash((const void*)payload.data[1]);
+		const PxU32 h0 = PxU32(PX_MAX_U32 & payload.data[0]);
+		const PxU32 h1 = PxU32(PX_MAX_U32 & payload.data[1]);
+		return Ps::hash(PxU64(h0)|(PxU64(h1)<<32));
+#else
+		return Ps::hash(PxU64(payload.data[0])|(PxU64(payload.data[1])<<32));
+#endif
+	}
+
+#ifdef USE_REGULAR_HASH_MAP
+	struct BucketPrunerPair : public Ps::UserAllocated
+	{
+		PX_FORCE_INLINE	BucketPrunerPair()	{}
+		PX_FORCE_INLINE	BucketPrunerPair(PxU32 index, PxU32 stamp) : mCoreIndex(index), mTimeStamp(stamp)	{}
+		PxU32			mCoreIndex;	// index in mCoreObjects
+		PxU32			mTimeStamp;
+	};
+	typedef Ps::HashMap<PrunerPayload, BucketPrunerPair> BucketPrunerMap;
+#else
+	struct BucketPrunerPair : public Ps::UserAllocated
+	{
+		PrunerPayload	mPayload;
+		PxU32			mCoreIndex;	// index in mCoreObjects
+		PxU32			mTimeStamp;
+	};
+
+	// Custom hash-map - currently faster than the regular hash-map (Ps::HashMap), in particular for 'find-and-erase' operations.
+	class BucketPrunerMap : public Ps::UserAllocated
+	{
+		public:
+												BucketPrunerMap();
+												~BucketPrunerMap();
+
+						void					purge();
+						void					shrinkMemory();
+
+						BucketPrunerPair*		addPair				(const PrunerPayload& payload, PxU32 coreIndex, PxU32 timeStamp);
+						bool					removePair			(const PrunerPayload& payload, PxU32& coreIndex, PxU32& timeStamp);
+						const BucketPrunerPair*	findPair			(const PrunerPayload& payload) const;
+		PX_FORCE_INLINE	PxU32					getPairIndex		(const BucketPrunerPair* pair)		const
+												{
+													return (PxU32((size_t(pair) - size_t(mActivePairs)))/sizeof(BucketPrunerPair));
+												}
+
+						PxU32					mHashSize;
+						PxU32					mMask;
+						PxU32					mNbActivePairs;
+						PxU32*					mHashTable;
+						PxU32*					mNext;
+						BucketPrunerPair*		mActivePairs;
+						PxU32					mReservedMemory;
+
+		PX_FORCE_INLINE	BucketPrunerPair*		findPair(const PrunerPayload& payload, PxU32 hashValue) const;
+						void					removePairInternal(const PrunerPayload& payload, PxU32 hashValue, PxU32 pairIndex);
+						void					reallocPairs();
+						void					reserveMemory(PxU32 memSize);
+	};
+#endif
+
+	class BucketPrunerCore : public Ps::UserAllocated
+	{
+		public:
+											BucketPrunerCore(bool externalMemory=true);
+											~BucketPrunerCore();
+
+						void				release();
+
+						void				setExternalMemory(PxU32 nbObjects, PxBounds3* boxes, PrunerPayload* objects);
+
+						bool				addObject(const PrunerPayload& object, const PxBounds3& worldAABB, PxU32 timeStamp=0);
+						bool				removeObject(const PrunerPayload& object, PxU32& timeStamp);
+						bool				updateObject(const PxBounds3& worldAABB, const PrunerPayload& object);
+
+		// PT: look for objects marked with input timestamp everywhere in the structure, and remove them. This is the same
+		// as calling 'removeObject' individually for all these objects, but much more efficient. Returns number of removed objects.
+						PxU32				removeMarkedObjects(PxU32 timeStamp);
+
+						PxAgain				raycast(const PxVec3& origin, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&) const;
+						PxAgain				overlap(const Gu::ShapeData& queryVolume, PrunerCallback&) const;
+						PxAgain				sweep(const Gu::ShapeData& queryVolume, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&) const;
+
+						void				shiftOrigin(const PxVec3& shift);
+
+						void				visualize(Cm::RenderOutput& out, PxU32 color) const;
+
+		PX_FORCE_INLINE	void				build()					{ classifyBoxes();	}
+
+		PX_FORCE_INLINE	PxU32				getNbObjects()	const	{ return mNbFree + mCoreNbObjects;	}
+
+//		private:
+						PxU32				mCoreNbObjects;		// Current number of objects in core arrays
+						PxU32				mCoreCapacity;		// Capacity of core arrays
+						PxBounds3*			mCoreBoxes;			// Core array
+						PrunerPayload*		mCoreObjects;		// Core array
+						PxU32*				mCoreRemap;			// Remaps core index to sorted index, i.e. sortedIndex = mCoreRemap[coreIndex]
+
+						BucketBox*			mSortedWorldBoxes;	// Sorted array
+						PrunerPayload*		mSortedObjects;		// Sorted array
+
+						PxU32				mNbFree;						// Current number of objects in the "free array" (mFreeObjects/mFreeBounds)
+						PrunerPayload		mFreeObjects[FREE_PRUNER_SIZE];	// mNbFree objects are stored here
+						PxBounds3			mFreeBounds[FREE_PRUNER_SIZE];	// mNbFree object bounds are stored here
+						PxU32				mFreeStamps[FREE_PRUNER_SIZE];
+
+						BucketPrunerMap		mMap;			// Maps (PrunerPayload) object to corresponding index in core array.
+															// Objects in the free array do not appear in this map.
+						PxU32				mSortedNb;
+						PxU32				mSortedCapacity;
+						PxU32				mSortAxis;
+
+						BucketBox			mGlobalBox;		// Global bounds around all objects in the structure (except the ones in the "free" array)
+						BucketPrunerNode	mLevel1;
+						BucketPrunerNode	mLevel2[5];
+						BucketPrunerNode	mLevel3[5][5];
+
+						bool				mDirty;
+						bool				mOwnMemory;
+		private:
+						void				classifyBoxes();
+						void				allocateSortedMemory(PxU32 nb);
+						void				resizeCore();
+		PX_FORCE_INLINE void				addObjectInternal(const PrunerPayload& object, const PxBounds3& worldAABB, PxU32 timeStamp);
+	};
+
+#if PX_VC 
+     #pragma warning(pop) 
+#endif
+
+	class BucketPruner : public Pruner
+	{
+		public:
+										BucketPruner();
+		virtual							~BucketPruner();
+
+		// Pruner
+		virtual	bool					addObjects(PrunerHandle* results, const PxBounds3* bounds, const PrunerPayload* payload, PxU32 count, bool);
+		virtual	void					removeObjects(const PrunerHandle* handles, PxU32 count);
+		virtual	void					updateObjects(const PrunerHandle* handles, const PxBounds3* newBounds, PxU32 count);
+		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;
+		// merge not implemented for bucket pruner
+		virtual void					merge(const void* ) {}
+		//~Pruner
+
+		private:
+				BucketPrunerCore		mCore;
+				PruningPool				mPool;
+	};
+
+} // namespace Sq
+
+}
+
+#endif // SQ_BUCKETPRUNER_H