BSP Tree perf tests to match LayerSorter perf tests

The BspTree perf tests should ideally perform equally or better than the
current LayerSorter tests do in the same tests (i.e. "rubik" vs.
"rubik").

Performance results on Z600:
layer_sort_cubes= 3.547ms
layer_sort_rubik= 0.634ms
bsp_tree_cubes= 1.485ms
bsp_tree_rubik= 0.136ms
bsp_tree_cubes_2= 2.915ms (2x duplicated layers)
bsp_tree_cubes_4= 5.667ms (4x duplicated layers)

BUG=230833

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

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@287182 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 259 insertions, 2 deletions

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index 1c04a89..aabbdf6 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn
@@ -215,6 +215,10 @@ component("cc") {
     "layers/video_layer_impl.h",
     "output/begin_frame_args.cc",
     "output/begin_frame_args.h",
+    "output/bsp_tree.cc",
+    "output/bsp_tree.h",
+    "output/bsp_walk_action.cc",
+    "output/bsp_walk_action.h",
     "output/compositor_frame.cc",
     "output/compositor_frame.h",
     "output/compositor_frame_ack.cc",
@@ -279,6 +283,8 @@ component("cc") {
     "quads/content_draw_quad_base.h",
     "quads/debug_border_draw_quad.cc",
     "quads/debug_border_draw_quad.h",
+    "quads/draw_polygon.cc",
+    "quads/draw_polygon.h",
     "quads/draw_quad.cc",
     "quads/draw_quad.h",
     "quads/io_surface_draw_quad.cc",
diff --git a/cc/base/math_util.cc b/cc/base/math_util.cc
index fd8e796..2504924 100644
--- a/cc/base/math_util.cc
+++ b/cc/base/math_util.cc
@@ -111,6 +111,13 @@ static inline void AddVertexToClippedQuad(const gfx::PointF& new_vertex,
   (*num_vertices_in_clipped_quad)++;
 }
 
+static inline void AddVertexToClippedQuad3d(const gfx::Point3F& new_vertex,
+                                            gfx::Point3F clipped_quad[8],
+                                            int* num_vertices_in_clipped_quad) {
+  clipped_quad[*num_vertices_in_clipped_quad] = new_vertex;
+  (*num_vertices_in_clipped_quad)++;
+}
+
 gfx::Rect MathUtil::MapEnclosingClippedRect(const gfx::Transform& transform,
                                             const gfx::Rect& src_rect) {
   if (transform.IsIdentityOrIntegerTranslation()) {
@@ -253,6 +260,76 @@ void MathUtil::MapClippedQuad(const gfx::Transform& transform,
   DCHECK_LE(*num_vertices_in_clipped_quad, 8);
 }
 
+bool MathUtil::MapClippedQuad3d(const gfx::Transform& transform,
+                                const gfx::QuadF& src_quad,
+                                gfx::Point3F clipped_quad[8],
+                                int* num_vertices_in_clipped_quad) {
+  HomogeneousCoordinate h1 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p1()));
+  HomogeneousCoordinate h2 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p2()));
+  HomogeneousCoordinate h3 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p3()));
+  HomogeneousCoordinate h4 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p4()));
+
+  // The order of adding the vertices to the array is chosen so that
+  // clockwise / counter-clockwise orientation is retained.
+
+  *num_vertices_in_clipped_quad = 0;
+
+  if (!h1.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h1.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h1.ShouldBeClipped() ^ h2.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h1, h2).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  if (!h2.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h2.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h2.ShouldBeClipped() ^ h3.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h2, h3).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  if (!h3.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h3.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h3.ShouldBeClipped() ^ h4.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h3, h4).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  if (!h4.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h4.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h4, h1).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  DCHECK_LE(*num_vertices_in_clipped_quad, 8);
+  return (*num_vertices_in_clipped_quad >= 4);
+}
+
 gfx::RectF MathUtil::ComputeEnclosingRectOfVertices(
     const gfx::PointF vertices[],
     int num_vertices) {
@@ -386,6 +463,48 @@ gfx::QuadF MathUtil::MapQuad(const gfx::Transform& transform,
                     h4.CartesianPoint2d());
 }
 
