C++ In Practice - Quad Trees, Object Pools

Spatial Partitioning (Quadtrees) in C++11

Problem 1: Viewport Culling (Spatial Query)

Input: An arbitrary distribution of 2D entities, each defined by an Axis-Aligned Bounding Box (AABB), and a singular dynamic AABB representing the active camera viewport.

Condition: Executing a linear intersection test against the entire entity pool requires CPU operations per frame. As the dataset scales, this strict linear scan exceeds frame time budgets.

Output: A localized subset of entities strictly intersecting the viewport boundaries. Spatial partitioning guarantees the isolation of this subset in operations, where represents the matching entities, structurally bypassing the evaluation of off-screen data.

Problem 2: Broad-Phase Collision Detection

Input: A dynamic system of moving 2D geometric entities requiring continuous physical overlap resolution.

Condition: Fine-grained narrow-phase collision math (e.g., Separating Axis Theorem, precise polygonal intersection) is computationally expensive. Evaluating all possible entity pairs necessitates an brute-force calculation.

Output: An aggregated list of potential collision pairs. By mapping entities to a spatial hierarchy, the algorithm identifies localized proximities, returning only entities sharing a geometric quadrant. This curtails the problem space, restricting the expensive narrow-phase calculations strictly to objects that are confirmed to share local coordinate space.

These problems can be solved using a Quadtree. A strictly didactic Quadtree utilizes a "Strict Containment" strategy. An object is stored exactly once in the deepest hierarchical node that entirely encapsulates its bounding box. Objects straddling boundary lines are trapped in the parent node. This eliminates duplication and simplifies mental modeling.

ASCII Execution State

Spatial Plane (Bounding Box 0,0 to 100,100):

(0,0)
  +-------------------------+-------------------------+
  | NW Quadrant             | NE Quadrant             |
  |                         |        [Obj B]          |
  |                         |                         |
  |                         |                         |
  +-------------------------+-------------------------+
  | SW Quadrant       [Obj A (Straddling)]            |
  |                         |                         |
  |       [Obj C]           |                         |
  |                         |                         |
  +-------------------------+-------------------------+
                                                (100,100)

Tree Representation:

Root Node (Level 0, Bounds: 0,0,100,100)
|-- Stored Objects: [Obj A]  <-- Trapped at root due to straddling the vertical axis.
|
|-- NW Child (Level 1)
|   |-- Stored Objects: []
|
|-- NE Child (Level 1)
|   |-- Stored Objects: [Obj B]
|
|-- SW Child (Level 1)
|   |-- Stored Objects: [Obj C]
|
|-- SE Child (Level 1)
    |-- Stored Objects: []

Implementation

#include <vector>
#include <memory>
#include <iostream>

struct Rect {
    float x, y, width, height;

    // Checks if this rectangle completely encapsulates the target.
    bool contains(const Rect& target) const {
        return (target.x >= x && target.x + target.width <= x + width &&
                target.y >= y && target.y + target.height <= y + height);
    }

    // Checks if this rectangle overlaps the target.
    bool intersects(const Rect& target) const {
        return !(x > target.x + target.width || 
                 x + target.width < target.x || 
                 y > target.y + target.height || 
                 y + target.height < target.y);
    }
};

struct SpatialObject {
    int id;
    Rect bounds;
};

class QuadTree {
    static const int MAX_OBJECTS = 4;
    static const int MAX_LEVELS = 5;

    int level;
    Rect bounds;
    std::vector<SpatialObject> objects;
    
    // std::unique_ptr enforces strict ownership. 
    // The parent node uniquely owns its four geometric subdivisions.
    std::unique_ptr<QuadTree> nodes[4];

    // Determines which quadrant entirely encapsulates the object.
    // Returns -1 if the object straddles a boundary.
    int getIndex(const Rect& objBounds) const {
        int index = -1;
        float verticalMidpoint = bounds.x + (bounds.width / 2.0f);
        float horizontalMidpoint = bounds.y + (bounds.height / 2.0f);

        bool fitsTop = (objBounds.y < horizontalMidpoint && objBounds.y + objBounds.height < horizontalMidpoint);
        bool fitsBottom = (objBounds.y > horizontalMidpoint);
        bool fitsLeft = (objBounds.x < verticalMidpoint && objBounds.x + objBounds.width < verticalMidpoint);
        bool fitsRight = (objBounds.x > verticalMidpoint);

        if (fitsTop) {
            if (fitsLeft) index = 0;      // NW
            else if (fitsRight) index = 1; // NE
        } else if (fitsBottom) {
            if (fitsLeft) index = 2;      // SW
            else if (fitsRight) index = 3; // SE
        }

        return index;
    }

