Skip to content

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, at eps_simplify_rel \(\cdot\,\text{diag}\), or eps_simplify if given (half of \(\varepsilon\) at the default eps_rel). The link condition applies only with preserve_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 under preserve_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