v0.16.3
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
MoFEM::CGALTools Struct Reference

#include "src/interfaces/CGALTools.hpp"

Collaboration diagram for MoFEM::CGALTools:
[legend]

Classes

struct  CrackExtensionCandidate
 
struct  CrackExtensionReport
 
struct  CrackExtensionSettings
 
struct  CrackJoinFace
 
struct  ImplicitMeshSettings
 
struct  RemeshReport
 
struct  RemeshSettings
 
struct  Simplex
 

Public Types

enum class  ReconstructionMethod { PointDelaunay , ConstrainedStrict }
 

Public Member Functions

void remesh (TetMeshData &result, const TetMeshData &source, const std::vector< int > &selected_cells, const RemeshSettings &settings, RemeshReport &report) const
 
void createImplicitMesh (TetMeshData &result, const std::function< double(const std::array< double, 3 > &)> &sdf, const ImplicitMeshSettings &settings) const
 
std::vector< int > reconstructDelaunay (TetMeshData &result, const TetMeshData &vertices, ReconstructionMethod method=ReconstructionMethod::PointDelaunay) const
 
std::vector< int > validateReconstruction (const TetMeshData &source, TetMeshData &result, const std::vector< std::array< int, 2 > > &protected_edges={}, const std::function< void(const std::string &)> &warning={}) const
 
std::vector< std::uint64_t > findVertexParents (const std::vector< std::array< double, 3 > > &points, const std::vector< Simplex > &sources) const
 
void createDelaunay (CGALMesh &mesh, const std::vector< std::array< double, 3 > > &points, const std::vector< std::uint64_t > &identifiers={}) const
 
std::vector< CrackExtensionCandidate > crackExtensionCandidates (const TetMeshData &patch, const std::vector< int > &crack_faces, std::array< int, 2 > front_edge, std::array< double, 3 > direction, const CrackExtensionSettings &settings, CrackExtensionReport *report=nullptr) const
 
std::vector< CrackExtensionCandidate > crackClosureCandidates (const TetMeshData &patch, const std::vector< int > &crack_faces, std::array< int, 2 > front_edge, std::array< double, 3 > direction, const CrackExtensionSettings &settings, CrackExtensionReport *report=nullptr) const
 
std::vector< CrackExtensionCandidate > crackJoiningCandidates (const TetMeshData &patch, const std::vector< int > &crack_faces, std::array< int, 2 > front_edge, std::array< double, 3 > direction, const CrackExtensionSettings &settings, CrackExtensionReport *report=nullptr) const
 
void applyCrackExtension (TetMeshData &patch, std::vector< int > &crack_faces, const CrackExtensionCandidate &candidate) const
 
std::vector< std::array< int, 3 > > crackFillFaces (const TetMeshData &patch, const std::vector< int > &crack_faces) const
 
std::vector< CrackJoinFace > crackJoinFaces (const TetMeshData &patch, const std::vector< int > &crack_faces, const std::vector< std::array< int, 2 > > &front_order={}, const std::function< bool(const std::array< int, 3 > &)> &accept_face={}) const
 

Public Attributes

double surfaceFlipAngle = 1e-6
 

Detailed Description

Definition at line 31 of file CGALTools.hpp.

Member Enumeration Documentation

◆ ReconstructionMethod

Enumerator
PointDelaunay 
ConstrainedStrict 

Definition at line 91 of file CGALTools.hpp.

Member Function Documentation

◆ applyCrackExtension()

void MoFEM::CGALTools::applyCrackExtension ( TetMeshData &  patch,
std::vector< int > &  crack_faces,
const CrackExtensionCandidate &  candidate 
) const

Apply a candidate returned for this exact patch state. Rejects a candidate whose patch digest differs (stale or foreign), then validates the proposed result before changing anything: created cells fill the removed cavity and are positive after the move, retained cells around a moved node keep their orientation, no face gains a third cell, and the new face and closure faces are interior. Removed cells are erased, created cells appended with labels/partitions of their parents, the free node moved, and the new face and closure faces appended to boundary and crack_faces. Throws MoFEMException without changing patch or crack_faces.

Definition at line 2411 of file CgalCrackExtension.cpp.

