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 | |
74 static bool VerifySidedness(const std::unique_ptr<BspNode>& node) { | 48 static bool VerifySidedness(const std::unique_ptr<BspNode>& node) { |
75 // We check if both the front and back child nodes have geometry that is | 49 // We check if both the front and back child nodes have geometry that is |
76 // completely on the expected side of the current node. | 50 // completely on the expected side of the current node. |
77 bool front_ok = true; | 51 bool front_ok = true; |
78 bool back_ok = true; | 52 bool back_ok = true; |
79 if (node->back_child) { | 53 if (node->back_child) { |
80 // Make sure the back child lies entirely behind this node. | 54 // Make sure the back child lies entirely behind this node. |
81 BspCompareResult result = | 55 BspCompareResult result = DrawPolygon::SideCompare( |
82 SideCompare(*(node->back_child->node_data), *(node->node_data)); | 56 *(node->back_child->node_data), *(node->node_data)); |
83 if (result != BSP_BACK) { | 57 if (result != BSP_BACK) { |
84 return false; | 58 return false; |
85 } | 59 } |
86 back_ok = VerifySidedness(node->back_child); | 60 back_ok = VerifySidedness(node->back_child); |
87 } | 61 } |
88 // Make sure the front child lies entirely in front of this node. | 62 // Make sure the front child lies entirely in front of this node. |
89 if (node->front_child) { | 63 if (node->front_child) { |
90 BspCompareResult result = | 64 BspCompareResult result = DrawPolygon::SideCompare( |
91 SideCompare(*(node->front_child->node_data), *(node->node_data)); | 65 *(node->front_child->node_data), *(node->node_data)); |
92 if (result != BSP_FRONT) { | 66 if (result != BSP_FRONT) { |
93 return false; | 67 return false; |
94 } | 68 } |
95 front_ok = VerifySidedness(node->front_child); | 69 front_ok = VerifySidedness(node->front_child); |
96 } | 70 } |
97 if (!back_ok || !front_ok) { | 71 if (!back_ok || !front_ok) { |
98 return false; | 72 return false; |
99 } | 73 } |
100 | 74 |
101 // Now we need to make sure our coplanar geometry is all actually coplanar. | 75 // Now we need to make sure our coplanar geometry is all actually coplanar. |
102 for (size_t i = 0; i < node->coplanars_front.size(); i++) { | 76 for (size_t i = 0; i < node->coplanars_front.size(); i++) { |
103 BspCompareResult result = | 77 BspCompareResult result = DrawPolygon::SideCompare( |
104 SideCompare(*(node->coplanars_front[i]), *(node->node_data)); | 78 *(node->coplanars_front[i]), *(node->node_data)); |
105 if (result != BSP_COPLANAR_FRONT) { | 79 if (result != BSP_COPLANAR_FRONT) { |
106 return false; | 80 return false; |
107 } | 81 } |
108 } | 82 } |
109 for (size_t i = 0; i < node->coplanars_back.size(); i++) { | 83 for (size_t i = 0; i < node->coplanars_back.size(); i++) { |
110 BspCompareResult result = | 84 BspCompareResult result = DrawPolygon::SideCompare( |
111 SideCompare(*(node->coplanars_back[i]), *(node->node_data)); | 85 *(node->coplanars_back[i]), *(node->node_data)); |
112 if (result != BSP_COPLANAR_BACK) { | 86 if (result != BSP_COPLANAR_BACK) { |
113 return false; | 87 return false; |
114 } | 88 } |
115 } | 89 } |
116 return true; | 90 return true; |
117 } | 91 } |
118 }; | 92 }; |
119 | 93 |
120 // Simple standing quads all parallel with each other, causing no splits. | 94 // Simple standing quads all parallel with each other, causing no splits. |
121 TEST(BspTreeTest, NoSplit) { | 95 TEST(BspTreeTest, NoSplit) { |
(...skipping 246 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
368 polygon_list.push_back(std::move(polygon_c)); | 342 polygon_list.push_back(std::move(polygon_c)); |
369 polygon_list.push_back(std::move(polygon_d)); | 343 polygon_list.push_back(std::move(polygon_d)); |
370 | 344 |
371 int compare_ids[] = {3, 0, 1, 2, 3}; | 345 int compare_ids[] = {3, 0, 1, 2, 3}; |
372 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); | 346 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids); |
373 BspTreeTest::RunTest(&polygon_list, compare_list); | 347 BspTreeTest::RunTest(&polygon_list, compare_list); |
374 } | 348 } |
375 | 349 |
376 } // namespace | 350 } // namespace |
377 } // namespace cc | 351 } // namespace cc |
OLD | NEW |