Acts/Seeding/SeedFinderOrthogonal.hpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 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 https://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include "Acts/EventData/SpacePointMutableData.hpp"
0012 #include "Acts/Seeding/SeedFilter.hpp"
0013 #include "Acts/Seeding/SeedFinderConfig.hpp"
0014 #include "Acts/Seeding/SeedFinderOrthogonalConfig.hpp"
0015 #include "Acts/Utilities/KDTree.hpp"
0016 #include "Acts/Utilities/Logger.hpp"
0017
0018 #include <array>
0019 #include <iostream>
0020 #include <list>
0021 #include <map>
0022 #include <memory>
0023 #include <set>
0024 #include <string>
0025 #include <utility>
0026 #include <vector>
0027
0028 namespace Acts {
0029 template <typename external_spacepoint_t>
0030 class SeedFinderOrthogonal {
0031  public:
0032   /**
0033    * @brief Set the number of dimensions in which to embed points. This is just
0034    * 3 for now (phi, r, and z), but we might want to increase or decrease this
0035    * number in the future.
0036    */
0037   static constexpr std::size_t NDims = 3;
0038
0039   /**
0040    * @brief The seed type used by this seeder internally.
0041    */
0042   using seed_t = Seed<external_spacepoint_t>;
0043
0044   /**
0045    * @brief The k-d tree type used by this seeder internally, which is
0046    * three-dimensional, contains internal spacepoint pointers, uses the Acts
0047    * scalar type for coordinates, stores its coordinates in std::arrays, and
0048    * has leaf size 4.
0049    */
0050   using tree_t =
0051       KDTree<NDims, const external_spacepoint_t *, double, std::array, 4>;
0052
0053   /**
0054    * @brief Construct a new orthogonal seed finder.
0055    *
0056    * @param config The configuration parameters for this seed finder.
0057    * @param logger The ACTS logger.
0058    */
0059   SeedFinderOrthogonal(
0060       const Acts::SeedFinderOrthogonalConfig<external_spacepoint_t> &config,
0061       std::unique_ptr<const Acts::Logger> logger =
0062           Acts::getDefaultLogger("Finder", Logging::Level::INFO));
0063   /**
0064    * @brief Destroy the orthogonal seed finder object.
0065    */
0066   ~SeedFinderOrthogonal() = default;
0067
0068   SeedFinderOrthogonal() = default;
0069   SeedFinderOrthogonal(const SeedFinderOrthogonal<external_spacepoint_t> &) =
0070       delete;
0071   SeedFinderOrthogonal<external_spacepoint_t> &operator=(
0072       const SeedFinderOrthogonal<external_spacepoint_t> &) = delete;
0073   SeedFinderOrthogonal(
0074       SeedFinderOrthogonal<external_spacepoint_t> &&) noexcept = default;
0075   SeedFinderOrthogonal<external_spacepoint_t> &operator=(
0076       SeedFinderOrthogonal<external_spacepoint_t> &&) noexcept = default;
0077
0078   /**
0079    * @brief Perform seed finding, appending seeds to a container.
0080    *
0081    * This method performs seed finding through an orthogonal range search
0082    * strategy. This strategy differs from binning approaches because it selects
0083    * seeds _constructively_ rather than _destructively_; instead of trying a
0084    * large number of possible space point combinations and then rejecting many
0085    * of them, this algorithm tries to only consider valid seed candidates to
0086    * reduce combinatorics.
0087    *
0088    * In addition, this algorithm replaces the binning step used in other seed
0089    * finding algorithms with the construction of a k-d tree, which allows us to
0090    * efficiently search for space points within a given range.
0091    *
0092    * The core idea behind this algorithm is to create axis-aligned bounding
0093    * boxes around the region of validity for a seed candidate (be it a bottom
0094    * spacepoint for a given middle, a top for a given middle, a middle for a
0095    * given bottom, or any other combination), and then searching the detector
0096    * volume for points that lie inside that AABB.
0097    *
0098    * @tparam input_container_t The type of the input spacepoint container.
0099    * @tparam output_container_t The type of the output seed container.
0100    *
0101    * @param options frequently changing configuration (like beam position)
0102    * @param spacePoints The input spacepoints from which to create seeds.
0103    * @param out_cont The output container to write seeds to.
0104    * covariance of the external space point
0105    */
0106   template <typename input_container_t, typename output_container_t>
0107   void createSeeds(const Acts::SeedFinderOptions &options,
0108                    const input_container_t &spacePoints,
0109                    output_container_t &out_cont) const;
0110
0111   /**
0112    * @brief Perform seed finding, returning a new container of seeds.
0113    *
0114    * This is a filterCandidates method for scenarios where a non-inserter API is
0115    * more ergonomic. In general, the inserter-based method should be preferred
0116    * as it is more flexible and usually more performant. For more information
0117    * about the seeding algorithm, please see that function.
0118    *
0119    * @tparam input_container_t The type of the input spacepoint container.
0120    * @param options frequently changing configuration (like beam position)
0121    * @param spacePoints The input spacepoints from which to create seeds.
0122    * covariance of the external space point
0123    *
0124    * @return A vector of seeds.
0125    */
0126   template <typename input_container_t>
0127   std::vector<seed_t> createSeeds(const Acts::SeedFinderOptions &options,
0128                                   const input_container_t &spacePoints) const;
0129
0130  private:
0131   /**
0132    * @brief Enumeration of the different dimensions in which we can apply cuts.
0133    */
0134   enum Dim { DimPhi = 0, DimR = 1, DimZ = 2 };
0135
0136   /**
0137    * @brief Return the AABB rearch range for a given spacepoint, searching
0138    * upwards.
0139    *
0140    * This function calculates an axis-aligned bounding box around the volume of
0141    * validity for the next spacepoint in a pair, given that the lower
0142    * spacepoint is given. Thus, this method either takes a bottom spacepoint
0143    * and returns a range for the middle spacepoint, or it takes a middle
0144    * spacepoint and returns the range for the top spacepoint.
0145    *
0146    * @param low The lower spacepoint to find a partner for.
0147    *
0148    * @return An N-dimensional axis-aligned search range.
0149    */
0150   typename tree_t::range_t validTupleOrthoRangeLH(
0151       const external_spacepoint_t &low) const;
0152
0153   /**
0154    * @brief Return the AABB rearch range for a given spacepoint, searching
0155    * downward.
0156    *
0157    * This function calculates an axis-aligned bounding box around the volume of
0158    * validity for the next spacepoint in a pair, given that the upper
0159    * spacepoint is given. Thus, this method either takes a middle spacepoint
0160    * and returns a range for the bottom spacepoint, or it takes a top
0161    * spacepoint and returns the range for the middle spacepoint.
0162    *
0163    * @param high The upper spacepoint to find a partner for.
0164    *
0165    * @return An N-dimensional axis-aligned search range.
0166    */
0167   typename tree_t::range_t validTupleOrthoRangeHL(
0168       const external_spacepoint_t &high) const;
0169
0170   /**
0171    * @brief Check whether two spacepoints form a valid tuple.
0172    *
0173    * This method checks whether the cuts that we have for pairs of space points
0174    * hold.
0175    *
0176    * @warning This method checks ONLY those constraints that cannot be exactly
0177    * represented as bounding boxes. Thus, this method should not be used on
0178    * pairs of points that were not generated using a constrained spatial search
0179    * strategy.
0180    *
0181    * @param options frequently changing configuration (like beam position)
0182    * @param low The lower spacepoint.
0183    * @param high The upper spacepoint.
0184    * @param isMiddleInverted If middle spacepoint is in the negative z region
0185    *
0186    * @return True if the two points form a valid pair, false otherwise.
0187    */
0188   bool validTuple(const SeedFinderOptions &options,
0189                   const external_spacepoint_t &low,
0190                   const external_spacepoint_t &high,
0191                   bool isMiddleInverted) const;
0192
0193   /**
0194    * @brief Create a k-d tree from a set of spacepoints.
0195    *
0196    * @param spacePoints The spacepoints to create a tree from.
0197    *
0198    * @return A k-d tree containing the given spacepoints.
0199    */
0200   tree_t createTree(
0201       const std::vector<const external_spacepoint_t *> &spacePoints) const;
0202
0203   /**
0204    * @brief Filter potential candidate pairs, and output seeds into an
0205    * iterator.
0206    *
0207    * @param options frequently changing configuration (like beam position)
0208    * @param mutableData Container for mutable variables used in the seeding
0209    * @param middle The (singular) middle spacepoint.
0210    * @param bottom The (vector of) candidate bottom spacepoints.
0211    * @param top The (vector of) candidate top spacepoints.
0212    * @param seedFilterState  holds quantities used in seed filter
0213    * @param candidates_collector The container to write the resulting
0214    * seed candidates to.
0215    */
0216   void filterCandidates(
0217       const SeedFinderOptions &options,
0218       Acts::SpacePointMutableData &mutableData,
0219       const external_spacepoint_t &middle,
0220       const std::vector<const external_spacepoint_t *> &bottom,
0221       const std::vector<const external_spacepoint_t *> &top,
0222       SeedFilterState seedFilterState,
0223       CandidatesForMiddleSp<const external_spacepoint_t> &candidates_collector)
0224       const;
0225
0226   /**
0227    * @brief Search for seeds starting from a given middle space point.
0228    *
0229    * @param options frequently changing configuration (like beam position)
0230    * @param mutableData Container for mutable variables used in the seeding
0231    * @tparam NDims Number of dimensions for our spatial embedding (probably 3).
0232    * @tparam output_container_t Type of the output container.
0233    *
0234    * @param tree The k-d tree to use for searching.
0235    * @param out_cont The container write output seeds to.
0236    * @param middle_p The middle spacepoint to find seeds for.
0237    */
0238   template <typename output_container_t>
0239   void processFromMiddleSP(const SeedFinderOptions &options,
0240                            Acts::SpacePointMutableData &mutableData,
0241                            const tree_t &tree, output_container_t &out_cont,
0242                            const typename tree_t::pair_t &middle_p) const;
0243
0244   /**
0245    * @brief The configuration for the seeding algorithm.
0246    */
0247   Acts::SeedFinderOrthogonalConfig<external_spacepoint_t> m_config;
0248
0249   /**
0250    * @brief Get the logger.
0251    */
0252   const Logger &logger() const { return *m_logger; }
0253
0254   /**
0255    * @brief The logger
0256    */
0257   std::unique_ptr<const Acts::Logger> m_logger{getDummyLogger().clone()};
0258 };
0259 }  // namespace Acts
0260
0261 #include "Acts/Seeding/SeedFinderOrthogonal.ipp"