Computing normals for 3D Bézier curves | Hacker News Reader

Computing normals for 3D Bézier curves

pomax.github.io

74 pointsTheRealPomax19 comments

A small but significant update to the Primer: the section on how to get decent normals in 3D finally makes sense. Previous it only explained how to compute Frenet normals (based on simple, four line maths), but those do _really_ weird things and cause normals to twist violently or even flip from one side of a curve to another... which is pretty useless when you're doing any kind of 3D graphics works.

So I finally managed to get a better approach documented, based on a nice paper on Rotation Minimising Frames, with some textual explanation, some code for the programmers amongst us, and an interactive graphic to show how much better that is compared to Frenet normals.

The midpoint reflection is an interesting way to compute the next frame, I haven’t seen this before. When I’ve implemented rotation minimizing frames, I used a less tricky version: project the previous frame normal & binormal onto the next tangent plane, then renormalize. A friend called this “poor man’s Bishop frames”. (Used in production on some CG movies you may have seen.)

My projection method fails when the tangent turns more than 90 degrees, of course, so adaptive sampling of the curve is required for the general case. I assume that adaptive sampling is still required for the method presented here? Are there some advantages to mirroring around the midpoint’s tangent plane?

It is worth noting that for the Quadratic Bézier curve, the Frenet Frame is a rotation minimizing frame. Frenet & RMF only differ for cubics and higher.

This guide is excellent, BTW, I refer to it all the time. Thank you!

Quite welcome!

Getting a tangent to change that drastically over a small interval is quite hard, except on a cusp, where the curve itself is discontinuous (so anything that happens at the cusp is always going to be wrong). Of course, cusps only occur in planar curves, but you _could_ still run into that. Splitting the curve at the cusp and treating it as two curves, to be joined "however is the most aesthetically pleasing way" is basically your only option.

A shift and renomalization is a very efficient RMF, but can lead to weird things when the projected binormal ends up lying in the plane of curvature. Say, a curve that starts off going up and left/right, then changes direction from left/right to front/back. If we're not framing on small enough intervals, the binormal of a frame on one side of that change projected to the other side of that change will suddenly lie in the plane of curvature, and renormalisation can suddenly be broken.

> Getting a tangent to change that drastically over a small interval is quite hard, except on a cusp, where the curve itself is discontinuous (so anything that happens at the cusp is always going to be wrong)

FWIW, I ran into near cusps with 3D curves immediately in production with hair physics simulations. They don’t happen a lot, but the frames are needed for guide hairs, so popping when frames flip is extremely noticeable, even though they not crazy common.

> Splitting the curve at the cusp and treating it as two curves, to be joined "however is the most aesthetically pleasing way" is basically your only option.

I came up with an adaptive sampling method that can guarantee a step size with no more than a given minimum change of angle. It worked well in my case for CG hair with cubics. (Not published, but happy to describe if you have any interest.)

I’ve also seen a really neat parametric remapping method for quadratics that can precompute all parameter values with an exact constant change of angle for every step.

As long as you have near-cusps rather than real cusps (and to be fair: real planar cusps in 3D are easily avoid by just forcing planar curves to be non-planar during your pre-render pass) simply drastically decreasing the sampling interval over low-radius-of-curvature sections is a perfectly valid approach. It's fast (ish =D) and gets the job done.

I tried much smaller steps, and it never got me there with a reasonable step size. It was a lot less expensive to do adaptive sampling than crank up the step size. Plus, you already know, there’s no guarantee with regular sampling. Near cusps can be arbitrarily small. Production wanted a guarantee, even if things were to run slower. I think adaptive was faster, but their primary concern was to know they wouldn’t have surprises or have to call in support once there were hundreds of hair shots in the pipe.

The other advantage of maximum angle sampling is when calculating arc length of a curve with piecewise approximation.

Anyway, It’s entirely possible that seeing as many very near cusps as we did was because our physics simulation was under constrained or not very good. ;) But for whatever reason, my experience left me with the feeling that they’re common enough to be a serious concern, rather than rare and easily avoidable...

Absolutely, when dollars are on the line, the procedure is always 1: make it work. 2: make it fast. 3: make it nice and write a paper on it. And while step 2 is sometimes optional, step 3 _always_ is =)

If you run into cusps a lot on a hair simulation, that feels like evidence of a bad model, but plenty of good things have been done with bad models so that's hardly an indictment on the process. If your model yields loads of cusps, you need a solution, and this type of RMF is probably a very expensive solution.

While it may be less efficient, it seems like the rotation minimizing frame can be constructed more intuitively with quaternions.

Using Unity's functions, it looks like the rotation for the current point can just be: ``` Q(t) = Quaternion.LookRotation(P(t)-P(t-1), Q(t-1) * Vector3.up); ``` (where Q is the list of rotations and P is the set of Points)

Possible also with the method IQ defines in this article (accumulating aligning delta rotations over the course of the curve): http://iquilezles.org/www/articles/noacos/noacos.htm

I feel like every month I see another article about calculating bezier curves. Are there _that_ many people who are interested in reading about bezier curves?

