cc/output/bsp_tree_unittest.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/macros.h"
   6 #include "base/memory/scoped_ptr.h"
   7 #include "cc/base/scoped_ptr_deque.h"
   8 #include "cc/base/scoped_ptr_vector.h"
   9 #include "cc/output/bsp_tree.h"
  10 #include "cc/output/bsp_walk_action.h"
  11 #include "cc/quads/draw_polygon.h"
  12 #include "testing/gtest/include/gtest/gtest.h"
  13
  14 namespace cc {
  15 namespace {
  16
  17 #define EXPECT_SORTED_LISTS_EQ(polygon_list, compare_list)        \
  18   do {                                                            \
  19     EXPECT_EQ(polygon_list.size(), compare_list.size());          \
  20     for (unsigned int i = 0; i < polygon_list.size(); i++) {      \
  21       EXPECT_EQ(polygon_list[i]->order_index(), compare_list[i]); \
  22     }                                                             \
  23   } while (false);
  24
  25 #define INT_VECTOR_FROM_ARRAY(array) \
  26   std::vector<int>(array, array + arraysize(array))
  27
  28 #define CREATE_DRAW_POLYGON(vertex_vector, normal, polygon_id) \
  29   new DrawPolygon(NULL, vertex_vector, normal, polygon_id)
  30
  31 class BspTreeTest {
  32  public:
  33   static void RunTest(ScopedPtrDeque<DrawPolygon>* test_polygons,
  34                       const std::vector<int>& compare_list) {
  35     BspTree bsp_tree(test_polygons);
  36
  37     std::vector<DrawPolygon*> sorted_list;
  38     BspWalkActionToVector action_handler(&sorted_list);
  39     bsp_tree.TraverseWithActionHandler(&action_handler);
  40
  41     EXPECT_SORTED_LISTS_EQ(sorted_list, compare_list);
  42     EXPECT_TRUE(VerifySidedness(bsp_tree.root()));
  43   }
  44
  45   static bool VerifySidedness(const scoped_ptr<BspNode>& node) {
  46     // We check if both the front and back child nodes have geometry that is
  47     // completely on the expected side of the current node.
  48     bool front_ok = true;
  49     bool back_ok = true;
  50     if (node->back_child) {
  51       // Make sure the back child lies entirely behind this node.
  52       BspCompareResult result = DrawPolygon::SideCompare(
  53           *(node->back_child->node_data), *(node->node_data));
  54       if (result != BSP_BACK) {
  55         return false;
  56       }
  57       back_ok = VerifySidedness(node->back_child);
  58     }
  59     // Make sure the front child lies entirely in front of this node.
  60     if (node->front_child) {
  61       BspCompareResult result = DrawPolygon::SideCompare(
  62           *(node->front_child->node_data), *(node->node_data));
  63       if (result != BSP_FRONT) {
  64         return false;
  65       }
  66       front_ok = VerifySidedness(node->front_child);
  67     }
  68     if (!back_ok || !front_ok) {
  69       return false;
  70     }
  71
  72     // Now we need to make sure our coplanar geometry is all actually coplanar.
  73     for (size_t i = 0; i < node->coplanars_front.size(); i++) {
  74       BspCompareResult result = DrawPolygon::SideCompare(
  75           *(node->coplanars_front[i]), *(node->node_data));
  76       if (result != BSP_COPLANAR_FRONT) {
  77         return false;
  78       }
  79     }
  80     for (size_t i = 0; i < node->coplanars_back.size(); i++) {
  81       BspCompareResult result = DrawPolygon::SideCompare(
  82           *(node->coplanars_back[i]), *(node->node_data));
  83       if (result != BSP_COPLANAR_BACK) {
  84         return false;
  85       }
  86     }
  87     return true;
  88   }
  89 };
  90
  91 // Simple standing quads all parallel with each other, causing no splits.
  92 TEST(BspTreeTest, NoSplit) {
  93   std::vector<gfx::Point3F> vertices_a;
  94   vertices_a.push_back(gfx::Point3F(0.0f, 10.0f, 0.0f));
  95   vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
  96   vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
  97   vertices_a.push_back(gfx::Point3F(10.0f, 10.0f, 0.0f));
  98   std::vector<gfx::Point3F> vertices_b;
  99   vertices_b.push_back(gfx::Point3F(0.0f, 10.0f, -5.0f));
 100   vertices_b.push_back(gfx::Point3F(0.0f, 0.0f, -5.0f));
 101   vertices_b.push_back(gfx::Point3F(10.0f, 0.0f, -5.0f));
 102   vertices_b.push_back(gfx::Point3F(10.0f, 10.0f, -5.0f));
 103   std::vector<gfx::Point3F> vertices_c;
 104   vertices_c.push_back(gfx::Point3F(0.0f, 10.0f, 5.0f));
 105   vertices_c.push_back(gfx::Point3F(0.0f, 0.0f, 5.0f));
 106   vertices_c.push_back(gfx::Point3F(10.0f, 0.0f, 5.0f));
 107   vertices_c.push_back(gfx::Point3F(10.0f, 10.0f, 5.0f));
 108
 109   scoped_ptr<DrawPolygon> polygon_a(
 110       CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
 111   scoped_ptr<DrawPolygon> polygon_b(
 112       CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1));
 113   scoped_ptr<DrawPolygon> polygon_c(
 114       CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2));
 115
 116   ScopedPtrDeque<DrawPolygon> polygon_list;
 117   polygon_list.push_back(polygon_a.Pass());
 118   polygon_list.push_back(polygon_b.Pass());
 119   polygon_list.push_back(polygon_c.Pass());
 120
 121   int compare_ids[] = {1, 0, 2};
 122   std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 123   BspTreeTest::RunTest(&polygon_list, compare_list);
 124 }
 125
 126 // Basic two polygon split, can be viewed as a + from above.
 127 TEST(BspTreeTest, BasicSplit) {
 128   std::vector<gfx::Point3F> vertices_a;
 129   vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
 130   vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f));
 131   vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f));
 132   vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f));
 133   std::vector<gfx::Point3F> vertices_b;
 134   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -5.0f));
 135   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -5.0f));
 136   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, 5.0f));
 137   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, 5.0f));
 138
 139   scoped_ptr<DrawPolygon> polygon_a(
 140       CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
 141   scoped_ptr<DrawPolygon> polygon_b(
 142       CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
 143
 144   ScopedPtrDeque<DrawPolygon> polygon_list;
 145   polygon_list.push_back(polygon_a.Pass());
 146   polygon_list.push_back(polygon_b.Pass());
 147
 148   int compare_ids[] = {1, 0, 1};
 149   std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 150   BspTreeTest::RunTest(&polygon_list, compare_list);
 151 }
 152
 153 // Same as above with the second quad offset so it doesn't intersect. One quad
 154 // should be very clearly on one side of the other, and no splitting should
 155 // occur.
 156 TEST(BspTreeTest, QuadOffset) {
 157   std::vector<gfx::Point3F> vertices_a;
 158   vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
 159   vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f));
 160   vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f));
 161   vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f));
 162   std::vector<gfx::Point3F> vertices_b;
 163   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -15.0f));
 164   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -15.0f));
 165   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -10.0f));
 166   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -10.0f));
 167
 168   scoped_ptr<DrawPolygon> polygon_a(
 169       CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
 170   scoped_ptr<DrawPolygon> polygon_b(
 171       CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
 172
 173   ScopedPtrDeque<DrawPolygon> polygon_list;
 174   polygon_list.push_back(polygon_a.Pass());
 175   polygon_list.push_back(polygon_b.Pass());
 176
 177   int compare_ids[] = {1, 0};
 178   std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 179   BspTreeTest::RunTest(&polygon_list, compare_list);
 180 }
 181
 182 // Same as above, but this time we change the order in which the quads are
 183 // inserted into the tree, causing one to actually cross the plane of the other
 184 // and cause a split.
 185 TEST(BspTreeTest, QuadOffsetSplit) {
 186   std::vector<gfx::Point3F> vertices_a;
 187   vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
 188   vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f));
 189   vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f));
 190   vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f));
 191   std::vector<gfx::Point3F> vertices_b;
 192   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -15.0f));
 193   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -15.0f));
 194   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -10.0f));
 195   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -10.0f));
 196
 197   scoped_ptr<DrawPolygon> polygon_a(
 198       CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
 199   scoped_ptr<DrawPolygon> polygon_b(
 200       CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
 201
 202   ScopedPtrDeque<DrawPolygon> polygon_list;
 203   polygon_list.push_back(polygon_b.Pass());
 204   polygon_list.push_back(polygon_a.Pass());
 205
 206   int compare_ids[] = {0, 1, 0};
 207   std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 208   BspTreeTest::RunTest(&polygon_list, compare_list);
 209 }
 210
 211 // In addition to what can be viewed as a + from above, another piece of
 212 // geometry is inserted to cut these pieces right in the middle, viewed as
 213 // a quad from overhead.
 214 TEST(BspTreeTest, ThreeWaySplit) {
 215   std::vector<gfx::Point3F> vertices_a;
 216   vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
 217   vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f));
 218   vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f));
 219   vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f));
 220   std::vector<gfx::Point3F> vertices_b;
 221   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -5.0f));
 222   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -5.0f));
 223   vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, 5.0f));
 224   vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, 5.0f));
 225   std::vector<gfx::Point3F> vertices_c;
 226   vertices_c.push_back(gfx::Point3F(-5.0f, 0.0f, -5.0f));
 227   vertices_c.push_back(gfx::Point3F(-5.0f, 0.0f, 5.0f));
 228   vertices_c.push_back(gfx::Point3F(5.0f, 0.0f, 5.0f));
 229   vertices_c.push_back(gfx::Point3F(5.0f, 0.0f, -5.0f));
 230
 231   scoped_ptr<DrawPolygon> polygon_a(
 232       CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
 233   scoped_ptr<DrawPolygon> polygon_b(
 234       CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
 235   scoped_ptr<DrawPolygon> polygon_c(
 236       CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 1.0f, 0.0f), 2));
 237
 238   ScopedPtrDeque<DrawPolygon> polygon_list;
 239   polygon_list.push_back(polygon_a.Pass());
 240   polygon_list.push_back(polygon_b.Pass());
 241   polygon_list.push_back(polygon_c.Pass());
 242
 243   int compare_ids[] = {2, 1, 2, 0, 2, 1, 2};
 244   std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 245   BspTreeTest::RunTest(&polygon_list, compare_list);
 246 }
 247
 248 // This test checks whether coplanar geometry, when inserted into the tree in
 249 // order, comes back in the same order as it should.
 250 TEST(BspTreeTest, Coplanar) {
 251   std::vector<gfx::Point3F> vertices_a;
 252   vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
 253   vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f));
 254   vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f));
 255   vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f));
 256   std::vector<gfx::Point3F> vertices_b;
 257   vertices_b.push_back(gfx::Point3F(-4.0f, -4.0f, 0.0f));
 258   vertices_b.push_back(gfx::Point3F(-4.0f, 4.0f, 0.0f));
 259   vertices_b.push_back(gfx::Point3F(4.0f, 4.0f, 0.0f));
 260   vertices_b.push_back(gfx::Point3F(4.0f, -4.0f, 0.0f));
 261   std::vector<gfx::Point3F> vertices_c;
 262   vertices_c.push_back(gfx::Point3F(-3.0f, -3.0f, 0.0f));
 263   vertices_c.push_back(gfx::Point3F(-3.0f, 3.0f, 0.0f));
 264   vertices_c.push_back(gfx::Point3F(3.0f, 3.0f, 0.0f));
 265   vertices_c.push_back(gfx::Point3F(3.0f, -3.0f, 0.0f));
 266
 267   scoped_ptr<DrawPolygon> polygon_a(
 268       CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
 269   scoped_ptr<DrawPolygon> polygon_b(
 270       CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1));
 271   scoped_ptr<DrawPolygon> polygon_c(
 272       CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2));
 273
 274   scoped_ptr<DrawPolygon> polygon_d = polygon_a->CreateCopy();
 275   scoped_ptr<DrawPolygon> polygon_e = polygon_b->CreateCopy();
 276   scoped_ptr<DrawPolygon> polygon_f = polygon_c->CreateCopy();
 277
 278   {
 279     ScopedPtrDeque<DrawPolygon> polygon_list;
 280     polygon_list.push_back(polygon_a.Pass());
 281     polygon_list.push_back(polygon_b.Pass());
 282     polygon_list.push_back(polygon_c.Pass());
 283
 284     int compare_ids[] = {0, 1, 2};
 285     std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 286     BspTreeTest::RunTest(&polygon_list, compare_list);
 287   }
 288
 289   // Now check a different order and ensure we get that back as well
 290   {
 291     ScopedPtrDeque<DrawPolygon> polygon_list;
 292     polygon_list.push_back(polygon_f.Pass());
 293     polygon_list.push_back(polygon_d.Pass());
 294     polygon_list.push_back(polygon_e.Pass());
 295
 296     int compare_ids[] = {0, 1, 2};
 297     std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 298     BspTreeTest::RunTest(&polygon_list, compare_list);
 299   }
 300 }
 301
 302 // A bunch of coplanar geometry should end up sharing a single node, and
 303 // result in the final piece of geometry splitting into just two pieces on
 304 // either side of the shared plane.
 305 TEST(BspTreeTest, CoplanarSplit) {
 306   std::vector<gfx::Point3F> vertices_a;
 307   vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
 308   vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f));
 309   vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f));
 310   vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f));
 311   std::vector<gfx::Point3F> vertices_b;
 312   vertices_b.push_back(gfx::Point3F(-4.0f, -4.0f, 0.0f));
 313   vertices_b.push_back(gfx::Point3F(-4.0f, 4.0f, 0.0f));
 314   vertices_b.push_back(gfx::Point3F(4.0f, 4.0f, 0.0f));
 315   vertices_b.push_back(gfx::Point3F(4.0f, -4.0f, 0.0f));
 316   std::vector<gfx::Point3F> vertices_c;
 317   vertices_c.push_back(gfx::Point3F(-3.0f, -3.0f, 0.0f));
 318   vertices_c.push_back(gfx::Point3F(-3.0f, 3.0f, 0.0f));
 319   vertices_c.push_back(gfx::Point3F(3.0f, 3.0f, 0.0f));
 320   vertices_c.push_back(gfx::Point3F(3.0f, -3.0f, 0.0f));
 321   std::vector<gfx::Point3F> vertices_d;
 322   vertices_d.push_back(gfx::Point3F(0.0f, -15.0f, -15.0f));
 323   vertices_d.push_back(gfx::Point3F(0.0f, 15.0f, -15.0f));
 324   vertices_d.push_back(gfx::Point3F(0.0f, 15.0f, 15.0f));
 325   vertices_d.push_back(gfx::Point3F(0.0f, -15.0f, 15.0f));
 326
 327   scoped_ptr<DrawPolygon> polygon_a(
 328       CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
 329   scoped_ptr<DrawPolygon> polygon_b(
 330       CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1));
 331   scoped_ptr<DrawPolygon> polygon_c(
 332       CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2));
 333   scoped_ptr<DrawPolygon> polygon_d(
 334       CREATE_DRAW_POLYGON(vertices_d, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 3));
 335
 336   ScopedPtrDeque<DrawPolygon> polygon_list;
 337   polygon_list.push_back(polygon_a.Pass());
 338   polygon_list.push_back(polygon_b.Pass());
 339   polygon_list.push_back(polygon_c.Pass());
 340   polygon_list.push_back(polygon_d.Pass());
 341
 342   int compare_ids[] = {3, 0, 1, 2, 3};
 343   std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
 344   BspTreeTest::RunTest(&polygon_list, compare_list);
 345 }
 346
 347 }  // namespace
 348 }  // namespace cc