OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "cc/output/bsp_tree.h" | 5 #include "cc/output/bsp_tree.h" |
6 | 6 |
7 #include <stddef.h> | 7 #include <stddef.h> |
8 | 8 |
9 #include <deque> | 9 #include <deque> |
10 #include <memory> | 10 #include <memory> |
(...skipping 27 matching lines...) Expand all Loading... |
38 BspTree bsp_tree(test_polygons); | 38 BspTree bsp_tree(test_polygons); |
39 | 39 |
40 std::vector<DrawPolygon*> sorted_list; | 40 std::vector<DrawPolygon*> sorted_list; |
41 BspWalkActionToVector action_handler(&sorted_list); | 41 BspWalkActionToVector action_handler(&sorted_list); |
42 bsp_tree.TraverseWithActionHandler(&action_handler); | 42 bsp_tree.TraverseWithActionHandler(&action_handler); |
43 | 43 |
44 EXPECT_SORTED_LISTS_EQ(sorted_list, compare_list); | 44 EXPECT_SORTED_LISTS_EQ(sorted_list, compare_list); |
45 EXPECT_TRUE(VerifySidedness(bsp_tree.root())); | 45 EXPECT_TRUE(VerifySidedness(bsp_tree.root())); |
46 } | 46 } |
47 | 47 |
| 48 static BspCompareResult SideCompare(const DrawPolygon& a, |
| 49 const DrawPolygon& b) { |
| 50 const float split_threshold = 0.05f; |
| 51 bool pos = false; |
| 52 bool neg = false; |
| 53 for (const auto& pt : a.points()) { |
| 54 float dist = b.SignedPointDistance(pt); |
| 55 neg |= dist < -split_threshold; |
| 56 pos |= dist > split_threshold; |
| 57 } |
| 58 if (pos && neg) |
| 59 return BSP_SPLIT; |
| 60 if (neg) |
| 61 return BSP_BACK; |
| 62 if (pos) |
| 63 return BSP_FRONT; |
| 64 double dot = gfx::DotProduct(a.normal(), b.normal()); |
| 65 if ((dot >= 0.0f && a.order_index() >= b.order_index()) || |
| 66 (dot <= 0.0f && a.order_index() <= b.order_index())) { |
| 67 // The sign of the dot product of the normals along with document order |
| 68 // determine which side it goes on, the vertices are ambiguous. |
| 69 return BSP_COPLANAR_BACK; |
| 70 } |
| 71 return BSP_COPLANAR_FRONT; |
| 72 } |
| 73 |
48 static bool VerifySidedness(const std::unique_ptr<BspNode>& node) { | 74 static bool VerifySidedness(const std::unique_ptr<BspNode>& node) { |
49 // We check if both the front and back child nodes have geometry that is | 75 // We check if both the front and back child nodes have geometry that is |
50 // completely on the expected side of the current node. | 76 // completely on the expected side of the current node. |
51 bool front_ok = true; | 77 bool front_ok = true; |
52 bool back_ok = true; | 78 bool back_ok = true; |
53 if (node->back_child) { | 79 if (node->back_child) { |
54 // Make sure the back child lies entirely behind this node. | 80 // Make sure the back child lies entirely behind this node. |
55 BspCompareResult result = DrawPolygon::SideCompare( | 81 BspCompareResult result = |
56 *(node->back_child->node_data), *(node->node_data)); | 82 SideCompare(*(node->back_child->node_data), *(node->node_data)); |
57 if (result != BSP_BACK) { | 83 if (result != BSP_BACK) { |
58 return false; | 84 return false; |
59 } | 85 } |
60 back_ok = VerifySidedness(node->back_child); | 86 back_ok = VerifySidedness(node->back_child); |
61 } | 87 } |
62 // Make sure the front child lies entirely in front of this node. | 88 // Make sure the front child lies entirely in front of this node. |
63 if (node->front_child) { | 89 if (node->front_child) { |
64 BspCompareResult result = DrawPolygon::SideCompare( | 90 BspCompareResult result = |
65 *(node->front_child->node_data), *(node->node_data)); | 91 SideCompare(*(node->front_child->node_data), *(node->node_data)); |
66 if (result != BSP_FRONT) { | 92 if (result != BSP_FRONT) { |
67 return false; | 93 return false; |
68 } | 94 } |
69 front_ok = VerifySidedness(node->front_child); | 95 front_ok = VerifySidedness(node->front_child); |
70 } | 96 } |
71 if (!back_ok || !front_ok) { | 97 if (!back_ok || !front_ok) { |
72 return false; | 98 return false; |
73 } | 99 } |
74 | 100 |
75 // Now we need to make sure our coplanar geometry is all actually coplanar. | 101 // Now we need to make sure our coplanar geometry is all actually coplanar. |
76 for (size_t i = 0; i < node->coplanars_front.size(); i++) { | 102 for (size_t i = 0; i < node->coplanars_front.size(); i++) { |
77 BspCompareResult result = DrawPolygon::SideCompare( | 103 BspCompareResult result = |
78 *(node->coplanars_front[i]), *(node->node_data)); | 104 SideCompare(*(node->coplanars_front[i]), *(node->node_data)); |
79 if (result != BSP_COPLANAR_FRONT) { | 105 if (result != BSP_COPLANAR_FRONT) { |
80 return false; | 106 return false; |
81 } | 107 } |
82 } | 108 } |
83 for (size_t i = 0; i < node->coplanars_back.size(); i++) { | 109 for (size_t i = 0; i < node->coplanars_back.size(); i++) { |
84 BspCompareResult result = DrawPolygon::SideCompare( | 110 BspCompareResult result = |
85 *(node->coplanars_back[i]), *(node->node_data)); | 111 SideCompare(*(node->coplanars_back[i]), *(node->node_data)); |
86 if (result != BSP_COPLANAR_BACK) { | 112 if (result != BSP_COPLANAR_BACK) { |
87 return false; | 113 return false; |
88 } | 114 } |
89 } | 115 } |
90 return true; | 116 return true; |
91 } | 117 } |
92 }; | 118 }; |
93 | 119 |
94 // Simple standing quads all parallel with each other, causing no splits. | 120 // Simple standing quads all parallel with each other, causing no splits. |
95 TEST(BspTreeTest, NoSplit) { | 121 TEST(BspTreeTest, NoSplit) { |
(...skipping 246 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
342 polygon_list.push_back(std::move(polygon_c)); | 368 polygon_list.push_back(std::move(polygon_c)); |
343 polygon_list.push_back(std::move(polygon_d)); | 369 polygon_list.push_back(std::move(polygon_d)); |
344 | 370 |
345 int compare_ids[] = {3, 0, 1, 2, 3}; | 371 int compare_ids[] = {3, 0, 1, 2, 3}; |
346 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); | 372 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
347 BspTreeTest::RunTest(&polygon_list, compare_list); | 373 BspTreeTest::RunTest(&polygon_list, compare_list); |
348 } | 374 } |
349 | 375 |
350 } // namespace | 376 } // namespace |
351 } // namespace cc | 377 } // namespace cc |
OLD | NEW |