8#include <unordered_map>
15 std::uint64_t
x = 0,
y = 0;
34 return p.
x ^ (p.
y + 0x9e3779b97f4a7c15ull + (p.
x << 6) + (p.
x >> 2));
44 double x = p.
x() == 0 ? 0 : p.
x(), y = p.
y() == 0 ? 0 : p.
y();
46 std::memcpy(&k.
x, &x, 8);
47 std::memcpy(&k.
y, &y, 8);
97 const std::function<
double(
const Box2 &)> &maximumSize,
98 const std::function<
double(
const Box2 &)> &tolerance,
99 Work &work,
int attempt)
104 for (
const auto &path : r.
paths) {
106 for (
auto index : path.vertices) {
107 if (index >= r.
points.size())
108 fail(
"path_index",
"Invalid source index before planning.");
112 geometry.
domains.append(polygon);
114 geometry.
holes.append(polygon);
116 geometry.
lines.append(polygon);
120 std::vector<bool> inPath(r.
points.size(),
false);
121 for (
const auto &path : r.
paths)
122 for (
auto i : path.vertices)
124 for (std::size_t i = 0; i < r.
points.size(); ++i)
149 for (
const auto &path : r.
paths) {
151 for (
auto i : path.vertices)
162 for (
const auto ®ion : regions) {
165 line.append(line.first());
174 fail(
"planning_grid",
"Automatic patch grid is invalid or cancelled.");
180 for (
auto ®ion : automatic) {
181 const auto box = region.ring.boundingRect();
185 const int nx = std::max(1,
int(std::ceil(
box.width() / side))),
186 ny = std::max(1,
int(std::ceil(
box.height() / side)));
187 for (
int y = 0; y < ny && added < blocks.
maxBlocks; ++y)
188 for (
int x = 0; x < nx && added < blocks.
maxBlocks; ++x) {
191 const double gap = std::min(region.spacing,
192 .1 * std::min(
box.width() / nx,
box.height() / ny));
193 const double x0 =
box.left() + x *
box.width() / nx + (x ? gap : 0),
194 x1 =
box.left() + (x + 1) *
box.width() / nx -
195 (x + 1 < nx ? gap : 0);
196 const double y0 =
box.top() + y *
box.height() / ny + (y ? gap : 0),
197 y1 =
box.top() + (y + 1) *
box.height() / ny -
198 (y + 1 < ny ? gap : 0);
199 tile.ring = {{x0, y0}, {x1, y0}, {x1, y1}, {x0, y1}};
200 tile.automaticCandidate =
true;
201 tile.isBackground =
true;
202 regions.append(std::move(tile));
210 fail(
"quad_conflict",
"Fixed quads conflict with triangles-only mode.");
214 work.
tick(result.workUsed);
216 fail(
"quad_plan", result.error,
221 out.
decisions.assign(result.decisions.begin(), result.decisions.end());
225 fail(
"fixed_patch", error);
228 fail(
"fixed_patch", assessment.reason);
232 for (std::size_t i = 0; i < result.patches.size(); ++i) {
233 out.
patches.push_back(std::move(result.patches[i]));
234 out.
regions.push_back(result.patchRegions[i]);
241 for (
auto point : ring) {
243 fail(
"region_geometry",
"Nonfinite region coordinate.");
245 out.
points.push_back(point);
249 for (std::size_t i = 0; i < regions.
size(); ++i)
250 if (!regions[i].isBackground && !regions[i].automaticCandidate)
252 for (
const auto &patch : out.
patches) {
253 out.
cells += patch.quads.size();
254 std::vector<int> sources(patch.xy.size(), -1);
255 for (
auto edge : patch.boundarySegments)
256 for (
int v : {edge.first, edge.second})
257 if (sources[v] < 0) {
258 sources[v] = int(out.
points.size());
259 out.
points.push_back(patch.xy[v]);
264 fail(
"planning_limit",
"Planned patch/source counts exceed the job limit.",
Automatic open-area quad blocks (workplans/MESH_REGIONAL_TRIQUAD_PLAN_2026-10-03.md,...
Axis-aligned rectangle in the XY plane, stored as an origin corner and a signed size.
Definition geometry.hpp:167
constexpr double width() const
Signed extent along x in XY plane units; negative when not normalized.
Definition geometry.hpp:194
Box2 united(Box2 b) const
Bounding box of this box and b.
Definition geometry.hpp:294
constexpr double height() const
Signed extent along y in XY plane units; negative when not normalized.
Definition geometry.hpp:196
Point or displacement vector in the horizontal (XY) plane.
Definition geometry.hpp:21
constexpr double y() const noexcept
Y coordinate in XY plane units.
Definition geometry.hpp:36
constexpr double x() const noexcept
X coordinate in XY plane units.
Definition geometry.hpp:34
std::vector<T> with the QVector-style member names the CDT kernel and plan model use.
Definition storage.hpp:31
void append(const Vector &v)
Append copies of all elements of v.
Definition storage.hpp:84
std::ptrdiff_t size() const noexcept
Number of elements as a signed std::ptrdiff_t.
Definition storage.hpp:107
decltype(auto) first()
Reference to the first element (front()); the vector must not be empty.
Definition storage.hpp:49
Point sequence in XY units used for polygon rings and polylines.
Definition planmodel.hpp:83
Box2 boundingRect() const
Axis-aligned bounding box of all points.
Definition planmodel.hpp:102
Implementation helpers of the native jobs and codecs (failure signalling, work accounting,...
Box2 box(const Point2 *p, int n)
Axis-aligned bounding box of a point array.
Definition operation.hpp:131
PreparedPatches preparePatches(const JobRequest &r, const Providers &p, const std::function< double(const Box2 &)> &maximumSize, const std::function< double(const Box2 &)> &tolerance, Work &work, int attempt)
Plan the request's fixed, authored and automatic quad patches before triangulation.
Definition mixed.hpp:96
void fail(std::string code, std::string message, RunStatus status=RunStatus::Infeasible)
Abort the current native operation by throwing a Stop.
Definition operation.hpp:32
bool finite(Point2 p)
Test whether both coordinates are finite.
Definition operation.hpp:158
Coordinate coordinate(Point2 p)
Build the exact key of a point, mapping -0.0 to +0.0.
Definition mixed.hpp:42
QuadPlan planQuadRegions(const Vector< QuadRegion > &, const QuadPlanningGeometry &, const QuadPlanningOptions &={})
Plan mapped quad patches for all regions jointly, before CDT construction.
Definition planning.cpp:320
Vector< QuadRegion > placeQuadBlocks(const QuadBlockGrid &grid, const QuadBlockOptions &options)
Greedily select axis-aligned mapped quad regions from approximately uniform usable grid bands.
Definition blocks.cpp:208
Text validate(const StructuredPatch &p)
Input checks.
Definition patch.cpp:407
PatchAssessment assessPlannedPatch(const PatchMesh &, const PatchLimits &)
Check a mapped patch cell by cell against shape, size and terrain limits.
Definition planning.cpp:211
QuadBlockGrid quadBlockGridFromField(const Box2 &, double pitch, const std::function< double(const Box2 &)> &maximumSize, const Vector< Vector< Point2 > > &blockers, const std::function< bool()> &cancelled={}, std::int64_t maximumCells=1000000)
Sample a footprint size callback onto a candidate block grid and mask blockers.
Definition blocks.cpp:142
std::uint32_t Index
Zero-based index into a native vertex, cell or edge array.
Definition mesh.hpp:13
PathKind
Role of a Path in a JobRequest or a delivered Mesh.
Definition mesh.hpp:27
@ Line
Constrained polyline (breakline) whose segments become chains of cell edges.
Definition mesh.hpp:27
@ Hole
Ring subtracted from the domain; cells inside it are removed.
Definition mesh.hpp:27
@ Outer
Outer domain ring; the domain is the union of all outer rings minus the holes.
Definition mesh.hpp:27
@ Region
Closed constrained ring inside the domain; it separates region-label components but does not add or r...
Definition mesh.hpp:27
@ Infeasible
Input or policy cannot be satisfied; no result.
Definition events.hpp:50
@ ResourceLimit
Stopped at a resource cap or allocation failure; no result.
Definition events.hpp:47
@ Cancelled
Stopped because cancellation was requested; no result.
Definition events.hpp:48
@ Triangles
Triangles only.
Definition job.hpp:13
Graded element sizing for Delaunay refinement (MESH_MINSIZE_ENFORCEMENT_V2_AND_GRADING_PLAN_2026-09-0...
double maximumSize
Global upper bound on nominal cell size, finite and >= 0; 0 (default) means no global bound.
Definition job.hpp:65
double terrainTolerance
Reference terrain tolerance in Z units, finite and >= 0; 0 (default) disables terrain checks.
Definition job.hpp:106
std::uint64_t maximumPatchCells
Most cells one mapped patch may hold; default 250 000.
Definition job.hpp:131
double minimumTarget
Advisory minimum nominal cell size, finite and >= 0; 0 (default) disables it.
Definition job.hpp:65
bool automaticBlocks
Whether patch planning also places automatic open-area quad blocks; default false.
Definition job.hpp:137
double minimumEdge
Minimum actual edge length, finite and >= 0; 0 (default) disables it.
Definition job.hpp:65
Limits limits
Resource caps of the job.
Definition job.hpp:139
int maximumAutomaticBlocks
Cap on automatic block tiles; default 4096.
Definition job.hpp:138
CellPlan cells
Cell types to deliver; default triangles only.
Definition job.hpp:45
double minimumAngleDegrees
Smallest triangle angle sought by refinement, in degrees from 0 to 34; default.
Definition job.hpp:65
Complete input of runJob(): source geometry, optional attributes, sizing inputs, metadata and options...
Definition job.hpp:148
std::vector< Point2 > points
Mandatory source points: at least three, at most Limits::maxVertices.
Definition job.hpp:154
std::vector< plan::PatchMesh > fixedPatches
Local quad patches inserted as given after validation; every cell centre must lie in the domain.
Definition job.hpp:186
JobOptions options
Meshing policy and limits.
Definition job.hpp:193
std::vector< Path > paths
Source paths indexing points; at least one PathKind::Outer path is required (no bounding box is infer...
Definition job.hpp:159
std::vector< plan::QuadRegion > quadRegions
Quad region policies (see plan::QuadRegion).
Definition job.hpp:181
std::uint64_t maxWorkspaceBytes
Cap on estimated workspace in bytes (computed from counts, not measured); default 4 GiB.
Definition mesh.hpp:211
std::uint64_t maxVertices
Maximum number of vertices (source points, working vertices during refinement, mesh vertices,...
Definition mesh.hpp:209
std::uint64_t maxWork
Work-unit allowance of one operation's own counter.
Definition mesh.hpp:218
std::uint64_t maxCells
Maximum number of cells; default 20 000 000.
Definition mesh.hpp:209
Indexed polyline or ring: a source constraint of a JobRequest, or a delivered path of a Mesh.
Definition mesh.hpp:48
bool closed
Explicit closure of a Line path.
Definition mesh.hpp:64
std::int64_t id
Caller identifier.
Definition mesh.hpp:59
std::vector< Index > vertices
Zero-based vertex indices; at least two are required.
Definition mesh.hpp:49
PathKind kind
Role of the path; defaults to an open Line.
Definition mesh.hpp:50
Optional caller callbacks used by runJob(), plus the provider identity.
Definition job.hpp:204
std::function< double(const Point2 *, const double *)> terrainBound
Certified maximum residual (Z units) of the linear triangle over three XY corners with the given heig...
Definition job.hpp:231
std::function< bool()> cancelled
Polled during the job; returning true stops it with RunStatus::Cancelled.
Definition job.hpp:233
std::function< double(double, double)> elevation
Elevation (Z units) at XY position (x, y).
Definition job.hpp:219
Hash functor for Coordinate keys in unordered containers.
Definition mixed.hpp:26
std::size_t operator()(Coordinate p) const
Mix the two bit patterns (boost-style hash_combine).
Definition mixed.hpp:32
Exact hash-map key of an XY point: the bit patterns of its two doubles.
Definition mixed.hpp:13
bool operator==(const Coordinate &b) const
Bitwise equality of both patterns.
Definition mixed.hpp:23
std::uint64_t y
IEEE-754 bit pattern of y.
Definition mixed.hpp:15
std::uint64_t x
IEEE-754 bit pattern of x (see coordinate()).
Definition mixed.hpp:15
Quad patches planned before triangulation, with the extra sources they need.
Definition mixed.hpp:51
std::uint64_t sharedSides
Patch sides the joint planner matched to an already registered side.
Definition mixed.hpp:68
std::vector< int > regions
Per patch: planning-region index, -1 for fixed patches.
Definition mixed.hpp:56
std::uint64_t cells
Total quads across patches.
Definition mixed.hpp:68
std::vector< std::vector< int > > boundarySources
Per patch, per patch vertex: index in points of its boundary station, or -1 for a vertex on no bounda...
Definition mixed.hpp:66
std::vector< Point2 > points
Request points, then explicit region-ring vertices, then patch boundary stations.
Definition mixed.hpp:60
std::vector< Path > extraPaths
One closed PathKind::Region path per explicit (non-background, non-automatic) region,...
Definition mixed.hpp:63
std::vector< plan::PatchDecision > decisions
Planner decision records, one per planning region (authored, then automatic tiles).
Definition mixed.hpp:58
std::vector< plan::PatchMesh > patches
Fixed patches from the request, in order, then the planner's patches.
Definition mixed.hpp:53
Work-unit budget, workspace-estimate gate and cancellation poll for one operation.
Definition operation.hpp:43
void memoryFor(std::initializer_list< std::pair< std::uint64_t, std::uint64_t > > terms) const
Gate a workspace estimate given as (count, bytes per item) terms.
Definition operation.hpp:91
void tick(std::uint64_t count=1)
Charge work units; cancellation is polled whenever the updated total is an exact multiple of 4096.
Definition operation.hpp:77
double minimumEdge
Shortest permitted cell edge, XY units; 0 disables.
Definition planning.hpp:60
std::function< double(double, double)> elevationAt
Ground elevation, Z units, at (x, y) in XY units.
Definition planning.hpp:85
std::function< double(const Box2 &)> terrainToleranceForFootprint
Tolerance, Z units, for a cell's XY bounding box.
Definition planning.hpp:78
std::function< bool()> cancelled
Polled before the first cell and then every 1024 cells; returning true stops with PatchAssessment::ca...
Definition planning.hpp:94
std::function< double(const Box2 &)> maximumSize
Maximum cell size, XY units, for an XY bounding box, compared with sqrt(cell area).
Definition planning.hpp:82
std::function< double(const Point2 *, const double *)> terrainBound
Certified maximum terrain error, Z units, of the planar triangle through three points.
Definition planning.hpp:91
double minimumAngleDegrees
Smallest permitted interior angle (quadQuality() minAngleDeg), degrees; must be < 180,...
Definition planning.hpp:60
double terrainTolerance
Constant terrain error tolerance, Z units, used when terrainToleranceForFootprint is empty.
Definition planning.hpp:74
Policy for placeQuadBlocks().
Definition blocks.hpp:53
double minSpacing
Blocks finer than this are not worth a patch.
Definition blocks.hpp:54
int maxBlocks
Most regions returned; <= 0 returns none.
Definition blocks.hpp:59
Source geometry that protects areas from mapped patches; XY units, finite coordinates.
Definition planning.hpp:168
Vector< Polygon > domains
Domain rings, closing vertex optional; a patch must lie inside one.
Definition planning.hpp:173
Vector< Vector< Point2 > > lines
Open protected polylines; patches may not cross or enclose.
Definition planning.hpp:174
Vector< PatchMesh > fixedPatches
Existing patches whose validated boundaries block new ones; an invalid fixed patch contributes no bou...
Definition planning.hpp:180
Vector< Point2 > pins
Protected points.
Definition planning.hpp:177
Vector< Polygon > holes
Hole rings, closing vertex optional; a patch may not lie inside one.
Definition planning.hpp:173
Settings, budgets and patch limits for planQuadRegions().
Definition planning.hpp:125
std::uint64_t maximumWorkspaceBytes
Estimated planning memory budget in bytes (about 160 per source segment, 32 per station and 192 per p...
Definition planning.hpp:152
bool allowQuads
False forces triangles everywhere: optional regions fall back and any required region fails the plan.
Definition planning.hpp:128
PatchLimits limits
Base patch limits.
Definition planning.hpp:136
std::uint64_t maximumCells
Cell budget for all planned patches together.
Definition planning.hpp:145
std::uint64_t maximumPatchCells
Cell budget for a single patch.
Definition planning.hpp:145
std::uint64_t workBudget
Maximum work units; 0 means maximumCells * 512 + 100000.
Definition planning.hpp:152
double defaultSize
Target spacing, XY units, for regions whose QuadRegion::spacing is not > 0; must be finite and > 0.
Definition planning.hpp:131