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