WIP BSP Tree for 3D Layer Sorting

cc/output/bsp_tree_unittest.cc

Index: cc/output/bsp_tree_unittest.cc
diff --git a/cc/output/bsp_tree_unittest.cc b/cc/output/bsp_tree_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..5dbbca67a55ee50e6b3a2ca5e83b0ecce38a8cef
--- /dev/null
+++ b/cc/output/bsp_tree_unittest.cc
@@ -0,0 +1,352 @@
+// Copyright 2014 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 "base/memory/scoped_ptr.h"
+#include "cc/base/scoped_ptr_vector.h"
+#include "cc/output/bsp_controller.h"
+#include "cc/output/bsp_tree.h"
+#include "cc/output/bsp_walk_action.h"
+#include "cc/quads/draw_polygon.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace cc {
+namespace {
+
+#define COMPARE_THRESHOLD 1.0f
+#define SPLIT_THRESHOLD 0.5f
+
+enum TestSide { IN_FRONT, BEHIND, COPLANAR };

[Ian Vollick, 2014/07/16 20:54:33]

It would be nice to use the bsp test enum here rather than creating another. (As
well as the what-side-am-I-on routine).

[troyhildebrandt, 2014/07/18 21:48:26]

Done.

+
+class TestBspController : public BspController {
+ public:
+  TestBspController(float compare_threshold, float split_threshold)
+      : BspController(compare_threshold, split_threshold) {}
+  virtual float SplitWeight(const DrawPolygon& poly) OVERRIDE { return 0.0f; }

[Ian Vollick, 2014/07/16 20:54:33]

I'm not sure I understand why we want to override SplitWeight to return 0.0f
here.

[troyhildebrandt, 2014/07/18 21:48:26]

Since the weights of polygons affect what order they're placed in the tree, it's
important that we don't break unit tests if the heuristic is ever changed. By
simply forcing all the weights to be 0, the polygons will all be put into the
tree in the same order as they're given, and the unit tests won't be affected by
changing heuristics.

[Ian Vollick, 2014/07/19 00:45:01]

That makes a lot of sense, but it's definitely not obvious. Maybe you could cut
and paste this into a comment in the code for future passers-by?

+};
+
+#define EXPECT_SORTED_LISTS_EQ(polygon_list, compare_list)   \
+  do {                                                       \
+    EXPECT_EQ(polygon_list.size(), compare_list.size());     \
+    for (unsigned int i = 0; i < polygon_list.size(); i++) { \
+      EXPECT_EQ(polygon_list[i]->id, compare_list[i]);       \
+    }                                                        \
+  } while (false);
+
+#define INT_VECTOR_FROM_ARRAY(array) \
+  std::vector<int>(array, array + sizeof(array) / sizeof(array[0]))

[Ian Vollick, 2014/07/16 20:54:33]

Might not need a macro for this? We've got ARRAYSIZE in base. Should just be
able to do std::vector<int>(array, array + ARRAYSIZE(array));

[troyhildebrandt, 2014/07/18 21:48:26]

Done.

+
+class BspTreeTesting {

[Ian Vollick, 2014/07/16 20:54:33]

nit: Present participle is weird for a class name. I'd go with BspTreeTest.

[troyhildebrandt, 2014/07/18 21:48:26]

Done.

+ public:
+  static void RunTest(ScopedPtrVector<DrawPolygon>* test_polygons,
+                      const std::vector<int>& compare_list) {
+    TestBspController bsp_controller(COMPARE_THRESHOLD, SPLIT_THRESHOLD);
+    BspTree bsp_tree(&bsp_controller, test_polygons);
+
+    std::vector<DrawPolygon*> sorted_list;
+    BspWalkActionToVector action_handler(&sorted_list);
+    bsp_tree.TraverseWithActionHandler(&action_handler);
+
+    // This loop is helpful for debugging purposes, will be removed once the
+    // tests are complete.
+    for (unsigned int i = 0; i < sorted_list.size(); i++)
+      LOG(ERROR) << sorted_list[i]->id;
+    EXPECT_SORTED_LISTS_EQ(sorted_list, compare_list);
+    EXPECT_TRUE(VerifySidedness(bsp_tree.root()));
+  }
+
+  static bool VerifySidedness(const scoped_ptr<BspNode>& node) {
+    // We check if both the front and back child nodes have geometry that is
+    // completely on the expected side of the current node.
+    bool front_ok = true;
+    bool back_ok = true;
+    if (node->back_child) {
+      // Make sure the back child lies entirely behind this node.
+      if (!GeometrySide(node, node->back_child->node_data.get(), BEHIND)) {
+        return false;
+      }
+      back_ok = VerifySidedness(node->back_child);
+    }
+    // Make sure the front child lies entirely in front of this node.
+    if (node->front_child) {
+      if (!GeometrySide(node, node->front_child->node_data.get(), IN_FRONT)) {
+        return false;
+      }
+      front_ok = VerifySidedness(node->front_child);
+    }
+    // Now we need to make sure our coplanar geometry is all actually coplanar.
+    for (unsigned int i = 0; i < node->coplanars_front.size(); i++) {
+      if (!GeometrySide(node, node->coplanars_front[i], COPLANAR)) {
+        return false;
+      }
+    }
+    for (unsigned int i = 0; i < node->coplanars_back.size(); i++) {
+      if (!GeometrySide(node, node->coplanars_back[i], COPLANAR)) {
+        return false;
+      }
+    }
+
+    if (!back_ok || !front_ok) {
+      return false;

[Ian Vollick, 2014/07/16 20:54:33]

Could we return false before recurring?

[troyhildebrandt, 2014/07/18 21:48:26]

Done.

+    }
+    return true;
+  }
+
+  static bool GeometrySide(const scoped_ptr<BspNode>& parent,
+                           DrawPolygon* child_data,
+                           TestSide side) {
+    for (unsigned int i = 0; i < child_data->points.size(); i++) {
+      float p_distance =
+          parent->node_data->SignedPointDistance(child_data->points[i]);
+      if (side == BEHIND) {
+        if (p_distance > COMPARE_THRESHOLD) {
+          return false;
+        }
+      } else if (side == IN_FRONT) {
+        if (p_distance < -COMPARE_THRESHOLD) {
+          return false;
+        }
+      } else {
+        // We assume here that we're testing if it's coplanar.
+        if (std::abs(p_distance) > COMPARE_THRESHOLD) {
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+};
+
+// Simple standing quads all parallel with each other, causing no splits.
+TEST(BspTreeTest, NoSplit) {
+  gfx::Point3F vertices_a[4];
+  vertices_a[0] = gfx::Point3F(0.0f, 10.0f, 0.0f);
+  vertices_a[1] = gfx::Point3F(0.0f, 0.0f, 0.0f);
+  vertices_a[2] = gfx::Point3F(10.0f, 0.0f, 0.0f);
+  vertices_a[3] = gfx::Point3F(10.0f, 10.0f, 0.0f);
+  gfx::Point3F vertices_b[4];
+  vertices_b[0] = gfx::Point3F(0.0f, 10.0f, -5.0f);
+  vertices_b[1] = gfx::Point3F(0.0f, 0.0f, -5.0f);
+  vertices_b[2] = gfx::Point3F(10.0f, 0.0f, -5.0f);
+  vertices_b[3] = gfx::Point3F(10.0f, 10.0f, -5.0f);
+  gfx::Point3F vertices_c[4];
+  vertices_c[0] = gfx::Point3F(0.0f, 10.0f, 5.0f);
+  vertices_c[1] = gfx::Point3F(0.0f, 0.0f, 5.0f);
+  vertices_c[2] = gfx::Point3F(10.0f, 0.0f, 5.0f);
+  vertices_c[3] = gfx::Point3F(10.0f, 10.0f, 5.0f);
+
+  scoped_ptr<DrawPolygon> polygon_a(
+      new DrawPolygon(NULL, vertices_a, 4, 0, true));
+  scoped_ptr<DrawPolygon> polygon_b(
+      new DrawPolygon(NULL, vertices_b, 4, 1, true));
+  scoped_ptr<DrawPolygon> polygon_c(
+      new DrawPolygon(NULL, vertices_c, 4, 2, true));
+  ScopedPtrVector<DrawPolygon> polygon_list;
+  polygon_list.push_back(polygon_a.Pass());
+  polygon_list.push_back(polygon_b.Pass());
+  polygon_list.push_back(polygon_c.Pass());
+
+  int compare_ids[] = {1, 0, 2};
+  std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
+  BspTreeTesting::RunTest(&polygon_list, compare_list);
+}
+
+// Basic two polygon split, can be viewed as a + from above.
+TEST(BspTreeTest, BasicSplit) {
+  gfx::Point3F vertices_a[4];
+  vertices_a[0] = gfx::Point3F(-5.0f, 5.0f, 0.0f);
+  vertices_a[1] = gfx::Point3F(-5.0f, -5.0f, 0.0f);
+  vertices_a[2] = gfx::Point3F(5.0f, -5.0f, 0.0f);
+  vertices_a[3] = gfx::Point3F(5.0f, 5.0f, 0.0f);
+  gfx::Point3F vertices_b[4];
+  vertices_b[0] = gfx::Point3F(0.0f, 5.0f, -5.0f);
+  vertices_b[1] = gfx::Point3F(0.0f, -5.0f, -5.0f);
+  vertices_b[2] = gfx::Point3F(0.0f, -5.0f, 5.0f);
+  vertices_b[3] = gfx::Point3F(0.0f, 5.0f, 5.0f);
+
+  scoped_ptr<DrawPolygon> polygon_a(
+      new DrawPolygon(NULL, vertices_a, 4, 0, true));
+  scoped_ptr<DrawPolygon> polygon_b(
+      new DrawPolygon(NULL, vertices_b, 4, 1, true));
+  ScopedPtrVector<DrawPolygon> polygon_list;
+  polygon_list.push_back(polygon_a.Pass());
+  polygon_list.push_back(polygon_b.Pass());
+
+  int compare_ids[] = {1, 0, 1};
+  std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
+  BspTreeTesting::RunTest(&polygon_list, compare_list);
+}
+
+// Same as above with the second quad offset so it doesn't intersect. One quad
+// should be very clearly on one side of the other, and no splitting should
+// occur.
+TEST(BspTreeTest, QuadOffset) {
+  gfx::Point3F vertices_a[4];
+  vertices_a[0] = gfx::Point3F(-5.0f, 5.0f, 0.0f);
+  vertices_a[1] = gfx::Point3F(-5.0f, -5.0f, 0.0f);
+  vertices_a[2] = gfx::Point3F(5.0f, -5.0f, 0.0f);
+  vertices_a[3] = gfx::Point3F(5.0f, 5.0f, 0.0f);
+  gfx::Point3F vertices_b[4];
+  vertices_b[0] = gfx::Point3F(0.0f, 5.0f, -15.0f);
+  vertices_b[1] = gfx::Point3F(0.0f, -5.0f, -15.0f);
+  vertices_b[2] = gfx::Point3F(0.0f, -5.0f, -10.0f);
+  vertices_b[3] = gfx::Point3F(0.0f, 5.0f, -10.0f);
+
+  scoped_ptr<DrawPolygon> polygon_a(
+      new DrawPolygon(NULL, vertices_a, 4, 0, true));
+  scoped_ptr<DrawPolygon> polygon_b(
+      new DrawPolygon(NULL, vertices_b, 4, 1, true));
+  ScopedPtrVector<DrawPolygon> polygon_list;
+  polygon_list.push_back(polygon_a.Pass());
+  polygon_list.push_back(polygon_b.Pass());
+
+  int compare_ids[] = {1, 0};
+  std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
+  BspTreeTesting::RunTest(&polygon_list, compare_list);
+}
+
+// Same as above, but this time we change the order in which the quads are
+// inserted into the tree, causing one to actually cross the plane of the other
+// and cause a split.
+TEST(BspTreeTest, QuadOffsetSplit) {
+  gfx::Point3F vertices_a[4];
+  vertices_a[0] = gfx::Point3F(-5.0f, 5.0f, 0.0f);
+  vertices_a[1] = gfx::Point3F(-5.0f, -5.0f, 0.0f);
+  vertices_a[2] = gfx::Point3F(5.0f, -5.0f, 0.0f);
+  vertices_a[3] = gfx::Point3F(5.0f, 5.0f, 0.0f);
+  gfx::Point3F vertices_b[4];
+  vertices_b[0] = gfx::Point3F(0.0f, 5.0f, -15.0f);
+  vertices_b[1] = gfx::Point3F(0.0f, -5.0f, -15.0f);
+  vertices_b[2] = gfx::Point3F(0.0f, -5.0f, -10.0f);
+  vertices_b[3] = gfx::Point3F(0.0f, 5.0f, -10.0f);
+
+  scoped_ptr<DrawPolygon> polygon_a(
+      new DrawPolygon(NULL, vertices_a, 4, 0, true));
+  scoped_ptr<DrawPolygon> polygon_b(
+      new DrawPolygon(NULL, vertices_b, 4, 1, true));
+  ScopedPtrVector<DrawPolygon> polygon_list;
+  polygon_list.push_back(polygon_b.Pass());
+  polygon_list.push_back(polygon_a.Pass());
+
+  int compare_ids[] = {0, 1, 0};
+  std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
+  BspTreeTesting::RunTest(&polygon_list, compare_list);
+}
+
+// In addition to what can be viewed as a + from above, another piece of
+// geometry is inserted to cut these pieces right in the middle, viewed as
+// a quad from overhead.
+TEST(BspTreeTest, ThreeWaySplit) {
+  gfx::Point3F vertices_a[4];
+  vertices_a[0] = gfx::Point3F(-5.0f, 5.0f, 0.0f);
+  vertices_a[1] = gfx::Point3F(-5.0f, -5.0f, 0.0f);
+  vertices_a[2] = gfx::Point3F(5.0f, -5.0f, 0.0f);
+  vertices_a[3] = gfx::Point3F(5.0f, 5.0f, 0.0f);
+  gfx::Point3F vertices_b[4];
+  vertices_b[0] = gfx::Point3F(0.0f, 5.0f, -5.0f);
+  vertices_b[1] = gfx::Point3F(0.0f, -5.0f, -5.0f);
+  vertices_b[2] = gfx::Point3F(0.0f, -5.0f, 5.0f);
+  vertices_b[3] = gfx::Point3F(0.0f, 5.0f, 5.0f);
+  gfx::Point3F vertices_c[4];
+  vertices_c[0] = gfx::Point3F(-5.0f, 0.0f, 5.0f);
+  vertices_c[1] = gfx::Point3F(-5.0f, 0.0f, -5.0f);
+  vertices_c[2] = gfx::Point3F(5.0f, 0.0f, -5.0f);
+  vertices_c[3] = gfx::Point3F(5.0f, 0.0f, 5.0f);
+
+  scoped_ptr<DrawPolygon> polygon_a(
+      new DrawPolygon(NULL, vertices_a, 4, 0, true));
+  scoped_ptr<DrawPolygon> polygon_b(
+      new DrawPolygon(NULL, vertices_b, 4, 1, true));
+  scoped_ptr<DrawPolygon> polygon_c(
+      new DrawPolygon(NULL, vertices_c, 4, 2, true));
+  ScopedPtrVector<DrawPolygon> polygon_list;
+  polygon_list.push_back(polygon_a.Pass());
+  polygon_list.push_back(polygon_b.Pass());
+  polygon_list.push_back(polygon_c.Pass());
+
+  int compare_ids[] = {2, 1, 2, 0, 2, 1, 2};
+  std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
+  BspTreeTesting::RunTest(&polygon_list, compare_list);
+}
+
+// This test checks whether coplanar geometry, when inserted into the tree in
+// order, comes back in the same order as it should.
+TEST(BspTreeTest, Coplanar) {
+  gfx::Point3F vertices_a[4];
+  vertices_a[0] = gfx::Point3F(-5.0f, 5.0f, 0.0f);
+  vertices_a[1] = gfx::Point3F(-5.0f, -5.0f, 0.0f);
+  vertices_a[2] = gfx::Point3F(5.0f, -5.0f, 0.0f);
+  vertices_a[3] = gfx::Point3F(5.0f, 5.0f, 0.0f);
+  gfx::Point3F vertices_b[4];
+  vertices_b[0] = gfx::Point3F(-4.0f, 4.0f, 0.0f);
+  vertices_b[1] = gfx::Point3F(-4.0f, -4.0f, 0.0f);
+  vertices_b[2] = gfx::Point3F(4.0f, -4.0f, 0.0f);
+  vertices_b[3] = gfx::Point3F(4.0f, 4.0f, 0.0f);
+  gfx::Point3F vertices_c[4];
+  vertices_c[0] = gfx::Point3F(-3.0f, 3.0f, 0.0f);
+  vertices_c[1] = gfx::Point3F(-3.0f, -3.0f, 0.0f);
+  vertices_c[2] = gfx::Point3F(3.0f, -3.0f, 0.0f);
+  vertices_c[3] = gfx::Point3F(3.0f, 3.0f, 0.0f);
+
+  scoped_ptr<DrawPolygon> polygon_a(
+      new DrawPolygon(NULL, vertices_a, 4, 0, true));
+  scoped_ptr<DrawPolygon> polygon_b(
+      new DrawPolygon(NULL, vertices_b, 4, 1, true));
+  scoped_ptr<DrawPolygon> polygon_c(
+      new DrawPolygon(NULL, vertices_c, 4, 2, true));
+  ScopedPtrVector<DrawPolygon> polygon_list;
+  polygon_list.push_back(polygon_a.Pass());
+  polygon_list.push_back(polygon_b.Pass());
+  polygon_list.push_back(polygon_c.Pass());
+
+  int compare_ids[] = {0, 1, 2};
+  std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
+  BspTreeTesting::RunTest(&polygon_list, compare_list);
+}
+
+// A bunch of coplanar geometry should end up sharing a single node, and
+// result in the final piece of geometry splitting into just two pieces on
+// either side of the shared plane.
+TEST(BspTreeTest, CoplanarSplit) {
+  gfx::Point3F vertices_a[4];
+  vertices_a[0] = gfx::Point3F(-5.0f, 5.0f, 0.0f);
+  vertices_a[1] = gfx::Point3F(-5.0f, -5.0f, 0.0f);
+  vertices_a[2] = gfx::Point3F(5.0f, -5.0f, 0.0f);
+  vertices_a[3] = gfx::Point3F(5.0f, 5.0f, 0.0f);
+  gfx::Point3F vertices_b[4];
+  vertices_b[0] = gfx::Point3F(-4.0f, 4.0f, 0.0f);
+  vertices_b[1] = gfx::Point3F(-4.0f, -4.0f, 0.0f);
+  vertices_b[2] = gfx::Point3F(4.0f, -4.0f, 0.0f);
+  vertices_b[3] = gfx::Point3F(4.0f, 4.0f, 0.0f);
+  gfx::Point3F vertices_c[4];
+  vertices_c[0] = gfx::Point3F(-3.0f, 3.0f, 0.0f);
+  vertices_c[1] = gfx::Point3F(-3.0f, -3.0f, 0.0f);
+  vertices_c[2] = gfx::Point3F(3.0f, -3.0f, 0.0f);
+  vertices_c[3] = gfx::Point3F(3.0f, 3.0f, 0.0f);
+  gfx::Point3F vertices_d[4];
+  vertices_d[0] = gfx::Point3F(0.0f, 15.0f, -15.0f);
+  vertices_d[1] = gfx::Point3F(0.0f, -15.0f, -15.0f);
+  vertices_d[2] = gfx::Point3F(0.0f, -15.0f, 15.0f);
+  vertices_d[3] = gfx::Point3F(0.0f, 15.0f, 15.0f);
+
+  scoped_ptr<DrawPolygon> polygon_a(
+      new DrawPolygon(NULL, vertices_a, 4, 0, true));
+  scoped_ptr<DrawPolygon> polygon_b(
+      new DrawPolygon(NULL, vertices_b, 4, 1, true));
+  scoped_ptr<DrawPolygon> polygon_c(
+      new DrawPolygon(NULL, vertices_c, 4, 2, true));
+  scoped_ptr<DrawPolygon> polygon_d(
+      new DrawPolygon(NULL, vertices_d, 4, 3, true));
+  ScopedPtrVector<DrawPolygon> polygon_list;
+  polygon_list.push_back(polygon_a.Pass());
+  polygon_list.push_back(polygon_b.Pass());
+  polygon_list.push_back(polygon_c.Pass());
+  polygon_list.push_back(polygon_d.Pass());
+
+  int compare_ids[] = {3, 0, 1, 2, 3};
+  std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
+  BspTreeTesting::RunTest(&polygon_list, compare_list);
+}
+
+}  // namespace
+}  // namespace cc