Debian Codegraph @

include/deal.II/grid/grid_tools.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2001 - 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_tools_h
16 #define dealii_grid_tools_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/bounding_box.h>
22 #include <deal.II/base/geometry_info.h>
23 #include <deal.II/base/point.h>
24
25 #include <deal.II/boost_adaptors/bounding_box.h>
26
27 #include <deal.II/distributed/shared_tria.h>
28
29 #include <deal.II/dofs/dof_handler.h>
30
31 #include <deal.II/fe/fe_values.h>
32 #include <deal.II/fe/mapping.h>
33
34 #include <deal.II/grid/grid_tools_geometry.h>
35 #include <deal.II/grid/grid_tools_topology.h>
36 #include <deal.II/grid/manifold.h>
37 #include <deal.II/grid/tria.h>
38 #include <deal.II/grid/tria_accessor.h>
39 #include <deal.II/grid/tria_iterator.h>
40
41 #include <deal.II/lac/la_parallel_vector.h>
42 #include <deal.II/lac/petsc_vector.h>
43 #include <deal.II/lac/sparsity_tools.h>
44 #include <deal.II/lac/trilinos_vector.h>
45
46 #include <deal.II/numerics/rtree.h>
47
48 #include <boost/archive/binary_iarchive.hpp>
49 #include <boost/archive/binary_oarchive.hpp>
50 #include <boost/random/mersenne_twister.hpp>
51 #include <boost/serialization/array.hpp>
52 #include <boost/serialization/vector.hpp>
53
54 #ifdef DEAL_II_WITH_ZLIB
55 # include <boost/iostreams/device/back_inserter.hpp>
56 # include <boost/iostreams/filter/gzip.hpp>
57 # include <boost/iostreams/filtering_stream.hpp>
58 # include <boost/iostreams/stream.hpp>
59 #endif
60
61 #include <optional>
62 #include <set>
63
64 #ifdef DEAL_II_HAVE_CXX20
65 # include <concepts>
66 #endif
67
68
69 DEAL_II_NAMESPACE_OPEN
70
71 // Forward declarations
72 #ifndef DOXYGEN
73 namespace parallel
74 {
75 namespace distributed
76 {
77 template <int dim, int spacedim>
78 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
79 class Triangulation;
80 }
81 } // namespace parallel
82
83 namespace hp
84 {
85 template <int, int>
86 class MappingCollection;
87 }
88
89 class SparsityPattern;
90
91 namespace GridTools
92 {
93 template <int dim, int spacedim>
94 class Cache;
95 }
96 #endif
97
98 namespace internal
99 {
100 template <int dim, int spacedim, typename MeshType>
101 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
102 class ActiveCellIterator
103 {
104 public:
105 #ifndef _MSC_VER
106 using type = typename MeshType::active_cell_iterator;
107 #else
108 using type = TriaActiveIterator<dealii::CellAccessor<dim, spacedim>>;
109 #endif
110 };
111
112 #ifdef _MSC_VER
113 template <int dim, int spacedim>
114 class ActiveCellIterator<dim, spacedim, DoFHandler<dim, spacedim>>
115 {
116 public:
117 using type =
118 TriaActiveIterator<dealii::DoFCellAccessor<dim, spacedim, false>>;
119 };
120 #endif
121 } // namespace internal
122
123 /**
124 * This namespace is a collection of algorithms working on triangulations,
125 * such as shifting or rotating triangulations, but also finding a cell that
126 * contains a given point. See the descriptions of the individual functions
127 * for more information.
128 *
129 * @ingroup grid
130 */
131 namespace GridTools
132 {
133 /**
134 * @name Rotating, stretching and otherwise transforming meshes
135 */
136 /** @{ */
137
138 /**
139 * Transform the vertices of the given triangulation by applying the
140 * function object provided as first argument to all its vertices.
141 *
142 * The transformation given as argument is used to transform each vertex.
143 * Its respective type has to offer a function-like syntax, i.e. the
144 * predicate is either an object of a type that has an <tt>operator()</tt>,
145 * or it is a pointer to a non-member function, or it is a lambda function
146 * object. In either case, argument and return
147 * value have to be of type Point<spacedim>. An example -- a simple
148 * transformation that moves the object two units to the
149 * right in the $x_1$ direction -- could look like as follows:
150 * @code
151 * Triangulation<dim> triangulation;
152 * ... // fill triangulation with something
153 * GridTools::transform ([](const Point<dim> &p) -> Point<dim>
154 * {
155 * Point<dim> q = p;
156 * q[0] += 2;
157 * return q;
158 * },
159 * triangulation);
160 * @endcode
161 * Here, the transformation is provided by a lambda function that
162 * takes a `Point<dim>` as input and returns a `Point<dim>` as output.
163 *
164 * @note The transformations that make sense to use with this function
165 * should have a Jacobian with a positive determinant. For example,
166 * rotation, shearing, stretching, or scaling all satisfy this (though
167 * there is no requirement that the transformation used actually is
168 * linear, as all of these examples are). On the other hand, reflections
169 * or inversions have a negative determinant of the Jacobian. The
170 * current function has no way of asserting a positive determinant
171 * of the Jacobian, but if you happen to use such a transformation,
172 * the result will be a triangulation in which cells have a negative
173 * volume.
174 *
175 * @note If you are using a parallel::distributed::Triangulation you will
176 * have hanging nodes in your local Triangulation even if your "global" mesh
177 * has no hanging nodes. This will cause issues with wrong positioning of
178 * hanging nodes in ghost cells if you call the current functions: The
179 * vertices of all locally owned cells will be correct, but the vertices of
180 * some ghost cells may not. This means that computations like
181 * KellyErrorEstimator may give wrong answers.
182 *
183 * @note This function is in general not compatible with manifolds attached
184 * to the triangulation. For example, in order to refine the grid (using
185 * manifolds) after the grid transformation, you have to make sure that
186 * the original manifold is still valid for the transformed geometry. This
187 * does not hold in general, and it is necessary to clear manifolds from
188 * the triangulation (for example, using Triangulation::clear_all_manifolds())
189 * before the transformation, and then attach new ones after the
190 * transformation that are valid for the transformed geometry. There are cases
191 * where this is awkward, most notably if you are using a mesh generated by
192 * the functions in GridGenerator which generally attach suitable manifolds
193 * upon mesh generation; in those cases, you will have to think about how
194 * these manifolds were constructed, and create a manifold that is constructed
195 * in a similar way but applies to the transformed geometry. As a consequence,
196 * if you only care about manifolds for mesh refinement, it is often simpler
197 * to just refine the original mesh before transformation as needed, and then
198 * simply forget about the manifolds. Of course, manifolds are also used for
199 * other cases (e.g., for normal vectors, curved edges and faces, and higher
200 * order mappings), and if these are relevant to what you are doing, then
201 * there is no alternative to building appropriate manifolds for the
202 * transformed geometry and attaching these to the transformed geometry. In
203 * general, detaching manifolds from a triangulation and then doing the
204 * transformation would look as follows:
205 * @code
206 * ...
207 * triangulation.reset_all_manifolds();
208 * GridTools::transform(MyTransformation<dim>(), triangulation);
209 * ...
210 * @endcode
211 *
212 * This function is used in the "Possibilities for extensions" section of
213 * step-38. It is also used in step-49 and step-53.
214 *
215 * @dealiiConceptRequires{(std::invocable<Transformation, Point<spacedim>> &&
216 * std::assignable_from<Point<spacedim> &,
217 * std::invoke_result_t<Transformation, Point<spacedim>>>)}
218 */
219 template <int dim, typename Transformation, int spacedim>
220 DEAL_II_CXX20_REQUIRES(
221 (std::invocable<Transformation, Point<spacedim>> &&
222 std::assignable_from<
223 Point<spacedim> &,
224 std::invoke_result_t<Transformation, Point<spacedim>>>))
225 void transform(const Transformation &transformation,
226 Triangulation<dim, spacedim> &triangulation);
227
228 /**
229 * Shift each vertex of the triangulation by the given shift vector. This
230 * function uses the transform() function above, so the requirements on the
231 * triangulation stated there hold for this function as well; in particular,
232 * this is true about the discussion about manifolds.
233 */
234 template <int dim, int spacedim>
235 void
236 shift(const Tensor<1, spacedim> &shift_vector,
237 Triangulation<dim, spacedim> &triangulation);
238
239
240 /**
241 * Rotate all vertices of the given two-dimensional triangulation in
242 * counter-clockwise sense around the origin of the coordinate system by the
243 * given angle (given in radians, rather than degrees). This function uses
244 * the transform() function above, so the requirements on the triangulation
245 * stated there hold for this function as well; in particular,
246 * this is true about the discussion about manifolds.
247 *
248 * @note This function is only supported for spacedim=2.
249 */
250 template <int dim, int spacedim>
251 void
252 rotate(const double angle, Triangulation<dim, spacedim> &triangulation);
253
254 /**
255 * Rotate all vertices of the given @p triangulation in counter-clockwise
256 * direction around the @p axis described by a unit vector. Otherwise like the
257 * function above; in particular, this function calls the transform() function
258 * and so the discussion about manifolds there also applies here.
259 *
260 * @param[in] angle Angle in radians to rotate the Triangulation by.
261 * @param[in] axis A unit vector that defines the axis of rotation.
262 * @param[in,out] triangulation The Triangulation object to rotate.
263 *
264 * @note Implemented for spacedim=3 and dim=1, 2, and 3.
265 */
266 template <int dim>
267 void
268 rotate(const Tensor<1, 3, double> &axis,
269 const double angle,
270 Triangulation<dim, 3> &triangulation);
271
272 /**
273 * Transform the given triangulation smoothly to a different domain where,
274 * typically, each of the vertices at the boundary of the triangulation is
275 * mapped to the corresponding points in the @p new_points map.
276 *
277 * The unknown displacement field $u_d(\mathbf x)$ in direction $d$ is
278 * obtained from the minimization problem \f[ \min\, \int \frac{1}{2}
279 * c(\mathbf x)
280 * \mathbf \nabla u_d(\mathbf x) \cdot
281 * \mathbf \nabla u_d(\mathbf x)
282 * \,\rm d x
283 * \f]
284 * subject to prescribed constraints. The minimizer is obtained by solving the
285 * Laplace equation of the dim components of a displacement field that maps
286 * the current
287 * domain into one described by @p new_points . Linear finite elements with
288 * four Gaussian quadrature points in each direction are used. The difference
289 * between the vertex positions specified in @p new_points and their current
290 * value in @p tria therefore represents the prescribed values of this
291 * displacement field at the boundary of the domain, or more precisely at all
292 * of those locations for which @p new_points provides values (which may be
293 * at part of the boundary, or even in the interior of the domain). The
294 * function then evaluates this displacement field at each unconstrained
295 * vertex and uses it to place the mapped vertex where the displacement
296 * field locates it. Because the solution of the Laplace equation is smooth,
297 * this guarantees a smooth mapping from the old domain to the new one.
298 *
299 * @param[in] new_points The locations where a subset of the existing
300 * vertices are to be placed. Typically, this would be a map from the vertex
301 * indices of all nodes on the boundary to their new locations, thus
302 * completely specifying the geometry of the mapped domain. However, it may
303 * also include interior points if necessary and it does not need to include
304 * all boundary vertices (although you then lose control over the exact
305 * shape of the mapped domain).
306 *
307 * @param[in,out] tria The Triangulation object. This object is changed
308 * in-place, i.e., the previous locations of vertices are overwritten.
309 *
310 * @param[in] coefficient An optional coefficient for the Laplace problem.
311 * Larger values make cells less prone to deformation (effectively
312 * increasing their stiffness). The coefficient is evaluated in the
313 * coordinate system of the old, undeformed configuration of the
314 * triangulation as input, i.e., before the transformation is applied.
315 * Should this function be provided, sensible results can only be expected
316 * if all coefficients are positive.
317 *
318 * @param[in] solve_for_absolute_positions If set to <code>true</code>, the
319 * minimization problem is formulated with respect to the final vertex
320 * positions as opposed to their displacement. The two formulations are
321 * equivalent for
322 * the homogeneous problem (default value of @p coefficient), but they
323 * result in very different mesh motion otherwise. Since in most cases one
324 * will be using a non-constant coefficient in displacement formulation, the
325 * default value of this parameter is <code>false</code>.
326 *
327 * @note This function is not currently implemented for the 1d case.
328 */
329 template <int dim>
330 void
331 laplace_transform(const std::map<unsigned int, Point<dim>> &new_points,
332 Triangulation<dim> &tria,
333 const Function<dim, double> *coefficient = nullptr,
334 const bool solve_for_absolute_positions = false);
335
336 /**
337 * Scale the entire triangulation by the given factor. To preserve the
338 * orientation of the triangulation, the factor must be positive.
339 *
340 * This function uses the transform() function above, so the requirements on
341 * the triangulation stated there hold for this function as well.
342 */
343 template <int dim, int spacedim>
344 void
345 scale(const double scaling_factor,
346 Triangulation<dim, spacedim> &triangulation);
347
348 /**
349 * Distort the given triangulation by randomly moving around all the
350 * vertices of the grid. The direction of movement of each vertex is
351 * random, while the length of the shift vector has a value of @p factor
352 * times the minimal length of the active edges adjacent to this vertex.
353 * Note that @p factor should obviously be well below <tt>0.5</tt> in order
354 * to avoid getting cells that are @ref GlossDistorted "distorted".
355 *
356 * The function will make sure that vertices on restricted faces
357 * (i.e., faces with hanging nodes) will end up in the correct
358 * place, i.e. in the middle of the two other vertices of the parent
359 * edge, and the analogue in higher space dimensions (vertices on
360 * the boundary are not corrected, so don't distort boundary
361 * vertices in more than two space dimensions, i.e. in dimensions
362 * where boundary vertices can be hanging nodes).
363 *
364 * If @p keep_boundary is set to @p true (which is the default), then
365 * boundary vertices are not moved.
366 *
367 * @p seed is used for the initialization of the random engine. Its
368 * default value initializes the engine with the same state as in
369 * previous versions of deal.II.
370 *
371 * @note If the Triangulation is of distributed kind (derived from
372 * parallel::DistributedTriangulationBase) and computations are done in
373 * parallel, the new vertex locations will be consistently updated
374 * on all ranks.
375 *
376 */
377 template <int dim, int spacedim>
378 void
379 distort_random(
380 const double factor,
381 Triangulation<dim, spacedim> &triangulation,
382 const bool keep_boundary = true,
383 const unsigned int seed = boost::random::mt19937::default_seed);
384
385 /**
386 * Analyze the boundary cells of a mesh, and if one cell is found at
387 * a corner position (with dim adjacent faces on the boundary), and its
388 * dim-dimensional angle fraction exceeds @p limit_angle_fraction,
389 * refine globally once, and replace the children of such cell
390 * with children where the corner is no longer offending the given angle
391 * fraction.
392 *
393 * If no boundary cells exist with two adjacent faces on the boundary, then
394 * the triangulation is left untouched. If instead we do have cells with dim
395 * adjacent faces on the boundary, then the fraction between the
396 * dim-dimensional
397 * solid angle and dim*pi/2 is checked against the parameter @p limit_angle_fraction.
398 * If it is higher, the grid is refined once, and the children of the
399 * offending cell are replaced with some cells that instead respect the limit.
400 * After this process the triangulation is flattened, and all Manifold objects
401 * are restored as they were in the original triangulation.
402 *
403 * An example is given by the following mesh, obtained by attaching a
404 * SphericalManifold to a mesh generated using GridGenerator::hyper_cube:
405 *
406 * @code
407 * const SphericalManifold<dim> m0;
408 * Triangulation<dim> tria;
409 * GridGenerator::hyper_cube(tria,-1,1);
410 * tria.set_all_manifold_ids_on_boundary(0);
411 * tria.set_manifold(0, m0);
412 * tria.refine_global(4);
413 * @endcode
414 *
415 * <p ALIGN="center">
416 * @image html regularize_mesh_01.png
417 * </p>
418 *
419 * The four cells that were originally the corners of a square will give you
420 * some troubles during computations, as the Jacobian of the transformation
421 * from the reference cell to those cells will go to zero, affecting the error
422 * constants of the finite element estimates.
423 *
424 * Those cells have a corner with an angle that is very close to 180 degrees,
425 * i.e., an angle fraction very close to one.
426 *
427 * The same code, adding a call to regularize_corner_cells:
428 * @code
429 * const SphericalManifold<dim> m0;
430 * Triangulation<dim> tria;
431 * GridGenerator::hyper_cube(tria,-1,1);
432 * tria.set_all_manifold_ids_on_boundary(0);
433 * tria.set_manifold(0, m0);
434 * GridTools::regularize_corner_cells(tria);
435 * tria.refine_global(2);
436 * @endcode
437 * generates a mesh that has a much better behavior w.r.t. the Jacobian of
438 * the Mapping:
439 *
440 * <p ALIGN="center">
441 * @image html regularize_mesh_02.png
442 * </p>
443 *
444 * This mesh is very similar to the one obtained by GridGenerator::hyper_ball.
445 * However, using GridTools::regularize_corner_cells one has the freedom to
446 * choose when to apply the regularization, i.e., one could in principle first
447 * refine a few times, and then call the regularize_corner_cells function:
448 *
449 * @code
450 * const SphericalManifold<dim> m0;
451 * Triangulation<dim> tria;
452 * GridGenerator::hyper_cube(tria,-1,1);
453 * tria.set_all_manifold_ids_on_boundary(0);
454 * tria.set_manifold(0, m0);
455 * tria.refine_global(2);
456 * GridTools::regularize_corner_cells(tria);
457 * tria.refine_global(1);
458 * @endcode
459 *
460 * This generates the following mesh:
461 *
462 * <p ALIGN="center">
463 * @image html regularize_mesh_03.png
464 * </p>
465 *
466 * The function is currently implemented only for dim = 2 and
467 * will throw an exception if called with dim = 3.
468 *
469 * @param[in,out] tria Triangulation to regularize.
470 *
471 * @param[in] limit_angle_fraction Maximum ratio of angle or solid
472 * angle that is allowed for a corner element in the mesh.
473 */
474 template <int dim, int spacedim>
475 void
476 regularize_corner_cells(Triangulation<dim, spacedim> &tria,
477 const double limit_angle_fraction = .75);
478
479 /** @} */
480 /**
481 * @name Finding cells and vertices of a triangulation
482 */
483 /** @{ */
484
485 /**
486 * Given a Triangulation's @p cache and a list of @p points, call
487 * find_active_cell_around_point() on each element of @p points, and return
488 * @p cells, reference positions @p qpoints, and a mapping @p maps from local
489 * to global indices into @p points .
490 *
491 * @param[in] cache The triangulation's GridTools::Cache .
492 * @param[in] points A vector of points.
493 * @param[in] cell_hint (optional) A cell iterator for a cell which likely
494 * contains the first point of @p points.
495 *
496 * @return A tuple containing the following information:
497 * - @p cells : A vector of all the cells containing at least one of
498 * the @p points .
499 * - @p qpoints : A vector of vectors of points. @p qpoints[i] contains
500 * the reference positions of all points that fall within the cell @p cells[i] .
501 * - @p indices : A vector of vectors of integers, containing the mapping between
502 * local numbering the @p cells array (the first component of the returned
503 * tuple), and global index in the input array @p points . In other words,
504 * the indices stored in the array `indices[c]` correspond to those points
505 * of the input argument `points` that are located on `cells[c]`.
506 *
507 * If @p points[a] and @p points[b] are the only two points that fall in @p cells[c],
508 * then @p qpoints[c][0] and @p qpoints[c][1] are the reference positions of
509 * @p points[a] and @p points[b] in @p cells[c], and @p indices[c][0] = a,
510 * @p indices[c][1] = b. The function
511 * Mapping::transform_unit_to_real(qpoints[c][0])
512 * returns @p points[a].
513 *
514 * The algorithm builds an rtree of @p points to sort them spatially, before
515 * attempting to call find_active_cell_around_point().
516 *
517 * @note This function is not implemented for the codimension one case (<tt>spacedim != dim</tt>).
518 *
519 * @note If a point is not found inside the mesh, or is lying inside an
520 * artificial cell of a parallel::TriangulationBase, the point is silently
521 * ignored. If you want to infer for which points the search failed, use the
522 * function compute_point_locations_try_all() that also returns a vector of
523 * indices indicating the points for which the search failed.
524 *
525 * @note The actual return type of this function, i.e., the type referenced
526 * above as @p return_type, is
527 * @code
528 * std::tuple<
529 * std::vector<
530 * typename Triangulation<dim, spacedim>::active_cell_iterator>,
531 * std::vector<std::vector<Point<dim>>>,
532 * std::vector<std::vector<unsigned int>>>
533 * @endcode
534 * The type is abbreviated in the online documentation to improve readability
535 * of this page.
536 *
537 * @note This function optimizes the search by making use of
538 * GridTools::Cache::get_cell_bounding_boxes_rtree(), which either returns
539 * a cached rtree or builds and stores one. Building an rtree might hinder
540 * the performance if the function is called only once on few points.
541 */
542 template <int dim, int spacedim>
543 #ifndef DOXYGEN
544 std::tuple<
545 std::vector<typename Triangulation<dim, spacedim>::active_cell_iterator>,
546 std::vector<std::vector<Point<dim>>>,
547 std::vector<std::vector<unsigned int>>>
548 #else
549 return_type
550 #endif
551 compute_point_locations(
552 const Cache<dim, spacedim> &cache,
553 const std::vector<Point<spacedim>> &points,
554 const typename Triangulation<dim, spacedim>::active_cell_iterator
555 &cell_hint =
556 typename Triangulation<dim, spacedim>::active_cell_iterator());
557
558 /**
559 * This function is similar to GridTools::compute_point_locations(),
560 * but while compute_point_locations() silently ignores all points for which
561 * find_active_cell_around_point() fails, this function also returns a
562 * vector containing the indices of the points for which
563 * find_active_cell_around_point() failed.
564 *
565 * @return A tuple containing four elements; the first three
566 * are documented in GridTools::compute_point_locations().
567 * The last element of the @p return_type contains the
568 * indices of points which are neither found inside the mesh
569 * nor lie in artificial cells. The @p return_type equals the
570 * following tuple type:
571 * @code
572 * std::tuple<
573 * std::vector<
574 * typename Triangulation<dim,spacedim>::active_cell_iterator>,
575 * std::vector<std::vector<Point<dim>>>,
576 * std::vector<std::vector<unsigned int>>,
577 * std::vector<unsigned int>
578 * >
579 * @endcode
580 *
581 * @note This function is not implemented for the codimension one case (<tt>spacedim != dim</tt>).
582 *
583 * @note This function optimizes the search by making use of
584 * GridTools::Cache::get_cell_bounding_boxes_rtree(), which either returns
585 * a cached rtree or builds and stores one. Building an rtree might hinder
586 * the performance if the function is called only once on few points.
587 *
588 * For a more detailed documentation see
589 * GridTools::compute_point_locations().
590 */
591 template <int dim, int spacedim>
592 #ifndef DOXYGEN
593 std::tuple<
594 std::vector<typename Triangulation<dim, spacedim>::active_cell_iterator>,
595 std::vector<std::vector<Point<dim>>>,
596 std::vector<std::vector<unsigned int>>,
597 std::vector<unsigned int>>
598 #else
599 return_type
600 #endif
601 compute_point_locations_try_all(
602 const Cache<dim, spacedim> &cache,
603 const std::vector<Point<spacedim>> &points,
604 const typename Triangulation<dim, spacedim>::active_cell_iterator
605 &cell_hint =
606 typename Triangulation<dim, spacedim>::active_cell_iterator());
607
608 /**
609 * Given a @p cache and a list of
610 * @p local_points for each process, find the points lying on the locally
611 * owned part of the mesh and compute the quadrature rules for them.
612 * Distributed compute point locations is a function similar to
613 * GridTools::compute_point_locations but working for
614 * parallel::TriangulationBase objects and, unlike its serial version, also
615 * for a distributed triangulation (see parallel::distributed::Triangulation).
616 *
617 * @param[in] cache a GridTools::Cache object
618 * @param[in] local_points the array of points owned by the current process.
619 * Every process can have a different array of points which can be empty and
620 * not contained within the locally owned part of the triangulation
621 * @param[in] global_bboxes a vector of vectors of bounding boxes; it
622 * describes the locally owned part of the mesh for each process. The bounding
623 * boxes describing which part of the mesh is locally owned by process with
624 * rank rk are contained in global_bboxes[rk]. The local description can be
625 * obtained from GridTools::compute_mesh_predicate_bounding_box; then the
626 * global one can be obtained using either
627 * GridTools::exchange_local_bounding_boxes or Utilities::MPI::all_gather
628 * @param[in] tolerance Tolerance in terms of unit cell coordinates. Depending
629 * on the problem, it might be necessary to adjust the tolerance in order
630 * to be able to identify a cell. Floating
631 * point arithmetic implies that a point will, in general, not lie exactly
632 * on a vertex, edge, or face. In either case, it is not predictable which
633 * of the cells adjacent to a vertex or an edge/face this function returns.
634 * Consequently, algorithms that call this function need to take into
635 * account that the returned cell will only contain the point approximately.
636 * @param[in] enforce_unique_mapping Enforce a one to one mapping between
637 points
638 * in real and reference space.
639 * @param[in] marked_vertices An array of bools indicating which
640 * vertices of @p mesh will be considered within the search
641 * as the potentially closest vertex. On receiving a non-empty
642 * @p marked_vertices, the function will
643 * only search among @p marked_vertices for the closest vertex,
644 * otherwise on all vertices in the mesh.
645
646 * @return A tuple containing the quadrature information
647 *
648 * The elements of the output tuple are:
649 * - cells : a vector of all cells containing at least one point.
650 * - qpoints : a vector of vector of points; containing in @p qpoints[i]
651 * the reference positions of all points that fall within the cell @p cells[i] .
652 * - maps : a vector of vector of integers, containing the mapping between
653 * the numbering in qpoints (previous element of the tuple), and the vector
654 * of local points of the process owning the points.
655 * - points : a vector of vector of points. @p points[i][j] is the point in the
656 * real space corresponding.
657 * to @p qpoints[i][j] . Notice @p points are the points lying on the locally
658 * owned part of the mesh; thus these can be either copies of @p local_points
659 * or points received from other processes i.e. local_points for other
660 * processes
661 * - owners : a vector of vectors; @p owners[i][j] contains the rank of
662 * the process owning the point[i][j] (previous element of the tuple).
663 *
664 * The function uses the triangulation's mpi communicator: for this reason it
665 * throws an assert error if the Triangulation is not derived from
666 * parallel::TriangulationBase .
667 *
668 * In a serial execution the first three elements of the tuple are the same
669 * as in GridTools::compute_point_locations .
670 *
671 * Note: this function is a @ref GlossCollectiveOperation "collective operation".
672 *
673 * @note The actual return type of this function, i.e., the type referenced
674 * above as @p return_type, is
675 * @code
676 * std::tuple<
677 * std::vector<
678 * typename Triangulation<dim, spacedim>::active_cell_iterator>,
679 * std::vector<std::vector<Point<dim>>>,
680 * std::vector<std::vector<unsigned int>>,
681 * std::vector<std::vector<Point<spacedim>>>,
682 * std::vector<std::vector<unsigned int>>>
683 * @endcode
684 * The type is abbreviated in the online documentation to improve readability
685 * of this page.
686 */
687 template <int dim, int spacedim>
688 #ifndef DOXYGEN
689 std::tuple<
690 std::vector<typename Triangulation<dim, spacedim>::active_cell_iterator>,
691 std::vector<std::vector<Point<dim>>>,
692 std::vector<std::vector<unsigned int>>,
693 std::vector<std::vector<Point<spacedim>>>,
694 std::vector<std::vector<unsigned int>>>
695 #else
696 return_type
697 #endif
698 distributed_compute_point_locations(
699 const GridTools::Cache<dim, spacedim> &cache,
700 const std::vector<Point<spacedim>> &local_points,
701 const std::vector<std::vector<BoundingBox<spacedim>>> &global_bboxes,
702 const double tolerance = 1e-10,
703 const std::vector<bool> &marked_vertices = {},
704 const bool enforce_unique_mapping = true);
705
706 namespace internal
707 {
708 /**
709 * Data structure returned by
710 * GridTools::internal::distributed_compute_point_locations(). It provides
711 * information to perform GridTools::distributed_compute_point_locations()
712 * and to set up the communication pattern within
713 * Utilities::MPI::RemotePointEvaluation::reinit().
714 *
715 * @note The name of the fields are chosen with
716 * Utilities::MPI::RemotePointEvaluation in mind. Here, quantities are
717 * computed at specified arbitrary positioned points (and even on remote
718 * processes in the MPI universe) cell by cell and these values are sent
719 * to requesting processes, which receive the result and resort the
720 * result according to the points.
721 */
722 template <int dim, int spacedim>
723 struct DistributedComputePointLocationsInternal
724 {
725 DistributedComputePointLocationsInternal();
726
727 /**
728 * Function which sets up @p send_ranks, @p send_ptrs, @p recv_ranks,
729 * and @p recv_ptrs from @p send_components, @p recv_components,
730 * and @p n_searched_points. Internally @p send_components and @p recv_components
731 * are sorted and enumerated.
732 */
733 void
734 finalize_setup();
735
736 /**
737 * Number of searched point locations.
738 */
739 unsigned int n_searched_points;
740
741 /**
742 * Information of each point on sending/evaluation side. The elements of
743 * the tuple are as follows: 0) cell level and index, 1) rank of the
744 * owning process, 2) local index of the owning process, 3) reference
745 * position, 4) real position, 5) permutation index within a send buffer.
746 */
747 std::vector<std::tuple<std::pair<int, int>,
748 unsigned int,
749 unsigned int,
750 Point<dim>,
751 Point<spacedim>,
752 unsigned int>>
753 send_components;
754
755 /**
756 * Ranks to send to.
757 */
758 std::vector<unsigned int> send_ranks;
759
760 /**
761 * Pointers of ranges within a send buffer to be sent to the ranks
762 * specified by send_ranks. The size of the send buffer is given
763 * by send_ptrs.back().
764 */
765 std::vector<unsigned int> send_ptrs;
766
767 /**
768 * Information of each received data value. The elements of the tuple are
769 * as follows: 0) rank of sender, 1) local index, 2) enumeration index.
770 *
771 * @note The vector is sorted according to 1), 0), 2).
772 *
773 * @note To each point multiple data values might be associated to. This
774 * might be the case if a point coincides with a geometric entity (e.g.,
775 * vertex) that is shared by multiple cells.
776 */
777 std::vector<std::tuple<unsigned int, unsigned int, unsigned int>>
778 recv_components;
779
780 /**
781 * Ranks from where data is received.
782 */
783 std::vector<unsigned int> recv_ranks;
784
785 /**
786 * Pointers of ranges within a receive buffer that are filled by ranks
787 * specified by recv_ranks. The size of the receive buffer is given by
788 * recv_ptrs.back().
789 */
790 std::vector<unsigned int> recv_ptrs;
791 };
792
793 /**
794 * A function that fills DistributedComputePointLocationsInternal.
795 * If the input argument @p perform_handshake is set to false only
796 * the fields needed by
797 * GridTools::internal::distributed_compute_point_locations() are filled.
798 * If the input argument is set to true additional data structures are
799 * set up to be able to set up the communication pattern within
800 * Utilities::MPI::RemotePointEvaluation::reinit().
801 */
802 template <int dim, int spacedim>
803 DistributedComputePointLocationsInternal<dim, spacedim>
804 distributed_compute_point_locations(
805 const GridTools::Cache<dim, spacedim> &cache,
806 const std::vector<Point<spacedim>> &points,
807 const std::vector<std::vector<BoundingBox<spacedim>>> &global_bboxes,
808 const std::vector<bool> &marked_vertices,
809 const double tolerance,
810 const bool perform_handshake,
811 const bool enforce_unique_mapping = false);
812
813
814 /**
815 * Data structure returned by
816 * GridTools::internal::distributed_compute_intersection_locations(). It can
817 * be converted to
818 * GridTools::internal::DistributedComputePointLocationsInternal, which can
819 * be used to reinit Utilities::MPI::RemotePointEvaluation.
820 */
821 template <int structdim, int spacedim>
822 struct DistributedComputeIntersectionLocationsInternal
823 {
824 /**
825 * Intersections are assumed to be simplices (as, e.g., provided by CGAL)
826 */
827 using IntersectionType =
828 std::array<dealii::Point<spacedim>, structdim + 1>;
829
830 /**
831 * Information of each intersection on sending/evaluation side. The
832 * elements of the tuple are as follows: 0) cell level and index, 1) rank
833 * of the owning process, 2) local index of the owning process, 3)
834 * found intersection.
835 *
836 * @note The vector is sorted according to 1), 2).
837 */
838 std::vector<std::tuple<std::pair<int, int>,
839 unsigned int,
840 unsigned int,
841 IntersectionType>>
842 send_components;
843
844 /**
845 * Information of each received data value. The elements of the tuple are
846 * as follows: 0) rank of sender, 1) local index, 2) found intersections.
847 *
848 * @note The vector is sorted according to 1), 0), 2).
849 *
850 * @note Multiple intersections between cells can be found
851 */
852 std::vector<std::tuple<unsigned int, unsigned int, IntersectionType>>
853 recv_components;
854
855 /**
856 * Pointers of ranges to found intersections for requested intersection.
857 */
858 std::vector<unsigned int> recv_ptrs;
859
860 /**
861 * Distribute quadrature points according to
862 * QGaussSimplex<structdim>(n_points_1D) on found intersections and
863 * construct GridTools::internal::DistributedComputePointLocationsInternal
864 * from class members. This can be done without searching for points again
865 * since all information is locally known.
866 *
867 * @p mapped_quadratures_recv_comp is a pointer to an empty vector of
868 * mapped quadratures. By default it is a `nullptr` and the parameter is
869 * ignored. Otherwise, the vector is filled with the mapped quadrature
870 * rules (in real coordinates) corresponding to recv_components.
871 *
872 * The parameter @p consistent_numbering_of_sender_and_receiver can be used to ensure
873 * points on sender and receiver side are numbered consistently.
874 * This parameter is optional if DistributedComputePointLocationsInternal
875 * is used to set up RemotePointEvaluation, but might be helpful for
876 * debugging or other usage of DistributedComputePointLocationsInternal.
877 * Note that setting this parameter true requires an additional
878 * communication step during the setup phase.
879 */
880 template <int dim>
881 GridTools::internal::DistributedComputePointLocationsInternal<dim,
882 spacedim>
883 convert_to_distributed_compute_point_locations_internal(
884 const unsigned int n_points_1D,
885 const Triangulation<dim, spacedim> &tria,
886 const Mapping<dim, spacedim> &mapping,
887 std::vector<Quadrature<spacedim>> *mapped_quadratures_recv_comp =
888 nullptr,
889 const bool consistent_numbering_of_sender_and_receiver = false) const;
890
891 private:
892 /**
893 * Helper function for
894 * convert_to_distributed_compute_point_locations_internal(). It sends the
895 * indices associated to quadrature points at the receiver side to the
896 * sender side, where the information is needed to build
897 * GridTools::internal::DistributedComputePointLocationsInternal::send_components
898 */
899 std::map<unsigned int, std::vector<unsigned int>>
900 communicate_indices(
901 const std::vector<std::tuple<unsigned int, unsigned int, unsigned int>>
902 &point_recv_components,
903 const MPI_Comm comm) const;
904 };
905
906 /**
907 * A function that fills DistributedComputeIntersectionLocationsInternal.
908 * @p intersection_requests are vertices of cells which describe the
909 * entities we want to search intersections for.
910 * The template parameter @p structdim provides the dimension of the
911 * resulting intersection.
912 */
913 template <int structdim, int dim, int spacedim>
914 DistributedComputeIntersectionLocationsInternal<structdim, spacedim>
915 distributed_compute_intersection_locations(
916 const Cache<dim, spacedim> &cache,
917 const std::vector<std::vector<Point<spacedim>>> &intersection_requests,
918 const std::vector<std::vector<BoundingBox<spacedim>>> &global_bboxes,
919 const std::vector<bool> &marked_vertices,
920 const double tolerance);
921
922 } // namespace internal
923
924 /**
925 * Find and return the index of the closest vertex to a given point in the
926 * map of vertices passed as the first argument.
927 *
928 * @param vertices A map of index->vertex, as returned by
929 * GridTools::extract_used_vertices().
930 * @param p The target point.
931 * @return The index of the vertex that is closest to the target point `p`.
932 */
933 template <int spacedim>
934 unsigned int
935 find_closest_vertex(const std::map<unsigned int, Point<spacedim>> &vertices,
936 const Point<spacedim> &p);
937
938 /**
939 * Find and return the index of the used vertex (or marked vertex) in a
940 * given mesh that is located closest to a given point.
941 *
942 * This function uses the locations of vertices as stored in the
943 * triangulation. This is usually sufficient, unless you are using a Mapping
944 * that moves the vertices around (for example, MappingQEulerian). In this
945 * case, you should call the function with the same name and with an
946 * additional Mapping argument.
947 *
948 * @param mesh A variable of a type that satisfies the requirements of the
949 * @ref ConceptMeshType "MeshType concept".
950 * @param p The point for which we want to find the closest vertex.
951 * @param marked_vertices An array of bools indicating which
952 * vertices of @p mesh will be considered within the search
953 * as the potentially closest vertex. On receiving a non-empty
954 * @p marked_vertices, the function will
955 * only search among @p marked_vertices for the closest vertex.
956 * The size of this array should be equal to the value returned by
957 * Triangulation::n_vertices() for the triangulation underlying the given mesh
958 * (as opposed to the value returned by Triangulation::n_used_vertices()).
959 * @return The index of the closest vertex found.
960 *
961 * @dealiiConceptRequires{
962 * concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>}
963 */
964 template <int dim, template <int, int> class MeshType, int spacedim>
965 DEAL_II_CXX20_REQUIRES(
966 (concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>))
967 unsigned int find_closest_vertex(
968 const MeshType<dim, spacedim> &mesh,
969 const Point<spacedim> &p,
970 const std::vector<bool> &marked_vertices = {});
971
972 /**
973 * Find and return the index of the used vertex (or marked vertex) in a
974 * given mesh that is located closest to a given point. Use the given
975 * mapping to compute the actual location of the vertices.
976 *
977 * If the Mapping does not modify the position of the mesh vertices (like,
978 * for example, MappingQEulerian does), then this function is equivalent to
979 * the one with the same name, and without the `mapping` argument.
980 *
981 * @param mapping A mapping used to compute the vertex locations
982 * @param mesh A variable of a type that satisfies the requirements of the
983 * @ref ConceptMeshType "MeshType concept".
984 * @param p The point for which we want to find the closest vertex.
985 * @param marked_vertices An array of bools indicating which
986 * vertices of @p mesh will be considered within the search
987 * as the potentially closest vertex. On receiving a non-empty
988 * @p marked_vertices, the function will
989 * only search among @p marked_vertices for the closest vertex.
990 * The size of this array should be equal to the value returned by
991 * Triangulation::n_vertices() for the triangulation underlying the given mesh
992 * (as opposed to the value returned by Triangulation::n_used_vertices()).
993 * @return The index of the closest vertex found.
994 *
995 * @dealiiConceptRequires{
996 * concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>}
997 */
998 template <int dim, template <int, int> class MeshType, int spacedim>
999 DEAL_II_CXX20_REQUIRES(
1000 (concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>))
1001 unsigned int find_closest_vertex(
1002 const Mapping<dim, spacedim> &mapping,
1003 const MeshType<dim, spacedim> &mesh,
1004 const Point<spacedim> &p,
1005 const std::vector<bool> &marked_vertices = {});
1006
1007
1008 /**
1009 * Find and return a vector of iterators to active cells that surround a
1010 * given vertex with index @p vertex_index.
1011 *
1012 * For locally refined grids, the vertex itself might not be a vertex of all
1013 * adjacent cells that are returned. However, it will always be either a
1014 * vertex of a cell or be a hanging node located on a face or an edge of it.
1015 *
1016 * @param container A variable of a type that satisfies the requirements of
1017 * the
1018 * @ref ConceptMeshType "MeshType concept".
1019 * @param vertex_index The index of the vertex for which we try to find
1020 * adjacent cells.
1021 * @return A vector of cells that lie adjacent to the given vertex.
1022 *
1023 * @note It isn't entirely clear at this time whether the function does the
1024 * right thing with anisotropically refined meshes. It needs to be checked
1025 * for this case.
1026 *
1027 * @dealiiConceptRequires{
1028 * concepts::is_triangulation_or_dof_handler<MeshType>}
1029 */
1030 template <typename MeshType>
1031 DEAL_II_CXX20_REQUIRES((concepts::is_triangulation_or_dof_handler<MeshType>))
1032 #ifndef _MSC_VER
1033 std::vector<typename MeshType::active_cell_iterator>
1034 #else
1035 std::vector<
1036 typename dealii::internal::ActiveCellIterator<MeshType::dimension,
1037 MeshType::space_dimension,
1038 MeshType>::type>
1039 #endif
1040 find_cells_adjacent_to_vertex(const MeshType &container,
1041 const unsigned int vertex_index);
1042
1043 /**
1044 * Find an active non-artificial cell that surrounds a given point @p p. The return type
1045 * is a pair of an iterator to the active cell along with the unit cell
1046 * coordinates of the point.
1047 *
1048 * The algorithm used in this function proceeds by first looking for the
1049 * vertex located closest to the given point, see
1050 * GridTools::find_closest_vertex(). Secondly, all adjacent cells to this
1051 * vertex are found in the mesh, see
1052 * GridTools::find_cells_adjacent_to_vertex(). Lastly, for each of these
1053 * cells, the function tests whether the point is inside. This check is
1054 * performed using the given @p mapping argument to determine whether cells
1055 * have straight or curved boundaries.
1056 *
1057 * If a point lies on the boundary of two or more cells, then the algorithm
1058 * tries to identify the cell that is of highest refinement level.
1059 *
1060 * If the point requested does not lie in a locally-owned or ghost cell,
1061 * then this function will return the (invalid) MeshType<dim, spacedim>::end()
1062 * iterator. This case can be handled similarly to the various `std::find()`
1063 * and `std::lower_bound()` functions.
1064 *
1065 * @param mapping The mapping used to determine whether the given point is
1066 * inside a given cell.
1067 * @param mesh A variable of a type that satisfies the requirements of the
1068 * @ref ConceptMeshType "MeshType concept".
1069 * @param p The point for which we want to find the surrounding cell.
1070 * @param marked_vertices An array of `bool`s indicating whether an
1071 * entry in the vertex array should be considered
1072 * (and the others must be ignored) as the potentially
1073 * closest vertex to the specified point. On specifying a non-default
1074 * @p marked_vertices, find_closest_vertex() would
1075 * only search among @p marked_vertices for the closest vertex.
1076 * The size of this array should be equal to n_vertices() of the
1077 * triangulation (as opposed to n_used_vertices() ). The motivation of using
1078 * @p marked_vertices is to cut down the search space of vertices if one has
1079 * a priori knowledge of a collection of vertices that the point of interest
1080 * may be close to.
1081 * @param tolerance Tolerance in terms of unit cell coordinates. Depending
1082 * on the problem, it might be necessary to adjust the tolerance in order
1083 * to be able to identify a cell. Floating
1084 * point arithmetic implies that a point will, in general, not lie exactly
1085 * on a vertex, edge, or face. In either case, it is not predictable which
1086 * of the cells adjacent to a vertex or an edge/face this function returns.
1087 * Consequently, algorithms that call this function need to take into
1088 * account that the returned cell will only contain the point approximately.
1089 *
1090 * @return A pair of an iterators into the mesh that points to the
1091 * surrounding cell, and of the unit cell coordinates of that point. This
1092 * local position might be located slightly outside an actual unit cell,
1093 * due to numerical roundoff. Therefore, the point returned by this function
1094 * should be projected onto the unit cell, using
1095 * ReferenceCell::closest_point(). This is not automatically performed
1096 * by the algorithm. The returned cell can be a locally-owned cell or a
1097 * ghost cell (but not an artificial cell). The returned cell might be a
1098 * ghost cell even if the given point is a vertex of a locally owned cell.
1099 * The reason behind is that this is the only way to guarantee that all
1100 * processors that participate in a parallel triangulation will agree which
1101 * cell contains a point. For example, if two processors come together
1102 * at one vertex and the function is called with this vertex, then one
1103 * processor will return a locally owned cell and the other one a ghost cell.
1104 *
1105 * @dealiiConceptRequires{
1106 * concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>}
1107 */
1108 template <int dim, template <int, int> class MeshType, int spacedim>
1109 DEAL_II_CXX20_REQUIRES(
1110 (concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>))
1111 #ifndef _MSC_VER
1112 std::pair<typename MeshType<dim, spacedim>::active_cell_iterator, Point<dim>>
1113 #else
1114 std::pair<typename dealii::internal::
1115 ActiveCellIterator<dim, spacedim, MeshType<dim, spacedim>>::type,
1116 Point<dim>>
1117 #endif
1118 find_active_cell_around_point(const Mapping<dim, spacedim> &mapping,
1119 const MeshType<dim, spacedim> &mesh,
1120 const Point<spacedim> &p,
1121 const std::vector<bool> &marked_vertices = {},
1122 const double tolerance = 1.e-10);
1123
1124 /**
1125 * A version of the above function that assumes straight boundaries and
1126 * as a consequence simply calls the above function using MappingQ1 for
1127 * the mapping argument.
1128 *
1129 * @return An iterator into the mesh that points to the surrounding cell.
1130 *
1131 * @dealiiConceptRequires{
1132 * concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>}
1133 */
1134 template <int dim, template <int, int> class MeshType, int spacedim>
1135 DEAL_II_CXX20_REQUIRES(
1136 (concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>))
1137 #ifndef _MSC_VER
1138 typename MeshType<dim, spacedim>::active_cell_iterator
1139 #else
1140 typename dealii::internal::
1141 ActiveCellIterator<dim, spacedim, MeshType<dim, spacedim>>::type
1142 #endif
1143 find_active_cell_around_point(const MeshType<dim, spacedim> &mesh,
1144 const Point<spacedim> &p,
1145 const std::vector<bool> &marked_vertices = {},
1146 const double tolerance = 1.e-10);
1147
1148 /**
1149 * Another version where we use that mapping on a given
1150 * cell that corresponds to the active finite element index of that cell.
1151 * This is obviously only useful for hp-problems, since the active finite
1152 * element index for all other DoF handlers is always zero.
1153 */
1154 template <int dim, int spacedim>
1155 std::pair<typename DoFHandler<dim, spacedim>::active_cell_iterator,
1156 Point<dim>>
1157 find_active_cell_around_point(
1158 const hp::MappingCollection<dim, spacedim> &mapping,
1159 const DoFHandler<dim, spacedim> &mesh,
1160 const Point<spacedim> &p,
1161 const double tolerance = 1.e-10);
1162
1163 /**
1164 * Finding an active non-artificial cell around a point can be very expensive
1165 * in terms of computational costs. This function aims at providing a fast
1166 * version of the above functions by using a space-tree to speed up the
1167 * geometry search.
1168 *
1169 * @param cache Object with information about the space-tree of a triangulation,
1170 * see GridTools::Cache.
1171 * @param p The point for which we want to find the surrounding cell.
1172 * @param cell_hint Gives a hint for the geometry search, which is beneficial
1173 * if a-priori knowledge is available regarding the cell on which the point
1174 * may likely be located. A typical use case would be that this search has
1175 * to be done for an array of points that are close to each other and where
1176 * the adjacent cell of the previous point is a good hint for the next point
1177 * in the array.
1178 * @param marked_vertices See above.
1179 * @param tolerance See above.
1180 *
1181 *
1182 * The following code example shows how to use this function:
1183 *
1184 * @code
1185 * GridTools::Cache<dim, dim> cache(triangulation, mapping);
1186 * auto cell_hint = typename Triangulation<dim, dim>::active_cell_iterator();
1187 * std::vector<bool> marked_vertices = {};
1188 * double tolerance = 1.e-10;
1189 *
1190 * std::vector<Point<dim>> points; // a vector of many points
1191 * ...
1192 *
1193 * for(auto p : points)
1194 * {
1195 * auto cell_and_ref_point = GridTools::find_active_cell_around_point(
1196 * cache, p, cell_hint, marked_vertices, tolerance);
1197 *
1198 * if (cell_and_ref_point.first != triangulation.end())
1199 * {
1200 * // use current cell as hint for the next point
1201 * cell_hint = cell_and_ref_point.first;
1202 * // do something with cell_and_ref_point
1203 * ...
1204 * }
1205 * else
1206 * {
1207 * // The function did not find a locally owned or ghost cell in which
1208 * // the point is located. We ought to handle this somehow here.
1209 * }
1210 * ...
1211 * }
1212 * @endcode
1213 */
1214 template <int dim, int spacedim>
1215 std::pair<typename Triangulation<dim, spacedim>::active_cell_iterator,
1216 Point<dim>>
1217 find_active_cell_around_point(
1218 const Cache<dim, spacedim> &cache,
1219 const Point<spacedim> &p,
1220 const typename Triangulation<dim, spacedim>::active_cell_iterator &
1221 cell_hint = typename Triangulation<dim, spacedim>::active_cell_iterator(),
1222 const std::vector<bool> &marked_vertices = {},
1223 const double tolerance = 1.e-10);
1224
1225 /**
1226 * A version of the previous function that exploits an already existing
1227 * map between vertices and cells (constructed using the function
1228 * GridTools::vertex_to_cell_map()), a map of vertex_to_cell_centers (obtained
1229 * through GridTools::vertex_to_cell_centers_directions()), and
1230 * optionally an RTree constructed from the used vertices of the
1231 * Triangulation.
1232 *
1233 * @note All of these structures can be queried from a
1234 * GridTools::Cache object. Note, however, that in this case MeshType
1235 * has to be Triangulation, so that it might be more appropriate to directly
1236 * call the function above with argument `cache` in this case.
1237 *
1238 * @dealiiConceptRequires{
1239 * concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>}
1240 */
1241 template <int dim, template <int, int> class MeshType, int spacedim>
1242 DEAL_II_CXX20_REQUIRES(
1243 (concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>))
1244 #ifndef _MSC_VER
1245 std::pair<typename MeshType<dim, spacedim>::active_cell_iterator, Point<dim>>
1246 #else
1247 std::pair<typename dealii::internal::
1248 ActiveCellIterator<dim, spacedim, MeshType<dim, spacedim>>::type,
1249 Point<dim>>
1250 #endif
1251 find_active_cell_around_point(
1252 const Mapping<dim, spacedim> &mapping,
1253 const MeshType<dim, spacedim> &mesh,
1254 const Point<spacedim> &p,
1255 const std::vector<
1256 std::set<typename MeshType<dim, spacedim>::active_cell_iterator>>
1257 &vertex_to_cell_map,
1258 const std::vector<std::vector<Tensor<1, spacedim>>>
1259 &vertex_to_cell_centers,
1260 const typename MeshType<dim, spacedim>::active_cell_iterator &cell_hint =
1261 typename MeshType<dim, spacedim>::active_cell_iterator(),
1262 const std::vector<bool> &marked_vertices = {},
1263 const RTree<std::pair<Point<spacedim>, unsigned int>> &
1264 used_vertices_rtree = RTree<std::pair<Point<spacedim>, unsigned int>>{},
1265 const double tolerance = 1.e-10,
1266 const RTree<
1267 std::pair<BoundingBox<spacedim>,
1268 typename Triangulation<dim, spacedim>::active_cell_iterator>>
1269 *relevant_cell_bounding_boxes_rtree = nullptr);
1270
1271 /**
1272 * As compared to the functions above, this function identifies all active
1273 * non-artificial cells around a point for a given tolerance level `tolerance`
1274 * in terms of unit coordinates. Given a first cell with reference coordinates
1275 * as parameter
1276 * @p first_cell, e.g. obtained by one of the functions above, all
1277 * corresponding neighboring cells with points in unit coordinates are also
1278 * identified.
1279 *
1280 * The parameter @p vertex_to_cells allows to accelerate the process of
1281 * identifying the neighbors of a cell, by first precomputing a map from the
1282 * vertex indices to the cells. Such data structure is, e.g., provided by
1283 * GridTools::Cache::get_vertex_to_cell_map().
1284 *
1285 * This function is useful e.g. for discontinuous function spaces where, for
1286 * the case the given point `p` lies on a vertex, edge or face, several
1287 * cells might hold independent values of the solution that get combined in
1288 * some way in a user code.
1289 *
1290 * This function is used as follows
1291 * @code
1292 * auto first_pair = GridTools::find_active_cell_around_point(...);
1293 * auto all_cells = GridTools::find_all_active_cells_around_point(
1294 * mapping, mesh, p, tolerance, first_pair);
1295 * @endcode
1296 *
1297 * @dealiiConceptRequires{
1298 * concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>}
1299 */
1300 template <int dim, template <int, int> class MeshType, int spacedim>
1301 DEAL_II_CXX20_REQUIRES(
1302 (concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>))
1303 #ifndef _MSC_VER
1304 std::vector<std::pair<typename MeshType<dim, spacedim>::active_cell_iterator,
1305 Point<dim>>>
1306 #else
1307 std::vector<std::pair<
1308 typename dealii::internal::
1309 ActiveCellIterator<dim, spacedim, MeshType<dim, spacedim>>::type,
1310 Point<dim>>>
1311 #endif
1312 find_all_active_cells_around_point(
1313 const Mapping<dim, spacedim> &mapping,
1314 const MeshType<dim, spacedim> &mesh,
1315 const Point<spacedim> &p,
1316 const double tolerance,
1317 const std::pair<typename MeshType<dim, spacedim>::active_cell_iterator,
1318 Point<dim>> &first_cell,
1319 const std::vector<
1320 std::set<typename MeshType<dim, spacedim>::active_cell_iterator>>
1321 *vertex_to_cells = nullptr);
1322
1323 /**
1324 * A variant of the previous function that internally calls one of the
1325 * functions find_active_cell_around_point() to obtain a first cell, and
1326 * subsequently adds all other active non-artificial cells by calling the
1327 * function find_all_active_cells_around_point() above.
1328 *
1329 * @dealiiConceptRequires{
1330 * concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>}
1331 */
1332 template <int dim, template <int, int> class MeshType, int spacedim>
1333 DEAL_II_CXX20_REQUIRES(
1334 (concepts::is_triangulation_or_dof_handler<MeshType<dim, spacedim>>))
1335 #ifndef _MSC_VER
1336 std::vector<std::pair<typename MeshType<dim, spacedim>::active_cell_iterator,
1337 Point<dim>>>
1338 #else
1339 std::vector<std::pair<
1340 typename dealii::internal::
1341 ActiveCellIterator<dim, spacedim, MeshType<dim, spacedim>>::type,
1342 Point<dim>>>
1343 #endif
1344 find_all_active_cells_around_point(
1345 const Mapping<dim, spacedim> &mapping,
1346 const MeshType<dim, spacedim> &mesh,
1347 const Point<spacedim> &p,
1348 const double tolerance = 1e-10,
1349 const std::vector<bool> &marked_vertices = {});
1350
1351 /**
1352 * Return a list of all descendants of the given cell that are active. For
1353 * example, if the current cell is once refined but none of its children are
1354 * any further refined, then the returned list will contain all its
1355 * children.
1356 *
1357 * If the current cell is already active, then the returned list is empty
1358 * (because the cell has no children that may be active).
1359 *
1360 * @tparam MeshType A type that satisfies the requirements of the
1361 * @ref ConceptMeshType "MeshType concept".
1362 * @param cell An iterator pointing to a cell of the mesh.
1363 * @return A list of active descendants of the given cell
1364 *
1365 * @note Since in C++ the MeshType template argument can not be deduced from
1366 * a function call, you will have to specify it after the function name, as
1367 * for example in
1368 * @code
1369 * GridTools::get_active_child_cells<DoFHandler<dim> > (cell)
1370 * @endcode
1371 *
1372 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1373 */
1374 template <typename MeshType>
1375 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1376 std::vector<typename MeshType::active_cell_iterator> get_active_child_cells(
1377 const typename MeshType::cell_iterator &cell);
1378
1379 /**
1380 * Extract the active cells around a given cell @p cell and return them in
1381 * the vector @p active_neighbors. These neighbors are specifically the
1382 * <i>face</i> neighbors of a cell or, if that neighbor is further
1383 * refined, its active children that border on that face. On the other
1384 * hand, the neighbors returned do not include cells that lie, for
1385 * example, diagonally opposite to a vertex but are not face neighbors
1386 * themselves. (In 3d, it also does not include cells that are
1387 * adjacent to one of the edges of the current cell, but are not
1388 * face neighbors.)
1389 *
1390 * @tparam MeshType A type that satisfies the requirements of the
1391 * @ref ConceptMeshType "MeshType concept".
1392 * @param[in] cell An iterator pointing to a cell of the mesh.
1393 * @param[out] active_neighbors A list of active descendants of the given
1394 * cell
1395 *
1396 * @note Since in C++ the MeshType template argument can not be deduced from
1397 * a function call, you will have to specify it after the function name, as
1398 * for example in
1399 * @code
1400 * GridTools::get_active_neighbors<DoFHandler<dim>>(cell, active_neighbors)
1401 * @endcode
1402 *
1403 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1404 */
1405 template <typename MeshType>
1406 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1407 void get_active_neighbors(
1408 const typename MeshType::active_cell_iterator &cell,
1409 std::vector<typename MeshType::active_cell_iterator> &active_neighbors);
1410
1411 /**
1412 * Extract and return the active cell layer around a subdomain (set of
1413 * active cells) in the @p mesh (i.e. those that share a common set of
1414 * vertices with the subdomain but are not a part of it). Here, the
1415 * "subdomain" consists of exactly all of those cells for which the @p
1416 * predicate returns @p true.
1417 *
1418 * An example of a custom predicate is one that checks for a given material
1419 * id
1420 * @code
1421 * template <int dim>
1422 * bool
1423 * pred_mat_id(const typename Triangulation<dim>::active_cell_iterator & cell)
1424 * {
1425 * return cell->material_id() == 1;
1426 * }
1427 * @endcode
1428 * and we can then extract the layer of cells around this material with the
1429 * following call:
1430 * @code
1431 * GridTools::compute_active_cell_halo_layer(tria, pred_mat_id<dim>);
1432 * @endcode
1433 *
1434 * Predicates that are frequently useful can be found in namespace
1435 * IteratorFilters. For example, it is possible to extract a layer
1436 * of cells around all of those cells with a given material id,
1437 * @code
1438 * GridTools::compute_active_cell_halo_layer(
1439 * tria, IteratorFilters::MaterialIdEqualTo(1, true));
1440 * @endcode
1441 * or around all cells with one of a set of active FE indices for a DoFHandler
1442 * with hp-capabilities
1443 * @code
1444 * GridTools::compute_active_cell_halo_layer(
1445 * hp_dof_handler, IteratorFilters::ActiveFEIndexEqualTo({1,2}, true));
1446 * @endcode
1447 * Note that in the last two examples we ensure that the predicate returns
1448 * true only for locally owned cells. This means that the halo layer will
1449 * not contain any artificial cells.
1450 *
1451 * @tparam MeshType A type that satisfies the requirements of the
1452 * @ref ConceptMeshType "MeshType concept".
1453 * @param[in] mesh A mesh (i.e. objects of type Triangulation or DoFHandler).
1454 * @param[in] predicate A function (or object of a type with an operator())
1455 * defining the subdomain around which the halo layer is to be extracted. It
1456 * is a function that takes in an active cell and returns a boolean.
1457 * @return A list of active cells sharing at least one common vertex with
1458 * the predicated subdomain.
1459 *
1460 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1461 */
1462 template <typename MeshType>
1463 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1464 std::
1465 vector<typename MeshType::active_cell_iterator> compute_active_cell_halo_layer(
1466 const MeshType &mesh,
1467 const std::function<bool(const typename MeshType::active_cell_iterator &)>
1468 &predicate);
1469
1470
1471 /**
1472 * Extract and return the cell layer around a subdomain (set of
1473 * cells) on a specified level of the @p mesh (i.e. those cells on
1474 * that level that share a common set of vertices with the subdomain
1475 * but are not a part of it). Here, the "subdomain" consists of exactly
1476 * all of those cells for which the @p predicate returns @p true.
1477 *
1478 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1479 */
1480 template <typename MeshType>
1481 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1482 std::
1483 vector<typename MeshType::cell_iterator> compute_cell_halo_layer_on_level(
1484 const MeshType &mesh,
1485 const std::function<bool(const typename MeshType::cell_iterator &)>
1486 &predicate,
1487 const unsigned int level);
1488
1489
1490 /**
1491 * Extract and return ghost cells which are the active cell layer around all
1492 * locally owned cells. This is most relevant for
1493 * parallel::shared::Triangulation where it will return a subset of all
1494 * ghost cells on a processor, but for parallel::distributed::Triangulation
1495 * this will return all the ghost cells.
1496 *
1497 * @tparam MeshType A type that satisfies the requirements of the
1498 * @ref ConceptMeshType "MeshType concept".
1499 * @param[in] mesh A mesh (i.e. objects of type Triangulation or DoFHandler).
1500 * @return A list of ghost cells
1501 *
1502 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1503 */
1504 template <typename MeshType>
1505 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1506 std::vector<
1507 typename MeshType::
1508 active_cell_iterator> compute_ghost_cell_halo_layer(const MeshType &mesh);
1509
1510 /**
1511 * Extract and return the set of active cells within a geometric distance of
1512 * @p layer_thickness around a subdomain (set of active cells) in the @p mesh.
1513 * Here, the "subdomain" consists of exactly all of
1514 * those cells for which the @p predicate returns @p true.
1515 *
1516 * The function first computes the cells that form the 'surface' of the
1517 * subdomain that consists of all of the active cells for which the predicate
1518 * is true. Using compute_bounding_box(), a bounding box is
1519 * computed for this subdomain and extended by @p layer_thickness. These
1520 * cells are called interior subdomain boundary cells.
1521 * The active cells with all of their vertices outside the extended
1522 * bounding box are ignored.
1523 * The cells that are inside the extended bounding box are then checked for
1524 * their proximity to the interior subdomain boundary cells. This implies
1525 * checking the distance between a pair of arbitrarily oriented cells,
1526 * which is not trivial in general. To simplify this, the algorithm checks
1527 * the distance between the two enclosing spheres of the cells.
1528 * This will definitely result in slightly more cells being marked but
1529 * also greatly simplifies the arithmetic complexity of the algorithm.
1530 *
1531 * @image html active_cell_layer_within_distance.png
1532 * The image shows a mesh generated by subdivided_hyper_rectangle(). The cells
1533 * are marked using three different colors. If the grey colored cells in the
1534 * image are the cells for which the predicate is true, then the function
1535 * compute_active_cell_layer_within_distance() will return a set of cell
1536 * iterators corresponding to the cells colored in red.
1537 * The red colored cells are the active cells that are within a given
1538 * distance to the grey colored cells.
1539 *
1540 * @tparam MeshType A type that satisfies the requirements of the
1541 * @ref ConceptMeshType "MeshType concept".
1542 * @param mesh A mesh (i.e. objects of type Triangulation or DoFHandler).
1543 * @param predicate A function (or object of a type with an operator())
1544 * defining the subdomain around which the halo layer is to be extracted. It
1545 * is a function that takes in an active cell and returns a boolean.
1546 * @param layer_thickness specifies the geometric distance within
1547 * which the function searches for active cells from the predicate domain.
1548 * If the minimal distance between the enclosing sphere of the an
1549 * active cell and the enclosing sphere of any of the cells for which
1550 * the @p predicate returns @p true is less than @p layer_thickness,
1551 * then the active cell is an \a active_cell_within_distance.
1552 * @return A list of active cells within a given geometric distance
1553 * @p layer_thickness from the set of active cells for which the @p predicate
1554 * returns @p true.
1555 *
1556 * See compute_active_cell_halo_layer().
1557 *
1558 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1559 */
1560 template <typename MeshType>
1561 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1562 std::
1563 vector<typename MeshType::active_cell_iterator> compute_active_cell_layer_within_distance(
1564 const MeshType &mesh,
1565 const std::function<bool(const typename MeshType::active_cell_iterator &)>
1566 &predicate,
1567 const double layer_thickness);
1568
1569 /**
1570 * Extract and return a set of ghost cells which are within a
1571 * @p layer_thickness around all locally owned cells.
1572 * This is most relevant for parallel::shared::Triangulation
1573 * where it will return a subset of all ghost cells on a process, but for
1574 * parallel::distributed::Triangulation this will return all the ghost cells.
1575 * All the cells for the parallel::shared::Triangulation class that
1576 * are not owned by the current processor can be considered as ghost cells;
1577 * in particular, they do not only form a single layer of cells around the
1578 * locally owned ones.
1579 *
1580 * @tparam MeshType A type that satisfies the requirements of the
1581 * @ref ConceptMeshType "MeshType concept".
1582 * @param mesh A mesh (i.e. objects of type Triangulation or DoFHandler).
1583 * @param layer_thickness specifies the geometric distance within
1584 * which the function searches for active cells from the locally owned cells.
1585 * @return A subset of ghost cells within a given geometric distance of @p
1586 * layer_thickness from the locally owned cells of a current process.
1587 *
1588 * Also see compute_ghost_cell_halo_layer() and
1589 * compute_active_cell_layer_within_distance().
1590 *
1591 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1592 */
1593 template <typename MeshType>
1594 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1595 std::
1596 vector<typename MeshType::active_cell_iterator> compute_ghost_cell_layer_within_distance(
1597 const MeshType &mesh,
1598 const double layer_thickness);
1599
1600 /**
1601 * Compute a collection of bounding boxes so that all active cells for which
1602 * the given predicate is true, are completely enclosed in at least one of the
1603 * bounding boxes. Notice the cover is only guaranteed to contain all these
1604 * active cells but it's not necessarily exact i.e. it can include a bigger
1605 * area than their union. (This is of course unavoidable in any case if cells
1606 * are not rectangular or brick-shaped, but it is also true if cells are
1607 * since it is inefficient to create as many bounding boxes as there are
1608 * cells; rather, the algorithm here tries to combine the bounding boxes
1609 * of multiple cells into a cheaper representation, at the cost of a set
1610 * of bounding boxes that may be larger than the union of the cells -- see
1611 * the description of the relevant function arguments below.)
1612 *
1613 * For each cell at a given refinement level containing active cells for which @p predicate is true,
1614 * the function creates a bounding box of its children for which @p predicate is true.
1615 *
1616 * This results in a cover of all active cells for which @p predicate is true; the parameters
1617 * @p allow_merge and @p max_boxes are used to reduce the number of cells at a computational cost and
1618 * covering a bigger n-dimensional volume.
1619 *
1620 * @param[in] mesh The mesh object this function is to work on. This
1621 * is generally either a triangulation of some kind, or a DoFHandler
1622 * object.
1623 * @param[in] predicate A function-like object that returns true or
1624 * false depending on whether the property of the cells to enclose
1625 * is satisfied. An example is IteratorFilters::LocallyOwnedCell,
1626 * but it can also be a lambda function or anything else that can be
1627 * called with a cell as argument.
1628 * This predicate is tested only on active cells.
1629 * @param[in] refinement_level Defines the level at which the
1630 * initial bounding boxes are created. The refinement should be set
1631 * to a coarse refinement level. A bounding box is created for each
1632 * active cell at a coarser level than @p refinement_level; if @p
1633 * refinement_level is higher than the number of levels of the
1634 * triangulation an exception is thrown.
1635 * @param[in] allow_merge This flag allows for box merging and, by
1636 * default, is false. The algorithm has a cost of O(N^2) where N is
1637 * the number of the bounding boxes created from the refinement
1638 * level; for this reason, if the flag is set to true, make sure to
1639 * choose wisely a coarse enough @p refinement_level.
1640 * @param[in] max_boxes The maximum number of bounding boxes to
1641 * compute. If more are created the smaller ones are merged with
1642 * neighbors. By default after merging the boxes which can be
1643 * expressed as a single one no more boxes are merged. See the
1644 * BoundingBox::get_neighbor_type () function for details. Notice
1645 * only neighboring cells are merged (see the @p get_neighbor_type
1646 * function in bounding box class): if the target number of
1647 * bounding boxes max_boxes can't be reached by merging neighbors
1648 * an exception is thrown.
1649 *
1650 * The following image describes an example of the algorithm with @p
1651 * refinement_level = 2, @p allow_merge = true and @p max_boxes =
1652 * 1. The cells with the property predicate are in red, the area of
1653 * a bounding box is slightly orange.
1654 * @image html bounding_box_predicate.png
1655 *
1656 * - 1. In black we can see the cells of the current level.
1657 * - 2. For each cell containing the red area a bounding box is created: by
1658 * default these are returned.
1659 * - 3. Because @p allow_merge = true the number of bounding boxes is reduced while not changing the cover.
1660 * If @p max_boxes was left as default or bigger than 1 these two boxes would be returned.
1661 * - 4. Because @p max_boxes = 1 the smallest bounding box is merged to the bigger one.
1662 * Notice it is important to choose the parameters wisely. For instance, @p allow_merge = false and
1663 * @p refinement_level = 1 returns the very same bounding box but with a
1664 * fraction of the computational cost.
1665 *
1666 * This function does not take into account the curvature of cells and thus it
1667 * is not suited for handling curved geometry: the mapping is assumed to be
1668 * linear.
1669 *
1670 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
1671 */
1672 template <typename MeshType>
1673 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
1674 std::
1675 vector<BoundingBox<MeshType::space_dimension>> compute_mesh_predicate_bounding_box(
1676 const MeshType &mesh,
1677 const std::function<bool(const typename MeshType::active_cell_iterator &)>
1678 &predicate,
1679 const unsigned int refinement_level = 0,
1680 const bool allow_merge = false,
1681 const unsigned int max_boxes = numbers::invalid_unsigned_int);
1682
1683 /**
1684 * Given an array of points, use the global bounding box description obtained
1685 * using GridTools::compute_mesh_predicate_bounding_box to guess, for each of
1686 * them, which process might own it.
1687 *
1688 * @param[in] global_bboxes Vector of bounding boxes describing the portion of
1689 * mesh with a property for each process.
1690 * @param[in] points Array of points to test.
1691 *
1692 * @return A tuple containing the following information:
1693 * - A vector indicized with ranks of processes. For each rank it contains
1694 * a vector of the indices of points it might own.
1695 * - A map from the index <code>unsigned int</code> of the point in @p points
1696 * to the rank of the owner.
1697 * - A map from the index <code>unsigned int</code> of the point in @p points
1698 * to the ranks of the guessed owners.
1699 *
1700 * @note The actual return type of this function, i.e., the type referenced
1701 * above as @p return_type, is
1702 * @code
1703 * std::tuple<std::vector<std::vector<unsigned int>>,
1704 * std::map< unsigned int, unsigned int>,
1705 * std::map< unsigned int, std::vector<unsigned int>>>
1706 * @endcode
1707 * The type is abbreviated in the online documentation to improve readability
1708 * of this page.
1709 */
1710 template <int spacedim>
1711 #ifndef DOXYGEN
1712 std::tuple<std::vector<std::vector<unsigned int>>,
1713 std::map<unsigned int, unsigned int>,
1714 std::map<unsigned int, std::vector<unsigned int>>>
1715 #else
1716 return_type
1717 #endif
1718 guess_point_owner(
1719 const std::vector<std::vector<BoundingBox<spacedim>>> &global_bboxes,
1720 const std::vector<Point<spacedim>> &points);
1721
1722
1723 /**
1724 * Given a covering rtree (see GridTools::Cache::get_covering_rtree()), and an
1725 * array of points, find a superset of processes which, individually,
1726 * may own the cell containing the points.
1727 *
1728 * For further details see GridTools::guess_point_owner; here only
1729 * different input/output types are reported:
1730 *
1731 * @param[in] covering_rtree RTRee which enables us to identify which
1732 * process(es) in a parallel computation may own the cell that
1733 * surrounds a given point.
1734 *
1735 * @param[in] points A vector of points to consider.
1736 *
1737 * @return A tuple containing the following information:
1738 * - A map indexed by processor ranks. For each rank it contains
1739 * a vector of the indices of points it might own.
1740 * - A map from the index <code>unsigned int</code> of the point in @p points
1741 * to the rank of the owner; these are points for which a single possible
1742 * owner was found.
1743 * - A map from the index <code>unsigned int</code> of the point in @p points
1744 * to the ranks of the guessed owners; these are points for which multiple
1745 * possible owners were found.
1746 *
1747 * @note The actual return type of this function, i.e., the type referenced
1748 * above as @p return_type, is
1749 * @code
1750 * std::tuple<std::map<unsigned int, std::vector<unsigned int>>,
1751 * std::map<unsigned int, unsigned int>,
1752 * std::map<unsigned int, std::vector<unsigned int>>>
1753 * @endcode
1754 * The type is abbreviated in the online documentation to improve readability
1755 * of this page.
1756 */
1757 template <int spacedim>
1758 #ifndef DOXYGEN
1759 std::tuple<std::map<unsigned int, std::vector<unsigned int>>,
1760 std::map<unsigned int, unsigned int>,
1761 std::map<unsigned int, std::vector<unsigned int>>>
1762 #else
1763 return_type
1764 #endif
1765 guess_point_owner(
1766 const RTree<std::pair<BoundingBox<spacedim>, unsigned int>> &covering_rtree,
1767 const std::vector<Point<spacedim>> &points);
1768
1769 /**
1770 * Return a vector of normalized tensors for each vertex-cell combination of
1771 * the output of GridTools::vertex_to_cell_map() (which is expected as input
1772 * parameter for this function). Each tensor represents a geometric vector
1773 * from the vertex to the respective cell center.
1774 *
1775 * An assertion will be thrown if the size of the input vector is not equal to
1776 * the number of vertices of the triangulation.
1777 *
1778 * result[v][c] is a unit Tensor for vertex index v, indicating the direction
1779 * of the center of the c-th cell with respect to the vertex v.
1780 */
1781 template <int dim, int spacedim>
1782 std::vector<std::vector<Tensor<1, spacedim>>>
1783 vertex_to_cell_centers_directions(
1784 const Triangulation<dim, spacedim> &mesh,
1785 const std::vector<
1786 std::set<typename Triangulation<dim, spacedim>::active_cell_iterator>>
1787 &vertex_to_cells);
1788
1789
1790 /**
1791 * Return the local vertex index of cell @p cell that is closest to
1792 * the given location @p position. The location of the vertices is extracted
1793 * from the (optional) @p mapping argument, to guarantee that the correct
1794 * answer is returned when the underlying mapping modifies the position of the
1795 * vertices.
1796 */
1797 template <int dim, int spacedim>
1798 unsigned int
1799 find_closest_vertex_of_cell(
1800 const typename Triangulation<dim, spacedim>::active_cell_iterator &cell,
1801 const Point<spacedim> &position,
1802 const Mapping<dim, spacedim> &mapping =
1803 (ReferenceCells::get_hypercube<dim>()
1804 #ifndef _MSC_VER
1805 .template get_default_linear_mapping<dim, spacedim>()
1806 #else
1807 .ReferenceCell::get_default_linear_mapping<dim, spacedim>()
1808 #endif
1809 ));
1810
1811 /**
1812 * Compute a globally unique index for each vertex and hanging node
1813 * associated with a locally owned active cell. The vertices of a ghost cell
1814 * that are hanging nodes of a locally owned cells have a global index.
1815 * However, the other vertices of the cells that do not <i>touch</i> an
1816 * active cell do not have a global index on this processor.
1817 *
1818 * The key of the map is the local index of the vertex and the value is the
1819 * global index. The indices need to be recomputed after refinement or
1820 * coarsening and may be different.
1821 */
1822 template <int dim, int spacedim>
1823 std::map<unsigned int, types::global_vertex_index>
1824 compute_local_to_global_vertex_index_map(
1825 const Triangulation<dim, spacedim> &triangulation);
1826
1827 /** @} */
1828 /**
1829 * @name Partitions and subdomains of triangulations
1830 */
1831 /** @{ */
1832
1833 /**
1834 * Use graph partitioner to partition the active cells making up the entire
1835 * domain. After calling this function, the subdomain ids of all active cells
1836 * will have values
1837 * between zero and @p n_partitions-1. You can access the subdomain id of a cell by using
1838 * <tt>cell-@>subdomain_id()</tt>.
1839 *
1840 * Use the third argument to select between partitioning algorithms provided
1841 * by METIS or ZOLTAN. METIS is the default partitioner.
1842 *
1843 * If deal.II was not installed with ZOLTAN or METIS, this function will
1844 * generate an error
1845 * when the respective partition method is chosen, unless @p n_partitions is one.
1846 * I.e., you can write a program so that it runs in the single-processor
1847 * single-partition case without packages installed, and only requires them
1848 * installed when multiple partitions are required.
1849 *
1850 * @note If the `weight` signal has been attached to the @p triangulation,
1851 * then this will be used and passed to the partitioner.
1852 */
1853 template <int dim, int spacedim>
1854 void
1855 partition_triangulation(const unsigned int n_partitions,
1856 Triangulation<dim, spacedim> &triangulation,
1857 const SparsityTools::Partitioner partitioner =
1858 SparsityTools::Partitioner::metis);
1859
1860 /**
1861 * This function performs the same operation as the one above, except that
1862 * it takes into consideration a specific set of @p cell_weights, which allow the
1863 * partitioner to balance the graph while taking into consideration the
1864 * computational effort expended on each cell.
1865 *
1866 * @note If the @p cell_weights vector is empty, then no weighting is taken
1867 * into consideration. If not then the size of this vector must equal to the
1868 * number of active cells in the triangulation.
1869 */
1870 template <int dim, int spacedim>
1871 void
1872 partition_triangulation(const unsigned int n_partitions,
1873 const std::vector<unsigned int> &cell_weights,
1874 Triangulation<dim, spacedim> &triangulation,
1875 const SparsityTools::Partitioner partitioner =
1876 SparsityTools::Partitioner::metis);
1877
1878 /**
1879 * This function does the same as the previous one, i.e. it partitions a
1880 * triangulation using a partitioning algorithm into a number of subdomains
1881 * identified by the <code>cell-@>subdomain_id()</code> flag.
1882 *
1883 * The difference to the previous function is the second argument, a
1884 * sparsity pattern that represents the connectivity pattern between cells.
1885 *
1886 * While the function above builds it directly from the triangulation by
1887 * considering which cells neighbor each other, this function can take a
1888 * more refined connectivity graph. The sparsity pattern needs to be of size
1889 * $N\times N$, where $N$ is the number of active cells in the
1890 * triangulation. If the sparsity pattern contains an entry at position
1891 * $(i,j)$, then this means that cells $i$ and $j$ (in the order in which
1892 * they are traversed by active cell iterators) are to be considered
1893 * connected; partitioning algorithm will then try to partition the domain in
1894 * such a way that (i) the subdomains are of roughly equal size, and (ii) a
1895 * minimal number of connections are broken.
1896 *
1897 * This function is mainly useful in cases where connections between cells
1898 * exist that are not present in the triangulation alone (otherwise the
1899 * previous function would be the simpler one to use). Such connections may
1900 * include that certain parts of the boundary of a domain are coupled
1901 * through symmetric boundary conditions or integrals (e.g. friction contact
1902 * between the two sides of a crack in the domain), or if a numerical scheme
1903 * is used that not only connects immediate neighbors but a larger
1904 * neighborhood of cells (e.g. when solving integral equations).
1905 *
1906 * In addition, this function may be useful in cases where the default
1907 * sparsity pattern is not entirely sufficient. This can happen because the
1908 * default is to just consider face neighbors, not neighboring cells that
1909 * are connected by edges or vertices. While the latter couple when using
1910 * continuous finite elements, they are typically still closely connected in
1911 * the neighborship graph, and partitioning algorithm
1912 * will not usually cut important connections in this case. However, if there
1913 * are vertices in the mesh where many cells (many more than the common 4 or 6
1914 * in 2d and 3d, respectively) come together, then there will be a significant
1915 * number of cells that are connected across a vertex, but several degrees
1916 * removed in the connectivity graph built only using face neighbors. In a
1917 * case like this, partitioning algorithm may sometimes make bad decisions and
1918 * you may want to build your own connectivity graph.
1919 *
1920 * @note If the `weight` signal has been attached to the @p triangulation,
1921 * then this will be used and passed to the partitioner.
1922 */
1923 template <int dim, int spacedim>
1924 void
1925 partition_triangulation(const unsigned int n_partitions,
1926 const SparsityPattern &cell_connection_graph,
1927 Triangulation<dim, spacedim> &triangulation,
1928 const SparsityTools::Partitioner partitioner =
1929 SparsityTools::Partitioner::metis);
1930
1931 /**
1932 * This function performs the same operation as the one above, except that
1933 * it takes into consideration a specific set of @p cell_weights, which allow the
1934 * partitioner to balance the graph while taking into consideration the
1935 * computational effort expended on each cell.
1936 *
1937 * @note If the @p cell_weights vector is empty, then no weighting is taken
1938 * into consideration. If not then the size of this vector must equal to the
1939 * number of active cells in the triangulation.
1940 */
1941 template <int dim, int spacedim>
1942 void
1943 partition_triangulation(const unsigned int n_partitions,
1944 const std::vector<unsigned int> &cell_weights,
1945 const SparsityPattern &cell_connection_graph,
1946 Triangulation<dim, spacedim> &triangulation,
1947 const SparsityTools::Partitioner partitioner =
1948 SparsityTools::Partitioner::metis);
1949
1950 /**
1951 * Generates a partitioning of the active cells making up the entire domain
1952 * using the same partitioning scheme as in the p4est library if the flag
1953 * @p group_siblings is set to true (default behavior of this function).
1954 * After calling this function, the subdomain ids of all active cells will
1955 * have values between zero and @p n_partitions-1. You can access the
1956 * subdomain id of a cell by using <tt>cell-@>subdomain_id()</tt>.
1957 *
1958 * @note If the flag @p group_siblings is set to false, children of a
1959 * cell might be placed on different processors even though they are all
1960 * active, which is an assumption made by p4est. By relaxing this, we
1961 * can create partitions owning a single cell (also for refined
1962 * meshes).
1963 */
1964 template <int dim, int spacedim>
1965 void
1966 partition_triangulation_zorder(const unsigned int n_partitions,
1967 Triangulation<dim, spacedim> &triangulation,
1968 const bool group_siblings = true);
1969
1970 /**
1971 * Partitions the cells of a multigrid hierarchy by assigning level subdomain
1972 * ids using the "youngest child" rule, that is, each cell in the hierarchy is
1973 * owned by the processor who owns its left most child in the forest, and
1974 * active cells have the same subdomain id and level subdomain id. You can
1975 * access the level subdomain id of a cell by using
1976 * <tt>cell-@>level_subdomain_id()</tt>.
1977 *
1978 * Note: This function assumes that the active cells have already been
1979 * partitioned.
1980 */
1981 template <int dim, int spacedim>
1982 void
1983 partition_multigrid_levels(Triangulation<dim, spacedim> &triangulation);
1984
1985 /**
1986 * This function allows to ask for the owning subdomain of cells identified by
1987 * CellId objects that do not have to exist on the current process.
1988 *
1989 * @note This function has not been implemented yet for
1990 * parallel::fullydistributed::Triangulation.
1991 */
1992 template <int dim, int spacedim>
1993 std::vector<types::subdomain_id>
1994 get_subdomain_association(const Triangulation<dim, spacedim> &triangulation,
1995 const std::vector<CellId> &cell_ids);
1996
1997 /**
1998 * For each active cell, return in the output array to which subdomain (as
1999 * given by the <tt>cell->subdomain_id()</tt> function) it belongs. The
2000 * output array is supposed to have the right size already when calling this
2001 * function.
2002 *
2003 * This function returns the association of each cell with one subdomain. If
2004 * you are looking for the association of each @em DoF with a subdomain, use
2005 * the <tt>DoFTools::get_subdomain_association</tt> function.
2006 */
2007 template <int dim, int spacedim>
2008 void
2009 get_subdomain_association(const Triangulation<dim, spacedim> &triangulation,
2010 std::vector<types::subdomain_id> &subdomain);
2011
2012 /**
2013 * Count how many cells are uniquely associated with the given @p subdomain
2014 * index.
2015 *
2016 * This function may return zero if there are no cells with the given @p
2017 * subdomain index. This can happen, for example, if you try to partition a
2018 * coarse mesh into more partitions (one for each processor) than there are
2019 * cells in the mesh.
2020 *
2021 * This function returns the number of cells associated with one subdomain.
2022 * If you are looking for the association of @em DoFs with this subdomain,
2023 * use the <tt>DoFTools::count_dofs_with_subdomain_association</tt>
2024 * function.
2025 */
2026 template <int dim, int spacedim>
2027 unsigned int
2028 count_cells_with_subdomain_association(
2029 const Triangulation<dim, spacedim> &triangulation,
2030 const types::subdomain_id subdomain);
2031
2032 /**
2033 * For a triangulation, return a mask that represents which of its vertices
2034 * are "owned" by the current process in the same way as we talk about
2035 * locally owned cells or degrees of freedom (see
2036 * @ref GlossLocallyOwnedCell
2037 * and
2038 * @ref GlossLocallyOwnedDof).
2039 * For the purpose of this function, we define a locally owned vertex as
2040 * follows: a vertex is owned by that processor with the smallest subdomain
2041 * id (which equals the MPI rank of that processor) among all owners of
2042 * cells adjacent to this vertex. In other words, vertices that are in the
2043 * interior of a partition of the triangulation are owned by the owner of
2044 * this partition; for vertices that lie on the boundary between two or more
2045 * partitions, the owner is the processor with the least subdomain_id among
2046 * all adjacent subdomains.
2047 *
2048 * For sequential triangulations (as opposed to, for example,
2049 * parallel::distributed::Triangulation), every user vertex is of course
2050 * owned by the current processor, i.e., the function returns
2051 * Triangulation::get_used_vertices(). For parallel triangulations, the
2052 * returned mask is a subset of what Triangulation::get_used_vertices()
2053 * returns.
2054 *
2055 * @param triangulation The triangulation of which the function evaluates
2056 * which vertices are locally owned.
2057 * @return The subset of vertices, as described above. The length of the
2058 * returned array equals Triangulation.n_vertices() and may, consequently,
2059 * be larger than Triangulation::n_used_vertices().
2060 */
2061 template <int dim, int spacedim>
2062 std::vector<bool>
2063 get_locally_owned_vertices(const Triangulation<dim, spacedim> &triangulation);
2064
2065 /** @} */
2066 /**
2067 * @name Dealing with distorted cells
2068 */
2069 /** @{ */
2070
2071 /**
2072 * Given a triangulation and a list of cells whose children have become
2073 * distorted as a result of mesh refinement, try to fix these cells up by
2074 * moving the center node around.
2075 *
2076 * The function returns a list of cells with distorted children that
2077 * couldn't be fixed up for whatever reason. The returned list is therefore
2078 * a subset of the input argument.
2079 *
2080 * For a definition of the concept of distorted cells, see the
2081 * @ref GlossDistorted "glossary entry".
2082 * The first argument passed to the current function is typically the
2083 * exception thrown by the Triangulation::execute_coarsening_and_refinement
2084 * function.
2085 *
2086 * @deprecated This function predates deal.II's use of manifolds and use of
2087 * cell-local transfinite interpolation to place new points and is no longer
2088 * necessary. See Manifolds::get_default_points_and_weights() for more
2089 * information.
2090 */
2091 template <int dim, int spacedim>
2092 DEAL_II_DEPRECATED typename Triangulation<dim, spacedim>::DistortedCellList
2093 fix_up_distorted_child_cells(
2094 const typename Triangulation<dim, spacedim>::DistortedCellList
2095 &distorted_cells,
2096 Triangulation<dim, spacedim> &triangulation);
2097
2098
2099
2100 /** @} */
2101 /**
2102 * @name Extracting and creating patches of cells
2103 *
2104 * These functions extract and create patches of cells surrounding a single
2105 * cell, and creating triangulation out of them.
2106 */
2107 /** @{ */
2108
2109
2110 /**
2111 * This function returns a list of all the active neighbor cells of the
2112 * given, active cell. Here, a neighbor is defined as one having at least
2113 * part of a face in common with the given cell, but not edge (in 3d) or
2114 * vertex neighbors (in 2d and 3d).
2115 *
2116 * The first element of the returned list is the cell provided as argument.
2117 * The remaining ones are neighbors: The function loops over all faces of
2118 * that given cell and checks if that face is not on the boundary of the
2119 * domain. Then, if the neighbor cell does not have any children (i.e., it
2120 * is either at the same refinement level as the current cell, or coarser)
2121 * then this neighbor cell is added to the list of cells. Otherwise, if the
2122 * neighbor cell is refined and therefore has children, then this function
2123 * loops over all subfaces of current face adds the neighbors behind these
2124 * sub-faces to the list to be returned.
2125 *
2126 * @tparam MeshType A type that satisfies the requirements of the
2127 * @ref ConceptMeshType "MeshType concept".
2128 * In C++, the compiler can not determine <code>MeshType</code> from the
2129 * function call. You need to specify it as an explicit template argument
2130 * following the function name.
2131 * @param[in] cell An iterator pointing to a cell of the mesh.
2132 * @return A list of active cells that form the patch around the given cell
2133 *
2134 * @note Patches are often used in defining error estimators that require
2135 * the solution of a local problem on the patch surrounding each of the
2136 * cells of the mesh. This also requires manipulating the degrees of freedom
2137 * associated with the cells of a patch. To this end, there are further
2138 * functions working on patches in namespace DoFTools.
2139 *
2140 * @note In the context of a parallel distributed computation, it only makes
2141 * sense to call this function on locally owned cells. This is because the
2142 * neighbors of locally owned cells are either locally owned themselves, or
2143 * ghost cells. For both, we know that these are in fact the real cells of
2144 * the complete, parallel triangulation. We can also query the degrees of
2145 * freedom on these.
2146 *
2147 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
2148 */
2149 template <typename MeshType>
2150 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
2151 std::vector<typename MeshType::active_cell_iterator> get_patch_around_cell(
2152 const typename MeshType::active_cell_iterator &cell);
2153
2154
2155 /**
2156 * This function takes a vector of active cells (hereafter named @p
2157 * patch_cells) as input argument, and returns a vector of their parent
2158 * cells with the coarsest common level of refinement. In other words, find
2159 * that set of cells living at the same refinement level so that all cells
2160 * in the input vector are children of the cells in the set, or are in the
2161 * set itself.
2162 *
2163 * @tparam Container In C++, the compiler can not determine the type of
2164 * <code>Container</code> from the function call. You need to specify it as
2165 * an explicit template argument following the function name. This type has
2166 * to satisfy the requirements of a mesh container (see
2167 * @ref ConceptMeshType).
2168 *
2169 * @param[in] patch_cells A vector of active cells for which this function
2170 * finds the parents at the coarsest common level. This vector of cells
2171 * typically results from calling the function
2172 * GridTools::get_patch_around_cell().
2173 * @return A list of cells with the coarsest common level of refinement of
2174 * the input cells.
2175 */
2176 template <class Container>
2177 std::vector<typename Container::cell_iterator>
2178 get_cells_at_coarsest_common_level(
2179 const std::vector<typename Container::active_cell_iterator> &patch_cells);
2180
2181 /**
2182 * This function constructs a Triangulation (named @p local_triangulation)
2183 * from a given vector of active cells. This vector (which we think of the
2184 * cells corresponding to a "patch") contains active cells that are part of
2185 * an existing global Triangulation. The goal of this function is to build a
2186 * local Triangulation that contains only the active cells given in @p patch
2187 * (and potentially a minimum number of additional cells required to form a
2188 * valid Triangulation). The function also returns a map that allows to
2189 * identify the cells in the output Triangulation and corresponding cells in
2190 * the input list.
2191 *
2192 * The function copies the location of vertices of cells from the cells of the
2193 * source triangulation to the triangulation that is built from the list of
2194 * patch cells. This adds support for triangulations which have been
2195 * perturbed or smoothed in some manner which makes the triangulation
2196 * deviate from the standard deal.II refinement strategy of placing new
2197 * vertices at midpoints of faces or edges.
2198 *
2199 * The operation implemented by this function is frequently used in the
2200 * definition of error estimators that need to solve "local" problems on
2201 * each cell and its neighbors. A similar construction is necessary in the
2202 * definition of the Clement interpolation operator in which one needs to
2203 * solve a local problem on all cells within the support of a shape
2204 * function. This function then builds a complete Triangulation from a list
2205 * of cells that make up such a patch; one can then later attach a
2206 * DoFHandler to such a Triangulation.
2207 *
2208 * If the list of input cells contains only cells at the same refinement
2209 * level, then the output Triangulation simply consists of a Triangulation
2210 * containing only exactly these patch cells. On the other hand, if the
2211 * input cells live on different refinement levels, i.e., the Triangulation
2212 * of which they are part is adaptively refined, then the construction of
2213 * the output Triangulation is not so simple because the coarsest level of a
2214 * Triangulation can not contain hanging nodes. Rather, we first have to
2215 * find the common refinement level of all input cells, along with their
2216 * common parents (see GridTools::get_cells_at_coarsest_common_level()),
2217 * build a Triangulation from those, and then adaptively refine it so that
2218 * the input cells all also exist in the output Triangulation.
2219 *
2220 * A consequence of this procedure is that the output Triangulation may
2221 * contain more active cells than the ones that exist in the input vector.
2222 * On the other hand, one typically wants to solve the local problem not on
2223 * the entire output Triangulation, but only on those cells of it that
2224 * correspond to cells in the input list. In this case, a user typically
2225 * wants to assign degrees of freedom only on cells that are part of the
2226 * "patch", and somehow ignore those excessive cells. The current function
2227 * supports this common requirement by setting the user flag for the cells
2228 * in the output Triangulation that match with cells in the input list.
2229 * Cells which are not part of the original patch will not have their @p
2230 * user_flag set; we can then avoid assigning degrees of freedom using the
2231 * FE_Nothing<dim> element.
2232 *
2233 * @tparam Container In C++, the compiler can not determine the type of
2234 * <code>Container</code> from the function call. You need to specify it as
2235 * an explicit template argument following the function name. This type that
2236 * satisfies the requirements of a mesh container (see
2237 * @ref ConceptMeshType).
2238 *
2239 * @param[in] patch A vector of active cells from a common triangulation.
2240 * These cells may or may not all be at the same refinement level.
2241 * @param[out] local_triangulation A triangulation whose active cells
2242 * correspond to the given vector of active cells in @p patch.
2243 * @param[out] patch_to_global_tria_map A map between the local
2244 * triangulation which is built as explained above, and the cell iterators
2245 * in the input list.
2246 */
2247 template <class Container>
2248 void
2249 build_triangulation_from_patch(
2250 const std::vector<typename Container::active_cell_iterator> &patch,
2251 Triangulation<Container::dimension, Container::space_dimension>
2252 &local_triangulation,
2253 std::map<
2254 typename Triangulation<Container::dimension,
2255 Container::space_dimension>::active_cell_iterator,
2256 typename Container::active_cell_iterator> &patch_to_global_tria_map);
2257
2258 /**
2259 * This function runs through the degrees of freedom defined by the
2260 * DoFHandler and for each dof constructs a vector of
2261 * active_cell_iterators representing the cells of support of the associated
2262 * basis element at that degree of freedom. This function was originally
2263 * designed for the implementation of local projections, for instance the
2264 * Clement interpolant, in conjunction with other local patch functions like
2265 * GridTools::build_triangulation_from_patch.
2266 *
2267 * DoFHandler's built on top of Triangulation or
2268 * parallel::distributed::Triangulation are supported and handled
2269 * appropriately.
2270 *
2271 * The result is the patch of cells representing the support of the basis
2272 * element associated to the degree of freedom. For instance using an FE_Q
2273 * finite element, we obtain the standard patch of cells touching the degree
2274 * of freedom and then add other cells that take care of possible hanging node
2275 * constraints. Using a FE_DGQ finite element, the degrees of freedom are
2276 * logically considered to be "interior" to the cells so the patch would
2277 * consist exclusively of the single cell on which the degree of freedom is
2278 * located.
2279 *
2280 * @param[in] dof_handler The DoFHandler which could be built on a
2281 * Triangulation or a parallel::distributed::Triangulation with a finite
2282 * element that has degrees of freedom that are logically associated to a
2283 * vertex, line, quad, or hex.
2284 * @return A map from the global_dof_index of
2285 * degrees of freedom on locally relevant cells to vectors containing
2286 * DoFHandler::active_cell_iterators of cells in the support of the basis
2287 * function at that degree of freedom.
2288 */
2289 template <int dim, int spacedim>
2290 std::map<
2291 types::global_dof_index,
2292 std::vector<typename DoFHandler<dim, spacedim>::active_cell_iterator>>
2293 get_dof_to_support_patch_map(DoFHandler<dim, spacedim> &dof_handler);
2294
2295
2296 /** @} */
2297
2298 /**
2299 * @name Dealing with periodic domains
2300 */
2301 /** @{ */
2302
2303 /**
2304 * Data type that provides all information necessary to create periodicity
2305 * constraints and a periodic p4est forest with respect to two 'periodic'
2306 * cell faces.
2307 *
2308 * @ingroup reordering
2309 */
2310 template <typename CellIterator>
2311 struct PeriodicFacePair
2312 {
2313 /**
2314 * The cells associated with the two 'periodic' faces.
2315 */
2316 CellIterator cell[2];
2317
2318 /**
2319 * The local face indices (with respect to the specified cells) of the two
2320 * 'periodic' faces.
2321 */
2322 unsigned int face_idx[2];
2323
2324 /**
2325 * The relative orientation of the first face with respect to the second
2326 * face as described in orthogonal_equality() and
2327 * DoFTools::make_periodicity_constraints().
2328 */
2329 types::geometric_orientation orientation;
2330
2331 /**
2332 * A @p dim $\times$ @p dim rotation matrix that describes how vector
2333 * valued DoFs of the first face should be modified prior to constraining
2334 * to the DoFs of the second face.
2335 *
2336 * The rotation matrix is used in DoFTools::make_periodicity_constraints()
2337 * by applying the rotation to all vector valued blocks listed in the
2338 * parameter @p first_vector_components of the finite element space. For
2339 * more details see DoFTools::make_periodicity_constraints() and the
2340 * glossary
2341 * @ref GlossPeriodicConstraints "glossary entry on periodic conditions".
2342 */
2343 FullMatrix<double> matrix;
2344
2345 /**
2346 * Return an estimate, in bytes, for the memory consumption of the object.
2347 */
2348 std::size_t
2349 memory_consumption() const;
2350 };
2351
2352
2353 /**
2354 * An orthogonal equality test for faces.
2355 *
2356 * @p face1 and @p face2 are considered equal, if a one to one matching
2357 * between its vertices can be achieved via an orthogonal equality relation.
2358 * If no such relation exists then the returned std::optional object is empty
2359 * (i.e., has_value() will return `false`).
2360 *
2361 * Here, two vertices <tt>v_1</tt> and <tt>v_2</tt> are considered equal, to
2362 * the nearest tolerance, e.g. distance < abs_tol, if $M\cdot v_1 + offset -
2363 * v_2$ is parallel to the
2364 * unit vector in unit direction @p direction. Note that this tolerance is not
2365 * scaled with the mesh, it's an absolute tolerance. If the parameter @p matrix
2366 * is a reference to a spacedim x spacedim matrix, $M$ is set to @p matrix,
2367 * otherwise $M$ is the identity matrix.
2368 *
2369 * If the matching was successful, the _relative_ orientation of @p face1 with
2370 * respect to @p face2 is returned a
2371 * std::optional<types::geometric_orientation>. More
2372 * information on that topic can be found in the
2373 * @ref GlossCombinedOrientation
2374 * "glossary" article.
2375 */
2376 template <typename FaceIterator>
2377 std::optional<types::geometric_orientation>
2378 orthogonal_equality(
2379 const FaceIterator &face1,
2380 const FaceIterator &face2,
2381 const unsigned int direction,
2382 const Tensor<1, FaceIterator::AccessorType::space_dimension> &offset =
2383 Tensor<1, FaceIterator::AccessorType::space_dimension>(),
2384 const FullMatrix<double> &matrix = FullMatrix<double>(),
2385 const double abs_tol = 1e-10);
2386
2387 /**
2388 * This function will collect periodic face pairs on the coarsest mesh level
2389 * of the given @p mesh (a Triangulation or DoFHandler) and add them to the
2390 * vector @p matched_pairs leaving the original contents intact.
2391 *
2392 * Define a 'first' boundary as all boundary faces having boundary_id @p
2393 * b_id1 and a 'second' boundary consisting of all faces belonging to @p
2394 * b_id2.
2395 *
2396 * This function tries to match all faces belonging to the first boundary
2397 * with faces belonging to the second boundary with the help of
2398 * orthogonal_equality().
2399 *
2400 * The value returned inside of PeriodicFacePair encodes the _relative_
2401 * orientation of the first face with respect to the second face, see the
2402 * documentation of orthogonal_equality() for further details.
2403 *
2404 * The @p direction refers to the space direction in which periodicity is
2405 * enforced. When matching periodic faces this vector component is ignored.
2406 *
2407 * The @p offset is a vector tangential to the faces that is added to the
2408 * location of vertices of the 'first' boundary when attempting to match
2409 * them (to the nearest absolute tolerance, distance < abs_tol) to the
2410 * corresponding vertices of the 'second' boundary. This can be used to
2411 * implement conditions such as $u(0,y)=u(1,y+1)$.
2412 *
2413 * Optionally, a $dim\times dim$ rotation @p matrix can be specified that
2414 * describes how vector valued DoFs of the first face should be modified
2415 * prior to constraining to the DoFs of the second face. The @p matrix is
2416 * used in two places. First, @p matrix will be supplied to
2417 * orthogonal_equality() and used for matching faces: Two vertices $v_1$ and
2418 * $v_2$ match if $\text{matrix}\cdot v_1 + \text{offset} - v_2$ is parallel
2419 * to the unit vector in unit direction @p direction. (For more details see
2420 * DoFTools::make_periodicity_constraints(), the glossary
2421 * @ref GlossPeriodicConstraints "glossary entry on periodic conditions"
2422 * and step-45). Second, @p matrix will be stored in the PeriodicFacePair
2423 * collection @p matched_pairs for further use.
2424 *
2425 * @tparam MeshType A type that satisfies the requirements of the
2426 * @ref ConceptMeshType "MeshType concept".
2427 *
2428 * @note The created std::vector can be used in
2429 * DoFTools::make_periodicity_constraints() and in
2430 * parallel::distributed::Triangulation::add_periodicity() to enforce
2431 * periodicity algebraically.
2432 *
2433 * @note Because elements will be added to @p matched_pairs (and existing
2434 * entries will be preserved), it is possible to call this function several
2435 * times with different boundary ids to generate a vector with all periodic
2436 * pairs.
2437 *
2438 * @note Since the periodic face pairs are found on the coarsest mesh level,
2439 * it is necessary to ensure that the coarsest level faces have the correct
2440 * boundary indicators set. In general, this means that one must first set
2441 * all boundary indicators on the coarse grid before performing any global
2442 * or local grid refinement.
2443 *
2444 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
2445 */
2446 template <typename MeshType>
2447 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
2448 void collect_periodic_faces(
2449 const MeshType &mesh,
2450 const types::boundary_id b_id1,
2451 const types::boundary_id b_id2,
2452 const unsigned int direction,
2453 std::vector<PeriodicFacePair<typename MeshType::cell_iterator>>
2454 &matched_pairs,
2455 const Tensor<1, MeshType::space_dimension> &offset =
2456 dealii::Tensor<1, MeshType::space_dimension>(),
2457 const FullMatrix<double> &matrix = FullMatrix<double>(),
2458 const double abs_tol = 1e-10);
2459
2460
2461 /**
2462 * Instead of defining a 'first' and 'second' boundary with the help of two
2463 * boundary_ids this function defines a 'left' boundary as all faces with
2464 * local face index <code>2*direction</code> and boundary indicator @p b_id
2465 * and, similarly, a 'right' boundary consisting of all face with local face
2466 * index <code>2*direction+1</code> and boundary indicator @p b_id. Faces
2467 * with coordinates only differing in the @p direction component are
2468 * identified.
2469 *
2470 * This function will collect periodic face pairs on the coarsest mesh level
2471 * and add them to @p matched_pairs leaving the original contents intact.
2472 *
2473 * See above function for further details.
2474 *
2475 * @warning This version of collect_periodic_faces() will not work on
2476 * meshes with faces not in the
2477 * @ref GlossCombinedOrientation "default orientation".
2478 *
2479 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
2480 */
2481 template <typename MeshType>
2482 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
2483 void collect_periodic_faces(
2484 const MeshType &mesh,
2485 const types::boundary_id b_id,
2486 const unsigned int direction,
2487 std::vector<PeriodicFacePair<typename MeshType::cell_iterator>>
2488 &matched_pairs,
2489 const dealii::Tensor<1, MeshType::space_dimension> &offset =
2490 dealii::Tensor<1, MeshType::space_dimension>(),
2491 const FullMatrix<double> &matrix = FullMatrix<double>(),
2492 const double abs_tol = 1e-10);
2493
2494 /** @} */
2495 /**
2496 * @name Dealing with boundary and manifold ids
2497 */
2498 /** @{ */
2499
2500 /**
2501 * Copy boundary ids to manifold ids on faces and edges at the boundary. The
2502 * default manifold_id for new Triangulation objects is
2503 * numbers::flat_manifold_id. This function copies the boundary_ids of
2504 * the boundary faces and edges to the manifold_ids of the same faces and
2505 * edges, allowing the user to change the boundary_ids and use them for
2506 * boundary conditions regardless of the geometry, which will use
2507 * manifold_ids to create new points. Only active cells will be iterated
2508 * over. This is a function you'd typically call when there is only one
2509 * active level on your Triangulation. Mesh refinement will then inherit
2510 * these indicators to child cells, faces, and edges.
2511 *
2512 * The optional parameter @p reset_boundary_ids, indicates whether this
2513 * function should reset the boundary_ids of boundary faces and edges to its
2514 * default value 0 after copying its value to the manifold_id. By default,
2515 * boundary_ids are left untouched.
2516 *
2517 * @ingroup manifold
2518 * @relatesalso boundary
2519 */
2520 template <int dim, int spacedim>
2521 void
2522 copy_boundary_to_manifold_id(Triangulation<dim, spacedim> &tria,
2523 const bool reset_boundary_ids = false);
2524
2525 /**
2526 * Map the given boundary ids to the given manifold ids on faces and
2527 * edges at the boundary.
2528 *
2529 * This function copies the boundary ids of the boundary faces and
2530 * edges that are present in the parameter @p src_boundary_ids to
2531 * the corresponding manifold id in @p dst_manifold_ids, of the same
2532 * faces and edges.
2533 *
2534 * If the optional parameter @p reset_boundary_ids is non empty,
2535 * each boundary id in @p src_boundary_ids, is replaced with the
2536 * corresponding boundary id in @p reset_boundary_ids.
2537 *
2538 * An exception is thrown if the size of the input vectors do not
2539 * match. If a boundary id indicated in @p src_boundary_ids is not
2540 * present in the triangulation, it is simply ignored during the
2541 * process.
2542 *
2543 * @ingroup manifold
2544 * @relatesalso boundary
2545 */
2546 template <int dim, int spacedim>
2547 void
2548 map_boundary_to_manifold_ids(
2549 const std::vector<types::boundary_id> &src_boundary_ids,
2550 const std::vector<types::manifold_id> &dst_manifold_ids,
2551 Triangulation<dim, spacedim> &tria,
2552 const std::vector<types::boundary_id> &reset_boundary_ids = {});
2553
2554 /**
2555 * Copy material ids to manifold ids. The default manifold_id for new
2556 * Triangulation objects is numbers::flat_manifold_id. When refinements
2557 * occurs, the Triangulation asks where to locate new points to the
2558 * underlying manifold.
2559 *
2560 * When reading a Triangulation from a supported input format, typical
2561 * information that can be stored in a file are boundary conditions for
2562 * boundary faces (which we store in the boundary_id of the faces), material
2563 * types for cells (which we store in the material_id of the cells) and in
2564 * some cases subdomain ids for cells (which we store in the subdomain_id of
2565 * the cell).
2566 *
2567 * If you read one of these grids into a Triangulation, you might still want
2568 * to use the material_id specified in the input file as a manifold_id
2569 * description. In this case you can associate a Manifold object to internal
2570 * cells, and this object will be used by the Triangulation to query
2571 * Manifold objects for new points. This function iterates over active cells
2572 * and copies the material_ids to the manifold_ids.
2573 *
2574 * The optional parameter @p compute_face_ids, indicates whether this
2575 * function should also set the manifold_ids of the faces (both for internal
2576 * faces and for faces on the boundary). If set to true, then each face will
2577 * get a manifold_id equal to the minimum of the surrounding manifold_ids,
2578 * ensuring that a unique manifold id is selected for each face of the
2579 * Triangulation. By default, face manifold_ids are not computed.
2580 *
2581 * @ingroup manifold
2582 */
2583 template <int dim, int spacedim>
2584 void
2585 copy_material_to_manifold_id(Triangulation<dim, spacedim> &tria,
2586 const bool compute_face_ids = false);
2587
2588 /**
2589 * Propagate manifold indicators associated with the cells of the
2590 * Triangulation @p tria to their co-dimension one and two objects.
2591 *
2592 * This function sets the @p manifold_id of faces and edges (both on the
2593 * interior and on the boundary) to the value returned by the
2594 * @p disambiguation_function method, called with the set of
2595 * manifold indicators of the cells that share the same face or edge.
2596 *
2597 * By default, the @p disambiguation_function returns
2598 * numbers::flat_manifold_id when the set has size greater than one (i.e.,
2599 * when it is not possible to decide what manifold indicator a face or edge
2600 * should have according to the manifold indicators of the adjacent cells)
2601 * and it returns the manifold indicator contained in the set when it has
2602 * dimension one (i.e., when all adjacent cells and faces have the same
2603 * manifold indicator).
2604 *
2605 * The parameter @p overwrite_only_flat_manifold_ids allows you to specify
2606 * what to do when a face or an edge already has a manifold indicator
2607 * different from numbers::flat_manifold_id. If the flag is @p true, the edge
2608 * or face will maintain its original manifold indicator.
2609 * If it is @p false, then also the manifold indicator of these faces and edges
2610 * is set according to the return value of the @p disambiguation_function.
2611 */
2612 template <int dim, int spacedim>
2613 void
2614 assign_co_dimensional_manifold_indicators(
2615 Triangulation<dim, spacedim> &tria,
2616 const std::function<types::manifold_id(
2617 const std::set<types::manifold_id> &)> &disambiguation_function =
2618 [](const std::set<types::manifold_id> &manifold_ids) {
2619 if (manifold_ids.size() == 1)
2620 return *manifold_ids.begin();
2621 else
2622 return numbers::flat_manifold_id;
2623 },
2624 bool overwrite_only_flat_manifold_ids = true);
2625 /** @} */
2626
2627 /**
2628 * Exchange arbitrary data of type @p DataType provided by the function
2629 * objects from locally owned cells to ghost cells on other processors.
2630 *
2631 * After this call, you typically will have received data from @p unpack on
2632 * every ghost cell as it was given by @p pack on the owning processor.
2633 * Whether you do or do not receive information to @p unpack on a given
2634 * ghost cell depends on whether the @p pack function decided that
2635 * something needs to be sent. It does so using the std::optional
2636 * mechanism: if the std::optional return object of the @p pack
2637 * function is empty, then this implies that no data has to be sent for
2638 * the locally owned cell it was called on. In that case, @p unpack will
2639 * also not be called on the ghost cell that corresponds to it on the
2640 * receiving side. On the other hand, if the std::optional object is
2641 * not empty, then the data stored within it will be sent to the received
2642 * and the @p unpack function called with it.
2643 *
2644 * @tparam DataType The type of the data to be communicated. It is assumed
2645 * to be serializable by boost::serialization. In many cases, this
2646 * data type can not be deduced by the compiler, e.g., if you provide
2647 * lambda functions for the second and third argument
2648 * to this function. In this case, you have to explicitly specify
2649 * the @p DataType as a template argument to the function call.
2650 * @tparam MeshType The type of @p mesh.
2651 *
2652 * @param mesh A variable of a type that satisfies the requirements of the
2653 * @ref ConceptMeshType "MeshType concept".
2654 * @param pack The function that will be called on each locally owned cell
2655 * that is a ghost cell somewhere else. As mentioned above, the function
2656 * may return a regular data object of type @p DataType to indicate
2657 * that data should be sent, or an empty
2658 * <code>std::optional@<DataType@></code> to indicate that nothing has
2659 * to be sent for this cell.
2660 * @param unpack The function that will be called for each ghost cell
2661 * for which data was sent, i.e., for which the @p pack function
2662 * on the sending side returned a non-empty std::optional object.
2663 * The @p unpack function is then called with the data sent by the
2664 * processor that owns that cell.
2665 * @param cell_filter Only cells are communicated where this filter function returns
2666 * the value `true`. In the default case, the function returns true on all
2667 * cells and thus, all relevant cells are communicated.
2668 *
2669 * <h4> An example </h4>
2670 *
2671 * Here is an example that shows how this function is to be used
2672 * in a concrete context. It is taken from the code that makes
2673 * sure that the @p active_fe_index (a single unsigned integer) is
2674 * transported from locally owned cells where one can set it in
2675 * DoFHandler objects with hp-capabilities, to the corresponding ghost cells
2676 * on other processors to ensure that one can query the right value also on
2677 * those processors:
2678 * @code
2679 * using active_cell_iterator =
2680 * typename DoFHandler<dim,spacedim>::active_cell_iterator;
2681 * auto pack = [] (const active_cell_iterator &cell) -> unsigned int
2682 * {
2683 * return cell->active_fe_index();
2684 * };
2685 *
2686 * auto unpack = [] (const active_cell_iterator &cell,
2687 * const unsigned int active_fe_index) -> void
2688 * {
2689 * cell->set_active_fe_index(active_fe_index);
2690 * };
2691 *
2692 * GridTools::exchange_cell_data_to_ghosts<
2693 * unsigned int, DoFHandler<dim,spacedim>> (dof_handler,
2694 * pack,
2695 * unpack);
2696 * @endcode
2697 *
2698 * You will notice that the @p pack lambda function returns an `unsigned int`,
2699 * not a `std::optional<unsigned int>`. The former converts
2700 * automatically to the latter, implying that data will always be transported
2701 * to the other processor.
2702 *
2703 * (In reality, the @p unpack function needs to be a bit more
2704 * complicated because it is not allowed to call
2705 * DoFAccessor::set_active_fe_index() on ghost cells. Rather, the
2706 * @p unpack function directly accesses internal data structures. But
2707 * you get the idea -- the code could, just as well, have exchanged
2708 * material ids, user indices, boundary indicators, or any kind of other
2709 * data with similar calls as the ones above.)
2710 *
2711 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
2712 */
2713 template <typename DataType, typename MeshType>
2714 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
2715 void exchange_cell_data_to_ghosts(
2716 const MeshType &mesh,
2717 const std::function<std::optional<DataType>(
2718 const typename MeshType::active_cell_iterator &)> &pack,
2719 const std::function<void(const typename MeshType::active_cell_iterator &,
2720 const DataType &)> &unpack,
2721 const std::function<bool(const typename MeshType::active_cell_iterator &)>
2722 &cell_filter =
2723 always_return<typename MeshType::active_cell_iterator, bool>{true});
2724
2725 /**
2726 * Exchange arbitrary data of type @p DataType provided by the function
2727 * objects from locally owned level cells to ghost level cells on other
2728 * processes.
2729 *
2730 * In addition to the parameters of exchange_cell_data_to_ghosts(), this
2731 * function allows to provide a @p cell_filter function, which can be used to only
2732 * communicate marked cells. In the default case, all relevant cells are
2733 * communicated.
2734 *
2735 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
2736 */
2737 template <typename DataType, typename MeshType>
2738 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
2739 void exchange_cell_data_to_level_ghosts(
2740 const MeshType &mesh,
2741 const std::function<std::optional<DataType>(
2742 const typename MeshType::level_cell_iterator &)> &pack,
2743 const std::function<void(const typename MeshType::level_cell_iterator &,
2744 const DataType &)> &unpack,
2745 const std::function<bool(const typename MeshType::level_cell_iterator &)> &
2746 cell_filter = always_return<typename MeshType::level_cell_iterator, bool>{
2747 true});
2748
2749 /* Exchange with all processors of the MPI communicator @p mpi_communicator the vector of bounding
2750 * boxes @p local_bboxes.
2751 *
2752 * This function is meant to exchange bounding boxes describing the locally
2753 * owned cells in a distributed triangulation obtained with the function
2754 * GridTools::compute_mesh_predicate_bounding_box .
2755 *
2756 * The output vector's size is the number of processes of the MPI
2757 * communicator:
2758 * its i-th entry contains the vector @p local_bboxes of the i-th process.
2759 */
2760 template <int spacedim>
2761 std::vector<std::vector<BoundingBox<spacedim>>>
2762 exchange_local_bounding_boxes(
2763 const std::vector<BoundingBox<spacedim>> &local_bboxes,
2764 const MPI_Comm mpi_communicator);
2765
2766 /**
2767 * In this @ref GlossCollectiveOperation "collective operation" each process provides a vector
2768 * of bounding boxes and a communicator.
2769 * All these vectors are gathered on each of the processes,
2770 * organized in a search tree, and then returned.
2771 *
2772 * The idea is that the vector of bounding boxes describes a
2773 * relevant property of the computations on each process
2774 * individually, which could also be of use to other processes. An
2775 * example would be if the input vector of bounding boxes
2776 * corresponded to a covering of the locally owned partition of a
2777 * mesh (see
2778 * @ref GlossLocallyOwnedCell)
2779 * of a
2780 * parallel::distributed::Triangulation object. While these may
2781 * overlap the bounding boxes of other processes, finding which
2782 * process owns the cell that encloses a given point is vastly
2783 * easier if the process trying to figure this out has a (relatively
2784 * small) list of processes whose bounding boxes contain that point.
2785 *
2786 * The returned search tree object is an r-tree with packing
2787 * algorithm, which is provided by boost library. See
2788 * https://www.boost.org/doc/libs/1_67_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html
2789 * for more information.
2790 *
2791 * In the returned tree, each node contains a pair of elements:
2792 * the first being a bounding box,
2793 * the second being the rank of the process for which at least some
2794 * of the locally owned cells overlap with the bounding box.
2795 *
2796 * @note This function is a @ref GlossCollectiveOperation "collective operation".
2797 */
2798 template <int spacedim>
2799 RTree<std::pair<BoundingBox<spacedim>, unsigned int>>
2800 build_global_description_tree(
2801 const std::vector<BoundingBox<spacedim>> &local_description,
2802 const MPI_Comm mpi_communicator);
2803
2804 /**
2805 * Collect for a given triangulation all locally relevant vertices that
2806 * coincide due to periodicity.
2807 *
2808 * Coinciding vertices are put into a group, e.g.: [1, 25, 51], which is
2809 * labeled by an arbitrary element from it, e.g.: "1". All coinciding vertices
2810 * store the label to its group, so that they can quickly access all the
2811 * coinciding vertices in that group: e.g.: 51 -> "1" -> [1, 25, 51]
2812 *
2813 * @param[in] tria Triangulation.
2814 * @param[out] coinciding_vertex_groups A map of equivalence classes (of
2815 * coinciding vertices) labeled by an arbitrary element from them.
2816 * Vertices not coinciding are ignored.
2817 * @param[out] vertex_to_coinciding_vertex_group Map of a vertex to the label
2818 * of a group of coinciding vertices. Vertices not contained in
2819 * this vector are not coinciding with any other vertex.
2820 */
2821 template <int dim, int spacedim>
2822 void
2823 collect_coinciding_vertices(
2824 const Triangulation<dim, spacedim> &tria,
2825 std::map<unsigned int, std::vector<unsigned int>> &coinciding_vertex_groups,
2826 std::map<unsigned int, unsigned int> &vertex_to_coinciding_vertex_group);
2827
2828 /**
2829 * Return a map that, for each vertex of the given triangulation,
2830 * provides a set of all the process subdomain ids whose subdomains
2831 * are adjacent to that vertex. The set excludes the subdomain id
2832 * of the current process. As a consequence, for a given vertex,
2833 * the returned set consists of exactly those subdomain ids that
2834 * correspond to the
2835 * @ref GlossGhostCell "ghost cells"
2836 * adjacent to that vertex, assuming there are any such ghost cells.
2837 *
2838 * For vertices that are not adjacent to a ghost cell, the map contains
2839 * no entries, and this should be interpreted in the same way as if
2840 * the map contained an entry for a given vertex index, but that the
2841 * `std::set` associated with that map entry is simply empty.
2842 * For non-parallel triangulations, the map is consequently empty
2843 * since no vertex has adjacent ghost cells.
2844 *
2845 * @param[in] tria Triangulation.
2846 */
2847 template <int dim, int spacedim>
2848 std::map<unsigned int, std::set<dealii::types::subdomain_id>>
2849 compute_vertices_with_ghost_neighbors(
2850 const Triangulation<dim, spacedim> &tria);
2851
2852 /**
2853 * An implementation of the marching-square (2d) and marching-cube algorithm
2854 * for creating data structures (vectors of Point and CellData) to
2855 * create a linear/bilinear surface mesh on the iso line/contour of a
2856 * scalar field.
2857 *
2858 * To improve the approximation of the iso line/contour and the resulting
2859 * linear surface mesh, one increases the number of subdivision so that the
2860 * algorithm is not run on a cell but on subcells with vertex values having
2861 * been interpolated from the cell values.
2862 *
2863 * @note The resulting mesh will contain lines in 2d and triangles in 3d.
2864 *
2865 * @note The resulting mesh will not be of high quality, since it might
2866 * contain cells with very small diameters if the mesh is cut close to a
2867 * vertex.
2868 *
2869 * @note Iso lines/contours as a saddle point within a subcell is not
2870 * detected by the implemented algorithm.
2871 */
2872 template <int dim, typename VectorType>
2873 class MarchingCubeAlgorithm
2874 {
2875 public:
2876 /**
2877 * Value type of vector.
2878 */
2879 using value_type = typename VectorType::value_type;
2880
2881 /**
2882 * Constructor.
2883 */
2884 MarchingCubeAlgorithm(const Mapping<dim, dim> &mapping,
2885 const FiniteElement<dim, dim> &fe,
2886 const unsigned int n_subdivisions = 1,
2887 const double tolerance = 1e-10);
2888
2889 /**
2890 * Process all locally-owned cells and fill @p vertices and @p cells for all
2891 * cells that are cut.
2892 *
2893 * @note This function is only implemented for dim>1. Use
2894 * process(background_dof_handler, ls_vector, iso_level, vertices) for
2895 * dim==1.
2896 *
2897 * @note Duplicate vertices are not deleted.
2898 */
2899 void
2900 process(const DoFHandler<dim> &background_dof_handler,
2901 const VectorType &ls_vector,
2902 const double iso_level,
2903 std::vector<Point<dim>> &vertices,
2904 std::vector<CellData<dim == 1 ? 1 : dim - 1>> &cells) const;
2905
2906 /**
2907 * Process all locally-owned cells and fill @p vertices for all cells that
2908 * are cut.
2909 */
2910 void
2911 process(const DoFHandler<dim> &background_dof_handler,
2912 const VectorType &ls_vector,
2913 const double iso_level,
2914 std::vector<Point<dim>> &vertices) const;
2915
2916 /**
2917 * Process the provided cell and fill @p vertices and @p cells for all cells
2918 * that are cut.
2919 *
2920 * @note The resulting vectors are empty if the cell is not cut.
2921 *
2922 * @note This function is only implemented for dim>1. Use
2923 * process_cell(cell, ls_vector, iso_level, vertices) for dim==1.
2924 */
2925 void
2926 process_cell(const typename DoFHandler<dim>::active_cell_iterator &cell,
2927 const VectorType &ls_vector,
2928 const double iso_level,
2929 std::vector<Point<dim>> &vertices,
2930 std::vector<CellData<dim == 1 ? 1 : dim - 1>> &cells) const;
2931 /**
2932 * Process the provided cell and fill @p vertices for all cells that are cut.
2933 *
2934 * @note The resulting vector is empty if the cell is not cut.
2935 */
2936 void
2937 process_cell(const typename DoFHandler<dim>::active_cell_iterator &cell,
2938 const VectorType &ls_vector,
2939 const double iso_level,
2940 std::vector<Point<dim>> &vertices) const;
2941
2942 private:
2943 /**
2944 * Internal function to create a quadrature rule with n_subdivisions+1
2945 * equally-positioned quadrature points.
2946 */
2947 static Quadrature<dim>
2948 create_quadrature_rule(const unsigned int n_subdivisions);
2949
2950 /**
2951 * Process a cell.
2952 */
2953 void
2954 process_cell(std::vector<value_type> &ls_values,
2955 const std::vector<Point<dim>> &points,
2956 const double iso_level,
2957 std::vector<Point<dim>> &vertices,
2958 std::vector<CellData<dim == 1 ? 1 : dim - 1>> &cells,
2959 const bool write_back_cell_data = true) const;
2960
2961 /**
2962 * Dummy function for 1d processing a sub-cell.
2963 */
2964 void
2965 process_sub_cell(const std::vector<value_type> &,
2966 const std::vector<Point<1>> &,
2967 const std::vector<unsigned int> &,
2968 const double,
2969 std::vector<Point<1>> &,
2970 std::vector<CellData<1>> &,
2971 const bool) const
2972 {
2973 AssertThrow(false, ExcNotImplemented());
2974 }
2975
2976 /**
2977 * Process a sub-cell (2d).
2978 *
2979 * @note Subcells with saddle points are ignored. Please increase the number
2980 * of subdivisions in this case.
2981 */
2982 void
2983 process_sub_cell(const std::vector<value_type> &ls_values,
2984 const std::vector<Point<2>> &points,
2985 const std::vector<unsigned int> &mask,
2986 const double iso_level,
2987 std::vector<Point<2>> &vertices,
2988 std::vector<CellData<1>> &cells,
2989 const bool write_back_cell_data) const;
2990
2991 /**
2992 * Process a sub-cell (3d).
2993 */
2994 void
2995 process_sub_cell(const std::vector<value_type> &ls_values,
2996 const std::vector<Point<3>> &points,
2997 const std::vector<unsigned int> &mask,
2998 const double iso_level,
2999 std::vector<Point<3>> &vertices,
3000 std::vector<CellData<2>> &cells,
3001 const bool write_back_cell_data) const;
3002
3003 /**
3004 * Number of subdivisions each cell is subdivided into in each direction to
3005 * improve the approximation.
3006 */
3007 const unsigned int n_subdivisions;
3008
3009 /**
3010 * Absolute tolerance specifying the minimum distance between a vertex and
3011 * the cut point so that a line is considered cut.
3012 */
3013 const double tolerance;
3014
3015 /**
3016 * FEValues used internally and set up with a quadrature rule with the
3017 * correct number of subdivisions.
3018 */
3019 mutable FEValues<dim> fe_values;
3020 };
3021
3022
3023
3024 /**
3025 * @name Exceptions
3026 */
3027 /** @{ */
3028
3029 /**
3030 * Exception
3031 */
3032 DeclException1(ExcInvalidNumberOfPartitions,
3033 int,
3034 << "The number of partitions you gave is " << arg1
3035 << ", but must be greater than zero.");
3036 /**
3037 * Exception
3038 */
3039 DeclException1(ExcNonExistentSubdomain,
3040 int,
3041 << "The subdomain id " << arg1
3042 << " has no cells associated with it.");
3043 /**
3044 * Exception
3045 */
3046 DeclException0(ExcTriangulationHasBeenRefined);
3047
3048 /**
3049 * Exception
3050 */
3051 DeclException1(ExcScalingFactorNotPositive,
3052 double,
3053 << "The scaling factor must be positive, but it is " << arg1
3054 << '.');
3055
3056 /**
3057 * Exception
3058 */
3059 DeclException1(ExcVertexNotUsed,
3060 unsigned int,
3061 << "The given vertex with index " << arg1
3062 << " is not used in the given triangulation.");
3063
3064 /** @} */
3065
3066 } /*namespace GridTools*/
3067
3068 /* ----------------- Template function --------------- */
3069
3070 #ifndef DOXYGEN
3071
3072 namespace GridTools
3073 {
3074 template <int dim>
3075 double
3076 cell_measure(
3077 const std::vector<Point<dim>> &all_vertices,
3078 const unsigned int (&indices)[GeometryInfo<dim>::vertices_per_cell])
3079 {
3080 // We forward call to the ArrayView version:
3081 const ArrayView<const unsigned int> view(
3082 indices, GeometryInfo<dim>::vertices_per_cell);
3083 return cell_measure(all_vertices, view);
3084 }
3085
3086
3087
3088 // This specialization is defined here so that the general template in the
3089 // source file doesn't need to have further 1d overloads for the internal
3090 // functions it calls.
3091 template <>
3092 inline Triangulation<1, 1>::DistortedCellList
3093 fix_up_distorted_child_cells(const Triangulation<1, 1>::DistortedCellList &,
3094 Triangulation<1, 1> &)
3095 {
3096 return {};
3097 }
3098
3099
3100
3101 template <int dim, typename Transformation, int spacedim>
3102 DEAL_II_CXX20_REQUIRES(
3103 (std::invocable<Transformation, Point<spacedim>> &&
3104 std::assignable_from<
3105 Point<spacedim> &,
3106 std::invoke_result_t<Transformation, Point<spacedim>>>))
3107 void transform(const Transformation &transformation,
3108 Triangulation<dim, spacedim> &triangulation)
3109 {
3110 std::vector<bool> treated_vertices(triangulation.n_vertices(), false);
3111
3112 // loop over all active cells, and
3113 // transform those vertices that
3114 // have not yet been touched. note
3115 // that we get to all vertices in
3116 // the triangulation by only
3117 // visiting the active cells.
3118 typename Triangulation<dim, spacedim>::active_cell_iterator
3119 cell = triangulation.begin_active(),
3120 endc = triangulation.end();
3121 for (; cell != endc; ++cell)
3122 for (const unsigned int v : cell->vertex_indices())
3123 if (treated_vertices[cell->vertex_index(v)] == false)
3124 {
3125 // transform this vertex
3126 cell->vertex(v) = transformation(cell->vertex(v));
3127 // and mark it as treated
3128 treated_vertices[cell->vertex_index(v)] = true;
3129 };
3130
3131
3132 // now fix any vertices on hanging nodes so that we don't create any holes
3133 if (dim == 2)
3134 {
3135 typename Triangulation<dim, spacedim>::active_cell_iterator
3136 cell = triangulation.begin_active(),
3137 endc = triangulation.end();
3138 for (; cell != endc; ++cell)
3139 for (const unsigned int face : cell->face_indices())
3140 if (cell->face(face)->has_children() &&
3141 !cell->face(face)->at_boundary())
3142 {
3143 Assert(cell->reference_cell() ==
3144 ReferenceCells::get_hypercube<dim>(),
3145 ExcNotImplemented());
3146
3147 // this line has children
3148 cell->face(face)->child(0)->vertex(1) =
3149 (cell->face(face)->vertex(0) + cell->face(face)->vertex(1)) /
3150 2.0;
3151 }
3152 }
3153 else if (dim == 3)
3154 {
3155 typename Triangulation<dim, spacedim>::active_cell_iterator
3156 cell = triangulation.begin_active(),
3157 endc = triangulation.end();
3158 for (; cell != endc; ++cell)
3159 for (const unsigned int face : cell->face_indices())
3160 if (cell->face(face)->has_children() &&
3161 !cell->face(face)->at_boundary())
3162 {
3163 if (static_cast<std::uint8_t>(
3164 cell->face(face)->refinement_case()) ==
3165 RefinementCase<dim - 1>::isotropic_refinement)
3166 {
3167 Assert(cell->reference_cell() ==
3168 ReferenceCells::get_hypercube<dim>(),
3169 ExcNotImplemented());
3170
3171 // this face has hanging nodes
3172 cell->face(face)->child(0)->vertex(1) =
3173 (cell->face(face)->vertex(0) +
3174 cell->face(face)->vertex(1)) /
3175 2.0;
3176 cell->face(face)->child(0)->vertex(2) =
3177 (cell->face(face)->vertex(0) +
3178 cell->face(face)->vertex(2)) /
3179 2.0;
3180 cell->face(face)->child(1)->vertex(3) =
3181 (cell->face(face)->vertex(1) +
3182 cell->face(face)->vertex(3)) /
3183 2.0;
3184 cell->face(face)->child(2)->vertex(3) =
3185 (cell->face(face)->vertex(2) +
3186 cell->face(face)->vertex(3)) /
3187 2.0;
3188
3189 // center of the face
3190 cell->face(face)->child(0)->vertex(3) =
3191 (cell->face(face)->vertex(0) +
3192 cell->face(face)->vertex(1) +
3193 cell->face(face)->vertex(2) +
3194 cell->face(face)->vertex(3)) /
3195 4.0;
3196 }
3197 else
3198 {
3199 // Special case for anisotropic refinement
3200 for (unsigned int line = 0;
3201 line < GeometryInfo<dim - 1>::faces_per_cell;
3202 line++)
3203 if (cell->face(face)->line(line)->has_children())
3204 cell->face(face)->line(line)->child(0)->vertex(1) =
3205 (cell->face(face)->line(line)->vertex(0) +
3206 cell->face(face)->line(line)->vertex(1)) /
3207 2.0;
3208 }
3209 }
3210 }
3211
3212 // Make sure FEValues notices that the mesh has changed
3213 triangulation.signals.mesh_movement();
3214 }
3215
3216
3217
3218 template <typename MeshType>
3219 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
3220 std::vector<typename MeshType::active_cell_iterator> get_active_child_cells(
3221 const typename MeshType::cell_iterator &cell)
3222 {
3223 std::vector<typename MeshType::active_cell_iterator> child_cells;
3224
3225 if (cell->has_children())
3226 {
3227 for (unsigned int child = 0; child < cell->n_children(); ++child)
3228 if (cell->child(child)->has_children())
3229 {
3230 const std::vector<typename MeshType::active_cell_iterator>
3231 children = get_active_child_cells<MeshType>(cell->child(child));
3232 child_cells.insert(child_cells.end(),
3233 children.begin(),
3234 children.end());
3235 }
3236 else
3237 child_cells.push_back(cell->child(child));
3238 }
3239
3240 return child_cells;
3241 }
3242
3243
3244
3245 template <typename MeshType>
3246 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
3247 void get_active_neighbors(
3248 const typename MeshType::active_cell_iterator &cell,
3249 std::vector<typename MeshType::active_cell_iterator> &active_neighbors)
3250 {
3251 active_neighbors.clear();
3252 for (const unsigned int n : cell->face_indices())
3253 if (!cell->at_boundary(n))
3254 {
3255 if (MeshType::dimension == 1)
3256 {
3257 // check children of neighbor. note
3258 // that in 1d children of the neighbor
3259 // may be further refined. In 1d the
3260 // case is simple since we know what
3261 // children bound to the present cell
3262 typename MeshType::cell_iterator neighbor_child =
3263 cell->neighbor(n);
3264 if (!neighbor_child->is_active())
3265 {
3266 while (neighbor_child->has_children())
3267 neighbor_child = neighbor_child->child(n == 0 ? 1 : 0);
3268
3269 Assert(neighbor_child->neighbor(n == 0 ? 1 : 0) == cell,
3270 ExcInternalError());
3271 }
3272 active_neighbors.push_back(neighbor_child);
3273 }
3274 else
3275 {
3276 if (cell->face(n)->has_children())
3277 // this neighbor has children. find
3278 // out which border to the present
3279 // cell
3280 for (unsigned int c = 0;
3281 c < cell->face(n)->n_active_descendants();
3282 ++c)
3283 active_neighbors.push_back(
3284 cell->neighbor_child_on_subface(n, c));
3285 else
3286 {
3287 // the neighbor must be active
3288 // himself
3289 Assert(cell->neighbor(n)->is_active(), ExcInternalError());
3290 active_neighbors.push_back(cell->neighbor(n));
3291 }
3292 }
3293 }
3294 }
3295
3296
3297
3298 template <typename CellIterator>
3299 std::size_t
3300 PeriodicFacePair<CellIterator>::memory_consumption() const
3301 {
3302 return sizeof(*this) + matrix.memory_consumption();
3303 }
3304
3305
3306
3307 namespace internal
3308 {
3309 template <typename DataType,
3310 typename MeshType,
3311 typename MeshCellIteratorType>
3312 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
3313 inline void exchange_cell_data(
3314 const MeshType &mesh,
3315 const std::function<std::optional<DataType>(const MeshCellIteratorType &)>
3316 &pack,
3317 const std::function<void(const MeshCellIteratorType &, const DataType &)>
3318 &unpack,
3319 const std::function<bool(const MeshCellIteratorType &)> &cell_filter,
3320 const std::function<void(
3321 const std::function<void(const MeshCellIteratorType &,
3322 const types::subdomain_id)> &)> &process_cells,
3323 const std::function<std::set<types::subdomain_id>(
3324 const parallel::TriangulationBase<MeshType::dimension,
3325 MeshType::space_dimension> &)>
3326 &compute_ghost_owners)
3327 {
3328 # ifndef DEAL_II_WITH_MPI
3329 (void)mesh;
3330 (void)pack;
3331 (void)unpack;
3332 (void)cell_filter;
3333 (void)process_cells;
3334 (void)compute_ghost_owners;
3335 Assert(false, ExcNeedsMPI());
3336 # else
3337 constexpr int dim = MeshType::dimension;
3338 constexpr int spacedim = MeshType::space_dimension;
3339 auto tria =
3340 dynamic_cast<const parallel::TriangulationBase<dim, spacedim> *>(
3341 &mesh.get_triangulation());
3342 Assert(
3343 tria != nullptr,
3344 ExcMessage(
3345 "The function exchange_cell_data_to_ghosts() only works with parallel triangulations."));
3346
3347 if (const auto tria = dynamic_cast<
3348 const parallel::shared::Triangulation<dim, spacedim> *>(
3349 &mesh.get_triangulation()))
3350 {
3351 Assert(
3352 tria->with_artificial_cells(),
3353 ExcMessage(
3354 "The functions GridTools::exchange_cell_data_to_ghosts() and "
3355 "GridTools::exchange_cell_data_to_level_ghosts() can only "
3356 "operate on a single layer of ghost cells. However, you have "
3357 "given a Triangulation object of type "
3358 "parallel::shared::Triangulation without artificial cells "
3359 "resulting in an arbitrary number of ghost layers. "
3360 "To use this function for a Triangulation object of type "
3361 "parallel::shared::Triangulation, make sure to create the "
3362 "Triangulation object with allow_artificial_cells set to true. "
3363 "This results in a parallel::shared::Triangulation with only "
3364 "a single layer of ghost cells."));
3365 }
3366
3367 // build list of cells to request for each neighbor
3368 std::set<dealii::types::subdomain_id> ghost_owners =
3369 compute_ghost_owners(*tria);
3370 std::map<dealii::types::subdomain_id,
3371 std::vector<typename CellId::binary_type>>
3372 neighbor_cell_list;
3373
3374 for (const auto ghost_owner : ghost_owners)
3375 neighbor_cell_list[ghost_owner] = {};
3376
3377 process_cells([&](const auto &cell, const auto key) -> void {
3378 if (cell_filter(cell))
3379 {
3380 constexpr int spacedim = MeshType::space_dimension;
3381 neighbor_cell_list[key].emplace_back(
3382 cell->id().template to_binary<spacedim>());
3383 }
3384 });
3385
3386 Assert(ghost_owners.size() == neighbor_cell_list.size(),
3387 ExcInternalError());
3388
3389
3390 // Before sending & receiving, make sure we protect this section with
3391 // a mutex:
3392 static Utilities::MPI::CollectiveMutex mutex;
3393 Utilities::MPI::CollectiveMutex::ScopedLock lock(
3394 mutex, tria->get_mpi_communicator());
3395
3396 const int mpi_tag =
3397 Utilities::MPI::internal::Tags::exchange_cell_data_request;
3398 const int mpi_tag_reply =
3399 Utilities::MPI::internal::Tags::exchange_cell_data_reply;
3400
3401 // send our requests
3402 std::vector<MPI_Request> requests(ghost_owners.size());
3403 {
3404 unsigned int idx = 0;
3405 for (const auto &it : neighbor_cell_list)
3406 {
3407 // send the data about the relevant cells
3408 const int ierr = MPI_Isend(it.second.data(),
3409 it.second.size() * sizeof(it.second[0]),
3410 MPI_BYTE,
3411 it.first,
3412 mpi_tag,
3413 tria->get_mpi_communicator(),
3414 &requests[idx]);
3415 AssertThrowMPI(ierr);
3416 ++idx;
3417 }
3418 }
3419
3420 // receive requests and reply with the results
3421 std::vector<MPI_Request> reply_requests(ghost_owners.size());
3422 std::vector<std::vector<char>> sendbuffers(ghost_owners.size());
3423
3424 for (unsigned int idx = 0; idx < ghost_owners.size(); ++idx)
3425 {
3426 MPI_Status status;
3427 int ierr = MPI_Probe(MPI_ANY_SOURCE,
3428 mpi_tag,
3429 tria->get_mpi_communicator(),
3430 &status);
3431 AssertThrowMPI(ierr);
3432
3433 int len;
3434 ierr = MPI_Get_count(&status, MPI_BYTE, &len);
3435 AssertThrowMPI(ierr);
3436 Assert(len % sizeof(typename CellId::binary_type) == 0,
3437 ExcInternalError());
3438
3439 const unsigned int n_cells =
3440 len / sizeof(typename CellId::binary_type);
3441 std::vector<typename CellId::binary_type> cells_with_requests(
3442 n_cells);
3443 std::vector<DataType> data_to_send;
3444 data_to_send.reserve(n_cells);
3445 std::vector<bool> cell_carries_data(n_cells, false);
3446
3447 ierr = MPI_Recv(cells_with_requests.data(),
3448 len,
3449 MPI_BYTE,
3450 status.MPI_SOURCE,
3451 status.MPI_TAG,
3452 tria->get_mpi_communicator(),
3453 &status);
3454 AssertThrowMPI(ierr);
3455
3456 // store data for each cell
3457 for (unsigned int c = 0; c < static_cast<unsigned int>(n_cells); ++c)
3458 {
3459 const auto cell =
3460 tria->create_cell_iterator(CellId(cells_with_requests[c]));
3461
3462 MeshCellIteratorType mesh_it(tria,
3463 cell->level(),
3464 cell->index(),
3465 &mesh);
3466
3467 const std::optional<DataType> data = pack(mesh_it);
3468 if (data)
3469 {
3470 data_to_send.emplace_back(*data);
3471 cell_carries_data[c] = true;
3472 }
3473 }
3474
3475 // collect data for sending the reply in a buffer
3476
3477 // (a) make room for storing the local offsets in case we receive
3478 // other data
3479 sendbuffers[idx].resize(sizeof(std::size_t));
3480
3481 // (b) append the actual data and store how much memory it
3482 // corresponds to, which we then insert into the leading position of
3483 // the sendbuffer
3484 std::size_t size_of_send =
3485 Utilities::pack(data_to_send,
3486 sendbuffers[idx],
3487 /*enable_compression*/ false);
3488 std::memcpy(sendbuffers[idx].data(),
3489 &size_of_send,
3490 sizeof(std::size_t));
3491
3492 // (c) append information of certain cells that got left out in case
3493 // we need it
3494 if (data_to_send.size() < n_cells)
3495 Utilities::pack(cell_carries_data,
3496 sendbuffers[idx],
3497 /*enable_compression*/ false);
3498
3499 // send data
3500 ierr = MPI_Isend(sendbuffers[idx].data(),
3501 sendbuffers[idx].size(),
3502 MPI_BYTE,
3503 status.MPI_SOURCE,
3504 mpi_tag_reply,
3505 tria->get_mpi_communicator(),
3506 &reply_requests[idx]);
3507 AssertThrowMPI(ierr);
3508 }
3509
3510 // finally receive the replies
3511 std::vector<char> receive;
3512 for (unsigned int id = 0; id < neighbor_cell_list.size(); ++id)
3513 {
3514 MPI_Status status;
3515 int ierr = MPI_Probe(MPI_ANY_SOURCE,
3516 mpi_tag_reply,
3517 tria->get_mpi_communicator(),
3518 &status);
3519 AssertThrowMPI(ierr);
3520
3521 int len;
3522 ierr = MPI_Get_count(&status, MPI_BYTE, &len);
3523 AssertThrowMPI(ierr);
3524
3525 receive.resize(len);
3526
3527 ierr = MPI_Recv(receive.data(),
3528 len,
3529 MPI_BYTE,
3530 status.MPI_SOURCE,
3531 status.MPI_TAG,
3532 tria->get_mpi_communicator(),
3533 &status);
3534 AssertThrowMPI(ierr);
3535
3536 // (a) first determine the length of the data section in the
3537 // received buffer
3538 auto data_iterator = receive.begin();
3539 std::size_t size_of_received_data =
3540 Utilities::unpack<std::size_t>(data_iterator,
3541 data_iterator + sizeof(std::size_t));
3542 data_iterator += sizeof(std::size_t);
3543
3544 // (b) unpack the data section in the indicated region
3545 auto received_data = Utilities::unpack<std::vector<DataType>>(
3546 data_iterator,
3547 data_iterator + size_of_received_data,
3548 /*enable_compression*/ false);
3549 data_iterator += size_of_received_data;
3550
3551 // (c) check if the received data contained fewer entries than the
3552 // number of cells we identified in the beginning, in which case we
3553 // need to extract the boolean vector with the relevant information
3554 const std::vector<typename CellId::binary_type> &this_cell_list =
3555 neighbor_cell_list[status.MPI_SOURCE];
3556 AssertIndexRange(received_data.size(), this_cell_list.size() + 1);
3557 std::vector<bool> cells_with_data;
3558 if (received_data.size() < this_cell_list.size())
3559 {
3560 cells_with_data = Utilities::unpack<std::vector<bool>>(
3561 data_iterator, receive.end(), /*enable_compression*/ false);
3562 AssertDimension(cells_with_data.size(), this_cell_list.size());
3563 }
3564
3565 // (d) go through the received data and call the user-provided
3566 // unpack function
3567 auto received_data_iterator = received_data.begin();
3568 for (unsigned int c = 0; c < this_cell_list.size(); ++c)
3569 if (cells_with_data.empty() || cells_with_data[c])
3570 {
3571 const typename Triangulation<dim, spacedim>::cell_iterator
3572 tria_cell = tria->create_cell_iterator(this_cell_list[c]);
3573
3574 MeshCellIteratorType cell(tria,
3575 tria_cell->level(),
3576 tria_cell->index(),
3577 &mesh);
3578
3579 unpack(cell, *received_data_iterator);
3580 ++received_data_iterator;
3581 }
3582 }
3583
3584 // make sure that all communication is finished
3585 // when we leave this function.
3586 if (requests.size() > 0)
3587 {
3588 const int ierr =
3589 MPI_Waitall(requests.size(), requests.data(), MPI_STATUSES_IGNORE);
3590 AssertThrowMPI(ierr);
3591 }
3592 if (reply_requests.size() > 0)
3593 {
3594 const int ierr = MPI_Waitall(reply_requests.size(),
3595 reply_requests.data(),
3596 MPI_STATUSES_IGNORE);
3597 AssertThrowMPI(ierr);
3598 }
3599
3600
3601 # endif // DEAL_II_WITH_MPI
3602 }
3603
3604 } // namespace internal
3605
3606 template <typename DataType, typename MeshType>
3607 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
3608 inline void exchange_cell_data_to_ghosts(
3609 const MeshType &mesh,
3610 const std::function<std::optional<DataType>(
3611 const typename MeshType::active_cell_iterator &)> &pack,
3612 const std::function<void(const typename MeshType::active_cell_iterator &,
3613 const DataType &)> &unpack,
3614 const std::function<bool(const typename MeshType::active_cell_iterator &)>
3615 &cell_filter)
3616 {
3617 # ifndef DEAL_II_WITH_MPI
3618 (void)mesh;
3619 (void)pack;
3620 (void)unpack;
3621 (void)cell_filter;
3622 Assert(false, ExcNeedsMPI());
3623 # else
3624 internal::exchange_cell_data<DataType,
3625 MeshType,
3626 typename MeshType::active_cell_iterator>(
3627 mesh,
3628 pack,
3629 unpack,
3630 cell_filter,
3631 [&](const auto &process) {
3632 for (const auto &cell : mesh.active_cell_iterators())
3633 if (cell->is_ghost())
3634 process(cell, cell->subdomain_id());
3635 },
3636 [](const auto &tria) { return tria.ghost_owners(); });
3637 # endif
3638 }
3639
3640
3641
3642 template <typename DataType, typename MeshType>
3643 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
3644 inline void exchange_cell_data_to_level_ghosts(
3645 const MeshType &mesh,
3646 const std::function<std::optional<DataType>(
3647 const typename MeshType::level_cell_iterator &)> &pack,
3648 const std::function<void(const typename MeshType::level_cell_iterator &,
3649 const DataType &)> &unpack,
3650 const std::function<bool(const typename MeshType::level_cell_iterator &)>
3651 &cell_filter)
3652 {
3653 # ifndef DEAL_II_WITH_MPI
3654 (void)mesh;
3655 (void)pack;
3656 (void)unpack;
3657 (void)cell_filter;
3658 Assert(false, ExcNeedsMPI());
3659 # else
3660 internal::exchange_cell_data<DataType,
3661 MeshType,
3662 typename MeshType::level_cell_iterator>(
3663 mesh,
3664 pack,
3665 unpack,
3666 cell_filter,
3667 [&](const auto &process) {
3668 for (const auto &cell : mesh.cell_iterators())
3669 if (cell->is_ghost_on_level())
3670 process(cell, cell->level_subdomain_id());
3671 },
3672 [](const auto &tria) { return tria.level_ghost_owners(); });
3673 # endif
3674 }
3675 } // namespace GridTools
3676
3677 #endif // DOXYGEN
3678
3679 DEAL_II_NAMESPACE_CLOSE
3680
3681 #endif