InvertNeighborsList.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
// -                        Open3D: www.open3d.org                            -
// ----------------------------------------------------------------------------
// Copyright (c) 2018-2023 www.open3d.org
// SPDX-License-Identifier: MIT
// ----------------------------------------------------------------------------
 
#pragma once
 
#include <tbb/parallel_for.h>
 
#include "open3d/core/Atomic.h"
#include "open3d/utility/ParallelScan.h"
 
namespace open3d {
namespace ml {
namespace impl {
 
template <class TIndex, class TAttr>
void InvertNeighborsListCPU(const TIndex* const inp_neighbors_index,
                            const TAttr* const inp_neighbors_attributes,
                            const int num_attributes_per_neighbor,
                            const int64_t* const inp_neighbors_row_splits,
                            const size_t inp_num_queries,
                            TIndex* out_neighbors_index,
                            TAttr* out_neighbors_attributes,
                            const size_t index_size,
                            int64_t* out_neighbors_row_splits,
                            const size_t out_num_queries) {
    using namespace open3d::utility;
 
    std::vector<uint32_t> tmp_neighbors_count(out_num_queries + 1, 0);
 
    // count how often an idx appears in inp_neighbors_index
    tbb::parallel_for(tbb::blocked_range<size_t>(0, index_size),
                      [&](const tbb::blocked_range<size_t>& r) {
                          for (size_t i = r.begin(); i != r.end(); ++i) {
                              TIndex idx = inp_neighbors_index[i];
                              core::AtomicFetchAddRelaxed(
                                      &tmp_neighbors_count[idx + 1], 1);
                          }
                      });
 
    InclusivePrefixSum(&tmp_neighbors_count[0],
                       &tmp_neighbors_count[tmp_neighbors_count.size()],
                       out_neighbors_row_splits);
 
    memset(tmp_neighbors_count.data(), 0,
           sizeof(uint32_t) * tmp_neighbors_count.size());
 
    // fill the new index vector
    tbb::parallel_for(
            tbb::blocked_range<size_t>(0, inp_num_queries),
            [&](const tbb::blocked_range<size_t>& r) {
                for (size_t i = r.begin(); i != r.end(); ++i) {
                    TIndex query_idx = i;
 
                    size_t begin_idx = inp_neighbors_row_splits[i];
                    size_t end_idx = inp_neighbors_row_splits[i + 1];
                    for (size_t j = begin_idx; j < end_idx; ++j) {
                        TIndex neighbor_idx = inp_neighbors_index[j];
 
                        size_t list_offset =
                                out_neighbors_row_splits[neighbor_idx];
                        size_t item_offset = core::AtomicFetchAddRelaxed(
                                &tmp_neighbors_count[neighbor_idx], 1);
                        out_neighbors_index[list_offset + item_offset] =
                                query_idx;
 
                        if (inp_neighbors_attributes) {
                            TAttr* attr_ptr =
                                    out_neighbors_attributes +
                                    num_attributes_per_neighbor *
                                            (list_offset + item_offset);
                            for (int attr_i = 0;
                                 attr_i < num_attributes_per_neighbor;
                                 ++attr_i) {
                                attr_ptr[attr_i] = inp_neighbors_attributes
                                        [num_attributes_per_neighbor * j +
                                         attr_i];
                            }
                        }
                    }
                }
            });
}
 
}  // namespace impl
}  // namespace ml
}  // namespace open3d