| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2022 - 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_cgal_utilities_h |
| 16 |
#define dealii_cgal_utilities_h |
| 17 |
|
| 18 |
#include <deal.II/base/config.h> |
| 19 |
|
| 20 |
#include <deal.II/base/exceptions.h> |
| 21 |
|
| 22 |
#include <deal.II/cgal/additional_data.h> |
| 23 |
|
| 24 |
#ifdef DEAL_II_WITH_CGAL |
| 25 |
# include <deal.II/base/quadrature_lib.h> |
| 26 |
|
| 27 |
# include <deal.II/cgal/surface_mesh.h> |
| 28 |
|
| 29 |
# include <deal.II/grid/tria.h> |
| 30 |
|
| 31 |
# include <boost/hana.hpp> |
| 32 |
|
| 33 |
# include <CGAL/version.h> |
| 34 |
# if CGAL_VERSION_MAJOR >= 6 |
| 35 |
# include <CGAL/Installation/internal/disable_deprecation_warnings_and_errors.h> |
| 36 |
# endif |
| 37 |
# include <CGAL/Cartesian.h> |
| 38 |
# include <CGAL/Complex_2_in_triangulation_3.h> |
| 39 |
# include <CGAL/Exact_predicates_exact_constructions_kernel.h> |
| 40 |
# include <CGAL/Exact_predicates_inexact_constructions_kernel.h> |
| 41 |
# include <CGAL/Kernel_traits.h> |
| 42 |
# include <CGAL/Mesh_complex_3_in_triangulation_3.h> |
| 43 |
# include <CGAL/Mesh_criteria_3.h> |
| 44 |
# include <CGAL/Mesh_triangulation_3.h> |
| 45 |
// Disable a warning that we get with gcc-13 about a potential uninitialized |
| 46 |
// usage of an <anonymous> lambda function in this external CGAL header. |
| 47 |
DEAL_II_DISABLE_EXTRA_DIAGNOSTICS |
| 48 |
# include <CGAL/Polygon_mesh_processing/corefinement.h> |
| 49 |
DEAL_II_ENABLE_EXTRA_DIAGNOSTICS |
| 50 |
# include <CGAL/Polygon_mesh_processing/measure.h> |
| 51 |
# include <CGAL/Polygon_mesh_processing/remesh.h> |
| 52 |
# include <CGAL/Polygon_mesh_processing/triangulate_faces.h> |
| 53 |
# include <CGAL/Polyhedral_mesh_domain_with_features_3.h> |
| 54 |
# include <CGAL/Simple_cartesian.h> |
| 55 |
# include <CGAL/Surface_mesh.h> |
| 56 |
# include <CGAL/Triangulation_3.h> |
| 57 |
# include <CGAL/boost/graph/copy_face_graph.h> |
| 58 |
# include <CGAL/boost/graph/selection.h> |
| 59 |
# include <CGAL/convex_hull_3.h> |
| 60 |
# include <CGAL/make_mesh_3.h> |
| 61 |
# include <CGAL/make_surface_mesh.h> |
| 62 |
|
| 63 |
# include <fstream> |
| 64 |
# include <limits> |
| 65 |
# include <type_traits> |
| 66 |
|
| 67 |
|
| 68 |
|
| 69 |
DEAL_II_NAMESPACE_OPEN |
| 70 |
/** |
| 71 |
* Interface to the Computational Geometry Algorithm Library (CGAL). |
| 72 |
* |
| 73 |
* CGAL is a software project that provides easy access to efficient and |
| 74 |
* reliable geometric algorithms. The library offers data structures and |
| 75 |
* algorithms like triangulations, Voronoi diagrams, Boolean operations on |
| 76 |
* polygons and polyhedra, point set processing, arrangements of curves, surface |
| 77 |
* and volume mesh generation, geometry processing, alpha shapes, convex hull |
| 78 |
* algorithms, shape reconstruction, AABB and KD trees... |
| 79 |
* |
| 80 |
* You can learn more about the CGAL library at https://www.cgal.org/ |
| 81 |
*/ |
| 82 |
namespace CGALWrappers |
| 83 |
{ |
| 84 |
# ifdef CGAL_CONCURRENT_MESH_3 |
| 85 |
using ConcurrencyTag = CGAL::Parallel_tag; |
| 86 |
# else |
| 87 |
using ConcurrencyTag = CGAL::Sequential_tag; |
| 88 |
# endif |
| 89 |
|
| 90 |
/** |
| 91 |
* An enum type given to functions that compute boolean operations between |
| 92 |
* geometrical objects, defined by triangulated surface grids. |
| 93 |
* |
| 94 |
* As an example, we show all supported boolean operations applied to a hedra |
| 95 |
* (the union of two pyramids) and a cube. |
| 96 |
* |
| 97 |
* @image html hedra_cube.png |
| 98 |
*/ |
| 99 |
enum class BooleanOperation |
| 100 |
{ |
| 101 |
/** |
| 102 |
* Given two triangulated surfaces, refine the first surface until its |
| 103 |
* intersection with the second surface is captured exactly by the |
| 104 |
* refinement |
| 105 |
* |
| 106 |
* @image html corefinement.png |
| 107 |
*/ |
| 108 |
compute_corefinement = 1 << 0, |
| 109 |
|
| 110 |
/** |
| 111 |
* Given two triangulated surfaces, compute the boolean difference of the |
| 112 |
* first surface minus the second surface |
| 113 |
* |
| 114 |
* @image html boolean_difference.png |
| 115 |
*/ |
| 116 |
compute_difference = 1 << 1, |
| 117 |
|
| 118 |
/** |
| 119 |
* Given two triangulated surfaces, compute their intersection |
| 120 |
* |
| 121 |
* @image html boolean_intersection.png |
| 122 |
*/ |
| 123 |
compute_intersection = 1 << 2, |
| 124 |
|
| 125 |
/** |
| 126 |
* Given two triangulated surfaces, compute their union |
| 127 |
* |
| 128 |
* @image html boolean_union.png |
| 129 |
*/ |
| 130 |
compute_union = 1 << 3, |
| 131 |
}; |
| 132 |
|
| 133 |
|
| 134 |
|
| 135 |
/** |
| 136 |
* Given a closed CGAL::Surface_mesh, this function fills the |
| 137 |
* region bounded by the surface with tets. |
| 138 |
* |
| 139 |
* |
| 140 |
* @param [in] surface_mesh The (closed) surface mesh bounding the volume that has to be filled. |
| 141 |
* @param [out] triangulation The output triangulation filled with tetrahedra. |
| 142 |
* @param [in] data AdditionalData object to pass to the CGAL::make_mesh_3 function. See the documentation |
| 143 |
* of that struct for a description of those parameters. |
| 144 |
*/ |
| 145 |
template <typename C3t3> |
| 146 |
void |
| 147 |
cgal_surface_mesh_to_cgal_triangulation( |
| 148 |
CGAL::Surface_mesh<typename C3t3::Point::Point> &surface_mesh, |
| 149 |
C3t3 &triangulation, |
| 150 |
const AdditionalData<3> &data = AdditionalData<3>{}); |
| 151 |
|
| 152 |
/** |
| 153 |
* Given two triangulated surface meshes that bound two volumes, execute a |
| 154 |
* boolean operation on them, and store the result in a third surface mesh. |
| 155 |
* |
| 156 |
* Quoting from CGAL documentation |
| 157 |
* (https://doc.cgal.org/latest/Polygon_mesh_processing/index.html#title14): |
| 158 |
* |
| 159 |
* > Given a closed triangulated surface mesh, each connected component splits |
| 160 |
* > the 3d space into two subspaces. The vertex sequence of each face of a |
| 161 |
* > component is seen either clockwise or counterclockwise from these two |
| 162 |
* > subspaces. The subspace that sees the sequence clockwise (resp. |
| 163 |
* > counterclockwise) is on the negative (resp. positive) side of the |
| 164 |
* > component. |
| 165 |
* |
| 166 |
* > Given a closed triangulated surface mesh `surface` with no |
| 167 |
* > self-intersections, we say that `surface` bounds a volume if each |
| 168 |
* > subspace lies exclusively on the positive (or negative) side of all the |
| 169 |
* > incident connected components of `surface`. The volume bounded by |
| 170 |
* > `surface` is the union of all subspaces that are on negative sides of |
| 171 |
* > their incident connected components of `surface`. |
| 172 |
* |
| 173 |
* > There is no restriction on the topology of the input volumes. However, |
| 174 |
* > there are some requirements on the input to guarantee that the operation |
| 175 |
* > is possible. First, the input meshes must not self-intersect. Second, the |
| 176 |
* > operation is possible only if the output can be bounded by a manifold |
| 177 |
* > triangulated surface mesh. In particular this means that the output |
| 178 |
* > volume has no part with zero thickness. Mathematically speaking, the |
| 179 |
* > intersection with an infinitesimally small ball centered in the output |
| 180 |
* > volume is a topological ball. At the surface level this means that no |
| 181 |
* > non-manifold vertex or edge is allowed in the output. For example, it is |
| 182 |
* > not possible to compute the union of two cubes that are disjoint but |
| 183 |
* > sharing an edge. |
| 184 |
* |
| 185 |
* See BooleanOperation for a list of available operations, with the |
| 186 |
* corresponding examples. |
| 187 |
* |
| 188 |
* @param[in] surface_mesh_1 The first surface mesh. |
| 189 |
* @param[in] surface_mesh_2 The second surface mesh. |
| 190 |
* @param[in] boolean_operation See BooleanOperation for the list of the |
| 191 |
* allowed operations. |
| 192 |
* @param[out] output_surface_mesh The surface mesh with the result of the |
| 193 |
* boolean operation. |
| 194 |
*/ |
| 195 |
template <typename CGALPointType> |
| 196 |
void |
| 197 |
compute_boolean_operation( |
| 198 |
const CGAL::Surface_mesh<CGALPointType> &surface_mesh_1, |
| 199 |
const CGAL::Surface_mesh<CGALPointType> &surface_mesh_2, |
| 200 |
const BooleanOperation &boolean_operation, |
| 201 |
CGAL::Surface_mesh<CGALPointType> &output_surface_mesh); |
| 202 |
|
| 203 |
/** |
| 204 |
* Given a CGAL Triangulation describing a polyhedral region, create |
| 205 |
* a Quadrature rule to integrate over the polygon by looping through all the |
| 206 |
* vertices and exploiting QGaussSimplex. |
| 207 |
* |
| 208 |
* @param[in] tria The CGAL triangulation object describing the polyhedral |
| 209 |
* region. |
| 210 |
* @param[in] degree Desired degree of the Quadrature rule on each element of |
| 211 |
* the polyhedral. |
| 212 |
* @return A global Quadrature rule that allows to integrate over the polyhedron. |
| 213 |
*/ |
| 214 |
template <typename CGALTriangulationType> |
| 215 |
dealii::Quadrature<CGALTriangulationType::Point::Ambient_dimension::value> |
| 216 |
compute_quadrature(const CGALTriangulationType &tria, |
| 217 |
const unsigned int degree); |
| 218 |
|
| 219 |
/** |
| 220 |
* Compute a Quadrature formula over the polygonal/polyhedral region described |
| 221 |
* by a BooleanOperation between two deal.II cell_iterator objects. The degree |
| 222 |
* of the Quadrature |
| 223 |
* rule is specified by the argument @p degree. This function splits the polygon/polyhedron |
| 224 |
* into simplices and collects QGaussSimplex quadrature rules. |
| 225 |
* |
| 226 |
* @param [in] cell0 A cell_iterator to the first deal.II cell. |
| 227 |
* @param [in] cell1 A cell_iterator to the second deal.II cell. |
| 228 |
* @param [in] degree The degree of accuracy you wish to get for the global quadrature formula. |
| 229 |
* @param [in] bool_op The BooleanOperation to be performed. |
| 230 |
* @param [in] mapping0 Mapping object for the first cell. |
| 231 |
* @param [in] mapping1 Mapping object for the first cell. |
| 232 |
* @return The global quadrature rule on the polygon/polyhedron. |
| 233 |
*/ |
| 234 |
template <int dim0, int dim1, int spacedim> |
| 235 |
dealii::Quadrature<spacedim> |
| 236 |
compute_quadrature_on_boolean_operation( |
| 237 |
const typename dealii::Triangulation<dim0, spacedim>::cell_iterator &cell0, |
| 238 |
const typename dealii::Triangulation<dim1, spacedim>::cell_iterator &cell1, |
| 239 |
const unsigned int degree, |
| 240 |
const BooleanOperation &bool_op, |
| 241 |
const Mapping<dim0, spacedim> &mapping0 = |
| 242 |
(ReferenceCells::get_hypercube<dim0>() |
| 243 |
.template get_default_linear_mapping<dim0, spacedim>()), |
| 244 |
const Mapping<dim1, spacedim> &mapping1 = |
| 245 |
(ReferenceCells::get_hypercube<dim1>() |
| 246 |
.template get_default_linear_mapping<dim1, spacedim>())); |
| 247 |
|
| 248 |
/** |
| 249 |
* A specialization of the function above when the BooleanOperation is an |
| 250 |
* intersection. The rationale behind this specialization is that deal.II |
| 251 |
* affine cells are convex sets, and as the intersection of convex sets is |
| 252 |
* itself convex, this function internally exploits this to use a cheaper way |
| 253 |
* to mesh the inside. |
| 254 |
* |
| 255 |
* |
| 256 |
* @param [in] cell0 A cell_iterator to the first deal.II cell. |
| 257 |
* @param [in] cell1 A cell_iterator to the second deal.II cell. |
| 258 |
* @param [in] mapping0 Mapping object for the first cell. |
| 259 |
* @param [in] mapping1 Mapping object for the first cell. |
| 260 |
* @param [in] degree The degree of accuracy you wish to get for the global quadrature formula. |
| 261 |
* @return The global quadrature rule on the polygon/polyhedron. |
| 262 |
*/ |
| 263 |
template <int dim0, int dim1, int spacedim> |
| 264 |
dealii::Quadrature<spacedim> |
| 265 |
compute_quadrature_on_intersection( |
| 266 |
const typename dealii::Triangulation<dim0, spacedim>::cell_iterator &cell0, |
| 267 |
const typename dealii::Triangulation<dim1, spacedim>::cell_iterator &cell1, |
| 268 |
const unsigned int degree, |
| 269 |
const Mapping<dim0, spacedim> &mapping0, |
| 270 |
const Mapping<dim1, spacedim> &mapping1); |
| 271 |
|
| 272 |
/** |
| 273 |
* Remesh a CGAL::Surface_mesh. |
| 274 |
* |
| 275 |
* If the domain has 1-dimensional exposed features, the criteria includes a |
| 276 |
* sizing field to guide the sampling of 1-dimensional features with |
| 277 |
* protecting balls centers. |
| 278 |
* - CGAL::parameters::edge_size. |
| 279 |
* |
| 280 |
* This utility should be exploited to improve the quality of a mesh coming |
| 281 |
* from boolean operations. As an example, consider two CGAL::Surface_mesh |
| 282 |
* objects describing two hyper_spheres that intersect non-trivially. After |
| 283 |
* computing their corefinement and union with compute_boolean_operation(), |
| 284 |
* the resulting mesh is the following: |
| 285 |
* |
| 286 |
* @image html boolean_union_hyper_spheres.png |
| 287 |
* |
| 288 |
* Clearly, elements (triangles) like the ones arising along the intersection |
| 289 |
* of the two spheres should be avoided as they're quite degenerate and would |
| 290 |
* decrease the accuracy of the results. A call to the present function will |
| 291 |
* try to remesh the surface, according to the given named parameters, to |
| 292 |
* improve its quality. In the present case, the result is the following: |
| 293 |
* |
| 294 |
* @image html boolean_union_hyper_spheres_remeshed.png |
| 295 |
* |
| 296 |
* @param surface_mesh The input CGAL::Surface_mesh. |
| 297 |
* @param [in] data AdditionalData object to pass to the CGAL::make_mesh_3 function. See the documentation |
| 298 |
* of that struct for a description of those parameters. |
| 299 |
*/ |
| 300 |
template <typename CGALPointType> |
| 301 |
void |
| 302 |
remesh_surface(CGAL::Surface_mesh<CGALPointType> &surface_mesh, |
| 303 |
const AdditionalData<3> &data = AdditionalData<3>{}); |
| 304 |
} // namespace CGALWrappers |
| 305 |
|
| 306 |
# ifndef DOXYGEN |
| 307 |
// Template implementations |
| 308 |
namespace CGALWrappers |
| 309 |
{ |
| 310 |
template <typename C3t3> |
| 311 |
void |
| 312 |
cgal_surface_mesh_to_cgal_triangulation( |
| 313 |
CGAL::Surface_mesh<typename C3t3::Point::Point> &surface_mesh, |
| 314 |
C3t3 &triangulation, |
| 315 |
const AdditionalData<3> &data) |
| 316 |
{ |
| 317 |
using CGALPointType = typename C3t3::Point::Point; |
| 318 |
Assert(CGAL::is_closed(surface_mesh), |
| 319 |
ExcMessage("The surface mesh must be closed.")); |
| 320 |
|
| 321 |
using K = typename CGAL::Kernel_traits<CGALPointType>::Kernel; |
| 322 |
using Mesh_domain = CGAL::Polyhedral_mesh_domain_with_features_3< |
| 323 |
K, |
| 324 |
CGAL::Surface_mesh<CGALPointType>>; |
| 325 |
using Tr = typename CGAL:: |
| 326 |
Mesh_triangulation_3<Mesh_domain, CGAL::Default, ConcurrencyTag>::type; |
| 327 |
using Mesh_criteria = CGAL::Mesh_criteria_3<Tr>; |
| 328 |
|
| 329 |
CGAL::Polygon_mesh_processing::triangulate_faces(surface_mesh); |
| 330 |
Mesh_domain domain(surface_mesh); |
| 331 |
domain.detect_features(); |
| 332 |
Mesh_criteria criteria(CGAL::parameters::facet_size = data.facet_size, |
| 333 |
CGAL::parameters::facet_angle = data.facet_angle, |
| 334 |
CGAL::parameters::facet_distance = |
| 335 |
data.facet_distance, |
| 336 |
CGAL::parameters::cell_radius_edge_ratio = |
| 337 |
data.cell_radius_edge_ratio, |
| 338 |
CGAL::parameters::cell_size = data.cell_size); |
| 339 |
// Mesh generation |
| 340 |
triangulation = CGAL::make_mesh_3<C3t3>(domain, |
| 341 |
criteria, |
| 342 |
CGAL::parameters::no_perturb(), |
| 343 |
CGAL::parameters::no_exude()); |
| 344 |
} |
| 345 |
|
| 346 |
|
| 347 |
|
| 348 |
template <typename CGALPointType> |
| 349 |
void |
| 350 |
compute_boolean_operation( |
| 351 |
const CGAL::Surface_mesh<CGALPointType> &surface_mesh_1, |
| 352 |
const CGAL::Surface_mesh<CGALPointType> &surface_mesh_2, |
| 353 |
const BooleanOperation &boolean_operation, |
| 354 |
CGAL::Surface_mesh<CGALPointType> &output_surface_mesh) |
| 355 |
{ |
| 356 |
Assert(output_surface_mesh.is_empty(), |
| 357 |
ExcMessage( |
| 358 |
"output_surface_mesh must be empty upon calling this function")); |
| 359 |
Assert(CGAL::is_closed(surface_mesh_1), |
| 360 |
ExcMessage( |
| 361 |
"The input surface_mesh_1 must be a closed surface mesh.")); |
| 362 |
Assert(CGAL::is_closed(surface_mesh_2), |
| 363 |
ExcMessage( |
| 364 |
"The input surface_mesh_2 must be a closed surface mesh.")); |
| 365 |
Assert(CGAL::is_triangle_mesh(surface_mesh_1), |
| 366 |
ExcMessage("The first CGAL mesh must be triangulated.")); |
| 367 |
Assert(CGAL::is_triangle_mesh(surface_mesh_2), |
| 368 |
ExcMessage("The second CGAL mesh must be triangulated.")); |
| 369 |
|
| 370 |
bool res = false; |
| 371 |
auto surf_1 = surface_mesh_1; |
| 372 |
auto surf_2 = surface_mesh_2; |
| 373 |
namespace PMP = CGAL::Polygon_mesh_processing; |
| 374 |
switch (boolean_operation) |
| 375 |
{ |
| 376 |
case BooleanOperation::compute_union: |
| 377 |
res = PMP::corefine_and_compute_union(surf_1, |
| 378 |
surf_2, |
| 379 |
output_surface_mesh); |
| 380 |
break; |
| 381 |
case BooleanOperation::compute_intersection: |
| 382 |
res = PMP::corefine_and_compute_intersection(surf_1, |
| 383 |
surf_2, |
| 384 |
output_surface_mesh); |
| 385 |
break; |
| 386 |
case BooleanOperation::compute_difference: |
| 387 |
res = PMP::corefine_and_compute_difference(surf_1, |
| 388 |
surf_2, |
| 389 |
output_surface_mesh); |
| 390 |
break; |
| 391 |
case BooleanOperation::compute_corefinement: |
| 392 |
PMP::corefine(surf_1, |
| 393 |
surf_2); // both surfaces are corefined |
| 394 |
output_surface_mesh = std::move(surf_1); |
| 395 |
res = true; |
| 396 |
break; |
| 397 |
default: |
| 398 |
output_surface_mesh.clear(); |
| 399 |
break; |
| 400 |
} |
| 401 |
(void)res; |
| 402 |
Assert(res, |
| 403 |
ExcMessage("The boolean operation was not successfully computed.")); |
| 404 |
} |
| 405 |
|
| 406 |
|
| 407 |
|
| 408 |
template <typename CGALTriangulationType> |
| 409 |
dealii::Quadrature<CGALTriangulationType::Point::Ambient_dimension::value> |
| 410 |
compute_quadrature(const CGALTriangulationType &tria, |
| 411 |
const unsigned int degree) |
| 412 |
{ |
| 413 |
Assert(tria.is_valid(), ExcMessage("The triangulation is not valid.")); |
| 414 |
Assert(CGALTriangulationType::Point::Ambient_dimension::value == 3, |
| 415 |
ExcNotImplemented()); |
| 416 |
Assert(degree > 0, |
| 417 |
ExcMessage("The degree of the Quadrature formula is not positive.")); |
| 418 |
|
| 419 |
constexpr int spacedim = |
| 420 |
CGALTriangulationType::Point::Ambient_dimension::value; |
| 421 |
std::vector<std::array<dealii::Point<spacedim>, spacedim + 1>> |
| 422 |
vec_of_simplices; // tets |
| 423 |
|
| 424 |
std::array<dealii::Point<spacedim>, spacedim + 1> simplex; |
| 425 |
for (const auto &f : tria.finite_cell_handles()) |
| 426 |
{ |
| 427 |
for (unsigned int i = 0; i < (spacedim + 1); ++i) |
| 428 |
{ |
| 429 |
simplex[i] = |
| 430 |
cgal_point_to_dealii_point<spacedim>(f->vertex(i)->point()); |
| 431 |
} |
| 432 |
|
| 433 |
vec_of_simplices.push_back(simplex); |
| 434 |
} |
| 435 |
|
| 436 |
return QGaussSimplex<spacedim>(degree).mapped_quadrature(vec_of_simplices); |
| 437 |
} |
| 438 |
|
| 439 |
|
| 440 |
|
| 441 |
template <int dim0, int dim1, int spacedim> |
| 442 |
dealii::Quadrature<spacedim> |
| 443 |
compute_quadrature_on_boolean_operation( |
| 444 |
const typename dealii::Triangulation<dim0, spacedim>::cell_iterator &cell0, |
| 445 |
const typename dealii::Triangulation<dim1, spacedim>::cell_iterator &cell1, |
| 446 |
const unsigned int degree, |
| 447 |
const BooleanOperation &bool_op, |
| 448 |
const Mapping<dim0, spacedim> &mapping0, |
| 449 |
const Mapping<dim1, spacedim> &mapping1) |
| 450 |
{ |
| 451 |
Assert(dim0 == 3 && dim1 == 3 && spacedim == 3, |
| 452 |
ExcNotImplemented("2d geometries are not yet supported.")); |
| 453 |
if (dim1 > dim0) |
| 454 |
{ |
| 455 |
return compute_quadrature_on_boolean_operation( |
| 456 |
cell1, |
| 457 |
cell0, |
| 458 |
degree, |
| 459 |
bool_op, |
| 460 |
mapping1, |
| 461 |
mapping0); // This function works for dim1<=dim0, so swap them if this |
| 462 |
// is not the case. |
| 463 |
} |
| 464 |
if (bool_op == BooleanOperation::compute_intersection) |
| 465 |
{ |
| 466 |
return compute_quadrature_on_intersection( |
| 467 |
cell0, cell1, degree, mapping0, mapping1); |
| 468 |
} |
| 469 |
else |
| 470 |
{ |
| 471 |
using K = CGAL::Exact_predicates_inexact_constructions_kernel; |
| 472 |
using CGALPoint = CGAL::Point_3<K>; |
| 473 |
using CGALTriangulation = CGAL::Triangulation_3<K>; |
| 474 |
CGAL::Surface_mesh<CGALPoint> surface_1, surface_2, out_surface; |
| 475 |
dealii_cell_to_cgal_surface_mesh(cell0, mapping0, surface_1); |
| 476 |
dealii_cell_to_cgal_surface_mesh(cell1, mapping1, surface_2); |
| 477 |
// They have to be triangle meshes |
| 478 |
CGAL::Polygon_mesh_processing::triangulate_faces(surface_1); |
| 479 |
CGAL::Polygon_mesh_processing::triangulate_faces(surface_2); |
| 480 |
Assert(CGAL::is_triangle_mesh(surface_1) && |
| 481 |
CGAL::is_triangle_mesh(surface_2), |
| 482 |
ExcMessage("The surface must be a triangle mesh.")); |
| 483 |
compute_boolean_operation(surface_1, surface_2, bool_op, out_surface); |
| 484 |
|
| 485 |
CGALTriangulation tria; |
| 486 |
tria.insert(out_surface.points().begin(), out_surface.points().end()); |
| 487 |
return compute_quadrature(tria, degree); |
| 488 |
} |
| 489 |
} |
| 490 |
|
| 491 |
|
| 492 |
|
| 493 |
template <int dim0, int dim1, int spacedim> |
| 494 |
dealii::Quadrature<spacedim> |
| 495 |
compute_quadrature_on_intersection( |
| 496 |
const typename dealii::Triangulation<dim0, spacedim>::cell_iterator &cell0, |
| 497 |
const typename dealii::Triangulation<dim1, spacedim>::cell_iterator &cell1, |
| 498 |
const unsigned int degree, |
| 499 |
const Mapping<dim0, spacedim> &mapping0, |
| 500 |
const Mapping<dim1, spacedim> &mapping1) |
| 501 |
{ |
| 502 |
Assert(dim0 == 3 && dim1 == 3 && spacedim == 3, |
| 503 |
ExcNotImplemented("2d geometries are not yet supported.")); |
| 504 |
using K = CGAL::Exact_predicates_inexact_constructions_kernel; |
| 505 |
using CGALPoint = CGAL::Point_3<K>; |
| 506 |
using CGALTriangulation = CGAL::Triangulation_3<K>; |
| 507 |
|
| 508 |
CGAL::Surface_mesh<CGALPoint> surface_1, surface_2, out_surface; |
| 509 |
dealii_cell_to_cgal_surface_mesh(cell0, mapping0, surface_1); |
| 510 |
dealii_cell_to_cgal_surface_mesh(cell1, mapping1, surface_2); |
| 511 |
// They have to be triangle meshes |
| 512 |
CGAL::Polygon_mesh_processing::triangulate_faces(surface_1); |
| 513 |
CGAL::Polygon_mesh_processing::triangulate_faces(surface_2); |
| 514 |
|
| 515 |
compute_boolean_operation(surface_1, |
| 516 |
surface_2, |
| 517 |
BooleanOperation::compute_intersection, |
| 518 |
out_surface); |
| 519 |
CGAL::Surface_mesh<CGALPoint> dummy; |
| 520 |
CGALTriangulation tr; |
| 521 |
CGAL::convex_hull_3(out_surface.points().begin(), |
| 522 |
out_surface.points().end(), |
| 523 |
dummy); |
| 524 |
tr.insert(dummy.points().begin(), dummy.points().end()); |
| 525 |
return compute_quadrature(tr, degree); |
| 526 |
} |
| 527 |
|
| 528 |
|
| 529 |
|
| 530 |
template <typename CGALPointType> |
| 531 |
void |
| 532 |
remesh_surface(CGAL::Surface_mesh<CGALPointType> &cgal_mesh, |
| 533 |
const AdditionalData<3> &data) |
| 534 |
{ |
| 535 |
using K = CGAL::Exact_predicates_inexact_constructions_kernel; |
| 536 |
using Mesh_domain = CGAL::Polyhedral_mesh_domain_with_features_3<K>; |
| 537 |
// Polyhedron type |
| 538 |
using Polyhedron = CGAL::Mesh_polyhedron_3<K>::type; |
| 539 |
// Triangulation |
| 540 |
using Tr = CGAL::Mesh_triangulation_3<Mesh_domain>::type; |
| 541 |
using C3t3 = |
| 542 |
CGAL::Mesh_complex_3_in_triangulation_3<Tr, |
| 543 |
Mesh_domain::Corner_index, |
| 544 |
Mesh_domain::Curve_index>; |
| 545 |
// Criteria |
| 546 |
using Mesh_criteria = CGAL::Mesh_criteria_3<Tr>; |
| 547 |
|
| 548 |
Polyhedron poly; |
| 549 |
CGAL::copy_face_graph(cgal_mesh, poly); |
| 550 |
// Create a vector with only one element: the pointer to the |
| 551 |
// polyhedron. |
| 552 |
std::vector<Polyhedron *> poly_ptrs_vector(1, &poly); |
| 553 |
// Create a polyhedral domain, with only one polyhedron, |
| 554 |
// and no "bounding polyhedron", so the volumetric part of the |
| 555 |
// domain will be empty. |
| 556 |
Mesh_domain domain(poly_ptrs_vector.begin(), poly_ptrs_vector.end()); |
| 557 |
// Get sharp features |
| 558 |
domain.detect_features(); // includes detection of borders |
| 559 |
|
| 560 |
// Mesh criteria |
| 561 |
const double default_value_edge_size = std::numeric_limits<double>::max(); |
| 562 |
if (data.edge_size > 0 && |
| 563 |
std::abs(data.edge_size - default_value_edge_size) > 1e-12) |
| 564 |
{ |
| 565 |
Mesh_criteria criteria(CGAL::parameters::edge_size = data.edge_size, |
| 566 |
CGAL::parameters::facet_size = data.facet_size, |
| 567 |
CGAL::parameters::facet_angle = data.facet_angle, |
| 568 |
CGAL::parameters::facet_distance = |
| 569 |
data.facet_distance, |
| 570 |
CGAL::parameters::cell_radius_edge_ratio = |
| 571 |
data.cell_radius_edge_ratio, |
| 572 |
CGAL::parameters::cell_size = data.cell_size); |
| 573 |
// Mesh generation |
| 574 |
C3t3 c3t3 = CGAL::make_mesh_3<C3t3>(domain, |
| 575 |
criteria, |
| 576 |
CGAL::parameters::no_perturb(), |
| 577 |
CGAL::parameters::no_exude()); |
| 578 |
cgal_mesh.clear(); |
| 579 |
CGAL::facets_in_complex_3_to_triangle_mesh(c3t3, cgal_mesh); |
| 580 |
} |
| 581 |
else if (std::abs(data.edge_size - default_value_edge_size) <= 1e-12) |
| 582 |
{ |
| 583 |
Mesh_criteria criteria(CGAL::parameters::facet_size = data.facet_size, |
| 584 |
CGAL::parameters::facet_angle = data.facet_angle, |
| 585 |
CGAL::parameters::facet_distance = |
| 586 |
data.facet_distance, |
| 587 |
CGAL::parameters::cell_radius_edge_ratio = |
| 588 |
data.cell_radius_edge_ratio, |
| 589 |
CGAL::parameters::cell_size = data.cell_size); |
| 590 |
// Mesh generation |
| 591 |
C3t3 c3t3 = CGAL::make_mesh_3<C3t3>(domain, |
| 592 |
criteria, |
| 593 |
CGAL::parameters::no_perturb(), |
| 594 |
CGAL::parameters::no_exude()); |
| 595 |
cgal_mesh.clear(); |
| 596 |
CGAL::facets_in_complex_3_to_triangle_mesh(c3t3, cgal_mesh); |
| 597 |
} |
| 598 |
else |
| 599 |
{ |
| 600 |
DEAL_II_ASSERT_UNREACHABLE(); |
| 601 |
} |
| 602 |
} |
| 603 |
|
| 604 |
|
| 605 |
|
| 606 |
/** |
| 607 |
* Resort vertices in deal.II order to vertices in CGAL order. |
| 608 |
* |
| 609 |
* @param structdim Dimension of the entity which is described by the vertices. |
| 610 |
* @param vertices Vertices in deal.II order which are resorted to CGAL order. |
| 611 |
*/ |
| 612 |
template <int spacedim> |
| 613 |
void |
| 614 |
resort_dealii_vertices_to_cgal_order(const unsigned int structdim, |
| 615 |
std::vector<Point<spacedim>> &vertices) |
| 616 |
{ |
| 617 |
// Mark the two arguments as "used" because some compilers complain about |
| 618 |
// arguments used only within an 'if constexpr' block. |
| 619 |
(void)structdim; |
| 620 |
(void)vertices; |
| 621 |
|
| 622 |
if constexpr (spacedim == 2) |
| 623 |
if (ReferenceCell::n_vertices_to_type(structdim, vertices.size()) == |
| 624 |
ReferenceCells::Quadrilateral) |
| 625 |
std::swap(vertices[2], vertices[3]); |
| 626 |
} |
| 627 |
|
| 628 |
|
| 629 |
|
| 630 |
/** |
| 631 |
* Get vertices of cell in CGAL ordering. |
| 632 |
* |
| 633 |
* @param cell A cell_iterator to a deal.II cell. |
| 634 |
* @param mapping Mapping object for the cell. |
| 635 |
* @return Array of vertices in CGAL order. |
| 636 |
*/ |
| 637 |
template <int dim, int spacedim> |
| 638 |
std::vector<Point<spacedim>> |
| 639 |
get_vertices_in_cgal_order( |
| 640 |
const typename dealii::Triangulation<dim, spacedim>::cell_iterator &cell, |
| 641 |
const Mapping<dim, spacedim> &mapping) |
| 642 |
{ |
| 643 |
// Elements have to be rectangular or simplices |
| 644 |
const unsigned int n_vertices = cell->n_vertices(); |
| 645 |
Assert((n_vertices == ReferenceCells::get_hypercube<dim>().n_vertices()) || |
| 646 |
(n_vertices == ReferenceCells::get_simplex<dim>().n_vertices()), |
| 647 |
ExcNotImplemented()); |
| 648 |
|
| 649 |
std::vector<Point<spacedim>> ordered_vertices(n_vertices); |
| 650 |
std::copy_n(mapping.get_vertices(cell).begin(), |
| 651 |
n_vertices, |
| 652 |
ordered_vertices.begin()); |
| 653 |
|
| 654 |
resort_dealii_vertices_to_cgal_order(dim, ordered_vertices); |
| 655 |
|
| 656 |
return ordered_vertices; |
| 657 |
} |
| 658 |
|
| 659 |
|
| 660 |
|
| 661 |
/** |
| 662 |
* Get vertices of face in CGAL ordering |
| 663 |
* |
| 664 |
* @param cell A cell_iterator to a deal.II cell. |
| 665 |
* @param face_no The face number within the given cell. |
| 666 |
* @param mapping Mapping object for the cell. |
| 667 |
* @return Array of vertices in CGAL order. |
| 668 |
*/ |
| 669 |
template <int dim, int spacedim> |
| 670 |
std::vector<Point<spacedim>> |
| 671 |
get_vertices_in_cgal_order( |
| 672 |
const typename dealii::Triangulation<dim, spacedim>::cell_iterator &cell, |
| 673 |
const unsigned int face_no, |
| 674 |
const Mapping<dim, spacedim> &mapping) |
| 675 |
{ |
| 676 |
// Elements have to be rectangular or simplices |
| 677 |
const unsigned int n_vertices = cell->face(face_no)->n_vertices(); |
| 678 |
Assert( |
| 679 |
(n_vertices == ReferenceCells::get_hypercube<dim - 1>().n_vertices()) || |
| 680 |
(n_vertices == ReferenceCells::get_simplex<dim - 1>().n_vertices()), |
| 681 |
ExcNotImplemented()); |
| 682 |
|
| 683 |
std::vector<Point<spacedim>> ordered_vertices(n_vertices); |
| 684 |
std::copy_n(mapping.get_vertices(cell, face_no).begin(), |
| 685 |
n_vertices, |
| 686 |
ordered_vertices.begin()); |
| 687 |
|
| 688 |
resort_dealii_vertices_to_cgal_order(dim - 1, ordered_vertices); |
| 689 |
|
| 690 |
return ordered_vertices; |
| 691 |
} |
| 692 |
|
| 693 |
|
| 694 |
|
| 695 |
} // namespace CGALWrappers |
| 696 |
# endif |
| 697 |
|
| 698 |
DEAL_II_NAMESPACE_CLOSE |
| 699 |
|
| 700 |
#else |
| 701 |
|
| 702 |
// Make sure the scripts that create the C++20 module input files have |
| 703 |
// something to latch on if the preprocessor #ifdef above would |
| 704 |
// otherwise lead to an empty content of the file. |
| 705 |
DEAL_II_NAMESPACE_OPEN |
| 706 |
DEAL_II_NAMESPACE_CLOSE |
| 707 |
|
| 708 |
#endif |
| 709 |
#endif |