2413 {
2414 if (!candidate.patchDigest ||
2415 candidate.patchDigest != patchDigest(patch, crack_faces))
2416 THROW_MESSAGE("Crack extension candidate does not match the patch; "
2417 "candidates must be regenerated after any change");
2418 const int np = patch.points.size();
2419 const int nc = patch.cells.size();
2420 const auto valid_point = [np](int v) { return v >= 0 && v < np; };
2421 const bool has_labels = !patch.cellLabels.empty();
2422 const bool has_partitions = !patch.partitions.empty();
2423 if (has_labels && patch.cellLabels.size() != patch.cells.size())
2424 THROW_MESSAGE("Crack extension cell labels do not match cells");
2425 if (has_partitions && patch.partitions.size() != patch.cells.size())
2426 THROW_MESSAGE("Crack extension partitions do not match cells");
2427 if (!patch.surfaceLabels.empty() &&
2428 patch.surfaceLabels.size() != patch.boundary.size())
2429 THROW_MESSAGE("Crack extension surface labels do not match boundary");
2430 for (int i : crack_faces)
2431 if (i < 0 || i >= static_cast<int>(patch.boundary.size()))
2432 THROW_MESSAGE("Invalid crack extension crack face index");
2433
2434 const auto &removed = candidate.removedCells;
2435 if (!std::is_sorted(removed.begin(), removed.end()) ||
2436 std::adjacent_find(removed.begin(), removed.end()) != removed.end())
2437 THROW_MESSAGE("Crack extension removed cells must be sorted and unique");
2438 for (int c : removed)
2439 if (c < 0 || c >= nc)
2440 THROW_MESSAGE("Invalid crack extension removed cell");
2441 if (candidate.createdParents.size() != candidate.createdCells.size())
2442 THROW_MESSAGE("Crack extension parents do not match created cells");
2443 for (std::size_t i = 0; i != candidate.createdCells.size(); ++i) {
2444 for (int v : candidate.createdCells[i])
2445 if (!valid_point(v))
2446 THROW_MESSAGE("Invalid crack extension created cell");
2447 if (!std::binary_search(removed.begin(), removed.end(),
2448 candidate.createdParents[i]))
2449 THROW_MESSAGE("Crack extension parent is not a removed cell");
2450 }
2451 const auto &f = candidate.newFace;
2452 const int w = candidate.freeNode;
2453 if (!valid_point(f[0]) || !valid_point(f[1]) || f[2] != w ||
2454 !valid_point(w) || !finite(candidate.displacement))
2455 THROW_MESSAGE("Invalid crack extension candidate");
2456 const auto face = faceKey(f[0], f[1], f[2]);
2457 std::vector<Face> added{face};
2458 for (const auto &c : candidate.closureFaces) {
2459 for (int v : c)
2460 if (!valid_point(v))
2461 THROW_MESSAGE("Invalid crack extension closure face");
2462 added.push_back(faceKey(c[0], c[1], c[2]));
2463 }
2464 {
2465 auto unique = added;
2466 std::sort(unique.begin(), unique.end());
2467 if (std::adjacent_find(unique.begin(), unique.end()) != unique.end())
2468 THROW_MESSAGE("Crack extension adds the same face twice");
2469 }
2470 for (const auto &b : patch.boundary)
2471 if (std::count(added.begin(), added.end(), faceKey(b[0], b[1], b[2])))
2472 THROW_MESSAGE("Crack extension face is already a boundary face");
2473
2474 // A moved node must be free to move.
2475 const bool moves = norm(candidate.displacement) > 0;
2476 if (moves) {
2477 if (std::count(patch.fixedVertices.begin(), patch.fixedVertices.end(), w))
2478 THROW_MESSAGE("Crack extension moves a fixed vertex");
2479 for (int i : crack_faces)
2480 if (std::count(patch.boundary[i].begin(), patch.boundary[i].end(), w))
2481 THROW_MESSAGE("Crack extension moves a crack node");
2482 }
2483
2484 // The created cells must fill exactly the cavity of the removed cells.
2485 const auto cavity_boundary = [](const auto &cells) {
2486 std::map<Face, int> count;
2487 for (const auto &cell : cells)
2488 for (int i = 0; i != 4; ++i)
2489 ++count[cellFace(cell, i)];
2490 std::set<Face> boundary;
2491 for (const auto &[key, n] : count) {
2492 if (n > 2)
2493 THROW_MESSAGE("Crack extension cavity is not a manifold");
2494 if (n == 1)
2495 boundary.insert(key);
2496 }
2497 return boundary;
2498 };
2499 std::vector<Cell> removed_cells;
2500 for (int c : removed)
2501 removed_cells.push_back(patch.cells[c]);
2502 if (cavity_boundary(removed_cells) != cavity_boundary(candidate.createdCells))
2503 THROW_MESSAGE("Crack extension created cells do not fill the cavity");
2504
2505 // Build the result before changing the patch.
2506 auto points = patch.points;
2507 points[w] = add(points[w], candidate.displacement);
2508 std::vector<Cell> cells;
2509 std::vector<int> labels, partitions;
2510 for (int c = 0, r = 0; c != nc; ++c) {
2511 if (r < static_cast<int>(removed.size()) && removed[r] == c) {
2512 ++r;
2513 continue;
2514 }
2515 // Retained cells around the moved node stay positively oriented.
2516 const auto &cell = patch.cells[c];
2517 if (moves && std::count(cell.begin(), cell.end(), w)) {
2518 const auto &p = patch.points;
2519 const int before =
2520 orientation(p[cell[0]], p[cell[1]], p[cell[2]], p[cell[3]]);
2521 const int after = orientation(points[cell[0]], points[cell[1]],
2522 points[cell[2]], points[cell[3]]);
2523 if (before <= 0 || after <= 0)
2524 THROW_MESSAGE("Crack extension move inverts a retained cell");
2525 }
2526 cells.push_back(cell);
2527 if (has_labels)
2528 labels.push_back(patch.cellLabels[c]);
2529 if (has_partitions)
2530 partitions.push_back(patch.partitions[c]);
2531 }
2532 for (std::size_t i = 0; i != candidate.createdCells.size(); ++i) {
2533 const auto &cell = candidate.createdCells[i];
2534 if (orientation(points[cell[0]], points[cell[1]], points[cell[2]],
2535 points[cell[3]]) <= 0)
2536 THROW_MESSAGE("Crack extension created cell is not positive");
2537 cells.push_back(cell);
2538 const int p = candidate.createdParents[i];
2539 if (has_labels)
2540 labels.push_back(patch.cellLabels[p]);
2541 if (has_partitions)
2542 partitions.push_back(patch.partitions[p]);
2543 }
2544 std::map<Face, int> count;
2545 for (const auto &cell : cells)
2546 for (int i = 0; i != 4; ++i)
2547 ++count[cellFace(cell, i)];
2548 for (const auto &[key, n] : count)
2549 if (n > 2)
2550 THROW_MESSAGE("Crack extension result has a face with three cells");
2551 for (const auto &a : added)
2552 if (count[a] != 2)
2553 THROW_MESSAGE("Crack extension face is not interior after application");
2554
2555 // Publish.
2556 patch.points.swap(points);
2557 patch.cells.swap(cells);
2558 if (has_labels)
2559 patch.cellLabels.swap(labels);
2560 if (has_partitions)
2561 patch.partitions.swap(partitions);
2562 const int crack_label = crack_faces.empty() || patch.surfaceLabels.empty()
2563 ? 0
2564 : patch.surfaceLabels[crack_faces.front()];
2565 for (std::size_t i = 0; i != added.size(); ++i) {
2566 patch.boundary.push_back(i ? candidate.closureFaces[i - 1] : f);
2567 if (!patch.surfaceLabels.empty())
2568 patch.surfaceLabels.push_back(crack_label);
2569 crack_faces.push_back(patch.boundary.size() - 1);
2570 }
2571}
std::map< EntityHandle, int > labels
CGALTools::CrackExtensionCandidate candidate
int boundary
const std::vector< Vec > * points
std::vector< int > removed
std::vector< int > size
int w
Free node.
std::vector< Cell > cells
ParentChildKey key
It end
Definition Schur.cpp:2568
constexpr double a
#define THROW_MESSAGE(msg)
Throw MoFEM exception.
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)
int r
Definition sdf.py:205

