Scene Graph Traveler

這一篇，就當做給我自己的記錄吧。

Scene Graph Traveler是我自己取的物件名字，是一個獲准在Scene Graph的樹狀結構中逛大街的物件。之所以會設計這樣的物件，主要是要從一個最近冒出來的需求，來調整整個引擎在Scene Graph中的架構。

原本，我在引擎中有一個Frustum Culler物件，負責將Scene Graph中所有可被Frustum見到的節點蒐集起來，然後一一交給Renderer做繪製。Culler會以遞迴呼叫的方式，跑一遍Scene Graph的樹狀結構，檢查與節點的碰撞關係，如果節點已經被Culler剔除了，那麼節點的Sub-Tree就可以不必再計算。

Scene Graph的遞迴方式，就類似以下的Code

er_code CNode::OnGetVisibleSet(CCuller* culler)
{
    if (node in frustum)
    {
        culler->Insert(this);
     }
     else return ER_OK;

    if (m_ChildList.size()==0) return ER_OK;
    er_code er=ER_OK;
    ChildList::iterator iter=m_ChildList.begin();
    while (iter!=m_ChildList.end())
    {
        er=(*iter)->OnGetVisibleSet(culler);
        if (er) return er; 
        ++iter;
    }
    return ER_OK;
}

 

現在，需求來了。

我要用滑鼠指標點選場景裡面的一個物件，所以我將滑鼠的座標，轉換成場景空間中的一條射線。我叫它做Picker。

Picker搜尋物件的方式跟Culler很類似，也是需要跑一遍Scene Graph中的樹狀結構，檢查射線與節點的碰撞關係，如果射線與節點有碰撞，就繼續搜尋Sub-Tree，否則就可以不必再計算。

簡單的做法呢，就是Scene Graph中，再增加一個讓Picker遞迴的函式。不過這麼一來，我就讓Picker與Scene Graph綁在了一起。

所以這絕對不是好設計。

Culler與Picker在Scene Graph中的行為幾乎是相同的，所差別只在判斷是否要繼續搜尋Sub-Tree的方式。至於在樹狀結構中遞迴的方式則是完全相同。所以我將這行為抽離出來，變成了Scene Graph Traveler。

class CSceneTraveler
{
public:
    enum TravelResult
    {
        Travel_InterruptAll=0,
        Travel_Interrupt,
        Travel_SubTree,
    };
public:
    CSceneTraveler() {};
    virtual ~CSceneTraveler() {};
    virtual TravelResult TravelTo(CNode* ) =0;
};

這是一個抽象物件，需要在Scene Graph中逛大街的物件，都可以繼承它來取得在Scene Graph中遞迴的許可。所以，Culler以及Picker就從這個類別繼承出來，並且各自實作所需要的TravelTo函式。

而Scene Graph Node本身的函式，則是做了這樣的修改

CSceneTraveler::TravelResult CNode::VisitBy(CSceneTraveler* rpTraveler)
{
    if (!rpTraveler) return CSceneTraveler::Travel_InterruptAll;
    CSceneTraveler::TravelResult res=rpTraveler->TravelTo(this);
    if (res!=CSceneTraveler::Travel_SubTree) return res;  // don't go sub-tree
    if (m_ChildList.size()==0) return CSceneTraveler::Travel_Interrupt;
    ChildList::iterator iter=m_ChildList.begin();
    while (iter!=m_ChildList.end())
    {
        res=(*iter)->VisitBy(rpTraveler);
        if (res=CSceneTraveler::Travel_InterruptAll) return res;
        ++iter;
    }
    return res;
}

 

其實會這樣修改設計，還有一個原因。我的Scene Graph以及Culler是放在繪圖核心的模組裡，而Picker是在遊戲層的物件，為了保持物件之間關係的乾淨清爽，所以我並沒有直接用簡單的方法，把Picker綁在Scene Graph裡，而是將這個Traveler抽離了出來。

未來還會不會有其他的物件可以繼承這個相同的行為，我也不知道。