v0.16.3
Loading...
Searching...
No Matches
CGALTools.cpp
Go to the documentation of this file.
1#include "CGALTools.hpp"
3#include <algorithm>
4#include <climits>
5#include <cmath>
6#include <numeric>
7#include <limits>
8#include <map>
9#include <memory>
10#include <CGAL/squared_distance_3.h>
11#include <CGAL/Tetrahedral_remeshing/Remeshing_triangulation_3.h>
12#include <CGAL/version.h>
13#if CGAL_VERSION_NR >= 1060200000
14 #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
15 #include <CGAL/Conforming_constrained_Delaunay_triangulation_cell_base_3.h>
16 #include <CGAL/Conforming_constrained_Delaunay_triangulation_vertex_base_3.h>
17 #include <CGAL/make_conforming_constrained_Delaunay_triangulation_3.h>
18 #include <CGAL/Polygon_mesh_processing/self_intersections.h>
19#endif
20#include <CGAL/AABB_segment_primitive_3.h>
21#include <CGAL/tetrahedral_remeshing.h>
22#include <CGAL/AABB_tree.h>
23#include <CGAL/AABB_traits_3.h>
24#include <CGAL/AABB_triangle_primitive_3.h>
25#include <CGAL/box_intersection_d.h>
26#include <CGAL/Box_intersection_d/Box_with_info_d.h>
27#include <boost/property_map/property_map.hpp>
28#include <set>
29#include <sstream>
30
31// Parse CGAL/Eigen before MoFEM imports Boost names into global scope.
32#include <MoFEM.hpp>
33
34namespace MoFEM {
35
36namespace {
37void logWarning(const std::string &message) {
38 if (!LogManager::checkIfChannelExist("CGALTools")) {
39 logging::core::get()->add_sink(
41 LogManager::setLog("CGALTools");
42 MOFEM_LOG_TAG("CGALTools", "CGALTools");
43 }
44 MOFEM_LOG("CGALTools", Sev::warning) << message;
45}
46
47using RemeshKernel = CGALMesh::Kernel;
48using RemeshPoint = RemeshKernel::Point_3;
49using RemeshFace = std::array<int, 3>;
50using RemeshEdge = std::array<int, 2>;
51using Triangles = std::vector<RemeshKernel::Triangle_3>;
52using TrianglePrimitive =
53 CGAL::AABB_triangle_primitive_3<RemeshKernel, Triangles::const_iterator>;
54using TriangleTree =
55 CGAL::AABB_tree<CGAL::AABB_traits_3<RemeshKernel, TrianglePrimitive>>;
56
57// Filtered nearest-face traversal retains normal constraints and deterministic
58// ties, instead of substituting the unrestricted nearest primitive.
59struct ClosestAlignedTriangle {
60 const Triangles &triangles;
61 std::function<bool(size_t)> accept;
62 std::function<bool(size_t, size_t)> preferred;
63 size_t best = std::numeric_limits<size_t>::max();
64 double distance = std::numeric_limits<double>::infinity();
65 bool go_further() const { return true; }
66 template <class Node>
67 bool do_intersect(const RemeshPoint &point, const Node &node) const {
68 const auto &box = node.bbox();
69 const double lo[] = {box.xmin(), box.ymin(), box.zmin()},
70 hi[] = {box.xmax(), box.ymax(), box.zmax()};
71 long double lower = 0;
72 for (int d = 0; d != 3; ++d) {
73 const long double x = point[d];
74 const auto delta = std::max({0.L, lo[d] - x, x - hi[d]});
75 lower += delta * delta;
76 }
77 return lower <= distance + 64 * std::numeric_limits<double>::epsilon() *
78 std::max(1., distance);
79 }
80 void intersection(const RemeshPoint &point,
81 const TrianglePrimitive &primitive) {
82 const size_t index = primitive.id() - triangles.begin();
83 if (!accept(index))
84 return;
85 const double value =
86 CGAL::to_double(CGAL::squared_distance(point, triangles[index]));
87 if (value < distance ||
88 (value == distance && (best == std::numeric_limits<size_t>::max() ||
89 preferred(index, best)))) {
90 best = index;
91 distance = value;
92 }
93 }
94};
95template <class Base> struct RemeshCellBase : Base {
96 using Base::Base;
97 bool selected = false;
98 template <class TDS> struct Rebind_TDS {
99 using Other =
100 RemeshCellBase<typename Base::template Rebind_TDS<TDS>::Other>;
101 };
102};
103template <class Tr> struct RemeshSelection {
104 using key_type = typename Tr::Cell_handle;
105 using value_type = bool;
106 using reference = bool;
107 using category = boost::read_write_property_map_tag;
108 friend bool get(const RemeshSelection &, key_type cell) {
109 return cell->selected;
110 }
111 friend void put(const RemeshSelection &, key_type cell, bool value) {
112 cell->selected = value;
113 }
114};
115template <class T> T simplexKey(T value) {
116 std::sort(value.begin(), value.end());
117 return value;
118}
119RemeshPoint remeshPoint(const TetMeshData &mesh, int i) {
120 const auto &p = mesh.points.at(i);
121 return {p[0], p[1], p[2]};
122}
123using RemeshFaces = std::map<RemeshFace, std::vector<int>>;
124
125// The face map checks the input before the soup builder, whose preconditions
126// are assertions in CGAL. Keeping this independent also checks exported data.
127RemeshFaces remeshFaces(const TetMeshData &mesh, bool check_embedding = true) {
128 RemeshFaces faces;
129 std::set<std::array<int, 4>> unique;
130 for (size_t i = 0; i != mesh.cells.size(); ++i) {
131 const auto &c = mesh.cells[i];
132 for (int v : c)
133 if (v < 0 || static_cast<size_t>(v) >= mesh.points.size())
134 THROW_MESSAGE("Invalid remeshing cell index");
135 const auto key = simplexKey(c);
136 if (std::adjacent_find(key.begin(), key.end()) != key.end() ||
137 !unique.insert(key).second ||
138 CGAL::orientation(remeshPoint(mesh, c[0]), remeshPoint(mesh, c[1]),
139 remeshPoint(mesh, c[2]),
140 remeshPoint(mesh, c[3])) != CGAL::POSITIVE)
141 THROW_MESSAGE("Remeshing requires unique positive tetrahedra");
142 for (int d = 0; d != 4; ++d) {
143 RemeshFace f;
144 int n = 0;
145 for (int j = 0; j != 4; ++j)
146 if (j != d)
147 f[n++] = c[j];
148 auto &incident = faces[simplexKey(f)];
149 incident.push_back(i);
150 if (incident.size() > 2)
151 THROW_MESSAGE("Non-manifold remeshing volume facet");
152 }
153 }
154 if (check_embedding)
155 for (const auto &[f, incident] : faces) {
156 int side = 0;
157 for (int i : incident) {
158 const auto &c = mesh.cells[i];
159 const int v = *std::find_if(c.begin(), c.end(), [&](int v) {
160 return std::find(f.begin(), f.end(), v) == f.end();
161 });
162 const int s =
163 CGAL::orientation(remeshPoint(mesh, f[0]), remeshPoint(mesh, f[1]),
164 remeshPoint(mesh, f[2]), remeshPoint(mesh, v));
165 if (s == side)
166 THROW_MESSAGE("Overlapping cells at a remeshing facet");
167 side = s;
168 }
169 }
170 return faces;
171}
172
173// Compare surface topology independently of triangle count and sampling.
174using PatchTopology = std::map<int, std::vector<std::pair<int, int>>>;
175PatchTopology patchTopology(const TetMeshData &mesh) {
176 std::map<int, std::vector<RemeshFace>> patches;
177 for (size_t i = 0; i != mesh.boundary.size(); ++i)
178 patches[mesh.surfaceLabels.at(i)].push_back(mesh.boundary[i]);
179 PatchTopology topology;
180 for (const auto &[label, triangles] : patches) {
181 std::map<RemeshEdge, std::vector<int>> edges;
182 std::map<int, std::vector<RemeshEdge>> links;
183 std::set<RemeshFace> unique;
184 for (size_t i = 0; i != triangles.size(); ++i) {
185 const auto &f = triangles[i];
186 if (!unique.insert(simplexKey(f)).second ||
187 CGAL::collinear(remeshPoint(mesh, f[0]), remeshPoint(mesh, f[1]),
188 remeshPoint(mesh, f[2])))
189 THROW_MESSAGE("Duplicate or degenerate remeshing surface");
190 for (int d = 0; d != 3; ++d) {
191 const RemeshEdge e =
192 simplexKey(RemeshEdge{f[(d + 1) % 3], f[(d + 2) % 3]});
193 edges[e].push_back(i);
194 links[f[d]].push_back(e);
195 }
196 }
197 for (const auto &[v, link] : links) {
198 std::map<int, std::vector<int>> graph;
199 for (const auto &e : link) {
200 graph[e[0]].push_back(e[1]);
201 graph[e[1]].push_back(e[0]);
202 }
203 std::set<int> reached;
204 std::vector<int> queue{graph.begin()->first};
205 int endpoints = 0;
206 for (const auto &[n, neighbours] : graph) {
207 if (neighbours.size() == 1)
208 ++endpoints;
209 else if (neighbours.size() != 2)
210 THROW_MESSAGE("Non-manifold remeshing surface vertex");
211 }
212 for (size_t i = 0; i != queue.size(); ++i)
213 if (reached.insert(queue[i]).second)
214 queue.insert(queue.end(), graph.at(queue[i]).begin(),
215 graph.at(queue[i]).end());
216 if (reached.size() != graph.size() || (endpoints != 0 && endpoints != 2))
217 THROW_MESSAGE("Disconnected remeshing surface vertex link");
218 }
219 std::vector<std::vector<int>> neighbours(triangles.size());
220 for (const auto &[e, adjacent] : edges) {
221 if (adjacent.size() > 2)
222 THROW_MESSAGE("Non-manifold remeshing surface edge");
223 if (adjacent.size() == 2) {
224 neighbours[adjacent[0]].push_back(adjacent[1]);
225 neighbours[adjacent[1]].push_back(adjacent[0]);
226 }
227 }
228 std::set<int> visited;
229 for (size_t seed = 0; seed != triangles.size(); ++seed) {
230 if (visited.count(seed))
231 continue;
232 std::vector<int> queue{static_cast<int>(seed)};
233 std::set<int> vertices;
234 std::set<RemeshEdge> component_edges;
235 std::map<int, std::vector<int>> boundary;
236 int count = 0;
237 for (size_t i = 0; i != queue.size(); ++i) {
238 const int f = queue[i];
239 if (!visited.insert(f).second)
240 continue;
241 ++count;
242 vertices.insert(triangles[f].begin(), triangles[f].end());
243 for (int d = 0; d != 3; ++d) {
244 const auto e = simplexKey(
245 RemeshEdge{triangles[f][d], triangles[f][(d + 1) % 3]});
246 component_edges.insert(e);
247 if (edges.at(e).size() == 1) {
248 boundary[e[0]].push_back(e[1]);
249 boundary[e[1]].push_back(e[0]);
250 }
251 }
252 queue.insert(queue.end(), neighbours[f].begin(), neighbours[f].end());
253 }
254 int loops = 0;
255 std::set<int> seen;
256 for (const auto &[v, adj] : boundary) {
257 if (adj.size() != 2)
258 THROW_MESSAGE("Branched remeshing patch boundary");
259 if (seen.count(v))
260 continue;
261 ++loops;
262 std::vector<int> walk{v};
263 for (size_t i = 0; i != walk.size(); ++i)
264 if (seen.insert(walk[i]).second)
265 walk.insert(walk.end(), boundary.at(walk[i]).begin(),
266 boundary.at(walk[i]).end());
267 }
268 topology[label].emplace_back(
269 static_cast<int>(vertices.size()) -
270 static_cast<int>(component_edges.size()) + count,
271 loops);
272 }
273 std::sort(topology[label].begin(), topology[label].end());
274 }
275 return topology;
276}
277
278double remeshQuality(const TetMeshData &mesh) {
279 double minimum = 1;
280 for (const auto &c : mesh.cells) {
281 double sum = 0;
282 for (int i = 0; i != 4; ++i)
283 for (int j = 0; j != i; ++j)
284 sum += CGAL::to_double(CGAL::squared_distance(remeshPoint(mesh, c[i]),
285 remeshPoint(mesh, c[j])));
286 const double volume = CGAL::to_double(
287 CGAL::volume(remeshPoint(mesh, c[0]), remeshPoint(mesh, c[1]),
288 remeshPoint(mesh, c[2]), remeshPoint(mesh, c[3])));
289 minimum = std::min(minimum, 12. * std::pow(3. * volume, 2. / 3.) / sum);
290 }
291 return minimum;
292}
293
294// A membership class is not necessarily a manifold surface patch. Split it
295// along creases and isolate triangles at pinched classification vertices,
296// retaining the original class for publication after geometric validation.
297std::map<int, int> classifySurfacePatches(TetMeshData &mesh,
298 double crease_angle) {
299 std::map<RemeshEdge, std::vector<int>> edges;
300 std::map<std::pair<int, int>, std::vector<int>> vertex_faces;
301 for (size_t i = 0; i != mesh.boundary.size(); ++i) {
302 const auto &f = mesh.boundary[i];
303 for (int d = 0; d != 3; ++d) {
304 edges[simplexKey(RemeshEdge{f[d], f[(d + 1) % 3]})].push_back(i);
305 vertex_faces[{mesh.surfaceLabels[i], f[d]}].push_back(i);
306 }
307 }
308 std::set<int> isolated;
309 for (const auto &[key, incident] : vertex_faces) {
310 const int vertex = key.second;
311 std::map<int, std::vector<int>> link;
312 for (int i : incident) {
313 RemeshEdge opposite;
314 int n = 0;
315 for (int v : mesh.boundary[i])
316 if (v != vertex)
317 opposite[n++] = v;
318 if (n != 2)
319 THROW_MESSAGE("Invalid remeshing surface triangle");
320 link[opposite[0]].push_back(opposite[1]);
321 link[opposite[1]].push_back(opposite[0]);
322 }
323 bool pinched = false;
324 int ends = 0;
325 for (const auto &[v, adj] : link) {
326 ends += adj.size() == 1;
327 pinched |= adj.size() > 2;
328 }
329 std::set<int> reached;
330 std::vector<int> queue{link.begin()->first};
331 for (size_t i = 0; i != queue.size(); ++i)
332 if (reached.insert(queue[i]).second)
333 queue.insert(queue.end(), link.at(queue[i]).begin(),
334 link.at(queue[i]).end());
335 if (pinched || reached.size() != link.size() || (ends != 0 && ends != 2))
336 isolated.insert(incident.begin(), incident.end());
337 }
338 std::vector<std::vector<int>> neighbours(mesh.boundary.size());
339 const double cosine = std::cos(crease_angle * std::acos(-1.) / 180.);
340 auto normal = [&](int i) {
341 const auto &f = mesh.boundary[i];
342 return CGAL::cross_product(
343 remeshPoint(mesh, f[1]) - remeshPoint(mesh, f[0]),
344 remeshPoint(mesh, f[2]) - remeshPoint(mesh, f[0]));
345 };
346 for (const auto &[edge, incident] : edges) {
347 std::map<int, std::vector<int>> classes;
348 for (int i : incident)
349 classes[mesh.surfaceLabels[i]].push_back(i);
350 for (const auto &[label, faces] : classes) {
351 if (faces.size() != 2 || isolated.count(faces[0]) ||
352 isolated.count(faces[1]))
353 continue;
354 const auto a = normal(faces[0]), b = normal(faces[1]);
355 if (std::abs(CGAL::to_double(a * b)) <
356 cosine * std::sqrt(CGAL::to_double(a.squared_length() *
357 b.squared_length())))
358 continue;
359 neighbours[faces[0]].push_back(faces[1]);
360 neighbours[faces[1]].push_back(faces[0]);
361 }
362 }
363 std::vector<int> labels(mesh.boundary.size());
364 std::map<int, int> classes;
365 for (size_t seed = 0; seed != mesh.boundary.size(); ++seed) {
366 if (labels[seed])
367 continue;
368 const int patch = classes.size() + 1;
369 classes.emplace(patch, mesh.surfaceLabels[seed]);
370 std::vector<int> queue{static_cast<int>(seed)};
371 for (size_t i = 0; i != queue.size(); ++i) {
372 const int face = queue[i];
373 if (labels[face])
374 continue;
375 labels[face] = patch;
376 queue.insert(queue.end(), neighbours[face].begin(),
377 neighbours[face].end());
378 }
379 }
380 mesh.surfaceLabels = std::move(labels);
381 return classes;
382}
383#if CGAL_VERSION_NR >= 1060200000
384using Vb = CgalVertexBase<
385 RemeshKernel,
386 CGAL::Tetrahedral_remeshing::Remeshing_vertex_base_3<RemeshKernel>>;
387using Cb = RemeshCellBase<
388 CGAL::Tetrahedral_remeshing::Remeshing_cell_base_3<RemeshKernel>>;
389using Tr = CGAL::Triangulation_3<RemeshKernel,
390 CGAL::Triangulation_data_structure_3<Vb, Cb>>;
391using ExactKernel = CGAL::Exact_predicates_exact_constructions_kernel;
392using ExactVb =
393 CGAL::Conforming_constrained_Delaunay_triangulation_vertex_base_3<
394 ExactKernel,
395 CGAL::Tetrahedral_remeshing::Remeshing_vertex_base_3<ExactKernel>>;
396using ExactCb = CGAL::Conforming_constrained_Delaunay_triangulation_cell_base_3<
397 ExactKernel,
398 CGAL::Tetrahedral_remeshing::Remeshing_cell_base_3<ExactKernel>>;
399using ExactTr = CGAL::Triangulation_3<
400 ExactKernel, CGAL::Triangulation_data_structure_3<ExactVb, ExactCb>>;
401using CCDT =
402 CGAL::Conforming_constrained_Delaunay_triangulation_3<ExactKernel, ExactTr>;
403struct Region {
404 int material;
405 bool selected;
406 int sourceCell;
407};
408struct Constraint {
409 std::pair<int, int> regions;
410 int patch;
411};
412
413// Shared PLC recovery and source-region classification. Remeshing alone adds
414// sizing, movement and collapse; reconstruction can reject Steiner points here,
415// before exact coordinates are converted to the remeshing kernel.
416void constructConstrained(Tr &tr,
417 const std::vector<std::array<double, 3>> &coordinates,
418 const std::vector<std::vector<int>> &polygons,
419 const std::vector<Constraint> &constraints,
420 const std::vector<Region> &regions, bool strict) {
421 using CH = Tr::Cell_handle;
422 // Recover intersections and Steiner points exactly. Inexact recovery can
423 // create near-zero caps when a rounded midpoint is located off its edge.
424 std::vector<ExactKernel::Point_3> exact_points;
425 for (const auto &p : coordinates)
426 exact_points.emplace_back(p[0], p[1], p[2]);
427 auto ccdt = CGAL::make_conforming_constrained_Delaunay_triangulation_3<CCDT>(
428 exact_points, polygons);
429 if (strict) {
430 std::set<ExactKernel::Point_3> original(exact_points.begin(),
431 exact_points.end());
432 for (auto vertex : ccdt.finite_vertex_handles())
433 if (!original.erase(vertex->point()))
435 "CGAL constrained recovery required additional points; strict "
436 "reconstruction preserves exactly the source vertices and IDs");
437 if (!original.empty())
438 THROW_MESSAGE("Constrained recovery omitted a source vertex");
439 }
440 auto exact =
441 CGAL::Tetrahedral_remeshing::get_remeshing_triangulation(std::move(ccdt));
442 // CGAL's remesher uses double-valued constructions. Copy connectivity and
443 // facet identities, evaluating lazy exact values before conversion. Backend
444 // conversion is approximate; validate the resulting numerical embedding.
445 struct CopyVertex {
446 const ExactTr::Vertex *infinite;
447 Tr::Vertex operator()(const ExactTr::Vertex &) const { return {}; }
448 void operator()(const ExactTr::Vertex &from, Tr::Vertex &to) const {
449 if (&from != infinite) {
450 const auto &p = from.point();
451 to.set_point(RemeshPoint(CGAL::to_double(CGAL::exact(p.x())),
452 CGAL::to_double(CGAL::exact(p.y())),
453 CGAL::to_double(CGAL::exact(p.z()))));
454 }
455 }
456 };
457 struct CopyCell {
458 Tr::Cell operator()(const ExactTr::Cell &) const { return {}; }
459 void operator()(const ExactTr::Cell &from, Tr::Cell &to) const {
460 for (int d = 0; d != 4; ++d)
461 to.set_surface_patch_index(d, from.surface_patch_index(d));
462 }
463 };
464 tr.set_infinite_vertex(
465 tr.tds().copy_tds(exact.tds(), exact.infinite_vertex(),
466 CopyVertex{&*exact.infinite_vertex()}, CopyCell{}));
467 if (!tr.is_valid())
468 THROW_MESSAGE("Invalid constrained triangulation");
469
470 // Flood components without crossing constraints, then propagate source
471 // region pairs from the exterior. Open crack sheets can have the same
472 // material on both sides; cavity parity is never used as a material ID.
473 std::map<CH, int> components;
474 int component_count = 0;
475 for (auto seed : tr.all_cell_handles()) {
476 if (components.count(seed))
477 continue;
478 const int component = component_count++;
479 std::vector<CH> queue{seed};
480 for (size_t i = 0; i != queue.size(); ++i) {
481 const auto cell = queue[i];
482 if (!components.emplace(cell, component).second)
483 continue;
484 for (int d = 0; d != 4; ++d)
485 if (!cell->is_facet_on_surface(d))
486 queue.push_back(cell->neighbor(d));
487 }
488 }
489 struct Transition {
490 int component;
491 std::pair<int, int> regions;
492 };
493 std::vector<std::vector<Transition>> graph(component_count);
494 for (auto f : tr.finite_facets()) {
495 const int index = f.first->surface_patch_index(f.second);
496 if (!index)
497 continue;
498 const auto &constraint = constraints.at(index - 1);
499 const auto other = tr.mirror_facet(f);
500 const int a = components.at(f.first), b = components.at(other.first);
501 graph[a].push_back({b, constraint.regions});
502 graph[b].push_back({a, constraint.regions});
503 }
504 std::vector<int> component_regions(component_count, -1);
505 const int exterior = components.at(tr.infinite_cell());
506 component_regions[exterior] = 0;
507 std::vector<int> queue{exterior};
508 for (size_t i = 0; i != queue.size(); ++i) {
509 const int component = queue[i], region = component_regions[component];
510 for (const auto &edge : graph[component]) {
511 const auto [a, b] = edge.regions;
512 if (region != a && region != b)
513 THROW_MESSAGE("Inconsistent constrained source region boundary");
514 const int next = region == a ? b : a;
515 if (component_regions[edge.component] == -1) {
516 component_regions[edge.component] = next;
517 queue.push_back(edge.component);
518 } else if (component_regions[edge.component] != next)
519 THROW_MESSAGE("Ambiguous constrained source region classification");
520 }
521 }
522 std::vector<size_t> region_cell_counts(regions.size());
523 for (auto c : tr.finite_cell_handles()) {
524 const int region = component_regions.at(components.at(c));
525 if (region >= 0)
526 ++region_cell_counts.at(region);
527 }
528 for (auto c : tr.all_cell_handles()) {
529 const int region = component_regions.at(components.at(c));
530 if (region < 0)
531 THROW_MESSAGE("Unclassified constrained component");
532 c->set_subdomain_index(regions.at(region).material);
533 // A recovered source tetrahedron may have been subdivided to match a
534 // refined facet. Improve those children too, within its fixed support.
535 c->selected = regions.at(region).selected ||
536 (region != 0 && region_cell_counts.at(region) > 1);
537 }
538}
539// Group only exact planar, equally classified facets. Simple patches become
540// PLC polygons only when all source vertices stay on the polygon boundary.
541// More complex patches use local pairs or individual triangles.
542std::vector<std::vector<int>>
543planarConstraintGroups(const TetMeshData &source, const RemeshFaces &faces,
544 const std::set<RemeshEdge> &protected_edges) {
545 std::map<RemeshEdge, std::vector<int>> incident;
546 for (size_t i = 0; i != source.boundary.size(); ++i)
547 for (int d = 0; d != 3; ++d)
548 incident[simplexKey(RemeshEdge{source.boundary[i][d],
549 source.boundary[i][(d + 1) % 3]})]
550 .push_back(i);
551 std::vector<std::vector<int>> neighbours(source.boundary.size());
552 for (const auto &[edge, adjacent] : incident) {
553 if (adjacent.size() != 2 || protected_edges.count(edge))
554 continue;
555 const int a = adjacent[0], b = adjacent[1];
556 if (source.surfaceLabels[a] != source.surfaceLabels[b] ||
557 faces.at(simplexKey(source.boundary[a])).size() !=
558 faces.at(simplexKey(source.boundary[b])).size())
559 continue;
560 const auto &f = source.boundary[a];
561 if (!std::all_of(source.boundary[b].begin(), source.boundary[b].end(),
562 [&](int v) {
563 return CGAL::coplanar(
564 remeshPoint(source, f[0]), remeshPoint(source, f[1]),
565 remeshPoint(source, f[2]), remeshPoint(source, v));
566 }))
567 continue;
568 neighbours[a].push_back(b);
569 neighbours[b].push_back(a);
570 }
571 std::vector<bool> visited(source.boundary.size());
572 std::vector<std::vector<int>> groups;
573 for (size_t seed = 0; seed != visited.size(); ++seed) {
574 if (visited[seed])
575 continue;
576 std::vector<int> group{int(seed)};
577 visited[seed] = true;
578 for (size_t i = 0; i != group.size(); ++i)
579 for (int next : neighbours[group[i]])
580 if (!visited[next]) {
581 visited[next] = true;
582 group.push_back(next);
583 }
584 groups.push_back(std::move(group));
585 }
586 return groups;
587}
588
589std::vector<int> reconstructConstrained(TetMeshData &result,
590 const TetMeshData &source) {
591 if (source.cells.empty() || source.vertexIds.size() != source.points.size() ||
592 source.surfaceLabels.size() != source.boundary.size() ||
593 (!source.cellLabels.empty() &&
594 source.cellLabels.size() != source.cells.size()))
595 THROW_MESSAGE("Invalid constrained reconstruction arrays");
596 std::set<int> ids;
597 std::set<RemeshPoint> coordinates;
598 for (size_t i = 0; i != source.points.size(); ++i) {
599 for (double x : source.points[i])
600 if (!std::isfinite(x))
601 THROW_MESSAGE("Non-finite reconstruction coordinate");
602 if (source.vertexIds[i] <= 0 || !ids.insert(source.vertexIds[i]).second ||
603 !coordinates.insert(remeshPoint(source, i)).second)
604 THROW_MESSAGE("Reconstruction requires unique IDs and coordinates");
605 }
606 TetMeshData input = source;
607 for (auto &cell : input.cells) {
608 for (int v : cell)
609 if (v < 0 || size_t(v) >= source.points.size())
610 THROW_MESSAGE("Invalid reconstruction cell index");
611 if (CGAL::orientation(remeshPoint(input, cell[0]),
612 remeshPoint(input, cell[1]),
613 remeshPoint(input, cell[2]),
614 remeshPoint(input, cell[3])) == CGAL::NEGATIVE)
615 std::swap(cell[0], cell[1]);
616 }
617 const auto faces = remeshFaces(input);
618 const int material =
619 source.cellLabels.empty() ? 1 : source.cellLabels.front();
620 if (material <= 0 ||
621 std::any_of(source.cellLabels.begin(), source.cellLabels.end(),
622 [&](int label) { return label != material; }))
623 THROW_MESSAGE("Reconstruction requires uniform volume classification");
624 std::map<RemeshFace, int> protected_faces;
625 for (size_t i = 0; i != source.boundary.size(); ++i)
626 if (!faces.count(simplexKey(source.boundary[i])) ||
627 source.surfaceLabels[i] <= 0 ||
628 !protected_faces.emplace(simplexKey(source.boundary[i]), i).second)
629 THROW_MESSAGE("Invalid protected reconstruction facet");
630 for (const auto &[face, adjacent] : faces)
631 if (adjacent.size() == 1 && !protected_faces.count(face))
633 "Constrained reconstruction requires the complete exterior");
634 std::set<RemeshEdge> source_edges, protected_edges;
635 for (const auto &cell : source.cells)
636 for (int i = 0; i != 4; ++i)
637 for (int j = 0; j != i; ++j)
638 source_edges.insert(simplexKey(RemeshEdge{cell[i], cell[j]}));
639 for (auto edge : source.featureEdges) {
640 edge = simplexKey(edge);
641 if (!source_edges.count(edge))
642 THROW_MESSAGE("Protected curve is not a source edge");
643 protected_edges.insert(edge);
644 }
645 std::vector<RemeshPoint> points;
646 for (size_t i = 0; i != source.points.size(); ++i)
647 points.push_back(remeshPoint(source, i));
648 if (CGAL::Polygon_mesh_processing::does_polygon_soup_self_intersect(
649 points, source.boundary))
650 THROW_MESSAGE("Protected reconstruction surfaces self-intersect");
651
652 std::map<RemeshEdge, std::vector<int>> surface_edge_faces;
653 for (size_t i = 0; i != source.boundary.size(); ++i) {
654 const auto &face = source.boundary[i];
655 for (int d = 0; d != 3; ++d)
656 surface_edge_faces[simplexKey(RemeshEdge{face[d], face[(d + 1) % 3]})]
657 .push_back(i);
658 }
659 std::vector<std::vector<int>> polygons, carriers;
660 std::vector<Constraint> constraints;
661 auto append = [&](const std::vector<int> &polygon,
662 const std::vector<int> &parents,
663 std::pair<int, int> regions) {
664 polygons.push_back(polygon);
665 carriers.push_back(parents);
666 constraints.push_back({regions, int(polygons.size())});
667 };
668 for (const auto &group :
669 planarConstraintGroups(source, faces, protected_edges)) {
670 std::map<RemeshEdge, int> counts;
671 for (int i : group)
672 for (int d = 0; d != 3; ++d)
673 ++counts[simplexKey(RemeshEdge{source.boundary[i][d],
674 source.boundary[i][(d + 1) % 3]})];
675 std::map<int, std::vector<int>> boundary;
676 bool simple = true;
677 for (const auto &[edge, count] : counts) {
678 if (count == 1) {
679 boundary[edge[0]].push_back(edge[1]);
680 boundary[edge[1]].push_back(edge[0]);
681 } else if (count != 2 || protected_edges.count(edge) ||
682 surface_edge_faces.at(edge).size() != 2)
683 simple = false;
684 }
685 // The soup constructor inserts every 3D point, but its face recovery sees
686 // polygon boundary vertices only. An omitted patch-interior vertex can
687 // make recovery repeatedly request a facet spanning that existing point.
688 for (int i : group)
689 for (int vertex : source.boundary[i])
690 simple &= boundary.count(vertex) != 0;
691 for (const auto &[vertex, neighbours] : boundary)
692 simple &= neighbours.size() == 2;
693 std::vector<int> polygon;
694 if (simple && !boundary.empty()) {
695 int previous = -1, vertex = boundary.begin()->first;
696 do {
697 polygon.push_back(vertex);
698 const auto &adjacent = boundary.at(vertex);
699 const int next = adjacent[0] == previous ? adjacent[1] : adjacent[0];
700 previous = vertex;
701 vertex = next;
702 } while (vertex != polygon.front() && polygon.size() <= boundary.size());
703 simple &= polygon.size() == boundary.size();
704 } else
705 simple = false;
706 const auto regions =
707 faces.at(simplexKey(source.boundary[group.front()])).size() == 1
708 ? std::make_pair(0, 1)
709 : std::make_pair(1, 1);
710 if (simple)
711 append(polygon, group, regions);
712 else {
713 // Local pairs allow flips while keeping every source vertex on a PLC
714 // boundary. Never remove a crack junction, explicit curve or patch seam.
715 std::set<int> remaining(group.begin(), group.end());
716 for (int i : group) {
717 if (!remaining.erase(i))
718 continue;
719 const auto &face = source.boundary[i];
720 int other = -1;
721 for (int d = 0; d != 3; ++d) {
722 const RemeshEdge edge =
723 simplexKey(RemeshEdge{face[d], face[(d + 1) % 3]});
724 const auto &incident = surface_edge_faces.at(edge);
725 if (incident.size() != 2 || protected_edges.count(edge))
726 continue;
727 const int j = incident[0] == i ? incident[1] : incident[0];
728 if (!remaining.count(j))
729 continue;
730 const auto &next = source.boundary[j];
731 const auto unique =
732 std::find_if(next.begin(), next.end(),
733 [&](int v) { return v != edge[0] && v != edge[1]; });
734 append({face[(d + 2) % 3], edge[0], *unique, edge[1]}, {i, j},
735 regions);
736 remaining.erase(j);
737 other = j;
738 break;
739 }
740 if (other < 0)
741 append({face.begin(), face.end()}, {i}, regions);
742 }
743 }
744 }
745 // A standalone interior curve needs a supporting PLC triangle. Its support
746 // is auxiliary and does not acquire a physical surface classification.
747 for (const auto &edge : protected_edges) {
748 const auto supported =
749 std::any_of(polygons.begin(), polygons.end(), [&](const auto &p) {
750 for (size_t d = 0; d != p.size(); ++d)
751 if (simplexKey(RemeshEdge{p[d], p[(d + 1) % p.size()]}) == edge)
752 return true;
753 return false;
754 });
755 if (!supported) {
756 const auto found =
757 std::find_if(faces.begin(), faces.end(), [&](const auto &entry) {
758 return std::find(entry.first.begin(), entry.first.end(), edge[0]) !=
759 entry.first.end() &&
760 std::find(entry.first.begin(), entry.first.end(), edge[1]) !=
761 entry.first.end();
762 });
763 if (!protected_faces.count(found->first))
764 append({found->first.begin(), found->first.end()}, {}, {1, 1});
765 }
766 }
767 // Include auxiliary support in the PLC intersection check too.
768 std::vector<RemeshFace> plc = source.boundary;
769 for (size_t i = 0; i != carriers.size(); ++i)
770 if (carriers[i].empty())
771 plc.push_back({polygons[i][0], polygons[i][1], polygons[i][2]});
772 if (CGAL::Polygon_mesh_processing::does_polygon_soup_self_intersect(points,
773 plc))
774 THROW_MESSAGE("Protected curve support cannot form a valid PLC");
775 Tr tr;
776 constructConstrained(tr, source.points, polygons, constraints,
777 {{0, false, -1}, {material, false, -1}}, true);
778 std::map<RemeshPoint, int> indices;
779 for (size_t i = 0; i != points.size(); ++i)
780 indices.emplace(points[i], i);
781 auto index = [&](Tr::Vertex_handle vertex) {
782 return indices.at(vertex->point());
783 };
784 TetMeshData next;
785 next.points = source.points;
786 next.vertexIds = source.vertexIds;
787 std::set<int> used;
788 std::set<RemeshEdge> output_edges;
789 for (auto cell : tr.finite_cell_handles())
790 if (cell->subdomain_index()) {
791 std::array<int, 4> conn;
792 for (int d = 0; d != 4; ++d)
793 conn[d] = index(cell->vertex(d));
794 next.cells.push_back(conn);
795 next.cellLabels.push_back(material);
796 used.insert(conn.begin(), conn.end());
797 for (int i = 0; i != 4; ++i)
798 for (int j = 0; j != i; ++j)
799 output_edges.insert(simplexKey(RemeshEdge{conn[i], conn[j]}));
800 }
801 if (used.size() != source.points.size())
802 THROW_MESSAGE("Physical reconstruction omitted a source vertex");
803 for (const auto &edge : protected_edges)
804 if (!output_edges.count(edge))
805 THROW_MESSAGE("Constrained recovery lost a protected curve");
806 std::vector<ExactKernel::Point_3> exact;
807 for (const auto &p : source.points)
808 exact.emplace_back(p[0], p[1], p[2]);
809 auto identity = [&](int i) {
810 auto key = source.boundary[i];
811 for (auto &v : key)
812 v = source.vertexIds[v];
813 return simplexKey(key);
814 };
815 std::vector<Triangles> patch_triangles(carriers.size());
816 std::vector<std::unique_ptr<TriangleTree>> patch_trees(carriers.size());
817 for (size_t i = 0; i != carriers.size(); ++i) {
818 auto &triangles = patch_triangles[i];
819 for (int parent : carriers[i]) {
820 const auto &f = source.boundary[parent];
821 triangles.emplace_back(points[f[0]], points[f[1]], points[f[2]]);
822 }
823 if (triangles.size() > 1)
824 patch_trees[i] =
825 std::make_unique<TriangleTree>(triangles.cbegin(), triangles.cend());
826 }
827 TetMeshData before = source, after = next;
828 before.boundary.clear();
829 before.surfaceLabels.clear();
830 std::vector<int> parents;
831 for (auto facet : tr.finite_facets()) {
832 const int id = facet.first->surface_patch_index(facet.second);
833 if (!id || carriers.at(id - 1).empty())
834 continue;
835 if (!facet.first->subdomain_index() &&
836 !facet.first->neighbor(facet.second)->subdomain_index())
837 THROW_MESSAGE("A protected surface lies outside the physical domain");
838 RemeshFace face;
839 int n = 0;
840 for (int d = 0; d != 4; ++d)
841 if (d != facet.second)
842 face[n++] = index(facet.first->vertex(d));
843 const auto centre =
844 CGAL::centroid(exact[face[0]], exact[face[1]], exact[face[2]]);
845 // The exact centroid's interval box only filters candidates. Final
846 // containment and GID tie-breaking remain exact and deterministic.
847 const auto &triangles = patch_triangles.at(id - 1);
848 std::vector<Triangles::const_iterator> hits;
849 if (triangles.size() == 1)
850 hits.push_back(triangles.cbegin());
851 else {
852 const auto box = centre.bbox();
853 const RemeshKernel::Iso_cuboid_3 bounds(box.xmin(), box.ymin(),
854 box.zmin(), box.xmax(),
855 box.ymax(), box.zmax());
856 patch_trees[id - 1]->all_intersected_primitives(bounds,
857 std::back_inserter(hits));
858 }
859 int parent = -1;
860 for (auto hit : hits) {
861 const int i = carriers[id - 1][hit - triangles.cbegin()];
862 const auto &f = source.boundary[i];
863 if (ExactKernel::Triangle_3(exact[f[0]], exact[f[1]], exact[f[2]])
864 .has_on(centre) &&
865 (parent < 0 || identity(i) < identity(parent)))
866 parent = i;
867 }
868 if (parent < 0)
869 THROW_MESSAGE("A recovered facet leaves its exact source patch");
870 const auto &f = source.boundary[parent];
871 if (CGAL::cross_product(exact[face[1]] - exact[face[0]],
872 exact[face[2]] - exact[face[0]]) *
873 CGAL::cross_product(exact[f[1]] - exact[f[0]],
874 exact[f[2]] - exact[f[0]]) <
875 0)
876 std::swap(face[1], face[2]);
877 next.boundary.push_back(face);
878 next.surfaceLabels.push_back(source.surfaceLabels[parent]);
879 after.boundary.push_back(face);
880 after.surfaceLabels.push_back(id);
881 parents.push_back(parent);
882 }
883 for (size_t i = 0; i != carriers.size(); ++i)
884 for (int parent : carriers[i]) {
885 before.boundary.push_back(source.boundary[parent]);
886 before.surfaceLabels.push_back(i + 1);
887 }
888 // Per-PLC-polygon topology and node sets catch holes without relying on area
889 // tolerance. Exact constraint recovery establishes the geometric support.
890 if (patchTopology(before) != patchTopology(after))
891 THROW_MESSAGE("Constrained recovery changes protected patch topology");
892 auto nodes = [](const TetMeshData &mesh) {
893 std::map<int, std::set<int>> result;
894 for (size_t i = 0; i != mesh.boundary.size(); ++i)
895 result[mesh.surfaceLabels[i]].insert(mesh.boundary[i].begin(),
896 mesh.boundary[i].end());
897 return result;
898 };
899 if (nodes(before) != nodes(after))
900 THROW_MESSAGE("Constrained recovery changes protected patch nodes");
901 remeshFaces(next);
902 auto volume = [&](const TetMeshData &mesh) {
903 // Accumulate evaluated rationals without a mesh-sized lazy expression.
904 auto total = CGAL::exact(ExactKernel::FT(0));
905 for (const auto &cell : mesh.cells)
906 total += CGAL::exact(CGAL::volume(exact[cell[0]], exact[cell[1]],
907 exact[cell[2]], exact[cell[3]]));
908 return total;
909 };
910 if (volume(input) != volume(next))
911 THROW_MESSAGE("Constrained reconstruction changes the source volume");
912 next.featureEdges = source.featureEdges;
913 next.edgeLabels = source.edgeLabels;
914 next.fixedVertices = source.fixedVertices;
915 result = std::move(next);
916 return parents;
917}
918
919#endif
920} // namespace
921
922void CGALTools::remesh(TetMeshData &result, const TetMeshData &source,
923 const std::vector<int> &selected_cells,
925 RemeshReport &report) const {
926#if CGAL_VERSION_NR < 1060200000
927 THROW_MESSAGE("Constrained tetrahedral remeshing requires CGAL 6.2");
928#else
929 const bool optimise = settings.targetEdgeLength > 0;
930 if (!std::isfinite(settings.targetEdgeLength) ||
931 settings.targetEdgeLength < 0 || (optimise && settings.iterations == 0) ||
932 !std::isfinite(settings.creaseAngle) || settings.creaseAngle < 0 ||
933 settings.creaseAngle > 90 ||
934 !std::isfinite(settings.relativeSurfaceTolerance) ||
935 settings.relativeSurfaceTolerance <= 0 ||
936 !std::isfinite(settings.minimumQuality) || settings.minimumQuality < 0 ||
937 settings.minimumQuality > 1)
938 THROW_MESSAGE("Invalid tetrahedral remeshing settings");
939 if (source.cells.empty() || source.vertexIds.size() != source.points.size() ||
940 (!source.cellLabels.empty() &&
941 source.cellLabels.size() != source.cells.size()) ||
942 source.surfaceLabels.size() != source.boundary.size() ||
943 source.edgeLabels.size() != source.featureEdges.size())
944 THROW_MESSAGE("Invalid remeshing arrays");
945 std::set<int> ids;
946 std::set<RemeshPoint> coordinates;
947 for (size_t i = 0; i != source.points.size(); ++i) {
948 for (double x : source.points[i])
949 if (!std::isfinite(x))
950 THROW_MESSAGE("Non-finite remeshing coordinate");
951 if (source.vertexIds[i] <= 0 || !ids.insert(source.vertexIds[i]).second ||
952 !coordinates.insert(remeshPoint(source, i)).second)
953 THROW_MESSAGE("Remeshing requires unique vertex IDs and coordinates");
954 }
955 TetMeshData input = source;
956 input.partitions.clear(); // Partition inheritance is a separate operation.
957 if (input.cellLabels.empty())
958 input.cellLabels.assign(input.cells.size(), 1);
959 for (int label : input.cellLabels)
960 if (label <= 0)
961 THROW_MESSAGE("Physical remeshing cell labels must be positive");
962 // MOAB does not require a particular corner ordering.
963 for (auto &c : input.cells) {
964 for (int v : c)
965 if (v < 0 || static_cast<size_t>(v) >= input.points.size())
966 THROW_MESSAGE("Invalid remeshing vertex index");
967 if (CGAL::orientation(remeshPoint(input, c[0]), remeshPoint(input, c[1]),
968 remeshPoint(input, c[2]),
969 remeshPoint(input, c[3])) == CGAL::NEGATIVE)
970 std::swap(c[0], c[1]);
971 }
972 const auto faces = remeshFaces(input, false);
973 std::set<RemeshEdge> cell_edges;
974 std::set<int> used_vertices;
975 for (const auto &c : input.cells) {
976 used_vertices.insert(c.begin(), c.end());
977 for (int i = 0; i != 4; ++i)
978 for (int j = 0; j != i; ++j)
979 cell_edges.insert(simplexKey(RemeshEdge{c[i], c[j]}));
980 }
981 if (used_vertices.size() != input.points.size())
982 THROW_MESSAGE("Remeshing source contains unused vertices");
983 for (size_t i = 0; i != input.featureEdges.size(); ++i)
984 if (!cell_edges.count(simplexKey(input.featureEdges[i])) ||
985 input.edgeLabels[i] <= 0)
986 THROW_MESSAGE("Invalid remeshing feature edge or label");
987 for (int i : input.fixedVertices)
988 if (!used_vertices.count(i))
989 THROW_MESSAGE("Invalid fixed remeshing vertex");
990 std::set<int> selected;
991 for (int i : selected_cells) {
992 if (i < 0 || static_cast<size_t>(i) >= input.cells.size())
993 THROW_MESSAGE("Selected remeshing cell is outside source");
994 selected.insert(i);
995 }
996 // Repair only the overlapping neighbourhood reached by the requested
997 // selection. Unrelated invalid cells remain an explicit input error.
998 bool expanded;
999 do {
1000 expanded = false;
1001 for (const auto &[face, adjacent] : faces) {
1002 if (adjacent.size() != 2)
1003 continue;
1004 int sides[2];
1005 for (int d = 0; d != 2; ++d) {
1006 const auto &cell = input.cells[adjacent[d]];
1007 const int opposite =
1008 *std::find_if(cell.begin(), cell.end(), [&](int v) {
1009 return std::find(face.begin(), face.end(), v) == face.end();
1010 });
1011 sides[d] = CGAL::orientation(
1012 remeshPoint(input, face[0]), remeshPoint(input, face[1]),
1013 remeshPoint(input, face[2]), remeshPoint(input, opposite));
1014 }
1015 if (sides[0] == sides[1] &&
1016 (selected.count(adjacent[0]) || selected.count(adjacent[1]))) {
1017 expanded |= selected.insert(adjacent[0]).second;
1018 expanded |= selected.insert(adjacent[1]).second;
1019 }
1020 }
1021 } while (expanded);
1022 int max_label = 0;
1023 std::map<RemeshFace, int> patches;
1024 for (size_t i = 0; i != input.boundary.size(); ++i) {
1025 const auto f = simplexKey(input.boundary[i]);
1026 if (!faces.count(f) || input.surfaceLabels[i] <= 0 ||
1027 !patches.emplace(f, input.surfaceLabels[i]).second)
1028 THROW_MESSAGE("Invalid remeshing surface facet or label");
1029 max_label = std::max(max_label, input.surfaceLabels[i]);
1030 }
1031 std::map<std::pair<int, int>, int> inferred;
1032 for (const auto &[f, adjacent] : faces) {
1033 const int a = input.cellLabels[adjacent[0]];
1034 const int b = adjacent.size() == 2 ? input.cellLabels[adjacent[1]] : 0;
1035 if ((a != b || adjacent.size() == 1) && !patches.count(f)) {
1036 const auto pair = std::minmax(a, b);
1037 const auto [it, added] = inferred.emplace(pair, max_label + 1);
1038 if (added)
1039 ++max_label;
1040 patches.emplace(f, it->second);
1041 input.boundary.push_back(f);
1042 input.surfaceLabels.push_back(it->second);
1043 }
1044 }
1045 // Keep physical patch boundaries (including crack fronts) at their source
1046 // vertices. A constrained edge may still collapse in CGAL, cutting across a
1047 // corner. Derive these before crease splitting, so interior surface edges
1048 // remain free to coarsen. Reuse fixedVertices for constraint and output checks.
1049 std::map<std::pair<int, RemeshEdge>, unsigned> boundary_edges;
1050 for (size_t i = 0; i != input.boundary.size(); ++i)
1051 for (int d = 0; d != 3; ++d)
1052 ++boundary_edges[{
1053 input.surfaceLabels[i],
1054 simplexKey(RemeshEdge{input.boundary[i][d],
1055 input.boundary[i][(d + 1) % 3]})}];
1056 std::set<int> fixed_vertices(input.fixedVertices.begin(),
1057 input.fixedVertices.end());
1058 for (const auto &[key, count] : boundary_edges)
1059 if (count == 1)
1060 fixed_vertices.insert(key.second.begin(), key.second.end());
1061 input.fixedVertices.assign(fixed_vertices.begin(), fixed_vertices.end());
1062
1063 const auto surface_classes =
1064 classifySurfacePatches(input, settings.creaseAngle);
1065 patches.clear();
1066 for (size_t i = 0; i != input.boundary.size(); ++i)
1067 patches.emplace(simplexKey(input.boundary[i]), input.surfaceLabels[i]);
1068 max_label = surface_classes.size();
1069 const auto topology = patchTopology(input);
1070 std::set<int> auxiliary_labels;
1071 std::set<RemeshEdge> auxiliary_edges;
1072 std::set<int> auxiliary_vertices;
1073 RemeshReport next_report;
1074 next_report.minQualityBefore = remeshQuality(input);
1075 if (selected.empty()) {
1076 next_report.minQualityAfter = next_report.minQualityBefore;
1077 for (auto &label : input.surfaceLabels)
1078 label = surface_classes.at(label);
1079 result = std::move(input);
1080 report = std::move(next_report);
1081 return;
1082 }
1083 using VH = Tr::Vertex_handle;
1084 std::vector<RemeshPoint> points;
1085 for (size_t i = 0; i != input.points.size(); ++i)
1086 points.push_back(remeshPoint(input, i));
1087
1088 double scale = 0;
1089 for (const auto &p : points)
1090 scale = std::max(scale, std::sqrt(CGAL::to_double(
1091 CGAL::squared_distance(p, points.front()))));
1092 const double tolerance2 =
1093 std::pow(settings.relativeSurfaceTolerance * scale, 2);
1094
1095 // Each unselected source tetrahedron is a separate construction region.
1096 // Its faces survive recovery; only conforming subdivision can change it.
1097 std::vector<Region> regions;
1098 std::vector<std::vector<int>> polygons;
1099 std::vector<Constraint> constraints;
1100 for (;;) {
1101 regions = {{0, false, -1}};
1102 polygons.clear();
1103 constraints.clear();
1104 max_label = surface_classes.size();
1105 auxiliary_labels.clear();
1106 auxiliary_edges.clear();
1107 std::map<std::pair<int, int>, int> region_ids;
1108 std::vector<int> cell_regions;
1109 for (size_t i = 0; i != input.cells.size(); ++i) {
1110 const bool active = selected.count(i);
1111 const auto key =
1112 std::make_pair(input.cellLabels[i], active ? -1 : int(i));
1113 auto [it, added] = region_ids.emplace(key, regions.size());
1114 if (added)
1115 regions.push_back({input.cellLabels[i], active, active ? -1 : int(i)});
1116 cell_regions.push_back(it->second);
1117 }
1118 auto add_constraint = [&](const RemeshFace &face,
1119 const std::vector<int> &adjacent, int patch) {
1120 const int a = cell_regions[adjacent[0]],
1121 b = adjacent.size() == 2 ? cell_regions[adjacent[1]] : 0;
1122 if (!patch) {
1123 patch = ++max_label;
1124 auxiliary_labels.insert(patch);
1125 for (int d = 0; d != 3; ++d)
1126 auxiliary_edges.insert(
1127 simplexKey(RemeshEdge{face[d], face[(d + 1) % 3]}));
1128 }
1129 polygons.emplace_back(face.begin(), face.end());
1130 constraints.push_back({std::minmax(a, b), patch});
1131 };
1132 std::set<RemeshEdge> constrained_source_edges;
1133 for (const auto &[face, adjacent] : faces) {
1134 const int a = cell_regions[adjacent[0]],
1135 b = adjacent.size() == 2 ? cell_regions[adjacent[1]] : 0;
1136 if (patches.count(face) || a != b) {
1137 add_constraint(face, adjacent,
1138 patches.count(face) ? patches.at(face) : 0);
1139 for (int d = 0; d != 3; ++d)
1140 constrained_source_edges.insert(
1141 simplexKey(RemeshEdge{face[d], face[(d + 1) % 3]}));
1142 }
1143 // A folded selection boundary is not a valid PLC. Require its entire
1144 // affected neighbourhood to be selected before replacing the old cells.
1145 if (adjacent.size() == 2 &&
1146 (!selected.count(adjacent[0]) || !selected.count(adjacent[1]))) {
1147 int sides[2];
1148 for (int d = 0; d != 2; ++d) {
1149 const auto &cell = input.cells[adjacent[d]];
1150 const int opposite =
1151 *std::find_if(cell.begin(), cell.end(), [&](int v) {
1152 return std::find(face.begin(), face.end(), v) == face.end();
1153 });
1154 sides[d] = CGAL::orientation(points[face[0]], points[face[1]],
1155 points[face[2]], points[opposite]);
1156 }
1157 if (sides[0] == sides[1])
1158 THROW_MESSAGE("Overlapping source cells touch unselected "
1159 "cells; expand the selection");
1160 }
1161 }
1162 // An isolated protected curve needs an incident facet in the PLC too.
1163 for (const auto &edge : input.featureEdges)
1164 if (!constrained_source_edges.count(simplexKey(edge))) {
1165 const auto found =
1166 std::find_if(faces.begin(), faces.end(), [&](const auto &entry) {
1167 return std::find(entry.first.begin(), entry.first.end(),
1168 edge[0]) != entry.first.end() &&
1169 std::find(entry.first.begin(), entry.first.end(),
1170 edge[1]) != entry.first.end();
1171 });
1172 add_constraint(found->first, found->second, 0);
1173 for (int d = 0; d != 3; ++d)
1174 constrained_source_edges.insert(simplexKey(
1175 RemeshEdge{found->first[d], found->first[(d + 1) % 3]}));
1176 }
1177 std::vector<std::pair<size_t, size_t>> intersections;
1178 CGAL::Polygon_mesh_processing::triangle_soup_self_intersections(
1179 points, polygons, std::back_inserter(intersections));
1180 if (intersections.empty())
1181 break;
1182 const auto previous = selected.size();
1183 for (const auto &[a, b] : intersections) {
1184 if (!auxiliary_labels.count(constraints[a].patch) &&
1185 !auxiliary_labels.count(constraints[b].patch))
1186 THROW_MESSAGE("Physical remeshing surfaces self-intersect");
1187 for (auto index : {a, b}) {
1188 if (!auxiliary_labels.count(constraints[index].patch))
1189 continue;
1190 for (int region : {constraints[index].regions.first,
1191 constraints[index].regions.second}) {
1192 const auto source_cell = regions[region].sourceCell;
1193 if (source_cell >= 0)
1194 selected.insert(source_cell);
1195 }
1196 }
1197 }
1198 if (selected.size() == previous)
1200 "Protected curve support cannot form a valid remeshing PLC");
1201 // Removing intersecting auxiliary faces grows the selected cavity while
1202 // leaving physical/CRACK constraints intact. Progress is bounded by input cells.
1203 }
1204 Tr tr;
1205 constructConstrained(tr, input.points, polygons, constraints, regions, false);
1206 std::map<RemeshPoint, int> point_indices;
1207 for (size_t i = 0; i != points.size(); ++i)
1208 point_indices.emplace(points[i], i);
1209 for (auto v : tr.finite_vertex_handles()) {
1210 const auto found = point_indices.find(v->point());
1211 v->moabHandle = found == point_indices.end() ? 0 : found->second + 1;
1212 // Remeshing recomputes patch/curve incidence from our classifications.
1213 v->set_dimension(3);
1214 }
1215 std::set<VH> fixed_support;
1216 for (auto f : tr.finite_facets()) {
1217 const int index = f.first->surface_patch_index(f.second);
1218 if (!index)
1219 continue;
1220 const int patch = constraints.at(index - 1).patch;
1221 f.first->set_surface_patch_index(f.second, patch);
1222 const auto other = tr.mirror_facet(f);
1223 other.first->set_surface_patch_index(other.second, patch);
1224 if (auxiliary_labels.count(patch))
1225 for (int d = 0; d != 4; ++d)
1226 if (d != f.second) {
1227 auto v = f.first->vertex(d);
1228 if (v->moabHandle) {
1229 fixed_support.insert(v);
1230 auxiliary_vertices.insert(v->moabHandle - 1);
1231 }
1232 }
1233 }
1234 // classifyVerts: patch incidence, open-sheet fronts and creases are derived
1235 // from CGAL topology, independently of the MOAB bridge and material names.
1236 std::map<RemeshEdge, std::vector<int>> edge_faces;
1237 for (size_t i = 0; i != input.boundary.size(); ++i)
1238 for (int d = 0; d != 3; ++d)
1239 edge_faces[simplexKey(RemeshEdge{input.boundary[i][d],
1240 input.boundary[i][(d + 1) % 3]})]
1241 .push_back(i);
1242 std::set<RemeshEdge> feature_edges;
1243 // Splits update both sides of this artificial interface. Its fixed support
1244 // prevents global projection from moving vertices onto a nearby crack sheet.
1245 feature_edges.insert(auxiliary_edges.begin(), auxiliary_edges.end());
1246 for (const auto &e : input.featureEdges) {
1247 if (e[0] < 0 || e[1] < 0 || e[0] == e[1] ||
1248 static_cast<size_t>(std::max(e[0], e[1])) >= points.size())
1249 THROW_MESSAGE("Invalid remeshing feature edge");
1250 feature_edges.insert(simplexKey(e));
1251 }
1252 const double cosine = std::cos(settings.creaseAngle * std::acos(-1.) / 180.);
1253 for (const auto &[edge, incident] : edge_faces) {
1254 bool feature = incident.size() != 2;
1255 if (!feature) {
1256 const auto &a = input.boundary[incident[0]],
1257 &b = input.boundary[incident[1]];
1258 const auto na = CGAL::cross_product(points[a[1]] - points[a[0]],
1259 points[a[2]] - points[a[0]]);
1260 const auto nb = CGAL::cross_product(points[b[1]] - points[b[0]],
1261 points[b[2]] - points[b[0]]);
1262 const double dot = std::abs(CGAL::to_double(na * nb));
1263 const int opposite = *std::find_if(b.begin(), b.end(), [&](int v) {
1264 return v != edge[0] && v != edge[1];
1265 });
1266 // Preserve reference geometry beyond its tolerance, while allowing
1267 // near-coplanar diagonals to flip despite floating-point noise.
1268 feature = input.surfaceLabels[incident[0]] !=
1269 input.surfaceLabels[incident[1]] ||
1270 CGAL::squared_distance(
1271 points[opposite],
1272 RemeshKernel::Plane_3(points[a[0]], points[a[1]],
1273 points[a[2]])) > tolerance2 ||
1274 dot < cosine * std::sqrt(CGAL::to_double(na.squared_length() *
1275 nb.squared_length()));
1276 }
1277 if (feature)
1278 feature_edges.insert(edge);
1279 }
1280 std::map<int, VH> vertices;
1281 for (auto v : tr.finite_vertex_handles())
1282 if (v->moabHandle)
1283 vertices.emplace(v->moabHandle - 1, v);
1284 std::map<std::pair<VH, VH>, bool> constrained_edges;
1285 using FeatureSegment = RemeshKernel::Segment_3;
1286 using FeatureSegments = std::vector<FeatureSegment>;
1287 using FeaturePrimitive =
1288 CGAL::AABB_segment_primitive_3<RemeshKernel,
1289 FeatureSegments::const_iterator>;
1290 using FeatureTree =
1291 CGAL::AABB_tree<CGAL::AABB_traits_3<RemeshKernel, FeaturePrimitive>>;
1292 FeatureSegments feature_segments;
1293 for (const auto &e : feature_edges)
1294 feature_segments.emplace_back(points[e[0]], points[e[1]]);
1295 // Curve identity uses round-off tolerance, independently of the allowed
1296 // surface approximation. Otherwise nearby curves acquire each other's edges.
1297 double coordinate_scale = 1;
1298 for (const auto &p : input.points)
1299 for (double x : p)
1300 coordinate_scale = std::max(coordinate_scale, std::abs(x));
1301 const double feature_tolerance2 = std::pow(
1302 128 * std::numeric_limits<double>::epsilon() * coordinate_scale, 2);
1303 if (!feature_segments.empty()) {
1304 const FeatureTree tree(feature_segments.cbegin(), feature_segments.cend());
1305 for (const auto &e : tr.finite_edges()) {
1306 auto a = e.first->vertex(e.second), b = e.first->vertex(e.third);
1307 const auto segment = tree.closest_point_and_primitive(
1308 CGAL::midpoint(a->point(), b->point()))
1309 .second;
1310 if (CGAL::squared_distance(a->point(), *segment) <= feature_tolerance2 &&
1311 CGAL::squared_distance(b->point(), *segment) <= feature_tolerance2)
1312 constrained_edges[std::minmax(a, b)] = true;
1313 }
1314 }
1315 std::map<VH, bool> constrained_vertices;
1316 for (auto v : fixed_support)
1317 constrained_vertices[v] = true;
1318 std::map<int, std::set<int>> curve_classes;
1319 for (size_t i = 0; i != input.featureEdges.size(); ++i)
1320 for (int v : input.featureEdges[i])
1321 curve_classes[v].insert(input.edgeLabels[i]);
1322 // A change of classification is a corner even on a straight polyline.
1323 for (const auto &[v, labels] : curve_classes)
1324 if (labels.size() > 1)
1325 constrained_vertices[vertices.at(v)] = true;
1326 for (int i : input.fixedVertices) {
1327 if (!vertices.count(i))
1328 THROW_MESSAGE("Invalid fixed remeshing vertex");
1329 constrained_vertices[vertices.at(i)] = true;
1330 }
1331 if (optimise)
1332 CGAL::tetrahedral_isotropic_remeshing(
1333 tr, settings.targetEdgeLength,
1334 CGAL::parameters::number_of_iterations(settings.iterations)
1335 .remesh_boundaries(settings.remeshSurfaces)
1336 .cell_is_selected_map(RemeshSelection<Tr>())
1337 .edge_is_constrained_map(
1338 boost::make_assoc_property_map(constrained_edges))
1339 .vertex_is_constrained_map(
1340 boost::make_assoc_property_map(constrained_vertices)));
1341 if (!tr.is_valid())
1342 THROW_MESSAGE("Invalid remeshed triangulation");
1343 TetMeshData next;
1344 std::map<VH, int> output_indices;
1345 std::set<int> retained;
1346 int max_id = *ids.rbegin();
1347 std::set<VH> physical_vertices;
1348 for (auto c : tr.finite_cell_handles())
1349 if (c->subdomain_index())
1350 for (int d = 0; d != 4; ++d)
1351 physical_vertices.insert(c->vertex(d));
1352 for (auto v : physical_vertices) {
1353 const auto &p = v->point();
1354 const std::array<double, 3> x{p.x(), p.y(), p.z()};
1355 int id;
1356 if (v->moabHandle && x == input.points.at(v->moabHandle - 1)) {
1357 const int i = v->moabHandle - 1;
1358 id = input.vertexIds[i];
1359 retained.insert(i);
1360 } else {
1361 if (max_id == INT_MAX)
1362 THROW_MESSAGE("Remeshing vertex IDs exhausted");
1363 id = ++max_id;
1364 if (v->moabHandle)
1365 ++next_report.movedVertices;
1366 else
1367 ++next_report.insertedVertices;
1368 }
1369 output_indices.emplace(v, next.points.size());
1370 next.points.push_back(x);
1371 next.vertexIds.push_back(id);
1372 }
1373 next_report.removedVertices =
1374 input.points.size() - retained.size() - next_report.movedVertices;
1375 if (!optimise && retained.size() != input.points.size())
1376 THROW_MESSAGE("Constraint recovery did not retain every source vertex");
1377 for (int i : auxiliary_vertices)
1378 if (!retained.count(i))
1379 THROW_MESSAGE("Remeshing changed a selection-interface vertex");
1380 for (int i : input.fixedVertices) {
1381 if (!retained.count(i))
1382 THROW_MESSAGE("Remeshing changed a fixed vertex");
1383 next.fixedVertices.push_back(output_indices.at(vertices.at(i)));
1384 }
1385 for (auto c : tr.finite_cell_handles()) {
1386 if (!c->subdomain_index())
1387 continue;
1388 std::array<int, 4> conn;
1389 for (int d = 0; d != 4; ++d)
1390 conn[d] = output_indices.at(c->vertex(d));
1391 next.cells.push_back(conn);
1392 next.cellLabels.push_back(c->subdomain_index());
1393 }
1394 for (auto f : tr.finite_facets()) {
1395 if (!f.first->is_facet_on_surface(f.second))
1396 continue;
1397 const int label = f.first->surface_patch_index(f.second);
1398 if (label <= 0 || label > max_label)
1399 THROW_MESSAGE("Remeshing lost a surface patch label");
1400 if (auxiliary_labels.count(label))
1401 continue;
1402 RemeshFace conn;
1403 int n = 0;
1404 for (int d = 0; d != 4; ++d)
1405 if (d != f.second)
1406 conn[n++] = output_indices.at(f.first->vertex(d));
1407 next.boundary.push_back(conn);
1408 next.surfaceLabels.push_back(label);
1409 }
1410 remeshFaces(next);
1411 if (patchTopology(next) != topology)
1412 THROW_MESSAGE("Remeshing changes protected surface topology");
1413 // Both directions are checked: proximity of the new vertices alone would
1414 // not detect a missing portion of the old surface.
1415 using Triangle = RemeshKernel::Triangle_3;
1416 using Triangles = std::vector<Triangle>;
1417 using Primitive =
1418 CGAL::AABB_triangle_primitive_3<RemeshKernel, Triangles::const_iterator>;
1419 using Tree = CGAL::AABB_tree<CGAL::AABB_traits_3<RemeshKernel, Primitive>>;
1420 auto triangles = [](const TetMeshData &mesh) {
1421 std::map<int, Triangles> values;
1422 for (size_t i = 0; i != mesh.boundary.size(); ++i) {
1423 const auto &f = mesh.boundary[i];
1424 values[mesh.surfaceLabels[i]].emplace_back(remeshPoint(mesh, f[0]),
1425 remeshPoint(mesh, f[1]),
1426 remeshPoint(mesh, f[2]));
1427 }
1428 return values;
1429 };
1430 const auto old_triangles = triangles(input), new_triangles = triangles(next);
1431 for (const auto &[label, old] : old_triangles) {
1432 const auto &current = new_triangles.at(label);
1433 Tree old_tree(old.begin(), old.end()),
1434 new_tree(current.begin(), current.end());
1435 auto maximum_distance = [&](const Triangles &from, const Tree &to) {
1436 double maximum = 0;
1437 for (const auto &triangle : from) {
1438 for (int d = 0; d != 3; ++d)
1439 maximum = std::max(maximum, CGAL::to_double(to.squared_distance(
1440 triangle.vertex(d))));
1441 maximum = std::max(maximum, CGAL::to_double(to.squared_distance(
1442 CGAL::centroid(triangle))));
1443 }
1444 return maximum;
1445 };
1446 const double deviation2 = std::max(maximum_distance(old, new_tree),
1447 maximum_distance(current, old_tree));
1448 if (deviation2 > tolerance2) {
1449 std::ostringstream message;
1450 message
1451 << "Remeshing surface patch " << label
1452 << " exceeds surface geometry tolerance: maximum sampled distance "
1453 << std::sqrt(deviation2) << ", allowed " << std::sqrt(tolerance2)
1454 << "; retaining the candidate";
1455 logWarning(message.str());
1456 }
1457 // Preserve the local winding carried by the source classification.
1458 for (size_t i = 0; i != next.boundary.size(); ++i) {
1459 if (next.surfaceLabels[i] != label)
1460 continue;
1461 auto &f = next.boundary[i];
1462 const Triangle triangle(remeshPoint(next, f[0]), remeshPoint(next, f[1]),
1463 remeshPoint(next, f[2]));
1464 const auto reference =
1465 old_tree.closest_point_and_primitive(CGAL::centroid(triangle)).second;
1466 const auto normal = CGAL::cross_product(triangle[1] - triangle[0],
1467 triangle[2] - triangle[0]);
1468 const auto old_normal = CGAL::cross_product(
1469 (*reference)[1] - (*reference)[0], (*reference)[2] - (*reference)[0]);
1470 if (normal * old_normal < 0)
1471 std::swap(f[1], f[2]);
1472 }
1473 }
1474 // Retain explicit curve membership by checking the evolved constrained edges
1475 // against their source polylines. Automatically inferred creases stay internal.
1476 using Segment = RemeshKernel::Segment_3;
1477 auto curves = [](const TetMeshData &mesh) {
1478 std::map<int, std::vector<Segment>> values;
1479 for (size_t i = 0; i != mesh.featureEdges.size(); ++i) {
1480 const auto &e = mesh.featureEdges[i];
1481 values[mesh.edgeLabels[i]].emplace_back(remeshPoint(mesh, e[0]),
1482 remeshPoint(mesh, e[1]));
1483 }
1484 return values;
1485 };
1486 const auto old_curves = curves(input);
1487 FeatureSegments curve_segments;
1488 std::vector<int> curve_labels;
1489 for (const auto &[label, segments] : old_curves)
1490 for (const auto &segment : segments) {
1491 curve_segments.push_back(segment);
1492 curve_labels.push_back(label);
1493 }
1494 const FeatureTree curve_tree(curve_segments.cbegin(), curve_segments.cend());
1495 auto covers_edge = [&](const RemeshPoint &a, const RemeshPoint &b,
1496 const auto &segments) {
1497 const auto direction = b - a;
1498 const double length2 = CGAL::to_double(direction.squared_length());
1499 const RemeshKernel::Line_3 line(a, b);
1500 std::vector<std::pair<double, double>> intervals;
1501 for (const auto &segment : segments) {
1502 if (CGAL::squared_distance(segment.source(), line) > feature_tolerance2 ||
1503 CGAL::squared_distance(segment.target(), line) > feature_tolerance2)
1504 continue;
1505 const double s = CGAL::to_double((segment.source() - a) * direction) /
1506 length2,
1507 t = CGAL::to_double((segment.target() - a) * direction) /
1508 length2;
1509 const auto [lo, hi] = std::minmax(s, t);
1510 if (hi >= 0 && lo <= 1)
1511 intervals.emplace_back(std::max(0., lo), std::min(1., hi));
1512 }
1513 std::sort(intervals.begin(), intervals.end());
1514 const double epsilon = std::sqrt(feature_tolerance2 / length2);
1515 double reached = 0;
1516 for (const auto &[lo, hi] : intervals) {
1517 if (lo > reached + epsilon)
1518 return false;
1519 reached = std::max(reached, hi);
1520 if (reached >= 1 - epsilon)
1521 return true;
1522 }
1523 return false;
1524 };
1525 for (const auto &e : tr.finite_edges()) {
1526 const std::pair<VH, VH> edge{e.first->vertex(e.second),
1527 e.first->vertex(e.third)};
1528 if (!output_indices.count(edge.first) || !output_indices.count(edge.second))
1529 continue;
1530 const auto &a = edge.first->point(), &b = edge.second->point();
1531 const double margin = std::sqrt(feature_tolerance2);
1532 const RemeshKernel::Iso_cuboid_3 bounds(
1533 std::min(a.x(), b.x()) - margin, std::min(a.y(), b.y()) - margin,
1534 std::min(a.z(), b.z()) - margin, std::max(a.x(), b.x()) + margin,
1535 std::max(a.y(), b.y()) + margin, std::max(a.z(), b.z()) + margin);
1536 std::vector<FeatureSegments::const_iterator> hits;
1537 curve_tree.all_intersected_primitives(bounds, std::back_inserter(hits));
1538 std::map<int, FeatureSegments> candidates;
1539 for (auto hit : hits)
1540 candidates[curve_labels[hit - curve_segments.cbegin()]].push_back(*hit);
1541 int label = 0;
1542 for (const auto &[id, segments] : candidates) {
1543 if (covers_edge(edge.first->point(), edge.second->point(), segments)) {
1544 if (label && label != id)
1545 THROW_MESSAGE("Ambiguous remeshed feature curve");
1546 label = id;
1547 }
1548 }
1549 if (label) {
1550 next.featureEdges.push_back(
1551 {output_indices.at(edge.first), output_indices.at(edge.second)});
1552 next.edgeLabels.push_back(label);
1553 }
1554 }
1555 const auto new_curves = curves(next);
1556 std::map<int, std::unique_ptr<FeatureTree>> curve_trees;
1557 for (const auto &[label, segments] : new_curves)
1558 curve_trees.emplace(label, std::make_unique<FeatureTree>(segments.cbegin(),
1559 segments.cend()));
1560 auto curve_topology = [](const TetMeshData &mesh) {
1561 std::map<int, std::map<int, std::vector<int>>> graphs;
1562 for (size_t i = 0; i != mesh.featureEdges.size(); ++i) {
1563 const auto &e = mesh.featureEdges[i];
1564 graphs[mesh.edgeLabels[i]][e[0]].push_back(e[1]);
1565 graphs[mesh.edgeLabels[i]][e[1]].push_back(e[0]);
1566 }
1567 std::map<int, std::pair<int, std::map<int, size_t>>> signatures;
1568 for (const auto &[label, graph] : graphs) {
1569 auto &value = signatures[label];
1570 std::set<int> visited;
1571 for (const auto &[v, adj] : graph) {
1572 if (adj.size() != 2)
1573 value.second.emplace(mesh.vertexIds[v], adj.size());
1574 if (visited.count(v))
1575 continue;
1576 ++value.first;
1577 std::vector<int> queue{v};
1578 for (size_t i = 0; i != queue.size(); ++i)
1579 if (visited.insert(queue[i]).second)
1580 queue.insert(queue.end(), graph.at(queue[i]).begin(),
1581 graph.at(queue[i]).end());
1582 }
1583 }
1584 return signatures;
1585 };
1586 const auto old_graphs = curve_topology(input),
1587 new_graphs = curve_topology(next);
1588 if (old_graphs != new_graphs) {
1589 std::ostringstream message;
1590 message << "Remeshing changes a protected curve graph";
1591 for (const auto &[label, original] : old_graphs) {
1592 const auto found = new_graphs.find(label);
1593 if (found == new_graphs.end()) {
1594 message << ": missing curve class " << label;
1595 break;
1596 }
1597 if (original == found->second)
1598 continue;
1599 message << ": class " << label << ", components " << original.first
1600 << " -> " << found->second.first;
1601 for (const auto &[id, degree] : original.second) {
1602 const auto node = found->second.second.find(id);
1603 if (node == found->second.second.end() || node->second != degree) {
1604 message << ", source junction GLOBAL_ID " << id << " degree "
1605 << degree << " -> "
1606 << (node == found->second.second.end() ? 0 : node->second);
1607 break;
1608 }
1609 }
1610 break;
1611 }
1612 THROW_MESSAGE(message.str());
1613 }
1614 for (const auto &[label, segments] : old_curves) {
1615 double deviation2 = 0;
1616 for (const auto &segment : segments) {
1617 const auto &tree = *curve_trees.at(label);
1618 deviation2 = std::max(
1619 {deviation2, CGAL::to_double(tree.squared_distance(segment.source())),
1620 CGAL::to_double(tree.squared_distance(segment.target())),
1621 CGAL::to_double(tree.squared_distance(CGAL::midpoint(segment)))});
1622 }
1623 if (deviation2 > tolerance2) {
1624 std::ostringstream message;
1625 message << "Remeshing protected curve " << label
1626 << " exceeds geometry tolerance: maximum sampled distance "
1627 << std::sqrt(deviation2) << ", allowed " << std::sqrt(tolerance2)
1628 << "; retaining the candidate";
1629 logWarning(message.str());
1630 }
1631 }
1632 std::set<std::array<int, 4>> output_cells;
1633 for (const auto &c : next.cells) {
1634 std::array<int, 4> key;
1635 for (int d = 0; d != 4; ++d)
1636 key[d] = next.vertexIds[c[d]];
1637 output_cells.insert(simplexKey(key));
1638 }
1639 for (size_t i = 0; i != input.cells.size(); ++i) {
1640 std::array<int, 4> key;
1641 for (int d = 0; d != 4; ++d)
1642 key[d] = input.vertexIds[input.cells[i][d]];
1643 if (!output_cells.count(simplexKey(key)))
1644 next_report.changedCells.push_back(i);
1645 }
1646 next_report.minQualityAfter = remeshQuality(next);
1647 if (optimise &&
1648 next_report.minQualityAfter <
1649 std::min(settings.minimumQuality, next_report.minQualityBefore)) {
1650 std::ostringstream message;
1651 message << "Remeshing candidate is below the minimum tetrahedron quality: "
1652 << next_report.minQualityAfter << " < "
1653 << std::min(settings.minimumQuality, next_report.minQualityBefore);
1654 THROW_MESSAGE(message.str());
1655 }
1656 for (auto &label : next.surfaceLabels)
1657 label = surface_classes.at(label);
1658 result = std::move(next);
1659 report = std::move(next_report);
1660#endif
1661}
1662
1663std::vector<int>
1664CGALTools::reconstructDelaunay(TetMeshData &result, const TetMeshData &vertices,
1665 ReconstructionMethod method) const {
1666 if (method == ReconstructionMethod::ConstrainedStrict) {
1667#if CGAL_VERSION_NR >= 1060200000
1668 return reconstructConstrained(result, vertices);
1669#else
1670 THROW_MESSAGE("Strict constrained reconstruction requires CGAL 6.2");
1671#endif
1672 }
1673 if (method != ReconstructionMethod::PointDelaunay)
1674 THROW_MESSAGE("Unknown reconstruction method");
1675 if (vertices.vertexIds.size() != vertices.points.size() ||
1676 std::any_of(vertices.vertexIds.begin(), vertices.vertexIds.end(),
1677 [](int id) { return id <= 0; }))
1678 THROW_MESSAGE("Reconstruction requires positive vertex IDs");
1679 CGALMesh mesh;
1680 createDelaunay(mesh, vertices.points,
1681 std::vector<std::uint64_t>(vertices.vertexIds.begin(),
1682 vertices.vertexIds.end()));
1683 if (mesh.tr.dimension() != 3)
1684 THROW_MESSAGE("Reconstruction requires a 3D point set");
1685 TetMeshData next;
1686 next.points = vertices.points;
1687 next.vertexIds = vertices.vertexIds;
1688 std::map<std::uint64_t, int> indices;
1689 for (size_t n = 0; n != next.vertexIds.size(); ++n)
1690 indices.emplace(next.vertexIds[n], n);
1691 for (auto c = mesh.tr.finite_cells_begin(); c != mesh.tr.finite_cells_end();
1692 ++c) {
1693 std::array<int, 4> cell;
1694 for (int n = 0; n != 4; ++n)
1695 cell[n] = indices.at(c->vertex(n)->moabHandle);
1696 next.cells.push_back(cell);
1697 }
1698 for (auto f = mesh.tr.finite_facets_begin(); f != mesh.tr.finite_facets_end();
1699 ++f)
1700 if (mesh.tr.is_infinite(f->first) ||
1701 mesh.tr.is_infinite(f->first->neighbor(f->second))) {
1702 auto face = *f;
1703 if (mesh.tr.is_infinite(face.first))
1704 face = mesh.tr.mirror_facet(face);
1705 std::array<int, 3> conn;
1706 int n = 0;
1707 for (int d = 0; d != 4; ++d)
1708 if (d != face.second)
1709 conn[n++] = indices.at(face.first->vertex(d)->moabHandle);
1710 next.boundary.push_back(conn);
1711 }
1712 next.cellLabels.assign(next.cells.size(), 1);
1713 next.surfaceLabels.assign(next.boundary.size(), 1);
1714 result = std::move(next);
1715 return {};
1716}
1717
1718std::vector<int> CGALTools::validateReconstruction(
1720 const std::vector<std::array<int, 2>> &protected_edges,
1721 const std::function<void(const std::string &)> &warning) const {
1722 const auto report_warning = [&](const std::string &message) {
1723 logWarning(message);
1724 if (warning)
1725 warning(message);
1726 };
1727 if (!std::isfinite(surfaceFlipAngle) || surfaceFlipAngle < 0 ||
1728 surfaceFlipAngle > 90)
1729 THROW_MESSAGE("Surface flip angle must be between 0 and 90 degrees");
1730 if (source.points != result.points || source.vertexIds != result.vertexIds ||
1731 source.surfaceLabels.size() != source.boundary.size())
1732 THROW_MESSAGE("Invalid reconstruction vertices or patch labels");
1733 using K = CGALMesh::Kernel;
1734 using Face = std::array<int, 3>;
1735 using Edge = std::array<int, 2>;
1736 using Normal = std::array<double, 3>;
1737 auto key = [](auto vertices) {
1738 std::sort(vertices.begin(), vertices.end());
1739 return vertices;
1740 };
1741 auto point = [&](int i) {
1742 const auto &x = source.points.at(i);
1743 return K::Point_3(x[0], x[1], x[2]);
1744 };
1745 auto normal = [&](const Face &face) {
1746 const auto n = CGAL::cross_product(point(face[1]) - point(face[0]),
1747 point(face[2]) - point(face[0]));
1748 const double scale =
1749 std::max({std::abs(n.x()), std::abs(n.y()), std::abs(n.z())});
1750 if (!std::isfinite(scale) || scale == 0)
1751 THROW_MESSAGE("Degenerate surface normal");
1752 Normal value{n.x() / scale, n.y() / scale, n.z() / scale};
1753 const double length = std::hypot(value[0], value[1], value[2]);
1754 for (auto &x : value)
1755 x /= length;
1756 return value;
1757 };
1758 auto dot = [](const Normal &a, const Normal &b) {
1759 return std::inner_product(a.begin(), a.end(), b.begin(), 0.);
1760 };
1761 const double chord = 2. * std::sin(surfaceFlipAngle * std::acos(-1.) / 360.);
1762 const double eps = std::numeric_limits<double>::epsilon();
1763 const double limit = chord * chord * (1. + 32. * eps) + 256. * eps * eps;
1764 auto aligned = [&](const Normal &a, const Normal &b) {
1765 // Plane normals are unoriented. Chord distance avoids acos cancellation
1766 // near zero angle and only admits machine-precision slack at angle zero.
1767 const double sign = dot(a, b) < 0 ? -1. : 1.;
1768 double distance = 0;
1769 for (int d = 0; d != 3; ++d)
1770 distance += (a[d] - sign * b[d]) * (a[d] - sign * b[d]);
1771 return distance <= limit;
1772 };
1773 auto faces = [&](const TetMeshData &mesh) {
1774 std::map<Face, int> counts;
1775 std::set<std::array<int, 4>> cells;
1776 for (auto cell : mesh.cells) {
1777 const auto sorted = key(cell);
1778 if (!cells.insert(sorted).second ||
1779 std::adjacent_find(sorted.begin(), sorted.end()) != sorted.end())
1780 THROW_MESSAGE("Duplicate or degenerate source cell");
1781 if (CGAL::orientation(point(cell[0]), point(cell[1]), point(cell[2]),
1782 point(cell[3])) == CGAL::COPLANAR)
1783 THROW_MESSAGE("Degenerate source tetrahedron");
1784 for (int opposite = 0; opposite != 4; ++opposite) {
1785 Face face;
1786 int n = 0;
1787 for (int d = 0; d != 4; ++d)
1788 if (d != opposite)
1789 face[n++] = cell[d];
1790 if (++counts[key(face)] > 2)
1791 THROW_MESSAGE("Nonmanifold source face");
1792 }
1793 }
1794 return counts;
1795 };
1796 const auto before = faces(source), after = faces(result);
1797 auto topology = [&](const std::set<Face> &triangles,
1798 bool *disconnected_links = nullptr) {
1799 std::map<Edge, int> counts;
1800 std::map<int, std::map<int, std::set<int>>> links;
1801 for (const auto &face : triangles) {
1802 for (int i = 0; i != 3; ++i) {
1803 const int v = face[i], a = face[(i + 1) % 3], b = face[(i + 2) % 3];
1804 links[v][a].insert(b);
1805 links[v][b].insert(a);
1806 if (i < 2)
1807 for (int j = i + 1; j != 3; ++j)
1808 if (++counts[{face[i], face[j]}] > 2)
1809 THROW_MESSAGE("Nonmanifold preserved surface edge");
1810 }
1811 }
1812 std::set<Edge> boundary;
1813 std::set<int> boundary_nodes;
1814 for (const auto &[edge, count] : counts)
1815 if (count == 1) {
1816 boundary.insert(edge);
1817 boundary_nodes.insert(edge.begin(), edge.end());
1818 }
1819 for (const auto &[v, link] : links) {
1820 int ends = 0;
1821 for (const auto &[node, neighbors] : link) {
1822 ends += neighbors.size() == 1;
1823 if (neighbors.empty() || neighbors.size() > 2)
1824 THROW_MESSAGE("Nonmanifold preserved surface vertex");
1825 }
1826 std::set<int> seen;
1827 std::vector<int> queue{link.begin()->first};
1828 for (size_t i = 0; i != queue.size(); ++i)
1829 if (seen.insert(queue[i]).second) {
1830 const auto &next = link.at(queue[i]);
1831 queue.insert(queue.end(), next.begin(), next.end());
1832 }
1833 if (seen.size() != link.size() ||
1834 ends != (boundary_nodes.count(v) ? 2 : 0)) {
1835 if (!disconnected_links)
1836 THROW_MESSAGE("Disconnected preserved surface vertex link");
1837 *disconnected_links = true;
1838 report_warning(
1839 "Disconnected preserved surface vertex link at GLOBAL_ID " +
1840 std::to_string(source.vertexIds[v]) +
1841 "; retaining the incomplete reconstructed patch for inspection");
1842 }
1843 }
1844 if (!links.empty()) {
1845 std::set<int> seen;
1846 std::vector<int> queue{links.begin()->first};
1847 for (size_t i = 0; i != queue.size(); ++i)
1848 if (seen.insert(queue[i]).second)
1849 for (const auto &[neighbor, unused] : links.at(queue[i]))
1850 queue.push_back(neighbor);
1851 if (seen.size() != links.size() &&
1852 !(disconnected_links && *disconnected_links))
1853 THROW_MESSAGE("Disconnected reconstructed surface patch");
1854 }
1855 const auto euler = static_cast<long long>(links.size()) -
1856 static_cast<long long>(counts.size()) +
1857 static_cast<long long>(triangles.size());
1858 return std::make_pair(boundary, euler);
1859 };
1860 std::vector<Normal> source_normals;
1861 std::map<Edge, std::vector<int>> adjacent;
1862 for (size_t i = 0; i != source.boundary.size(); ++i) {
1863 const auto face = key(source.boundary[i]);
1864 if (!before.count(face))
1865 THROW_MESSAGE("Protected triangle is not a source cell face");
1866 source_normals.push_back(normal(source.boundary[i]));
1867 for (int a = 0; a != 3; ++a)
1868 for (int b = a + 1; b != 3; ++b)
1869 adjacent[{face[a], face[b]}].push_back(i);
1870 }
1871 std::set<Edge> creases;
1872 for (const auto &[edge, patch] : adjacent)
1873 if (patch.size() != 2 ||
1874 source.surfaceLabels[patch[0]] != source.surfaceLabels[patch[1]] ||
1875 before.at(key(source.boundary[patch[0]])) !=
1876 before.at(key(source.boundary[patch[1]])) ||
1877 !aligned(source_normals[patch[0]], source_normals[patch[1]]))
1878 creases.insert(edge);
1879 std::map<int, std::set<Face>> incident;
1880 std::set<Edge> result_edges;
1881 std::set<Face> exterior, covered_exterior;
1882 for (const auto &[face, count] : after) {
1883 if (count == 1)
1884 exterior.insert(face);
1885 for (int i = 0; i != 3; ++i) {
1886 incident[face[i]].insert(face);
1887 for (int j = i + 1; j != 3; ++j)
1888 result_edges.insert({face[i], face[j]});
1889 }
1890 }
1891 for (auto edge : protected_edges)
1892 if (!result_edges.count(key(edge)))
1893 THROW_MESSAGE("Reconstruction loses a protected curve; "
1894 "constrained recovery is required");
1895 for (auto edge : creases)
1896 if (!result_edges.count(edge))
1897 THROW_MESSAGE("Reconstruction removes protected surface edge (" +
1898 std::to_string(source.vertexIds[edge[0]]) + "," +
1899 std::to_string(source.vertexIds[edge[1]]) +
1900 ") at the requested surface flip angle");
1901 auto identity = [&](int i) {
1902 auto face = source.boundary[i];
1903 for (auto &v : face)
1904 v = source.vertexIds[v];
1905 return key(face);
1906 };
1907 std::vector<bool> visited(source.boundary.size(), false);
1908 std::vector<Face> output;
1909 std::vector<int> labels, parents;
1910 for (size_t seed = 0; seed != source.boundary.size(); ++seed) {
1911 if (visited[seed])
1912 continue;
1913 const int incidence = before.at(key(source.boundary[seed]));
1914 std::vector<int> patch{static_cast<int>(seed)};
1915 visited[seed] = true;
1916 for (size_t i = 0; i != patch.size(); ++i) {
1917 const auto face = key(source.boundary[patch[i]]);
1918 for (int a = 0; a != 3; ++a)
1919 for (int b = a + 1; b != 3; ++b) {
1920 const Edge edge{face[a], face[b]};
1921 if (!creases.count(edge))
1922 for (int next : adjacent.at(edge))
1923 if (!visited[next]) {
1924 visited[next] = true;
1925 patch.push_back(next);
1926 }
1927 }
1928 }
1929 std::set<Face> original_faces, selected;
1930 std::set<int> vertices, selected_vertices;
1931 std::map<int, std::vector<int>> vertex_faces;
1932 for (int i : patch) {
1933 const auto &face = source.boundary[i];
1934 original_faces.insert(key(face));
1935 vertices.insert(face.begin(), face.end());
1936 for (int v : face)
1937 vertex_faces[v].push_back(i);
1938 }
1939 Triangles patch_triangles;
1940 for (int i : patch) {
1941 const auto &f = source.boundary[i];
1942 patch_triangles.emplace_back(point(f[0]), point(f[1]), point(f[2]));
1943 }
1944 const TriangleTree patch_tree(patch_triangles.cbegin(),
1945 patch_triangles.cend());
1946 std::set<Face> candidates;
1947 for (int v : vertices)
1948 candidates.insert(incident[v].begin(), incident[v].end());
1949 std::map<Face, Normal> normals;
1950 std::map<Face, int> carriers;
1951 for (const auto &face : candidates) {
1952 if (after.at(face) != incidence ||
1953 !std::all_of(face.begin(), face.end(),
1954 [&](int v) { return vertices.count(v); }))
1955 continue;
1956 const auto n = normal(face);
1957 if (!std::all_of(face.begin(), face.end(), [&](int v) {
1958 const auto &old = vertex_faces.at(v);
1959 return std::any_of(old.begin(), old.end(), [&](int i) {
1960 return aligned(n, source_normals[i]);
1961 });
1962 }))
1963 continue;
1964 const K::Point_3 center(
1965 (point(face[0]).x() / 3.) + (point(face[1]).x() / 3.) +
1966 (point(face[2]).x() / 3.),
1967 (point(face[0]).y() / 3.) + (point(face[1]).y() / 3.) +
1968 (point(face[2]).y() / 3.),
1969 (point(face[0]).z() / 3.) + (point(face[1]).z() / 3.) +
1970 (point(face[2]).z() / 3.));
1971 ClosestAlignedTriangle nearest{
1972 patch_triangles,
1973 [&](size_t i) { return aligned(n, source_normals[patch[i]]); },
1974 [&](size_t a, size_t b) {
1975 return identity(patch[a]) < identity(patch[b]);
1976 }};
1977 patch_tree.traversal(center, nearest);
1978 const int carrier = nearest.best == std::numeric_limits<size_t>::max()
1979 ? -1
1980 : patch[nearest.best];
1981 if (carrier < 0)
1982 continue;
1983 selected.insert(face);
1984 selected_vertices.insert(face.begin(), face.end());
1985 normals.emplace(face, n);
1986 carriers.emplace(face, carrier);
1987 }
1988 const auto original_topology = topology(original_faces);
1989 bool disconnected_links = false;
1990 const auto selected_topology = topology(selected, &disconnected_links);
1991 auto check_patch = [&](bool valid, const std::string &message) {
1992 if (valid)
1993 return;
1994 if (!disconnected_links)
1995 THROW_MESSAGE(message);
1996 report_warning(message + "; retaining " +
1997 std::to_string(selected.size()) +
1998 " reconstructed triangles for a source patch of " +
1999 std::to_string(original_faces.size()) + " triangles");
2000 };
2001 check_patch(vertices == selected_vertices &&
2002 original_topology == selected_topology,
2003 "Reconstruction changes protected surface nodes, boundary or "
2004 "topology at the requested flip angle");
2005 std::set<Edge> old_edges;
2006 for (auto face : original_faces)
2007 for (int i = 0; i != 3; ++i)
2008 for (int j = i + 1; j != 3; ++j)
2009 old_edges.insert({face[i], face[j]});
2010 std::map<Edge, std::vector<Face>> new_edges;
2011 for (auto face : selected)
2012 for (int i = 0; i != 3; ++i)
2013 for (int j = i + 1; j != 3; ++j)
2014 new_edges[{face[i], face[j]}].push_back(face);
2015 for (const auto &edge : old_edges)
2016 check_patch(!creases.count(edge) || new_edges.count(edge),
2017 "Reconstruction removes a protected crease from its surface");
2018 for (auto edge : protected_edges)
2019 check_patch(!old_edges.count(key(edge)) || new_edges.count(key(edge)),
2020 "Reconstruction removes a protected curve from its surface");
2021 for (const auto &[edge, pair] : new_edges)
2022 if (!old_edges.count(edge) && pair.size() == 2 &&
2023 !aligned(normals.at(pair[0]), normals.at(pair[1])))
2025 "A new surface diagonal exceeds the requested flip angle");
2026 for (auto face : selected) {
2027 if (incidence == 1)
2028 covered_exterior.insert(face);
2029 const int carrier = carriers.at(face);
2030 if (dot(normals.at(face), source_normals[carrier]) < 0)
2031 std::swap(face[1], face[2]);
2032 output.push_back(face);
2033 labels.push_back(source.surfaceLabels[carrier]);
2034 parents.push_back(carrier);
2035 }
2036 }
2037 if (exterior != covered_exterior)
2038 THROW_MESSAGE("Reconstruction changes the protected domain boundary");
2039 result.boundary = std::move(output);
2040 result.surfaceLabels = std::move(labels);
2041 return parents;
2042}
2043
2044std::vector<std::uint64_t>
2045CGALTools::findVertexParents(const std::vector<std::array<double, 3>> &points,
2046 const std::vector<Simplex> &sources) const {
2047 using Kernel = CGALMesh::Kernel;
2048 using Point = Kernel::Point_3;
2049 auto point = [](const std::array<double, 3> &x) {
2050 if (!std::isfinite(x[0]) || !std::isfinite(x[1]) || !std::isfinite(x[2]))
2051 THROW_MESSAGE("Parent classification requires finite coordinates");
2052 return Point(x[0], x[1], x[2]);
2053 };
2054 std::vector<std::vector<Point>> vertices;
2055 std::set<std::uint64_t> identifiers;
2056 for (const auto &source : sources) {
2057 if (!source.identifier || !identifiers.insert(source.identifier).second ||
2058 source.vertices.size() < 2 || source.vertices.size() > 4)
2059 THROW_MESSAGE("Invalid source simplex or identifier");
2060 auto &x = vertices.emplace_back();
2061 for (const auto &v : source.vertices)
2062 x.push_back(point(v));
2063 const bool degenerate =
2064 x.size() == 2 ? Kernel::Segment_3(x[0], x[1]).is_degenerate()
2065 : x.size() == 3
2066 ? Kernel::Triangle_3(x[0], x[1], x[2]).is_degenerate()
2067 : Kernel::Tetrahedron_3(x[0], x[1], x[2], x[3]).is_degenerate();
2068 if (degenerate)
2069 THROW_MESSAGE("Cannot classify against a degenerate source simplex");
2070 }
2071
2072 using Box = CGAL::Box_intersection_d::Box_with_info_d<double, 3, size_t>;
2073 std::vector<Box> source_boxes, point_boxes;
2074 for (size_t i = 0; i != vertices.size(); ++i) {
2075 auto box = vertices[i].front().bbox();
2076 for (const auto &v : vertices[i])
2077 box = box + v.bbox();
2078 source_boxes.emplace_back(box, i);
2079 }
2080 for (size_t i = 0; i != points.size(); ++i)
2081 point_boxes.emplace_back(point(points[i]).bbox(), i);
2082 std::vector<std::vector<size_t>> candidates(points.size());
2083 CGAL::box_intersection_d(point_boxes.begin(), point_boxes.end(),
2084 source_boxes.begin(), source_boxes.end(),
2085 [&](const Box &query, const Box &source) {
2086 candidates[query.info()].push_back(source.info());
2087 });
2088 std::vector<std::uint64_t> parents;
2089 parents.reserve(points.size());
2090 for (size_t i = 0; i != points.size(); ++i) {
2091 const auto p = point(points[i]);
2092 size_t dimension = 4;
2093 std::uint64_t parent = 0;
2094 bool ambiguous = false;
2095 for (size_t n : candidates[i]) {
2096 const auto &x = vertices[n];
2097 if (x.size() - 1 > dimension)
2098 continue;
2099 const bool contains =
2100 x.size() == 2 ? Kernel::Segment_3(x[0], x[1]).has_on(p)
2101 : x.size() == 3
2102 ? Kernel::Triangle_3(x[0], x[1], x[2]).has_on(p)
2103 : Kernel::Tetrahedron_3(x[0], x[1], x[2], x[3]).bounded_side(p) !=
2104 CGAL::ON_UNBOUNDED_SIDE;
2105 if (!contains)
2106 continue;
2107 if (x.size() - 1 < dimension) {
2108 dimension = x.size() - 1;
2109 parent = sources[n].identifier;
2110 ambiguous = false;
2111 } else {
2112 ambiguous = true;
2113 }
2114 }
2115 if (!parent || ambiguous)
2116 THROW_MESSAGE(ambiguous ? "Ambiguous source parent for vertex"
2117 : "Vertex lies outside the source mesh");
2118 parents.push_back(parent);
2119 }
2120 return parents;
2121}
2122
2123void CGALTools::createDelaunay(
2124 CGALMesh &mesh, const std::vector<std::array<double, 3>> &points,
2125 const std::vector<std::uint64_t> &identifiers) const {
2126 if (!identifiers.empty() && identifiers.size() != points.size())
2127 THROW_MESSAGE("CGAL point and identifier counts differ");
2128
2130 std::set<std::uint64_t> used_ids;
2131 for (size_t n = 0; n != points.size(); ++n) {
2132 const auto &p = points[n];
2133 if (!std::isfinite(p[0]) || !std::isfinite(p[1]) || !std::isfinite(p[2]))
2134 THROW_MESSAGE("CGAL points must have finite coordinates");
2135 const auto id = identifiers.empty() ? 0 : identifiers[n];
2136 if (id && !used_ids.insert(id).second)
2137 THROW_MESSAGE("CGAL vertex identifiers must be unique");
2138 const auto count = result.tr.number_of_vertices();
2139 auto vertex = result.tr.insert(CGALMesh::Kernel::Point_3(p[0], p[1], p[2]));
2140 if (result.tr.number_of_vertices() == count)
2141 THROW_MESSAGE("Coincident CGAL points cannot retain distinct identities");
2142 vertex->moabHandle = id;
2143 }
2144 mesh.tr.swap(result.tr);
2145}
2146
2147} // namespace MoFEM
Opt-in CGAL types; not included by MoFEM.hpp.
std::map< EntityHandle, int > labels
std::map< EntityHandle, int > index
std::vector< std::array< EntityHandle, 3 > > faces
Sorted keys.
TetMeshData result
std::vector< std::array< EntityHandle, 2 > > curves
Sorted keys.
std::function< bool(size_t, size_t)> preferred
Definition CGALTools.cpp:62
double distance
Definition CGALTools.cpp:64
const Triangles & triangles
Definition CGALTools.cpp:60
bool selected
Definition CGALTools.cpp:97
size_t best
Definition CGALTools.cpp:63
std::function< bool(size_t)> accept
Definition CGALTools.cpp:61
CGAL algorithms independent of the MoFEM/MOAB database.
Report & report
std::vector< int > source
bool topology
const Settings & settings
int boundary
const std::vector< Vec > * points
std::vector< int > size
std::vector< int > label
double length
WorkMesh mesh
std::vector< int > polygon
std::vector< int > vertices
Vec t
Removal: the ring edge.
std::vector< int > parent
std::unordered_map< int, NodeConstraint > constraints
std::vector< Cell > cells
ParentChildKey key
bool active
int components
Inferred from the source tag length.
std::map< EntityHandle, std::pair< bool, std::vector< double > > > previous
std::vector< double > empty
One value per component.
std::vector< std::array< double, 3 > > coordinates
It it
Definition Schur.cpp:2568
int nb
number of DOFs
Definition Schur.cpp:2505
It end
Definition Schur.cpp:2568
SmartPetscObj< Vec > values
void simple(double P1[], double P2[], double P3[], double c[], const int N)
Definition acoustic.cpp:69
constexpr double a
static const double eps
#define THROW_MESSAGE(msg)
Throw MoFEM exception.
static LoggerType & setLog(const std::string channel)
Set ans resset chanel logger.
#define MOFEM_LOG(channel, severity)
Log.
#define MOFEM_LOG_TAG(channel, tag)
Tag channel.
FTensor::Index< 'i', SPACE_DIM > i
const double c
speed of light (cm/ns)
const double v
phase velocity of light in medium (cm/ns)
FTensor::Index< 'j', 3 > j
implementation of Data Operators for Forces and Sources
Definition Common.hpp:10
double constraint(double eqiv, double dot_tau, double f, double sigma_y, double abs_w, double vis_H, double sigma_Y)
double scale
Definition plastic.cpp:124
static constexpr double delta
CGAL::Exact_predicates_inexact_constructions_kernel Kernel
std::vector< int > changedCells
Source cell indices, including neighbours.
Definition CGALTools.hpp:46
static boost::shared_ptr< SinkType > createSink(boost::shared_ptr< std::ostream > stream_ptr, std::string comm_filter)
Create a sink object.
static bool checkIfChannelExist(const std::string channel)
Check if channel exist.
static boost::shared_ptr< std::ostream > getStrmSelf()
Get the strm self object.
std::vector< int > partitions
Optional cell-to-rank assignment.
Definition CGALTools.hpp:22
std::vector< std::array< int, 3 > > boundary
Definition CGALTools.hpp:20
std::vector< std::array< int, 2 > > featureEdges
Definition CGALTools.hpp:23
std::vector< int > edgeLabels
Definition CGALTools.hpp:24
std::vector< int > cellLabels
Definition CGALTools.hpp:21
std::vector< std::array< int, 4 > > cells
Zero-based point indices.
Definition CGALTools.hpp:19
std::vector< std::array< double, 3 > > points
Definition CGALTools.hpp:17
std::vector< int > vertexIds
Definition CGALTools.hpp:18
std::vector< int > surfaceLabels
Definition CGALTools.hpp:21
std::vector< int > fixedVertices
Point indices which cannot move or collapse.
Definition CGALTools.hpp:26