| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2023 - 2025 by the deal.II authors |
| 5 |
// |
| 6 |
// This file is part of the deal.II library. |
| 7 |
// |
| 8 |
// Part of the source code is dual licensed under Apache-2.0 WITH |
| 9 |
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information |
| 10 |
// governing the source code and code contributions can be found in |
| 11 |
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. |
| 12 |
// |
| 13 |
// ------------------------------------------------------------------------ |
| 14 |
|
| 15 |
#ifndef dealii_grid_tools_geometry_h |
| 16 |
#define dealii_grid_tools_geometry_h |
| 17 |
|
| 18 |
#include <deal.II/base/config.h> |
| 19 |
|
| 20 |
#include <deal.II/base/bounding_box.h> |
| 21 |
#include <deal.II/base/point.h> |
| 22 |
#include <deal.II/base/template_constraints.h> |
| 23 |
#include <deal.II/base/tensor.h> |
| 24 |
|
| 25 |
#include <deal.II/fe/mapping.h> |
| 26 |
|
| 27 |
#include <deal.II/grid/manifold.h> |
| 28 |
#include <deal.II/grid/tria.h> |
| 29 |
|
| 30 |
#include <algorithm> |
| 31 |
#include <array> |
| 32 |
#include <cmath> |
| 33 |
#include <numeric> |
| 34 |
#include <utility> |
| 35 |
#include <vector> |
| 36 |
|
| 37 |
DEAL_II_NAMESPACE_OPEN |
| 38 |
|
| 39 |
namespace GridTools |
| 40 |
{ |
| 41 |
/** |
| 42 |
* @name Information about meshes and cells |
| 43 |
*/ |
| 44 |
/** @{ */ |
| 45 |
|
| 46 |
/** |
| 47 |
* Return the diameter of a triangulation. The diameter is computed using |
| 48 |
* only the vertices, i.e. if the diameter should be larger than the maximal |
| 49 |
* distance between boundary vertices due to a higher order mapping, then |
| 50 |
* this function will not catch this. |
| 51 |
*/ |
| 52 |
template <int dim, int spacedim> |
| 53 |
double |
| 54 |
diameter(const Triangulation<dim, spacedim> &tria); |
| 55 |
|
| 56 |
/** |
| 57 |
* Compute the volume (i.e. the dim-dimensional measure) of the |
| 58 |
* triangulation. We compute the measure using the integral $\sum_K \int_K 1 |
| 59 |
* \; dx$ where $K$ are the cells of the given triangulation. The integral |
| 60 |
* is approximated via quadrature. This version of the function uses a |
| 61 |
* linear mapping to compute the JxW values on each cell. |
| 62 |
* |
| 63 |
* If the triangulation is a dim-dimensional one embedded in a higher |
| 64 |
* dimensional space of dimension spacedim, then the value returned is the |
| 65 |
* dim-dimensional measure. For example, for a two-dimensional triangulation |
| 66 |
* in three-dimensional space, the value returned is the area of the surface |
| 67 |
* so described. (This obviously makes sense since the spacedim-dimensional |
| 68 |
* measure of a dim-dimensional triangulation would always be zero if dim @< |
| 69 |
* spacedim). |
| 70 |
* |
| 71 |
* This function also works for objects of type |
| 72 |
* parallel::distributed::Triangulation, in which case the function is a |
| 73 |
* @ref GlossCollectiveOperation "collective operation". |
| 74 |
* |
| 75 |
* @param tria The triangulation. |
| 76 |
* @return The dim-dimensional measure of the domain described by the |
| 77 |
* triangulation, as discussed above. |
| 78 |
*/ |
| 79 |
template <int dim, int spacedim> |
| 80 |
double |
| 81 |
volume(const Triangulation<dim, spacedim> &tria); |
| 82 |
|
| 83 |
/** |
| 84 |
* Compute the volume (i.e. the dim-dimensional measure) of the |
| 85 |
* triangulation. We compute the measure using the integral $\sum_K \int_K 1 |
| 86 |
* \; dx$ where $K$ are the cells of the given triangulation. The integral |
| 87 |
* is approximated via quadrature for which we use the mapping argument. |
| 88 |
* |
| 89 |
* If the triangulation is a dim-dimensional one embedded in a higher |
| 90 |
* dimensional space of dimension spacedim, then the value returned is the |
| 91 |
* dim-dimensional measure. For example, for a two-dimensional triangulation |
| 92 |
* in three-dimensional space, the value returned is the area of the surface |
| 93 |
* so described. (This obviously makes sense since the spacedim-dimensional |
| 94 |
* measure of a dim-dimensional triangulation would always be zero if dim @< |
| 95 |
* spacedim. |
| 96 |
* |
| 97 |
* This function also works for objects of type |
| 98 |
* parallel::distributed::Triangulation, in which case the function is a |
| 99 |
* @ref GlossCollectiveOperation "collective operation". |
| 100 |
* |
| 101 |
* @param tria The triangulation. |
| 102 |
* @param mapping The Mapping which computes the Jacobians used to |
| 103 |
* approximate the volume via quadrature. Explicitly using a higher-order |
| 104 |
* Mapping (i.e., instead of using the other version of this function) will |
| 105 |
* result in a more accurate approximation of the volume on Triangulations |
| 106 |
* with curvature described by Manifold objects. |
| 107 |
* @return The dim-dimensional measure of the domain described by the |
| 108 |
* triangulation, as discussed above. |
| 109 |
*/ |
| 110 |
template <int dim, int spacedim> |
| 111 |
double |
| 112 |
volume(const Triangulation<dim, spacedim> &tria, |
| 113 |
const Mapping<dim, spacedim> &mapping); |
| 114 |
|
| 115 |
/** |
| 116 |
* Return an approximation of the diameter of the smallest active cell of a |
| 117 |
* triangulation. See step-24 for an example of use of this function. |
| 118 |
* |
| 119 |
* Notice that, even if you pass a non-trivial mapping, the returned value is |
| 120 |
* computed only using information on the vertices of the triangulation, |
| 121 |
* possibly transformed by the mapping. While this is accurate most of the |
| 122 |
* times, it may fail to give the correct result when the triangulation |
| 123 |
* contains very distorted cells. |
| 124 |
*/ |
| 125 |
template <int dim, int spacedim> |
| 126 |
double |
| 127 |
minimal_cell_diameter( |
| 128 |
const Triangulation<dim, spacedim> &triangulation, |
| 129 |
const Mapping<dim, spacedim> &mapping = |
| 130 |
(ReferenceCells::get_hypercube<dim>() |
| 131 |
#ifndef _MSC_VER |
| 132 |
.template get_default_linear_mapping<dim, spacedim>() |
| 133 |
#else |
| 134 |
.ReferenceCell::get_default_linear_mapping<dim, spacedim>() |
| 135 |
#endif |
| 136 |
)); |
| 137 |
|
| 138 |
/** |
| 139 |
* Return an approximation of the diameter of the largest active cell of a |
| 140 |
* triangulation. |
| 141 |
* |
| 142 |
* Notice that, even if you pass a non-trivial mapping to this function, the |
| 143 |
* returned value is computed only using information on the vertices of the |
| 144 |
* triangulation, possibly transformed by the mapping. While this is accurate |
| 145 |
* most of the times, it may fail to give the correct result when the |
| 146 |
* triangulation contains very distorted cells. |
| 147 |
*/ |
| 148 |
template <int dim, int spacedim> |
| 149 |
double |
| 150 |
maximal_cell_diameter( |
| 151 |
const Triangulation<dim, spacedim> &triangulation, |
| 152 |
const Mapping<dim, spacedim> &mapping = |
| 153 |
(ReferenceCells::get_hypercube<dim>() |
| 154 |
#ifndef _MSC_VER |
| 155 |
.template get_default_linear_mapping<dim, spacedim>() |
| 156 |
#else |
| 157 |
.ReferenceCell::get_default_linear_mapping<dim, spacedim>() |
| 158 |
#endif |
| 159 |
)); |
| 160 |
|
| 161 |
/** |
| 162 |
* Given a list of vertices (typically obtained using |
| 163 |
* Triangulation::get_vertices()) as the first, and a list of vertex indices |
| 164 |
* that characterize a single cell as the second argument, return the |
| 165 |
* measure (area, volume) of this cell. If this is a real cell, then you can |
| 166 |
* get the same result using <code>cell-@>measure()</code>, but this |
| 167 |
* function also works for cells that do not exist except that you make it |
| 168 |
* up by naming its vertices from the list. |
| 169 |
* |
| 170 |
* The size of @p vertex_indices, combined with `dim`, implicitly encodes |
| 171 |
* the ReferenceCell type of the provided cell. For example, if `dim == 2` and |
| 172 |
* `vertex_indices.size() == 3` then the cell is a triangle, but if |
| 173 |
* `dim == 2` and `vertex_indices.size() == 4` then the cell is a |
| 174 |
* quadrilateral. A std::vector is implicitly convertible to an ArrayView, so |
| 175 |
* it can be passed directly to this function. See the ArrayView class for |
| 176 |
* more information. |
| 177 |
* |
| 178 |
* @note This function is only implemented for codimension zero objects. |
| 179 |
*/ |
| 180 |
template <int dim> |
| 181 |
double |
| 182 |
cell_measure(const std::vector<Point<dim>> &all_vertices, |
| 183 |
const ArrayView<const unsigned int> &vertex_indices); |
| 184 |
|
| 185 |
/** |
| 186 |
* Return the highest value among ratios between extents in each of the |
| 187 |
* coordinate directions of a @p cell. Moreover, return the dimension |
| 188 |
* relative to the highest elongation. |
| 189 |
* |
| 190 |
* @param[in] cell an iterator pointing to the cell. |
| 191 |
* |
| 192 |
* @return A std::pair<unsigned int, double> such that the @p first value |
| 193 |
* is the dimension of the highest elongation and the @p second value is the |
| 194 |
* ratio among the dimensions of the @p cell. |
| 195 |
*/ |
| 196 |
template <int dim, int spacedim> |
| 197 |
std::pair<unsigned int, double> |
| 198 |
get_longest_direction( |
| 199 |
typename Triangulation<dim, spacedim>::active_cell_iterator cell); |
| 200 |
|
| 201 |
/** |
| 202 |
* This function computes an affine approximation of the map from the unit |
| 203 |
* coordinates to the real coordinates of the form $p_\text{real} = A |
| 204 |
* p_\text{unit} + b $ by a least squares fit of this affine function to the |
| 205 |
* $2^\text{dim}$ vertices representing a quadrilateral or hexahedral cell |
| 206 |
* in `spacedim` dimensions. The result is returned as a pair with the |
| 207 |
* matrix <i>A</i> as the first argument and the vector <i>b</i> describing |
| 208 |
* distance of the plane to the origin. |
| 209 |
* |
| 210 |
* For any valid mesh cell whose geometry is not degenerate, this operation |
| 211 |
* results in a unique affine mapping, even in cases where the actual |
| 212 |
* transformation by a bi-/trilinear or higher order mapping might be |
| 213 |
* singular. The result is exact in case the transformation from the unit to |
| 214 |
* the real cell is indeed affine, such as in one dimension or for Cartesian |
| 215 |
* and affine (parallelogram) meshes in 2d/3d. |
| 216 |
* |
| 217 |
* This approximation is underlying the function |
| 218 |
* TriaAccessor::real_to_unit_cell_affine_approximation() function. |
| 219 |
* |
| 220 |
* For exact transformations to the unit cell, use |
| 221 |
* Mapping::transform_real_to_unit_cell(). |
| 222 |
*/ |
| 223 |
template <int dim, int spacedim> |
| 224 |
std::pair<DerivativeForm<1, dim, spacedim>, Tensor<1, spacedim>> |
| 225 |
affine_cell_approximation(const ArrayView<const Point<spacedim>> &vertices); |
| 226 |
|
| 227 |
/** |
| 228 |
* Computes an aspect ratio measure for all locally-owned active cells and |
| 229 |
* fills a vector with one entry per cell, given a @p triangulation and |
| 230 |
* @p mapping. The size of the vector that is returned equals the number of |
| 231 |
* active cells. The vector contains zero for non locally-owned cells. The |
| 232 |
* aspect ratio of a cell is defined as the ratio of the maximum to minimum |
| 233 |
* singular value of the Jacobian, taking the maximum over all quadrature |
| 234 |
* points of a quadrature rule specified via @p quadrature. For example, for |
| 235 |
* the special case of rectangular elements in 2d with dimensions $a$ and $b$ |
| 236 |
* ($a \geq b$), this function returns the usual aspect ratio definition |
| 237 |
* $a/b$. The above definition using singular values is a generalization to |
| 238 |
* arbitrarily deformed elements. This function is intended to be used for |
| 239 |
* $d=2,3$ space dimensions, but it can also be used for $d=1$ returning a |
| 240 |
* value of 1. |
| 241 |
* |
| 242 |
* @note Inverted elements do not throw an exception. Instead, a value of inf |
| 243 |
* is written into the vector in case of inverted elements. |
| 244 |
* |
| 245 |
* @note Make sure to use enough quadrature points for a precise calculation |
| 246 |
* of the aspect ratio in case of deformed elements. |
| 247 |
* |
| 248 |
* @note In parallel computations the return value will have the length |
| 249 |
* n_active_cells but the aspect ratio is only computed for the cells that |
| 250 |
* are locally owned and placed at index CellAccessor::active_cell_index(), |
| 251 |
* respectively. All other values are set to 0. |
| 252 |
* |
| 253 |
* @note This function can only be used if deal.II was configured with |
| 254 |
* support for LAPACK. |
| 255 |
*/ |
| 256 |
template <int dim> |
| 257 |
Vector<double> |
| 258 |
compute_aspect_ratio_of_cells(const Mapping<dim> &mapping, |
| 259 |
const Triangulation<dim> &triangulation, |
| 260 |
const Quadrature<dim> &quadrature); |
| 261 |
|
| 262 |
/** |
| 263 |
* Computes the maximum aspect ratio by taking the maximum over all cells. |
| 264 |
* |
| 265 |
* @note When running in parallel with a Triangulation that supports MPI, |
| 266 |
* this is a collective call and the return value is the maximum over all |
| 267 |
* processors. |
| 268 |
*/ |
| 269 |
template <int dim> |
| 270 |
double |
| 271 |
compute_maximum_aspect_ratio(const Mapping<dim> &mapping, |
| 272 |
const Triangulation<dim> &triangulation, |
| 273 |
const Quadrature<dim> &quadrature); |
| 274 |
|
| 275 |
/** |
| 276 |
* Compute the smallest box containing the entire triangulation. |
| 277 |
* |
| 278 |
* If the input triangulation is a `parallel::distributed::Triangulation`, |
| 279 |
* then each processor will compute a bounding box enclosing all locally |
| 280 |
* owned, ghost, and artificial cells. In the case of a domain without curved |
| 281 |
* boundaries, these bounding boxes will all agree between processors because |
| 282 |
* the union of the areas occupied by artificial and ghost cells equals the |
| 283 |
* union of the areas occupied by the cells that other processors own. |
| 284 |
* However, if the domain has curved boundaries, this is no longer the case. |
| 285 |
* The bounding box returned may be appropriate for the current processor, |
| 286 |
* but different from the bounding boxes computed on other processors. |
| 287 |
*/ |
| 288 |
template <int dim, int spacedim> |
| 289 |
BoundingBox<spacedim> |
| 290 |
compute_bounding_box(const Triangulation<dim, spacedim> &triangulation); |
| 291 |
|
| 292 |
/** |
| 293 |
* Compute and return a bounding box, defined through a pair of points |
| 294 |
* bottom left and top right, that surrounds a subdomain of the @p mesh. |
| 295 |
* Here, the "subdomain" consists of exactly all of those |
| 296 |
* active cells for which the @p predicate returns @p true. |
| 297 |
* |
| 298 |
* For a description of how @p predicate works, |
| 299 |
* see compute_active_cell_halo_layer(). |
| 300 |
* |
| 301 |
* @note This function was written before the BoundingBox class was invented. |
| 302 |
* Consequently, it returns a pair of points, rather than a BoundingBox |
| 303 |
* object as one may expect. However, BoundingBox has a conversion constructor |
| 304 |
* from pairs of points, so the result of this function can still be assigned |
| 305 |
* to a BoundingBox object. |
| 306 |
* |
| 307 |
* @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>} |
| 308 |
*/ |
| 309 |
template <typename MeshType> |
| 310 |
DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>) |
| 311 |
std::pair< |
| 312 |
Point<MeshType::space_dimension>, |
| 313 |
Point<MeshType:: |
| 314 |
space_dimension>> compute_bounding_box(const MeshType &mesh, |
| 315 |
const std::function<bool( |
| 316 |
const typename MeshType:: |
| 317 |
active_cell_iterator &)> |
| 318 |
&predicate); |
| 319 |
|
| 320 |
/** |
| 321 |
* Return the point on the geometrical object @p object closest to the given |
| 322 |
* point @p trial_point. For example, if @p object is a one-dimensional line |
| 323 |
* or edge, then the returned point will be a point on the geodesic that |
| 324 |
* connects the vertices as the manifold associated with the object sees it |
| 325 |
* (i.e., the geometric line may be curved if it lives in a higher |
| 326 |
* dimensional space). If the iterator points to a quadrilateral in a higher |
| 327 |
* dimensional space, then the returned point lies within the convex hull of |
| 328 |
* the vertices of the quad as seen by the associated manifold. |
| 329 |
* |
| 330 |
* @note This projection is usually not well-posed since there may be |
| 331 |
* multiple points on the object that minimize the distance. The algorithm |
| 332 |
* used in this function is robust (and the output is guaranteed to be on |
| 333 |
* the given @p object) but may only provide a few correct digits if the |
| 334 |
* object has high curvature. If your manifold supports it then the |
| 335 |
* specialized function Manifold::project_to_manifold() may perform better. |
| 336 |
*/ |
| 337 |
template <typename Iterator> |
| 338 |
Point<Iterator::AccessorType::space_dimension> |
| 339 |
project_to_object( |
| 340 |
const Iterator &object, |
| 341 |
const Point<Iterator::AccessorType::space_dimension> &trial_point); |
| 342 |
/** @} */ |
| 343 |
} // namespace GridTools |
| 344 |
|
| 345 |
#ifndef DOXYGEN |
| 346 |
namespace GridTools |
| 347 |
{ |
| 348 |
namespace internal |
| 349 |
{ |
| 350 |
namespace ProjectToObject |
| 351 |
{ |
| 352 |
/** |
| 353 |
* The method GridTools::project_to_object requires taking derivatives |
| 354 |
* along the surface of a simplex. In general these cannot be |
| 355 |
* approximated with finite differences but special differences of the |
| 356 |
* form |
| 357 |
* |
| 358 |
* df/dx_i - df/dx_j |
| 359 |
* |
| 360 |
* <em>can</em> be approximated. This <code>struct</code> just stores |
| 361 |
* the two derivatives approximated by the stencil (in the case of the |
| 362 |
* example above <code>i</code> and <code>j</code>). |
| 363 |
*/ |
| 364 |
struct CrossDerivative |
| 365 |
{ |
| 366 |
const unsigned int direction_0; |
| 367 |
const unsigned int direction_1; |
| 368 |
|
| 369 |
CrossDerivative(const unsigned int d0, const unsigned int d1); |
| 370 |
}; |
| 371 |
|
| 372 |
inline CrossDerivative::CrossDerivative(const unsigned int d0, |
| 373 |
const unsigned int d1) |
| 374 |
: direction_0(d0) |
| 375 |
, direction_1(d1) |
| 376 |
{} |
| 377 |
|
| 378 |
|
| 379 |
|
| 380 |
/** |
| 381 |
* Standard second-order approximation to the first derivative with a |
| 382 |
* two-point centered scheme. This is used below in a 1d Newton method. |
| 383 |
*/ |
| 384 |
template <typename F> |
| 385 |
inline auto |
| 386 |
centered_first_difference(const double center, |
| 387 |
const double step, |
| 388 |
const F &f) -> decltype(f(center) - f(center)) |
| 389 |
{ |
| 390 |
return (f(center + step) - f(center - step)) / (2.0 * step); |
| 391 |
} |
| 392 |
|
| 393 |
|
| 394 |
|
| 395 |
/** |
| 396 |
* Standard second-order approximation to the second derivative with a |
| 397 |
* three-point centered scheme. This is used below in a 1d Newton method. |
| 398 |
*/ |
| 399 |
template <typename F> |
| 400 |
inline auto |
| 401 |
centered_second_difference(const double center, |
| 402 |
const double step, |
| 403 |
const F &f) -> decltype(f(center) - f(center)) |
| 404 |
{ |
| 405 |
return (f(center + step) - 2.0 * f(center) + f(center - step)) / |
| 406 |
(step * step); |
| 407 |
} |
| 408 |
|
| 409 |
|
| 410 |
|
| 411 |
/** |
| 412 |
* Fourth order approximation of the derivative |
| 413 |
* |
| 414 |
* df/dx_i - df/dx_j |
| 415 |
* |
| 416 |
* where <code>i</code> and <code>j</code> are specified by @p |
| 417 |
* cross_derivative. The derivative approximation is at @p center with a |
| 418 |
* step size of @p step and function @p f. |
| 419 |
*/ |
| 420 |
template <int structdim, typename F> |
| 421 |
inline auto |
| 422 |
cross_stencil( |
| 423 |
const CrossDerivative cross_derivative, |
| 424 |
const Tensor<1, GeometryInfo<structdim>::vertices_per_cell> ¢er, |
| 425 |
const double step, |
| 426 |
const F &f) -> decltype(f(center) - f(center)) |
| 427 |
{ |
| 428 |
Tensor<1, GeometryInfo<structdim>::vertices_per_cell> simplex_vector; |
| 429 |
simplex_vector[cross_derivative.direction_0] = 0.5 * step; |
| 430 |
simplex_vector[cross_derivative.direction_1] = -0.5 * step; |
| 431 |
return (-4.0 * f(center) - 1.0 * f(center + simplex_vector) - |
| 432 |
1.0 / 3.0 * f(center - simplex_vector) + |
| 433 |
16.0 / 3.0 * f(center + 0.5 * simplex_vector)) / |
| 434 |
step; |
| 435 |
} |
| 436 |
|
| 437 |
|
| 438 |
|
| 439 |
/** |
| 440 |
* The optimization algorithm used in GridTools::project_to_object is |
| 441 |
* essentially a gradient descent method. This function computes entries |
| 442 |
* in the gradient of the objective function; see the description in the |
| 443 |
* comments inside GridTools::project_to_object for more information. |
| 444 |
*/ |
| 445 |
template <int spacedim, int structdim, typename F> |
| 446 |
inline double |
| 447 |
gradient_entry( |
| 448 |
const unsigned int row_n, |
| 449 |
const unsigned int dependent_direction, |
| 450 |
const Point<spacedim> &p0, |
| 451 |
const Tensor<1, GeometryInfo<structdim>::vertices_per_cell> ¢er, |
| 452 |
const double step, |
| 453 |
const F &f) |
| 454 |
{ |
| 455 |
Assert(row_n < GeometryInfo<structdim>::vertices_per_cell && |
| 456 |
dependent_direction < |
| 457 |
GeometryInfo<structdim>::vertices_per_cell, |
| 458 |
ExcMessage("This function assumes that the last weight is a " |
| 459 |
"dependent variable (and hence we cannot take its " |
| 460 |
"derivative directly).")); |
| 461 |
Assert(row_n != dependent_direction, |
| 462 |
ExcMessage( |
| 463 |
"We cannot differentiate with respect to the variable " |
| 464 |
"that is assumed to be dependent.")); |
| 465 |
|
| 466 |
const Point<spacedim> manifold_point = f(center); |
| 467 |
const Tensor<1, spacedim> stencil_value = cross_stencil<structdim>( |
| 468 |
{row_n, dependent_direction}, center, step, f); |
| 469 |
double entry = 0.0; |
| 470 |
for (unsigned int dim_n = 0; dim_n < spacedim; ++dim_n) |
| 471 |
entry += |
| 472 |
-2.0 * (p0[dim_n] - manifold_point[dim_n]) * stencil_value[dim_n]; |
| 473 |
return entry; |
| 474 |
} |
| 475 |
|
| 476 |
/** |
| 477 |
* Project onto a d-linear object. This is more accurate than the |
| 478 |
* general algorithm in project_to_object but only works for geometries |
| 479 |
* described by linear, bilinear, or trilinear mappings. |
| 480 |
*/ |
| 481 |
template <typename Iterator, int spacedim, int structdim> |
| 482 |
Point<spacedim> |
| 483 |
project_to_d_linear_object(const Iterator &object, |
| 484 |
const Point<spacedim> &trial_point) |
| 485 |
{ |
| 486 |
// let's look at this for simplicity for a quadrilateral |
| 487 |
// (structdim==2) in a space with spacedim>2 (notate trial_point by |
| 488 |
// y): all points on the surface are given by |
| 489 |
// x(\xi) = sum_i v_i phi_x(\xi) |
| 490 |
// where v_i are the vertices of the quadrilateral, and |
| 491 |
// \xi=(\xi_1,\xi_2) are the reference coordinates of the |
| 492 |
// quadrilateral. so what we are trying to do is find a point x on the |
| 493 |
// surface that is closest to the point y. there are different ways to |
| 494 |
// solve this problem, but in the end it's a nonlinear problem and we |
| 495 |
// have to find reference coordinates \xi so that J(\xi) = 1/2 || |
| 496 |
// x(\xi)-y ||^2 is minimal. x(\xi) is a function that is |
| 497 |
// structdim-linear in \xi, so J(\xi) is a polynomial of degree |
| 498 |
// 2*structdim that we'd like to minimize. unless structdim==1, we'll |
| 499 |
// have to use a Newton method to find the answer. This leads to the |
| 500 |
// following formulation of Newton steps: |
| 501 |
// |
| 502 |
// Given \xi_k, find \delta\xi_k so that |
| 503 |
// H_k \delta\xi_k = - F_k |
| 504 |
// where H_k is an approximation to the second derivatives of J at |
| 505 |
// \xi_k, and F_k is the first derivative of J. We'll iterate this a |
| 506 |
// number of times until the right hand side is small enough. As a |
| 507 |
// stopping criterion, we terminate if ||\delta\xi||<eps. |
| 508 |
// |
| 509 |
// As for the Hessian, the best choice would be |
| 510 |
// H_k = J''(\xi_k) |
| 511 |
// but we'll opt for the simpler Gauss-Newton form |
| 512 |
// H_k = A^T A |
| 513 |
// i.e. |
| 514 |
// (H_k)_{nm} = \sum_{i,j} v_i*v_j * |
| 515 |
// \partial_n phi_i * |
| 516 |
// \partial_m phi_j |
| 517 |
// we start at xi=(0.5, 0.5). |
| 518 |
Point<structdim> xi; |
| 519 |
for (unsigned int d = 0; d < structdim; ++d) |
| 520 |
xi[d] = 0.5; |
| 521 |
|
| 522 |
Point<spacedim> x_k; |
| 523 |
for (const unsigned int i : GeometryInfo<structdim>::vertex_indices()) |
| 524 |
x_k += object->vertex(i) * |
| 525 |
GeometryInfo<structdim>::d_linear_shape_function(xi, i); |
| 526 |
|
| 527 |
do |
| 528 |
{ |
| 529 |
Tensor<1, structdim> F_k; |
| 530 |
for (const unsigned int i : |
| 531 |
GeometryInfo<structdim>::vertex_indices()) |
| 532 |
F_k += |
| 533 |
(x_k - trial_point) * object->vertex(i) * |
| 534 |
GeometryInfo<structdim>::d_linear_shape_function_gradient(xi, |
| 535 |
i); |
| 536 |
|
| 537 |
Tensor<2, structdim> H_k; |
| 538 |
for (const unsigned int i : |
| 539 |
GeometryInfo<structdim>::vertex_indices()) |
| 540 |
for (const unsigned int j : |
| 541 |
GeometryInfo<structdim>::vertex_indices()) |
| 542 |
{ |
| 543 |
Tensor<2, structdim> tmp = outer_product( |
| 544 |
GeometryInfo<structdim>::d_linear_shape_function_gradient( |
| 545 |
xi, i), |
| 546 |
GeometryInfo<structdim>::d_linear_shape_function_gradient( |
| 547 |
xi, j)); |
| 548 |
H_k += (object->vertex(i) * object->vertex(j)) * tmp; |
| 549 |
} |
| 550 |
|
| 551 |
const Tensor<1, structdim> delta_xi = -invert(H_k) * F_k; |
| 552 |
xi += delta_xi; |
| 553 |
|
| 554 |
x_k = Point<spacedim>(); |
| 555 |
for (const unsigned int i : |
| 556 |
GeometryInfo<structdim>::vertex_indices()) |
| 557 |
x_k += object->vertex(i) * |
| 558 |
GeometryInfo<structdim>::d_linear_shape_function(xi, i); |
| 559 |
|
| 560 |
if (delta_xi.norm() < 1e-7) |
| 561 |
break; |
| 562 |
} |
| 563 |
while (true); |
| 564 |
|
| 565 |
return x_k; |
| 566 |
} |
| 567 |
} // namespace ProjectToObject |
| 568 |
|
| 569 |
// We hit an internal compiler error in ICC 15 if we define this as a lambda |
| 570 |
// inside the project_to_object function below. |
| 571 |
template <int structdim> |
| 572 |
inline bool |
| 573 |
weights_are_ok( |
| 574 |
const Tensor<1, GeometryInfo<structdim>::vertices_per_cell> &v) |
| 575 |
{ |
| 576 |
// clang has trouble figuring out structdim here, so define it |
| 577 |
// again: |
| 578 |
static const std::size_t n_vertices_per_cell = |
| 579 |
Tensor<1, GeometryInfo<structdim>::vertices_per_cell>:: |
| 580 |
n_independent_components; |
| 581 |
std::array<double, n_vertices_per_cell> copied_weights; |
| 582 |
for (unsigned int i = 0; i < n_vertices_per_cell; ++i) |
| 583 |
{ |
| 584 |
copied_weights[i] = v[i]; |
| 585 |
if (v[i] < 0.0 || v[i] > 1.0) |
| 586 |
return false; |
| 587 |
} |
| 588 |
|
| 589 |
// check the sum: try to avoid some roundoff errors by summing in order |
| 590 |
std::sort(copied_weights.begin(), copied_weights.end()); |
| 591 |
const double sum = |
| 592 |
std::accumulate(copied_weights.begin(), copied_weights.end(), 0.0); |
| 593 |
return std::abs(sum - 1.0) < 1e-10; // same tolerance used in manifold.cc |
| 594 |
} |
| 595 |
} // namespace internal |
| 596 |
|
| 597 |
|
| 598 |
|
| 599 |
template <typename Iterator> |
| 600 |
Point<Iterator::AccessorType::space_dimension> |
| 601 |
project_to_object( |
| 602 |
const Iterator &object, |
| 603 |
const Point<Iterator::AccessorType::space_dimension> &trial_point) |
| 604 |
{ |
| 605 |
const int spacedim = Iterator::AccessorType::space_dimension; |
| 606 |
const int structdim = Iterator::AccessorType::structure_dimension; |
| 607 |
|
| 608 |
Point<spacedim> projected_point = trial_point; |
| 609 |
|
| 610 |
if (structdim >= spacedim) |
| 611 |
return projected_point; |
| 612 |
else if (structdim == 1 || structdim == 2) |
| 613 |
{ |
| 614 |
using namespace internal::ProjectToObject; |
| 615 |
// Try to use the special flat algorithm for quads (this is better |
| 616 |
// than the general algorithm in 3d). This does not take into account |
| 617 |
// whether projected_point is outside the quad, but we optimize along |
| 618 |
// lines below anyway: |
| 619 |
const int dim = Iterator::AccessorType::dimension; |
| 620 |
const Manifold<dim, spacedim> &manifold = object->get_manifold(); |
| 621 |
if (structdim == 2 && dynamic_cast<const FlatManifold<dim, spacedim> *>( |
| 622 |
&manifold) != nullptr) |
| 623 |
{ |
| 624 |
projected_point = |
| 625 |
project_to_d_linear_object<Iterator, spacedim, structdim>( |
| 626 |
object, trial_point); |
| 627 |
} |
| 628 |
else |
| 629 |
{ |
| 630 |
// We want to find a point on the convex hull (defined by the |
| 631 |
// vertices of the object and the manifold description) that is |
| 632 |
// relatively close to the trial point. This has a few issues: |
| 633 |
// |
| 634 |
// 1. For a general convex hull we are not guaranteed that a unique |
| 635 |
// minimum exists. |
| 636 |
// 2. The independent variables in the optimization process are the |
| 637 |
// weights given to Manifold::get_new_point, which must sum to 1, |
| 638 |
// so we cannot use standard finite differences to approximate a |
| 639 |
// gradient. |
| 640 |
// |
| 641 |
// There is not much we can do about 1., but for 2. we can derive |
| 642 |
// finite difference stencils that work on a structdim-dimensional |
| 643 |
// simplex and rewrite the optimization problem to use those |
| 644 |
// instead. Consider the structdim 2 case and let |
| 645 |
// |
| 646 |
// F(c0, c1, c2, c3) = Manifold::get_new_point(vertices, {c0, c1, |
| 647 |
// c2, c3}) |
| 648 |
// |
| 649 |
// where {c0, c1, c2, c3} are the weights for the four vertices on |
| 650 |
// the quadrilateral. We seek to minimize the Euclidean distance |
| 651 |
// between F(...) and trial_point. We can solve for c3 in terms of |
| 652 |
// the other weights and get, for one coordinate direction |
| 653 |
// |
| 654 |
// d/dc0 ((x0 - F(c0, c1, c2, 1 - c0 - c1 - c2))^2) |
| 655 |
// = -2(x0 - F(...)) (d/dc0 F(...) - d/dc3 F(...)) |
| 656 |
// |
| 657 |
// where we substitute back in for c3 after taking the |
| 658 |
// derivative. We can compute a stencil for the cross derivative |
| 659 |
// d/dc0 - d/dc3: this is exactly what cross_stencil approximates |
| 660 |
// (and gradient_entry computes the sum over the independent |
| 661 |
// variables). Below, we somewhat arbitrarily pick the last |
| 662 |
// component as the dependent one. |
| 663 |
// |
| 664 |
// Since we can now calculate derivatives of the objective |
| 665 |
// function we can use gradient descent to minimize it. |
| 666 |
// |
| 667 |
// Of course, this is much simpler in the structdim = 1 case (we |
| 668 |
// could rewrite the projection as a 1d optimization problem), but |
| 669 |
// to reduce the potential for bugs we use the same code in both |
| 670 |
// cases. |
| 671 |
const double step_size = object->diameter() / 64.0; |
| 672 |
|
| 673 |
constexpr unsigned int n_vertices_per_cell = |
| 674 |
GeometryInfo<structdim>::vertices_per_cell; |
| 675 |
|
| 676 |
std::array<Point<spacedim>, n_vertices_per_cell> vertices; |
| 677 |
for (unsigned int vertex_n = 0; vertex_n < n_vertices_per_cell; |
| 678 |
++vertex_n) |
| 679 |
vertices[vertex_n] = object->vertex(vertex_n); |
| 680 |
|
| 681 |
auto get_point_from_weights = |
| 682 |
[&](const Tensor<1, n_vertices_per_cell> &weights) |
| 683 |
-> Point<spacedim> { |
| 684 |
return object->get_manifold().get_new_point( |
| 685 |
make_array_view(vertices.begin(), vertices.end()), |
| 686 |
make_array_view(weights.begin_raw(), weights.end_raw())); |
| 687 |
}; |
| 688 |
|
| 689 |
// pick the initial weights as (normalized) inverse distances from |
| 690 |
// the trial point: |
| 691 |
Tensor<1, n_vertices_per_cell> guess_weights; |
| 692 |
double guess_weights_sum = 0.0; |
| 693 |
for (unsigned int vertex_n = 0; vertex_n < n_vertices_per_cell; |
| 694 |
++vertex_n) |
| 695 |
{ |
| 696 |
const double distance = |
| 697 |
vertices[vertex_n].distance(trial_point); |
| 698 |
if (distance == 0.0) |
| 699 |
{ |
| 700 |
guess_weights = 0.0; |
| 701 |
guess_weights[vertex_n] = 1.0; |
| 702 |
guess_weights_sum = 1.0; |
| 703 |
break; |
| 704 |
} |
| 705 |
else |
| 706 |
{ |
| 707 |
guess_weights[vertex_n] = 1.0 / distance; |
| 708 |
guess_weights_sum += guess_weights[vertex_n]; |
| 709 |
} |
| 710 |
} |
| 711 |
guess_weights /= guess_weights_sum; |
| 712 |
Assert(internal::weights_are_ok<structdim>(guess_weights), |
| 713 |
ExcInternalError()); |
| 714 |
|
| 715 |
// The optimization algorithm consists of two parts: |
| 716 |
// |
| 717 |
// 1. An outer loop where we apply the gradient descent algorithm. |
| 718 |
// 2. An inner loop where we do a line search to find the optimal |
| 719 |
// length of the step one should take in the gradient direction. |
| 720 |
// |
| 721 |
for (unsigned int outer_n = 0; outer_n < 40; ++outer_n) |
| 722 |
{ |
| 723 |
const unsigned int dependent_direction = |
| 724 |
n_vertices_per_cell - 1; |
| 725 |
Tensor<1, n_vertices_per_cell> current_gradient; |
| 726 |
for (unsigned int row_n = 0; row_n < n_vertices_per_cell; |
| 727 |
++row_n) |
| 728 |
{ |
| 729 |
if (row_n != dependent_direction) |
| 730 |
{ |
| 731 |
current_gradient[row_n] = |
| 732 |
gradient_entry<spacedim, structdim>( |
| 733 |
row_n, |
| 734 |
dependent_direction, |
| 735 |
trial_point, |
| 736 |
guess_weights, |
| 737 |
step_size, |
| 738 |
get_point_from_weights); |
| 739 |
|
| 740 |
current_gradient[dependent_direction] -= |
| 741 |
current_gradient[row_n]; |
| 742 |
} |
| 743 |
} |
| 744 |
|
| 745 |
// We need to travel in the -gradient direction, as noted |
| 746 |
// above, but we may not want to take a full step in that |
| 747 |
// direction; instead, guess that we will go -0.5*gradient and |
| 748 |
// do quasi-Newton iteration to pick the best multiplier. The |
| 749 |
// goal is to find a scalar alpha such that |
| 750 |
// |
| 751 |
// F(x - alpha g) |
| 752 |
// |
| 753 |
// is minimized, where g is the gradient and F is the |
| 754 |
// objective function. To find the optimal value we find roots |
| 755 |
// of the derivative of the objective function with respect to |
| 756 |
// alpha by Newton iteration, where we approximate the first |
| 757 |
// and second derivatives of F(x - alpha g) with centered |
| 758 |
// finite differences. |
| 759 |
double gradient_weight = -0.5; |
| 760 |
auto gradient_weight_objective_function = |
| 761 |
[&](const double gradient_weight_guess) -> double { |
| 762 |
return (trial_point - |
| 763 |
get_point_from_weights(guess_weights + |
| 764 |
gradient_weight_guess * |
| 765 |
current_gradient)) |
| 766 |
.norm_square(); |
| 767 |
}; |
| 768 |
|
| 769 |
for (unsigned int inner_n = 0; inner_n < 10; ++inner_n) |
| 770 |
{ |
| 771 |
const double update_numerator = centered_first_difference( |
| 772 |
gradient_weight, |
| 773 |
step_size, |
| 774 |
gradient_weight_objective_function); |
| 775 |
const double update_denominator = |
| 776 |
centered_second_difference( |
| 777 |
gradient_weight, |
| 778 |
step_size, |
| 779 |
gradient_weight_objective_function); |
| 780 |
|
| 781 |
// avoid division by zero. Note that we limit the gradient |
| 782 |
// weight below |
| 783 |
if (std::abs(update_denominator) == 0.0) |
| 784 |
break; |
| 785 |
gradient_weight = |
| 786 |
gradient_weight - update_numerator / update_denominator; |
| 787 |
|
| 788 |
// Put a fairly lenient bound on the largest possible |
| 789 |
// gradient (things tend to be locally flat, so the gradient |
| 790 |
// itself is usually small) |
| 791 |
if (std::abs(gradient_weight) > 10) |
| 792 |
{ |
| 793 |
gradient_weight = -10.0; |
| 794 |
break; |
| 795 |
} |
| 796 |
} |
| 797 |
|
| 798 |
// It only makes sense to take convex combinations with weights |
| 799 |
// between zero and one. If the update takes us outside of this |
| 800 |
// region then rescale the update to stay within the region and |
| 801 |
// try again |
| 802 |
Tensor<1, n_vertices_per_cell> tentative_weights = |
| 803 |
guess_weights + gradient_weight * current_gradient; |
| 804 |
|
| 805 |
double new_gradient_weight = gradient_weight; |
| 806 |
for (unsigned int iteration_count = 0; iteration_count < 40; |
| 807 |
++iteration_count) |
| 808 |
{ |
| 809 |
if (internal::weights_are_ok<structdim>(tentative_weights)) |
| 810 |
break; |
| 811 |
|
| 812 |
for (unsigned int i = 0; i < n_vertices_per_cell; ++i) |
| 813 |
{ |
| 814 |
if (tentative_weights[i] < 0.0) |
| 815 |
{ |
| 816 |
tentative_weights -= |
| 817 |
(tentative_weights[i] / current_gradient[i]) * |
| 818 |
current_gradient; |
| 819 |
} |
| 820 |
if (tentative_weights[i] < 0.0 || |
| 821 |
1.0 < tentative_weights[i]) |
| 822 |
{ |
| 823 |
new_gradient_weight /= 2.0; |
| 824 |
tentative_weights = |
| 825 |
guess_weights + |
| 826 |
new_gradient_weight * current_gradient; |
| 827 |
} |
| 828 |
} |
| 829 |
} |
| 830 |
|
| 831 |
// the update might still send us outside the valid region, so |
| 832 |
// check again and quit if the update is still not valid |
| 833 |
if (!internal::weights_are_ok<structdim>(tentative_weights)) |
| 834 |
break; |
| 835 |
|
| 836 |
// if we cannot get closer by traveling in the gradient |
| 837 |
// direction then quit |
| 838 |
if (get_point_from_weights(tentative_weights) |
| 839 |
.distance(trial_point) < |
| 840 |
get_point_from_weights(guess_weights).distance(trial_point)) |
| 841 |
guess_weights = tentative_weights; |
| 842 |
else |
| 843 |
break; |
| 844 |
Assert(internal::weights_are_ok<structdim>(guess_weights), |
| 845 |
ExcInternalError()); |
| 846 |
} |
| 847 |
Assert(internal::weights_are_ok<structdim>(guess_weights), |
| 848 |
ExcInternalError()); |
| 849 |
projected_point = get_point_from_weights(guess_weights); |
| 850 |
} |
| 851 |
|
| 852 |
// if structdim == 2 and the optimal point is not on the interior then |
| 853 |
// we may be able to get a more accurate result by projecting onto the |
| 854 |
// lines. |
| 855 |
if (structdim == 2) |
| 856 |
{ |
| 857 |
std::array<Point<spacedim>, GeometryInfo<structdim>::lines_per_cell> |
| 858 |
line_projections; |
| 859 |
for (unsigned int line_n = 0; |
| 860 |
line_n < GeometryInfo<structdim>::lines_per_cell; |
| 861 |
++line_n) |
| 862 |
{ |
| 863 |
line_projections[line_n] = |
| 864 |
project_to_object(object->line(line_n), trial_point); |
| 865 |
} |
| 866 |
std::sort(line_projections.begin(), |
| 867 |
line_projections.end(), |
| 868 |
[&](const Point<spacedim> &a, const Point<spacedim> &b) { |
| 869 |
return a.distance(trial_point) < |
| 870 |
b.distance(trial_point); |
| 871 |
}); |
| 872 |
if (line_projections[0].distance(trial_point) < |
| 873 |
projected_point.distance(trial_point)) |
| 874 |
projected_point = line_projections[0]; |
| 875 |
} |
| 876 |
} |
| 877 |
else |
| 878 |
{ |
| 879 |
DEAL_II_NOT_IMPLEMENTED(); |
| 880 |
return projected_point; |
| 881 |
} |
| 882 |
|
| 883 |
return projected_point; |
| 884 |
} |
| 885 |
} // namespace GridTools |
| 886 |
#endif // DOXYGEN |
| 887 |
|
| 888 |
DEAL_II_NAMESPACE_CLOSE |
| 889 |
|
| 890 |
#endif |