| 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 */ |