cc: Add RTree class.

This patch adds an RTree class which is borrowed from Skia's SkRTree
implementation.

BUG=527245
R=enne
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Review URL: https://codereview.chromium.org/1344633002

Cr-Commit-Position: refs/heads/master@{#350356}

7 files changed, 298 insertions, 0 deletions

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index 922ac34..71183de 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn
@@ -728,6 +728,7 @@ test("cc_unittests") {
     "base/random_access_list_container_unittest.cc",
     "base/region_unittest.cc",
     "base/rolling_time_delta_history_unittest.cc",
+    "base/rtree_unittest.cc",
     "base/scoped_ptr_vector_unittest.cc",
     "base/simple_enclosed_region_unittest.cc",
     "base/tiling_data_unittest.cc",
diff --git a/cc/base/BUILD.gn b/cc/base/BUILD.gn
index 53194c9..c6dc603 100644
--- a/cc/base/BUILD.gn
+++ b/cc/base/BUILD.gn
@@ -24,6 +24,8 @@ source_set("base") {
     "resource_id.h",
     "rolling_time_delta_history.cc",
     "rolling_time_delta_history.h",
+    "rtree.cc",
+    "rtree.h",
     "scoped_ptr_algorithm.h",
     "scoped_ptr_deque.h",
     "scoped_ptr_vector.h",
diff --git a/cc/base/rtree.cc b/cc/base/rtree.cc
new file mode 100644
index 0000000..0828a34d
--- /dev/null
+++ b/cc/base/rtree.cc
@@ -0,0 +1,140 @@
+// Copyright (c) 2015 The Chromium 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 "cc/base/rtree.h"
+
+#include <cmath>
+
+#include "base/logging.h"
+
+namespace cc {
+
+RTree::RTree() : num_data_elements_(0u) {}
+
+RTree::~RTree() {}
+
+void RTree::Build(const std::vector<gfx::RectF>& rects) {
+  DCHECK_EQ(0u, num_data_elements_);
+
+  std::vector<Branch> branches;
+  branches.reserve(rects.size());
+
+  for (size_t i = 0; i < rects.size(); i++) {
+    const gfx::RectF& bounds = rects[i];
+    if (bounds.IsEmpty())
+      continue;
+
+    branches.push_back(Branch());
+    Branch& branch = branches.back();
+    branch.bounds = bounds;
+    branch.index = i;
+  }
+
+  num_data_elements_ = branches.size();
+  if (num_data_elements_ == 1) {
+    Node* node = AllocateNodeAtLevel(0);
+    node->num_children = 1;
+    node->children[0] = branches[0];
+    root_.subtree = node;
+    root_.bounds = branches[0].bounds;
+  } else if (num_data_elements_ > 1) {
+    root_ = BuildRecursive(&branches, 0);
+  }
+}
+
+RTree::Node* RTree::AllocateNodeAtLevel(int level) {
+  nodes_.push_back(Node());
+  Node& node = nodes_.back();
+  node.num_children = 0;
+  node.level = level;
+  return &node;
+}
+
+RTree::Branch RTree::BuildRecursive(std::vector<Branch>* branches, int level) {
+  // Only one branch.  It will be the root.
+  if (branches->size() == 1)
+    return (*branches)[0];
+
+  // TODO(vmpstr): Investigate if branches should be sorted in y.
+  // The comment from Skia reads:
+  // We might sort our branches here, but we expect Blink gives us a reasonable
+  // x,y order. Skipping a call to sort (in Y) here resulted in a 17% win for
+  // recording with negligible difference in playback speed.
+  int num_branches = static_cast<int>(branches->size() / MAX_CHILDREN);
+  int remainder = static_cast<int>(branches->size() % MAX_CHILDREN);
+
+  if (remainder > 0) {
+    ++num_branches;
+    // If the remainder isn't enough to fill a node, we'll add fewer nodes to
+    // other branches.
+    if (remainder >= MIN_CHILDREN)
+      remainder = 0;
+    else
+      remainder = MIN_CHILDREN - remainder;
+  }
+
+  int num_strips = static_cast<int>(std::ceil(std::sqrt(num_branches)));
+  int num_tiles = static_cast<int>(
+      std::ceil(num_branches / static_cast<float>(num_strips)));
+  size_t current_branch = 0;
+
+  size_t new_branch_index = 0;
+  for (int i = 0; i < num_strips; ++i) {
+    // Might be worth sorting by X here too.
+    for (int j = 0; j < num_tiles && current_branch < branches->size(); ++j) {
+      int increment_by = MAX_CHILDREN;
+      if (remainder != 0) {
+        // if need be, omit some nodes to make up for remainder
+        if (remainder <= MAX_CHILDREN - MIN_CHILDREN) {
+          increment_by -= remainder;
+          remainder = 0;
+        } else {
+          increment_by = MIN_CHILDREN;
+          remainder -= MAX_CHILDREN - MIN_CHILDREN;
+        }
+      }
+      Node* node = AllocateNodeAtLevel(level);
+      node->num_children = 1;
+      node->children[0] = (*branches)[current_branch];
+
+      Branch branch;
+      branch.bounds = (*branches)[current_branch].bounds;
+      branch.subtree = node;
+      ++current_branch;
+      for (int k = 1; k < increment_by && current_branch < branches->size();
+           ++k) {
+        branch.bounds.Union((*branches)[current_branch].bounds);
+        node->children[k] = (*branches)[current_branch];
+        ++node->num_children;
+        ++current_branch;
+      }
+      DCHECK_LT(new_branch_index, current_branch);
+      (*branches)[new_branch_index] = branch;
+      ++new_branch_index;
+    }
+  }
+  branches->resize(new_branch_index);
+  return BuildRecursive(branches, level + 1);
+}
+
+void RTree::Search(const gfx::RectF& query,
+                   std::vector<size_t>* results) const {
+  if (num_data_elements_ > 0 && query.Intersects(root_.bounds))
+    SearchRecursive(root_.subtree, query, results);
+}
+
+void RTree::SearchRecursive(Node* node,
+                            const gfx::RectF& query,
+                            std::vector<size_t>* results) const {
+  for (uint16_t i = 0; i < node->num_children; ++i) {
+    if (query.Intersects(node->children[i].bounds)) {
+      if (node->level == 0)
+        results->push_back(node->children[i].index);
+      else
+        SearchRecursive(node->children[i].subtree, query, results);
+    }
+  }
+}
+
+}  // namespace cc
diff --git a/cc/base/rtree.h b/cc/base/rtree.h
new file mode 100644
index 0000000..17a1d8c
--- /dev/null
+++ b/cc/base/rtree.h
@@ -0,0 +1,84 @@
+// Copyright (c) 2015 The Chromium 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 CC_BASE_RTREE_H_
+#define CC_BASE_RTREE_H_
+
+#include <deque>
+#include <vector>
+
+#include "cc/base/cc_export.h"
+#include "ui/gfx/geometry/rect_f.h"
+
+namespace cc {
+
+// The following description and most of the implementation is borrowed from
+// Skia's SkRTree implementation.
+//
+// An R-Tree implementation. In short, it is a balanced n-ary tree containing a
+// hierarchy of bounding rectangles.
+//
+// It only supports bulk-loading, i.e. creation from a batch of bounding
+// rectangles. This performs a bottom-up bulk load using the STR
+// (sort-tile-recursive) algorithm.
+//
+// Things to do: Experiment with other bulk-load algorithms (in particular the
+// Hilbert pack variant, which groups rects by position on the Hilbert curve, is
+// probably worth a look). There also exist top-down bulk load variants
+// (VAMSplit, TopDownGreedy, etc).
+//
+// For more details see:
+//
+//  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990).
+//  "The R*-tree: an efficient and robust access method for points and
+//  rectangles"
+class CC_EXPORT RTree {
+ public:
+  RTree();
+  ~RTree();
+
+  void Build(const std::vector<gfx::RectF>& rects);
+  void Search(const gfx::RectF& query, std::vector<size_t>* results) const;
+
+ private:
+  // These values were empirically determined to produce reasonable performance
+  // in most cases.
+  enum { MIN_CHILDREN = 6, MAX_CHILDREN = 11 };
+
+  struct Node;
+  struct Branch {
+    // When the node level is 0, then the node is a leaf and the branch has a
+    // valid index pointing to an element in the vector that was used to build
+    // this rtree. When the level is not 0, it's an internal node and it has a
+    // valid subtree pointer.
+    union {
+      Node* subtree;
+      size_t index;
+    };
+    gfx::RectF bounds;
+  };
+
+  struct Node {
+    uint16_t num_children;
+    uint16_t level;
+    Branch children[MAX_CHILDREN];
+  };
+
+  void SearchRecursive(Node* root,
+                       const gfx::RectF& query,
+                       std::vector<size_t>* results) const;
+
+  // Consumes the input array.
+  Branch BuildRecursive(std::vector<Branch>* branches, int level);
+  Node* AllocateNodeAtLevel(int level);
+
+  // This is the count of data elements (rather than total nodes in the tree)
+  size_t num_data_elements_;
+  Branch root_;
+  std::deque<Node> nodes_;
+};
+
+}  // namespace cc
+
+#endif  // CC_BASE_RTREE_H_
diff --git a/cc/base/rtree_unittest.cc b/cc/base/rtree_unittest.cc
new file mode 100644
index 0000000..b703a17
--- /dev/null
+++ b/cc/base/rtree_unittest.cc
@@ -0,0 +1,68 @@
+// Copyright 2015 The Chromium 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 "cc/base/rtree.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace cc {
+
+TEST(RTreeTest, NoOverlap) {
+  std::vector<gfx::RectF> rects;
+  for (int y = 0; y < 50; ++y) {
+    for (int x = 0; x < 50; ++x) {
+      rects.push_back(gfx::RectF(x, y, 1.f, 1.f));
+    }
+  }
+
+  RTree rtree;
+  rtree.Build(rects);
+
+  std::vector<size_t> results;
+  rtree.Search(gfx::RectF(0.f, 0.f, 50.f, 50.f), &results);
+  ASSERT_EQ(2500u, results.size());
+  for (size_t i = 0; i < 2500; ++i) {
+    ASSERT_EQ(results[i], i);
+  }
+
+  results.clear();
+  rtree.Search(gfx::RectF(0.f, 0.f, 50.f, 49.f), &results);
+  ASSERT_EQ(2450u, results.size());
+  for (size_t i = 0; i < 2450; ++i) {
+    ASSERT_EQ(results[i], i);
+  }
+
+  results.clear();
+  rtree.Search(gfx::RectF(5.2f, 6.3f, 0.1f, 0.2f), &results);
+  ASSERT_EQ(1u, results.size());
+  EXPECT_EQ(6u * 50 + 5u, results[0]);
+}
+
+TEST(RTreeTest, Overlap) {
+  std::vector<gfx::RectF> rects;
+  for (int h = 1; h <= 50; ++h) {
+    for (int w = 1; w <= 50; ++w) {
+      rects.push_back(gfx::RectF(0, 0, w, h));
+    }
+  }
+
+  RTree rtree;
+  rtree.Build(rects);
+
+  std::vector<size_t> results;
+  rtree.Search(gfx::RectF(0.f, 0.f, 1.f, 1.f), &results);
+  ASSERT_EQ(2500u, results.size());
+  for (size_t i = 0; i < 2500; ++i) {
+    ASSERT_EQ(results[i], i);
+  }
+
+  results.clear();
+  rtree.Search(gfx::RectF(0.f, 49.f, 1.f, 1.f), &results);
+  ASSERT_EQ(50u, results.size());
+  for (size_t i = 0; i < 50; ++i) {
+    EXPECT_EQ(results[i], 2450u + i);
+  }
+}
+
+}  // namespace cc
diff --git a/cc/cc.gyp b/cc/cc.gyp
index 2c6c280..9692712 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp
@@ -91,6 +91,8 @@
         'base/resource_id.h',
         'base/rolling_time_delta_history.cc',
         'base/rolling_time_delta_history.h',
+        'base/rtree.cc',
+        'base/rtree.h',
         'base/scoped_ptr_algorithm.h',
         'base/scoped_ptr_deque.h',
         'base/scoped_ptr_vector.h',
diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index c5a0124..5709d35 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp
@@ -25,6 +25,7 @@
       'base/random_access_list_container_unittest.cc',
       'base/region_unittest.cc',
       'base/rolling_time_delta_history_unittest.cc',
+      'base/rtree_unittest.cc',
       'base/scoped_ptr_vector_unittest.cc',
       'base/simple_enclosed_region_unittest.cc',
       'base/tiling_data_unittest.cc',