OPC_AABBTree.cpp

Go to the documentation of this file.

/*
 *      OPCODE - Optimized Collision Detection
 *      Copyright (C) 2001 Pierre Terdiman
 *      Homepage: http://www.codercorner.com/Opcode.htm
 */







// Precompiled Header
#include "Stdafx.h"

using namespace Opcode;


AABBTreeNode::AABBTreeNode() :
        mPos                    (null),
#ifndef OPC_NO_NEG_VANILLA_TREE
        mNeg                    (null),
#endif
        mNodePrimitives (null),
        mNbPrimitives   (0)
{
#ifdef OPC_USE_TREE_COHERENCE
        mBitmask = 0;
#endif
}


AABBTreeNode::~AABBTreeNode()
{
        // Opcode 1.3:
        const AABBTreeNode* Pos = GetPos();
#ifndef OPC_NO_NEG_VANILLA_TREE
        const AABBTreeNode* Neg = GetNeg();
        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;
}


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;
}


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
                Point 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
                Point 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
                Point Vars(0.0f, 0.0f, 0.0f);
                for(udword i=0;i<mNbPrimitives;i++)
                {
                        udword Index = mNodePrimitives[i];
                        volatile float Cx = builder->GetSplittingValue(Index, 0);
                        volatile float Cy = builder->GetSplittingValue(Index, 1);
                        volatile 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
                Point 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 = EXWORD(&Pool[Count+0])|1;
#ifndef OPC_NO_NEG_VANILLA_TREE
                mNeg = EXWORD(&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 = (EXWORD)new AABBTreeNode;        CHECKALLOC(mPos);
                mNeg = (EXWORD)new AABBTreeNode;        CHECKALLOC(mNeg);
#else
                AABBTreeNode* PosNeg = new AABBTreeNode[2];
                CHECKALLOC(PosNeg);
                mPos = (EXWORD)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;
}


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);
}


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);
}




AABBTree::AABBTree() : mIndices(null), mPool(null), mTotalNbNodes(0)
{
}


AABBTree::~AABBTree()
{
        Release();
}


void AABBTree::Release()
{
        DELETEARRAY(mPool);
        DELETEARRAY(mIndices);
}


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;
}


udword AABBTree::ComputeDepth() const
{
        return Walk(null, null);        // Use the walking code without callback
}


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;
}


bool AABBTree::Refit(AABBTreeBuilder* builder)
{
        if(!builder)    return false;
        _Refit(builder);
        return true;
}


bool AABBTree::Refit2(AABBTreeBuilder* builder)
{
        // Checkings
        if(!builder)    return false;

        ASSERT(mPool);

        // Bottom-up update
        Point Min,Max;
        Point 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;
}


udword AABBTree::GetUsedBytes() const
{
        udword TotalSize = mTotalNbNodes*GetNodeSize();
        if(mIndices)    TotalSize+=mNbPrimitives*sizeof(udword);
        return TotalSize;
}


bool AABBTree::IsComplete() const
{
        return (GetNbNodes()==GetNbPrimitives()*2-1);
}