TestBSPTree.cpp (32413B)
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 22 static void RunTest(std::deque<MozPolygon> aPolygons, 23 std::deque<MozPolygon> aExpected) { 24 std::list<TestPolygon> layers; 25 for (MozPolygon& polygon : aPolygons) { 26 layers.push_back(TestPolygon(nullptr, std::move(polygon))); 27 } 28 29 const BSPTree tree(layers); 30 const nsTArray<TestPolygon> 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 }