Initial commit:

PhysX 3.4.0 Update @ 21294896
APEX 1.4.0 Update @ 21275617

[CL 21300167]

1 files changed, 797 insertions, 0 deletions

diff --git a/PhysX_3.4/Source/PhysXCooking/src/convex/ConvexHullBuilder.cpp b/PhysX_3.4/Source/PhysXCooking/src/convex/ConvexHullBuilder.cpp
new file mode 100644
index 00000000..3b9c3ac6
--- /dev/null
+++ b/PhysX_3.4/Source/PhysXCooking/src/convex/ConvexHullBuilder.cpp
@@ -0,0 +1,797 @@
+// 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/PxMemory.h"
+#include "EdgeList.h"
+#include "GuTriangle32.h"
+#include "GuConvexMesh.h"
+#include "PxCooking.h"
+#include "CookingUtils.h"
+#include "ConvexHullBuilder.h"
+#include "CmRadixSortBuffered.h"
+#include "MeshCleaner.h"
+#include "PsArray.h"
+#include "PsFoundation.h"
+#include "PsVecMath.h"
+
+
+// 7: added mHullDataFacesByVertices8
+// 8: added mEdges
+static const physx::PxU32 gVersion = 8;
+
+using namespace physx;
+using namespace Gu;
+using namespace Ps::aos;
+
+#define USE_PRECOMPUTED_HULL_PROJECTION
+
+//////////////////////////////////////////////////////////////////////////
+// default constructor 
+ConvexHullBuilder::ConvexHullBuilder(Gu::ConvexHullData* hull, const bool buildGRBData) : 
+	mHullDataHullVertices		(NULL),
+	mHullDataPolygons			(NULL),
+	mHullDataVertexData8		(NULL),
+	mHullDataFacesByEdges8		(NULL),
+	mHullDataFacesByVertices8	(NULL),
+	mHullDataFacesByAllEdges8	(NULL),
+	mEdgeData16					(NULL),
+	mEdges						(NULL),
+	mHull						(hull),
+	mBuildGRBData				(buildGRBData)
+{
+}
+
+//////////////////////////////////////////////////////////////////////////
+// default destructor
+ConvexHullBuilder::~ConvexHullBuilder()
+{
+	PX_DELETE_POD(mEdgeData16);
+	PX_DELETE_POD(mEdges);
+
+	PX_DELETE_POD(mHullDataHullVertices);
+	PX_DELETE_POD(mHullDataPolygons);
+	PX_DELETE_POD(mHullDataVertexData8);
+	PX_DELETE_POD(mHullDataFacesByEdges8);
+	PX_DELETE_POD(mHullDataFacesByVertices8);
+	PX_DELETE_POD(mHullDataFacesByAllEdges8);
+}
+
+//////////////////////////////////////////////////////////////////////////
+// initialize the convex hull
+// \param		nbVerts	[in] number of vertices used
+// \param		verts	[in] vertices array
+// \param		indices	[in] indices array
+// \param		nbPolygons	[in] number of polygons
+// \param		hullPolygons	[in] polygons array
+bool ConvexHullBuilder::init(PxU32 nbVerts, const PxVec3* verts, const PxU32* indices, const PxU32 nbIndices,
+	const PxU32 nbPolygons, const PxHullPolygon* hullPolygons, PxU32 gaussMapVertexLimit, bool doValidation, bool userPolygons)
+{
+	PX_ASSERT(indices);
+	PX_ASSERT(verts);
+	PX_ASSERT(hullPolygons);
+	PX_ASSERT(nbVerts);
+	PX_ASSERT(nbPolygons);
+
+	mHullDataHullVertices			= NULL;
+	mHullDataPolygons				= NULL;
+	mHullDataVertexData8			= NULL;
+	mHullDataFacesByEdges8			= NULL;
+	mHullDataFacesByVertices8		= NULL;
+	mHullDataFacesByAllEdges8		= NULL;
+
+	mEdges							= NULL;
+	mEdgeData16						= NULL;
+
+	mHull->mNbHullVertices			= Ps::to8(nbVerts);
+	// allocate additional vec3 for V4 safe load in VolumeInteration
+	mHullDataHullVertices			= reinterpret_cast<PxVec3*>(PX_ALLOC(sizeof(PxVec3) * mHull->mNbHullVertices + 1, "PxVec3"));
+	PxMemCopy(mHullDataHullVertices, verts, mHull->mNbHullVertices*sizeof(PxVec3));
+	
+	// Cleanup
+	mHull->mNbPolygons = 0;
+	PX_DELETE_POD(mHullDataVertexData8);
+	PX_FREE_AND_RESET(mHullDataPolygons);
+
+	if(nbPolygons>255)
+	{
+  		Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "ConvexHullBuilder::init: convex hull has more than 255 polygons!");
+		return false;
+	}
+
+	// Precompute hull polygon structures
+	mHull->mNbPolygons = Ps::to8(nbPolygons);
+	mHullDataPolygons = reinterpret_cast<Gu::HullPolygonData*>(PX_ALLOC(sizeof(Gu::HullPolygonData)*mHull->mNbPolygons, "Gu::HullPolygonData"));
+
+	mHullDataVertexData8 = PX_NEW(PxU8)[nbIndices];	
+	PxU8* dest = mHullDataVertexData8;
+	for(PxU32 i=0;i<nbPolygons;i++)
+	{
+		const PxHullPolygon& inPolygon = hullPolygons[i];
+		mHullDataPolygons[i].mVRef8 = PxU16(dest - mHullDataVertexData8);	// Setup link for current polygon
+
+		PxU32 numVerts = inPolygon.mNbVerts;
+		PX_ASSERT(numVerts>=3);			// Else something very wrong happened...
+		mHullDataPolygons[i].mNbVerts = Ps::to8(numVerts);
+
+		for (PxU32 j = 0; j < numVerts; j++)
+		{
+			dest[j] = Ps::to8(indices[inPolygon.mIndexBase + j]);
+		}
+
+		mHullDataPolygons[i].mPlane = PxPlane(inPolygon.mPlane[0],inPolygon.mPlane[1],inPolygon.mPlane[2],inPolygon.mPlane[3]);				
+
+		// Next one
+		dest += numVerts;
+	}
+
+	if(!calculateVertexMapTable(nbPolygons, userPolygons))
+		return false;
+
+	// moved create edge list here from save, copy. This is a part of the validation process and
+	// we need to create the edge list anyway
+	if (!createEdgeList(doValidation, nbIndices, mHull->mNbHullVertices > gaussMapVertexLimit ? true : false))
+		return false;
+		
+#ifdef USE_PRECOMPUTED_HULL_PROJECTION		
+	// Loop through polygons	
+	for (PxU32 j = 0; j < nbPolygons; j++)
+	{
+		// Precompute hull projection along local polygon normal
+		PxU32 NbVerts = mHull->mNbHullVertices;
+		const PxVec3* Verts = mHullDataHullVertices;
+		Gu::HullPolygonData& polygon = mHullDataPolygons[j];
+		PxReal min = PX_MAX_F32;
+		PxU8 minIndex = 0xff;
+		for (PxU8 i = 0; i < NbVerts; i++)
+		{
+			float dp = (*Verts++).dot(polygon.mPlane.n);
+			if (dp < min)
+			{
+				min = dp;
+				minIndex = i;
+			}
+		}
+		polygon.mMinIndex = minIndex;
+	}
+#endif
+	
+	if(doValidation)
+		return checkHullPolygons();
+	else
+		return true;
+}
+
+//////////////////////////////////////////////////////////////////////////
+// hull polygons check
+bool ConvexHullBuilder::checkHullPolygons() const
+{
+	const PxVec3* hullVerts = mHullDataHullVertices;
+	const PxU8* vertexData = mHullDataVertexData8;
+	Gu::HullPolygonData* hullPolygons = mHullDataPolygons;
+
+	// Check hull validity
+	if(!hullVerts || !hullPolygons)	
+		return false;
+
+	if(mHull->mNbPolygons<4)
+		return false;
+
+	PxVec3 max(-FLT_MAX,-FLT_MAX,-FLT_MAX);
+
+	PxVec3 hullMax = hullVerts[0];
+	PxVec3 hullMin = hullVerts[0];
+
+	for(PxU32 j=0;j<mHull->mNbHullVertices;j++)
+	{
+		const PxVec3& hullVert = hullVerts[j];
+		if(fabsf(hullVert.x) > max.x)
+			max.x = fabsf(hullVert.x);
+
+		if(fabsf(hullVert.y) > max.y)
+			max.y = fabsf(hullVert.y);
+
+		if(fabsf(hullVert.z) > max.z)
+			max.z = fabsf(hullVert.z);
+
+		if (hullVert.x > hullMax.x)
+		{
+			hullMax.x = hullVert.x;			
+		}
+		else if (hullVert.x < hullMin.x)
+		{
+			hullMin.x = hullVert.x;			
+		}
+
+		if (hullVert.y > hullMax.y)
+		{
+			hullMax.y = hullVert.y;			
+		}
+		else if (hullVert.y < hullMin.y)
+		{
+			hullMin.y = hullVert.y;			
+		}
+
+		if (hullVert.z > hullMax.z)
+		{
+			hullMax.z = hullVert.z;			
+		}
+		else if (hullVert.z < hullMin.z)
+		{
+			hullMin.z = hullVert.z;			
+		}
+	}
+
+	max += PxVec3(0.02f,0.02f,0.02f);	
+
+	PxVec3 testVectors[8];
+	bool	foundPlane[8];
+	for (PxU32 i = 0; i < 8; i++)
+	{
+		foundPlane[i] = false;
+	}
+
+	testVectors[0] = PxVec3(max.x,max.y,max.z);
+	testVectors[1] = PxVec3(max.x,-max.y,-max.z);
+	testVectors[2] = PxVec3(max.x,max.y,-max.z);
+	testVectors[3] = PxVec3(max.x,-max.y,max.z);
+	testVectors[4] = PxVec3(-max.x,max.y,max.z);
+	testVectors[5] = PxVec3(-max.x,-max.y,max.z);
+	testVectors[6] = PxVec3(-max.x,max.y,-max.z);
+	testVectors[7] = PxVec3(-max.x,-max.y,-max.z);
+
+
+	// Extra convex hull validity check. This is less aggressive than previous convex decomposer!
+	// Loop through polygons
+	for(PxU32 i=0;i<mHull->mNbPolygons;i++)
+	{
+		const PxPlane& P = hullPolygons[i].mPlane;
+
+		for (PxU32 k = 0; k < 8; k++)
+		{
+			if(!foundPlane[k])
+			{
+				const float d = P.distance(testVectors[k]);
+				if(d >= 0)
+				{
+					foundPlane[k] = true;
+				}
+			}
+		}
+
+		// Test hull vertices against polygon plane
+		// compute the test epsilon the same way we construct the hull, verts are considered coplanar within this epsilon	
+		const float planeTolerance = 0.002f;
+		const float testEpsilon = PxMax(planeTolerance * (PxMax(PxAbs(hullMax.x), PxAbs(hullMin.x)) +
+			PxMax(PxAbs(hullMax.y), PxAbs(hullMin.y)) +
+			PxMax(PxAbs(hullMax.z), PxAbs(hullMin.z))), planeTolerance);
+
+		for(PxU32 j=0;j<mHull->mNbHullVertices;j++)
+		{
+			// Don't test vertex if it belongs to plane (to prevent numerical issues)
+			PxU32 nb = hullPolygons[i].mNbVerts;
+			bool discard=false;
+			for(PxU32 k=0;k<nb;k++)
+			{
+				if(vertexData[hullPolygons[i].mVRef8+k]==PxU8(j))
+				{
+					discard = true;
+					break;
+				}
+			}
+
+			if(!discard)
+			{
+				const float d = P.distance(hullVerts[j]);
+//					if(d>0.0001f)					
+				//if(d>0.02f)
+				if(d > testEpsilon)
+				{					
+					Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "Gu::ConvexMesh::checkHullPolygons: Some hull vertices seems to be too far from hull planes.");
+					return false;
+				}
+			}
+		}
+	}
+
+	for (PxU32 i = 0; i < 8; i++)
+	{
+		if(!foundPlane[i])
+		{
+			Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "Gu::ConvexMesh::checkHullPolygons: Hull seems to have opened volume or do (some) faces have reversed winding?");			
+			return false;
+		}
+	}
+	
+	return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+*	Computes the center of the hull. It should be inside it !
+*	\param		center	[out] hull center
+*	\return		true if success
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool ConvexHullBuilder::computeGeomCenter(PxVec3& center, PxU32 numFaces, HullTriangleData* faces) const
+{
+	// Checkings
+	const PxVec3* PX_RESTRICT hullVerts = mHullDataHullVertices;
+	if (!mHull->mNbHullVertices || !hullVerts)	return false;
+
+	// Use the topological method
+	float totalArea = 0.0f;
+	center = PxVec3(0);
+	for (PxU32 i = 0; i < numFaces; i++)
+	{
+		Gu::TriangleT<PxU32> curTri(faces[i].mRef[0], faces[i].mRef[1], faces[i].mRef[2]);
+		const float area = curTri.area(hullVerts);
+		PxVec3 curCenter;	curTri.center(hullVerts, curCenter);
+		center += area * curCenter;
+		totalArea += area;
+	}
+	center /= totalArea;
+
+	return true;
+}
+
+//////////////////////////////////////////////////////////////////////////
+// hull data store
+PX_COMPILE_TIME_ASSERT(sizeof(Gu::EdgeDescData)==8);
+PX_COMPILE_TIME_ASSERT(sizeof(Gu::EdgeData)==8);
+bool ConvexHullBuilder::save(PxOutputStream& stream, bool platformMismatch) const
+{
+	// Export header
+	if(!WriteHeader('C', 'L', 'H', 'L', gVersion, platformMismatch, stream))
+		return false;
+
+	// Export header
+	if(!WriteHeader('C', 'V', 'H', 'L', gVersion, platformMismatch, stream))
+		return false;
+
+	// Export figures
+
+	//embed grb flag into mNbEdges
+	PxU16 hasGRBData = PxU16(mBuildGRBData);
+	hasGRBData = PxU16(hasGRBData << 15);
+	PX_ASSERT(mHull->mNbEdges <( (1 << 15) - 1));
+	const PxU16 nbEdges = PxU16(mHull->mNbEdges | hasGRBData);
+	writeDword(mHull->mNbHullVertices, platformMismatch, stream);
+	writeDword(nbEdges, platformMismatch, stream);
+	writeDword(computeNbPolygons(), platformMismatch, stream);	// Use accessor to lazy-build
+	PxU32 nb=0;
+	for(PxU32 i=0;i<mHull->mNbPolygons;i++)
+		nb += mHullDataPolygons[i].mNbVerts;
+	writeDword(nb, platformMismatch, stream);
+
+	// Export triangles
+
+	writeFloatBuffer(&mHullDataHullVertices->x, PxU32(mHull->mNbHullVertices*3), platformMismatch, stream);
+
+	// Export polygons
+	// TODO: allow lazy-evaluation
+	// We can't really store the buffer in one run anymore!
+	for(PxU32 i=0;i<mHull->mNbPolygons;i++)
+	{
+		Gu::HullPolygonData tmpCopy = mHullDataPolygons[i];
+		if(platformMismatch)
+			flipData(tmpCopy);
+
+		stream.write(&tmpCopy, sizeof(Gu::HullPolygonData));
+	}
+
+	// PT: why not storeBuffer here?
+	for(PxU32 i=0;i<nb;i++)
+		stream.write(&mHullDataVertexData8[i], sizeof(PxU8));
+
+	stream.write(mHullDataFacesByEdges8, PxU32(mHull->mNbEdges*2));
+	stream.write(mHullDataFacesByVertices8, PxU32(mHull->mNbHullVertices*3));
+
+	if (mBuildGRBData)
+		writeWordBuffer(mEdges, PxU32(mHull->mNbEdges * 2), platformMismatch, stream);
+
+	return true;
+}
+
+//////////////////////////////////////////////////////////////////////////
+bool ConvexHullBuilder::copy(ConvexHullData& hullData)
+{
+	// set the numbers
+	hullData.mNbHullVertices = mHull->mNbHullVertices;
+	hullData.mNbEdges = mHull->mNbEdges;
+	hullData.mNbPolygons = Ps::to8(computeNbPolygons());
+	PxU32 nb = 0;
+	for (PxU32 i = 0; i < mHull->mNbPolygons; i++)
+		nb += mHullDataPolygons[i].mNbVerts;
+
+	PxU32 bytesNeeded = Gu::computeBufferSize(hullData, nb);
+
+	// allocate the memory first.	
+	void* dataMemory = PX_ALLOC(bytesNeeded, "ConvexHullData data");
+
+	PxU8* address = reinterpret_cast<PxU8*>(dataMemory);
+
+	// set data pointers
+	hullData.mPolygons = reinterpret_cast<Gu::HullPolygonData*>(address);	address += sizeof(Gu::HullPolygonData) * hullData.mNbPolygons;
+	PxVec3* dataHullVertices = reinterpret_cast<PxVec3*>(address);			address += sizeof(PxVec3) * hullData.mNbHullVertices;
+	PxU8* dataFacesByEdges8 = reinterpret_cast<PxU8*>(address);				address += sizeof(PxU8) * hullData.mNbEdges * 2;
+	PxU8* dataFacesByVertices8 = reinterpret_cast<PxU8*>(address);			address += sizeof(PxU8) * hullData.mNbHullVertices * 3;
+	PxU16* dataEdges = reinterpret_cast<PxU16*>(address); 					address += hullData.mNbEdges.isBitSet() ? sizeof(PxU16) *hullData.mNbEdges * 2 : 0;
+	PxU8* dataVertexData8 = reinterpret_cast<PxU8*>(address);				address += sizeof(PxU8) * nb;	// PT: leave that one last, so that we don't need to serialize "Nb"
+
+	PX_ASSERT(!(size_t(dataHullVertices) % sizeof(PxReal)));
+	PX_ASSERT(!(size_t(hullData.mPolygons) % sizeof(PxReal)));
+	PX_ASSERT(size_t(address) <= size_t(dataMemory) + bytesNeeded);
+
+	PX_ASSERT(mHullDataHullVertices);
+	PX_ASSERT(mHullDataPolygons);
+	PX_ASSERT(mHullDataVertexData8);
+	PX_ASSERT(mHullDataFacesByEdges8);
+	PX_ASSERT(mHullDataFacesByVertices8);
+
+	// copy the data
+	PxMemCopy(dataHullVertices, &mHullDataHullVertices->x, PxU32(mHull->mNbHullVertices * 3)*sizeof(float));
+	PxMemCopy(hullData.mPolygons, mHullDataPolygons , hullData.mNbPolygons*sizeof(Gu::HullPolygonData));
+	PxMemCopy(dataVertexData8, mHullDataVertexData8, nb);
+	PxMemCopy(dataFacesByEdges8,mHullDataFacesByEdges8, PxU32(mHull->mNbEdges * 2));
+	if (hullData.mNbEdges.isBitSet())
+		PxMemCopy(dataEdges, mEdges, PxU32(mHull->mNbEdges * 2) * sizeof(PxU16));
+	PxMemCopy(dataFacesByVertices8, mHullDataFacesByVertices8, PxU32(mHull->mNbHullVertices * 3));	
+	return true;
+}
+
+//////////////////////////////////////////////////////////////////////////
+// calculate vertex map table
+bool ConvexHullBuilder::calculateVertexMapTable(PxU32 nbPolygons, bool userPolygons)
+{
+	mHullDataFacesByVertices8 = PX_NEW(PxU8)[mHull->mNbHullVertices*3u];
+	PxU8 vertexMarker[256];
+	PxMemSet(vertexMarker, 0, mHull->mNbHullVertices);
+
+	for (PxU32 i = 0; i < nbPolygons; i++)
+	{
+		const Gu::HullPolygonData& polygon = mHullDataPolygons[i];
+		for (PxU32 k = 0; k < polygon.mNbVerts; ++k)
+		{
+			const PxU8 index = mHullDataVertexData8[polygon.mVRef8 + k];
+			if (vertexMarker[index] < 3)
+			{
+				//Found a polygon
+				mHullDataFacesByVertices8[index*3 + vertexMarker[index]++] = Ps::to8(i);
+			}
+		}
+	}
+
+	bool noPlaneShift = false;
+	for (PxU32 i = 0; i < mHull->mNbHullVertices; ++i)
+	{
+		if(vertexMarker[i] != 3)
+			noPlaneShift = true;
+	}
+
+	if (noPlaneShift)
+	{
+		//PCM will use the original shape, which means it will have a huge performance drop
+		if (!userPolygons)
+			Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "ConvexHullBuilder: convex hull does not have vertex-to-face info! Try to use different convex mesh cooking settings.");
+		else
+			Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "ConvexHullBuilder: convex hull does not have vertex-to-face info! Some of the vertices have less than 3 neighbor polygons. The vertex is most likely inside a polygon or on an edge between 2 polygons, please remove those vertices.");
+		for (PxU32 i = 0; i < mHull->mNbHullVertices; ++i)
+		{
+			mHullDataFacesByVertices8[i * 3 + 0] = 0xFF;
+			mHullDataFacesByVertices8[i * 3 + 1] = 0xFF;
+			mHullDataFacesByVertices8[i * 3 + 2] = 0xFF;
+		}
+		return false;
+	}
+
+	return true;
+}
+
+
+//////////////////////////////////////////////////////////////////////////
+// create edge list
+bool ConvexHullBuilder::createEdgeList(bool doValidation, PxU32 nbEdges, bool prepareBigHullData)
+{
+	// Code below could be greatly simplified if we assume manifold meshes!
+
+	//feodorb: ok, let's assume manifold meshes, since the code before this change 
+	//would fail on non-maniflold meshes anyways
+
+	// We need the adjacency graph for hull polygons, similar to what we have for triangles.
+	// - sort the polygon edges and walk them in order
+	// - each edge should appear exactly twice since a convex is a manifold mesh without boundary edges
+	// - the polygon index is implicit when we walk the sorted list => get the 2 polygons back and update adjacency graph
+	//
+	// Two possible structures:
+	// - polygon to edges: needed for local search (actually: polygon to polygons)
+	// - edge to polygons: needed to compute edge normals on-the-fly
+
+	// Below is largely copied from the edge-list code
+
+	// Polygon to edges:
+	//
+	// We're dealing with convex polygons made of N vertices, defining N edges. For each edge we want the edge in
+	// an edge array.
+	//
+	// Edges to polygon:
+	//
+	// For each edge in the array, we want two polygon indices - ie an edge.
+
+	// 0) Compute the total size needed for "polygon to edges"
+	const PxU32 nbPolygons = mHull->mNbPolygons;
+	PxU32 nbEdgesUnshared = nbEdges;
+
+	// in a manifold mesh, each edge is repeated exactly twice as it shares exactly 2 faces
+	if (nbEdgesUnshared % 2 != 0)
+	{
+		Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "Cooking::cookConvexMesh: non-manifold mesh cannot be used, invalid mesh!");
+		return false;
+	}
+
+	if (prepareBigHullData)
+	{
+		mHullDataFacesByAllEdges8 = PX_NEW(PxU8)[nbEdges * 2];
+	}
+
+	// 1) Get some bytes: I need one EdgesRefs for each face, and some temp buffers	
+
+	// Face indices by edge indices. First face is the one where the edge is ordered from tail to head.
+	PX_DELETE_POD(mHullDataFacesByEdges8);
+	mHullDataFacesByEdges8 = PX_NEW(PxU8)[nbEdgesUnshared];
+
+	PxU32* tempBuffer = PX_NEW_TEMP(PxU32)[nbEdgesUnshared*8];	// Temp storage
+	PxU32* bufferAdd = tempBuffer;
+	PxU32*	PX_RESTRICT vRefs0		= tempBuffer; tempBuffer += nbEdgesUnshared;
+	PxU32*	PX_RESTRICT vRefs1		= tempBuffer; tempBuffer += nbEdgesUnshared;
+	PxU32*	polyIndex	= tempBuffer; tempBuffer += nbEdgesUnshared;
+	PxU32*	vertexIndex	= tempBuffer; tempBuffer += nbEdgesUnshared;
+	PxU32*	polyIndex2 = tempBuffer; tempBuffer += nbEdgesUnshared;
+	PxU32*	vertexIndex2 = tempBuffer; tempBuffer += nbEdgesUnshared;
+	PxU32*	edgeIndex = tempBuffer; tempBuffer += nbEdgesUnshared;
+	PxU32*	edgeData = tempBuffer; tempBuffer += nbEdgesUnshared;	
+
+	// TODO avoroshilov: use the same "tempBuffer"
+	bool* flippedVRefs = PX_NEW_TEMP(bool)[nbEdgesUnshared];	// Temp storage
+
+	PxU32* run0 = vRefs0;
+	PxU32* run1 = vRefs1;
+	PxU32* run2 = polyIndex;
+	PxU32* run3 = vertexIndex;
+	bool* run4 = flippedVRefs;
+
+	// 2) Create a full redundant list of edges	
+	PxU32 edgeCounter = 0;
+	for(PxU32 i=0;i<nbPolygons;i++)
+	{
+		PxU32 nbVerts = mHullDataPolygons[i].mNbVerts;
+		const PxU8* PX_RESTRICT Data = mHullDataVertexData8 + mHullDataPolygons[i].mVRef8;
+
+		// Loop through polygon vertices
+		for(PxU32 j=0;j<nbVerts;j++)
+		{
+			PxU32 vRef0 = Data[j];
+			PxU32 vRef1 = Data[(j+1)%nbVerts];
+			bool flipped = vRef0>vRef1;
+
+			if (flipped)
+				physx::shdfnd::swap(vRef0, vRef1);
+
+			*run0++ = vRef0;
+			*run1++ = vRef1;
+			*run2++ = i;
+			*run3++ = j;
+			*run4++ = flipped;
+			edgeData[edgeCounter] = edgeCounter;
+			edgeCounter++;
+		}
+	}
+	PX_ASSERT(PxU32(run0-vRefs0)==nbEdgesUnshared);
+	PX_ASSERT(PxU32(run1-vRefs1)==nbEdgesUnshared);
+
+	// 3) Sort the list according to both keys (VRefs0 and VRefs1)
+	Cm::RadixSortBuffered sorter;
+	const PxU32* PX_RESTRICT sorted = sorter.Sort(vRefs1, nbEdgesUnshared,Cm::RADIX_UNSIGNED).Sort(vRefs0, nbEdgesUnshared,Cm::RADIX_UNSIGNED).GetRanks();
+
+	PX_DELETE_POD(mEdges);
+	// Edges by their tail and head VRefs. NbEdgesUnshared == nbEdges * 2
+	// mEdges[edgeIdx*2 + 0] = tailVref, mEdges[edgeIdx*2 + 1] = headVref
+	// Tails and heads should be consistent with face refs, so that the edge is given in the order of
+	// his first face and opposite to the order of his second face
+	mEdges = PX_NEW(PxU16)[nbEdgesUnshared];
+
+	PX_DELETE_POD(mEdgeData16);
+	// Face to edge mapping
+	mEdgeData16 = PX_NEW(PxU16)[nbEdgesUnshared];
+
+	// TODO avoroshilov: remove this comment
+	//mHull->mNbEdges = Ps::to16(nbEdgesUnshared / 2);							// #non-redundant edges
+	
+	mHull->mNbEdges = 0;												// #non-redundant edges
+
+	// A.B. Comment out the early exit temporary since we need to precompute the additonal edge data for GPU
+	//if (!doValidation)
+	//{
+	//	// TODO avoroshilov: this codepath is not supported
+
+	//	for (PxU32 i = 0; i < nbEdgesUnshared; i = i + 2)
+	//	{
+	//		const PxU32 sortedIndex = sorted[i];							// Between 0 and Nb
+	//		const PxU32 nextSortedIndex = sorted[i + 1];							// Between 0 and Nb
+	//		const PxU32 polyID = polyIndex[sortedIndex];					// Poly index
+	//		const PxU32 nextPolyID = polyIndex[nextSortedIndex];					// Poly index
+	//		
+	//		mHullDataFacesByEdges8[(mHull->mNbEdges) * 2] = Ps::to8(polyID);
+	//		mHullDataFacesByEdges8[(mHull->mNbEdges) * 2 + 1] = Ps::to8(nextPolyID);
+
+	//		// store the full edge data for later use in big convex hull valencies computation			
+	//		if(mHullDataFacesByAllEdges8)
+	//		{
+	//			mHullDataFacesByAllEdges8[edgeData[sortedIndex] * 2] = Ps::to8(polyID);
+	//			mHullDataFacesByAllEdges8[edgeData[sortedIndex] * 2 + 1] = Ps::to8(nextPolyID);
+
+	//			mHullDataFacesByAllEdges8[edgeData[nextSortedIndex] * 2] = Ps::to8(polyID);
+	//			mHullDataFacesByAllEdges8[edgeData[nextSortedIndex] * 2 + 1] = Ps::to8(nextPolyID);
+	//		}
+	//		mHull->mNbEdges++;
+	//	}
+
+	//	PX_DELETE_POD(bufferAdd);
+	//	return true;
+	//}
+
+	// 4) Loop through all possible edges
+	// - clean edges list by removing redundant edges
+	// - create EdgesRef list	
+	//	mNbFaces = nbFaces;
+
+	// TODO avoroshilov:
+	PxU32 numFacesPerEdgeVerificationCounter = 0;
+	
+	PxU16* edgeVertOutput = mEdges;
+
+	PxU32 previousRef0 = PX_INVALID_U32;
+	PxU32 previousRef1 = PX_INVALID_U32;
+	PxU32 previousIndex = PX_INVALID_U32;
+	PxU32 previousPolyId = PX_INVALID_U32;
+
+	PxU16 nbHullEdges = 0;
+	for (PxU32 i = 0; i < nbEdgesUnshared; i++)
+	{
+		const PxU32 sortedIndex = sorted[i];							// Between 0 and Nb
+		const PxU32 polyID = polyIndex[sortedIndex];					// Poly index
+		const PxU32 vertexID = vertexIndex[sortedIndex];				// Poly index
+		PxU32 sortedRef0 = vRefs0[sortedIndex];				// (SortedRef0, SortedRef1) is the sorted edge
+		PxU32 sortedRef1 = vRefs1[sortedIndex];
+		bool flipped = flippedVRefs[sortedIndex];
+
+		if (sortedRef0 != previousRef0 || sortedRef1 != previousRef1)
+		{
+			// TODO avoroshilov: remove this?
+			if (i != 0 && numFacesPerEdgeVerificationCounter != 1)
+			{
+				Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "Cooking::cookConvexMesh: non-manifold mesh cannot be used, invalid mesh!");
+				return false;
+			}
+			numFacesPerEdgeVerificationCounter = 0;
+
+			// ### TODO: change this in edge list as well
+			previousRef0 = sortedRef0;
+			previousRef1 = sortedRef1;
+			previousPolyId = polyID;
+
+			//feodorb:restore the original order of VRefs (tail and head)
+			if (flipped)
+				physx::shdfnd::swap(sortedRef0, sortedRef1);
+
+			*edgeVertOutput++ = Ps::to16(sortedRef0);
+			*edgeVertOutput++ = Ps::to16(sortedRef1);
+
+			nbHullEdges++;
+		}
+		else
+		{
+			mHullDataFacesByEdges8[(nbHullEdges - 1) * 2] = Ps::to8(previousPolyId);
+			mHullDataFacesByEdges8[(nbHullEdges - 1) * 2 + 1] = Ps::to8(polyID);
+
+			++numFacesPerEdgeVerificationCounter;
+		}
+
+		mEdgeData16[mHullDataPolygons[polyID].mVRef8 + vertexID] = Ps::to16(i / 2);
+
+		if (mHullDataFacesByAllEdges8)
+		{
+			if (previousIndex != PX_INVALID_U32)
+			{
+				// store the full edge data for later use in big convex hull valencies computation			
+				mHullDataFacesByAllEdges8[edgeData[sortedIndex] * 2] = Ps::to8(polyID);
+				mHullDataFacesByAllEdges8[edgeData[sortedIndex] * 2 + 1] = Ps::to8(polyIndex[previousIndex]);
+
+				mHullDataFacesByAllEdges8[edgeData[previousIndex] * 2] = Ps::to8(polyID);
+				mHullDataFacesByAllEdges8[edgeData[previousIndex] * 2 + 1] = Ps::to8(polyIndex[previousIndex]);
+				previousIndex = PX_INVALID_U32;
+			}
+			else
+			{
+				previousIndex = sortedIndex;
+			}
+		}
+		// Create mEdgesRef on the fly
+
+		polyIndex2[i] = polyID;
+		vertexIndex2[i] = vertexID;
+		edgeIndex[i] = PxU32(nbHullEdges - 1);
+	}
+
+	mHull->mNbEdges = nbHullEdges;
+
+	//////////////////////
+
+	// 2) Get some bytes: one Pair structure / edge	
+	// create this structure only for validation purpose
+	// 3) Create Counters, ie compute the #faces sharing each edge
+	if(doValidation)
+	{
+		//
+		sorted = sorter.Sort(vertexIndex2, nbEdgesUnshared, Cm::RADIX_UNSIGNED).Sort(polyIndex2, nbEdgesUnshared, Cm::RADIX_UNSIGNED).GetRanks();
+
+		for (PxU32 i = 0; i < nbEdgesUnshared; i++)	edgeData[i] = edgeIndex[sorted[i]];
+
+		Gu::EdgeDescData* edgeToTriangles = PX_NEW(Gu::EdgeDescData)[PxU16(mHull->mNbEdges)];
+		PxMemZero(edgeToTriangles, sizeof(Gu::EdgeDescData)*mHull->mNbEdges);
+
+		PxU32* data = edgeData;
+		for(PxU32 i=0;i<nbEdgesUnshared;i++)	// <= maybe not the same Nb
+		{
+			edgeToTriangles[*data++].Count++;
+		}
+
+		// if we don't have a manifold mesh, this can fail... but the runtime would assert in any case
+		for (PxU32 i = 0; i < mHull->mNbEdges; i++)
+		{
+			if (edgeToTriangles[i].Count != 2)
+			{
+				Ps::getFoundation().error(PxErrorCode::eINTERNAL_ERROR, __FILE__, __LINE__, "Cooking::cookConvexMesh: non-manifold mesh cannot be used, invalid mesh!");
+				return false;
+			}
+		}
+		PX_DELETE_POD(edgeToTriangles);
+	}
+
+	// ### free temp ram
+	PX_DELETE_POD(bufferAdd);
+
+	// TODO avoroshilov: use the same "tempBuffer"
+	PX_DELETE_POD(flippedVRefs);
+
+	return true;
+}
+