Manifold extraction¶

manifold_extraction makes the boundary of a selection of regions manifold. In a tagged tet mesh (3D) or triangle mesh (2D), a selection is a set of cells given by a tag expression, and its boundary is the surface (3D) or curve (2D) between the selected cells and the others. Where two parts of the selection touch only along an edge or at a vertex, that boundary is non-manifold there. The component finds those edges and vertices, carves a thin region around them, and gives the carved cells the tags in fill_tags: the background separates the parts, a selected tag joins them.

Use it on a tagged mesh whose regions touch, before a step that needs a manifold boundary, such as a surface extracted for a solver or a surface remesher. The carving is a topological offset of the non-manifold edges and vertices, construction only: it is fast, but the cells it cuts are of lower quality, and simwild's remeshing is the step after it.

What is non-manifold¶

The test is local, at each vertex and edge on the selection's boundary:

An edge (3D) is non-manifold when the selected tets around it do not form one fan: going from tet to tet across their faces around the edge does not reach all of them. Around an edge of the circle where two balls touch, the tets go ball, outside, ball, outside: the selected ones form two fans.
A vertex (3D) is non-manifold when the selected tets around it, or the other tets around it, are not one face-connected set each. The outside of the mesh counts as one cell of the others.
A vertex (2D) is non-manifold when the selected triangles around it do not form one fan across their edges: two triangles that share a vertex and no edge.

An edge or vertex that is not on the boundary is not tested. A boundary that passes the test everywhere is a closed manifold surface (in 2D, closed curves).

A first run¶

Two spheres, tag_0 and tag_1, overlap; the overlap was removed, so they touch along the circle where their surfaces cross. The union tag_0 | tag_1 has a non-manifold boundary along that circle. With the default fill_tags, the background:

Command linePythonC++

{
  "application": "manifold_extraction",
  "input": "double_sphere_hole.msh",
  "output": "double_sphere_manifold",
  "tag_selection": "tag_0 | tag_1",
  "fill_tags": [],
  "write_surface": true,
  "report": "double_sphere_manifold.json"
}

wmtk_app -j manifold_extraction.json

The input must be a .msh. The repaired mesh is double_sphere_manifold.msh, and with write_surface the boundary of the selection is double_sphere_manifold.obj.

spheres = wm.read_mesh(str(DATA / "double_sphere_hole.msh"))
outputs, report = wm.manifold_extraction(
    {"input": "spheres", "tag_selection": "tag_0 | tag_1", "fill_tags": []},
    {"spheres": spheres},
)
repaired = outputs["mesh"]
print(report["before #t"], "->", report["after #t"], "tets")

On files instead, with the same options as the JSON file:

wm.manifold_extraction({
    "input": str(DATA / "double_sphere_hole.msh"),
    "output": "double_sphere_manifold",
    "tag_selection": "tag_0 | tag_1",
    "fill_tags": [],
    "write_surface": True,
})

wmtk::MeshMap meshes{{"spheres", wmtk::io::read_mesh(data / "double_sphere_hole.msh")}};
auto [outputs, report] = wmtk::components::manifold_extraction::manifold_extraction(
    {{"input", "spheres"},
     {"tag_selection", "tag_0 | tag_1"},
     {"fill_tags", nlohmann::json::array()}},
    meshes);
std::cout << report["before #t"] << " -> " << report["after #t"] << " tets\n";
wmtk::io::write_mesh("double_sphere_manifold.msh", outputs.at("mesh"));
// The boundary of the selection after the repair, a triangle mesh of its own.
wmtk::io::write_mesh("double_sphere_manifold_surface.msh", outputs.at("surface"));

Link wmtk::manifold_extraction.

