I say "was" as the new version in Vello is much more sophisticated, and handles both flattening and stroke expansion, all on the GPU. A paper is in the works, and I'll post it to HN when it's ready.
[1]: https://docs.rs/kurbo/latest/kurbo/struct.BezPath.html#metho...
Aside from seeming like a good solution, would you go that route?
What kurbo does is lower to quadratic Béziers[1], then the analytic solution to nearest for a quadratic Bézier is the solution to a cubic equation[2].
I'm not sure this is the best possible answer, but it's at least pretty good, and certainly better than flattening to lines.
And I'd like for people to get in the habit of checking kurbo; the intent is for it to always have the best in class algorithm.
[1]: https://docs.rs/kurbo/latest/src/kurbo/cubicbez.rs.html#647-...
[2]: https://docs.rs/kurbo/latest/src/kurbo/quadbez.rs.html#297-3...
"in the old days", books on computer graphics used to be full on "rasterization" techniques - how to convert high-level shapes, whether lines, polygons, circles/ellipses or other curves to pixels, minimising errors while maximising speed.
Much of that has gone out in favour of "engines" - how to program shaders to do transforms of all sorts.
While the latter is a big part of what "makes cool graphics cool", it also leaves a gap ... that "immediacy" between the image/shape and the discrete representation in memory is gone.
Nice to see you're still happy to lift the curtain on it!
The animations make it very intuitive to understand what's happening. Once you get that it's trivial to turn that into a parametric formula (`x(t)` and `y(t)`, not `f(x)`) to calculate all the points along the curve.
Start by understanding quadratic beziers, they're pretty straightforward. Then when you move to cubic ones realize that it's just adding one more level of interpolation.
The hurdle for me was realizing that it's impossible to calculate the corresponding y position given the x position for all 2d curves, because there may be multiple y positions. Instead think of it as little steps that get you from the beginning to the end.
I also learned from this one which I think is simpler but not as detailed
https://webglfundamentals.org/webgl/lessons/webgl-3d-geometr...
Do you have a project which might be able to make use of this? What sort of work do you do?
I am bookmarking this for re-reading later because I hope it will help me to understand how to implement Bézier curves in a tool I've been working on for controlling a CNC machine/creating files for cutting on a CNC:
https://github.com/WillAdams/gcodepreview
(but first I have to get arcs working)
def bezier(t, *points):
if len(points) <= 1:
return points[0]
next_set = []
for i in range(1, len(points)):
next_set.append([p[0] + t * (p[1] - p[0]) for p in zip(points[i - 1], points[i])])
return bezier(t, *next_set)
n = 10
for t in range(n):
print(
bezier(
t / (n - 1),
(0, 0),
(1, 0),
(0, 1),
(1, 1)
))