12#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
13#include <CGAL/intersections.h>
21#include <unordered_map>
22#include <unordered_set>
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;
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}};
46constexpr double slideBack = 0.1;
49 template <std::
size_t N>
50 std::size_t operator()(
const std::array<int, N> &
key)
const {
53 hash ^=
std::hash<
int>()(value) + 0x9e3779b97f4a7c15ull + (hash << 6) +
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>;
63Edge edgeKey(
int a,
int b) {
return a < b ? Edge{
a, b} : Edge{b,
a}; }
64Face faceKey(
int a,
int b,
int c) {
66 std::sort(face.begin(), face.end());
69Face cellFace(
const Cell &cell,
int i) {
70 return faceKey(cell[cellFaces[
i][0]], cell[cellFaces[
i][1]],
71 cell[cellFaces[
i][2]]);
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])};
77Vec sub(
const Vec &
a,
const Vec &b) {
78 return {
a[0] - b[0],
a[1] - b[1],
a[2] - b[2]};
80Vec add(
const Vec &
a,
const Vec &b) {
81 return {
a[0] + b[0],
a[1] + b[1],
a[2] + b[2]};
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];
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]};
91double norm(
const Vec &
a) {
return std::sqrt(dot(
a,
a)); }
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));
97bool finite(
const Vec &
a) {
98 return std::isfinite(
a[0]) && std::isfinite(
a[1]) && std::isfinite(
a[2]);
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])));
109void cellCoordinates(
const Vec &
a,
const Vec &b,
const Vec &
c,
const Vec &
d,
111 for (
int i = 0;
i != 3; ++
i) {
113 coords[3 +
i] = b[
i];
114 coords[6 +
i] =
c[
i];
115 coords[9 +
i] =
d[
i];
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) {
128 hash *= 1099511628211ull;
131 const auto vector = [&](
const auto &
values) {
137 vector(patch.points);
139 vector(patch.cellLabels);
140 vector(patch.boundary);
141 vector(patch.featureEdges);
142 vector(patch.fixedVertices);
144 return hash ? hash : 1;
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)
160 if (
v < 0 ||
v >= np)
162 for (
int i : crack_faces)
170struct PatchTopology {
177 PatchTopology(
const TetMeshData &patch,
const std::vector<int> &crack_faces)
179 for (
int c = 0;
c !=
static_cast<int>(patch.cells.size()); ++
c) {
180 for (
int v : patch.cells[
c])
182 for (
int f = 0;
f != 4; ++
f)
186 for (
const auto &e : faceEdges(face))
190 std::vector<char> is_crack(patch.boundary.size(), 0);
191 for (
int i : crack_faces)
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]);
204 for (
const auto &e : faceEdges(face))
213EdgeMap<int> crackEdgeCounts(
const FaceSet &
crack) {
215 for (
const auto &face :
crack)
216 for (const auto &e : faceEdges(face))
225template <
class IsCrack,
class IsSkin>
226CellFaces countCellFaces(
const Cell &cell, IsCrack is_crack, IsSkin is_skin) {
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);
238bool foldsOrDangles(
const CellFaces &count) {
239 return count.crack >= 2 || count.boundary >= 3;
244struct CrackComponents {
247 CrackComponents(std::size_t count,
const FaceSet &
crack)
249 for (std::size_t
i = 0;
i != count; ++
i)
251 for (
const auto &face :
crack)
256 while (parent[
v] !=
v) {
263 void addFace(
const Face &face) {
264 for (
int i = 1;
i != 3; ++
i) {
265 int a = root(face[0]), b = root(face[
i]);
268 if (size[
a] < size[b])
275 bool createsCycle(
const Face &face,
const EdgeMap<int> &edge_count) {
278 for (
const auto &edge : faceEdges(face)) {
279 const auto it = edge_count.find(edge);
280 if (
it != edge_count.end() &&
it->second) {
288 if (
v != shared[0] &&
v != shared[1])
289 return root(
v) == root(shared[0]);
296bool cutFree(
const CellFaces &count) {
return count.boundary == 4; }
300bool singleFan(
const std::vector<Face> &fan,
int v) {
303 std::vector<char> reached(fan.size(), 0);
304 std::vector<std::size_t> stack{0};
306 std::size_t visited = 1;
307 while (!stack.empty()) {
308 const auto i = stack.back();
310 for (std::size_t
j = 0;
j != fan.size(); ++
j) {
315 shared +=
a !=
v &&
std::count(fan[
j].begin(), fan[
j].
end(),
a);
323 return visited == fan.size();
336 const std::vector<Vec> *
points =
nullptr;
342 std::unordered_map<int, std::vector<int>>
vertexCells;
346 const Vec &point(
int v)
const {
349 int orient(
const Cell &
c)
const {
350 return orientation(point(
c[0]), point(
c[1]), point(
c[2]), point(
c[3]));
352 double quality(
const Cell &
c)
const {
354 cellCoordinates(point(
c[0]), point(
c[1]), point(
c[2]), point(
c[3]), coords);
356 return std::isnormal(
q) ?
q : -2;
359 double volume(
const Cell &
c)
const {
361 cellCoordinates(point(
c[0]), point(
c[1]), point(
c[2]), point(
c[3]), coords);
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;
370 const std::vector<int> &cellsOf(
const Edge &edge)
const {
371 return find(edgeCells, edge);
373 const std::vector<int> &cellsOf(
const Face &face)
const {
374 return find(faceCells, face);
376 const std::vector<int> &cellsOf(
int vertex)
const {
377 return find(vertexCells, vertex);
379 int add(
const Cell &cell,
int src,
int par,
int lab) {
381 cells.push_back(cell);
385 label.push_back(lab);
388 for (
const auto &e : cellEdges)
390 for (
int f = 0;
f != 4; ++
f)
391 faceCells[cellFace(cell,
f)].push_back(
index);
394 void remove(
int index) {
396 const auto erase = [
index](std::vector<int> &list) {
397 list.erase(std::remove(list.begin(), list.end(),
index), list.end());
402 for (
const auto &e : cellEdges) {
403 const auto it =
edgeCells.find(edgeKey(cell[e[0]], cell[e[1]]));
405 if (
it->second.empty())
408 for (
int f = 0;
f != 4; ++
f) {
411 if (
it->second.empty())
417enum class NodeKind { Fixed, Interior, Slide };
424struct NodeConstraint {
425 NodeKind
kind = NodeKind::Fixed;
433 void merge(
const Flags &other) {
435 angle |= other.angle;
441 fixed |= other.fixed;
444 pinch |= other.pinch;
446 void count(Report &
report)
const {
462 Context(
const Settings &settings, Report &report,
463 const std::vector<Vec> &points)
467 const std::vector<Vec> &
points;
499 std::vector<Cell>
cells;
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();
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]);
514bool isClosingEdge(
const Trial &trial,
const Edge &edge) {
515 if (trial.closureRoute && faceHasEdge(trial.newFace, edge))
518 if (faceHasEdge(
f, edge))
522bool isFixedFace(
const Context &ctx,
const Trial &trial,
const Face &face) {
523 return isCrack(ctx, trial, face) || ctx.protectedFaces.count(face);
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);
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))
540 return std::all_of(cell.begin(), cell.end(),
541 [&](
int v) { return ctx.crackNode[v]; });
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;
555 if (trial.mesh.edgeCells.count(edgeKey(
a, b))) {
556 trial.flags.topology =
true;
568bool edgeRing(
const WorkMesh &
mesh,
int s,
int t, Ring &ring) {
569 ring.polygon.clear();
572 if (
cells.size() < 3)
574 std::unordered_map<int, int> successor;
578 if (
v !=
s &&
v !=
t)
581 mesh.point(other[0]),
mesh.point(other[1]));
585 std::swap(other[0], other[1]);
586 if (!successor.emplace(other[0], other[1]).second)
590 for (
const auto &[
v, next] : successor)
591 start =
std::min(start,
v);
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())
602 auto unique = ring.polygon;
603 std::sort(unique.begin(), unique.end());
604 if (std::adjacent_find(unique.begin(), unique.end()) != unique.end())
615bool planRemoval(
const Context &ctx, Trial &trial,
int s,
int t,
616 const std::vector<int> &forced,
const Edge *allowed,
618 const auto &
mesh = trial.mesh;
619 if (isFixedEdge(ctx, trial, edgeKey(
s,
t))) {
620 trial.flags.fixed =
true;
624 if (!edgeRing(
mesh,
s,
t, ring)) {
625 trial.flags.topology =
true;
628 const int label =
mesh.label[ring.cells.front()];
631 trial.flags.fixed =
true;
634 const auto &
polygon = ring.polygon;
637 if (isFixedFace(ctx, trial, faceKey(
s,
t,
v))) {
638 trial.flags.fixed =
true;
642 for (
int v : forced) {
646 trial.flags.topology =
true;
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;
657 std::vector<double> memo(
m *
m *
m, std::numeric_limits<double>::quiet_NaN());
660 const auto value = [&](
int a,
int b,
int c) {
661 auto &cached = memo[(
a *
m + b) *
m +
c];
662 if (!std::isnan(cached))
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) &&
672 if (
mesh.orient(upper) <= 0 ||
mesh.orient(lower) <= 0) {
673 trial.flags.inversion =
true;
676 if (isPocket(ctx, trial, upper) || isPocket(ctx, trial, lower)) {
677 trial.flags.pocket =
true;
680 cached = std::min(
mesh.quality(upper),
mesh.quality(lower));
686 struct Triangulation {
688 int split = -1, left = 0, right = 0;
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];
695 for (
int i = 0;
i !=
m; ++
i)
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) {
705 std::min({
quality, choice_at(
i,
k, left).quality,
706 choice_at(cyc(
i +
k),
n -
k, right).quality}),
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));
715 double forced_quality = infinity;
716 std::vector<std::array<int, 2>> chains;
717 std::vector<std::array<int, 3>>
triangles;
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;
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);
734 forced_quality = value(
a, b,
c);
735 chains = {{
a, ob}, {b, oc - ob}, {
c,
m - oc}};
738 trial.flags.topology =
true;
743 std::array<int, 3> ranks;
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);
756 if (combination.quality > -infinity)
757 combinations.push_back(combination);
759 std::stable_sort(combinations.begin(), combinations.end(),
760 [](
const Combination &
a,
const Combination &b) {
761 return a.quality > b.quality;
763 if (
alternative >=
static_cast<int>(combinations.size()))
766 std::vector<std::array<int, 3>>
work;
767 for (std::size_t
j = 0;
j != chains.size(); ++
j)
769 {chains[j][0], chains[j][1], combinations[alternative].ranks[j]});
770 while (!
work.empty()) {
771 const auto [
i,
n, rank] =
work.back();
775 const auto &choice = choice_at(
i,
n, rank);
776 const int k = choice.split;
778 work.push_back({
i,
k, choice.left});
779 work.push_back({cyc(
i +
k),
n -
k, choice.right});
781 plan.removed = ring.cells;
783 plan.minQuality = combinations[
alternative].quality;
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;
799 if (
cells.size() != 2) {
800 trial.flags.topology =
true;
804 trial.flags.fixed =
true;
807 const auto apex = [&](
int index) {
809 if (
v != face[0] &&
v != face[1] &&
v != face[2])
813 const int top = apex(
cells[0]), bottom = apex(
cells[1]);
818 trial.flags.inversion =
true;
822 std::swap(
f[1],
f[2]);
823 if (!newEdgeAllowed(ctx, trial, top, bottom))
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;
833 if (isPocket(ctx, trial, cell)) {
834 trial.flags.pocket =
true;
837 plan.minQuality = std::min(plan.minQuality,
mesh.quality(cell));
843void applyPlan(Trial &trial,
const Plan &plan) {
844 auto &
mesh = trial.mesh;
846 const int label =
mesh.label[plan.removed.front()];
851 for (
const auto &cell : plan.
cells)
856bool moveNode(Trial &trial,
int w,
const Vec &
position) {
857 auto &
mesh = trial.mesh;
860 for (
int c :
mesh.cellsOf(
w))
863 trial.flags.inversion =
true;
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) {
878 for (std::size_t
c = 0;
c !=
mesh.cells.size(); ++
c)
881 fail(
"non-positive cell");
886 double expected = ctx.initialVolume;
891 if (std::abs(volume - expected) > 1e-8 * ctx.initialVolume)
892 fail(
"region volume changed");
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");
901 fail(
"region boundary changed");
904 fail(
"fixed face removed");
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])];
915 if (ctx.
crack.count(face))
917 if (
mesh.faceCells.count(trial.newFace))
918 count(trial.newFace);
919 for (
const auto &face : trial.
closures)
922 for (
const auto &[edge,
k] : crack_edges)
924 fail(
"non-manifold crack edge");
927 ctx.
crackNode[edge[1]] && !isClosingEdge(trial, edge))
928 fail(
"bridging edge created");
931 fail(
"pocket created");
934std::vector<int> changedCells(
const Trial &trial) {
935 const auto &
mesh = trial.mesh;
936 std::vector<int>
cells;
950void repair(
const Context &ctx, Trial &trial,
double target) {
951 auto &
mesh = trial.mesh;
952 while (trial.operations < ctx.settings.maxFlipsPerCandidate) {
954 double worst_quality = infinity;
955 for (
int c : changedCells(trial)) {
956 const double q =
mesh.quality(
c);
957 if (
q < worst_quality) {
962 if (worst < 0 || worst_quality >=
target)
964 const Cell cell =
mesh.cells[worst];
965 const Flags saved = trial.flags;
967 double chosen_gain = 0;
968 const auto consider = [&](
const Plan &plan) {
969 double before = infinity;
972 const double gain = plan.minQuality - before;
973 if (gain > chosen_gain + 1e-12 && plan.minQuality > worst_quality) {
978 for (
const auto &e : cellEdges) {
980 if (planRemoval(ctx, trial, cell[e[0]], cell[e[1]], {},
nullptr, plan))
983 for (
int f = 0;
f != 4; ++
f) {
985 if (planFlip(ctx, trial, cellFace(cell,
f), plan))
991 if (chosen.cells.empty())
993 applyPlan(trial, chosen);
994 if (ctx.settings.audit)
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);
1022 for (
const auto &edge : edges)
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);
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};
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())
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);
1071 case NodeKind::Interior:
1072 targets.push_back({sub(x, mul(ctx.n, un - ratio * ud))});
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)
1080 const double alpha = (ratio * ud - un) / denominator;
1081 if (alpha < -slideBack * slide.length || alpha >= slide.length)
1083 targets.push_back({add(x, mul(slide.axis, alpha)), alpha < 0});
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);
1098 count += faceHasEdge(
f, edge);
1111bool frontCorner(
const Context &ctx,
const Trial &trial,
int f,
1113 if (!ctx.completeStar.count(
f))
1115 const auto &
mesh = trial.mesh;
1116 std::map<int, int> neighbours;
1118 const auto x =
mesh.point(
f);
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))
1126 int other[2],
k = 0;
1132 sector += angleAt(x,
mesh.point(other[0]),
mesh.point(other[1]));
1134 std::vector<int> front;
1135 for (
const auto &[
v, count] : neighbours) {
1138 if (count == 1 && !ctx.skinEdges.count(edgeKey(
f,
v)))
1141 if (front.size() != 2 || !(sector > M_PI))
1143 corner = {
f, front[0], front[1]};
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))
1154 const auto closing = edgeKey(corner.g, corner.h);
1155 if (crackFaceCount(ctx, trial,
closing) > 1)
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)
1162 const std::array<int, 3>
vertices{corner.f, corner.g, corner.h};
1166 const auto cells = attempt.mesh.cellsOf(
v);
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)
1174 if (!edgeRing(attempt.mesh,
a, b, ring))
1176 std::vector<int> forced;
1180 forced.push_back(x);
1185 if (forced.size() == 2 && missing !=
a && missing != b)
1187 if (forced.size() < 2)
1190 const Flags saved = attempt.flags;
1191 if (planRemoval(ctx, attempt,
a, b, forced, &
closing, plan) &&
1192 plan.minQuality > chosen.minQuality)
1194 attempt.flags = saved;
1197 if (chosen.cells.empty() || chosen.minQuality < ctx.settings.minimumQuality)
1199 applyPlan(attempt, chosen);
1200 if (attempt.mesh.cellsOf(face).size() != 2)
1202 if (ctx.settings.audit)
1203 audit(ctx, attempt);
1205 for (
int c : attempt.
mesh.cellsOf(face))
1206 if (isPocket(ctx, attempt, attempt.
mesh.
cells[
c]))
1208 trial = std::move(attempt);
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());
1220 for (
int guard = 0; !
work.empty() && guard != 64; ++guard) {
1221 const int v =
work.back();
1224 if (!frontCorner(ctx, trial,
v, corner) || !closeCorner(ctx, trial, corner))
1226 for (
int x : {corner.g, corner.h}) {
1232 for (
int v : visited) {
1234 open += frontCorner(ctx, trial,
v, corner);
1240bool pinched(
const Context &ctx,
const Trial &trial,
int v) {
1241 const auto &
mesh = trial.mesh;
1242 std::vector<Face> fan;
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);
1251 return !singleFan(fan,
v);
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;
1268 const auto point = [&](
int v) {
1269 const auto &x =
mesh.point(
v);
1270 return K::Point_3(x[0], x[1], x[2]);
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;
1278 Edge crossing{-1, -1};
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)))
1284 if (CGAL::do_intersect(K::Segment_3(point(edge[0]), point(edge[1])),
1288 if (crossing[0] < 0) {
1289 trial.flags.topology =
true;
1292 std::vector<int> forced;
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);
1298 forced.assign(face.begin(), face.end());
1300 if (!planRemoval(ctx, trial, crossing[0], crossing[1], forced, allowed,
1303 applyPlan(trial, plan);
1304 if (ctx.settings.audit)
1311enum class RouteKind {
1318 RouteKind
kind = RouteKind::Existing;
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);
1337 : trial.closureRoute ? Candidate::CLOSURE
1338 : norm(sub(final_position, x)) > 0
1340 : Candidate::EXTENSION;
1344 for (std::size_t
c = 0;
c != ctx.base.cells.size(); ++
c)
1354 for (
const auto &face : trial.
closures)
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;
1381bool runTrial(
const Context &ctx,
const Route &route,
int candidate_class,
1385 trial.mesh = ctx.base;
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);
1394 const auto move = [&]() {
1397 if (!moveNode(trial, route.w, *
position))
1399 if (ctx.settings.audit)
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)
1409 if (trial.operations >= ctx.settings.maxFlipsPerCandidate) {
1410 trial.flags.topology =
true;
1414 if (!planRemoval(ctx, trial, route.s, route.t, {ctx.f0, ctx.f1, route.w},
1415 route.closure ? &route.closing : nullptr, plan,
1418 applyPlan(trial, plan);
1419 if (ctx.settings.audit)
1423 if (move_first ? !(
move() && extend()) : !(extend() &&
move()))
1426 auto &
mesh = trial.mesh;
1427 if (
mesh.cellsOf(trial.newFace).size() != 2) {
1428 trial.flags.topology =
true;
1431 if (ctx.protectedFaces.count(trial.newFace)) {
1432 trial.flags.fixed =
true;
1437 trial.flags.pocket =
true;
1443 int open_corners = 0;
1445 open_corners = closeCorners(ctx, trial);
1447 for (
int v : {ctx.f0, ctx.f1, route.w}) {
1449 open_corners += frontCorner(ctx, trial,
v, corner);
1451 if (!route.joining && ctx.settings.requireClosedCorners && open_corners) {
1452 trial.flags.openCorner =
true;
1457 std::set<int>
vertices(trial.newFace.begin(), trial.newFace.end());
1458 for (
const auto &face : trial.
closures)
1462 if (pinched(ctx, trial,
v)) {
1463 trial.flags.pinch =
true;
1470 double before = infinity;
1471 for (std::size_t
c = 0;
c != ctx.base.cells.size(); ++
c)
1473 before = std::min(before, ctx.base.quality(
c));
1475 for (
int c : ctx.
base.cellsOf(route.
w))
1479 std::max(ctx.settings.minimumQuality, std::min(before, 1.)));
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;
1489 min_quality = std::min(min_quality,
q);
1494 const auto &x = ctx.points[route.w];
1497 if (route.joining) {
1500 TetMeshData recovered;
1501 recovered.points = ctx.points;
1502 for (std::size_t
c = 0;
c !=
mesh.cells.size(); ++
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);
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;
1516 if (joins.empty()) {
1517 trial.flags.topology =
true;
1521 if (ctx.settings.joinGapsOnly ||
1528enum class Outcome { Skipped, Rejected, Accepted };
1530Outcome tryRoute(
const Context &ctx,
const Route &route,
int candidate_class,
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) {
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;
1547 if (current.angle > ctx.tolerance) {
1549 return Outcome::Rejected;
1552 if (route.closure || candidate_class == Candidate::Flips)
1553 return runTrial(ctx, route, candidate_class,
nullptr,
true,
candidate,
1556 : Outcome::Rejected;
1558 if (current.angle <= ctx.tolerance)
1559 return Outcome::Skipped;
1560 const double ratio = candidate_class == Candidate::PartialMove
1561 ? std::tan(0.9 * ctx.tolerance)
1563 const auto targets = targetPositions(ctx, route.w, ratio);
1564 if (targets.empty())
1568 bool accepted =
false;
1569 for (
const auto &
target : targets) {
1572 ctx.settings.maxMoveRelative * ctx.meanEdge.at(route.w)) {
1576 const auto placed = placement(ctx,
position);
1577 if (!placed.ahead) {
1578 flags.behind =
true;
1581 if (placed.angle > ctx.tolerance) {
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,
1592 const double c = std::max(1, found.cardinality);
1593 found.score -= 0.5 * found.minQuality / (
c *
c);
1595 if (!accepted || better(found,
candidate)) {
1600 return accepted ? Outcome::Accepted : Outcome::Rejected;
1606enum class SearchMode { Extension, Closure, Joining };
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))
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");
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)
1630 if (!valid_point(
v))
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) {
1637 if (!valid_point(
v))
1639 if (face[0] == face[1] || face[1] == face[2] || face[0] == face[2])
1642 for (
const auto &edge : patch.featureEdges)
1643 if (!valid_point(edge[0]) || !valid_point(edge[1]) || edge[0] == edge[1])
1645 for (
int v : patch.fixedVertices)
1646 if (!valid_point(
v))
1648 const auto [
f0,
f1] = front_edge;
1649 if (!valid_point(
f0) || !valid_point(
f1) ||
f0 ==
f1)
1651 if (!finite(direction))
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])
1663void classifyCrack(Context &ctx,
const TetMeshData &patch,
1666 ctx.protectedFaces =
topology.protectedFaces;
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)
1674 for (
const auto &b : patch.
boundary)
1675 for (const auto &edge : faceEdges(faceKey(b[0], b[1], b[2])))
1677 for (
const auto &edge : patch.featureEdges)
1678 ctx.
fixedEdges.insert(edgeKey(edge[0], edge[1]));
1680 if (count == 1 && !ctx.
skinEdges.count(edge))
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))
1696 if (
v != ctx.
f0 &&
v != ctx.
f1)
1703 std::vector<char>
cells;
1706Region selectRegion(
const Context &ctx,
const TetMeshData &patch,
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)
1719 region.cells[
c] = 1;
1720 for (
int u : patch.
cells[
c])
1724 region.vertices.push_back(u);
1727 frontier.swap(next);
1731 THROW_MESSAGE(
"Crack extension region has a non-finite point");
1739void buildBaseMesh(Context &ctx,
const TetMeshData &patch,
1740 const Region ®ion) {
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];
1746 orientation(patch.points[cell[0]], patch.points[cell[1]],
1747 patch.points[cell[2]], patch.points[cell[3]]);
1749 std::ostringstream message;
1750 message << (
sign ?
"Inverted" :
"Degenerate")
1751 <<
" cell in the crack extension region: cell " <<
c
1753 Vec centre{0, 0, 0};
1754 for (
int v : cell) {
1756 << (patch.vertexIds.empty() ?
v : patch.vertexIds.at(
v));
1757 centre = add(centre, mul(patch.points[
v], 0.25));
1759 message << (patch.vertexIds.empty() ?
" (point indices)" :
" (IDs)")
1760 <<
", centre " << centre[0] <<
' ' << centre[1] <<
' '
1761 << centre[2] <<
"; fix the mesh, cells must be positively "
1765 ctx.base.add(cell,
c,
c,
1766 patch.cellLabels.empty() ? 0 : patch.cellLabels[
c]);
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");
1795void setNodeConstraints(Context &ctx,
const TetMeshData &patch,
1796 const PatchTopology &
topology,
const Region ®ion) {
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;
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]);
1810 EdgeSet edges, protected_edges;
1811 bool star_in_region =
true;
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))
1823 const bool is_protected = ctx.protectedFaces.count(face);
1824 if (
topology.faceCells.at(face).size() == 1 && !is_protected)
1825 star_in_region =
false;
1829 protected_edges.insert(edgeKey(u,
v));
1833 for (
const auto &edge : edges)
1835 ctx.meanEdge[
v] = edges.empty() ? 0 :
length / edges.size();
1838 const auto features = feature_neighbours.find(
v);
1839 const auto add_slide = [&](
int u) {
1842 const auto a = sub(patch.points[u], patch.points[
v]);
1843 constraint.slides.push_back({mul(
a, 1 / norm(
a)), norm(
a)});
1845 if (!star_in_region || fixed_vertex[
v] || ctx.crackNode[
v]) {
1847 }
else if (
features != feature_neighbours.end()) {
1848 if (
features->second.size() == 2) {
1853 }
else if (!protected_edges.empty()) {
1855 for (
const auto &e : protected_edges)
1856 add_slide(e[0] ==
v ? e[1] : e[0]);
1862 ctx.completeStar.insert(
v);
1867void recordReference(Context &ctx) {
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);
1875 ctx.initialEdges.insert(edge);
1876 if (ctx.fixedEdges.count(edge))
1877 ctx.initialFixedEdges.insert(edge);
1879 for (std::size_t
c = 0;
c != ctx.base.cells.size(); ++
c)
1880 ctx.initialVolume += ctx.base.volume(ctx.base.cells[
c]);
1889std::vector<Route> generateRoutes(
const Context &ctx, SearchMode mode) {
1890 const int f0 = ctx.f0,
f1 = ctx.f1;
1892 if (!edgeRing(ctx.base,
f0,
f1, front_ring))
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)
1904 for (
int f : {
f0,
f1}) {
1906 if (!frontCorner(ctx, before,
f, corner))
1908 const int other =
f ==
f0 ?
f1 :
f0;
1909 if (corner.g != other && corner.h != other)
1911 add_closing(corner.g == other ? corner.h : corner.
g, other);
1913 if (mode == SearchMode::Closure)
1914 for (
int f : {
f0,
f1}) {
1915 const int other =
f ==
f0 ?
f1 :
f0;
1917 if (
n != 1 || !ctx.wholeFront.count(edge) ||
1918 (edge[0] !=
f && edge[1] !=
f))
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)
1924 add_closing(
w, other);
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())
1935 const auto face = faceKey(
f0,
f1,
v);
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]);
1942 if (CGAL::collinear(point(
f0), point(
f1), point(
v)))
1945 for (
const auto &edge : faceEdges(face))
1947 if (ctx.settings.joinGapsOnly && shared < 2)
1949 if (ctx.protectedFaces.count(face) ||
1950 components.createsCycle(face, ctx.crackEdgeCount))
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;
1959 if (!ctx.crackNode[
v] && !ctx.skinEdges.count(edgeKey(
f0,
v)) &&
1960 !ctx.skinEdges.count(edgeKey(
f1,
v)))
1964 route.joining =
true;
1965 route.kind = ctx.base.cellsOf(face).size() == 2 ? RouteKind::Existing
1966 : RouteKind::Recovery;
1967 routes.push_back(route);
1971 const auto add_route = [&](
int v, RouteKind
kind,
int s,
int t) {
1974 if (!ctx.crackNode[
v]) {
1975 routes.push_back({
v,
kind,
s,
t});
1978 const auto it = closes.find(
v);
1979 if (
it != closes.end())
1980 routes.push_back({
v,
kind,
s,
t,
true,
it->second});
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];
1988 if (!edgeRing(ctx.base,
s,
t, ring))
1992 add_route(
v, RouteKind::Removal,
s,
t);
1994 if (mode == SearchMode::Closure) {
1995 for (
const auto &[
w,
closing] : closes)
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; }),
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) {
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)
2024 std::map<int, Candidate>
best;
2025 std::vector<Candidate> shortlist;
2026 for (
const auto &route : routes) {
2029 const auto outcome =
2031 if (outcome == Outcome::Skipped)
2033 ++ctx.report.candidatesTried;
2034 if (outcome == Outcome::Rejected) {
2035 flags.count(ctx.report);
2038 ++ctx.report.accepted;
2039 if (route.alternative)
2040 ++ctx.report.alternativeTriangulations;
2041 if (ctx.settings.lookAheadCandidates) {
2043 const auto same = [&](
const Candidate &
c) {
2051 for (
auto *
cells : {&left, &right}) {
2052 for (
auto &cell : *
cells)
2053 std::sort(cell.begin(), cell.
end());
2056 return left == right;
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);
2065 if (shortlist.size() >
2066 static_cast<std::size_t
>(ctx.settings.lookAheadCandidates))
2067 shortlist.pop_back();
2071 auto it =
best.find(route.w);
2075 std::vector<Candidate> ranked = std::move(shortlist);
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);
2083 result.insert(
result.end(), ranked.begin(), ranked.end());
2084 if (ctx.settings.stopAtFirstClass && !
result.empty())
2090void rankContinuations(
const Context &ctx,
const TetMeshData &patch,
2091 const std::vector<int> &crack_faces,
2092 std::vector<Candidate> &candidates);
2096std::vector<Candidate>
2097searchCandidates(
const TetMeshData &patch,
const std::vector<int> &crack_faces,
2098 const std::array<int, 2> &front_edge,
const Vec &direction,
2100 validateSearchInput(patch, crack_faces, front_edge, direction,
settings);
2101 const PatchTopology
topology(patch, crack_faces);
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);
2117 rankContinuations(ctx, patch, crack_faces,
result);
2124void rankContinuations(
const Context &ctx,
const TetMeshData &patch,
2125 const std::vector<int> &crack_faces,
2126 std::vector<Candidate> &candidates) {
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]);
2146 const auto digest = patchDigest(local, crack_faces);
2150 TetMeshData preview;
2151 std::vector<int> preview_crack;
2154 std::min<int>(ctx.settings.lookAheadCandidates, candidates.size());
2155 for (
int i = 0;
i != count; ++
i) {
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;
2164 preview_crack = crack_faces;
2166 ++ctx.report.lookAheadTrials;
2168 const PatchTopology
topology(preview, preview_crack);
2169 const auto edge_count = crackEdgeCounts(
topology.crack);
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)
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))
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)))
2194 direction = mul(direction, 1 /
length);
2197 if (
v != edge[0] &&
v != edge[1])
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);
2205 direction = mul(direction, -1);
2206 const double forward = dot(direction, ctx.d);
2208 edges.push_back({edge, direction, forward});
2210 std::sort(edges.begin(), edges.end(),
2211 [](
const NextEdge &
a,
const NextEdge &b) {
2212 return a.forward != b.forward ? a.forward > b.forward
2215 bool unknown = edges.empty() || edges.size() > 2;
2218 const auto record = [&](Candidate::ContinuationKind
kind,
const Face &face,
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]]);
2232 cross(mul(tangent, 1 / norm(tangent)), next.direction);
2233 const auto face_angle = [&](
const Face &face) {
2235 sub(preview.points[face[2]], preview.points[next.edge[0]]);
2236 return std::atan2(std::abs(dot(r, normal)), dot(r, next.direction)) *
2239 const auto follows_face = [&](
const Face &face) {
2240 return face_angle(face) <=
settings.angleToleranceDegrees;
2243 const auto closes_gap = [&](
const Face &face) {
2245 for (
const auto &edge : faceEdges(face))
2246 shared += edge_count.count(edge) != 0;
2247 return shared >= 2 && follows_face(face);
2250 {next.edge}, closes_gap);
2252 record(Candidate::CLOSURE,
closing.front().face,
2253 face_angle(
closing.front().face));
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);
2263 bool complete =
true;
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);
2274 if (!edgeRing(star, next.edge[0], next.edge[1], ring)) {
2280 const auto follows_direction = [&](
const Candidate &
c) {
2282 return c.angleDeviationDegrees <=
settings.angleToleranceDegrees;
2286 searchCandidates(preview, preview_crack, next.edge, next.direction,
2287 settings, future_report, SearchMode::Closure);
2291 record(Candidate::CLOSURE,
closing->newFace,
2292 closing->angleDeviationDegrees);
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);
2307 {next.edge}, follows_face);
2308 if (!joins.empty()) {
2309 record(Candidate::JOIN, joins.front().face,
2310 face_angle(joins.front().face));
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()) {
2322 joining->angleDeviationDegrees);
2323 if (
joining->operation == Candidate::CLOSURE)
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)) {
2335 all_classes.stopAtFirstClass =
false;
2337 searchCandidates(preview, preview_crack, next.edge, next.direction,
2338 all_classes, future_report, SearchMode::Extension);
2340 for (
const auto &found : continuation)
2341 if (follows_direction(found)) {
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);
2349 unknown |= !complete;
2352 ++ctx.report.lookAheadFeasible;
2353 ctx.report.lookAheadJoins +=
2355 ctx.report.lookAheadClosures +=
2357 }
else if (!unknown)
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);
2371std::vector<CGALTools::CrackExtensionCandidate>
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,
2383std::vector<CGALTools::CrackExtensionCandidate>
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,
2395std::vector<CGALTools::CrackExtensionCandidate>
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,
2411void CGALTools::applyCrackExtension(
2412 TetMeshData &patch, std::vector<int> &crack_faces,
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();
2424 THROW_MESSAGE(
"Crack extension cell labels do not match cells");
2426 THROW_MESSAGE(
"Crack extension partitions do not match cells");
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()))
2437 THROW_MESSAGE(
"Crack extension removed cells must be sorted and unique");
2439 if (c < 0 || c >= nc)
2442 THROW_MESSAGE(
"Crack extension parents do not match created cells");
2443 for (std::size_t
i = 0;
i !=
candidate.createdCells.size(); ++
i) {
2445 if (!valid_point(
v))
2449 THROW_MESSAGE(
"Crack extension parent is not a removed cell");
2453 if (!valid_point(
f[0]) || !valid_point(
f[1]) ||
f[2] !=
w ||
2454 !valid_point(
w) || !finite(
candidate.displacement))
2456 const auto face = faceKey(
f[0],
f[1],
f[2]);
2457 std::vector<Face> added{face};
2458 for (
const auto &
c :
candidate.closureFaces) {
2460 if (!valid_point(
v))
2462 added.push_back(faceKey(
c[0],
c[1],
c[2]));
2465 auto unique = added;
2466 std::sort(unique.begin(), unique.end());
2467 if (std::adjacent_find(unique.begin(), unique.end()) != unique.end())
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");
2475 const bool moves = norm(
candidate.displacement) > 0;
2479 for (
int i : crack_faces)
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)];
2491 for (
const auto &[
key,
n] : count) {
2499 std::vector<Cell> removed_cells;
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");
2508 std::vector<Cell>
cells;
2509 std::vector<int>
labels, partitions;
2510 for (
int c = 0, r = 0;
c != nc; ++
c) {
2516 const auto &cell = patch.
cells[
c];
2517 if (moves && std::count(cell.begin(), cell.end(),
w)) {
2518 const auto &p = patch.
points;
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]],
2523 if (before <= 0 || after <= 0)
2524 THROW_MESSAGE(
"Crack extension move inverts a retained cell");
2526 cells.push_back(cell);
2532 for (std::size_t
i = 0;
i !=
candidate.createdCells.size(); ++
i) {
2533 const auto &cell =
candidate.createdCells[
i];
2536 THROW_MESSAGE(
"Crack extension created cell is not positive");
2537 cells.push_back(cell);
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)
2550 THROW_MESSAGE(
"Crack extension result has a face with three cells");
2551 for (
const auto &
a : added)
2553 THROW_MESSAGE(
"Crack extension face is not interior after application");
2562 const int crack_label = crack_faces.empty() || patch.
surfaceLabels.empty()
2565 for (std::size_t
i = 0;
i != added.size(); ++
i) {
2569 crack_faces.push_back(patch.
boundary.size() - 1);
2580const std::vector<Face> &facesOf(
const PatchTopology &
topology,
2582 static const std::vector<Face> none;
2583 const auto it =
topology.edgeFaces.find(edge);
2584 return it ==
topology.edgeFaces.end() ? none :
it->second;
2589std::vector<std::array<int, 3>>
2591 const std::vector<int> &crack_faces)
const {
2592 checkPatchIndices(patch, crack_faces,
"crack fill");
2593 const PatchTopology
topology(patch, crack_faces);
2598 features.insert(edgeKey(e[0], e[1]));
2599 const auto &p = patch.
points;
2601 const auto folds = [&](
const Face &face) {
2602 for (
int c :
topology.faceCells.at(face)) {
2603 const auto count = countCellFaces(
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))
2613 const auto sector = [&](
int v) {
2615 for (
const auto &face :
crack)
2616 if (std::count(face.begin(), face.end(),
v)) {
2617 int other[2],
k = 0;
2621 sum += angleAt(p[
v], p[other[0]], p[other[1]]);
2626 std::vector<std::array<int, 3>> added;
2628 auto crack_edge_count = crackEdgeCounts(
crack);
2632 std::set<int> boundary_nodes;
2633 for (
const auto &[e, count] : crack_edge_count) {
2634 crack_edges.insert(e);
2637 boundary_nodes.insert(e[0]);
2638 boundary_nodes.insert(e[1]);
2641 std::set<Face> candidates;
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))
2653 const std::size_t on_front = edges.size();
2655 for (
const auto &e : faceEdges(face))
2657 std::find(edges.begin(), edges.end(), e) == edges.end())
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);
2666 for (
int v : edges[0])
2667 if ((
v == edges[1][0] ||
v == edges[1][1]) && boundary_nodes.count(
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))
2677 fill = !interior || sector(apex) > M_PI;
2679 }
else if (edges.size() == 3) {
2682 if (on_front == 1) {
2683 for (
const auto &e : faceEdges(face))
2685 std::find(edges.begin(), edges.end(), e) == edges.end())
2687 fill = edges.size() == 2;
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;
2694 if (fill && !
components.createsCycle(face, crack_edge_count) &&
2698 for (
const auto &e : faceEdges(face))
2699 ++crack_edge_count[e];
2700 accepted.push_back(face);
2703 if (accepted.empty())
2705 for (
const auto &face : accepted)
2706 added.push_back(face);
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 {
2716 checkPatchIndices(patch, crack_faces,
"crack join");
2717 const PatchTopology
topology(patch, crack_faces);
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 ||
2728 THROW_MESSAGE(
"Crack join front order has an invalid edge");
2729 priority.emplace(edgeKey(edge[0], edge[1]),
i);
2732 std::vector<Join> joined;
2733 for (std::size_t guard = 0; guard != patch.
cells.size() + 1; ++guard) {
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) {
2741 vertex_faces[
v].push_back(face);
2743 std::vector<Edge> front;
2744 for (
const auto &[e,
n] : count)
2745 if (
n == 1 && !skin_edges.count(e)) {
2747 front_node[e[0]] = front_node[e[1]] = 1;
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);
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)))
2763 for (
const auto &other : front) {
2764 if (other == e || (other[0] != o && other[1] != o))
2766 const int g = other[0] == o ? other[1] : other[0];
2769 if (skin_edges.count(edgeKey(
w,
g)) &&
2770 it !=
topology.faceCells.end() &&
it->second.size() == 2 &&
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())
2785 const auto edge_priority = front_order.empty() ? 0 : it_priority->second;
2788 for (
const auto &face : facesOf(
topology, e))
2789 if (
crack.count(face))
2791 if (
v != e[0] &&
v != e[1])
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)));
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)
2808 if (
v != e[0] &&
v != e[1])
2810 if (accept_face && !accept_face({e[0], e[1],
w}))
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)
2817 const auto r = sub(p[
w],
m);
2818 if (!(dot(r,
d) > 0))
2820 bool cut_free =
false;
2821 for (
int c :
topology.faceCells.at(face))
2822 cut_free |= cutFree(countCellFaces(
2824 [&](
const Face &
f) { return f == face || crack.count(f) != 0; },
2825 [&](
const Face &
f) { return topology.skin.count(f) != 0; }));
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;
2834 closes |= edge != e &&
n == 2;
2836 if (!manifold ||
components.createsCycle(face, count))
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) &&
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;
2864 joined.push_back(
best);
2865 if (!front_order.empty())
std::map< EntityHandle, int > labels
std::map< EntityHandle, int > index
std::vector< std::array< EntityHandle, 3 > > faces
Sorted keys.
CGALTools::CrackExtensionCandidate candidate
std::vector< int > created
FaceSet initialFixedFaces
EdgeMap< std::vector< int > > edgeCells
int h
Corner vertex and its two front neighbours.
int alternative
Second ring triangulation, before quality pruning.
FaceMap< std::vector< int > > faceCells
std::vector< int > source
std::vector< Slide > slides
Edges a sliding node may move along.
std::vector< std::vector< int > > vertexCells
std::unordered_map< int, double > meanEdge
const Settings & settings
const std::vector< Vec > * points
std::vector< Face > closures
Faces closing non-convex front corners.
std::vector< int > removed
int crackApex
Third node of the crack face at (f0, f1).
EdgeSet initialFixedEdges
bool angle
Radians between candidate face and target plane.
bool closureRoute
The new face itself closes a corner.
std::vector< int > polygon
std::vector< int > vertices
std::unordered_set< int > completeStar
Vertices whose star is in region.
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.
EdgeMap< std::vector< Face > > edgeFaces
Sorted faces of the cells.
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
int components
Inferred from the source tag length.
std::vector< double > empty
One value per component.
SmartPetscObj< Vec > work
SmartPetscObj< Vec > values
#define THROW_MESSAGE(msg)
Throw MoFEM exception.
FTensor::Index< 'i', SPACE_DIM > i
const double c
speed of light (cm/ns)
const double v
phase velocity of light in medium (cm/ns)
FTensor::Index< 'j', 3 > j
FTensor::Index< 'k', 3 > k
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 > &)
implementation of Data Operators for Forces and Sources
double constraint(double eqiv, double dot_tau, double f, double sigma_y, double abs_w, double vis_H, double sigma_Y)
FTensor::Index< 'm', 3 > m
std::vector< int > partitions
Optional cell-to-rank assignment.
std::vector< std::array< int, 3 > > boundary
std::vector< std::array< int, 2 > > featureEdges
std::vector< int > cellLabels
std::vector< std::array< int, 4 > > cells
Zero-based point indices.
std::vector< std::array< double, 3 > > points
std::vector< int > surfaceLabels
std::vector< int > fixedVertices
Point indices which cannot move or collapse.