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_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 | |
OLD | NEW |