很久沒貼程式碼了，據說blog 要注重單一話題做定時更新才會有人氣，這對我來說還蠻難的~
Scene Tree，很多人討厭這東西。但是對我而言， 大型 3D 程式沒有 tree 根本活不下去。
在這邊貼出我的 Scene Tree，感覺上還有些 bug，如果有誰發現就請告知一下。
主體可使用 map 或 hash_map，blog 上沒辦法縮排，有興趣看的人請自便吧。
順便一提，用 hash_map 是 47 號同學的主意。
#ifndef SceneTreeNode_H
#define SceneTreeNode_H
#pragma once
#ifndef _XBOX
#include <windows.h>
#endif
#ifdef _XBOX
#include <xtl.h>
#endif
#include <d3dx9math.h>
#include <string>
#include "safemacro.h"
//#include "SceneTreeNode.h"
/*
use std::map for now,
we can change it into hash_map later
*/
#include <map>
class CSceneTreeNode;
typedef std::map<std::string, CSceneTreeNode*> SceneTreeMap;
typedef std::map<std::string, CSceneTreeNode*>::iterator SceneTreeMapIterator;
typedef std::pair<std::string, CSceneTreeNode*> SceneTreePair;
typedef std::pair<SceneTreeMapIterator,bool> SceneTreeOperationReturnValue;
class CSceneTreeNode
{
public:
CSceneTreeNode();
virtual ~CSceneTreeNode();
///////////////////////////////////////////////////////////////////////////
//scene tree operation
///////////////////////////////////////////////////////////////////////////
//And new node, return new node pointer, return NULL if fail
CSceneTreeNode* AddNewChildNode(std::string* pName);
//And kill all it's child node
HRESULT DeleteChildNode(std::string* pName);
// If this node's parent isn't NULL, call DisAttachThisNodeFromParent() automatically
HRESULT AttachThisNodeToNewParent(CSceneTreeNode* pNewParent);
// split node from parent , this node will be new tree root
HRESULT DisAttachThisNodeFromParent();
void DeleteAllChild();
CSceneTreeNode* FindChildNodeByName(std::string* pName);
CSceneTreeNode* GetParentNode();
///////////////////////////////////////////////////////////////////////////
//node matrix operation
///////////////////////////////////////////////////////////////////////////
HRESULT SetLocalMatrix(D3DXMATRIX* pMatrix);
HRESULT SetGlobalMatrix(D3DXMATRIX* pMatrix);
const D3DXMATRIX* GetLocalMatrix();
const D3DXMATRIX* GetGlobalMatrix();
// flag == true 才 update
HRESULT UpdateChildNode();
// flag == false 就 recursive , flag == true 就呼叫 UpdateChildNode();
HRESULT UpdateChildNodeFromSceneRoot();
protected:
//flag operation (self dirty)
HRESULT SetAllChildNeedUpdateFlag(bool bFlag);
//flag operation (some child dirty)
HRESULT SetAllParentSomeChildNeedUpdate(bool bFlag);
std::string m_Name;
SceneTreeMap m_ChildNodeMap;
D3DXMATRIX m_LocalMatrix;
D3DXMATRIX m_GlobalMatrix;
/*
m_bSomeChildNeedUpdateFlag => reduce recursive pass
m_bNeedUpdateFlag => reduce matrix multiplication
*/
bool m_bNeedUpdateFlag;
bool m_bSomeChildNeedUpdateFlag;
CSceneTreeNode* m_pParent;
};
#endif
// 上面是 h , 下面是 cpp
#include "SceneTreeNode.h"
CSceneTreeNode::CSceneTreeNode()
{
m_Name = "";
m_pParent = NULL;
m_bNeedUpdateFlag = false;
m_bSomeChildNeedUpdateFlag = false;
D3DXMatrixIdentity(&m_LocalMatrix);
D3DXMatrixIdentity(&m_GlobalMatrix);
}
CSceneTreeNode::~CSceneTreeNode()
{
if(m_ChildNodeMap.empty() == false)
{
DeleteAllChild();
}
m_pParent = NULL;
}
///////////////////////////////////////////////////////////////////////////
//scene tree operation
///////////////////////////////////////////////////////////////////////////
CSceneTreeNode* CSceneTreeNode::AddNewChildNode(std::string* pName)
{
SceneTreeMapIterator pos;
pos = m_ChildNodeMap.find(*pName);
if( pos == m_ChildNodeMap.end() )
{
CSceneTreeNode* pNewSceneTreeNode = new CSceneTreeNode;
m_ChildNodeMap.insert(SceneTreePair(*pName, pNewSceneTreeNode));
pNewSceneTreeNode->SetGlobalMatrix(&m_GlobalMatrix);
pNewSceneTreeNode->m_pParent = this;
return pNewSceneTreeNode;
}
return NULL;
}
HRESULT CSceneTreeNode::DeleteChildNode(std::string* pName)
{
SceneTreeMapIterator pos;
pos = m_ChildNodeMap.find(*pName);
if( pos != m_ChildNodeMap.end() )
{
SAFE_DELETE(pos->second);
return S_OK;
}
return E_FAIL;
}
HRESULT CSceneTreeNode::AttachThisNodeToNewParent(CSceneTreeNode* pNewParent)
{
if(m_pParent != NULL)
DisAttachThisNodeFromParent();
SceneTreeOperationReturnValue result;
result = (pNewParent->m_ChildNodeMap).insert(SceneTreePair(m_Name, this));
if(result.second ==false)
return E_FAIL;
m_pParent = pNewParent;
return S_OK;
}
HRESULT CSceneTreeNode::DisAttachThisNodeFromParent()
{
if(!m_pParent)
return E_FAIL;
SceneTreeMapIterator pos;
pos = (m_pParent->m_ChildNodeMap).find(m_Name);
if(pos == (m_pParent->m_ChildNodeMap).end())
return E_FAIL;
pos->second = NULL;
(m_pParent->m_ChildNodeMap).erase(pos);
m_pParent = NULL;
return S_OK;
}
void CSceneTreeNode::DeleteAllChild()
{
SceneTreeMapIterator pos;
//DeleteAllChild recursive
for(pos = m_ChildNodeMap.begin(); pos!=m_ChildNodeMap.end(); ++pos)
{
pos->second->DeleteAllChild();
SAFE_DELETE(pos->second);
//m_ChildNodeMap.~map();
}
//clean the Node Map
if(m_ChildNodeMap.begin() != m_ChildNodeMap.end())
m_ChildNodeMap.erase(m_ChildNodeMap.begin(),m_ChildNodeMap.end());
}
CSceneTreeNode* CSceneTreeNode::FindChildNodeByName(std::string* pName)
{
SceneTreeMapIterator pos;
pos = m_ChildNodeMap.find(*pName);
if(pos != m_ChildNodeMap.end())
{
return pos->second;
}
else
return NULL;
}
CSceneTreeNode* CSceneTreeNode::GetParentNode()
{
return m_pParent;
}
///////////////////////////////////////////////////////////////////////////
//node matrix operation
///////////////////////////////////////////////////////////////////////////
HRESULT CSceneTreeNode::SetLocalMatrix(D3DXMATRIX* pMatrix)
{
if(pMatrix)
{
m_LocalMatrix = *pMatrix;
SetAllChildNeedUpdateFlag(true);
SetAllParentSomeChildNeedUpdate(true);
return S_OK;
}
return E_FAIL;
}
HRESULT CSceneTreeNode::SetGlobalMatrix(D3DXMATRIX* pMatrix)
{
//注意矩陣乘法順序
//[L] * [Par_G] = [G]
//[L] = [G] * [Par_G]^-1
if(pMatrix)
{
m_GlobalMatrix = *pMatrix;
SetAllChildNeedUpdateFlag(true);
SetAllParentSomeChildNeedUpdate(true);
if(m_pParent != NULL)
{
D3DXMATRIX ParentGlobalMatrixInverse;
D3DXMatrixInverse( &ParentGlobalMatrixInverse, NULL, &(m_pParent->m_GlobalMatrix));
D3DXMatrixMultiply( &m_LocalMatrix, &m_GlobalMatrix, &ParentGlobalMatrixInverse);
}
else
{
m_LocalMatrix = m_GlobalMatrix;
}
m_bNeedUpdateFlag = false;
return S_OK;
}
return E_FAIL;
}
const D3DXMATRIX* CSceneTreeNode::GetLocalMatrix()
{
return &m_LocalMatrix;
}
const D3DXMATRIX* CSceneTreeNode::GetGlobalMatrix()
{
return &m_GlobalMatrix;
}
HRESULT CSceneTreeNode::UpdateChildNode()
{
//注意矩陣乘法順序
//[L] * [Par_G] = [G]
if(m_bNeedUpdateFlag == true)
{
if(m_pParent != NULL)
{
D3DXMatrixMultiply( &m_GlobalMatrix, &m_LocalMatrix, &(m_pParent->m_GlobalMatrix));
}
else
{
m_GlobalMatrix = m_LocalMatrix;
}
m_bNeedUpdateFlag = false;
m_bSomeChildNeedUpdateFlag = false;
SceneTreeMapIterator pos;
for(pos = m_ChildNodeMap.begin(); pos!=m_ChildNodeMap.end(); ++pos)
{
pos->second->UpdateChildNode();
}
return S_OK;
}
return E_FAIL;
}
HRESULT CSceneTreeNode::UpdateChildNodeFromSceneRoot()
{
// keep on looking, while some child dirty
if(m_bSomeChildNeedUpdateFlag == false)
{
return S_OK;
}
if(m_bNeedUpdateFlag == true)
{
UpdateChildNode();
return S_OK;
}
SceneTreeMapIterator pos;
for(pos = m_ChildNodeMap.begin(); pos!=m_ChildNodeMap.end(); ++pos)
{
pos->second->UpdateChildNodeFromSceneRoot();
m_bSomeChildNeedUpdateFlag = false;
}
return S_OK;
}
// protected functions
HRESULT CSceneTreeNode::SetAllChildNeedUpdateFlag(bool bFlag)
{
if( bFlag == m_bNeedUpdateFlag)
{
return E_FAIL;
}
m_bNeedUpdateFlag = bFlag;
SceneTreeMapIterator pos;
for(pos = m_ChildNodeMap.begin(); pos!=m_ChildNodeMap.end(); ++pos)
{
pos->second->SetAllChildNeedUpdateFlag(bFlag);
}
return S_OK;
}
HRESULT CSceneTreeNode::SetAllParentSomeChildNeedUpdate(bool bFlag)
{
if(bFlag == m_bSomeChildNeedUpdateFlag)
{
return E_FAIL;
}
m_bSomeChildNeedUpdateFlag = bFlag;
if(m_pParent != NULL)
m_pParent->SetAllParentSomeChildNeedUpdate(bFlag);
return S_OK;
}
