Skip to content

TriWild

triwild triangulates the plane around curve networks as they come: polylines that cross, overlap, or miss each other by a little. It simplifies the curves inside an envelope, inserts them exactly into a triangulation of their bounding box, so that every input segment becomes a chain of triangle edges and every crossing a vertex, and then improves the triangles' shape while the inserted curves stay within a distance \(\varepsilon\) of the input (Hu et al. 2019). A filter can remove what lies outside the curves at the end.

Use it to mesh a 2D domain bounded by drawn or traced curves, or several overlapping regions at once: each triangle records which inputs it lies inside. For the same in 3D, from triangle surfaces, use TetWild; for regions in a mesh you already have, SimWild.

A first run

Five closed curves that overlap, each its own input file, named after its shape:

{
  "application": "triwild",
  "input": [
    "triwild_blob1.obj",
    "triwild_blob2.obj",
    "triwild_circle.obj",
    "triwild_ellipse.obj",
    "triwild_rectangle.obj"
  ],
  "input_names": ["blob1", "blob2", "circle", "ellipse", "rectangle"],
  "output": "shapes",
  "filter": "input",
  "stop_energy": 10,
  "num_threads": 4,
  "report": "shapes_report.json"
}
wmtk_app -j triwild.json

The input paths are relative to the JSON file; the outputs, the triangle mesh shapes.msh among them (see outputs), are written to the working directory.

curves = {name: wm.read_mesh(str(DATA / f"triwild_{name}.obj")) for name in NAMES}
outputs, report = wm.triwild(
    {"input": NAMES, "input_names": NAMES, "filter": "input", "stop_energy": 10,
     "num_threads": 4},
    curves,
)
mesh = outputs["mesh"]
triangles = mesh["cells"]["triangle"]
print(len(mesh["V"]), "vertices,", len(triangles["connectivity"]), "triangles,",
      f"max energy {report['max_energy']:.2f}")
# The tracked curves, one column per input: 1 where the edge lies on that curve.
tags = mesh["cells"]["edge"]["attributes"]["tags"]
for label, count in zip(tags["labels"], np.asarray(tags["values"]).sum(axis=0)):
    print(f"  {label}: {count} edges")

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

wm.triwild({
    "input": [str(DATA / f"triwild_{name}.obj") for name in NAMES],
    "input_names": NAMES,
    "output": "shapes",
    "filter": "input",
    "stop_energy": 10,
    "num_threads": 4,
    "report": "shapes_report.json",
})
const std::vector<std::string> names = {"blob1", "blob2", "circle", "ellipse", "rectangle"};
wmtk::MeshMap curves;
for (const std::string& name : names) {
    curves[name] = wmtk::io::read_mesh(data / ("triwild_" + name + ".obj"));
}
auto [outputs, report] = wmtk::components::triwild::triwild(
    {{"input", names},
     {"input_names", names},
     {"filter", "input"},
     {"stop_energy", 10},
     {"num_threads", 4}},
    curves);
const wmtk::MeshData& mesh = outputs.at("mesh");
const wmtk::CellData& triangles = mesh.cell(wmtk::CellType::Triangle);
std::cout << mesh.V.rows() << " vertices, " << triangles.connectivity.rows()
          << " triangles, max energy " << report["max_energy"].get<double>() << "\n";
// The tracked curves, one column per input: 1 where the edge lies on that curve.
const wmtk::MeshAttribute& tags = mesh.cell(wmtk::CellType::Edge).attributes.at("tags");
const wmtk::DataMatrix<int64_t> on = tags.integers();
for (size_t j = 0; j < tags.labels.size(); ++j) {
    std::cout << "  " << tags.labels[j] << ": " << on.col(j).sum() << " edges\n";
}
wmtk::io::write_mesh("shapes.msh", mesh);

Link wmtk::triwild.

The 719 input vertices (716 segments) are simplified to 297, the arrangement inserts them into a triangulation of the bounding box, and the optimization ends with 265 to 289 vertices and 407 to 455 triangles over seven runs (see threads), the largest energy between 6.1 and 8.8 for a target of 10. A run takes a fraction of a second. The Python and C++ examples then print, for each name, the number of tracked edges on that curve (one run with 4 threads):

blob1: 71 edges
blob2: 62 edges
circle: 38 edges
ellipse: 19 edges
rectangle: 24 edges

The curves are the mesh's edge tags; the triangles carry none but ambient, as triwild writes no regions (until 2026-11 each name also labelled the triangles inside its curve).

The input on the left, the result on the right: drag to rotate, scroll to zoom. Every example is in the gallery.

Key settings

The numbers below come from the sweep section of the example, which changes one option at a time against the first run (with num_threads 0, so that they repeat exactly):

