v0.16.3
Loading...
Searching...
No Matches
CGALTools.hpp
Go to the documentation of this file.
1/** \file CGALTools.hpp
2 * \brief CGAL algorithms independent of the MoFEM/MOAB database.
3 */
4#ifndef MOFEM_CGAL_TOOLS_HPP
5#define MOFEM_CGAL_TOOLS_HPP
6
7#include <array>
8#include <cstdint>
9#include <vector>
10#include <functional>
11#include <string>
12
13namespace MoFEM {
14
15/** Indexed linear tetrahedral mesh exchanged by algorithms and bridges. */
17 std::vector<std::array<double, 3>> points;
18 std::vector<int> vertexIds;
19 std::vector<std::array<int, 4>> cells; ///< Zero-based point indices.
20 std::vector<std::array<int, 3>> boundary;
21 std::vector<int> cellLabels, surfaceLabels;
22 std::vector<int> partitions; ///< Optional cell-to-rank assignment.
23 std::vector<std::array<int, 2>> featureEdges;
24 std::vector<int> edgeLabels;
25 std::vector<int>
26 fixedVertices; ///< Point indices which cannot move or collapse.
27};
28
29struct CGALMesh;
30
31struct CGALTools {
33 double targetEdgeLength = 0; ///< Zero: constraint recovery only.
34 unsigned iterations = 1; ///< Used only for a positive target length.
35 bool remeshSurfaces = true;
36 double creaseAngle =
37 30; ///< Facet-plane angle above which edges are features.
40 1e-3; ///< Quality floor for size-driven remeshing, not recovery only.
41 };
42
43 struct RemeshReport {
45 std::vector<int>
46 changedCells; ///< Source cell indices, including neighbours.
48 };
49
50 /** Improve existing connectivity in one conforming triangulation.
51 * selected_cells contains source cell indices; empty selects nothing.
52 * CGAL 6.2 constrained construction supports non-convex domains and cavities.
53 * Unselected cell faces constrain recovery; conforming subdivision may change
54 * neighbours. The selection grows around intersecting auxiliary support near
55 * invalid source cells. Physical constraints must form a valid PLC.
56 * Supplied boundary triangles include internal patches. Feature curves and
57 * fixed vertices are respected. New/moved points receive fresh positive IDs.
58 * A zero targetEdgeLength runs constraint recovery only: all source vertices
59 * keep coordinates and IDs, and only recovery may add Steiner points. No
60 * isotropic remeshing or quality-improvement requirement is applied.
61 * Geometry-tolerance exceedances warn on the tagged CGALTools channel.
62 * Validity, topology and quality failures throw MoFEMException without
63 * replacing result/report.
64 */
66 const std::vector<int> &selected_cells,
68
69 /** Maximum accepted surface flip angle in degrees, measured between facet
70 * planes (0 is flat, range 0..90). Used by validated reconstruction; point
71 * triangulation itself remains unconstrained.
72 */
73 double surfaceFlipAngle = 1e-6;
74
76 std::array<double, 3> centre{0, 0, 0};
77 double radius = 2, isovalue = 0;
78 double facetAngle = 25, facetSize = .25, facetDistance = .02;
79 double cellSize = .3, cellRadiusEdgeRatio = 3;
80 double relativeError = 1e-5;
81 };
82
83 /** Mesh a closed negative implicit region strictly inside the bounding sphere.
84 * Sequential Mesh_3; no optimisation. Throws before replacing the result.
85 */
88 const std::function<double(const std::array<double, 3> &)> &sdf,
89 const ImplicitMeshSettings &settings) const;
90
92
93 /** Reconstruct using exactly the given coordinates and IDs.
94 * PointDelaunay fills the convex hull; validateReconstruction is separate.
95 * ConstrainedStrict (CGAL 6.2) requires source cells, the complete exterior
96 * and protected internal boundary facets with positive surfaceLabels.
97 * Exactly planar, equally classified simple patches may reconnect; seams
98 * and featureEdges stay constrained. Physical volume classification is
99 * uniform. Outside cells are removed. If CGAL inserts points, throws before
100 * replacing result; there is no permissive fallback. Returns source.boundary
101 * parent indices for constrained result.boundary, or empty for point mode.
102 * surfaceFlipAngle applies only to point-mode validation.
103 */
104 std::vector<int> reconstructDelaunay(
107
108 /** Validate surface preservation before importing reconstruction into MOAB.
109 * source.boundary contains exterior/protected triangles, grouped by identical
110 * classification in source.surfaceLabels. Adjacent facets below
111 * surfaceFlipAngle may reconnect, preserving topology, boundary and vertex
112 * IDs. Above-threshold edges remain fixed. Nonzero angles permit changes to
113 * piecewise-planar geometry, with local normal deviations bounded. Explicit
114 * protected edges use source point indices. Returns source.boundary parent
115 * indices for result.boundary, which is replaced by the preserved patches.
116 * Disconnected reconstructed vertex links and their associated patch defects
117 * are logged on CGALTools and reported to the optional warning observer;
118 * the available patch is retained for inspection.
119 * Throws if constraint recovery is needed; this is not a constrained CDT.
120 */
121 std::vector<int> validateReconstruction(
123 const std::vector<std::array<int, 2>> &protected_edges = {},
124 const std::function<void(const std::string &)> &warning = {}) const;
125 /** Source simplex for geometric classification; identifier is opaque. */
126 struct Simplex {
127 std::uint64_t identifier;
128 std::vector<std::array<double, 3>> vertices;
129 };
130
131 /** Return the lowest-dimensional containing source simplex for each point.
132 * Sources are nondegenerate segments, triangles or tetrahedra with unique,
133 * nonzero identifiers. Exact predicates classify the supplied coordinates.
134 * Missing or ambiguous parents throw MoFEMException.
135 */
136 std::vector<std::uint64_t>
137 findVertexParents(const std::vector<std::array<double, 3>> &points,
138 const std::vector<Simplex> &sources) const;
139
140 /** Replace mesh with the Delaunay triangulation of points.
141 * Identifiers are opaque provenance; zero means an unlinked vertex.
142 * An empty identifiers vector assigns zero to every vertex. Nonzero IDs
143 * must be unique. Coincident or non-finite points are rejected with
144 * MoFEMException, leaving mesh unchanged.
145 */
147 const std::vector<std::array<double, 3>> &points,
148 const std::vector<std::uint64_t> &identifiers = {}) const;
149
150 /** Settings for crackExtensionCandidates and crackClosureCandidates, see
151 * doc/development/cgal_crack_extension_algorithm.md.
152 */
155 3; ///< Accepted angle between candidate face and target plane.
157 0.5; ///< Move bound, fraction of mean edge length at the free node.
159 1e-3; ///< Volume-length floor for created and moved cells.
160 int ringLimit = 2; ///< Vertex rings around the front edge that may change.
161 int maxFlipsPerCandidate = 12; ///< Topological operations per candidate.
162 /// Preview one further step for at most this many current candidates.
163 /// Zero disables preview and retains a single triangulation per route.
165 /// Include existing joins and standalone gap closure in the preview.
166 /// CgalCrackGrowth disables these when its join policy is disabled.
167 bool lookAheadJoin = true;
168 /// Restrict crackJoiningCandidates to faces sharing two crack edges.
169 bool joinGapsOnly = false;
170 bool stopAtFirstClass = true; ///< Return only the first successful class.
171 /// Try only the move classes (2 and 3) in an extension search; the
172 /// look-ahead preview still tries all classes. Useful when a search of
173 /// the same patch at the same tolerance found no flips-only candidate.
174 bool skipFlips = false;
175 /// Reject a candidate that leaves a non-convex front corner open at the
176 /// ends of its new edges, so a notch can never deepen into a slit.
178 bool audit = false; ///< Validate the region after every operation.
179 };
180
181 /** One admissible extension; a description, not an applied change. It is
182 * bound to the exact patch state it was generated from (patchDigest), so
183 * applying any change invalidates every other candidate. */
185 /// Candidate classes, tried in this order; see "Candidate classes".
186 enum Class {
187 Flips = 1, ///< The face exists, or one edge removal makes it.
188 PartialMove = 2, ///< The free node moves until within the tolerance.
189 OnPlaneMove = 3 ///< The free node moves onto the target plane.
190 };
191 int candidateClass = 0; ///< A Class.
192 int freeNode = -1; ///< Patch point index of the free node.
193 std::array<double, 3> displacement{0, 0, 0};
194 std::array<int, 3> newFace{-1, -1, -1}; ///< (f0, f1, freeNode).
195 std::vector<int> removedCells; ///< Sorted patch cell indices.
196 std::vector<std::array<int, 4>> createdCells; ///< Positively oriented.
197 std::vector<int>
198 createdParents; ///< Representative removed patch cell per created cell.
199 int operations = 0; ///< Node moves are not counted.
200 /// Faces closing non-convex front corners at the new edges; they join
201 /// the crack with newFace. Created by existing faces or flips.
202 std::vector<std::array<int, 3>> closureFaces;
203 int openCorners = 0; ///< Non-convex corners at new edges left open.
205 double score = 0;
206 int cardinality = 0;
207 enum Continuation { BLOCKED = -1, UNKNOWN = 0, FEASIBLE = 1 };
208 /// UNKNOWN includes a preview cut by the patch boundary or not evaluated.
210 /// Gap closure, joining and flip-only advance precede vertex movement.
213 int joinCategory = 0; ///< CrackJoinFace category for a joining candidate.
215 std::array<int, 3> continuationFace{-1, -1, -1};
217 std::uint64_t patchDigest = 0; ///< Patch state the candidate belongs to.
218 };
219
220 /** Counts of tentative operations or candidates rejected by each rule. */
222 std::size_t candidatesTried = 0, accepted = 0;
223 std::size_t rejectedBehind = 0, rejectedAngle = 0, rejectedMove = 0;
224 std::size_t rejectedInversion = 0, rejectedQuality = 0;
227 std::size_t rejectedOpenCorner = 0, rejectedPinch = 0;
228 std::size_t lookAheadTrials = 0, lookAheadFeasible = 0;
229 std::size_t lookAheadJoins = 0, lookAheadClosures = 0;
231 };
232
233 /** Candidates for extending the crack by one face at front_edge.
234 * patch: cells positively oriented, det(p1-p0, p2-p0, p3-p0) > 0; a
235 * non-positive cell in the region is rejected, not flipped, since flipping
236 * cannot tell an inverted element from reversed vertex order. boundary
237 * holding crack faces and protected faces (body skin, interfaces), optional
238 * cellLabels, featureEdges (geometry curves) and fixedVertices.
239 * crack_faces index patch.boundary. front_edge (point indices) must be an
240 * interior edge of exactly one crack face. direction is the extension
241 * direction; its component orthogonal to the edge is used and must point
242 * away from that crack face. No point is created, no fixed entity changes
243 * and no cell outside settings.ringLimit vertex rings changes. A
244 * non-convex front corner at a new edge (its two front edges open away from
245 * the crack behind it; a sign test, no threshold) is closed by the face
246 * spanning them, existing or created by one forced edge removal; closures
247 * repeat at the new edges they create. With lookAheadCandidates > 0, retain
248 * a bounded shortlist including alternative ring triangulations, and
249 * preview one further extension within the original region. Returns
250 * candidates by operation (gap, join, flip-only advance, vertex move),
251 * then class, open corners and continuation feasibility. Future closure,
252 * join and flip-only advance precede a future move; quality score and free
253 * node break remaining ties. Empty means no
254 * admissible extension. Throws MoFEMException on invalid input, or on an
255 * audit failure.
256 */
257 std::vector<CrackExtensionCandidate> crackExtensionCandidates(
258 const TetMeshData &patch, const std::vector<int> &crack_faces,
259 std::array<int, 2> front_edge, std::array<double, 3> direction,
261 CrackExtensionReport *report = nullptr) const;
262
263 /** Candidates that close a gap at front_edge whose closing face is
264 * missing: the free node is a crack node joined to an end of the edge by a
265 * front edge and ahead of it, and the face (f0, f1, w) closes that
266 * corner. The face exists, one edge removal makes it, or removing the
267 * edges that cross it recovers it. Same contract and ranking as
268 * crackExtensionCandidates; only class 1 applies.
269 */
270 std::vector<CrackExtensionCandidate> crackClosureCandidates(
271 const TetMeshData &patch, const std::vector<int> &crack_faces,
272 std::array<int, 2> front_edge, std::array<double, 3> direction,
274 CrackExtensionReport *report = nullptr) const;
275
276 /** Join the front without moving vertices, recovering a missing face by
277 * flips. The recovered result must pass the same hole, pocket and edge
278 * manifold checks as crackJoinFaces. joinGapsOnly restricts this to a
279 * face sharing at least two existing crack edges. Same publication
280 * contract as crackExtensionCandidates.
281 */
282 std::vector<CrackExtensionCandidate> crackJoiningCandidates(
283 const TetMeshData &patch, const std::vector<int> &crack_faces,
284 std::array<int, 2> front_edge, std::array<double, 3> direction,
286 CrackExtensionReport *report = nullptr) const;
287
288 /** Apply a candidate returned for this exact patch state. Rejects a
289 * candidate whose patch digest differs (stale or foreign), then validates
290 * the proposed result before changing anything: created cells fill the
291 * removed cavity and are positive after the move, retained cells around a
292 * moved node keep their orientation, no face gains a third cell, and the
293 * new face and closure faces are interior. Removed cells are erased,
294 * created cells appended with labels/partitions of their parents, the free
295 * node moved, and the new face and closure faces appended to boundary and
296 * crack_faces. Throws MoFEMException without
297 * changing patch or crack_faces.
298 */
299 void applyCrackExtension(TetMeshData &patch, std::vector<int> &crack_faces,
301
302 /** Faces that close notches of the crack front, by the edge-based rule of
303 * the fracture module. An interior face that is not protected joins the
304 * crack when two of its edges lie on the crack boundary and their common
305 * node does not turn the crack back, when all three edges do (or two do and
306 * the third is on the body skin), or when one does and another is a feature
307 * edge. A face is also rejected if a cell next to it would get two crack
308 * faces or three crack or skin faces. Iterated to a fixed point; returns
309 * the faces in the order they were added. A face sharing only one crack
310 * edge cannot reconnect to the same crack component at its third vertex:
311 * that would create a new hole. The patch is not modified.
312 */
313 std::vector<std::array<int, 3>>
314 crackFillFaces(const TetMeshData &patch,
315 const std::vector<int> &crack_faces) const;
316
317 /** A face that joins the crack front to the existing crack. */
319 /// Join categories, numbered in order of preference; see "Joining".
320 enum Category {
321 /// Closes onto another front edge; manifold, no pinch.
323 /// w is a skin node and the face's other two edges are skin edges:
324 /// the crack ends on the skin. At any angle.
326 /// Starts closing a front corner along the skin: an end of the front
327 /// edge and w share a skin edge, and the face from the other end to w
328 /// and the far node of its second front edge, also joined to w by a
329 /// skin edge, closes the corner next. At any angle.
331 /// Reaches a front node only at w: non-manifold at w.
333 /// Reaches the crack surface at w: non-manifold at w.
335 };
336 std::array<int, 3> face{-1, -1, -1}; ///< (f0, f1, w): front edge, w.
337 int category = 0; ///< A Category.
338 };
339
340 /** Faces that join the crack front to the existing crack, without moving
341 * any node. A face through a front edge (f0, f1) qualifies when its third
342 * node w is a crack node ahead of the edge, or a skin node that ends the
343 * crack on the skin or closes a front corner along it; the face exists in
344 * the mesh between two cells; it is neither a crack nor a protected face;
345 * no edge would get a third crack face; and no cell next to it would then
346 * be bounded by crack and skin faces only. Categories are tried in their
347 * order; within a category the face best aligned with the edge's extension
348 * direction wins. Applied greedily, one face at a time, to a fixed point;
349 * returns the faces in the order they were added. A point contact back to
350 * the same connected crack component is rejected when only one edge is
351 * shared, since it would create a new hole. Joining separate components
352 * and filling an existing hole remain allowed. With front_order, consider
353 * only listed edges and return one join, prioritising edge order before
354 * category/alignment. An optional accept_face predicate further restricts
355 * eligible faces before ranking; it never bypasses the topology checks.
356 * Its face is ordered (f0, f1, w). The patch is not modified.
357 */
358 std::vector<CrackJoinFace> crackJoinFaces(
359 const TetMeshData &patch, const std::vector<int> &crack_faces,
360 const std::vector<std::array<int, 2>> &front_order = {},
361 const std::function<bool(const std::array<int, 3> &)> &accept_face = {})
362 const;
363};
364
365} // namespace MoFEM
366
367#endif
TetMeshData result
CGALTools::CrackExtensionCandidate candidate
Report & report
std::vector< int > source
const Settings & settings
const std::vector< Vec > * points
WorkMesh mesh
std::vector< int > vertices
implementation of Data Operators for Forces and Sources
Definition Common.hpp:10
Definition sdf.py:1
Continuation continuation
UNKNOWN includes a preview cut by the patch boundary or not evaluated.
std::vector< int > createdParents
Representative removed patch cell per created cell.
std::vector< std::array< int, 3 > > closureFaces
std::array< int, 3 > newFace
(f0, f1, freeNode).
int joinCategory
CrackJoinFace category for a joining candidate.
std::vector< int > removedCells
Sorted patch cell indices.
ContinuationKind
Gap closure, joining and flip-only advance precede vertex movement.
int freeNode
Patch point index of the free node.
std::vector< std::array< int, 4 > > createdCells
Positively oriented.
Class
Candidate classes, tried in this order; see "Candidate classes".
@ OnPlaneMove
The free node moves onto the target plane.
@ PartialMove
The free node moves until within the tolerance.
@ Flips
The face exists, or one edge removal makes it.
std::uint64_t patchDigest
Patch state the candidate belongs to.
int openCorners
Non-convex corners at new edges left open.
double minimumQuality
Volume-length floor for created and moved cells.
double maxMoveRelative
Move bound, fraction of mean edge length at the free node.
int ringLimit
Vertex rings around the front edge that may change.
bool joinGapsOnly
Restrict crackJoiningCandidates to faces sharing two crack edges.
double angleToleranceDegrees
Accepted angle between candidate face and target plane.
bool audit
Validate the region after every operation.
std::array< int, 3 > face
(f0, f1, w): front edge, w.
Category
Join categories, numbered in order of preference; see "Joining".
@ AtFrontNode
Reaches a front node only at w: non-manifold at w.
@ AtCrackSurface
Reaches the crack surface at w: non-manifold at w.
@ ClosingFront
Closes onto another front edge; manifold, no pinch.
std::vector< int > changedCells
Source cell indices, including neighbours.
Definition CGALTools.hpp:46
double minimumQuality
Quality floor for size-driven remeshing, not recovery only.
Definition CGALTools.hpp:39
unsigned iterations
Used only for a positive target length.
Definition CGALTools.hpp:34
double creaseAngle
Facet-plane angle above which edges are features.
Definition CGALTools.hpp:36
double targetEdgeLength
Zero: constraint recovery only.
Definition CGALTools.hpp:33
std::vector< std::array< double, 3 > > vertices
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 > validateReconstruction(const TetMeshData &source, TetMeshData &result, const std::vector< std::array< int, 2 > > &protected_edges={}, const std::function< void(const std::string &)> &warning={}) const
void applyCrackExtension(TetMeshData &patch, std::vector< int > &crack_faces, const CrackExtensionCandidate &candidate) const
std::vector< int > reconstructDelaunay(TetMeshData &result, const TetMeshData &vertices, ReconstructionMethod method=ReconstructionMethod::PointDelaunay) const
std::vector< std::array< int, 3 > > crackFillFaces(const TetMeshData &patch, const std::vector< int > &crack_faces) 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< std::uint64_t > findVertexParents(const std::vector< std::array< double, 3 > > &points, const std::vector< Simplex > &sources) 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
double surfaceFlipAngle
Definition CGALTools.hpp:73
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< 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
void createDelaunay(CGALMesh &mesh, const std::vector< std::array< double, 3 > > &points, const std::vector< std::uint64_t > &identifiers={}) const
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