A Primer on Bézier Curves (2011) | Hacker News Reader

A Primer on Bézier Curves (2011)

pomax.github.io

190 pointsant6n43 comments

Neat site. Unless I missed it, I didn't see a discussion of blossoms, which I've found to be a very nice tool when dealing with Bezier curves. There's a great paper called, "Blossoming : a connect-the-dots approach to splines" by Ramshaw (http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-19.pdf) that discusses these ideas. I've also gained a lot of value out of Goldman's book, "Pyramid Algorithms," (https://books.google.com/books?id=xFuhIl1rb2sC). Finally, it's not a great book, but Prautzsch, Boehm, and Paluszny's book, "Bezier and B-Spline Techniques," (https://www.springer.com/us/book/9783540437611) has the most compact and correct description of triangle Bernstein-Bezier patches that I've seen, so I refer to it when working in higher dimensions.

Sure, but let's be fair: blossoms are "Bezier curves are nice but what if we did something completely different", which isn't really in scope =)

That’s not a fair summary. Blossoms are the same thing, but with a “cleaner” but more abstract mathematical description. They make certain proofs easier, but require a bit more mathematical sophistication for the reader.

Personally I like Ramshaw’s later whitepaper (“On multiplying points: the paired algebras of forms and sites”) even better, I found it yielded some neat insights, but it’s been mostly ignored in the literature. Probably because it’s even more abstract than the blossoming paper, and takes significant amounts of concentrated effort to digest for anyone who isn’t a professional mathematician: http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-169.pdf

"completely" was perhaps a poor choice of word, but insofar as Bezier theory is concerned, blossoms do depart from it quite a bit. It's a great topic (and your links are excellent!) but not something that would likely find its way into the Primer any time soon (although that said, it would be nice to add a "further exploration" section with links to material such as this, so I just filed https://github.com/Pomax/BezierInfo-2/issues/26 and hopefully I can get to that soon)

Thanks for the link to Ramshaw's other paper. I'd not seen that before and I think it'll be very helpful for some work that I occasionally toy with.

As a side note to the parent comment, things like blossoms, polar forms, and sites aren't really introductory material, but it's something that I've found incredibly useful and a tool that I wish more people new about. Beyond graphics, Bezier surfaces have an extremely rich structure of properties that can be exploited and, for me, blossoms were the key to understanding that. For example, by using blossoms, I can force the intersection between two different triangular Bernstein-Bezier patches to be smooth and differentiable up to p-2 derivatives where p is the polynomial order. And, this can be done with linear constraints. See proposition 21.1 in Ramshaw's 1987 paper. There's a litany of other properties as well. Anyway, this is more of a way to say that Bezier curves have important applications in optimal design and other fields outside of computer graphics, but I think that requires using some of the lesser known properties of which blossoms are one tool.

Alright, so most of that was for the parent commentator's benefit, but I'll say thanks again for the link to the other Ramshaw paper. I didn't realize there was a continuation of the original blossoming work and I think the results in that newer paper will be incredibly helpful for me.

Hmm looks like the Bezier equivalent to "the NURBS Book "http://www.springer.com/de/book/9783540615453. Understandable math, good drawings and pseudocode. Great for a medicore developer like me. Now I only need a book "From Bezier to Nurbs and back" and I'm all done.

I remember reading bits of this for a college project. I should buy a copy.

Farin’s book about NURBS is pretty good, http://www.amazon.com/dp/1568810849

Farin’s other CAGD book is probably the best overall survey, and should meet your criterion. http://www.amazon.com/dp/0122490541

Second Farin's books, the CAGD one is great. On an unrelated note, he passed away earlier this year: https://asunow.asu.edu/20160128-life-and-career-gerald-farin...

Whenever I dabble in type design or vector graphics I'm cursing Bézier curves. I do understand them rationally. But I just can't move the control points such that the result is what I want.

It's a pity that Knuth's Metafont curve definition system (with on-curve points) hasn't gotten more attention.

Or Karow's Ikarus software also had something with on-curve points, IIRC.

Look up Raph Levien’s Ph.D thesis about “spiro” curves (a.k.a. cornu or Euler spirals). He not only proposes a pretty neat type of curve to use, which affords some nice UIs, but also does a great job detailing the history of splines, including other types of smooth “minimum energy” curves, IKARUS splines, Hobby splines (used by METAFONT), etc. http://www.levien.com/phd/phd.html

