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

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: Small fixes to style/formatting, minor cleanup. 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/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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698