OLD | NEW |
| (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_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: | |
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 | |
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. | |
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. | |
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. | |
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. | |
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. | |
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. | |
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. | |
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 | |
OLD | NEW |