Debian Codegraph @

include/deal.II/arborx/bvh.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2021 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_arborx_bvh_h
16 #define dealii_arborx_bvh_h
17
18 #include <deal.II/base/config.h>
19
20 #ifdef DEAL_II_WITH_ARBORX
21 # include <deal.II/arborx/access_traits.h>
22
23 # include <ArborX_Config.hpp>
24 # include <ArborX_LinearBVH.hpp>
25 # include <Kokkos_Core.hpp>
26
27 DEAL_II_NAMESPACE_OPEN
28
29 /**
30 * This namespace contains wrappers for the ArborX library.
31 */
32 namespace ArborXWrappers
33 {
34 /**
35 * This class implements a wrapper around ArborX::BVH. BVH stands for Bounding
36 * Volume Hierarchy.
37 *
38 * From [Wikipedia](https://en.wikipedia.org/wiki/Bounding_Volume_Hierarchy):
39 * <blockquote>
40 * A bounding volume hierarchy (BVH) is a tree structure on a set of geometric
41 * objects. All geometric objects are wrapped in bounding volumes that form
42 * the leaf nodes of the tree. These nodes are then grouped as small sets and
43 * enclosed within larger bounding volumes. These, in turn, are also grouped
44 * and enclosed within other larger bounding volumes in a recursive fashion,
45 * eventually resulting in a tree structure with a single bounding volume at
46 * the top of the tree. Bounding volume hierarchies are used to support
47 * several operations on sets of geometric objects efficiently, such as in
48 * collision detection and ray tracing.
49 * </blockquote>
50 */
51 # if ARBORX_VERSION_MAJOR < 2
52 class BVH
53 {
54 public:
55 /**
56 * Constructor. Use a vector of BoundingBox @p bounding_boxes as primitives.
57 */
58 template <int dim, typename Number>
59 BVH(const std::vector<BoundingBox<dim, Number>> &bounding_boxes);
60
61 /**
62 * Constructor. Use a vector of @p points as primitives.
63 */
64 template <int dim, typename Number>
65 BVH(const std::vector<Point<dim, Number>> &points);
66
67 /**
68 * Return the indices of those BoundingBox objects that satisfy the @p queries.
69 * Because @p queries can contain multiple queries, the function returns a pair
70 * of indices and offsets.
71 *
72 * Below is an example piece of code that does the following: Let us assume
73 * that we have a set of bounding boxes for objects -- say, the bounding
74 * boxes of each of the cells in a triangulation, or the bounding boxes for
75 * each of the parts of a triangulation in a parallel triangulation. We will
76 * store those in the `bvh_bounding_boxes` array below.
77 *
78 * Let us then also assume that we have a set of other bounding boxes, let's
79 * say for small objects that are moving around in our domain. We will put
80 * these bounding boxes into the `bb_intersect` array. The question we would
81 * then like to answer is the following: with which of the BVH bounding
82 * box(es) do each of the bb_intersect bounding boxes intersect? In other
83 * words, in which cell(s) or partition(s) are the particles?
84 *
85 * This query is answered by the following piece of code:
86 *
87 * @code
88 * const std::vector<BoundingBox<dim>> query_bounding_boxes = ...
89 * ArborXWrappers::BoundingBoxIntersectPredicate
90 * bb_intersect(query_bounding_boxes);
91 *
92 * const std::vector<BoundingBox<dim>> bvh_bounding_boxes = ...
93 * ArborxWrappers::BVH bvh(bvh_bounding_boxes);
94 *
95 * auto [indices, offset] = bvh.query(bb_intersect);
96 * @endcode
97 *
98 * The elements of `bvh_bounding_boxes` that intersect the `j`th BoundingBox
99 * of `query_bounding_boxes` are given by:
100 *
101 * @code
102 * std::vector<int> bvh_bounding_box_indices;
103 * for (int i = offset[j]; i < offset[j+1]; ++i)
104 * bvh_bounding_box_indices.push_back(indices[i]);
105 * @endcode
106 *
107 * In many other applications, we are interested not only in finding which
108 * bounding boxes another bounding box lies in, but in fact which bounding
109 * boxes individual points lie in -- say, if instead of objects we have
110 * point-like particles moving around. In that case, we would need to answer
111 * a query for points, and this can be done as follows:
112 *
113 * @code
114 * const std::vector<Point<dim>> query_points = ...
115 * ArborXWrappers::PointIntersectPredicate pt_intersect(query_points);
116 *
117 * const std::vector<BoundingBox<dim>> bvh_bounding_boxes = ...
118 * ArborxWrappers::BVH bvh(bvh_bounding_boxes);
119 *
120 * auto [indices, offset] = bvh.query(pt_intersect);
121 * @endcode
122 *
123 * As a final example, we want to show how to find the five nearest points
124 * of a given set of points. This can done as follows:
125 *
126 * @code
127 * const std::vector<Point<dim>> query_points = ...
128 * ArborXWrappers::PointNearestPredicate pt_nearest(query_points, 5);
129 *
130 * const std::vector<Point<dim>> bvh_points = ...
131 * ArborxWrappers::BVH bvh(bvh_points);
132 *
133 * auto [indices, offset] = bvh.query(pt_nearest);
134 * @endcode
135 */
136 template <typename QueryType>
137 std::pair<std::vector<int>, std::vector<int>>
138 query(const QueryType &queries);
139
140 private:
141 /**
142 * Underlying ArborX object.
143 */
144 ArborX::BVH<Kokkos::HostSpace> bvh;
145 };
146
147
148
149 template <int dim, typename Number>
150 BVH::BVH(const std::vector<BoundingBox<dim, Number>> &bounding_boxes)
151 : bvh(Kokkos::DefaultHostExecutionSpace{}, bounding_boxes)
152 {}
153
154
155
156 template <int dim, typename Number>
157 BVH::BVH(const std::vector<Point<dim, Number>> &points)
158 : bvh(Kokkos::DefaultHostExecutionSpace{}, points)
159 {}
160
161
162
163 template <typename QueryType>
164 std::pair<std::vector<int>, std::vector<int>>
165 BVH::query(const QueryType &queries)
166 {
167 Kokkos::View<int *, Kokkos::HostSpace> indices("indices", 0);
168
169 Kokkos::View<int *, Kokkos::HostSpace> offset("offset", 0);
170 ArborX::query(
171 bvh, Kokkos::DefaultHostExecutionSpace{}, queries, indices, offset);
172 std::vector<int> indices_vector;
173 indices_vector.insert(indices_vector.begin(),
174 indices.data(),
175 indices.data() + indices.extent(0));
176 std::vector<int> offset_vector;
177 offset_vector.insert(offset_vector.begin(),
178 offset.data(),
179 offset.data() + offset.extent(0));
180
181 return {indices_vector, offset_vector};
182 }
183 # else
184 template <typename Value>
185 class BVH
186 {
187 public:
188 /**
189 * Constructor. Use a vector of Point, BoundingBox, or sphere (std::pair<Point,Number>) @p values as primitives.
190 */
191 BVH(const std::vector<Value> &values);
192
193 /**
194 * Return the indices of those primitive objects that satisfy the @p queries.
195 * Because @p queries can contain multiple queries, the function returns a pair
196 * of indices and offsets.
197 *
198 * Below is an example piece of code that does the following: Let us assume
199 * that we have a set of bounding boxes for objects -- say, the bounding
200 * boxes of each of the cells in a triangulation, or the bounding boxes for
201 * each of the parts of a triangulation in a parallel triangulation. We will
202 * store those in the `bvh_bounding_boxes` array below.
203 *
204 * Let us then also assume that we have a set of other bounding boxes, let's
205 * say for small objects that are moving around in our domain. We will put
206 * these bounding boxes into the `bb_intersect` array. The question we would
207 * then like to answer is the following: with which of the BVH bounding
208 * box(es) do each of the bb_intersect bounding boxes intersect? In other
209 * words, in which cell(s) or partition(s) are the particles?
210 *
211 * This query is answered by the following piece of code:
212 *
213 * @code
214 * const std::vector<BoundingBox<dim>> query_bounding_boxes = ...
215 * ArborXWrappers::BoundingBoxIntersectPredicate
216 * bb_intersect(query_bounding_boxes);
217 *
218 * const std::vector<BoundingBox<dim>> bvh_bounding_boxes = ...
219 * ArborxWrappers::BVH<BoundingBox<dim>> bvh(bvh_bounding_boxes);
220 *
221 * auto [indices, offset] = bvh.query(bb_intersect);
222 * @endcode
223 *
224 * The elements of `bvh_bounding_boxes` that intersect the `j`th BoundingBox
225 * of `query_bounding_boxes` are given by:
226 *
227 * @code
228 * std::vector<int> bvh_bounding_box_indices;
229 * for (int i = offset[j]; i < offset[j+1]; ++i)
230 * bvh_bounding_box_indices.push_back(indices[i]);
231 * @endcode
232 *
233 * In many other applications, we are interested not only in finding which
234 * bounding boxes another bounding box lies in, but in fact which bounding
235 * boxes individual points lie in -- say, if instead of objects we have
236 * point-like particles moving around. In that case, we would need to answer
237 * a query for points, and this can be done as follows:
238 *
239 * @code
240 * const std::vector<Point<dim>> query_points = ...
241 * ArborXWrappers::PointIntersectPredicate pt_intersect(query_points);
242 *
243 * const std::vector<BoundingBox<dim>> bvh_bounding_boxes = ...
244 * ArborxWrappers::BVH<BoundingBox<dim>> bvh(bvh_bounding_boxes);
245 *
246 * auto [indices, offset] = bvh.query(pt_intersect);
247 * @endcode
248 *
249 * As a final example, we want to show how to find the five nearest points
250 * of a given set of points. This can done as follows:
251 *
252 * @code
253 * const std::vector<Point<dim>> query_points = ...
254 * ArborXWrappers::PointNearestPredicate pt_nearest(query_points, 5);
255 *
256 * const std::vector<Point<dim>> bvh_points = ...
257 * ArborxWrappers::BVH<Point<dim>> bvh(bvh_points);
258 *
259 * auto [indices, offset] = bvh.query(pt_nearest);
260 * @endcode
261 */
262 template <typename QueryType>
263 std::pair<std::vector<int>, std::vector<int>>
264 query(const QueryType &queries);
265
266 private:
267 /**
268 * Underlying ArborX object.
269 */
270 ArborX::BVH<Kokkos::HostSpace,
271 ArborX::PairValueIndex<Value, unsigned int>,
272 internal::IndexableGetter>
273 bvh;
274 };
275
276
277
278 template <typename Value>
279 BVH<Value>::BVH(const std::vector<Value> &values)
280 : bvh(Kokkos::DefaultHostExecutionSpace{},
281 ArborX::Experimental::attach_indices(values),
282 internal::IndexableGetter{})
283 {}
284
285
286
287 template <typename Value>
288 template <typename QueryType>
289 std::pair<std::vector<int>, std::vector<int>>
290 BVH<Value>::query(const QueryType &queries)
291 {
292 Kokkos::View<int *, Kokkos::HostSpace> indices("indices", 0);
293
294 Kokkos::View<int *, Kokkos::HostSpace> offset("offset", 0);
295 bvh.query(Kokkos::DefaultHostExecutionSpace{},
296 queries,
297 internal::ExtractIndex{},
298 indices,
299 offset);
300 std::vector<int> indices_vector;
301 indices_vector.insert(indices_vector.begin(),
302 indices.data(),
303 indices.data() + indices.extent(0));
304 std::vector<int> offset_vector;
305 offset_vector.insert(offset_vector.begin(),
306 offset.data(),
307 offset.data() + offset.extent(0));
308
309 return {indices_vector, offset_vector};
310 }
311 # endif
312 } // namespace ArborXWrappers
313
314 DEAL_II_NAMESPACE_CLOSE
315
316 #else
317
318 // Make sure the scripts that create the C++20 module input files have
319 // something to latch on if the preprocessor #ifdef above would
320 // otherwise lead to an empty content of the file.
321 DEAL_II_NAMESPACE_OPEN
322 DEAL_II_NAMESPACE_CLOSE
323
324 #endif
325 #endif