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