The log reports 28 non-manifold edges and 28 non-manifold vertices (the count of vertices includes the edges' ends), and the mesh goes from 15,131 to 17,093 tets in a fraction of a second. The union's boundary had 970 triangles and 28 non-manifold edges; it now has 1,284 triangles, no non-manifold edge or vertex, and is two closed surfaces: the spheres no longer touch. To check a result, count the edges of the boundary that are not on exactly two triangles:

def selected(mesh, *tags):
    """The tets that carry any of `tags`."""
    t = mesh["cells"]["tetrahedron"]["attributes"]["tags"]
    columns = [t["labels"].index(tag) for tag in tags]
    return np.asarray(t["values"])[:, columns].any(axis=1)


def boundary(mesh, inside):
    """The triangles between the tets in `inside` and the others (or the outside)."""
    T = np.asarray(mesh["cells"]["tetrahedron"]["connectivity"])[inside]
    F = np.sort(np.concatenate([T[:, [0, 1, 2]], T[:, [0, 1, 3]], T[:, [0, 2, 3]],
                                T[:, [1, 2, 3]]]), axis=1)
    faces, count = np.unique(F, axis=0, return_counts=True)
    return faces[count == 1]


def nonmanifold_edges(F):
    """Edges of the triangles F that are not on exactly two of them."""
    E = np.sort(np.concatenate([F[:, [0, 1]], F[:, [1, 2]], F[:, [2, 0]]]), axis=1)
    _, count = np.unique(E, axis=0, return_counts=True)
    return int((count != 2).sum())


before = boundary(spheres, selected(spheres, "tag_0", "tag_1"))
after = boundary(repaired, selected(repaired, "tag_0", "tag_1"))
print("non-manifold edges:", nonmanifold_edges(before), "->", nonmanifold_edges(after))
print("extracted surface:", len(outputs["surface"]["cells"]["triangle"]["connectivity"]),
      "triangles, non-manifold edges:",
      nonmanifold_edges(outputs["surface"]["cells"]["triangle"]["connectivity"]))

It prints 28 -> 0, and 0 for the extracted surface.

In 2D¶

Two triangles of tag_0 share one vertex and no edge (vertex_adj_tris.msh, 50 triangles):

Command linePython

{
  "application": "manifold_extraction",
  "input": "vertex_adj_tris.msh",
  "output": "vertex_adj_tris_manifold",
  "tag_selection": "tag_0",
  "write_surface": true
}

wmtk_app -j manifold_extraction_2d.json

With write_surface in 2D, vertex_adj_tris_manifold.obj holds the boundary as polylines (l records).

# Two triangles of tag_0 that share a vertex and nothing else.
triangles = wm.read_mesh(str(DATA / "vertex_adj_tris.msh"))
out, report = wm.manifold_extraction(
    {"input": "triangles", "tag_selection": "tag_0"}, {"triangles": triangles})
curve = out["surface"]  # the boundary of tag_0 after the repair: edges
print(report["before #f"], "->", report["after #f"], "triangles;",
      len(curve["cells"]["edge"]["connectivity"]), "boundary edges")

The log reports one non-manifold vertex. The mesh goes from 50 to 62 triangles; tag_0 is four triangles in two pieces, which no longer touch, with a manifold boundary of 8 edges.

The input on the left, the result on the right: drag to rotate, scroll to zoom; on the tet mesh, move the cut with the slider. Every example is in the gallery.

Key settings¶

The selection: `tag_selection`¶

tag_selection (default tag_0) is the selection whose boundary is made manifold: an expression over the tag names, with & (and), | (or), ! (not) and parentheses, as in simwild. ambient names the background. A cell is selected when its tags satisfy the expression. On the two spheres, tag_0 | tag_1 and !ambient select the same cells and give the same mesh.

The selection decides what counts as touching. tag_0 alone is a ball with a dent where the overlap was; its boundary is manifold, and so is tag_1's. Only their union is non-manifold.

What fills the cut: `fill_tags`¶

fill_tags are the tags given to every carved cell, replacing the tags it had. The default, [], is the background: ambient cannot be named here (the component ignores it, with a warning). On the two spheres, the carved tube is 886 tets:

# Fill the carved tube with tag_0 instead of ambient: the two spheres are joined, not separated.
for fill in [[], ["tag_0"]]:
    out, _ = wm.manifold_extraction(
        {"input": "spheres", "tag_selection": "tag_0 | tag_1", "fill_tags": fill},
        {"spheres": spheres})
    m = out["mesh"]
    print(f"fill_tags {fill}: tag_0 {selected(m, 'tag_0').sum()} tets,"
          f" tag_1 {selected(m, 'tag_1').sum()} tets,"
          f" non-manifold edges {nonmanifold_edges(boundary(m, selected(m, 'tag_0', 'tag_1')))}")

`fill_tags`	`tag_0` tets	`tag_1` tets	boundary of the union
`[]`	1,637	1,574	1,284 triangles, two closed surfaces
`["tag_0"]`	2,523	1,574	1,568 triangles, an outer surface and the cavity

With the background, the parts come apart. With a selected tag, the tube joins them, and the removed overlap becomes a closed cavity. A tag the mesh does not have is added as a new region (the log says Tag 'bridge' does not exist. Adding to mesh.), which marks the carved cells; for the selection it is background unless the expression names it. In 2D, filling with tag_0 gives tag_0 10 triangles in one piece, with a manifold boundary of 10 edges.

The size of the cut: `radius_rel`, `radius`¶

radius_rel (default 0.01) is the radius of the carved region, relative to the bounding box diagonal; radius, when positive, replaces it with an absolute length. The carved region is always one ring of cells around the non-manifold edges and vertices; the radius places the cut inside that ring. Each edge that leaves a non-manifold simplex is cut at the radius when the far end of every such edge is farther than the radius from the non-manifold simplices; otherwise every one is cut at half the smallest of those distances (the log calls it the maximum marchable distance). The log says which:

[construction] construction_mode max_marchable_fallback: maximum marchable distance 0.0587032 over 356 marched edges; target_distance 0.0674414 is not below it, so the march traces to half of it, 0.0293516 (0.4352x target_distance)

On the two spheres (diagonal 3.37), the default radius, 0.0337, is below that limit, 0.0587:

`radius_rel`	where the cut is	max AMIPS
(input)		7.26
0.005	at the radius, 0.0169	112.9
0.01	at the radius, 0.0337	42.06
0.02	at half the limit, 0.0294	51.43
0.05	at half the limit, 0.0294	51.43

So a small radius cuts thin cells next to the non-manifold edges, and a radius above the limit changes nothing: the cut never reaches beyond the cells that touch the contact.

Output files: `write_surface`¶

write_surface writes the boundary of the selection after the repair as <output>.obj: triangles in 3D, polylines in 2D. The component checks it before writing and logs Vertex manifoldness check passed. and Edge manifoldness check passed. (in 2D, Curve manifoldness check passed.), or a warning.

Outputs¶

The repaired mesh: output on the command line (default out, written as out.msh), outputs["mesh"] in memory. It has the input's tags, the fill tags on the carved cells, and diagnostic fields of the offset (labels, offset_tag, amips and others).
outputs["surface"] in memory: the boundary of the selection after the repair, a triangle mesh in 3D and an edge mesh in 2D, with vertices of its own. On files, write_surface writes it.
With report, a JSON file with the vertex, edge, face (and in 3D tet) counts before and after, and the run time. In memory, the report is the second return value.
With save_vtu, the mesh as .vtu files for ParaView.

Pitfalls¶

A selection that is already manifold is left as it is. When no edge or vertex is non-manifold (on the two spheres, tag_0 alone, or tag_0 & tag_1, which selects nothing), there is nothing to offset: the run logs it and returns the mesh unchanged.
The quality drops. The cut is not optimized: on the two spheres the max AMIPS goes from 7.26 to 42.06 (avg 3.69 to 4.29). Run simwild's remeshing on the result; it keeps the regions' topology and so their manifold boundary.
The radius is not a distance guarantee. See the size of the cut: the cut stays within one ring of cells.
A selection that reaches the mesh boundary. Vertices on the mesh boundary are judged with the outside of the mesh as one more cell; the log warns Vertex of offset input complex lies on mesh boundary, and the final check may report a non-manifold surface, which it attributes to that. Keep the selection inside the domain, with background cells around it.
Face tags are refused. A mesh with tagged faces (simwild's input_type surface) stops with manifold_extraction does not take tagged faces yet.

Manifold extraction¶

What is non-manifold¶

A first run¶

In 2D¶

Key settings¶

The selection: tag_selection¶

What fills the cut: fill_tags¶

The size of the cut: radius_rel, radius¶

Output files: write_surface¶