First cut at least-squares offset curves #427

raphlinus · 2025-03-19T01:51:12Z

Replace the quartic solver with the new least-squares one.

The robustness story is not complete. For now, it relies on the existing "regularize" hack, but it would be better to be robust by construction.

The stroke options are not respected. It tries to do a better job with subdivision but does not attempt an absolutely minimal number of segments as before. That could be re-added.

The old offset methods are still exported. They should probably be deprecated.

Progress toward #317

Replace the quartic solver with the new least-squares one. The robustness story is not complete. For now, it relies on the existing "regularize" hack, but it would be better to be robust by construction. The stroke options are not respected. It tries to do a better job with subdivision but does not attempt an absolutely minimal number of segments as before. That could be re-added. The old offset methods are still exported. They should probably be deprecated. Progress toward #317

tomcur

Some initial observations inline based on a first dive into this.

tomcur · 2025-04-03T14:36:14Z

src/offset.rs

+    tolerance: f64,
+}
+
+// We never let cusp values haven an absolute value smaller than


Suggested change

// We never let cusp values haven an absolute value smaller than

// We never let cusp values have an absolute value smaller than

tomcur · 2025-04-06T10:27:33Z

src/offset.rs

+            let a_n = 3.0 * mt * t * mt * rec.utan0.dot(n);
+            let a_t = 3.0 * mt * t * mt * rec.utan0.cross(n);
+            let b_n = 3.0 * mt * t * t * rec.utan1.dot(n);
+            let b_t = 3.0 * mt * t * t * rec.utan1.cross(n);


On x86 it may be very slightly faster to group the squarings here: https://godbolt.org/z/b1xa96Kff

let a_n = 3.0 * (mt * mt) * t * rec.utan0.dot(n);

tomcur · 2025-04-08T08:44:08Z

src/stroke.rs

 pub fn stroke(
    path: impl IntoIterator<Item = PathEl>,
    style: &Stroke,
-    opts: &StrokeOpts,
+    _opts: &StrokeOpts,
    tolerance: f64,
 ) -> BezPath {


As an API change (not for this PR), we could consider taking &mut BezPath here, allowing reusing the allocation.

tomcur · 2025-04-08T12:37:44Z

src/offset.rs

+        ((self.c2 * t + self.c1) * t + self.c0) / (ds2 * ds2.sqrt()) + 1.0
+    }
+
+    /// Compute cusp and unit tangent of endpoint.


Suggested change

/// Compute cusp and unit tangent of endpoint.

/// Compute cusp and unit tangent of endpoint.

///

/// See [`Self::cusp_sign`] for the meaning of the cusp calculation.

tomcur · 2025-04-08T12:57:32Z

src/offset.rs

+    // Compute a function which has a zero-crossing at cusps, and is
+    // positive at low curvatures on the source curve.


An explanation here could be helpful. It took me some reading of some curve properties (one, two) to come to (what I hope is) the right explanation. (As a minor observation relative to the equations given on Wikipedia, IIUC, we calculate negative curvature here due to the order of the cross product, which cancels out with another negative in the "cusp" calculation.)

Suggested change

// Compute a function which has a zero-crossing at cusps, and is

// positive at low curvatures on the source curve.

/// Compute a function which has a zero-crossing at cusps on the parallel curve,

/// and is positive at low curvatures on the source curve.

///

/// This is based on the geometric property that given a source curve with

/// a curvature of `k(t)`, the parallel curve at an offset `d/2` potentially

/// has a cusp when `1 + d/2 k(t) = 0`.

///

/// Note that given a curve `c(t)`, its signed curvature is

/// `k(t) = c''(t) x c'(t) / ||c'(t)||^3`. This is encoded (including the distance

/// offset) in `c0`, `c1` and `c2`.

Basically right, but I have a couple of nits. First, it doesn't "potentially" have a cusp, I think it's fair to say that when the curvature is equal to reciprocal half-width, there is a cusp. Second, the "this" in "this is encoded" is an unclear referent, I'd say, "the cross product is a quadratic polynomial, and c0, c1, and c2 encode its coefficients."

I don't generally carefully work out sign conventions, I just make it come out right. That's something that potentially can be cleaned up.

tomcur · 2025-04-09T12:34:27Z

src/offset.rs