# One option at a time against the first run (filter input, stop_energy 10); eps_rel with the
# simplification at half of it, as at the default.
base = {"filter": "input", "stop_energy": 10}
for change in [{}, {"stop_energy": 100}, {"stop_energy": 5}, {"stop_energy": 3},
               {"eps_rel": 0.0002, "eps_simplify_rel": 0.0001},
               {"eps_rel": 0.005, "eps_simplify_rel": 0.0025},
               {"length_rel": 0.02}, {"length_rel": 0.01},
               {"coarsen_pass": True}]:
    outputs, report = triangulate({**base, **change, "DEBUG_hausdorff": True})
    print(f"{change}: {report['#t']} triangles, max energy {report['max_energy']:.2f}, "
          f"avg {report['avg_energy']:.2f}, iterations {report['#iterations']}, "
          f"curves within {report['hausdorff']:.3f} of the input (eps {report['eps']:.3f})")

The inputs: input, input_names, output

input is a list of OBJ files of polylines (v and l lines), up to 64, and of point files (v lines alone). Each curve file is one input: its curves are kept apart from the others' in the output tags, and each tracked edge is held to the envelope of the inputs it lies on. Vertices that coincide exactly are merged when a file is read; a vertex of a curve file that no segment uses is kept as a feature point, as every vertex of a point file is. input_names gives the inputs names, in the same order: they label the tag columns of the output (tag_0, tag_1, ... without them) and each input's winding-number field on the triangles, wn_<name> in the VTU file and the memory outputs (wn_0, wn_1, ... in the .msh and without names). output is the file name without extension.

In memory, input names entries of the meshes dictionary, and the input names can be the same strings.

A triangle mesh as the input, alone, takes the tagged route: on files a .msh with triangles, in memory a mesh with a triangle block. triwild continues from it as it is -- no simplification, no arrangement, the triangles kept -- holding its edge block's tags as tracked curves, named as the mesh names them, and its point block as input points. No regions: a mesh whose triangles carry a tag other than ambient is refused, as it is simwild's to remesh; triwild writes none, so its own output goes back in as it is. The mesh must fill its bounding box, as an output with filter: "none" does: a filtered mesh, whose boundary is its tracked edges, is refused, and its curves go in as inputs instead. With envelope, the reference an earlier run returned, it holds the curves to that rather than to the mesh received, so a chain stays within one eps of the first input. filter_inputs names the inputs that bound the domain a filter keeps.

The envelope: eps_rel

eps_rel (default 0.001) is the distance the output's curves may be from the input, relative to the bounding box diagonal. The input is simplified within eps_simplify_rel of the diagonal (default 0.0005, half the default \(\varepsilon\)), so detail smaller than \(\varepsilon\) may disappear, and the optimization keeps every tracked edge within \(\varepsilon\) of the input. A thinner envelope keeps more of the input's vertices and constrains the optimization more:

eps_rel \(\varepsilon\) triangles largest distance to the input iterations
0.0002 0.025 977 0.018 10
0.001 (default) 0.127 428 0.090 2
0.005 0.637 297 0.447 1

These runs simplified within half of each \(\varepsilon\), eps_simplify_rel = eps_rel / 2. eps_simplify_rel does not follow eps_rel, and an eps_rel at or below it is refused under the default envelope_reference: lower both together.

The distance is the containment that DEBUG_hausdorff measures: the largest distance from a point of the output's curves to the input. It stays below \(\varepsilon\) in every run.

The edge length: length_rel

length_rel (default 0.05) is the target edge length, relative to the bounding box diagonal. Edges longer than 4/3 of it are split, and edges shorter than 4/5 of it are collapsed when the envelope and the quality allow. Away from the curves it sets the size of the triangles; along them, the curves' own detail and the envelope do:

length_rel triangles max energy
0.05 (default) 428 6.85
0.02 1,549 7.18
0.01 6,185 5.00

length and eps give the edge length and \(\varepsilon\) in the input's units instead, as simwild's do; a positive value wins over the relative one.

Edge length that varies: sizing_mesh

Every vertex carries a sizing, the factor of the target length that the stuck refinement lowers where the quality is stuck. sizing_mesh sets it from a target length that varies over the plane: a triangle mesh whose vertices carry the length in a field named target_length, interpolated linearly inside its triangles. On the memory route it names a mesh of the call; on the file route it is a mesh file. It sets the sizing at the start and caps it after every pass, so the vertices a pass makes follow it and the refinement is kept; outside its triangles the global length applies. A unit square whose field grows from 0.02 on its left side to 0.12 on its right, with length 0.12, ends with tracked edges of 0.026 on average on the left side and 0.100 on the right.

