A Primer on Bézier Curves | Hacker News Reader

A Primer on Bézier Curves

pomax.github.io

398 pointsmabynogy61 comments

I love bezier curves. I'm working on rebuilding a project I started in college, a vector graphics editor. The function for determining intersections between two cubic bezier curves, which I found on a professor's website, is absolutely insane:

https://github.com/artursapek/mondrian/blob/master/src/coffe...

It's a wall of this:

      c11.x*c12.y*c13.x*c13.y*c23.x*c23.y - c11.y*c12.x*c13.x*c13.y*c23.x*c23.y + 6*c21.x*c22.x*c13y3*c23.x +
      3*c11.x*c12.x*c13.x*c13.y*c23y2 + 6*c10.x*c13.x*c13y2*c23.x*c23.y - 3*c11.x*c12.x*c13y2*c23.x*c23.y -
      3*c11.y*c12.y*c13.x*c13.y*c23x2 - 6*c10.y*c13x2*c13.y*c23.x*c23.y - 6*c20.x*c13.x*c13y2*c23.x*c23.y +
      3*c11.y*c12.y*c13x2*c23.x*c23.y - 2*c12.x*c12y2*c13.x*c23.x*c23.y - 6*c21.x*c13.x*c22.x*c13y2*c23.y -
      6*c21.x*c13.x*c13y2*c22.y*c23.x - 6*c13.x*c21.y*c22.x*c13y2*c23.x + 6*c21.x*c13x2*c13.y*c22.y*c23.y +

Maybe there's a way to refactor it, but I wouldn't know because I still don't understand it; I just know that it works.

I'm not sure what that wall does, but the easiest way to find intersections, roots, etc. of Bézier curves is to use their convex-hull property and recursively bisect them. The convex hull property is that the curve is within the convex hull of the control points. So given two Bézier curves, if their convex hulls don't overlap, then they don't intersect. If they do, then split them both in half and see which of those Béziers' convex hulls overlap. Recur until you reach a tolerance, then just approximate the curves by a straight line and find the intersection point (or basically equivalently, just use the average position of the control points, since at that point the line is pretty much straight).

It's not even a complete solution which is roots for a ninth-degree polynomial. Approximation with quadratics is what makes it feasible with some caveats [1].

[1] https://youtu.be/OmfliNQsk88?t=19m7s

What the heck...!?! I would really love for someone to explain how something like this happens.

It happens because the curves are not polynomials in the normal sense. The parameter t that ranges from [0..1] is not the same between the two curves, so it is not equivalent to setting two polynomials equal to each other and solving for x, or t in this case. A solution to the intersection is equivalent to solving for the t parameter of both curves simultaneously and IIRC that ends up having an order that is the product of the orders of the curves (9th order for 2 cubics?). On second thought it's not the product, but it is definitely much higher order. That is the reason people use the matrix representations, once you get a feel for that the complexity tends to get hidden by representing an entire matrix of Nth order polynomials by a letter like B.

If anyone is really interested in this stuff and wants to make a major contribution to open source software... First study these and then move on to NURBS, surfaces, and then trimmed NURBS surfaces. These are the core of all CAD software and a clean library for trimmed NURBS is sorely lacking. There are two that I'm aware of, the one in OpenCascade which is a huge ball of mud (but works) and the one in SolveSpace which doesn't scale well and has some other limitations - that is the one I feel is most worthy of someones time.

