From c01469dddabe404506ef3a64542e8423f9e11f2c Mon Sep 17 00:00:00 2001 From: Aki Date: Sun, 30 Jan 2022 17:44:05 +0100 Subject: Converted Opcode and Ice into unix newlines format --- Opcode/OPC_AABBTree.cpp | 1146 +++++++++++++++++++++++------------------------ 1 file changed, 573 insertions(+), 573 deletions(-) (limited to 'Opcode/OPC_AABBTree.cpp') diff --git a/Opcode/OPC_AABBTree.cpp b/Opcode/OPC_AABBTree.cpp index 166cb0f..bc1a4e0 100644 --- a/Opcode/OPC_AABBTree.cpp +++ b/Opcode/OPC_AABBTree.cpp @@ -1,573 +1,573 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/* - * OPCODE - Optimized Collision Detection - * Copyright (C) 2001 Pierre Terdiman - * Homepage: http://www.codercorner.com/Opcode.htm - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Contains code for a versatile AABB tree. - * \file OPC_AABBTree.cpp - * \author Pierre Terdiman - * \date March, 20, 2001 - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Contains a generic AABB tree node. - * - * \class AABBTreeNode - * \author Pierre Terdiman - * \version 1.3 - * \date March, 20, 2001 -*/ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Contains a generic AABB tree. - * This is a vanilla AABB tree, without any particular optimization. It contains anonymous references to - * user-provided primitives, which can theoretically be anything - triangles, boxes, etc. Each primitive - * is surrounded by an AABB, regardless of the primitive's nature. When the primitive is a triangle, the - * resulting tree can be converted into an optimized tree. If the primitive is a box, the resulting tree - * can be used for culling - VFC or occlusion -, assuming you cull on a mesh-by-mesh basis (modern way). - * - * \class AABBTree - * \author Pierre Terdiman - * \version 1.3 - * \date March, 20, 2001 -*/ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -// Precompiled Header -#include "StdAfx.h" - -using namespace Opcode; - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Constructor. - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -AABBTreeNode::AABBTreeNode() : - mPos (null), -#ifndef OPC_NO_NEG_VANILLA_TREE - mNeg (null), -#endif - mNbPrimitives (0), - mNodePrimitives (null) -{ -#ifdef OPC_USE_TREE_COHERENCE - mBitmask = 0; -#endif -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Destructor. - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -AABBTreeNode::~AABBTreeNode() -{ - // Opcode 1.3: - const AABBTreeNode* Pos = GetPos(); - const AABBTreeNode* Neg = GetNeg(); -#ifndef OPC_NO_NEG_VANILLA_TREE - if(!(mPos&1)) DELETESINGLE(Pos); - if(!(mNeg&1)) DELETESINGLE(Neg); -#else - if(!(mPos&1)) DELETEARRAY(Pos); -#endif - mNodePrimitives = null; // This was just a shortcut to the global list => no release - mNbPrimitives = 0; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Splits the node along a given axis. - * The list of indices is reorganized according to the split values. - * \param axis [in] splitting axis index - * \param builder [in] the tree builder - * \return the number of primitives assigned to the first child - * \warning this method reorganizes the internal list of primitives - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -udword AABBTreeNode::Split(udword axis, AABBTreeBuilder* builder) -{ - // Get node split value - float SplitValue = builder->GetSplittingValue(mNodePrimitives, mNbPrimitives, mBV, axis); - - udword NbPos = 0; - // Loop through all node-related primitives. Their indices range from mNodePrimitives[0] to mNodePrimitives[mNbPrimitives-1]. - // Those indices map the global list in the tree builder. - for(udword i=0;iGetSplittingValue(Index, axis); - - // Reorganize the list of indices in this order: positive - negative. - if(PrimitiveValue > SplitValue) - { - // Swap entries - udword Tmp = mNodePrimitives[i]; - mNodePrimitives[i] = mNodePrimitives[NbPos]; - mNodePrimitives[NbPos] = Tmp; - // Count primitives assigned to positive space - NbPos++; - } - } - return NbPos; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Subdivides the node. - * - * N - * / \ - * / \ - * N/2 N/2 - * / \ / \ - * N/4 N/4 N/4 N/4 - * (etc) - * - * A well-balanced tree should have a O(log n) depth. - * A degenerate tree would have a O(n) depth. - * Note a perfectly-balanced tree is not well-suited to collision detection anyway. - * - * \param builder [in] the tree builder - * \return true if success - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -bool AABBTreeNode::Subdivide(AABBTreeBuilder* builder) -{ - // Checkings - if(!builder) return false; - - // Stop subdividing if we reach a leaf node. This is always performed here, - // else we could end in trouble if user overrides this. - if(mNbPrimitives==1) return true; - - // Let the user validate the subdivision - if(!builder->ValidateSubdivision(mNodePrimitives, mNbPrimitives, mBV)) return true; - - bool ValidSplit = true; // Optimism... - udword NbPos; - if(builder->mSettings.mRules & SPLIT_LARGEST_AXIS) - { - // Find the largest axis to split along - IcePoint Extents; mBV.GetExtents(Extents); // Box extents - udword Axis = Extents.LargestAxis(); // Index of largest axis - - // Split along the axis - NbPos = Split(Axis, builder); - - // Check split validity - if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false; - } - else if(builder->mSettings.mRules & SPLIT_SPLATTER_POINTS) - { - // Compute the means - IcePoint Means(0.0f, 0.0f, 0.0f); - for(udword i=0;iGetSplittingValue(Index, 0); - Means.y+=builder->GetSplittingValue(Index, 1); - Means.z+=builder->GetSplittingValue(Index, 2); - } - Means/=float(mNbPrimitives); - - // Compute variances - IcePoint Vars(0.0f, 0.0f, 0.0f); - for(udword i=0;iGetSplittingValue(Index, 0); - float Cy = builder->GetSplittingValue(Index, 1); - float Cz = builder->GetSplittingValue(Index, 2); - Vars.x += (Cx - Means.x)*(Cx - Means.x); - Vars.y += (Cy - Means.y)*(Cy - Means.y); - Vars.z += (Cz - Means.z)*(Cz - Means.z); - } - Vars/=float(mNbPrimitives-1); - - // Choose axis with greatest variance - udword Axis = Vars.LargestAxis(); - - // Split along the axis - NbPos = Split(Axis, builder); - - // Check split validity - if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false; - } - else if(builder->mSettings.mRules & SPLIT_BALANCED) - { - // Test 3 axis, take the best - float Results[3]; - NbPos = Split(0, builder); Results[0] = float(NbPos)/float(mNbPrimitives); - NbPos = Split(1, builder); Results[1] = float(NbPos)/float(mNbPrimitives); - NbPos = Split(2, builder); Results[2] = float(NbPos)/float(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]; - udword Min=0; - if(Results[1]mSettings.mRules & SPLIT_BEST_AXIS) - { - // Test largest, then middle, then smallest axis... - - // Sort axis - IcePoint Extents; mBV.GetExtents(Extents); // Box extents - udword SortedAxis[] = { 0, 1, 2 }; - float* Keys = (float*)&Extents.x; - for(udword j=0;j<3;j++) - { - for(udword i=0;i<2;i++) - { - if(Keys[SortedAxis[i]]mSettings.mRules & SPLIT_FIFTY) - { - // Don't even bother splitting (mainly a performance test) - NbPos = mNbPrimitives>>1; - } - else return false; // Unknown splitting rules - - // 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(builder->mSettings.mRules&SPLIT_COMPLETE) - if(builder->mSettings.mLimit==1) - { - builder->IncreaseNbInvalidSplits(); - NbPos = mNbPrimitives>>1; - } - else return true; - } - - // Now create children and assign their pointers. - if(builder->mNodeBase) - { - // We use a pre-allocated linear pool for complete trees [Opcode 1.3] - AABBTreeNode* Pool = (AABBTreeNode*)builder->mNodeBase; - udword Count = builder->GetCount() - 1; // Count begins to 1... - // Set last bit to tell it shouldn't be freed ### pretty ugly, find a better way. Maybe one bit in mNbPrimitives - ASSERT(!(udword(&Pool[Count+0])&1)); - ASSERT(!(udword(&Pool[Count+1])&1)); - mPos = udword(&Pool[Count+0])|1; -#ifndef OPC_NO_NEG_VANILLA_TREE - mNeg = udword(&Pool[Count+1])|1; -#endif - } - else - { - // Non-complete trees and/or Opcode 1.2 allocate nodes on-the-fly -#ifndef OPC_NO_NEG_VANILLA_TREE - mPos = (udword)new AABBTreeNode; CHECKALLOC(mPos); - mNeg = (udword)new AABBTreeNode; CHECKALLOC(mNeg); -#else - AABBTreeNode* PosNeg = new AABBTreeNode[2]; - CHECKALLOC(PosNeg); - mPos = (udword)PosNeg; -#endif - } - - // Update stats - builder->IncreaseCount(2); - - // Assign children - AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); - AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); - Pos->mNodePrimitives = &mNodePrimitives[0]; - Pos->mNbPrimitives = NbPos; - Neg->mNodePrimitives = &mNodePrimitives[NbPos]; - Neg->mNbPrimitives = mNbPrimitives - NbPos; - - return true; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Recursive hierarchy building in a top-down fashion. - * \param builder [in] the tree builder - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -void AABBTreeNode::_BuildHierarchy(AABBTreeBuilder* builder) -{ - // 1) Compute the global box for current node. The box is stored in mBV. - builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV); - - // 2) Subdivide current node - Subdivide(builder); - - // 3) Recurse - AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); - AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); - if(Pos) Pos->_BuildHierarchy(builder); - if(Neg) Neg->_BuildHierarchy(builder); -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Refits the tree (top-down). - * \param builder [in] the tree builder - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -void AABBTreeNode::_Refit(AABBTreeBuilder* builder) -{ - // 1) Recompute the new global box for current node - builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV); - - // 2) Recurse - AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); - AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); - if(Pos) Pos->_Refit(builder); - if(Neg) Neg->_Refit(builder); -} - - - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Constructor. - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -AABBTree::AABBTree() : mIndices(null), mTotalNbNodes(0), mPool(null) -{ -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Destructor. - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -AABBTree::~AABBTree() -{ - Release(); -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Releases the tree. - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -void AABBTree::Release() -{ - DELETEARRAY(mPool); - DELETEARRAY(mIndices); -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Builds a generic AABB tree from a tree builder. - * \param builder [in] the tree builder - * \return true if success - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -bool AABBTree::Build(AABBTreeBuilder* builder) -{ - // Checkings - if(!builder || !builder->mNbPrimitives) return false; - - // Release previous tree - Release(); - - // Init stats - builder->SetCount(1); - builder->SetNbInvalidSplits(0); - - // Initialize indices. This list will be modified during build. - mIndices = new udword[builder->mNbPrimitives]; - CHECKALLOC(mIndices); - // Identity permutation - for(udword i=0;imNbPrimitives;i++) mIndices[i] = i; - - // Setup initial node. Here we have a complete permutation of the app's primitives. - mNodePrimitives = mIndices; - mNbPrimitives = builder->mNbPrimitives; - - // Use a linear array for complete trees (since we can predict the final number of nodes) [Opcode 1.3] -// if(builder->mRules&SPLIT_COMPLETE) - if(builder->mSettings.mLimit==1) - { - // Allocate a pool of nodes - mPool = new AABBTreeNode[builder->mNbPrimitives*2 - 1]; - - builder->mNodeBase = mPool; // ### ugly ! - } - - // Build the hierarchy - _BuildHierarchy(builder); - - // Get back total number of nodes - mTotalNbNodes = builder->GetCount(); - - // For complete trees, check the correct number of nodes has been created [Opcode 1.3] - if(mPool) ASSERT(mTotalNbNodes==builder->mNbPrimitives*2 - 1); - - return true; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Computes the depth of the tree. - * A well-balanced tree should have a log(n) depth. A degenerate tree O(n) depth. - * \return depth of the tree - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -udword AABBTree::ComputeDepth() const -{ - return Walk(null, null); // Use the walking code without callback -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Walks the tree, calling the user back for each node. - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -udword AABBTree::Walk(WalkingCallback callback, void* user_data) const -{ - // Call it without callback to compute max depth - udword MaxDepth = 0; - udword CurrentDepth = 0; - - struct Local - { - static void _Walk(const AABBTreeNode* current_node, udword& max_depth, udword& current_depth, WalkingCallback callback, void* user_data) - { - // 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, user_data)) return; - - // Recurse - if(current_node->GetPos()) { _Walk(current_node->GetPos(), max_depth, current_depth, callback, user_data); current_depth--; } - if(current_node->GetNeg()) { _Walk(current_node->GetNeg(), max_depth, current_depth, callback, user_data); current_depth--; } - } - }; - Local::_Walk(this, MaxDepth, CurrentDepth, callback, user_data); - return MaxDepth; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Refits the tree in a top-down way. - * \param builder [in] the tree builder - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -bool AABBTree::Refit(AABBTreeBuilder* builder) -{ - if(!builder) return false; - _Refit(builder); - return true; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Refits the tree in a bottom-up way. - * \param builder [in] the tree builder - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -bool AABBTree::Refit2(AABBTreeBuilder* builder) -{ - // Checkings - if(!builder) return false; - - ASSERT(mPool); - - // Bottom-up update - IcePoint Min,Max; - IcePoint Min_,Max_; - udword Index = mTotalNbNodes; - while(Index--) - { - AABBTreeNode& Current = mPool[Index]; - - if(Current.IsLeaf()) - { - builder->ComputeGlobalBox(Current.GetPrimitives(), Current.GetNbPrimitives(), *(AABB*)Current.GetAABB()); - } - else - { - Current.GetPos()->GetAABB()->GetMin(Min); - Current.GetPos()->GetAABB()->GetMax(Max); - - Current.GetNeg()->GetAABB()->GetMin(Min_); - Current.GetNeg()->GetAABB()->GetMax(Max_); - - Min.Min(Min_); - Max.Max(Max_); - - ((AABB*)Current.GetAABB())->SetMinMax(Min, Max); - } - } - return true; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Computes the number of bytes used by the tree. - * \return number of bytes used - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -udword AABBTree::GetUsedBytes() const -{ - udword TotalSize = mTotalNbNodes*GetNodeSize(); - if(mIndices) TotalSize+=mNbPrimitives*sizeof(udword); - return TotalSize; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -/** - * Checks the tree is a complete tree or not. - * A complete tree is made of 2*N-1 nodes, where N is the number of primitives in the tree. - * \return true for complete trees - */ -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -bool AABBTree::IsComplete() const -{ - return (GetNbNodes()==GetNbPrimitives()*2-1); -} +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/* + * OPCODE - Optimized Collision Detection + * Copyright (C) 2001 Pierre Terdiman + * Homepage: http://www.codercorner.com/Opcode.htm + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains code for a versatile AABB tree. + * \file OPC_AABBTree.cpp + * \author Pierre Terdiman + * \date March, 20, 2001 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a generic AABB tree node. + * + * \class AABBTreeNode + * \author Pierre Terdiman + * \version 1.3 + * \date March, 20, 2001 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains a generic AABB tree. + * This is a vanilla AABB tree, without any particular optimization. It contains anonymous references to + * user-provided primitives, which can theoretically be anything - triangles, boxes, etc. Each primitive + * is surrounded by an AABB, regardless of the primitive's nature. When the primitive is a triangle, the + * resulting tree can be converted into an optimized tree. If the primitive is a box, the resulting tree + * can be used for culling - VFC or occlusion -, assuming you cull on a mesh-by-mesh basis (modern way). + * + * \class AABBTree + * \author Pierre Terdiman + * \version 1.3 + * \date March, 20, 2001 +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Precompiled Header +#include "StdAfx.h" + +using namespace Opcode; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBTreeNode::AABBTreeNode() : + mPos (null), +#ifndef OPC_NO_NEG_VANILLA_TREE + mNeg (null), +#endif + mNbPrimitives (0), + mNodePrimitives (null) +{ +#ifdef OPC_USE_TREE_COHERENCE + mBitmask = 0; +#endif +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Destructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBTreeNode::~AABBTreeNode() +{ + // Opcode 1.3: + const AABBTreeNode* Pos = GetPos(); + const AABBTreeNode* Neg = GetNeg(); +#ifndef OPC_NO_NEG_VANILLA_TREE + if(!(mPos&1)) DELETESINGLE(Pos); + if(!(mNeg&1)) DELETESINGLE(Neg); +#else + if(!(mPos&1)) DELETEARRAY(Pos); +#endif + mNodePrimitives = null; // This was just a shortcut to the global list => no release + mNbPrimitives = 0; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Splits the node along a given axis. + * The list of indices is reorganized according to the split values. + * \param axis [in] splitting axis index + * \param builder [in] the tree builder + * \return the number of primitives assigned to the first child + * \warning this method reorganizes the internal list of primitives + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +udword AABBTreeNode::Split(udword axis, AABBTreeBuilder* builder) +{ + // Get node split value + float SplitValue = builder->GetSplittingValue(mNodePrimitives, mNbPrimitives, mBV, axis); + + udword NbPos = 0; + // Loop through all node-related primitives. Their indices range from mNodePrimitives[0] to mNodePrimitives[mNbPrimitives-1]. + // Those indices map the global list in the tree builder. + for(udword i=0;iGetSplittingValue(Index, axis); + + // Reorganize the list of indices in this order: positive - negative. + if(PrimitiveValue > SplitValue) + { + // Swap entries + udword Tmp = mNodePrimitives[i]; + mNodePrimitives[i] = mNodePrimitives[NbPos]; + mNodePrimitives[NbPos] = Tmp; + // Count primitives assigned to positive space + NbPos++; + } + } + return NbPos; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Subdivides the node. + * + * N + * / \ + * / \ + * N/2 N/2 + * / \ / \ + * N/4 N/4 N/4 N/4 + * (etc) + * + * A well-balanced tree should have a O(log n) depth. + * A degenerate tree would have a O(n) depth. + * Note a perfectly-balanced tree is not well-suited to collision detection anyway. + * + * \param builder [in] the tree builder + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBTreeNode::Subdivide(AABBTreeBuilder* builder) +{ + // Checkings + if(!builder) return false; + + // Stop subdividing if we reach a leaf node. This is always performed here, + // else we could end in trouble if user overrides this. + if(mNbPrimitives==1) return true; + + // Let the user validate the subdivision + if(!builder->ValidateSubdivision(mNodePrimitives, mNbPrimitives, mBV)) return true; + + bool ValidSplit = true; // Optimism... + udword NbPos; + if(builder->mSettings.mRules & SPLIT_LARGEST_AXIS) + { + // Find the largest axis to split along + IcePoint Extents; mBV.GetExtents(Extents); // Box extents + udword Axis = Extents.LargestAxis(); // Index of largest axis + + // Split along the axis + NbPos = Split(Axis, builder); + + // Check split validity + if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false; + } + else if(builder->mSettings.mRules & SPLIT_SPLATTER_POINTS) + { + // Compute the means + IcePoint Means(0.0f, 0.0f, 0.0f); + for(udword i=0;iGetSplittingValue(Index, 0); + Means.y+=builder->GetSplittingValue(Index, 1); + Means.z+=builder->GetSplittingValue(Index, 2); + } + Means/=float(mNbPrimitives); + + // Compute variances + IcePoint Vars(0.0f, 0.0f, 0.0f); + for(udword i=0;iGetSplittingValue(Index, 0); + float Cy = builder->GetSplittingValue(Index, 1); + float Cz = builder->GetSplittingValue(Index, 2); + Vars.x += (Cx - Means.x)*(Cx - Means.x); + Vars.y += (Cy - Means.y)*(Cy - Means.y); + Vars.z += (Cz - Means.z)*(Cz - Means.z); + } + Vars/=float(mNbPrimitives-1); + + // Choose axis with greatest variance + udword Axis = Vars.LargestAxis(); + + // Split along the axis + NbPos = Split(Axis, builder); + + // Check split validity + if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false; + } + else if(builder->mSettings.mRules & SPLIT_BALANCED) + { + // Test 3 axis, take the best + float Results[3]; + NbPos = Split(0, builder); Results[0] = float(NbPos)/float(mNbPrimitives); + NbPos = Split(1, builder); Results[1] = float(NbPos)/float(mNbPrimitives); + NbPos = Split(2, builder); Results[2] = float(NbPos)/float(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]; + udword Min=0; + if(Results[1]mSettings.mRules & SPLIT_BEST_AXIS) + { + // Test largest, then middle, then smallest axis... + + // Sort axis + IcePoint Extents; mBV.GetExtents(Extents); // Box extents + udword SortedAxis[] = { 0, 1, 2 }; + float* Keys = (float*)&Extents.x; + for(udword j=0;j<3;j++) + { + for(udword i=0;i<2;i++) + { + if(Keys[SortedAxis[i]]mSettings.mRules & SPLIT_FIFTY) + { + // Don't even bother splitting (mainly a performance test) + NbPos = mNbPrimitives>>1; + } + else return false; // Unknown splitting rules + + // 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(builder->mSettings.mRules&SPLIT_COMPLETE) + if(builder->mSettings.mLimit==1) + { + builder->IncreaseNbInvalidSplits(); + NbPos = mNbPrimitives>>1; + } + else return true; + } + + // Now create children and assign their pointers. + if(builder->mNodeBase) + { + // We use a pre-allocated linear pool for complete trees [Opcode 1.3] + AABBTreeNode* Pool = (AABBTreeNode*)builder->mNodeBase; + udword Count = builder->GetCount() - 1; // Count begins to 1... + // Set last bit to tell it shouldn't be freed ### pretty ugly, find a better way. Maybe one bit in mNbPrimitives + ASSERT(!(udword(&Pool[Count+0])&1)); + ASSERT(!(udword(&Pool[Count+1])&1)); + mPos = udword(&Pool[Count+0])|1; +#ifndef OPC_NO_NEG_VANILLA_TREE + mNeg = udword(&Pool[Count+1])|1; +#endif + } + else + { + // Non-complete trees and/or Opcode 1.2 allocate nodes on-the-fly +#ifndef OPC_NO_NEG_VANILLA_TREE + mPos = (udword)new AABBTreeNode; CHECKALLOC(mPos); + mNeg = (udword)new AABBTreeNode; CHECKALLOC(mNeg); +#else + AABBTreeNode* PosNeg = new AABBTreeNode[2]; + CHECKALLOC(PosNeg); + mPos = (udword)PosNeg; +#endif + } + + // Update stats + builder->IncreaseCount(2); + + // Assign children + AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); + AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); + Pos->mNodePrimitives = &mNodePrimitives[0]; + Pos->mNbPrimitives = NbPos; + Neg->mNodePrimitives = &mNodePrimitives[NbPos]; + Neg->mNbPrimitives = mNbPrimitives - NbPos; + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Recursive hierarchy building in a top-down fashion. + * \param builder [in] the tree builder + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void AABBTreeNode::_BuildHierarchy(AABBTreeBuilder* builder) +{ + // 1) Compute the global box for current node. The box is stored in mBV. + builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV); + + // 2) Subdivide current node + Subdivide(builder); + + // 3) Recurse + AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); + AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); + if(Pos) Pos->_BuildHierarchy(builder); + if(Neg) Neg->_BuildHierarchy(builder); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Refits the tree (top-down). + * \param builder [in] the tree builder + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void AABBTreeNode::_Refit(AABBTreeBuilder* builder) +{ + // 1) Recompute the new global box for current node + builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV); + + // 2) Recurse + AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); + AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); + if(Pos) Pos->_Refit(builder); + if(Neg) Neg->_Refit(builder); +} + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Constructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBTree::AABBTree() : mIndices(null), mTotalNbNodes(0), mPool(null) +{ +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Destructor. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +AABBTree::~AABBTree() +{ + Release(); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Releases the tree. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +void AABBTree::Release() +{ + DELETEARRAY(mPool); + DELETEARRAY(mIndices); +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Builds a generic AABB tree from a tree builder. + * \param builder [in] the tree builder + * \return true if success + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBTree::Build(AABBTreeBuilder* builder) +{ + // Checkings + if(!builder || !builder->mNbPrimitives) return false; + + // Release previous tree + Release(); + + // Init stats + builder->SetCount(1); + builder->SetNbInvalidSplits(0); + + // Initialize indices. This list will be modified during build. + mIndices = new udword[builder->mNbPrimitives]; + CHECKALLOC(mIndices); + // Identity permutation + for(udword i=0;imNbPrimitives;i++) mIndices[i] = i; + + // Setup initial node. Here we have a complete permutation of the app's primitives. + mNodePrimitives = mIndices; + mNbPrimitives = builder->mNbPrimitives; + + // Use a linear array for complete trees (since we can predict the final number of nodes) [Opcode 1.3] +// if(builder->mRules&SPLIT_COMPLETE) + if(builder->mSettings.mLimit==1) + { + // Allocate a pool of nodes + mPool = new AABBTreeNode[builder->mNbPrimitives*2 - 1]; + + builder->mNodeBase = mPool; // ### ugly ! + } + + // Build the hierarchy + _BuildHierarchy(builder); + + // Get back total number of nodes + mTotalNbNodes = builder->GetCount(); + + // For complete trees, check the correct number of nodes has been created [Opcode 1.3] + if(mPool) ASSERT(mTotalNbNodes==builder->mNbPrimitives*2 - 1); + + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the depth of the tree. + * A well-balanced tree should have a log(n) depth. A degenerate tree O(n) depth. + * \return depth of the tree + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +udword AABBTree::ComputeDepth() const +{ + return Walk(null, null); // Use the walking code without callback +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Walks the tree, calling the user back for each node. + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +udword AABBTree::Walk(WalkingCallback callback, void* user_data) const +{ + // Call it without callback to compute max depth + udword MaxDepth = 0; + udword CurrentDepth = 0; + + struct Local + { + static void _Walk(const AABBTreeNode* current_node, udword& max_depth, udword& current_depth, WalkingCallback callback, void* user_data) + { + // 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, user_data)) return; + + // Recurse + if(current_node->GetPos()) { _Walk(current_node->GetPos(), max_depth, current_depth, callback, user_data); current_depth--; } + if(current_node->GetNeg()) { _Walk(current_node->GetNeg(), max_depth, current_depth, callback, user_data); current_depth--; } + } + }; + Local::_Walk(this, MaxDepth, CurrentDepth, callback, user_data); + return MaxDepth; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Refits the tree in a top-down way. + * \param builder [in] the tree builder + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBTree::Refit(AABBTreeBuilder* builder) +{ + if(!builder) return false; + _Refit(builder); + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Refits the tree in a bottom-up way. + * \param builder [in] the tree builder + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBTree::Refit2(AABBTreeBuilder* builder) +{ + // Checkings + if(!builder) return false; + + ASSERT(mPool); + + // Bottom-up update + IcePoint Min,Max; + IcePoint Min_,Max_; + udword Index = mTotalNbNodes; + while(Index--) + { + AABBTreeNode& Current = mPool[Index]; + + if(Current.IsLeaf()) + { + builder->ComputeGlobalBox(Current.GetPrimitives(), Current.GetNbPrimitives(), *(AABB*)Current.GetAABB()); + } + else + { + Current.GetPos()->GetAABB()->GetMin(Min); + Current.GetPos()->GetAABB()->GetMax(Max); + + Current.GetNeg()->GetAABB()->GetMin(Min_); + Current.GetNeg()->GetAABB()->GetMax(Max_); + + Min.Min(Min_); + Max.Max(Max_); + + ((AABB*)Current.GetAABB())->SetMinMax(Min, Max); + } + } + return true; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Computes the number of bytes used by the tree. + * \return number of bytes used + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +udword AABBTree::GetUsedBytes() const +{ + udword TotalSize = mTotalNbNodes*GetNodeSize(); + if(mIndices) TotalSize+=mNbPrimitives*sizeof(udword); + return TotalSize; +} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Checks the tree is a complete tree or not. + * A complete tree is made of 2*N-1 nodes, where N is the number of primitives in the tree. + * \return true for complete trees + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +bool AABBTree::IsComplete() const +{ + return (GetNbNodes()==GetNbPrimitives()*2-1); +} -- cgit v1.1