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