I remember in 1st grade, not long after having been introduced to numbers by coloring and cutting them out in paper, we were set to draw meshes by systematically connecting inverted points on an angled line using only a straight-edge. The result was a mind-bogglingly curved mesh! Years later I realized we had essentially been constructing quadratic Bézier curves. (But I don't think our teacher knew that, honestly.) https://commons.wikimedia.org/wiki/File:Quadratic_Beziers_in...

My point is that Bézier curves have great bang for the buck. A kid can understand the principle and an adult mathematician/engineer can write a thesis about them. And the curves look equally pretty to both parties. The topic sucks you in!

That's exactly how we constructed a parabola, as an envelope out of straight line segments. Always looked like a curved 3D geo, but was it? Nah

It seems to me that it's a computer analog to bike-shedding[1]. A problem 'easy' enough that people feel comfortable explaining it. Same reason there are lots of articles on linear algebra, FFTs, etc. or even why there are so many static site generators etc. -- they occupy that sweet spot of something useful, not entirely trivial, but not too complex that they reduce their audience.

[With that said, I think this is actually a really nice article, and well-presented.]

[1] https://en.wikipedia.org/wiki/Law_of_triviality

That's... not what bike-shedding means (which the wikipedia article you link to should have made clear).

The "computer equivalent of bike-shedding" would be arguing over indentation style[0] and tabs vs. spaces, or over naming conventions[1].

I'm not sure that the thing you're pointing out has a name, actually, but it also shows up in the form of endlessly reimplemented canonical example apps like todo lists as well as the examples you cited.

A related phenomenon - I think - is Zawinski's law of software envelopment[2], as "reading mail" is the kind of feature that meets the same sweet-spot criteria.

[0] https://en.wikipedia.org/wiki/Indentation_style

[1] https://en.wikipedia.org/wiki/Naming_convention_(programming...

[2] http://www.catb.org/~esr/jargon/html/Z/Zawinskis-Law.html

Ignoring the misunderstanding about what bike-shedding is (already covered in another comment), this seems a misinformed statement: I started this article because there _aren't_ any articles that actually explain Bezier curves for programmers to the degree necessary to actually implement them, and perform common operations with them that make them useful in codebases.

I still see almost no articles in this space: they're all either the (super valuable) jason davies style "here is why they work, it's just linear interpolation!" pages, or very short explanations that give the calculus expression, and then... stop. This in contrast to linear algebra and calculus, which as general maths subjects have an almost countless number of free ebooks, book-sites, college professors putting up slide decks for their entire courses, and researchers making their phd theses and research papers available online.

This is still a niche subject (it's a tiny speck in the Venn diagram of calculus, linear algebra, geometry, and graphics programming), especially as most people don't need to know anything about Bezier curves to _use_ them in things like CSS or Illustrator; you can make them do what you want just by playing with them.

If you need to program with them, though, you have a problem: of course, you can find all the information in this primer if you want to look up 30 different web pages that all cover each section on their own, with disjointed maths notation and level of detail, but that's how you figure out any niche subject in the absence of single page resources like this primer =)

> Are there _that_ many people who are interested in reading about Bézier curves?

That’s how Hacker News works. To make the front page, enough people have to up-vote the article.

I think comments might influence the article ranking too, but I don’t know that. If you’re not interested in this topic, why comment on the article?

As to why there might be a lot of developers on Hacker News interested in Bézier curves, they’re used a lot, and they’re taught a lot. More or less all video games & CG movies ever made use them for animation & modeling. Most fonts in use are defined by Bézier curves. SVG & web animations use Bézier curves. Motion planning and mapping people use them for boundaries & routes. And those are just a few applications.

Heck, I started writing this primer back in 2011 because I needed to understand this stuff myself in the context of implementing font parsers and generators.

I commented on the article because I feel I see this topic come up more frequently than I would expect, and wanted to know if others felt the same way. Do you think that is too far off-topic of a discussion for HN?

No, it's not too far off topic, meta discussions are welcome, especially if you're genuinely curious. (Your phrasing & emphasis made you not sound particularly curious to me, FWIW.) This particular meta discussion, however, is less relevant than the topic of Bezier curves for HN in general. You can't have it both ways.

What good would confirming that some other people feel the same way do? We've already established that the fact people are both submitting and up-voting Bezier articles means that there are enough people interested, relative to other articles. The existence of this article on the front page means that the only thing wrong here is your own expectation that people aren't interested in Bezier curves, right? Personally, I'm pretty sure that some people reading HN don't care about Bezier curves, but I know for a fact that quite a few do, because enough people are posting and bubbling up articles on the topic.

I have no idea what percentage of the HN crowd cares about Bezier curves, but fortunately it doesn't take a majority to get articles on the front page. I love that niche topics come across the front page, that it only takes a handful of interested people. That's exactly why I come to HN.

So, enjoy it and have fun. If you want HN articles to have more things you find interesting, then submit and up-vote the things you care about.

I can't speak for other articles, but my primer usually makes HN maybe once a year, unless I happen to write a new section and get lucky enough on upvotes when I post a link to it myself.

My normal pace of writing new sections is "maybe once every half year", this time I was requested to write about rotation minimising frames less than a month after the previous update, so if you remember seeing this same primer last month: you did indeed, although it was on a completely topic (namely, curve fitting).

Reply on news.ycombinator.com