Structuring PDF Content for Whiteboard Regions

The Two-Worlds Problem: PDF vs. Whiteboard Coordinates

Before we can place our ExtractedItems on the whiteboard, we must resolve a fundamental mismatch in coordinate systems. PDFium, like the PDF specification itself, typically uses a coordinate system where the origin (0,0) is at the bottom-left of the page. In contrast, most rendering APIs, including Skia, place the origin at the top-left.

This means a y coordinate of 10 in PDF space is near the bottom of the page, while in Skia space it's near the top. Attempting to use PDF coordinates directly for rendering will result in a vertically flipped layout.

To solve this, we will perform a one-time conversion when an item is first processed. For a page of a given page_height, a PDF coordinate (x, y_pdf) is converted to a top-left world coordinate (x, y_world) using the formula:

$y_{\text{world}}=\text{page\_height}-y_{\text{pdf}}$

The FS_RECTF from PDFium gives us left, top, right, and bottom. Because top > bottom in PDF space, our WhiteboardItem's bounding box will need to be constructed carefully. Let's define the data structures that will hold our content in the whiteboard's "world space":

// From the previous lesson, holding raw PDF data
struct ExtractedItem {
    std::string type;
    std::string number;
    std::vector<TextBlock> blocks;
    FS_RECTF combined_bounding_box; // In PDF coordinates
};

// Represents an item placed on the whiteboard
struct WhiteboardObject {
    // Skia's rectangle type, using float. Assumes top-left origin.
    SkRect bounds; 

    // The original parsed data. We can use a shared_ptr if the data is large
    // and might be referenced from multiple places, or store by value if simpler.
    ExtractedItem source_data; 
    
    // You might also add a unique ID
    uint64_t id; 
};

When you process a ExtractedItem, you will create a WhiteboardObject, converting combined_bounding_box into bounds using the page height. The WhiteboardObject is what we need to manage and render.

Spatial Indexing: Beyond the std::vector

With potentially thousands of WhiteboardObjects, how do we efficiently find which ones are inside the user's current viewport for rendering? A simple std::vector<WhiteboardObject> and a loop is an O(N) operation that must run every single frame. This does not scale.

We need a spatial index: a data structure that organizes data by its position in space, allowing for rapid queries of a specific region. For our 2D whiteboard, the two most common and effective choices are the Quadtree and the R-tree.

The Quadtree: Recursive Space Division

A Quadtree is an intuitive and powerful spatial index. The core idea is to recursively subdivide a 2D area into four equal quadrants.

• A node in the tree represents a rectangular area.
• If the number of objects in that area exceeds a certain capacity, the node subdivides, creating four child nodes (north-west, north-east, south-west, south-east).
• The objects are then pushed down into the appropriate child quadrant.
• This process continues recursively down to a maximum depth.

To find objects in a given area (our viewport), you start at the root and recursively check which of its children intersect the query area. You only traverse the relevant branches of the tree, dramatically pruning the search space.

The following video from javidx9 gives an excellent, in-depth explanation and C++ implementation of a Quadtree, with a strong focus on performance optimizations that will resonate with your systems background.

This wrapper approach is the foundation for our design. We will create a class that owns both the definitive list of WhiteboardObjects and the Quadtree that indexes them.

The R-tree: A Production-Grade Alternative

While a Quadtree is excellent and a great structure to implement yourself, it's also important to be aware of R-trees, which are often considered superior for real-world applications, especially for non-point data like our bounding boxes.

Instead of dividing space, an R-tree groups nearby objects.

• Leaf nodes contain pointers to the actual data objects.
• Internal (branch) nodes store the minimum bounding rectangle (MBR) that encloses all the bounding boxes of their children.

R-trees adapt better to non-uniform data distributions, as they don't create empty subdivisions. For production systems, you would typically use a library implementation, such as the one in Boost.Geometry.

The choice of balancing algorithm has a real performance impact. For an application like yours where query performance (i.e., rendering) is critical, rstar is usually the best choice, even if it's slightly slower to build the tree initially.

Finalizing the Data Structure Design

For your project, implementing a Quadtree is the next learning objective. Therefore, we will base our design on the optimized wrapper approach from the javidx9 video. This gives you a clear implementation path while applying advanced C++ performance concepts.

Here is the proposed design for the class that will manage all extracted PDF content:

#include <list>
#include <memory>
#include "YourQuadtree.h" // The quadtree class we will design based on javidx9
#include "WhiteboardObject.h" // The struct we defined earlier

// Define the "value" that the Quadtree will store.
// It's a lightweight iterator to the actual object in our list.
using ObjectIterator = std::list<WhiteboardObject>::iterator;

class DocumentLayer {
public:
    DocumentLayer(const SkRect& bounds) : m_quadtree(bounds) {}

    // Adds a new object extracted from the PDF.
    void addObject(const ExtractedItem& item, float page_height) {
        // 1. Convert PDF coordinates to whiteboard world coordinates.
        SkRect world_bounds = convertPdfRectToSkRect(item.combined_bounding_box, page_height);

        // 2. Add the full object to our list. std::list iterators are stable.
        m_objects.emplace_back(WhiteboardObject{world_bounds, item, /* generate new ID */});

        // 3. Get an iterator to the newly added object.
        ObjectIterator it = std::prev(m_objects.end());

        // 4. Insert the iterator and its bounds into the Quadtree.
        m_quadtree.insert(it, world_bounds);
    }

    // Finds all objects visible within a given viewport.
    std::vector<ObjectIterator> getVisibleObjects(const SkRect& viewport) const {
        return m_quadtree.search(viewport);
    }

    // Allow iterating over all objects if needed
    const std::list<WhiteboardObject>& getAllObjects() const {
        return m_objects;
    }

private:
    // The single source of truth for all object data.
    // std::list is chosen because its iterators are not invalidated by insertions/deletions
    // (except for the deleted element itself).
    std::list<WhiteboardObject> m_objects;

    // The spatial index. It stores iterators, not full objects.
    // We will define this class in the next lesson.
    Quadtree<ObjectIterator> m_quadtree; 

    SkRect convertPdfRectToSkRect(const FS_RECTF& pdf_rect, float page_height) {
        // Implementation of the coordinate transformation
        float top = page_height - pdf_rect.top;
        float bottom = page_height - pdf_rect.bottom;
        return SkRect::MakeLTRB(pdf_rect.left, top, pdf_rect.right, bottom);
    }
};

This design cleanly separates the storage of data (m_objects) from the spatial index (m_quadtree). The DocumentLayer class serves as the single point of contact for adding and querying content, providing a clean interface to the rest of your application.

Conclusion

In this lesson, we have designed the critical data structures for managing interactive content on your whiteboard. You've seen the importance of handling coordinate system transformations and have explored the principles behind spatial indexes like Quadtrees and R-trees.

Key Takeaways:

• Coordinate Transformation is Essential: PDF content coordinates must be converted from their bottom-left origin to the top-left origin used by your rendering system.
• Spatial Indexes Avoid Linear Scans: Data structures like Quadtrees and R-trees are necessary to achieve high-performance rendering by quickly culling objects outside the viewport.
• A Wrapper Design Optimizes Performance: Storing full objects in a stable container (like std::list) and having the spatial index store lightweight iterators or pointers is a powerful C++ technique that avoids costly data copies.
• Our Design: We've laid out a DocumentLayer class that owns the object data and a Quadtree to index it, providing a clear and efficient architecture.

In the next lesson, you will take this design and implement the Quadtree data structure from the ground up. You will then be able to integrate it into your application to achieve efficient spatial querying.