#include "Mix/Private/Scene/Common/Octree.h"

#include "Mix/Private/Scene/Common/OctreeNode.h"
#include "Mix/Private/Scene/Common/PointLight.h"
#include "Mix/Private/Scene/Common/SpotLight.h"
#include "Mix/Private/Scene/Common/WaterPool.h"
#include "Mix/Private/Scene/Common/Planter.h"
#include "Mix/Private/Scene/Common/LeavingParticle.h"
#include "Mix/Private/Scene/Common/ScatterParticle.h"
#include "Mix/Private/Scene/Common/ActorModel.h"
#include "Mix/Geometry/Frustum.h"

#ifdef _DEBUG
	#include "Mix/Graphics/Utility/IPerspectiveRenderer.h"
#endif //_DEBUG

namespace Mix{ namespace Scene{ namespace Common{

const UInt32 Octree::V_LL_OBJECTS__DEF_SIZE = 256;
const UInt32 Octree::V_LL_OBJECTS__RESIZE_STEP = 32;

const UInt32 Octree::V_WP_OBJECTS__DEF_SIZE = 256;
const UInt32 Octree::V_WP_OBJECTS__RESIZE_STEP = 32;

const UInt32 Octree::V_PT_OBJECTS__DEF_SIZE = 256;
const UInt32 Octree::V_PT_OBJECTS__RESIZE_STEP = 32;

const UInt32 Octree::V_SPU_OBJECTS__DEF_SIZE = 512;
const UInt32 Octree::V_SPU_OBJECTS__DEF_RESIZE_STEP = 64;

const UInt32 Octree::V_AM_OBJECTS__DEF_SIZE = 512;
const UInt32 Octree::V_AM_OBJECTS__RESIZE_STEP = 64;

////////////////////////////////////////////////////////////////////////////////////////////////////
// Public
////////////////////////////////////////////////////////////////////////////////////////////////////

Octree::Octree( const wchar_t* pName ) :
m_bInit( False ),
m_pIllegalNode( NULL ),
m_ppNodes( NULL ),
m_NodeMax( 0 ),
m_NodeNum( 0 ),
m_Level( 0 ),
m_ppRefreshNodes( NULL ),
m_RefreshNodeNum( 0 ),
m_pCurView( NULL )
{
	MIX_ASSERT( pName != NULL );

	Int32 i;
	UInt32 viewID;

	////////////////////////////////////////////////////////////////////////////////////////////////////

	m_Name = pName;

	////////////////////////////////////////////////////////////////////////////////////////////////////

	m_Pows[0] = 1;

	for( i = 1; i < ( Octree::MAX_LEVEL + 1 ); i++ )
	{
		m_Pows[i] = m_Pows[i - 1] * 8;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////

	m_ViewDataStack.reserve( Mix::Scene::Common::OCTREE_VIEW_MAX );

	viewID = Mix::Scene::Common::OCTREE_VIEW_MAX - 1;

	for( i = ( Mix::Scene::Common::OCTREE_VIEW_MAX * 2 - 1 ); i >= 0; i -= 2, --viewID )
	{
		Mix::Scene::Common::OCTREE_VIEW_DATA viewData;

		viewData.id = viewID;
		viewData.colBit = ( 1 << ( i - 1 ) );
		viewData.sdwBit = ( 1 << i );
		viewData.mask = ( viewData.colBit | viewData.sdwBit );
		viewData.invMask = ( viewData.mask ^ 0xFFFFFFFF );

		m_ViewDataStack.push_back( viewData );
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////

#ifdef _DEBUG

	Mix::String tempStr;

	m_pDebVisibleNodes = NULL;
	m_DebVisibleNodeCount = 0;

	tempStr.Sprintf( L"%s/ValidLocalLightObjects", m_Name.GetConstPtr() );
	m_ValidLocalLightObjects.Initialize( Octree::V_LL_OBJECTS__DEF_SIZE, Octree::V_LL_OBJECTS__RESIZE_STEP, tempStr.GetConstPtr() );

	tempStr.Sprintf( L"%s/ValidWaterPoolObjects", m_Name.GetConstPtr() );
	m_ValidWaterPoolObjects.Initialize( Octree::V_WP_OBJECTS__DEF_SIZE, Octree::V_WP_OBJECTS__RESIZE_STEP, tempStr.GetConstPtr() );

	tempStr.Sprintf( L"%s/ValidPlanterObjects", m_Name.GetConstPtr() );
	m_ValidPlanterObjects.Initialize( Octree::V_PT_OBJECTS__DEF_SIZE, Octree::V_PT_OBJECTS__RESIZE_STEP, tempStr.GetConstPtr() );

	tempStr.Sprintf( L"%s/SPUnitObjStock", m_Name.GetConstPtr() );
	m_SPUnitObjStock.Initialize( Octree::V_SPU_OBJECTS__DEF_SIZE, Octree::V_SPU_OBJECTS__DEF_RESIZE_STEP, tempStr.GetConstPtr() );

	tempStr.Sprintf( L"%s/ValidScatterParticleUnitObjects", m_Name.GetConstPtr() );
	m_ValidScatterParticleUnitObjects.Initialize( Octree::V_SPU_OBJECTS__DEF_SIZE, Octree::V_SPU_OBJECTS__DEF_RESIZE_STEP, tempStr.GetConstPtr() );

	tempStr.Sprintf( L"%s/TempValidActorModelObjects", m_Name.GetConstPtr() );
	m_TempValidActorModelObjects.Initialize( Octree::V_AM_OBJECTS__DEF_SIZE, Octree::V_AM_OBJECTS__RESIZE_STEP, tempStr.GetConstPtr() );

	tempStr.Sprintf( L"%s/TempValidShadowActorModelObjects", m_Name.GetConstPtr() );
	m_TempValidShadowActorModelObjects.Initialize( Octree::V_AM_OBJECTS__DEF_SIZE, Octree::V_AM_OBJECTS__RESIZE_STEP, tempStr.GetConstPtr() );

#else //_DEBUG

	m_ValidLocalLightObjects.Initialize( Octree::V_LL_OBJECTS__DEF_SIZE, Octree::V_LL_OBJECTS__RESIZE_STEP );
	m_ValidWaterPoolObjects.Initialize( Octree::V_WP_OBJECTS__DEF_SIZE, Octree::V_WP_OBJECTS__RESIZE_STEP );
	m_ValidPlanterObjects.Initialize( Octree::V_PT_OBJECTS__DEF_SIZE, Octree::V_PT_OBJECTS__RESIZE_STEP );
	m_SPUnitObjStock.Initialize( Octree::V_SPU_OBJECTS__DEF_SIZE, Octree::V_SPU_OBJECTS__DEF_RESIZE_STEP );
	m_ValidScatterParticleUnitObjects.Initialize( Octree::V_SPU_OBJECTS__DEF_SIZE, Octree::V_SPU_OBJECTS__DEF_RESIZE_STEP );
	m_TempValidActorModelObjects.Initialize( Octree::V_AM_OBJECTS__DEF_SIZE, Octree::V_AM_OBJECTS__RESIZE_STEP );
	m_TempValidShadowActorModelObjects.Initialize( Octree::V_AM_OBJECTS__DEF_SIZE, Octree::V_AM_OBJECTS__RESIZE_STEP );

#endif //_DEBUG
}

Octree::~Octree( void )
{
	Release();
}

Boolean Octree::NeedsInitialize( const Mix::Vector3& aabbMin, const Mix::Vector3& aabbMax, UInt32 level ) const
{
	if( ( m_bInit == False ) ||
		( m_Bounds.min != aabbMin ) ||
		( m_Bounds.max != aabbMax ) ||
		( m_Level != level ) )
	{
		return True;
	}

	return False;
}

Boolean Octree::Initialize( const Mix::Vector3& aabbMin, const Mix::Vector3& aabbMax, UInt32 level )
{
	MIX_ASSERT( level <= Octree::MAX_LEVEL );
	MIX_ASSERT( m_bInit == False );
	MIX_ASSERT( m_ppNodes == NULL );
	MIX_ASSERT( m_ppRefreshNodes == NULL );

	////////////////////////////////////////////////////////////////////////////////////////////////////

	m_NodeMax = ( m_Pows[level + 1] - 1 ) / 7;

	m_pIllegalNode = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::IllegalOctreeNode, this, 0xFFFFFFFF );
	if( m_pIllegalNode == NULL )
	{
		return False;
	}

	m_ppNodes = MIX_LIB_NEW_ARRAY_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::OctreeNode*, m_NodeMax );
	if( m_ppNodes != NULL )
	{
		for( UInt32 i = 0; i < m_NodeMax; i++ )
		{
			m_ppNodes[i] = NULL;
		}
	}
	else
	{
		return False;
	}

	m_ppRefreshNodes = MIX_LIB_NEW_ARRAY_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::OctreeNode*, m_NodeMax );
	if( m_ppRefreshNodes != NULL )
	{
		for( UInt32 i = 0; i < m_NodeMax; i++ )
		{
			m_ppRefreshNodes[i] = NULL;
		}
	}
	else
	{
		return False;
	}

#ifdef _DEBUG

