InvertNeighborsList.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
// -                        Open3D: www.open3d.org                            -
// ----------------------------------------------------------------------------
// The MIT License (MIT)
//
// Copyright (c) 2020 www.open3d.org
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
// ----------------------------------------------------------------------------

#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