Show node.cpp syntax highlighted
/***************************************************************************
node.cpp - Node in ABT
-------------------
begin : Tue Jul 8 2003
copyright : (C) 2003 by Reality Rift Studios
email : mattias@realityrift.com
***************************************************************************
The contents of this file are subject to the Mozilla Public License Version
1.1 (the "License"); you may not use this file except in compliance with
the License. You may obtain a copy of the License at
http://www.mozilla.org/MPL/
Software distributed under the License is distributed on an "AS IS" basis,
WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
for the specific language governing rights and limitations under the
License.
The Original Code is the NeoEngine, NeoABT, node.cpp
The Initial Developer of the Original Code is Mattias Jansson.
Portions created by Mattias Jansson are Copyright (C) 2003
Reality Rift Studios. All Rights Reserved.
***************************************************************************/
#include "node.h"
#include <neoengine/radix.h>
using namespace std;
using namespace NeoEngine;
namespace NeoABT
{
Node::Node( Node *pkParent, Node *pkRoot ) :
m_eType( LEAF ),
m_pkRoot( pkRoot ),
m_pkParent( pkParent ),
m_pkLeft( 0 ),
m_pkRight( 0 ),
m_uiNumNodes( 0 ),
m_fRefSize( 0.0f )
{
if( !m_pkRoot )
m_pkRoot = this;
}
Node::~Node()
{
delete m_pkLeft;
delete m_pkRight;
unsigned int uiNodes = m_uiNumNodes;
m_uiNumNodes = 0;
for( unsigned int i = 0; i < uiNodes; ++i )
delete m_apkNodes[i];
}
bool Node::Render( Frustum *pkFrustum, bool bForce )
{
if( m_eType == NODE )
{
if( m_pkLeft->m_kAABB.Intersection( pkFrustum ) )
m_pkLeft->Render( pkFrustum, bForce );
if( m_pkRight->m_kAABB.Intersection( pkFrustum ) )
m_pkRight->Render( pkFrustum, bForce );
}
else for( unsigned int i = 0; i < m_uiNumNodes; ++i )
if( m_apkNodes[i] && m_apkNodes[i]->GetBoundingVolume()->Intersection( pkFrustum ) )
{
m_apkNodes[i]->Render( pkFrustum, bForce );
// Gianca: DEBUG!!!
//m_apkNodes[i]->GetBoundingVolume()->RenderOutlines( Color::WHITE );
}
return true;
}
void Node::Update( float fDeltaTime )
{
if( m_eType == NODE )
{
m_pkLeft->Update( fDeltaTime );
m_pkRight->Update( fDeltaTime );
}
else for( unsigned int i = 0; i < m_uiNumNodes; ++i )
m_apkNodes[i]->Update( fDeltaTime );
}
void Node::AddNode( SceneNode *pkNode )
{
if( m_eType == NODE )
{
//Find the best matching child node calculated as the node
//that will grow least (relatively) when adding the node
static bool sbChooseLeft = true;
AABB kAABB[2] = { m_kAABB, m_kAABB };
float fInc[2] = { 0.0f, 0.0f };
((BoundingVolume*)&kAABB[0])->Merge( pkNode->GetBoundingVolume() );
((BoundingVolume*)&kAABB[1])->Merge( pkNode->GetBoundingVolume() );
fInc[0] = ( kAABB[0].GetDim().Len2() / m_kAABB.GetDim().Len2() ) + ( sbChooseLeft ? 0.01f : 0.0f );
fInc[1] = ( kAABB[1].GetDim().Len2() / m_kAABB.GetDim().Len2() ) + ( !sbChooseLeft ? 0.01f : 0.0f );
if( fInc[0] < fInc[1] )
m_pkLeft->AddNode( pkNode );
else
m_pkRight->AddNode( pkNode );
sbChooseLeft = !sbChooseLeft;
return;
}
m_apkNodes[ m_uiNumNodes++ ] = pkNode;
if( m_uiNumNodes <= MAXNODES )
{
pkNode->AddCallback( this );
if( m_uiNumNodes == 1 )
((BoundingVolume*)&m_kAABB)->Generate( pkNode->GetBoundingVolume() );
else
((BoundingVolume*)&m_kAABB)->Merge( pkNode->GetBoundingVolume() );
m_fRefSize = m_kAABB.GetRadius();
if( m_pkParent )
m_pkParent->NodeChanged( this );
}
else
{
((BoundingVolume*)&m_kAABB)->Merge( pkNode->GetBoundingVolume() );
//Split
static RadixSort kSort[3] = { RadixSort::FLOAT32, RadixSort::FLOAT32, RadixSort::FLOAT32 };
int i;
float fSplit[3] = { 0.0f, 0.0f, 0.0f };
float fPos[ MAXNODES + 1 ];
for( i = 0; i < ( MAXNODES + 1 ); ++i )
fPos[i] = m_apkNodes[i]->GetWorldTranslation().x;
kSort[0].Sort( (void*)fPos, MAXNODES + 1 );
unsigned int *piIndices = kSort[0].GetIndices();
fSplit[0] = 0.5f * ( fPos[ piIndices[ MAXNODES / 2 ] ] + fPos[ piIndices[ 1 + ( MAXNODES / 2 ) ] ] );
for( i = 0; i < ( MAXNODES + 1 ); ++i )
fPos[i] = m_apkNodes[i]->GetWorldTranslation().y;
kSort[1].Sort( (void*)fPos, MAXNODES + 1 );
piIndices = kSort[1].GetIndices();
fSplit[1] = 0.5f * ( fPos[ piIndices[ MAXNODES / 2 ] ] + fPos[ piIndices[ 1 + ( MAXNODES / 2 ) ] ] );
for( i = 0; i < ( MAXNODES + 1 ); ++i )
fPos[i] = m_apkNodes[i]->GetWorldTranslation().z;
kSort[2].Sort( (void*)fPos, MAXNODES + 1 );
piIndices = kSort[2].GetIndices();
fSplit[2] = 0.5f * ( fPos[ piIndices[ MAXNODES / 2 ] ] + fPos[ piIndices[ 1 + ( MAXNODES / 2 ) ] ] );
//Calculate the best split plane
const Vector3d &kDim = m_kAABB.GetDim();
// const Vector3d &kPos = m_kAABB.GetTranslation();
const Vector3d &kPos = m_kAABB.GetTranslation() + m_kAABB.m_kDelta;
int iBest = ( kDim.x > kDim.y ? 0 : ( kDim.z > kDim.y ? 2 : 1 ) );
float fFactor[3] = { 0.0f, 0.0f, 0.0f };
fFactor[0] = fabsf( fPos[0] - kPos.x ) / kDim.x;
fFactor[1] = fabsf( fPos[1] - kPos.y ) / kDim.y;
fFactor[2] = fabsf( fPos[2] - kPos.z ) / kDim.z;
//Favour the major axis
if( kDim.x > kDim.y ) fFactor[1] += 0.2f; else fFactor[0] += 0.2f;
if( kDim.x > kDim.z ) fFactor[2] += 0.2f; else fFactor[0] += 0.2f;
if( kDim.y > kDim.z ) fFactor[2] += 0.2f; else fFactor[1] += 0.2f;
iBest = ( fFactor[0] < fFactor[1] ? ( fFactor[0] < fFactor[2] ? 0 : 2 ) : 1 );
//Create new child nodes and add scenenodes
m_eType = NODE;
m_pkLeft = new Node( this, m_pkRoot );
m_pkRight = new Node( this, m_pkRoot );
for( i = 0; i < ( MAXNODES + 1 ); ++i )
m_apkNodes[i]->RemoveCallback( this );
piIndices = kSort[iBest].GetIndices();
m_pkLeft->AddNode( m_apkNodes[*piIndices] );
m_pkLeft->AddNode( m_apkNodes[*(++piIndices)] );
m_pkLeft->AddNode( m_apkNodes[*(++piIndices)] );
m_pkRight->AddNode( m_apkNodes[*(++piIndices)] );
m_pkRight->AddNode( m_apkNodes[*(++piIndices)] );
m_pkRight->AddNode( m_apkNodes[*(++piIndices)] );
m_uiNumNodes = 0;
m_fRefSize = 0.0f;
//Recalc bounding volume from child nodes
RecalcVolume();
}
}
int Node::RemoveNode( SceneNode *pkNode )
{
if( m_eType == NODE )
{
// ### FIXME: We can do better than this!
if( m_pkLeft->RemoveNode( pkNode ) > 0 )
m_pkRight->RemoveNode( pkNode );
}
else
{
for( unsigned int i = 0; i < m_uiNumNodes; ++i )
if( m_apkNodes[i] == pkNode )
{
for( ; i < m_uiNumNodes - 1; ++i )
m_apkNodes[i] = m_apkNodes[i+1];
--m_uiNumNodes;
pkNode->RemoveCallback( this );
if( !m_uiNumNodes )
{
if( m_pkParent )
{
//Remove nodes from other child nodes to merge into parent
m_pkParent->MergeChildren();
return -1;
}
}
else
RecalcVolume();
return 0;
}
}
return 1;
}
void Node::NodeChanged( SceneNode *pkNode )
{
//Check if we need to modify tree (if node has moved too far)
//If so, remove the node and readd at the top of the tree
float fLastSize = m_fRefSize;
//Recalculate bounding volume
RecalcVolume();
m_fRefSize = m_kAABB.GetRadius();
if( fabsf( 1.0f - ( m_fRefSize / fLastSize ) ) > 0.1f )
{
//Remove the node
assert( m_uiNumNodes <= MAXNODES );
Node *pkRoot = m_pkRoot ? m_pkRoot : this;
int iResult = RemoveNode( pkNode );
pkRoot->AddNode( pkNode );
if( ( iResult >= 0 ) && ( m_eType == LEAF ) && !m_uiNumNodes )
{
// ### FIXME: What to do when we get empty? Is it possible?
neolog << LogLevel( WARNING ) << "*** empty leaf in ABT tree after node change!" << endl;
}
}
}
void Node::NodeDeleted( NeoEngine::SceneNode *pkNode )
{
RemoveNode( pkNode );
}
void Node::NodeChanged( Node *pkNode )
{
RecalcVolume();
}
void Node::MergeChildren()
{
if( ( m_pkLeft->m_eType == LEAF ) && ( m_pkRight->m_eType == LEAF ) && ( ( m_pkLeft->m_uiNumNodes + m_pkRight->m_uiNumNodes ) <= MAXNODES ) )
{
//Two leaf children, one empty
unsigned int uiLeft = m_pkLeft->m_uiNumNodes;
unsigned int uiRight = m_pkRight->m_uiNumNodes;
unsigned int uiNode = 0;
m_pkLeft->m_uiNumNodes = 0;
m_pkRight->m_uiNumNodes = 0;
m_uiNumNodes = uiLeft + uiRight;
for( ; uiNode < uiLeft; ++uiNode )
{
m_pkLeft->m_apkNodes[ uiNode ]->RemoveCallback( m_pkLeft );
m_apkNodes[ uiNode ] = m_pkLeft->m_apkNodes[ uiNode ];
m_apkNodes[ uiNode ]->AddCallback( this );
}
for( ; uiNode < uiLeft + uiRight; ++uiNode )
{
m_pkRight->m_apkNodes[ uiNode - uiLeft ]->RemoveCallback( m_pkRight );
m_apkNodes[ uiNode ] = m_pkRight->m_apkNodes[ uiNode - uiLeft ];
m_apkNodes[ uiNode ]->AddCallback( this );
}
delete m_pkLeft, m_pkLeft = 0;
delete m_pkRight, m_pkRight = 0;
m_eType = LEAF;
RecalcVolume();
}
else
{
//We got one empty child leaf and one child node with a subtree
vector< SceneNode* > vpkNodes;
m_pkRight->CollectNodes( &vpkNodes );
m_pkLeft->CollectNodes( &vpkNodes );
delete m_pkRight, m_pkRight = 0;
delete m_pkLeft, m_pkLeft = 0;
m_eType = LEAF;
vector< SceneNode* >::iterator ppkNode = vpkNodes.begin();
vector< SceneNode* >::iterator ppkEnd = vpkNodes.end();
for( ; ppkNode != ppkEnd; ++ppkNode )
AddNode( *ppkNode );
}
}
void Node::CollectNodes( std::vector< NeoEngine::SceneNode* > *pvpkNodes )
{
if( m_eType == NODE )
{
m_pkRight->CollectNodes( pvpkNodes );
m_pkLeft->CollectNodes( pvpkNodes );
}
else
{
for( unsigned int uiNode = 0; uiNode < m_uiNumNodes; ++uiNode )
{
m_apkNodes[ uiNode ]->RemoveCallback( this );
pvpkNodes->push_back( m_apkNodes[ uiNode ] );
}
m_uiNumNodes = 0;
}
}
void Node::RecalcVolume()
{
if( m_eType == LEAF )
{
if( !m_uiNumNodes )
{
// ### FIXME: What to do when we get empty?
// This is not good, as it will fuck up the chooser when adding scenenodes
//m_kAABB.SetDim( Vector3d::ZERO );
return;
}
((BoundingVolume*)&m_kAABB)->Generate( m_apkNodes[0]->GetBoundingVolume() );
for( unsigned int i = 1; i < m_uiNumNodes; ++i )
((BoundingVolume*)&m_kAABB)->Merge( m_apkNodes[i]->GetBoundingVolume() );
}
else
{
m_kAABB.Generate( &m_pkLeft->m_kAABB );
m_kAABB.Merge( &m_pkRight->m_kAABB );
}
if( m_pkParent )
m_pkParent->NodeChanged( this );
}
bool Node::Intersection( NeoEngine::BoundingVolume *pkObj, NeoEngine::ContactSet *pkContactSet )
{
bool bIntersect = false;
if( m_eType == NODE )
{
if( pkObj->Intersection( &m_pkLeft->m_kAABB ) )
bIntersect |= m_pkLeft->Intersection( pkObj, pkContactSet );
if( ( !bIntersect || pkContactSet ) && pkObj->Intersection( &m_pkRight->m_kAABB ) )
bIntersect |= m_pkRight->Intersection( pkObj, pkContactSet );
return bIntersect;
}
for( unsigned int i = 0; i < m_uiNumNodes; ++i )
{
if( !m_apkNodes[i]->IsActive() )
continue;
if( pkObj->Intersection( m_apkNodes[i]->GetBoundingVolume() ) )
bIntersect |= m_apkNodes[i]->Intersection( pkObj, pkContactSet );
if( !pkContactSet && bIntersect )
return true;
}
return bIntersect;
}
bool Node::Intersection( const NeoEngine::Ray &rkRay, NeoEngine::ContactSet *pkContactSet )
{
bool bIntersect = false;
if( m_eType == NODE )
{
if( m_pkLeft->m_kAABB.Intersection( rkRay ) )
bIntersect |= m_pkLeft->Intersection( rkRay, pkContactSet );
if( ( !bIntersect || pkContactSet ) && m_pkRight->m_kAABB.Intersection( rkRay ) )
bIntersect |= m_pkRight->Intersection( rkRay, pkContactSet );
return bIntersect;
}
for( unsigned int i = 0; i < m_uiNumNodes; ++i )
{
if( !m_apkNodes[i]->IsActive() )
continue;
if( m_apkNodes[i]->GetBoundingVolume()->Intersection( rkRay ) )
bIntersect |= m_apkNodes[i]->Intersection( rkRay, pkContactSet );
if( !pkContactSet && bIntersect )
return true;
}
return bIntersect;
}
SceneNode *Node::GetByName( const HashString &rstrName, SceneNode::NODESEARCHMODE eMode )
{
if( eMode == SceneNode::BREADTH_FIRST )
{
// Loop children, breadth first
SceneNode *pkNode;
unsigned int i;
for( i = 0; i < m_uiNumNodes; ++i )
if( m_apkNodes[i]->GetName() == rstrName )
return m_apkNodes[i];
for( i = 0; i < m_uiNumNodes; ++i )
if( ( pkNode = m_apkNodes[i]->GetByName( rstrName, SceneNode::BREADTH_FIRST, false ) ) )
return pkNode;
return 0;
}
SceneNode *pkNode = 0;
for( unsigned int i = 0; i < m_uiNumNodes; ++i )
if( ( pkNode = m_apkNodes[i]->GetByName( rstrName, SceneNode::DEPTH_FIRST, false ) ) )
return pkNode;
return 0;
}
void Node::Traverse( BaseVisitor &rkVisitor, SceneNode::NODESEARCHMODE eMode, int iDirection )
{
if( eMode == SceneNode::BREADTH_FIRST )
{
unsigned int i;
for( i = 0; i < m_uiNumNodes; ++i )
m_apkNodes[i]->TraverseNode( rkVisitor );
for( i = 0; i < m_uiNumNodes; ++i )
m_apkNodes[i]->Traverse( rkVisitor, SceneNode::BREADTH_FIRST, false );
return;
}
for( unsigned int i = 0; i < m_uiNumNodes; ++i )
m_apkNodes[i]->Traverse( rkVisitor, SceneNode::DEPTH_FIRST, false );
}
};
See more files for this project here