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

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 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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698