Initial commit:

PhysX 3.4.0 Update @ 21294896
APEX 1.4.0 Update @ 21275617

[CL 21300167]

1 files changed, 658 insertions, 0 deletions

diff --git a/APEX_1.4/common/src/ApexIsoMesh.cpp b/APEX_1.4/common/src/ApexIsoMesh.cpp
new file mode 100644
index 00000000..7700c9e2
--- /dev/null
+++ b/APEX_1.4/common/src/ApexIsoMesh.cpp
@@ -0,0 +1,658 @@
+/*
+ * Copyright (c) 2008-2015, NVIDIA CORPORATION.  All rights reserved.
+ *
+ * NVIDIA CORPORATION and its licensors retain all intellectual property
+ * and proprietary rights in and to this software, 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.
+ */
+
+
+#include "ApexIsoMesh.h"
+#include "ApexCollision.h"
+#include "ApexMarchingCubes.h"
+#include "ApexSharedUtils.h"
+
+#include "ApexSDKIntl.h"
+
+#include "PsSort.h"
+
+namespace nvidia
+{
+namespace apex
+{
+
+ApexIsoMesh::ApexIsoMesh(uint32_t isoGridSubdivision, uint32_t keepNBiggestMeshes, bool discardInnerMeshes) :
+	mIsoGridSubdivision(isoGridSubdivision),
+	mKeepNBiggestMeshes(keepNBiggestMeshes),
+	mDiscardInnerMeshes(discardInnerMeshes),
+	mCellSize(0.0f),
+	mThickness(0.0f),
+	mOrigin(0.0f, 0.0f, 0.0f),
+	mNumX(0), mNumY(0), mNumZ(0),
+	mIsoValue(0.5f)
+{
+	if (mIsoGridSubdivision == 0)
+	{
+		APEX_INVALID_PARAMETER("isoGridSubdivision must be bigger than 0, setting it to 10");
+		mIsoGridSubdivision = 10;
+	}
+	mBound.setEmpty();
+}
+
+
+
+ApexIsoMesh::~ApexIsoMesh()
+{
+}
+
+
+
+void ApexIsoMesh::setBound(const PxBounds3& bound)
+{
+	mBound = bound;
+	mCellSize = (mBound.maximum - mBound.minimum).magnitude() / mIsoGridSubdivision;
+	if (mCellSize == 0.0f)
+	{
+		mCellSize = 1.0f;
+	}
+	mThickness = mCellSize * 1.5f;
+	PX_ASSERT(!mBound.isEmpty());
+	mBound.fattenFast(2.0f * mThickness);
+
+	mOrigin = mBound.minimum;
+	float invH = 1.0f / mCellSize;
+	mNumX = (int32_t)((mBound.maximum.x - mBound.minimum.x) * invH) + 1;
+	mNumY = (int32_t)((mBound.maximum.y - mBound.minimum.y) * invH) + 1;
+	mNumZ = (int32_t)((mBound.maximum.z - mBound.minimum.z) * invH) + 1;
+}
+
+
+
+void ApexIsoMesh::clear()
+{
+	mCellSize = 0.0f;
+	mThickness = 0.0f;
+	mOrigin = PxVec3(0.0f);
+	mNumX = mNumY = mNumZ = 0;
+	mBound.setEmpty();
+
+	clearTemp();
+
+	mIsoVertices.clear();
+	mIsoTriangles.clear();
+	mIsoEdges.clear();
+}
+
+
+
+void ApexIsoMesh::clearTemp()
+{
+	mGrid.clear();
+	mGrid.reset();
+}
+
+
+
+void ApexIsoMesh::addTriangle(const PxVec3& v0, const PxVec3& v1, const PxVec3& v2)
+{
+	int32_t num = mNumX * mNumY * mNumZ;
+	if (mGrid.size() != (uint32_t) num)
+	{
+		IsoCell cell;
+		cell.init();
+		mGrid.resize((uint32_t)num, cell);
+	}
+
+	PX_ASSERT(mThickness != 0.0f);
+
+	PxBounds3 bounds;
+	bounds.minimum = bounds.maximum = v0;
+	bounds.include(v1);
+	bounds.include(v2);
+	PX_ASSERT(!bounds.isEmpty());
+	bounds.fattenFast(mThickness);
+
+	float h = mCellSize;
+	float invH = 1.0f / h;
+	float invT = 1.0f / mThickness;
+
+	int32_t x0 = PxMax(0, (int32_t)((bounds.minimum.x - mOrigin.x) * invH));
+	int32_t x1 = PxMin(mNumX - 1, (int32_t)((bounds.maximum.x - mOrigin.x) * invH));
+	int32_t y0 = PxMax(0, (int32_t)((bounds.minimum.y - mOrigin.y) * invH));
+	int32_t y1 = PxMin(mNumY - 1, (int32_t)((bounds.maximum.y - mOrigin.y) * invH));
+	int32_t z0 = PxMax(0, (int32_t)((bounds.minimum.z - mOrigin.z) * invH));
+	int32_t z1 = PxMin(mNumZ - 1, (int32_t)((bounds.maximum.z - mOrigin.z) * invH));
+
+	for (int32_t xi = x0; xi <= x1; xi++)
+	{
+		PxVec3 pos;
+		pos.x = mOrigin.x + h * xi;
+		for (int32_t yi = y0; yi <= y1; yi++)
+		{
+			pos.y = mOrigin.y + h * yi;
+			for (int32_t zi = z0; zi <= z1; zi++)
+			{
+				pos.z = mOrigin.z + h * zi;
+				Triangle triangle(v0, v1, v2);
+				float dist = PxSqrt(APEX_pointTriangleSqrDst(triangle, pos));
+				if (dist > mThickness)
+				{
+					continue;
+				}
+
+				IsoCell& cell = cellAt(xi, yi, zi);
+				float density = 1.0f - dist * invT;
+				PX_ASSERT(density >= 0);
+				cell.density = PxMax(cell.density, density); ///< \todo, is this right?
+			}
+		}
+	}
+}
+
+
+
+bool ApexIsoMesh::update(IProgressListener* progressListener)
+{
+	HierarchicalProgressListener progress(100, progressListener);
+	progress.setSubtaskWork(90, "Generating first mesh");
+
+	if (generateMesh(&progress))
+	{
+
+		progress.completeSubtask();
+		progress.setSubtaskWork(5, "Finding Neighbors");
+
+		if (findNeighbors(&progress))
+		{
+
+			if (mKeepNBiggestMeshes > 0 || mDiscardInnerMeshes)
+			{
+				progress.completeSubtask();
+				progress.setSubtaskWork(3, "Removing layers");
+				removeLayers();
+				//	removeSide(2);
+			}
+			progress.completeSubtask();
+			progress.setSubtaskWork(2, "Removing Triangles and Vertices");
+
+			removeTrisAndVerts();
+		}
+	}
+	progress.completeSubtask();
+
+	return true;
+}
+
+
+
+void ApexIsoMesh::getTriangle(uint32_t index, uint32_t& v0, uint32_t& v1, uint32_t& v2) const
+{
+	PX_ASSERT(index < mIsoTriangles.size());
+	const IsoTriangle& t = mIsoTriangles[index];
+	v0 = (uint32_t)t.vertexNr[0];
+	v1 = (uint32_t)t.vertexNr[1];
+	v2 = (uint32_t)t.vertexNr[2];
+}
+
+
+
+bool ApexIsoMesh::generateMesh(IProgressListener* progressListener)
+{
+	mIsoVertices.clear();
+
+	int xi, yi, zi;
+	float h = mCellSize;
+	PxVec3 pos, vPos;
+
+	uint32_t maximum = (uint32_t)(mNumX * mNumY * mNumZ);
+	uint32_t progressCounter = 0;
+
+	HierarchicalProgressListener progress(100, progressListener);
+	progress.setSubtaskWork(80, "Generating Vertices");
+
+	// generate vertices
+	for (xi = 0; xi < mNumX; xi++)
+	{
+		pos.x = mOrigin.x + h * xi;
+		for (yi = 0; yi < mNumY; yi++)
+		{
+			pos.y = mOrigin.y + h * yi;
+			for (zi = 0; zi < mNumZ; zi++)
+			{
+
+				if ((progressCounter++ & 0xff) == 0)
+				{
+					const int32_t curr = ((xi * mNumY) + yi) * mNumZ + zi;
+					const int32_t percent = 100 * curr / (int32_t)maximum;
+					progress.setProgress(percent);
+				}
+
+				pos.z = mOrigin.z + h * zi;
+				IsoCell& cell = cellAt(xi, yi, zi);
+				float d  = cell.density;
+				if (xi < mNumX - 1)
+				{
+					float dx = cellAt(xi + 1, yi, zi).density;
+					if (interpolate(d, dx, pos, pos + PxVec3(h, 0.0f, 0.0f), vPos))
+					{
+						cell.vertNrX = (int32_t)mIsoVertices.size();
+						mIsoVertices.pushBack(vPos);
+					}
+				}
+				if (yi < mNumY - 1)
+				{
+					float dy = cellAt(xi, yi + 1, zi).density;
+					if (interpolate(d, dy, pos, pos + PxVec3(0.0f, h, 0.0f), vPos))
+					{
+						cell.vertNrY = (int32_t)mIsoVertices.size();
+						mIsoVertices.pushBack(vPos);
+					}
+				}
+				if (zi < mNumZ - 1)
+				{
+					float dz = cellAt(xi, yi, zi + 1).density;
+					if (interpolate(d, dz, pos, pos + PxVec3(0.0f, 0.0f, h), vPos))
+					{
+						cell.vertNrZ = (int32_t)mIsoVertices.size();
+						mIsoVertices.pushBack(vPos);
+					}
+				}
+			}
+		}
+	}
+
+	progress.completeSubtask();
+	progress.setSubtaskWork(20, "Generating Faces");
+	progressCounter = 0;
+
+	mIsoTriangles.clear();
+	// generate triangles
+	int edges[12];
+	IsoTriangle triangle;
+
+	for (xi = 0; xi < mNumX - 1; xi++)
+	{
+		pos.x = mOrigin.x + h * xi;
+		for (yi = 0; yi < mNumY - 1; yi++)
+		{
+			pos.y = mOrigin.y + h * yi;
+			for (zi = 0; zi < mNumZ - 1; zi++)
+			{
+
+				if ((progressCounter++ & 0xff) == 0)
+				{
+					const int32_t curr = ((xi * mNumY) + yi) * mNumZ + zi;
+					const int32_t percent = 100 * curr / (int32_t)maximum;
+					progress.setProgress(percent);
+				}
+				pos.z = mOrigin.z + h * zi;
+				int code = 0;
+				if (cellAt(xi,  yi,  zi).density > mIsoValue)
+				{
+					code |= 1;
+				}
+				if (cellAt(xi + 1, yi,  zi).density > mIsoValue)
+				{
+					code |= 2;
+				}
+				if (cellAt(xi + 1, yi + 1, zi).density > mIsoValue)
+				{
+					code |= 4;
+				}
+				if (cellAt(xi,  yi + 1, zi).density > mIsoValue)
+				{
+					code |= 8;
+				}
+				if (cellAt(xi,  yi,  zi + 1).density > mIsoValue)
+				{
+					code |= 16;
+				}
+				if (cellAt(xi + 1, yi,  zi + 1).density > mIsoValue)
+				{
+					code |= 32;
+				}
+				if (cellAt(xi + 1, yi + 1, zi + 1).density > mIsoValue)
+				{
+					code |= 64;
+				}
+				if (cellAt(xi,  yi + 1, zi + 1).density > mIsoValue)
+				{
+					code |= 128;
+				}
+				if (code == 0 || code == 255)
+				{
+					continue;
+				}
+
+				edges[ 0] = cellAt(xi,  yi,  zi).vertNrX;
+				edges[ 1] = cellAt(xi + 1, yi,  zi).vertNrY;
+				edges[ 2] = cellAt(xi,  yi + 1, zi).vertNrX;
+				edges[ 3] = cellAt(xi,  yi,  zi).vertNrY;
+
+				edges[ 4] = cellAt(xi,  yi,  zi + 1).vertNrX;
+				edges[ 5] = cellAt(xi + 1, yi,  zi + 1).vertNrY;
+				edges[ 6] = cellAt(xi,  yi + 1, zi + 1).vertNrX;
+				edges[ 7] = cellAt(xi,  yi,  zi + 1).vertNrY;
+
+				edges[ 8] = cellAt(xi,  yi,  zi).vertNrZ;
+				edges[ 9] = cellAt(xi + 1, yi,  zi).vertNrZ;
+				edges[10] = cellAt(xi + 1, yi + 1, zi).vertNrZ;
+				edges[11] = cellAt(xi,  yi + 1, zi).vertNrZ;
+
+				IsoCell& c = cellAt(xi, yi, zi);
+				c.firstTriangle = (int32_t)mIsoTriangles.size();
+
+				const int* v = MarchingCubes::triTable[code];
+				while (*v >= 0)
+				{
+					int v0 = edges[*v++];
+					PX_ASSERT(v0 >= 0);
+					int v1 = edges[*v++];
+					PX_ASSERT(v1 >= 0);
+					int v2 = edges[*v++];
+					PX_ASSERT(v2 >= 0);
+					triangle.set(v0, v1, v2, xi, yi, zi);
+					mIsoTriangles.pushBack(triangle);
+					c.numTriangles++;
+				}
+			}
+		}
+	}
+	progress.completeSubtask();
+
+	return true;
+}
+
+
+
+bool ApexIsoMesh::interpolate(float d0, float d1, const PxVec3& pos0, const PxVec3& pos1, PxVec3& pos)
+{
+	if ((d0 < mIsoValue && d1 < mIsoValue) || (d0 > mIsoValue && d1 > mIsoValue))
+	{
+		return false;
+	}
+
+	float s = (mIsoValue - d0) / (d1 - d0);
+	s = PxClamp(s, 0.01f, 0.99f);	// safety not to produce vertices at the same location
+	pos = pos0 * (1.0f - s) + pos1 * s;
+	return true;
+}
+
+
+
+bool ApexIsoMesh::findNeighbors(IProgressListener* progress)
+{
+	mIsoEdges.clear();
+	IsoEdge edge;
+
+	for (int32_t i = 0; i < (int32_t)mIsoTriangles.size(); i++)
+	{
+		IsoTriangle& t = mIsoTriangles[(uint32_t)i];
+		edge.set(t.vertexNr[0], t.vertexNr[1], i);
+		mIsoEdges.pushBack(edge);
+		edge.set(t.vertexNr[1], t.vertexNr[2], i);
+		mIsoEdges.pushBack(edge);
+		edge.set(t.vertexNr[2], t.vertexNr[0], i);
+		mIsoEdges.pushBack(edge);
+	}
+
+	progress->setProgress(30);
+
+	shdfnd::sort(mIsoEdges.begin(), mIsoEdges.size(), IsoEdge());
+
+	progress->setProgress(60);
+
+	uint32_t i = 0;
+	while (i < mIsoEdges.size())
+	{
+		uint32_t j = i + 1;
+		while (j < mIsoEdges.size() && mIsoEdges[j] == mIsoEdges[i])
+		{
+			j++;
+		}
+		if (j > i + 1)
+		{
+			mIsoTriangles[(uint32_t)mIsoEdges[i  ].triangleNr].addNeighbor(mIsoEdges[j - 1].triangleNr);
+			mIsoTriangles[(uint32_t)mIsoEdges[j - 1].triangleNr].addNeighbor(mIsoEdges[i  ].triangleNr);
+		}
+		i = j;
+	}
+
+	progress->setProgress(100);
+	return true;
+}
+
+struct GroupAndSize
+{
+	int32_t group;
+	uint32_t size;
+	bool deleteMesh;
+
+	bool operator()(const GroupAndSize& a, const GroupAndSize& b) const
+	{
+		return a.size > b.size;
+	}
+};
+
+struct TimeAndDot
+{
+	float time;
+	float dot;
+
+	bool operator()(const TimeAndDot& a, const TimeAndDot& b) const
+	{
+		return a.time > b.time;
+	}
+};
+
+void ApexIsoMesh::removeLayers()
+{
+	// mark regions
+	nvidia::Array<GroupAndSize> triangleGroups;
+
+	for (uint32_t i = 0; i < mIsoTriangles.size(); i++)
+	{
+		if (mIsoTriangles[i].groupNr >= 0)
+		{
+			continue;
+		}
+
+		GroupAndSize gas;
+		gas.size = 0;
+		gas.group = (int32_t)triangleGroups.size();
+		gas.deleteMesh = false;
+
+		gas.size = floodFill(i, (uint32_t)gas.group);
+
+		triangleGroups.pushBack(gas);
+	}
+
+	if (triangleGroups.size() == 0)
+	{
+		return;
+	}
+
+	// clear regions
+	if (mDiscardInnerMeshes)
+	{
+		nvidia::Array<TimeAndDot> raycastHits;
+		for (uint32_t group = 0; group < triangleGroups.size(); group++)
+		{
+			// see if this group is an inner mesh
+			raycastHits.clear();
+
+			const int32_t groupNumber = triangleGroups[group].group;
+
+			uint32_t start = 0;
+			const uint32_t numTriangles = mIsoTriangles.size();
+			for (uint32_t i = 0; i < numTriangles; i++)
+			{
+				if (mIsoTriangles[i].groupNr == groupNumber)
+				{
+					start = i;
+					break;
+				}
+			}
+
+			// raycast from the start triangle
+			const PxVec3 rayOrig =   (mIsoVertices[(uint32_t)mIsoTriangles[start].vertexNr[0]] 
+									+ mIsoVertices[(uint32_t)mIsoTriangles[start].vertexNr[1]] 
+									+ mIsoVertices[(uint32_t)mIsoTriangles[start].vertexNr[2]]) / 3.0f;
+			PxVec3 rayDir(1.0f, 1.0f, 1.0f);
+			rayDir.normalize(); // can really be anything.
+
+			// Find all ray hits
+			for (uint32_t i = start; i < numTriangles; i++)
+			{
+				if (mIsoTriangles[i].groupNr != groupNumber)
+				{
+					continue;
+				}
+
+				float t, u, v;
+				PxVec3 verts[3] =
+				{
+					mIsoVertices[(uint32_t)mIsoTriangles[i].vertexNr[0]],
+					mIsoVertices[(uint32_t)mIsoTriangles[i].vertexNr[1]],
+					mIsoVertices[(uint32_t)mIsoTriangles[i].vertexNr[2]],
+				};
+
+				if (APEX_RayTriangleIntersect(rayOrig, rayDir, verts[0], verts[1], verts[2], t, u, v))
+				{
+					TimeAndDot hit;
+					hit.time = t;
+
+					PxVec3 faceNormal = (verts[1] - verts[0]).cross(verts[2] - verts[0]);
+					faceNormal.normalize();
+
+					hit.dot = faceNormal.dot(rayDir);
+
+					raycastHits.pushBack(hit);
+				}
+			}
+
+			if (raycastHits.size() > 0)
+			{
+				shdfnd::sort(raycastHits.begin(), raycastHits.size(), TimeAndDot());
+
+				triangleGroups[group].deleteMesh = raycastHits[0].dot > 0.0f;
+			}
+		}
+	}
+
+	if (mKeepNBiggestMeshes > 0)
+	{
+		shdfnd::sort(triangleGroups.begin(), triangleGroups.size(), GroupAndSize());
+
+		for (uint32_t i = mKeepNBiggestMeshes; i < triangleGroups.size(); i++)
+		{
+			triangleGroups[i].deleteMesh = true;
+		}
+	}
+
+
+	for (uint32_t i = 0; i < triangleGroups.size(); i++)
+	{
+		if (!triangleGroups[i].deleteMesh)
+		{
+			continue;
+		}
+
+		const int32_t group = triangleGroups[i].group;
+
+		const uint32_t size = mIsoTriangles.size();
+		for (uint32_t j = 0; j < size; j++)
+		{
+			if (mIsoTriangles[j].groupNr == group)
+			{
+				mIsoTriangles[j].deleted = true;
+			}
+		}
+	}
+}
+
+
+
+uint32_t ApexIsoMesh::floodFill(uint32_t triangleNr, uint32_t groupNr)
+{
+	uint32_t numTriangles = 0;
+	nvidia::Array<uint32_t> queue;
+	queue.pushBack(triangleNr);
+
+	while (!queue.empty())
+	{
+		IsoTriangle& t = mIsoTriangles[queue.back()];
+		queue.popBack();
+		if (t.groupNr == int32_t(groupNr))
+		{
+			continue;
+		}
+
+		t.groupNr = (int32_t)groupNr;
+		numTriangles++;
+
+		int32_t adj = t.adjTriangles[0];
+		if (adj >= 0 && mIsoTriangles[(uint32_t)adj].groupNr < 0)
+		{
+			queue.pushBack((uint32_t)adj);
+		}
+		adj = t.adjTriangles[1];
+		if (adj >= 0 && mIsoTriangles[(uint32_t)adj].groupNr < 0)
+		{
+			queue.pushBack((uint32_t)adj);
+		}
+		adj = t.adjTriangles[2];
+		if (adj >= 0 && mIsoTriangles[(uint32_t)adj].groupNr < 0)
+		{
+			queue.pushBack((uint32_t)adj);
+		}
+	}
+
+	return numTriangles;
+}
+
+
+
+void ApexIsoMesh::removeTrisAndVerts()
+{
+	for (int32_t i = (int32_t)mIsoTriangles.size() - 1; i >= 0; i--)
+	{
+		if (mIsoTriangles[(uint32_t)i].deleted)
+		{
+			mIsoTriangles.replaceWithLast((uint32_t)i);
+		}
+	}
+
+	Array<int32_t> oldToNew;
+	Array<PxVec3> newVertices;
+
+	oldToNew.resize(mIsoVertices.size(), -1);
+
+	for (uint32_t i = 0; i < mIsoTriangles.size(); i++)
+	{
+		IsoTriangle& t = mIsoTriangles[i];
+		for (uint32_t j = 0; j < 3; j++)
+		{
+			uint32_t vNr = (uint32_t)t.vertexNr[j];
+			if (oldToNew[vNr] < 0)
+			{
+				oldToNew[vNr] = (int32_t)newVertices.size();
+				newVertices.pushBack(mIsoVertices[vNr]);
+			}
+			t.vertexNr[j] = oldToNew[vNr];
+		}
+	}
+
+	mIsoVertices.clear();
+	mIsoVertices.reserve(newVertices.size());
+
+	for (uint32_t i = 0; i < newVertices.size(); i++)
+	{
+		mIsoVertices.pushBack(newVertices[i]);
+	}
+}
+
+} // end namespace apex
+} // end namespace nvidia