    // Subdivides the current node into four equal quadrants.
    void split() {
        float subWidth = bounds.width / 2.0f;
        float subHeight = bounds.height / 2.0f;
        float x = bounds.x;
        float y = bounds.y;

        nodes[0] = std::make_unique<QuadTree>(level + 1, Rect{x, y, subWidth, subHeight});
        nodes[1] = std::make_unique<QuadTree>(level + 1, Rect{x + subWidth, y, subWidth, subHeight});
        nodes[2] = std::make_unique<QuadTree>(level + 1, Rect{x, y + subHeight, subWidth, subHeight});
        nodes[3] = std::make_unique<QuadTree>(level + 1, Rect{x + subWidth, y + subHeight, subWidth, subHeight});
    }

public:
    QuadTree(int pLevel, Rect pBounds) : level(pLevel), bounds(pBounds) {}

    void insert(const SpatialObject& obj) {
        // If the node has active subdivisions, attempt to push the object down.
        if (nodes[0] != nullptr) {
            int index = getIndex(obj.bounds);
            if (index != -1) {
                nodes[index]->insert(obj);
                return;
            }
        }

        // If the object straddles a boundary (index == -1) OR there are no subdivisions,
        // it must be stored in the current node.
        objects.push_back(obj);

        // Evaluate subdivision criteria.
        if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
            if (nodes[0] == nullptr) {
                split();
            }

            // Redistribute existing objects to newly created children if possible.
            int i = 0;
            while (i < objects.size()) {
                int index = getIndex(objects[i].bounds);
                if (index != -1) {
                    nodes[index]->insert(objects[i]);
                    // Overwrite the migrated object with the last element and shrink the vector.
                    objects[i] = objects.back();
                    objects.pop_back();
                } else {
                    // Object straddles, must remain in this node.
                    i++;
                }
            }
        }
    }

    void retrieve(std::vector<SpatialObject>& returnObjects, const Rect& searchArea) const {
        // Find which quadrant the search area resides in.
        int index = getIndex(searchArea);

        // If the search area fits perfectly in a child, traverse down.
        if (index != -1 && nodes[0] != nullptr) {
            nodes[index]->retrieve(returnObjects, searchArea);
        } else if (nodes[0] != nullptr) {
            // If the search area straddles boundaries, we must check all children that intersect it.
            for (int i = 0; i < 4; ++i) {
                if (nodes[i]->bounds.intersects(searchArea)) {
                    nodes[i]->retrieve(returnObjects, searchArea);
                }
            }
        }

        // Add all objects stored at this specific hierarchical level.
        // The caller will perform the final precise intersection test.
        for (const auto& obj : objects) {
            returnObjects.push_back(obj);
        }
    }
};

Under the Hood Mechanics

The Straddling Constraint

The fundamental limitation of the strict containment architecture is the straddling constraint. If an object is placed exactly in the center of the root bounding box, it intersects the vertical and horizontal division axes. getIndex() will return -1.

Consequently, the object is permanently anchored to the Root node, regardless of its physical size. When the retrieve() function is invoked, every object trapped at the Root node is yielded to the caller for intersection testing, bypassing the logarithmic culling advantages of the spatial tree.

Redistribution State Reversal

During the split() operation, the node iterates through its locally stored objects and re-evaluates them against the newly created children. If an object fits entirely within a child, it is migrated, and the local objects vector is compacted. This is a destructive read pattern (objects[i] = objects.back(); objects.pop_back();). It operates in time per element, avoiding the penalty of std::vector::erase.

Quad Tree Production Optimizations

The problem statement describes a classic "Broad Phase" collision detection or visibility culling scenario. A high-performance C++ implementation must address memory layout, pointer chasing, and the cost of dynamic allocation.

In C++, we do not want to allocate QuadTreeNode objects individually on the heap (new QuadTreeNode). This causes memory fragmentation and destroys cache locality.

