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"
}
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:
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):
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 itsquality(its energy), onewn_<i>per input (that input's winding number at its centroid) andtagswith 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, withtags, one column per input labelled byinput_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, withquality, the winding numbers (wn_<name>withinput_names), andflood_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, withDEBUG_hausdorff, the distanceshausdorff(output to input, the containment) andcoverage(input to output); withDEBUG_feature_retention,features_retainedandfeatures_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}")floodkeeps the inside of the drawing's frame (1.35 million square units of the box's 2.76), whileinputandtrackedkeep 1.60 million, a band of triangles above the frame included. On open curves, usefilternoneand select the triangles from the output yourself. - Several inputs withfiltertracked. It sums all curves with their orientation; inputs that run the other way cancel (79 triangles of 428 above). Useinput. -preserve_topologyand 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. Withpreserve_topologyit 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: underpreserve_topology,remove_duplicate_epsis ignored. - A misspelled option is ignored.wmtk_appand 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¶
- Reference: every option of
triwild - Embedding: the simplification, the arrangement and the filters; Quality: the energy and the optimization loop.
- TetWild, the same in 3D; SimWild for regions in a mesh; tracking to map points through the history.
- Hu et al. 2019, TriWild: Robust Triangulation with Curve Constraints