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)
    {
        udword i;
        // Compute the means
        Point Means(0.0f, 0.0f, 0.0f);
        for(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(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
        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
        OPASSERT(!(uintptr_t(&Pool[Count+0])&1));
        OPASSERT(!(uintptr_t(&Pool[Count+1])&1));
        mPos = uintptr_t(&Pool[Count+0])|1;
#ifndef OPC_NO_NEG_VANILLA_TREE
        mNeg = uintptr_t(&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 = (uintptr_t)new AABBTreeNode; CHECKALLOC(mPos);
        mNeg = (uintptr_t)new AABBTreeNode; CHECKALLOC(mNeg);
#else
        AABBTreeNode* PosNeg = new AABBTreeNode[2];
        CHECKALLOC(PosNeg);
        mPos = (uintptr_t)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)   OPASSERT(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;

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