Acts/Seeding/SeedFinderOrthogonal.hpp

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