Loading...
Searching...
No Matches
mixed.hpp
Go to the documentation of this file.
1// SPDX-License-Identifier: Apache-2.0
2#pragma once
3#include "meshkit/job.hpp"
5#include "meshkit/blocks.hpp"
7#include "operation.hpp"
8#include <unordered_map>
9#include <cstring>
11{
13struct Coordinate {
15 std::uint64_t x = 0, y = 0;
23 bool operator==(const Coordinate &b) const { return x == b.x && y == b.y; }
24};
25
32 std::size_t operator()(Coordinate p) const
33 {
34 return p.x ^ (p.y + 0x9e3779b97f4a7c15ull + (p.x << 6) + (p.x >> 2));
35 }
36};
37
43{
44 double x = p.x() == 0 ? 0 : p.x(), y = p.y() == 0 ? 0 : p.y();
45 Coordinate k;
46 std::memcpy(&k.x, &x, 8);
47 std::memcpy(&k.y, &y, 8);
48 return k;
49}
50
53 std::vector<plan::PatchMesh> patches;
56 std::vector<int> regions;
58 std::vector<plan::PatchDecision> decisions;
60 std::vector<Point2> points;
63 std::vector<Path> extraPaths;
66 std::vector<std::vector<int>> boundarySources;
68 std::uint64_t cells = 0, sharedSides = 0;
71};
72
97 const std::function<double(const Box2 &)> &maximumSize,
98 const std::function<double(const Box2 &)> &tolerance,
99 Work &work, int attempt)
100{
101 PreparedPatches out;
102 out.points = r.points;
104 for (const auto &path : r.paths) {
105 plan::Polygon polygon;
106 for (auto index : path.vertices) {
107 if (index >= r.points.size())
108 fail("path_index", "Invalid source index before planning.");
109 polygon.append(r.points[index]);
110 }
111 if (path.kind == PathKind::Outer)
112 geometry.domains.append(polygon);
113 else if (path.kind == PathKind::Hole)
114 geometry.holes.append(polygon);
115 else
116 geometry.lines.append(polygon);
117 }
118 // Source identities that already lie on a required path are protected by its
119 // segment graph. Unattached mandatory points additionally constrain placement.
120 std::vector<bool> inPath(r.points.size(), false);
121 for (const auto &path : r.paths)
122 for (auto i : path.vertices)
123 inPath[i] = true;
124 for (std::size_t i = 0; i < r.points.size(); ++i)
125 if (!inPath[i])
126 geometry.pins.append(r.points[i]);
129 options.defaultSize =
130 r.options.maximumSize > 0 ? r.options.maximumSize : std::max(1., r.options.minimumTarget);
134 options.workBudget = r.options.limits.maxWork;
137 options.limits.maximumSize = maximumSize;
138 options.limits.cancelled = p.cancelled;
139 if (r.options.terrainTolerance > 0) {
141 options.limits.terrainToleranceForFootprint = tolerance;
142 options.limits.elevationAt = p.elevation;
143 options.limits.terrainBound = p.terrainBound;
144 }
145 if (r.options.automaticBlocks) {
146 Box2 bounds;
147 bool first = true;
149 for (const auto &path : r.paths) {
151 for (auto i : path.vertices)
152 line.append(r.points[i]);
153 if (path.closed || path.kind != PathKind::Line)
154 line.append(line.first());
155 blockers.append(line);
156 if (path.kind == PathKind::Outer) {
157 auto box = plan::Polygon(line).boundingRect();
158 bounds = first ? box : bounds.united(box);
159 first = false;
160 }
161 }
162 for (const auto &region : regions) {
163 auto line = plan::Vector<Point2>(region.ring);
164 if (!line.empty())
165 line.append(line.first());
166 blockers.append(line);
167 }
168 const double pitch =
169 std::max(4 * std::max(r.options.minimumTarget, options.defaultSize / 4),
170 std::max(bounds.width(), bounds.height()) / 256);
171 const auto grid =
172 plan::quadBlockGridFromField(bounds, pitch, maximumSize, blockers, p.cancelled);
173 if (!grid.isValid())
174 fail("planning_grid", "Automatic patch grid is invalid or cancelled.");
177 blocks.minSpacing = std::max(.5 * r.options.minimumTarget, 1e-9);
178 auto automatic = plan::placeQuadBlocks(grid, blocks);
179 int added = 0;
180 for (auto &region : automatic) {
181 const auto box = region.ring.boundingRect();
182 // Leave room for up to three rounds of terrain/metric refinement.
183 const double side =
184 region.spacing * std::sqrt(std::max(16., double(r.options.maximumPatchCells) / 64));
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) {
189 work.tick();
190 auto tile = region;
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));
203 ++added;
204 }
205 }
206 }
208 options.allowQuads = false;
209 if (!r.fixedPatches.empty())
210 fail("quad_conflict", "Fixed quads conflict with triangles-only mode.");
211 }
213 auto result = plan::planQuadRegions(regions, geometry, options);
214 work.tick(result.workUsed);
215 if (!result.ok)
216 fail("quad_plan", result.error,
217 result.cancelled ? RunStatus::Cancelled
218 : result.resourceLimited ? RunStatus::ResourceLimit
220 out.sharedSides = result.sharedSides;
221 out.decisions.assign(result.decisions.begin(), result.decisions.end());
222 for (const auto &fixed : r.fixedPatches) {
223 auto error = plan::validate(fixed);
224 if (!error.empty())
225 fail("fixed_patch", error);
226 const auto assessment = plan::assessPlannedPatch(fixed, options.limits);
227 if (!assessment.ok)
228 fail("fixed_patch", assessment.reason);
229 out.patches.push_back(fixed);
230 out.regions.push_back(-1);
231 }
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]);
235 }
236 auto addRing = [&](const plan::Polygon &ring, PathKind kind, std::int64_t id) {
237 Path path;
238 path.kind = kind;
239 path.closed = true;
240 path.id = id;
241 for (auto point : ring) {
242 if (!finite(point))
243 fail("region_geometry", "Nonfinite region coordinate.");
244 path.vertices.push_back(Index(out.points.size()));
245 out.points.push_back(point);
246 }
247 out.extraPaths.push_back(std::move(path));
248 };
249 for (std::size_t i = 0; i < regions.size(); ++i)
250 if (!regions[i].isBackground && !regions[i].automaticCandidate)
251 addRing(regions[i].ring, PathKind::Region, -std::int64_t(i + 1));
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]);
260 }
261 out.boundarySources.push_back(std::move(sources));
262 }
263 if (out.cells > r.options.limits.maxCells || out.points.size() > r.options.limits.maxVertices)
264 fail("planning_limit", "Planned patch/source counts exceed the job limit.",
266 work.memoryFor({{out.cells, 192}, {out.points.size(), 256}});
267 return out;
268}
269}
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