There is GoTools (https://github.com/SINTEF-Geometry/GoTools) and SISL (https://github.com/SINTEF-Geometry/SISL). These are open-source geometry libraries for parametric surface modeling, that include NURBS surfaces and intersections and trimmings of such.

Intersections are computed approximatively within some prescribed geometrical tolerance, and intersection curves are "marched out".

Thanks. The links have been forwarded to people who may be interested.

BTW they don't explicitly say "trimmed NURBS" but doing boolean operations implies that is the case ;-)

NLib is the gold standard in closed-source, right?

Disclaimer: I am financially tied to NLib's current distributor.

NLib has a lot of sophisticated NURBS math tools. It was literally written by one of the men who wrote The NURBS Book.

As far as I know, it doesn't do anything much for trimmed NURBS surfaces, in the sense of a surface trimmed by an arbitrary series of curves. (Might be a tessellation routine for that case?) Basically it is mostly geometry, with only very limited topology support.

There are lots of products which provide geometry & topology support: SMLib, SOLIDS++, Acis, and Parasolid come to mind. The first two are built on NLib. I don't think any of them have as sophisticated NURBS geometry tools as NLib does. (Except to the extent that you can call NLib routines directly with the first two.)

I'm not aware of any commercial product which directly competes with NLib at all. Which doesn't mean one doesn't exist! I'd be interested if anyone has experience with other libraries.

No, that would be Parasolid:

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

Look at the list of applications that use it.

Me too. It's constructing some polynomial, but the rest is lost on me.

Looks like what you would get if you wrote out all the operations for matrix multiplication? It must be related to expressing the coordinates of the nodes as matrices.

I would guess the factors of 3 and 6 arise from derivatives of the cubics: x^3 derives to 3x^2 derives to 6x.

The intersection of two NURBS (Non-uniform Rational B-Spline) surfaces has a degree into the hundreds. Those are the surface types used in virtually all CAD modelers. For that reason the intersection is not calculated exactly but approximated to a geometric tolerance. It is harder, mathematically and algorithm-wise to calculate the approximation, but much faster to evaluate afterwards. It's amazing what magic lurks below the surface of even something as simple as "find the intersection of two polynomial functions".

> NURBS (Non-uniform Rational B-Spline)

I believe NURBS stands for Nobody Understands Rational B-Splines [0] :)

[0] http://www.springer.com/productFlyer_978-3-540-61545-3.pdf?S... (pdf)

I had a similar experience looking up algorithms for space-filling curves:

https://www.reddit.com/r/ProgrammerHumor/comments/4xzi9a/oh_...

Same thing when I was looking for Reinsch Spline code it's a mess.

http://stackoverflow.com/questions/5072758/spline-smoothing-...

I converted Algol code from a paper into C because I couldn't find any clean C code on the web but it's still ugly eg. here is a chunk of it:

    for (i=m1; i < m2; i++) //Choleksy Decomposition {(R^T)R of [(Q^T)(D^2)Q + pT]}
           {
               r1[i-1] = f*r[i-1];
               r2[i-2] = g*r[i-2];
               r[i] = 1/(p*b[i]+t[i]-f*r1[i-1]-g*r2[i-2]);
               u[i] = a[i]-r1[i-1]*u[i-1]-r2[i-2]*u[i-2];
               f = p*c[i]+t1[i]-h*r1[i-1];
               g = h;
               h = d[i]*p;
           }

This kind of feels like an export of a WolframAlpha query, exported and written out as code =D

Haha yea that is some straight up Mathematica -> C codegen (damn you //cform). A couple of years ago I inherited a project with a 90 meg .c file that was auto generated by Mathematica... the thing caused GCC to allocate ~4 gigs of ram. Simplifying the math by hand we got it down to a few hundred lines of code, and reduced the build time by three orders of magnitude.

Please, tell me you simplified the math in Mathematica and that you didn't go through the C file manually?

If it's the latter, how did you keep your sanity?

We got a couple of big ass whiteboards and carefully went through the math. Lots of big expressions simplified to zero that Mathematica couldn't see, and we were able to factor out a lot of shared expressions.

hahaha that is amazing!

Pomax (the author) here: for those wondering about what's different since last time this hit HN, this is a slowly-but-surely updating project that has been in the works since 2011. If you remember seeing it before: you're not wrong! But it will probably have been less content or less functionality than it is this time round =)

The latest improvement is that the codebase now supports localization which means that if you're a dual (triple, etc) speaker and you want to help bring this content to people who don't speak English, now you can! Chinese and Japanese localizations are already underway (although it's a volunteer effort, much like the Primer itself, so progress is again steady, but slow) and currently cover the first 10 or so sections.

For more details on the fine points of the build system and how much work it was to overhaul an "everything is assumed to be English, no l10n provisions have been made whatsoever" to "EASY to localize" (not just 'possible to', but 'easy'), hit up http://pomax.github.io/1489108158510/localization-is-hard where I've blogged about the uplift and the tech choices I made.

And on a less impressive note but certainly more useful for social sharing, the social share buttons now actually point to the section you're reading, so that future sections can be shared waaay easier. For the last six years, those things have just pointed to the base article URL and that is not very useful when you want to share the fact that you just read up on how to split a Bézier curve using matrix operations, or want to link to the B-Spline section all the way at the bottom of the Primer.

You're apparently part of the biannual State of SVG days on HN

2017: https://news.ycombinator.com/item?id=14155393

2015: https://news.ycombinator.com/item?id=10678652

2013: https://news.ycombinator.com/item?id=6470908

Haha, that made my day, thanks! (it's only 10am atm, but that'll carry for a few hours yet)

Excuse the pedantry: Biennial is every 2 years ;-)

