Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(366)

Side by Side Diff: cc/output/bsp_tree_unittest.cc

Issue 384083002: WIP BSP Tree for 3D Layer Sorting (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698