Scene Tree

很久沒貼程式碼了，據說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;
}