[I’m somewhat surprised that the Pomax page doesn’t have a section about Hobby splines to go with the section about Catmull-Rom splines. Here’s the Stanford tech report describing them http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1047/CS-TR-8... ; Apple’s Pages and Keynote programs now can use Hobby splines for making shapes, https://bosker.wordpress.com/2013/11/13/beyond-bezier-curves... ; the problem I have with Hobby splines is that there are certain types of shapes that are a real pain to create. As long as you want something very smooth it works pretty well, but whenever the Hobby curve isn’t giving you quite the result you want, tweaking it precisely can become really tricky, and you wish you just had full control over the Bézier arms. It could just be that I don’t have enough practice with them though.]

Another type of curve that is very interesting for some applications is a Pythagorean-hodograph curve. These are curves such that the derivative in the X and Y direction are represented by "Pythagorean" polynomials, i.e. the hypotenuse √(x²+y²) is itself a polynomial. This means that the arclength can be precisely computed in closed form, as can mathematically precise offset curves, which makes them great for defining CAM cut paths.

Lots of CAD software uses b-splines, specifically “NURBS”, as the main curve primitive. Some computer animation software uses subdivision surfaces instead. I’ve never been the biggest fan of UIs for manipulating either one. YMMV.

Personally, I think even for using parametric cubic polynomial segments (i.e. for interoperating 1:1 with systems where the main drawing primitive is a cubic Bézier curve), it works a bit better from a UI perspective to specify the (x, y) locations of on-curve points at t = {0.0, 0.25, 0.75, 1.0} in each segment [these points are the extrema of the Chebyshev polynomial of the appropriate degree] and then convert to Bézier basis by multiplying by the appropriate matrix. I haven’t ever seen anyone try to implement such a UI in production software though, only my own little experimental doodles. (Only downside is that makes it slightly trickier to ensure smoothness at the endpoints in cases where that matters. I think this can be worked around with some extra UI effort.)

Free software vector drawing application Inkscape supports these spiro curves in its UI. It is an option you can select for the curves and lines drawing tool.

Yeah. Unfortunately I found Inkscape’s support for them kinda hacky and buggy: it’s clearly a bolted-on afterthought rather than a core part of the design. It also doesn’t support the full set of UI ideas from Levien’s thesis.

But even so, it’s certainly a nice feature to have. Even with some interaction glitches, it’s still in many cases nicer to use than Bézier curves.

FontForge's support for them is better in this regard, IMO.

Raph's thesis is a great piece of work. Having said that, it's worth making clear that the use of Euler Spirals in CAD predates his work. (His thesis is clear about this point.)

In highway design they are known as clothoids.

https://en.wikipedia.org/wiki/Track_transition_curve

I worked as a consultant on a Japanese road design system (Sanei's STRAX Road CAD - still being sold it looks), and clothoids were already well established when I started in 1995.

My coffee table book "The Physics Book", by Clifford A. Pickover, dates practical applications of the clothoid curve back to at least 1901, when an engineer by the name of Edwin C. Prescott received a patent for their use in rollercoaster designs (after discovering the acceleration problems associated with circular loops some 1~2 years prior).

My point was that the use of Euler Spirals (aka clothoids) were ubiquitous in commercial CAD systems for highway design well before Raph Levien's work in fonts. My datapoint of 1995 in Japan certainly would not have been the first, but it does show how widespread their use has been.

I had honestly never heard about Hobby splines. In my day to day exposure to the various programming languages and graphics suites, they simply never came up (as opposed to Catmull-Rom, which is a mainstay of Processing -the language- for instance). I've been in touch with Raph before, and very much enjoy the beauty of Euler spirals, but I've not found the right way to present them in the Primer yet. They can't be perfectly represented by Bezier curves (his phd thesis covers this), so we end up with a section similar to the circle apprximation sections, but then for a type of curve that most people will be unfamiliar with, so it needs a pretty solid description to not feel like a completely new topic "forced" in.

This is understandable, since each control point affects the curve globally it is very difficult to get all the points in the correct position at once, particularly when the curve becomes higher order. Using NURBS is much more intuitive as using a particular knot will allow for specific local control.

In a piecewise Bézier curve, as used in vector graphics tools like Adobe Illustrator or Inkscape, or as the main curve primitive in PostScript, PDF, SVG, font formats, etc., each control point affects only a particular segment. Every shape tends to be made of numerous tiny segments.

NURBS curve can always be converted to piecewise Bézier by repeated knot-insertion. Having said that I too prefer spirals.

Designing with piecewise Bézier curves is just a bad idea.

Piecewise Bézier is a fine representation format once the curve is immutably defined. Bézier curves and surfaces, and the Bernstein Polynomial basis have "excellent numerical stability properties"

http://mae.engr.ucdavis.edu/~farouki/bernstein.pdf

which is just what you need for downstream processing. For example, intersection algorithms in CAD systems.

Edit: I just realised that we are talking about polynomial Bézier curves here (rather than rational Bézier), so what I suggested for converting from NURBS to piecewise Bézier isn't going to work in general.

Farouki’s paper is nice, but the advantages of the Bernstein basis are oversold IMO. In my opinion Chebyshev basis would be a better core representation for nearly every purpose (including rendering efficiency, degree raising / lowering, intersections, computing approximate arclengths, approximation of arbitrary parametric curves, etc.). I’ve been meaning to email Pomax about this for a while, but it’s going to take a somewhat long and involved email, so I keep putting it off.

> But I just can't move the control points such that the result is what I want.

What you probably want is something like Kochanek-Bartels spline [0], which has on-the-curve control points with some extra parameters (tension, continuity, bias) and it gets broken down to Bezier segments.

[0] https://en.wikipedia.org/wiki/Kochanek–Bartels_spline

I'm confused. The splines used in e.g. Inkscape (and Adobe Illustrator) are Bezier splines, right? And they allow local control of direction, with control-points on the spline. Are these also the splines used by SVG?

What exactly is different in the splines of metafont?

Metafont uses Hobby splines. Here’s the paper: http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1047/CS-TR-8...

Yes, in Inkscape the SVG backing what you see in the UI uses Bézier curves. A curving line drawn in Inkscape is an SVG path:

https://developer.mozilla.org/en-US/docs/Web/SVG/Tutorial/Pa...

In Inkscape you can open the XML Editor (from the Edit menu) and see how the object you've drawn is represented in SVG. A simple path with one Bézier curve may look like this:

    d: m 10,20 c 5,-5 15,10 20,5

Sadly a lot of tools make it harder to work with beziers than necessary. Recently I checked half a dozen open source tools - and only a single one allowed locking the tangents at the points connecting 2 bezier curves. That is trivial to code as you just have to ensure the connecting point and the 2 control points before and behind it form a straight line. And without that using beziers is so much harder because that is the only way to have a smooth curve when connecting bezier-segments and fixing that manually is rather annoying.

This animated demo by Jason Davies makes the basics very easy to understand: https://www.jasondavies.com/animated-bezier/

No argument there: if you want an immediate understanding of "how do they work", Jason's site is it. But: if you want to dive a bit deeper, hopefully the Primer covers the rest (and if it doesn't, it's open source on github; comments, questions, and PRs welcome)

Absolutely, the primer has a lot of great info. :) I didn't mean to imply there's any competition between the two; just linking another resource.

Same here - Jason did a great job getting the core idea across, I like to think of his site, http://cubic-bezier.com, and my Primer as a "this should cover all the things you care about" =)

There is a cool algorithm to least-squares fit Bezier curves to a list of points by Philip J. Schneidr, printed in Graphics Gems. Here is a C# version I found on github:

https://github.com/burningmime/curves/blob/master/README.md

For example, you can use it convert scanned bitmapped font edges to curves to create a scalable font.

In the same category of curve ftting, there's also work done by Itoh and Ohno ("A curve fitting algorithm for character fonts", https://pdfs.semanticscholar.org/e8fa/3b676324dc17ce3098ddbc...) that tries to do the same kind of fitting, with fewer segments but slightly higher MSE. If you read graphics gems, you might want to read this, too.

This page really helped me wrap my head around Bezier curves. It's very well done.

One thing, given all the live code on the site, it would be nice to have a live sample where one can select points and a t in [0, 1], and it shows it's coordinate along the line. I implemented a Bezier curve, and had trouble coming up with unit test samples.

unit tests are generally easiest to do with unit curves: (0,0)-(0,1)-(1,1)-(1,0) has well defined coordinates for many t values. t=0.5 -> (1/2,3/4), t=0.25 -> (5/32, 9/16), etc. If you need this for unit testing, hit up http://pomax.github.io/bezierjs instead, open dev tools, type "var b = new Bezier(x1,y1,x2,y2,x3,y3,x4,y4)" with real values of course, and then check the coordinates you get for "b.get(0.5)", "b.get(0.25", etc.

I wish I'd had this when I implemented Bezier curve drawing in 1988.

I have a question. How does one make a perfect circle using Bezier curves?

You can’t. However, if you add enough segments you can get arbitrarily close.

This also holds for straight line segments :)

Indeed. It also holds for points only connected by horizontal or vertical lines. Or even for sets of disconnected points. :-)

However, you need a lot fewer parametric cubic segments than straight lines to get to any desired tolerance.

Reminds me that I did this on a geometry assignment. All shapes were n-gones. Circle = ngon<64>. Here you go.

As per jacob's comment - you can't, http://pomax.github.io/bezierinfo/#circles_cubic covers the "how close do you want to get" part of circle approximation.

As other said it's not possible with polynomial curves, but you can get good approximation.

Only rational curves can form arcs. Wikipedia has a nice explanation https://en.wikipedia.org/wiki/Non-uniform_rational_B-spline#...

Reply on news.ycombinator.com