clusterization/impl/sparse_ccl.ipp

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 // System include(s).
0011 #include <cassert>
0012
0013 namespace traccc::details {
0014
0015 TRACCC_HOST_DEVICE inline unsigned int find_root(
0016     const vecmem::device_vector<unsigned int>& labels, unsigned int e) {
0017   unsigned int r = e;
0018   assert(r < labels.size());
0019   while (labels[r] != r) {
0020     r = labels[r];
0021     assert(r < labels.size());
0022   }
0023   return r;
0024 }
0025
0026 TRACCC_HOST_DEVICE inline unsigned int make_union(
0027     vecmem::device_vector<unsigned int>& labels, unsigned int e1,
0028     unsigned int e2) {
0029   unsigned int e;
0030   if (e1 < e2) {
0031     e = e1;
0032     assert(e2 < labels.size());
0033     labels[e2] = e;
0034   } else {
0035     e = e2;
0036     assert(e1 < labels.size());
0037     labels[e1] = e;
0038   }
0039   return e;
0040 }
0041
0042 template <typename T1, typename T2>
0043 TRACCC_HOST_DEVICE inline bool is_adjacent(const edm::silicon_cell<T1>& a,
0044                                            const edm::silicon_cell<T2>& b) {
0045   return (a.channel0() - b.channel0()) * (a.channel0() - b.channel0()) <= 1 &&
0046          (a.channel1() - b.channel1()) * (a.channel1() - b.channel1()) <= 1 &&
0047          a.module_index() == b.module_index();
0048 }
0049
0050 template <typename T1, typename T2>
0051 TRACCC_HOST_DEVICE inline bool is_far_enough(const edm::silicon_cell<T1>& a,
0052                                              const edm::silicon_cell<T2>& b) {
0053   assert((a.channel1() >= b.channel1()) ||
0054          (a.module_index() != b.module_index()));
0055   return (a.channel1() > (b.channel1() + 1)) ||
0056          (a.module_index() != b.module_index());
0057 }
0058
0059 TRACCC_HOST_DEVICE inline unsigned int sparse_ccl(
0060     const edm::silicon_cell_collection::const_device& cells,
0061     vecmem::device_vector<unsigned int>& labels) {
0062   unsigned int nlabels = 0;
0063
0064   // The number of cells.
0065   const unsigned int n_cells = cells.size();
0066
0067   // first scan: pixel association
0068   unsigned int start_j = 0;
0069   for (unsigned int i = 0; i < n_cells; ++i) {
0070     labels[i] = i;
0071     unsigned int ai = i;
0072     for (unsigned int j = start_j; j < i; ++j) {
0073       if (is_adjacent(cells.at(i), cells.at(j))) {
0074         ai = make_union(labels, ai, find_root(labels, j));
0075       } else if (is_far_enough(cells.at(i), cells.at(j))) {
0076         ++start_j;
0077       }
0078     }
0079   }
0080
0081   // second scan: transitive closure
0082   for (unsigned int i = 0; i < n_cells; ++i) {
0083     if (labels[i] == i) {
0084       labels[i] = nlabels++;
0085     } else {
0086       labels[i] = labels[labels[i]];
0087     }
0088   }
0089   return nlabels;
0090 }
0091
0092 }  // namespace traccc::details