+        let mut max_err = 0.0;
+        for (i, t) in ts.iter_mut().enumerate() {
+            let mut ta = *t;
+            // TODO: probably should also store in rec, we always need this


Is this a vestigial TODO?

tomcur · 2025-04-09T13:40:55Z

src/offset.rs

+    }
+
+    fn apply(&self, rec: &OffsetRec, a: f64, b: f64) -> CubicBez {
+        // wondering if p0 and p3 should be in rec


That would also prevent the doubling of those calculations for the midpoint when subdividing.

> [!NOTE] > The measurements in this PR were done very rough via a quick Chrome profile. Because the numbers are small, until we run a rigorous benchmark it'll be hard to validate the impact. Especially across browser engines, and with JS engines optimising WASM and fusing operators. ## Overview This PR adds initial WASM SIMD support to `fearless_simd`, implementing enough operations to enable WASM S 8000 IMD in linebender/vello#1053. Rather than implementing all operations in one large PR, this focuses on the essential subset needed for Vello and breaks up an otherwise huge change. There's also some tricky operations to implement using the small amount of WASM instructions 😅 . ## Performance Impact Tested with Ghost Tiger rendering in Vello: ### Without fast kurbo (baseline): - **Without SIMD**: ~42.31ms per frame - **With SIMD**: ~39.91ms per frame - **Improvement**: ~5% faster ### With fast kurbo (linebender/kurbo#427): - **Without SIMD**: ~6ms per frame - **With SIMD**: ~4ms per frame - **Improvement**: ~30% faster (Take this with a huge grain of salt) *Test methodology: I linked `vello` locally to `fearless_simd` via `path` reference, and modified `vello_hybrid` to use the WASM SIMD level.* ## Changes - **New architecture**: Added WASM SIMD128 support - **Operations implemented**: Core subset including: - Binary ops: `add`, `sub`, `mul`, `min`, `max` - Comparison ops: `simd_eq`, `simd_ne`, `simd_lt`, etc. - Math ops: `sqrt`, `madd` - **Testing**: Added parity tests ensuring Fallback and WASM SIMD produce identical results - **Bug fix**: Fixed incorrect mask generation in Fallback comparison operations (was returning `0/1` instead of `0/-1`) ## Test Plan Added `test_wasm_simd_parity!` macro that verifies operations produce identical results across Fallback and WASM SIMD implementations. I only tested a small subset. Maybe in the future we code-gen the tests as well? ## Next Steps Future PRs will add more operations to achieve full WASM SIMD coverage.

Instead of linearized least error, which can generate incorrect approximations (especially in near-cusp situations), use arc drawing. Also make error evaluation more robust, specifically to reject non-finite solutions. Sample points are equally spaced on the approximation rather than on the source curve. Thus, the Newton step refines t values on the source curve. The error report is expanded so that intermediate results can be reused in least square error refinement, as an optimization.

Subdivide by integral of absolute curvature, which should improve near-cusp behavior. I'm trying to make the core algorithm so robust it generates correct results even without the regularization step. However, that approach is not looking especially promising. A major sticking point is that it's difficult to ensure that both sides make consistent decisions. Also adds a stroke example adapted from Vello "tricky strokes", which in turn is adapted from Skia.

Use existing methods rather than doing rotation by hand. Fix typo.

LaurenzV · 2025-06-26T12:17:00Z

See my Zulip message for two suggestions for performance improvements: https://xi.zulipchat.com/#narrow/channel/260979-kurbo/topic/New.20stroker.20for.20sparse.20strips/near/525882812

raphlinus marked this pull request as ready for review March 20, 2025 14:13

tomcur reviewed Apr 8, 2025

View reviewed changes

tomcur reviewed Apr 9, 2025

View reviewed changes

LaurenzV mentioned this pull request May 4, 2025

Low framerate with vello_hybrid_winit example linebender/vello#955

Open

ajakubowicz-canva mentioned this pull request Jun 18, 2025

Add initial WASM SIMD128 support raphlinus/fearless_simd#8

Merged

raphlinus added 4 commits June 18, 2025 18:39

Merge branch 'main' into fast_stroke

b1d804f

Minor cleanup

4ecf72d

Use existing methods rather than doing rotation by hand. Fix typo.

Use temporary path for result

08d784c

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

First cut at least-squares offset curves #427

First cut at least-squares offset curves #427

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

	// We never let cusp values haven an absolute value smaller than
	// We never let cusp values have an absolute value smaller than

		// Compute a function which has a zero-crossing at cusps, and is
		// positive at low curvatures on the source curve.

-    // Compute a function which has a zero-crossing at cusps, and is
-    // positive at low curvatures on the source curve.
+    /// Compute a function which has a zero-crossing at cusps on the parallel curve,
+    /// and is positive at low curvatures on the source curve.
+    ///
+    /// This is based on the geometric property that given a source curve with
+    /// a curvature of `k(t)`, the parallel curve at an offset `d/2` potentially
+    /// has a cusp when `1 + d/2 k(t) = 0`.
+    ///
+    /// Note that given a curve `c(t)`, its signed curvature is
+    /// `k(t) = c''(t) x c'(t) / ||c'(t)||^3`. This is encoded (including the distance
+    /// offset) in `c0`, `c1` and `c2`.

First cut at least-squares offset curves #427

Are you sure you want to change the base?

First cut at least-squares offset curves #427

Conversation

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!