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