* security: bound geometry-kernel degree and work (CWE-407)
Several geometry routines let a crafted spline or region cause quadratic or
worse CPU work:
- B-spline basis evaluation is O(degree²) per sample and tessellation takes
O(degree) samples, so a HATCH/DXF spline edge declaring a very high degree
(DXF allows up to 100 000) turned a tiny spline into billions of iterations.
Add `MAX_DEGREE = 64` and treat higher-degree splines as invalid, so
`eval`/`tessellate` fall back to the control polygon. The render clip boundary
also rejects such degrees up front (rows 18, 28).
- `Spline::derivative` re-ran the O(knots) validity scan on every call, and
arc-length integration calls it once per sample, making a valid spline's
measurement quadratic. Split off `derivative_unchecked` and have integration
(validated once by its public entry points) use it (row 24).
- `infer_knot_param` matched each fit parameter against the whole knot vector
from the start. Both are ascending, so replace it with a linear merge (row 16).
- Fillet seed collection did not stop the enclosing run-pair loops when the
per-call candidate cap was hit, and refined duplicate candidates. Bound total
seeds across pairs and deduplicate before Newton refinement (row 36).
- Region grid intersection counted only distinct pairs against its budget, so a
long segment replicated across many cells re-visited the same pair unbounded.
Charge every candidate-pair visit against a budget (row 41).
New spline degree tests added; all geom and render tests pass, clippy clean.
Addresses findings rows 16, 18, 24, 28, 36, 41.
* fix: preserve spline knot and fillet search behavior
---------
Co-authored-by: skylartaylor <26588250+skylartaylor@users.noreply.github.com>
AREA's Object option reported a full ellipse's perimeter with
Ramanujan's closed-form estimate, which falls short as the ellipse
flattens: 46.0256 for a 10 x 4 ellipse (exactly 46.0262), 39.8741 for a
10 x 0.1 one (exactly 40.0110, 0.34% short). It now integrates the
perimeter with the geometry crate's ellipse arc length, the one LENGTHEN
measures with, so both report the same length for the same ellipse.
Ellipse::arc_length_from halves a panel where it needs it (the same
adaptive Gauss-Legendre as spline arc lengths): with fixed panels a
100:1 ellipse came out 4e-8 long, as it turns sharply at its ends.
Tests check four ellipses (round to 100:1) against the
arithmetic-geometric mean to 1e-9, and the printed AREA line.
Co-authored-by: Brandon Thomas <echelon@gmail.com>
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
* Inquiry: SHAPES reports closed-shape geometry facts
`shapes` is a read-only command that reports, for every closed shape in the
current space (closed polylines, circles, full ellipses, closed splines),
its perimeter, area, centroid, winding, first self-intersection and
coincident vertices, exact with arcs and bulges. It filters and pages like
`entities` and counts other matches under `skipped` with the reason.
`Polyline::centroid` and `polygon_centroid` give the area centroid.
Fixes#1436.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
* shapes: cap the quadratic self-intersection test at 4000 edges
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
---------
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
Co-authored-by: Brandon Thomas <echelon@gmail.com>
Found while testing crates/geom/src/curve.rs:435 (bulge_to_arc) together with crates/geom/src/lib.rs:45-48 (ccw_sweep)
Co-Authored-By: Claude Haiku 5.5 <noreply@anthropic.com>
Co-Authored-By: Claude Sonnet 5.5 <noreply@anthropic.com>
* Property-based and hostile-input tests for geometry numerics (gaps.md S6)
A deterministic xorshift64* generator (no new dependency) drives a few
thousand cases per property in crates/geom/src/property_tests.rs:
- line/line: hits lie on both lines, parameters reproduce the point,
swapping the operands gives the same point, finite results agree with
the infinite parameters
- line/circle and circle/circle: hits lie on both curves, results are
symmetric, properly crossing circles match the closed form; hostile
inputs (NaN, infinities, subnormals, raw bit patterns, 1e300) never
panic and the guarded functions return only finite hits or none
- segments: extending only adds hits
- closest points: fixed point of closest, perpendicular inside the
segment, endpoints outside
- arcs: at(0)/at(1) are the endpoints at radii from 1e-6 to 1e6; the
three-point arc keeps {start, end} = {p1, p3} and contains p2 (the
CCW-only storage swaps the pair when p2 is on the clockwise side, as
DXF stores arcs) and matches the circumradius closed form; collinear
inputs are rejected
- bounds and vector identities
- known answers at 1e6-1e7 coordinates hold to 1e-9 relative
gaps.md S6 removed and geometry-parity.md's Tests section updated in
the same change.
* docs: drop the sentence the new numerics tests make stale
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
---------
Co-authored-by: Brandon Thomas <echelon@gmail.com>
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
* Geometry: spline arc length converges on tight bends, so LENGTHEN shortens to the target (fixes#705)
* Geometry: cap adaptive spline quadrature (depth 10, 1e-10 relative) so a hostile spline can't make LENGTHEN slow
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
---------
Co-authored-by: Brandon Thomas <echelon@gmail.com>
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
SPLINE's Knots, Object, start/end Tangency and toLerance options printed
"not available yet". Fit-point splines now take a knot parametrisation
(chord, square root, uniform), end tangents (clamped cubic with derivative
constraints) and a fit tolerance (least-squares approximation with the
fewest control points that stay within it). The spline keeps these options
so grip and SPLINEDIT edits refit the same way; DXF writes the tolerance
(44) and tangents (12/13) and recovers the parametrisation from the knots.
Object turns 2D/3D polylines with straight segments (PEDIT Spline output)
into splines through their vertices.
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
SPLINE Close now builds a smooth closed (periodic) curve through the fit points
instead of repeating the first point. The geometry gets Spline::from_fit_points_closed:
chord-length parameters including the closing chord, a periodic knot vector, and the
first three control points repeated at the end. The fit data no longer duplicates the
first point. DXF writes group 70 bit 2 (periodic) for it, and a file whose closed spline
needs refitting is refitted closed. SPLINEDIT Close/refit/move and fit-point grips keep
a closed spline periodic.
SPLINE Method asks Fit/CV, and CV continues as SPLINE by control vertices. Knots, Object,
start/end Tangency and toLerance report "not available yet" and stay at the prompt.
Garbage text reports "Point or option keyword required.".
POLYGON with a typed radius puts the bottom edge horizontal for Inscribed and for
Circumscribed. The JSON form uses the same orientation when no angle is given.
CIRCLE reports "Point or option keyword required." for an invalid token at the centre
prompt, and "Invalid point." at the 3P/2P point prompts, then asks again.
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
TAN and PER snaps need the other end of the line, so the first point of a
LINE (no base point yet) could never snap tangent: a belt line tangent to
two circles was impossible to draw.
Now, as in AutoCAD, a point prompt can accept *deferred* snaps:
- snap: with no base and the new `deferred` flag, osnap offers "Deferred
Tangent" (circles, arcs) and "Deferred Perpendicular" (circles, arcs,
lines, xlines, rays) where no other snap wins. The hit carries the curve
(`SnapHit::deferred`, `Deferred`, `SnapCurve`).
- `resolve_deferred` solves the line once the other end is known: tangent
or perpendicular from a point, tangent-to-tangent (common tangents of two
circles, new `Circle::common_tangents` in geom) and the perpendicular
mixes. Among several solutions the one nearest the picks wins. No
solution (point inside the circle, concentric or nested circles,
non-finite input) is `None`, never a panic.
- prompt: `Prompt::deferred()` opts a prompt in; `Input::Deferred` reaches
only such prompts, everywhere else the session turns it into the point it
was picked at, so other commands snap as before.
- LINE opts in for its first point (and the next one while the first is
still deferred). No solution reports and re-prompts; Undo drops the
deferred point. The rubber band shows the resolved line, also the
tangent-to-tangent one while hovering the second curve
(`Session::cursor_deferred`, set by the canvas).
- canvas: passes the prompt's flag to osnap and sends a deferred pick as
`Input::Deferred`.
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
Point picks found the outer boundary by tracing the planar graph of all
curves, but islands only came from single closed objects (circles, closed
polylines, full ellipses, closed splines). A square drawn as four LINEs
inside a rectangle was ignored: HATCH drew through it, GRADIENT filled it
and BOUNDARY created only the outer polyline.
- geom::region::boundary_at returns the outer loop plus islands: every
connected group of curves inside the face that doesn't touch its
boundary and doesn't surround the pick point. Each island is the
outline of the group's outside, traced with the same sharpest-turn
walk from its leftmost vertex after dangling ends are pruned. Islands
report which input curves they came from. Traces are bounded by the
group's edge count and islands are capped at MAX_ISLANDS.
- loops_at (shared by HATCH, GRADIENT and BOUNDARY) adds those islands
when every curve in the group is an open LINE, ARC, elliptical arc,
open polyline or open spline. Groups containing a closed object keep
the existing per-object islands, so closed-polyline and circle islands
are unchanged (bulges kept).
- Tests: geom region tests for separate-line islands, dangling ends,
open and attached curves, nesting and hostile input; engine tests for
HATCH (rendered pattern stays out of the hole), GRADIENT (375 filled,
hole clear) and BOUNDARY (two polylines) with four-line and
closed-polyline islands.
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
DIMLINEAR/ALIGNED/RADIUS/DIAMETER/ANGULAR/ARC/ORDINATE/CONTINUE/BASELINE, QDIM, MLEADER, LEADER;
HATCH/GRADIENT/BOUNDARY/REGION with pick-point boundary tracing (planar face walk with islands);
BLOCK/INSERT/ATTDEF/ATTEDIT/WBLOCK/PURGE/BATTMAN; dimension text gaps and horizontal text;
DXF header writer whitelist (correct group codes).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
