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

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

Powered by Google App Engine
This is Rietveld 408576698