summaryrefslogtreecommitdiffhomepage
path: root/Opcode/OPC_AABBTree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Opcode/OPC_AABBTree.cpp')
-rw-r--r--Opcode/OPC_AABBTree.cpp1146
1 files changed, 573 insertions, 573 deletions
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;i<mNbPrimitives;i++)
- {
- // Get index in global list
- udword Index = mNodePrimitives[i];
-
- // Test against the splitting value. The primitive value is tested against the enclosing-box center.
- // [We only need an approximate partition of the enclosing box here.]
- float PrimitiveValue = builder->GetSplittingValue(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;i<mNbPrimitives;i++)
- {
- udword Index = mNodePrimitives[i];
- Means.x+=builder->GetSplittingValue(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;i<mNbPrimitives;i++)
- {
- udword Index = mNodePrimitives[i];
- float Cx = builder->GetSplittingValue(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]<Results[Min]) Min = 1;
- if(Results[2]<Results[Min]) Min = 2;
-
- // Split along the axis
- NbPos = Split(Min, builder);
-
- // Check split validity
- if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false;
- }
- else if(builder->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]]<Keys[SortedAxis[i+1]])
- {
- udword Tmp = SortedAxis[i];
- SortedAxis[i] = SortedAxis[i+1];
- SortedAxis[i+1] = Tmp;
- }
- }
- }
-
- // Find the largest axis to split along
- udword CurAxis = 0;
- ValidSplit = false;
- while(!ValidSplit && CurAxis!=3)
- {
- NbPos = Split(SortedAxis[CurAxis], builder);
- // Check the subdivision has been successful
- if(!NbPos || NbPos==mNbPrimitives) CurAxis++;
- else ValidSplit = true;
- }
- }
- else if(builder->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;i<builder->mNbPrimitives;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;i<mNbPrimitives;i++)
+ {
+ // Get index in global list
+ udword Index = mNodePrimitives[i];
+
+ // Test against the splitting value. The primitive value is tested against the enclosing-box center.
+ // [We only need an approximate partition of the enclosing box here.]
+ float PrimitiveValue = builder->GetSplittingValue(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;i<mNbPrimitives;i++)
+ {
+ udword Index = mNodePrimitives[i];
+ Means.x+=builder->GetSplittingValue(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;i<mNbPrimitives;i++)
+ {
+ udword Index = mNodePrimitives[i];
+ float Cx = builder->GetSplittingValue(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]<Results[Min]) Min = 1;
+ if(Results[2]<Results[Min]) Min = 2;
+
+ // Split along the axis
+ NbPos = Split(Min, builder);
+
+ // Check split validity
+ if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false;
+ }
+ else if(builder->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]]<Keys[SortedAxis[i+1]])
+ {
+ udword Tmp = SortedAxis[i];
+ SortedAxis[i] = SortedAxis[i+1];
+ SortedAxis[i+1] = Tmp;
+ }
+ }
+ }
+
+ // Find the largest axis to split along
+ udword CurAxis = 0;
+ ValidSplit = false;
+ while(!ValidSplit && CurAxis!=3)
+ {
+ NbPos = Split(SortedAxis[CurAxis], builder);
+ // Check the subdivision has been successful
+ if(!NbPos || NbPos==mNbPrimitives) CurAxis++;
+ else ValidSplit = true;
+ }
+ }
+ else if(builder->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;i<builder->mNbPrimitives;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);
+}
generated by cgit v1.1 at 2024-11-05 01:06:01 +0000