	m_pDebVisibleNodes = MIX_LIB_MALLOC_T( Mix::Memory::SECTION_SCENE, UInt32, m_NodeMax );
	if( m_pDebVisibleNodes != NULL )
	{
		Mix::Memory::Zero( m_pDebVisibleNodes, sizeof( UInt32 ) * m_NodeMax );
	}
	else
	{
		return False;
	}

#endif //_DEBUG

	////////////////////////////////////////////////////////////////////////////////////////////////////

	m_Level = level;

	m_Bounds.min = aabbMin;
	m_Bounds.max = aabbMax;
	m_Bounds.ComputePoints();

	m_BoundsMin = aabbMin;
	m_BoundsMax = aabbMax;

	m_Unit = ( m_Bounds.max - m_Bounds.min ) / ( static_cast<float>( 1 << m_Level ) );
	m_InvUnit.x = MIX_FLOAT_RECIPROCAL( m_Unit.x );
	m_InvUnit.y = MIX_FLOAT_RECIPROCAL( m_Unit.y );
	m_InvUnit.z = MIX_FLOAT_RECIPROCAL( m_Unit.z );

	m_bInit = True;

	////////////////////////////////////////////////////////////////////////////////////////////////////

	MIX_LOG_INFO( L"八分木を初期化 : Name[%s] Level[%d] Min(%f, %f, %f) Max(%f, %f, %f) ] NodeMax[%d] Unit(%f %f %f)",
		m_Name.GetConstPtr(),
		m_Level,
		m_Bounds.min.x, m_Bounds.min.y, m_Bounds.min.z,
		m_Bounds.max.x, m_Bounds.max.y, m_Bounds.max.z,
		m_NodeMax,
		m_Unit.x, m_Unit.y, m_Unit.z );

	////////////////////////////////////////////////////////////////////////////////////////////////////

	return True;
}

void Octree::Release( void )
{
	MIX_ASSERT( m_DebLocalLightObjects.size() == 0 );
	MIX_ASSERT( m_DebWaterPoolObjects.size() == 0 );
	MIX_ASSERT( m_DebPlanterObjects.size() == 0 );
	MIX_ASSERT( m_DebLeavingParticleObjects.size() == 0 );
	MIX_ASSERT( m_DebSPUnitObjects.size() == 0 );
	MIX_ASSERT( m_DebActorModelObjects.size() == 0 );

	UInt32 spUnitNum = m_SPUnitObjStock.GetCount();

#ifdef _DEBUG
	for( UInt32 i = 0; i < m_ViewList.size(); i++ )
	{
		MIX_ASSERT( m_ViewList[i]->Debug_HasValidObjects() == False );
	}
#endif //_DEBUG

	for( UInt32 i = 0; i < spUnitNum; i++ )
	{
		Mix::Scene::Common::ScatterParticleUnitObject* pSPUnitObj = m_SPUnitObjStock[i];
		MIX_LIB_DELETE_T( ScatterParticleUnitObject, pSPUnitObj )
	}

	MIX_LIB_DELETE_PTR_ARRAY_T( m_ppRefreshNodes );
	MIX_LIB_DELETE_T( IllegalOctreeNode, m_pIllegalNode );

	if( m_ppNodes != NULL )
	{
		for( UInt32 i = 0; i < m_NodeMax; i++ )
		{
			MIX_LIB_DELETE_T( OctreeNode, m_ppNodes[i] );
		}

		MIX_LIB_DELETE_PTR_ARRAY_T( m_ppNodes );
	}

	m_NodeMax = 0;
	m_NodeNum = 0;
	m_RefreshNodeNum = 0;
	m_Level = 0;
	m_Bounds.min = Mix::Vector3::Zero();
	m_Bounds.max = Mix::Vector3::Zero();
	m_Unit.Set( 0.0f, 0.0f, 0.0f );
	m_InvUnit.Set( 0.0f, 0.0f, 0.0f );

#ifdef _DEBUG
	MIX_LIB_FREE( m_pDebVisibleNodes );
#endif //_DEBUG

	m_bInit = False;
}

UInt32 Octree::GetNodeMax( void ) const
{
	return m_NodeMax;
}

UInt32 Octree::GetNodeNum( void ) const
{
	return m_NodeNum;
}

const Mix::Geometry::AABB& Octree::GetBounds( void ) const
{
	return m_Bounds;
}

const Mix::Vector3& Octree::GetUnit( void ) const
{
	return m_Unit;
}

UInt32 Octree::GetViewCount( void ) const
{
	return MIX_UIT_TO_UI32( m_ViewList.size() );
}

Mix::Scene::Common::OctreeView* Octree::AddView( void )
{
	MIX_ASSERT( m_ViewList.size() < Mix::Scene::Common::OCTREE_VIEW_MAX );

	Mix::String name;
	Mix::Scene::Common::OctreeView* pView;

	name.Sprintf( L"%s/OctreeView", m_Name.GetConstPtr() );

	pView = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::OctreeView, this, m_ViewDataStack.back(), name.GetConstPtr() );
	MIX_ASSERT( pView != NULL );

