PhysX 3.4, APEX 1.4 patch release @23879214

1 files changed, 19 insertions, 239 deletions

diff --git a/PhysX_3.4/Source/SceneQuery/src/SqAABBTree.cpp b/PhysX_3.4/Source/SceneQuery/src/SqAABBTree.cpp
index bb628010..bcb0e0ef 100644
--- a/PhysX_3.4/Source/SceneQuery/src/SqAABBTree.cpp
+++ b/PhysX_3.4/Source/SceneQuery/src/SqAABBTree.cpp
@@ -42,105 +42,42 @@ using namespace Sq;
 // Progressive building
 class Sq::FIFOStack : public Ps::UserAllocated
 {
-	public:
-										FIFOStack() : mStack(PX_DEBUG_EXP("SQFIFOStack")), mCurIndex(0) {}
-										~FIFOStack() {}
+public:
+	FIFOStack() : mStack(PX_DEBUG_EXP("SQFIFOStack")), mCurIndex(0) {}
+	~FIFOStack() {}
 
 	PX_FORCE_INLINE	PxU32				getNbEntries() const { return mStack.size(); }
-	PX_FORCE_INLINE	void				push(AABBTreeBuildNode* entry)	{ mStack.pushBack(entry); }
-					bool				pop(AABBTreeBuildNode*& entry);
-	private:
-		Ps::Array<AABBTreeBuildNode*>	mStack;
-		PxU32							mCurIndex;			//!< Current index within the container
+	PX_FORCE_INLINE	void				push(AABBTreeBuildNode* entry) { mStack.pushBack(entry); }
+	bool				pop(AABBTreeBuildNode*& entry);
+private:
+	Ps::Array<AABBTreeBuildNode*>	mStack;
+	PxU32							mCurIndex;			//!< Current index within the container
 };
 
 bool Sq::FIFOStack::pop(AABBTreeBuildNode*& entry)
 {
 	const PxU32 NbEntries = mStack.size(); // Get current number of entries
-	if(!NbEntries)
+	if (!NbEntries)
 		return false; // Can be NULL when no value has been pushed. This is an invalid pop call.
 	entry = mStack[mCurIndex++]; // Get oldest entry, move to next one
-	if(mCurIndex==NbEntries)
+	if (mCurIndex == NbEntries)
 	{
 		// All values have been poped
 		mStack.clear();
-		mCurIndex=0;
+		mCurIndex = 0;
 	}
 	return true;
 }
 //~Progressive building
 