◆ crackClosureCandidates()

std::vector< CGALTools::CrackExtensionCandidate > MoFEM::CGALTools::crackClosureCandidates ( const TetMeshData &  patch,
const std::vector< int > &  crack_faces,
std::array< int, 2 >  front_edge,
std::array< double, 3 >  direction,
const CrackExtensionSettings &  settings,
CrackExtensionReport *  report = nullptr 
) const

Candidates that close a gap at front_edge whose closing face is missing: the free node is a crack node joined to an end of the edge by a front edge and ahead of it, and the face (f0, f1, w) closes that corner. The face exists, one edge removal makes it, or removing the edges that cross it recovers it. Same contract and ranking as crackExtensionCandidates; only class 1 applies.

Definition at line 2384 of file CgalCrackExtension.cpp.

2389 {
2390 CrackExtensionReport local;
2391 return searchCandidates(patch, crack_faces, front_edge, direction, settings,
2392 report ? *report : local, SearchMode::Closure);
2393}
Report & report
const Settings & settings

◆ crackExtensionCandidates()

std::vector< CGALTools::CrackExtensionCandidate > MoFEM::CGALTools::crackExtensionCandidates ( const TetMeshData &  patch,
const std::vector< int > &  crack_faces,
std::array< int, 2 >  front_edge,
std::array< double, 3 >  direction,
const CrackExtensionSettings &  settings,
CrackExtensionReport *  report = nullptr 
) const

Candidates for extending the crack by one face at front_edge. patch: cells positively oriented, det(p1-p0, p2-p0, p3-p0) > 0; a non-positive cell in the region is rejected, not flipped, since flipping cannot tell an inverted element from reversed vertex order. boundary holding crack faces and protected faces (body skin, interfaces), optional cellLabels, featureEdges (geometry curves) and fixedVertices. crack_faces index patch.boundary. front_edge (point indices) must be an interior edge of exactly one crack face. direction is the extension direction; its component orthogonal to the edge is used and must point away from that crack face. No point is created, no fixed entity changes and no cell outside settings.ringLimit vertex rings changes. A non-convex front corner at a new edge (its two front edges open away from the crack behind it; a sign test, no threshold) is closed by the face spanning them, existing or created by one forced edge removal; closures repeat at the new edges they create. With lookAheadCandidates > 0, retain a bounded shortlist including alternative ring triangulations, and preview one further extension within the original region. Returns candidates by operation (gap, join, flip-only advance, vertex move), then class, open corners and continuation feasibility. Future closure, join and flip-only advance precede a future move; quality score and free node break remaining ties. Empty means no admissible extension. Throws MoFEMException on invalid input, or on an audit failure.

Definition at line 2372 of file CgalCrackExtension.cpp.

2377 {
2378 CrackExtensionReport local;
2379 return searchCandidates(patch, crack_faces, front_edge, direction, settings,
2380 report ? *report : local, SearchMode::Extension);
2381}

◆ crackFillFaces()

