src/Seeding/TripletSeeder.cpp

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 #include "Acts/Seeding/TripletSeeder.hpp"
0010
0011 #include "Acts/EventData/SpacePointContainer.hpp"
0012 #include "Acts/Seeding/DoubletSeedFinder.hpp"
0013 #include "Acts/Seeding/TripletSeedFinder.hpp"
0014
0015 #include <Eigen/Dense>
0016
0017 namespace Acts {
0018
0019 namespace {
0020
0021 template <typename DoubletCollections>
0022 void createAndFilterTriplets(TripletSeeder::Cache& cache,
0023                              const TripletSeedFinder& tripletFinder,
0024                              const ITripletSeedFilter& filter,
0025                              const SpacePointContainer& spacePoints,
0026                              DoubletCollections bottomDoublets,
0027                              const ConstSpacePointProxy& spM,
0028                              DoubletCollections topDoublets) {
0029   for (auto bottomDoublet : bottomDoublets) {
0030     if (topDoublets.empty()) {
0031       break;
0032     }
0033
0034     cache.tripletTopCandidates.clear();
0035     tripletFinder.createTripletTopCandidates(spacePoints, spM, bottomDoublet,
0036                                              topDoublets,
0037                                              cache.tripletTopCandidates);
0038
0039     filter.filterTripletTopCandidates(spacePoints, spM, bottomDoublet,
0040                                       cache.tripletTopCandidates);
0041   }
0042 }
0043
0044 template <typename SpacePointCollections>
0045 void createSeedsFromGroupsImpl(
0046     const Logger& logger, TripletSeeder::Cache& cache,
0047     const DoubletSeedFinder& bottomFinder, const DoubletSeedFinder& topFinder,
0048     const TripletSeedFinder& tripletFinder, const ITripletSeedFilter& filter,
0049     const SpacePointContainer& spacePoints,
0050     SpacePointCollections& bottomSpGroups, const ConstSpacePointProxy& middleSp,
0051     SpacePointCollections& topSpGroups, SeedContainer& outputSeeds) {
0052   MiddleSpInfo middleSpInfo = DoubletSeedFinder::computeMiddleSpInfo(middleSp);
0053
0054   // create middle-top doublets
0055   cache.topDoublets.clear();
0056   for (auto& topSpGroup : topSpGroups) {
0057     topFinder.createDoublets(middleSp, middleSpInfo, topSpGroup,
0058                              cache.topDoublets);
0059   }
0060
0061   // no top SP found -> cannot form any triplet
0062   if (cache.topDoublets.empty()) {
0063     ACTS_VERBOSE("No compatible Tops, returning");
0064     return;
0065   }
0066
0067   if (!filter.sufficientTopDoublets(spacePoints, middleSp, cache.topDoublets)) {
0068     return;
0069   }
0070
0071   // create middle-bottom doublets
0072   cache.bottomDoublets.clear();
0073   for (auto& bottomSpGroup : bottomSpGroups) {
0074     bottomFinder.createDoublets(middleSp, middleSpInfo, bottomSpGroup,
0075                                 cache.bottomDoublets);
0076   }
0077
0078   // no bottom SP found -> cannot form any triplet
0079   if (cache.bottomDoublets.empty()) {
0080     ACTS_VERBOSE("No compatible Bottoms, returning");
0081     return;
0082   }
0083
0084   ACTS_VERBOSE("Candidates: " << cache.bottomDoublets.size() << " bottoms and "
0085                               << cache.topDoublets.size()
0086                               << " tops for middle candidate indexed "
0087                               << middleSp.index());
0088
0089   // combine doublets to triplets
0090   if (tripletFinder.config().sortedByCotTheta) {
0091     cache.bottomDoublets.sortByCotTheta({0, cache.bottomDoublets.size()},
0092                                         cache.sortedBottoms);
0093     cache.topDoublets.sortByCotTheta({0, cache.topDoublets.size()},
0094                                      cache.sortedTops);
0095
0096     createAndFilterTriplets(cache, tripletFinder, filter, spacePoints,
0097                             cache.bottomDoublets.subset(cache.sortedBottoms),
0098                             middleSp,
0099                             cache.topDoublets.subset(cache.sortedTops));
0100   } else {
0101     createAndFilterTriplets(cache, tripletFinder, filter, spacePoints,
0102                             cache.bottomDoublets.range(), middleSp,
0103                             cache.topDoublets.range());
0104   }
0105
0106   filter.filterTripletsMiddleFixed(spacePoints, outputSeeds);
0107 }
0108
0109 }  // namespace
0110
0111 TripletSeeder::TripletSeeder(std::unique_ptr<const Logger> logger_)
0112     : m_logger(std::move(logger_)) {
0113   if (m_logger == nullptr) {
0114     throw std::invalid_argument("TripletSeeder: logger cannot be null");
0115   }
0116 }
0117
0118 void TripletSeeder::createSeedsFromGroup(
0119     Cache& cache, const DoubletSeedFinder& bottomFinder,
0120     const DoubletSeedFinder& topFinder, const TripletSeedFinder& tripletFinder,
0121     const ITripletSeedFilter& filter, const SpacePointContainer& spacePoints,
0122     SpacePointContainer::ConstSubset& bottomSps,
0123     const ConstSpacePointProxy& middleSp,
0124     SpacePointContainer::ConstSubset& topSps,
0125     SeedContainer& outputSeeds) const {
0126   assert((bottomFinder.config().spacePointsSortedByRadius ==
0127           topFinder.config().spacePointsSortedByRadius) &&
0128          "Inconsistent space point sorting");
0129
0130   std::array<SpacePointContainer::ConstSubset, 1> bottomSpGroups{bottomSps};
0131   std::array<SpacePointContainer::ConstSubset, 1> topSpGroups{topSps};
0132
0133   createSeedsFromGroupsImpl(*m_logger, cache, bottomFinder, topFinder,
0134                             tripletFinder, filter, spacePoints, bottomSpGroups,
0135                             middleSp, topSpGroups, outputSeeds);
0136 }
0137
0138 void TripletSeeder::createSeedsFromGroups(
0139     Cache& cache, const DoubletSeedFinder& bottomFinder,
0140     const DoubletSeedFinder& topFinder, const TripletSeedFinder& tripletFinder,
0141     const ITripletSeedFilter& filter, const SpacePointContainer& spacePoints,
0142     const std::span<SpacePointContainer::ConstRange>& bottomSpGroups,
0143     const SpacePointContainer::ConstRange& middleSpGroup,
0144     const std::span<SpacePointContainer::ConstRange>& topSpGroups,
0145     const std::pair<float, float>& radiusRangeForMiddle,
0146     SeedContainer& outputSeeds) const {
0147   assert((bottomFinder.config().spacePointsSortedByRadius ==
0148           topFinder.config().spacePointsSortedByRadius) &&
0149          "Inconsistent space point sorting");
0150   const bool spacePointsSortedByRadius =
0151       bottomFinder.config().spacePointsSortedByRadius;
0152
0153   if (middleSpGroup.empty()) {
0154     return;
0155   }
0156
0157   if (spacePointsSortedByRadius) {
0158     // Initialize initial offsets for bottom and top space points with binary
0159     // search. This requires at least one middle space point to be present which
0160     // is already checked above.
0161     const ConstSpacePointProxy firstMiddleSp = middleSpGroup.front();
0162     const float firstMiddleSpR = firstMiddleSp.zr()[1];
0163
0164     for (auto& bottomSpGroup : bottomSpGroups) {
0165       // Find the first bottom space point that is within the deltaRMax of the
0166       // first middle space point.
0167       const auto low = std::ranges::lower_bound(
0168           bottomSpGroup, firstMiddleSpR - bottomFinder.config().deltaRMax, {},
0169           [&](const ConstSpacePointProxy& sp) { return sp.zr()[1]; });
0170       bottomSpGroup = bottomSpGroup.subrange(low - bottomSpGroup.begin());
0171     }
0172
0173     for (auto& topSpGroup : topSpGroups) {
0174       // Find the first top space point that is within the deltaRMin of the
0175       // first middle space point.
0176       const auto low = std::ranges::lower_bound(
0177           topSpGroup, firstMiddleSpR + topFinder.config().deltaRMin, {},
0178           [&](const ConstSpacePointProxy& sp) { return sp.zr()[1]; });
0179       topSpGroup = topSpGroup.subrange(low - topSpGroup.begin());
0180     }
0181   }
0182
0183   for (ConstSpacePointProxy spM : middleSpGroup) {
0184     const float rM = spM.zr()[1];
0185
0186     if (spacePointsSortedByRadius) {
0187       // check if spM is outside our radial region of interest
0188       if (rM < radiusRangeForMiddle.first) {
0189         continue;
0190       }
0191       if (rM > radiusRangeForMiddle.second) {
0192         // break because SPs are sorted in r
0193         break;
0194       }
0195     }
0196
0197     createSeedsFromGroupsImpl(*m_logger, cache, bottomFinder, topFinder,
0198                               tripletFinder, filter, spacePoints,
0199                               bottomSpGroups, spM, topSpGroups, outputSeeds);
0200   }
0201 }
0202
0203 }  // namespace Acts