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 "cooking/PxCooking.h"
#include "foundation/PxUserAllocated.h"
#include "foundation/PxUtilities.h"
#include "foundation/PxVecMath.h"
#include "GuConvexMeshData.h"
#include "GuBigConvexData2.h"
#include "GuIntersectionRayPlane.h"
#include "GuCookingBigConvexDataBuilder.h"
#include "GuCookingConvexHullBuilder.h"
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
using namespace physx;
using namespace Gu;
using namespace aos;
static const PxU32 gSupportVersion = 0;
static const PxU32 gVersion = 0;
BigConvexDataBuilder::BigConvexDataBuilder(const Gu::ConvexHullData* hull, BigConvexData* gm, const PxVec3* hullVerts) : mHullVerts(hullVerts)
{
mSVM = gm;
mHull = hull;
}
BigConvexDataBuilder::~BigConvexDataBuilder()
{
}
bool BigConvexDataBuilder::initialize()
{
mSVM->mData.mSamples = PX_ALLOCATE(PxU8, mSVM->mData.mNbSamples*2u, "mData.mSamples");
#if PX_DEBUG
// printf("SVM: %d bytes\n", mNbSamples*sizeof(PxU8)*2);
#endif
return true;
}
bool BigConvexDataBuilder::save(PxOutputStream& stream, bool platformMismatch) const
{
// Export header
if(!Cm::WriteHeader('S', 'U', 'P', 'M', gSupportVersion, platformMismatch, stream))
return false;
// Save base gaussmap
// if(!GaussMapBuilder::Save(stream, platformMismatch)) return false;
// Export header
if(!Cm::WriteHeader('G', 'A', 'U', 'S', gVersion, platformMismatch, stream))
return false;
// Export basic info
// stream.StoreDword(mSubdiv);
writeDword(mSVM->mData.mSubdiv, platformMismatch, stream); // PT: could now write Word here
// stream.StoreDword(mNbSamples);
writeDword(mSVM->mData.mNbSamples, platformMismatch, stream); // PT: could now write Word here
// Save map data
// It's an array of bytes so we don't care about 'PlatformMismatch'
stream.write(mSVM->mData.mSamples, sizeof(PxU8)*mSVM->mData.mNbSamples*2);
if(!saveValencies(stream, platformMismatch))
return false;
return true;
}
//////////////////////////////////////////////////////////////////////////
// compute valencies for each vertex
// we dont compute the edges again here, we have them temporary stored in mHullDataFacesByAllEdges8 structure
bool BigConvexDataBuilder::computeValencies(const ConvexHullBuilder& meshBuilder)
{
// Create valencies
const PxU32 numVertices = meshBuilder.mHull->mNbHullVertices;
mSVM->mData.mNbVerts = numVertices;
// Get ram for valencies and adjacent verts
const PxU32 numAlignedVerts = (numVertices+3)&~3;
const PxU32 TotalSize = sizeof(Gu::Valency)*numAlignedVerts + sizeof(PxU8)*meshBuilder.mHull->mNbEdges*2u;
mSVM->mVBuffer = PX_ALLOC(TotalSize, "BigConvexData data");
mSVM->mData.mValencies = reinterpret_cast<Gu::Valency*>(mSVM->mVBuffer);
mSVM->mData.mAdjacentVerts = (reinterpret_cast<PxU8*>(mSVM->mVBuffer)) + sizeof(Gu::Valency)*numAlignedVerts;
PxMemZero(mSVM->mData.mValencies, numVertices*sizeof(Gu::Valency));
PxU8 vertexMarker[256];
PxMemZero(vertexMarker,numVertices);
// Compute valencies
for (PxU32 i = 0; i < meshBuilder.mHull->mNbPolygons; i++)
{
const PxU32 numVerts = meshBuilder.mHullDataPolygons[i].mNbVerts;
const PxU8* Data = meshBuilder.mHullDataVertexData8 + meshBuilder.mHullDataPolygons[i].mVRef8;
for (PxU32 j = 0; j < numVerts; j++)
{
mSVM->mData.mValencies[Data[j]].mCount++;
PX_ASSERT(mSVM->mData.mValencies[Data[j]].mCount != 0xffff);
}
}
// Create offsets
mSVM->CreateOffsets();
// mNbAdjVerts = mOffsets[mNbVerts-1] + mValencies[mNbVerts-1];
mSVM->mData.mNbAdjVerts = PxU32(mSVM->mData.mValencies[mSVM->mData.mNbVerts - 1].mOffset + mSVM->mData.mValencies[mSVM->mData.mNbVerts - 1].mCount);
PX_ASSERT(mSVM->mData.mNbAdjVerts == PxU32(meshBuilder.mHull->mNbEdges * 2));
// Create adjacent vertices
// parse the polygons and its vertices
for (PxU32 i = 0; i < meshBuilder.mHull->mNbPolygons; i++)
{
PxU32 numVerts = meshBuilder.mHullDataPolygons[i].mNbVerts;
const PxU8* Data = meshBuilder.mHullDataVertexData8 + meshBuilder.mHullDataPolygons[i].mVRef8;
for (PxU32 j = 0; j < numVerts; j++)
{
const PxU8 vertexIndex = Data[j];
PxU8 numAdj = 0;
// if we did not parsed this vertex, traverse to the adjacent face and then
// again to next till we hit back the original polygon
if(vertexMarker[vertexIndex] == 0)
{
PxU8 prevIndex = Data[(j+1)%numVerts];
mSVM->mData.mAdjacentVerts[mSVM->mData.mValencies[vertexIndex].mOffset++] = prevIndex;
numAdj++;
// now traverse the neighbors
const PxU16 edgeIndex = PxU16(meshBuilder.mEdgeData16[meshBuilder.mHullDataPolygons[i].mVRef8 + j]*2);
PxU8 n0 = meshBuilder.mHullDataFacesByEdges8[edgeIndex];
PxU8 n1 = meshBuilder.mHullDataFacesByEdges8[edgeIndex + 1];
PxU32 neighborPolygon = n0 == i ? n1 : n0;
while (neighborPolygon != i)
{
PxU32 numNeighborVerts = meshBuilder.mHullDataPolygons[neighborPolygon].mNbVerts;
const PxU8* neighborData = meshBuilder.mHullDataVertexData8 + meshBuilder.mHullDataPolygons[neighborPolygon].mVRef8;
PxU32 nextEdgeIndex = 0;
// search in the neighbor face for the tested vertex
for (PxU32 k = 0; k < numNeighborVerts; k++)
{
// search the vertexIndex
if(neighborData[k] == vertexIndex)
{
const PxU8 nextIndex = neighborData[(k+1)%numNeighborVerts];
// next index already there, pick the previous
if(nextIndex == prevIndex)
{
prevIndex = k == 0 ? neighborData[numNeighborVerts - 1] : neighborData[k-1];
nextEdgeIndex = k == 0 ? numNeighborVerts - 1 : k-1;
}
else
{
prevIndex = nextIndex;
nextEdgeIndex = k;
}
mSVM->mData.mAdjacentVerts[mSVM->mData.mValencies[vertexIndex].mOffset++] = prevIndex;
numAdj++;
break;
}
}
// now move to next neighbor
const PxU16 edgeIndex2 = PxU16(meshBuilder.mEdgeData16[(meshBuilder.mHullDataPolygons[neighborPolygon].mVRef8 + nextEdgeIndex)]*2);
n0 = meshBuilder.mHullDataFacesByEdges8[edgeIndex2];
n1 = meshBuilder.mHullDataFacesByEdges8[edgeIndex2 + 1];
neighborPolygon = n0 == neighborPolygon ? n1 : n0;
}
vertexMarker[vertexIndex] = numAdj;
}
}
}
// Recreate offsets
mSVM->CreateOffsets();
return true;
}
//////////////////////////////////////////////////////////////////////////
// compute the min dot product from the verts for given dir
void BigConvexDataBuilder::precomputeSample(const PxVec3& dir, PxU8& startIndex_, float negativeDir)
{
PxU8 startIndex = startIndex_;
const PxVec3* verts = mHullVerts;
const Valency* valency = mSVM->mData.mValencies;
const PxU8* adjacentVerts = mSVM->mData.mAdjacentVerts;
// we have only 256 verts
PxU32 smallBitMap[8] = {0,0,0,0,0,0,0,0};
float minimum = negativeDir * verts[startIndex].dot(dir);
PxU32 initialIndex = startIndex;
do
{
initialIndex = startIndex;
const PxU32 numNeighbours = valency[startIndex].mCount;
const PxU32 offset = valency[startIndex].mOffset;
for (PxU32 a = 0; a < numNeighbours; ++a)
{
const PxU8 neighbourIndex = adjacentVerts[offset + a];
const float dist = negativeDir * verts[neighbourIndex].dot(dir);
if (dist < minimum)
{
const PxU32 ind = PxU32(neighbourIndex >> 5);
const PxU32 mask = PxU32(1 << (neighbourIndex & 31));
if ((smallBitMap[ind] & mask) == 0)
{
smallBitMap[ind] |= mask;
minimum = dist;
startIndex = neighbourIndex;
}
}
}
} while (startIndex != initialIndex);
startIndex_ = startIndex;
}
//////////////////////////////////////////////////////////////////////////
// Precompute the min/max vertices for cube directions.
bool BigConvexDataBuilder::precompute(PxU32 subdiv)
{
mSVM->mData.mSubdiv = PxTo16(subdiv);
mSVM->mData.mNbSamples = PxTo16(6 * subdiv*subdiv);
if (!initialize())
return false;
PxU8 startIndex[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
PxU8 startIndex2[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
const float halfSubdiv = float(subdiv - 1) * 0.5f;
for (PxU32 j = 0; j < subdiv; j++)
{
for (PxU32 i = j; i < subdiv; i++)
{
const float iSubDiv = 1.0f - i / halfSubdiv;
const float jSubDiv = 1.0f - j / halfSubdiv;
PxVec3 tempDir(1.0f, iSubDiv, jSubDiv);
// we need to normalize only once, then we permute the components
// as before for each i,j and j,i face direction
tempDir.normalize();
const PxVec3 dirs[12] = {
PxVec3(-tempDir.x, tempDir.y, tempDir.z),
PxVec3(tempDir.x, tempDir.y, tempDir.z),
PxVec3(tempDir.z, -tempDir.x, tempDir.y),
PxVec3(tempDir.z, tempDir.x, tempDir.y),
PxVec3(tempDir.y, tempDir.z, -tempDir.x),
PxVec3(tempDir.y, tempDir.z, tempDir.x),
PxVec3(-tempDir.x, tempDir.z, tempDir.y),
PxVec3(tempDir.x, tempDir.z, tempDir.y),
PxVec3(tempDir.y, -tempDir.x, tempDir.z),
PxVec3(tempDir.y, tempDir.x, tempDir.z),
PxVec3(tempDir.z, tempDir.y, -tempDir.x),
PxVec3(tempDir.z, tempDir.y, tempDir.x)
};
// compute in each direction + negative/positive dot, we have
// then two start indexes, which are used then for hill climbing
for (PxU32 dStep = 0; dStep < 12; dStep++)
{
precomputeSample(dirs[dStep], startIndex[dStep], 1.0f);
precomputeSample(dirs[dStep], startIndex2[dStep], -1.0f);
}
// decompose the vector results into face directions
for (PxU32 k = 0; k < 6; k++)
{
const PxU32 ksub = k*subdiv*subdiv;
const PxU32 offset = j + i*subdiv + ksub;
const PxU32 offset2 = i + j*subdiv + ksub;
PX_ASSERT(offset < mSVM->mData.mNbSamples);
PX_ASSERT(offset2 < mSVM->mData.mNbSamples);
mSVM->mData.mSamples[offset] = startIndex[k];
mSVM->mData.mSamples[offset + mSVM->mData.mNbSamples] = startIndex2[k];
mSVM->mData.mSamples[offset2] = startIndex[k + 6];
mSVM->mData.mSamples[offset2 + mSVM->mData.mNbSamples] = startIndex2[k + 6];
}
}
}
return true;
}
static const PxU32 gValencyVersion = 2;
//////////////////////////////////////////////////////////////////////////
bool BigConvexDataBuilder::saveValencies(PxOutputStream& stream, bool platformMismatch) const
{
// Export header
if(!Cm::WriteHeader('V', 'A', 'L', 'E', gValencyVersion, platformMismatch, stream))
return false;
writeDword(mSVM->mData.mNbVerts, platformMismatch, stream);
writeDword(mSVM->mData.mNbAdjVerts, platformMismatch, stream);
{
PxU16* temp = PX_ALLOCATE(PxU16, mSVM->mData.mNbVerts, "tmp");
for(PxU32 i=0;i<mSVM->mData.mNbVerts;i++)
temp[i] = mSVM->mData.mValencies[i].mCount;
const PxU32 maxIndex = computeMaxIndex(temp, mSVM->mData.mNbVerts);
writeDword(maxIndex, platformMismatch, stream);
Cm::StoreIndices(PxTo16(maxIndex), mSVM->mData.mNbVerts, temp, stream, platformMismatch);
PX_FREE(temp);
}
stream.write(mSVM->mData.mAdjacentVerts, mSVM->mData.mNbAdjVerts);
return true;
}