Struct CubicOffset 

struct CubicOffset {
    c: CubicBez,
    q: QuadBez,
    d: f64,
    c0: f64,
    c1: f64,
    c2: f64,
    tolerance: f64,
}

State used for computing an offset curve of a single cubic.

Fields

c: CubicBez

The cubic being offset. This has been regularized.

q: QuadBez

The derivative of c.

d: f64

The offset distance (same as the argument).

c0: f64

c0 + c1 t + c2 t^2 is the cross product of second and first derivatives of the underlying cubic, multiplied by the offset. This is used for computing cusps on the offset curve.

Note that given a curve c(t), its signed curvature is c''(t) x c'(t) / ||c'(t)||^3. See also Self::cusp_sign.

c1: f64

c2: f64

tolerance: f64

The tolerance (same as the argument).

Implementations

impl CubicOffset

fn new(c: CubicBez, d: f64, tolerance: f64) -> Self

Create a new curve from Bézier segment and offset.

fn cusp_sign(&self, t: f64) -> f64

Compute curvature of the source curve times offset plus 1.

This quantity is called “cusp” because cusps appear in the offset curve where this value crosses zero. This is based on the geometric property that the offset curve has a cusp when the radius of curvature of the source curve is equal to the offset curve’s distance.

Note: there is a potential division by zero when the derivative vanishes. We avoid doing so for interior points by regularizing the cubic beforehand. We avoid doing so for endpoints by calling endpoint_cusp instead.

fn endpoint_cusp(&self, tan: Point, y: f64) -> f64

Compute cusp value of endpoint.

This is a special case of Self::cusp_sign. For the start point, tan should be the start point tangent and y should be c0. For the end point, tan should be the end point tangent and y should be c0 + c1 + c2.

This is just evaluating the polynomial at t=0 and t=1.

See Self::cusp_sign for a description of what “cusp value” means.

fn offset_rec(&self, rec: &OffsetRec, result: &mut BezPath)

Primary entry point for recursive subdivision.

At a high level, this method determines whether subdivision is necessary. If so, it determines a subdivision point and then recursively calls itself on both subdivisions. If not, it computes a single cubic Bézier to approximate the offset curve, and appends it to result.

fn subdivide( &self, rec: &OffsetRec, result: &mut BezPath, t: f64, utan_t: Vec2, cusp_t_minus: f64, cusp_t_plus: f64, )

Recursively subdivide.

In the case of subdividing at a cusp, the cusp value at the subdivision point is mathematically zero, but in those cases we treat it as a signed infinitesimal value representing the values at t minus epsilon and t plus epsilon.

Note that unit tangents are passed down explicitly. In the general case, they are equal to the derivative (evaluated at that t value) normalized to unit length, but in cases where the derivative is near-zero, they are computed more robustly.

fn apply(&self, rec: &OffsetRec, a: f64, b: f64) -> CubicBez

Convert from (a, b) parameter space to the approximate cubic Bézier.

The offset approximation can be considered B(t) + d * D(t), where D(t) is roughly a unit vector in the direction of the unit normal of the source curve. (The word “roughly” is appropriate because transverse error may cancel out normal error, resulting in a lower error than either alone). The endpoints of D(t) must be the unit normals of the source curve, and the endpoint tangents of D(t) must tangent to the endpoint tangents of the source curve, to ensure G1 continuity.

The (a, b) parameters refer to the magnitude of the vector from the endpoint to the corresponding control point in D(t), the direction being determined by the unit tangent.

When the candidate solution would lead to negative distance from the endpoint to the control point, that distance is clamped to zero. Otherwise such solutions should be considered invalid, and have the unpleasant property of sometimes passing error tolerance checks.

fn draw_arc(&self, rec: &OffsetRec) -> (f64, f64)

Compute arc approximation.

This is called “arc drawing” because if we just look at the delta vector, it describes an arc from the initial unit normal to the final unit normal, with “as smooth as possible” parametrization. This approximation is not necessarily great, but is very robust, and in particular, accuracy does not degrade for J shaped near-cusp source curves or when the offset distance is large (with respect to the source curve arc length).

It is a pretty good approximation overall and has very clean O(n^4) scaling. Its worst performance is on curves with a large cubic component, where it undershoots. The theory is that the least squares refinement improves those cases.

fn eval_err( &self, rec: &OffsetRec, c_approx: CubicBez, ts: &mut [f64; 8], ) -> ErrEval

Evaluate error and also refine t values.

Returns evaluation of error including error vectors and (squared) maximum error.

The vector of t values represents points on the source curve; the logic here is a Newton step to bring those points closer to the normal ray of the approximation.

fn refine_least_squares( &self, rec: &OffsetRec, a: f64, b: f64, err: &ErrEval, ) -> (f64, f64)

Refine an approximation, minimizing least squares error.

Compute the approximation that minimizes least squares error, based on the given error evaluation.

The effectiveness of this refinement varies. Basically, if the curve has a large cubic component, then the arc drawing will undershoot systematically and this refinement will reduce error considerably. In other cases, it will eventually converge to a local minimum, but convergence is slow.

The BLEND parameter controls a tradeoff between robustness and speed of convergence. In the happy case, convergence is fast and not very sensitive to this parameter. If the parameter is too small, then in near-parabola cases the determinant will be small and the result not numerically stable.

A value of 1.0 for BLEND corresponds to essentially the Hoschek method, minimizing Euclidean distance (which tends to over-anchor on the given t values). A value of 0 would minimize the dot product of error wrt the normal vector, ignoring the cross product component.

A possible future direction would be to tune the parameter adaptively.

fn find_subdivision_point(&self, rec: &OffsetRec) -> SubdivisionPoint

Decide where to subdivide when error is exceeded.

For curves not containing an inflection point, subdivide at the tangent bisecting the endpoint tangents. The logic is that for a near cusp in the source curve, you want the subdivided sections to be approximately circular arcs with progressively smaller angles.

When there is an inflection point (or, more specifically, when the curve crosses its chord), bisecting the angle can lead to very lopsided arc lengths, so just subdivide by t in that case.

fn subdivide_for_tangent( &self, utan0: Vec2, t0: f64, t1: f64, tan: Vec2, force: bool, ) -> Option<SubdivisionPoint>

Find a subdivision point, given a tangent vector.

When subdividing by bisecting the angle (or, more generally, subdividing by the L1 norm of curvature when there are inflection points), we find the subdivision point by solving for the tangent matching, specifically the cross-product of the tangent and the curve’s derivative being zero. For internal cusps, subdividing near the cusp is a good thing, but there is still a robustness concern for vanishing derivative at the endpoints.