	m_ViewList.push_back( pView );
	m_ViewDataStack.pop_back();

	return pView;
}

Mix::Scene::Common::LocalLightObject* Octree::AddLocalLight( Mix::Scene::Common::PointLight* pPointLight )
{
	MIX_ASSERT( pPointLight != NULL );
	MIX_ASSERT( Debug_ContainsObject( m_DebLocalLightObjects, pPointLight ) == False );

	Mix::Scene::Common::OctreeNode* pNode;
	Mix::Scene::Common::PointLightObject* pObj;

	pNode = GetNode( GetMortonCode( pPointLight->GetBounds() ) );
	MIX_ASSERT( pNode != NULL );

	pObj = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::PointLightObject, pNode, pPointLight );
	MIX_ASSERT( pObj != NULL );

#ifdef _DEBUG
	m_DebLocalLightObjects.push_back( pObj );
#endif //_DEBUG

	return pObj;
}

Mix::Scene::Common::LocalLightObject* Octree::AddLocalLight( Mix::Scene::Common::SpotLight* pSpotLight )
{
	MIX_ASSERT( pSpotLight != NULL );
	MIX_ASSERT( Debug_ContainsObject( m_DebLocalLightObjects, pSpotLight ) == False );

	Mix::Scene::Common::OctreeNode* pNode;
	Mix::Scene::Common::SpotLightObject* pObj;

	pNode = GetNode( GetMortonCode( pSpotLight->GetBounds() ) );
	MIX_ASSERT( pNode != NULL );

	pObj = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::SpotLightObject, pNode, pSpotLight );
	MIX_ASSERT( pObj != NULL );

#ifdef _DEBUG
	m_DebLocalLightObjects.push_back( pObj );
#endif //_DEBUG

	return pObj;
}

Mix::Scene::Common::WaterPoolObject* Octree::AddWaterPool( Mix::Scene::Common::WaterPool* pWaterPool )
{
	MIX_ASSERT( pWaterPool != NULL );
	MIX_ASSERT( Debug_ContainsObject( m_DebWaterPoolObjects, pWaterPool ) == False );

	const Mix::Geometry::AABB& bounds = pWaterPool->GetBounds();

	Mix::Scene::Common::OctreeNode* pNode;
	Mix::Scene::Common::WaterPoolObject* pObj;

	pNode = GetNode( GetMortonCode( bounds.min, bounds.max ) );
	MIX_ASSERT( pNode != NULL );

	pObj = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::WaterPoolObject, pNode, pWaterPool );
	MIX_ASSERT( pObj != NULL );

#ifdef _DEBUG
	m_DebWaterPoolObjects.push_back( pObj );
#endif //_DEBUG

	return pObj;
}

Mix::Scene::Common::PlanterObject* Octree::AddPlanter( Mix::Scene::Common::Planter* pPlanter )
{
	MIX_ASSERT( pPlanter != NULL );
	MIX_ASSERT( Debug_ContainsObject( m_DebPlanterObjects, pPlanter ) == False );

	const Mix::Geometry::AABB& bounds = pPlanter->GetBounds();

	Mix::Scene::Common::OctreeNode* pNode;
	Mix::Scene::Common::PlanterObject* pObj;

	pNode = GetNode( GetMortonCode( bounds.min, bounds.max ) );
	MIX_ASSERT( pNode != NULL );

	pObj = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::PlanterObject, pNode, pPlanter );
	MIX_ASSERT( pObj != NULL );

#ifdef _DEBUG
	m_DebPlanterObjects.push_back( pObj );
#endif //_DEBUG

	return pObj;
}

Mix::Scene::Common::LeavingParticleObject* Octree::AddLeavingParticle( Mix::Scene::Common::LeavingParticle* pParticle )
{
	MIX_ASSERT( pParticle != NULL );
	MIX_ASSERT( Debug_ContainsObject( m_DebLeavingParticleObjects, pParticle ) == False );

	const Mix::Geometry::AABB& bounds = pParticle->GetBounds();

	Mix::Scene::Common::OctreeNode* pNode;
	Mix::Scene::Common::LeavingParticleObject* pObj;

	pNode = GetNode( GetMortonCode( bounds.min, bounds.max ) );
	MIX_ASSERT( pNode != NULL );

	pObj = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::LeavingParticleObject, m_CurBits, pNode, pParticle );
	MIX_ASSERT( pObj != NULL );

#ifdef _DEBUG
	m_DebLeavingParticleObjects.push_back( pObj );
#endif //_DEBUG

	return pObj;
}

