Analysis Software
Documentation for sPHENIX simulation software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
BoundingBoxTest.cpp
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file BoundingBoxTest.cpp
1 // This file is part of the Acts project.
2 //
3 // Copyright (C) 2018-2019 CERN for the benefit of the Acts project
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public
6 // License, v. 2.0. If a copy of the MPL was not distributed with this
7 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 
9 #include <boost/test/unit_test.hpp>
10 
11 #include "Acts/Definitions/Algebra.hpp"
12 #include "Acts/Geometry/AbstractVolume.hpp"
13 #include "Acts/Geometry/GenericCuboidVolumeBounds.hpp"
14 #include "Acts/Tests/CommonHelpers/FloatComparisons.hpp"
15 #include "Acts/Utilities/BoundingBox.hpp"
16 #include "Acts/Utilities/Frustum.hpp"
17 #include "Acts/Utilities/Ray.hpp"
18 #include "Acts/Visualization/IVisualization3D.hpp"
19 #include "Acts/Visualization/PlyVisualization3D.hpp"
20 
21 #include <algorithm>
22 #include <array>
23 #include <cmath>
24 #include <cstdio>
25 #include <filesystem>
26 #include <fstream>
27 #include <iostream>
28 #include <memory>
29 #include <set>
30 #include <sstream>
31 #include <string>
32 #include <utility>
33 #include <vector>
34 
35 namespace Acts {
36 namespace Test {
37 
38 struct Object {};
39 
40 using BoundingBoxScalar = ActsScalar;
41 
42 using ObjectBBox = Acts::AxisAlignedBoundingBox<Object, BoundingBoxScalar, 3>;
43 
44 using Vector2F = Eigen::Matrix<BoundingBoxScalar, 2, 1>;
45 using Vector3F = Eigen::Matrix<BoundingBoxScalar, 3, 1>;
46 using AngleAxis3F = Eigen::AngleAxis<BoundingBoxScalar>;
47 
48 std::filesystem::path tmp_path = []() {
49  auto p = std::filesystem::temp_directory_path() / "acts_unit_tests";
50  std::filesystem::create_directory(p);
51  std::cout << "Writing test output to: " << p << std::endl;
52  return p;
53 }();
54 
55 std::ofstream tmp(const std::string& path) {
56  return std::ofstream{(tmp_path / path).string()};
57 }
58 
59 BOOST_AUTO_TEST_CASE(box_construction) {
60  BOOST_TEST_CONTEXT("2D") {
61  Object o;
62  using Box = Acts::AxisAlignedBoundingBox<Object, BoundingBoxScalar, 2>;
63  Box bb(&o, {-1, -1}, {2, 2});
64 
65  typename Box::transform_type rot;
66  rot = Eigen::Rotation2D<BoundingBoxScalar>(M_PI / 7.);
67  Box bb_rot = bb.transformed(rot);
68 
69  CHECK_CLOSE_ABS(bb_rot.min(), Vector2F(-1.76874, -1.33485), 1e-4);
70  CHECK_CLOSE_ABS(bb_rot.max(), Vector2F(2.23582, 2.66971), 1e-4);
71  }
72 
73  BOOST_TEST_CONTEXT("3D") {
74  Object o;
75  using Box = Acts::AxisAlignedBoundingBox<Object, BoundingBoxScalar, 3>;
76  Box bb(&o, {-1, -1, -1}, {2, 2, 2});
77 
78  typename Box::transform_type rot;
79  rot = AngleAxis3F(M_PI / 3., Vector3F::UnitZ());
80  Box bb_rot = bb.transformed(rot);
81 
82  CHECK_CLOSE_ABS(bb_rot.min(), Vector3F(-2.23205, -1.36603, -1), 1e-4);
83  CHECK_CLOSE_ABS(bb_rot.max(), Vector3F(1.86603, 2.73205, 2), 1e-4);
84 
85  rot *= AngleAxis3F(M_PI / 5., Vector3F(1, 1, 0).normalized());
86  Box bb_rot2 = bb.transformed(rot);
87 
88  CHECK_CLOSE_ABS(bb_rot2.min(), Vector3F(-2.40848, -1.51816, -2.0559), 1e-4);
89  CHECK_CLOSE_ABS(bb_rot2.max(), Vector3F(2.61021, 3.03631, 2.86491), 1e-4);
90  }
91 }
92 
93 BOOST_AUTO_TEST_CASE(intersect_points) {
94  using VertexType = ObjectBBox::VertexType;
95 
96  Object o;
97  ObjectBBox bb(&o, {0, 0, 0}, {1, 1, 1});
98  VertexType p;
99 
100  p = {0.5, 0.5, 0.5};
101  BOOST_CHECK(bb.intersect(p));
102  p = {0.25, 0.25, 0.25};
103  BOOST_CHECK(bb.intersect(p));
104  p = {0.75, 0.75, 0.75};
105  BOOST_CHECK(bb.intersect(p));
106 
107  // lower bound is inclusive
108  p = {0, 0, 0};
109  BOOST_CHECK(bb.intersect(p));
110  // upper bound is exclusive
111  p = {1.0, 1.0, 1.0};
112  BOOST_CHECK(!bb.intersect(p));
113 
114  // some outsides
115  p = {2, 0, 0};
116  BOOST_CHECK(!bb.intersect(p));
117  p = {0, 2, 0};
118  BOOST_CHECK(!bb.intersect(p));
119  p = {0, 0, 2};
120  BOOST_CHECK(!bb.intersect(p));
121  p = {2, 2, 0};
122  BOOST_CHECK(!bb.intersect(p));
123  p = {2, 0, 2};
124  BOOST_CHECK(!bb.intersect(p));
125  p = {2, 2, 2};
126  BOOST_CHECK(!bb.intersect(p));
127 
128  p = {-1, 0, 0};
129  BOOST_CHECK(!bb.intersect(p));
130  p = {0, -1, 0};
131  BOOST_CHECK(!bb.intersect(p));
132  p = {0, 0, -1};
133  BOOST_CHECK(!bb.intersect(p));
134  p = {-1, -1, 0};
135  BOOST_CHECK(!bb.intersect(p));
136  p = {-1, 0, -1};
137  BOOST_CHECK(!bb.intersect(p));
138  p = {-1, -1, -1};
139  BOOST_CHECK(!bb.intersect(p));
140 }
141 
142 BOOST_AUTO_TEST_CASE(intersect_rays) {
143  /* temporarily removed, fails with double precision
144  BOOST_TEST_CONTEXT("2D") {
145  using Box = AxisAlignedBoundingBox<Object, BoundingBoxScalar, 2>;
146 
147  Object o;
148  Box bb(&o, {-1, -1}, {1, 1});
149 
150  // ray in positive x direction
151 
152  Ray<BoundingBoxScalar, 2> ray({-2, 0}, {1, 0});
153  BOOST_CHECK(bb.intersect(ray));
154 
155  ray = {{-2, 2}, {1, 0}};
156  BOOST_CHECK(!bb.intersect(ray));
157 
158  ray = {{-2, -2}, {1, 0}};
159  BOOST_CHECK(!bb.intersect(ray));
160 
161  // upper bound is exclusive
162  ray = {{-2, 1}, {1, 0}};
163  BOOST_CHECK(!bb.intersect(ray));
164 
165  // lower bound is inclusive
166  ray = {{-2, -1}, {1, 0}};
167  BOOST_CHECK(bb.intersect(ray));
168 
169  // ray faces away from box
170  ray = {{2, 0}, {1, 0}};
171  BOOST_CHECK(!bb.intersect(ray));
172 
173  // ray in negative x direction
174 
175  ray = {{2, 0}, {-1, 0}};
176  BOOST_CHECK(bb.intersect(ray));
177 
178  ray = {{2, 2}, {-1, 0}};
179  BOOST_CHECK(!bb.intersect(ray));
180 
181  ray = {{2, -2}, {-1, 0}};
182  BOOST_CHECK(!bb.intersect(ray));
183 
184  // upper bound is exclusive
185  ray = {{2, 1}, {-1, 0}};
186  BOOST_CHECK(!bb.intersect(ray));
187 
188  // lower bound is inclusive
189  ray = {{2, -1}, {-1, 0}};
190  BOOST_CHECK(bb.intersect(ray));
191 
192  // ray in positive y direction
193 
194  ray = {{0, -2}, {0, 1}};
195  BOOST_CHECK(bb.intersect(ray));
196 
197  ray = {{2, -2}, {0, 1}};
198  BOOST_CHECK(!bb.intersect(ray));
199 
200  ray = {{-2, -2}, {0, 1}};
201  BOOST_CHECK(!bb.intersect(ray));
202 
203  // upper bound is exclusive
204  ray = {{1, -2}, {0, 1}};
205  BOOST_CHECK(!bb.intersect(ray));
206 
207  // lower bound is not inclusive,
208  // due to Eigen's NaN handling.
209  ray = {{-1, -2}, {0, 1}};
210  BOOST_CHECK(!bb.intersect(ray));
211 
212  // other direction
213  ray = {{0, -2}, {0, -1}};
214  BOOST_CHECK(!bb.intersect(ray));
215 
216  // ray in positive y direction
217 
218  ray = {{0, 2}, {0, -1}};
219  BOOST_CHECK(bb.intersect(ray));
220 
221  ray = {{2, 2}, {0, -1}};
222  BOOST_CHECK(!bb.intersect(ray));
223 
224  ray = {{-2, 2}, {0, -1}};
225  BOOST_CHECK(!bb.intersect(ray));
226 
227  // upper bound is exclusive
228  ray = {{1, 2}, {0, -1}};
229  BOOST_CHECK(!bb.intersect(ray));
230 
231  // lower bound is not inclusive,
232  // due to Eigen's NaN handling.
233  ray = {{-1, 2}, {0, -1}};
234  BOOST_CHECK(!bb.intersect(ray));
235 
236  // other direction
237  ray = {{0, 2}, {0, 1}};
238  BOOST_CHECK(!bb.intersect(ray));
239 
240  // some off axis rays
241 
242  ray = {{-2, 0}, {0.5, 0.25}};
243  BOOST_CHECK(bb.intersect(ray));
244 
245  ray = {{-2, 0}, {0.5, 0.4}};
246  BOOST_CHECK(bb.intersect(ray));
247 
248  ray = {{-2, 0}, {0.5, 0.6}};
249  BOOST_CHECK(!bb.intersect(ray));
250 
251  ray = {{-2, 0}, {0.5, 0.1}};
252  BOOST_CHECK(bb.intersect(ray));
253 
254  ray = {{-2, 0}, {0.5, -0.4}};
255  BOOST_CHECK(bb.intersect(ray));
256 
257  ray = {{-2, 0}, {0.5, -0.6}};
258  BOOST_CHECK(!bb.intersect(ray));
259 
260  ray = {{-2, 0}, {0.1, 0.5}};
261  BOOST_CHECK(!bb.intersect(ray));
262 
263  // starting point inside
264  ray = {{
265  0,
266  0,
267  },
268  {-1, 0}};
269  BOOST_CHECK(bb.intersect(ray));
270  ray = {{
271  0,
272  0,
273  },
274  {1, 0}};
275  BOOST_CHECK(bb.intersect(ray));
276  ray = {{
277  0,
278  0,
279  },
280  {0, -1}};
281  BOOST_CHECK(bb.intersect(ray));
282  ray = {{
283  0,
284  0,
285  },
286  {0, 1}};
287  BOOST_CHECK(bb.intersect(ray));
288  } */
289 
290  BOOST_TEST_CONTEXT("3D visualize") {
291  Object o;
292 
293  // let's make sure it also works in 3d
294  ObjectBBox bb3(&o, {-1, -1, -1}, {1, 1, 1});
295  Ray<BoundingBoxScalar, 3> ray3({0, 0, -2}, {0, 0, 1});
296  BOOST_CHECK(bb3.intersect(ray3));
297 
298  PlyVisualization3D<BoundingBoxScalar> ply;
299 
300  ray3.draw(ply);
301  auto os = tmp("ray3d.ply");
302  os << ply << std::flush;
303  os.close();
304  }
305 
306  BOOST_TEST_CONTEXT("3D") {
307  using VertexType3 = ObjectBBox::VertexType;
308  Object o;
309 
310  // let's make sure it also works in 3d
311  ObjectBBox bb3(&o, {-1, -1, -1}, {1, 1, 1});
312  Ray<BoundingBoxScalar, 3> ray3({0, 0, -2}, {0, 0, 1});
313  BOOST_CHECK(bb3.intersect(ray3));
314 
315  // facing away from box
316  ray3 = {{0, 0, -2}, {0, 0, -1}};
317  BOOST_CHECK(!bb3.intersect(ray3));
318 
319  ray3 = {{0, 2, -2}, {0, 0, 1}};
320  BOOST_CHECK(!bb3.intersect(ray3));
321 
322  ray3 = {{0, -2, -2}, {0, 0, 1}};
323  BOOST_CHECK(!bb3.intersect(ray3));
324 
325  // right on slab - temporarily removed, fails with double precision
326  // ray3 = {{0, 1, -2}, {0, 0, 1}};
327  // BOOST_CHECK(!bb3.intersect(ray3));
328 
329  // right on slab - temporarily removed, fails with double precision
330  // ray3 = {{0, -1, -2}, {0, 0, 1}};
331  // BOOST_CHECK(bb3.intersect(ray3));
332 
333  // right on slab
334  ray3 = {{-1, 0, -2}, {0, 0, 1}};
335  BOOST_CHECK(!bb3.intersect(ray3));
336 
337  // right on slab - temporarily removed, fails with double precision
338  // ray3 = {{1, 0, -2}, {0, 0, 1}};
339  // BOOST_CHECK(!bb3.intersect(ray3));
340 
341  ray3 = {{-0.95, 0, -2}, {0, 0, 1}};
342  BOOST_CHECK(bb3.intersect(ray3));
343 
344  // some off-axis rays
345  ObjectBBox::VertexType p(0, 0, -2);
346 
347  ray3 = {p, VertexType3(1, 1, 1) - p};
348  BOOST_CHECK(bb3.intersect(ray3));
349 
350  ray3 = {p, VertexType3(-1, 1, 1) - p};
351  BOOST_CHECK(bb3.intersect(ray3));
352 
353  ray3 = {p, VertexType3(-1, -1, 1) - p};
354  BOOST_CHECK(bb3.intersect(ray3));
355 
356  ray3 = {p, VertexType3(1, -1, 1) - p};
357  BOOST_CHECK(bb3.intersect(ray3));
358 
359  ray3 = {p, VertexType3(1.1, 0, -1) - p};
360  BOOST_CHECK(!bb3.intersect(ray3));
361 
362  ray3 = {p, VertexType3(-1.1, 0, -1) - p};
363  BOOST_CHECK(!bb3.intersect(ray3));
364 
365  ray3 = {p, VertexType3(0, 1.1, -1) - p};
366  BOOST_CHECK(!bb3.intersect(ray3));
367 
368  ray3 = {p, VertexType3(0, -1.1, -1) - p};
369  BOOST_CHECK(!bb3.intersect(ray3));
370 
371  ray3 = {p, VertexType3(0.9, 0, -1) - p};
372  BOOST_CHECK(bb3.intersect(ray3));
373 
374  ray3 = {p, VertexType3(-0.9, 0, -1) - p};
375  BOOST_CHECK(bb3.intersect(ray3));
376 
377  ray3 = {p, VertexType3(0, 0.9, -1) - p};
378  BOOST_CHECK(bb3.intersect(ray3));
379 
380  ray3 = {p, VertexType3(0, -0.9, -1) - p};
381  BOOST_CHECK(bb3.intersect(ray3));
382 
383  ray3 = {{0, 0, 0}, {1, 0, 0}};
384  BOOST_CHECK(bb3.intersect(ray3));
385  ray3 = {{0, 0, 0}, {0, 1, 0}};
386  BOOST_CHECK(bb3.intersect(ray3));
387  ray3 = {{0, 0, 0}, {0, 0, 1}};
388  BOOST_CHECK(bb3.intersect(ray3));
389 
390  ray3 = {{0, 0, 0}, {-1, 0, 0}};
391  BOOST_CHECK(bb3.intersect(ray3));
392  ray3 = {{0, 0, 0}, {0, -1, 0}};
393  BOOST_CHECK(bb3.intersect(ray3));
394  ray3 = {{0, 0, 0}, {0, 0, -1}};
395  BOOST_CHECK(bb3.intersect(ray3));
396  }
397 } // namespace Test
398 
399 BOOST_AUTO_TEST_CASE(ray_obb_intersect) {
400  using Ray = Ray<double, 3>;
401 
402  std::array<Vector3, 8> vertices;
403  vertices = {{{0, 0, 0},
404  {2, 0, 0.4},
405  {2, 1, 0.4},
406  {0, 1, 0},
407  {0, 0, 1},
408  {1.8, 0, 1},
409  {1.8, 1, 1},
410  {0, 1, 1}}};
411  auto cubo = std::make_shared<GenericCuboidVolumeBounds>(vertices);
412  auto trf = Transform3(Translation3(Vector3(0, 8, -5)) *
413  AngleAxis3(M_PI / 3., Vector3(1, -3, 9).normalized()));
414 
415  AbstractVolume vol(trf, cubo);
416 
417  PlyVisualization3D<double> ply;
418 
419  Transform3 trl = Transform3::Identity();
420  trl.translation() = trf.translation();
421 
422  cubo->draw(ply);
423 
424  auto obb = vol.orientedBoundingBox();
425  obb.draw(ply, {200, 0, 0});
426 
427  ply.clear();
428 
429  Vector3 origin(10, -20, 6);
430  Vector3 centroid(0., 0., 0.);
431 
432  for (const auto& vtx_ : vertices) {
433  Vector3 vtx = trf * vtx_;
434  centroid += vtx;
435  }
436 
437  // approximately the centroid
438  centroid *= 0.125;
439 
440  // shoot rays to the corner points of the cuboid
441  for (const auto& vtx_ : vertices) {
442  Vector3 vtx = trf * vtx_;
443 
444  // this ray goes straight to the actual vertex, this should
445  // definitely intersect the OBB
446  Ray ray(origin, (vtx - origin).normalized());
447  ray = ray.transformed(trf.inverse());
448  BOOST_CHECK(obb.intersect(ray));
449  ray.draw(ply, (vtx - origin).norm());
450 
451  // now shift the target point away from the centroid
452  // this should definitely NOT intersect the OBB
453  vtx += (vtx - centroid);
454  ray = Ray(origin, (vtx - origin).normalized());
455  ray = ray.transformed(trf.inverse());
456  BOOST_CHECK(!obb.intersect(ray));
457  ray.draw(ply, (vtx - origin).norm());
458  }
459 }
460 
461 BOOST_AUTO_TEST_CASE(frustum_intersect) {
462  BOOST_TEST_CONTEXT("2D") {
463  auto make_svg = [](const std::string& fname, size_t w, size_t h) {
464  auto os = tmp(fname);
465  os << "<?xml version=\"1.0\" standalone=\"no\"?>\n";
466  os << "<svg width=\"" << w << "\" height=\"" << h
467  << "\" version=\"1.1\" xmlns=\"http://www.w3.org/2000/svg\">\n";
468  return os;
469  };
470 
471  using Frustum2 = Frustum<BoundingBoxScalar, 2, 2>;
472 
473  std::ofstream os;
474 
475  size_t w = 1000;
476  size_t n = 10;
477 
478  // BEGIN VISUAL PARAMETER TEST
479 
480  // BoundingBoxScalar min = -20, max = 20;
481  // os = make_svg("frust2d.svg", w, w);
482 
483  // BoundingBoxScalar step = (max - min) / BoundingBoxScalar(n);
484  // for (size_t i = 0; i <= n; i++) {
485  // for (size_t j = 0; j <= n; j++) {
486  // ActsVector<BoundingBoxScalar,2> dir = {1, 0};
487  // ActsVector<BoundingBoxScalar,2> origin = {min + step * i, min + step *
488  // j}; origin.x() *= 1.10; // visual Eigen::Rotation2D<BoundingBoxScalar>
489  // rot(2 * M_PI / BoundingBoxScalar(n) * i); BoundingBoxScalar angle = 0.5 *
490  // M_PI / n * j; Frustum2 fr(origin, rot * dir, angle);
491  // fr.svg(os, w, w, 2);
492  //}
493  //}
494 
495  // os << "</svg>";
496  // os.close();
497 
498  // END VISUAL PARAMETER TEST
499 
500  w = 1000;
501  BoundingBoxScalar unit = 20;
502 
503  using Box = AxisAlignedBoundingBox<Object, BoundingBoxScalar, 2>;
504  Object o;
505  Box::Size size(Eigen::Matrix<BoundingBoxScalar, 2, 1>(2, 2));
506 
507  n = 10;
508  BoundingBoxScalar minx = -20;
509  BoundingBoxScalar miny = -20;
510  BoundingBoxScalar maxx = 20;
511  BoundingBoxScalar maxy = 20;
512  BoundingBoxScalar stepx = (maxx - minx) / BoundingBoxScalar(n);
513  BoundingBoxScalar stepy = (maxy - miny) / BoundingBoxScalar(n);
514 
515  std::set<size_t> act_idxs;
516 
517  // clang-format off
518  std::vector<std::pair<Frustum2, std::set<size_t>>> fr_exp;
519  fr_exp = {
520  {Frustum2({0, 0}, {1, 0}, M_PI / 2.),
521  {60, 70, 71, 72, 80, 81, 82, 83, 84, 90, 91, 92,
522  93, 94, 95, 96, 100, 101, 102, 103, 104, 105, 106, 107,
523  108, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120}
524  },
525  {Frustum2({0, 0}, {1, 0}, 0.5 * M_PI / 2.),
526  {60, 71, 81, 82, 83, 92, 93, 94, 102,
527  103, 104, 105, 106, 113, 114, 115, 116, 117}
528  },
529  {Frustum2({0, 0}, {1, 0}, 0.2 * M_PI / 2.),
530  {60, 71, 82, 93, 104, 114, 115, 116}
531  },
532  {Frustum2({0, 0}, {1, 0}, 3 * M_PI / 4.),
533  {60, 68, 69, 70, 71, 72, 73, 74, 77, 78, 79, 80, 81, 82, 83,
534  84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98,
535  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
536  112, 113, 114, 115, 116, 117, 118, 119, 120}
537  },
538  {Frustum2({0, 0}, {0, 1}, 0.5 * M_PI / 2.),
539  {42, 43, 51, 52, 53, 54, 60, 61, 62, 63, 64, 65, 73, 74, 75, 76, 86, 87}
540  },
541  {Frustum2({0, 0}, {-1, 0}, 0.5 * M_PI / 2.),
542  {3, 4, 5, 6, 7, 14, 15, 16, 17, 18, 26, 27, 28, 37, 38, 39, 49, 60}
543  },
544  {Frustum2({0, 0}, {0, -1}, 0.5 * M_PI / 2.),
545  {33, 34, 44, 45, 46, 47, 55, 56, 57, 58, 59, 60, 66, 67, 68, 69, 77, 78}
546  },
547  {Frustum2({0, 0}, {1, 1}, 0.5 * M_PI / 2.),
548  {60, 72, 73, 74, 83, 84, 85, 86, 87, 94, 95, 96, 97, 98, 106, 107,
549  108, 109, 117, 118, 119, 120}
550  },
551  {Frustum2({0, 0}, {-1, 1}, 0.5 * M_PI / 2.),
552  {7, 8, 9, 10, 18, 19, 20, 21, 28, 29, 30, 31, 32, 39, 40, 41, 42,
553  43, 50, 51, 52, 60}
554  },
555  {Frustum2({0, 0}, {-1, -1}, 0.5 * M_PI / 2.),
556  {0, 1, 2, 3, 11, 12, 13, 14, 22, 23, 24, 25, 26, 33, 34, 35, 36,
557  37, 46, 47, 48, 60}
558  },
559  {Frustum2({0, 0}, {1, -1}, 0.5 * M_PI / 2.),
560  {60, 68, 69, 70, 77, 78, 79, 80, 81, 88, 89, 90, 91, 92, 99, 100,
561  101, 102, 110, 111, 112, 113}
562  },
563  {Frustum2({1, 1}, {1, -1}, M_PI / 2.),
564  {55, 56, 57, 58, 59, 60, 66, 67, 68, 69, 70, 71, 77, 78, 79, 80,
565  81, 82, 88, 89, 90, 91, 92, 93, 99, 100, 101, 102, 103, 104, 110, 111, 112, 113, 114, 115}
566  },
567  {Frustum2({-1, -1}, {1, -1}, M_PI / 2.),
568  {55, 56, 57, 58, 59, 60, 66, 67, 68, 69, 70, 71, 77, 78, 79, 80,
569  81, 82, 88, 89, 90, 91, 92, 93, 99, 100, 101, 102, 103, 104, 110, 111, 112, 113, 114, 115}
570  },
571  {Frustum2({10, -10}, {1, 1}, 0.5 * M_PI / 2.),
572  {91, 92, 102, 103, 104, 105, 114, 115, 116, 117, 118, 119}
573  },
574  {Frustum2({-10.3, 12.8}, {0.3, -1}, 0.5 * M_PI / 2.),
575  {22, 23, 24, 25, 26, 27, 28, 33, 34, 35, 36, 37, 38, 39, 40, 41,
576  44, 45, 46, 47, 48, 49, 50, 55, 56, 57, 58, 59, 60, 66, 67, 68,
577  69, 70, 77, 78, 79, 80, 88, 89, 99}
578  },
579  {Frustum2({17.2, 19.45}, {-1, -0.1}, 0.5 * M_PI / 2.),
580  {5, 6, 7, 8, 9, 10, 17, 18, 19, 20, 21, 28, 29, 30, 31, 32, 40,
581  41, 42, 43, 51, 52, 53, 54, 63, 64, 65, 74, 75, 76, 86, 87, 97,
582  98, 109}
583  },
584  };
585  // clang-format on
586 
587  for (size_t l = 0; l < fr_exp.size(); l++) {
588  const Frustum2& fr = fr_exp.at(l).first;
589  const std::set<size_t>& exp_idxs = fr_exp.at(l).second;
590  std::stringstream ss;
591  ss << "frust2d_test_" << l << ".svg";
592  os = make_svg(ss.str(), w, w);
593 
594  act_idxs.clear();
595 
596  std::vector<Box> boxes;
597  boxes.reserve((n + 1) * (n + 1));
598  for (size_t i = 0; i <= n; i++) {
599  for (size_t j = 0; j <= n; j++) {
600  boxes.emplace_back(&o,
601  Eigen::Matrix<BoundingBoxScalar, 2, 1>{
602  minx + i * stepx, miny + j * stepy},
603  size);
604  std::stringstream st;
605  st << boxes.size() - 1;
606 
607  std::string color = "red";
608  if (boxes.back().intersect(fr)) {
609  color = "green";
610  act_idxs.insert(boxes.size() - 1);
611  }
612 
613  boxes.back().svg(os, w, w, unit, st.str(), color);
614  }
615  }
616 
617  BOOST_CHECK(act_idxs == exp_idxs);
618 
619  fr.svg(os, w, w, maxx, unit);
620  os << "</svg>";
621 
622  os.close();
623  }
624  }
625 
626  PlyVisualization3D<BoundingBoxScalar> helper;
627  BOOST_TEST_CONTEXT("3D - 3 Sides") {
628  using Frustum3 = Frustum<BoundingBoxScalar, 3, 3>;
629  std::ofstream os;
630  size_t n = 10;
631  size_t s = 5;
632  double min = -10, max = 10;
633  double step = (max - min) / double(s);
634 
635  // BEGIN VISUAL PARAMETER TEST
636 
637  // size_t n_vtx = 1;
638  // auto make = [&](double angle, ActsVector<BoundingBoxScalar,3> origin,
639  // std::ofstream& os)
640  // {
641  // helper.clear();
642  // BoundingBoxScalar far = 1;
643  // Frustum3 fr(origin, {0, 0, 1}, angle);
644  // fr.draw(helper, far);
645  // fr = Frustum3(origin, {0, 0, -1}, angle);
646  // fr.draw(helper, far);
647  // fr = Frustum3(origin, {1, 0, 0}, angle);
648  // fr.draw(helper, far);
649  // fr = Frustum3(origin, {-1, 0, 0}, angle);
650  // fr.draw(helper, far);
651 
652  // fr = Frustum3(origin, {0, 1, 0}, angle);
653  // fr.draw(helper, far);
654  // fr = Frustum3(origin, {0, -1, 0}, angle);
655  // fr.draw(helper, far);
656 
657  // os << helper << std::flush;
658 
659  // helper.clear();
660  //};
661 
662  // os = std::ofstreams("frust3d_dir.ply");
663  // for (size_t i = 0; i <= s; i++) {
664  // for (size_t j = 0; j <= s; j++) {
665  // for (size_t k = 0; k <= s; k++) {
666  // ActsVector<BoundingBoxScalar,3> origin(
667  // min + i * step, min + j * step, min + k * step);
669  // make(M_PI / 4., origin, os);
670  //}
671  //}
672  //}
673  // os.close();
674 
675  // os = tmp("frust3D_angle.ply");
676  // helper.clear();
677  // n_vtx = 1;
678  // Eigen::Affine3f rot;
679  // for (size_t i = 0; i <= n; i++) {
680  // ActsVector<BoundingBoxScalar,3> origin(i * 4, 0, 0);
681  // rot = Eigen::AngleAxisf(M_PI / BoundingBoxScalar(n) * i,
682  // ActsVector<BoundingBoxScalar,3>::UnitY()); BoundingBoxScalar angle =
683  // (M_PI / 2.) / BoundingBoxScalar(n) * (1 + i);
684  // ActsVector<BoundingBoxScalar,3> dir(1, 0, 0); Frustum3 fr(origin, rot *
685  // dir, angle); fr.draw(helper, 2);
686  //}
687 
688  // os << helper << std::flush;
689  // os.close();
690 
692 
693  std::set<size_t> act_idxs;
694 
695  std::vector<std::pair<Frustum3, std::set<size_t>>> fr_exp;
696  fr_exp = {
697  {Frustum3({0, 0, 0}, {1, 0, 0}, M_PI / 2.),
698  {
699  665, 763, 774, 775, 785, 786, 787, 788, 796, 797, 807,
700  872, 873, 883, 884, 885, 886, 894, 895, 896, 897, 898,
701  905, 906, 907, 908, 909, 910, 911, 916, 917, 918, 919,
702  920, 927, 928, 929, 930, 938, 939, 970, 971, 981, 982,
703  983, 992, 993, 994, 995, 996, 1003, 1004, 1005, 1006, 1007,
704  1008, 1009, 1014, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1025,
705  1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1036, 1037, 1038,
706  1039, 1040, 1041, 1042, 1043, 1047, 1048, 1049, 1050, 1051, 1052,
707  1053, 1058, 1059, 1060, 1061, 1062, 1069, 1070, 1071, 1080, 1081,
708  1090, 1091, 1092, 1093, 1094, 1101, 1102, 1103, 1104, 1105, 1106,
709  1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119, 1123, 1124, 1125,
710  1126, 1127, 1128, 1129, 1130, 1131, 1132, 1134, 1135, 1136, 1137,
711  1138, 1139, 1140, 1141, 1142, 1143, 1145, 1146, 1147, 1148, 1149,
712  1150, 1151, 1152, 1153, 1154, 1156, 1157, 1158, 1159, 1160, 1161,
713  1162, 1163, 1164, 1165, 1167, 1168, 1169, 1170, 1171, 1172, 1173,
714  1174, 1175, 1176, 1178, 1179, 1180, 1181, 1182, 1183, 1184, 1185,
715  1189, 1190, 1191, 1192, 1193, 1194, 1200, 1201, 1202, 1203, 1204,
716  1210, 1211, 1212, 1213, 1214, 1215, 1216, 1217, 1221, 1222, 1223,
717  1224, 1225, 1226, 1227, 1228, 1229, 1232, 1233, 1234, 1235, 1236,
718  1237, 1238, 1239, 1240, 1241, 1242, 1243, 1244, 1245, 1246, 1247,
719  1248, 1249, 1250, 1251, 1252, 1253, 1254, 1255, 1256, 1257, 1258,
720  1259, 1260, 1261, 1262, 1263, 1264, 1265, 1266, 1267, 1268, 1269,
721  1270, 1271, 1272, 1273, 1274, 1275, 1276, 1277, 1278, 1279, 1280,
722  1281, 1282, 1283, 1284, 1285, 1286, 1287, 1288, 1289, 1290, 1291,
723  1292, 1293, 1294, 1295, 1296, 1297, 1298, 1299, 1300, 1301, 1302,
724  1303, 1304, 1305, 1306, 1307, 1308, 1309, 1310, 1311, 1312, 1313,
725  1314, 1315, 1316, 1317, 1320, 1321, 1322, 1323, 1324, 1325, 1326,
726  1327,
727  }},
728  {Frustum3({0, 0, 0}, {0, 1, 0}, M_PI / 2.),
729  {93, 102, 103, 104, 105, 106, 112, 113, 114, 115, 116,
730  117, 118, 203, 213, 214, 215, 223, 224, 225, 226, 227,
731  233, 234, 235, 236, 237, 238, 239, 324, 333, 334, 335,
732  336, 337, 343, 344, 345, 346, 347, 348, 349, 353, 354,
733  355, 356, 357, 358, 359, 360, 361, 434, 444, 445, 446,
734  454, 455, 456, 457, 458, 464, 465, 466, 467, 468, 469,
735  470, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482,
736  483, 555, 564, 565, 566, 567, 568, 574, 575, 576, 577,
737  578, 579, 580, 584, 585, 586, 587, 588, 589, 590, 591,
738  592, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603,
739  604, 665, 675, 676, 677, 685, 686, 687, 688, 689, 695,
740  696, 697, 698, 699, 700, 701, 704, 705, 706, 707, 708,
741  709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719,
742  720, 721, 722, 723, 724, 725, 795, 796, 797, 798, 799,
743  805, 806, 807, 808, 809, 810, 811, 815, 816, 817, 818,
744  819, 820, 821, 822, 823, 825, 826, 827, 828, 829, 830,
745  831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841,
746  842, 843, 844, 845, 846, 926, 927, 928, 929, 930, 931,
747  932, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944,
748  945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955,
749  956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966,
750  967, 1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063, 1064, 1065,
751  1066, 1067, 1068, 1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076,
752  1077, 1078, 1079, 1080, 1081, 1082, 1083, 1084, 1085, 1086, 1087,
753  1088, 1188, 1189, 1190, 1191, 1192, 1193, 1194, 1195, 1196, 1197,
754  1198, 1199, 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1207, 1208,
755  1209, 1320, 1321, 1322, 1323, 1324, 1325, 1326, 1327, 1328, 1329,
756  1330}},
757  {Frustum3({0, 0, 0}, {0, 0, 1}, M_PI / 2.),
758  {32, 42, 43, 53, 54, 63, 64, 65, 75, 76, 86,
759  87, 98, 153, 163, 164, 173, 174, 175, 183, 184, 185,
760  186, 195, 196, 197, 207, 208, 219, 263, 273, 274, 283,
761  284, 285, 294, 295, 296, 304, 305, 306, 307, 316, 317,
762  318, 327, 328, 329, 339, 340, 351, 373, 384, 394, 395,
763  404, 405, 406, 414, 415, 416, 417, 424, 425, 426, 427,
764  428, 436, 437, 438, 439, 448, 449, 450, 460, 461, 472,
765  483, 494, 504, 505, 514, 515, 516, 524, 525, 526, 527,
766  535, 536, 537, 538, 545, 546, 547, 548, 549, 557, 558,
767  559, 560, 568, 569, 570, 571, 580, 581, 582, 592, 593,
768  604, 614, 615, 625, 626, 635, 636, 637, 645, 646, 647,
769  648, 655, 656, 657, 658, 659, 665, 666, 667, 668, 669,
770  670, 677, 678, 679, 680, 681, 689, 690, 691, 692, 701,
771  702, 703, 713, 714, 724, 725, 735, 736, 745, 746, 747,
772  755, 756, 757, 758, 765, 766, 767, 768, 769, 776, 777,
773  778, 779, 780, 787, 788, 789, 790, 791, 798, 799, 800,
774  801, 802, 809, 810, 811, 812, 813, 821, 822, 823, 824,
775  833, 834, 835, 845, 846, 855, 856, 857, 866, 867, 868,
776  876, 877, 878, 879, 887, 888, 889, 890, 898, 899, 900,
777  901, 909, 910, 911, 912, 920, 921, 922, 923, 931, 932,
778  933, 934, 942, 943, 944, 945, 954, 955, 956, 965, 966,
779  967, 976, 977, 978, 987, 988, 989, 998, 999, 1000, 1009,
780  1010, 1011, 1020, 1021, 1022, 1031, 1032, 1033, 1042, 1043, 1044,
781  1053, 1054, 1055, 1064, 1065, 1066, 1075, 1076, 1077, 1086, 1087,
782  1088, 1098, 1099, 1109, 1110, 1120, 1121, 1131, 1132, 1142, 1143,
783  1153, 1154, 1164, 1165, 1175, 1176, 1186, 1187, 1197, 1198, 1208,
784  1209, 1220, 1231, 1242, 1253, 1264, 1275, 1286, 1297, 1308, 1319,
785  1330}},
786  {Frustum3({0, 0, 0}, {0, 0, 1}, M_PI / 4.),
787  {186, 305, 306, 307, 416, 417, 425, 426, 427, 428, 438, 439,
788  527, 536, 537, 538, 545, 546, 547, 548, 549, 558, 559, 560,
789  571, 647, 648, 656, 657, 658, 659, 665, 666, 667, 668, 669,
790  670, 678, 679, 680, 681, 691, 692, 758, 767, 768, 769, 777,
791  778, 779, 780, 788, 789, 790, 791, 799, 800, 801, 802, 811,
792  812, 813, 824, 879, 890, 901, 912, 923, 934, 945}},
793  {Frustum3({0, 0, 0}, {0, 0, 1}, M_PI / 8.),
794  {427, 428, 546, 547, 548, 549, 658, 659, 665, 666, 667, 668, 669, 670,
795  680, 681, 780, 791, 802}},
796  {Frustum3({0, 0, 0}, {0, 0, 1}, M_PI * 3. / 4.),
797  {8, 9, 10, 19, 20, 21, 29, 30, 31, 32, 40,
798  41, 42, 43, 51, 52, 53, 54, 61, 62, 63, 64,
799  65, 73, 74, 75, 76, 84, 85, 86, 87, 95, 96,
800  97, 98, 107, 108, 109, 118, 119, 120, 129, 130, 131,
801  140, 141, 142, 150, 151, 152, 153, 161, 162, 163, 164,
802  171, 172, 173, 174, 175, 182, 183, 184, 185, 186, 193,
803  194, 195, 196, 197, 205, 206, 207, 208, 216, 217, 218,
804  219, 228, 229, 230, 239, 240, 241, 250, 251, 252, 260,
805  261, 262, 263, 271, 272, 273, 274, 282, 283, 284, 285,
806  292, 293, 294, 295, 296, 303, 304, 305, 306, 307, 314,
807  315, 316, 317, 318, 326, 327, 328, 329, 337, 338, 339,
808  340, 348, 349, 350, 351, 360, 361, 362, 370, 371, 372,
809  373, 381, 382, 383, 384, 392, 393, 394, 395, 402, 403,
810  404, 405, 406, 413, 414, 415, 416, 417, 424, 425, 426,
811  427, 428, 435, 436, 437, 438, 439, 446, 447, 448, 449,
812  450, 458, 459, 460, 461, 469, 470, 471, 472, 480, 481,
813  482, 483, 491, 492, 493, 494, 502, 503, 504, 505, 513,
814  514, 515, 516, 523, 524, 525, 526, 527, 534, 535, 536,
815  537, 538, 544, 545, 546, 547, 548, 549, 556, 557, 558,
816  559, 560, 567, 568, 569, 570, 571, 579, 580, 581, 582,
817  590, 591, 592, 593, 601, 602, 603, 604, 612, 613, 614,
818  615, 623, 624, 625, 626, 633, 634, 635, 636, 637, 644,
819  645, 646, 647, 648, 655, 656, 657, 658, 659, 665, 666,
820  667, 668, 669, 670, 677, 678, 679, 680, 681, 688, 689,
821  690, 691, 692, 699, 700, 701, 702, 703, 711, 712, 713,
822  714, 722, 723, 724, 725, 733, 734, 735, 736, 743, 744,
823  745, 746, 747, 754, 755, 756, 757, 758, 765, 766, 767,
824  768, 769, 776, 777, 778, 779, 780, 787, 788, 789, 790,
825  791, 798, 799, 800, 801, 802, 809, 810, 811, 812, 813,
826  820, 821, 822, 823, 824, 831, 832, 833, 834, 835, 843,
827  844, 845, 846, 854, 855, 856, 857, 864, 865, 866, 867,
828  868, 875, 876, 877, 878, 879, 886, 887, 888, 889, 890,
829  897, 898, 899, 900, 901, 908, 909, 910, 911, 912, 919,
830  920, 921, 922, 923, 930, 931, 932, 933, 934, 941, 942,
831  943, 944, 945, 952, 953, 954, 955, 956, 964, 965, 966,
832  967, 975, 976, 977, 978, 986, 987, 988, 989, 997, 998,
833  999, 1000, 1008, 1009, 1010, 1011, 1019, 1020, 1021, 1022, 1030,
834  1031, 1032, 1033, 1041, 1042, 1043, 1044, 1052, 1053, 1054, 1055,
835  1063, 1064, 1065, 1066, 1074, 1075, 1076, 1077, 1085, 1086, 1087,
836  1088, 1096, 1097, 1098, 1099, 1107, 1108, 1109, 1110, 1118, 1119,
837  1120, 1121, 1129, 1130, 1131, 1132, 1140, 1141, 1142, 1143, 1151,
838  1152, 1153, 1154, 1162, 1163, 1164, 1165, 1173, 1174, 1175, 1176,
839  1184, 1185, 1186, 1187, 1195, 1196, 1197, 1198, 1206, 1207, 1208,
840  1209, 1217, 1218, 1219, 1220, 1228, 1229, 1230, 1231, 1239, 1240,
841  1241, 1242, 1250, 1251, 1252, 1253, 1261, 1262, 1263, 1264, 1272,
842  1273, 1274, 1275, 1283, 1284, 1285, 1286, 1294, 1295, 1296, 1297,
843  1305, 1306, 1307, 1308, 1316, 1317, 1318, 1319, 1327, 1328, 1329,
844  1330}},
845  {Frustum3({1.3, -5.9, 3.5}, {0.2, 0.4, 1}, M_PI / 3.),
846  {318, 426, 427, 428, 438, 439, 450, 538, 546, 547, 548,
847  549, 558, 559, 560, 570, 571, 582, 655, 656, 657, 658,
848  659, 667, 668, 669, 670, 678, 679, 680, 681, 690, 691,
849  692, 702, 703, 714, 768, 769, 777, 778, 779, 780, 787,
850  788, 789, 790, 791, 799, 800, 801, 802, 810, 811, 812,
851  813, 822, 823, 824, 834, 835, 846, 888, 889, 890, 899,
852  900, 901, 910, 911, 912, 920, 921, 922, 923, 931, 932,
853  933, 934, 942, 943, 944, 945, 954, 955, 956, 966, 967,
854  1000, 1010, 1011, 1021, 1022, 1032, 1033, 1042, 1043, 1044, 1053,
855  1054, 1055, 1064, 1065, 1066, 1074, 1075, 1076, 1077, 1086, 1087,
856  1088, 1143, 1154, 1165, 1175, 1176, 1186, 1187, 1197, 1198, 1207,
857  1208, 1209, 1308, 1319, 1330}}};
858 
859  for (size_t l = 0; l < fr_exp.size(); l++) {
860  const Frustum3& fr = fr_exp.at(l).first;
861  const std::set<size_t>& exp_idxs = fr_exp.at(l).second;
862  std::stringstream ss;
863  ss << "frust3d-3s_test_" << l << ".ply";
864 
865  os = tmp(ss.str());
866 
867  helper.clear();
868 
869  act_idxs.clear();
870 
871  fr.draw(helper, 50);
872 
873  n = 10;
874  min = -33;
875  max = 33;
876  step = (max - min) / BoundingBoxScalar(n);
877 
878  Object o;
879  using Box = AxisAlignedBoundingBox<Object, BoundingBoxScalar, 3>;
880  Box::Size size(Eigen::Matrix<BoundingBoxScalar, 3, 1>(2, 2, 2));
881 
882  size_t idx = 0;
883 
884  for (size_t i = 0; i <= n; i++) {
885  for (size_t j = 0; j <= n; j++) {
886  for (size_t k = 0; k <= n; k++) {
887  Eigen::Matrix<BoundingBoxScalar, 3, 1> pos(
888  min + i * step, min + j * step, min + k * step);
889  Box bb(&o, pos, size);
890 
891  std::array<int, 3> color = {255, 0, 0};
892 
893  if (bb.intersect(fr)) {
894  color = {0, 255, 0};
895  act_idxs.insert(idx);
896  }
897 
898  bb.draw(helper, color);
899  idx++;
900  }
901  }
902  }
903 
904  os << helper << std::flush;
905  os.close();
906 
907  BOOST_CHECK(act_idxs == exp_idxs);
908  }
909  }
910 
911  BOOST_TEST_CONTEXT("3D - 4 Sides") {
912  using Frustum34 = Frustum<BoundingBoxScalar, 3, 4>;
913  size_t n = 10;
914  double min = -10, max = 10;
915  size_t s = 5;
916  double step = (max - min) / double(s);
917  std::ofstream os;
918 
919  // BEGIN VISUAL PARAMETER TEST
920 
921  // size_t n_vtx = 1;
922 
923  // helper.clear();
924  // os = tmp("frust3d-4s_dir.ply");
925 
926  // double angle = M_PI / 4.;
927  // for (size_t i = 0; i <= s; i++) {
928  // for (size_t j = 0; j <= s; j++) {
929  // for (size_t k = 0; k <= s; k++) {
930  // ActsVector<BoundingBoxScalar,3> origin(
931  // min + i * step, min + j * step, min + k * step);
932  // ActsVector<BoundingBoxScalar,3> dir(1, 0, 0);
933 
934  // Eigen::Affine3f rot;
935  // rot = Eigen::AngleAxisf(M_PI / BoundingBoxScalar(s) * i,
936  // ActsVector<BoundingBoxScalar,3>::UnitX())
937  //* Eigen::AngleAxisf(M_PI / BoundingBoxScalar(s) * j,
938  // ActsVector<BoundingBoxScalar,3>::UnitY())
939  //* Eigen::AngleAxisf(M_PI / BoundingBoxScalar(s) * k,
940  // ActsVector<BoundingBoxScalar,3>::UnitZ());
941 
942  // Frustum34 fr(origin, rot * dir, angle);
943  // fr.draw(helper, 1);
944  //}
945  //}
946  //}
947 
948  // os << helper << std::flush;
949  // os.close();
950  // os = tmp("frust3d-4s_angle.ply");
951  // helper.clear();
952 
953  // n_vtx = 1;
954  // for (size_t i = 0; i <= n; i++) {
955  // ActsVector<BoundingBoxScalar,3> origin(i * 4, 0, 0);
956  // Eigen::Affine3f rot;
957  // rot = Eigen::AngleAxisf(M_PI / BoundingBoxScalar(n) * i,
958  // ActsVector<BoundingBoxScalar,3>::UnitY());
959  // angle = (M_PI / 2.) / BoundingBoxScalar(n) * (1 + i);
960  // ActsVector<BoundingBoxScalar,3> dir(1, 0, 0);
961  // Frustum34 fr(origin, rot * dir, angle);
962  // fr.draw(helper, 2);
963  //}
964 
965  // os << helper << std::flush;
966  // os.close();
967 
968  // END VISUAL PARAMETER TEST
969 
970  std::set<size_t> act_idxs;
971 
972  std::vector<std::pair<Frustum34, std::set<size_t>>> fr_exp;
973  fr_exp = {
974  {Frustum34({0, 0, 0}, {1, 0, 0}, M_PI / 2.),
975  {665, 774, 775, 776, 785, 786, 787, 796, 797, 798, 883,
976  884, 885, 886, 887, 894, 895, 896, 897, 898, 905, 906,
977  907, 908, 909, 916, 917, 918, 919, 920, 927, 928, 929,
978  930, 931, 992, 993, 994, 995, 996, 997, 998, 1003, 1004,
979  1005, 1006, 1007, 1008, 1009, 1014, 1015, 1016, 1017, 1018, 1019,
980  1020, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1036, 1037, 1038,
981  1039, 1040, 1041, 1042, 1047, 1048, 1049, 1050, 1051, 1052, 1053,
982  1058, 1059, 1060, 1061, 1062, 1063, 1064, 1101, 1102, 1103, 1104,
983  1105, 1106, 1107, 1108, 1109, 1112, 1113, 1114, 1115, 1116, 1117,
984  1118, 1119, 1120, 1123, 1124, 1125, 1126, 1127, 1128, 1129, 1130,
985  1131, 1134, 1135, 1136, 1137, 1138, 1139, 1140, 1141, 1142, 1145,
986  1146, 1147, 1148, 1149, 1150, 1151, 1152, 1153, 1156, 1157, 1158,
987  1159, 1160, 1161, 1162, 1163, 1164, 1167, 1168, 1169, 1170, 1171,
988  1172, 1173, 1174, 1175, 1178, 1179, 1180, 1181, 1182, 1183, 1184,
989  1185, 1186, 1189, 1190, 1191, 1192, 1193, 1194, 1195, 1196, 1197,
990  1210, 1211, 1212, 1213, 1214, 1215, 1216, 1217, 1218, 1219, 1220,
991  1221, 1222, 1223, 1224, 1225, 1226, 1227, 1228, 1229, 1230, 1231,
992  1232, 1233, 1234, 1235, 1236, 1237, 1238, 1239, 1240, 1241, 1242,
993  1243, 1244, 1245, 1246, 1247, 1248, 1249, 1250, 1251, 1252, 1253,
994  1254, 1255, 1256, 1257, 1258, 1259, 1260, 1261, 1262, 1263, 1264,
995  1265, 1266, 1267, 1268, 1269, 1270, 1271, 1272, 1273, 1274, 1275,
996  1276, 1277, 1278, 1279, 1280, 1281, 1282, 1283, 1284, 1285, 1286,
997  1287, 1288, 1289, 1290, 1291, 1292, 1293, 1294, 1295, 1296, 1297,
998  1298, 1299, 1300, 1301, 1302, 1303, 1304, 1305, 1306, 1307, 1308,
999  1309, 1310, 1311, 1312, 1313, 1314, 1315, 1316, 1317, 1318, 1319,
1000  1320, 1321, 1322, 1323, 1324, 1325, 1326, 1327, 1328, 1329, 1330}},
1001  {Frustum34({0, 0, 0}, {0, 1, 0}, M_PI / 2.),
1002  {110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120,
1003  221, 222, 223, 224, 225, 226, 227, 228, 229, 231, 232,
1004  233, 234, 235, 236, 237, 238, 239, 240, 241, 332, 333,
1005  334, 335, 336, 337, 338, 342, 343, 344, 345, 346, 347,
1006  348, 349, 350, 352, 353, 354, 355, 356, 357, 358, 359,
1007  360, 361, 362, 443, 444, 445, 446, 447, 453, 454, 455,
1008  456, 457, 458, 459, 463, 464, 465, 466, 467, 468, 469,
1009  470, 471, 473, 474, 475, 476, 477, 478, 479, 480, 481,
1010  482, 483, 554, 555, 556, 564, 565, 566, 567, 568, 574,
1011  575, 576, 577, 578, 579, 580, 584, 585, 586, 587, 588,
1012  589, 590, 591, 592, 594, 595, 596, 597, 598, 599, 600,
1013  601, 602, 603, 604, 665, 675, 676, 677, 685, 686, 687,
1014  688, 689, 695, 696, 697, 698, 699, 700, 701, 705, 706,
1015  707, 708, 709, 710, 711, 712, 713, 715, 716, 717, 718,
1016  719, 720, 721, 722, 723, 724, 725, 796, 797, 798, 806,
1017  807, 808, 809, 810, 816, 817, 818, 819, 820, 821, 822,
1018  826, 827, 828, 829, 830, 831, 832, 833, 834, 836, 837,
1019  838, 839, 840, 841, 842, 843, 844, 845, 846, 927, 928,
1020  929, 930, 931, 937, 938, 939, 940, 941, 942, 943, 947,
1021  948, 949, 950, 951, 952, 953, 954, 955, 957, 958, 959,
1022  960, 961, 962, 963, 964, 965, 966, 967, 1058, 1059, 1060,
1023  1061, 1062, 1063, 1064, 1068, 1069, 1070, 1071, 1072, 1073, 1074,
1024  1075, 1076, 1078, 1079, 1080, 1081, 1082, 1083, 1084, 1085, 1086,
1025  1087, 1088, 1189, 1190, 1191, 1192, 1193, 1194, 1195, 1196, 1197,
1026  1199, 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1207, 1208, 1209,
1027  1320, 1321, 1322, 1323, 1324, 1325, 1326, 1327, 1328, 1329, 1330}},
1028  {Frustum34({0, 0, 0}, {0, 0, 1}, M_PI / 2.),
1029  {10, 21, 32, 43, 54, 65, 76, 87, 98, 109, 120,
1030  131, 141, 142, 152, 153, 163, 164, 174, 175, 185, 186,
1031  196, 197, 207, 208, 218, 219, 229, 230, 241, 252, 262,
1032  263, 272, 273, 274, 283, 284, 285, 294, 295, 296, 305,
1033  306, 307, 316, 317, 318, 327, 328, 329, 338, 339, 340,
1034  350, 351, 362, 373, 383, 384, 393, 394, 395, 403, 404,
1035  405, 406, 414, 415, 416, 417, 425, 426, 427, 428, 436,
1036  437, 438, 439, 447, 448, 449, 450, 459, 460, 461, 471,
1037  472, 483, 494, 504, 505, 514, 515, 516, 524, 525, 526,
1038  527, 534, 535, 536, 537, 538, 545, 546, 547, 548, 549,
1039  556, 557, 558, 559, 560, 568, 569, 570, 571, 580, 581,
1040  582, 592, 593, 604, 615, 625, 626, 635, 636, 637, 645,
1041  646, 647, 648, 655, 656, 657, 658, 659, 665, 666, 667,
1042  668, 669, 670, 677, 678, 679, 680, 681, 689, 690, 691,
1043  692, 701, 702, 703, 713, 714, 725, 736, 746, 747, 756,
1044  757, 758, 766, 767, 768, 769, 776, 777, 778, 779, 780,
1045  787, 788, 789, 790, 791, 798, 799, 800, 801, 802, 810,
1046  811, 812, 813, 822, 823, 824, 834, 835, 846, 857, 867,
1047  868, 877, 878, 879, 887, 888, 889, 890, 898, 899, 900,
1048  901, 909, 910, 911, 912, 920, 921, 922, 923, 931, 932,
1049  933, 934, 943, 944, 945, 955, 956, 967, 978, 988, 989,
1050  998, 999, 1000, 1009, 1010, 1011, 1020, 1021, 1022, 1031, 1032,
1051  1033, 1042, 1043, 1044, 1053, 1054, 1055, 1064, 1065, 1066, 1076,
1052  1077, 1088, 1099, 1109, 1110, 1120, 1121, 1131, 1132, 1142, 1143,
1053  1153, 1154, 1164, 1165, 1175, 1176, 1186, 1187, 1197, 1198, 1209,
1054  1220, 1231, 1242, 1253, 1264, 1275, 1286, 1297, 1308, 1319, 1330}},
1055  {Frustum34({0, 0, 0}, {0, 0, 1}, M_PI / 4.),
1056  {406, 417, 428, 439, 450, 527, 535, 536, 537, 538, 546, 547, 548, 549,
1057  557, 558, 559, 560, 571, 648, 656, 657, 658, 659, 665, 666, 667, 668,
1058  669, 670, 678, 679, 680, 681, 692, 769, 777, 778, 779, 780, 788, 789,
1059  790, 791, 799, 800, 801, 802, 813, 890, 901, 912, 923, 934}},
1060  {Frustum34({0, 0, 0}, {0, 0, 1}, M_PI / 8.),
1061  {538, 549, 560, 659, 665, 666, 667, 668, 669, 670, 681, 780, 791,
1062  802}},
1063  {Frustum34({0, 0, 0}, {0, 0, 1}, M_PI * 3. / 4.),
1064  {7, 8, 9, 10, 18, 19, 20, 21, 29, 30, 31,
1065  32, 40, 41, 42, 43, 51, 52, 53, 54, 62, 63,
1066  64, 65, 73, 74, 75, 76, 84, 85, 86, 87, 95,
1067  96, 97, 98, 106, 107, 108, 109, 117, 118, 119, 120,
1068  128, 129, 130, 131, 139, 140, 141, 142, 150, 151, 152,
1069  153, 161, 162, 163, 164, 172, 173, 174, 175, 183, 184,
1070  185, 186, 194, 195, 196, 197, 205, 206, 207, 208, 216,
1071  217, 218, 219, 227, 228, 229, 230, 238, 239, 240, 241,
1072  249, 250, 251, 252, 260, 261, 262, 263, 271, 272, 273,
1073  274, 282, 283, 284, 285, 293, 294, 295, 296, 304, 305,
1074  306, 307, 315, 316, 317, 318, 326, 327, 328, 329, 337,
1075  338, 339, 340, 348, 349, 350, 351, 359, 360, 361, 362,
1076  370, 371, 372, 373, 381, 382, 383, 384, 392, 393, 394,
1077  395, 402, 403, 404, 405, 406, 413, 414, 415, 416, 417,
1078  424, 425, 426, 427, 428, 435, 436, 437, 438, 439, 446,
1079  447, 448, 449, 450, 458, 459, 460, 461, 469, 470, 471,
1080  472, 480, 481, 482, 483, 491, 492, 493, 494, 502, 503,
1081  504, 505, 513, 514, 515, 516, 523, 524, 525, 526, 527,
1082  534, 535, 536, 537, 538, 545, 546, 547, 548, 549, 556,
1083  557, 558, 559, 560, 567, 568, 569, 570, 571, 579, 580,
1084  581, 582, 590, 591, 592, 593, 601, 602, 603, 604, 612,
1085  613, 614, 615, 623, 624, 625, 626, 634, 635, 636, 637,
1086  644, 645, 646, 647, 648, 655, 656, 657, 658, 659, 665,
1087  666, 667, 668, 669, 670, 677, 678, 679, 680, 681, 688,
1088  689, 690, 691, 692, 700, 701, 702, 703, 711, 712, 713,
1089  714, 722, 723, 724, 725, 733, 734, 735, 736, 744, 745,
1090  746, 747, 755, 756, 757, 758, 765, 766, 767, 768, 769,
1091  776, 777, 778, 779, 780, 787, 788, 789, 790, 791, 798,
1092  799, 800, 801, 802, 809, 810, 811, 812, 813, 821, 822,
1093  823, 824, 832, 833, 834, 835, 843, 844, 845, 846, 854,
1094  855, 856, 857, 865, 866, 867, 868, 876, 877, 878, 879,
1095  886, 887, 888, 889, 890, 897, 898, 899, 900, 901, 908,
1096  909, 910, 911, 912, 919, 920, 921, 922, 923, 930, 931,
1097  932, 933, 934, 942, 943, 944, 945, 953, 954, 955, 956,
1098  964, 965, 966, 967, 975, 976, 977, 978, 986, 987, 988,
1099  989, 997, 998, 999, 1000, 1008, 1009, 1010, 1011, 1019, 1020,
1100  1021, 1022, 1030, 1031, 1032, 1033, 1041, 1042, 1043, 1044, 1052,
1101  1053, 1054, 1055, 1063, 1064, 1065, 1066, 1074, 1075, 1076, 1077,
1102  1085, 1086, 1087, 1088, 1096, 1097, 1098, 1099, 1107, 1108, 1109,
1103  1110, 1118, 1119, 1120, 1121, 1129, 1130, 1131, 1132, 1140, 1141,
1104  1142, 1143, 1151, 1152, 1153, 1154, 1162, 1163, 1164, 1165, 1173,
1105  1174, 1175, 1176, 1184, 1185, 1186, 1187, 1195, 1196, 1197, 1198,
1106  1206, 1207, 1208, 1209, 1217, 1218, 1219, 1220, 1228, 1229, 1230,
1107  1231, 1239, 1240, 1241, 1242, 1250, 1251, 1252, 1253, 1261, 1262,
1108  1263, 1264, 1272, 1273, 1274, 1275, 1283, 1284, 1285, 1286, 1294,
1109  1295, 1296, 1297, 1305, 1306, 1307, 1308, 1316, 1317, 1318, 1319,
1110  1327, 1328, 1329, 1330}},
1111  {Frustum34({1.3, -5.9, 3.5}, {0.2, 0.4, 1}, M_PI / 3.),
1112  {461, 472, 537, 538, 548, 549, 558, 559, 560, 569, 570,
1113  571, 581, 582, 593, 655, 656, 657, 658, 659, 666, 667,
1114  668, 669, 670, 678, 679, 680, 681, 690, 691, 692, 702,
1115  703, 714, 777, 778, 779, 780, 787, 788, 789, 790, 791,
1116  799, 800, 801, 802, 811, 812, 813, 823, 824, 835, 846,
1117  899, 900, 901, 910, 911, 912, 920, 921, 922, 923, 932,
1118  933, 934, 944, 945, 955, 956, 967, 1021, 1022, 1032, 1033,
1119  1042, 1043, 1044, 1053, 1054, 1055, 1064, 1065, 1066, 1076, 1077,
1120  1088, 1143, 1154, 1165, 1175, 1176, 1186, 1187, 1197, 1198, 1209,
1121  1308, 1319, 1330}}};
1122 
1123  for (size_t l = 0; l < fr_exp.size(); l++) {
1124  const Frustum34& fr = fr_exp.at(l).first;
1125  const std::set<size_t>& exp_idxs = fr_exp.at(l).second;
1126  std::stringstream ss;
1127  ss << "frust3d-4s_test_" << l << ".ply";
1128 
1129  os = tmp(ss.str());
1130 
1131  helper.clear();
1132 
1133  act_idxs.clear();
1134 
1135  fr.draw(helper, 50);
1136 
1137  n = 10;
1138  min = -33;
1139  max = 33;
1140  step = (max - min) / BoundingBoxScalar(n);
1141 
1142  Object o;
1143  using Box = AxisAlignedBoundingBox<Object, BoundingBoxScalar, 3>;
1144  Box::Size size(Eigen::Matrix<BoundingBoxScalar, 3, 1>(2, 2, 2));
1145 
1146  size_t idx = 0;
1147  for (size_t i = 0; i <= n; i++) {
1148  for (size_t j = 0; j <= n; j++) {
1149  for (size_t k = 0; k <= n; k++) {
1150  Eigen::Matrix<BoundingBoxScalar, 3, 1> pos(
1151  min + i * step, min + j * step, min + k * step);
1152  Box bb(&o, pos, size);
1153 
1154  std::array<int, 3> color = {255, 0, 0};
1155 
1156  if (bb.intersect(fr)) {
1157  color = {0, 255, 0};
1158  act_idxs.insert(idx);
1159  }
1160 
1161  bb.draw(helper, color);
1162  idx++;
1163  }
1164  }
1165  }
1166 
1167  os << helper << std::flush;
1168  os.close();
1169 
1170  BOOST_CHECK(act_idxs == exp_idxs);
1171  }
1172  }
1173 
1174  BOOST_TEST_CONTEXT("3D - 5 Sides") {
1175  using Frustum = Frustum<BoundingBoxScalar, 3, 5>;
1176  using Box = AxisAlignedBoundingBox<Object, BoundingBoxScalar, 3>;
1177  Box::Size size(Eigen::Matrix<BoundingBoxScalar, 3, 1>(2, 2, 2));
1178 
1179  Object o;
1180 
1181  PlyVisualization3D<BoundingBoxScalar> ply;
1182 
1183  Frustum fr({0, 0, 0}, {0, 0, 1}, M_PI / 8.);
1184  fr.draw(ply, 10);
1185 
1186  Box bb(&o, {0, 0, 10}, size);
1187  bb.draw(ply);
1188 
1189  BOOST_CHECK(bb.intersect(fr));
1190 
1191  auto os = tmp("frust3d-5s.ply");
1192  os << ply << std::flush;
1193  os.close();
1194  }
1195 
1196  BOOST_TEST_CONTEXT("3D - 10 Sides") {
1197  using Frustum = Frustum<BoundingBoxScalar, 3, 10>;
1198  using Box = AxisAlignedBoundingBox<Object, BoundingBoxScalar, 3>;
1199  using vec3 = Eigen::Matrix<BoundingBoxScalar, 3, 1>;
1200  Box::Size size(vec3(2, 2, 2));
1201 
1202  Object o;
1203 
1204  PlyVisualization3D<BoundingBoxScalar> ply;
1205 
1206  // Frustum fr({0, 0, 0}, {0, 0, 1}, M_PI/8.);
1207  vec3 pos = {-12.4205, 29.3578, 44.6207};
1208  vec3 dir = {-0.656862, 0.48138, 0.58035};
1209  Frustum fr(pos, dir, 0.972419);
1210  fr.draw(ply, 10);
1211 
1212  Box bb(&o, pos + dir * 10, size);
1213  bb.draw(ply);
1214 
1215  BOOST_CHECK(bb.intersect(fr));
1216 
1217  auto os = tmp("frust3d-10s.ply");
1218  os << ply << std::flush;
1219  os.close();
1220  }
1221 
1222  BOOST_TEST_CONTEXT("3D - 4 Sides - Big box") {
1223  using Frustum = Frustum<BoundingBoxScalar, 3, 4>;
1224  using Box = AxisAlignedBoundingBox<Object, BoundingBoxScalar, 3>;
1225  using vec3 = Eigen::Matrix<BoundingBoxScalar, 3, 1>;
1226 
1227  Object o;
1228 
1229  PlyVisualization3D<BoundingBoxScalar> ply;
1230 
1231  vec3 pos = {0, 0, 0};
1232  vec3 dir = {0, 0, 1};
1233  Frustum fr(pos, dir, 0.972419);
1234  fr.draw(ply, 10);
1235 
1236  Box::Size size(vec3(100, 100, 2));
1237  Box bb(&o, pos + dir * 7, size);
1238  bb.draw(ply);
1239 
1240  BOOST_CHECK(bb.intersect(fr));
1241 
1242  auto os = tmp("frust3d-4s-bigbox.ply");
1243  os << ply << std::flush;
1244  os.close();
1245  }
1246 }
1247 
1248 BOOST_AUTO_TEST_CASE(ostream_operator) {
1249  Object o;
1250  using Box = Acts::AxisAlignedBoundingBox<Object, BoundingBoxScalar, 2>;
1251  Box bb(&o, {-1, -1}, {2, 2});
1252 
1253  std::stringstream ss;
1254  ss << bb;
1255 
1256  BOOST_CHECK(ss.str() == "AABB(ctr=(0.5, 0.5) vmin=(-1, -1) vmax=(2, 2))");
1257 }
1258 
1259 } // namespace Test
1260 } // namespace Acts