Loading...
Searching...
No Matches
cdt.hpp
Go to the documentation of this file.
1
36
37#pragma once
40#include "meshkit/progress.hpp"
41#include <functional>
42#include <limits>
43
44namespace meshkit
45{
46
64template <class Storage> class BasicConstrainedDelaunay
65{
66public:
68 using Point = typename Storage::Point;
70 using Box = typename Storage::Box;
72 using String = typename Storage::String;
74 using PointInput = typename Storage::PointInput;
76 template <class T> using Vector = typename Storage::template Vector<T>;
78 template <class K, class V> using Hash = typename Storage::template Hash<K, V>;
80 template <class K, class V> using MultiHash = typename Storage::template MultiHash<K, V>;
82 template <class K> using Set = typename Storage::template Set<K>;
87 struct Triangle {
88 int v[3];
89 int adj[3];
90 bool constrained[3];
93 bool alive;
94 };
95
110 [[nodiscard]] static double orientExact(const Point &a, const Point &b, const Point &c);
111
140 bool build(const PointInput &points, Vector<int> *vertexOfPoint = nullptr,
141 const std::function<bool()> &cancelled = {},
142 const std::function<void(std::uint64_t)> &progress = {});
143
162 bool insertConstraint(int a, int b);
163
179 int insertPoint(const Point &p);
180
196 bool removeVertex(int v);
204 [[nodiscard]] bool isVertexActive(int v) const
205 {
206 return v >= 0 && v < m_vertexTri.size() && m_vertexTri[v] >= 0;
207 }
208
246 int removeRegionLeftOf(int a, int b);
254 [[nodiscard]] int inputVertexCount() const { return m_superBase; }
255
265 int removeRegionAt(const Point &p);
266
272 std::function<double(double, double)> hAt;
278 std::function<double(const Point *)> maximumAreaForTriangle;
288 std::function<double(int, int)> fixedNeighbourSize;
303 std::function<double(const Point *, const double *, Point *)> terrainError;
307 std::function<double(double, double)> terrainElevationAt;
312 double terrainTolerance = 0.0;
316 std::function<double(const Box &)>
318
323 double terrainMinSpacing = 0.0;
328 bool terrainWorstFirst = false;
333 bool terrainFinalCheck = true;
349 std::function<double(const Box &)>
360
363 std::function<bool(const Point &)> protectedLocation;
368 std::function<double(const Point *, const double *)> terrainErrorBound;
372 bool prioritizeQuality = true;
377 int maxTriangles = std::numeric_limits<int>::max();
381 double minAngleDeg = 30.0;
383 int maxInsertions = std::numeric_limits<int>::max();
389 double minEdge = 0.0;
391 std::function<bool()> cancelled;
394 std::function<void(const GenerationProgress &)> onProgress;
395 };
396
489
523 QualityReport refineQuality(const QualityOptions &opt);
537 void setFixedConstraint(int a, int b);
550 [[nodiscard]] bool smallAngleExempt(int t) const;
561 [[nodiscard]] bool touchesFixed(int t) const;
562
563 // Optional diagnostic provenance. Bits may overlap at coincident inputs;
564 // endpoint associations are not a causal explanation of final cell counts.
571 enum Origin : std::uint32_t {
572 Domain = 1,
573 Hole = 2,
574 Line = 4,
575 Patch = 8,
576 Node = 16,
578 Region = 64,
579 Lattice = 128,
580 Size = 256,
581 Angle = 512,
582 Terrain = 1024,
584 };
585
590 void enableProvenance() { m_origins.fill(0, m_pts.size()); }
599 void addVertexOrigin(int v, std::uint32_t origin)
600 {
601 if (!m_origins.isEmpty() && v >= 0 && v < m_origins.size())
602 m_origins[v] |= origin;
603 }
604
612 [[nodiscard]] const Vector<std::uint32_t> &vertexOrigins() const { return m_origins; }
613
614 // ── Read-out ───────────────────────────────────────────────────────
623 [[nodiscard]] const Vector<Point> &vertices() const { return m_pts; }
632 [[nodiscard]] const Vector<Triangle> &triangles() const { return m_tris; }
640 [[nodiscard]] const Vector<double> &terrainElevations() const { return m_terrainElevations; }
646 [[nodiscard]] int liveTriangleCount() const;
657 [[nodiscard]] int locate(const Point &p) const;
668 [[nodiscard]] bool isConstrained(int a, int b) const;
684 [[nodiscard]] Vector<int> constrainedChain(int a, int b) const;
691 [[nodiscard]] bool isSuperVertex(int v) const
692 {
693 return v >= m_superBase && v < m_superBase + 3;
694 }
695
701 [[nodiscard]] String errorMsg() const { return m_errorMsg; }
702
703private:
704 struct Removal {
705 Vector<int> star, ring;
706 Vector<Triangle> replacement;
707 };
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;
920
921 Vector<Point> m_pts;
922 Vector<std::uint32_t> m_origins;
923 Vector<double> m_terrainElevations;
924 Vector<Triangle> m_tris;
925 int m_liveTriangles = 0;
926 Vector<int> m_vertexTri;
927 int m_superBase = 0;
928 int m_lastLocate = 0;
929 String m_errorMsg;
931 m_segOrigin;
933 m_segOriginExtra;
935 m_segPiece;
937 m_vertexSeg;
938 Set<std::uint64_t> m_fixedSub;
939 // Installed only during refinement. Every geometric edit invalidates the
940 // affected work, including flips outside the inserted vertex's final star.
941 std::function<void(int)> m_triangleChanged;
942};
943
947} // namespace meshkit
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
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