A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
// SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0
#include "foundation/PxMemory.h"
#include "cooking/PxCooking.h"
#include "GuEdgeList.h"
#include "GuTriangle.h"
#include "GuConvexMesh.h"
#include "GuMeshCleaner.h"
#include "GuCookingConvexHullBuilder.h"
#include "GuCookingConvexHullLib.h"
#include "foundation/PxArray.h"
#include "foundation/PxVecMath.h"
#include "CmRadixSort.h"
// PT: TODO: To refactor/revisit
// Original implementation derived from Pierre Terdiman's ICE framework (https://www.codercorner.com/Ice.htm)
// 7: added mHullDataFacesByVertices8
// 8: added mEdges
// 9: removed duplicite 'C', 'V', 'H', 'L' header
static const physx::PxU32 gVersion = 9;
using namespace physx;
using namespace Gu;
using namespace Cm;
using namespace aos;
#define USE_PRECOMPUTED_HULL_PROJECTION
///////////////////////////////////////////////////////////////////////////////
PX_IMPLEMENT_OUTPUT_ERROR
///////////////////////////////////////////////////////////////////////////////
// default constructor
ConvexHullBuilder::ConvexHullBuilder(ConvexHullData* hull, const bool buildGRBData) :
mHullDataHullVertices (NULL),
mHullDataPolygons (NULL),
mHullDataVertexData8 (NULL),
mHullDataFacesByEdges8 (NULL),
mHullDataFacesByVertices8 (NULL),
mEdgeData16 (NULL),
mEdges (NULL),
mHull (hull),
mBuildGRBData (buildGRBData)
{
}
//////////////////////////////////////////////////////////////////////////
// default destructor
ConvexHullBuilder::~ConvexHullBuilder()
{
PX_FREE(mEdgeData16);
PX_FREE(mEdges);
PX_FREE(mHullDataHullVertices);
PX_FREE(mHullDataPolygons);
PX_FREE(mHullDataVertexData8);
PX_FREE(mHullDataFacesByEdges8);
PX_FREE(mHullDataFacesByVertices8);
}
//////////////////////////////////////////////////////////////////////////
// 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
// \param doValidation [in] specifies whether we should run the validation code
// \param hullLib [in] if hullLib is provided, we can reuse the hull create data, hulllib is NULL in case of user provided polygons
bool ConvexHullBuilder::init(PxU32 nbVerts, const PxVec3* verts, const PxU32* indices, const PxU32 nbIndices,
const PxU32 nbPolygons, const PxHullPolygon* hullPolygons, bool doValidation, ConvexHullLib* hullLib)
{
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;
mEdges = NULL;
mEdgeData16 = NULL;
mHull->mNbHullVertices = PxTo8(nbVerts);
// allocate additional vec3 for V4 safe load in VolumeInteration
mHullDataHullVertices = PX_ALLOCATE(PxVec3, (mHull->mNbHullVertices + 1), "PxVec3");
PxMemCopy(mHullDataHullVertices, verts, mHull->mNbHullVertices*sizeof(PxVec3));
// Cleanup
mHull->mNbPolygons = 0;
PX_FREE(mHullDataVertexData8);
PX_FREE(mHullDataPolygons);
if(nbPolygons>255)
return outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "ConvexHullBuilder::init: convex hull has more than 255 polygons!");
// Precompute hull polygon structures
mHull->mNbPolygons = PxTo8(nbPolygons);
mHullDataPolygons = PX_ALLOCATE(HullPolygonData, mHull->mNbPolygons, "Gu::HullPolygonData");
mHullDataVertexData8 = PX_ALLOCATE(PxU8, nbIndices, "mHullDataVertexData8");
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 = PxTo8(numVerts);
for (PxU32 j = 0; j < numVerts; j++)
{
dest[j] = PxTo8(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, (hullLib != NULL) ? false : true))
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(!hullLib || !hullLib->createEdgeList(nbIndices, mHullDataVertexData8, &mHullDataFacesByEdges8, &mEdgeData16, &mEdges))
{
if (!createEdgeList(doValidation, nbIndices))
return false;
}
else
{
mHull->mNbEdges = PxU16(nbIndices/2);
}
#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;
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;
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;
}
}
// compute the test epsilon the same way we construct the hull, verts are considered coplanar within this epsilon
const float planeTolerance = 0.02f;
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);
max += PxVec3(testEpsilon, testEpsilon, testEpsilon);
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
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)
return outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "Gu::ConvexMesh::checkHullPolygons: Some hull vertices seems to be too far from hull planes.");
}
}
}
for (PxU32 i = 0; i < 8; i++)
{
if(!foundPlane[i])
return outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "Gu::ConvexMesh::checkHullPolygons: Hull seems to have opened volume or do (some) faces have reversed winding?");
}
return true;
}
//////////////////////////////////////////////////////////////////////////
// hull data store
PX_COMPILE_TIME_ASSERT(sizeof(EdgeDescData)==8);
PX_COMPILE_TIME_ASSERT(sizeof(EdgeData)==8);
bool ConvexHullBuilder::save(PxOutputStream& stream, bool platformMismatch) const
{
// Export header
if(!WriteHeader('C', 'L', '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++)
{
HullPolygonData tmpCopy = mHullDataPolygons[i];
if(platformMismatch)
flipData(tmpCopy);
stream.write(&tmpCopy, sizeof(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, PxU32& mNb)
{
// set the numbers
hullData.mNbHullVertices = mHull->mNbHullVertices;
PxU16 hasGRBData = PxU16(mBuildGRBData);
hasGRBData = PxU16(hasGRBData << 15);
PX_ASSERT(mHull->mNbEdges <((1 << 15) - 1));
hullData.mNbEdges = PxU16(mHull->mNbEdges | hasGRBData);
hullData.mNbPolygons = PxTo8(computeNbPolygons());
PxU32 nb = 0;
for (PxU32 i = 0; i < mHull->mNbPolygons; i++)
nb += mHullDataPolygons[i].mNbVerts;
mNb = nb;
PxU32 bytesNeeded = 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<HullPolygonData*>(address); address += sizeof(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(HullPolygonData));
PxMemCopy(dataVertexData8, mHullDataVertexData8, nb);
PxMemCopy(dataFacesByEdges8,mHullDataFacesByEdges8, PxU32(mHull->mNbEdges * 2));
if (mBuildGRBData)
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_ALLOCATE(PxU8, mHull->mNbHullVertices*3u, "mHullDataFacesByVertices8");
PxU8 vertexMarker[256];
PxMemSet(vertexMarker, 0, mHull->mNbHullVertices);
for (PxU32 i = 0; i < nbPolygons; i++)
{
const 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]++] = PxTo8(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)
outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "ConvexHullBuilder: convex hull does not have vertex-to-face info! Try to use different convex mesh cooking settings.");
else
outputError<PxErrorCode::eINTERNAL_ERROR>(__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)
{
// 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)
return outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "Cooking::cookConvexMesh: non-manifold mesh cannot be used, invalid mesh!");
// 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_FREE(mHullDataFacesByEdges8);
mHullDataFacesByEdges8 = PX_ALLOCATE(PxU8, nbEdgesUnshared, "mHullDataFacesByEdges8");
PxU32* tempBuffer = PX_ALLOCATE(PxU32, nbEdgesUnshared*8, "tmp"); // 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_ALLOCATE(bool, nbEdgesUnshared, "tmp"); // 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::PxSwap(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_FREE(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_ALLOCATE(PxU16, nbEdgesUnshared, "mEdges");
PX_FREE(mEdgeData16);
// Face to edge mapping
mEdgeData16 = PX_ALLOCATE(PxU16, nbEdgesUnshared, "mEdgeData16");
// TODO avoroshilov: remove this comment
//mHull->mNbEdges = PxTo16(nbEdgesUnshared / 2); // #non-redundant edges
mHull->mNbEdges = 0; // #non-redundant edges
// 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 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)
return outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "Cooking::cookConvexMesh: non-manifold mesh cannot be used, invalid mesh!");
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::PxSwap(sortedRef0, sortedRef1);
*edgeVertOutput++ = PxTo16(sortedRef0);
*edgeVertOutput++ = PxTo16(sortedRef1);
nbHullEdges++;
}
else
{
mHullDataFacesByEdges8[(nbHullEdges - 1) * 2] = PxTo8(previousPolyId);
mHullDataFacesByEdges8[(nbHullEdges - 1) * 2 + 1] = PxTo8(polyID);
++numFacesPerEdgeVerificationCounter;
}
mEdgeData16[mHullDataPolygons[polyID].mVRef8 + vertexID] = PxTo16(i / 2);
// 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]];
const PxU16 nbToGo = PxU16(mHull->mNbEdges);
EdgeDescData* edgeToTriangles = PX_ALLOCATE(EdgeDescData, nbToGo, "edgeToTriangles");
PxMemZero(edgeToTriangles, sizeof(EdgeDescData)*nbToGo);
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 < nbToGo; i++)
{
if (edgeToTriangles[i].Count != 2)
return outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "Cooking::cookConvexMesh: non-manifold mesh cannot be used, invalid mesh!");
}
PX_FREE(edgeToTriangles);
}
// TODO avoroshilov: use the same "tempBuffer"
PX_FREE(flippedVRefs);
// ### free temp ram
PX_FREE(bufferAdd);
return true;
}