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 349
