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 "GuBV4Build.h"
#include "foundation/PxVec4.h"
#include "foundation/PxMemory.h"
#include "GuAABBTreeBuildStats.h"
#include "GuAABBTree.h"
#include "GuSAH.h"
#include "GuBounds.h"
#include "GuBV4.h"
#include <stdio.h>
using namespace physx;
using namespace Gu;
#include "foundation/PxVecMath.h"
using namespace aos;
#define GU_BV4_USE_NODE_POOLS
PX_IMPLEMENT_OUTPUT_ERROR
static PX_FORCE_INLINE PxU32 largestAxis(const PxVec4& v)
{
const float* Vals = &v.x;
PxU32 m = 0;
if(Vals[1] > Vals[m]) m = 1;
if(Vals[2] > Vals[m]) m = 2;
return m;
}
BV4_AABBTree::BV4_AABBTree() : mIndices(NULL), mPool(NULL), mTotalNbNodes(0)
{
}
BV4_AABBTree::~BV4_AABBTree()
{
release();
}
void BV4_AABBTree::release()
{
PX_DELETE_ARRAY(mPool);
PX_FREE(mIndices);
}
namespace
{
struct BuildParams
{
PX_FORCE_INLINE BuildParams(const PxBounds3* boxes, const PxVec3* centers, const AABBTreeNode* const node_base, const PxU32 limit, const SourceMesh* mesh) :
mBoxes(boxes), mCenters(centers), mNodeBase(node_base), mLimit(limit), mMesh(mesh) {}
const PxBounds3* mBoxes;
const PxVec3* mCenters;
const AABBTreeNode* const mNodeBase;
const PxU32 mLimit;
const SourceMesh* mMesh;
PX_NOCOPY(BuildParams)
};
}
static PxU32 local_Split(const AABBTreeNode* PX_RESTRICT node, const PxBounds3* PX_RESTRICT /*Boxes*/, const PxVec3* PX_RESTRICT centers, PxU32 axis, const BuildParams& params)
{
const PxU32 nb = node->mNbPrimitives;
PxU32* PX_RESTRICT prims = node->mNodePrimitives;
// Get node split value
float splitValue = 0.0f;
if(params.mMesh)
{
VertexPointers VP;
for(PxU32 i=0;i<nb;i++)
{
params.mMesh->getTriangle(VP, prims[i]);
splitValue += (*VP.Vertex[0])[axis];
splitValue += (*VP.Vertex[1])[axis];
splitValue += (*VP.Vertex[2])[axis];
}
splitValue /= float(nb*3);
}
else
splitValue = node->mBV.getCenter(axis);
return reshuffle(nb, prims, centers, splitValue, axis);
}
static bool local_Subdivide(AABBTreeNode* PX_RESTRICT node, BuildStats& stats, const BuildParams& params)
{
const PxU32* PX_RESTRICT prims = node->mNodePrimitives;
const PxU32 nb = node->mNbPrimitives;
const PxBounds3* PX_RESTRICT boxes = params.mBoxes;
const PxVec3* PX_RESTRICT centers = params.mCenters;
// Compute bv & means at the same time
Vec4V meansV;
{
Vec4V minV = V4LoadU(&boxes[prims[0]].minimum.x);
Vec4V maxV = V4LoadU(&boxes[prims[0]].maximum.x);
meansV = V4LoadU(¢ers[prims[0]].x);
for(PxU32 i=1;i<nb;i++)
{
const PxU32 index = prims[i];
minV = V4Min(minV, V4LoadU(&boxes[index].minimum.x));
maxV = V4Max(maxV, V4LoadU(&boxes[index].maximum.x));
meansV = V4Add(meansV, V4LoadU(¢ers[index].x));
}
const float coeffNb = 1.0f/float(nb);
meansV = V4Scale(meansV, FLoad(coeffNb));
// BV4_ALIGN16(PxVec4 mergedMin);
// BV4_ALIGN16(PxVec4 mergedMax);
PX_ALIGN_PREFIX(16) PxVec4 mergedMin PX_ALIGN_SUFFIX(16);
PX_ALIGN_PREFIX(16) PxVec4 mergedMax PX_ALIGN_SUFFIX(16);
V4StoreA_Safe(minV, &mergedMin.x);
V4StoreA_Safe(maxV, &mergedMax.x);
node->mBV.minimum = PxVec3(mergedMin.x, mergedMin.y, mergedMin.z);
node->mBV.maximum = PxVec3(mergedMax.x, mergedMax.y, mergedMax.z);
}
#ifndef GU_BV4_FILL_GAPS
// // Stop subdividing if we reach a leaf node. This is always performed here,
// // else we could end in trouble if user overrides this.
// if(nb==1)
// return false;
if(nb<=params.mLimit)
return false;
#endif
bool validSplit = true;
PxU32 nbPos;
{
// Compute variances
Vec4V varsV = V4Zero();
for(PxU32 i=0;i<nb;i++)
{
const PxU32 index = prims[i];
Vec4V centerV = V4LoadU(¢ers[index].x);
centerV = V4Sub(centerV, meansV);
centerV = V4Mul(centerV, centerV);
varsV = V4Add(varsV, centerV);
}
const float coeffNb1 = nb>1 ? 1.0f/float(nb-1) : 0.0f;
varsV = V4Scale(varsV, FLoad(coeffNb1));
// BV4_ALIGN16(PxVec4 vars);
PX_ALIGN_PREFIX(16) PxVec4 vars PX_ALIGN_SUFFIX(16);
V4StoreA_Safe(varsV, &vars.x);
// Choose axis with greatest variance
const PxU32 axis = largestAxis(vars);
// Split along the axis
nbPos = local_Split(node, boxes, centers, axis, params);
// Check split validity
if(!nbPos || nbPos==nb)
validSplit = false;
}
// Check the subdivision has been successful
if(!validSplit)
{
// Here, all boxes lie in the same sub-space. Two strategies:
// - if the tree *must* be complete, make an arbitrary 50-50 split
// - else stop subdividing
// if(nb>limit)
{
nbPos = node->mNbPrimitives>>1;
if(1)
{
// Test 3 axes, take the best
float results[3];
nbPos = local_Split(node, boxes, centers, 0, params); results[0] = float(nbPos)/float(node->mNbPrimitives);
nbPos = local_Split(node, boxes, centers, 1, params); results[1] = float(nbPos)/float(node->mNbPrimitives);
nbPos = local_Split(node, boxes, centers, 2, params); results[2] = float(nbPos)/float(node->mNbPrimitives);
results[0]-=0.5f; results[0]*=results[0];
results[1]-=0.5f; results[1]*=results[1];
results[2]-=0.5f; results[2]*=results[2];
PxU32 Min=0;
if(results[1]<results[Min]) Min = 1;
if(results[2]<results[Min]) Min = 2;
// Split along the axis
nbPos = local_Split(node, boxes, centers, Min, params);
// Check split validity
if(!nbPos || nbPos==node->mNbPrimitives)
nbPos = node->mNbPrimitives>>1;
}
}
//else return
}
#ifdef GU_BV4_FILL_GAPS
// We split the node a last time before returning when we're below the limit, for the "fill the gaps" strategy
if(nb<=params.mLimit)
{
node->mNextSplit = nbPos;
return false;
}
#endif
// Now create children and assign their pointers.
// We use a pre-allocated linear pool for complete trees [Opcode 1.3]
const PxU32 count = stats.getCount();
node->mPos = size_t(params.mNodeBase + count);
// Update stats
stats.increaseCount(2);
// Assign children
AABBTreeNode* pos = const_cast<AABBTreeNode*>(node->getPos());
AABBTreeNode* neg = const_cast<AABBTreeNode*>(node->getNeg());
pos->mNodePrimitives = node->mNodePrimitives;
pos->mNbPrimitives = nbPos;
neg->mNodePrimitives = node->mNodePrimitives + nbPos;
neg->mNbPrimitives = node->mNbPrimitives - nbPos;
return true;
}
static bool local_Subdivide_SAH(AABBTreeNode* PX_RESTRICT node, BuildStats& stats, const BuildParams& params, SAH_Buffers& buffers)
{
const PxU32* prims = node->mNodePrimitives;
const PxU32 nb = node->mNbPrimitives;
const PxBounds3* PX_RESTRICT boxes = params.mBoxes;
const PxVec3* PX_RESTRICT centers = params.mCenters;
// Compute bv
computeGlobalBox(node->mBV, nb, boxes, prims);
#ifndef GU_BV4_FILL_GAPS
// // Stop subdividing if we reach a leaf node. This is always performed here,
// // else we could end in trouble if user overrides this.
// if(nb==1)
// return false;
if(nb<=params.mLimit)
return false;
#endif
PxU32 leftCount;
if(!buffers.split(leftCount, nb, prims, boxes, centers))
{
// Invalid split => fallback to previous strategy
return local_Subdivide(node, stats, params);
}
#ifdef GU_BV4_FILL_GAPS
// We split the node a last time before returning when we're below the limit, for the "fill the gaps" strategy
if(nb<=params.mLimit)
{
node->mNextSplit = leftCount;
return false;
}
#endif
// Now create children and assign their pointers.
// We use a pre-allocated linear pool for complete trees [Opcode 1.3]
const PxU32 count = stats.getCount();
node->mPos = size_t(params.mNodeBase + count);
// Update stats
stats.increaseCount(2);
// Assign children
AABBTreeNode* pos = const_cast<AABBTreeNode*>(node->getPos());
AABBTreeNode* neg = const_cast<AABBTreeNode*>(node->getNeg());
pos->mNodePrimitives = node->mNodePrimitives;
pos->mNbPrimitives = leftCount;
neg->mNodePrimitives = node->mNodePrimitives + leftCount;
neg->mNbPrimitives = node->mNbPrimitives - leftCount;
return true;
}
// PT: TODO: consider local_BuildHierarchy & local_BuildHierarchy_SAH
static void local_BuildHierarchy(AABBTreeNode* PX_RESTRICT node, BuildStats& stats, const BuildParams& params)
{
if(local_Subdivide(node, stats, params))
{
AABBTreeNode* pos = const_cast<AABBTreeNode*>(node->getPos());
AABBTreeNode* neg = const_cast<AABBTreeNode*>(node->getNeg());
local_BuildHierarchy(pos, stats, params);
local_BuildHierarchy(neg, stats, params);
}
}
static void local_BuildHierarchy_SAH(AABBTreeNode* PX_RESTRICT node, BuildStats& stats, const BuildParams& params, SAH_Buffers& buffers)
{
if(local_Subdivide_SAH(node, stats, params, buffers))
{
AABBTreeNode* pos = const_cast<AABBTreeNode*>(node->getPos());
AABBTreeNode* neg = const_cast<AABBTreeNode*>(node->getNeg());
local_BuildHierarchy_SAH(pos, stats, params, buffers);
local_BuildHierarchy_SAH(neg, stats, params, buffers);
}
}
bool BV4_AABBTree::buildFromMesh(SourceMeshBase& mesh, PxU32 limit, BV4_BuildStrategy strategy)
{
const PxU32 nbBoxes = mesh.getNbPrimitives();
if(!nbBoxes)
return false;
PxBounds3* boxes = PX_ALLOCATE(PxBounds3, (nbBoxes + 1), "BV4"); // PT: +1 to safely V4Load/V4Store the last element
PxVec3* centers = PX_ALLOCATE(PxVec3, (nbBoxes + 1), "BV4"); // PT: +1 to safely V4Load/V4Store the last element
const FloatV halfV = FLoad(0.5f);
for (PxU32 i = 0; i<nbBoxes; i++)
{
Vec4V minV, maxV;
mesh.getPrimitiveBox(i, minV, maxV);
V4StoreU_Safe(minV, &boxes[i].minimum.x); // PT: safe because 'maximum' follows 'minimum'
V4StoreU_Safe(maxV, &boxes[i].maximum.x); // PT: safe because we allocated one more box
const Vec4V centerV = V4Scale(V4Add(maxV, minV), halfV);
V4StoreU_Safe(centerV, ¢ers[i].x); // PT: safe because we allocated one more PxVec3
}
{
// Release previous tree
release();
// Init stats
BuildStats Stats;
Stats.setCount(1);
// Initialize indices. This list will be modified during build.
mIndices = PX_ALLOCATE(PxU32, nbBoxes, "BV4 indices");
// Identity permutation
for (PxU32 i = 0; i<nbBoxes; i++)
mIndices[i] = i;
// Use a linear array for complete trees (since we can predict the final number of nodes) [Opcode 1.3]
// Allocate a pool of nodes
// PT: TODO: optimize memory here (TA34704)
mPool = PX_NEW(AABBTreeNode)[nbBoxes * 2 - 1];
if(!mPool)
return false; // PT: OMPE-68715
// Setup initial node. Here we have a complete permutation of the app's primitives.
mPool->mNodePrimitives = mIndices;
mPool->mNbPrimitives = nbBoxes;
// Build the hierarchy
if(strategy==BV4_SPLATTER_POINTS||strategy==BV4_SPLATTER_POINTS_SPLIT_GEOM_CENTER)
{
// PT: not sure what the equivalent would be for tet-meshes here
SourceMesh* triMesh = NULL;
if(strategy==BV4_SPLATTER_POINTS_SPLIT_GEOM_CENTER)
{
if(mesh.getMeshType()==SourceMeshBase::TRI_MESH)
triMesh = static_cast<SourceMesh*>(&mesh);
}
local_BuildHierarchy(mPool, Stats, BuildParams(boxes, centers, mPool, limit, triMesh));
}
else if(strategy==BV4_SAH)
{
SAH_Buffers sah(nbBoxes);
local_BuildHierarchy_SAH(mPool, Stats, BuildParams(boxes, centers, mPool, limit, NULL), sah);
}
else
return false;
// Get back total number of nodes
mTotalNbNodes = Stats.getCount();
}
PX_FREE(centers);
PX_FREE(boxes);
if(0)
printf("Tree depth: %d\n", walk(NULL, NULL));
return true;
}
PxU32 BV4_AABBTree::walk(WalkingCallback cb, void* userData) const
{
// Call it without callback to compute max depth
PxU32 maxDepth = 0;
PxU32 currentDepth = 0;
struct Local
{
static void _walk(const AABBTreeNode* current_node, PxU32& max_depth, PxU32& current_depth, WalkingCallback callback, void* userData_)
{
// Checkings
if(!current_node)
return;
// Entering a new node => increase depth
current_depth++;
// Keep track of max depth
if(current_depth>max_depth)
max_depth = current_depth;
// Callback
if(callback && !(callback)(current_node, current_depth, userData_))
return;
// Recurse
if(current_node->getPos()) { _walk(current_node->getPos(), max_depth, current_depth, callback, userData_); current_depth--; }
if(current_node->getNeg()) { _walk(current_node->getNeg(), max_depth, current_depth, callback, userData_); current_depth--; }
}
};
Local::_walk(mPool, maxDepth, currentDepth, cb, userData);
return maxDepth;
}
PxU32 BV4_AABBTree::walkDistance(WalkingCallback cb, WalkingDistanceCallback cb2, void* userData) const
{
// Call it without callback to compute max depth
PxU32 maxDepth = 0;
PxU32 currentDepth = 0;
struct Local
{
static void _walk(const AABBTreeNode* current_node, PxU32& max_depth, PxU32& current_depth, WalkingCallback callback, WalkingDistanceCallback distanceCheck, void* userData_)
{
// Checkings
if (!current_node)
return;
// Entering a new node => increase depth
current_depth++;
// Keep track of max depth
if (current_depth > max_depth)
max_depth = current_depth;
// Callback
if (callback && !(callback)(current_node, current_depth, userData_))
return;
// Recurse
bool posHint = distanceCheck && (distanceCheck)(current_node, userData_);
if (posHint)
{
if (current_node->getPos()) { _walk(current_node->getPos(), max_depth, current_depth, callback, distanceCheck, userData_); current_depth--; }
if (current_node->getNeg()) { _walk(current_node->getNeg(), max_depth, current_depth, callback, distanceCheck, userData_); current_depth--; }
}
else
{
if (current_node->getNeg()) { _walk(current_node->getNeg(), max_depth, current_depth, callback, distanceCheck, userData_); current_depth--; }
if (current_node->getPos()) { _walk(current_node->getPos(), max_depth, current_depth, callback, distanceCheck, userData_); current_depth--; }
}
}
};
Local::_walk(mPool, maxDepth, currentDepth, cb, cb2, userData);
return maxDepth;
}
#include "GuBV4_Internal.h"
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
// PT: see http://www.codercorner.com/blog/?p=734
static PxU32 precomputeNodeSorting(const PxBounds3& box0, const PxBounds3& box1)
{
const PxVec3 C0 = box0.getCenter();
const PxVec3 C1 = box1.getCenter();
PxVec3 dirPPP(1.0f, 1.0f, 1.0f); dirPPP.normalize();
PxVec3 dirPPN(1.0f, 1.0f, -1.0f); dirPPN.normalize();
PxVec3 dirPNP(1.0f, -1.0f, 1.0f); dirPNP.normalize();
PxVec3 dirPNN(1.0f, -1.0f, -1.0f); dirPNN.normalize();
PxVec3 dirNPP(-1.0f, 1.0f, 1.0f); dirNPP.normalize();
PxVec3 dirNPN(-1.0f, 1.0f, -1.0f); dirNPN.normalize();
PxVec3 dirNNP(-1.0f, -1.0f, 1.0f); dirNNP.normalize();
PxVec3 dirNNN(-1.0f, -1.0f, -1.0f); dirNNN.normalize();
const PxVec3 deltaC = C0 - C1;
const bool bPPP = deltaC.dot(dirPPP)<0.0f;
const bool bPPN = deltaC.dot(dirPPN)<0.0f;
const bool bPNP = deltaC.dot(dirPNP)<0.0f;
const bool bPNN = deltaC.dot(dirPNN)<0.0f;
const bool bNPP = deltaC.dot(dirNPP)<0.0f;
const bool bNPN = deltaC.dot(dirNPN)<0.0f;
const bool bNNP = deltaC.dot(dirNNP)<0.0f;
const bool bNNN = deltaC.dot(dirNNN)<0.0f;
PxU32 code = 0;
if(!bPPP)
code |= (1<<7); // Bit 0: PPP
if(!bPPN)
code |= (1<<6); // Bit 1: PPN
if(!bPNP)
code |= (1<<5); // Bit 2: PNP
if(!bPNN)
code |= (1<<4); // Bit 3: PNN
if(!bNPP)
code |= (1<<3); // Bit 4: NPP
if(!bNPN)
code |= (1<<2); // Bit 5: NPN
if(!bNNP)
code |= (1<<1); // Bit 6: NNP
if(!bNNN)
code |= (1<<0); // Bit 7: NNN
return code;
}
#endif
#ifdef GU_BV4_USE_SLABS
#include "GuBV4_Common.h"
#endif
// PT: warning, not the same as CenterExtents::setEmpty()
static void setEmpty(CenterExtents& box)
{
box.mCenter = PxVec3(0.0f, 0.0f, 0.0f);
box.mExtents = PxVec3(-1.0f, -1.0f, -1.0f);
}
#define PX_INVALID_U64 0xffffffffffffffff
// Data:
// 1 bit for leaf/no leaf
// 2 bits for child-node type
// 8 bits for PNS
// => 32 - 1 - 2 - 8 = 21 bits left for encoding triangle index or node *offset*
// => limited to 2.097.152 triangles
// => and 2Mb-large trees (this one may not work out well in practice)
// ==> lines marked with //* have been changed to address this. Now we don't store offsets in bytes directly
// but in BVData indices. There's more work at runtime calculating addresses, but now the format can support
// 2 million single nodes.
//
// That being said we only need 3*8 = 24 bits in total, so that could be only 6 bits in each BVData.
// For type0: we have 2 nodes, we need 8 bits => 6 bits/node = 12 bits available, ok
// For type1: we have 3 nodes, we need 8*2 = 16 bits => 6 bits/node = 18 bits available, ok
// For type2: we have 4 nodes, we need 8*3 = 24 bits => 6 bits/node = 24 bits available, ok
//#pragma pack(1)
struct BVData : public physx::PxUserAllocated
{
BVData();
CenterExtents mAABB;
size_t mData64;
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
PxU32 mTempPNS;
#endif
};
//#pragma pack()
BVData::BVData() : mData64(PX_INVALID_U64)
{
setEmpty(mAABB);
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
mTempPNS = 0;
#endif
}
struct BV4Node : public physx::PxUserAllocated
{
PX_FORCE_INLINE BV4Node() {}
PX_FORCE_INLINE ~BV4Node() {}
BVData mBVData[4];
PX_FORCE_INLINE size_t isLeaf(PxU32 i) const { return mBVData[i].mData64 & 1; }
PX_FORCE_INLINE PxU32 getPrimitive(PxU32 i) const { return PxU32(mBVData[i].mData64 >> 1); }
PX_FORCE_INLINE const BV4Node* getChild(PxU32 i) const { return reinterpret_cast<BV4Node*>(mBVData[i].mData64); }
PxU32 getType() const
{
PxU32 Nb=0;
for(PxU32 i=0;i<4;i++)
{
if(mBVData[i].mData64!=PX_INVALID_U64)
Nb++;
}
return Nb;
}
PxU32 getSize() const
{
const PxU32 type = getType();
return sizeof(BVData)*type;
}
};
#define NB_NODES_PER_SLAB 256
struct BV4BuildParams
{
PX_FORCE_INLINE BV4BuildParams(const BV4_AABBTree& source, const SourceMesh* mesh, float epsilon) : mSource(source), mMesh(mesh), mEpsilon(epsilon)
#ifdef GU_BV4_USE_NODE_POOLS
,mTop(NULL)
#endif
{}
~BV4BuildParams();
const BV4_AABBTree& mSource;
const SourceMesh* mMesh;
// Stats
PxU32 mNbNodes;
PxU32 mStats[4];
//
float mEpsilon;
#ifdef GU_BV4_USE_NODE_POOLS
//
struct Slab : public physx::PxUserAllocated
{
BV4Node mNodes[NB_NODES_PER_SLAB];
PxU32 mNbUsedNodes;
Slab* mNext;
};
Slab* mTop;
BV4Node* allocateNode();
void releaseNodes();
#endif
PX_NOCOPY(BV4BuildParams)
};
BV4BuildParams::~BV4BuildParams()
{
#ifdef GU_BV4_USE_NODE_POOLS
releaseNodes();
#endif
}
#ifdef GU_BV4_USE_NODE_POOLS
BV4Node* BV4BuildParams::allocateNode()
{
if(!mTop || mTop->mNbUsedNodes==NB_NODES_PER_SLAB)
{
Slab* newSlab = PX_NEW(Slab);
newSlab->mNbUsedNodes = 0;
newSlab->mNext = mTop;
mTop = newSlab;
}
return &mTop->mNodes[mTop->mNbUsedNodes++];
}
void BV4BuildParams::releaseNodes()
{
Slab* current = mTop;
while(current)
{
Slab* next = current->mNext;
PX_DELETE(current);
current = next;
}
mTop = NULL;
}
#endif
static PX_FORCE_INLINE void setupBounds(BV4Node* node4, PxU32 i, const AABBTreeNode* node, float epsilon)
{
node4->mBVData[i].mAABB = node->getAABB();
if(epsilon!=0.0f)
node4->mBVData[i].mAABB.mExtents += PxVec3(epsilon);
}
static void setPrimitive(const BV4_AABBTree& source, BV4Node* node4, PxU32 i, const AABBTreeNode* node, float epsilon)
{
const PxU32 nbPrims = node->getNbPrimitives();
PX_ASSERT(nbPrims<16);
const PxU32* indexBase = source.getIndices();
const PxU32* prims = node->getPrimitives();
const PxU64 offset = PxU64(prims - indexBase);
for(PxU32 j=0;j<nbPrims;j++)
{
PX_ASSERT(prims[j] == offset+j);
}
const PxU64 primitiveIndex = (offset<<4)|(nbPrims&15);
setupBounds(node4, i, node, epsilon);
node4->mBVData[i].mData64 = (primitiveIndex<<1)|1;
}
#ifdef GU_BV4_FILL_GAPS
static bool splitPrimitives(const BV4BuildParams& params, BV4Node* node4, PxU32 i, const AABBTreeNode* node)
{
if(!params.mMesh)
return false;
const PxU32 nbPrims = node->getNbPrimitives();
PX_ASSERT(nbPrims<16);
if(nbPrims<2)
return false;
const PxU32* indexBase = params.mSource.getIndices();
const PxU32* prims = node->getPrimitives();
PxU64 offset = PxU64(prims - indexBase);
// In theory we should reshuffle the list but it would mean updating the remap table again.
// A way to avoid that would be to virtually split & sort the triangles directly in the BV2
// source tree, before the initial remap table is created.
//const PxU32 splitPrims = NbPrims/2; // ### actually should be the number in the last split in bv2
const PxU32 splitPrims = node->mNextSplit;
PxU32 j=0;
for(PxU32 ii=0;ii<2;ii++)
{
const PxU32 currentNb = ii==0 ? splitPrims : (nbPrims-splitPrims);
PxBounds3 bounds = PxBounds3::empty();
for(PxU32 k=0;k<currentNb;k++)
{
PX_ASSERT(prims[j] == offset+k);
PxU32 vref0, vref1, vref2;
getVertexReferences(vref0, vref1, vref2, prims[j], params.mMesh->getTris32(), params.mMesh->getTris16());
// PT: TODO: SIMD
const PxVec3* verts = params.mMesh->getVerts();
bounds.include(verts[vref0]);
bounds.include(verts[vref1]);
bounds.include(verts[vref2]);
j++;
}
PX_ASSERT(bounds.isInside(node->mBV));
const PxU64 primitiveIndex = (offset<<4)|(currentNb&15);
// SetupBounds(node4, i, node, context.mEpsilon);
node4->mBVData[i+ii].mAABB = bounds;
if(params.mEpsilon!=0.0f)
node4->mBVData[i+ii].mAABB.mExtents += PxVec3(params.mEpsilon);
node4->mBVData[i+ii].mData64 = (primitiveIndex<<1)|1;
offset += currentNb;
}
return true;
}
#endif
static BV4Node* setNode(const BV4_AABBTree& source, BV4Node* node4, PxU32 i, const AABBTreeNode* node, BV4BuildParams& params)
{
BV4Node* child = NULL;
if(node->isLeaf())
{
setPrimitive(source, node4, i, node, params.mEpsilon);
}
else
{
setupBounds(node4, i, node, params.mEpsilon);
params.mNbNodes++;
#ifdef GU_BV4_USE_NODE_POOLS
child = params.allocateNode();
#else
child = PX_NEW(BV4Node);
#endif
node4->mBVData[i].mData64 = size_t(child);
}
return child;
}
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
static inline PxBounds3 getMinMaxBox(const CenterExtents& box)
{
if(box.mExtents.x>=0.0f && box.mExtents.y>=0.0f && box.mExtents.z>=0.0f)
// if(!box.isEmpty()) // ### asserts!
return PxBounds3::centerExtents(box.mCenter, box.mExtents);
else
return PxBounds3::empty();
}
static void FigureOutPNS(BV4Node* node)
{
// ____A____
// P N
// __|__ __|__
// PP PN NP NN
const CenterExtents& box0 = node->mBVData[0].mAABB;
const CenterExtents& box1 = node->mBVData[1].mAABB;
const CenterExtents& box2 = node->mBVData[2].mAABB;
const CenterExtents& box3 = node->mBVData[3].mAABB;
// PT: TODO: SIMD, optimize
const PxBounds3 boxPP = getMinMaxBox(box0);
const PxBounds3 boxPN = getMinMaxBox(box1);
const PxBounds3 boxNP = getMinMaxBox(box2);
const PxBounds3 boxNN = getMinMaxBox(box3);
PxBounds3 boxP = boxPP; boxP.include(boxPN);
PxBounds3 boxN = boxNP; boxN.include(boxNN);
node->mBVData[0].mTempPNS = precomputeNodeSorting(boxP, boxN);
node->mBVData[1].mTempPNS = precomputeNodeSorting(boxPP, boxPN);
node->mBVData[2].mTempPNS = precomputeNodeSorting(boxNP, boxNN);
}
#endif
/*static bool hasTwoLeafChildren(const AABBTreeNode* current_node)
{
if(current_node->isLeaf())
return false;
const AABBTreeNode* P = current_node->getPos();
const AABBTreeNode* N = current_node->getNeg();
return P->isLeaf() && N->isLeaf();
}*/
static void buildBV4(const BV4_AABBTree& source, BV4Node* tmp, const AABBTreeNode* current_node, BV4BuildParams& params)
{
PX_ASSERT(!current_node->isLeaf());
// In the regular tree we have current node A, and:
// ____A____
// P N
// __|__ __|__
// PP PN NP NN
//
// For PNS we have:
// bit0 to sort P|N
// bit1 to sort PP|PN
// bit2 to sort NP|NN
//
// As much as possible we need to preserve the original order in BV4, if we want to reuse the same PNS bits.
//
// bit0|bit1|bit2 Order 8bits code
// 0 0 0 PP PN NP NN 0 1 2 3
// 0 0 1 PP PN NN NP 0 1 3 2
// 0 1 0 PN PP NP NN 1 0 2 3
// 0 1 1 PN PP NN NP 1 0 3 2
// 1 0 0 NP NN PP PN 2 3 0 1
// 1 0 1 NN NP PP PN 3 2 0 1
// 1 1 0 NP NN PN PP 2 3 1 0
// 1 1 1 NN NP PN PP 3 2 1 0
//
// So we can fetch/compute the sequence from the bits, combine it with limitations from the node type, and process the nodes in order. In theory.
// 8*8bits => the whole thing fits in a single 64bit register, so we could potentially use a "register LUT" here.
const AABBTreeNode* P = current_node->getPos();
const AABBTreeNode* N = current_node->getNeg();
const bool PLeaf = P->isLeaf();
const bool NLeaf = N->isLeaf();
if(PLeaf)
{
if(NLeaf)
{
// Case 1: P and N are both leaves:
// ____A____
// P N
// => store as (P,N) and keep bit0
#ifndef GU_BV4_FILL_GAPS
params.mStats[0]++;
// PN leaves => store 2 triangle pointers, lose 50% of node space
setPrimitive(source, tmp, 0, P, params.mEpsilon);
setPrimitive(source, tmp, 1, N, params.mEpsilon);
#else
{
PxU32 nextIndex = 2;
if(!splitPrimitives(params, tmp, 0, P))
{
setPrimitive(source, tmp, 0, P, params.mEpsilon);
nextIndex = 1;
}
if(!splitPrimitives(params, tmp, nextIndex, N))
setPrimitive(source, tmp, nextIndex, N, params.mEpsilon);
const PxU32 statIndex = tmp->getType();
if(statIndex==4)
params.mStats[3]++;
else if(statIndex==3)
params.mStats[1]++;
else if(statIndex==2)
params.mStats[0]++;
else
PX_ASSERT(0);
}
#endif
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT0
tmp->mBVData[0].mTempPNS = precomputeNodeSorting(P->mBV, N->mBV);
#endif
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
FigureOutPNS(tmp);
#endif
}
else
{
// Case 2: P leaf, N no leaf
// ____A____
// P N
// __|__
// NP NN
// => store as (P,NP,NN), keep bit0 and bit2
//#define NODE_FUSION
#ifdef NODE_FUSION
// P leaf => store 1 triangle pointers and 2 node pointers
// => 3 slots used, 25% wasted
const AABBTreeNode* NP = N->getPos();
const AABBTreeNode* NN = N->getNeg();
BV4Node* ChildNP;
BV4Node* ChildNN;
#ifdef GU_BV4_FILL_GAPS
if(splitPrimitives(params, tmp, 0, P))
{
// We used up the empty slot, continue as usual in slot 2
ChildNP = setNode(source, tmp, 2, NP, params);
ChildNN = setNode(source, tmp, 3, NN, params);
}
else
#endif
{
// We oouldn't split the prims, continue searching for a way to use the empty slot
setPrimitive(source, tmp, 0, P, params.mEpsilon);
PxU32 c=0;
if(hasTwoLeafChildren(NP))
{
// Drag the terminal leaves directly into this BV4 node, drop internal node NP
setPrimitive(source, tmp, 1, NP->getPos(), params.mEpsilon);
setPrimitive(source, tmp, 2, NP->getNeg(), params.mEpsilon);
ChildNP = NULL;
c=1;
}
else
{
ChildNP = setNode(source, tmp, 1, NP, params);
}
if(c==0 && hasTwoLeafChildren(NN))
{
// Drag the terminal leaves directly into this BV4 node, drop internal node NN
setPrimitive(source, tmp, 2, NN->getPos(), params.mEpsilon);
setPrimitive(source, tmp, 3, NN->getNeg(), params.mEpsilon);
ChildNN = NULL;
}
else
{
#ifdef GU_BV4_FILL_GAPS
if(c==0 && NN->isLeaf())
{
ChildNN = NULL;
if(!splitPrimitives(params, tmp, 2, NN))
setPrimitive(source, tmp, 2, NN, params.mEpsilon);
}
else
#endif
{
ChildNN = setNode(source, tmp, 2+c, NN, params);
}
}
}
const PxU32 statIndex = tmp->getType();
if(statIndex==4)
params.mStats[3]++;
else if(statIndex==3)
params.mStats[1]++;
else if(statIndex==2)
params.mStats[0]++;
else
PX_ASSERT(0);
#else
params.mStats[1]++;
// P leaf => store 1 triangle pointers and 2 node pointers
// => 3 slots used, 25% wasted
setPrimitive(source, tmp, 0, P, params.mEpsilon);
const AABBTreeNode* NP = N->getPos();
const AABBTreeNode* NN = N->getNeg();
BV4Node* ChildNP = setNode(source, tmp, 1, NP, params);
BV4Node* ChildNN = setNode(source, tmp, 2, NN, params);
#endif
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT0
tmp->mBVData[0].mTempPNS = precomputeNodeSorting(P->mBV, N->mBV);
tmp->mBVData[2].mTempPNS = precomputeNodeSorting(NP->mBV, NN->mBV);
#endif
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
FigureOutPNS(tmp);
#endif
if(ChildNP)
buildBV4(source, ChildNP, NP, params);
if(ChildNN)
buildBV4(source, ChildNN, NN, params);
}
}
else
{
if(NLeaf)
{
// Note: this case doesn't exist anymore because of the node reorganizing for shadow rays
// Case 3: P no leaf, N leaf
// ____A____
// P N
// __|__
// PP PN
// => store as (PP,PN,N), keep bit0 and bit1
params.mStats[2]++;
// N leaf => store 1 triangle pointers and 2 node pointers
// => 3 slots used, 25% wasted
setPrimitive(source, tmp, 2, N, params.mEpsilon);
//
const AABBTreeNode* PP = P->getPos();
const AABBTreeNode* PN = P->getNeg();
BV4Node* ChildPP = setNode(source, tmp, 0, PP, params);
BV4Node* ChildPN = setNode(source, tmp, 1, PN, params);
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT0
tmp->mBVData[0].mTempPNS = precomputeNodeSorting(P->mBV, N->mBV);
tmp->mBVData[1].mTempPNS = precomputeNodeSorting(PP->mBV, PN->mBV);
#endif
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
FigureOutPNS(tmp);
#endif
if(ChildPP)
buildBV4(source, ChildPP, PP, params);
if(ChildPN)
buildBV4(source, ChildPN, PN, params);
}
else
{
// Case 4: P and N are no leaves:
// => store as (PP,PN,NP,NN), keep bit0/bit1/bit2
params.mStats[3]++;
// No leaves => store 4 node pointers
const AABBTreeNode* PP = P->getPos();
const AABBTreeNode* PN = P->getNeg();
const AABBTreeNode* NP = N->getPos();
const AABBTreeNode* NN = N->getNeg();
BV4Node* ChildPP = setNode(source, tmp, 0, PP, params);
BV4Node* ChildPN = setNode(source, tmp, 1, PN, params);
BV4Node* ChildNP = setNode(source, tmp, 2, NP, params);
BV4Node* ChildNN = setNode(source, tmp, 3, NN, params);
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT0
tmp->mBVData[0].mTempPNS = precomputeNodeSorting(P->mBV, N->mBV);
tmp->mBVData[1].mTempPNS = precomputeNodeSorting(PP->mBV, PN->mBV);
tmp->mBVData[2].mTempPNS = precomputeNodeSorting(NP->mBV, NN->mBV);
#endif
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
FigureOutPNS(tmp);
#endif
if(ChildPP)
buildBV4(source, ChildPP, PP, params);
if(ChildPN)
buildBV4(source, ChildPN, PN, params);
if(ChildNP)
buildBV4(source, ChildNP, NP, params);
if(ChildNN)
buildBV4(source, ChildNN, NN, params);
}
}
}
#ifdef GU_BV4_USE_SLABS
static void computeMaxValues(const BV4Node* current, PxVec3& MinMax, PxVec3& MaxMax)
#else
static void computeMaxValues(const BV4Node* current, PxVec3& CMax, PxVec3& EMax)
#endif
{
for(PxU32 i=0; i<4; i++)
{
if(current->mBVData[i].mData64 != PX_INVALID_U64)
{
const CenterExtents& Box = current->mBVData[i].mAABB;
#ifdef GU_BV4_USE_SLABS
const PxVec3 Min = Box.mCenter - Box.mExtents;
const PxVec3 Max = Box.mCenter + Box.mExtents;
if(fabsf(Min.x)>MinMax.x) MinMax.x = fabsf(Min.x);
if(fabsf(Min.y)>MinMax.y) MinMax.y = fabsf(Min.y);
if(fabsf(Min.z)>MinMax.z) MinMax.z = fabsf(Min.z);
if(fabsf(Max.x)>MaxMax.x) MaxMax.x = fabsf(Max.x);
if(fabsf(Max.y)>MaxMax.y) MaxMax.y = fabsf(Max.y);
if(fabsf(Max.z)>MaxMax.z) MaxMax.z = fabsf(Max.z);
#else
if(fabsf(Box.mCenter.x)>CMax.x) CMax.x = fabsf(Box.mCenter.x);
if(fabsf(Box.mCenter.y)>CMax.y) CMax.y = fabsf(Box.mCenter.y);
if(fabsf(Box.mCenter.z)>CMax.z) CMax.z = fabsf(Box.mCenter.z);
if(fabsf(Box.mExtents.x)>EMax.x) EMax.x = fabsf(Box.mExtents.x);
if(fabsf(Box.mExtents.y)>EMax.y) EMax.y = fabsf(Box.mExtents.y);
if(fabsf(Box.mExtents.z)>EMax.z) EMax.z = fabsf(Box.mExtents.z);
#endif
if(!current->isLeaf(i))
{
const BV4Node* ChildNode = current->getChild(i);
#ifdef GU_BV4_USE_SLABS
computeMaxValues(ChildNode, MinMax, MaxMax);
#else
computeMaxValues(ChildNode, CMax, EMax);
#endif
}
}
}
}
template<class T>
static PX_FORCE_INLINE bool copyData(T* PX_RESTRICT dst, const BV4Node* PX_RESTRICT src, PxU32 i)
{
if(src->isLeaf(i))
{
if(src->mBVData[i].mData64 > 0xffffffff)
return false;
}
dst->mData = PxU32(src->mBVData[i].mData64);
//dst->mData = PxTo32(src->mBVData[i].mData);
// dst->mData = PxU32(src->mBVData[i].mData);
// dst->encodePNS(src->mBVData[i].mTempPNS);
return true;
}
namespace
{
struct flattenQParams
{
PxVec3 mCQuantCoeff;
PxVec3 mEQuantCoeff;
PxVec3 mCenterCoeff;
PxVec3 mExtentsCoeff;
};
}
template<class T>
static PX_FORCE_INLINE bool processNode(T* PX_RESTRICT data, const BV4Node* PX_RESTRICT current, PxU64* PX_RESTRICT nextIDs, const BV4Node** PX_RESTRICT childNodes, PxU32 i, PxU64& current_id, PxU32& nbToGo)
{
const BV4Node* childNode = current->getChild(i);
const PxU64 nextID = current_id;
#ifdef GU_BV4_USE_SLABS
current_id += 4;
#else
const PxU32 childSize = childNode->getType();
current_id += childSize;
#endif
const PxU32 childType = (childNode->getType() - 2) << 1;
const PxU64 data64 = size_t(childType + (nextID << GU_BV4_CHILD_OFFSET_SHIFT_COUNT));
if(data64 <= 0xffffffff)
{
data[i].mData = PxU32(data64);
}
else
{
outputError<PxErrorCode::eINTERNAL_ERROR>(__LINE__, "Too many child nodes. Adjust PxMidphaseDesc::mBVH34Desc::numPrimsPerLeaf or reduce the number of triangles in the mesh.");
return false;
}
//PX_ASSERT(data[i].mData == size_t(childType+(nextID<<3)));
nextIDs[nbToGo] = nextID;
childNodes[nbToGo] = childNode;
nbToGo++;
#ifdef GU_BV4_PRECOMPUTED_NODE_SORT
data[i].encodePNS(current->mBVData[i].mTempPNS);
#endif
return true;
}
static bool flattenQ(const flattenQParams& params, BVDataPackedQ* const dest, const PxU64 box_id, PxU64& current_id, const BV4Node* current, PxU32& max_depth, PxU32& current_depth)
{
// Entering a new node => increase depth
current_depth++;
// Keep track of max depth
if(current_depth>max_depth)
max_depth = current_depth;
// dest[box_id] = *current;
const PxU32 CurrentType = current->getType();
for(PxU32 i=0; i<CurrentType; i++)
{
const CenterExtents& Box = current->mBVData[i].mAABB;
#ifdef GU_BV4_USE_SLABS
const PxVec3 m = Box.mCenter - Box.mExtents;
const PxVec3 M = Box.mCenter + Box.mExtents;
dest[box_id + i].mAABB.mData[0].mCenter = PxI16(m.x * params.mCQuantCoeff.x);
dest[box_id + i].mAABB.mData[1].mCenter = PxI16(m.y * params.mCQuantCoeff.y);
dest[box_id + i].mAABB.mData[2].mCenter = PxI16(m.z * params.mCQuantCoeff.z);
dest[box_id + i].mAABB.mData[0].mExtents = PxU16(PxI16(M.x * params.mEQuantCoeff.x));
dest[box_id + i].mAABB.mData[1].mExtents = PxU16(PxI16(M.y * params.mEQuantCoeff.y));
dest[box_id + i].mAABB.mData[2].mExtents = PxU16(PxI16(M.z * params.mEQuantCoeff.z));
if (1)
{
for (PxU32 j = 0; j<3; j++)
{
// Dequantize the min/max
// const float qmin = float(dest[box_id+i].mAABB.mData[j].mCenter) * mCenterCoeff[j];
// const float qmax = float(PxI16(dest[box_id+i].mAABB.mData[j].mExtents)) * mExtentsCoeff[j];
// Compare real & dequantized values
/* if(qmax<M[j] || qmin>m[j])
{
int stop=1;
}*/
bool CanLeave;
do
{
CanLeave = true;
const float qmin = float(dest[box_id + i].mAABB.mData[j].mCenter) * params.mCenterCoeff[j];
const float qmax = float(PxI16(dest[box_id + i].mAABB.mData[j].mExtents)) * params.mExtentsCoeff[j];
if (qmax<M[j])
{
// if(dest[box_id+i].mAABB.mData[j].mExtents!=0xffff)
if (dest[box_id + i].mAABB.mData[j].mExtents != 0x7fff)
{
dest[box_id + i].mAABB.mData[j].mExtents++;
CanLeave = false;
}
}
if (qmin>m[j])
{
if (dest[box_id + i].mAABB.mData[j].mCenter)
{
dest[box_id + i].mAABB.mData[j].mCenter--;
CanLeave = false;
}
}
} while (!CanLeave);
}
}
#else // GU_BV4_USE_SLABS
dest[box_id + i].mAABB.mData[0].mCenter = PxI16(Box.mCenter.x * CQuantCoeff.x);
dest[box_id + i].mAABB.mData[1].mCenter = PxI16(Box.mCenter.y * CQuantCoeff.y);
dest[box_id + i].mAABB.mData[2].mCenter = PxI16(Box.mCenter.z * CQuantCoeff.z);
dest[box_id + i].mAABB.mData[0].mExtents = PxU16(Box.mExtents.x * EQuantCoeff.x);
dest[box_id + i].mAABB.mData[1].mExtents = PxU16(Box.mExtents.y * EQuantCoeff.y);
dest[box_id + i].mAABB.mData[2].mExtents = PxU16(Box.mExtents.z * EQuantCoeff.z);
// Fix quantized boxes
if (1)
{
// Make sure the quantized box is still valid
const PxVec3 Max = Box.mCenter + Box.mExtents;
const PxVec3 Min = Box.mCenter - Box.mExtents;
// For each axis
for (PxU32 j = 0; j<3; j++)
{ // Dequantize the box center
const float qc = float(dest[box_id + i].mAABB.mData[j].mCenter) * mCenterCoeff[j];
bool FixMe = true;
do
{ // Dequantize the box extent
const float qe = float(dest[box_id + i].mAABB.mData[j].mExtents) * mExtentsCoeff[j];
// Compare real & dequantized values
if (qc + qe<Max[j] || qc - qe>Min[j]) dest[box_id + i].mAABB.mData[j].mExtents++;
else FixMe = false;
// Prevent wrapping
if (!dest[box_id + i].mAABB.mData[j].mExtents)
{
dest[box_id + i].mAABB.mData[j].mExtents = 0xffff;
FixMe = false;
}
} while (FixMe);
}
}
#endif // GU_BV4_USE_SLABS
if(!copyData(&dest[box_id + i], current, i))
return false;
}
PxU32 NbToGo = 0;
PxU64 NextIDs[4] = { PX_INVALID_U64, PX_INVALID_U64, PX_INVALID_U64, PX_INVALID_U64 };
const BV4Node* ChildNodes[4] = { NULL, NULL, NULL, NULL };
BVDataPackedQ* data = dest + box_id;
for(PxU32 i=0; i<4; i++)
{
if(current->mBVData[i].mData64 != PX_INVALID_U64 && !current->isLeaf(i))
{
if(!processNode(data, current, NextIDs, ChildNodes, i, current_id, NbToGo))
return false;
//#define DEPTH_FIRST
#ifdef DEPTH_FIRST
if(!flattenQ(params, dest, NextID, current_id, ChildNode, max_depth, current_depth, CQuantCoeff, EQuantCoeff, mCenterCoeff, mExtentsCoeff))
return false;
current_depth--;
#endif
}
#ifdef GU_BV4_USE_SLABS
if (current->mBVData[i].mData64 == PX_INVALID_U64)
{
data[i].mAABB.mData[0].mExtents = 0;
data[i].mAABB.mData[1].mExtents = 0;
data[i].mAABB.mData[2].mExtents = 0;
data[i].mAABB.mData[0].mCenter = 0;
data[i].mAABB.mData[1].mCenter = 0;
data[i].mAABB.mData[2].mCenter = 0;
data[i].mData = PX_INVALID_U32;
}
#endif
}
#ifndef DEPTH_FIRST
for(PxU32 i=0; i<NbToGo; i++)
{
if(!flattenQ(params, dest, NextIDs[i], current_id, ChildNodes[i], max_depth, current_depth))
return false;
current_depth--;
}
#endif
#ifndef GU_BV4_USE_NODE_POOLS
PX_DELETE(current);
#endif
return true;
}
static bool flattenNQ(BVDataPackedNQ* const dest, const PxU64 box_id, PxU64& current_id, const BV4Node* current, PxU32& max_depth, PxU32& current_depth)
{
// Entering a new node => increase depth
current_depth++;
// Keep track of max depth
if(current_depth>max_depth)
max_depth = current_depth;
// dest[box_id] = *current;
const PxU32 CurrentType = current->getType();
for(PxU32 i=0; i<CurrentType; i++)
{
#ifdef GU_BV4_USE_SLABS
// Compute min & max right here. Store temp as Center/Extents = Min/Max
const CenterExtents& Box = current->mBVData[i].mAABB;
dest[box_id + i].mAABB.mCenter = Box.mCenter - Box.mExtents;
dest[box_id + i].mAABB.mExtents = Box.mCenter + Box.mExtents;
#else // GU_BV4_USE_SLABS
dest[box_id + i].mAABB = current->mBVData[i].mAABB;
#endif // GU_BV4_USE_SLABS
if(!copyData(&dest[box_id + i], current, i))
return false;
}
PxU32 NbToGo = 0;
PxU64 NextIDs[4] = { PX_INVALID_U64, PX_INVALID_U64, PX_INVALID_U64, PX_INVALID_U64 };
const BV4Node* ChildNodes[4] = { NULL, NULL, NULL, NULL };
BVDataPackedNQ* data = dest + box_id;
for(PxU32 i=0; i<4; i++)
{
if(current->mBVData[i].mData64 != PX_INVALID_U64 && !current->isLeaf(i))
{
if(!processNode(data, current, NextIDs, ChildNodes, i, current_id, NbToGo))
return false;
//#define DEPTH_FIRST
#ifdef DEPTH_FIRST
if(!flattenNQ(dest, NextID, current_id, ChildNode, max_depth, current_depth))
return false;
current_depth--;
#endif
}
#ifdef GU_BV4_USE_SLABS
if (current->mBVData[i].mData64 == PX_INVALID_U64)
{
data[i].mAABB.mCenter = PxVec3(0.0f);
data[i].mAABB.mExtents = PxVec3(0.0f);
data[i].mData = PX_INVALID_U32;
}
#endif
}
#ifndef DEPTH_FIRST
for(PxU32 i=0; i<NbToGo; i++)
{
if(!flattenNQ(dest, NextIDs[i], current_id, ChildNodes[i], max_depth, current_depth))
return false;
current_depth--;
}
#endif
#ifndef GU_BV4_USE_NODE_POOLS
PX_DELETE(current);
#endif
return true;
}
static bool buildBV4FromRoot(BV4Tree& tree, BV4Node* Root, BV4BuildParams& Params, bool quantized, float epsilon)
{
GU_PROFILE_ZONE("....buildBV4FromRoot")
BV4Tree* T = &tree;
T->mQuantized = quantized;
// Version with variable-sized nodes in single stream
{
const PxU32 NbSingleNodes = Params.mStats[0] * 2 + (Params.mStats[1] + Params.mStats[2]) * 3 + Params.mStats[3] * 4;
PxU64 CurID = Root->getType();
PxU32 InitData = PX_INVALID_U32;
#ifdef GU_BV4_USE_SLABS
PX_UNUSED(NbSingleNodes);
const PxU32 NbNeeded = (Params.mStats[0] + Params.mStats[1] + Params.mStats[2] + Params.mStats[3]) * 4;
// PT: TODO: refactor with code in BV4Tree::load
// BVDataPacked* Nodes = reinterpret_cast<BVDataPacked*>(PX_ALLOC(sizeof(BVDataPacked)*NbNeeded, "BV4 nodes")); // PT: PX_NEW breaks alignment here
// BVDataPacked* Nodes = PX_NEW(BVDataPacked)[NbNeeded];
void* nodes;
{
const PxU32 nodeSize = T->mQuantized ? sizeof(BVDataPackedQ) : sizeof(BVDataPackedNQ);
const PxU32 dataSize = nodeSize*NbNeeded;
nodes = PX_ALLOC(dataSize, "BV4 nodes"); // PT: PX_NEW breaks alignment here
}
if (CurID == 2)
{
InitData = 0;
}
else if (CurID == 3)
{
InitData = 2;
}
else if (CurID == 4)
{
InitData = 4;
}
CurID = 4;
// PxU32 CurID = 4;
// PxU32 InitData = 4;
#else
BVDataPacked* Nodes = PX_NEW(BVDataPacked)[NbSingleNodes];
if (CurID == 2)
{
InitData = 0;
}
else if (CurID == 3)
{
InitData = 2;
}
else if (CurID == 4)
{
InitData = 4;
}
#endif
T->mInitData = InitData;
PxU32 MaxDepth = 0;
PxU32 CurrentDepth = 0;
bool buildStatus;
if(T->mQuantized)
{
flattenQParams params;
#ifdef GU_BV4_USE_SLABS
PxVec3 MinQuantCoeff, MaxQuantCoeff;
// Get max values
PxVec3 MinMax(-FLT_MAX);
PxVec3 MaxMax(-FLT_MAX);
computeMaxValues(Root, MinMax, MaxMax);
const PxU32 nbm = 15;
// Compute quantization coeffs
const float MinCoeff = float((1 << nbm) - 1);
const float MaxCoeff = float((1 << nbm) - 1);
MinQuantCoeff.x = MinMax.x != 0.0f ? MinCoeff / MinMax.x : 0.0f;
MinQuantCoeff.y = MinMax.y != 0.0f ? MinCoeff / MinMax.y : 0.0f;
MinQuantCoeff.z = MinMax.z != 0.0f ? MinCoeff / MinMax.z : 0.0f;
MaxQuantCoeff.x = MaxMax.x != 0.0f ? MaxCoeff / MaxMax.x : 0.0f;
MaxQuantCoeff.y = MaxMax.y != 0.0f ? MaxCoeff / MaxMax.y : 0.0f;
MaxQuantCoeff.z = MaxMax.z != 0.0f ? MaxCoeff / MaxMax.z : 0.0f;
// Compute and save dequantization coeffs
T->mCenterOrMinCoeff.x = MinMax.x / MinCoeff;
T->mCenterOrMinCoeff.y = MinMax.y / MinCoeff;
T->mCenterOrMinCoeff.z = MinMax.z / MinCoeff;
T->mExtentsOrMaxCoeff.x = MaxMax.x / MaxCoeff;
T->mExtentsOrMaxCoeff.y = MaxMax.y / MaxCoeff;
T->mExtentsOrMaxCoeff.z = MaxMax.z / MaxCoeff;
params.mCQuantCoeff = MinQuantCoeff;
params.mEQuantCoeff = MaxQuantCoeff;
#else
// Get max values
PxVec3 CMax(-FLT_MAX);
PxVec3 EMax(-FLT_MAX);
computeMaxValues(Root, CMax, EMax);
const PxU32 nbc = 15;
const PxU32 nbe = 16;
// const PxU32 nbc=7;
// const PxU32 nbe=8;
const float UnitQuantError = 2.0f / 65535.0f;
EMax.x += CMax.x*UnitQuantError;
EMax.y += CMax.y*UnitQuantError;
EMax.z += CMax.z*UnitQuantError;
// Compute quantization coeffs
const float CCoeff = float((1 << nbc) - 1);
CQuantCoeff.x = CMax.x != 0.0f ? CCoeff / CMax.x : 0.0f;
CQuantCoeff.y = CMax.y != 0.0f ? CCoeff / CMax.y : 0.0f;
CQuantCoeff.z = CMax.z != 0.0f ? CCoeff / CMax.z : 0.0f;
const float ECoeff = float((1 << nbe) - 32);
EQuantCoeff.x = EMax.x != 0.0f ? ECoeff / EMax.x : 0.0f;
EQuantCoeff.y = EMax.y != 0.0f ? ECoeff / EMax.y : 0.0f;
EQuantCoeff.z = EMax.z != 0.0f ? ECoeff / EMax.z : 0.0f;
// Compute and save dequantization coeffs
T->mCenterOrMinCoeff.x = CMax.x / CCoeff;
T->mCenterOrMinCoeff.y = CMax.y / CCoeff;
T->mCenterOrMinCoeff.z = CMax.z / CCoeff;
T->mExtentsOrMaxCoeff.x = EMax.x / ECoeff;
T->mExtentsOrMaxCoeff.y = EMax.y / ECoeff;
T->mExtentsOrMaxCoeff.z = EMax.z / ECoeff;
params.mCQuantCoeff = CQuantCoeff;
params.mEQuantCoeff = EQuantCoeff;
#endif
params.mCenterCoeff = T->mCenterOrMinCoeff;
params.mExtentsCoeff = T->mExtentsOrMaxCoeff;
buildStatus = flattenQ(params, reinterpret_cast<BVDataPackedQ*>(nodes), 0, CurID, Root, MaxDepth, CurrentDepth);
}
else
{
buildStatus = flattenNQ(reinterpret_cast<BVDataPackedNQ*>(nodes), 0, CurID, Root, MaxDepth, CurrentDepth);
}
#ifdef GU_BV4_USE_NODE_POOLS
Params.releaseNodes();
#endif
if(!buildStatus)
{
T->mNodes = nodes;
return false;
}
#ifdef GU_BV4_USE_SLABS
// PT: TODO: revisit this, don't duplicate everything
if(T->mQuantized)
{
BVDataPackedQ* _nodes = reinterpret_cast<BVDataPackedQ*>(nodes);
PX_COMPILE_TIME_ASSERT(sizeof(BVDataSwizzledQ) == sizeof(BVDataPackedQ) * 4);
BVDataPackedQ* Copy = PX_ALLOCATE(BVDataPackedQ, NbNeeded, "BVDataPackedQ");
PxMemCopy(Copy, nodes, sizeof(BVDataPackedQ)*NbNeeded);
for (PxU32 i = 0; i<NbNeeded / 4; i++)
{
const BVDataPackedQ* Src = Copy + i * 4;
BVDataSwizzledQ* Dst = reinterpret_cast<BVDataSwizzledQ*>(_nodes + i * 4);
for (PxU32 j = 0; j<4; j++)
{
// We previously stored m/M within c/e so we just need to swizzle now
const QuantizedAABB& Box = Src[j].mAABB;
Dst->mX[j].mMin = Box.mData[0].mCenter;
Dst->mY[j].mMin = Box.mData[1].mCenter;
Dst->mZ[j].mMin = Box.mData[2].mCenter;
Dst->mX[j].mMax = PxI16(Box.mData[0].mExtents);
Dst->mY[j].mMax = PxI16(Box.mData[1].mExtents);
Dst->mZ[j].mMax = PxI16(Box.mData[2].mExtents);
Dst->mData[j] = Src[j].mData;
}
}
PX_FREE(Copy);
}
else
{
BVDataPackedNQ* _nodes = reinterpret_cast<BVDataPackedNQ*>(nodes);
PX_COMPILE_TIME_ASSERT(sizeof(BVDataSwizzledNQ) == sizeof(BVDataPackedNQ) * 4);
BVDataPackedNQ* Copy = PX_ALLOCATE(BVDataPackedNQ, NbNeeded, "BVDataPackedNQ");
PxMemCopy(Copy, nodes, sizeof(BVDataPackedNQ)*NbNeeded);
for (PxU32 i = 0; i<NbNeeded / 4; i++)
{
const BVDataPackedNQ* Src = Copy + i * 4;
BVDataSwizzledNQ* Dst = reinterpret_cast<BVDataSwizzledNQ*>(_nodes + i * 4);
for (PxU32 j = 0; j<4; j++)
{
// We previously stored m/M within c/e so we just need to swizzle now
const CenterExtents& Box = Src[j].mAABB;
Dst->mMinX[j] = Box.mCenter.x;
Dst->mMinY[j] = Box.mCenter.y;
Dst->mMinZ[j] = Box.mCenter.z;
Dst->mMaxX[j] = Box.mExtents.x;
Dst->mMaxY[j] = Box.mExtents.y;
Dst->mMaxZ[j] = Box.mExtents.z;
Dst->mData[j] = Src[j].mData;
}
}
PX_FREE(Copy);
if(0)
{
const PxVec3 eps(epsilon);
float maxError = 0.0f;
PxU32 nb = NbNeeded/4;
BVDataSwizzledNQ* data = reinterpret_cast<BVDataSwizzledNQ*>(nodes);
while(nb--)
{
BVDataSwizzledNQ* current = data + nb;
for(PxU32 j=0;j<4;j++)
{
if(current->getChildData(j)==PX_INVALID_U32)
continue;
const PxBounds3 localBox( PxVec3(current->mMinX[j], current->mMinY[j], current->mMinZ[j]),
PxVec3(current->mMaxX[j], current->mMaxY[j], current->mMaxZ[j]));
PxBounds3 refitBox;
refitBox.setEmpty();
if(current->isLeaf(j))
{
PxU32 primIndex = current->getPrimitive(j);
PxU32 nbToGo = getNbPrimitives(primIndex);
do
{
PX_ASSERT(primIndex<T->mMeshInterface->getNbPrimitives());
T->mMeshInterface->refit(primIndex, refitBox);
primIndex++;
}while(nbToGo--);
}
else
{
PxU32 childOffset = current->getChildOffset(j);
PX_ASSERT(!(childOffset&3));
childOffset>>=2;
PX_ASSERT(childOffset>nb);
const PxU32 childType = current->getChildType(j);
const BVDataSwizzledNQ* next = data + childOffset;
{
if(childType>1)
{
const PxBounds3 childBox( PxVec3(next->mMinX[3], next->mMinY[3], next->mMinZ[3]),
PxVec3(next->mMaxX[3], next->mMaxY[3], next->mMaxZ[3]));
refitBox.include(childBox);
}
if(childType>0)
{
const PxBounds3 childBox( PxVec3(next->mMinX[2], next->mMinY[2], next->mMinZ[2]),
PxVec3(next->mMaxX[2], next->mMaxY[2], next->mMaxZ[2]));
refitBox.include(childBox);
}
{
const PxBounds3 childBox( PxVec3(next->mMinX[1], next->mMinY[1], next->mMinZ[1]),
PxVec3(next->mMaxX[1], next->mMaxY[1], next->mMaxZ[1]));
refitBox.include(childBox);
}
{
const PxBounds3 childBox( PxVec3(next->mMinX[0], next->mMinY[0], next->mMinZ[0]),
PxVec3(next->mMaxX[0], next->mMaxY[0], next->mMaxZ[0]));
refitBox.include(childBox);
}
}
}
refitBox.minimum -= eps;
refitBox.maximum += eps;
{
float error = (refitBox.minimum - localBox.minimum).magnitude();
if(error>maxError)
maxError = error;
}
{
float error = (refitBox.maximum - localBox.maximum).magnitude();
if(error>maxError)
maxError = error;
}
}
}
printf("maxError: %f\n", double(maxError));
}
}
PX_ASSERT(CurID == NbNeeded);
T->mNbNodes = NbNeeded;
#else
PX_ASSERT(CurID == NbSingleNodes);
T->mNbNodes = NbSingleNodes;
#endif
T->mNodes = nodes;
}
return true;
}
static bool buildBV4Internal(BV4Tree& tree, const BV4_AABBTree& source, SourceMeshBase* mesh, float epsilon, bool quantized)
{
GU_PROFILE_ZONE("..buildBV4Internal")
if(mesh->getNbPrimitives()<=4)
return tree.init(mesh, source.getBV());
{
GU_PROFILE_ZONE("....CheckMD")
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)
{
PxSwap(*P, *N);
PxSwap(P, N);
}
}
_check(P);
_check(N);
}
};
Local::_check(const_cast<AABBTreeNode*>(source.getNodes()));
}
// PT: not sure what the equivalent would be for tet-meshes here
SourceMesh* triMesh = NULL;
if(mesh->getMeshType()==SourceMeshBase::TRI_MESH)
triMesh = static_cast<SourceMesh*>(mesh);
BV4BuildParams Params(source, triMesh, epsilon);
Params.mNbNodes=1; // Root node
Params.mStats[0]=0;
Params.mStats[1]=0;
Params.mStats[2]=0;
Params.mStats[3]=0;
#ifdef GU_BV4_USE_NODE_POOLS
BV4Node* Root = Params.allocateNode();
#else
BV4Node* Root = PX_NEW(BV4Node);
#endif
{
GU_PROFILE_ZONE("....buildBV4")
buildBV4(source, Root, source.getNodes(), Params);
}
if(!tree.init(mesh, source.getBV()))
return false;
return buildBV4FromRoot(tree, Root, Params, quantized, epsilon);
}
/////
#define REORDER_STATS_SIZE 16
struct ReorderData
{
public:
PxU32* mOrder;
PxU32 mNbPrimsPerLeaf;
PxU32 mIndex;
PxU32 mNbPrims;
PxU32 mStats[REORDER_STATS_SIZE];
const SourceMeshBase* mMesh;
};
static bool gReorderCallback(const AABBTreeNode* current, PxU32 /*depth*/, void* userData)
{
ReorderData* Data = reinterpret_cast<ReorderData*>(userData);
if(current->isLeaf())
{
const PxU32 n = current->getNbPrimitives();
PX_ASSERT(n<=Data->mNbPrimsPerLeaf);
Data->mStats[n]++;
PxU32* Prims = const_cast<PxU32*>(current->getPrimitives());
for(PxU32 i=0;i<n;i++)
{
PX_ASSERT(Prims[i]<Data->mNbPrims);
Data->mOrder[Data->mIndex] = Prims[i];
PX_ASSERT(Data->mIndex<Data->mNbPrims);
Prims[i] = Data->mIndex;
Data->mIndex++;
}
}
return true;
}
bool physx::Gu::buildBV4Ex(BV4Tree& tree, SourceMeshBase& mesh, float epsilon, PxU32 nbPrimitivePerLeaf, bool quantized, BV4_BuildStrategy strategy)
{
//either number of triangle or number of tetrahedron
const PxU32 nbPrimitives = mesh.getNbPrimitives();
BV4_AABBTree Source;
{
GU_PROFILE_ZONE("..BuildBV4Ex_buildFromMesh")
if(!Source.buildFromMesh(mesh, nbPrimitivePerLeaf, strategy))
return false;
}
{
GU_PROFILE_ZONE("..BuildBV4Ex_remap")
PxU32* orderArray = PX_ALLOCATE(PxU32, nbPrimitives, "BV4");
ReorderData RD;
RD.mMesh = &mesh;
RD.mOrder = orderArray;
RD.mNbPrimsPerLeaf = nbPrimitivePerLeaf;
RD.mIndex = 0;
RD.mNbPrims = nbPrimitives;
for(PxU32 i=0;i<REORDER_STATS_SIZE;i++)
RD.mStats[i] = 0;
Source.walk(gReorderCallback, &RD);
PX_ASSERT(RD.mIndex== nbPrimitives);
mesh.remapTopology(orderArray);
PX_FREE(orderArray);
// for(PxU32 i=0;i<16;i++)
// printf("%d: %d\n", i, RD.mStats[i]);
}
if(mesh.getNbPrimitives() <= nbPrimitivePerLeaf)
return tree.init(&mesh, Source.getBV());
return buildBV4Internal(tree, Source, &mesh, epsilon, quantized);
}