Cool to see! The tweak suggested in the blog post when you're near the vertex of the parabola is valid, and the implementation that was in Vello did something very similar. This is also the flatten algorithm that's in kurbo[1], and the code for that is probably the most accessible source for the ideas. However, if approaching this again I'd suggest placing a subdivision point at the vertex, which will also handle the degenerate colinear case; I now have reason to believe that the error metric that all this is based on works for monotonic curvature, and can fail otherwise.
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.
The OP had perfect timing as I was scratching my head on how to implement click hit-testing a bezier. Flattening and then hit testing the segments in parallel is exactly what I was looking for, as it should be fast and I already implemented hit-testing line segments with stroke/margin-of-error expansion.
Aside from seeming like a good solution, would you go that route?
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.
"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.
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:
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)
That'll compute a point along your bezier curve. The `t` parameter is how far along the curve you want to go, 0 <= t <= 1. You can give it as many dimensions and whatever order (number of handles) you want. So for example, to get a cubic bezier curve on a 2d plane from (0, 0) to (1, 1) with handles at (1, 0), (0, 1) (an aggressive ease-in/ease-out curve) with 9 segments (10 points) you'd run:
n = 10
for t in range(n):
print(
bezier(
t / (n - 1),
(0, 0),
(1, 0),
(0, 1),
(1, 1)
))
I think that's right. I did it from memory. Obviously don't mix 2d and 3d, but it should work if all points have the same number of dimensions.
Oh, there is no guarantee about the spacing of these points. They won't be equidistant from each other, the points may cluster towards one end of the curve or another. With an infinite number of points you'll get the correct curve, but experiment with it to determine how finite you're willing to go.
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.
Thanks! I'll definitely give that a go when I get to that point.
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.
Nice project! I see the tool can already handle polylines, so in theory you should be able to add support for Bézier curves and arcs by converting them to polylines. But of course, the devil is usually in the details. I hope it works out.
Yes, the details have gotten so niggling that I've decided it's time for a re-write as a "Literate Program" as noted elsethread. I'll be using the docmfp package which I think will keep the complexity manageable, we'll see.
I've tried Solvespace a couple of times, but haven't done well with it --- I wish that it was scriptable and that there was some sort of support for Bézier curves --- please feel free to make use of any of my code/concepts, but it's a pretty small codebase (and weird to boot) and I doubt anything which is helpful couldn't be coded up by someone else about as quickly as they could read through my code to repurpose it.
Having spent some time wrestling cubic beziers just last week, I must say A Primer on Bezier Curves (referenced in TFA) is an approachable and genuinely useful work, even to the functionally math illiterate like myself.
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...