Mix::Scene::Common::ScatterParticleUnitObject* Octree::AddScatterParticleUnit( Mix::Scene::Common::ScatterParticleUnit* pParticleUnit )
{
	MIX_ASSERT( pParticleUnit != NULL );
	MIX_ASSERT( Debug_ContainsObject( m_DebSPUnitObjects, pParticleUnit ) == False );

	const Mix::Geometry::Sphere& bounds = pParticleUnit->GetBounds();

	Mix::Scene::Common::OctreeNode* pNode;
	Mix::Scene::Common::ScatterParticleUnitObject* pObj;

	pNode = GetNode( GetMortonCode( bounds ) );
	MIX_ASSERT( pNode != NULL );

	if( m_SPUnitObjStock.IsEmpty() == False )
	{
		pObj = m_SPUnitObjStock.PopBack();
	}
	else
	{
		pObj = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::ScatterParticleUnitObject );
	}

	MIX_ASSERT( pObj != NULL );

	pObj->Initialize( pNode, pParticleUnit );

#ifdef _DEBUG
	m_DebSPUnitObjects.push_back( pObj );
#endif //_DEBUG

	return pObj;
}

Mix::Scene::Common::ActorModelObject* Octree::AddActorModel( Mix::Scene::Common::ActorModel* pModel )
{
	MIX_ASSERT( pModel != NULL );
	MIX_ASSERT( Debug_ContainsObject( m_DebActorModelObjects, pModel ) == False );

	Mix::Scene::Common::OctreeNode* pNode;
	Mix::Scene::Common::ActorModelObject* pObj;

	pNode = GetNode( GetMortonCode( pModel->GetBounds() ) );
	MIX_ASSERT( pNode != NULL );

	pObj = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::ActorModelObject, m_CurBits, pNode, pModel );
	MIX_ASSERT( pObj != NULL );

#ifdef _DEBUG
	m_DebActorModelObjects.push_back( pObj );
#endif //_DEBUG

	return pObj;
}

void Octree::Refresh( void )
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	// デバッグ : ノードのチェック
	////////////////////////////////////////////////////////////////////////////////////////////////////

#ifdef _DEBUG
	if( m_ppNodes[0] != NULL )
	{
		Debug_CheckNode( 0 );
	}
#endif //_DEBUG

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// ノードのリフレッシュ
	////////////////////////////////////////////////////////////////////////////////////////////////////

	if( m_RefreshNodeNum > 0 )
	{
		Mix::Scene::Common::OctreeNode** ppNode = &( m_ppRefreshNodes[0] );
		Mix::Scene::Common::OctreeNode** ppNodeEnd = ppNode + m_RefreshNodeNum;

		//子→親へソート
		SortRefreshNodes( m_ppRefreshNodes, 0, m_RefreshNodeNum - 1 );

		while( ppNode != ppNodeEnd )
		{
			MIX_ASSERT( ( *ppNode ) != NULL );

			( *ppNode )->Refresh();

			ppNode++;
		}


		m_RefreshNodeNum = 0;
	}
}

void Octree::RenderBegin( void )
{
	m_ValidLocalLightObjects.Clear();
	m_ValidWaterPoolObjects.Clear();
	m_ValidPlanterObjects.Clear();
	m_ValidScatterParticleUnitObjects.Clear();
	m_TempValidActorModelObjects.Clear();
	m_TempValidShadowActorModelObjects.Clear();
}

void Octree::RenderColor( const Mix::Geometry::Frustum& frustum )
{
#ifdef _DEBUG
	Mix::Memory::Zero( m_pDebVisibleNodes, sizeof( UInt32 ) * m_NodeMax );
	m_DebVisibleNodeCount = 0;
#endif //_DEBUG

	if( m_ppNodes[0] != NULL )
	{
		RenderColor( 0, frustum, m_CurBits[Mix::Scene::Common::OCTREE_VIEW_COLOR] );
	}
}

void Octree::RenderShadow( const Mix::Geometry::Sphere& bounds )
{
	if( m_ppNodes[0] != NULL )
	{
		RenderShadow( 0, bounds, m_CurBits[Mix::Scene::Common::OCTREE_VIEW_SHADOW] );
	}
}

void Octree::RenderEnd( void )
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	// パーティクルオブジェクト : 特に無し
	////////////////////////////////////////////////////////////////////////////////////////////////////

	;

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// アクターモデルオブジェクト : カラーとシャドウを分ける
	////////////////////////////////////////////////////////////////////////////////////////////////////

	if( m_pCurValidActorModelObjects->IsEmpty() == False )
	{
		UInt32 objStart;

		//C→S→SC の順にソート( C=COLOR S=SHADOW )
		Octree::SortValidObjects( m_pCurValidActorModelObjects->GetBeginPtr(), 0, m_pCurValidActorModelObjects->GetCount() - 1, m_CurMask );

		//ソートされた有効リストから C→S→SC の順に取り出していく
		objStart = Octree::AppendValidObjects( m_TempValidActorModelObjects, *m_pCurValidActorModelObjects, 0, m_CurMask, m_CurBits[Mix::Scene::Common::OCTREE_VIEW_COLOR] );
		objStart = Octree::AppendValidObjects( m_TempValidShadowActorModelObjects, *m_pCurValidActorModelObjects, objStart, m_CurMask, m_CurBits[Mix::Scene::Common::OCTREE_VIEW_SHADOW] );
		Octree::AppendValidObjects( m_TempValidActorModelObjects, m_TempValidShadowActorModelObjects, *m_pCurValidActorModelObjects, objStart, m_CurMask );
	}
}

void Octree::ValidView( Mix::Scene::Common::OCTREE_VIEW_TYPE viewType )
{
	MIX_ASSERT( m_pCurView != NULL );

	m_pCurView->Valid( viewType );
}

void Octree::Finish( void )
{
	size_t viewCount = m_ViewList.size();

	if( viewCount == 0 )
	{
		return;
	}

	Mix::Scene::Common::OctreeView** ppView = &( m_ViewList[0] );
	Mix::Scene::Common::OctreeView** ppViewEnd = ppView + viewCount;

	while( ppView != ppViewEnd )
	{
		( *ppView )->Finish();
		ppView++;
	}
}

const Mix::ContainerT<Mix::Scene::Common::LocalLightObject*, Mix::Memory::SECTION_SCENE>& Octree::GetValidLocalLightObjects( void ) const
{
	return m_ValidLocalLightObjects;
}

const Mix::ContainerT<Mix::Scene::Common::WaterPoolObject*, Mix::Memory::SECTION_SCENE>& Octree::GetValidWaterPoolObjects( void ) const
{
	return m_ValidWaterPoolObjects;
}

