v0.16.3
Loading...
Searching...
No Matches
CgalCrackExtension.cpp
Go to the documentation of this file.
1/** \file CgalCrackExtension.cpp
2 * \brief Crack extension by local flips, without Steiner points.
3 *
4 * Implements CGALTools::crackExtensionCandidates and applyCrackExtension, see
5 * doc/development/cgal_crack_extension_algorithm.md. Every operation replaces
6 * a cavity whose boundary is unchanged. An operation is valid when each new
7 * cell is strictly positively oriented under exact predicates evaluated on the
8 * stored double coordinates, so the decision matches the data written back.
9 */
10#include <MoFEM.hpp>
11#include "CGALTools.hpp"
12#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
13#include <CGAL/intersections.h>
14#include <algorithm>
15#include <climits>
16#include <cmath>
17#include <limits>
18#include <map>
19#include <set>
20#include <sstream>
21#include <unordered_map>
22#include <unordered_set>
23
24namespace MoFEM {
25
26namespace {
27
28// ===========================================================================
29// Geometry and keys
30// ===========================================================================
31
32using Vec = std::array<double, 3>;
33using Edge = std::array<int, 2>;
34using Face = std::array<int, 3>;
35using Cell = std::array<int, 4>;
36using Settings = CGALTools::CrackExtensionSettings;
37using Candidate = CGALTools::CrackExtensionCandidate;
38using Report = CGALTools::CrackExtensionReport;
39
40constexpr double infinity = std::numeric_limits<double>::infinity();
41constexpr int cellEdges[6][2] = {{0, 1}, {0, 2}, {0, 3},
42 {1, 2}, {1, 3}, {2, 3}};
43constexpr int cellFaces[4][3] = {{1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2}};
44// A node sliding along an edge may also move back beyond its position, by
45// this fraction of the edge length, as in the fracture module.
46constexpr double slideBack = 0.1;
47
48struct KeyHash {
49 template <std::size_t N>
50 std::size_t operator()(const std::array<int, N> &key) const {
51 std::size_t hash = 0;
52 for (int value : key)
53 hash ^= std::hash<int>()(value) + 0x9e3779b97f4a7c15ull + (hash << 6) +
54 (hash >> 2);
55 return hash;
56 }
57};
58template <class T> using EdgeMap = std::unordered_map<Edge, T, KeyHash>;
59template <class T> using FaceMap = std::unordered_map<Face, T, KeyHash>;
60using EdgeSet = std::unordered_set<Edge, KeyHash>;
61using FaceSet = std::unordered_set<Face, KeyHash>;
62
63Edge edgeKey(int a, int b) { return a < b ? Edge{a, b} : Edge{b, a}; }
64Face faceKey(int a, int b, int c) {
65 Face face{a, b, c};
66 std::sort(face.begin(), face.end());
67 return face;
68}
69Face cellFace(const Cell &cell, int i) {
70 return faceKey(cell[cellFaces[i][0]], cell[cellFaces[i][1]],
71 cell[cellFaces[i][2]]);
72}
73std::array<Edge, 3> faceEdges(const Face &f) {
74 return {edgeKey(f[0], f[1]), edgeKey(f[1], f[2]), edgeKey(f[0], f[2])};
75}
76
77Vec sub(const Vec &a, const Vec &b) {
78 return {a[0] - b[0], a[1] - b[1], a[2] - b[2]};
79}
80Vec add(const Vec &a, const Vec &b) {
81 return {a[0] + b[0], a[1] + b[1], a[2] + b[2]};
82}
83Vec mul(const Vec &a, double s) { return {a[0] * s, a[1] * s, a[2] * s}; }
84double dot(const Vec &a, const Vec &b) {
85 return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
86}
87Vec cross(const Vec &a, const Vec &b) {
88 return {a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2],
89 a[0] * b[1] - a[1] * b[0]};
90}
91double norm(const Vec &a) { return std::sqrt(dot(a, a)); }
92/** Angle at x between the directions to a and b. */
93double angleAt(const Vec &x, const Vec &a, const Vec &b) {
94 const auto u = sub(a, x), v = sub(b, x);
95 return std::atan2(norm(cross(u, v)), dot(u, v));
96}
97bool finite(const Vec &a) {
98 return std::isfinite(a[0]) && std::isfinite(a[1]) && std::isfinite(a[2]);
99}
100
101/** Exact orientation sign of (a, b, c, d) on the stored doubles. */
102int orientation(const Vec &a, const Vec &b, const Vec &c, const Vec &d) {
103 using Point = CGAL::Exact_predicates_inexact_constructions_kernel::Point_3;
104 return static_cast<int>(
105 CGAL::orientation(Point(a[0], a[1], a[2]), Point(b[0], b[1], b[2]),
106 Point(c[0], c[1], c[2]), Point(d[0], d[1], d[2])));
107}
108
109void cellCoordinates(const Vec &a, const Vec &b, const Vec &c, const Vec &d,
110 double *coords) {
111 for (int i = 0; i != 3; ++i) {
112 coords[i] = a[i];
113 coords[3 + i] = b[i];
114 coords[6 + i] = c[i];
115 coords[9 + i] = d[i];
116 }
117}
118
119/** FNV-1a digest of every patch input a crack operation depends on. A
120 * candidate is valid only for the exact patch state it was generated from. */
121std::uint64_t patchDigest(const TetMeshData &patch,
122 const std::vector<int> &crack_faces) {
123 std::uint64_t hash = 1469598103934665603ull;
124 const auto bytes = [&hash](const void *data, std::size_t size) {
125 const auto *c = static_cast<const unsigned char *>(data);
126 for (std::size_t i = 0; i != size; ++i) {
127 hash ^= c[i];
128 hash *= 1099511628211ull;
129 }
130 };
131 const auto vector = [&](const auto &values) {
132 const std::uint64_t size = values.size();
133 bytes(&size, sizeof(size));
134 if (size)
135 bytes(values.data(), size * sizeof(values[0]));
136 };
137 vector(patch.points);
138 vector(patch.cells);
139 vector(patch.cellLabels);
140 vector(patch.boundary);
141 vector(patch.featureEdges);
142 vector(patch.fixedVertices);
143 vector(crack_faces);
144 return hash ? hash : 1;
145}
146
147// ===========================================================================
148// Patch topology and crack surface predicates, shared by extension, fill and
149// joining. Each operation states which predicates it applies; see
150// "Invariants" in doc/development/cgal_crack_extension_algorithm.md.
151// ===========================================================================
152
153/** Cell and crack face indices of a patch, for fill and joining. */
154void checkPatchIndices(const TetMeshData &patch,
155 const std::vector<int> &crack_faces,
156 const std::string &what) {
157 const int np = patch.points.size();
158 for (const auto &cell : patch.cells)
159 for (int v : cell)
160 if (v < 0 || v >= np)
161 THROW_MESSAGE("Invalid " + what + " cell index");
162 for (int i : crack_faces)
163 if (i < 0 || i >= static_cast<int>(patch.boundary.size()))
164 THROW_MESSAGE("Invalid " + what + " crack face index");
165}
166
167/** Incidence and classification of an indexed patch, built once per call.
168 * crack_faces must be valid indices into patch.boundary. Other boundary
169 * faces are protected; those with one cell are body skin. */
170struct PatchTopology {
171 FaceMap<std::vector<int>> faceCells;
172 EdgeMap<std::vector<Face>> edgeFaces; ///< Sorted faces of the cells.
173 std::vector<std::vector<int>> vertexCells;
175 EdgeSet skinEdges;
176
177 PatchTopology(const TetMeshData &patch, const std::vector<int> &crack_faces)
178 : vertexCells(patch.points.size()) {
179 for (int c = 0; c != static_cast<int>(patch.cells.size()); ++c) {
180 for (int v : patch.cells[c])
181 vertexCells[v].push_back(c);
182 for (int f = 0; f != 4; ++f)
183 faceCells[cellFace(patch.cells[c], f)].push_back(c);
184 }
185 for (const auto &[face, cells] : faceCells)
186 for (const auto &e : faceEdges(face))
187 edgeFaces[e].push_back(face);
188 for (auto &[e, faces] : edgeFaces)
189 std::sort(faces.begin(), faces.end());
190 std::vector<char> is_crack(patch.boundary.size(), 0);
191 for (int i : crack_faces)
192 is_crack[i] = 1;
193 for (std::size_t i = 0; i != patch.boundary.size(); ++i) {
194 const auto &b = patch.boundary[i];
195 const auto face = faceKey(b[0], b[1], b[2]);
196 if (is_crack[i]) {
197 crack.insert(face);
198 continue;
199 }
200 protectedFaces.insert(face);
201 const auto it = faceCells.find(face);
202 if (it != faceCells.end() && it->second.size() == 1) {
203 skin.insert(face);
204 for (const auto &e : faceEdges(face))
205 skinEdges.insert(e);
206 }
207 }
208 }
209};
210
211/** Crack faces per edge. An edge with one crack face bounds the crack: on
212 * the body skin, or on the front. */
213EdgeMap<int> crackEdgeCounts(const FaceSet &crack) {
214 EdgeMap<int> count;
215 for (const auto &face : crack)
216 for (const auto &e : faceEdges(face))
217 ++count[e];
218 return count;
219}
220
221/** Crack faces and boundary faces (crack or body skin) of a cell. */
222struct CellFaces {
223 int crack = 0, boundary = 0;
224};
225template <class IsCrack, class IsSkin>
226CellFaces countCellFaces(const Cell &cell, IsCrack is_crack, IsSkin is_skin) {
227 CellFaces count;
228 for (int f = 0; f != 4; ++f) {
229 const auto face = cellFace(cell, f);
230 const bool crack = is_crack(face);
231 count.crack += crack;
232 count.boundary += crack || is_skin(face);
233 }
234 return count;
235}
236/** Two crack faces (a fold) or three crack or skin faces (a dangling
237 * cell). Extension and fill reject such a cell. */
238bool foldsOrDangles(const CellFaces &count) {
239 return count.crack >= 2 || count.boundary >= 3;
240}
241/** Connectivity of the complete crack, including point contacts. Adding a
242 * triangle through one crack edge and a vertex of the same component creates
243 * a new cycle. Two shared edges close a corner; three can fill an old hole. */
244struct CrackComponents {
245 std::vector<int> parent, size;
246
247 CrackComponents(std::size_t count, const FaceSet &crack)
248 : parent(count), size(count, 1) {
249 for (std::size_t i = 0; i != count; ++i)
250 parent[i] = static_cast<int>(i);
251 for (const auto &face : crack)
252 addFace(face);
253 }
254
255 int root(int v) {
256 while (parent[v] != v) {
257 parent[v] = parent[parent[v]];
258 v = parent[v];
259 }
260 return v;
261 }
262
263 void addFace(const Face &face) {
264 for (int i = 1; i != 3; ++i) {
265 int a = root(face[0]), b = root(face[i]);
266 if (a == b)
267 continue;
268 if (size[a] < size[b])
269 std::swap(a, b);
270 parent[b] = a;
271 size[a] += size[b];
272 }
273 }
274
275 bool createsCycle(const Face &face, const EdgeMap<int> &edge_count) {
276 Edge shared;
277 int count = 0;
278 for (const auto &edge : faceEdges(face)) {
279 const auto it = edge_count.find(edge);
280 if (it != edge_count.end() && it->second) {
281 shared = edge;
282 ++count;
283 }
284 }
285 if (count != 1)
286 return false;
287 for (int v : face)
288 if (v != shared[0] && v != shared[1])
289 return root(v) == root(shared[0]);
290 return false;
291 }
292};
293
294/** Crack and skin faces only: the cell is cut free. Joining rejects only
295 * this, since closing a slit one element wide gives a cell two crack faces. */
296bool cutFree(const CellFaces &count) { return count.boundary == 4; }
297
298/** The crack faces at v form one fan, connected through edges at v. Two
299 * fans meeting only at v are a pinch: a non-manifold vertex. */
300bool singleFan(const std::vector<Face> &fan, int v) {
301 if (fan.size() < 2)
302 return true;
303 std::vector<char> reached(fan.size(), 0);
304 std::vector<std::size_t> stack{0};
305 reached[0] = 1;
306 std::size_t visited = 1;
307 while (!stack.empty()) {
308 const auto i = stack.back();
309 stack.pop_back();
310 for (std::size_t j = 0; j != fan.size(); ++j) {
311 if (reached[j])
312 continue;
313 int shared = 0;
314 for (int a : fan[i])
315 shared += a != v && std::count(fan[j].begin(), fan[j].end(), a);
316 if (shared) {
317 reached[j] = 1;
318 ++visited;
319 stack.push_back(j);
320 }
321 }
322 }
323 return visited == fan.size();
324}
325
326// ===========================================================================
327// Work mesh and elementary operations: the flip engine. Edge removal, 2-3
328// flips and one node move on a copy of the region, each checked before it is
329// applied; repair; the audit. Crack rules enter only through isPocket,
330// newEdgeAllowed and the fixed entities.
331// ===========================================================================
332
333/** Indexed cell complex with incremental incidence. Points are shared with the
334 * patch; a single moved vertex is overridden locally. */
335struct WorkMesh {
336 const std::vector<Vec> *points = nullptr;
337 int moved = -1;
338 Vec movedPosition{0, 0, 0};
339 std::vector<Cell> cells;
340 std::vector<char> alive;
341 std::vector<int> source, parent, label;
342 std::unordered_map<int, std::vector<int>> vertexCells;
343 EdgeMap<std::vector<int>> edgeCells;
344 FaceMap<std::vector<int>> faceCells;
345
346 const Vec &point(int v) const {
347 return v == moved ? movedPosition : (*points)[v];
348 }
349 int orient(const Cell &c) const {
350 return orientation(point(c[0]), point(c[1]), point(c[2]), point(c[3]));
351 }
352 double quality(const Cell &c) const {
353 double coords[12];
354 cellCoordinates(point(c[0]), point(c[1]), point(c[2]), point(c[3]), coords);
355 const double q = Tools::volumeLengthQuality(coords);
356 return std::isnormal(q) ? q : -2;
357 }
358 double quality(int index) const { return quality(cells[index]); }
359 double volume(const Cell &c) const {
360 double coords[12];
361 cellCoordinates(point(c[0]), point(c[1]), point(c[2]), point(c[3]), coords);
362 return Tools::tetVolume(coords);
363 }
364 template <class Map, class Key>
365 static const std::vector<int> &find(const Map &map, const Key &key) {
366 static const std::vector<int> none;
367 const auto it = map.find(key);
368 return it == map.end() ? none : it->second;
369 }
370 const std::vector<int> &cellsOf(const Edge &edge) const {
371 return find(edgeCells, edge);
372 }
373 const std::vector<int> &cellsOf(const Face &face) const {
374 return find(faceCells, face);
375 }
376 const std::vector<int> &cellsOf(int vertex) const {
377 return find(vertexCells, vertex);
378 }
379 int add(const Cell &cell, int src, int par, int lab) {
380 const int index = cells.size();
381 cells.push_back(cell);
382 alive.push_back(1);
383 source.push_back(src);
384 parent.push_back(par);
385 label.push_back(lab);
386 for (int v : cell)
387 vertexCells[v].push_back(index);
388 for (const auto &e : cellEdges)
389 edgeCells[edgeKey(cell[e[0]], cell[e[1]])].push_back(index);
390 for (int f = 0; f != 4; ++f)
391 faceCells[cellFace(cell, f)].push_back(index);
392 return index;
393 }
394 void remove(int index) {
395 alive[index] = 0;
396 const auto erase = [index](std::vector<int> &list) {
397 list.erase(std::remove(list.begin(), list.end(), index), list.end());
398 };
399 const auto &cell = cells[index];
400 for (int v : cell)
401 erase(vertexCells[v]);
402 for (const auto &e : cellEdges) {
403 const auto it = edgeCells.find(edgeKey(cell[e[0]], cell[e[1]]));
404 erase(it->second);
405 if (it->second.empty())
406 edgeCells.erase(it);
407 }
408 for (int f = 0; f != 4; ++f) {
409 const auto it = faceCells.find(cellFace(cell, f));
410 erase(it->second);
411 if (it->second.empty())
412 faceCells.erase(it);
413 }
414 }
415};
416
417enum class NodeKind { Fixed, Interior, Slide };
418/** An edge a node on a protected surface or a geometry curve may slide
419 * along: unit direction towards its other end, and its length. */
420struct Slide {
421 Vec axis{0, 0, 0};
422 double length = 0;
423};
424struct NodeConstraint {
425 NodeKind kind = NodeKind::Fixed;
426 std::vector<Slide> slides; ///< Edges a sliding node may move along.
427};
428
429struct Flags {
430 bool behind = false, angle = false, move = false, inversion = false,
431 quality = false, bridging = false, pocket = false, fixed = false,
432 topology = false, openCorner = false, pinch = false;
433 void merge(const Flags &other) {
434 behind |= other.behind;
435 angle |= other.angle;
436 move |= other.move;
437 inversion |= other.inversion;
438 quality |= other.quality;
439 bridging |= other.bridging;
440 pocket |= other.pocket;
441 fixed |= other.fixed;
442 topology |= other.topology;
443 openCorner |= other.openCorner;
444 pinch |= other.pinch;
445 }
446 void count(Report &report) const {
447 report.rejectedBehind += behind;
448 report.rejectedAngle += angle;
449 report.rejectedMove += move;
450 report.rejectedInversion += inversion;
451 report.rejectedQuality += quality;
452 report.rejectedBridging += bridging;
453 report.rejectedPocket += pocket;
454 report.rejectedFixed += fixed;
455 report.rejectedTopology += topology;
456 report.rejectedOpenCorner += openCorner;
457 report.rejectedPinch += pinch;
458 }
459};
460
461struct Context {
462 Context(const Settings &settings, Report &report,
463 const std::vector<Vec> &points)
465 const Settings &settings;
466 Report &report;
467 const std::vector<Vec> &points;
468 int f0 = -1, f1 = -1;
469 int crackApex = -1; ///< Third node of the crack face at (f0, f1).
470 Vec t{}, d{}, n{};
471 double tolerance = 0; ///< Radians.
472 FaceSet crack, protectedFaces, skin;
474 EdgeMap<int> crackEdgeCount; ///< Crack faces per edge before extension.
475 std::unordered_set<int> completeStar; ///< Vertices whose star is in region.
476 std::vector<char> crackNode;
477 std::unordered_map<int, NodeConstraint> constraints;
478 std::unordered_map<int, double> meanEdge;
479 WorkMesh base;
482 double initialVolume = 0;
483};
484
485struct Trial {
486 WorkMesh mesh;
487 int w = -1;
488 Face newFace{};
489 std::vector<Face> closures; ///< Faces closing non-convex front corners.
490 bool closureRoute = false; ///< The new face itself closes a corner.
491 bool joiningRoute = false; ///< Use the existing joining topology rules.
492 int operations = 0;
493 std::vector<int> created;
494 Flags flags;
495};
496
497struct Plan {
498 std::vector<int> removed;
499 std::vector<Cell> cells;
500 double minQuality = -infinity;
501};
502
503bool isCrack(const Context &ctx, const Trial &trial, const Face &face) {
504 return face == trial.newFace || ctx.crack.count(face) ||
505 std::find(trial.closures.begin(), trial.closures.end(), face) !=
506 trial.closures.end();
507}
508bool faceHasEdge(const Face &f, const Edge &edge) {
509 return edge == edgeKey(f[0], f[1]) || edge == edgeKey(f[1], f[2]) ||
510 edge == edgeKey(f[0], f[2]);
511}
512/** An edge of a closure face; the only created edge allowed to join two
513 * crack nodes. */
514bool isClosingEdge(const Trial &trial, const Edge &edge) {
515 if (trial.closureRoute && faceHasEdge(trial.newFace, edge))
516 return true;
517 for (const auto &f : trial.closures)
518 if (faceHasEdge(f, edge))
519 return true;
520 return false;
521}
522bool isFixedFace(const Context &ctx, const Trial &trial, const Face &face) {
523 return isCrack(ctx, trial, face) || ctx.protectedFaces.count(face);
524}
525bool isFixedEdge(const Context &ctx, const Trial &trial, const Edge &edge) {
526 return ctx.fixedEdges.count(edge) || faceHasEdge(trial.newFace, edge) ||
527 isClosingEdge(trial, edge);
528}
529
530/** A fold or a dangling cell (foldsOrDangles), or four nodes on the crack
531 * before extension (a pocket). The crack includes the trial's faces. */
532bool isPocket(const Context &ctx, const Trial &trial, const Cell &cell) {
533 const auto count = countCellFaces(
534 cell, [&](const Face &f) { return isCrack(ctx, trial, f); },
535 [&](const Face &f) { return ctx.skin.count(f) != 0; });
536 if (trial.joiningRoute)
537 return cutFree(count);
538 if (foldsOrDangles(count))
539 return true;
540 return std::all_of(cell.begin(), cell.end(),
541 [&](int v) { return ctx.crackNode[v]; });
542}
543
544/** A created edge must not join two crack nodes (a bridging edge), unless it
545 * is the allowed closing edge of a corner closure, and must not duplicate an
546 * existing edge. */
547bool newEdgeAllowed(const Context &ctx, Trial &trial, int a, int b,
548 const Edge *allowed = nullptr) {
549 if (ctx.crackNode[a] && ctx.crackNode[b] &&
550 !(trial.joiningRoute && faceHasEdge(trial.newFace, edgeKey(a, b))) &&
551 !(allowed && *allowed == edgeKey(a, b))) {
552 trial.flags.bridging = true;
553 return false;
554 }
555 if (trial.mesh.edgeCells.count(edgeKey(a, b))) {
556 trial.flags.topology = true;
557 return false;
558 }
559 return true;
560}
561
562struct Ring {
563 std::vector<int> polygon, cells;
564};
565
566/** Closed ring of the cells around edge (s, t), oriented so that every cell
567 * (s, t, p_i, p_i+1) is positive, starting at its smallest vertex. */
568bool edgeRing(const WorkMesh &mesh, int s, int t, Ring &ring) {
569 ring.polygon.clear();
570 ring.cells.clear();
571 const auto &cells = mesh.cellsOf(edgeKey(s, t));
572 if (cells.size() < 3)
573 return false;
574 std::unordered_map<int, int> successor;
575 for (int index : cells) {
576 int other[2], k = 0;
577 for (int v : mesh.cells[index])
578 if (v != s && v != t)
579 other[k++] = v;
580 const int sign = orientation(mesh.point(s), mesh.point(t),
581 mesh.point(other[0]), mesh.point(other[1]));
582 if (sign == 0)
583 return false;
584 if (sign < 0)
585 std::swap(other[0], other[1]);
586 if (!successor.emplace(other[0], other[1]).second)
587 return false;
588 }
589 int start = INT_MAX;
590 for (const auto &[v, next] : successor)
591 start = std::min(start, v);
592 int vertex = start;
593 for (std::size_t i = 0; i != cells.size(); ++i) {
594 ring.polygon.push_back(vertex);
595 const auto it = successor.find(vertex);
596 if (it == successor.end())
597 return false;
598 vertex = it->second;
599 }
600 if (vertex != start)
601 return false;
602 auto unique = ring.polygon;
603 std::sort(unique.begin(), unique.end());
604 if (std::adjacent_find(unique.begin(), unique.end()) != unique.end())
605 return false;
606 ring.cells = cells;
607 return true;
608}
609
610/** Edge removal (Shewchuk): replace the ring of (s, t) by a triangulation of
611 * its polygon, maximising the minimum quality. forced lists polygon vertices
612 * that must appear together: three for a triangle, two for a diagonal (whose
613 * faces with s and t then exist). allowed exempts one new edge from the
614 * bridging rule. alternative selects the second retained triangulation. */
615bool planRemoval(const Context &ctx, Trial &trial, int s, int t,
616 const std::vector<int> &forced, const Edge *allowed,
617 Plan &plan, int alternative = 0) {
618 const auto &mesh = trial.mesh;
619 if (isFixedEdge(ctx, trial, edgeKey(s, t))) {
620 trial.flags.fixed = true;
621 return false;
622 }
623 Ring ring;
624 if (!edgeRing(mesh, s, t, ring)) {
625 trial.flags.topology = true;
626 return false;
627 }
628 const int label = mesh.label[ring.cells.front()];
629 for (int c : ring.cells)
630 if (mesh.label[c] != label) {
631 trial.flags.fixed = true;
632 return false;
633 }
634 const auto &polygon = ring.polygon;
635 const int m = polygon.size();
636 for (int v : polygon)
637 if (isFixedFace(ctx, trial, faceKey(s, t, v))) {
638 trial.flags.fixed = true;
639 return false;
640 }
641 std::vector<int> at;
642 for (int v : forced) {
643 const int i =
644 std::find(polygon.begin(), polygon.end(), v) - polygon.begin();
645 if (i == m) {
646 trial.flags.topology = true;
647 return false;
648 }
649 at.push_back(i);
650 }
651
652 const auto cyc = [m](int i) { return ((i % m) + m) % m; };
653 const auto polygon_edge = [m](int a, int b) {
654 const int d = std::abs(a - b);
655 return d == 1 || d == m - 1;
656 };
657 std::vector<double> memo(m * m * m, std::numeric_limits<double>::quiet_NaN());
658 // Triangle (a, b, c) in cyclic polygon order is counterclockwise seen from
659 // t, giving the positive cells (a, b, c, t) and (a, c, b, s).
660 const auto value = [&](int a, int b, int c) {
661 auto &cached = memo[(a * m + b) * m + c];
662 if (!std::isnan(cached))
663 return cached;
664 cached = -infinity;
665 const std::array<std::array<int, 2>, 3> pairs{{{a, b}, {b, c}, {a, c}}};
666 for (const auto &[i, j] : pairs)
667 if (!polygon_edge(i, j) &&
668 !newEdgeAllowed(ctx, trial, polygon[i], polygon[j], allowed))
669 return cached;
670 const Cell upper{polygon[a], polygon[b], polygon[c], t};
671 const Cell lower{polygon[a], polygon[c], polygon[b], s};
672 if (mesh.orient(upper) <= 0 || mesh.orient(lower) <= 0) {
673 trial.flags.inversion = true;
674 return cached;
675 }
676 if (isPocket(ctx, trial, upper) || isPocket(ctx, trial, lower)) {
677 trial.flags.pocket = true;
678 return cached;
679 }
680 cached = std::min(mesh.quality(upper), mesh.quality(lower));
681 return cached;
682 };
683 // Keep two distinct triangulations only when an alternative is requested.
684 // Each chain has O(m) splits; the two retained choices keep the O(m^3)
685 // time and O(m^2) DP storage (the quality memo above uses O(m^3)).
686 struct Triangulation {
687 double quality = -infinity;
688 int split = -1, left = 0, right = 0;
689 };
690 const int count = alternative ? 2 : 1;
691 std::vector<Triangulation> best(m * m * count);
692 const auto choice_at = [&](int i, int n, int rank) -> Triangulation & {
693 return best[(i * m + n) * count + rank];
694 };
695 for (int i = 0; i != m; ++i)
696 for (int n : {0, 1})
697 choice_at(i, n, 0).quality = infinity;
698 for (int n = 2; n < m; ++n)
699 for (int i = 0; i != m; ++i) {
700 for (int k = 1; k < n; ++k) {
701 const double quality = value(i, cyc(i + k), cyc(i + n));
702 for (int left = 0; left != count; ++left)
703 for (int right = 0; right != count; ++right) {
704 Triangulation found{
705 std::min({quality, choice_at(i, k, left).quality,
706 choice_at(cyc(i + k), n - k, right).quality}),
707 k, left, right};
708 for (int rank = 0; rank != count; ++rank)
709 if (found.quality > choice_at(i, n, rank).quality)
710 std::swap(found, choice_at(i, n, rank));
711 }
712 }
713 }
714
715 double forced_quality = infinity;
716 std::vector<std::array<int, 2>> chains;
717 std::vector<std::array<int, 3>> triangles;
718 if (at.empty()) {
719 chains = {{0, m - 1}};
720 } else if (at.size() == 2) {
721 const int a = at[0], b = at[1], d = cyc(b - a);
722 if (d <= 1 || d >= m - 1) {
723 trial.flags.topology = true;
724 return false;
725 }
726 chains = {{a, d}, {b, m - d}};
727 } else if (at.size() == 3) {
728 int a = at[0], b = at[1], c = at[2];
729 int ob = cyc(b - a), oc = cyc(c - a);
730 if (ob > oc) {
731 std::swap(b, c);
732 std::swap(ob, oc);
733 }
734 forced_quality = value(a, b, c);
735 chains = {{a, ob}, {b, oc - ob}, {c, m - oc}};
736 triangles.push_back({a, b, c});
737 } else {
738 trial.flags.topology = true;
739 return false;
740 }
741 struct Combination {
742 double quality;
743 std::array<int, 3> ranks;
744 };
745 std::vector<Combination> combinations;
746 const int combinations_count = 1 << chains.size();
747 for (int mask = 0; mask != (alternative ? combinations_count : 1); ++mask) {
748 Combination combination{forced_quality, {0, 0, 0}};
749 for (std::size_t j = 0; j != chains.size(); ++j) {
750 const auto [i, n] = chains[j];
751 const int rank = (mask >> j) & 1;
752 combination.ranks[j] = rank;
753 combination.quality =
754 std::min(combination.quality, choice_at(i, n, rank).quality);
755 }
756 if (combination.quality > -infinity)
757 combinations.push_back(combination);
758 }
759 std::stable_sort(combinations.begin(), combinations.end(),
760 [](const Combination &a, const Combination &b) {
761 return a.quality > b.quality;
762 });
763 if (alternative >= static_cast<int>(combinations.size()))
764 return false;
765
766 std::vector<std::array<int, 3>> work;
767 for (std::size_t j = 0; j != chains.size(); ++j)
768 work.push_back(
769 {chains[j][0], chains[j][1], combinations[alternative].ranks[j]});
770 while (!work.empty()) {
771 const auto [i, n, rank] = work.back();
772 work.pop_back();
773 if (n < 2)
774 continue;
775 const auto &choice = choice_at(i, n, rank);
776 const int k = choice.split;
777 triangles.push_back({i, cyc(i + k), cyc(i + n)});
778 work.push_back({i, k, choice.left});
779 work.push_back({cyc(i + k), n - k, choice.right});
780 }
781 plan.removed = ring.cells;
782 plan.cells.clear();
783 plan.minQuality = combinations[alternative].quality;
784 for (const auto &[a, b, c] : triangles) {
785 plan.cells.push_back({polygon[a], polygon[b], polygon[c], t});
786 plan.cells.push_back({polygon[a], polygon[c], polygon[b], s});
787 }
788 return true;
789}
790
791/** 2-3 flip of an interior face. */
792bool planFlip(const Context &ctx, Trial &trial, const Face &face, Plan &plan) {
793 const auto &mesh = trial.mesh;
794 if (isFixedFace(ctx, trial, face)) {
795 trial.flags.fixed = true;
796 return false;
797 }
798 const auto &cells = mesh.cellsOf(face);
799 if (cells.size() != 2) {
800 trial.flags.topology = true;
801 return false;
802 }
803 if (mesh.label[cells[0]] != mesh.label[cells[1]]) {
804 trial.flags.fixed = true;
805 return false;
806 }
807 const auto apex = [&](int index) {
808 for (int v : mesh.cells[index])
809 if (v != face[0] && v != face[1] && v != face[2])
810 return v;
811 return -1;
812 };
813 const int top = apex(cells[0]), bottom = apex(cells[1]);
814 Face f = face;
815 const int sign = orientation(mesh.point(f[0]), mesh.point(f[1]),
816 mesh.point(f[2]), mesh.point(top));
817 if (sign == 0) {
818 trial.flags.inversion = true;
819 return false;
820 }
821 if (sign < 0)
822 std::swap(f[1], f[2]);
823 if (!newEdgeAllowed(ctx, trial, top, bottom))
824 return false;
825 plan.cells = {Cell{bottom, top, f[0], f[1]}, Cell{bottom, top, f[1], f[2]},
826 Cell{bottom, top, f[2], f[0]}};
827 plan.minQuality = infinity;
828 for (const auto &cell : plan.cells) {
829 if (mesh.orient(cell) <= 0) {
830 trial.flags.inversion = true;
831 return false;
832 }
833 if (isPocket(ctx, trial, cell)) {
834 trial.flags.pocket = true;
835 return false;
836 }
837 plan.minQuality = std::min(plan.minQuality, mesh.quality(cell));
838 }
839 plan.removed = {cells[0], cells[1]};
840 return true;
841}
842
843void applyPlan(Trial &trial, const Plan &plan) {
844 auto &mesh = trial.mesh;
845 int parent = INT_MAX;
846 const int label = mesh.label[plan.removed.front()];
847 for (int c : plan.removed)
848 parent = std::min(parent, mesh.parent[c]);
849 for (int c : plan.removed)
850 mesh.remove(c);
851 for (const auto &cell : plan.cells)
852 trial.created.push_back(mesh.add(cell, -1, parent, label));
853 ++trial.operations;
854}
855
856bool moveNode(Trial &trial, int w, const Vec &position) {
857 auto &mesh = trial.mesh;
858 mesh.moved = w;
859 mesh.movedPosition = position;
860 for (int c : mesh.cellsOf(w))
861 if (mesh.orient(mesh.cells[c]) <= 0) {
862 mesh.moved = -1;
863 trial.flags.inversion = true;
864 return false;
865 }
866 return true;
867}
868
869/** Validate the whole region after an operation. A failure is a defect of
870 * this implementation, never a property of the input. */
871void audit(const Context &ctx, const Trial &trial) {
872 ++ctx.report.auditedOperations;
873 const auto &mesh = trial.mesh;
874 const auto fail = [](const std::string &what) {
875 THROW_MESSAGE("Crack extension audit failed: " + what);
876 };
877 double volume = 0;
878 for (std::size_t c = 0; c != mesh.cells.size(); ++c)
879 if (mesh.alive[c]) {
880 if (mesh.orient(mesh.cells[c]) <= 0)
881 fail("non-positive cell");
882 volume += mesh.volume(mesh.cells[c]);
883 }
884 // Flips keep the volume; a node sliding on a curved skin changes it by
885 // what its star gains.
886 double expected = ctx.initialVolume;
887 if (mesh.moved >= 0)
888 for (int c : ctx.base.cellsOf(mesh.moved))
889 expected +=
890 mesh.volume(ctx.base.cells[c]) - ctx.base.volume(ctx.base.cells[c]);
891 if (std::abs(volume - expected) > 1e-8 * ctx.initialVolume)
892 fail("region volume changed");
893 for (const auto &[face, cells] : mesh.faceCells) {
894 if (cells.size() > 2)
895 fail("face with more than two cells");
896 if (cells.size() == 1 && !ctx.initialBoundary.count(face))
897 fail("region boundary changed");
898 }
899 for (const auto &face : ctx.initialBoundary)
900 if (mesh.cellsOf(face).size() != 1)
901 fail("region boundary changed");
902 for (const auto &face : ctx.initialFixedFaces)
903 if (!mesh.faceCells.count(face))
904 fail("fixed face removed");
905 for (const auto &edge : ctx.initialFixedEdges)
906 if (!mesh.edgeCells.count(edge))
907 fail("fixed edge removed");
908 EdgeMap<int> crack_edges;
909 const auto count = [&](const Face &face) {
910 ++crack_edges[edgeKey(face[0], face[1])];
911 ++crack_edges[edgeKey(face[1], face[2])];
912 ++crack_edges[edgeKey(face[0], face[2])];
913 };
914 for (const auto &face : ctx.initialFixedFaces)
915 if (ctx.crack.count(face))
916 count(face);
917 if (mesh.faceCells.count(trial.newFace))
918 count(trial.newFace);
919 for (const auto &face : trial.closures)
920 if (mesh.faceCells.count(face))
921 count(face);
922 for (const auto &[edge, k] : crack_edges)
923 if (k > 2)
924 fail("non-manifold crack edge");
925 for (const auto &[edge, cells] : mesh.edgeCells)
926 if (!ctx.initialEdges.count(edge) && ctx.crackNode[edge[0]] &&
927 ctx.crackNode[edge[1]] && !isClosingEdge(trial, edge))
928 fail("bridging edge created");
929 for (int c : trial.created)
930 if (mesh.alive[c] && isPocket(ctx, trial, mesh.cells[c]))
931 fail("pocket created");
932}
933
934std::vector<int> changedCells(const Trial &trial) {
935 const auto &mesh = trial.mesh;
936 std::vector<int> cells;
937 for (int c : trial.created)
938 if (mesh.alive[c])
939 cells.push_back(c);
940 if (mesh.moved >= 0)
941 for (int c : mesh.cellsOf(mesh.moved))
942 cells.push_back(c);
943 std::sort(cells.begin(), cells.end());
944 cells.erase(std::unique(cells.begin(), cells.end()), cells.end());
945 return cells;
946}
947
948/** Improve the worst changed cell by edge removal or 2-3 flips while it is
949 * below target and the operation budget lasts. */
950void repair(const Context &ctx, Trial &trial, double target) {
951 auto &mesh = trial.mesh;
952 while (trial.operations < ctx.settings.maxFlipsPerCandidate) {
953 int worst = -1;
954 double worst_quality = infinity;
955 for (int c : changedCells(trial)) {
956 const double q = mesh.quality(c);
957 if (q < worst_quality) {
958 worst_quality = q;
959 worst = c;
960 }
961 }
962 if (worst < 0 || worst_quality >= target)
963 break;
964 const Cell cell = mesh.cells[worst];
965 const Flags saved = trial.flags;
966 Plan chosen;
967 double chosen_gain = 0;
968 const auto consider = [&](const Plan &plan) {
969 double before = infinity;
970 for (int c : plan.removed)
971 before = std::min(before, mesh.quality(c));
972 const double gain = plan.minQuality - before;
973 if (gain > chosen_gain + 1e-12 && plan.minQuality > worst_quality) {
974 chosen = plan;
975 chosen_gain = gain;
976 }
977 };
978 for (const auto &e : cellEdges) {
979 Plan plan;
980 if (planRemoval(ctx, trial, cell[e[0]], cell[e[1]], {}, nullptr, plan))
981 consider(plan);
982 }
983 for (int f = 0; f != 4; ++f) {
984 Plan plan;
985 if (planFlip(ctx, trial, cellFace(cell, f), plan))
986 consider(plan);
987 }
988 // Repair attempts are optional; their rejections do not reject the
989 // candidate.
990 trial.flags = saved;
991 if (chosen.cells.empty())
992 break;
993 applyPlan(trial, chosen);
994 if (ctx.settings.audit)
995 audit(ctx, trial);
996 }
997}
998
999// ===========================================================================
1000// Candidate search: placement of the free node, corner closure, routes,
1001// trials and their ranking.
1002// ===========================================================================
1003
1004/** Number of face layers from the new face to another front or skin edge,
1005 * capped at ten. */
1006int cardinality(const Context &ctx, const Trial &trial) {
1007 const auto &mesh = trial.mesh;
1008 constexpr int cap = 10;
1009 EdgeSet seen{edgeKey(ctx.f0, ctx.f1)};
1010 FaceSet visited{trial.newFace};
1011 std::vector<Face> layer{trial.newFace};
1012 for (int c = 0; c != cap; ++c) {
1013 std::vector<Edge> edges;
1014 for (const auto &face : layer)
1015 for (const auto &edge :
1016 {edgeKey(face[0], face[1]), edgeKey(face[1], face[2]),
1017 edgeKey(face[0], face[2])})
1018 if (seen.insert(edge).second)
1019 edges.push_back(edge);
1020 if (edges.empty())
1021 return cap;
1022 for (const auto &edge : edges)
1023 if (ctx.wholeFront.count(edge))
1024 return c;
1025 std::vector<Face> next;
1026 for (const auto &edge : edges)
1027 for (int cell : mesh.cellsOf(edge))
1028 for (int f = 0; f != 4; ++f) {
1029 const auto face = cellFace(mesh.cells[cell], f);
1030 const bool has_edge = std::count(face.begin(), face.end(), edge[0]) &&
1031 std::count(face.begin(), face.end(), edge[1]);
1032 if (has_edge && visited.insert(face).second)
1033 next.push_back(face);
1034 }
1035 layer.swap(next);
1036 }
1037 return cap;
1038}
1039
1040struct Placement {
1041 double angle; ///< Radians between candidate face and target plane.
1042 bool ahead;
1043};
1044Placement placement(const Context &ctx, const Vec &x) {
1045 const auto r = sub(x, ctx.points[ctx.f0]);
1046 const double un = dot(r, ctx.n), ud = dot(r, ctx.d);
1047 return {std::atan2(std::abs(un), ud), ud > 0};
1048}
1049
1050/** A position of the free node putting the face at tan(angle) = ratio on
1051 * the node's current side of the target plane. */
1052struct Target {
1054 bool back = false; ///< Slid back beyond the node along its edge.
1055};
1056
1057/** Admissible positions: for an interior node the shortest move; for a
1058 * sliding node one per edge whose line meets the plane between slideBack of
1059 * the edge behind the node and the other end of the edge. */
1060std::vector<Target> targetPositions(const Context &ctx, int w, double ratio) {
1061 std::vector<Target> targets;
1062 const auto it = ctx.constraints.find(w);
1063 if (it == ctx.constraints.end())
1064 return targets;
1065 const auto &constraint = it->second;
1066 const auto &x = ctx.points[w];
1067 const auto r = sub(x, ctx.points[ctx.f0]);
1068 const double un = dot(r, ctx.n), ud = dot(r, ctx.d);
1069 ratio = std::copysign(ratio, un);
1070 switch (constraint.kind) {
1071 case NodeKind::Interior:
1072 targets.push_back({sub(x, mul(ctx.n, un - ratio * ud))});
1073 break;
1074 case NodeKind::Slide:
1075 for (const auto &slide : constraint.slides) {
1076 const double denominator =
1077 dot(slide.axis, ctx.n) - ratio * dot(slide.axis, ctx.d);
1078 if (std::abs(denominator) < 1e-6)
1079 continue;
1080 const double alpha = (ratio * ud - un) / denominator;
1081 if (alpha < -slideBack * slide.length || alpha >= slide.length)
1082 continue;
1083 targets.push_back({add(x, mul(slide.axis, alpha)), alpha < 0});
1084 }
1085 break;
1086 default:
1087 break;
1088 }
1089 return targets;
1090}
1091
1092/** Crack faces on edge, including faces added by the trial. */
1093int crackFaceCount(const Context &ctx, const Trial &trial, const Edge &edge) {
1094 const auto it = ctx.crackEdgeCount.find(edge);
1095 int count = it == ctx.crackEdgeCount.end() ? 0 : it->second;
1096 count += faceHasEdge(trial.newFace, edge);
1097 for (const auto &f : trial.closures)
1098 count += faceHasEdge(f, edge);
1099 return count;
1100}
1101
1102struct Corner {
1103 int f = -1, g = -1, h = -1; ///< Corner vertex and its two front neighbours.
1104};
1105
1106/** A non-convex corner of the crack front at f: exactly two front edges
1107 * (f, g) and (f, h), and the crack faces around f span more than half a turn
1108 * (the sum of their angles at f exceeds pi). This is the definition of a
1109 * re-entrant corner, not a tuned threshold, and it stays correct for nearly
1110 * closed fans, where a sum of edge directions does not. */
1111bool frontCorner(const Context &ctx, const Trial &trial, int f,
1112 Corner &corner) {
1113 if (!ctx.completeStar.count(f))
1114 return false;
1115 const auto &mesh = trial.mesh;
1116 std::map<int, int> neighbours;
1117 FaceSet seen;
1118 const auto x = mesh.point(f);
1119 double sector = 0;
1120 for (int c : mesh.cellsOf(f))
1121 for (int i = 0; i != 4; ++i) {
1122 const auto face = cellFace(mesh.cells[c], i);
1123 if (!std::count(face.begin(), face.end(), f) ||
1124 !seen.insert(face).second || !isCrack(ctx, trial, face))
1125 continue;
1126 int other[2], k = 0;
1127 for (int v : face)
1128 if (v != f) {
1129 ++neighbours[v];
1130 other[k++] = v;
1131 }
1132 sector += angleAt(x, mesh.point(other[0]), mesh.point(other[1]));
1133 }
1134 std::vector<int> front;
1135 for (const auto &[v, count] : neighbours) {
1136 if (count > 2)
1137 return false;
1138 if (count == 1 && !ctx.skinEdges.count(edgeKey(f, v)))
1139 front.push_back(v);
1140 }
1141 if (front.size() != 2 || !(sector > M_PI))
1142 return false;
1143 corner = {f, front[0], front[1]};
1144 return true;
1145}
1146
1147/** Close a corner with the face (g, f, h): use it if it exists, otherwise
1148 * create it by one edge removal in which it is forced. Its edge (g, h) is the
1149 * only created edge allowed to join two crack nodes. */
1150bool closeCorner(const Context &ctx, Trial &trial, const Corner &corner) {
1151 const auto face = faceKey(corner.f, corner.g, corner.h);
1152 if (isCrack(ctx, trial, face) || ctx.protectedFaces.count(face))
1153 return false;
1154 const auto closing = edgeKey(corner.g, corner.h);
1155 if (crackFaceCount(ctx, trial, closing) > 1)
1156 return false;
1157 Trial attempt = trial;
1158 attempt.closures.push_back(face);
1159 if (attempt.mesh.cellsOf(face).size() != 2) {
1160 if (attempt.operations >= ctx.settings.maxFlipsPerCandidate)
1161 return false;
1162 const std::array<int, 3> vertices{corner.f, corner.g, corner.h};
1163 Plan chosen;
1164 EdgeSet tried;
1165 for (int v : vertices) {
1166 const auto cells = attempt.mesh.cellsOf(v);
1167 for (int c : cells)
1168 for (const auto &e : cellEdges) {
1169 const int a = attempt.mesh.cells[c][e[0]];
1170 const int b = attempt.mesh.cells[c][e[1]];
1171 if (!tried.insert(edgeKey(a, b)).second)
1172 continue;
1173 Ring ring;
1174 if (!edgeRing(attempt.mesh, a, b, ring))
1175 continue;
1176 std::vector<int> forced;
1177 int missing = -1;
1178 for (int x : vertices)
1179 if (std::count(ring.polygon.begin(), ring.polygon.end(), x))
1180 forced.push_back(x);
1181 else
1182 missing = x;
1183 // Either the face is a polygon triangle, or its third vertex ends
1184 // the removed edge and the other two form a forced diagonal.
1185 if (forced.size() == 2 && missing != a && missing != b)
1186 continue;
1187 if (forced.size() < 2)
1188 continue;
1189 Plan plan;
1190 const Flags saved = attempt.flags;
1191 if (planRemoval(ctx, attempt, a, b, forced, &closing, plan) &&
1192 plan.minQuality > chosen.minQuality)
1193 chosen = plan;
1194 attempt.flags = saved;
1195 }
1196 }
1197 if (chosen.cells.empty() || chosen.minQuality < ctx.settings.minimumQuality)
1198 return false;
1199 applyPlan(attempt, chosen);
1200 if (attempt.mesh.cellsOf(face).size() != 2)
1201 return false;
1202 if (ctx.settings.audit)
1203 audit(ctx, attempt);
1204 }
1205 for (int c : attempt.mesh.cellsOf(face))
1206 if (isPocket(ctx, attempt, attempt.mesh.cells[c]))
1207 return false;
1208 trial = std::move(attempt);
1209 return true;
1210}
1211
1212/** Close non-convex corners at the ends of new front edges, including the
1213 * edges created by closures, while closures succeed. Returns the number of
1214 * corners left open. */
1215int closeCorners(const Context &ctx, Trial &trial) {
1216 std::vector<int> work{ctx.f0, ctx.f1};
1217 std::set<int> visited(work.begin(), work.end());
1218 // A safety bound on iterations; every closure adds a crack face, and the
1219 // region and the operation budget bound them anyway.
1220 for (int guard = 0; !work.empty() && guard != 64; ++guard) {
1221 const int v = work.back();
1222 work.pop_back();
1223 Corner corner;
1224 if (!frontCorner(ctx, trial, v, corner) || !closeCorner(ctx, trial, corner))
1225 continue;
1226 for (int x : {corner.g, corner.h}) {
1227 visited.insert(x);
1228 work.push_back(x);
1229 }
1230 }
1231 int open = 0;
1232 for (int v : visited) {
1233 Corner corner;
1234 open += frontCorner(ctx, trial, v, corner);
1235 }
1236 return open;
1237}
1238
1239/** The crack faces at v, including the trial's, are not a single fan. */
1240bool pinched(const Context &ctx, const Trial &trial, int v) {
1241 const auto &mesh = trial.mesh;
1242 std::vector<Face> fan;
1243 FaceSet seen;
1244 for (int c : mesh.cellsOf(v))
1245 for (int i = 0; i != 4; ++i) {
1246 const auto face = cellFace(mesh.cells[c], i);
1247 if (std::count(face.begin(), face.end(), v) && seen.insert(face).second &&
1248 isCrack(ctx, trial, face))
1249 fan.push_back(face);
1250 }
1251 return !singleFan(fan, v);
1252}
1253
1254/** Make face, whose three edges exist, a face of the mesh by removing the
1255 * edges that cross it, one edge removal at a time within the flip budget.
1256 * Each removal re-triangulates the edge's ring for the best minimum quality
1257 * under the usual rules, forcing the face once its nodes are all in the
1258 * ring. A triangle whose edges exist and which no edge crosses is a face. */
1259bool recoverFace(const Context &ctx, Trial &trial, const Face &face,
1260 const Edge *allowed) {
1261 using K = CGAL::Exact_predicates_inexact_constructions_kernel;
1262 auto &mesh = trial.mesh;
1263 for (int k = 0; k != 3; ++k)
1264 if (!mesh.edgeCells.count(edgeKey(face[k], face[(k + 1) % 3]))) {
1265 trial.flags.topology = true;
1266 return false;
1267 }
1268 const auto point = [&](int v) {
1269 const auto &x = mesh.point(v);
1270 return K::Point_3(x[0], x[1], x[2]);
1271 };
1272 const K::Triangle_3 triangle(point(face[0]), point(face[1]), point(face[2]));
1273 while (mesh.cellsOf(face).size() != 2) {
1274 if (trial.operations >= ctx.settings.maxFlipsPerCandidate) {
1275 trial.flags.topology = true;
1276 return false;
1277 }
1278 Edge crossing{-1, -1};
1279 for (const auto &[edge, cells] : mesh.edgeCells) {
1280 if (std::count(face.begin(), face.end(), edge[0]) ||
1281 std::count(face.begin(), face.end(), edge[1]) ||
1282 (crossing[0] >= 0 && !(edge < crossing)))
1283 continue;
1284 if (CGAL::do_intersect(K::Segment_3(point(edge[0]), point(edge[1])),
1285 triangle))
1286 crossing = edge;
1287 }
1288 if (crossing[0] < 0) {
1289 trial.flags.topology = true;
1290 return false;
1291 }
1292 std::vector<int> forced;
1293 Ring ring;
1294 if (edgeRing(mesh, crossing[0], crossing[1], ring) &&
1295 std::all_of(face.begin(), face.end(), [&](int v) {
1296 return std::count(ring.polygon.begin(), ring.polygon.end(), v);
1297 }))
1298 forced.assign(face.begin(), face.end());
1299 Plan plan;
1300 if (!planRemoval(ctx, trial, crossing[0], crossing[1], forced, allowed,
1301 plan))
1302 return false;
1303 applyPlan(trial, plan);
1304 if (ctx.settings.audit)
1305 audit(ctx, trial);
1306 }
1307 return true;
1308}
1309
1310/** How a route makes the face (f0, f1, w). */
1311enum class RouteKind {
1312 Existing, ///< The face exists.
1313 Removal, ///< Removing the ring edge (s, t) creates it.
1314 Recovery ///< Removing the edges that cross it recovers it (gap closure).
1315};
1316struct Route {
1317 int w = -1; ///< Free node.
1318 RouteKind kind = RouteKind::Existing;
1319 int s = -1, t = -1; ///< Removal: the ring edge.
1320 bool closure = false; ///< The face (f0, f1, w) closes a corner at f0 or f1.
1321 Edge closing{-1, -1}; ///< Its edge allowed to join two crack nodes.
1322 int alternative = 0; ///< Second ring triangulation, before quality pruning.
1323 bool joining = false;
1324};
1325
1326/** Describe an accepted trial as a candidate. */
1327void makeCandidate(const Context &ctx, const Trial &trial, int candidate_class,
1328 const Vec &final_position, int open_corners,
1329 double min_quality, Candidate &candidate) {
1330 const auto &mesh = trial.mesh;
1331 const int w = trial.w;
1332 const auto &x = ctx.points[w];
1333 const auto final_placement = placement(ctx, final_position);
1334 candidate = Candidate();
1335 candidate.candidateClass = candidate_class;
1336 candidate.operation = trial.joiningRoute ? Candidate::JOIN
1337 : trial.closureRoute ? Candidate::CLOSURE
1338 : norm(sub(final_position, x)) > 0
1339 ? Candidate::MOVE
1340 : Candidate::EXTENSION;
1342 candidate.displacement = sub(final_position, x);
1343 candidate.newFace = {ctx.f0, ctx.f1, w};
1344 for (std::size_t c = 0; c != ctx.base.cells.size(); ++c)
1345 if (!mesh.alive[c])
1346 candidate.removedCells.push_back(mesh.source[c]);
1347 std::sort(candidate.removedCells.begin(), candidate.removedCells.end());
1348 for (int c : trial.created)
1349 if (mesh.alive[c]) {
1350 candidate.createdCells.push_back(mesh.cells[c]);
1351 candidate.createdParents.push_back(mesh.parent[c]);
1352 }
1353 candidate.operations = trial.operations;
1354 for (const auto &face : trial.closures)
1355 candidate.closureFaces.push_back(face);
1356 candidate.openCorners = open_corners;
1357 candidate.minQuality = min_quality;
1358 candidate.angleDeviationDegrees = final_placement.angle * 180 / M_PI;
1359 candidate.moveRelative = norm(candidate.displacement) / ctx.meanEdge.at(w);
1360 candidate.cardinality = cardinality(ctx, trial);
1361 const double c = std::max(1, candidate.cardinality);
1362 candidate.score = min_quality / (c * c);
1363}
1364
1365/** Prefer fewer open corners, then continuation feasibility and kind, then
1366 * score. Equal choices retain their order; the final ranking breaks ties
1367 * by the smaller free node index. */
1368bool better(const Candidate &a, const Candidate &b) {
1369 if (a.operation != b.operation)
1370 return a.operation > b.operation;
1371 if (a.openCorners != b.openCorners)
1372 return a.openCorners < b.openCorners;
1373 if (a.continuation != b.continuation)
1374 return a.continuation > b.continuation;
1375 if (a.continuationKind != b.continuationKind)
1376 return a.continuationKind > b.continuationKind;
1377 return a.score > b.score;
1378}
1379
1380/** One ordering of one route; returns true and fills candidate on success. */
1381bool runTrial(const Context &ctx, const Route &route, int candidate_class,
1382 const Vec *position, bool move_first, Candidate &candidate,
1383 Flags &flags) {
1384 Trial trial;
1385 trial.mesh = ctx.base;
1386 trial.w = route.w;
1387 trial.newFace = faceKey(ctx.f0, ctx.f1, route.w);
1388 trial.closureRoute = route.closure;
1389 trial.joiningRoute = route.joining;
1390 const auto fail = [&]() {
1391 flags.merge(trial.flags);
1392 return false;
1393 };
1394 const auto move = [&]() {
1395 if (!position)
1396 return true;
1397 if (!moveNode(trial, route.w, *position))
1398 return false;
1399 if (ctx.settings.audit)
1400 audit(ctx, trial);
1401 return true;
1402 };
1403 const auto extend = [&]() {
1404 if (route.kind == RouteKind::Recovery)
1405 return recoverFace(ctx, trial, trial.newFace,
1406 route.closure ? &route.closing : nullptr);
1407 if (route.kind == RouteKind::Existing)
1408 return true;
1409 if (trial.operations >= ctx.settings.maxFlipsPerCandidate) {
1410 trial.flags.topology = true;
1411 return false;
1412 }
1413 Plan plan;
1414 if (!planRemoval(ctx, trial, route.s, route.t, {ctx.f0, ctx.f1, route.w},
1415 route.closure ? &route.closing : nullptr, plan,
1416 route.alternative))
1417 return false;
1418 applyPlan(trial, plan);
1419 if (ctx.settings.audit)
1420 audit(ctx, trial);
1421 return true;
1422 };
1423 if (move_first ? !(move() && extend()) : !(extend() && move()))
1424 return fail();
1425
1426 auto &mesh = trial.mesh;
1427 if (mesh.cellsOf(trial.newFace).size() != 2) {
1428 trial.flags.topology = true;
1429 return fail();
1430 }
1431 if (ctx.protectedFaces.count(trial.newFace)) {
1432 trial.flags.fixed = true;
1433 return fail();
1434 }
1435 for (int c : mesh.cellsOf(trial.newFace))
1436 if (isPocket(ctx, trial, mesh.cells[c])) {
1437 trial.flags.pocket = true;
1438 return fail();
1439 }
1440
1441 // Non-convex front corners at the new edges are singular; close them by
1442 // existing faces or flips where possible.
1443 int open_corners = 0;
1444 if (!route.joining)
1445 open_corners = closeCorners(ctx, trial);
1446 else
1447 for (int v : {ctx.f0, ctx.f1, route.w}) {
1448 Corner corner;
1449 open_corners += frontCorner(ctx, trial, v, corner);
1450 }
1451 if (!route.joining && ctx.settings.requireClosedCorners && open_corners) {
1452 trial.flags.openCorner = true;
1453 return fail();
1454 }
1455 // No vertex of an added face may join two separate fans of crack faces.
1456 {
1457 std::set<int> vertices(trial.newFace.begin(), trial.newFace.end());
1458 for (const auto &face : trial.closures)
1459 vertices.insert(face.begin(), face.end());
1460 for (int v : vertices)
1461 if (!route.joining)
1462 if (pinched(ctx, trial, v)) {
1463 trial.flags.pinch = true;
1464 return fail();
1465 }
1466 }
1467
1468 // Repair only what this candidate changed, aiming at no worse than the
1469 // replaced or moved cells were before.
1470 double before = infinity;
1471 for (std::size_t c = 0; c != ctx.base.cells.size(); ++c)
1472 if (!mesh.alive[c])
1473 before = std::min(before, ctx.base.quality(c));
1474 if (position)
1475 for (int c : ctx.base.cellsOf(route.w))
1476 before = std::min(before, ctx.base.quality(c));
1477 if (trial.operations || position)
1478 repair(ctx, trial,
1479 std::max(ctx.settings.minimumQuality, std::min(before, 1.)));
1480
1481 const auto changed = changedCells(trial);
1482 double min_quality = infinity;
1483 for (int c : changed) {
1484 const double q = mesh.quality(c);
1485 if (q < ctx.settings.minimumQuality) {
1486 trial.flags.quality = true;
1487 return fail();
1488 }
1489 min_quality = std::min(min_quality, q);
1490 }
1491 for (int c : mesh.cellsOf(trial.newFace))
1492 min_quality = std::min(min_quality, mesh.quality(c));
1493
1494 const auto &x = ctx.points[route.w];
1495 makeCandidate(ctx, trial, candidate_class, position ? *position : x,
1496 open_corners, min_quality, candidate);
1497 if (route.joining) {
1498 // Validate the intended join on the recovered connectivity before it
1499 // can enter a shortlist. The complete crack keeps the cycle test exact.
1500 TetMeshData recovered;
1501 recovered.points = ctx.points;
1502 for (std::size_t c = 0; c != mesh.cells.size(); ++c)
1503 if (mesh.alive[c])
1504 recovered.cells.push_back(mesh.cells[c]);
1505 std::vector<int> crack;
1506 for (const auto &face : ctx.crack) {
1507 crack.push_back(recovered.boundary.size());
1508 recovered.boundary.push_back(face);
1509 }
1510 for (const auto &face : ctx.protectedFaces)
1511 recovered.boundary.push_back(face);
1512 const auto joins = CGALTools().crackJoinFaces(
1513 recovered, crack, {edgeKey(ctx.f0, ctx.f1)}, [&](const Face &face) {
1514 return faceKey(face[0], face[1], face[2]) == trial.newFace;
1515 });
1516 if (joins.empty()) {
1517 trial.flags.topology = true;
1518 return fail();
1519 }
1520 candidate.joinCategory = joins.front().category;
1521 if (ctx.settings.joinGapsOnly ||
1523 candidate.operation = Candidate::CLOSURE;
1524 }
1525 return true;
1526}
1527
1528enum class Outcome { Skipped, Rejected, Accepted };
1529
1530Outcome tryRoute(const Context &ctx, const Route &route, int candidate_class,
1531 Candidate &candidate, Flags &flags) {
1532 const auto &x = ctx.points[route.w];
1533 const auto current = placement(ctx, x);
1534 if (route.joining && candidate_class != Candidate::Flips)
1535 return Outcome::Skipped;
1536 if (route.closure) {
1537 // A closure is decided by topology and the corner test, not by the
1538 // target plane; it never moves a node.
1539 if (candidate_class != Candidate::Flips)
1540 return Outcome::Skipped;
1541 } else if (candidate_class == Candidate::Flips &&
1542 !(route.joining && ctx.settings.joinGapsOnly)) {
1543 if (!current.ahead) {
1544 flags.behind = true;
1545 return Outcome::Rejected;
1546 }
1547 if (current.angle > ctx.tolerance) {
1548 flags.angle = true;
1549 return Outcome::Rejected;
1550 }
1551 }
1552 if (route.closure || candidate_class == Candidate::Flips)
1553 return runTrial(ctx, route, candidate_class, nullptr, true, candidate,
1554 flags)
1555 ? Outcome::Accepted
1556 : Outcome::Rejected;
1557
1558 if (current.angle <= ctx.tolerance)
1559 return Outcome::Skipped; // Class 1 covers this node without a move.
1560 const double ratio = candidate_class == Candidate::PartialMove
1561 ? std::tan(0.9 * ctx.tolerance)
1562 : 0.;
1563 const auto targets = targetPositions(ctx, route.w, ratio);
1564 if (targets.empty())
1565 flags.move = true;
1566 // The best position, with the quality term halved after a slide back, as
1567 // the fracture module ranks its edge moves.
1568 bool accepted = false;
1569 for (const auto &target : targets) {
1570 const auto &position = target.position;
1571 if (norm(sub(position, x)) >
1572 ctx.settings.maxMoveRelative * ctx.meanEdge.at(route.w)) {
1573 flags.move = true;
1574 continue;
1575 }
1576 const auto placed = placement(ctx, position);
1577 if (!placed.ahead) {
1578 flags.behind = true;
1579 continue;
1580 }
1581 if (placed.angle > ctx.tolerance) {
1582 flags.angle = true;
1583 continue;
1584 }
1585 Candidate found;
1586 if (!runTrial(ctx, route, candidate_class, &position, true, found, flags) &&
1587 !(route.kind == RouteKind::Removal &&
1588 runTrial(ctx, route, candidate_class, &position, false, found,
1589 flags)))
1590 continue;
1591 if (target.back) {
1592 const double c = std::max(1, found.cardinality);
1593 found.score -= 0.5 * found.minQuality / (c * c);
1594 }
1595 if (!accepted || better(found, candidate)) {
1596 candidate = std::move(found);
1597 accepted = true;
1598 }
1599 }
1600 return accepted ? Outcome::Accepted : Outcome::Rejected;
1601}
1602
1603/** Extension or gap closure. A closure takes only the routes that close a
1604 * front corner with the crack node next to it, existing, made by one edge
1605 * removal, or recovered; no free node off the crack. */
1606enum class SearchMode { Extension, Closure, Joining };
1607
1608/** Settings, indices, front edge and direction of a search. */
1609void validateSearchInput(const TetMeshData &patch,
1610 const std::vector<int> &crack_faces,
1611 const std::array<int, 2> &front_edge,
1612 const Vec &direction, const Settings &settings) {
1613 if (!(settings.angleToleranceDegrees > 0 &&
1614 settings.angleToleranceDegrees < 90))
1615 THROW_MESSAGE("Crack extension angle tolerance must be in (0, 90)");
1616 if (!(settings.maxMoveRelative >= 0) ||
1617 !std::isfinite(settings.maxMoveRelative))
1618 THROW_MESSAGE("Crack extension move bound must be finite and >= 0");
1619 if (!std::isfinite(settings.minimumQuality))
1620 THROW_MESSAGE("Crack extension settings must be finite");
1621 if (settings.ringLimit < 1 || settings.maxFlipsPerCandidate < 0)
1622 THROW_MESSAGE("Crack extension needs ringLimit >= 1 and a flip budget");
1623 if (settings.lookAheadCandidates < 0)
1624 THROW_MESSAGE("Crack extension look-ahead budget must be >= 0");
1625
1626 const int np = patch.points.size();
1627 const auto valid_point = [np](int v) { return v >= 0 && v < np; };
1628 for (const auto &cell : patch.cells)
1629 for (int v : cell)
1630 if (!valid_point(v))
1631 THROW_MESSAGE("Invalid crack extension cell index");
1632 if (!patch.cellLabels.empty() &&
1633 patch.cellLabels.size() != patch.cells.size())
1634 THROW_MESSAGE("Crack extension cell labels do not match cells");
1635 for (const auto &face : patch.boundary) {
1636 for (int v : face)
1637 if (!valid_point(v))
1638 THROW_MESSAGE("Invalid crack extension boundary index");
1639 if (face[0] == face[1] || face[1] == face[2] || face[0] == face[2])
1640 THROW_MESSAGE("Degenerate crack extension boundary face");
1641 }
1642 for (const auto &edge : patch.featureEdges)
1643 if (!valid_point(edge[0]) || !valid_point(edge[1]) || edge[0] == edge[1])
1644 THROW_MESSAGE("Invalid crack extension feature edge");
1645 for (int v : patch.fixedVertices)
1646 if (!valid_point(v))
1647 THROW_MESSAGE("Invalid crack extension fixed vertex");
1648 const auto [f0, f1] = front_edge;
1649 if (!valid_point(f0) || !valid_point(f1) || f0 == f1)
1650 THROW_MESSAGE("Invalid crack extension front edge");
1651 if (!finite(direction))
1652 THROW_MESSAGE("Crack extension direction must be finite");
1653 std::vector<char> seen(patch.boundary.size(), 0);
1654 for (int i : crack_faces) {
1655 if (i < 0 || i >= static_cast<int>(patch.boundary.size()) || seen[i])
1656 THROW_MESSAGE("Invalid or repeated crack face index");
1657 seen[i] = 1;
1658 }
1659}
1660
1661/** Crack and protected faces, crack nodes and edges, fixed edges, the whole
1662 * front (front and uncracked skin edges), and the crack face at (f0, f1). */
1663void classifyCrack(Context &ctx, const TetMeshData &patch,
1664 const PatchTopology &topology) {
1665 ctx.crack = topology.crack;
1666 ctx.protectedFaces = topology.protectedFaces;
1667 ctx.skin = topology.skin;
1668 ctx.skinEdges = topology.skinEdges;
1669 ctx.crackEdgeCount = crackEdgeCounts(ctx.crack);
1670 ctx.crackNode.assign(patch.points.size(), 0);
1671 for (const auto &face : ctx.crack)
1672 for (int v : face)
1673 ctx.crackNode[v] = 1;
1674 for (const auto &b : patch.boundary)
1675 for (const auto &edge : faceEdges(faceKey(b[0], b[1], b[2])))
1676 ctx.fixedEdges.insert(edge);
1677 for (const auto &edge : patch.featureEdges)
1678 ctx.fixedEdges.insert(edgeKey(edge[0], edge[1]));
1679 for (const auto &[edge, count] : ctx.crackEdgeCount)
1680 if (count == 1 && !ctx.skinEdges.count(edge))
1681 ctx.wholeFront.insert(edge);
1682 for (const auto &edge : ctx.skinEdges)
1683 if (!ctx.crackEdgeCount.count(edge))
1684 ctx.wholeFront.insert(edge);
1685
1686 const auto e = edgeKey(ctx.f0, ctx.f1);
1687 const auto front_count = ctx.crackEdgeCount.find(e);
1688 if (front_count == ctx.crackEdgeCount.end() || front_count->second != 1)
1689 THROW_MESSAGE("Front edge must belong to exactly one crack face");
1690 if (ctx.skinEdges.count(e))
1691 THROW_MESSAGE("Front edge must not lie on a protected surface");
1692 for (const auto &face : ctx.crack)
1693 if (std::count(face.begin(), face.end(), ctx.f0) &&
1694 std::count(face.begin(), face.end(), ctx.f1))
1695 for (int v : face)
1696 if (v != ctx.f0 && v != ctx.f1)
1697 ctx.crackApex = v;
1698}
1699
1700/** Cells within ringLimit vertex rings of the front edge, and their
1701 * vertices. */
1702struct Region {
1703 std::vector<char> cells;
1704 std::vector<int> vertices;
1705};
1706Region selectRegion(const Context &ctx, const TetMeshData &patch,
1707 const PatchTopology &topology) {
1708 Region region;
1709 region.cells.assign(patch.cells.size(), 0);
1710 std::vector<char> marked(patch.points.size(), 0);
1711 std::vector<int> frontier{ctx.f0, ctx.f1};
1712 region.vertices = {ctx.f0, ctx.f1};
1713 marked[ctx.f0] = marked[ctx.f1] = 1;
1714 for (int ring = 0; ring != ctx.settings.ringLimit; ++ring) {
1715 std::vector<int> next;
1716 for (int v : frontier)
1717 for (int c : topology.vertexCells[v])
1718 if (!region.cells[c]) {
1719 region.cells[c] = 1;
1720 for (int u : patch.cells[c])
1721 if (!marked[u]) {
1722 marked[u] = 1;
1723 next.push_back(u);
1724 region.vertices.push_back(u);
1725 }
1726 }
1727 frontier.swap(next);
1728 }
1729 for (int v : region.vertices)
1730 if (!finite(patch.points[v]))
1731 THROW_MESSAGE("Crack extension region has a non-finite point");
1732 return region;
1733}
1734
1735/** The work mesh of the region. A negative cell is rejected, not flipped:
1736 * flipping cannot tell an inverted element from reversed vertex order, and
1737 * an inverted element overlaps its neighbours, which breaks every validity
1738 * argument of the search. */
1739void buildBaseMesh(Context &ctx, const TetMeshData &patch,
1740 const Region &region) {
1741 ctx.base.points = &patch.points;
1742 for (int c = 0; c != static_cast<int>(patch.cells.size()); ++c)
1743 if (region.cells[c]) {
1744 const auto &cell = patch.cells[c];
1745 const int sign =
1746 orientation(patch.points[cell[0]], patch.points[cell[1]],
1747 patch.points[cell[2]], patch.points[cell[3]]);
1748 if (sign <= 0) {
1749 std::ostringstream message;
1750 message << (sign ? "Inverted" : "Degenerate")
1751 << " cell in the crack extension region: cell " << c
1752 << ", vertices";
1753 Vec centre{0, 0, 0};
1754 for (int v : cell) {
1755 message << ' '
1756 << (patch.vertexIds.empty() ? v : patch.vertexIds.at(v));
1757 centre = add(centre, mul(patch.points[v], 0.25));
1758 }
1759 message << (patch.vertexIds.empty() ? " (point indices)" : " (IDs)")
1760 << ", centre " << centre[0] << ' ' << centre[1] << ' '
1761 << centre[2] << "; fix the mesh, cells must be positively "
1762 << "oriented";
1763 THROW_MESSAGE(message.str());
1764 }
1765 ctx.base.add(cell, c, c,
1766 patch.cellLabels.empty() ? 0 : patch.cellLabels[c]);
1767 }
1768}
1769
1770/** Target plane frame: t along the front edge, d the extension direction
1771 * orthogonal to it and away from the crack face, n = t x d. */
1772void setDirection(Context &ctx, const TetMeshData &patch,
1773 const Vec &direction) {
1774 const auto edge_vector = sub(patch.points[ctx.f1], patch.points[ctx.f0]);
1775 if (!(norm(edge_vector) > 0))
1776 THROW_MESSAGE("Crack extension front edge has zero length");
1777 ctx.t = mul(edge_vector, 1 / norm(edge_vector));
1778 const auto projected = sub(direction, mul(ctx.t, dot(direction, ctx.t)));
1779 if (!(norm(projected) > 1e-8 * norm(direction)))
1780 THROW_MESSAGE("Crack extension direction is parallel to the front edge");
1781 ctx.d = mul(projected, 1 / norm(projected));
1782 ctx.n = cross(ctx.t, ctx.d);
1783 const auto midpoint =
1784 mul(add(patch.points[ctx.f0], patch.points[ctx.f1]), 0.5);
1785 if (!(dot(sub(patch.points[ctx.crackApex], midpoint), ctx.d) < 0))
1787 "Crack extension direction must point away from the crack face");
1788}
1789
1790/** Node constraints and local edge lengths of region vertices; see "Node
1791 * constraints". A node on a geometry curve slides along its two curve
1792 * edges; a corner or a curve end is fixed. A node on protected faces slides
1793 * along their edges, so it stays on the faceted surface. Never along an
1794 * edge to a front node, as in the fracture module. */
1795void setNodeConstraints(Context &ctx, const TetMeshData &patch,
1796 const PatchTopology &topology, const Region &region) {
1797 const int np = patch.points.size();
1798 std::vector<char> fixed_vertex(np, 0), front_node(np, 0);
1799 for (int v : patch.fixedVertices)
1800 fixed_vertex[v] = 1;
1801 for (const auto &[edge, count] : ctx.crackEdgeCount)
1802 if (count == 1 && !ctx.skinEdges.count(edge))
1803 front_node[edge[0]] = front_node[edge[1]] = 1;
1804 std::unordered_map<int, std::vector<int>> feature_neighbours;
1805 for (const auto &edge : patch.featureEdges) {
1806 feature_neighbours[edge[0]].push_back(edge[1]);
1807 feature_neighbours[edge[1]].push_back(edge[0]);
1808 }
1809 for (int v : region.vertices) {
1810 EdgeSet edges, protected_edges;
1811 bool star_in_region = true;
1812 for (int c : topology.vertexCells[v]) {
1813 if (!region.cells[c])
1814 star_in_region = false;
1815 const auto &cell = patch.cells[c];
1816 for (const auto &ce : cellEdges)
1817 if (cell[ce[0]] == v || cell[ce[1]] == v)
1818 edges.insert(edgeKey(cell[ce[0]], cell[ce[1]]));
1819 for (int f = 0; f != 4; ++f) {
1820 const auto face = cellFace(cell, f);
1821 if (!std::count(face.begin(), face.end(), v))
1822 continue;
1823 const bool is_protected = ctx.protectedFaces.count(face);
1824 if (topology.faceCells.at(face).size() == 1 && !is_protected)
1825 star_in_region = false; // Cut by the patch boundary.
1826 if (is_protected)
1827 for (int u : face)
1828 if (u != v)
1829 protected_edges.insert(edgeKey(u, v));
1830 }
1831 }
1832 double length = 0;
1833 for (const auto &edge : edges)
1834 length += norm(sub(patch.points[edge[0]], patch.points[edge[1]]));
1835 ctx.meanEdge[v] = edges.empty() ? 0 : length / edges.size();
1836
1837 NodeConstraint constraint;
1838 const auto features = feature_neighbours.find(v);
1839 const auto add_slide = [&](int u) {
1840 if (front_node[u])
1841 return;
1842 const auto a = sub(patch.points[u], patch.points[v]);
1843 constraint.slides.push_back({mul(a, 1 / norm(a)), norm(a)});
1844 };
1845 if (!star_in_region || fixed_vertex[v] || ctx.crackNode[v]) {
1846 constraint.kind = NodeKind::Fixed;
1847 } else if (features != feature_neighbours.end()) {
1848 if (features->second.size() == 2) {
1849 constraint.kind = NodeKind::Slide;
1850 for (int u : features->second)
1851 add_slide(u);
1852 }
1853 } else if (!protected_edges.empty()) {
1854 constraint.kind = NodeKind::Slide;
1855 for (const auto &e : protected_edges)
1856 add_slide(e[0] == v ? e[1] : e[0]);
1857 } else {
1858 constraint.kind = NodeKind::Interior;
1859 }
1860 ctx.constraints[v] = constraint;
1861 if (star_in_region)
1862 ctx.completeStar.insert(v);
1863 }
1864}
1865
1866/** Reference state for the audit. */
1867void recordReference(Context &ctx) {
1868 for (const auto &[face, cells] : ctx.base.faceCells) {
1869 if (cells.size() == 1)
1870 ctx.initialBoundary.insert(face);
1871 if (ctx.crack.count(face) || ctx.protectedFaces.count(face))
1872 ctx.initialFixedFaces.insert(face);
1873 }
1874 for (const auto &[edge, cells] : ctx.base.edgeCells) {
1875 ctx.initialEdges.insert(edge);
1876 if (ctx.fixedEdges.count(edge))
1877 ctx.initialFixedEdges.insert(edge);
1878 }
1879 for (std::size_t c = 0; c != ctx.base.cells.size(); ++c)
1880 ctx.initialVolume += ctx.base.volume(ctx.base.cells[c]);
1881}
1882
1883/** Routes: faces through the front edge, existing or created by removing
1884 * one edge of its ring. A free node on the crack is admissible only when
1885 * the face closes a non-convex corner at f0 or f1 with it. A closure search
1886 * also admits a crack node joined to f0 or f1 by a front edge and ahead,
1887 * where crack parts touch, recovers faces no single removal makes, and
1888 * keeps closing routes only. */
1889std::vector<Route> generateRoutes(const Context &ctx, SearchMode mode) {
1890 const int f0 = ctx.f0, f1 = ctx.f1;
1891 Ring front_ring;
1892 if (!edgeRing(ctx.base, f0, f1, front_ring))
1893 THROW_MESSAGE("Front edge must be interior to the patch");
1894 Trial before;
1895 before.mesh = ctx.base;
1896 before.newFace = {-1, -1, -1};
1897 std::map<int, Edge> closes;
1898 const auto add_closing = [&](int w, int other) {
1899 const auto closing = edgeKey(other, w);
1900 const auto count = ctx.crackEdgeCount.find(closing);
1901 if (count == ctx.crackEdgeCount.end() || count->second <= 1)
1902 closes.emplace(w, closing);
1903 };
1904 for (int f : {f0, f1}) {
1905 Corner corner;
1906 if (!frontCorner(ctx, before, f, corner))
1907 continue;
1908 const int other = f == f0 ? f1 : f0;
1909 if (corner.g != other && corner.h != other)
1910 continue;
1911 add_closing(corner.g == other ? corner.h : corner.g, other);
1912 }
1913 if (mode == SearchMode::Closure)
1914 for (int f : {f0, f1}) {
1915 const int other = f == f0 ? f1 : f0;
1916 for (const auto &[edge, n] : ctx.crackEdgeCount) {
1917 if (n != 1 || !ctx.wholeFront.count(edge) ||
1918 (edge[0] != f && edge[1] != f))
1919 continue;
1920 const int w = edge[0] == f ? edge[1] : edge[0];
1921 if (w == other || w == ctx.crackApex || closes.count(w) ||
1922 !placement(ctx, ctx.points[w]).ahead)
1923 continue;
1924 add_closing(w, other);
1925 }
1926 }
1927
1928 std::vector<Route> routes;
1929 if (mode == SearchMode::Joining) {
1930 CrackComponents components(ctx.points.size(), ctx.crack);
1931 for (std::size_t v = 0; v != ctx.points.size(); ++v) {
1932 if (static_cast<int>(v) == f0 || static_cast<int>(v) == f1 ||
1933 static_cast<int>(v) == ctx.crackApex || ctx.base.cellsOf(v).empty())
1934 continue;
1935 const auto face = faceKey(f0, f1, v);
1936 using Point =
1937 CGAL::Exact_predicates_inexact_constructions_kernel::Point_3;
1938 const auto point = [&](int x) {
1939 const auto &p = ctx.points[x];
1940 return Point(p[0], p[1], p[2]);
1941 };
1942 if (CGAL::collinear(point(f0), point(f1), point(v)))
1943 continue;
1944 int shared = 0;
1945 for (const auto &edge : faceEdges(face))
1946 shared += ctx.crackEdgeCount.count(edge) != 0;
1947 if (ctx.settings.joinGapsOnly && shared < 2)
1948 continue;
1949 if (ctx.protectedFaces.count(face) ||
1950 components.createsCycle(face, ctx.crackEdgeCount))
1951 continue;
1952 bool manifold = true;
1953 for (const auto &edge : faceEdges(face)) {
1954 const auto it = ctx.crackEdgeCount.find(edge);
1955 manifold &= it == ctx.crackEdgeCount.end() || it->second < 2;
1956 }
1957 if (!manifold)
1958 continue;
1959 if (!ctx.crackNode[v] && !ctx.skinEdges.count(edgeKey(f0, v)) &&
1960 !ctx.skinEdges.count(edgeKey(f1, v)))
1961 continue;
1962 Route route;
1963 route.w = v;
1964 route.joining = true;
1965 route.kind = ctx.base.cellsOf(face).size() == 2 ? RouteKind::Existing
1966 : RouteKind::Recovery;
1967 routes.push_back(route);
1968 }
1969 return routes;
1970 }
1971 const auto add_route = [&](int v, RouteKind kind, int s, int t) {
1972 if (v == f0 || v == f1)
1973 return;
1974 if (!ctx.crackNode[v]) {
1975 routes.push_back({v, kind, s, t});
1976 return;
1977 }
1978 const auto it = closes.find(v);
1979 if (it != closes.end())
1980 routes.push_back({v, kind, s, t, true, it->second});
1981 };
1982 for (int a : front_ring.polygon)
1983 add_route(a, RouteKind::Existing, -1, -1);
1984 const int k = front_ring.polygon.size();
1985 for (int i = 0; i != k; ++i) {
1986 const int s = front_ring.polygon[i], t = front_ring.polygon[(i + 1) % k];
1987 Ring ring;
1988 if (!edgeRing(ctx.base, s, t, ring))
1989 continue;
1990 for (int v : ring.polygon)
1991 if (ctx.base.cellsOf(faceKey(f0, f1, v)).empty())
1992 add_route(v, RouteKind::Removal, s, t);
1993 }
1994 if (mode == SearchMode::Closure) {
1995 for (const auto &[w, closing] : closes)
1996 if (ctx.base.cellsOf(faceKey(f0, f1, w)).empty())
1997 routes.push_back({w, RouteKind::Recovery, -1, -1, true, closing});
1998 routes.erase(std::remove_if(routes.begin(), routes.end(),
1999 [](const Route &r) { return !r.closure; }),
2000 routes.end());
2001 }
2002 if (ctx.settings.lookAheadCandidates) {
2003 const auto count = routes.size();
2004 for (std::size_t i = 0; i != count; ++i)
2005 if (routes[i].kind == RouteKind::Removal) {
2006 auto alternative = routes[i];
2007 alternative.alternative = 1;
2008 routes.push_back(alternative);
2009 }
2010 }
2011 return routes;
2012}
2013
2014/** Try every route in each class, retaining a bounded shortlist for preview
2015 * or the best candidate per free node when preview is disabled. A later class
2016 * is tried only when earlier ones failed, unless stopAtFirstClass is false. */
2017std::vector<Candidate> evaluateRoutes(const Context &ctx,
2018 const std::vector<Route> &routes) {
2019 std::vector<Candidate> result;
2020 for (int candidate_class :
2021 {Candidate::Flips, Candidate::PartialMove, Candidate::OnPlaneMove}) {
2022 if (candidate_class == Candidate::Flips && ctx.settings.skipFlips)
2023 continue;
2024 std::map<int, Candidate> best;
2025 std::vector<Candidate> shortlist;
2026 for (const auto &route : routes) {
2027 Candidate candidate;
2028 Flags flags;
2029 const auto outcome =
2030 tryRoute(ctx, route, candidate_class, candidate, flags);
2031 if (outcome == Outcome::Skipped)
2032 continue;
2033 ++ctx.report.candidatesTried;
2034 if (outcome == Outcome::Rejected) {
2035 flags.count(ctx.report);
2036 continue;
2037 }
2038 ++ctx.report.accepted;
2039 if (route.alternative)
2040 ++ctx.report.alternativeTriangulations;
2041 if (ctx.settings.lookAheadCandidates) {
2042 // Keep distinct connectivity for the same free node until previewed.
2043 const auto same = [&](const Candidate &c) {
2044 if (c.freeNode != candidate.freeNode ||
2045 c.displacement != candidate.displacement ||
2046 c.removedCells != candidate.removedCells ||
2047 c.createdCells.size() != candidate.createdCells.size() ||
2048 c.closureFaces != candidate.closureFaces)
2049 return false;
2050 auto left = c.createdCells, right = candidate.createdCells;
2051 for (auto *cells : {&left, &right}) {
2052 for (auto &cell : *cells)
2053 std::sort(cell.begin(), cell.end());
2054 std::sort(cells->begin(), cells->end());
2055 }
2056 return left == right;
2057 };
2058 if (std::none_of(shortlist.begin(), shortlist.end(), same)) {
2059 shortlist.push_back(std::move(candidate));
2060 std::stable_sort(shortlist.begin(), shortlist.end(),
2061 [](const Candidate &a, const Candidate &b) {
2062 return better(a, b) ||
2063 (!better(b, a) && a.freeNode < b.freeNode);
2064 });
2065 if (shortlist.size() >
2066 static_cast<std::size_t>(ctx.settings.lookAheadCandidates))
2067 shortlist.pop_back();
2068 }
2069 continue;
2070 }
2071 auto it = best.find(route.w);
2072 if (it == best.end() || better(candidate, it->second))
2073 best[route.w] = std::move(candidate);
2074 }
2075 std::vector<Candidate> ranked = std::move(shortlist);
2076 for (auto &[w, candidate] : best)
2077 ranked.push_back(std::move(candidate));
2078 std::stable_sort(ranked.begin(), ranked.end(),
2079 [](const Candidate &a, const Candidate &b) {
2080 return better(a, b) ||
2081 (!better(b, a) && a.freeNode < b.freeNode);
2082 });
2083 result.insert(result.end(), ranked.begin(), ranked.end());
2084 if (ctx.settings.stopAtFirstClass && !result.empty())
2085 break;
2086 }
2087 return result;
2088}
2089
2090void rankContinuations(const Context &ctx, const TetMeshData &patch,
2091 const std::vector<int> &crack_faces,
2092 std::vector<Candidate> &candidates);
2093
2094/** A search: validate, prepare the region and its constraints, generate
2095 * routes, evaluate them by class, and bind the result to the patch state. */
2096std::vector<Candidate>
2097searchCandidates(const TetMeshData &patch, const std::vector<int> &crack_faces,
2098 const std::array<int, 2> &front_edge, const Vec &direction,
2099 const Settings &settings, Report &report, SearchMode mode) {
2100 validateSearchInput(patch, crack_faces, front_edge, direction, settings);
2101 const PatchTopology topology(patch, crack_faces);
2102 Context ctx(settings, report, patch.points);
2103 ctx.f0 = front_edge[0];
2104 ctx.f1 = front_edge[1];
2105 ctx.tolerance = settings.angleToleranceDegrees * M_PI / 180;
2106 classifyCrack(ctx, patch, topology);
2107 const auto region = selectRegion(ctx, patch, topology);
2108 buildBaseMesh(ctx, patch, region);
2109 setDirection(ctx, patch, direction);
2110 setNodeConstraints(ctx, patch, topology, region);
2111 recordReference(ctx);
2112 auto result = evaluateRoutes(ctx, generateRoutes(ctx, mode));
2113 const auto digest = patchDigest(patch, crack_faces);
2114 for (auto &candidate : result)
2115 candidate.patchDigest = digest;
2116 if (settings.lookAheadCandidates && !result.empty())
2117 rankContinuations(ctx, patch, crack_faces, result);
2118 return result;
2119}
2120
2121/** Preview only the current region, one candidate and one future search at
2122 * a time. Cut regions give UNKNOWN rather than evidence of a blocked front.
2123 * The supplied patch and the candidate's publication digest never change. */
2124void rankContinuations(const Context &ctx, const TetMeshData &patch,
2125 const std::vector<int> &crack_faces,
2126 std::vector<Candidate> &candidates) {
2127 TetMeshData local;
2128 local.points = patch.points;
2129 local.vertexIds = patch.vertexIds;
2130 local.boundary = patch.boundary;
2131 local.surfaceLabels = patch.surfaceLabels;
2132 local.featureEdges = patch.featureEdges;
2133 local.edgeLabels = patch.edgeLabels;
2134 local.fixedVertices = patch.fixedVertices;
2135 local.cells.reserve(ctx.base.cells.size());
2136 std::vector<int> cell_index(patch.cells.size(), -1);
2137 for (std::size_t c = 0; c != ctx.base.cells.size(); ++c) {
2138 const int source = ctx.base.source[c];
2139 cell_index[source] = local.cells.size();
2140 local.cells.push_back(ctx.base.cells[c]);
2141 if (!patch.cellLabels.empty())
2142 local.cellLabels.push_back(patch.cellLabels[source]);
2143 if (!patch.partitions.empty())
2144 local.partitions.push_back(patch.partitions[source]);
2145 }
2146 const auto digest = patchDigest(local, crack_faces);
2147 Settings settings = ctx.settings;
2148 settings.lookAheadCandidates = 0; // Exactly one future step, no recursion.
2149 settings.skipFlips = false; // The future search starts afresh.
2150 TetMeshData preview;
2151 std::vector<int> preview_crack;
2152 CGALTools tools;
2153 const int count =
2154 std::min<int>(ctx.settings.lookAheadCandidates, candidates.size());
2155 for (int i = 0; i != count; ++i) {
2156 auto &candidate = candidates[i];
2157 Candidate mapped = candidate;
2158 for (int &c : mapped.removedCells)
2159 c = cell_index.at(c);
2160 for (int &c : mapped.createdParents)
2161 c = cell_index.at(c);
2162 mapped.patchDigest = digest;
2163 preview = local;
2164 preview_crack = crack_faces;
2165 tools.applyCrackExtension(preview, preview_crack, mapped);
2166 ++ctx.report.lookAheadTrials;
2167
2168 const PatchTopology topology(preview, preview_crack);
2169 const auto edge_count = crackEdgeCounts(topology.crack);
2170 FaceSet added{faceKey(candidate.newFace[0], candidate.newFace[1],
2171 candidate.newFace[2])};
2172 for (const auto &face : candidate.closureFaces)
2173 added.insert(faceKey(face[0], face[1], face[2]));
2174 auto crack_node = ctx.crackNode;
2175 for (const auto &face : added)
2176 for (int v : face)
2177 crack_node[v] = 1;
2178 struct NextEdge {
2179 Edge edge;
2180 Vec direction;
2181 double forward;
2182 };
2183 std::vector<NextEdge> edges;
2184 for (const auto &face : added)
2185 for (const auto &edge : faceEdges(face)) {
2186 if (edge_count.at(edge) != 1 || topology.skinEdges.count(edge))
2187 continue;
2188 const auto tangent =
2189 sub(preview.points[edge[1]], preview.points[edge[0]]);
2190 Vec direction = cross(ctx.n, tangent);
2191 const double length = norm(direction);
2192 if (!(length > 1e-8 * norm(tangent)))
2193 continue;
2194 direction = mul(direction, 1 / length);
2195 int apex = -1;
2196 for (int v : face)
2197 if (v != edge[0] && v != edge[1])
2198 apex = v;
2199 const auto midpoint =
2200 mul(add(preview.points[edge[0]], preview.points[edge[1]]), 0.5);
2201 const double side = dot(sub(preview.points[apex], midpoint), direction);
2202 if (!side)
2203 continue;
2204 if (side > 0)
2205 direction = mul(direction, -1);
2206 const double forward = dot(direction, ctx.d);
2207 if (forward > 1e-8)
2208 edges.push_back({edge, direction, forward});
2209 }
2210 std::sort(edges.begin(), edges.end(),
2211 [](const NextEdge &a, const NextEdge &b) {
2212 return a.forward != b.forward ? a.forward > b.forward
2213 : a.edge < b.edge;
2214 });
2215 bool unknown = edges.empty() || edges.size() > 2;
2216 candidate.continuation = Candidate::UNKNOWN;
2217 candidate.continuationKind = Candidate::NONE;
2218 const auto record = [&](Candidate::ContinuationKind kind, const Face &face,
2219 double angle) {
2221 candidate.continuation = Candidate::FEASIBLE;
2225 }
2226 };
2227 for (std::size_t j = 0; j != std::min<std::size_t>(2, edges.size()); ++j) {
2228 const auto &next = edges[j];
2229 const auto tangent =
2230 sub(preview.points[next.edge[1]], preview.points[next.edge[0]]);
2231 const auto normal =
2232 cross(mul(tangent, 1 / norm(tangent)), next.direction);
2233 const auto face_angle = [&](const Face &face) {
2234 const auto r =
2235 sub(preview.points[face[2]], preview.points[next.edge[0]]);
2236 return std::atan2(std::abs(dot(r, normal)), dot(r, next.direction)) *
2237 180 / M_PI;
2238 };
2239 const auto follows_face = [&](const Face &face) {
2240 return face_angle(face) <= settings.angleToleranceDegrees;
2241 };
2242 if (settings.lookAheadJoin) {
2243 const auto closes_gap = [&](const Face &face) {
2244 int shared = 0;
2245 for (const auto &edge : faceEdges(face))
2246 shared += edge_count.count(edge) != 0;
2247 return shared >= 2 && follows_face(face);
2248 };
2249 const auto closing = tools.crackJoinFaces(preview, preview_crack,
2250 {next.edge}, closes_gap);
2251 if (!closing.empty()) {
2252 record(Candidate::CLOSURE, closing.front().face,
2253 face_angle(closing.front().face));
2254 break;
2255 }
2256 }
2257 Report future_report;
2258 Context future(settings, future_report, preview.points);
2259 future.f0 = next.edge[0];
2260 future.f1 = next.edge[1];
2261 const auto region = selectRegion(future, preview, topology);
2262 // A missing cell beyond the local patch is not a geometric obstacle.
2263 bool complete = true;
2264 for (const auto &[face, cells] : topology.faceCells)
2265 if (cells.size() == 1 && region.cells[cells.front()] &&
2266 !topology.protectedFaces.count(face))
2267 complete = false;
2268 WorkMesh star;
2269 star.points = &preview.points;
2270 for (std::size_t c = 0; c != preview.cells.size(); ++c)
2271 if (region.cells[c])
2272 star.add(preview.cells[c], c, c, 0);
2273 Ring ring;
2274 if (!edgeRing(star, next.edge[0], next.edge[1], ring)) {
2275 unknown = true;
2276 continue;
2277 }
2278 // Release the temporary star before the full future search.
2279 star = WorkMesh();
2280 const auto follows_direction = [&](const Candidate &c) {
2281 // Topological corner closures can ignore the direction filter.
2282 return c.angleDeviationDegrees <= settings.angleToleranceDegrees;
2283 };
2284 if (settings.lookAheadJoin) {
2285 const auto closures =
2286 searchCandidates(preview, preview_crack, next.edge, next.direction,
2287 settings, future_report, SearchMode::Closure);
2288 const auto closing =
2289 std::find_if(closures.begin(), closures.end(), follows_direction);
2290 if (closing != closures.end()) {
2291 record(Candidate::CLOSURE, closing->newFace,
2292 closing->angleDeviationDegrees);
2293 break; // Gap closure has highest priority.
2294 }
2295 auto gap_settings = settings;
2296 gap_settings.joinGapsOnly = true;
2297 const auto recovered_gap =
2298 searchCandidates(preview, preview_crack, next.edge, next.direction,
2299 gap_settings, future_report, SearchMode::Joining);
2300 const auto gap = std::find_if(recovered_gap.begin(),
2301 recovered_gap.end(), follows_direction);
2302 if (gap != recovered_gap.end()) {
2303 record(Candidate::CLOSURE, gap->newFace, gap->angleDeviationDegrees);
2304 break;
2305 }
2306 const auto joins = tools.crackJoinFaces(preview, preview_crack,
2307 {next.edge}, follows_face);
2308 if (!joins.empty()) {
2309 record(Candidate::JOIN, joins.front().face,
2310 face_angle(joins.front().face));
2311 continue;
2312 }
2313 auto join_settings = settings;
2314 join_settings.joinGapsOnly = false;
2315 const auto recovered_join =
2316 searchCandidates(preview, preview_crack, next.edge, next.direction,
2317 join_settings, future_report, SearchMode::Joining);
2318 const auto joining = std::find_if(
2319 recovered_join.begin(), recovered_join.end(), follows_direction);
2320 if (joining != recovered_join.end()) {
2321 record(joining->operation, joining->newFace,
2322 joining->angleDeviationDegrees);
2323 if (joining->operation == Candidate::CLOSURE)
2324 break;
2325 continue;
2326 }
2327 }
2328 auto continuation =
2329 searchCandidates(preview, preview_crack, next.edge, next.direction,
2330 settings, future_report, SearchMode::Extension);
2331 if (!continuation.empty() && settings.stopAtFirstClass &&
2332 std::none_of(continuation.begin(), continuation.end(),
2333 follows_direction)) {
2334 auto all_classes = settings;
2335 all_classes.stopAtFirstClass = false;
2336 continuation =
2337 searchCandidates(preview, preview_crack, next.edge, next.direction,
2338 all_classes, future_report, SearchMode::Extension);
2339 }
2340 for (const auto &found : continuation)
2341 if (follows_direction(found)) {
2342 const bool closes =
2343 !found.closureFaces.empty() || crack_node[found.freeNode];
2344 record(found.operation == Candidate::MOVE ? Candidate::MOVE
2345 : closes ? Candidate::CLOSURE
2346 : Candidate::EXTENSION,
2347 found.newFace, found.angleDeviationDegrees);
2348 }
2349 unknown |= !complete;
2350 }
2351 if (candidate.continuation == Candidate::FEASIBLE) {
2352 ++ctx.report.lookAheadFeasible;
2353 ctx.report.lookAheadJoins +=
2354 candidate.continuationKind == Candidate::JOIN;
2355 ctx.report.lookAheadClosures +=
2356 candidate.continuationKind == Candidate::CLOSURE;
2357 } else if (!unknown)
2358 candidate.continuation = Candidate::BLOCKED;
2359 }
2360 std::stable_sort(candidates.begin(), candidates.end(),
2361 [](const Candidate &a, const Candidate &b) {
2362 if (a.candidateClass != b.candidateClass)
2363 return a.candidateClass < b.candidateClass;
2364 return better(a, b) ||
2365 (!better(b, a) && a.freeNode < b.freeNode);
2366 });
2367}
2368
2369} // namespace
2370
2371std::vector<CGALTools::CrackExtensionCandidate>
2372CGALTools::crackExtensionCandidates(const TetMeshData &patch,
2373 const std::vector<int> &crack_faces,
2374 std::array<int, 2> front_edge,
2375 std::array<double, 3> direction,
2379 return searchCandidates(patch, crack_faces, front_edge, direction, settings,
2380 report ? *report : local, SearchMode::Extension);
2381}
2382
2383std::vector<CGALTools::CrackExtensionCandidate>
2384CGALTools::crackClosureCandidates(const TetMeshData &patch,
2385 const std::vector<int> &crack_faces,
2386 std::array<int, 2> front_edge,
2387 std::array<double, 3> direction,
2391 return searchCandidates(patch, crack_faces, front_edge, direction, settings,
2392 report ? *report : local, SearchMode::Closure);
2393}
2394
2395std::vector<CGALTools::CrackExtensionCandidate>
2396CGALTools::crackJoiningCandidates(const TetMeshData &patch,
2397 const std::vector<int> &crack_faces,
2398 std::array<int, 2> front_edge,
2399 std::array<double, 3> direction,
2403 return searchCandidates(patch, crack_faces, front_edge, direction, settings,
2404 report ? *report : local, SearchMode::Joining);
2405}
2406
2407// ===========================================================================
2408// Applying a candidate
2409// ===========================================================================
2410
2411void CGALTools::applyCrackExtension(
2412 TetMeshData &patch, std::vector<int> &crack_faces,
2413 const CrackExtensionCandidate &candidate) const {
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}
2572
2573// ===========================================================================
2574// Notch fill and joining: crack faces added without changing the mesh.
2575// ===========================================================================
2576
2577namespace {
2578
2579/** Faces of an edge in the patch, sorted; none for an unknown edge. */
2580const std::vector<Face> &facesOf(const PatchTopology &topology,
2581 const Edge &edge) {
2582 static const std::vector<Face> none;
2583 const auto it = topology.edgeFaces.find(edge);
2584 return it == topology.edgeFaces.end() ? none : it->second;
2585}
2586
2587} // namespace
2588
2589std::vector<std::array<int, 3>>
2590CGALTools::crackFillFaces(const TetMeshData &patch,
2591 const std::vector<int> &crack_faces) const {
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}
2710
2711std::vector<CGALTools::CrackJoinFace> CGALTools::crackJoinFaces(
2712 const TetMeshData &patch, const std::vector<int> &crack_faces,
2713 const std::vector<Edge> &front_order,
2714 const std::function<bool(const Face &)> &accept_face) const {
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}
2870
2871} // namespace MoFEM
std::map< EntityHandle, int > labels
std::map< EntityHandle, int > index
CGALTools & tools
std::vector< std::array< EntityHandle, 3 > > faces
Sorted keys.
TetMeshData result
CGALTools::CrackExtensionCandidate candidate
const Triangles & triangles
Definition CGALTools.cpp:60
size_t best
Definition CGALTools.cpp:63
CGAL algorithms independent of the MoFEM/MOAB database.
Report & report
std::vector< int > created
FaceSet initialFixedFaces
EdgeSet wholeFront
EdgeMap< std::vector< int > > edgeCells
FaceSet protectedFaces
int h
Corner vertex and its two front neighbours.
int alternative
Second ring triangulation, before quality pruning.
FaceMap< std::vector< int > > faceCells
FaceSet skin
std::vector< int > source
bool topology
std::vector< Slide > slides
Edges a sliding node may move along.
std::vector< std::vector< int > > vertexCells
double minQuality
bool pocket
std::unordered_map< int, double > meanEdge
const Settings & settings
int boundary
bool move
bool joining
EdgeSet skinEdges
const std::vector< Vec > * points
FaceSet crack
std::vector< Face > closures
Faces closing non-convex front corners.
EdgeSet fixedEdges
NodeKind kind
Vec movedPosition
std::vector< int > removed
std::vector< int > size
int crackApex
Third node of the crack face at (f0, f1).
EdgeSet initialFixedEdges
bool angle
Radians between candidate face and target plane.
bool behind
bool quality
bool closureRoute
The new face itself closes a corner.
std::vector< int > label
bool pinch
double length
double tolerance
Radians.
WorkMesh base
WorkMesh mesh
Flags flags
std::vector< int > polygon
std::vector< int > vertices
FaceSet initialBoundary
int w
Free node.
bool fixed
std::unordered_set< int > completeStar
Vertices whose star is in region.
Face newFace
bool openCorner
Vec t
Removal: the ring edge.
bool joiningRoute
Use the existing joining topology rules.
std::vector< int > parent
std::vector< char > crackNode
bool back
Slid back beyond the node along its edge.
double initialVolume
EdgeSet initialEdges
EdgeMap< std::vector< Face > > edgeFaces
Sorted faces of the cells.
bool inversion
bool closure
The face (f0, f1, w) closes a corner at f0 or f1.
std::vector< char > alive
Edge closing
Its edge allowed to join two crack nodes.
std::unordered_map< int, NodeConstraint > constraints
EdgeMap< int > crackEdgeCount
Crack faces per edge before extension.
std::vector< Cell > cells
bool bridging
int operations
ParentChildKey key
int components
Inferred from the source tag length.
const Field * target
std::vector< double > empty
One value per component.
It it
Definition Schur.cpp:2568
It end
Definition Schur.cpp:2568
SmartPetscObj< Vec > work
SmartPetscObj< Vec > values
constexpr double a
#define THROW_MESSAGE(msg)
Throw MoFEM exception.
const char features[]
FTensor::Index< 'i', SPACE_DIM > i
const double c
speed of light (cm/ns)
const double v
phase velocity of light in medium (cm/ns)
FTensor::Index< 'j', 3 > j
FTensor::Index< 'k', 3 > k
double sign(double x)
const FTensor::Tensor2< T, Dim, Dim > Vec
auto cross(const Tensor1_Expr< A, T, 3, i > &a, const Tensor1_Expr< B, U, 3, j > &b, const Index< k, 3 > &)
Definition cross.hpp:10
implementation of Data Operators for Forces and Sources
Definition Common.hpp:10
double constraint(double eqiv, double dot_tau, double f, double sigma_y, double abs_w, double vis_H, double sigma_Y)
int r
Definition sdf.py:205
double q
FTensor::Index< 'm', 3 > m
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.
int freeNode
Patch point index of the free node.
std::vector< std::array< int, 4 > > createdCells
Positively oriented.
int openCorners
Non-convex corners at new edges left open.
@ ClosingFront
Closes onto another front edge; manifold, no pinch.
void applyCrackExtension(TetMeshData &patch, std::vector< int > &crack_faces, const CrackExtensionCandidate &candidate) 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
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 > 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 > surfaceLabels
Definition CGALTools.hpp:21
std::vector< int > fixedVertices
Point indices which cannot move or collapse.
Definition CGALTools.hpp:26
static double tetVolume(const double *coords)
Calculate volume of tetrahedron.
Definition Tools.cpp:30
static double volumeLengthQuality(const double *coords)
Calculate tetrahedron volume length quality.
Definition Tools.cpp:15