clusterization/details/sparse_ccl.hpp

0001 /** TRACCC library, part of the ACTS project (R&D line)
0002  *
0003  * (c) 2021-2024 CERN for the benefit of the ACTS project
0004  *
0005  * Mozilla Public License Version 2.0
0006  */
0007
0008 #pragma once
0009
0010 // Library include(s).
0011 #include "traccc/definitions/qualifiers.hpp"
0012 #include "traccc/edm/silicon_cell_collection.hpp"
0013 #include "traccc/geometry/detector_conditions_description.hpp"
0014
0015 // VecMem include(s).
0016 #include <vecmem/containers/device_vector.hpp>
0017
0018 namespace traccc::details {
0019
0020 /// Implemementation of SparseCCL, following
0021 /// [DOI: 10.1109/DASIP48288.2019.9049184]
0022 ///
0023 /// Requires cells to be sorted in column major
0024
0025 /// Find root of the tree for entry @param e
0026 ///
0027 /// @param labels an equivalance table
0028 ///
0029 /// @return the root of @param e
0030 ///
0031 TRACCC_HOST_DEVICE inline unsigned int find_root(
0032     const vecmem::device_vector<unsigned int>& labels, unsigned int e);
0033
0034 /// Create a union of two entries @param e1 and @param e2
0035 ///
0036 /// @param labels an equivalance table
0037 ///
0038 /// @return the rleast common ancestor of the entries
0039 ///
0040 TRACCC_HOST_DEVICE inline unsigned int make_union(
0041     vecmem::device_vector<unsigned int>& labels, unsigned int e1,
0042     unsigned int e2);
0043
0044 /// Helper method to find adjacent cells
0045 ///
0046 /// @param a the first cell
0047 /// @param b the second cell
0048 ///
0049 /// @return boolan to indicate 8-cell connectivity
0050 ///
0051 template <typename T1, typename T2>
0052 TRACCC_HOST_DEVICE inline bool is_adjacent(const edm::silicon_cell<T1>& a,
0053                                            const edm::silicon_cell<T2>& b);
0054
0055 /// Helper method to find define distance,
0056 /// does not need abs, as channels are sorted in
0057 /// column major
0058 ///
0059 /// @param a the first cell
0060 /// @param b the second cell
0061 ///
0062 /// @return boolan to indicate !8-cell connectivity
0063 ///
0064 template <typename T1, typename T2>
0065 TRACCC_HOST_DEVICE inline bool is_far_enough(const edm::silicon_cell<T1>& a,
0066                                              const edm::silicon_cell<T2>& b);
0067
0068 /// Sparce CCL algorithm
0069 ///
0070 /// @param cells is the cell collection
0071 /// @param labels is the vector of the output indices (to which cluster a cell
0072 ///               belongs to)
0073 /// @return number of clusters
0074 ///
0075 TRACCC_HOST_DEVICE inline unsigned int sparse_ccl(
0076     const edm::silicon_cell_collection::const_device& cells,
0077     vecmem::device_vector<unsigned int>& labels);
0078
0079 }  // namespace traccc::details
0080
0081 // Include the implementation.
0082 #include "traccc/clusterization/impl/sparse_ccl.ipp"