Octree

Octree Data Structure

class Octree : public Spatial
{
public:
    struct Node
    {
        AABB box;
        std::vector<int> tris;
        std::shared_ptr<Node> child[8] = {nullptr};
    };

    std::shared_ptr<Node> root = nullptr;
    int maxDepth = 8;
    int maxPerNode = 16;
    
    ...
};

Insert Triangle

    void InsertTri(std::shared_ptr<Node> n, int triIndex, int depth)
    {
        if (depth == maxDepth) {
            n->tris.push_back(triIndex);
            return;
        }

        Triangle t = getTriangle(triIndex);
        glm::vec3 triMin = glm::min(t.v0, glm::min(t.v1, t.v2));
        glm::vec3 triMax = glm::max(t.v0, glm::max(t.v1, t.v2));

        if (n->tris.size() < maxPerNode) {
            n->tris.push_back(triIndex);
            return;
        }

        if (n->child[0] == nullptr)
            Subdivide(n);

        for (int i = 0; i < 8; i++)
        {
            const AABB &b = n->child[i]->box;
            // AABB intersection
            if (!(triMax.x < b.min.x || triMin.x > b.max.x ||
                  triMax.y < b.min.y || triMin.y > b.max.y ||
                  triMax.z < b.min.z || triMin.z > b.max.z))
            {
                InsertTri(n->child[i], triIndex, depth + 1);
            }
        }
    }

QueryAABB

It checks if the query AABB intersects with the current octree node.

If there is an intersection, it adds all triangles in the current node and recursively checks its children.

    void QueryAABB(const AABB &box, std::vector<int> &out) const override
    {
        QueryNode(root, box, out);
    }
    
    void QueryNode(std::shared_ptr<Node> n, const AABB &box, std::vector<int> &out) const
    {
        if (n == nullptr)
            return;

        // AABB no intersection
        if (n->box.max.x < box.min.x || n->box.min.x > box.max.x ||
            n->box.max.y < box.min.y || n->box.min.y > box.max.y ||
            n->box.max.z < box.min.z || n->box.min.z > box.max.z)
            return;

        out.insert(out.end(), n->tris.begin(), n->tris.end());

        for (int i = 0; i < 8; i++)
            QueryNode(n->child[i], box, out);
    }

Raycast

bool Raycast(const Ray &ray, HitInfo &outHit) override
    {
        HitInfo best;
        best.t = FLT_MAX;
        best.triIndex = -1;

        bool result = RaycastNode(root, ray, best);
        if (result)
            outHit = best;
        return result;
    }
    
bool RaycastNode(std::shared_ptr<Node> n, const Ray &ray, HitInfo &best)
    {
        float t;

        if (!RayAABB(ray.origin, ray.dir, n->box.min, n->box.max, t))
            return false;

        bool hit = false;

        for (int triIdx : n->tris)
        {
            float tt;
            Triangle tri = getTriangle(triIdx);
            if (RayTriangle(ray, tri, tt) && tt < best.t)
            {
                best.t = tt;
                best.triIndex = triIdx;
                hit = true;
            }
        }

        for (int i = 0; i < 8; i++)
            if (n->child[i])
                hit |= RaycastNode(n->child[i], ray, best);

        return hit;
    }