dl_rtree.cc

Go to the documentation of this file.

// 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.
 
#include "flutter/display_list/geometry/dl_rtree.h"
#include "flutter/display_list/geometry/dl_region.h"
 
#include "flutter/fml/logging.h"
 
namespace flutter {
 
DlRTree::DlRTree(const SkRect rects[],
                 int N,
                 const int ids[],
                 bool p(int),
                 int invalid_id)
    : invalid_id_(invalid_id) {
  if (N <= 0) {
    FML_DCHECK(N >= 0);
    return;
  }
  FML_DCHECK(rects != nullptr);
 
  // Count the number of rectangles we actually want to track,
  // which includes only non-empty rectangles whose optional
  // ID is not filtered by the predicate.
  int leaf_count = 0;
  for (int i = 0; i < N; i++) {
    if (!rects[i].isEmpty()) {
      if (ids == nullptr || p(ids[i])) {
        leaf_count++;
      }
    }
  }
  leaf_count_ = leaf_count;
 
  // Count the total number of nodes (leaf and internal) up front
  // so we can resize the vector just once.
  uint32_t total_node_count = leaf_count;
  uint32_t gen_count = leaf_count;
  while (gen_count > 1) {
    uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
    total_node_count += family_count;
    gen_count = family_count;
  }
 
  nodes_.resize(total_node_count);
 
  // Now place only the tracked rectangles into the nodes array
  // in the first leaf_count_ entries.
  int leaf_index = 0;
  int id = invalid_id;
  for (int i = 0; i < N; i++) {
    if (!rects[i].isEmpty()) {
      if (ids == nullptr || p(id = ids[i])) {
        Node& node = nodes_[leaf_index++];
        node.bounds = rects[i];
        node.id = id;
      }
    }
  }
  FML_DCHECK(leaf_index == leaf_count);
 
  // --- Implementation note ---
  // Many R-Tree algorithms attempt to consolidate nearby rectangles
  // into branches of the tree in order to maximize the benefit of
  // bounds testing against whole sub-trees. The Skia code from which
  // this was based, though, indicated that empirical tests against a
  // browser client showed little gains in rendering performance while
  // costing 17% performance in bulk loading the rects into the R-Tree:
  // https://github.com/google/skia/blob/12b6bd042f7cdffb9012c90c3b4885601fc7be95/src/core/SkRTree.cpp#L96
  //
  // Given that this class will most often be used to track rendering
  // operations that were drawn in an app that performs a type of
  // "page layout" with rendering proceeding in a linear fashion from
  // top to bottom (and left to right or right to left), the rectangles
  // are likely nearly sorted when they are delivered to this constructor
  // so leaving them in their original order should show similar results
  // to what Skia found in their empirical browser tests.
  // ---
 
  // Continually process the previous level (generation) of nodes,
  // combining them into a new generation of parent groups each grouping
  // at most |kMaxChildren| children and joining their bounds into its
  // parent bounds.
  // Each generation will end up reduced by a factor of up to kMaxChildren
  // until there is just one node left, which is the root node of
  // the R-Tree.
  uint32_t gen_start = 0;
  gen_count = leaf_count;
  while (gen_count > 1) {
    uint32_t gen_end = gen_start + gen_count;
 
    uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
    FML_DCHECK(gen_end + family_count <= total_node_count);
 
    // D here is similar to the variable in a Bresenham line algorithm where
    // we want to slowly move |family_count| steps along the minor axis as
    // we move |gen_count| steps along the major axis.
    //
    // Each inner loop increments D by family_count.
    // The inner loop executes a total of gen_count times.
    // Every time D exceeds 0 we subtract gen_count and move to a new parent.
    // All told we will increment D by family_count a total of gen_count times.
    // All told we will decrement D by gen_count a total of family_count times.
    // This leaves D back at its starting value.
    //
    // We could bias/balance where the extra children are placed by varying
    // the initial count of D from 0 to (1 - family_count), but we aren't
    // looking at this process aesthetically so we just use 0 as an initial
    // value. Using 0 provides a "greedy" allocation of the extra children.
    // Bresenham also uses double the size of the steps we use here also to
    // have better rounding of when the minor axis steps occur, but again we
    // don't care about the distribution of the extra children.
    int D = 0;
 
    uint32_t sibling_index = gen_start;
    uint32_t parent_index = gen_end;
    Node* parent = nullptr;
    while (sibling_index < gen_end) {
      if ((D += family_count) > 0) {
        D -= gen_count;
        FML_DCHECK(parent_index < gen_end + family_count);
        parent = &nodes_[parent_index++];
        parent->bounds.setEmpty();
        parent->child.index = sibling_index;
        parent->child.count = 0;
      }
      FML_DCHECK(parent != nullptr);
      parent->bounds.join(nodes_[sibling_index++].bounds);
      parent->child.count++;
    }
    FML_DCHECK(D == 0);
    FML_DCHECK(sibling_index == gen_end);
    FML_DCHECK(parent_index == gen_end + family_count);
    gen_start = gen_end;
    gen_count = family_count;
  }
  FML_DCHECK(gen_start + gen_count == total_node_count);
}
 
void DlRTree::search(const SkRect& query, std::vector<int>* results) const {
  FML_DCHECK(results != nullptr);
  if (query.isEmpty()) {
    return;
  }
  if (nodes_.size() <= 0) {
    FML_DCHECK(leaf_count_ == 0);
    return;
  }
  const Node& root = nodes_.back();
  if (root.bounds.intersects(query)) {
    if (nodes_.size() == 1) {
      FML_DCHECK(leaf_count_ == 1);
      // The root node is the only node and it is a leaf node
      results->push_back(0);
    } else {
      search(root, query, results);
    }
  }
}
 
std::list<SkRect> DlRTree::searchAndConsolidateRects(const SkRect& query,
                                                     bool deband) const {
  // Get the indexes for the operations that intersect with the query rect.
  std::vector<int> intermediary_results;
  search(query, &intermediary_results);
 
  std::vector<SkIRect> rects;
  rects.reserve(intermediary_results.size());
  for (int index : intermediary_results) {
    SkIRect current_record_rect;
    bounds(index).roundOut(&current_record_rect);
    rects.push_back(current_record_rect);
  }
  DlRegion region(rects);
 
  auto non_overlapping_rects = region.getRects(deband);
  std::list<SkRect> final_results;
  for (const auto& rect : non_overlapping_rects) {
    final_results.push_back(SkRect::Make(rect));
  }
  return final_results;
}
 
void DlRTree::search(const Node& parent,
                     const SkRect& query,
                     std::vector<int>* results) const {
  // Caller protects against empty query
  int start = parent.child.index;
  int end = start + parent.child.count;
  for (int i = start; i < end; i++) {
    const Node& node = nodes_[i];
    if (node.bounds.intersects(query)) {
      if (i < leaf_count_) {
        results->push_back(i);
      } else {
        search(node, query, results);
      }
    }
  }
}
 
const DlRegion& DlRTree::region() const {
  if (!region_) {
    std::vector<SkIRect> rects;
    rects.resize(leaf_count_);
    for (int i = 0; i < leaf_count_; i++) {
      nodes_[i].bounds.roundOut(&rects[i]);
    }
    region_.emplace(rects);
  }
  return *region_;
}
 
const SkRect& DlRTree::bounds() const {
  if (!nodes_.empty()) {
    return nodes_.back().bounds;
  } else {
    return kEmpty;
  }
}
 
}  // namespace flutter