std::vector< std::array< int, 3 > > MoFEM::CGALTools::crackFillFaces ( const TetMeshData &  patch,
const std::vector< int > &  crack_faces 
) const

Faces that close notches of the crack front, by the edge-based rule of the fracture module. An interior face that is not protected joins the crack when two of its edges lie on the crack boundary and their common node does not turn the crack back, when all three edges do (or two do and the third is on the body skin), or when one does and another is a feature edge. A face is also rejected if a cell next to it would get two crack faces or three crack or skin faces. Iterated to a fixed point; returns the faces in the order they were added. A face sharing only one crack edge cannot reconnect to the same crack component at its third vertex: that would create a new hole. The patch is not modified.

Definition at line 2590 of file CgalCrackExtension.cpp.

2591 {
2592 checkPatchIndices(patch, crack_faces, "crack fill");
2593 const PatchTopology topology(patch, crack_faces);
2594 auto crack = topology.crack;
2595 CrackComponents components(patch.points.size(), crack);
2596 EdgeSet features;
2597 for (const auto &e : patch.featureEdges)
2598 features.insert(edgeKey(e[0], e[1]));
2599 const auto &p = patch.points;
2600 // A cell next to a filled face must not fold or dangle.
2601 const auto folds = [&](const Face &face) {
2602 for (int c : topology.faceCells.at(face)) {
2603 const auto count = countCellFaces(
2604 patch.cells[c],
2605 [&](const Face &f) { return f == face || crack.count(f) != 0; },
2606 [&](const Face &f) { return topology.skin.count(f) != 0; });
2607 if (foldsOrDangles(count))
2608 return true;
2609 }
2610 return false;
2611 };
2612 // Sum of the angles at v of the crack faces around v.
2613 const auto sector = [&](int v) {
2614 double sum = 0;
2615 for (const auto &face : crack)
2616 if (std::count(face.begin(), face.end(), v)) {
2617 int other[2], k = 0;
2618 for (int u : face)
2619 if (u != v)
2620 other[k++] = u;
2621 sum += angleAt(p[v], p[other[0]], p[other[1]]);
2622 }
2623 return sum;
2624 };
2625
2626 std::vector<std::array<int, 3>> added;
2627 for (;;) {
2628 auto crack_edge_count = crackEdgeCounts(crack);
2629 // The crack at the start of the pass: its edges, and the edges with one
2630 // crack face, on the front or on the skin.
2631 EdgeSet crack_edges, boundary;
2632 std::set<int> boundary_nodes;
2633 for (const auto &[e, count] : crack_edge_count) {
2634 crack_edges.insert(e);
2635 if (count == 1) {
2636 boundary.insert(e);
2637 boundary_nodes.insert(e[0]);
2638 boundary_nodes.insert(e[1]);
2639 }
2640 }
2641 std::set<Face> candidates;
2642 for (const auto &e : boundary)
2643 for (const auto &face : facesOf(topology, e))
2644 if (!crack.count(face) && !topology.protectedFaces.count(face) &&
2645 topology.faceCells.at(face).size() == 2)
2646 candidates.insert(face);
2647 std::vector<Face> accepted;
2648 for (const auto &face : candidates) {
2649 std::vector<Edge> edges;
2650 for (const auto &e : faceEdges(face))
2651 if (boundary.count(e))
2652 edges.push_back(e);
2653 const std::size_t on_front = edges.size();
2654 if (on_front == 2)
2655 for (const auto &e : faceEdges(face))
2656 if (topology.skinEdges.count(e) &&
2657 std::find(edges.begin(), edges.end(), e) == edges.end())
2658 edges.push_back(e);
2659 bool fill = false;
2660 if (edges.size() == 2) {
2661 int adjacent_crack = 0;
2662 for (const auto &e : edges)
2663 for (const auto &f : facesOf(topology, e))
2664 adjacent_crack += crack.count(f);
2665 int apex = -1;
2666 for (int v : edges[0])
2667 if ((v == edges[1][0] || v == edges[1][1]) && boundary_nodes.count(v))
2668 apex = v;
2669 if (adjacent_crack == 2 && apex >= 0) {
2670 bool interior = false;
2671 for (const auto &e : crack_edges)
2672 if ((e[0] == apex || e[1] == apex) && !boundary.count(e))
2673 interior = true;
2674 // The corner at the apex must be re-entrant: the crack faces
2675 // around it span more than half a turn, so filling does not turn
2676 // the crack back. Without interior edges the face joins two fans.
2677 fill = !interior || sector(apex) > M_PI;
2678 }
2679 } else if (edges.size() == 3) {
2680 fill = true;
2681 }
2682 if (on_front == 1) {
2683 for (const auto &e : faceEdges(face))
2684 if (features.count(e) &&
2685 std::find(edges.begin(), edges.end(), e) == edges.end())
2686 edges.push_back(e);
2687 fill = edges.size() == 2;
2688 }
2689 // Never a third crack face on an edge, also among faces of one pass.
2690 for (const auto &e : faceEdges(face)) {
2691 const auto it = crack_edge_count.find(e);
2692 fill &= it == crack_edge_count.end() || it->second < 2;
2693 }
2694 if (fill && !components.createsCycle(face, crack_edge_count) &&
2695 !folds(face)) {
2696 crack.insert(face);
2697 components.addFace(face);
2698 for (const auto &e : faceEdges(face))
2699 ++crack_edge_count[e];
2700 accepted.push_back(face);
2701 }
2702 }
2703 if (accepted.empty())
2704 break;
2705 for (const auto &face : accepted)
2706 added.push_back(face);
2707 }
2708 return added;
2709}
FaceSet protectedFaces
FaceMap< std::vector< int > > faceCells
bool topology
EdgeSet skinEdges
FaceSet crack
int components
Inferred from the source tag length.
It it
Definition Schur.cpp:2568
const char features[]
FTensor::Index< 'k', 3 > k