Additional pedantry: while biennial does exclusively mean "once every two years", biannual is not strictly speaking wrong. However, quite inconveniently, like most "bi-[time span]" words, biannual can mean either twice a year or once every two years.

I actually had it first with biennial, but thought but that would be the word for the event (like the italian Biennale) not the time interval, since it sounded weird as an adjective. Oh the ambivalence; yet listing the years should make the intent obvious.

Also if you use search, there are some more high profile SVG related posts that don't follow that made up pattern.

It's a truly great resource. Have you thought about the Primer for people who are newer to curves? For those unfamiliarized and looking to start adopting beziers, the Primer's layout, length and depth may be off-putting from a learning resource perspective. The layout makes it seem like you have to learn all of the parts in sequence which isn't the case. Depending on a person's use case, it could be that, for example, only 20% is applicable and found in sections 1-3, 17, 20-23, and could be learned without going through all the sections in-between. Someone totally new to beziers wouldn't know where to start making the distinction for which sections apply to them and give up entirely.

My suggestion is, think you could create an "applications of beziers" page which lists common bezier use cases? eg. Draw a curved path. Animate using easing. Animate along a curve. Animate along a curve with an ease. Then link from there to only to the sections you'd need to learn and apply to get to that application? It would be infinitely more helpful to new learners.

The Primer would then remain a great resource as a standalone. And the Applications page would be a great navigation and learning resource page for people looking to start.

An interesting idea... hit up the github repo and we can discuss this idea in an issue - HN comments tend to easily get lost.

I used this as a resource when I was studying geometric modelling, since your page was way more understandable than our course notes (http://www.uio.no/studier/emner/matnat/math/MAT-INF4160/h15/...). It definitely helped with my comprehension and passing the course. So, thank you!

Feature request: please expand the spline section or make a similar, separate primer on splines.

Aw, that's awesome. I mean, not awesome that the course notes were inaccessible but if the material helped you pass a course, that's fantastic =)

Very nice article! I've been willing to delve into Bézier curves for a while now, and this looks like an awesome reference to start.

I'd just like to make an annoying mathematician comment on the beginning (paragraph 3): you might want to point out that the first definition you give of Bézier(n,t) is, for any n and t, nothing else than the constant function 1 (that, by the way, is an absolutely fine polynomial, unlike the statement above that if f(x) has no x then it's not a polynomial).

You can see this by noting that it's nothing else than $((1-t)\cdot t)^n = 1^n = 1$. If you insist on being fancy, you can say that the i-th term in the sum is the probability of a discrete random variable X with binomial law being equal to i, so the sum over all i must be 1 (here the binomial law has parameters (n,t)).

By the way, this last thing has the nice interpretation that each point of the Bézier curve is just the expected value of $p(X)$, where $p(0), \dots, p(n)$ are the points you are interpolating - by changing t you are just changing the parameter of the random variable.

This depends on which definitions you work with. If you consider polynomials "any expression of \sum^n_{i=0}(c_i x^i) then sure, setting n=0 gets you "a polynomial that is a constant function". If you take polynomials to be "functions that are expressions of weighted terms" then constant functions are out, and the set of functions described by the previous summation contains, but is itself larger than, the set of possible polynomials.

BTW, since you mention the Catmull-Rom spline later on, it might be worth-while to mention it is proven that only centripetal CR splines will never form cusps and self-intersections:

> In this paper we prove that, for cubic Catmull-Rom curves, centripetal parameterization is the only parameterization in this family that guarantees that the curves do not form cusps or self-intersections within curve segments.

http://www.cemyuksel.com/research/catmullrom_param/catmullro...

(speaking as someone who gets slightly twitchy whenever he sees interpolated animations go bad)

Please file this over on the repo - since we're dealing with CR/Bezier equivalence, there's technically nothing wrong with the fact that a CR spline might have a cusp if the corresponding Bezier does, too.

True, it is not a technical bug, but it can be a visual one that the artist did not intend to have ;)

