Embedding¶
tetwild, triwild and simwild do not require a clean input. A tetwild input is a triangle soup that may intersect itself, have holes, duplicates and non-manifold edges; a triwild input is a set of polylines that may cross and overlap. Before the optimization, the input is inserted exactly into a background mesh that covers its bounding box: every input triangle (or segment) ends up as a union of faces (or edges) of the mesh, which are tracked from then on. This page describes the steps from the input files to that mesh, and the filter that removes the outside at the end.
1. Read and weld¶
The input files are read and concatenated. Vertices closer than
remove_duplicate_eps (a fraction of the bounding
box diagonal) are merged; 0 merges only vertices that coincide exactly. The bounding box of the
input sets the scale: \(\varepsilon\) and the target edge length are relative to its diagonal (see
Robust geometry).
2. Simplify the input¶
An input often has far more detail than the target edge length: thousands of tiny triangles on a flat region, tessellated curves. Inserting all of it would give the optimizer a mesh much finer than asked for, which it would first have to coarsen. So the input is simplified first, inside an envelope of its own:
- In 3D, tetwild simplifies the input surface, a
TriMesh, by shortest edge collapse, with the envelope as invariant, ateps_simplify_rel\(\cdot\,\text{diag}\), oreps_simplifyif given (half of \(\varepsilon\) at the defaulteps_rel). The link condition applies only withpreserve_topology, so by default the simplification may change the topology of the surface. With it, the simplification may still fold the surface through itself, which the link condition (connectivity only) does not see and the envelope admits, and the insertion then cuts the crossing triangles; tetwild checks the simplified surface for this and warns. The open boundary may move within a tube around the input's boundary (simplify_boundary_envelope). simwild does the same, except underpreserve_topology, where it simplifies after the insertion instead. - In 2D, triwild collapses the shortest segments of the curves while they stay inside the
simplification envelope. simwild does the same, except under
preserve_topology, where it simplifies after the insertion instead, as in 3D.
The tighter envelope leaves the optimizer room: the simplified surface is within half of
\(\varepsilon\) of the input (by default), and the optimizer, which is held to the full
\(\varepsilon\) around the original input, starts with room to move.
With simplify false, the input is inserted as it is.
3. The background mesh and the arrangement¶
In 3D (tetwild, and simwild on surfaces), the background is a Delaunay tetrahedralization of
the simplified input's vertices, the eight corners of the input's bounding box grown by a
fifteenth of its diagonal, and a regular grid of points spaced at most a twentieth of the diagonal
apart, without the grid points closer to the input than half of that
(DelaunayBoxMesh.hpp).
The input triangles are then inserted with VolumeRemesher's embed_tri_in_poly_mesh, which
computes the exact arrangement of the triangles and the background tetrahedra, and returns
tetrahedra that conform to every input triangle
(EmbedTriangles.hpp).
Intersections between input triangles are resolved there, exactly. The remesher's tetrahedra are
used directly, with no extra vertices at cell centres. The vertices have rational coordinates;
how they become doubles is described in
Robust geometry. tetwild's feature curves and
points (its curve and point inputs, input) are inserted in the
same arrangement, so each feature edge is tiled by tetrahedron edges and each feature point is a
vertex.
In 2D (triwild, and simwild on curves), VolumeRemesher's embed_seg_in_tri_mesh computes the
exact arrangement of the segments: a triangulation of the input's bounding box, seeded with a grid
of background points, in which every input segment is a chain of triangle edges and every crossing
of two segments is a vertex
(EmbedSegments.hpp).
The coordinates of a crossing are rational and are kept as such: two distinct crossings can round
to the same doubles.
4. The tracked surface¶
The faces of the arrangement that lie on an input triangle form the tracked surface (in 2D, the
edges on an input segment form the tracked curves). Which faces they are comes from the
arrangement's provenance, the record of which output faces tile each input triangle, not from a
geometric test after the fact. Each face (or edge) carries a few tags
(SurfaceTagAttributes.h):
/// Is this simplex part of the tracked surface.
bool m_is_surface_fs = false;
/// Which bbox side this simplex is on; -1 for none.
int8_t m_is_bbox_fs = -1;
and an orientation (the signed number of input sheets lying on it) and an input set (which inputs it lies on). The operations carry these through every split, collapse and swap. The optimization keeps the tracked surface inside the envelope and the faces on the bounding box on it, so the box does not collapse.
5. The outside: winding numbers and filter¶
The mesh covers the whole bounding box. After the optimization, the
filter option of tetwild and triwild decides what to keep:
filter |
Keeps |
|---|---|
none (default) |
Everything. |
input |
The cells inside the input: the winding number of the input, evaluated at each cell's centroid, is above 1/2. |
tracked |
The same with the winding number of the tracked surface, oriented as the input was. Coincident surfaces add up and opposite ones cancel. Each component must be closed. |
flood |
The tracked surface divides the mesh into parts, and the part that touches the bounding box most is removed. The input must be closed; otherwise the whole mesh is one part and nothing is left. |
The winding number is the generalized winding number, so it is defined for open and
self-intersecting inputs too: 1 inside a closed, consistently oriented input, 0 outside, and
fractional near holes
(WindingNumber.hpp).
input judges each cell by the input rather than by the surface the mesh conforms to, so it can
misclassify cells along the surface and leave it wrinkled; tracked judges by the tracked surface
itself. The winding numbers can also be written to the output as fields (tetwild and triwild write
one per input, wn_<name>): with skip_winding_number
false. By default they are computed only when a filter needs them.
triwild writes the per-input winding numbers as fields of the triangles, as tetwild does on its tets, and not as regions: its triangles carry no region tags. simwild has no filter: it keeps the whole box and tags every cell with the inputs that contain it (see Regions).
With history_output, the whole sequence above is
recorded, from the files as read to the output: the weld, the simplification, the insertion, the
optimization and the filter (see Histories).
See also¶
- The tetwild and triwild tutorials.
- Robust geometry for rational coordinates and the envelope.
- VolumeRemesher, the exact arrangement both dimensions use.
- Hu et al. 2018, Tetrahedral Meshing in the Wild, and Hu et al. 2019, TriWild.