Integrating Quadtrees for Spatial Stroke Partitioning

The Wrapper Pattern in Practice: DocumentLayer

Let's begin by integrating the Quadtree into our DocumentLayer class. As we discussed, this class will act as a "wrapper," owning both the definitive collection of all strokes and the spatial index that accelerates queries on them. This pattern, which you saw in the javidx9 video from our last lesson, is key to a clean and efficient design.

The DocumentLayer will contain two primary members:

1. std::list<Stroke> m_strokes: This is the "source of truth." We use std::list because its iterators are not invalidated when elements are added or removed elsewhere in the list, making them stable references.
2. Quadtree<std::list<Stroke>::iterator, ...> m_quadtree: This is our spatial index. It will not store heavy Stroke objects, but rather the stable iterators pointing to the strokes in m_strokes.

To instantiate our templated Quadtree, we need to provide the GetBox callable—a function that tells the Quadtree how to find the bounding box of a given item (in this case, an iterator). A simple lambda is perfect for this.

Here is what the header for DocumentLayer and its constructor will look like:

// In DocumentLayer.h



#pragma once




#include "Quadtree.h" // The Quadtree you built in the last lesson
#include "Stroke.h"   // Assumes Stroke class from Module 5
#include <list>

// A helper lambda to get the bounds of a stroke from its iterator.
// This can be defined in the .cpp file.
inline auto getStrokeBounds = [](const std::list<Stroke>::iterator& it) {
    return it->getBounds(); // Assumes Stroke has a getBounds() const method returning SkRect
};

class DocumentLayer {
public:
    using StrokeIterator = std::list<Stroke>::iterator;

    DocumentLayer(const SkRect& worldBounds);

    // Adds a new stroke to the document
    void addStroke(Stroke stroke);

    // ... other methods for querying, etc. will go here

private:
    // The master list of all strokes. This is the source of truth.
    std::list<Stroke> m_strokes;

    // The Quadtree, storing iterators into m_strokes.
    Quadtree<StrokeIterator, decltype(getStrokeBounds)> m_quadtree;
};


// In DocumentLayer.cpp
DocumentLayer::DocumentLayer(const SkRect& worldBounds)
    : m_quadtree(worldBounds, getStrokeBounds) {
    // The Quadtree is now initialized with the total canvas area
    // and the lambda function it needs to get bounding boxes.
}

Partitioning Strokes on Insertion

With the DocumentLayer set up, the core of spatial partitioning happens when a new stroke is added. The addStroke method needs to perform two actions: add the stroke to the master list and add its iterator to the Quadtree.

The process is straightforward:

1. Move the new Stroke object into the back of the m_strokes list.
2. Obtain an iterator to that newly added element. For std::list, std::prev(m_strokes.end()) gives an iterator to the last element.
3. Pass this stable iterator to the m_quadtree.add() method.

The Quadtree's internal logic, which you implemented in the last lesson, takes care of the rest, placing the iterator in the correct node based on the stroke's bounding box.

Here's the implementation of addStroke:

void DocumentLayer::addStroke(Stroke stroke) {
    // 1. Add the stroke object to the master list.
    m_strokes.push_back(std::move(stroke));

    // 2. Get a stable iterator to the newly added stroke.
    StrokeIterator it = std::prev(m_strokes.end());

    // 3. Add the iterator to the Quadtree for spatial indexing.
    m_quadtree.add(it);
}

That's it. Every time a user finishes drawing a line, it will be automatically indexed in our spatial data structure. As more strokes are added, the Quadtree will dynamically subdivide, ensuring that queries remain fast regardless of the document's complexity.

A Deeper Dive: Cache-Friendly Quadtrees

The pointer-based Quadtree you built is a fantastic, general-purpose implementation. However, given your interest in high-performance systems, it's worth exploring an alternative design that prioritizes CPU cache efficiency.

The implementation using std::unique_ptr for child nodes involves separate heap allocations for each node. When traversing the tree, this can lead to pointer chasing and cache misses, as nodes are not guaranteed to be contiguous in memory. An alternative is to store all nodes in a single, contiguous block of memory, like a std::vector, and use integer indices instead of pointers. This is a classic "data-oriented" design pattern.

A blog post by "lisyarus" presents an exceptionally concise and performant implementation based on this very idea. It's an excellent example of how rethinking data layout can yield significant performance gains.

The lisyarus implementation is essentially a Struct-of-Arrays (SoA) approach applied to a tree. The tree's structure (parent-child relationships) is stored in one array (nodes), while the data associated with each node can be stored in parallel arrays. This is a concept we will explore in detail in Module 6, but you can see the core idea here.

For your whiteboard, where strokes are added dynamically, the pointer-based Quadtree we are using is more flexible. However, if you were, for example, loading a complex document with thousands of strokes at once, building the Quadtree using the lisyarus partitioning method would be significantly more efficient than inserting each stroke one by one. Understanding these trade-offs is a key part of performance engineering.

Handling Dynamic Objects: Deletion and Relocation

Our system now correctly partitions strokes as they are added. But what happens when we need to remove or move an object? This is a critical consideration for features like an eraser, object selection/movement, or an undo/redo system. A naive removal would require searching the entire Quadtree to find the item, which, as you'll see, defeats the purpose of the data structure.

The second part of the javidx9 series on Quadtrees provides an elegant solution to this very problem.

This bidirectional linking strategy is a powerful technique. By storing a little extra information, you transform an expensive search operation into a direct lookup. For your whiteboard application, implementing this would involve modifying the Stroke objects (or a wrapper around them in your m_strokes list) to store a handle that points back to their entry in the Quadtree. While we won't implement this today, it's the clear next step for building a fully dynamic and editable canvas.

Conclusion

In this lesson, you have successfully bridged the gap from theory to practice by integrating your Quadtree into the application's data management layer. You now have a system that automatically partitions every stroke on the canvas, laying the groundwork for massive performance optimizations.

Key Takeaways:

• Integration via Wrapper Pattern: You've implemented the DocumentLayer as a wrapper that owns both the master std::list of strokes and the Quadtree that indexes them using stable iterators.
• Partitioning on Insertion: The addStroke method now populates both the list and the tree, ensuring all data is spatially indexed as it's created.
• Performance Trade-offs: You've contrasted our dynamic, pointer-based Quadtree with a static, index-based implementation, highlighting the trade-offs between flexibility and raw cache performance.
• Efficient Dynamic Updates: You've explored the "bookkeeping" strategy required for efficient object removal and relocation, a crucial concept for building a fully interactive application.

You have successfully partitioned the data. In our next lesson, Perform view frustum culling by querying the Quadtree to retrieve only visible strokes, you will leverage this partitioning to achieve a dramatic performance boost. We will modify the render loop to query the Quadtree for only the strokes that are inside the current viewport, ensuring your application remains fluid even with hundreds of thousands of strokes on the canvas.