display_list/geometry/dl_rtree.h

// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef FLUTTER_DISPLAY_LIST_GEOMETRY_DL_RTREE_H_
#define FLUTTER_DISPLAY_LIST_GEOMETRY_DL_RTREE_H_

#include <list>
#include <optional>
#include <vector>

#include "flutter/display_list/geometry/dl_region.h"
#include "flutter/fml/logging.h"
#include "third_party/skia/include/core/SkColorSpace.h"
#include "third_party/skia/include/core/SkRect.h"
#include "third_party/skia/include/core/SkRefCnt.h"

namespace flutter {

/// An R-Tree that stores a list of bounding rectangles with optional
/// associated IDs.
///
/// The R-Tree can be searched in one of two ways:
/// - Query for a list of hits among the original rectangles
///   @see |search|
/// - Query for a set of non-overlapping rectangles that are joined
///   from the original rectangles that intersect a query rect
///   @see |searchAndConsolidateRects|
class DlRTree : public SkRefCnt {
 private:
  static constexpr int kMaxChildren = 11;

  // Leaf nodes at start of vector have an ID,
  // Internal nodes after that have child index and count.
  struct Node {
    SkRect bounds;
    union {
      struct {
        uint32_t index;
        uint32_t count;
      } child;
      int id;
    };
  };

 public:
  /// Construct an R-Tree from the list of rectangles respecting the
  /// order in which they appear in the list. An optional array of
  /// IDs can be provided to tag each rectangle with information needed
  /// by the caller as well as an optional predicate that can filter
  /// out rectangles with IDs that should not be stored in the R-Tree.
  ///
  /// If an array of IDs is not specified then all leaf nodes will be
  /// represented by the |invalid_id| (which defaults to -1).
  ///
  /// Invalid rects that are empty or contain a NaN value will not be
  /// stored in the R-Tree. And, if a |predicate| function is provided,
  /// that function will be called to query if the rectangle associated
  /// with the ID should be included.
  ///
  /// Duplicate rectangles and IDs are allowed and not processed in any
  /// way except to eliminate invalid rectangles and IDs that are rejected
  /// by the optional predicate function.
  DlRTree(
      const SkRect rects[],
      int N,
      const int ids[] = nullptr,
      bool predicate(int id) = [](int) { return true; },
      int invalid_id = -1);

  /// Search the rectangles and return a vector of leaf node indices for
  /// rectangles that intersect the query.
  ///
  /// Note that the indices are internal indices of the stored data
  /// and not the index of the rectangles or ids in the constructor.
  /// The returned indices may not themselves be in numerical order,
  /// but they will represent the rectangles and IDs in the order in
  /// which they were passed into the constructor. The actual rectangle
  /// and ID associated with each index can be retrieved using the
  /// |DlRTree::id| and |DlRTree::bounds| methods.
  void search(const SkRect& query, std::vector<int>* results) const;

  /// Return the ID for the indicated result of a query or
  /// invalid_id if the index is not a valid leaf node index.
  int id(int result_index) const {
    return (result_index >= 0 && result_index < leaf_count_)
               ? nodes_[result_index].id
               : invalid_id_;
  }

  /// Returns maximum and minimum axis values of rectangles in this R-Tree.
  /// If R-Tree is empty returns an empty SkRect.
  const SkRect& bounds() const;

  /// Return the rectangle bounds for the indicated result of a query
  /// or an empty rect if the index is not a valid leaf node index.
  const SkRect& bounds(int result_index) const {
    return (result_index >= 0 && result_index < leaf_count_)
               ? nodes_[result_index].bounds
               : kEmpty;
  }

  /// Returns the bytes used by the object and all of its node data.
  size_t bytes_used() const {
    return sizeof(DlRTree) + sizeof(Node) * nodes_.size();
  }

  /// Returns the number of leaf nodes corresponding to non-empty
  /// rectangles that were passed in the constructor and not filtered
  /// out by the predicate.
  int leaf_count() const { return leaf_count_; }

  /// Return the total number of nodes used in the R-Tree, both leaf
  /// and internal consolidation nodes.
  int node_count() const { return nodes_.size(); }

  /// Finds the rects in the tree that intersect with the query rect.
  ///
  /// The returned list of rectangles will be non-overlapping.
  /// In other words, the bounds of each rect in the result list are mutually
  /// exclusive.
  ///
  /// If |deband| is true, then matching rectangles from adjacent DlRegion
  /// spanlines will be joined together. This reduces the number of
  /// rectangles returned, but requires some extra computation.
  std::list<SkRect> searchAndConsolidateRects(const SkRect& query,
                                              bool deband = true) const;

  /// Returns DlRegion that represents the union of all rectangles in the
  /// R-Tree.
  const DlRegion& region() const;

  /// Returns DlRegion that represents the union of all rectangles in the
  /// R-Tree intersected with the query rect.
  DlRegion region(const SkRect& query) const {
    return DlRegion::MakeIntersection(region(), DlRegion(query.roundOut()));
  }

 private:
  static constexpr SkRect kEmpty = SkRect::MakeEmpty();

  void search(const Node& parent,
              const SkRect& query,
              std::vector<int>* results) const;

  std::vector<Node> nodes_;
  int leaf_count_ = 0;
  int invalid_id_;
  mutable std::optional<DlRegion> region_;
};

}  // namespace flutter

#endif  // FLUTTER_DISPLAY_LIST_GEOMETRY_DL_RTREE_H_