Debian Codegraph @

include/deal.II/non_matching/quadrature_generator.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2020 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_non_matching_quadrature_generator_h
16 #define dealii_non_matching_quadrature_generator_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/bounding_box.h>
21 #include <deal.II/base/function.h>
22 #include <deal.II/base/function_restriction.h>
23 #include <deal.II/base/quadrature.h>
24
25 #include <deal.II/dofs/dof_handler.h>
26
27 #include <deal.II/grid/tria.h>
28
29 #include <deal.II/hp/q_collection.h>
30
31 #include <deal.II/non_matching/immersed_surface_quadrature.h>
32
33 #include <functional>
34 #include <optional>
35
36 DEAL_II_NAMESPACE_OPEN
37 namespace NonMatching
38 {
39 namespace internal
40 {
41 namespace QuadratureGeneratorImplementation
42 {
43 template <int dim, int spacedim>
44 class QGenerator;
45 } // namespace QuadratureGeneratorImplementation
46
47
48 namespace DiscreteQuadratureGeneratorImplementation
49 {
50 template <int dim>
51 class CellWiseFunction;
52 } // namespace DiscreteQuadratureGeneratorImplementation
53 } // namespace internal
54
55
56 /**
57 * Struct storing settings for the QuadratureGenerator class.
58 */
59 struct AdditionalQGeneratorData
60 {
61 /**
62 * Constructor.
63 */
64 AdditionalQGeneratorData(const unsigned int max_box_splits = 4,
65 const double lower_bound_implicit_function = 1e-11,
66 const double min_distance_between_roots = 1e-12,
67 const double limit_to_be_definite = 1e-11,
68 const double root_finder_tolerance = 1e-12,
69 const unsigned int max_root_finder_splits = 2,
70 bool split_in_half = true);
71
72 /**
73 * The number of times we are allowed to split the incoming box
74 * and recurse on each child.
75 */
76 unsigned int max_box_splits;
77
78 /**
79 * For a level set function, $\psi$, the implicit function theorem states
80 * that it is possible to write one of the coordinates $x_i$ as a function
81 * of the others if
82 *
83 * $|\frac{\partial \psi}{\partial x_i}| > 0$.
84 *
85 * In practice, the bound we have for the expression in the left-hand side
86 * may be near but not equal to zero due to roundoff errors.
87 *
88 * This constant is a safety margin, $C$, that states that the implicit
89 * function theorem can be used when
90 *
91 * $|\frac{\partial \psi}{\partial x_i}| > C$
92 *
93 * Thus this constant must be non-negative.
94 */
95 double lower_bound_implicit_function;
96
97 /**
98 * If two roots are closer to each other than this distance they are
99 * merged to one.
100 */
101 double min_distance_between_roots;
102
103 /**
104 * A constant, $C$, controlling when a level set function, $\psi$, is
105 * considered positive or negative definite:
106 *
107 * $\psi(x) > C \Rightarrow \text{Positive definite}$,
108 * $\psi(x) < -C \Rightarrow \text{Negative definite}$.
109 */
110 double limit_to_be_definite;
111
112 /**
113 * Tolerance for convergence of the underlying root finder.
114 */
115 double root_finder_tolerance;
116
117 /**
118 * The number of times the underlying rootfinder is allowed to split
119 * an interval, while trying to find multiple roots.
120 */
121 unsigned int max_root_finder_splits;
122
123 /**
124 * This determines how a box is split when this is necessary. If true, the
125 * box is split in two, if set to false the box is split into its $2^{dim}$
126 * children.
127 */
128 bool split_in_half;
129 };
130
131
132
133 /**
134 * This class creates immersed quadrature rules over a BoundingBox,
135 * $B \subset \mathbb{R}^{dim}$, when the domain is described by a level set
136 * function, $\psi$.
137 *
138 * This class creates quadrature rules for the intersections between the box
139 * and the three different regions defined by the level set function. That is,
140 * it creates quadrature rules to integrate over the following regions
141 * @f[
142 * N = \{x \in B : \psi(x) < 0 \}, \\
143 * P = \{x \in B : \psi(x) > 0 \}, \\
144 * S = \{x \in B : \psi(x) = 0 \}.
145 * @f]
146 * @image html immersed_quadratures.svg
147 *
148 * When working with level set functions, the most common is to describe a
149 * domain, $\Omega$, as
150 * @f[
151 * \Omega = \{ x \in \mathbb{R}^{dim} : \psi(x) < 0 \}.
152 * @f]
153 * Given this, we shall use the name convention that $N$ is the "inside"
154 * region (i.e. inside $\Omega$), $P$ is the "outside" region and $S$ is
155 * the "surface" region. The "inside" and "outside" quadratures will also be
156 * referred to as the "bulk"-quadratures.
157 *
158 * The underlying algorithm use a 1-dimensional quadrature rule as base for
159 * creating the immersed quadrature rules. Gauss-Legendre quadrature
160 * (QGauss) is recommended. The constructor takes an hp::QCollection<1>.
161 * One can select which 1d-quadrature in the collection should be used
162 * through the set_1d_quadrature() function. The number of quadrature points
163 * in the constructed quadratures will vary depending on the level set
164 * function. More quadrature points will be created if the intersection is
165 * "bad", for example, if the zero-contour has a high curvature compared to
166 * the size of the box. However, if the number of points in the 1d quadrature
167 * is $n$ the number of points will be proportional to $n^{dim}$ in the bulk
168 * quadratures and to $n^{dim-1}$ in the surface quadrature. For example,
169 * in the 2d-example in the above figure, there are 2 points in the
170 * 1d-quadrature. If the 1d-quadrature is a Gauss-Legendre quadrature and the
171 * grid has size $h$, the immersed quadratures typically give global errors
172 * proportional to $h^{2n}$, both for the bulk and surface integrals. If the
173 * 1d-quadrature has positive weights, the weights of the immersed quadratures
174 * will also be positive.
175 *
176 * A detailed description of the underlying algorithm can be found in
177 * @cite saye_2015. This implementation has some modifications
178 * compared to the algorithm description in the paper. In particular, it
179 * builds the three different types of quadratures (inside, outside and
180 * surface) simultaneously. Further, the so-called "pruning" step is not yet
181 * implemented.
182 */
183 template <int dim>
184 class QuadratureGenerator
185 {
186 public:
187 using AdditionalData = AdditionalQGeneratorData;
188
189 /**
190 * Constructor. Each Quadrature<1> in @p quadratures1d can be chosen as base
191 * for generating the immersed quadrature rules.
192 *
193 * @note It is important that each 1d-quadrature rule in the
194 * hp::QCollection does not contain the points 0 and 1.
195 */
196 QuadratureGenerator(
197 const hp::QCollection<1> &quadratures1D,
198 const AdditionalData &additional_data = AdditionalData());
199
200 /**
201 * Clears the inside, outside and surface quadratures.
202 */
203 void
204 clear_quadratures();
205
206 /**
207 * Construct immersed quadratures rules for the incoming level set
208 * function over the BoundingBox.
209 *
210 * To get the constructed quadratures, use the functions
211 * get_inside_quadrature(),
212 * get_outside_quadrature(),
213 * get_surface_quadrature().
214 *
215 * @note Both value, gradient and hessian need to be implemented on the
216 * incoming function.
217 */
218 void
219 generate(const Function<dim> &level_set, const BoundingBox<dim> &box);
220
221 /**
222 * Same as above but does not clear quadratures and appends it to the
223 * existing quadrature instead.
224 */
225 void
226 generate_append(const Function<dim> &level_set,
227 const BoundingBox<dim> &box);
228
229 /**
230 * Return the quadrature rule for the region
231 * $\{x \in B : \psi(x) < 0 \}$
232 * created in the previous call to generate().
233 * Here, $B$ is BoundingBox passed to generate().
234 */
235 const Quadrature<dim> &
236 get_inside_quadrature() const;
237
238 /**
239 * Return the quadrature rule for the region
240 * $\{x \in B : \psi(x) > 0 \}$
241 * created in the previous call to generate().
242 * Here, $B$ is BoundingBox passed to generate().
243 */
244 const Quadrature<dim> &
245 get_outside_quadrature() const;
246
247 /**
248 * Return the quadrature rule for the region
249 * $\{x \in B : \psi(x) = 0 \}$
250 * created in the previous call to generate().
251 * Here, $B$ is BoundingBox passed to generate().
252 *
253 * @note The normal at the quadrature points will be parallel to $\nabla \psi$.
254 */
255 const ImmersedSurfaceQuadrature<dim> &
256 get_surface_quadrature() const;
257
258 /**
259 * Set which 1d-quadrature in the collection passed to the constructor
260 * should be used to create the immersed quadratures.
261 */
262 void
263 set_1D_quadrature(const unsigned int q_index);
264
265 private:
266 /**
267 * QuadratureGenerator is mainly used to start up the recursive
268 * algorithm. This is the object that actually generates the quadratures.
269 */
270 internal::QuadratureGeneratorImplementation::QGenerator<dim, dim>
271 q_generator;
272 };
273
274
275 /**
276 * This class creates immersed quadrature rules over a face, $F$, of a
277 * BoundingBox, when the domain is described by a level set function, $\psi$.
278 *
279 * In the same way as in the QuadratureGenerator class, this class generates
280 * quadrature rules to integrate over 3 different regions of the face,
281 * $F \subset \mathbb{R}^{dim}$:
282 * @f[
283 * N = \{x \in F : \psi(x) < 0 \}, \\
284 * P = \{x \in F : \psi(x) > 0 \}, \\
285 * S = \{x \in F : \psi(x) = 0 \},
286 * @f]
287 * which are again referred to as the "inside", $N$, "outside", $P$,
288 * and "surface" region, $S$. These type of quadrature rules are in general
289 * needed in immersed discontinuous Galerkin methods.
290 *
291 * Under the hood, this class uses the QuadratureGenerator class to build
292 * these rules. This is done by restricting the dim-dimensional level set
293 * function to the face, thus creating a (dim-1)-dimensional level set
294 * function, $\phi$. It then creates the (dim-1)-dimensional quadratures by
295 * calling QuadratureGenerator with $\phi$. This means that what holds for the
296 * QuadratureGenerator class in general also holds for this class. In
297 * particular, if the 1d-quadrature that is used as base contains $n$ points,
298 * the number of points will be proportional to $n^{dim-1}$ in the in the
299 * inside/outside quadratures and to $n^{dim-2}$ in the surface quadrature.
300 */
301 template <int dim>
302 class FaceQuadratureGenerator
303 {
304 public:
305 using AdditionalData = AdditionalQGeneratorData;
306
307 /**
308 * Constructor. Each Quadrature<1> in @p quadratures1d can be chosen as base
309 * for generating the immersed quadrature rules.
310 *
311 * @note It is important that each 1d-quadrature rule in the
312 * hp::QCollection does not contain the points 0 and 1.
313 */
314 FaceQuadratureGenerator(
315 const hp::QCollection<1> &quadratures1D,
316 const AdditionalData &additional_data = AdditionalData());
317
318 /**
319 * Clears the inside, outside and surface quadratures.
320 */
321 void
322 clear_quadratures();
323
324 /**
325 * Construct immersed quadratures rules for the incoming level set
326 * function on a given face of the BoundingBox.
327 *
328 * To get the constructed quadratures, use the functions
329 * get_inside_quadrature(),
330 * get_outside_quadrature(),
331 * get_surface_quadrature().
332 *
333 * @note Both value, gradient and hessian need to be implemented on the
334 * incoming function.
335 */
336 void
337 generate(const Function<dim> &level_set,
338 const BoundingBox<dim> &box,
339 const unsigned int face_index);
340
341 /**
342 * Same as above but does not clear quadratures and appends it to the
343 * existing quadrature instead.
344 */
345 void
346 generate_append(const Function<dim> &level_set,
347 const BoundingBox<dim> &box,
348 const unsigned int face_index);
349
350 /**
351 * Return the quadrature rule for the region
352 * $\{x \in F : \psi(x) < 0 \}$
353 * created in the previous call to generate().
354 * Here, $F$ is the face of the BoundingBox passed to generate().
355 */
356 const Quadrature<dim - 1> &
357 get_inside_quadrature() const;
358
359 /**
360 * Return the quadrature rule for the region
361 * $\{x \in F : \psi(x) > 0 \}$
362 * created in the previous call to generate().
363 * Here, $F$ is the face of the BoundingBox passed to generate().
364 */
365 const Quadrature<dim - 1> &
366 get_outside_quadrature() const;
367
368 /**
369 * Return the quadrature rule for the region
370 * $\{x \in F : \psi(x) = 0 \}$
371 * created in the previous call to generate().
372 * Here, $F$ is the face of the BoundingBox passed to generate().
373 *
374 * @note The normal at the quadrature points will be parallel to $\nabla \psi$.
375 */
376 const ImmersedSurfaceQuadrature<dim - 1, dim> &
377 get_surface_quadrature() const;
378
379 /**
380 * Set which 1d-quadrature in the collection passed to the constructor
381 * should be used to create the immersed quadratures.
382 */
383 void
384 set_1D_quadrature(const unsigned int q_index);
385
386 private:
387 /**
388 * Lower-dimensional quadrature generator used to build the quadratures over
389 * the face.
390 */
391 QuadratureGenerator<dim - 1> quadrature_generator;
392
393 /**
394 * The same surface quadrature as created by the quadrature_generator,
395 * but having dim-dimensional normals.
396 */
397 ImmersedSurfaceQuadrature<dim - 1, dim> surface_quadrature;
398 };
399
400
401 /**
402 * Specialization of the FaceQuadratureGenerator class for the 1-dimensional
403 * case.
404 *
405 * In 1d, a face is only a point. Thus to generate the immersed
406 * quadrature rules we add a single 0-dimensional quadrature point to the
407 * inside or outside quadrature rule depending on if the level set function is
408 * positive or negative at the face. The added quadrature point will have
409 * weight equal to 1. The immersed surface quadrature over a face corresponds
410 * to integrating over a dim-1 dimensional curve. Thus, surface quadrature
411 * generated by this specialized class is always empty.
412 *
413 * This class must be specialized in 1d, because the general
414 * FaceQuadratureGenerator<dim> class uses the QuadratureGenerator<dim-1>
415 * class internally, which does not make sense when dim-1 = 0.
416 */
417 template <>
418 class FaceQuadratureGenerator<1>
419 {
420 public:
421 using AdditionalData = AdditionalQGeneratorData;
422
423 /**
424 * Constructor. The incoming hp::QCollection is not used. But this class
425 * must have the same signature as the non-specialized class.
426 */
427 FaceQuadratureGenerator(
428 const hp::QCollection<1> &quadratures1D,
429 const AdditionalData &additional_data = AdditionalData());
430
431 /**
432 * Does nothing. Exists for compatibility reasons.
433 */
434 void
435 clear_quadratures();
436
437 /**
438 * Construct immersed quadratures rules for the incoming level set
439 * function on a given face of the BoundingBox.
440 *
441 * To get the constructed quadratures, use the functions
442 * get_inside_quadrature(),
443 * get_outside_quadrature(),
444 * get_surface_quadrature().
445 */
446 void
447 generate(const Function<1> &level_set,
448 const BoundingBox<1> &box,
449 const unsigned int face_index);
450
451 /**
452 * Same as above but does not clear quadratures and appends it to the
453 * existing quadrature instead.
454 */
455 void
456 generate_append(const Function<1> &level_set,
457 const BoundingBox<1> &box,
458 const unsigned int face_index);
459
460 /**
461 * @copydoc FaceQuadratureGenerator<dim>::get_inside_quadrature()
462 */
463 const Quadrature<0> &
464 get_inside_quadrature() const;
465
466 /**
467 * @copydoc FaceQuadratureGenerator<dim>::get_outside_quadrature()
468 */
469 const Quadrature<0> &
470 get_outside_quadrature() const;
471
472 /**
473 * Return the quadrature rule for the region
474 * $\{x \in F : \psi(x) = 0 \}$
475 * where, $F$ is the face of the BoundingBox passed to generate().
476 *
477 * @note In 1d, this quadrature always contains 0 points.
478 */
479 const ImmersedSurfaceQuadrature<0, 1> &
480 get_surface_quadrature() const;
481
482 /**
483 * This function does nothing. It only exist to be compatible with
484 * FaceQuadratureGenerator<dim>.
485 */
486 void
487 set_1D_quadrature(const unsigned int q_index);
488
489 private:
490 /**
491 * Quadrature for the region
492 * $\{x \in F : \psi(x) < 0 \}$.
493 * Created in the last call to generate().
494 */
495 Quadrature<0> inside_quadrature;
496
497 /**
498 * Quadrature for the region
499 * $\{x \in F : \psi(x) > 0 \}$.
500 * Created in the last call to generate().
501 */
502 Quadrature<0> outside_quadrature;
503
504 /**
505 * Quadrature for the region
506 * $\{x \in F : \psi(x) = 0 \}$.
507 * This quadrature always contains zero points in 1d.
508 */
509 const ImmersedSurfaceQuadrature<0, 1> surface_quadrature;
510 };
511
512
513 /**
514 * This class generates the same type of immersed quadrature rules as those
515 * described in the QuadratureGenerator class. The difference is that this
516 * class handles the case when the domain is a discrete level set
517 * function, i.e., when the level set function is described as a
518 * (DoFHandler, Vector) pair. The generate()-function of this class takes a
519 * cell in real space and constructs the immersed quadrature rules in
520 * reference space over this cell. These quadrature rules can then be obtained
521 * with one of the functions:
522 * get_inside_quadrature(),
523 * get_outside_quadrature(), and
524 * get_surface_quadrature().
525 *
526 * Internally, the quadrature generation is done by transforming the discrete
527 * level set function from real space to reference space and using the same
528 * algorithm as in the QuadratureGenerator class.
529 */
530 template <int dim>
531 class DiscreteQuadratureGenerator : public QuadratureGenerator<dim>
532 {
533 public:
534 using AdditionalData = AdditionalQGeneratorData;
535
536 /**
537 * Constructor, the discrete level set function is described by the
538 * incoming DoFHandler and Vector. Pointers to these are stored
539 * internally, so they must have a longer lifetime than the created this
540 * class. The hp::QCollection<1> and AdditionalData is passed to the
541 * QuadratureGenerator class.
542 */
543 template <typename Number>
544 DiscreteQuadratureGenerator(
545 const hp::QCollection<1> &quadratures1D,
546 const DoFHandler<dim> &dof_handler,
547 const ReadVector<Number> &level_set,
548 const AdditionalData &additional_data = AdditionalData());
549
550 /**
551 * Construct immersed quadratures rules based on the discrete level
552 * set vector over the incoming cell.
553 *
554 * @note The cell needs to belong to the same triangulation as the one
555 * associated with the DoFHandler passed to the constructor.
556 */
557 void
558 generate(const typename Triangulation<dim>::active_cell_iterator &cell);
559
560 private:
561 /**
562 * Construct immersed quadratures for FE_Q_iso_Q1.
563 */
564 void
565 generate_fe_q_iso_q1(const BoundingBox<dim> &unit_box);
566
567 /**
568 * Function that describes our level set function in reference space.
569 */
570 std::unique_ptr<internal::DiscreteQuadratureGeneratorImplementation::
571 CellWiseFunction<dim>>
572 reference_space_level_set;
573 };
574
575 /**
576 * This class generates the same type of immersed quadrature rules as those
577 * described in the FaceQuadratureGenerator class. The difference is that this
578 * class handles the case when the domain is a discrete level set
579 * function, i.e., when the level set function is described as a
580 * (DoFHandler, Vector) pair. The generate()-function of this class takes a
581 * cell in real space plus the respective face index and constructs the
582 * immersed quadrature rules in reference space over this face. These
583 * quadrature rules can then be obtained with one of the functions:
584 * get_inside_quadrature(),
585 * get_outside_quadrature(), and
586 * get_surface_quadrature().
587 *
588 * Internally, the quadrature generation is done by transforming the discrete
589 * level set function from real space to reference space and using the same
590 * algorithm as in the FaceQuadratureGenerator class.
591 */
592 template <int dim>
593 class DiscreteFaceQuadratureGenerator : public FaceQuadratureGenerator<dim>
594 {
595 public:
596 using AdditionalData = AdditionalQGeneratorData;
597
598 /**
599 * Constructor, the discrete level set function is described by the
600 * incoming DoFHandler and Vector. Pointers to these are stored
601 * internally, so they must have a longer lifetime than the created this
602 * class. The hp::QCollection<1> and AdditionalData is passed to the
603 * QuadratureGenerator class.
604 */
605 template <typename Number>
606 DiscreteFaceQuadratureGenerator(
607 const hp::QCollection<1> &quadratures1D,
608 const DoFHandler<dim> &dof_handler,
609 const ReadVector<Number> &level_set,
610 const AdditionalData &additional_data = AdditionalData());
611
612 /**
613 * Construct immersed quadratures rules based on the discrete level
614 * set vector over the incoming face described by cell and face index.
615 *
616 * @note The cell needs to belong to the same triangulation as the one
617 * associated with the DoFHandler passed to the constructor.
618 */
619 void
620 generate(const typename Triangulation<dim>::active_cell_iterator &cell,
621 const unsigned int face_index);
622
623 private:
624 /**
625 * Construct immersed quadratures for FE_Q_iso_Q1.
626 */
627 void
628 generate_fe_q_iso_q1(const BoundingBox<dim> &unit_box,
629 unsigned int face_index);
630
631 /**
632 * Function that describes our level set function in reference space.
633 */
634 std::unique_ptr<internal::DiscreteQuadratureGeneratorImplementation::
635 CellWiseFunction<dim>>
636 reference_space_level_set;
637 };
638
639
640 namespace internal
641 {
642 namespace QuadratureGeneratorImplementation
643 {
644 /**
645 * A class that attempts to find multiple distinct roots of a function,
646 * $f(x)$, over an interval, $[l, r]$. This is done as follows. If there
647 * is a sign change in function value between the interval end points,
648 * we solve for the root. If there is no sign change, we attempt to
649 * bound the function value away from zero on $[a, b]$, to conclude that
650 * no roots exist. If we can't exclude that there are roots, we split
651 * the interval in two: $[l, (r + l) / 2]$, $[(r + l) / 2, r]$, and use
652 * the same algorithm recursively on each interval. This means that we
653 * can typically find 2 distinct roots, but not 3.
654 *
655 * The bounds on the functions values are estimated using the function
656 * taylor_estimate_function_bounds, which approximates the function as a
657 * second order Taylor-polynomial around the interval midpoint.
658 * When we have a sign change on an interval, this class uses
659 * boost::math::tools::toms748_solve for finding roots .
660 */
661 class RootFinder
662 {
663 public:
664 /**
665 * Struct storing settings for the RootFinder class.
666 */
667 struct AdditionalData
668 {
669 /**
670 * Constructor.
671 */
672 AdditionalData(const double tolerance = 1e-12,
673 const unsigned int max_recursion_depth = 2,
674 const unsigned int max_iterations = 500);
675
676 /**
677 * The tolerance in the stopping criteria for the underlying root
678 * finding algorithm boost::math::tools::toms748_solve.
679 */
680 double tolerance;
681
682 /**
683 * The number of times we are allowed to split the interval where we
684 * seek roots.
685 */
686 unsigned int max_recursion_depth;
687
688 /**
689 * The maximum number of iterations in
690 * boost::math::tools::toms748_solve.
691 */
692 unsigned int max_iterations;
693 };
694
695
696 /**
697 * Constructor.
698 */
699 RootFinder(const AdditionalData &data = AdditionalData());
700
701 /**
702 * For each of the incoming @p functions, attempt to find the roots over
703 * the interval defined by @p interval and add these to @p roots.
704 * The returned roots will be sorted in ascending order:
705 * $x_0 < x_1 <...$ and duplicate roots (with respect to the tolerance
706 * in AdditionalData) will be removed.
707 */
708 void
709 find_roots(const std::vector<std::reference_wrapper<const Function<1>>>
710 &functions,
711 const BoundingBox<1> &interval,
712 std::vector<double> &roots);
713
714 private:
715 /**
716 * Attempt to find the roots of the @p function over the interval defined by
717 * @p interval and add these to @p roots. @p recursion_depth holds the number
718 * of times this function has been called recursively.
719 */
720 void
721 find_roots(const Function<1> &function,
722 const BoundingBox<1> &interval,
723 const unsigned int recursion_depth,
724 std::vector<double> &roots);
725
726 const AdditionalData additional_data;
727 };
728
729
730 /**
731 * This is a special Quadrature class with a push_back() method for
732 * conveniently adding a point with an associated weight.
733 *
734 * Since we build the quadrature rules in step-wise fashion,
735 * it's easier to use this class than to pass around two vectors:
736 * std::vector<Point<dim>>,
737 * std::vector<double>.
738 * Further, two std::vectors could accidentally end up with different
739 * sizes. Using push_back we make sure that the number of points and
740 * weights are the same.
741 */
742 template <int dim>
743 class ExtendableQuadrature : public Quadrature<dim>
744 {
745 public:
746 /**
747 * Constructor, creates an empty quadrature rule with no
748 * points.
749 */
750 ExtendableQuadrature() = default;
751
752 /**
753 * Constructor, copies the incoming Quadrature.
754 */
755 ExtendableQuadrature(const Quadrature<dim> &quadrature);
756
757 /**
758 * Clears weights and points vectors.
759 */
760 void
761 clear();
762
763 /**
764 * Add a point with an associated weight to the quadrature.
765 */
766 void
767 push_back(const Point<dim> &point, const double weight);
768 };
769
770
771 /**
772 * Type that describes the definiteness of a function over a region.
773 */
774 enum class Definiteness
775 {
776 negative,
777 positive,
778 indefinite
779 };
780
781
782 /**
783 * Class that stores quadrature rules to integrate over 4 different
784 * regions of a single BoundingBox, $B$. Given multiple level set
785 * functions,
786 *
787 * $\psi_i : \mathbb{R}^{dim} \rightarrow \mathbb{R}$, $i = 0, 1, ...$,
788 *
789 * the box, $B \subset \mathbb{R}^{dim}$, is partitioned into a
790 * "negative", "positive", and "indefinite" region, $B = N \cup P \cup I$,
791 * according to the signs of $\psi_i$ over each region:
792 *
793 * @f[
794 * N = \{x \in B : \psi_i(x) < 0, \forall i \}, \\
795 * P = \{x \in B : \psi_i(x) > 0, \forall i \}, \\
796 * I = B \setminus (\overline{N} \cup \overline{P}).
797 * @f]
798 *
799 * Thus, all $\psi_i$ are positive over $P$ and negative over $N$. Over
800 * $I$ the level set functions differ in sign. This class holds quadrature
801 * rules for each of these regions. In addition, when there is a single
802 * level set function, $\psi$, it holds a surface quadrature for the zero
803 * contour of $\psi$:
804 *
805 * $S = \{x \in B : \psi(x) = 0 \}$.
806 *
807 * Note that when there is a single level set function, $I$ is empty
808 * and $N$ and $P$ are the regions that one typically integrates over in
809 * an immersed finite element method.
810 */
811 template <int dim>
812 class QPartitioning
813 {
814 public:
815 /**
816 * Return a reference to the "bulk" quadrature with the same name as the
817 * member in Definiteness.
818 */
819 ExtendableQuadrature<dim> &
820 quadrature_by_definiteness(const Definiteness definiteness);
821
822 /**
823 * Clears all quadratures.
824 */
825 void
826 clear();
827
828 /**
829 * Quadrature for the region $\{x \in B : \psi_i(x) < 0 \forall i \}$ of
830 * the box, $B$.
831 */
832 ExtendableQuadrature<dim> negative;
833
834 /**
835 * Quadrature for the region $\{x \in B : \psi_i(x) > 0 \forall i \}$ of
836 * the box, $B$.
837 */
838 ExtendableQuadrature<dim> positive;
839
840 /**
841 * Quadrature for a region where the level set functions have different
842 * sign.
843 */
844 ExtendableQuadrature<dim> indefinite;
845
846 /**
847 * Quadrature for the region $\{x \in B : \psi(x) = 0 \}$ of the
848 * box, $B$.
849 */
850 ImmersedSurfaceQuadrature<dim> surface;
851 };
852
853
854 /**
855 * This class is responsible for creating quadrature points for
856 * the $dim$-dimensional quadrature partitioning from an
857 * $(dim - 1)$-dimensional "indefinite" quadrature (see
858 * QPartitioning documentation).
859 *
860 * To be precise, let $[L, R]$ be the extents of the box in the height
861 * function direction and let $I \subset \mathbb{R}^{dim-1}$ be the lower
862 * dimensional indefinite region. This class will create quadrature points
863 * over $I \times [L, R] \subset \mathbb{R}^{dim}$ and in the case
864 * $dim=spacedim$, points for the surface quadrature.
865 *
866 * For each lower dimensional quadrature point, $(x_I, w_I)$ in the
867 * indefinite quadrature, we create several 1d-level set functions by
868 * restricting $\psi_j$ to $x_I$. We then partition the interval $[L, R]$
869 * into $[y_0, y_1, ..., y_n]$, where $y_0 = L$, $y_n = R$, and the
870 * remaining $y_i$ are the roots of the 1d-level set functions in
871 * $[L, R]$. Since the level set functions change sign between the
872 * roots, each interval belong to different regions in the quadrature
873 * partitioning.
874 *
875 * In each interval, $[y_i, y_{i+1}]$, we distribute points
876 * according to the 1d-base quadrature, $(x_q, w_q)$ and take the
877 * cartesian product with $(x_I, w_I)$ to create the $dim$-dimensional
878 * quadrature points, $(X_q, W_q)$:
879 * $X_q = x_I \times (y_i + (y_{i+1} - y_i) x_q)$,
880 * $W_q = w_I (y_{i+1} - y_i) w_q$.
881 *
882 * When $dim=spacedim$, we have a single level set function, $\psi$. Since
883 * we have fulfilled the implicit function theorem, there is a single root
884 * $y_1 \in [L, R]$. The point, $x_s = x_I \times y_1$, will be added as a
885 * point in the surface quadrature. One can show that the correct weight
886 * of this point is
887 *
888 * $w_s = \frac{\|\nabla \psi(x_s)\|}{|\partial_i \psi(x_s)|} w_I$,
889 *
890 * where $i$ is the height function direction.
891 */
892 template <int dim, int spacedim>
893 class UpThroughDimensionCreator
894 {
895 public:
896 /**
897 * Constructor. Takes the same parameters as QuadratureGenerator.
898 */
899 UpThroughDimensionCreator(
900 const hp::QCollection<1> &q_collection1D,
901 const AdditionalQGeneratorData &additional_data);
902
903 /**
904 * Create $dim$-dimensional immersed quadratures from the incoming
905 * $(dim-1)$-dimensional quadratures and add these to
906 * @p q_partitioning.
907 */
908 void
909 generate(const std::vector<std::reference_wrapper<const Function<dim>>>
910 &level_sets,
911 const BoundingBox<dim> &box,
912 const Quadrature<dim - 1> &low_dim_quadrature,
913 const unsigned int height_function_direction,
914 QPartitioning<dim> &q_partitioning);
915
916 /**
917 * Set which 1d-quadrature in the collection passed to the constructor
918 * should be used to create the immersed quadratures.
919 */
920 void
921 set_1D_quadrature(const unsigned int q_index);
922
923 private:
924 /**
925 * Create a surface quadrature point from the lower-dimensional point
926 * and add it to surface_quadrature.
927 *
928 * This function is only called when $dim=spacedim$ and there is a
929 * single level set function. At this point there should only be a
930 * single root in the interval $[L, R]$
931 */
932 void
933 create_surface_point(
934 const Point<dim - 1> &point,
935 const double weight,
936 const std::vector<std::reference_wrapper<const Function<dim>>>
937 &level_sets,
938 const BoundingBox<dim> &box,
939 const unsigned int height_function_direction,
940 ImmersedSurfaceQuadrature<dim> &surface_quadrature);
941
942 /**
943 * One dimensional quadrature rules used to create the immersed
944 * quadratures.
945 */
946 const ObserverPointer<const hp::QCollection<1>> q_collection1D;
947
948 /**
949 * Stores options/settings for the algorithm.
950 */
951 const AdditionalQGeneratorData additional_data;
952
953 /**
954 * Which quadrature rule in the above collection that is used to
955 * create the immersed quadrature rules.
956 */
957 unsigned int q_index;
958
959 /**
960 * 1d-functions, that are restrictions of each dim-dimensional level set
961 * function passed to generate() to some $(dim-1)$-dimensional point.
962 */
963 std::vector<Functions::PointRestriction<dim - 1>> point_restrictions;
964
965 /**
966 * Class used to find the roots of the above 1d-restrictions.
967 */
968 RootFinder root_finder;
969
970 /**
971 * The roots of the functions in point_restrictions.
972 * This will be the values of the height functions, $\{H_i(x_I)\}$ at
973 * some lower dimensional quadrature point,
974 * $x_I \in \mathbb{R}^{dim-1}$.
975 */
976 std::vector<double> roots;
977 };
978
979
980 /**
981 * Data representing the best choice of height-function direction,
982 * which is returned by the function find_best_height_direction.
983 *
984 * This data consists of a coordinate direction
985 *
986 * $i \in \{0, ..., dim - 1 \}$,
987 *
988 * and lower bound on the absolute value of the derivative of some
989 * associated function, f, taken in the above coordinate direction. That
990 * is, a bound $C$ such that
991 *
992 * $|\frac{\partial f}{\partial x_i}| > C$,
993 *
994 * holding over some subset of $\mathbb{R}^{dim}$.
995 */
996 struct HeightDirectionData
997 {
998 /**
999 * Constructor. Initializes the direction to invalid_unsigned_int and
1000 * the bound to 0.
1001 */
1002 HeightDirectionData();
1003
1004
1005 /**
1006 * The height-function direction, described above.
1007 */
1008 unsigned int direction;
1009
1010 /**
1011 * The lower bound on $|\frac{\partial f}{\partial x_i}|$, described
1012 * above.
1013 */
1014 double min_abs_dfdx;
1015 };
1016
1017
1018 /**
1019 * Base class for the class QGenerator<dim, spacedim> and the
1020 * one-dimensional specialization QGenerator<1, spacedim>.
1021 */
1022 template <int dim, int spacedim>
1023 class QGeneratorBase
1024 {
1025 public:
1026 QGeneratorBase(const hp::QCollection<1> &q_collection1D,
1027 const AdditionalQGeneratorData &additional_data);
1028
1029 /**
1030 * Clear the quadratures created by the previous call to generate().
1031 */
1032 void
1033 clear_quadratures();
1034
1035 /**
1036 * Return the created quadratures.
1037 */
1038 const QPartitioning<dim> &
1039 get_quadratures() const;
1040
1041 protected:
1042 /**
1043 * Stores options/settings for the algorithm.
1044 */
1045 const AdditionalQGeneratorData additional_data;
1046
1047 /**
1048 * Which 1d-quadrature in the collection we should use to generate
1049 * the immersed quadrature.
1050 */
1051 unsigned int q_index;
1052
1053 /**
1054 * Index of the quadrature in q_collection1d that should use to
1055 * generate the immersed quadrature rules.
1056 */
1057 const ObserverPointer<const hp::QCollection<1>> q_collection1D;
1058
1059 /**
1060 * Quadratures that the derived classes create.
1061 */
1062 QPartitioning<dim> q_partitioning;
1063 };
1064
1065
1066 /**
1067 * This class implements the Saye-algorithm cited in the documentation of
1068 * the QuadratureGenerator class.
1069 *
1070 * The generate function takes a number of $dim$-dimensional level set
1071 * functions, $\psi_i$, and a BoundingBox<dim>, and builds a partitioning
1072 * of quadratures, as defined in documentation of the QPartitioning class.
1073 * That is, this class builds an object of type QPartitioning<dim>.
1074 *
1075 * If all $\psi_i$ passed to generate can be determined to be positive or
1076 * negative definite, the QPartitioning will consist of a single
1077 * quadrature forming a tensor product.
1078 *
1079 * If this is not the case, the algorithm uses recursion over the spatial
1080 * dimension. The spacedim template parameter denotes the dimension we
1081 * started with and dim denotes on what level we are in the recursion.
1082 * That is, we first construct a QPartitioning<dim - 1> and then
1083 * build the higher dimensional quadratures from these. What we in the end
1084 * actually want is a spacedim-dimensional partitioning of quadratures,
1085 * for a single level set function, $\psi$.
1086 *
1087 * The algorithm is based on the implicit function theorem. Starting with
1088 * a single level set function, $\psi$, we try to find a direction $i$,
1089 * such that
1090 *
1091 * $|\frac{\partial \psi}{\partial x_i}| > 0$.
1092 *
1093 * throughout the whole box. This means that the zero-contour of the
1094 * level set function can be parameterized by an implicit function
1095 *
1096 * $H = H(x_0, ..., x_{i-1}, x_{i+1}, ..., x_{dim-1})$,
1097 *
1098 * so that
1099 *
1100 * $\psi(..., x_{i-1}, H(..., x_{i-1}, x_{i+1}, ...), x_{i+1}, ...) = 0$,
1101 *
1102 * over a subset, $I \subset C \subset \mathbb{R}^{dim-1}$, of the cross
1103 * section, $C$, of the box (see BoundingBox::cross_section). Here, $I$ is
1104 * the "indefinite"-region defined in the QPartitioning class. To follow
1105 * convention in the original paper, we will -refer to $H$ as the
1106 * "height-function" and to $i$ as the "height-function direction".
1107 *
1108 * If a height function direction can be found, we go down in dimension by
1109 * creating two new level set functions, $\{\psi_0, \psi_1\}$, which are
1110 * the restriction of $\psi$ to the top and bottom faces of the box (in
1111 * the height function direction). We then delegate to
1112 * QGenerator<dim-1, spacedim> to create a QPartitioning<dim-1> over
1113 * the cross section.
1114 *
1115 * When we reach the base case, $dim = 1$, the creation of
1116 * QPartitioning<1> is simple. See the documentation in specialized
1117 * class: QGenerator<1, spacedim>.
1118 *
1119 * As we go up through the dimensions and create the higher dimensional
1120 * quadratures, we need to know the function value of the height
1121 * functions at the lower dimensional quadrature points. Since the
1122 * functions are implicit, we need to do root-finding on the level set
1123 * functions to find the function values. For this we use the class
1124 * UpThroughDimensionCreator, see documentation there.
1125 *
1126 * When we have $n$ level set functions (i.e. after having gone
1127 * down in dimension), we try to find a height function direction,
1128 * which works for all those $\psi_i$ which are intersected by the zero
1129 * contour (i.e. those not positive or negative definite).
1130 * If such a direction exist, we will have a maximum of $n$ associated
1131 * implicit height functions, $H_j$. Each $H_j$ parametrize the
1132 * $x_i$-coordinate of the zero-contour over a region, $I_j$. The
1133 * indefinite region in the lower dimensional partitioning is the union of
1134 * these $I = \cup_j I_j$.
1135 *
1136 * As we try to find a height function direction, we estimate bounds on
1137 * the gradient components by approximating each component as a 1st-order
1138 * Taylor-polynomial. If a direction can not be found, the box is split
1139 * and we recurse on each smaller box. This makes an implicit function
1140 * more likely to exist since we seek it over a smaller portion of the
1141 * zero contour. It also makes the estimated bounds tighter since we
1142 * extrapolate the Taylor-polynomial a shorter distance.
1143 *
1144 * Since we can not split a box forever, there is an maximum number of
1145 * allowed splits on the additional data struct passed to the constructor.
1146 * If this is reached, the algorithm uses the midpoint method as a last
1147 * resort.
1148 */
1149 template <int dim, int spacedim>
1150 class QGenerator : public QGeneratorBase<dim, spacedim>
1151 {
1152 public:
1153 /**
1154 * Constructor. Takes the same parameters QuadratureGenerator.
1155 */
1156 QGenerator(const hp::QCollection<1> &q_collection1D,
1157 const AdditionalQGeneratorData &additional_data);
1158
1159 /**
1160 * Create immersed quadrature rules over the incoming @p box and add
1161 * these to the internal QPartitioning<dim> object in the base class.
1162 * These quadratures can then be obtained using the
1163 * get_quadratures-function.
1164 *
1165 * This function calls itself if the incoming box need to be split.
1166 * @p n_box_splits counts the number of times this function has called
1167 * itself.
1168 */
1169 void
1170 generate(const std::vector<std::reference_wrapper<const Function<dim>>>
1171 &level_sets,
1172 const BoundingBox<dim> &box,
1173 const unsigned int n_box_splits);
1174
1175 /**
1176 * Set which 1d-quadrature in the collection passed to the constructor
1177 * should be used to create the immersed quadratures.
1178 */
1179 void
1180 set_1D_quadrature(const unsigned int q_index);
1181
1182 private:
1183 /**
1184 * Restricts the incoming level set functions to the top and bottom of
1185 * the incoming box (w.r.t @p height_function_direction). Then call the
1186 * lower dimensional QGenerator with the cross section of the box
1187 * to generate the lower dimensional immersed quadrature rules.
1188 */
1189 void
1190 create_low_dim_quadratures(
1191 const unsigned int height_function_direction,
1192 const std::vector<std::reference_wrapper<const Function<dim>>>
1193 &level_sets,
1194 const BoundingBox<dim> &box,
1195 const unsigned int n_box_splits);
1196
1197 /**
1198 * Gets the $(dim - 1)$-dimensional quadratures from the lower
1199 * dimensional algorithm and creates the $dim$-dimensional quadrature
1200 * rules over the box from the lower dimensional ones.
1201 */
1202 void
1203 create_high_dim_quadratures(
1204 const unsigned int height_function_direction,
1205 const std::vector<std::reference_wrapper<const Function<dim>>>
1206 &level_sets,
1207 const BoundingBox<dim> &box);
1208
1209 /**
1210 * Split the incoming box and call generate() recursively with each box.
1211 * The box is split in 2 or 4 parts depending on the value of
1212 * AdditionalQGeneratorData::split_in_half.
1213 */
1214 void
1215 split_box_and_recurse(
1216 const std::vector<std::reference_wrapper<const Function<dim>>>
1217 &level_sets,
1218 const BoundingBox<dim> &box,
1219 const std::optional<HeightDirectionData> &direction_data,
1220 const unsigned int n_box_splits);
1221
1222 /**
1223 * Uses the midpoint-method to create a quadrature over the box.
1224 * That is, add a single quadrature point at the center of the box
1225 * with weight corresponding to the volume of the box.
1226 *
1227 * The point is added to the region defined in QPartitioning
1228 * according to the signs of the level set functions at the center of
1229 * the box.
1230 */
1231 void
1232 use_midpoint_method(
1233 const std::vector<std::reference_wrapper<const Function<dim>>>
1234 &level_sets,
1235 const BoundingBox<dim> &box);
1236
1237 /**
1238 * The same algorithm as this, but creating immersed quadratures
1239 * in one dimension lower.
1240 */
1241 QGenerator<dim - 1, spacedim> low_dim_algorithm;
1242
1243 /**
1244 * Object responsible for creating the $dim$-dimensional quadratures
1245 * from
1246 */
1247 UpThroughDimensionCreator<dim, spacedim> up_through_dimension_creator;
1248
1249 /**
1250 * Stores tensor products of each of the Quadrature<1>'s in
1251 * q_collection1d.
1252 */
1253 hp::QCollection<dim> tensor_products;
1254 };
1255
1256
1257 /**
1258 * The 1d-base case of the recursive algorithm QGenerator<dim, spacedim>.
1259 *
1260 * Let $L$ and $R$ be the left and right bounds of the one-dimensional
1261 * BoundingBox. This interval is partitioned into $[x_0, x_1, ..., x_n]$
1262 * where $x_0 = L$, $x_n = R$, and the remaining $x_i$ are the roots
1263 * of the level set functions in the interval $[L, R]$. In each interval,
1264 * $[x_i, x_{i+1}]$, quadrature points are distributed according to a
1265 * 1d-quadrature rule. These points are added to one of the regions of
1266 * QPartitioning determined from the signs of the level set
1267 * functions on the interval (see documentation of QPartitioning).
1268 *
1269 * If spacedim = 1 the points $[x_1, x_{n-1}]$ are also added as surface
1270 * quadrature points to QPartitioning::surface.
1271 */
1272 template <int spacedim>
1273 class QGenerator<1, spacedim> : public QGeneratorBase<1, spacedim>
1274 {
1275 public:
1276 /**
1277 * Constructor. Takes the same parameters QuadratureGenerator.
1278 */
1279 QGenerator(const hp::QCollection<1> &quadratures1D,
1280 const AdditionalQGeneratorData &additional_data);
1281
1282 /**
1283 * Creates quadrature points over the interval defined by the incoming
1284 * box and adds these quadrature points to the internally stored
1285 * QPartitioning. These quadratures can then be obtained using
1286 * the get_quadratures-function.
1287 */
1288 void
1289 generate(const std::vector<std::reference_wrapper<const Function<1>>>
1290 &level_sets,
1291 const BoundingBox<1> &box,
1292 const unsigned int n_box_splits);
1293
1294 /**
1295 * Set which 1d-quadrature in the collection passed to the constructor
1296 * should be used to create the immersed quadratures.
1297 */
1298 void
1299 set_1D_quadrature(const unsigned int q_index);
1300
1301 private:
1302 /**
1303 * Adds the point defined by coordinate to the surface quadrature of
1304 * ImmersedQuadrature with unit weight.
1305 */
1306 void
1307 create_surface_points(
1308 const std::vector<std::reference_wrapper<const Function<1>>>
1309 &level_sets);
1310
1311 /**
1312 * Class used to find the roots of the functions passed to generate().
1313 */
1314 RootFinder root_finder;
1315
1316 /**
1317 * Roots of the functions passed to generate().
1318 */
1319 std::vector<double> roots;
1320
1321 /**
1322 * This would be the height-function direction in higher dimensions,
1323 * but in 1d there is only one coordinate direction.
1324 */
1325 const unsigned int direction = 0;
1326
1327 /**
1328 * To reuse the distribute_points_between_roots()-function
1329 * we need a zero-dimensional quadrature point with unit weight.
1330 */
1331 const Point<0> zero_dim_point;
1332 const double unit_weight = 1;
1333 };
1334
1335
1336 /**
1337 * Take the tensor product between (point, weight) and @p quadrature1d
1338 * scaled over [start, end] and add the resulting dim-dimensional
1339 * quadrature points to @p quadrature.
1340 *
1341 * @p component_in_dim specifies which dim-dimensional coordinate
1342 * quadrature1d should be written to.
1343 */
1344 template <int dim>
1345 void
1346 tensor_point_with_1D_quadrature(const Point<dim - 1> &point,
1347 const double weight,
1348 const Quadrature<1> &quadrature1D,
1349 const double start,
1350 const double end,
1351 const unsigned int component_in_dim,
1352 ExtendableQuadrature<dim> &quadrature);
1353
1354
1355 /**
1356 * Checks the sign of the incoming Functions at the incoming point and
1357 * returns Definiteness::positive/negative if all the functions are
1358 * positive/negative at the point, otherwise returns
1359 * Definiteness::indefinite.
1360 */
1361 template <int dim>
1362 Definiteness
1363 pointwise_definiteness(
1364 const std::vector<std::reference_wrapper<const Function<dim>>>
1365 &functions,
1366 const Point<dim> &point);
1367
1368
1369 /**
1370 * A struct storing the bounds on the function value and bounds
1371 * on each component of the gradient.
1372 */
1373 template <int dim>
1374 struct FunctionBounds
1375 {
1376 public:
1377 /**
1378 * Lower and upper bounds on the functions value.
1379 */
1380 std::pair<double, double> value;
1381
1382 /**
1383 * Lower and upper bounds on each component of the gradient.
1384 */
1385 std::array<std::pair<double, double>, dim> gradient;
1386 };
1387
1388
1389 /**
1390 * Returns the max/min bounds on the value, taken over all the entries
1391 * in the incoming vector of FunctionBounds. That is, given the incoming
1392 * function bounds, $[L_j, U_j]$, this function returns
1393 * $[L, U]$,
1394 * where $L = \min_{j} L_j$ and $U = \max_{j} U_j$.
1395 */
1396 template <int dim>
1397 std::pair<double, double>
1398 find_extreme_values(
1399 const std::vector<FunctionBounds<dim>> &all_function_bounds);
1400
1401
1402 /**
1403 * Finds the best choice of height function direction, given the
1404 * FunctionBounds for a number of functions $\{\psi_j\}_{j=0}^{n-1}$.
1405 * Here, "best" is meant in the sense of the implicit function theorem.
1406 *
1407 * Let $J_I$ be the index set of the indefinite functions:
1408 *
1409 * $J_I = \{0,..., n - 1\} \setminus \{ j : |\psi_j| > 0 \}$.
1410 *
1411 * This function converts the incoming bounds to a lower bound, $L_{ij}$,
1412 * on the absolute value of each component of the gradient:
1413 *
1414 * $|\partial_k \psi_j| > L_{jk}$.
1415 *
1416 * and then returns a coordinate direction, $i$, and a lower bound $L$,
1417 * such that
1418 *
1419 * @f[
1420 * i = \arg \max_{k} \min_{j \in J_I} L_{jk}, \\
1421 * L = \max_{k} \min_{j \in J_I} L_{jk}.
1422 * @f]
1423 *
1424 * This means $i$ is a coordinate direction such that all functions
1425 * intersected by the zero contour (i.e. those belonging to $J_I$) fulfill
1426 *
1427 * $|\partial_i \psi_j| > L$.
1428 *
1429 * Note that the estimated lower bound, $L$, can be zero or negative. This
1430 * means that no suitable height function direction exists. If all of the
1431 * incoming functions are positive or negative definite the returned
1432 * std::optional is non-set.
1433 */
1434 template <int dim>
1435 std::optional<HeightDirectionData>
1436 find_best_height_direction(
1437 const std::vector<FunctionBounds<dim>> &all_function_bounds);
1438
1439 } // namespace QuadratureGeneratorImplementation
1440
1441
1442 namespace DiscreteQuadratureGeneratorImplementation
1443 {
1444 /**
1445 * Interface for a scalar Function which has a
1446 * set_active_cell(..)-function. That is, a function which we in some way
1447 * need to associate with a given cell in order to evaluate.
1448 */
1449 template <int dim>
1450 class CellWiseFunction : public Function<dim>
1451 {
1452 public:
1453 /**
1454 * Destructor. Declared to make it virtual.
1455 */
1456 virtual ~CellWiseFunction() = default;
1457
1458 /**
1459 * Set the cell that the function should be evaluated on.
1460 */
1461 virtual void
1462 set_active_cell(
1463 const typename Triangulation<dim>::active_cell_iterator &cell) = 0;
1464
1465 /**
1466 * Set the dof values and the bounding box of the subcell the
1467 * function should be evaluated on. Relevant for FE_Q_iso_Q1.
1468 */
1469 virtual void
1470 set_subcell(const std::vector<unsigned int> &mask,
1471 const BoundingBox<dim> &subcell_box) = 0;
1472
1473 /**
1474 * Returns flag indicating if the finite element is FE_Q_iso_Q1.
1475 */
1476 virtual bool
1477 is_fe_q_iso_q1() const = 0;
1478
1479 /**
1480 * Number of subdivisions of the FE_Q_iso_Q1 element.
1481 */
1482 virtual unsigned int
1483 n_subdivisions() const = 0;
1484 };
1485
1486 } // namespace DiscreteQuadratureGeneratorImplementation
1487 } // namespace internal
1488
1489 } // namespace NonMatching
1490 DEAL_II_NAMESPACE_CLOSE
1491
1492 #endif /* dealii_non_matching_quadrature_generator_h */