sysprog21 / mado

A window system for resource-constrained devices
MIT License
38 stars 13 forks source link

Improve spline decomposition #2

Open jserv opened 3 months ago

jserv commented 3 months ago

The usual method to convert a spline into a sequence of line segments is to split the spline in half using de Casteljau's algorithm recursively until the spline can be approximated by a straight line within a defined tolerance. The commit 6d85b4280db3288485c9261b512ec1640697a678 has already changed the original recursion to an iterative method, avoiding unbounded recursion. Four levels of recursion will consume more than 64 coordinates' worth of space, which can easily overflow the stack of a tiny machine. However, as Keith mentioned in Slightly Better Iterative Spline Decomposition, it is possible to make the overall computational cost lower than a straightforward binary decomposition, and no recursion is required.

See also: Decomposing Splines Without Recursion

jserv commented 3 months ago

The font-edit is not only useful for observing how font rendering works but also serves as a testbed for evaluating the enhancement of iterative spline decomposition, where you can operate with floating point arithmetic instead of fixed-point arithmetic.

font-edit
jouae commented 3 months ago

Here are two books that might be helpful:

A Primer on Bézier Curves This book gives some interactive content can visually aid in understanding the significance of parameters.

Computer Aided Geometric Design Discussing curve interpolation with rigorous mathematical exposition.

In the second book 10.6 Error Bounds,

We can assure that the approximation error will be less than a specified tolerance $\epsilon$ by using $m$ line segments whose endpoints are evenly spaced in $x$, where $m\geq \sqrt{\frac{L}{8\epsilon}}(x_1-x_0)$

jouae commented 1 month ago

Another feasible interpolation method is called the Euler spiral. According to @weihsinyeh's notes, the Google team adopted the Euler spiral in their paper titled "GPU-friendly Stroke Expansion," published in the Proceedings of the ACM on Computer Graphics and Interactive Techniques in 2024.

Raphael Linus Levien's work, From Spiral to Spline: Optimal Techniques in Interactive Curve Design, provides a detailed description of the characteristics of the curve, covering both its physical and mathematical aspects, as well as its application in font rendering.