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