Opcode::AABBTreeNode Class Reference

#include <Opcode.h>

Inheritance diagram for Opcode::AABBTreeNode:

Public Member Functions
inline_ const udword *	GetPrimitives () const
inline_ udword	GetNbPrimitives () const

Protected Member Functions
udword	Split (udword axis, AABBTreeBuilder *builder)
bool	Subdivide (AABBTreeBuilder *builder)
void	_BuildHierarchy (AABBTreeBuilder *builder)
void	_Refit (AABBTreeBuilder *builder)

Protected Attributes
udword *	mNodePrimitives
	Node-related primitives (shortcut to a position in mIndices below) More...
udword	mNbPrimitives
	Number of primitives for this node. More...

Detailed Description

Definition at line 79 of file Opcode.h.

Member Function Documentation

void AABBTreeNode::_BuildHierarchy ( AABBTreeBuilder *  builder)

protected

Recursive hierarchy building in a top-down fashion.

Parameters

builder

[in] the tree builder

Definition at line 334 of file OPC_AABBTree.cpp.

{
    // 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)

protected

Refits the tree (top-down).

Parameters

builder

[in] the tree builder

Definition at line 355 of file OPC_AABBTree.cpp.

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

inline_ udword Opcode::AABBTreeNode::GetNbPrimitives ( ) const

inline

Definition at line 85 of file Opcode.h.

inline_ const udword* Opcode::AABBTreeNode::GetPrimitives ( ) const

inline

Definition at line 84 of file Opcode.h.

udword AABBTreeNode::Split ( udword  axis, AABBTreeBuilder *  builder  )

protected

Splits the node along a given axis. The list of indices is reorganized according to the split values.

Parameters

axis	[in] splitting axis index
builder	[in] the tree builder

Returns

the number of primitives assigned to the first child

Warning

this method reorganizes the internal list of primitives

Definition at line 99 of file OPC_AABBTree.cpp.

{
    // 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)

protected

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.

Parameters

builder

[in] the tree builder

Returns

true if success

Definition at line 150 of file OPC_AABBTree.cpp.

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

Member Data Documentation

udword Opcode::AABBTreeNode::mNbPrimitives

protected

Number of primitives for this node.

Definition at line 90 of file Opcode.h.

udword* Opcode::AABBTreeNode::mNodePrimitives

protected

Node-related primitives (shortcut to a position in mIndices below)

Definition at line 89 of file Opcode.h.

---

The documentation for this class was generated from the following files:

• src/cmd/collide2/OPC_AABBTree.h
• src/cmd/collide2/OPC_AABBTree.cpp