|
|
|
This document describes what Triangle does internally, and what kind of per- and post-processing is done within BASEmesh.
|
|
|
|
|
|
|
|
Note that these are simplifications to illustrate its operation for BASEmesh users. For accurate information on how Triangle is implemented, please refer to the [Triangle website](https://www.cs.cmu.edu/afs/cs/project/quake/public/www/triangle.html) or help command.
|
|
|
|
|
|
|
|
### Mesh Representation
|
|
|
|
|
|
|
|
Triangle operates on planar linear straight-line graphs (PSLGs), which are comparable to the quality mesh in the BASEmesh workflow, albeit with additional restrictions on the mesh topology.
|
|
|
|
|
|
|
|
Point elevation data, if provided as part of the elevation meshing workflow, is stored in a separate dataset that is not used during triangulation but instead interpolated in a separate step.
|
|
|
|
|
|
|
|
### Input Data
|
|
|
|
|
|
|
|
Triangle internally converts any input data prior to its triangulation. As part of this, it will perform some minor geometry fixes:
|
|
|
|
|
|
|
|
- Exact duplicate vertices are merged
|
|
|
|
- If a segment describes a connection between two vertices that is already established by another segment (regardless of vertex order), it is ignored
|
|
|
|
- Any zero-length segments are ignored
|
|
|
|
|
|
|
|
These fixes are always applied by Triangle, even when input cleanup is disabled in BASEmesh. They produce warnings for every occurrence in the Triangle output, but are safe and do not threaten triangulation success.
|
|
|
|
|
|
|
|
This leaves the following geometry errors that cannot be fixed by Triangle and lead to fatal errors:
|
|
|
|
|
|
|
|
- Vertices that are very close but were not considered exact duplicates are still considered separate points. When combined with mesh quality constraints such as minimum included angle, this causes "spider webbing" in the resulting triangulation and - if this inflates the mesh size enough - may result in a `MemoryError`.
|
|
|
|
|
|
|
|
- Vertices bisecting a segment produce a degenerate element during triangulation. This is the most common way `Topological inconsistency after splitting segment` errors occur.
|
|
|
|
|
|
|
|
### Mesh Regions
|
|
|
|
|
|
|
|
Mesh regions are areas of the triangulation that are surrounded by input segments (aka. break lines).
|
|
|
|
|
|
|
|
Any elements generated within a region will gain the properties of the region marker that was passed as part of the input geometry. If multiple region markers are specified, they may partially overwrite each other.
|
|
|
|
|
|
|
|
### Triangulation
|
|
|
|
|
|
|
|
After loading the input data, Triangle will start with a basic triangulation of all loaded vertices and segments. It starts out at the segments and attempts to find a vertex within the same region that it can connect to form a triangle. This prioritizes isosceles triangles.
|
|
|
|
|
|
|
|
This is deterministic, the same input will produce the same triangulation.
|
|
|
|
|
|
|
|
For elevation meshing in BASEmesh, this is the end of the process. The resulting triangulation is converted into a TIN via the previously stored vertex elevation data, and the elevation mesh is generated.
|
|
|
|
|
|
|
|
### Mesh Refinement
|
|
|
|
|
|
|
|
If mesh quality constraints such as minimum included angle or maximum element area have been applied, Triangle will check any generated elements to see if any constraints are violated. If they are, one or more triangles are removed, and extra points are inserted to create smaller, more uniform triangles.
|
|
|
|
|
|
|
|
As part of this step, Triangle employs some randomness. That means that the position of an inserted node is not always derived from surrounding geometry but instead randomly chosen and then checked for compatibility with the constraints.
|
|
|
|
|
|
|
|
This means that multiple quality meshes generated in BASEmesh may differ despite being generated from the exact same input geometry, with the same command-line flags.
|
|
|
|
|
|
|
|
### Mesh holes and concavities
|
|
|
|
|
|
|
|
After mesh refinement is complete, Triangle re-checks the hole marker of its containing region. If the region has been flagged as a hole, the element is deleted.
|
|
|
|
|
|
|
|
This also includes the mesh boundary as the triangulation generated a full convex hull. Deletion of the convex hull can be disabled in BASEmesh using either the *'Keep convex hull'* option in the quality mesh or the `c` flag, though this risks invalid output meshes and errors in Triangle if multiple boundary vertices are collinear, since the resulting boundary elements have zero area.
|
|
|
|
|
|
|
|
Also note that when Triangle deletes elements, it does *not* delete the corresponding vertices by default, leading to disjoint vertices that are not connected to any elements. Manual deletion of these vertices can be specified using the `j` flag in Triangle.
|
|
|
|
|
|
|
|
## Troubleshooting
|
|
|
|
|
|
|
|
### Triangle output is missing elements or empty
|
|
|
|
|
|
|
|
Make sure your outermost break lines/segments are a closed loop without gaps. If they are not closed, Triangle may delete the inner regions while shrinking the outer segments.
|
|
|
|
|
|
|
|
Similarly, gaps in the segments bounding an inner hole region of the mesh can cause the hole to "spill out" into the surrounding mesh, potentially also consuming some or all of the elements generated.
|
|
|
|
|
|
|
|
### Triangle exits after printing `MemoryError`
|
|
|
|
|
|
|
|
The most common cause of this is Triangle producing more elements than fit inside its process memory.
|
|
|
|
|
|
|
|
This should generally be interpreted as a sign that the mesh quality settings are too aggressive, or that there are distinct vertices in the input dataset that produce a very large number of elements.
|
|
|
|
|
|
|
|
On the 32 bit version of Triangle included in the Windows version of the BASEmesh plugin, this memory limit corresponds to upwards of 30'000'000 elements.
|
|
|
|
|
|
|
|
### Triangle exits after printing `Topological inconsistency...`
|
|
|
|
|
|
|
|
Topological inconsistencies include things like zero area triangles, or points that coincide with other points after a segment was split to maintain mesh quality.
|
|
|
|
|
|
|
|
A first troubleshooting step should be to dramatically reduce or completely disable mesh quality settings. If the error persists, it is likely related to bad input data. If the issue goes away, a reduction in mesh quality might be required.
|
|
|
|
|
|
|
|
### Other Triangle crashes
|
|
|
|
|
|
|
|
Finally, there are numerous errors related to Triangle running out of precision in its coordinate resolution.
|
|
|
|
|
|
|
|
This is generally another failure mode of overly restrictive mesh quality settings causing newly inserted points to coincide with existing ones. |
