1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4  * License, v. 2.0. If a copy of the MPL was not distributed with this
5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 
7 #include "gtest/gtest.h"
8 
9 #include "BSPTree.h"
10 #include "Polygon.h"
11 #include "PolygonTestUtils.h"
12 
13 #include <deque>
14 #include <list>
15 
16 using namespace mozilla::gfx;
17 using namespace mozilla::layers;
18 typedef mozilla::gfx::Polygon MozPolygon;
19 
20 namespace {
21 
RunTest(std::deque<MozPolygon> aPolygons,std::deque<MozPolygon> aExpected)22 static void RunTest(std::deque<MozPolygon> aPolygons,
23                     std::deque<MozPolygon> aExpected) {
24   std::list<LayerPolygon> layers;
25   for (MozPolygon& polygon : aPolygons) {
26     layers.push_back(LayerPolygon(nullptr, Move(polygon)));
27   }
28 
29   const BSPTree tree(layers);
30   const nsTArray<LayerPolygon> order = tree.GetDrawOrder();
31 
32   EXPECT_EQ(aExpected.size(), order.Length());
33 
34   for (size_t i = 0; i < order.Length(); ++i) {
35     EXPECT_TRUE(aExpected[i] == *order[i].geometry);
36   }
37 }
38 
39 }  // namespace
40 
TEST(BSPTree,SameNode)41 TEST(BSPTree, SameNode) {
42   const std::deque<MozPolygon> polygons{
43       MozPolygon{
44           Point4D(0.0f, 0.0f, 0.0f, 1.0f), Point4D(1.0f, 0.0f, 0.0f, 1.0f),
45           Point4D(1.0f, 1.0f, 0.0f, 1.0f), Point4D(0.0f, 1.0f, 0.0f, 1.0f)},
46       MozPolygon{
47           Point4D(0.0f, 0.0f, 0.0f, 1.0f), Point4D(1.0f, 0.0f, 0.0f, 1.0f),
48           Point4D(1.0f, 1.0f, 0.0f, 1.0f), Point4D(0.0f, 1.0f, 0.0f, 1.0f)}};
49 
50   ::RunTest(polygons, polygons);
51 }
52 
TEST(BSPTree,OneChild)53 TEST(BSPTree, OneChild) {
54   const MozPolygon p1{
55       Point4D(0.0f, 0.0f, 0.0f, 1.0f), Point4D(1.0f, 0.0f, 0.0f, 1.0f),
56       Point4D(1.0f, 1.0f, 0.0f, 1.0f), Point4D(0.0f, 1.0f, 0.0f, 1.0f)};
57 
58   const MozPolygon p2{
59       Point4D(0.0f, 0.0f, 1.0f, 1.0f), Point4D(1.0f, 0.0f, 1.0f, 1.0f),
60       Point4D(1.0f, 1.0f, 1.0f, 1.0f), Point4D(0.0f, 1.0f, 1.0f, 1.0f)};
61 
62   ::RunTest({p1, p2}, {p1, p2});
63   ::RunTest({p2, p1}, {p1, p2});
64 }
65 
TEST(BSPTree,SharedEdge1)66 TEST(BSPTree, SharedEdge1) {
67   MozPolygon p1{
68       Point4D(1.0f, 0.0f, 1.0f, 1.0f), Point4D(0.0f, 0.0f, 1.0f, 1.0f),
69       Point4D(0.0f, 1.0f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 1.0f, 1.0f)};
70 
71   MozPolygon p2{
72       Point4D(1.0f, 0.0f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 1.0f, 1.0f),
73       Point4D(2.0f, 2.0f, 1.0f, 1.0f), Point4D(2.0f, 0.0f, 1.0f, 1.0f)};
74 
75   ::RunTest({p1, p2}, {p1, p2});
76 }
77 
TEST(BSPTree,SharedEdge2)78 TEST(BSPTree, SharedEdge2) {
79   MozPolygon p1{
80       Point4D(1.0f, 0.0f, 1.0f, 1.0f), Point4D(0.0f, 0.0f, 1.0f, 1.0f),
81       Point4D(0.0f, 1.0f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 1.0f, 1.0f)};
82 
83   MozPolygon p2{
84       Point4D(1.0f, 0.0f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 1.0f, 1.0f),
85       Point4D(2.0f, 2.0f, 0.0f, 1.0f), Point4D(2.0f, 0.0f, 0.0f, 1.0f)};
86 
87   ::RunTest({p1, p2}, {p2, p1});
88 }
89 
TEST(BSPTree,SplitSharedEdge)90 TEST(BSPTree, SplitSharedEdge) {
91   MozPolygon p1{
92       Point4D(1.0f, 0.0f, 1.0f, 1.0f), Point4D(0.0f, 0.0f, 1.0f, 1.0f),
93       Point4D(0.0f, 1.0f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 1.0f, 1.0f)};
94 
95   MozPolygon p2{
96       Point4D(1.0f, 0.0f, 2.0f, 1.0f), Point4D(1.0f, 1.0f, 2.0f, 1.0f),
97       Point4D(1.0f, 1.0f, 0.0f, 1.0f), Point4D(1.0f, 0.0f, 0.0f, 1.0f)};
98 
99   const std::deque<MozPolygon> expected{
100       MozPolygon{
101           Point4D(1.0f, 1.0f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 0.0f, 1.0f),
102           Point4D(1.0f, 0.0f, 0.0f, 1.0f), Point4D(1.0f, 0.0f, 1.0f, 1.0f)},
103       MozPolygon{
104           Point4D(1.0f, 0.0f, 1.0f, 1.0f), Point4D(0.0f, 0.0f, 1.0f, 1.0f),
105           Point4D(0.0f, 1.0f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 1.0f, 1.0f)},
106       MozPolygon{
107           Point4D(1.0f, 0.0f, 2.0f, 1.0f), Point4D(1.0f, 1.0f, 2.0f, 1.0f),
108           Point4D(1.0f, 1.0f, 1.0f, 1.0f), Point4D(1.0f, 0.0f, 1.0f, 1.0f)}};
109 
110   ::RunTest({p1, p2}, expected);
111 }
112 
TEST(BSPTree,SplitSimple1)113 TEST(BSPTree, SplitSimple1) {
114   MozPolygon p1{
115       Point4D(0.0f, 0.0f, 1.0f, 1.0f), Point4D(1.0f, 0.0f, 1.0f, 1.0f),
116       Point4D(1.0f, 1.0f, 1.0f, 1.0f), Point4D(0.0f, 1.0f, 1.0f, 1.0f)};
117 
118   MozPolygon p2{
119       Point4D(0.0f, 0.0f, 2.0f, 1.0f), Point4D(1.0f, 0.0f, 2.0f, 1.0f),
120       Point4D(1.0f, 1.0f, 0.0f, 1.0f), Point4D(0.0f, 1.0f, 0.0f, 1.0f)};
121 
122   const std::deque<MozPolygon> expected{
123       MozPolygon{
124           Point4D(0.0f, 1.0f, 0.0f, 1.0f), Point4D(0.0f, 0.5f, 1.0f, 1.0f),
125           Point4D(1.0f, 0.5f, 1.0f, 1.0f), Point4D(1.0f, 1.0f, 0.0f, 1.0f)},
126       p1,
127       MozPolygon{
128           Point4D(0.0f, 0.0f, 2.0f, 1.0f), Point4D(1.0f, 0.0f, 2.0f, 1.0f),
129           Point4D(1.0f, 0.5f, 1.0f, 1.0f), Point4D(0.0f, 0.5f, 1.0f, 1.0f)}};
130 
131   ::RunTest({p1, p2}, expected);
132 }
133 
TEST(BSPTree,SplitSimple2)134 TEST(BSPTree, SplitSimple2) {
135   const std::deque<MozPolygon> polygons{
136       MozPolygon{Point4D(-5.00000f, -5.00000f, 0.00000f, 1.0f),
137                  Point4D(-5.00000f, 5.00000f, 0.00000f, 1.0f),
138                  Point4D(5.00000f, 5.00000f, 0.00000f, 1.0f),
139                  Point4D(5.00000f, -5.00000f, 0.00000f, 1.0f)},
140       MozPolygon{Point4D(0.00000f, -5.00000f, -5.00000f, 1.0f),
141                  Point4D(0.00000f, 5.00000f, -5.00000f, 1.0f),
142                  Point4D(0.00000f, 5.00000f, 5.00000f, 1.0f),
143                  Point4D(0.00000f, -5.00000f, 5.00000f, 1.0f)}};
144 
145   const std::deque<MozPolygon> expected{
146       MozPolygon{Point4D(0.00000f, -5.00000f, 0.00000f, 1.0f),
147                  Point4D(0.00000f, -5.00000f, -5.00000f, 1.0f),
148                  Point4D(0.00000f, 5.00000f, -5.00000f, 1.0f),
149                  Point4D(0.00000f, 5.00000f, 0.00000f, 1.0f)},
150       MozPolygon{Point4D(-5.00000f, -5.00000f, 0.00000f, 1.0f),
151                  Point4D(-5.00000f, 5.00000f, 0.00000f, 1.0f),
152                  Point4D(5.00000f, 5.00000f, 0.00000f, 1.0f),
153                  Point4D(5.00000f, -5.00000f, 0.00000f, 1.0f)},
154       MozPolygon{Point4D(0.00000f, 5.00000f, 0.00000f, 1.0f),
155                  Point4D(0.00000f, 5.00000f, 5.00000f, 1.0f),
156                  Point4D(0.00000f, -5.00000f, 5.00000f, 1.0f),
157                  Point4D(0.00000f, -5.00000f, 0.00000f, 1.0f)}};
158   ::RunTest(polygons, expected);
159 }
160 
TEST(BSPTree,NoSplit1)161 TEST(BSPTree, NoSplit1) {
162   const std::deque<MozPolygon> polygons{
163       MozPolygon{Point4D(0.00000f, 10.00000f, 0.00000f, 1.0f),
164                  Point4D(0.00000f, 0.00000f, 0.00000f, 1.0f),
165                  Point4D(10.00000f, 0.00000f, 0.00000f, 1.0f),
166                  Point4D(10.00000f, 10.00000f, 0.00000f, 1.0f)},
167       MozPolygon{Point4D(0.00000f, 10.00000f, -5.00000f, 1.0f),
168                  Point4D(0.00000f, 0.00000f, -5.00000f, 1.0f),
169                  Point4D(10.00000f, 0.00000f, -5.00000f, 1.0f),
170                  Point4D(10.00000f, 10.00000f, -5.00000f, 1.0f)},
171       MozPolygon{Point4D(0.00000f, 10.00000f, 5.00000f, 1.0f),
172                  Point4D(0.00000f, 0.00000f, 5.00000f, 1.0f),
173                  Point4D(10.00000f, 0.00000f, 5.00000f, 1.0f),
174                  Point4D(10.00000f, 10.00000f, 5.00000f, 1.0f)}};
175 
176   const std::deque<MozPolygon> expected{
177       MozPolygon{Point4D(0.00000f, 10.00000f, -5.00000f, 1.0f),
178                  Point4D(0.00000f, 0.00000f, -5.00000f, 1.0f),
179                  Point4D(10.00000f, 0.00000f, -5.00000f, 1.0f),
180                  Point4D(10.00000f, 10.00000f, -5.00000f, 1.0f)},
181       MozPolygon{Point4D(0.00000f, 10.00000f, 0.00000f, 1.0f),
182                  Point4D(0.00000f, 0.00000f, 0.00000f, 1.0f),
183                  Point4D(10.00000f, 0.00000f, 0.00000f, 1.0f),
184                  Point4D(10.00000f, 10.00000f, 0.00000f, 1.0f)},
185       MozPolygon{Point4D(0.00000f, 10.00000f, 5.00000f, 1.0f),
186                  Point4D(0.00000f, 0.00000f, 5.00000f, 1.0f),
187                  Point4D(10.00000f, 0.00000f, 5.00000f, 1.0f),
188                  Point4D(10.00000f, 10.00000f, 5.00000f, 1.0f)}};
189   ::RunTest(polygons, expected);
190 }
191 
TEST(BSPTree,NoSplit2)192 TEST(BSPTree, NoSplit2) {
193   const std::deque<MozPolygon> polygons{
194       MozPolygon{Point4D(-5.00000f, -5.00000f, 0.00000f, 1.0f),
195                  Point4D(-5.00000f, 5.00000f, 0.00000f, 1.0f),
196                  Point4D(5.00000f, 5.00000f, 0.00000f, 1.0f),
197                  Point4D(5.00000f, -5.00000f, 0.00000f, 1.0f)},
198       MozPolygon{Point4D(0.00000f, 5.00000f, -15.00000f, 1.0f),
199                  Point4D(0.00000f, -5.00000f, -15.00000f, 1.0f),
200                  Point4D(0.00000f, -5.00000f, -10.00000f, 1.0f),
201                  Point4D(0.00000f, 5.00000f, -10.00000f, 1.0f)}};
202 
203   const std::deque<MozPolygon> expected{
204       MozPolygon{Point4D(0.00000f, 5.00000f, -15.00000f, 1.0f),
205                  Point4D(0.00000f, -5.00000f, -15.00000f, 1.0f),
206                  Point4D(0.00000f, -5.00000f, -10.00000f, 1.0f),
207                  Point4D(0.00000f, 5.00000f, -10.00000f, 1.0f)},
208       MozPolygon{Point4D(-5.00000f, -5.00000f, 0.00000f, 1.0f),
209                  Point4D(-5.00000f, 5.00000f, 0.00000f, 1.0f),
210                  Point4D(5.00000f, 5.00000f, 0.00000f, 1.0f),
211                  Point4D(5.00000f, -5.00000f, 0.00000f, 1.0f)}};
212   ::RunTest(polygons, expected);
213 }
214 
TEST(BSPTree,TwoPlaneIntersectRotate0degrees)215 TEST(BSPTree, TwoPlaneIntersectRotate0degrees) {
216   const std::deque<MozPolygon> polygons{
217       MozPolygon{Point4D(-0.00000f, 2.00000f, 2.00000f, 1.0f),
218                  Point4D(-0.00000f, -2.00000f, 2.00000f, 1.0f),
219                  Point4D(0.00010f, -2.00000f, -2.00000f, 1.0f),
220                  Point4D(0.00010f, 2.00000f, -2.00000f, 1.0f)},
221       MozPolygon{Point4D(2.00000f, 0.00000f, 2.00000f, 1.0f),
222                  Point4D(2.00000f, -0.00000f, -2.00000f, 1.0f),
223                  Point4D(-2.00000f, 0.00000f, -2.00000f, 1.0f),
224                  Point4D(-2.00000f, 0.00010f, 2.00000f, 1.0f)}};
225 
226   const std::deque<MozPolygon> expected{
227       MozPolygon{Point4D(2.00000f, 0.00000f, 2.00000f, 1.0f),
228                  Point4D(2.00000f, -0.00000f, -2.00000f, 1.0f),
229                  Point4D(-2.00000f, 0.00000f, -2.00000f, 1.0f),
230                  Point4D(-2.00000f, 0.00010f, 2.00000f, 1.0f)},
231       MozPolygon{Point4D(-0.00000f, 2.00000f, 2.00000f, 1.0f),
232                  Point4D(-0.00000f, -2.00000f, 2.00000f, 1.0f),
233                  Point4D(0.00010f, -2.00000f, -2.00000f, 1.0f),
234                  Point4D(0.00010f, 2.00000f, -2.00000f, 1.0f)}};
235   ::RunTest(polygons, expected);
236 }
237 
TEST(BSPTree,TwoPlaneIntersectRotate20degrees)238 TEST(BSPTree, TwoPlaneIntersectRotate20degrees) {
239   const std::deque<MozPolygon> polygons{
240       MozPolygon{Point4D(-0.00000f, 1.19540f, 2.56350f, 1.0f),
241                  Point4D(-0.00000f, -2.56340f, 1.19540f, 1.0f),
242                  Point4D(0.00010f, -1.19530f, -2.56340f, 1.0f),
243                  Point4D(0.00010f, 2.56350f, -1.19530f, 1.0f)},
244       MozPolygon{Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
245                  Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
246                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f),
247                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f)}};
248 
249   const std::deque<MozPolygon> expected{
250       MozPolygon{Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
251                  Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
252                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f),
253                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f)},
254       MozPolygon{Point4D(-0.00000f, 1.19540f, 2.56350f, 1.0f),
255                  Point4D(-0.00000f, -2.56340f, 1.19540f, 1.0f),
256                  Point4D(0.00010f, -1.19530f, -2.56340f, 1.0f),
257                  Point4D(0.00010f, 2.56350f, -1.19530f, 1.0f)}};
258   ::RunTest(polygons, expected);
259 }
260 
TEST(BSPTree,TwoPlaneIntersectRotate40degrees)261 TEST(BSPTree, TwoPlaneIntersectRotate40degrees) {
262   const std::deque<MozPolygon> polygons{
263       MozPolygon{Point4D(-0.00000f, -0.73200f, 2.73210f, 1.0f),
264                  Point4D(-0.00000f, -2.73200f, -0.73200f, 1.0f),
265                  Point4D(0.00010f, 0.73210f, -2.73200f, 1.0f),
266                  Point4D(0.00010f, 2.73210f, 0.73210f, 1.0f)},
267       MozPolygon{Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
268                  Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
269                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f),
270                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f)}};
271 
272   const std::deque<MozPolygon> expected{
273       MozPolygon{Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
274                  Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
275                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f),
276                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f)},
277       MozPolygon{Point4D(-0.00000f, -0.73200f, 2.73210f, 1.0f),
278                  Point4D(-0.00000f, -2.73200f, -0.73200f, 1.0f),
279                  Point4D(0.00010f, 0.73210f, -2.73200f, 1.0f),
280                  Point4D(0.00010f, 2.73210f, 0.73210f, 1.0f)}};
281   ::RunTest(polygons, expected);
282 }
283 
TEST(BSPTree,TwoPlaneIntersectRotate60degrees)284 TEST(BSPTree, TwoPlaneIntersectRotate60degrees) {
285   const std::deque<MozPolygon> polygons{
286       MozPolygon{Point4D(-0.00000f, -2.73200f, 0.73210f, 1.0f),
287                  Point4D(-0.00000f, -0.73200f, -2.73200f, 1.0f),
288                  Point4D(0.00010f, 2.73210f, -0.73200f, 1.0f),
289                  Point4D(0.00010f, 0.73210f, 2.73210f, 1.0f)},
290       MozPolygon{Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
291                  Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
292                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f),
293                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f)}};
294 
295   const std::deque<MozPolygon> expected{
296       MozPolygon{Point4D(-2.00000f, 1.26793f, 0.73210f, 1.0f),
297                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f),
298                  Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
299                  Point4D(2.00000f, 1.26793f, 0.73210f, 1.0f)},
300       MozPolygon{Point4D(-0.00000f, -2.73200f, 0.73210f, 1.0f),
301                  Point4D(-0.00000f, -0.73200f, -2.73200f, 1.0f),
302                  Point4D(0.00010f, 2.73210f, -0.73200f, 1.0f),
303                  Point4D(0.00010f, 0.73210f, 2.73210f, 1.0f)},
304       MozPolygon{Point4D(2.00000f, 1.26793f, 0.73210f, 1.0f),
305                  Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
306                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f),
307                  Point4D(-2.00000f, 1.26793f, 0.73210f, 1.0f)}};
308   ::RunTest(polygons, expected);
309 }
310 
TEST(BSPTree,TwoPlaneIntersectRotate80degrees)311 TEST(BSPTree, TwoPlaneIntersectRotate80degrees) {
312   const std::deque<MozPolygon> polygons{
313       MozPolygon{Point4D(-0.00000f, -1.19530f, -2.56340f, 1.0f),
314                  Point4D(-0.00000f, 2.56350f, -1.19530f, 1.0f),
315                  Point4D(0.00010f, 1.19540f, 2.56350f, 1.0f),
316                  Point4D(0.00010f, -2.56340f, 1.19540f, 1.0f)},
317       MozPolygon{Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
318                  Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
319                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f),
320                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f)}};
321 
322   const std::deque<MozPolygon> expected{
323       MozPolygon{Point4D(-0.00000f, -1.19530f, -2.56340f, 1.0f),
324                  Point4D(-0.00000f, 2.56350f, -1.19530f, 1.0f),
325                  Point4D(0.00010f, 1.19540f, 2.56350f, 1.0f),
326                  Point4D(0.00010f, -2.56340f, 1.19540f, 1.0f)},
327       MozPolygon{Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
328                  Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
329                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f),
330                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f)}};
331   ::RunTest(polygons, expected);
332 }
333 
TEST(BSPTree,TwoPlaneIntersectRotate100degrees)334 TEST(BSPTree, TwoPlaneIntersectRotate100degrees) {
335   const std::deque<MozPolygon> polygons{
336       MozPolygon{Point4D(-0.00000f, 2.73210f, -0.73200f, 1.0f),
337                  Point4D(-0.00000f, 0.73210f, 2.73210f, 1.0f),
338                  Point4D(0.00010f, -2.73200f, 0.73210f, 1.0f),
339                  Point4D(0.00010f, -0.73200f, -2.73200f, 1.0f)},
340       MozPolygon{Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
341                  Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
342                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f),
343                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f)}};
344 
345   const std::deque<MozPolygon> expected{
346       MozPolygon{Point4D(2.00000f, -1.26783f, -0.73200f, 1.0f),
347                  Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
348                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f),
349                  Point4D(-2.00000f, -1.26783f, -0.73200f, 1.0f)},
350       MozPolygon{Point4D(-0.00000f, 2.73210f, -0.73200f, 1.0f),
351                  Point4D(-0.00000f, 0.73210f, 2.73210f, 1.0f),
352                  Point4D(0.00010f, -2.73200f, 0.73210f, 1.0f),
353                  Point4D(0.00010f, -0.73200f, -2.73200f, 1.0f)},
354       MozPolygon{Point4D(-2.00000f, -1.26783f, -0.73200f, 1.0f),
355                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f),
356                  Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
357                  Point4D(2.00000f, -1.26783f, -0.73200f, 1.0f)}};
358   ::RunTest(polygons, expected);
359 }
360 
TEST(BSPTree,TwoPlaneIntersectRotate120degrees)361 TEST(BSPTree, TwoPlaneIntersectRotate120degrees) {
362   const std::deque<MozPolygon> polygons{
363       MozPolygon{Point4D(-0.00000f, -0.73200f, 2.73210f, 1.0f),
364                  Point4D(-0.00000f, -2.73200f, -0.73200f, 1.0f),
365                  Point4D(0.00010f, 0.73210f, -2.73200f, 1.0f),
366                  Point4D(0.00010f, 2.73210f, 0.73210f, 1.0f)},
367       MozPolygon{Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
368                  Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
369                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f),
370                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f)}};
371 
372   const std::deque<MozPolygon> expected{
373       MozPolygon{Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
374                  Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
375                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f),
376                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f)},
377       MozPolygon{Point4D(-0.00000f, -0.73200f, 2.73210f, 1.0f),
378                  Point4D(-0.00000f, -2.73200f, -0.73200f, 1.0f),
379                  Point4D(0.00010f, 0.73210f, -2.73200f, 1.0f),
380                  Point4D(0.00010f, 2.73210f, 0.73210f, 1.0f)}};
381   ::RunTest(polygons, expected);
382 }
383 
TEST(BSPTree,TwoPlaneIntersectRotate140degrees)384 TEST(BSPTree, TwoPlaneIntersectRotate140degrees) {
385   const std::deque<MozPolygon> polygons{
386       MozPolygon{Point4D(-0.00000f, -1.19530f, -2.56340f, 1.0f),
387                  Point4D(-0.00000f, 2.56350f, -1.19530f, 1.0f),
388                  Point4D(0.00010f, 1.19540f, 2.56350f, 1.0f),
389                  Point4D(0.00010f, -2.56340f, 1.19540f, 1.0f)},
390       MozPolygon{Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
391                  Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
392                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f),
393                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f)}};
394 
395   const std::deque<MozPolygon> expected{
396       MozPolygon{Point4D(-0.00000f, -1.19530f, -2.56340f, 1.0f),
397                  Point4D(-0.00000f, 2.56350f, -1.19530f, 1.0f),
398                  Point4D(0.00010f, 1.19540f, 2.56350f, 1.0f),
399                  Point4D(0.00010f, -2.56340f, 1.19540f, 1.0f)},
400       MozPolygon{Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
401                  Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
402                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f),
403                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f)}};
404   ::RunTest(polygons, expected);
405 }
406 
TEST(BSPTree,TwoPlaneIntersectRotate160degrees)407 TEST(BSPTree, TwoPlaneIntersectRotate160degrees) {
408   const std::deque<MozPolygon> polygons{
409       MozPolygon{Point4D(-0.00000f, 2.00000f, 2.00000f, 1.0f),
410                  Point4D(-0.00000f, -2.00000f, 2.00000f, 1.0f),
411                  Point4D(0.00010f, -2.00000f, -2.00000f, 1.0f),
412                  Point4D(0.00010f, 2.00000f, -2.00000f, 1.0f)},
413       MozPolygon{Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
414                  Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
415                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f),
416                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f)}};
417 
418   const std::deque<MozPolygon> expected{
419       MozPolygon{Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
420                  Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
421                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f),
422                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f)},
423       MozPolygon{Point4D(-0.00000f, 2.00000f, 2.00000f, 1.0f),
424                  Point4D(-0.00000f, -2.00000f, 2.00000f, 1.0f),
425                  Point4D(0.00010f, -2.00000f, -2.00000f, 1.0f),
426                  Point4D(0.00010f, 2.00000f, -2.00000f, 1.0f)}};
427   ::RunTest(polygons, expected);
428 }
429 
TEST(BSPTree,TwoPlaneIntersectRotate180degrees)430 TEST(BSPTree, TwoPlaneIntersectRotate180degrees) {
431   const std::deque<MozPolygon> polygons{
432       MozPolygon{Point4D(-0.00000f, -2.00000f, -2.00000f, 1.0f),
433                  Point4D(-0.00000f, 2.00000f, -2.00000f, 1.0f),
434                  Point4D(0.00010f, 2.00000f, 2.00000f, 1.0f),
435                  Point4D(0.00010f, -2.00000f, 2.00000f, 1.0f)},
436       MozPolygon{Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
437                  Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
438                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f),
439                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f)}};
440 
441   const std::deque<MozPolygon> expected{
442       MozPolygon{Point4D(-0.00000f, -2.00000f, -2.00000f, 1.0f),
443                  Point4D(-0.00000f, 2.00000f, -2.00000f, 1.0f),
444                  Point4D(0.00010f, 2.00000f, 2.00000f, 1.0f),
445                  Point4D(0.00010f, -2.00000f, 2.00000f, 1.0f)},
446       MozPolygon{Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
447                  Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
448                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f),
449                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f)}};
450   ::RunTest(polygons, expected);
451 }
452 
TEST(BSPTree,TwoPlaneIntersectRotate200degrees)453 TEST(BSPTree, TwoPlaneIntersectRotate200degrees) {
454   const std::deque<MozPolygon> polygons{
455       MozPolygon{Point4D(-0.00000f, 1.19540f, 2.56350f, 1.0f),
456                  Point4D(-0.00000f, -2.56340f, 1.19540f, 1.0f),
457                  Point4D(0.00010f, -1.19530f, -2.56340f, 1.0f),
458                  Point4D(0.00010f, 2.56350f, -1.19530f, 1.0f)},
459       MozPolygon{Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
460                  Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
461                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f),
462                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f)}};
463 
464   const std::deque<MozPolygon> expected{
465       MozPolygon{Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
466                  Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
467                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f),
468                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f)},
469       MozPolygon{Point4D(-0.00000f, 1.19540f, 2.56350f, 1.0f),
470                  Point4D(-0.00000f, -2.56340f, 1.19540f, 1.0f),
471                  Point4D(0.00010f, -1.19530f, -2.56340f, 1.0f),
472                  Point4D(0.00010f, 2.56350f, -1.19530f, 1.0f)}};
473   ::RunTest(polygons, expected);
474 }
475 
TEST(BSPTree,TwoPlaneIntersectRotate220degrees)476 TEST(BSPTree, TwoPlaneIntersectRotate220degrees) {
477   const std::deque<MozPolygon> polygons{
478       MozPolygon{Point4D(-0.00000f, 0.73210f, -2.73200f, 1.0f),
479                  Point4D(-0.00000f, 2.73210f, 0.73210f, 1.0f),
480                  Point4D(0.00010f, -0.73200f, 2.73210f, 1.0f),
481                  Point4D(0.00010f, -2.73200f, -0.73200f, 1.0f)},
482       MozPolygon{Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
483                  Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
484                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f),
485                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f)}};
486 
487   const std::deque<MozPolygon> expected{
488       MozPolygon{Point4D(-0.00000f, 0.73210f, -2.73200f, 1.0f),
489                  Point4D(-0.00000f, 2.73210f, 0.73210f, 1.0f),
490                  Point4D(0.00010f, -0.73200f, 2.73210f, 1.0f),
491                  Point4D(0.00010f, -2.73200f, -0.73200f, 1.0f)},
492       MozPolygon{Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
493                  Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
494                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f),
495                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f)}};
496   ::RunTest(polygons, expected);
497 }
498 
TEST(BSPTree,TwoPlaneIntersectRotate240degrees)499 TEST(BSPTree, TwoPlaneIntersectRotate240degrees) {
500   const std::deque<MozPolygon> polygons{
501       MozPolygon{Point4D(-0.00000f, -2.73200f, 0.73210f, 1.0f),
502                  Point4D(-0.00000f, -0.73200f, -2.73200f, 1.0f),
503                  Point4D(0.00010f, 2.73210f, -0.73200f, 1.0f),
504                  Point4D(0.00010f, 0.73210f, 2.73210f, 1.0f)},
505       MozPolygon{Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
506                  Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
507                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f),
508                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f)}};
509 
510   const std::deque<MozPolygon> expected{
511       MozPolygon{Point4D(-2.00000f, 1.26793f, 0.73210f, 1.0f),
512                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f),
513                  Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
514                  Point4D(2.00000f, 1.26793f, 0.73210f, 1.0f)},
515       MozPolygon{Point4D(-0.00000f, -2.73200f, 0.73210f, 1.0f),
516                  Point4D(-0.00000f, -0.73200f, -2.73200f, 1.0f),
517                  Point4D(0.00010f, 2.73210f, -0.73200f, 1.0f),
518                  Point4D(0.00010f, 0.73210f, 2.73210f, 1.0f)},
519       MozPolygon{Point4D(2.00000f, 1.26793f, 0.73210f, 1.0f),
520                  Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
521                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f),
522                  Point4D(-2.00000f, 1.26793f, 0.73210f, 1.0f)}};
523   ::RunTest(polygons, expected);
524 }
525 
TEST(BSPTree,TwoPlaneIntersectRotate260degrees)526 TEST(BSPTree, TwoPlaneIntersectRotate260degrees) {
527   const std::deque<MozPolygon> polygons{
528       MozPolygon{Point4D(-0.00000f, 1.19540f, 2.56350f, 1.0f),
529                  Point4D(-0.00000f, -2.56340f, 1.19540f, 1.0f),
530                  Point4D(0.00010f, -1.19530f, -2.56340f, 1.0f),
531                  Point4D(0.00010f, 2.56350f, -1.19530f, 1.0f)},
532       MozPolygon{Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
533                  Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
534                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f),
535                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f)}};
536 
537   const std::deque<MozPolygon> expected{
538       MozPolygon{Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
539                  Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
540                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f),
541                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f)},
542       MozPolygon{Point4D(-0.00000f, 1.19540f, 2.56350f, 1.0f),
543                  Point4D(-0.00000f, -2.56340f, 1.19540f, 1.0f),
544                  Point4D(0.00010f, -1.19530f, -2.56340f, 1.0f),
545                  Point4D(0.00010f, 2.56350f, -1.19530f, 1.0f)}};
546   ::RunTest(polygons, expected);
547 }
548 
TEST(BSPTree,TwoPlaneIntersectRotate280degrees)549 TEST(BSPTree, TwoPlaneIntersectRotate280degrees) {
550   const std::deque<MozPolygon> polygons{
551       MozPolygon{Point4D(-0.00000f, 2.73210f, -0.73200f, 1.0f),
552                  Point4D(-0.00000f, 0.73210f, 2.73210f, 1.0f),
553                  Point4D(0.00010f, -2.73200f, 0.73210f, 1.0f),
554                  Point4D(0.00010f, -0.73200f, -2.73200f, 1.0f)},
555       MozPolygon{Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
556                  Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
557                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f),
558                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f)}};
559 
560   const std::deque<MozPolygon> expected{
561       MozPolygon{Point4D(2.00000f, -1.26783f, -0.73200f, 1.0f),
562                  Point4D(2.00000f, -1.73200f, -1.00000f, 1.0f),
563                  Point4D(-2.00000f, -1.73200f, -1.00000f, 1.0f),
564                  Point4D(-2.00000f, -1.26783f, -0.73200f, 1.0f)},
565       MozPolygon{Point4D(-0.00000f, 2.73210f, -0.73200f, 1.0f),
566                  Point4D(-0.00000f, 0.73210f, 2.73210f, 1.0f),
567                  Point4D(0.00010f, -2.73200f, 0.73210f, 1.0f),
568                  Point4D(0.00010f, -0.73200f, -2.73200f, 1.0f)},
569       MozPolygon{Point4D(-2.00000f, -1.26783f, -0.73200f, 1.0f),
570                  Point4D(-2.00000f, 1.73210f, 1.00010f, 1.0f),
571                  Point4D(2.00000f, 1.73210f, 1.00010f, 1.0f),
572                  Point4D(2.00000f, -1.26783f, -0.73200f, 1.0f)}};
573   ::RunTest(polygons, expected);
574 }
575 
TEST(BSPTree,TwoPlaneIntersectRotate300degrees)576 TEST(BSPTree, TwoPlaneIntersectRotate300degrees) {
577   const std::deque<MozPolygon> polygons{
578       MozPolygon{Point4D(-0.00000f, 0.73210f, -2.73200f, 1.0f),
579                  Point4D(-0.00000f, 2.73210f, 0.73210f, 1.0f),
580                  Point4D(0.00010f, -0.73200f, 2.73210f, 1.0f),
581                  Point4D(0.00010f, -2.73200f, -0.73200f, 1.0f)},
582       MozPolygon{Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
583                  Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
584                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f),
585                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f)}};
586 
587   const std::deque<MozPolygon> expected{
588       MozPolygon{Point4D(-0.00000f, 0.73210f, -2.73200f, 1.0f),
589                  Point4D(-0.00000f, 2.73210f, 0.73210f, 1.0f),
590                  Point4D(0.00010f, -0.73200f, 2.73210f, 1.0f),
591                  Point4D(0.00010f, -2.73200f, -0.73200f, 1.0f)},
592       MozPolygon{Point4D(2.00000f, 1.73210f, -0.99990f, 1.0f),
593                  Point4D(2.00000f, -1.73200f, 1.00000f, 1.0f),
594                  Point4D(-2.00000f, -1.73200f, 1.00000f, 1.0f),
595                  Point4D(-2.00000f, 1.73210f, -0.99990f, 1.0f)}};
596   ::RunTest(polygons, expected);
597 }
598 
TEST(BSPTree,TwoPlaneIntersectRotate320degrees)599 TEST(BSPTree, TwoPlaneIntersectRotate320degrees) {
600   const std::deque<MozPolygon> polygons{
601       MozPolygon{Point4D(-0.00000f, -1.19530f, -2.56340f, 1.0f),
602                  Point4D(-0.00000f, 2.56350f, -1.19530f, 1.0f),
603                  Point4D(0.00010f, 1.19540f, 2.56350f, 1.0f),
604                  Point4D(0.00010f, -2.56340f, 1.19540f, 1.0f)},
605       MozPolygon{Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
606                  Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
607                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f),
608                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f)}};
609 
610   const std::deque<MozPolygon> expected{
611       MozPolygon{Point4D(-0.00000f, -1.19530f, -2.56340f, 1.0f),
612                  Point4D(-0.00000f, 2.56350f, -1.19530f, 1.0f),
613                  Point4D(0.00010f, 1.19540f, 2.56350f, 1.0f),
614                  Point4D(0.00010f, -2.56340f, 1.19540f, 1.0f)},
615       MozPolygon{Point4D(2.00000f, 0.68410f, -1.87930f, 1.0f),
616                  Point4D(2.00000f, -0.68400f, 1.87940f, 1.0f),
617                  Point4D(-2.00000f, -0.68400f, 1.87940f, 1.0f),
618                  Point4D(-2.00000f, 0.68410f, -1.87930f, 1.0f)}};
619   ::RunTest(polygons, expected);
620 }
621 
TEST(BSPTree,TwoPlaneIntersectRotate340degrees)622 TEST(BSPTree, TwoPlaneIntersectRotate340degrees) {
623   const std::deque<MozPolygon> polygons{
624       MozPolygon{Point4D(-0.00000f, -2.00000f, -2.00000f, 1.0f),
625                  Point4D(-0.00000f, 2.00000f, -2.00000f, 1.0f),
626                  Point4D(0.00010f, 2.00000f, 2.00000f, 1.0f),
627                  Point4D(0.00010f, -2.00000f, 2.00000f, 1.0f)},
628       MozPolygon{Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
629                  Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
630                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f),
631                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f)}};
632 
633   const std::deque<MozPolygon> expected{
634       MozPolygon{Point4D(-0.00000f, -2.00000f, -2.00000f, 1.0f),
635                  Point4D(-0.00000f, 2.00000f, -2.00000f, 1.0f),
636                  Point4D(0.00010f, 2.00000f, 2.00000f, 1.0f),
637                  Point4D(0.00010f, -2.00000f, 2.00000f, 1.0f)},
638       MozPolygon{Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
639                  Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
640                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f),
641                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f)}};
642   ::RunTest(polygons, expected);
643 }
644 
TEST(BSPTree,TwoPlaneIntersectRotate360degrees)645 TEST(BSPTree, TwoPlaneIntersectRotate360degrees) {
646   const std::deque<MozPolygon> polygons{
647       MozPolygon{Point4D(-0.00000f, -2.00000f, -2.00000f, 1.0f),
648                  Point4D(-0.00000f, 2.00000f, -2.00000f, 1.0f),
649                  Point4D(0.00010f, 2.00000f, 2.00000f, 1.0f),
650                  Point4D(0.00010f, -2.00000f, 2.00000f, 1.0f)},
651       MozPolygon{Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
652                  Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
653                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f),
654                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f)}};
655 
656   const std::deque<MozPolygon> expected{
657       MozPolygon{Point4D(-0.00000f, -2.00000f, -2.00000f, 1.0f),
658                  Point4D(-0.00000f, 2.00000f, -2.00000f, 1.0f),
659                  Point4D(0.00010f, 2.00000f, 2.00000f, 1.0f),
660                  Point4D(0.00010f, -2.00000f, 2.00000f, 1.0f)},
661       MozPolygon{Point4D(2.00000f, 0.00010f, -2.00000f, 1.0f),
662                  Point4D(2.00000f, -0.00000f, 2.00000f, 1.0f),
663                  Point4D(-2.00000f, -0.00000f, 2.00000f, 1.0f),
664                  Point4D(-2.00000f, 0.00010f, -2.00000f, 1.0f)}};
665   ::RunTest(polygons, expected);
666 }
667