Opcode::AABBTree Class Reference

#include <Opcode.h>

Inheritance diagram for Opcode::AABBTree:

Public Member Functions
	AABBTree ()
	~AABBTree ()
bool	Build (AABBTreeBuilder *builder)
void	Release ()
inline_ const udword *	GetIndices () const
	Catch the indices. More...
inline_ udword	GetNbNodes () const
	Catch the number of nodes. More...
bool	IsComplete () const
udword	ComputeDepth () const
udword	GetUsedBytes () const
udword	Walk (WalkingCallback callback, void *user_data) const
bool	Refit (AABBTreeBuilder *builder)
bool	Refit2 (AABBTreeBuilder *builder)
Public Member Functions inherited from Opcode::AABBTreeNode
inline_ const udword *	GetPrimitives () const
inline_ udword	GetNbPrimitives () const

Additional Inherited Members
Protected Member Functions inherited from Opcode::AABBTreeNode
udword	Split (udword axis, AABBTreeBuilder *builder)
bool	Subdivide (AABBTreeBuilder *builder)
void	_BuildHierarchy (AABBTreeBuilder *builder)
void	_Refit (AABBTreeBuilder *builder)
Protected Attributes inherited from Opcode::AABBTreeNode
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 109 of file Opcode.h.

Constructor & Destructor Documentation

AABBTree::AABBTree

(

)

Constructor.

Definition at line 374 of file OPC_AABBTree.cpp.

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

AABBTree::~AABBTree

(

)

Destructor.

Definition at line 383 of file OPC_AABBTree.cpp.

{
    Release();
}

Member Function Documentation

bool AABBTree::Build

(

AABBTreeBuilder *

builder)

Builds a generic AABB tree from a tree builder.

Parameters

builder

[in] the tree builder

Returns

true if success

Definition at line 406 of file OPC_AABBTree.cpp.

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

Computes the depth of the tree. A well-balanced tree should have a log(n) depth. A degenerate tree O(n) depth.

Returns

depth of the tree

Definition at line 457 of file OPC_AABBTree.cpp.

{
    return Walk(null, null);    // Use the walking code without callback
}

inline_ const udword* Opcode::AABBTree::GetIndices ( ) const

inline

Catch the indices.

Definition at line 120 of file Opcode.h.

inline_ udword Opcode::AABBTree::GetNbNodes ( ) const

inline

Catch the number of nodes.

Definition at line 121 of file Opcode.h.

udword AABBTree::GetUsedBytes

(

)

const

Computes the number of bytes used by the tree.

Returns

number of bytes used

Definition at line 557 of file OPC_AABBTree.cpp.

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

bool AABBTree::IsComplete

(

)

const

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.

Returns

true for complete trees

Definition at line 571 of file OPC_AABBTree.cpp.

{
    return (GetNbNodes()==GetNbPrimitives()*2-1);
}

bool AABBTree::Refit

(

AABBTreeBuilder *

builder)

Refits the tree in a top-down way.

Parameters

builder

[in] the tree builder

Definition at line 502 of file OPC_AABBTree.cpp.

{
    if(!builder)    return false;
    _Refit(builder);
    return true;
}

bool AABBTree::Refit2

(

AABBTreeBuilder *

builder)

Refits the tree in a bottom-up way.

Parameters

builder

[in] the tree builder

Definition at line 515 of file OPC_AABBTree.cpp.

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

void AABBTree::Release

(

)

Releases the tree.

Definition at line 393 of file OPC_AABBTree.cpp.

{
    DELETEARRAY(mPool);
    DELETEARRAY(mIndices);
}

udword AABBTree::Walk	(	WalkingCallback	callback,
		void *	user_data
	)		const

Walks the tree, calling the user back for each node.

Definition at line 467 of file OPC_AABBTree.cpp.

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

---

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

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