detray/navigation/caching_navigator.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 // Project include(s)
0012 #include "detray/definitions/algorithms.hpp"
0013 #include "detray/definitions/detail/qualifiers.hpp"
0014 #include "detray/definitions/indexing.hpp"
0015 #include "detray/definitions/navigation.hpp"
0016 #include "detray/definitions/units.hpp"
0017 #include "detray/geometry/surface.hpp"
0018 #include "detray/navigation/detail/navigation_functions.hpp"
0019 #include "detray/navigation/intersection/intersection.hpp"
0020 #include "detray/navigation/intersection/ray_intersector.hpp"
0021 #include "detray/navigation/navigation_config.hpp"
0022 #include "detray/navigation/navigation_state.hpp"
0023 #include "detray/navigation/navigator_base.hpp"
0024 #include "detray/utils/logging.hpp"
0025
0026 namespace detray {
0027
0028 namespace navigation {
0029
0030 static constexpr std::size_t default_cache_size{8u};
0031
0032 }  // namespace navigation
0033
0034 /// @brief Navigation class which caches a 'road' through the detector
0035 ///
0036 /// This navigator applies a trust level based update of its candidate
0037 /// (intersection) cache, which is kept in the naviagtor's state. The trust
0038 /// level, and with it the appropriate update policy, must be set by an actor,
0039 /// otherwise no update will be performed.
0040 ///
0041 /// @tparam detector_t the detector to navigate
0042 /// @tparam k_cache_capacity the capacity of the candidate cache
0043 /// @tparam inspector_t is a validation inspector that can record information
0044 ///         about the navigation state at different points of the nav. flow.
0045 /// @tparam intersection_t candidate type
0046 template <typename detector_t,
0047           std::size_t k_cache_capacity = navigation::default_cache_size,
0048           typename inspector_t = navigation::void_inspector,
0049           typename intersection_t = intersection2D<
0050               typename detector_t::surface_type,
0051               typename detector_t::algebra_type, !intersection::contains_pos>>
0052 class caching_navigator
0053     : public navigator_base<caching_navigator<detector_t, k_cache_capacity,
0054                                               inspector_t, intersection_t>> {
0055   friend class navigator_base<caching_navigator>;
0056
0057   using scalar_t = dscalar<typename detector_t::algebra_type>;
0058
0059  public:
0060   using detector_type = detector_t;
0061   using context_type = typename detector_type::geometry_context;
0062   using intersection_type = intersection_t;
0063   using inspector_type = inspector_t;
0064
0065   /// @brief Navigation state that contains a cache of candidates
0066   ///
0067   /// Once a volume is reached, the cache is filled by building a 'road' of
0068   /// surfaces that will likely be encountered by the track in that volume.
0069   /// The cache keeps a range of reachable candidates that lie between the
0070   /// next and last index in the cache. The cache is sorted by distance
0071   /// to the track position.
0072   class state
0073       : public navigation::base_state<state, detector_type, k_cache_capacity,
0074                                       inspector_type, intersection_type> {
0075     // Allow the navigator classes to access methods that update the state
0076     friend class caching_navigator;
0077     friend class navigator_base<caching_navigator>;
0078
0079     // Allow the filling/updating of candidates
0080     friend struct detail::intersection_initialize<ray_intersector>;
0081     friend struct detail::intersection_update<ray_intersector>;
0082
0083     // Navigation utility functions that need to modify the state
0084     friend struct navigation::candidate_search;
0085
0086     template <typename state_t>
0087     friend constexpr void navigation::update_status(state_t &,
0088                                                     const navigation::config &);
0089
0090     template <typename track_t, typename state_t, typename ctx_t>
0091     friend constexpr void navigation::local_navigation(
0092         const track_t &, state_t &, const navigation::config &, const ctx_t &,
0093         const bool);
0094
0095     template <typename track_t, typename state_t, typename ctx_t>
0096     friend constexpr void navigation::volume_switch(const track_t &, state_t &,
0097                                                     const navigation::config &,
0098                                                     const ctx_t &);
0099
0100     template <typename track_t, typename state_t, typename ctx_t>
0101     friend constexpr void navigation::init_loose_cfg(const track_t &, state_t &,
0102                                                      navigation::config,
0103                                                      const ctx_t &);
0104     using base_type =
0105         navigation::base_state<state, detector_type, k_cache_capacity,
0106                                inspector_type, intersection_type>;
0107
0108     // Result of a geometry object evaluation
0109     using candidate_t = typename base_type::candidate_t;
0110     using candidate_cache_t = typename base_type::candidate_cache_t;
0111     using candidate_itr_t = typename base_type::candidate_itr_t;
0112     using candidate_const_itr_t = typename base_type::candidate_const_itr_t;
0113     using dist_t = typename base_type::dist_t;
0114
0115    public:
0116     using value_type = candidate_t;
0117
0118     using view_type = detail::get_view_t<inspector_t>;
0119     using const_view_type = detail::get_view_t<const inspector_t>;
0120
0121     /// Use common methods of constructing a nvaigation state
0122     using base_type::base_type;
0123
0124     /// Update navigation trust level to high trust
0125     DETRAY_HOST_DEVICE
0126     constexpr void set_high_trust() {
0127       DETRAY_VERBOSE_HOST_DEVICE("Flagging re-navigation: \"high trust\"");
0128       this->trust_level(this->trust_level() < navigation::trust_level::e_high
0129                             ? this->trust_level()
0130                             : navigation::trust_level::e_high);
0131     }
0132
0133     /// Update navigation trust level to fair trust
0134     DETRAY_HOST_DEVICE
0135     constexpr void set_fair_trust() {
0136       DETRAY_VERBOSE_HOST_DEVICE("Flagging re-navigation: \"fair trust\"");
0137       this->trust_level(this->trust_level() < navigation::trust_level::e_fair
0138                             ? this->trust_level()
0139                             : navigation::trust_level::e_fair);
0140     }
0141
0142    private:
0143     /// Insert a new element @param new_candidate before position @param pos
0144     DETRAY_HOST_DEVICE
0145     constexpr void insert(candidate_const_itr_t pos,
0146                           const intersection_type &new_candidate) {
0147       // Candidate is too far away to be placed in cache
0148       if (pos == this->candidates().end()) {
0149         return;
0150       }
0151
0152       assert(detail::is_invalid_value(new_candidate.volume_link()) ||
0153              new_candidate.volume_link() < this->detector().volumes().size());
0154
0155       // Insert the first candidate
0156       if (this->n_candidates() == 0) [[unlikely]] {
0157         this->candidates()[0] = new_candidate;
0158         this->last_index(this->last_index() + 1);
0159         assert(this->next_index() <= this->last_index() + 1);
0160         assert(static_cast<std::size_t>(this->last_index()) < k_cache_capacity);
0161         return;
0162       }
0163
0164       // Position where to insert the new candidate
0165       auto idx{static_cast<dist_t>(
0166           detray::ranges::distance(this->candidates().cbegin(), pos))};
0167       assert(idx >= 0);
0168
0169       // Do not add the same surface (intersection) multiple times
0170       const auto is_overlap_at_pos = [this, &new_candidate](std::size_t index) {
0171         return (math::fabs(this->candidates()[index].path() -
0172                            new_candidate.path()) <= 1.f * unit<scalar_t>::um);
0173       };
0174
0175       // Do not add the same surface (intersection) multiple times
0176       const auto is_clash_at_pos = [this, &new_candidate,
0177                                     &is_overlap_at_pos](std::size_t index) {
0178         return (this->candidates()[index].surface().identifier() ==
0179                 new_candidate.surface().identifier()) &&
0180                is_overlap_at_pos(index);
0181       };
0182
0183       const auto idxu{static_cast<std::size_t>(idx)};
0184       if (is_clash_at_pos(idxu) || ((idxu > 0u) && is_clash_at_pos(idxu - 1u)))
0185           [[unlikely]] {
0186         return;
0187       }
0188
0189       // Shift all following candidates and evict the last element,
0190       // if the cache is already full
0191       constexpr auto shift_max{static_cast<dist_t>(k_cache_capacity - 2)};
0192       const dist_t shift_begin{math::min(this->last_index(), shift_max)};
0193
0194       // In case of overlaps, prefer sensitives over portals and
0195       // direct hits over edge hits
0196       if (is_overlap_at_pos(idxu) &&
0197           (new_candidate.is_edge() || new_candidate.surface().is_portal())) {
0198         // Don't shift the overlapping candidate and put the new
0199         // candidate behind it
0200         idx++;
0201         idx = idx > shift_begin ? shift_begin : idx;
0202       }
0203
0204       for (dist_t i = shift_begin; i >= idx; --i) {
0205         const auto j{static_cast<std::size_t>(i)};
0206         this->candidates()[j + 1u] = this->candidates()[j];
0207       }
0208
0209       // Now insert the new candidate and update candidate range
0210       this->candidates()[static_cast<std::size_t>(idx)] = new_candidate;
0211       this->last_index(math::min(static_cast<dist_t>(this->last_index() + 1),
0212                                  static_cast<dist_t>(k_cache_capacity - 1)));
0213
0214       assert(this->next_index() <= this->last_index() + 1);
0215       assert(static_cast<std::size_t>(this->last_index()) < k_cache_capacity);
0216     }
0217
0218     /// Clear the state
0219     DETRAY_HOST_DEVICE constexpr void clear_cache() {
0220       base_type::clear_cache();
0221       this->next_index(0);
0222       this->last_index(-1);
0223     }
0224   };
0225
0226  private:
0227   /// Helper method to update the candidates (surface intersections)
0228   /// based on an externally provided trust level. Will (re-)initialize the
0229   /// navigation if there is no trust.
0230   ///
0231   /// @tparam track_t type of track, needs to provide pos() and dir() methods
0232   ///
0233   /// @param track access to the track parameters
0234   /// @param state the current navigation state
0235   /// @param cfg the navigation configuration
0236   /// @param ctx the geometry context
0237   template <typename track_t>
0238   DETRAY_HOST_DEVICE constexpr bool update_impl(const track_t &track,
0239                                                 state &navigation,
0240                                                 const navigation::config &cfg,
0241                                                 const context_type &ctx) const {
0242     const auto &det = navigation.detector();
0243     constexpr bool is_init{true};
0244
0245     assert(navigation.trust_level() != navigation::trust_level::e_full);
0246
0247     // Update only the current candidate and the corresponding next target
0248     // - do this only when the navigation state is still coherent
0249     if (navigation.trust_level() == navigation::trust_level::e_high) {
0250       DETRAY_VERBOSE_HOST_DEVICE("Called 'update()' - high trust");
0251
0252       // Update next candidate: If not reachable, 'high trust' is broken
0253       if (!navigation::update_candidate(
0254               navigation.direction(), navigation.target(), track, det,
0255               cfg.intersection, navigation.external_tol(), ctx)) {
0256         DETRAY_VERBOSE_HOST_DEVICE(
0257             "-> Candidate not reachable! High trust broken:");
0258
0259         navigation.status(navigation::status::e_unknown);
0260         // This will run into the fair trust case below.
0261         navigation.set_fair_trust();
0262       } else {
0263         // Update navigation flow on the new candidate information
0264         navigation::update_status(navigation, cfg);
0265
0266         navigation.run_inspector(cfg, track.pos(), track.dir(),
0267                                  "Update complete: high trust: ");
0268
0269         // The work is done if: the track has not reached a surface yet
0270         // or trust is gone (portal was reached or the cache is broken).
0271         if (navigation.status() == navigation::status::e_towards_object ||
0272             navigation.is_on_portal()) {
0273           if (navigation.status() == navigation::status::e_towards_object) {
0274             DETRAY_VERBOSE_HOST_DEVICE("-> Towards surface: %d",
0275                                        navigation.next_surface().index());
0276           } else {
0277             DETRAY_VERBOSE_HOST_DEVICE("-> On portal: idx %d",
0278                                        navigation.current_surface().index());
0279           }
0280           return !is_init;
0281         }
0282         // Else (if full trust): Track is on non-portal surface and
0283         // cache is not exhausted. Ready the next target
0284         if (navigation.trust_level() == navigation::trust_level::e_full &&
0285             navigation::update_candidate(
0286                 navigation.direction(), navigation.target(), track, det,
0287                 cfg.intersection, navigation.external_tol(), ctx)) {
0288           DETRAY_VERBOSE_HOST_DEVICE(
0289               "-> On non-portal surface (idx %d) and next candidate "
0290               "in cache is reachable",
0291               navigation.current_surface().index());
0292           return !is_init;
0293         }
0294         DETRAY_VERBOSE_HOST_DEVICE(
0295             "-> Next candidate no longer reachable: High trust broken");
0296
0297         // If next candidate is not reachable, don't 'return', but
0298         // escalate the trust level.
0299         // This will run into the fair trust case below or the no trust
0300         // case if the cache is broken
0301         navigation.set_fair_trust();
0302       }
0303     }
0304     // Re-evaluate all currently available candidates and sort again
0305     // - do this when your navigation state is stale, but not invalid
0306     if (navigation.trust_level() == navigation::trust_level::e_fair &&
0307         !navigation.cache_exhausted()) {
0308       DETRAY_VERBOSE_HOST_DEVICE("Called 'update()' - fair trust");
0309
0310       for (auto &candidate : navigation) {
0311         // Disregard this candidate if it is not reachable
0312         if (!navigation::update_candidate(navigation.direction(), candidate,
0313                                           track, det, cfg.intersection,
0314                                           navigation.external_tol(), ctx)) {
0315           // Forcefully set dist to numeric max for sorting
0316           candidate.set_path(std::numeric_limits<scalar_t>::max());
0317         }
0318       }
0319       detray::sequential_sort(navigation.begin(), navigation.end());
0320       // Take the nearest (sorted) candidate first
0321       navigation.set_next(navigation.begin());
0322       // Ignore unreachable elements (needed to determine exhaustion)
0323       navigation.set_last(find_invalid(navigation.candidates()));
0324       // Update navigation flow on the new candidate information
0325       navigation::update_status(navigation, cfg);
0326
0327       navigation.run_inspector(cfg, track.pos(), track.dir(),
0328                                "Update complete: fair trust: ");
0329
0330       // If there are no reachable candidates in the cache after
0331       // re-evaluation, re-initialize the volume
0332       if (navigation.cache_exhausted()) {
0333         navigation.set_no_trust();
0334       }
0335     }
0336     // Re-initialize the volume (actor flagged 'no trust' or previous trust
0337     // level update failed)
0338     if (navigation.trust_level() == navigation::trust_level::e_no_trust) {
0339       DETRAY_VERBOSE_HOST_DEVICE("Called 'update()' - no trust");
0340
0341       constexpr bool resolve_overstepping{true};
0342       navigation::local_navigation(track, navigation, cfg, ctx,
0343                                    resolve_overstepping);
0344       return is_init;
0345     }
0346
0347     return !is_init;
0348   }
0349
0350   /// Helper to evict all unreachable/invalid candidates from the cache:
0351   /// Finds the first unreachable candidate (has been invalidated during
0352   /// update) in a sorted (!) cache.
0353   ///
0354   /// @param candidates the cache of candidates to be cleaned
0355   ///
0356   /// @returns iterator to the last reachable candidate
0357   DETRAY_HOST_DEVICE constexpr auto find_invalid(
0358       const typename state::candidate_cache_t &candidates) const {
0359     // Depends on previous invalidation of unreachable candidates!
0360     auto not_reachable = [](const intersection_type &candidate) {
0361       return candidate.path() == std::numeric_limits<scalar_t>::max();
0362     };
0363
0364     return detray::find_if(candidates.begin(), candidates.end(), not_reachable);
0365   }
0366 };
0367
0368 }  // namespace detray