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