C++11 Architecture: The Linear Quadtree

Instead of a pointer-based tree, we can use a Linear Quadtree (stored in a std::vector) or a Region-Based Memory Pool. Given the "infinite canvas" requirement, a pointer-based tree with a custom allocator is often the most flexible balance.

Data Structures:

#include <vector>
#include <memory>
#include <algorithm>
#include <cmath>

// Simple POD (Plain Old Data) for geometry
struct Rect {
    float x, y, width, height;

    bool intersects(const Rect& other) const {
        return !(x > other.x + other.width || 
                 x + other.width < other.x || 
                 y > other.y + other.height || 
                 y + other.height < other.y);
    }
    
    bool contains(const Rect& other) const {
        return (other.x >= x && other.x + other.width <= x + width &&
                other.y >= y && other.y + other.height <= y + height);
    }
};

struct SpatialObject {
    int id;
    Rect bounds;
};

// Optimization: Use a Pool Allocator for Nodes to ensure cache locality
// For this example, we'll use std::unique_ptr for clarity, but in production,
// a std::vector<QuadTreeNode> with indices (int) instead of pointers is faster.

1. The QuadTreeNode Class

We use a MAX_OBJECTS threshold and MAX_DEPTH to prevent infinite recursion on overlapping points.

class QuadTreeNode {
    // Tuning parameters
    static const int MAX_OBJECTS = 8;
    static const int MAX_LEVELS = 10;

    int level;
    Rect bounds;
    std::vector<SpatialObject> objects;
    std::unique_ptr<QuadTreeNode> children[4]; // NW, NE, SW, SE
    bool isLeaf;

public:
    QuadTreeNode(int lvl, Rect b) : level(lvl), bounds(b), isLeaf(true) {
        for(int i=0; i<4; ++i) children[i] = nullptr;
    }

    // Split the node into 4 subnodes
    void split() {
        float subWidth = bounds.width / 2;
        float subHeight = bounds.height / 2;
        float x = bounds.x;
        float y = bounds.y;

        children[0] = std::unique_ptr<QuadTreeNode>(new QuadTreeNode(level + 1, {x, y, subWidth, subHeight})); // NW
        children[1] = std::unique_ptr<QuadTreeNode>(new QuadTreeNode(level + 1, {x + subWidth, y, subWidth, subHeight})); // NE
        children[2] = std::unique_ptr<QuadTreeNode>(new QuadTreeNode(level + 1, {x, y + subHeight, subWidth, subHeight})); // SW
        children[3] = std::unique_ptr<QuadTreeNode>(new QuadTreeNode(level + 1, {x + subWidth, y + subHeight, subWidth, subHeight})); // SE
        
        isLeaf = false;
    }

    // Determine which index(es) the object belongs to.
    // Returns a bitmask or list of indices. 
    // Optimization: If object overlaps lines, it might need to go into parent, 
    // or be duplicated in multiple children.
    // Strategy: Insert into ALL intersecting children.
    void getIndices(const Rect& pRect, std::vector<int>& indices) {
        for (int i = 0; i < 4; ++i) {
            if (children[i]->bounds.intersects(pRect)) {
                indices.push_back(i);
            }
        }
    }

    void insert(SpatialObject obj) {
        // If node has children, try to push down
        if (!isLeaf) {
            std::vector<int> indices;
            getIndices(obj.bounds, indices);
            for (int index : indices) {
                children[index]->insert(obj);
            }
            return;
        }

        // If leaf, add object
        objects.push_back(obj);

        // Check for split
        if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
            split();
            // Redistribute existing objects
            while (!objects.empty()) {
                SpatialObject existing = objects.back();
                objects.pop_back();
                std::vector<int> indices;
                getIndices(existing.bounds, indices);
                for (int index : indices) {
                    children[index]->insert(existing);
                }
            }
        }
    }

    // Query Range
    void query(const Rect& range, std::vector<SpatialObject>& results) {
        // Pruning: handled by parent or initial call, but good to check
        if (!bounds.intersects(range)) return;

        // Add local objects
        for (const auto& obj : objects) {
            if (range.intersects(obj.bounds)) {
                results.push_back(obj);
            }
        }

        // Recurse
        if (!isLeaf) {
            for (int i = 0; i < 4; ++i) {
                if (children[i]->bounds.intersects(range)) {
                    children[i]->query(range, results);
                }
            }
        }
    }
};

