Debian Codegraph @

include/deal.II/grid/grid_tools_cache.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2017 - 2025 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_grid_grid_tools_cache_h
16 #define dealii_grid_grid_tools_cache_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/enable_observer_pointer.h>
22 #include <deal.II/base/exceptions.h>
23 #include <deal.II/base/point.h>
24
25 #include <deal.II/fe/mapping.h>
26
27 #include <deal.II/grid/grid_tools_cache_update_flags.h>
28 #include <deal.II/grid/tria.h>
29 #include <deal.II/grid/tria_accessor.h>
30 #include <deal.II/grid/tria_iterator.h>
31
32 #include <deal.II/numerics/rtree.h>
33
34 #include <boost/signals2.hpp>
35
36 #include <atomic>
37 #include <cmath>
38 #include <set>
39
40
41 DEAL_II_NAMESPACE_OPEN
42
43 namespace GridTools
44 {
45 /**
46 * A class that caches computationally intensive information about a
47 * Triangulation.
48 *
49 * This class attaches a signal to the Triangulation passed at construction
50 * time to keep track about refinement changes, and allows the user to query
51 * some of the data structures constructed using functions in the GridTools
52 * namespace which are computed only once, and then cached inside this class
53 * for faster access whenever the triangulation has not changed.
54 *
55 * Notice that this class only notices if the underlying Triangulation has
56 * changed due to a Triangulation::Signals::any_change() signal being
57 * triggered.
58 *
59 * If the triangulation changes for other reasons, for example because you
60 * use it in conjunction with a MappingQEulerian object that sees the
61 * vertices through its own transformation, or because you manually change
62 * some vertex locations, then some of the structures in this class become
63 * obsolete, and you will have to mark them as outdated, by calling the
64 * method mark_for_update() manually.
65 */
66 template <int dim, int spacedim = dim>
67 class Cache : public EnableObserverPointer
68 {
69 public:
70 /**
71 * Constructor.
72 *
73 * If you provide the optional `mapping` argument, then this is used
74 * whenever a mapping is required.
75 *
76 * @param tria The triangulation for which to store information.
77 * @param mapping The Mapping to use when computing cached objects.
78 */
79 Cache(const Triangulation<dim, spacedim> &tria,
80 const Mapping<dim, spacedim> &mapping);
81
82 /**
83 * Constructor. Uses the default linear or multilinear mapping for the
84 * underlying ReferenceCell of @p tria.
85 *
86 * @param tria The triangulation for which to store information.
87 */
88 Cache(const Triangulation<dim, spacedim> &tria);
89
90 /**
91 * Destructor.
92 */
93 ~Cache() override;
94
95 /**
96 * Make sure that the objects marked for update are recomputed during
97 * subsequent calls to the `get_*` functions defined in this class.
98 *
99 * Notice that no work is performed when you call this function. The actual
100 * data structures are computed the next time you call the corresponding
101 * `get_*` method.
102 *
103 * @param flags What to mark for update
104 */
105 void
106 mark_for_update(const CacheUpdateFlags &flags = update_all);
107
108
109 /**
110 * Return the cached vertex_to_cell_map as computed by
111 * GridTools::vertex_to_cell_map().
112 */
113 const std::vector<
114 std::set<typename Triangulation<dim, spacedim>::active_cell_iterator>> &
115 get_vertex_to_cell_map() const;
116
117 /**
118 * Return the cached vertex_to_cell_centers_directions as computed by
119 * GridTools::vertex_to_cell_centers_directions().
120 */
121 const std::vector<std::vector<Tensor<1, spacedim>>> &
122 get_vertex_to_cell_centers_directions() const;
123
124 /**
125 * Return the cached map of used vertices, as computed by
126 * GridTools::extract_used_vertices().
127 */
128 const std::map<unsigned int, Point<spacedim>> &
129 get_used_vertices() const;
130
131 /**
132 * Return the cached RTree object for the vertices, constructed using the
133 * used vertices of the triangulation.
134 */
135 const RTree<std::pair<Point<spacedim>, unsigned int>> &
136 get_used_vertices_rtree() const;
137
138 /**
139 * Return the cached RTree object of the cell bounding boxes, constructed
140 * using the active cell iterators of the stored triangulation. For
141 * parallel::distributed::Triangulation objects, this function will return
142 * also the bounding boxes of ghost and artificial cells.
143 */
144 const RTree<
145 std::pair<BoundingBox<spacedim>,
146 typename Triangulation<dim, spacedim>::active_cell_iterator>> &
147 get_cell_bounding_boxes_rtree() const;
148
149 /**
150 * Return the cached RTree object of bounding boxes containing locally owned
151 * active cells, constructed using the active cell iterators of the stored
152 * triangulation.
153 *
154 * In contrast to the previous function, this function builds the RTree
155 * using only the locally owned cells, i.e., not including ghost or
156 * artificial cells. The two functions return the same result in serial
157 * computations.
158 */
159 const RTree<
160 std::pair<BoundingBox<spacedim>,
161 typename Triangulation<dim, spacedim>::active_cell_iterator>> &
162 get_locally_owned_cell_bounding_boxes_rtree() const;
163
164
165 /**
166 * Returns the vector of set of integer containing the subdomain id
167 * to which each vertex is connected to. This feature is used extensively
168 * in the particle_handler to detect on which processors ghost particles
169 * must be built.
170 */
171 const std::vector<std::set<unsigned int>> &
172 get_vertex_to_neighbor_subdomain() const;
173
174 /**
175 * Return a map that, for each vertex, lists all the processes whose
176 * subdomains are adjacent to that vertex.
177 */
178 const std::map<unsigned int, std::set<types::subdomain_id>> &
179 get_vertices_with_ghost_neighbors() const;
180
181 /**
182 * Return a reference to the stored triangulation.
183 */
184 const Triangulation<dim, spacedim> &
185 get_triangulation() const;
186
187 /**
188 * Return a reference to the stored mapping.
189 */
190 const Mapping<dim, spacedim> &
191 get_mapping() const;
192
193
194 /**
195 * This function returns an object that allows identifying
196 * which process(es) in a parallel computation may own the
197 * cell that surrounds a given point. The elements of this
198 * object -- an Rtree -- are pairs of bounding boxes denoting
199 * areas that cover all or parts of the local portion of a
200 * parallel triangulation, and an unsigned int representing
201 * the process or subdomain that owns the cells falling within the given
202 * bounding box.
203 *
204 * Given a point on a parallel::TriangulationBase, this tree
205 * allows to identify one, or few candidate processes, for
206 * which the point lies on a locally owned cell.
207 *
208 * Constructing or updating the rtree requires a call to
209 * GridTools::build_global_description_tree(), which exchanges
210 * bounding boxes between all processes using
211 * Utilities::MPI::all_gather(), a @ref GlossCollectiveOperation "collective operation".
212 * Therefore this function must be called by all processes
213 * at the same time.
214 *
215 * The local bounding boxes are constructed by extracting the
216 * specified @p level from the rtree object returned by the
217 * get_locally_owned_cell_bounding_boxes_rtree(). Notice that @p level
218 * in this context does not refer to the level of the triangulation, but
219 * refer to the level of the RTree object (see, e.g.,
220 * https://en.wikipedia.org/wiki/R-tree).
221 */
222 const RTree<std::pair<BoundingBox<spacedim>, unsigned int>> &
223 get_covering_rtree(const unsigned int level = 0) const;
224
225 private:
226 /**
227 * Keep track of what needs to be updated every time the triangulation
228 * is changed. Each of the get_*() functions above checks whether a
229 * data structure still needs to be updated before returning a reference
230 * to it; if it needs to be updated, it does so and resets the
231 * corresponding flag. The constructor as well as the signal slot
232 * that is called whenever the triangulation changes the re-sets this
233 * flag to `update_all` again.
234 *
235 * The various get_() member functions may be reading and updating this
236 * variable from different threads, but are only ever reading or writing
237 * individual bits. We can make that thread-safe by using std::atomic
238 * with the correct integer type for the `enum` type of `CacheUpdateFlags`.
239 */
240 mutable std::atomic<std::underlying_type_t<CacheUpdateFlags>> update_flags;
241
242 /**
243 * A pointer to the Triangulation.
244 */
245 ObserverPointer<const Triangulation<dim, spacedim>, Cache<dim, spacedim>>
246 tria;
247
248 /**
249 * Mapping to use when computing on the Triangulation.
250 */
251 ObserverPointer<const Mapping<dim, spacedim>, Cache<dim, spacedim>> mapping;
252
253
254 /**
255 * Store vertex to cell map information, as generated by
256 * GridTools::vertex_to_cell_map()
257 */
258 mutable std::vector<
259 std::set<typename Triangulation<dim, spacedim>::active_cell_iterator>>
260 vertex_to_cells;
261 mutable std::mutex vertex_to_cells_mutex;
262
263 /**
264 * Store vertex to cell center directions, as generated by
265 * GridTools::vertex_to_cell_centers_directions().
266 */
267 mutable std::vector<std::vector<Tensor<1, spacedim>>>
268 vertex_to_cell_centers;
269 mutable std::mutex vertex_to_cell_centers_mutex;
270
271 /**
272 * A collection of rtree objects covering the whole mesh.
273 *
274 * Each entry of the map is constructed from the function
275 * extract_rtree_level() applied to the rtree returned by the function
276 * get_locally_owned_cell_bounding_boxes_rtree(), with the specified level
277 * in input.
278 */
279 mutable std::map<unsigned int,
280 RTree<std::pair<BoundingBox<spacedim>, unsigned int>>>
281 covering_rtree;
282 mutable std::mutex covering_rtree_mutex;
283
284 /**
285 * Store the used vertices of the Triangulation, as generated by
286 * GridTools::extract_used_vertices().
287 */
288 mutable std::map<unsigned int, Point<spacedim>> used_vertices;
289 mutable std::mutex used_vertices_mutex;
290
291 /**
292 * Store an RTree object, containing the used vertices of the triangulation.
293 */
294 mutable RTree<std::pair<Point<spacedim>, unsigned int>> used_vertices_rtree;
295 mutable std::mutex used_vertices_rtree_mutex;
296
297 /**
298 * Store an RTree object, containing the bounding boxes of the cells of the
299 * triangulation.
300 */
301 mutable RTree<
302 std::pair<BoundingBox<spacedim>,
303 typename Triangulation<dim, spacedim>::active_cell_iterator>>
304 cell_bounding_boxes_rtree;
305 mutable std::mutex cell_bounding_boxes_rtree_mutex;
306
307 /**
308 * Store an RTree object, containing the bounding boxes of the locally owned
309 * cells of the triangulation.
310 */
311 mutable RTree<
312 std::pair<BoundingBox<spacedim>,
313 typename Triangulation<dim, spacedim>::active_cell_iterator>>
314 locally_owned_cell_bounding_boxes_rtree;
315 mutable std::mutex locally_owned_cell_bounding_boxes_rtree_mutex;
316
317 /**
318 * Store an std::vector of std::set of integer containing the id of all
319 * subdomain to which a vertex is connected to.
320 */
321 mutable std::vector<std::set<unsigned int>> vertex_to_neighbor_subdomain;
322 mutable std::mutex vertex_to_neighbor_subdomain_mutex;
323
324 /**
325 * Store an std::map of unsigned integer containing
326 * the set of subdomains connected to each vertex.
327 */
328 mutable std::map<unsigned int, std::set<dealii::types::subdomain_id>>
329 vertices_with_ghost_neighbors;
330 mutable std::mutex vertices_with_ghost_neighbors_mutex;
331
332 /**
333 * Storage for the status of the triangulation change signal.
334 */
335 boost::signals2::connection tria_change_signal;
336
337 /**
338 * Storage for the status of the triangulation creation signal.
339 */
340 boost::signals2::connection tria_create_signal;
341 };
342
343
344
345 // Inline functions
346 template <int dim, int spacedim>
347 inline const Triangulation<dim, spacedim> &
348 Cache<dim, spacedim>::get_triangulation() const
349 {
350 return *tria;
351 }
352
353
354
355 template <int dim, int spacedim>
356 inline const Mapping<dim, spacedim> &
357 Cache<dim, spacedim>::get_mapping() const
358 {
359 Assert(mapping, ExcNotInitialized());
360 return *mapping;
361 }
362 } // namespace GridTools
363
364
365
366 DEAL_II_NAMESPACE_CLOSE
367
368 #endif