自訂八分樹

在計算機繪圖學中，八分樹是一個常用來加速查詢場景中物件的一種資料結構。UE本身就擁有數個用途不同的八分樹，除了PrimitiveComponent用的八分樹，其他大都利用TOctree類別模板來定義：

template<typename ElementType, typename OctreeSemantics>
class TOctree;

ElementType可以視為跟STL容器的value type是一樣的東西，至於OctreeSemantics則是用來設定八分樹的參數，或是提供八分樹類別操作ElementType物件的方法。其實就是所謂的traits。

OctreeSemantics需要提供的成員如下：

• MaxElementsPerLeaf：每個葉節點的最大能容納的元素。當新增元素會超過此上限時，會分割葉節點。
• MaxNodeDepth：最大樹深。
• GetBoundingBox：傳回元素的邊界盒。
• SetElementId：TOctree會給予元素一個ID。移除元素時會用到這個ID。

TOctree提供TConstIterator用來巡曳節點，以及TConstElementBoxIterator用來在指定區域巡曳元素。

跟一般的八分樹比較不一樣的地方是，TOctree的卦限大小會膨漲八分之一邊長，同一個父節點的卦限間會有互相重疊的區域，但不同分支下的卦限不會重疊。

範例

以下程式碼展示如何為自訂的Actor建立自己的八分樹。先列出自訂的Actor：

class MyActor extends Actor
    native
    placeable;
    
var() DrawBoxComponent BoxComponent;

var const native OctreeElementId OctreeId{FOctreeElementId};

cpptext
{
    void AddToOctree();
    void RemoveFromOctree();
    
    // UObject interface
    virtual void BeginDestroy();
    
    // AActor interface
    virtual void UpdateComponentsInternal(UBOOL bCollisionUpdate = FALSE);
}

defaultpropeties
{
    bStatic=true
    
    begin object class=DrawBoxComponent name=BoxComp
        BoxColor=(R=128,G=0,B=128,A=255)
        BoxExtent=(X=100.0,Y=100.0,Z=50.0)
        bDrawWireBox=true
        HiddenGame=false
    end object
    BoxComponent=BoxComp
    Components.Add(BoxComp)
}

MyActor是靜態Actor，利用DrawBoxComponent的方塊大小當成它所佔的空間。建立時會自動加入八分樹，消失時會自動從八分樹中移除。

以下是自訂的OctreeSemantics：

struct FMyOctreeSemantics
{
    enum { MaxElementsPerLeaf = 16 };
    enum { MaxNodeDepth = 10 };
    
    typedef TInlineAllocator<MaxElementsPerLeaf> ElementAllocator;
    
    static FBoxCenterAndExtent GetBoundingBox(AMyActor* Actor);
    {
        return FBoxCenterAndExtent(Actor->Location, Actor->BoxComponent->BoxExtent);
    }
    
    static void SetElementId(AMyActor* Actor, FOctreeElementId Id)
    {
        Actor->OctreeId = Id;
    }   
};

利用自訂的OctreeSemantics定義客製八分樹：

class FMyOctreeType : public TOctree<AMyActor*, FMyOctreeSemantics>
{
public:

    FMyOctreeType(const FVector& InOrigin, FLOAT InExtent)
        : TOctree(InOrigin, InExtent)
        , RootNodeBounds(InOrigin, InExtent)
    {
    }
    
    void Draw(FPrimitiveDrawInterface* PDI, FColor DrawColor);
    
protected:

    FOctreeNodeBounds RootNodeBounds;
};

void FMyOctreeType::Draw(FPrimitiveDrawInterface* PDI, FColor DrawColor)
{
    TConstIterator<DefaultStackAllocator> It(*this);
    
    while( It.HasPendingNodes() )
    {
        const FNode& CurrNode = It.GetCurrentNode();
        const FOctreeNodeContext& CurrContext = It.GetCurrentContext();
        
        DrawWireBox(PDI, CurrContext.Bounds.GetBox(), DrawColor, SDPG_World);
        
        FOREACH_OCTREE_CHILD_NODE(ChildRef)
        {
            if( CurrNode.HasChild(ChildRef) )
            {
                It.PushChild(ChildRef);
            }
            
            It.Advance();
        }
    }
}

FMyOctreeType GMyOctree( FVector::ZeroVector, HALF_WORLD_MAX );

上一行中定義一個全域的八分樹以供MyActor加入之用。FMyOctreeType中另外加了一個Draw函式示範如何使用八分樹的迭代子。

最後列出MyActor的函式實作部分：

void AMyActor::BeginDestroy()
{
    RemoveFromOctree();
    Super::BeginDestroy();
}
    
void AMyActor::UpdateComponentsInternal(UBOOL bCollisionUpdate)
{
    if( GIsEdtor && !GIsCooking && !GIsPlayInEditorWorld && !GIsUCC )
    {
        AddToOctree();
    }
    
    Super::UpdateComponentsInternal(bCollisionUpdate);
}

void AMyActor::AddToOctree()
{
    if( OctreeId.IsValidId() )
    {
        GMyOctree.RemoveElment(OctreeId);
        OctreeId = FOctreeElementId();
    }
    
    GMyOctree.AddElement(this);
}

void AMyActor::RemoveFromOctree()
{
    if( OctreeId.IsValidId() )
    {
        GMyOctree.RemoveElment(OctreeId);
    }
    
    OctreeId = FOctreeElementId();
}