Flattening Bézier Curves and Arcs | Hacker News Reader

Flattening Bézier Curves and Arcs

minus-ze.ro

89 pointsvg_head18 comments

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.

[1]: https://docs.rs/kurbo/latest/kurbo/struct.BezPath.html#metho...

Thank you! Looking forward to your research.

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?

It's... ok.

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...

Thanks for point out kurbo.

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.

late to the fray, but thanks for posting this!

"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!

I will never understand this

Do you have a need to?

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)

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.

For bezier curves in Python try this:

    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.

If you're into this kind of geometry, and CNC, we could use some more eyeballs on Solvespace. I'd like better g-code generation.

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.

Try this link: https://blog.richardekwonye.com/bezier-curves

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.

Try https://pomax.github.io/bezierinfo/

I also learned from this one which I think is simpler but not as detailed

https://webglfundamentals.org/webgl/lessons/webgl-3d-geometr...

Reply on news.ycombinator.com