Edge length that varies: a sizing mesh¶
The meshing and remeshing components aim for one edge length everywhere:
length_rel times the input's bounding box diagonal, or
length in the input's units. Only where the quality gets
stuck do they refine on their own. Often a simulation wants something else: small elements near a
crack, a load or a thin part, large ones far from it.
A sizing mesh gives the largest edge length as a field over space. TriWild, TetWild, SimWild
and isotropic remeshing take one as their sizing_mesh option:
| Component | The sizing mesh | Where a point reads it |
|---|---|---|
| TriWild | triangles, in the plane | the triangle containing it |
| TetWild | tetrahedra | the tet containing it |
| SimWild | triangles in 2D, tetrahedra in 3D | the cell containing it |
| Isotropic remeshing | a triangle surface | the point of the surface closest to it |
The option is optional: without it, every component runs exactly as before.
The sizing mesh¶
Any mesh with those cells whose vertices carry the length, in the input's units, as a vertex field
named target_length: one positive value per vertex, interpolated linearly inside the cells. It
does not have to match the input: a few large cells around it are enough for a smooth field. In
Python it is a mesh dictionary, here a square of two triangles whose
length grows from 1% of a circle's size on its left side to 6% on its right:
# A square around the input, two triangles, whose length grows from `left` on its left side to
# `right` on its right: interpolated linearly in between.
def planar_sizing(lo, hi, left, right):
V = np.array([[lo, lo, 0], [hi, lo, 0], [hi, hi, 0], [lo, hi, 0]], dtype=float)
F = np.array([[0, 1, 2], [0, 2, 3]])
return {
"V": V,
"cells": {"triangle": {"connectivity": F}},
"vertex_attributes": {"target_length": np.array([left, right, right, left])},
}
# The lengths are in the input's units: from 1% of the circle's size to 6%. The square reaches a
# fifth of that size past the circle on each side, beyond the background mesh TriWild builds
# around its input: a point outside every triangle takes the global length.
circle = wm.read_mesh(str(DATA / "triwild_circle.obj"))
lo, hi = circle["V"][:, :2].min(), circle["V"][:, :2].max()
size = hi - lo
lo, hi = lo - 0.2 * size, hi + 0.2 * size
sizing = planar_sizing(lo, hi, 0.01 * size, 0.06 * size)
A point outside every cell is not covered, and takes the component's global length there. Make the sizing mesh cover more than the input: TriWild and TetWild mesh a box larger than the input's bounding box (by 1/15 of its diagonal on each side), and its vertices are sized too. A surface sizing mesh covers every point: isotropic remeshing reads it at the closest point.
TriWild¶
On the memory route, sizing_mesh names a mesh of the call. The inside of the circle, first at
the default length_rel 0.05, then with the sizing mesh. Each edge is compared with the field at
its midpoint:
# The inside of the circle, with and without the sizing mesh, sequentially (num_threads 0) so
# that the numbers repeat exactly.
options = {"input": ["circle"], "filter": "input", "stop_energy": 10, "num_threads": 0}
for name, extra in [("length_rel 0.05", {}), ("sizing mesh", {"sizing_mesh": "sizing"})]:
outputs, report = wm.triwild({**options, **extra}, {"circle": circle, "sizing": sizing})
triangles = len(outputs["mesh"]["cells"]["triangle"]["connectivity"])
print(f"triwild, {name}: {triangles} triangles after {report['#iterations']} iteration(s), "
f"{against(outputs['mesh'], 'triangle', field)}")
wmtk::MeshData circle = wmtk::io::read_mesh(data / "triwild_circle.obj");
const double size = circle.V.leftCols(2).maxCoeff() - circle.V.leftCols(2).minCoeff();
const double lo = circle.V.leftCols(2).minCoeff() - 0.2 * size;
const double hi = circle.V.leftCols(2).maxCoeff() + 0.2 * size;
// A square around the circle, past the background mesh TriWild builds around it, two
// triangles, whose vertex field target_length grows from 1% of the circle's size on its left
// side to 6% on its right, in the input's units.
wmtk::MeshData sizing;
sizing.V.resize(4, 3);
sizing.V << lo, lo, 0, hi, lo, 0, hi, hi, 0, lo, hi, 0;
sizing.cells[wmtk::CellType::Triangle].connectivity.resize(2, 3);
sizing.cells[wmtk::CellType::Triangle].connectivity << 0, 1, 2, 0, 2, 3;
wmtk::DataMatrix<double> length(4, 1);
length << 0.01 * size, 0.06 * size, 0.06 * size, 0.01 * size;
sizing.vertex_attributes["target_length"].values = length;
wmtk::MeshMap meshes{{"circle", circle}, {"sizing", sizing}};
auto [outputs, report] = wmtk::components::triwild::triwild(
{{"input", nlohmann::json::array({"circle"})},
{"sizing_mesh", "sizing"},
{"filter", "input"},
{"stop_energy", 10},
{"num_threads", 0}},
meshes);
// Every edge against the field at its midpoint: the share longer than 4/3 of it, those a
// split would cut. The field is a largest length; shorter is fine.
const wmtk::MeshData& mesh = outputs.at("mesh");
const auto& F = mesh.cell(wmtk::CellType::Triangle).connectivity;
size_t total = 0, too_long = 0;
for (Eigen::Index f = 0; f < F.rows(); ++f) {
for (int k = 0; k < 3; ++k) {
const Eigen::RowVector3d a = mesh.V.row(F(f, k)), b = mesh.V.row(F(f, (k + 1) % 3));
const double t = (0.5 * (a.x() + b.x()) - lo) / (hi - lo);
const double field = (0.01 + 0.05 * t) * size;
++total; // each interior edge twice, as both its triangles see it
if ((a - b).norm() > 4. / 3. * field) ++too_long;
}
}
std::cout << F.rows() << " triangles, " << 100. * too_long / total
<< "% of the edges past 4/3 of the field\n";
wmtk::io::write_mesh("circle.msh", mesh);
triwild, length_rel 0.05: 289 triangles after 1 iteration(s), 52.9% of the edges past 4/3 of the field, median 1.38 of it
triwild, sizing mesh: 841 triangles after 1 iteration(s), 0.3% of the edges past 4/3 of the field, median 0.85 of it
length_rel 0.05 on the left, the sizing mesh on the right. Each triangle is colored by its
longest edge over the field at the edge's midpoint: white as long as the field, pale up to 4/3 of
it, red past that, blue shorter. The field grows from left to right; one length for the whole
circle suits its right side only. Scroll to zoom, switch the coloring below the meshes. Every
example is in the gallery.
On the file route, sizing_mesh is the path of a mesh file, relative to
input_dir like the inputs. A .msh file written by
wm.write_mesh keeps the field, as a node field target_length:
# The same run on files: the sizing mesh is a mesh file whose vertices carry the field
# target_length, relative to input_dir like the inputs.
wm.write_mesh("sizing.msh", sizing)
wm.triwild({**options, "input": [str(DATA / "triwild_circle.obj")], "sizing_mesh": "sizing.msh",
"output": "circle"})
print(f"triwild on files: {against(wm.read_mesh('circle.msh'), 'triangle', field)}")
The same mesh as on the memory route. On the command line, the same is
"sizing_mesh": "sizing.msh" in the JSON.
A largest length, not a target¶
In TriWild, TetWild and SimWild every vertex carries a sizing, the factor of the target length its edges are split and collapsed to (an edge longer than 4/3 of its target is split, one shorter than 4/5 collapsed; the optimization loop). The sizing mesh sets the sizing of every vertex it covers when the optimization starts, to the field's length over the global one, and caps it after every pass:
- New vertices follow the field. A split's new vertex takes the mean of its ends' sizing, and the cap lowers it where the field asks for less.
- Finer is allowed. Where the quality gets stuck, the stuck refinement lowers the sizing further, and the cap only ever lowers it. A collapse that would make an element worse is still refused. Either way the mesh ends finer than the field there, and that is a valid result: the median edge above is 0.85 of the field.
- Longer than
lengthis allowed. The field may ask for more than the global length;lengthandlength_relthen only apply where it does not reach.
Keeping the edges under the field¶
Two things hold the edges under the field, both only with a sizing mesh:
limit_collapse_lengthis on unless set to false, in all four components. A collapse is judged by the edge it removes; without the limit, it may leave edges longer than their target, and since the optimization ends on collapses, nothing splits them again. With it, no collapse leaves an edge longer than 4/3 of its target, the length above which a split would cut it, as Botsch and Kobbelt's isotropic remeshing does.- The optimization does not stop on quality alone (TriWild, TetWild, SimWild). It goes on past
stop_energywhile more than 1% of the edges are longer than 4/3 of their target and that share still drops by a tenth from one iteration to the next, up tomax_iterations. Edges shorter than the field never keep it going.
Turned off, the limit costs fewer elements and more edges past the field; the second rule then runs one more iteration:
# With a sizing mesh, limit_collapse_length is on unless set: no collapse leaves an edge longer
# than 4/3 of its target. Turned off, collapses merge edges past the field:
for limit in [True, False]:
outputs, report = wm.triwild(
{**options, "sizing_mesh": "sizing", "limit_collapse_length": limit},
{"circle": circle, "sizing": sizing})
triangles = len(outputs["mesh"]["cells"]["triangle"]["connectivity"])
print(f"limit_collapse_length {limit}: {triangles} triangles after {report['#iterations']} "
f"iteration(s), {against(outputs['mesh'], 'triangle', field)}")
limit_collapse_length True: 841 triangles after 1 iteration(s), 0.3% of the edges past 4/3 of the field, median 0.85 of it
limit_collapse_length False: 577 triangles after 2 iteration(s), 13.0% of the edges past 4/3 of the field, median 1.02 of it
The limit on the left, off on the right: there, the collapses leave the red triangles, whose longest edge is past the field.
Smoothing can still stretch an edge a little past 4/3 of its target: to keep every edge under a bound, give about 3/4 of it as the field.
The field is read at the vertices: an edge's target is the mean of its ends'. A field smooth at the scale of the edges, as above, is kept closely; one that varies a lot within an edge's length is followed less well, since the field between the ends does not count: give the sizing mesh cells no smaller than the edges you expect. The stuck refinement grades its own refinement into the neighbourhood, but not past a vertex whose sizing the field set above the global length.
TetWild¶
The sizing mesh is a tet mesh. A box around a sphere of radius 0.7, as five tets, whose length grows from 0.03 at its bottom to 0.15 at its top:
# TetWild: the sizing mesh is a tet mesh. A box around a sphere of radius 0.7, as five tets,
# whose length grows from 0.03 at its bottom to 0.15 at its top: linear in z.
def box_sizing(lo, hi, bottom, top):
x0, y0, z0 = lo
x1, y1, z1 = hi
V = np.array([[x, y, z] for z in (z0, z1) for y in (y0, y1) for x in (x0, x1)], dtype=float)
T = np.array([[0, 1, 3, 5], [0, 3, 2, 6], [0, 5, 4, 6], [3, 5, 6, 7], [0, 3, 6, 5]])
return {"V": V, "cells": {"tetrahedron": {"connectivity": T}},
"vertex_attributes": {"target_length": np.where(V[:, 2] == z0, bottom, top)}}
sphere = wm.read_mesh(str(DATA / "sphere.obj"))
margin = 0.2 * np.linalg.norm(sphere["V"].max(axis=0) - sphere["V"].min(axis=0))
box_lo, box_hi = sphere["V"].min(axis=0) - margin, sphere["V"].max(axis=0) + margin
box = box_sizing(box_lo, box_hi, 0.03, 0.15)
for name, extra in [("length_rel 0.05", {}), ("sizing mesh", {"sizing_mesh": "box"})]:
outputs, report = wm.tetwild(
{"input": ["sphere"], "filter": "tracked", "num_threads": 0, **extra},
{"sphere": sphere, "box": box})
tets = len(outputs["mesh"]["cells"]["tetrahedron"]["connectivity"])
print(f"tetwild, {name}: {tets} tets, {against(outputs['mesh'], 'tetrahedron', box_field)}")
tetwild, length_rel 0.05: 12687 tets, 29.6% of the edges past 4/3 of the field, median 1.16 of it
tetwild, sizing mesh: 34011 tets, 0.6% of the edges past 4/3 of the field, median 0.85 of it
The tets the cut exposes are colored as above, the faces of the boundary gray. Here z points to the left: the field grows from right to left. Drag to rotate, move the cut with the slider.
Isotropic remeshing¶
The sizing mesh is a surface, and isotropic remeshing reads it at the point closest to each
vertex, again wherever an operation moves one; an edge's target is the mean of its ends'. For
isotropic remeshing the field is a target rather than a largest length, as length is: it splits
and collapses every edge toward it, for a fixed number of iterations, with no stuck refinement and
no energy target to stop at. The input itself can be the sizing mesh: here the bunny, with a field
that goes from 4% of its diagonal at its feet to 1% at its ears:
# Isotropic remeshing: the sizing mesh is a surface, read at the point closest to each vertex.
# Here it is the input itself, with a field that goes from 4% of the bunny's diagonal at its
# feet to 1% at its ears: linear in y.
bunny = wm.read_mesh(str(DATA / "bunny.obj"))
y0, y1 = bunny["V"][:, 1].min(), bunny["V"][:, 1].max()
diag = np.linalg.norm(bunny["V"].max(axis=0) - bunny["V"].min(axis=0))
height = (bunny["V"][:, 1] - y0) / (y1 - y0)
bunny_sizing = dict(bunny, vertex_attributes={"target_length": diag * (0.04 - 0.03 * height)})
for name, extra in [("length_rel 0.025", {"length_rel": 0.025}),
("sizing mesh", {"sizing_mesh": "field"})]:
outputs, _ = wm.isotropic_remeshing({"input": "bunny", "max_iterations": 5, **extra},
{"bunny": bunny, "field": bunny_sizing})
triangles = len(outputs["mesh"]["cells"]["triangle"]["connectivity"])
print(f"isotropic_remeshing, {name}: {triangles} triangles, "
f"{against(outputs['mesh'], 'triangle', bunny_field)}")
isotropic_remeshing, length_rel 0.025: 2559 triangles, 21.0% of the edges past 4/3 of the field, median 0.96 of it
isotropic_remeshing, sizing mesh: 3633 triangles, 0.5% of the edges past 4/3 of the field, median 1.02 of it
At one length, the triangles are too long for the ears (red); with the sizing mesh, they follow the field from the feet to the ears.
SimWild: with regions¶
SimWild also sizes by region:
sizing_field gives a length per region expression.
With both, a vertex takes the smaller of its regions' length and the sizing mesh's; where only
the sizing mesh reaches, its length, even longer than length; where only a region, the region's.
Only the remeshing operation optimizes: the region
operations ignore both options, so one set of options can be passed to every step of a pipeline.
The coarsening pass¶
The optional coarsening pass of TriWild, TetWild and
SimWild runs after the optimization and removes the elements the quality target does not need: it
takes collapses the optimization refused, and keeps one when, after smoothing around it, no
element there is worse than before (the coarsening pass).
With a sizing mesh, limit_collapse_length holds it under the field too: none of its collapses
leaves an edge longer than 4/3 of the field's length. It coarsens where it can without breaking
the field:
# The coarsening pass takes collapses the optimization refused on quality. With the sizing mesh,
# limit_collapse_length holds it under the field too; turned off, it coarsens past the field.
for name, extra in [("coarsen_pass", {}), ("coarsen_pass, limit off", {"limit_collapse_length": False})]:
outputs, report = wm.tetwild(
{"input": ["sphere"], "filter": "tracked", "num_threads": 0, "sizing_mesh": "box",
"coarsen_pass": True, **extra},
{"sphere": sphere, "box": box})
tets = len(outputs["mesh"]["cells"]["tetrahedron"]["connectivity"])
print(f"tetwild, {name}: {tets} tets, {against(outputs['mesh'], 'tetrahedron', box_field)}")
tetwild, coarsen_pass: 32667 tets, 0.6% of the edges past 4/3 of the field, median 0.87 of it
tetwild, coarsen_pass, limit off: 15009 tets, 24.0% of the edges past 4/3 of the field, median 1.10 of it
With the limit (on the left), the pass removes 4% of the 34011 tets, and the field still holds: the optimization had already brought the edges to the field, so most collapses would make them longer than it. Without the limit, it removes 56% of them, and makes the edges longer than the field (red). Where the mesh is finer than the field, after a stuck refinement or near the input's details, the pass has more to remove.
Unbounded (the default), the pass knows no target
length but the limit's. Bounded, it also leaves alone the edges at or past 4/5 of the target: with
a sizing mesh, of the field's length at the edge's ends, also where that is longer than length.
Summary¶
For TriWild, TetWild and SimWild; isotropic remeshing shares the first and the
limit_collapse_length rows.
| Without a sizing mesh | With one | |
|---|---|---|
| Largest edge length | length, or length_rel times the diagonal |
the field's where it covers the vertex, else as without |
| Finer than that | stuck refinement, and collapses refused on quality | the same |
limit_collapse_length |
off unless set | on unless set to false |
| Stops when | the energy is under stop_energy |
the same, and at most 1% of the edges past 4/3 of their target, or no more progress |
| Coarsening pass | as far as the energy allows; bounded, stops at 4/5 of length |
under 4/3 of the field (the limit); bounded, also stops at 4/5 of it |
SimWild's sizing_field |
the region's length | the smaller of the region's and the field's |