const Mix::ContainerT<Mix::Scene::Common::PlanterObject*, Mix::Memory::SECTION_SCENE>& Octree::GetValidPlanterObjects( void ) const
{
	return m_ValidPlanterObjects;
}

const Mix::ContainerT<Mix::Scene::Common::LeavingParticleObject*, Mix::Memory::SECTION_SCENE>& Octree::GetValidLeavingParticleObjects( void ) const
{
	MIX_ASSERT( m_pCurValidLeavingParticleObjects != NULL );

	return *m_pCurValidLeavingParticleObjects;
}

const Mix::ContainerT<Mix::Scene::Common::ScatterParticleUnitObject*, Mix::Memory::SECTION_SCENE>& Octree::GetValidScatterParticleUnitObjects( void ) const
{
	return m_ValidScatterParticleUnitObjects;
}

const Mix::ContainerT<Mix::Scene::Common::ActorModelObject*, Mix::Memory::SECTION_SCENE>& Octree::GetValidActorModelObjects( void ) const
{
	return m_TempValidActorModelObjects;
}

const Mix::ContainerT<Mix::Scene::Common::ActorModelObject*, Mix::Memory::SECTION_SCENE>& Octree::GetValidShadowActorModelObjects( void ) const
{
	return m_TempValidShadowActorModelObjects;
}

#ifdef _DEBUG

UInt32 Octree::Debug_GetIllegalLocalLightNum( void ) const
{
	return m_pIllegalNode->Debug_GetLocalLightNum();
}

UInt32 Octree::Debug_GetIllegalWaterPoolNum( void ) const
{
	return m_pIllegalNode->Debug_GetWaterPoolNum();
}

UInt32 Octree::Debug_GetIllegalPlanterNum( void ) const
{
	return m_pIllegalNode->Debug_GetPlanterNum();
}

UInt32 Octree::Debug_GetIllegalLeavingParticleNum( void ) const
{
	return m_pIllegalNode->Debug_GetLeavingParticleNum();
}

UInt32 Octree::Debug_GetIllegalScatterParticleUnitNum( void ) const
{
	return m_pIllegalNode->Debug_GetScatterParticleUnitNum();
}

UInt32 Octree::Debug_GetIllegalActorModelNum( void ) const
{
	return m_pIllegalNode->Debug_GetActorModelNum();
}

void Octree::Debug_CheckNode( UInt32 nodeIndex )
{
	MIX_ASSERT( m_NodeMax > nodeIndex );

	Mix::Scene::Common::OctreeNode* pNode = m_ppNodes[nodeIndex];
	MIX_ASSERT( pNode != NULL );

	UInt32 childs = pNode->GetChilds();
	if( childs == 0 )
	{
		return;
	}

	UInt32 childNodeIndex;
	UInt32 i;

	for( i = 0; i < 8; i++ )
	{
		childNodeIndex = ( nodeIndex << 3 ) + 1 + i;

		if( MIX_TESTBIT( childs, ( 1 << i ) ) != 0 )
		{
			MIX_ASSERT( m_ppNodes[childNodeIndex] != NULL );
			Debug_CheckNode( childNodeIndex );
		}
		else
		{
			MIX_ASSERT( m_ppNodes[childNodeIndex] == NULL );
		}
	}
}

void Octree::Debug_Draw( Mix::Graphics::Utility::IPerspectiveRenderer* pPerspectiveRenderer, UInt32 flags )
{
	MIX_ASSERT( pPerspectiveRenderer != NULL );
	MIX_ASSERT( m_ppNodes != NULL );
	MIX_ASSERT( m_pDebVisibleNodes != NULL );

	Mix::Scene::Common::OctreeNode** ppNode = &( m_ppNodes[0] );
	Mix::Scene::Common::OctreeNode** ppNodeEnd = ppNode + m_NodeMax;

	while( ppNode != ppNodeEnd )
	{
		Mix::Scene::Common::OctreeNode* pNode = *ppNode;

		if( pNode != NULL )
		{
			UInt32 nodeIndex = pNode->GetIndex();

			if( MIX_TESTBIT( m_pDebVisibleNodes[ nodeIndex >> 5 ], 1 << ( nodeIndex % 32 ) ) != 0 )
			{
				pNode->Debug_Draw( pPerspectiveRenderer, flags );
			}
		}

		ppNode++;
	}
}

#endif //_DEBUG

////////////////////////////////////////////////////////////////////////////////////////////////////
// Private
////////////////////////////////////////////////////////////////////////////////////////////////////

void Octree::SwitchView( Mix::Scene::Common::OctreeView* pView )
{
	MIX_ASSERT( pView != NULL );
	MIX_ASSERT( pView->m_pOwner == this );

	const Mix::Scene::Common::OCTREE_VIEW_DATA& data = pView->m_Data;

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 必要なものを展開しておく
	////////////////////////////////////////////////////////////////////////////////////////////////////

	m_pCurView = pView;

	m_CurBits[Mix::Scene::Common::OCTREE_VIEW_COLOR] = data.colBit;
	m_CurBits[Mix::Scene::Common::OCTREE_VIEW_SHADOW] = data.sdwBit;
	m_CurMask = data.mask;

	m_pCurValidLeavingParticleObjects = &( m_pCurView->m_ValidLeavingParticleObjects );
	m_pCurValidActorModelObjects = &( m_pCurView->m_ValidActorModelObjects );
}

void Octree::DestroyView( Mix::Scene::Common::OctreeView* pView )
{
	MIX_ASSERT( pView != NULL );
	MIX_ASSERT( pView->m_pOwner == this );
	MIX_ASSERT( std::find( m_ViewDataStack.begin(), m_ViewDataStack.end(), pView->m_Data ) == m_ViewDataStack.end() );

	//現在のビューだったら NULL に設定
	if( m_pCurView == pView )
	{
		m_pCurView = NULL;

		m_CurBits[Mix::Scene::Common::OCTREE_VIEW_COLOR] = 0;
		m_CurBits[Mix::Scene::Common::OCTREE_VIEW_SHADOW] = 0;
		m_CurMask = 0;

		m_pCurValidLeavingParticleObjects = NULL;
		m_pCurValidActorModelObjects = NULL;
	}

	//ビューのデータを返す
	m_ViewDataStack.push_back( pView->m_Data );

	//ビューをリストから削除
	Mix::STL::Vector_FirstErase( m_ViewList, pView );
}

