68 using Point =
typename Storage::Point;
70 using Box =
typename Storage::Box;
72 using String =
typename Storage::String;
78 template <
class K,
class V>
using Hash =
typename Storage::template
Hash<K, V>;
82 template <
class K>
using Set =
typename Storage::template
Set<K>;
141 const std::function<
bool()> &cancelled = {},
142 const std::function<void(std::uint64_t)> &progress = {});
206 return v >= 0 && v < m_vertexTri.size() && m_vertexTri[v] >= 0;
272 std::function<double(
double,
double)>
hAt;
316 std::function<double(
const Box &)>
349 std::function<double(
const Box &)>
601 if (!m_origins.isEmpty() && v >= 0 && v < m_origins.size())
602 m_origins[v] |= origin;
693 return v >= m_superBase && v < m_superBase + 3;
705 Vector<int> star, ring;
719 bool prepareRemoval(
int v, Removal *out)
const;
730 void commitRemoval(
int v,
const Removal &removal);
742 double orient(
int a,
int b,
int c)
const;
753 double orient(
int a,
int b,
const Point &p)
const;
767 bool inCircle(
int a,
int b,
int c,
int d)
const;
778 int findTriangle(
const Point &p,
int start)
const;
790 int triangleWithEdge(
int a,
int b,
int *edgeIndexOut)
const;
801 void legalize(
int t,
int e);
811 void flip(
int t,
int e);
819 void setAdj(
int t,
int e,
int n);
830 void splitTriangle(
int t,
int v);
842 void splitEdge(
int t,
int e,
int v);
849 int edgeIndex(
int t,
int v)
const;
859 void trianglesAround(
int v, Vector<int> *out)
const;
867 void markConstrained(
int a,
int b);
879 bool insertConstraintImpl(
int a,
int b, std::uint64_t origin);
892 int splitSubsegment(
int a,
int b);
901 bool subsegmentEncroached(
int a,
int b)
const;
909 bool isFixedSub(
int a,
int b)
const;
919 bool exemptShortestEdge(
int u,
int v)
const;
923 Vector<double> m_terrainElevations;
925 int m_liveTriangles = 0;
926 Vector<int> m_vertexTri;
928 int m_lastLocate = 0;
941 std::function<void(
int)> m_triangleChanged;
Constrained Delaunay triangulation kernel with quality and terrain refinement and optional coarsening...
Definition cdt.hpp:65
typename meshkit::detail::QtStorage::PointInput PointInput
Definition cdt.hpp:74
void enableProvenance()
Enable/reset optional origin bits for all currently stored vertices.
Definition cdt.hpp:590
typename meshkit::detail::QtStorage::template Vector< T > Vector
Definition cdt.hpp:76
int insertPoint(const Point &p)
Insert one finite point in a live triangle, splitting a triangle/edge and restoring Delaunay edges.
Definition cdt_impl.hpp:807
int liveTriangleCount() const
Count slots whose alive flag is true, including super faces if still alive.
Definition cdt_impl.hpp:394
bool isVertexActive(int v) const
Test whether an in-range vertex has a nonnegative incident-triangle hint.
Definition cdt.hpp:204
static double orientExact(const Point &a, const Point &b, const Point &c)
Return adaptive-exact orientation sign after thread-safe one-time predicate initialization.
Definition cdt_impl.hpp:150
bool smallAngleExempt(int t) const
Test the shortest edge of a triangle for equal-radius input-corner shell exemption.
Definition cdt_impl.hpp:1252
void addVertexOrigin(int v, std::uint32_t origin)
OR diagnostic provenance flags into an enabled in-range origin slot.
Definition cdt.hpp:599
typename meshkit::detail::QtStorage::template MultiHash< K, V > MultiHash
Definition cdt.hpp:80
typename meshkit::detail::QtStorage::template Set< K > Set
Definition cdt.hpp:82
typename meshkit::detail::QtStorage::String String
Definition cdt.hpp:72
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.
Definition cdt_impl.hpp:658
int locate(const Point &p) const
Locate a finite point and require its found triangle to be alive.
Definition cdt_impl.hpp:388
int removeRegionLeftOf(int a, int b)
Delete live constraint-bounded faces topologically seeded to a directed edge's left.
Definition cdt_impl.hpp:1066
bool touchesFixed(int t) const
Test whether any triangle vertex participates in a marked fixed constrained edge.
Definition cdt_impl.hpp:1267
int inputVertexCount() const
Return the unique-input count recorded as the super-vertex base at successful build.
Definition cdt.hpp:254
void setFixedConstraint(int a, int b)
Mark every recovered subedge of a requested constraint chain unsplittable for refinement.
Definition cdt_impl.hpp:1112
const Vector< Point > & vertices() const
Borrow all stored XY positions including super, inactive and newly inserted vertices.
Definition cdt.hpp:623
bool insertConstraint(int a, int b)
Recover/mark a straight constraint, recursively splitting at exactly collinear existing vertices.
Definition cdt_impl.hpp:839
const Vector< std::uint32_t > & vertexOrigins() const
Borrow diagnostic origin storage from this triangulation.
Definition cdt.hpp:612
Origin
Diagnostic vertex-provenance bits stored by enableProvenance()/addVertexOrigin().
Definition cdt.hpp:571
@ SegmentSplit
Definition cdt.hpp:583
@ Size
Definition cdt.hpp:580
@ Domain
Definition cdt.hpp:572
@ Node
Definition cdt.hpp:576
@ Line
Definition cdt.hpp:574
@ Breakline
Definition cdt.hpp:577
@ Hole
Definition cdt.hpp:573
@ Patch
Definition cdt.hpp:575
@ Region
Definition cdt.hpp:578
@ Lattice
Definition cdt.hpp:579
@ Angle
Definition cdt.hpp:581
@ Terrain
Definition cdt.hpp:582
int removeRegionAt(const Point &p)
Mark the live constraint-bounded component containing a finite seed point dead.
Definition cdt_impl.hpp:1041
const Vector< Triangle > & triangles() const
Borrow all triangle slots with alive flags, adjacency and opposite-edge constraints.
Definition cdt.hpp:632
const Vector< double > & terrainElevations() const
Borrow the most recent refinement's cached per-vertex elevation samples.
Definition cdt.hpp:640
QualityReport refineQuality(const QualityOptions &opt)
Mutate live constrained triangulation by bounded size/angle/terrain refinement and optional coarsenin...
Definition cdt_impl.hpp:1468
typename meshkit::detail::QtStorage::template Hash< K, V > Hash
Definition cdt.hpp:78
void removeSuperTriangles()
Mark only live faces touching one of the three super vertices dead.
Definition cdt_impl.hpp:1032
String errorMsg() const
Copy the last explicitly recorded build/constraint diagnostic.
Definition cdt.hpp:701
bool isSuperVertex(int v) const
Test whether an integer falls in the recorded three-super-vertex interval.
Definition cdt.hpp:691
bool isConstrained(int a, int b) const
Check whether a direct edge between two stored vertices is marked constrained.
Definition cdt_impl.hpp:271
bool removeVertex(int v)
Transactionally remove a free post-build interior vertex and retriangulate its local cavity.
Definition cdt_impl.hpp:1458
Vector< int > constrainedChain(int a, int b) const
Follow direct, origin-associated or collinear constrained edges from one endpoint to another.
Definition cdt_impl.hpp:281
typename meshkit::detail::QtStorage::Box Box
Definition cdt.hpp:70
void removeExterior()
Mark super-touching faces and every unconstrained reachable neighbor dead.
Definition cdt_impl.hpp:1006
typename meshkit::detail::QtStorage::Point Point
Definition cdt.hpp:68
The Qt-free MeshKit library: job events and progress (meshkit::runtime), the neutral mesh model,...
BasicConstrainedDelaunay< detail::StandardStorage > ConstrainedDelaunay
Kernel instantiated with standard C++ storage (Point2, Box2, std::string, std::vector-based container...
Definition cdt.hpp:946
CoarseningOrder
Order in which terrain coarsening tries to remove free vertices.
Definition terrainpolicy.hpp:10
@ LegacyFlatness
Flattest vertex star first (smallest facet-normal spread), tile by tile in spatial (Morton) order.
Definition terrainpolicy.hpp:10
Options for refineQuality().
Definition cdt.hpp:268
double terrainMinSpacing
Minimum XY distance from a terrain-driven point to existing vertices; the spacing used is max(terrain...
Definition cdt.hpp:323
std::function< double(const Point *, const double *)> terrainErrorBound
Certified maximum residual INCLUDING coverage, unlike terrainError's refinement witness.
Definition cdt.hpp:368
Set< int > protectedVertices
Additional template vertices to retain.
Definition cdt.hpp:364
double coarseningReferenceSize
ResolutionAware only: target size in XY units used for a star's priority when coarseningTargetSize() ...
Definition cdt.hpp:359
CoarseningOrder coarseningOrder
Order of coarsening candidates.
Definition cdt.hpp:348
int coarsenPasses
Maximum attempts per free vertex; 0 = off.
Definition cdt.hpp:341
std::function< double(const Point *, const double *, Point *)> terrainError
Actual surface error at the reference DEM samples covered by a triangle.
Definition cdt.hpp:303
std::function< double(double, double)> terrainElevationAt
Reference elevation (Z units) at XY (x, y).
Definition cdt.hpp:307
bool prioritizeQuality
True (default) with minAngleDeg > 0: queue triangles in 32 buckets of sin(smallest angle) / sin(minAn...
Definition cdt.hpp:372
int maxInsertions
Safety cap on inserted vertices (segment splits included).
Definition cdt.hpp:383
int sizingRepairPasses
Passes of bounded size repair after smoothing, terrain insertion and coarsening; clamped to [0,...
Definition cdt.hpp:299
double terrainTolerance
Allowed terrain residual in Z units; a triangle whose terrainError exceeds it is refined.
Definition cdt.hpp:312
std::function< bool()> cancelled
Polled every 4096 insertions; returning true stops refinement.
Definition cdt.hpp:391
std::function< void(const GenerationProgress &)> onProgress
Advisory typed counters at bounded checkpoints; no topology scans.
Definition cdt.hpp:394
double normalVerticalToXY
ResolutionAware only: factor applied to elevation differences before facet normals are compared,...
Definition cdt.hpp:359
std::function< double(double, double)> hAt
Target edge length h at (x, y): a triangle is split when its area exceeds the equilateral triangle of...
Definition cdt.hpp:272
int maxTriangles
Cap on liveTriangleCount(), checked before refinement and after every insertion.
Definition cdt.hpp:377
double minEdge
Floor against refinement cascades (an angle bound near the limit on an awkward input can otherwise sh...
Definition cdt.hpp:389
bool terrainFinalCheck
After refinement, measure every live triangle's terrain error for Report::terrainUnresolved / terrain...
Definition cdt.hpp:333
double minAngleDeg
Smallest angle every triangle must reach (degrees); 0 = size only.
Definition cdt.hpp:381
std::function< double(const Box &)> terrainToleranceForFootprint
Positive immutable tolerance for a whole footprint box, replacing terrainTolerance.
Definition cdt.hpp:317
int maximumSizingRepairInsertions
Cap on vertices (segment splits included) inserted by sizing repair; reaching it sets QualityReport::...
Definition cdt.hpp:299
std::function< double(const Point *)> maximumAreaForTriangle
Optional per-triangle area cap in squared XY units.
Definition cdt.hpp:278
std::function< bool(const Point &)> protectedLocation
Coarsening gate: a vertex whose position returns true is never removed.
Definition cdt.hpp:363
std::function< double(int, int)> fixedNeighbourSize
Sizing-repair only (needs maximumAdjacentRatio >= 1).
Definition cdt.hpp:288
bool terrainWorstFirst
Refine size and angle first, then insert terrain points worst error first until the tolerance or maxT...
Definition cdt.hpp:328
double maximumAdjacentRatio
Sizing-repair only.
Definition cdt.hpp:283
std::function< double(const Box &)> coarseningTargetSize
Prescribed size; zero means unbounded, never evolving geometry.
Definition cdt.hpp:350
int smoothingPasses
Passes of non-degrading smoothing after size and angle refinement: each free vertex (inserted after b...
Definition cdt.hpp:340
Counters and diagnostics of one refineQuality() call.
Definition cdt.hpp:400
bool coarsenSkippedTerrain
Terrain is active but terrainErrorBound is absent, so coarsening was skipped.
Definition cdt.hpp:473
int segmentSplits
Constrained subsegments split; also counted in inserted.
Definition cdt.hpp:411
bool capped
Stopped at maxInsertions or maxTriangles.
Definition cdt.hpp:439
std::uint64_t coarsenQueuePeak
Largest size reached by the coarsening priority queue.
Definition cdt.hpp:481
int inserted
Vertices added, segment splits included.
Definition cdt.hpp:410
int terrainInsertions
Terrain witness points inserted, excluding segment splits.
Definition cdt.hpp:427
int terrainUnresolved
Final check: live triangles whose terrain error still exceeds the tolerance.
Definition cdt.hpp:436
int terrainUnknown
Final check: live triangles whose error or tolerance is not finite.
Definition cdt.hpp:436
int sizingRepairInserted
Vertices (segment splits included) inserted by the sizing-repair stage.
Definition cdt.hpp:407
int coarsenAttempts
Removal attempts, including stars that could not be retriangulated.
Definition cdt.hpp:460
int coarsenExactQueries
Calls to QualityOptions::terrainErrorBound.
Definition cdt.hpp:471
int coarsenBoundAccepts
Replacement triangles certified by the cached bound without calling terrainErrorBound.
Definition cdt.hpp:471
int sizeInsertions
Point insertions, excluding segment splits, for a size target (hAt, maximumAreaForTriangle or sizing-...
Definition cdt.hpp:427
int coarsenRejectedSize
Removals refused because a replacement triangle exceeds hAt, coarseningTargetSize (ResolutionAware) o...
Definition cdt.hpp:450
int coarsenRejectedEdge
Removals refused because a replacement edge is shorter than the star's shortest edge.
Definition cdt.hpp:460
bool sizingRepairLimited
Sizing repair reached maximumSizingRepairInsertions (at once when that is <= 0).
Definition cdt.hpp:409
int coarsenRejectedTerrain
Removals refused by the terrain checks; includes coarsenHeightRejects.
Definition cdt.hpp:460
double maxTerrainError
Final check: largest finite terrain error found, in Z units; 0 when not checked.
Definition cdt.hpp:438
int coarsenRejectedAngle
Removals refused because a replacement triangle breaks the angle bound.
Definition cdt.hpp:450
int coarsenRemoved
Free vertices removed by coarsening.
Definition cdt.hpp:450
bool cancelled
QualityOptions::cancelled returned true; edits are kept.
Definition cdt.hpp:440
int qualityInsertions
Point insertions, excluding segment splits, for the minimum-angle bound.
Definition cdt.hpp:427
int coarsenHeightRejects
Removals refused because the removed vertex's own height misses the replacement plane by more than th...
Definition cdt.hpp:471
bool invalidPolicy
Options or a callback result were invalid (coarseningOrder requirements, terrainToleranceForFootprint...
Definition cdt.hpp:487
std::uint64_t coarsenPriorityQueries
ResolutionAware only: coarseningTargetSize calls made for queue priorities.
Definition cdt.hpp:481
int sizingRepairPasses
Sizing-repair passes started (at most 3).
Definition cdt.hpp:407
int blockedByFixed
Bad triangles whose point would encroach constrained subsegments of which none could be split: fixed,...
Definition cdt.hpp:416
double coarsenSeconds
Wall-clock seconds spent in the coarsening stage.
Definition cdt.hpp:474
One triangle slot of triangles().
Definition cdt.hpp:87
int adj[3]
Neighbour across the edge opposite v[i] (v[i+1], v[i+2]); -1 = none.
Definition cdt.hpp:89
bool alive
False once the slot is removed (removeExterior(), removeSuperTriangles(), region removal,...
Definition cdt.hpp:93
int v[3]
Counter-clockwise.
Definition cdt.hpp:88
bool constrained[3]
Edge opposite v[i] is a constraint.
Definition cdt.hpp:90
Counter snapshot passed to ConstrainedDelaunay::QualityOptions::onProgress during refineQuality().
Definition progress.hpp:14