◆ crackJoinFaces()

std::vector< CGALTools::CrackJoinFace > MoFEM::CGALTools::crackJoinFaces ( const TetMeshData &  patch,
const std::vector< int > &  crack_faces,
const std::vector< std::array< int, 2 > > &  front_order = {},
const std::function< bool(const std::array< int, 3 > &)> &  accept_face = {} 
) const

Faces that join the crack front to the existing crack, without moving any node. A face through a front edge (f0, f1) qualifies when its third node w is a crack node ahead of the edge, or a skin node that ends the crack on the skin or closes a front corner along it; the face exists in the mesh between two cells; it is neither a crack nor a protected face; no edge would get a third crack face; and no cell next to it would then be bounded by crack and skin faces only. Categories are tried in their order; within a category the face best aligned with the edge's extension direction wins. Applied greedily, one face at a time, to a fixed point; returns the faces in the order they were added. A point contact back to the same connected crack component is rejected when only one edge is shared, since it would create a new hole. Joining separate components and filling an existing hole remain allowed. With front_order, consider only listed edges and return one join, prioritising edge order before category/alignment. An optional accept_face predicate further restricts eligible faces before ranking; it never bypasses the topology checks. Its face is ordered (f0, f1, w). The patch is not modified.

Definition at line 2711 of file CgalCrackExtension.cpp.