2. Viewport Query & Deduplication

One tricky aspect of Quadtrees (where objects are stored in all intersecting leaves) is Deduplication. An object spanning the center of the canvas might be stored in all 4 children. A query covering the center will retrieve it 4 times.

C++ Solution: Use a std::vector + std::sort + std::unique (efficient) or std::unordered_set (easy but potentially slower due to allocation). For rendering 50k objects, sort/unique on the result vector usually beats set insertion overhead.

class QuadTree {
    std::unique_ptr<QuadTreeNode> root;

public:
    QuadTree(Rect bounds) {
        root = std::unique_ptr<QuadTreeNode>(new QuadTreeNode(0, bounds));
    }

    void insert(SpatialObject obj) {
        root->insert(obj);
    }

    std::vector<SpatialObject> query(Rect range) {
        std::vector<SpatialObject> results;
        root->query(range, results);

        // Deduplicate results based on ID
        std::sort(results.begin(), results.end(), 
            [](const SpatialObject& a, const SpatialObject& b) {
                return a.id < b.id;
            });
        
        auto last = std::unique(results.begin(), results.end(),
            [](const SpatialObject& a, const SpatialObject& b) {
                return a.id == b.id;
            });
        
        results.erase(last, results.end());
        return results;
    }
};

3. Handling Infinite Canvas (The Coordinate Problem)

Standard Quadtrees require fixed bounds. "Infinite" usually means "Very Large" (e.g., coordinate range of int32 or float). If the canvas is truly infinite (or sparse and growing), a spatial hash (Sparse Grid) might be better, or a Dynamic Quadtree that grows upwards (adding a new root) when objects go out of bounds.

Loose Quadtree (Optimization): To solve the issue of objects straddling boundaries being pushed deep into children (or duplicating), a Loose Quadtree expands the bounding box of the tree nodes (e.g., by 2x). An object is inserted into the node that fully contains it. This simplifies insertion but complicates queries slightly (overlap tests need to account for looseness).

4. Moving Objects (Mutation)

Updating a Quadtree is O(Remove) + O(Insert).

Optimization:

  1. Lazy Update: As mentioned, verify if the object moved enough to leave its current tree node. If it's still inside Node->bounds, you might not need to re-insert (though precise culling might degrade slightly).
  2. Double Buffering: If 1000 objects move per frame, rebuilding the tree might be faster than updating.
    • Static objects (backgrounds) in Tree A.
    • Dynamic objects (units, cursors) in Tree B (rebuilt every frame).

Summary: Spatial Partitioning

Feature Quadtree (Region) Grid (Uniform) BVH / R-Tree
Structure Recursive 4-way split Flat Array/Map Balanced Tree of rectangles
Best For Uneven distribution (Clumps) Uniform distribution Complex shapes, minimize overlap
Memory Tree nodes (Ptr/Index) Sparse Map / 2D Array Nodes + Bounds
Insert O(\text{depth}) O(1) O(\log N) (Complex rebalance)
Query O(\log N) O(1) lookup + Scan O(\log N)

Object Pool Architecture (C++11)

Under the Hood Implementation

  1. Contiguous Memory Block: A raw array of bytes. To prevent undefined behavior, this memory must satisfy the alignment requirements of the target type T. C++11 provides std::aligned_storage for this exact purpose.
  2. Intrusive Free List: To achieve zero-overhead tracking, unallocated blocks store a pointer to the next free block within their own memory footprint. This requires casting the raw bytes of an unallocated block into a void**.
  3. Placement New: Constructs an object at a pre-allocated memory address without calling standard operator new (which triggers heap allocation).
  4. Explicit Destruction: When returning an object to the pool, the destructor ~T() must be called explicitly to release internal resources before the memory is overwritten by the free list pointer.

Big O Complexity

  • Allocate: O(1) strictly bounded. One pointer dereference.
  • Deallocate: O(1) strictly bounded. One pointer reassignment.
  • Cache Locality: High. Traversal triggers linear cache line loads, maximizing memory bandwidth.

Data Types Memory allocated statically or dynamically as a single block. Internal pointers use raw hardware addresses.