The field is a largest edge length: with it, limit_collapse_length is on unless set to false, and the optimization goes on past stop_energy while more than 1% of the edges are longer than 4/3 of their target. The sizing mesh workflow builds one in Python and on files, and shows it in TriWild, TetWild and isotropic remeshing.

A bound on the edge length: limit_collapse_length

A collapse is judged by the edge it removes, shorter than 4/5 of the target, and not by those it leaves: along a curve a short edge merges into its neighbour, up to 0.8 + 4/3 of the target, and the optimization ends on collapses, so no split cuts it again. limit_collapse_length refuses a collapse that leaves an edge longer than 4/3 of the target, the length above which the split cuts one. On a unit square sampled with 200 points a side, length 0.06 and stop_energy 3.6:

limit_collapse_length triangles longest tracked edge smallest angle
off (default) 465 2.16 \(l\) 21.0°
on 809 1.35 \(l\) 30.6°

Smoothing can still stretch an edge a little past 4/3, so to keep the edges under a bound, ask for about 3/4 of it, for a denser mesh. With a sizing_mesh, the bounded coarsening pass (coarsen_unbounded off) stops at 0.8 of the field's length rather than of the global one.

The quality target: stop_energy

The shape of a triangle is measured by its AMIPS energy: 2 for an equilateral triangle, growing without bound as the triangle flattens (see Quality). The optimization stops when the largest energy is below stop_energy, or after max_iterations (80). The default, 100, is a loose target in 2D, 50 times the minimum; the example asks for 10:

stop_energy triangles max energy average iterations
100 (default) 423 21.47 3.74 1
10 428 6.85 2.91 2
5 498 4.36 2.58 8
3 680 2.95 2.26 6

The average barely moves until the target gets close to the minimum: what the target buys is the worst triangles. When the largest energy stops improving, the triangles above the target are refined; with a target close to 2 that is nearly all of them, so set stuck_refine_num_worst to a positive number there.

The outside: filter

The triangulation covers a box around the input. filter decides what is kept (see Embedding for how each works):

filter Keeps On the five shapes
none (default) everything 924 triangles
flood all but the region the curves separate from the box's border 457 triangles
input the triangles inside at least one input, by each input's winding number 428 triangles
tracked the triangles inside the tracked curves, oriented as the input was 79 triangles

flood keeps 29 triangles more than input: they lie in pockets enclosed by the union of the curves but inside none of them. tracked counts all the curves together, with their orientation: four of the shapes run clockwise and the rectangle counterclockwise, so the winding number is −1 inside a clockwise shape and 0 where one overlaps the rectangle, and only the part of the rectangle that no other curve covers is kept. input orients each input on its own. Use it for several inputs. All three need closed curves (see the pitfalls).

Feature points

A point file in input (v lines alone) has its vertices inserted as vertices of the triangulation. Until 2026-11 such files came in a list of their own, input_points. The endpoints of open polylines are kept the same way. Each is anchored: some vertex stays within its radius of it -- feature_envelope_ratio \(\cdot\,\varepsilon\) for the points, order2_envelope_ratio \(\cdot\,\varepsilon\) for the endpoints, both \(\varepsilon\) by default -- and a collapse that would remove it is refused. Junctions, where three or more polylines meet, are not anchored. Here a closed curve and twelve points, nine inside it and three outside:

# A closed curve and twelve points to keep as vertices: nine inside, three outside.
star = {"curve": wm.read_mesh(str(DATA / "triwild_free_points_curve.obj")),
        "points": wm.read_mesh(str(DATA / "triwild_free_points_points.obj"))}
outputs, report = triangulate(
    {"stop_energy": 10, "DEBUG_feature_retention": True}, star, ["curve", "points"])
V = outputs["mesh"]["V"]
# How far each input point is from the nearest vertex of the output.
worst = max(np.linalg.norm(V - p, axis=1).min() for p in star["points"]["V"])
print(f"{report['features_retained']} of {report['features_total']} points kept, the worst "
      f"{worst:.3f} from a vertex (eps {report['eps']:.3f})")

All 12 points keep a vertex within \(\varepsilon\), the farthest at 0. Without the anchors (until 2026-10, preserve_feature_points false turned them off), the collapses took the points' vertices like any other: 0 of 12 kept, the farthest 1.50 (44 \(\varepsilon\)) from a vertex. The points outside the curve's bounding box grow it, and with it \(\varepsilon\) and the edge length, which are relative to its diagonal. A point in a region the filter discards leaves the mesh, and its point block, with that region.

Topology: preserve_topology