-NodeAllocator::NodeAllocator() : mPool(NULL), mCurrentSlabIndex(0), mTotalNbNodes(0)
-{
-}
-
-NodeAllocator::~NodeAllocator()
-{
-	release();
-}
-
-void NodeAllocator::release()
-{
-	const PxU32 nbSlabs = mSlabs.size();
-	for(PxU32 i=0;i<nbSlabs;i++)
-	{
-		Slab& s = mSlabs[i];
-		PX_DELETE_ARRAY(s.mPool);
-	}
-
-	mSlabs.reset();
-	mCurrentSlabIndex = 0;
-	mTotalNbNodes = 0;
-}
-
-void NodeAllocator::init(PxU32 nbPrimitives, PxU32 limit)
-{
-	const PxU32 maxSize = nbPrimitives*2 - 1;	// PT: max possible #nodes for a complete tree
-	const PxU32 estimatedFinalSize = maxSize<=1024 ? maxSize : maxSize/limit;
-	mPool = PX_NEW(AABBTreeBuildNode)[estimatedFinalSize];
-	PxMemZero(mPool, sizeof(AABBTreeBuildNode)*estimatedFinalSize);
-
-	// Setup initial node. Here we have a complete permutation of the app's primitives.
-	mPool->mNodeIndex		= 0;
-	mPool->mNbPrimitives	= nbPrimitives;
-
-	mSlabs.pushBack(Slab(mPool, 1, estimatedFinalSize));
-	mCurrentSlabIndex = 0;
-	mTotalNbNodes = 1;
-}
-
-// PT: TODO: inline this?
-AABBTreeBuildNode* NodeAllocator::getBiNode()
-{
-	mTotalNbNodes += 2;
-	Slab& currentSlab = mSlabs[mCurrentSlabIndex];
-	if(currentSlab.mNbUsedNodes+2<=currentSlab.mMaxNbNodes)
-	{
-		AABBTreeBuildNode* biNode = currentSlab.mPool + currentSlab.mNbUsedNodes;
-		currentSlab.mNbUsedNodes += 2;
-		return biNode;
-	}
-	else
-	{
-		// Allocate new slab
-		const PxU32 size = 1024;
-		AABBTreeBuildNode* pool = PX_NEW(AABBTreeBuildNode)[size];
-		PxMemZero(pool, sizeof(AABBTreeBuildNode)*size);
-
-		mSlabs.pushBack(Slab(pool, 2, size));
-		mCurrentSlabIndex++;
-		return pool;
-	}
-}
-
-void NodeAllocator::flatten(AABBTreeRuntimeNode* dest)
+void flatten(const NodeAllocator& nodeAllocator, AABBTreeRuntimeNode* dest)
 {
 	// PT: gathers all build nodes allocated so far and flatten them to a linear destination array of smaller runtime nodes
 	PxU32 offset = 0;
-	const PxU32 nbSlabs = mSlabs.size();
+	const PxU32 nbSlabs = nodeAllocator.mSlabs.size();
 	for(PxU32 s=0;s<nbSlabs;s++)
 	{
-		const Slab& currentSlab = mSlabs[s];
+		const NodeAllocator::Slab& currentSlab = nodeAllocator.mSlabs[s];
 
 		AABBTreeBuildNode* pool = currentSlab.mPool;
 		for(PxU32 i=0;i<currentSlab.mNbUsedNodes;i++)
@@ -162,177 +99,19 @@ void NodeAllocator::flatten(AABBTreeRuntimeNode* dest)
 				PxU32 nodeBase = 0;
 				for(PxU32 j=0;j<nbSlabs;j++)
 				{
-					if(pool[i].mPos>=mSlabs[j].mPool && pool[i].mPos<mSlabs[j].mPool+mSlabs[j].mNbUsedNodes)
+					if(pool[i].mPos>= nodeAllocator.mSlabs[j].mPool && pool[i].mPos < nodeAllocator.mSlabs[j].mPool + nodeAllocator.mSlabs[j].mNbUsedNodes)
 					{
-						localNodeIndex = PxU32(pool[i].mPos - mSlabs[j].mPool);
+						localNodeIndex = PxU32(pool[i].mPos - nodeAllocator.mSlabs[j].mPool);
 						break;
 					}
-					nodeBase += mSlabs[j].mNbUsedNodes;
+					nodeBase += nodeAllocator.mSlabs[j].mNbUsedNodes;
 				}
 				const PxU32 nodeIndex = nodeBase + localNodeIndex;
-				PX_ASSERT(nodeIndex<mTotalNbNodes);
 				dest[offset].mData = nodeIndex<<1;
 			}
 			offset++;
 		}
 	}
