Immutable 2D vector path. More...
#include "donner/base/Path.h"
Classes | |
| struct | Command |
| A command in the path, pairing a verb with the index of its first point. More... | |
| struct | PointOnPath |
| Result of sampling the path at a given arc length distance. More... | |
| class | MeasuredPath |
| Precomputed arc-length index for repeated path sampling. More... | |
| struct | Vertex |
| Vertex in a path's edge list, used for marker placement. More... | |
Public Types | |
| enum class | Verb : uint8_t { MoveTo , LineTo , QuadTo , CurveTo , ClosePath } |
| Verb types describing how points are connected. More... | |
Public Member Functions | |
| Path ()=default | |
| Construct an empty path. | |
| Path (const Path &)=default | |
| Copy constructor. | |
| Path (Path &&) noexcept=default | |
| Move constructor. | |
| Path & | operator= (const Path &)=default |
| Copy assignment operator. | |
| Path & | operator= (Path &&) noexcept=default |
| Move assignment operator. | |
| ~Path ()=default | |
| Destructor. | |
| bool | operator== (const Path &other) const |
| Value equality. Two paths compare equal iff their command verb / point-index sequences match and their points compare equal with Vector2d::operator==, which allows an absolute difference of machine epsilon per coordinate. Command::isInternal is not compared. Used to skip redundant updates when shape attributes recompute to the same geometry. | |
Accessors | |
| std::span< const Vector2d > | points () const |
| Returns the points array. | |
| std::span< const Command > | commands () const |
| Returns the commands array. | |
| bool | empty () const |
| Returns true if the path has no commands. | |
| size_t | verbCount () const |
| Returns the number of commands (verbs) in the path. | |
| std::optional< std::size_t > | retainedBytes () const |
| Dynamic bytes reserved by the path's command and point vectors, or nullopt on overflow. | |
Geometric queries | |
| Box2d | bounds () const |
| Returns the axis-aligned bounding box of the path. | |
| Box2d | transformedBounds (const Transform2d &transform) const |
Returns the bounding box of the path transformed by transform. | |
| Path | transformed (const Transform2d &transform) const |
Returns this path with every point mapped through transform. | |
| bool | isInside (const Vector2d &point, FillRule fillRule=FillRule::NonZero) const |
| Returns true if the given point is inside this path's fill region. | |
| bool | isOnPath (const Vector2d &point, double strokeWidth) const |
Returns true if the given point is within strokeWidth of any path segment. | |
| MeasuredPath | measure () const |
| Build a reusable arc-length index for this path. | |
| MeasuredPath | measure (std::size_t maximumWorkUnits) const |
Builds an arc-length index without consuming more than maximumWorkUnits command visits and recursive subdivisions. | |
| std::optional< std::size_t > | measurementBaseRetainedBytes () const |
| Bytes needed to reserve the maximum possible segment array before measurement starts. | |
| std::optional< std::size_t > | measurementRetainedBytesUpperBound (std::size_t maximumWorkUnits) const |
| Conservative retained-byte ceiling for a measurement with the given work allowance. | |
| std::size_t | measurementWorkLimitForRetainedBytes (std::size_t maximumBytes) const |
| Largest measurement work allowance whose conservative retention fits in p maximumBytes. | |
| double | pathLength () const |
| Compute the total arc length of the path. | |
| PointOnPath | pointAtArcLength (double distance) const |
Sample the path at the given arc length distance from the start. | |
| Vector2d | pointAt (size_t index, double t) const |
Evaluate the position on segment index at parameter t in [0, 1]. | |
| Vector2d | tangentAt (size_t index, double t) const |
Return the un-normalized tangent vector at segment index, parameter t. | |
| Vector2d | normalAt (size_t index, double t) const |
Return the normal vector (perpendicular to the tangent) at segment index, parameter t. | |
| Box2d | strokeMiterBounds (double strokeWidth, double miterLimit) const |
| Compute a bounding box of the path's on-curve points, extended to include miter tips. | |
Serialization | |
| RcString | toSVGPathData () const |
| Serialize this path to its canonical SVG d attribute text. | |
Iteration | |
| template<typename F> | |
| void | forEach (F &&fn) const |
Iterate over path segments, calling fn for each command. | |
| std::vector< Vertex > | vertices () const |
| Returns the vertices of the path as a flat list for marker placement. | |
Static Public Member Functions | |
| static constexpr size_t | pointsPerVerb (Verb verb) |
| Returns the number of points consumed by a given verb. | |
Static Public Attributes | |
| static constexpr double | kLocalFlattenTolerance = 0.25 |
| Curve-flattening tolerance for callers that consume the flattened result in the path's OWN coordinate space, such as hit testing and bounds computation. | |
| static constexpr std::size_t | kMaximumGeometryQueryWork = 1024 * 1024 |
| Maximum command visits and recursive subdivisions in one geometric query. | |
| static constexpr int | kMaximumArcLengthSubdivisionDepth = 19 |
| Maximum zero-based recursion depth used by adaptive arc-length subdivision. | |
| static constexpr int | kMaximumHitTestSubdivisionDepth = 10 |
| Maximum zero-based recursion depth used by cubic hit-test subdivision. | |
| static constexpr int | kMaximumFlattenSubdivisionDepth = 10 |
| Maximum zero-based recursion depth used while flattening one curve. | |
| static constexpr std::size_t | kMaximumMeasuredPathRetainedBytes = 32 * 1024 * 1024 |
| Maximum heap retained by one measured-path arc index. | |
Friends | |
| class | PathBuilder |
| std::ostream & | operator<< (std::ostream &os, Verb verb) |
| Ostream output operator for Verb. | |
| std::ostream & | operator<< (std::ostream &os, const Path &path) |
| Ostream output operator. | |
Conversions | |
| enum class | MonotonicAxis : uint8_t { Y , X } |
| Axis along which toMonotonic splits curves. More... | |
| Path | cubicToQuadratic (double tolerance=0.1) const |
Convert all cubic Bézier curves to quadratic approximations within tolerance. | |
| Path | toMonotonic (MonotonicAxis axis=MonotonicAxis::Y) const |
| Split all curves at the chosen axis's extrema so each segment is monotonic along it. | |
| Path | flatten (double tolerance=0.25) const |
Flatten all curves to line segments within tolerance. | |
| Path | reversed () const |
| Reverse the direction of travel, tracing the same geometry from end to start. | |
| Path | strokeToFill (const StrokeStyle &style, double flattenTolerance) const |
| Convert this path's stroke to a filled outline. | |
Immutable 2D vector path.
Once constructed via PathBuilder, a Path is immutable and thread-safe. Paths are suitable for caching in ECS components (e.g., GPU band data for the Geode renderer).
Supports line segments, quadratic Bézier curves, and cubic Bézier curves.
| struct donner::Path::PointOnPath |
Result of sampling the path at a given arc length distance.
| Class Members | ||
|---|---|---|
| double | angle | Tangent angle in radians (atan2). |
| Vector2d | point | Position on the path. |
| Vector2d | tangent | Un-normalized tangent vector. Measured paths use the limiting direction at a curve endpoint whose derivative is zero. |
| bool | valid = true | False if the distance is negative, non-finite, or exceeds the path length, or if the path has no drawable segments or could not be measured. |
|
strong |
Axis along which toMonotonic splits curves.
| Enumerator | |
|---|---|
| Y | Split at Y-extrema (each segment monotonic in Y) - horizontal-ray banding. |
| X | Split at X-extrema (each segment monotonic in X) - vertical-ray banding. |
|
strong |
Verb types describing how points are connected.
| Path donner::Path::cubicToQuadratic | ( | double | tolerance = 0.1 | ) | const |
Convert all cubic Bézier curves to quadratic approximations within tolerance.
This is critical for the Slug GPU rendering pipeline, where quadratic root-finding in the fragment shader is significantly cheaper than cubic.
| tolerance | Maximum allowed distance between the cubic and its quadratic approximation. Default 0.1 is suitable for text-size content. |
| Path donner::Path::flatten | ( | double | tolerance = 0.25 | ) | const |
Flatten all curves to line segments within tolerance.
Each curve is subdivided at most kMaximumFlattenSubdivisionDepth levels deep, so an extreme curve may deviate from its approximation by more than tolerance.
| tolerance | Maximum distance between the curve and its line approximation. |
|
inline |
Iterate over path segments, calling fn for each command.
The callback receives the verb and a span of the points consumed by that verb:
| fn | Callback invoked for each command. |
| bool donner::Path::isInside | ( | const Vector2d & | point, |
| FillRule | fillRule = FillRule::NonZero ) const |
Returns true if the given point is inside this path's fill region.
Uses a winding-number ray-casting algorithm. Points within 0.1 units of the path boundary are also considered inside. Returns false if the query exceeds its work or subdivision limits.
| point | Point to test. |
| fillRule | Fill rule to use (NonZero or EvenOdd). |
| bool donner::Path::isOnPath | ( | const Vector2d & | point, |
| double | strokeWidth ) const |
Returns true if the given point is within strokeWidth of any path segment.
The distance is compared against the full strokeWidth, not half of it. Returns false if the query exceeds its work or subdivision limits.
| point | Point to test. |
| strokeWidth | Maximum distance from the path that counts as a hit. |
|
nodiscard |
Builds an arc-length index without consuming more than maximumWorkUnits command visits and recursive subdivisions.
Values above kMaximumGeometryQueryWork are clamped to that existing per-query ceiling. If the supplied allowance is exhausted, the returned measurement is invalid and reports the work it consumed.
| maximumWorkUnits | Caller-provided work allowance for this query. |
|
nodiscard |
Bytes needed to reserve the maximum possible segment array before measurement starts.
Callers retaining a MeasuredPath can preflight this base allocation before calling measure(). Returns nullopt if the path has more than kMaximumGeometryQueryWork commands, or if the estimate overflows or exceeds the per-index retained-memory cap.
|
nodiscard |
Conservative retained-byte ceiling for a measurement with the given work allowance.
Includes segment and adaptive arc-sample vector capacity.
| Vector2d donner::Path::normalAt | ( | size_t | index, |
| double | t ) const |
| double donner::Path::pathLength | ( | ) | const |
Compute the total arc length of the path.
Line segments are measured directly. Quadratic Bezier curves are elevated to cubics. Cubic Bezier arc lengths are approximated via recursive subdivision. Returns infinity when the path cannot be measured within its numeric, work, and memory limits.
| Vector2d donner::Path::pointAt | ( | size_t | index, |
| double | t ) const |
Evaluate the position on segment index at parameter t in [0, 1].
| index | Command index. |
| t | Parameter in [0, 1]. |
| PointOnPath donner::Path::pointAtArcLength | ( | double | distance | ) | const |
Sample the path at the given arc length distance from the start.
Returns the position, tangent vector, and tangent angle at that distance. If distance exceeds the total path length, returns the endpoint with valid = false. A negative or non-finite distance, or a path that cannot be measured, also returns valid = false.
| Path donner::Path::reversed | ( | ) | const |
Reverse the direction of travel, tracing the same geometry from end to start.
Subpaths are emitted in reverse order and each is traced backwards, so a distance measured from the start of the result covers the same points as the same distance measured back from the end of the original. A closed subpath stays closed.
The result carries no arc-decomposition grouping: an arc that was expanded into several cubics reverses into ordinary cubics, so marker placement must use the original path.
| Box2d donner::Path::strokeMiterBounds | ( | double | strokeWidth, |
| double | miterLimit ) const |
Compute a bounding box of the path's on-curve points, extended to include miter tips.
The box is not expanded by half the stroke width, and curve control points and extrema are not included. At each join between segments, a miter tip is placed at a distance of strokeWidth / sin(theta / 2) from the join vertex, where theta is the angle between the two segments. The tip is included only when that distance is less than miterLimit and the join is not straight.
| strokeWidth | Width of the stroke. |
| miterLimit | Maximum miter length, compared directly against the tip distance above. |
| Path donner::Path::strokeToFill | ( | const StrokeStyle & | style, |
| double | flattenTolerance ) const |
Convert this path's stroke to a filled outline.
Takes stroke parameters and returns a new closed Path whose fill region represents the area that would be covered by stroking this path with the given style.
The implementation flattens curves to line segments first, then offsets each segment by width/2 perpendicular to the segment direction, applying the specified line join at corners and line cap at open subpath endpoints.
The tolerance is deliberately NOT defaulted. It is expressed in this path's own coordinate space, so the correct value depends on the scale at which the result is consumed: rendering callers must derive it from their device transform (donner::geode::StrokeFlattenToleranceFor), while callers that stay in path-local space (hit testing, bounds) pass kLocalFlattenTolerance. Requiring an explicit argument makes that choice a compile-time obligation for every call site, so a scale-blind stroke cannot be reintroduced by accident.
The result is a union of overlapping, positive-winding pieces and must be consumed with FillRule::NonZero.
| style | Stroke parameters (width, cap, join, miter limit, dash pattern). |
| flattenTolerance | Tolerance for curve flattening, in this path's coordinate space. |
flattenTolerance is not a positive finite number, or when the outline cannot be represented: the aggregate point budget or the dash work budget is exhausted, or a piece's coordinates or corner products do not fit a double. | Vector2d donner::Path::tangentAt | ( | size_t | index, |
| double | t ) const |
Return the un-normalized tangent vector at segment index, parameter t.
The tangent is the first derivative of the curve at t. For degenerate cubic curves where the derivative is zero, the parameter is slightly adjusted and retried.
| index | Command index. |
| t | Parameter in [0, 1]. |
| Path donner::Path::toMonotonic | ( | MonotonicAxis | axis = MonotonicAxis::Y | ) | const |
Split all curves at the chosen axis's extrema so each segment is monotonic along it.
Required for Slug band decomposition - a Y-monotonic curve intersects any horizontal band boundary at most once (horizontal ray); an X-monotonic curve intersects any vertical band boundary at most once (vertical ray, used by Slug dual-ray coverage).
| axis | The axis to make monotonic along (default Y for the horizontal-ray path). |
axis. | RcString donner::Path::toSVGPathData | ( | ) | const |
Serialize this path to its canonical SVG d attribute text.
Commands are emitted using absolute uppercase letters with a single space between parameters. Integers are emitted without a decimal point; fractional values use the shortest round-trippable decimal form (C++20 {} format).
Supported verbs and output format:
Arc commands (PathBuilder::arcTo) are decomposed to cubic Bézier curves by the builder before they reach the Path data model, so they appear as one or more C segments here.
Round-trips with donner::svg::parser::PathParser::Parse.
| Path donner::Path::transformed | ( | const Transform2d & | transform | ) | const |
Returns this path with every point mapped through transform.
An affine transform maps Bézier control points exactly, so the verb sequence is preserved and the result describes the same curves in the target space without flattening.
| transform | Transform applied to every point. |
| std::vector< Vertex > donner::Path::vertices | ( | ) | const |
Returns the vertices of the path as a flat list for marker placement.
Each vertex contains a point on the path and an orientation vector indicating the direction at that point. For vertices at joints between segments, the orientation is interpolated between the outgoing tangent of the previous segment and the incoming tangent of the next.
|
staticconstexpr |
Curve-flattening tolerance for callers that consume the flattened result in the path's OWN coordinate space, such as hit testing and bounds computation.
Rendering code must NOT use this value. A renderer submits geometry in document space and lets the device transform scale it, so a fixed path-local tolerance is magnified by the view scale and turns curves into visible polygons. Renderers derive their tolerance from the device transform instead - see donner::geode::StrokeFlattenToleranceFor.
1.15.0