Flattening Bézier Curves and Arcs(minus-ze.ro) |
Flattening Bézier Curves and Arcs(minus-ze.ro) |
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)
))
Another question(s): What is your opinion of Sederberg's CAGD publication? Has that publication had tangible mapping to your API designs? If so, what percentage of that publication (in your opinion) would be exposed as API in an ideal CAGD API?
I'm sure there's an art to what should be in an API and I have limited understanding of how the math maps to actual needed implementation.
I was also able to do this in OpenScad. The technique is the same. I was 3d printing a router template for rounding off corners of tables that used splines like this so it wasn't as obvious where the corners started and ended. I think ~40 points was accurate enough for me, but I was hitting the corner with sandpaper afterwards.
Like I said, arcs are next (once I finish a re-write as a "Literate Program", 'cause managing stuff spread across three files has gotten to be a pain. I'm going to try the docmfp package as something straight-forward enough for me to wrap my mind around and which I can use on pretty much any computer I'm inclined to.