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
14namespace cc {
15namespace {
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
31class 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.
92TEST(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.
127TEST(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.
156TEST(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.
185TEST(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.
214TEST(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.
250TEST(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.
305TEST(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