void Octree::AttachObject( UInt32 nodeIndex, Mix::Scene::Common::LocalLightObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( pObj->m_pNode == NULL );
	MIX_ASSERT( pObj->m_pPrev == NULL );
	MIX_ASSERT( pObj->m_pNext == NULL );

	GetNode( nodeIndex )->AttachObject( pObj );
}

void Octree::AttachObject( UInt32 nodeIndex, Mix::Scene::Common::WaterPoolObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( pObj->m_pNode == NULL );
	MIX_ASSERT( pObj->m_pPrev == NULL );
	MIX_ASSERT( pObj->m_pNext == NULL );

	GetNode( nodeIndex )->AttachObject( pObj );
}

void Octree::AttachObject( UInt32 nodeIndex, Mix::Scene::Common::PlanterObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( pObj->m_pNode == NULL );
	MIX_ASSERT( pObj->m_pPrev == NULL );
	MIX_ASSERT( pObj->m_pNext == NULL );

	GetNode( nodeIndex )->AttachObject( pObj );
}

void Octree::AttachObject( UInt32 nodeIndex, Mix::Scene::Common::LeavingParticleObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( pObj->m_pNode == NULL );
	MIX_ASSERT( pObj->m_pPrev == NULL );
	MIX_ASSERT( pObj->m_pNext == NULL );

	GetNode( nodeIndex )->AttachObject( pObj );
}

void Octree::AttachObject( UInt32 nodeIndex, Mix::Scene::Common::ScatterParticleUnitObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( pObj->m_pNode == NULL );
	MIX_ASSERT( pObj->m_pPrev == NULL );
	MIX_ASSERT( pObj->m_pNext == NULL );

	GetNode( nodeIndex )->AttachObject( pObj );
}

void Octree::AttachObject( UInt32 nodeIndex, Mix::Scene::Common::ActorModelObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( pObj->m_pNode == NULL );
	MIX_ASSERT( pObj->m_pPrev == NULL );
	MIX_ASSERT( pObj->m_pNext == NULL );

	GetNode( nodeIndex )->AttachObject( pObj );
}

void Octree::DetachObject( Mix::Scene::Common::LocalLightObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( Mix::STL::Vector_FirstErase( m_DebLocalLightObjects, pObj ) == True );
}

void Octree::DetachObject( Mix::Scene::Common::WaterPoolObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( Mix::STL::Vector_FirstErase( m_DebWaterPoolObjects, pObj ) == True );
}

void Octree::DetachObject( Mix::Scene::Common::PlanterObject* pObj )
{
	MIX_ASSERT( pObj != NULL );
	MIX_ASSERT( Mix::STL::Vector_FirstErase( m_DebPlanterObjects, pObj ) == True );
}

void Octree::DetachObject( Mix::Scene::Common::LeavingParticleObject* pObj )
{
	MIX_ASSERT( pObj != NULL );

	//ビューから削除
	Octree::DestroyObjectFromView( m_ViewList, pObj );

	//デバッグ : 自身から削除
	MIX_ASSERT( Mix::STL::Vector_FirstErase( m_DebLeavingParticleObjects, pObj ) == True );
}

void Octree::DetachObject( Mix::Scene::Common::ScatterParticleUnitObject* pObj )
{
	MIX_ASSERT( pObj != NULL );

	//返却
	m_SPUnitObjStock.Add( pObj );

	//デバッグ : 自身から削除
	MIX_ASSERT( Mix::STL::Vector_FirstErase( m_DebSPUnitObjects, pObj ) == True );
}

void Octree::DetachObject( Mix::Scene::Common::ActorModelObject* pObj )
{
	MIX_ASSERT( pObj != NULL );

	//ビューから削除
	Octree::DestroyObjectFromView( m_ViewList, pObj );

	//デバッグ : 自身から削除
	MIX_ASSERT( Mix::STL::Vector_FirstErase( m_DebActorModelObjects, pObj ) == True );
}

Boolean Octree::RefreshNode( Mix::Scene::Common::OctreeNode* pNode )
{
	MIX_ASSERT( pNode != NULL );

	if( pNode->IsReqRefresh() == True )
	{
		//すでにリフレッシュ要求( OctreeNode::m_Flags != 0 )がでている
		//もしくわ、イリーガルノード
		return False;
	}

	MIX_ASSERT( m_RefreshNodeNum < m_NodeMax );

	m_ppRefreshNodes[m_RefreshNodeNum] = pNode;
	m_RefreshNodeNum++;

	RefreshParentNode( pNode );

	return True;
}

void Octree::RefreshParentNode( Mix::Scene::Common::OctreeNode* pChildNode )
{
	MIX_ASSERT( pChildNode != NULL );

	//ノードのインデックスを取得
	UInt32 parentNodeIndex = ( pChildNode->GetIndex() - 1 ) >> 3;
	if( parentNodeIndex >= m_NodeMax )
	{
		return;
//		parentNodeIndex = 0;
	}

	//ノードを取得
	Mix::Scene::Common::OctreeNode* pParentNode = m_ppNodes[parentNodeIndex];
	if( ( pParentNode == NULL ) ||
		( pParentNode->IsReqRefresh() == True ) )
	{
		return;
	}

	//ノードに境界のリフレッシュをリクエスト
	pParentNode->ReqRefreshBounds();

	//リフレッシュするノードを追加
	MIX_ASSERT( m_RefreshNodeNum < m_NodeMax );
	m_ppRefreshNodes[m_RefreshNodeNum] = pParentNode;
	m_RefreshNodeNum++;

	//親を処理
	RefreshParentNode( pParentNode );
}

