Initial commit:

PhysX 3.4.0 Update @ 21294896
APEX 1.4.0 Update @ 21275617

[CL 21300167]

1 files changed, 530 insertions, 0 deletions

diff --git a/PhysX_3.4/Source/GeomUtils/src/mesh/GuBV32Build.cpp b/PhysX_3.4/Source/GeomUtils/src/mesh/GuBV32Build.cpp
new file mode 100644
index 00000000..da62280f
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/mesh/GuBV32Build.cpp
@@ -0,0 +1,530 @@
+// 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.  
+
+#include "foundation/PxVec4.h"
+#include "GuBV32Build.h"
+#include "GuBV32.h"
+#include "PxTriangle.h"
+#include "CmPhysXCommon.h"
+#include "PsBasicTemplates.h"
+#include "GuCenterExtents.h"
+#include "GuBV4Build.h"
+#include "PsAllocator.h"
+
+using namespace physx;
+using namespace Gu;
+
+#include "PsVecMath.h"
+using namespace physx::shdfnd::aos;
+
+#define DELETESINGLE(x)	if (x) { delete x;		x = NULL; }
+#define DELETEARRAY(x)	if (x) { delete []x;	x = NULL; }
+
+struct BV32Node : public physx::shdfnd::UserAllocated
+{
+	BV32Node() : mNbChildBVNodes(0)
+	{}
+
+	BV32Data	mBVData[32];
+	PxU32		mNbChildBVNodes;
+
+	PX_FORCE_INLINE	size_t			isLeaf(PxU32 i)			const	{ return mBVData[i].mData & 1; }
+	PX_FORCE_INLINE	PxU32			getPrimitive(PxU32 i)	const	{ return PxU32(mBVData[i].mData >> 1); }
+	PX_FORCE_INLINE	const BV32Node*	getChild(PxU32 i)		const	{ return reinterpret_cast<BV32Node*>(mBVData[i].mData); }
+
+
+	PxU32 getSize() const
+	{
+		return sizeof(BV32Data)*mNbChildBVNodes;
+	}
+};
+
+
+static void fillInNodes(const AABBTreeNode* current_node, const PxU32 startIndex, const PxU32 endIndex, const AABBTreeNode** NODES, PxU32& stat)
+{
+
+	if (startIndex + 1 == endIndex)
+	{
+		//fill in nodes
+		const AABBTreeNode* P = current_node->getPos();
+		const AABBTreeNode* N = current_node->getNeg();
+		NODES[startIndex] = P;
+		NODES[endIndex] = N;
+		stat += 2;
+	}
+	else
+	{
+		const AABBTreeNode* P = current_node->getPos();
+		const AABBTreeNode* N = current_node->getNeg();
+		const PxU32 midIndex = startIndex + ((endIndex - startIndex) / 2);
+		if (!P->isLeaf())
+			fillInNodes(P, startIndex, midIndex, NODES, stat);
+		else
+		{
+			NODES[startIndex] = P;
+			stat++;
+		}
+
+		if (!N->isLeaf())
+			fillInNodes(N, midIndex + 1, endIndex, NODES, stat);
+		else
+		{
+			NODES[midIndex + 1] = N;
+			stat++;
+		}
+	}
+}
+
+
+
+static void setPrimitive(const AABBTree& source, BV32Node* node32, PxU32 i, const AABBTreeNode* node, float epsilon)
+{
+	const PxU32 nbPrims = node->getNbPrimitives();
+	PX_ASSERT(nbPrims<=32);
+	const PxU32* indexBase = source.getIndices();
+	const PxU32* prims = node->getPrimitives();
+	const PxU32 offset = PxU32(prims - indexBase);
+	
+#if BV32_VALIDATE
+	for (PxU32 j = 0; j<nbPrims; j++)
+	{
+		PX_ASSERT(prims[j] == offset + j);
+	}
+#endif
+	const PxU32 primitiveIndex = (offset << 6) | (nbPrims & 63);
+
+	node32->mBVData[i].mCenter = node->getAABB().getCenter();
+	node32->mBVData[i].mExtents = node->getAABB().getExtents();
+	if (epsilon != 0.0f)
+		node32->mBVData[i].mExtents += PxVec3(epsilon, epsilon, epsilon);
+	node32->mBVData[i].mData = (primitiveIndex << 1) | 1;
+}
+
+static BV32Node* setNode(const AABBTree& source, BV32Node* node32, PxU32 i, const AABBTreeNode* node, float epsilon)
+{
+	BV32Node* child = NULL;
+
+	if (node)
+	{
+		if (node->isLeaf())
+		{
+			setPrimitive(source, node32, i, node, epsilon);
+		}
+		else
+		{
+			node32->mBVData[i].mCenter = node->getAABB().getCenter();
+			node32->mBVData[i].mExtents = node->getAABB().getExtents();
+			if (epsilon != 0.0f)
+				node32->mBVData[i].mExtents += PxVec3(epsilon, epsilon, epsilon);
+
+			child = PX_NEW(BV32Node);
+			node32->mBVData[i].mData = size_t(child);
+		}
+	}
+	
+	return child;
+}
+
+
+static void _BuildBV32(const AABBTree& source, BV32Node* tmp, const AABBTreeNode* current_node, float epsilon, PxU32& nbNodes)
+{
+	PX_ASSERT(!current_node->isLeaf());
+
+	const AABBTreeNode* NODES[32];
+	memset(NODES, 0, sizeof(AABBTreeNode*) * 32);
+
+	fillInNodes(current_node, 0, 31, NODES, tmp->mNbChildBVNodes);
+
+	PxU32 left = 0;
+	PxU32 right = 31;
+
+	while (left < right)
+	{
+		
+		//sweep from the front
+		while (left<right)
+		{
+			//found a hole
+			if (NODES[left] == NULL)
+				break;
+			left++;
+		}
+
+		//sweep from the back
+		while (left < right)
+		{
+			//found a node
+			if (NODES[right])
+				break;
+			right--;
+		}
+
+		if (left != right)
+		{
+			//swap left and right
+			const AABBTreeNode* node = NODES[right];
+			NODES[right] = NODES[left];
+			NODES[left] = node;
+		}
+
+	}
+
+	nbNodes += tmp->mNbChildBVNodes;
+
+	for (PxU32 i = 0; i < tmp->mNbChildBVNodes; ++i)
+	{
+		const AABBTreeNode* tempNode = NODES[i];
+		BV32Node* Child = setNode(source, tmp, i, tempNode, epsilon);
+		if (Child)
+		{
+			_BuildBV32(source, Child, tempNode, epsilon, nbNodes);
+		}
+	}
+
+}
+
+//
+//static void validateTree(const AABBTree& Source, const AABBTreeNode* currentNode)
+//{
+//	if (currentNode->isLeaf())
+//	{
+//		const PxU32* indexBase = Source.getIndices();
+//		const PxU32* prims = currentNode->getPrimitives();
+//		const PxU32 offset = PxU32(prims - indexBase);
+//		const PxU32 nbPrims = currentNode->getNbPrimitives();
+//		for (PxU32 j = 0; j<nbPrims; j++)
+//		{
+//			PX_ASSERT(prims[j] == offset + j);
+//		}
+//	}
+//	else
+//	{
+//		const AABBTreeNode* pos = currentNode->getPos();
+//		validateTree(Source, pos);
+//		const AABBTreeNode* neg = currentNode->getNeg();
+//		validateTree(Source, neg);
+//	}
+//}
+
+#if BV32_VALIDATE
+static void validateNodeBound(const BV32Node* currentNode, SourceMesh* mesh)
+{
+	const PxU32 nbNodes = currentNode->mNbChildBVNodes;
+	for (PxU32 i = 0; i < nbNodes; ++i)
+	{
+		const BV32Node* node = currentNode->getChild(i);
+		if (currentNode->isLeaf(i))
+		{
+			BV32Data data = currentNode->mBVData[i];
+			PxU32 nbTriangles = data.getNbReferencedTriangles();
+			PxU32 startIndex = data.getTriangleStartIndex();
+			const IndTri32* triIndices = mesh->getTris32();
+			const PxVec3* verts = mesh->getVerts();
+			PxVec3 min(PX_MAX_F32, PX_MAX_F32, PX_MAX_F32);
+			PxVec3 max(-PX_MAX_F32, -PX_MAX_F32, -PX_MAX_F32);
+			for (PxU32 j = 0; j < nbTriangles; ++j)
+			{
+				IndTri32 index = triIndices[startIndex + j];
+
+				for (PxU32 k = 0; k < 3; ++k)
+				{
+					const PxVec3& v = verts[index.mRef[k]];
+
+					min.x = (min.x > v.x) ? v.x : min.x;
+					min.y = (min.y > v.y) ? v.y : min.y;
+					min.z = (min.z > v.z) ? v.z : min.z;
+
+					max.x = (max.x < v.x) ? v.x : max.x;
+					max.y = (max.y > v.y) ? v.y : max.y;
+					max.z = (max.z > v.z) ? v.z : max.z;
+				}
+			}
+
+			PxVec3 dMin, dMax;
+			data.getMinMax(dMin, dMax);
+			PX_ASSERT(dMin.x <= min.x && dMin.y <= min.y && dMin.z <= min.z);
+			PX_ASSERT(dMax.x >= max.x && dMax.y >= max.y && dMax.z >= min.z);
+
+		}
+		else
+		{
+			validateNodeBound(node, mesh);
+		}
+	}
+}
+#endif
+
+static bool BuildBV32Internal(BV32Tree& bv32Tree, const AABBTree& Source, SourceMesh* mesh, float epsilon)
+{
+	if (mesh->getNbTriangles() <= 32)
+	{
+		bv32Tree.mNbPackedNodes = 1;
+		bv32Tree.mPackedNodes = reinterpret_cast<BV32DataPacked*>(PX_ALLOC(sizeof(BV32DataPacked), "BV32DataPacked"));
+		BV32DataPacked& packedData = bv32Tree.mPackedNodes[0];
+		packedData.mNbNodes = 1;
+		packedData.mCenter[0] = PxVec4(Source.getBV().getCenter(), 0.f);
+		packedData.mExtents[0] = PxVec4(Source.getBV().getExtents(), 0.f);
+		packedData.mData[0] = (mesh->getNbTriangles() << 1) | 1;
+		return bv32Tree.init(mesh, Source.getBV());
+	}
+
+	{
+		struct Local
+		{
+			static void _CheckMD(const AABBTreeNode* current_node, PxU32& md, PxU32& cd)
+			{
+				cd++;
+				md = PxMax(md, cd);
+
+				if (current_node->getPos())	{ _CheckMD(current_node->getPos(), md, cd);	cd--; }
+				if (current_node->getNeg())	{ _CheckMD(current_node->getNeg(), md, cd);	cd--; }
+			}
+
+			static void _Check(AABBTreeNode* current_node)
+			{
+				if (current_node->isLeaf())
+					return;
+
+				AABBTreeNode* P = const_cast<AABBTreeNode*>(current_node->getPos());
+				AABBTreeNode* N = const_cast<AABBTreeNode*>(current_node->getNeg());
+				{
+					PxU32 MDP = 0;	PxU32 CDP = 0;	_CheckMD(P, MDP, CDP);
+					PxU32 MDN = 0;	PxU32 CDN = 0;	_CheckMD(N, MDN, CDN);
+
+					if (MDP>MDN)
+						//					if(MDP<MDN)
+					{
+						Ps::swap(*P, *N);
+						Ps::swap(P, N);
+					}
+				}
+				_Check(P);
+				_Check(N);
+			}
+		};
+		Local::_Check(const_cast<AABBTreeNode*>(Source.getNodes()));
+	}
+
+
+	PxU32 nbNodes = 1;
+	BV32Node* Root32 = PX_NEW(BV32Node);
+
+
+	_BuildBV32(Source, Root32, Source.getNodes(), epsilon, nbNodes);
+
+#if BV32_VALIDATE
+	validateNodeBound(Root32, mesh);
+#endif
+
+	if (!bv32Tree.init(mesh, Source.getBV()))
+		return false;
+	BV32Tree* T = &bv32Tree;
+
+	// Version with variable-sized nodes in single stream
+	{
+		struct Local
+		{
+			static void _Flatten(BV32Data* const dest, const PxU32 box_id, PxU32& current_id, const BV32Node* current, PxU32& max_depth, PxU32& current_depth, const PxU32 nb_nodes)
+			{
+				// Entering a new node => increase depth
+				current_depth++;
+				// Keep track of max depth
+				if (current_depth>max_depth)
+					max_depth = current_depth;
+
+				for (PxU32 i = 0; i<current->mNbChildBVNodes; i++)
+				{
+					dest[box_id + i].mCenter = current->mBVData[i].mCenter;
+					dest[box_id + i].mExtents = current->mBVData[i].mExtents;
+					dest[box_id + i].mData = PxU32(current->mBVData[i].mData);
+
+					PX_ASSERT(box_id + i < nb_nodes);
+				}
+
+				PxU32 NbToGo = 0;
+				PxU32 NextIDs[32];
+				memset(NextIDs, PX_INVALID_U32, sizeof(PxU32)*32); 
+				const BV32Node* ChildNodes[32];
+				memset(ChildNodes, 0, sizeof(BV32Node*)*32);
+
+				BV32Data* data = dest + box_id;
+				for (PxU32 i = 0; i<current->mNbChildBVNodes; i++)
+				{
+					PX_ASSERT(current->mBVData[i].mData != PX_INVALID_U32);
+
+					if (!current->isLeaf(i))
+					{
+
+						const BV32Node* ChildNode = current->getChild(i);
+
+						const PxU32 NextID = current_id;
+
+						const PxU32 ChildSize = ChildNode->mNbChildBVNodes;
+						current_id += ChildSize;
+
+						const PxU32 ChildType = ChildNode->mNbChildBVNodes << 1;
+						data[i].mData = size_t(ChildType + (NextID << GU_BV4_CHILD_OFFSET_SHIFT_COUNT));
+						//PX_ASSERT(data[i].mData == size_t(ChildType+(NextID<<3)));
+
+						PX_ASSERT(box_id + i < nb_nodes);
+
+						NextIDs[NbToGo] = NextID;
+						ChildNodes[NbToGo] = ChildNode;
+						NbToGo++;
+					}
+				}
+
+			
+
+				for (PxU32 i = 0; i<NbToGo; i++)
+				{
+					_Flatten(dest, NextIDs[i], current_id, ChildNodes[i], max_depth, current_depth, nb_nodes);
+					current_depth--;
+				}
+
+				DELETESINGLE(current);
+			}
+		};
+
+
+		PxU32 CurID = Root32->mNbChildBVNodes+1;
+
+		BV32Data* Nodes = PX_NEW(BV32Data)[nbNodes];
+		Nodes[0].mCenter = Source.getBV().getCenter();
+		Nodes[0].mExtents = Source.getBV().getExtents();
+
+		const PxU32 ChildType = Root32->mNbChildBVNodes << 1;
+		Nodes[0].mData = size_t(ChildType + (1 << GU_BV4_CHILD_OFFSET_SHIFT_COUNT));
+
+		const PxU32 nbChilden = Nodes[0].getNbChildren();
+
+		PX_UNUSED(nbChilden);
+
+
+		T->mInitData = CurID;
+		PxU32 MaxDepth = 0;
+		PxU32 CurrentDepth = 0;
+
+		Local::_Flatten(Nodes, 1, CurID, Root32, MaxDepth, CurrentDepth, nbNodes);
+
+		PX_ASSERT(CurID == nbNodes);
+
+		T->mNbNodes = nbNodes;
+
+		T->mNodes = Nodes;
+	}
+
+	
+	bv32Tree.calculateLeafNode(bv32Tree.mNodes[0]);
+	
+	bv32Tree.mPackedNodes = reinterpret_cast<BV32DataPacked*>(PX_ALLOC(sizeof(BV32DataPacked)*nbNodes, "BV32DataPacked"));
+	bv32Tree.mNbPackedNodes = nbNodes;
+
+	PxU32 nbPackedNodes = 1;
+	PxU32 currentIndex = bv32Tree.mNodes[0].getNbChildren() - bv32Tree.mNodes[0].mNbLeafNodes + 1;
+	BV32DataPacked& packedData = bv32Tree.mPackedNodes[0];
+	bv32Tree.createSOAformatNode(packedData, bv32Tree.mNodes[0], 1, currentIndex, nbPackedNodes);
+
+	bv32Tree.mNbPackedNodes = nbPackedNodes;
+
+	PX_ASSERT(nbPackedNodes == currentIndex);
+	PX_ASSERT(nbPackedNodes > 0);
+
+	return true;
+}
+
+/////
+
+struct ReorderData32
+{
+	const SourceMesh*	mMesh;
+	PxU32*				mOrder;
+	PxU32				mNbTrisPerLeaf;
+	PxU32				mIndex;
+	PxU32				mNbTris;
+	PxU32				mStats[32];
+};
+
+static bool gReorderCallback(const AABBTreeNode* current, PxU32 /*depth*/, void* userData)
+{
+	ReorderData32* Data = reinterpret_cast<ReorderData32*>(userData);
+	if (current->isLeaf())
+	{
+		const PxU32 n = current->getNbPrimitives();
+		PX_ASSERT(n > 0);
+		PX_ASSERT(n <= Data->mNbTrisPerLeaf);
+		Data->mStats[n-1]++;
+		PxU32* Prims = const_cast<PxU32*>(current->getPrimitives());
+
+		for (PxU32 i = 0; i<n; i++)
+		{
+			PX_ASSERT(Prims[i]<Data->mNbTris);
+			Data->mOrder[Data->mIndex] = Prims[i];
+			PX_ASSERT(Data->mIndex<Data->mNbTris);
+			Prims[i] = Data->mIndex;
+			Data->mIndex++;
+		}
+	}
+	return true;
+}
+
+
+bool physx::Gu::BuildBV32Ex(BV32Tree& tree, SourceMesh& mesh, float epsilon, PxU32 nbTrisPerLeaf)
+{
+	const PxU32 nbTris = mesh.mNbTris;
+
+	AABBTree Source;
+	if (!Source.buildFromMesh(mesh, nbTrisPerLeaf))
+		return false;
+
+
+	{
+		PxU32* order = reinterpret_cast<PxU32*>(PX_ALLOC(sizeof(PxU32)*nbTris, "BV32"));
+		ReorderData32 RD;
+		RD.mMesh = &mesh;
+		RD.mOrder = order;
+		RD.mNbTrisPerLeaf = nbTrisPerLeaf;
+		RD.mIndex = 0;
+		RD.mNbTris = nbTris;
+		for (PxU32 i = 0; i<32; i++)
+			RD.mStats[i] = 0;
+		Source.walk(gReorderCallback, &RD);
+		PX_ASSERT(RD.mIndex == nbTris);
+		mesh.remapTopology(order);
+		PX_FREE(order);
+		//		for(PxU32 i=0;i<16;i++)
+		//			printf("%d: %d\n", i, RD.mStats[i]);
+	}
+
+
+	//if (mesh.getNbTriangles() <= nbTrisPerLeaf)
+	//	return tree.init(&mesh, Source.getBV());
+
+	return BuildBV32Internal(tree, Source, &mesh, epsilon);
+}