2714 {
2715 using Join = CrackJoinFace;
2716 checkPatchIndices(patch, crack_faces, "crack join");
2717 const PatchTopology topology(patch, crack_faces);
2718 auto crack = topology.crack;
2719 CrackComponents components(patch.points.size(), crack);
2720 const auto &skin_edges = topology.skinEdges;
2721 const int np = patch.points.size();
2722 const auto &p = patch.points;
2723 EdgeMap<std::size_t> priority;
2724 for (std::size_t i = 0; i != front_order.size(); ++i) {
2725 const auto &edge = front_order[i];
2726 if (edge[0] < 0 || edge[1] < 0 || edge[0] >= np || edge[1] >= np ||
2727 edge[0] == edge[1])
2728 THROW_MESSAGE("Crack join front order has an invalid edge");
2729 priority.emplace(edgeKey(edge[0], edge[1]), i);
2730 }
2731
2732 std::vector<Join> joined;
2733 for (std::size_t guard = 0; guard != patch.cells.size() + 1; ++guard) {
2734 // Crack state: faces per edge, front edges and nodes, faces per vertex.
2735 const auto count = crackEdgeCounts(crack);
2736 std::vector<char> crack_node(np, 0), front_node(np, 0);
2737 std::unordered_map<int, std::vector<Face>> vertex_faces;
2738 for (const auto &face : crack)
2739 for (int v : face) {
2740 crack_node[v] = 1;
2741 vertex_faces[v].push_back(face);
2742 }
2743 std::vector<Edge> front;
2744 for (const auto &[e, n] : count)
2745 if (n == 1 && !skin_edges.count(e)) {
2746 front.push_back(e);
2747 front_node[e[0]] = front_node[e[1]] = 1;
2748 }
2749 std::sort(front.begin(), front.end());
2750 const auto pinched = [&](int v, const Face &added) {
2751 auto fan = vertex_faces[v];
2752 fan.push_back(added);
2753 return !singleFan(fan, v);
2754 };
2755 // Category 3: an end s of the front edge e and w share a skin edge; the
2756 // other end o has a second front edge (o, g) with (w, g) a skin edge,
2757 // and the face (o, w, g), which then closes the corner, exists.
2758 const auto closes_along_skin = [&](const Edge &e, int w) {
2759 for (int k = 0; k != 2; ++k) {
2760 const int s = e[k], o = e[1 - k];
2761 if (!skin_edges.count(edgeKey(s, w)))
2762 continue;
2763 for (const auto &other : front) {
2764 if (other == e || (other[0] != o && other[1] != o))
2765 continue;
2766 const int g = other[0] == o ? other[1] : other[0];
2767 const auto closing = faceKey(o, w, g);
2768 const auto it = topology.faceCells.find(closing);
2769 if (skin_edges.count(edgeKey(w, g)) &&
2770 it != topology.faceCells.end() && it->second.size() == 2 &&
2771 !topology.protectedFaces.count(closing))
2772 return true;
2773 }
2774 }
2775 return false;
2776 };
2777
2778 Join best;
2779 std::size_t best_priority = front_order.size();
2780 double best_alignment = -2;
2781 for (const auto &e : front) {
2782 const auto it_priority = priority.find(e);
2783 if (!front_order.empty() && it_priority == priority.end())
2784 continue;
2785 const auto edge_priority = front_order.empty() ? 0 : it_priority->second;
2786 // Extension direction: in the crack face, orthogonal to e, away.
2787 int apex = -1;
2788 for (const auto &face : facesOf(topology, e))
2789 if (crack.count(face))
2790 for (int v : face)
2791 if (v != e[0] && v != e[1])
2792 apex = v;
2793 if (apex < 0)
2794 continue;
2795 const auto t = sub(p[e[1]], p[e[0]]);
2796 const auto m = mul(add(p[e[0]], p[e[1]]), 0.5);
2797 auto d = sub(m, p[apex]);
2798 d = sub(d, mul(t, dot(d, t) / dot(t, t)));
2799 if (!(norm(d) > 0))
2800 continue;
2801 d = mul(d, 1 / norm(d));
2802 for (const auto &face : facesOf(topology, e)) {
2803 if (crack.count(face) || topology.protectedFaces.count(face) ||
2804 topology.faceCells.at(face).size() != 2)
2805 continue;
2806 int w = -1;
2807 for (int v : face)
2808 if (v != e[0] && v != e[1])
2809 w = v;
2810 if (accept_face && !accept_face({e[0], e[1], w}))
2811 continue;
2812 const bool ends_on_skin = skin_edges.count(edgeKey(e[0], w)) &&
2813 skin_edges.count(edgeKey(e[1], w));
2814 const bool along_skin = !crack_node[w] && closes_along_skin(e, w);
2815 if (!crack_node[w] && !ends_on_skin && !along_skin)
2816 continue;
2817 const auto r = sub(p[w], m);
2818 if (!(dot(r, d) > 0))
2819 continue; // Behind the front edge: a fold onto the crack.
2820 bool cut_free = false;
2821 for (int c : topology.faceCells.at(face))
2822 cut_free |= cutFree(countCellFaces(
2823 patch.cells[c],
2824 [&](const Face &f) { return f == face || crack.count(f) != 0; },
2825 [&](const Face &f) { return topology.skin.count(f) != 0; }));
2826 if (cut_free)
2827 continue;
2828 // No edge may get a third crack face: a fin along the crack.
2829 bool closes = false, manifold = true;
2830 for (const auto &edge : faceEdges(face)) {
2831 const auto it = count.find(edge);
2832 const int n = (it == count.end() ? 0 : it->second) + 1;
2833 manifold &= n <= 2;
2834 closes |= edge != e && n == 2;
2835 }
2836 if (!manifold || components.createsCycle(face, count))
2837 continue;
2838 int category = Join::AtCrackSurface;
2839 if (ends_on_skin && !crack_node[w])
2840 category = Join::EndingOnSkin;
2841 else if (along_skin)
2842 category = Join::ClosingAlongSkin;
2843 else if (closes && !pinched(e[0], face) && !pinched(e[1], face) &&
2844 !pinched(w, face))
2845 category = Join::ClosingFront;
2846 else if (front_node[w])
2847 category = Join::AtFrontNode;
2848 const double alignment = dot(r, d) / norm(r);
2849 if (!best.category || edge_priority < best_priority ||
2850 (edge_priority == best_priority &&
2851 (category < best.category ||
2852 (category == best.category && alignment > best_alignment)))) {
2853 best.face = {e[0], e[1], w};
2854 best.category = category;
2855 best_alignment = alignment;
2856 best_priority = edge_priority;
2857 }
2858 }
2859 }
2860 if (!best.category)
2861 break;
2862 crack.insert(faceKey(best.face[0], best.face[1], best.face[2]));
2863 components.addFace(best.face);
2864 joined.push_back(best);
2865 if (!front_order.empty())
2866 break;
2867 }
2868 return joined;
2869}
size_t best
Definition CGALTools.cpp:63
Vec t
Removal: the ring edge.
Edge closing
Its edge allowed to join two crack nodes.
FTensor::Index< 'm', 3 > m

◆ crackJoiningCandidates()

std::vector< CGALTools::CrackExtensionCandidate > MoFEM::CGALTools::crackJoiningCandidates ( const TetMeshData &  patch,
const std::vector< int > &  crack_faces,
std::array< int, 2 >  front_edge,
std::array< double, 3 >  direction,
const CrackExtensionSettings &  settings,
CrackExtensionReport *  report = nullptr 
) const

Join the front without moving vertices, recovering a missing face by flips. The recovered result must pass the same hole, pocket and edge manifold checks as crackJoinFaces. joinGapsOnly restricts this to a face sharing at least two existing crack edges. Same publication contract as crackExtensionCandidates.

Definition at line 2396 of file CgalCrackExtension.cpp.

2401 {
2402 CrackExtensionReport local;
2403 return searchCandidates(patch, crack_faces, front_edge, direction, settings,
2404 report ? *report : local, SearchMode::Joining);
2405}

◆ createDelaunay()

void MoFEM::CGALTools::createDelaunay ( CGALMesh &  mesh,
const std::vector< std::array< double, 3 > > &  points,
const std::vector< std::uint64_t > &  identifiers = {} 
) const