void Octree::RenderColor( UInt32 nodeIndex, const Mix::Geometry::Frustum& frustum, UInt32 bit )
{
	MIX_ASSERT( m_NodeMax > nodeIndex );
	MIX_ASSERT( m_ppNodes[nodeIndex] != NULL );
	MIX_ASSERT( m_pDebVisibleNodes != NULL );

	Mix::Scene::Common::OctreeNode* pNode = m_ppNodes[nodeIndex];

	Mix::Scene::Common::LocalLightObject* pLLObj;
	Mix::Scene::Common::WaterPoolObject* pWPObj;
	Mix::Scene::Common::PlanterObject* pPTObj;
	Mix::Scene::Common::LeavingParticleObject* pLPCObj;
	Mix::Scene::Common::ScatterParticleUnitObject* pSPUnitObj;
	Mix::Scene::Common::ActorModelObject* pAMObj;

	UInt32 childs;
	UInt32 childNodeStart;
	UInt32 i;

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// ノードの境界がフラスタムに含まれているかをチェック
	////////////////////////////////////////////////////////////////////////////////////////////////////

	if( frustum.Contains( pNode->GetBounds() ) == False )
	{
		return;
	}

#ifdef _DEBUG
	m_pDebVisibleNodes[ nodeIndex >> 5 ] |= 1 << ( nodeIndex % 32 );
	m_DebVisibleNodeCount++;
#endif //_DEBUG

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// オブジェクトを収集
	////////////////////////////////////////////////////////////////////////////////////////////////////

	pLLObj = pNode->GetLocalLightObjects();
	pWPObj = pNode->GetWaterPoolObjects();
	pPTObj = pNode->GetPlanterObjects();
	pLPCObj = pNode->GetLeavingParticleObjects();
	pSPUnitObj = pNode->GetScatterParticleUnitObjects();
	pAMObj = pNode->GetActorModelObjects();

	// ローカルライト
	while( pLLObj != NULL )
	{
		if( pLLObj->IsEnabled() == True )
		{
			m_ValidLocalLightObjects.Add( pLLObj );
		}

		pLLObj = pLLObj->m_pNext;
	}

	// ウォータープール
	while( pWPObj != NULL )
	{
		m_ValidWaterPoolObjects.Add( pWPObj );

		pWPObj = pWPObj->m_pNext;
	}

	// プランター
	while( pPTObj != NULL )
	{
		if( pPTObj->IsEnabled() == True )
		{
			m_ValidPlanterObjects.Add( pPTObj );
		}

		pPTObj = pPTObj->m_pNext;
	}

	// リービングパーティクル
	while( pLPCObj != NULL )
	{
		if( ( pLPCObj->m_NxtState & m_CurMask ) == 0 )
		{
			m_pCurValidLeavingParticleObjects->Add( pLPCObj );
		}

		MIX_SETBIT( pLPCObj->m_NxtState, bit );

		pLPCObj = pLPCObj->m_pNext;
	}

	// スキャッターパーティクルユニット
	while( pSPUnitObj != NULL )
	{
		m_ValidScatterParticleUnitObjects.Add( pSPUnitObj );

		pSPUnitObj = pSPUnitObj->m_pNext;
	}

	// アクター
	while( pAMObj != NULL )
	{
		if( ( pAMObj->m_NxtState & m_CurMask ) == 0 )
		{
			m_pCurValidActorModelObjects->Add( pAMObj );
		}

		MIX_SETBIT( pAMObj->m_NxtState, bit );

		pAMObj = pAMObj->m_pNext;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 子を処理
	////////////////////////////////////////////////////////////////////////////////////////////////////

	childs = pNode->GetChilds();
	childNodeStart = ( nodeIndex << 3 ) + 1;

	// 子空間へ移動
	for( i = 0; i < 8; i++ )
	{
		if( MIX_TESTBIT( childs, ( 1 << i ) ) != 0 )
		{
			RenderColor( childNodeStart + i, frustum, bit );
		}
	}
}

void Octree::RenderShadow( UInt32 nodeIndex, const Mix::Geometry::Sphere& bounds, UInt32 bit )
{
	MIX_ASSERT( m_NodeMax > nodeIndex );
	MIX_ASSERT( m_ppNodes[nodeIndex] != NULL );

	Mix::Scene::Common::OctreeNode* pNode = m_ppNodes[nodeIndex];

	Mix::Scene::Common::ActorModelObject* pAMObj;

	UInt32 childs;
	UInt32 childNodeStart;
	UInt32 i;

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 境界をチェック
	////////////////////////////////////////////////////////////////////////////////////////////////////

	if( Mix::Geometry::IntersectSphereAABB( bounds, pNode->GetBounds() ) == False )
	{
		return;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 収集
	////////////////////////////////////////////////////////////////////////////////////////////////////

	pAMObj = pNode->GetActorModelObjects();

	/*
		アクターモデル
	*/

	while( pAMObj != NULL )
	{
		if( ( pAMObj->m_NxtState & m_CurMask ) == 0 )
		{
			m_pCurValidActorModelObjects->Add( pAMObj );
		}

		MIX_SETBIT( pAMObj->m_NxtState, bit );

		pAMObj = pAMObj->m_pNext;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 子を処理
	////////////////////////////////////////////////////////////////////////////////////////////////////

	childs = pNode->GetChilds();
	childNodeStart = ( nodeIndex << 3 ) + 1;

	/*
		子空間へ移動
	*/

	for( i = 0; i < 8; i++ )
	{
		if( MIX_TESTBIT( childs, ( 1 << i ) ) != 0 )
		{
			RenderShadow( childNodeStart + i, bounds, bit );
		}
	}
}

void Octree::InvalidObject( Mix::Scene::Common::OCTREE_VIEW_TYPE viewType, Mix::Scene::Common::LeavingParticleObject* pObj )
{
	MIX_ASSERT( pObj != NULL );

	MIX_RESETBIT( pObj->m_NxtState, m_CurBits[viewType] );
}

void Octree::InvalidObject( Mix::Scene::Common::OCTREE_VIEW_TYPE viewType, Mix::Scene::Common::ActorModelObject* pObj )
{
	MIX_ASSERT( pObj != NULL );

	MIX_RESETBIT( pObj->m_NxtState, m_CurBits[viewType] );
}

Mix::Scene::Common::OctreeNode* Octree::GetNode( UInt32 nodeIndex )
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 早期チェック
	////////////////////////////////////////////////////////////////////////////////////////////////////

	if( nodeIndex > m_NodeMax )
	{
		return m_pIllegalNode;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////

	UInt32 index;
	UInt32 childs;
	UInt32 childNodeIndex;
	UInt32 i;

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 親へ向かって作成していく
	////////////////////////////////////////////////////////////////////////////////////////////////////

	index = nodeIndex;

	while( m_ppNodes[index] == NULL )
	{
		m_ppNodes[index] = MIX_LIB_NEW_T( Mix::Memory::SECTION_SCENE, Mix::Scene::Common::DefaultOctreeNode, this, index );
		MIX_ASSERT( m_ppNodes[index] != NULL );
		m_NodeNum++;

		//次(親)のインデックス
		index = ( index - 1 ) >> 3;
		if( index >= m_NodeMax )
		{
			break;
		}
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 子ビットを更新
	////////////////////////////////////////////////////////////////////////////////////////////////////

	index = nodeIndex;

	while( index < m_NodeMax )
	{
		childs = 0;

		for( i = 0; i < 8; i++ )
		{
			childNodeIndex = ( index << 3 ) + 1 + i;

			if( ( childNodeIndex < m_NodeMax ) &&
				( m_ppNodes[childNodeIndex] != NULL ) )
			{
				childs |= ( 1 << i );
			}
		}

		m_ppNodes[index]->SetChilds( childs );

		index = ( index - 1 ) >> 3;
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////

	return m_ppNodes[nodeIndex];
}

Boolean Octree::GetChildBounds( Mix::Scene::Common::OctreeNode* pNode, Mix::Geometry::AABB& bounds )
{
	MIX_ASSERT( pNode != NULL );

	UInt32 nodeIndex = pNode->GetIndex();
	UInt32 childs = pNode->GetChilds();
	UInt32 childNodeCount = 0;

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 境界をリセット
	////////////////////////////////////////////////////////////////////////////////////////////////////

	bounds.min.Set( +MIX_FLOAT_MAX, +MIX_FLOAT_MAX, +MIX_FLOAT_MAX );
	bounds.max.Set( -MIX_FLOAT_MAX, -MIX_FLOAT_MAX, -MIX_FLOAT_MAX );

	////////////////////////////////////////////////////////////////////////////////////////////////////
	// 境界を結合
	////////////////////////////////////////////////////////////////////////////////////////////////////

	childs = pNode->GetChilds();

	if( childs != 0 )
	{
		UInt32 childNodeStart = ( nodeIndex << 3 ) + 1;

		for( UInt32 i = 0; i < 8; i++ )
		{
			if( MIX_TESTBIT( childs, ( 1 << i ) ) != 0 )
			{
				bounds += m_ppNodes[childNodeStart + i]->GetBounds();
				childNodeCount++;
			}
		}
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////

	return ( childNodeCount > 0 );
}

UInt32 Octree::GetMortonCode( const Mix::Vector3& aabbMin, const Mix::Vector3& aabbMax )
{
	if( ( m_BoundsMin.x > aabbMax.x ) || ( m_BoundsMin.y > aabbMax.y ) || ( m_BoundsMin.z > aabbMax.z ) ||
		( m_BoundsMax.x < aabbMin.x ) || ( m_BoundsMax.y < aabbMin.y ) || ( m_BoundsMax.z < aabbMin.z ) )
	{
		//有効範囲外
		return 0xFFFFFFFF;
	}

	UInt32 LT = GetPointElement( aabbMin );
	UInt32 RB = GetPointElement( aabbMax );

	UInt32 def = RB ^ LT;
	UInt32 maxLevel = 1;

	UInt32 i;
	UInt32 temp;

	for( i = 0; i < m_Level; i++ )
	{
		temp = ( def >> ( i * 3 ) ) & 0x7;
		if( temp != 0 )
		{
			maxLevel = i + 1;
		}
	}

#if 1

	UInt32 nodeIndex = ( RB >> ( maxLevel * 3 ) ) + ( ( m_Pows[m_Level - maxLevel] - 1 ) / 7 );

	return ( nodeIndex <= m_NodeMax )? nodeIndex : 0xFFFFFFFF;

#else

	UInt32 spaceNum = RB >> ( maxLevel * 3 );
	UInt32 addNum = ( m_Pows[m_Level - maxLevel] - 1 ) / 7;

	spaceNum += addNum;
	if( spaceNum > m_NodeMax )
	{
		//イリーガルノードに入れるために 0xFFFFFFFF を返す
		return 0xFFFFFFFF;
	}

	return spaceNum;

#endif
}

UInt32 Octree::GetMortonCode( const Mix::Geometry::Sphere& bounds )
{
	Float32 radius = bounds.radius;
	const Mix::Vector3& center = bounds.center;

	Mix::Vector3 aabbMin( center.x - radius, center.y - radius, center.z - radius );
	Mix::Vector3 aabbMax( center.x + radius, center.y + radius, center.z + radius );

	return GetMortonCode( aabbMin, aabbMax );
}

UInt32 Octree::GetMortonCode( UInt8 x, UInt8 y, UInt8 z )
{
	return BitSeparate( x ) | ( BitSeparate( y ) << 1 ) | ( BitSeparate( z ) << 2 );
}

UInt32 Octree::BitSeparate( UInt8 n )
{
	DWORD ret = n;

	ret = ( ret | ret << 8 ) & 0x0000f00f;
	ret = ( ret | ret << 4 ) & 0x000c30c3;
	ret = ( ret | ret << 2 ) & 0x00249249;

	return ret;
}

UInt32 Octree::GetPointElement( const Mix::Vector3& p )
{
	UInt8 x = static_cast<BYTE>( ( p.x - m_BoundsMin.x ) * m_InvUnit.x );
	UInt8 y = static_cast<BYTE>( ( p.y - m_BoundsMin.y ) * m_InvUnit.y );
	UInt8 z = static_cast<BYTE>( ( p.z - m_BoundsMin.z ) * m_InvUnit.z );

	return GetMortonCode( x, y, z );
}

void Octree::SortRefreshNodes( Mix::Scene::Common::OctreeNode** list, Int32 first, Int32 last )
{
	const Mix::Scene::Common::OctreeNode* pNode  = list[( first + last ) >> 1];

	UInt32 sortKey = pNode->GetIndex();

	Int32 i = first;
	Int32 j = last;

	do
	{
		while( list[i]->GetIndex() > sortKey ) { i++; }
		while( list[j]->GetIndex() < sortKey ) { j--; }

		if( i <= j )
		{
			MIX_ASSERT( ( i <= last ) && ( j >= first ) );

			Mix::Scene::Common::OctreeNode* pTempNode = list[i];

			list[i] = list[j];
			list[j] = pTempNode;

			i++;
			j--;
		}

	}while( i <= j );

	if( first < j ) { Octree::SortRefreshNodes( list, first, j ); }
	if( i < last ) { Octree::SortRefreshNodes( list, i, last ); }
}

}}}
