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_deque.h"
8 #include "cc/base/scoped_ptr_vector.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, normal, polygon_id) \
29 new DrawPolygon(NULL, vertex_vector, normal, polygon_id)
30
31 class BspTreeTest {
32 public:
RunTest(ScopedPtrDeque<DrawPolygon> * test_polygons,const std::vector<int> & compare_list)33 static void RunTest(ScopedPtrDeque<DrawPolygon>* test_polygons,
34 const std::vector<int>& compare_list) {
35 BspTree bsp_tree(test_polygons);
36
37 std::vector<DrawPolygon*> sorted_list;
38 BspWalkActionToVector action_handler(&sorted_list);
39 bsp_tree.TraverseWithActionHandler(&action_handler);
40
41 EXPECT_SORTED_LISTS_EQ(sorted_list, compare_list);
42 EXPECT_TRUE(VerifySidedness(bsp_tree.root()));
43 }
44
VerifySidedness(const scoped_ptr<BspNode> & node)45 static bool VerifySidedness(const scoped_ptr<BspNode>& node) {
46 // We check if both the front and back child nodes have geometry that is
47 // completely on the expected side of the current node.
48 bool front_ok = true;
49 bool back_ok = true;
50 if (node->back_child) {
51 // Make sure the back child lies entirely behind this node.
52 BspCompareResult result = DrawPolygon::SideCompare(
53 *(node->back_child->node_data), *(node->node_data));
54 if (result != BSP_BACK) {
55 return false;
56 }
57 back_ok = VerifySidedness(node->back_child);
58 }
59 // Make sure the front child lies entirely in front of this node.
60 if (node->front_child) {
61 BspCompareResult result = DrawPolygon::SideCompare(
62 *(node->front_child->node_data), *(node->node_data));
63 if (result != BSP_FRONT) {
64 return false;
65 }
66 front_ok = VerifySidedness(node->front_child);
67 }
68 if (!back_ok || !front_ok) {
69 return false;
70 }
71
72 // Now we need to make sure our coplanar geometry is all actually coplanar.
73 for (size_t i = 0; i < node->coplanars_front.size(); i++) {
74 BspCompareResult result = DrawPolygon::SideCompare(
75 *(node->coplanars_front[i]), *(node->node_data));
76 if (result != BSP_COPLANAR_FRONT) {
77 return false;
78 }
79 }
80 for (size_t i = 0; i < node->coplanars_back.size(); i++) {
81 BspCompareResult result = DrawPolygon::SideCompare(
82 *(node->coplanars_back[i]), *(node->node_data));
83 if (result != BSP_COPLANAR_BACK) {
84 return false;
85 }
86 }
87 return true;
88 }
89 };
90
91 // Simple standing quads all parallel with each other, causing no splits.
TEST(BspTreeTest,NoSplit)92 TEST(BspTreeTest, NoSplit) {
93 std::vector<gfx::Point3F> vertices_a;
94 vertices_a.push_back(gfx::Point3F(0.0f, 10.0f, 0.0f));
95 vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
96 vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
97 vertices_a.push_back(gfx::Point3F(10.0f, 10.0f, 0.0f));
98 std::vector<gfx::Point3F> vertices_b;
99 vertices_b.push_back(gfx::Point3F(0.0f, 10.0f, -5.0f));
100 vertices_b.push_back(gfx::Point3F(0.0f, 0.0f, -5.0f));
101 vertices_b.push_back(gfx::Point3F(10.0f, 0.0f, -5.0f));
102 vertices_b.push_back(gfx::Point3F(10.0f, 10.0f, -5.0f));
103 std::vector<gfx::Point3F> vertices_c;
104 vertices_c.push_back(gfx::Point3F(0.0f, 10.0f, 5.0f));
105 vertices_c.push_back(gfx::Point3F(0.0f, 0.0f, 5.0f));
106 vertices_c.push_back(gfx::Point3F(10.0f, 0.0f, 5.0f));
107 vertices_c.push_back(gfx::Point3F(10.0f, 10.0f, 5.0f));
108
109 scoped_ptr<DrawPolygon> polygon_a(
110 CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
111 scoped_ptr<DrawPolygon> polygon_b(
112 CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1));
113 scoped_ptr<DrawPolygon> polygon_c(
114 CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2));
115
116 ScopedPtrDeque<DrawPolygon> polygon_list;
117 polygon_list.push_back(polygon_a.Pass());
118 polygon_list.push_back(polygon_b.Pass());
119 polygon_list.push_back(polygon_c.Pass());
120
121 int compare_ids[] = {1, 0, 2};
122 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
123 BspTreeTest::RunTest(&polygon_list, compare_list);
124 }
125
126 // Basic two polygon split, can be viewed as a + from above.
TEST(BspTreeTest,BasicSplit)127 TEST(BspTreeTest, BasicSplit) {
128 std::vector<gfx::Point3F> vertices_a;
129 vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
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 std::vector<gfx::Point3F> vertices_b;
134 vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -5.0f));
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
139 scoped_ptr<DrawPolygon> polygon_a(
140 CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
141 scoped_ptr<DrawPolygon> polygon_b(
142 CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
143
144 ScopedPtrDeque<DrawPolygon> polygon_list;
145 polygon_list.push_back(polygon_a.Pass());
146 polygon_list.push_back(polygon_b.Pass());
147
148 int compare_ids[] = {1, 0, 1};
149 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
150 BspTreeTest::RunTest(&polygon_list, compare_list);
151 }
152
153 // Same as above with the second quad offset so it doesn't intersect. One quad
154 // should be very clearly on one side of the other, and no splitting should
155 // occur.
TEST(BspTreeTest,QuadOffset)156 TEST(BspTreeTest, QuadOffset) {
157 std::vector<gfx::Point3F> vertices_a;
158 vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
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 std::vector<gfx::Point3F> vertices_b;
163 vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -15.0f));
164 vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -15.0f));
165 vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -10.0f));
166 vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -10.0f));
167
168 scoped_ptr<DrawPolygon> polygon_a(
169 CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
170 scoped_ptr<DrawPolygon> polygon_b(
171 CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
172
173 ScopedPtrDeque<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};
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, but this time we change the order in which the quads are
183 // inserted into the tree, causing one to actually cross the plane of the other
184 // and cause a split.
TEST(BspTreeTest,QuadOffsetSplit)185 TEST(BspTreeTest, QuadOffsetSplit) {
186 std::vector<gfx::Point3F> vertices_a;
187 vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
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 std::vector<gfx::Point3F> vertices_b;
192 vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -15.0f));
193 vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -15.0f));
194 vertices_b.push_back(gfx::Point3F(0.0f, 5.0f, -10.0f));
195 vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -10.0f));
196
197 scoped_ptr<DrawPolygon> polygon_a(
198 CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
199 scoped_ptr<DrawPolygon> polygon_b(
200 CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
201
202 ScopedPtrDeque<DrawPolygon> polygon_list;
203 polygon_list.push_back(polygon_b.Pass());
204 polygon_list.push_back(polygon_a.Pass());
205
206 int compare_ids[] = {0, 1, 0};
207 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
208 BspTreeTest::RunTest(&polygon_list, compare_list);
209 }
210
211 // In addition to what can be viewed as a + from above, another piece of
212 // geometry is inserted to cut these pieces right in the middle, viewed as
213 // a quad from overhead.
TEST(BspTreeTest,ThreeWaySplit)214 TEST(BspTreeTest, ThreeWaySplit) {
215 std::vector<gfx::Point3F> vertices_a;
216 vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
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 std::vector<gfx::Point3F> vertices_b;
221 vertices_b.push_back(gfx::Point3F(0.0f, -5.0f, -5.0f));
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 std::vector<gfx::Point3F> vertices_c;
226 vertices_c.push_back(gfx::Point3F(-5.0f, 0.0f, -5.0f));
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
231 scoped_ptr<DrawPolygon> polygon_a(
232 CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
233 scoped_ptr<DrawPolygon> polygon_b(
234 CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1));
235 scoped_ptr<DrawPolygon> polygon_c(
236 CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 1.0f, 0.0f), 2));
237
238 ScopedPtrDeque<DrawPolygon> polygon_list;
239 polygon_list.push_back(polygon_a.Pass());
240 polygon_list.push_back(polygon_b.Pass());
241 polygon_list.push_back(polygon_c.Pass());
242
243 int compare_ids[] = {2, 1, 2, 0, 2, 1, 2};
244 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
245 BspTreeTest::RunTest(&polygon_list, compare_list);
246 }
247
248 // This test checks whether coplanar geometry, when inserted into the tree in
249 // order, comes back in the same order as it should.
TEST(BspTreeTest,Coplanar)250 TEST(BspTreeTest, Coplanar) {
251 std::vector<gfx::Point3F> vertices_a;
252 vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
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 std::vector<gfx::Point3F> vertices_b;
257 vertices_b.push_back(gfx::Point3F(-4.0f, -4.0f, 0.0f));
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 std::vector<gfx::Point3F> vertices_c;
262 vertices_c.push_back(gfx::Point3F(-3.0f, -3.0f, 0.0f));
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
267 scoped_ptr<DrawPolygon> polygon_a(
268 CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
269 scoped_ptr<DrawPolygon> polygon_b(
270 CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1));
271 scoped_ptr<DrawPolygon> polygon_c(
272 CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2));
273
274 scoped_ptr<DrawPolygon> polygon_d = polygon_a->CreateCopy();
275 scoped_ptr<DrawPolygon> polygon_e = polygon_b->CreateCopy();
276 scoped_ptr<DrawPolygon> polygon_f = polygon_c->CreateCopy();
277
278 {
279 ScopedPtrDeque<DrawPolygon> polygon_list;
280 polygon_list.push_back(polygon_a.Pass());
281 polygon_list.push_back(polygon_b.Pass());
282 polygon_list.push_back(polygon_c.Pass());
283
284 int compare_ids[] = {0, 1, 2};
285 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
286 BspTreeTest::RunTest(&polygon_list, compare_list);
287 }
288
289 // Now check a different order and ensure we get that back as well
290 {
291 ScopedPtrDeque<DrawPolygon> polygon_list;
292 polygon_list.push_back(polygon_f.Pass());
293 polygon_list.push_back(polygon_d.Pass());
294 polygon_list.push_back(polygon_e.Pass());
295
296 int compare_ids[] = {0, 1, 2};
297 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
298 BspTreeTest::RunTest(&polygon_list, compare_list);
299 }
300 }
301
302 // A bunch of coplanar geometry should end up sharing a single node, and
303 // result in the final piece of geometry splitting into just two pieces on
304 // either side of the shared plane.
TEST(BspTreeTest,CoplanarSplit)305 TEST(BspTreeTest, CoplanarSplit) {
306 std::vector<gfx::Point3F> vertices_a;
307 vertices_a.push_back(gfx::Point3F(-5.0f, -5.0f, 0.0f));
308 vertices_a.push_back(gfx::Point3F(-5.0f, 5.0f, 0.0f));
309 vertices_a.push_back(gfx::Point3F(5.0f, 5.0f, 0.0f));
310 vertices_a.push_back(gfx::Point3F(5.0f, -5.0f, 0.0f));
311 std::vector<gfx::Point3F> vertices_b;
312 vertices_b.push_back(gfx::Point3F(-4.0f, -4.0f, 0.0f));
313 vertices_b.push_back(gfx::Point3F(-4.0f, 4.0f, 0.0f));
314 vertices_b.push_back(gfx::Point3F(4.0f, 4.0f, 0.0f));
315 vertices_b.push_back(gfx::Point3F(4.0f, -4.0f, 0.0f));
316 std::vector<gfx::Point3F> vertices_c;
317 vertices_c.push_back(gfx::Point3F(-3.0f, -3.0f, 0.0f));
318 vertices_c.push_back(gfx::Point3F(-3.0f, 3.0f, 0.0f));
319 vertices_c.push_back(gfx::Point3F(3.0f, 3.0f, 0.0f));
320 vertices_c.push_back(gfx::Point3F(3.0f, -3.0f, 0.0f));
321 std::vector<gfx::Point3F> vertices_d;
322 vertices_d.push_back(gfx::Point3F(0.0f, -15.0f, -15.0f));
323 vertices_d.push_back(gfx::Point3F(0.0f, 15.0f, -15.0f));
324 vertices_d.push_back(gfx::Point3F(0.0f, 15.0f, 15.0f));
325 vertices_d.push_back(gfx::Point3F(0.0f, -15.0f, 15.0f));
326
327 scoped_ptr<DrawPolygon> polygon_a(
328 CREATE_DRAW_POLYGON(vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0));
329 scoped_ptr<DrawPolygon> polygon_b(
330 CREATE_DRAW_POLYGON(vertices_b, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 1));
331 scoped_ptr<DrawPolygon> polygon_c(
332 CREATE_DRAW_POLYGON(vertices_c, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 2));
333 scoped_ptr<DrawPolygon> polygon_d(
334 CREATE_DRAW_POLYGON(vertices_d, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 3));
335
336 ScopedPtrDeque<DrawPolygon> polygon_list;
337 polygon_list.push_back(polygon_a.Pass());
338 polygon_list.push_back(polygon_b.Pass());
339 polygon_list.push_back(polygon_c.Pass());
340 polygon_list.push_back(polygon_d.Pass());
341
342 int compare_ids[] = {3, 0, 1, 2, 3};
343 std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
344 BspTreeTest::RunTest(&polygon_list, compare_list);
345 }
346
347 } // namespace
348 } // namespace cc
349