Replace mesh with the Delaunay triangulation of points. Identifiers are opaque provenance; zero means an unlinked vertex. An empty identifiers vector assigns zero to every vertex. Nonzero IDs must be unique. Coincident or non-finite points are rejected with MoFEMException, leaving mesh unchanged.

Definition at line 2123 of file CGALTools.cpp.

2125 {
2126 if (!identifiers.empty() && identifiers.size() != points.size())
2127 THROW_MESSAGE("CGAL point and identifier counts differ");
2128
2129 CGALMesh result;
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}
TetMeshData result
WorkMesh mesh

◆ createImplicitMesh()

void MoFEM::CGALTools::createImplicitMesh ( TetMeshData &  result,
const std::function< double(const std::array< double, 3 > &)> &  sdf,
const ImplicitMeshSettings &  settings 
) const

Mesh a closed negative implicit region strictly inside the bounding sphere. Sequential Mesh_3; no optimisation. Throws before replacing the result.

Examples
mesh_reconstruction.cpp.

Definition at line 14 of file CgalImplicitMesh.cpp.

17 {
18 using K = CGAL::Exact_predicates_inexact_constructions_kernel;
19 using Domain = CGAL::Labeled_mesh_domain_3<K>;
20 using Tr = CGAL::Mesh_triangulation_3<Domain, CGAL::Default,
21 CGAL::Sequential_tag>::type;
22 using Complex = CGAL::Mesh_complex_3_in_triangulation_3<Tr>;
23 for (double x : {s.radius, s.facetAngle, s.facetSize, s.facetDistance,
24 s.cellSize, s.cellRadiusEdgeRatio, s.relativeError})
25 if (!std::isfinite(x) || x <= 0)
26 throw std::invalid_argument(
27 "Implicit mesh criteria must be finite and positive");
28 for (auto x : s.centre)
29 if (!std::isfinite(x))
30 throw std::invalid_argument("Non-finite bounding sphere centre");
31 if (!sdf || !std::isfinite(s.isovalue) || s.facetAngle > 30 ||
32 s.cellRadiusEdgeRatio <= 2 || s.relativeError >= 1 ||
33 !std::isfinite(s.radius * s.radius))
34 throw std::invalid_argument("Invalid implicit mesh function or criteria");
35 auto function = [&](const K::Point_3 &p) {
36 const double v = sdf({CGAL::to_double(p.x()), CGAL::to_double(p.y()),
37 CGAL::to_double(p.z())}) -
38 s.isovalue;
39 if (!std::isfinite(v))
40 throw std::invalid_argument(
41 "Implicit function returned a non-finite value");
42 return v;
43 };
44 auto domain = Domain::create_implicit_mesh_domain(
45 function,
46 K::Sphere_3(K::Point_3(s.centre[0], s.centre[1], s.centre[2]),
47 s.radius * s.radius),
48 CGAL::parameters::relative_error_bound(s.relativeError));
49 CGAL::Mesh_criteria_3<Tr> criteria(
50 CGAL::parameters::facet_angle(s.facetAngle)
51 .facet_size(s.facetSize)
52 .facet_distance(s.facetDistance)
53 .cell_radius_edge_ratio(s.cellRadiusEdgeRatio)
54 .cell_size(s.cellSize));
55 auto mesh = CGAL::make_mesh_3<Complex>(
56 domain, criteria, CGAL::parameters::no_perturb().no_exude(),
57 CGAL::parameters::mesh_3_options(
58 CGAL::parameters::number_of_initial_points(64)));
59 if (!mesh.number_of_cells_in_complex())
60 throw std::runtime_error("Implicit domain produced no tetrahedra");
61 TetMeshData next;
62 std::map<Tr::Vertex_handle, int> indices;
63 auto index = [&](Tr::Vertex_handle v) {
64 auto it = indices.find(v);
65 if (it != indices.end())
66 return it->second;
67 if (next.points.size() >=
68 static_cast<size_t>(std::numeric_limits<int>::max()))
69 throw std::length_error("Implicit mesh exceeds integer index range");
70 const int n = next.points.size();
71 const auto &p = v->point().point();
72 next.points.push_back({CGAL::to_double(p.x()), CGAL::to_double(p.y()),
73 CGAL::to_double(p.z())});
74 next.vertexIds.push_back(n + 1);
75 indices.emplace(v, n);
76 return n;
77 };
78 for (auto c = mesh.cells_in_complex_begin(); c != mesh.cells_in_complex_end();
79 ++c) {
80 next.cells.push_back({index(c->vertex(0)), index(c->vertex(1)),
81 index(c->vertex(2)), index(c->vertex(3))});
82 next.cellLabels.push_back(mesh.subdomain_index(c));
83 }
84 for (auto f = mesh.facets_in_complex_begin();
85 f != mesh.facets_in_complex_end(); ++f) {
86 std::array<int, 3> face;
87 int n = 0;
88 for (int d = 0; d != 4; ++d)
89 if (d != f->second)
90 face[n++] = index(f->first->vertex(d));
91 next.boundary.push_back(face);
92 // A single implicit region has one boundary patch.
93 next.surfaceLabels.push_back(1);
94 }
95 result = std::move(next);
96}
std::map< EntityHandle, int > index
std::string type
Definition sdf.py:1

