深入了解Octree

一、Octrees

Octree是一種數據結構，常用於快速查找三維空間中的物體。Octree將三維空間劃分為立方體，並逐層細分，最終得到一個由小立方體組成的樹狀結構，每個小立方體稱為葉子節點。Octree葉子節點保存了相應的物體信息，如位置、大小等。

這個過程類似於將一棵三維的空間劃分成小塊，其中每個小塊都只負責一塊區域，而且它們的大小可以自行調節，比如將大三維空間劃分成一個32*32*32的正方體，每個正方體可以存儲一個物體的信息。如果這個正方體裡面還有其他的小塊，那麼就會繼續細分下去，直到臨界大小為止。

Octree主要用於處理視覺或物理模擬中需要訪問場景中多個對象的操作。例如，使用Octree可以檢測與一個物體相交的物體數量，或者在離相機較遠的物體上節省計算資源。

二、Octree演算法

Octree構建演算法通常使用遞歸演算法實現。該演算法基於如下步驟：

1. 創建Octree根節點

根節點代表整個三維空間。這個節點始終存在，直到Octree被銷毀。它包含八個子節點，因此被稱為「八叉樹」。

    class OctreeNode {
    public:
        OctreeNode(BoundingBox bbox) {
            m_bbox = bbox;
            for (int i = 0; i < 8; i++)
                m_children[i] = nullptr;
        }
        // ...
    private:
        BoundingBox m_bbox;
        OctreeNode* m_children[8];
    };

2. 判斷是否需要繼續細分

對於每個節點，判斷其邊界包圍盒是否包含場景中的任何物體或是否處於相機的視錐中。如果包含，則繼續細分此節點。

    void Build(OctreeNode* parent, std::vector