src/gpu/graphite/geom/IntersectionTree.h

/*
 * Copyright 2021 Google LLC
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef skgpu_graphite_geom_IntersectionTree_DEFINED
#define skgpu_graphite_geom_IntersectionTree_DEFINED

#include "src/core/SkArenaAlloc.h"
#include "src/gpu/graphite/geom/Rect.h"

namespace skgpu::graphite {

/**
 * Maintains a collection of non-overlapping rectangles.
 *
 * add() either adds the given rect to the collection, or returns false if it intersected with a
 * rect already in the collection.
 */
class IntersectionTree {
public:
    IntersectionTree();

    bool add(Rect rect) {
        if (rect.isEmptyNegativeOrNaN()) {
            // Empty and undefined rects can simply pass without modifying the tree.
            return true;
        }
        if (!fRoot->intersects(rect)) {
            fRoot = fRoot->addNonIntersecting(rect, &fArena);
            return true;
        }
        return false;
    }

private:
    class Node {
    public:
        virtual ~Node() = default;

        virtual bool intersects(Rect) = 0;
        virtual Node* addNonIntersecting(Rect, SkArenaAlloc*) = 0;
    };

    enum class SplitType : bool {
        kX,
        kY
    };

    template<SplitType kSplitType> class TreeNode;
    class LeafNode;

    // The TreeNode size is made of a vtable (i.e. sizeof(void*)), float, and two Node* pointers.
    // We also align between the Node* and the float which may add some extra padding.
    constexpr static int kTreeNodeSize = SkAlignTo(sizeof(void*) + sizeof(float), alignof(void*)) +
                                         2 * sizeof(Node*);
    constexpr static int kLeafNodeSize = 16 + (2 + 64) * sizeof(Rect);
    constexpr static int kPadSize = 256;  // For footers and alignment.
    SkArenaAlloc fArena{kLeafNodeSize + kTreeNodeSize + kPadSize*2};
    Node* fRoot;
};

} // namespace skgpu::graphite

#endif // skgpu_graphite_geom_IntersectionTree_DEFINED