It never fully clicked for me until I saw it animated https://www.jasondavies.com/animated-bezier/

I've got a few other references on Bezier curves, including a link to a previous HN conversation:

https://github.com/melling/ComputerGraphics/blob/master/bezi...

And the cool thing is that this animation is actually in the article! (not the exact animation but the same conceptual animation, and you can move your mouse left or right and walk it forward and backward)

I never thought to seek out animations for it.

That makes them a hell of a lot more intuitive for imagining "how will my modifications affect the curve?"

Thanks for sharing.

Likewise, I always find an animation when I need to explain it to someone. A great example of an intuitive understanding of a tricky problem.

This is a really good article! It was thanks to this (and the Wikipedia page) that I managed to write code[1] for drawing evenly-spaced letters along the curve. The letters are even rotated to match the curve, all thanks to this article. It's basically a one-stop shop for all things Bezier :)

[1] In Racket, here: https://github.com/piotrklibert/curved-text

Always happy to hear the primer made a difference in someone's life =)

  > They're named after Pierre Bézier . . . publishing his investigations in 1962

  > One might be tempted to say that the mathematician Paul de Casteljau was first,
  investigating the nature of these curves in 1959

  > Bézier curves are, at their core, "Bernstein polynomials", 
  a family of mathematical functions investigated by Sergei Natanovich Bernstein,
  with publications on them at least as far back as 1912.

I see many stories like this, which shatter the idea of a lone inventor bringing something new out of thin air.

Hmm, I don't think anyone who actually learned even a modicum of maths history holds that idea, though. Where were you made to believe the idea of one person coming up with complete solutions all on their own?

Pierre Béziers, in addition to being a great mathematician and engineer, was a great teacher (including when he was ranting about us, youngsters, not being able to solve "simple" mechanical problems !) It's good to see people investing such effort to make it easy to understand and available to everyone

I used this resource about six months ago as a refresher so I could build bezier splines[1] for character pathing while I was learning Unity. It is probably the best resource out there for this.(Outside of game engine specific information.)

1: http://i.imgur.com/8pWMTZS.png

2: https://vid.me/GMso

Oh that's cool - it's always great to see the primer having helped in making a thing!

Look at the archives, this link has been doing the rounds for at least 6 years now.

That makes it especially impressive that he used React and other recent Web technologies to build the site.

(It's been around a while but this is a rewrite and looks like a pretty massive update)

My day job is web techs, so I've been slowly upgrading this article ever since I turned it into a "real page" in 2011. The latest part (that got done after the last time this hit HN) is localization support, so there are now Chinese and Japanese translations for the first 10ish sections, and a relatively clean way to translate entire sections at a time (each section is now an .md file that gets transpiled to a JSX component, before bundling kicks in. It's nifty)

Good on you for keeping it up to date. This page is extremely dense with information and clearly has cost you a lot of your time.

The link has, the content hasn't: it's always growing, even if not at a terribly fast pace =)

I was expecting another superficial article with some interactive graphs but this is a lot deeper with handy formulas for various flavors and uses of Bézier curves. Worth a bookmark!

Lovely explanation, I always find them fascinating. I really need to get around to coding some of them sometimes, but I find most of the itnerest in the mathetics.

That said, early higheschoolers knows jack about binomials unless they are particularly smart. I would venture a majority of college students (in subjects other than engineering and science) would find this too daunting. I think by downplaying the complexity it actually turns people off from trying to learn. Which of course is a shame.

> In fact, they even need this for straight lines, but the function is ridiculously easy, so we tend to ignore that as far as computers are concerned

Well.... If it was so easy, why does the algorithm have a name? (Bresenham's algorithm), if it's named surely it must've been "invented" at some point, implying it wasn't as easy?

Bresenham's algorithm is for rasterization, and I think the article refers to the function f(t) -> (x,y), which is just a linear interpolation in 2D.

Plus Bresenham is for doing things just using integer math, with floats rasterizing a line is little more than straightforward linear interpolation.

Easy or hard are always relative terms. I think in this case the author means easy or hard relative to the status quo.

I think I used an earlier version of the section of splitting bezier curves to do the opposite: Combining two bezier curves in SVG (probably they were split at some point before by the outputting program).

This came in very handy for me on one of my side projects, specifically finding intersections between curves. Excellent content.

Reply on news.ycombinator.com