Acts/Utilities/BoundingBox.hpp

0001 // This file is part of the Acts project.
0002 //
0003 // Copyright (C) 2018-2019 CERN for the benefit of the Acts project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include "Acts/Definitions/Algebra.hpp"
0012 #include "Acts/Utilities/Frustum.hpp"
0013 #include "Acts/Utilities/Ray.hpp"
0014 #include "Acts/Visualization/IVisualization3D.hpp"
0015
0016 #include <array>
0017 #include <memory>
0018 #include <tuple>
0019 #include <vector>
0020
0021 namespace Acts {
0022
0023 /**
0024  * Implementation of an Axis Aligned Bounding Box. This type is compatible
0025  * with 2D and 3D boxes
0026  */
0027 template <typename entity_t, typename value_t, std::size_t DIM>
0028 class AxisAlignedBoundingBox {
0029  private:
0030   /**
0031    * Private self type to capture template parameters
0032    */
0033   using self_t = AxisAlignedBoundingBox<entity_t, value_t, DIM>;
0034
0035   /**
0036    * Strong type helper, not public
0037    * This is only used to provide sensible tag-dispatch below.
0038    */
0039   template <typename T, typename P>
0040   class NamedType {
0041    public:
0042     explicit NamedType(const T& value) : m_value(value) {}
0043     explicit NamedType(T&& value) : m_value(std::move(value)) {}
0044     T& get() { return m_value; }
0045     const T& get() const { return m_value; }
0046
0047    private:
0048     T m_value;
0049   };
0050
0051   /**
0052    * SizeParameter Tag
0053    */
0054   struct SizeParameter {};
0055
0056  public:
0057   /**
0058    * The value type used by this class
0059    */
0060
0061   using value_type = value_t;
0062   /**
0063    * Re-export vertex type based on value type given
0064    */
0065
0066   using VertexType = Eigen::Matrix<value_t, DIM, 1>;
0067   /**
0068    * Associated array value to `VertexType`
0069    */
0070
0071   using vertex_array_type = Eigen::Array<value_t, DIM, 1>;
0072
0073   /**
0074    * Type of stored entity
0075    */
0076   using entity_type = entity_t;
0077
0078   /**
0079    * The transform type based on the `value_type`
0080    */
0081   using transform_type = Eigen::Transform<value_type, DIM, Eigen::Affine>;
0082
0083   /**
0084    * Strong type to select the correct constructor
0085    */
0086   using Size = NamedType<VertexType, struct SizeParameter>;
0087
0088   /**
0089    * Re-export dimension from template parameter
0090    */
0091   static const std::size_t dim = DIM;
0092
0093   /**
0094    * Copy constructor from other bounding box.
0095    * @param other The other AABB
0096    */
0097   AxisAlignedBoundingBox(const self_t& other) = default;
0098
0099   /**
0100    * Copy assignment operator from other bounding box.
0101    * @param other The other AABB
0102    */
0103   AxisAlignedBoundingBox& operator=(const self_t& other) = default;
0104
0105   /**
0106    * Constructor from an entity pointer, and the min and max vertices.
0107    * @param entity The entity to store
0108    * @param vmin The minimum vertex.
0109    * @param vmax The maximum vertex.
0110    */
0111   AxisAlignedBoundingBox(const entity_t* entity, const VertexType& vmin,
0112                          const VertexType& vmax);
0113
0114   /**
0115    * Constructor from a center position, and a width and height.
0116    * @param entity The entity to store
0117    * @param center The center position
0118    * @param size The size (width and height) of the box.
0119    * @note The special type @c size is required to disambiguate this constructor
0120    * from the other one above. It is a wrapper around a simple @c Vector3.
0121    */
0122   AxisAlignedBoundingBox(const entity_t* entity, const VertexType& center,
0123                          const Size& size);
0124
0125   /**
0126    * Constructor from a list of child boxes. This box will wrap around all boxes
0127    * contained in @p boxes, and additional envelope can be given.
0128    * @param boxes Vector of child boxes to store in this bounding box.
0129    * @param envelope Envelope that will be added/subtracted to the dimension.
0130    */
0131   AxisAlignedBoundingBox(
0132       const std::vector<self_t*>& boxes,
0133       vertex_array_type envelope = vertex_array_type::Zero());
0134
0135   /**
0136    * Helper function to calculate the size of a bounding box enclosing @p boxes.
0137    * @param boxes The boxes to wrap (const pointers)
0138    * @param envelope Optional envelop to add/subtract to dimension.
0139    * @return Pair of vertices: min and max.
0140    */
0141   static std::pair<VertexType, VertexType> wrap(
0142       const std::vector<const self_t*>& boxes,
0143       vertex_array_type envelope = vertex_array_type::Zero());
0144
0145   /**
0146    * Helper function to calculate the size of a bounding box enclosing @p boxes.
0147    * Overload which accepts non-const boxes in @p boxes.
0148    * @param boxes The boxes to wrap (non-const pointers)
0149    * @param envelope Optional envelop to add/subtract to dimension.
0150    * @return Pair of vertices: min and max.
0151    */
0152   static std::pair<VertexType, VertexType> wrap(
0153       const std::vector<self_t*>& boxes,
0154       vertex_array_type envelope = vertex_array_type::Zero());
0155
0156   /**
0157    * Helper function to calculate the size of a bounding box enclosing @p boxes.
0158    * Overload which accepts a vector in @p boxes which owns the instances
0159    * @param boxes The boxes to wrap (by-value vector)
0160    * @param envelope Optional envelop to add/subtract to dimension.
0161    * @return Pair of vertices: min and max.
0162    */
0163   static std::pair<VertexType, VertexType> wrap(
0164       const std::vector<self_t>& boxes,
0165       vertex_array_type envelope = vertex_array_type::Zero());
0166
0167   /**
0168    * Calculate whether a point is inside this box.
0169    * @param point The point to test.
0170    * @return Whether the point is inside or not.
0171    */
0172   bool intersect(const VertexType& point) const;
0173
0174   /**
0175    * @brief Implements the slab method for Ray/AABB intersections.
0176    *
0177    * See https://tavianator.com/fast-branchless-raybounding-box-intersections/,
0178    * https://tavianator.com/fast-branchless-raybounding-box-intersections-part-2-nans/,
0179    * https://medium.com/@bromanz/another-view-on-the-classic-ray-aabb-intersection-algorithm-for-bvh-traversal-41125138b525
0180    * The original algorithms is described in "Graphics Gems (1990)" [1]
0181    * (https://doi.org/10.1016/B978-0-08-050753-8.50084-X)
0182    *
0183    * @note This implementation may treat parallel rays on any of the slabs
0184    *       as **outside** due to how @c NaNs are handled by Eigen.
0185    *       See http://eigen.tuxfamily.org/bz/show_bug.cgi?id=564
0186    * @param ray The ray to intersect with
0187    * @return Whether the ray intersects this AABB
0188    */
0189   bool intersect(const Ray<value_type, DIM>& ray) const;
0190
0191   /**
0192    * Check if a frustum intersects with this bounding box.
0193    *
0194    * This method implements an algorithm similar to the one described in
0195    * "Optimized View Frustum Culling Algorithms for Bounding Boxes (2012)" [2]
0196    * (https://doi.org/10.1080/10867651.2000.10487517), but drops some of the
0197    * more sophisticated optimization.
0198    *
0199    * @param fr The frustum
0200    * @return Whether the frustum intersects this AABB
0201    */
0202   template <std::size_t sides>
0203   bool intersect(const Frustum<value_type, DIM, sides>& fr) const;
0204
0205   /**
0206    * Set the skip node (bounding box)
0207    * @param skip The target skip node pointer
0208    */
0209   void setSkip(self_t* skip);
0210
0211   /**
0212    * Get the skip node for this box
0213    * @return The skip node pointer
0214    */
0215   const self_t* getSkip() const;
0216
0217   /**
0218    * Get the left child (i.e. the first of the children that are inside this
0219    * bounding box).
0220    * @return The lest most child.
0221    */
0222   const self_t* getLeftChild() const;
0223
0224   /**
0225    * Check whether this node as an associated entity. If it does not have one,
0226    * this is a purely abstract container box.
0227    * @return Whether the box has an entity attached.
0228    */
0229   bool hasEntity() const;
0230
0231   /**
0232    * Return the entity associated with this box. This might be nullptr if there
0233    * is no entity attached.
0234    * @return The entity pointer, might be nullptr
0235    */
0236   const entity_t* entity() const;
0237
0238   /**
0239    * Set the entity associated with with this box.
0240    * @param entity The entity
0241    */
0242   void setEntity(const entity_t* entity);
0243
0244   /**
0245    * Get the center position of this bounding box.
0246    * @return The center position
0247    */
0248   const VertexType& center() const;
0249
0250   /**
0251    * Get the minimum vertex
0252    * @return The minimum vertex
0253    */
0254   const VertexType& min() const;
0255
0256   /**
0257    * Get the maximum vertex
0258    * @return The maximum vertex
0259    */
0260   const VertexType& max() const;
0261
0262   /**
0263    * Write information about this bounding box to a stream.
0264    * @param os The output stream.
0265    * @return The stream given as an argument.
0266    */
0267   std::ostream& toStream(std::ostream& os) const;
0268
0269   /**
0270    * Transforms this bounding box using the given transform. This method
0271    * modifies the box it is called on.
0272    * @param trf The transform
0273    */
0274   void transform(const transform_type& trf);
0275
0276   /**
0277    * Transforms this bounding box using the given transform. This method returns
0278    * a copy of this box, with the transformation applied, and leaves this
0279    * instance unchanged.
0280    * @param trf The transform
0281    * @return The transformed bounding box
0282    */
0283   self_t transformed(const transform_type& trf) const;
0284
0285   /**
0286    * Draw this bounding box using the given visualization helper. This method is
0287    * only available for the 3D case.
0288    * @tparam D (used for SFINAE)
0289    * @param helper The visualization helper to write to
0290    * @param color The color to use for drawing
0291    * @param trf An optional transform to apply first.
0292    */
0293   template <std::size_t D = DIM, std::enable_if_t<D == 3, int> = 0>
0294   void draw(IVisualization3D& helper,
0295             std::array<int, 3> color = {120, 120, 120},
0296             const transform_type& trf = transform_type::Identity()) const;
0297
0298   /**
0299    * Draw this bounding box as SVG. This method is only available for the 2D
0300    * case.
0301    * @tparam D (used for SFINAE)
0302    * @param os The output stream to write to
0303    * @param w The width of the output SVG.
0304    * @param h The height of the output SVG.
0305    * @param unit A scale factor to apply before drawing
0306    * @param label A label to put next to the box.
0307    * @param fillcolor Color to fill the box with.
0308    * @return The outstream given in @p os.
0309    */
0310   template <std::size_t D = DIM, std::enable_if_t<D == 2, int> = 0>
0311   std::ostream& svg(std::ostream& os, value_type w, value_type h,
0312                     value_type unit = 10, const std::string& label = "",
0313                     const std::string& fillcolor = "grey") const;
0314
0315  private:
0316   template <std::size_t D = DIM, std::enable_if_t<D == 2, int> = 0>
0317   std::pair<VertexType, VertexType> transformVertices(
0318       const transform_type& trf) const;
0319
0320   template <std::size_t D = DIM, std::enable_if_t<D == 3, int> = 0>
0321   std::pair<VertexType, VertexType> transformVertices(
0322       const transform_type& trf) const;
0323
0324   const entity_t* m_entity;
0325   VertexType m_vmin;
0326   VertexType m_vmax;
0327   VertexType m_center;
0328   vertex_array_type m_width;
0329   vertex_array_type m_iwidth;
0330
0331   self_t* m_left_child{nullptr};
0332   self_t* m_right_child{nullptr};
0333   self_t* m_skip{nullptr};
0334 };
0335
0336 /**
0337  * Build an octree from a list of bounding boxes.
0338  * @note @p store and @p prims do not need to contain the same objects. @p store
0339  * is only used to pass ownership back to the caller while preserving memory
0340  * location.
0341  * @tparam box_t Works will all box types.
0342  * @param store Owns the created boxes by means of `std::unique_ptr`.
0343  * @param prims Boxes to store. This is a read only vector.
0344  * @param max_depth No subdivisions beyond this level.
0345  * @param envelope1 Envelope to add/subtract to dimensions in all directions.
0346  * @return Pointer to the top most bounding box, containing the entire octree
0347  */
0348 template <typename box_t>
0349 box_t* make_octree(std::vector<std::unique_ptr<box_t>>& store,
0350                    const std::vector<box_t*>& prims, std::size_t max_depth = 1,
0351                    typename box_t::value_type envelope1 = 0);
0352
0353 /**
0354  * Overload of the << operator for bounding boxes.
0355  * @tparam T entity type
0356  * @tparam U value type
0357  * @tparam V dimension
0358  * @param os The output stream
0359  * @param box The bounding box
0360  * @return The given output stream.
0361  */
0362 template <typename T, typename U, std::size_t V>
0363 std::ostream& operator<<(std::ostream& os,
0364                          const AxisAlignedBoundingBox<T, U, V>& box);
0365
0366 }  // namespace Acts
0367
0368 #include "Acts/Utilities/BoundingBox.ipp"