+gfx::QuadF MathUtil::MapQuad3d(const gfx::Transform& transform,
+                               const gfx::QuadF& q,
+                               gfx::Point3F* p,
+                               bool* clipped) {
+  if (transform.IsIdentityOrTranslation()) {
+    gfx::QuadF mapped_quad(q);
+    mapped_quad +=
+        gfx::Vector2dF(SkMScalarToFloat(transform.matrix().get(0, 3)),
+                       SkMScalarToFloat(transform.matrix().get(1, 3)));
+    *clipped = false;
+    p[0] = gfx::Point3F(mapped_quad.p1().x(), mapped_quad.p1().y(), 0.0f);
+    p[1] = gfx::Point3F(mapped_quad.p2().x(), mapped_quad.p2().y(), 0.0f);
+    p[2] = gfx::Point3F(mapped_quad.p3().x(), mapped_quad.p3().y(), 0.0f);
+    p[3] = gfx::Point3F(mapped_quad.p4().x(), mapped_quad.p4().y(), 0.0f);
+    return mapped_quad;
+  }
+
+  HomogeneousCoordinate h1 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p1()));
+  HomogeneousCoordinate h2 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p2()));
+  HomogeneousCoordinate h3 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p3()));
+  HomogeneousCoordinate h4 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p4()));
+
+  *clipped = h1.ShouldBeClipped() || h2.ShouldBeClipped() ||
+             h3.ShouldBeClipped() || h4.ShouldBeClipped();
+
+  // Result will be invalid if clipped == true. But, compute it anyway just in
+  // case, to emulate existing behavior.
+  p[0] = h1.CartesianPoint3d();
+  p[1] = h2.CartesianPoint3d();
+  p[2] = h3.CartesianPoint3d();
+  p[3] = h4.CartesianPoint3d();
+
+  return gfx::QuadF(h1.CartesianPoint2d(),
+                    h2.CartesianPoint2d(),
+                    h3.CartesianPoint2d(),
+                    h4.CartesianPoint2d());
+}
+
 gfx::PointF MathUtil::MapPoint(const gfx::Transform& transform,
                                const gfx::PointF& p,
                                bool* clipped) {
diff --git a/cc/base/math_util.h b/cc/base/math_util.h
index 4301add..cf18b53 100644
--- a/cc/base/math_util.h
+++ b/cc/base/math_util.h
@@ -7,6 +7,7 @@
 
 #include <algorithm>
 #include <cmath>
+#include <vector>
 
 #include "base/logging.h"
 #include "base/memory/scoped_ptr.h"
@@ -123,6 +124,10 @@ class CC_EXPORT MathUtil {
                              const gfx::QuadF& src_quad,
                              gfx::PointF clipped_quad[8],
                              int* num_vertices_in_clipped_quad);
+  static bool MapClippedQuad3d(const gfx::Transform& transform,
+                               const gfx::QuadF& src_quad,
+                               gfx::Point3F clipped_quad[8],
+                               int* num_vertices_in_clipped_quad);
 
   static gfx::RectF ComputeEnclosingRectOfVertices(const gfx::PointF vertices[],
                                                    int num_vertices);
@@ -137,6 +142,10 @@ class CC_EXPORT MathUtil {
   static gfx::QuadF MapQuad(const gfx::Transform& transform,
                             const gfx::QuadF& quad,
                             bool* clipped);
+  static gfx::QuadF MapQuad3d(const gfx::Transform& transform,
+                              const gfx::QuadF& q,
+                              gfx::Point3F* p,
+                              bool* clipped);
   static gfx::PointF MapPoint(const gfx::Transform& transform,
                               const gfx::PointF& point,
                               bool* clipped);
diff --git a/cc/quads/draw_polygon.cc b/cc/quads/draw_polygon.cc
index db2249c..bfc2b492 100644
--- a/cc/quads/draw_polygon.cc
+++ b/cc/quads/draw_polygon.cc
@@ -7,6 +7,7 @@
 #include <vector>
 
 #include "cc/output/bsp_compare_result.h"
+#include "cc/quads/draw_quad.h"
 
 namespace {
 // This allows for some imperfection in the normal comparison when checking if
@@ -45,6 +46,32 @@ DrawPolygon::DrawPolygon(DrawQuad* original,
   normal_ = normal;
 }
 
+// This takes the original DrawQuad that this polygon should be based on,
+// a visible content rect to make the 4 corner points from, and a transformation
+// to move it and its normal into screen space.
+DrawPolygon::DrawPolygon(DrawQuad* original_ref,
+                         const gfx::RectF& visible_content_rect,
+                         const gfx::Transform& transform,
+                         int draw_order_index)
+    : order_index_(draw_order_index), original_ref_(original_ref) {
+  normal_ = default_normal;
+  gfx::Point3F points[8];
+  int num_vertices_in_clipped_quad;
+  gfx::QuadF send_quad(visible_content_rect);
+
+  // Doing this mapping here is very important, since we can't just transform
+  // the points without clipping and not run into strange geometry issues when
+  // crossing w = 0. At this point, in the constructor, we know that we're
+  // working with a quad, so we can reuse the MathUtil::MapClippedQuad3d
+  // function instead of writing a generic polygon version of it.
+  MathUtil::MapClippedQuad3d(
+      transform, send_quad, points, &num_vertices_in_clipped_quad);
+  for (int i = 0; i < num_vertices_in_clipped_quad; i++) {
+    points_.push_back(points[i]);
+  }
+  ApplyTransformToNormal(transform);
+}
+
 DrawPolygon::~DrawPolygon() {
 }
 
diff --git a/cc/quads/draw_polygon.h b/cc/quads/draw_polygon.h
index c4dfa13..8e65ea8 100644
--- a/cc/quads/draw_polygon.h
+++ b/cc/quads/draw_polygon.h
@@ -9,13 +9,16 @@
 
 #include "cc/base/math_util.h"
 #include "cc/output/bsp_compare_result.h"
-#include "cc/quads/draw_quad.h"
 #include "ui/gfx/point3_f.h"
 #include "ui/gfx/quad_f.h"
+#include "ui/gfx/rect_f.h"
+#include "ui/gfx/transform.h"
 #include "ui/gfx/vector3d_f.h"
 
 namespace cc {
 
+class DrawQuad;
+
 class CC_EXPORT DrawPolygon {
  public:
   DrawPolygon();
@@ -25,6 +28,10 @@ class CC_EXPORT DrawPolygon {
               const std::vector<gfx::Point3F>& in_points,
               const gfx::Vector3dF& normal,
               int draw_order_index = 0);
+  DrawPolygon(DrawQuad* original_ref,
+              const gfx::RectF& visible_content_rect,
+              const gfx::Transform& transform,
+              int draw_order_index = 0);
 
   // Split takes this DrawPolygon and splits it into two pieces that are on
   // either side of |splitter|. Any edges of this polygon that cross the plane
diff --git a/cc/trees/layer_tree_host_common_perftest.cc b/cc/trees/layer_tree_host_common_perftest.cc
index 02b0770..94b4594 100644
--- a/cc/trees/layer_tree_host_common_perftest.cc
+++ b/cc/trees/layer_tree_host_common_perftest.cc
@@ -8,12 +8,18 @@
 
 #include "base/file_util.h"
 #include "base/files/file_path.h"
+#include "base/memory/scoped_ptr.h"
 #include "base/path_service.h"
 #include "base/strings/string_piece.h"
 #include "base/threading/thread.h"
 #include "base/time/time.h"
+#include "cc/base/scoped_ptr_deque.h"
+#include "cc/base/scoped_ptr_vector.h"
 #include "cc/debug/lap_timer.h"
 #include "cc/layers/layer.h"
+#include "cc/output/bsp_tree.h"
+#include "cc/quads/draw_polygon.h"
+#include "cc/quads/draw_quad.h"
 #include "cc/test/fake_content_layer_client.h"
 #include "cc/test/fake_layer_tree_host_client.h"
 #include "cc/test/layer_tree_json_parser.h"
@@ -197,7 +203,7 @@ class LayerSorterMainTest : public CalcDrawPropsImplTest {
       list->push_back(layer);
     }
 
-    for (unsigned int i = 0; i < layer->children().size(); i++) {
+    for (size_t i = 0; i < layer->children().size(); i++) {
       BuildLayerImplList(layer->children()[i], list);
     }
   }
@@ -207,6 +213,61 @@ class LayerSorterMainTest : public CalcDrawPropsImplTest {
   LayerSorter layer_sorter_;
 };
 
+class BspTreePerfTest : public LayerSorterMainTest {
+ public:
+  void RunSortLayers() { RunTest(false, false, false); }
+
+  void SetNumberOfDuplicates(int num_duplicates) {
+    num_duplicates_ = num_duplicates;
+  }
+
+  virtual void BeginTest() OVERRIDE { PostSetNeedsCommitToMainThread(); }
+
+  virtual void DrawLayersOnThread(LayerTreeHostImpl* host_impl) OVERRIDE {
+    LayerTreeImpl* active_tree = host_impl->active_tree();
+    // First build the tree and then we'll start running tests on layersorter
+    // itself
+    bool can_render_to_separate_surface = true;
+    int max_texture_size = 8096;
+    DoCalcDrawPropertiesImpl(can_render_to_separate_surface,
+                             max_texture_size,
+                             active_tree,
+                             host_impl);
+
+    LayerImplList base_list;
+    BuildLayerImplList(active_tree->root_layer(), &base_list);
+
+    int polygon_counter = 0;
+    ScopedPtrVector<DrawPolygon> polygon_list;
+    for (LayerImplList::iterator it = base_list.begin(); it != base_list.end();
+         ++it) {
+      DrawPolygon* draw_polygon =
+          new DrawPolygon(NULL,
+                          gfx::RectF((*it)->content_bounds()),
+                          (*it)->draw_transform(),
+                          polygon_counter++);
+      polygon_list.push_back(scoped_ptr<DrawPolygon>(draw_polygon));
+    }
+
+    timer_.Reset();
+    do {
+      ScopedPtrDeque<DrawPolygon> test_list;
+      for (int i = 0; i < num_duplicates_; i++) {
+        for (size_t i = 0; i < polygon_list.size(); i++) {
+          test_list.push_back(polygon_list[i]->CreateCopy());
+        }
+      }
+      BspTree bsp_tree(&test_list);
+      timer_.NextLap();
+    } while (!timer_.HasTimeLimitExpired());
+
+    EndTest();
+  }
+
+ private:
+  int num_duplicates_;
+};
+
 TEST_F(CalcDrawPropsMainTest, TenTen) {
   SetTestName("10_10_main_thread");
   ReadTestFile("10_10_layer_tree");
@@ -267,5 +328,33 @@ TEST_F(LayerSorterMainTest, LayerSorterRubik) {
   RunSortLayers();
 }
 
+TEST_F(BspTreePerfTest, BspTreeCubes) {
+  SetTestName("bsp_tree_cubes");
+  SetNumberOfDuplicates(1);
+  ReadTestFile("layer_sort_cubes");
+  RunSortLayers();
+}
+
+TEST_F(BspTreePerfTest, BspTreeRubik) {
+  SetTestName("bsp_tree_rubik");
+  SetNumberOfDuplicates(1);
+  ReadTestFile("layer_sort_rubik");
+  RunSortLayers();
+}
+
+TEST_F(BspTreePerfTest, BspTreeCubes_2) {
+  SetTestName("bsp_tree_cubes_2");
+  SetNumberOfDuplicates(2);
+  ReadTestFile("layer_sort_cubes");
+  RunSortLayers();
+}
+
+TEST_F(BspTreePerfTest, BspTreeCubes_4) {
+  SetTestName("bsp_tree_cubes_4");
+  SetNumberOfDuplicates(4);
+  ReadTestFile("layer_sort_cubes");
+  RunSortLayers();
+}
+
 }  // namespace
 }  // namespace cc