ASCII Illustration

State: Initialized, 0 Allocations.
[ Block 0 ] -> [ Block 1 ] -> [ Block 2 ] -> nullptr
(Free List Head points to Block 0)

State: 1 Allocation.
[ Object A ]   [ Block 1 ] -> [ Block 2 ] -> nullptr
(Free List Head points to Block 1)

State: 2 Allocations, 1 Deallocation (A is freed).
[ Block 0 ] -> [ Block 2 ] -> nullptr
[ Object B ]
(Free List Head points to Block 0. Block 0 'next' points to Block 2)

C++11 Implementation: Zero-Overhead Static Object Pool

This implementation uses a fixed-size buffer. It generates zero heap allocations during runtime, making it compliant with safety-critical constraints (e.g., MISRA C++, DO-178C).

#include <type_traits>
#include <utility>
#include <cstdint>
#include <cassert>

template <typename T, std::size_t PoolSize>
class StaticObjectPool {
private:
    // Ensure the memory block respects the alignment requirements of T.
    // This prevents hardware traps on architectures like ARM that forbid unaligned access.
    typename std::aligned_storage<sizeof(T), alignof(T)>::type memory_[PoolSize];
    
    // Pointer to the first available block in the intrusive free list.
    void* free_list_head_;

public:
    StaticObjectPool() {
        // Assert that the object is large enough to hold a pointer.
        // If sizeof(T) < sizeof(void*), the intrusive free list corrupts memory.
        static_assert(sizeof(T) >= sizeof(void*), "Type T must be at least the size of a pointer.");

        free_list_head_ = &memory_[0];
        void** current = static_cast<void**>(free_list_head_);

        // Chain the blocks together. Each block stores the address of the next block.
        for (std::size_t i = 1; i < PoolSize; ++i) {
            *current = &memory_[i];
            current = static_cast<void**>(*current);
        }
        
        // Terminate the list
        *current = nullptr;
    }

    // Disable copy semantics to prevent memory corruption and double-frees.
    StaticObjectPool(const StaticObjectPool&) = delete;
    StaticObjectPool& operator=(const StaticObjectPool&) = delete;

    // Perfect forwarding allows construction directly in the allocated memory,
    // bypassing move/copy overhead.
    template <typename... Args>
    T* allocate(Args&&... args) {
        if (!free_list_head_) {
            return nullptr; // Pool exhaustion
        }

        // Pop the head of the free list
        void* allocated_block = free_list_head_;
        free_list_head_ = *static_cast<void**>(free_list_head_);

        // Placement new: Construct object T at the raw address
        return new (allocated_block) T(std::forward<Args>(args)...);
    }

    void deallocate(T* ptr) {
        if (!ptr) return;

        // 1. Explicitly call destructor to clean up the object's internal state.
        ptr->~T();

        // 2. Repurpose the object's memory block to store the free list pointer.
        void** block = reinterpret_cast<void**>(ptr);
        
        // 3. Push to the front of the free list (LIFO reuse increases cache warmth).
        *block = free_list_head_;
        free_list_head_ = block;
    }
};

Usage Scenario: Bypassing Sequence Container Fragmentation

When implementing a custom Red-Black Tree or Doubly Linked List, standard implementations allocate nodes sequentially via new. Over time, node creation and deletion fragment the heap. Successive node pointers scatter across physical memory. Traversing node->next results in continuous CPU cache misses, forcing the CPU to fetch from main memory (RAM), stalling execution by 100-300 clock cycles per fetch.

Injecting the StaticObjectPool into the node structure forces spatial locality.

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

void pointer_chasing_optimization() {
    // Allocates a strictly contiguous block in the data segment / stack.
    StaticObjectPool<TreeNode, 10000> node_pool;

    // Guaranteed O(1) allocation. 
    // Memory addresses are adjacent.
    TreeNode* root = node_pool.allocate(50);
    root->left = node_pool.allocate(25);
    root->right = node_pool.allocate(75);

    // Traversal down root->left triggers a cache hit, 
    // as hardware prefetchers load the contiguous bytes surrounding root.
    
    node_pool.deallocate(root->left);
    node_pool.deallocate(root->right);
    node_pool.deallocate(root);
}

C++ In Practice - Quad Trees | Bijup.com