OLD | NEW |
(Empty) | |
| 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 |
OLD | NEW |