◆ findVertexParents()

std::vector< std::uint64_t > MoFEM::CGALTools::findVertexParents ( const std::vector< std::array< double, 3 > > &  points,
const std::vector< Simplex > &  sources 
) const

Return the lowest-dimensional containing source simplex for each point. Sources are nondegenerate segments, triangles or tetrahedra with unique, nonzero identifiers. Exact predicates classify the supplied coordinates. Missing or ambiguous parents throw MoFEMException.

Definition at line 2045 of file CGALTools.cpp.

2046 {
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}
std::vector< int > source
std::vector< int > vertices
std::vector< int > parent
CGAL::Exact_predicates_inexact_constructions_kernel Kernel

◆ reconstructDelaunay()

std::vector< int > MoFEM::CGALTools::reconstructDelaunay ( TetMeshData &  result,
const TetMeshData &  vertices,
ReconstructionMethod  method = ReconstructionMethod::PointDelaunay 
) const

Reconstruct using exactly the given coordinates and IDs. PointDelaunay fills the convex hull; validateReconstruction is separate. ConstrainedStrict (CGAL 6.2) requires source cells, the complete exterior and protected internal boundary facets with positive surfaceLabels. Exactly planar, equally classified simple patches may reconnect; seams and featureEdges stay constrained. Physical volume classification is uniform. Outside cells are removed. If CGAL inserts points, throws before replacing result; there is no permissive fallback. Returns source.boundary parent indices for constrained result.boundary, or empty for point mode. surfaceFlipAngle applies only to point-mode validation.

Definition at line 1664 of file CGALTools.cpp.

1665 {
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 }
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;
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}
void createDelaunay(CGALMesh &mesh, const std::vector< std::array< double, 3 > > &points, const std::vector< std::uint64_t > &identifiers={}) const

◆ remesh()

void MoFEM::CGALTools::remesh ( TetMeshData &  result,
const TetMeshData &  source,
const std::vector< int > &  selected_cells,
const RemeshSettings &  settings,
RemeshReport &  report 
) const

Improve existing connectivity in one conforming triangulation. selected_cells contains source cell indices; empty selects nothing. CGAL 6.2 constrained construction supports non-convex domains and cavities. Unselected cell faces constrain recovery; conforming subdivision may change neighbours. The selection grows around intersecting auxiliary support near invalid source cells. Physical constraints must form a valid PLC. Supplied boundary triangles include internal patches. Feature curves and fixed vertices are respected. New/moved points receive fresh positive IDs. A zero targetEdgeLength runs constraint recovery only: all source vertices keep coordinates and IDs, and only recovery may add Steiner points. No isotropic remeshing or quality-improvement requirement is applied. Geometry-tolerance exceedances warn on the tagged CGALTools channel. Validity, topology and quality failures throw MoFEMException without replacing result/report.

Definition at line 922 of file CGALTools.cpp.

925 {
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}
std::vector< std::array< EntityHandle, 3 > > faces
Sorted keys.
std::vector< std::array< EntityHandle, 2 > > curves
Sorted keys.
const Triangles & triangles
Definition CGALTools.cpp:60
bool selected
Definition CGALTools.cpp:97
std::vector< int > label
std::unordered_map< int, NodeConstraint > constraints
bool active
std::map< EntityHandle, std::pair< bool, std::vector< double > > > previous
std::vector< std::array< double, 3 > > coordinates
int nb
number of DOFs
Definition Schur.cpp:2505
SmartPetscObj< Vec > values
FTensor::Index< 'j', 3 > j
double scale
Definition plastic.cpp:124

◆ validateReconstruction()

std::vector< int > MoFEM::CGALTools::validateReconstruction ( const TetMeshData &  source,
TetMeshData &  result,
const std::vector< std::array< int, 2 > > &  protected_edges = {},
const std::function< void(const std::string &)> &  warning = {} 
) const

Validate surface preservation before importing reconstruction into MOAB. source.boundary contains exterior/protected triangles, grouped by identical classification in source.surfaceLabels. Adjacent facets below surfaceFlipAngle may reconnect, preserving topology, boundary and vertex IDs. Above-threshold edges remain fixed. Nonzero angles permit changes to piecewise-planar geometry, with local normal deviations bounded. Explicit protected edges use source point indices. Returns source.boundary parent indices for result.boundary, which is replaced by the preserved patches. Disconnected reconstructed vertex links and their associated patch defects are logged on CGALTools and reported to the optional warning observer; the available patch is retained for inspection. Throws if constraint recovery is needed; this is not a constrained CDT.

Definition at line 1718 of file CGALTools.cpp.

1721 {
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}
double distance
Definition CGALTools.cpp:64
double length
static const double eps
double sign(double x)
double surfaceFlipAngle
Definition CGALTools.hpp:73

Member Data Documentation

◆ surfaceFlipAngle

double MoFEM::CGALTools::surfaceFlipAngle = 1e-6

Maximum accepted surface flip angle in degrees, measured between facet planes (0 is flat, range 0..90). Used by validated reconstruction; point triangulation itself remains unconstrained.

Definition at line 73 of file CGALTools.hpp.


The documentation for this struct was generated from the following files: