Constrained Delaunay triangulation kernel with quality and terrain refinement and optional coarsening (see the file comment for the algorithms). More...
#include <meshkit/cdt.hpp>
Classes | |
| struct | QualityOptions |
| Options for refineQuality(). More... | |
| struct | QualityReport |
| Counters and diagnostics of one refineQuality() call. More... | |
| struct | Triangle |
| One triangle slot of triangles(). More... | |
Public Types | |
| enum | Origin : std::uint32_t { Domain = 1 , Hole = 2 , Line = 4 , Patch = 8 , Node = 16 , Breakline = 32 , Region = 64 , Lattice = 128 , Size = 256 , Angle = 512 , Terrain = 1024 , SegmentSplit = 2048 } |
| Diagnostic vertex-provenance bits stored by enableProvenance()/addVertexOrigin(). More... | |
| using | Point = typename Storage::Point |
| 2D point type of the storage (meshkit::Point2 or QPointF), in XY plane units. | |
| using | Box = typename Storage::Box |
| Axis-aligned XY rectangle type of the storage; passed to footprint callbacks. | |
| using | String = typename Storage::String |
| Text type of errorMsg() (std::string or QString). | |
| using | PointInput = typename Storage::PointInput |
| Point container accepted by build() (std::vector<Point2> or QVector<QPointF>). | |
| template<class T> | |
| using | Vector = typename Storage::template Vector<T> |
| Dynamic array type of the storage, used for owned arrays and read-out buffers. | |
| template<class K, class V> | |
| using | Hash = typename Storage::template Hash<K, V> |
| Hash map type of the storage, used for internal segment bookkeeping. | |
| template<class K, class V> | |
| using | MultiHash = typename Storage::template MultiHash<K, V> |
| Hash multimap type of the storage, used for overlapping-segment bookkeeping. | |
| template<class K> | |
| using | Set = typename Storage::template Set<K> |
| Hash set type of the storage (QualityOptions::protectedVertices, fixed subsegments). | |
Public Member Functions | |
| bool | build (const PointInput &points, Vector< int > *vertexOfPoint=nullptr, const std::function< bool()> &cancelled={}, const std::function< void(std::uint64_t)> &progress={}) |
| Reset and incrementally triangulate distinct finite points inside a constructed super triangle. | |
| bool | insertConstraint (int a, int b) |
| Recover/mark a straight constraint, recursively splitting at exactly collinear existing vertices. | |
| int | insertPoint (const Point &p) |
| Insert one finite point in a live triangle, splitting a triangle/edge and restoring Delaunay edges. | |
| bool | removeVertex (int v) |
| Transactionally remove a free post-build interior vertex and retriangulate its local cavity. | |
| bool | isVertexActive (int v) const |
| Test whether an in-range vertex has a nonnegative incident-triangle hint. | |
| void | removeExterior () |
| Mark super-touching faces and every unconstrained reachable neighbor dead. | |
| void | removeSuperTriangles () |
| Mark only live faces touching one of the three super vertices dead. | |
| int | removeRegionLeftOf (int a, int b) |
| Delete live constraint-bounded faces topologically seeded to a directed edge's left. | |
| int | inputVertexCount () const |
| Return the unique-input count recorded as the super-vertex base at successful build. | |
| int | removeRegionAt (const Point &p) |
| Mark the live constraint-bounded component containing a finite seed point dead. | |
| QualityReport | refineQuality (const QualityOptions &opt) |
| Mutate live constrained triangulation by bounded size/angle/terrain refinement and optional coarsening. | |
| void | setFixedConstraint (int a, int b) |
| Mark every recovered subedge of a requested constraint chain unsplittable for refinement. | |
| bool | smallAngleExempt (int t) const |
| Test the shortest edge of a triangle for equal-radius input-corner shell exemption. | |
| bool | touchesFixed (int t) const |
| Test whether any triangle vertex participates in a marked fixed constrained edge. | |
| void | enableProvenance () |
| Enable/reset optional origin bits for all currently stored vertices. | |
| void | addVertexOrigin (int v, std::uint32_t origin) |
| OR diagnostic provenance flags into an enabled in-range origin slot. | |
| const Vector< std::uint32_t > & | vertexOrigins () const |
| Borrow diagnostic origin storage from this triangulation. | |
| const Vector< Point > & | vertices () const |
| Borrow all stored XY positions including super, inactive and newly inserted vertices. | |
| const Vector< Triangle > & | triangles () const |
| Borrow all triangle slots with alive flags, adjacency and opposite-edge constraints. | |
| const Vector< double > & | terrainElevations () const |
| Borrow the most recent refinement's cached per-vertex elevation samples. | |
| int | liveTriangleCount () const |
| Count slots whose alive flag is true, including super faces if still alive. | |
| int | locate (const Point &p) const |
| Locate a finite point and require its found triangle to be alive. | |
| bool | isConstrained (int a, int b) const |
| Check whether a direct edge between two stored vertices is marked constrained. | |
| Vector< int > | constrainedChain (int a, int b) const |
| Follow direct, origin-associated or collinear constrained edges from one endpoint to another. | |
| bool | isSuperVertex (int v) const |
| Test whether an integer falls in the recorded three-super-vertex interval. | |
| String | errorMsg () const |
| Copy the last explicitly recorded build/constraint diagnostic. | |
Static Public Member Functions | |
| static double | orientExact (const Point &a, const Point &b, const Point &c) |
| Return adaptive-exact orientation sign after thread-safe one-time predicate initialization. | |
Constrained Delaunay triangulation kernel with quality and terrain refinement and optional coarsening (see the file comment for the algorithms).
| Storage | Container and geometry vocabulary: detail::StandardStorage (standard C++ containers, std::string) for ConstrainedDelaunay, or the Qt storage (QVector, QPointF, QString) used by the Qt mesh library. |
Typical use: build() the point set, insertConstraint() each segment, remove the exterior, holes and other regions, optionally refineQuality(), then read vertices() and the alive entries of triangles(). Vertex ids index vertices(): unique input points first, then the three super-triangle vertices (inputVertexCount() .. inputVertexCount() + 2), then vertices inserted later. All coordinates share one Cartesian XY frame; the kernel performs no unit conversion. An instance has no internal synchronization: mutating calls need exclusive access and const calls must not race a mutation. The exact-predicate tables are initialised once per process under std::call_once.
| using meshkit::BasicConstrainedDelaunay< Storage >::Box = typename Storage::Box |
Axis-aligned XY rectangle type of the storage; passed to footprint callbacks.
| using meshkit::BasicConstrainedDelaunay< Storage >::Hash = typename Storage::template Hash<K, V> |
Hash map type of the storage, used for internal segment bookkeeping.
| using meshkit::BasicConstrainedDelaunay< Storage >::MultiHash = typename Storage::template MultiHash<K, V> |
Hash multimap type of the storage, used for overlapping-segment bookkeeping.
| using meshkit::BasicConstrainedDelaunay< Storage >::Point = typename Storage::Point |
2D point type of the storage (meshkit::Point2 or QPointF), in XY plane units.
| using meshkit::BasicConstrainedDelaunay< Storage >::PointInput = typename Storage::PointInput |
| using meshkit::BasicConstrainedDelaunay< Storage >::Set = typename Storage::template Set<K> |
Hash set type of the storage (QualityOptions::protectedVertices, fixed subsegments).
| using meshkit::BasicConstrainedDelaunay< Storage >::String = typename Storage::String |
Text type of errorMsg() (std::string or QString).
| using meshkit::BasicConstrainedDelaunay< Storage >::Vector = typename Storage::template Vector<T> |
Dynamic array type of the storage, used for owned arrays and read-out buffers.
| enum meshkit::BasicConstrainedDelaunay::Origin : std::uint32_t |
Diagnostic vertex-provenance bits stored by enableProvenance()/addVertexOrigin().
They never affect the triangulation. Domain to Lattice are caller conventions (as used by the mesh generator); the kernel itself sets Size, Angle and Terrain on refinement insertions and SegmentSplit on subsegment splits.
| Enumerator | |
|---|---|
| Domain | Vertex of a domain-boundary constraint (caller-set). |
| Hole | Vertex of a hole-boundary constraint (caller-set). |
| Line | Vertex of another constraint line (caller-set). |
| Patch | Vertex of a fixed patch constraint (caller-set). |
| Node | Free input node (caller-set). |
| Breakline | Vertex of a terrain breakline (caller-set). |
| Region | Vertex of a region boundary (caller-set). |
| Lattice | Seeded lattice point inserted by the caller. |
| Size | refineQuality() insertion for a size target. |
| Angle | refineQuality() insertion for the minimum-angle bound. |
| Terrain | refineQuality() insertion for terrain error. |
| SegmentSplit | Subsegment split; also inherits endpoints' Domain..Region bits. |
|
inline |
OR diagnostic provenance flags into an enabled in-range origin slot.
| [in] | v | Arbitrary vertex-origin index, bounds checked; no-op if origins disabled/out of range. |
| [in] | origin | Bit mask to accumulate, no enum-mask validation; overlapping roles allowed. No geometry mutation or allocation, no retained arguments; caller excludes concurrent origin updates. |
| bool meshkit::BasicConstrainedDelaunay< Storage >::build | ( | const PointInput & | points, |
| Vector< int > * | vertexOfPoint = nullptr, | ||
| const std::function< bool()> & | cancelled = {}, | ||
| const std::function< void(std::uint64_t)> & | progress = {} ) |
Reset and incrementally triangulate distinct finite points inside a constructed super triangle.
| [in] | points | Borrowed finite Cartesian coordinates, unchanged; coordinate extents/super-triangle expansion and int counts must remain representable. Exact numeric coordinate duplicates coalesce, including +/-0 normalization; no tolerance merging. |
| [out] | vertexOfPoint | Optional borrowed mapping resized to input count. Each processed input maps to first-occurrence unique vertex ID; early failure may retain partial mapping. Not retained. |
| [in] | cancelled | Optional callable polled before work starts, while sorting the insertion order and every 4096 insertions; returning true stops the build, which then returns false with the diagnostic "cdt: cancelled". Not retained. |
| [in] | progress | Optional callable invoked every 4096 insertions with the number of points inserted so far. Not retained. |
Triangulate points. vertexOfPoint receives, per input point, its vertex id (duplicates share one). Rejects fewer than 3 distinct points; collinear output needs caller inspection.
|
nodiscard |
Follow direct, origin-associated or collinear constrained edges from one endpoint to another.
| [in] | a | Valid stored starting vertex, unchecked; consistent incident topology required. |
| [in] | b | Valid stored ending vertex, unchecked; same predicate-safe frame. |
The vertices from a to b along the constrained edges that realise the input constraint (a, b) — {a, b} when it is one edge, more when vertices lying on the segment or refinement split it. Empty when no such chain.
|
inline |
Enable/reset optional origin bits for all currently stored vertices.
Fills owned origin array with zero, discarding prior diagnostic bits; call after build. Allocates parallel storage, no geometry/topology mutation, source IO or concurrent access allowed.
|
inlinenodiscard |
Copy the last explicitly recorded build/constraint diagnostic.
|
inlinenodiscard |
Return the unique-input count recorded as the super-vertex base at successful build.
| bool meshkit::BasicConstrainedDelaunay< Storage >::insertConstraint | ( | int | a, |
| int | b ) |
Recover/mark a straight constraint, recursively splitting at exactly collinear existing vertices.
| [in] | a | Stored nonsuper endpoint index; negative/out-of-range rejected unless a==b early no-op. |
| [in] | b | Stored nonsuper endpoint, same frame; active consistent built topology required. |
Force the edge between two vertex ids into the triangulation and mark it constrained. Returns false when the edge cannot be recovered (it would cross another constraint).
| int meshkit::BasicConstrainedDelaunay< Storage >::insertPoint | ( | const Point & | p | ) |
Insert one finite point in a live triangle, splitting a triangle/edge and restoring Delaunay edges.
| [in] | p | Borrowed finite XY query, unchanged; current consistent built topology required. |
Insert a new vertex at p (inside the current hull). Returns its id, or -1 when the point is outside every live triangle.
|
nodiscard |
Check whether a direct edge between two stored vertices is marked constrained.
| [in] | a | Valid stored vertex index, unchecked. |
| [in] | b | Valid stored vertex index, unchecked; active consistent incidence expected. |
True when the (min,max) vertex pair is a constrained edge.
|
inlinenodiscard |
Test whether an integer falls in the recorded three-super-vertex interval.
| [in] | v | Arbitrary candidate integer, range compared without storage indexing. |
|
inlinenodiscard |
Test whether an in-range vertex has a nonnegative incident-triangle hint.
| [in] | v | Arbitrary integer index, bounds checked. |
|
nodiscard |
Count slots whose alive flag is true, including super faces if still alive.
|
nodiscard |
Locate a finite point and require its found triangle to be alive.
| [in] | p | Borrowed predicate-safe XY query, unchanged; on-edge ownership may select either neighbor. |
Index of the live triangle containing p (on an edge counts), -1 = none.
|
staticnodiscard |
Return adaptive-exact orientation sign after thread-safe one-time predicate initialization.
| [in] | a | Borrowed finite line origin, unchanged. |
| [in] | b | Borrowed finite line endpoint in same Cartesian XY frame, unchanged. |
| [in] | c | Borrowed finite query, unchanged. |
Exact orientation of c against the line a-> left, negative right, exactly zero when collinear. b: positive
| auto meshkit::BasicConstrainedDelaunay< Storage >::refineQuality | ( | const QualityOptions & | opt | ) |
Mutate live constrained triangulation by bounded size/angle/terrain refinement and optional coarsening.
| [in] | opt | Borrowed settings and synchronous callbacks, not retained after return. Call only after successful build, constraint insertion and dead-region removal. hAt receives XY and returns positive target edge length in XY units, <=0/NaN disables local size bound. minAngleDeg clamps to [0,60] degrees, finite intended; minEdge/terrainMinSpacing use XY units. Terrain activates only with terrainError, terrainElevationAt and positive terrainTolerance; elevations/residual/tolerance share one Z unit. terrainError receives borrowed three-point/height arrays and writable witness point, must initialize a finite useful witness for positive finite error; NaN means unknown coverage. terrainElevationAt results cache per vertex, unavailable samples become NaN. terrainErrorBound must certify nonnegative maximum residual INCLUDING coverage for coarsening; absent skips terrain coarsening. protectedLocation/protectedVertices gate coarsening, not all insertions/smoothing. Callbacks must not throw, reenter/mutate this object or race shared state; temporary pointers expire after each invocation. cancelled is polled periodically, not before every operation or smoothing step. |
Delaunay refinement to the size and angle bounds (see the file comment). Call after the constraints are inserted and the exterior, holes and any other removed regions are dead; only live triangles are refined and new vertices never enter a dead region.
| void meshkit::BasicConstrainedDelaunay< Storage >::removeExterior | ( | ) |
Mark super-touching faces and every unconstrained reachable neighbor dead.
Requires successfully built constrained topology; insert closed boundaries first or all connected faces can be removed. Leaves vertex/triangle slots, adjacency and incidence hints allocated; does not compact arrays or clear every active hint. Allocates flood stack, mutates alive flags only, no error return, cancellation, source IO or concurrent queries during mutation.
Drop every triangle reachable from the super-triangle without crossing a constrained edge (the exterior of a constrained boundary).
| int meshkit::BasicConstrainedDelaunay< Storage >::removeRegionAt | ( | const Point & | p | ) |
Mark the live constraint-bounded component containing a finite seed point dead.
| [in] | p | Borrowed XY seed, unchanged; on shared edge locate chooses a face, so use strict interior seed when ownership matters. Requires consistent built topology and predicate-safe coordinates. |
| int meshkit::BasicConstrainedDelaunay< Storage >::removeRegionLeftOf | ( | int | a, |
| int | b ) |
Delete live constraint-bounded faces topologically seeded to a directed edge's left.
| [in] | a | Valid stored endpoint index, unchecked by edge lookup; stable built topology required. |
| [in] | b | Valid distinct endpoint index; orientation a-to-b defines left in XY frame. |
Drop the region (constraint-bounded component) to the left of the constrained edge a -> b.
| void meshkit::BasicConstrainedDelaunay< Storage >::removeSuperTriangles | ( | ) |
Mark only live faces touching one of the three super vertices dead.
Leaves the unconstrained real-point hull and all storage/adjacency/incidence hints in place; no flood across neighbors or compaction. Requires successful build, exclusive mutation, no allocation/IO.
Drop only the triangles touching a super-triangle vertex, leaving the convex hull of the input (unconstrained use).
| bool meshkit::BasicConstrainedDelaunay< Storage >::removeVertex | ( | int | v | ) |
Transactionally remove a free post-build interior vertex and retriangulate its local cavity.
| [in] | v | Vertex index; invalid/inactive/input/super/segment vertices rejected by preparation. |
Remove a free, interior vertex inserted after build(). Transactional: failure leaves the mesh untouched. Input and constraint vertices are protected. Vertex ids stay stable; removed vertices become unreferenced.
| void meshkit::BasicConstrainedDelaunay< Storage >::setFixedConstraint | ( | int | a, |
| int | b ) |
Mark every recovered subedge of a requested constraint chain unsplittable for refinement.
| [in] | a | Valid stored endpoint index, unchecked. |
| [in] | b | Valid stored endpoint index, unchecked; corresponding constraint should already exist. Absent chain is no-op. Allocates chain/set storage, does not insert missing constraints or make arbitrary external insertPoint calls respect this flag. No IO or retained arguments. |
Mark the input segment (a, b), already inserted with insertConstraint(), as unsplittable: refineQuality() never puts a vertex on it (a structured patch edge that must keep its stations).
|
nodiscard |
Test the shortest edge of a triangle for equal-radius input-corner shell exemption.
| [in] | t | Valid live triangle slot, unchecked. |
True when live triangle t is below the angle bound only because of a small input angle (Shewchuk's exemption: its shortest edge joins two segment vertices equidistant from the input vertex their segments share). For reporting and tests.
|
inlinenodiscard |
Borrow the most recent refinement's cached per-vertex elevation samples.
|
nodiscard |
Test whether any triangle vertex participates in a marked fixed constrained edge.
| [in] | t | Valid live triangle slot, unchecked; consistent incidence topology required. |
True when a vertex of live triangle t lies on a fixed segment (see setFixedConstraint). For reporting and tests.
|
inlinenodiscard |
Borrow all triangle slots with alive flags, adjacency and opposite-edge constraints.
|
inlinenodiscard |
Borrow diagnostic origin storage from this triangulation.
|
inlinenodiscard |
Borrow all stored XY positions including super, inactive and newly inserted vertices.