-	PX_ASSERT(offset==mTotalNbNodes);
-	release();
-}
-
-static PX_FORCE_INLINE float getSplittingValue(const PxBounds3& global_box, PxU32 axis)
-{
-	// Default split value = middle of the axis (using only the box)
-	return global_box.getCenter(axis);
-}
-
-static PxU32 split(const PxBounds3& box, PxU32 nb, PxU32* const PX_RESTRICT prims, PxU32 axis, const AABBTreeBuildParams& params)
-{
-	// Get node split value
-	const float splitValue = getSplittingValue(box, axis);
-
-	PxU32 nbPos = 0;
-	// Loop through all node-related primitives. Their indices range from "mNodePrimitives[0]" to "mNodePrimitives[mNbPrimitives-1]",
-	// with mNodePrimitives = mIndices + mNodeIndex (i.e. those indices map the global list in the tree params).
-
-	// PT: to avoid calling the unsafe [] operator
-	const size_t ptrValue = size_t(params.mCache) + axis*sizeof(float);
-	const PxVec3* /*PX_RESTRICT*/ cache = reinterpret_cast<const PxVec3*>(ptrValue);
-
-	for(PxU32 i=0;i<nb;i++)
-	{
-		// Get index in global list
-		const PxU32 index = prims[i];
-
-		// Test against the splitting value. The primitive value is tested against the enclosing-box center.
-		// [We only need an approximate partition of the enclosing box here.]
-		const float primitiveValue = cache[index].x;
-		PX_ASSERT(primitiveValue==params.mCache[index][axis]);
-
-		// Reorganize the list of indices in this order: positive - negative.
-		if(primitiveValue > splitValue)
-		{
-			// Swap entries
-			prims[i] = prims[nbPos];
-			prims[nbPos] = index;
-			// Count primitives assigned to positive space
-			nbPos++;
-		}
-	}
-	return nbPos;
-}
-
-void AABBTreeBuildNode::subdivide(const AABBTreeBuildParams& params, BuildStats& stats, NodeAllocator& allocator, PxU32* const indices)
-{
-	PxU32* const PX_RESTRICT primitives = indices + mNodeIndex;
-	const PxU32 nbPrims = mNbPrimitives;
-
-	// Compute global box & means for current node. The box is stored in mBV.
-	Vec4V meansV;
-	{
-		const PxBounds3* PX_RESTRICT boxes = params.mAABBArray;
-		PX_ASSERT(boxes);
-		PX_ASSERT(primitives);
-		PX_ASSERT(nbPrims);
-
-		Vec4V minV = V4LoadU(&boxes[primitives[0]].minimum.x);
-		Vec4V maxV = V4LoadU(&boxes[primitives[0]].maximum.x);
-
-		meansV = V4LoadU(&params.mCache[primitives[0]].x);
-
-		for(PxU32 i=1;i<nbPrims;i++)
-		{
-			const PxU32 index = primitives[i];
-			const Vec4V curMinV = V4LoadU(&boxes[index].minimum.x);
-			const Vec4V curMaxV = V4LoadU(&boxes[index].maximum.x);
-			meansV = V4Add(meansV, V4LoadU(&params.mCache[index].x));
-			minV = V4Min(minV, curMinV);
-			maxV = V4Max(maxV, curMaxV);
-		}
-
-		StoreBounds(mBV, minV, maxV);
-
-		const float coeff = 1.0f/float(nbPrims);
-		meansV = V4Scale(meansV, FLoad(coeff));
-	}
-
-	// Check the user-defined limit. Also ensures we stop subdividing if we reach a leaf node.
-	if(nbPrims<=params.mLimit)
-		return;
-
-	bool validSplit = true;
-	PxU32 nbPos;
-	{
-		// Compute variances
-		Vec4V varsV = V4Zero();
-		for(PxU32 i=0;i<nbPrims;i++)
-		{
-			const PxU32 index = primitives[i];
-			Vec4V centerV = V4LoadU(&params.mCache[index].x);
-			centerV = V4Sub(centerV, meansV);
-			centerV = V4Mul(centerV, centerV);
-			varsV = V4Add(varsV, centerV);
-		}
-		const float coeffNb1 = 1.0f/float(nbPrims-1);
-		varsV = V4Scale(varsV, FLoad(coeffNb1));
-		PX_ALIGN(16, PxVec4) vars;
-		V4StoreA(varsV, &vars.x);
-
-		// Choose axis with greatest variance
-		const PxU32 axis = Ps::largestAxis(PxVec3(vars.x, vars.y, vars.z));
-
-		// Split along the axis
-		nbPos = split(mBV, nbPrims, primitives, axis, params);
-
-		// Check split validity
-		if(!nbPos || nbPos==nbPrims)
-			validSplit = false;
-	}
-
-	// Check the subdivision has been successful
-	if(!validSplit)
-	{
-		// Here, all boxes lie in the same sub-space. Two strategies:
-		// - if we are over the split limit, make an arbitrary 50-50 split
-		// - else stop subdividing
-		if(nbPrims>params.mLimit)
-		{
-			nbPos = nbPrims>>1;
-		}
-		else return;
-	}
-
-	// Now create children and assign their pointers.
-	mPos = allocator.getBiNode();
-
-	stats.increaseCount(2);
-
-	// Assign children
-	PX_ASSERT(!isLeaf());
-	AABBTreeBuildNode* Pos = const_cast<AABBTreeBuildNode*>(mPos);
-	AABBTreeBuildNode* Neg = Pos + 1;
-	Pos->mNodeIndex		= mNodeIndex;
-	Pos->mNbPrimitives	= nbPos;
-	Neg->mNodeIndex		= mNodeIndex + nbPos;
-	Neg->mNbPrimitives	= mNbPrimitives - nbPos;
-}
-
-void AABBTreeBuildNode::_buildHierarchy(AABBTreeBuildParams& params, BuildStats& stats, NodeAllocator& nodeBase, PxU32* const indices)
-{
-	// Subdivide current node
-	subdivide(params, stats, nodeBase, indices);
-
-	// Recurse
-	if(!isLeaf())
-	{
-		AABBTreeBuildNode* Pos = const_cast<AABBTreeBuildNode*>(getPos());
-		PX_ASSERT(Pos);
-		AABBTreeBuildNode* Neg = Pos + 1;
-		Pos->_buildHierarchy(params, stats, nodeBase, indices);
-		Neg->_buildHierarchy(params, stats, nodeBase, indices);
-	}
-
-	stats.mTotalPrims += mNbPrimitives;
 }
 
 AABBTree::AABBTree() :
@@ -449,7 +228,8 @@ void AABBTree::buildEnd(AABBTreeBuildParams& params, BuildStats& stats)
 
 	mRuntimePool = PX_NEW(AABBTreeRuntimeNode)[mTotalNbNodes];
 	PX_ASSERT(mTotalNbNodes==mNodeAllocator.mTotalNbNodes);
-	mNodeAllocator.flatten(mRuntimePool);
+	flatten(mNodeAllocator, mRuntimePool);
+	mNodeAllocator.release();
 }
 
 bool AABBTree::build(AABBTreeBuildParams& params)