By default the simplification and the optimization may change the curves' topology: close a gap narrower than \(\varepsilon\), merge two junctions, remove a loop smaller than \(\varepsilon\). DEBUG_euler logs the Euler characteristic of each connected curve at each stage, which shows such changes. preserve_topology forbids these: only exactly coincident vertices are merged, the simplification does not merge junctions or endpoints, and the operations check the link condition. The simplification before the insertion may still change the topology: it can move a curve across another, or across itself, within its envelope, which nothing checks. The insertion keeps the topology of the curves it receives where they do not cross, and the optimization keeps that of the inserted curves. Set it when the curves' connectivity matters, after making sure the input has no gaps far below \(\varepsilon\) (see the pitfalls).

Threads and reproducibility

num_threads 0 runs sequentially and gives the same mesh every time (428 triangles here). With threads, the order of the operations depends on the schedule, and the result changes slightly from run to run: seven runs of the first run gave 407 to 455 triangles. On inputs of this size a run takes a fraction of a second either way.

Outputs

On files, output names:

  • shapes.msh: the triangles, with the vertices in 3D (z = 0). Each triangle has its quality (its energy), one wn_<i> per input (that input's winding number at its centroid) and tags with a single column, ambient: triwild writes no regions, which are simwild's (until 2026-11 one column per input, 1 where the triangle is inside that input). The tracked curves are its edges, with tags, one column per input labelled by input_names: each edge under every input it lies on, oriented as its input. simwild reads them back as edge tags. The input points are its point block, each vertex under the inputs with a point there.
  • shapes.vtu: the same triangles for ParaView, with quality, the winding numbers (wn_<name> with input_names), and flood_fill (the regions the curves separate) when the flood fill ran (compute_flood_fill).
  • shapes_surf.vtu: the tracked curves, the edges of the mesh that lie on the input.
  • With report, a JSON file with the vertex and triangle counts (#v, #t), max_energy, avg_energy, #iterations, eps, the coarsening statistics, and, with DEBUG_hausdorff, the distances hausdorff (output to input, the containment) and coverage (input to output); with DEBUG_feature_retention, features_retained and features_total. A value of -1 means not measured.

The winding-number fields let a filter none run be split afterwards, as tetwild's do: a triangle is inside an input where its wn_<i> is above 1/2. skip_winding_number leaves them out when no filter needs them.

In memory, the outputs are mesh (as in the .msh, the winding numbers named as in the VTU file), surface (the tracked curves, as edges), features (with feature points) and envelope (the input curves the envelope is built around). The report holds the same keys as the file.

history_output records every change to the tracked curves, from the input files to the output, and tracking maps points between the two from it. Recording does not change the output.

Pitfalls

  • Open curves have no inside. The filters decide what is inside from the curves, and an open polyline does not bound anything. On triwild_polylines.obj, a drawing of 46 polylines with 94 loose ends:

    # Open curves: 46 polylines with 94 loose ends. The filters do not agree on what is inside.
    drawing = {"drawing": wm.read_mesh(str(DATA / "triwild_polylines.obj"))}
    for filter in ["none", "flood", "input", "tracked"]:
        outputs, report = triangulate({"filter": filter}, drawing, ["drawing"])
        V, F = outputs["mesh"]["V"], outputs["mesh"]["cells"]["triangle"]["connectivity"]
        e1, e2 = V[F[:, 1]] - V[F[:, 0]], V[F[:, 2]] - V[F[:, 0]]
        area = 0.5 * np.abs(e1[:, 0] * e2[:, 1] - e1[:, 1] * e2[:, 0]).sum()
        print(f"filter {filter}: {len(F)} triangles, area {area:.0f}")
    

    flood keeps the inside of the drawing's frame (1.35 million square units of the box's 2.76), while input and tracked keep 1.60 million, a band of triangles above the frame included. On open curves, use filter none and select the triangles from the output yourself. - Several inputs with filter tracked. It sums all curves with their orientation; inputs that run the other way cancel (79 triangles of 428 above). Use input. - preserve_topology and tiny gaps. The rectangle of the first run is two polylines whose corners miss each other by \(3 \cdot 10^{-15}\). By default a collapse closes the gap during the optimization. With preserve_topology it stays, and the optimization cannot get rid of the near-degenerate triangles there: on the rectangle alone, the largest energy is \(7.8 \cdot 10^{8}\) after 30 iterations, and on the five shapes it does not converge in 80. With the coordinates rounded to 9 digits, the same run converges in one iteration. Weld such vertices in the input before asking for the topology to be kept: under preserve_topology, remove_duplicate_eps is ignored. - A misspelled option is ignored. wmtk_app and the Python bindings log a warning (triwild has no option ...) and run with the defaults. Editors catch it beforehand with the JSON Schemas.

See also