Open3D (C++ API)  0.16.1
ParallelScan.h
Go to the documentation of this file.
1// ----------------------------------------------------------------------------
2// - Open3D: www.open3d.org -
3// ----------------------------------------------------------------------------
4// The MIT License (MIT)
5//
6// Copyright (c) 2018-2021 www.open3d.org
7//
8// Permission is hereby granted, free of charge, to any person obtaining a copy
9// of this software and associated documentation files (the "Software"), to deal
10// in the Software without restriction, including without limitation the rights
11// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12// copies of the Software, and to permit persons to whom the Software is
13// furnished to do so, subject to the following conditions:
14//
15// The above copyright notice and this permission notice shall be included in
16// all copies or substantial portions of the Software.
17//
18// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
24// IN THE SOFTWARE.
25// ----------------------------------------------------------------------------
26
27#pragma once
28
29#include <tbb/parallel_for.h>
30#include <tbb/parallel_scan.h>
31
32// clang-format off
33#if TBB_INTERFACE_VERSION >= 10000
34 #ifdef OPEN3D_USE_ONEAPI_PACKAGES
35 #include <oneapi/dpl/execution>
36 #include <oneapi/dpl/numeric>
37 #else
38 // Check if the C++ standard library implements parallel algorithms
39 // and use this over parallelstl to avoid conflicts.
40 // Clang does not implement it so far, so checking for C++17 is not sufficient.
41 #ifdef __cpp_lib_parallel_algorithm
42 #include <execution>
43 #include <numeric>
44 #else
45 #include <pstl/execution>
46 #include <pstl/numeric>
47 // parallelstl incorrectly assumes MSVC to unconditionally implement
48 // parallel algorithms even if __cpp_lib_parallel_algorithm is not
49 // defined. So manually include the header which pulls all
50 // "pstl::execution" definitions into the "std" namespace.
51 #if __PSTL_CPP17_EXECUTION_POLICIES_PRESENT
52 #include <pstl/internal/glue_execution_defs.h>
53 #endif
54 #endif
55 #endif
56#endif
57
58// clang-format on
59
60namespace open3d {
61namespace utility {
62
63namespace {
64template <class Tin, class Tout>
65class ScanSumBody {
66 Tout sum;
67 const Tin* in;
68 Tout* const out;
69
70public:
71 ScanSumBody(Tout* out_, const Tin* in_) : sum(0), in(in_), out(out_) {}
72 Tout get_sum() const { return sum; }
73
74 template <class Tag>
75 void operator()(const tbb::blocked_range<size_t>& r, Tag) {
76 Tout temp = sum;
77 for (size_t i = r.begin(); i < r.end(); ++i) {
78 temp = temp + in[i];
79 if (Tag::is_final_scan()) out[i] = temp;
80 }
81 sum = temp;
82 }
83 ScanSumBody(ScanSumBody& b, tbb::split) : sum(0), in(b.in), out(b.out) {}
84 void reverse_join(ScanSumBody& a) { sum = a.sum + sum; }
85 void assign(ScanSumBody& b) { sum = b.sum; }
86};
87} // namespace
88
89template <class Tin, class Tout>
90void InclusivePrefixSum(const Tin* first, const Tin* last, Tout* out) {
91#if TBB_INTERFACE_VERSION >= 10000
92 // use parallelstl if we have TBB 2018 or later
93#ifdef OPEN3D_USE_ONEAPI_PACKAGES
94 std::inclusive_scan(oneapi::dpl::execution::par_unseq, first, last, out);
95
96#else
97 std::inclusive_scan(std::execution::par_unseq, first, last, out);
98#endif
99#else
100 ScanSumBody<Tin, Tout> body(out, first);
101 size_t n = std::distance(first, last);
102 tbb::parallel_scan(tbb::blocked_range<size_t>(0, n), body);
103#endif
104}
105
106} // namespace utility
107} // namespace open3d
void InclusivePrefixSum(const Tin *first, const Tin *last, Tout *out)
Definition: ParallelScan.h:90
Definition: PinholeCameraIntrinsic.cpp:35