The Continuity of Splines [video](youtube.com)
youtube.com
The Continuity of Splines [video]
https://www.youtube.com/watch?v=jvPPXbo87ds
42 comments
As the author of [2], I strongly recommend everyone watch Freya's video summary of Bezier curves in addition to this tour de force. They're both authoritative works.
Seconded. A lot of the video runtime is covering fairly well known topics, but there are moments of brilliance, where it made things "click" for me. The treatment of the characteristic matrix and how the same matrix can derive both t and point parameterizations was particularly insightful.
Indeed, there were a number of places where I had that "...this never occurred to me, this is fantastic" moment, too.
Great video.
One fun basis for 3rd degree parametric polynomials that Freya skipped is a basis of values through which a polynomial can be interpolated. You can pick any 4 nodes in the interval, but I recommend [0, 0.25, 0.75, 1] for the least erratic behavior.
Example: https://observablehq.com/@jrus/bez-cheb – try dragging the blue dots.
Or for a higher degree polynomial, choose "Chebyshev nodes": equally spaced points on a semicircle projected down onto the diameter. This is one of the most "intuitive" control methods for manipulating a single parametric polynomial segment; the downside of this basis is that it doesn't facilitate matching boundary slope (etc.) between adjacent segments.
The "Hermite" basis (which is equivalent to the Bernstein basis up to some constant scale factors in the 3rd degree case) is in a certain sense what you get when you instead pick the nodes [0, 0, 1, 1] to interpolate; that gives you a double root at each end so you can also pick the slope there.
* * *
Freya: if you are looking for a next project, animating Raph’s excellent PhD thesis would be a great public service. :-) https://levien.com/phd/thesis.pdf
For something a bit easier, chord-length parametrized splines are surprisingly effective, definitely worth playing around with. e.g. the natural cubic spline using chord length for parameter spacing. Implementation (but no demo) here: https://observablehq.com/@jrus/cubic-spline#parametric_NCS
One fun basis for 3rd degree parametric polynomials that Freya skipped is a basis of values through which a polynomial can be interpolated. You can pick any 4 nodes in the interval, but I recommend [0, 0.25, 0.75, 1] for the least erratic behavior.
Example: https://observablehq.com/@jrus/bez-cheb – try dragging the blue dots.
Or for a higher degree polynomial, choose "Chebyshev nodes": equally spaced points on a semicircle projected down onto the diameter. This is one of the most "intuitive" control methods for manipulating a single parametric polynomial segment; the downside of this basis is that it doesn't facilitate matching boundary slope (etc.) between adjacent segments.
The "Hermite" basis (which is equivalent to the Bernstein basis up to some constant scale factors in the 3rd degree case) is in a certain sense what you get when you instead pick the nodes [0, 0, 1, 1] to interpolate; that gives you a double root at each end so you can also pick the slope there.
* * *
Freya: if you are looking for a next project, animating Raph’s excellent PhD thesis would be a great public service. :-) https://levien.com/phd/thesis.pdf
For something a bit easier, chord-length parametrized splines are surprisingly effective, definitely worth playing around with. e.g. the natural cubic spline using chord length for parameter spacing. Implementation (but no demo) here: https://observablehq.com/@jrus/cubic-spline#parametric_NCS
Ooh, the Chebyshev basis is neat. I hadn't seen exactly that before. It reminds me a lot of the "shape control" technique[1] which is also similar to a basis function approach but has a bit of linear solving. Essentially, you get one point (usually at t = 0.5), and also the direction but not magnitudes of the tangents at the endpoints (G1, not C1). This is one of the better-performing existing techniques for offset curve, though does have stability problems (in particular, nasty behavior for a symmetric "S" curve).
Regarding collaboration with Freya, if she is open to it, please get in touch. I do have some ideas.
[1]: A New Shape Control and Classification for Cubic Bézier Curves, Yang and Huang, 1993, PDF cache: https://github.com/paperjs/paper.js/files/752955/A.New.Shape...
Regarding collaboration with Freya, if she is open to it, please get in touch. I do have some ideas.
[1]: A New Shape Control and Classification for Cubic Bézier Curves, Yang and Huang, 1993, PDF cache: https://github.com/paperjs/paper.js/files/752955/A.New.Shape...
ah gosh, a collab would be cool but I think you overestimate my knowledge in this area! I have no formal education or even an eighth of the vocabulary let alone mathematical background to contribute much ;-; I've been reading your paper on the spiro splines and a lot of it goes way over my head! I'd have to research every step along the way
After a year of skimming papers and fiddling with relevant code, I’m sure you know more than almost anyone. (Though as is always the case with math, there’s an infinite pool of deeper knowledge to swim through.)
While you’re here, it’s a bit of a tangent, but the introductory part of the video talking about lerp reminded me again that not enough people know about (not quite uniformly) interpolating along a circular arc using two lerps and one division:
For complex numbers a (start), m ("midpoint" on the circle), b (end), and t (parameter in [0,1], or in [-∞, ∞] to cover the whole circle),
Conveniently, this works for points in a straight line (a circle of infinite diameter) and we never need to explicitly construct the center or radius of the circle.
I was astonished to find this, and even more astonished to find it had never been clearly published anywhere (at least not that I could find after a lot of searching).
[This parametrization of the circle can equivalently be rewritten as a rational quadratic Bézier, but this formula is IMO a lot clearer to understand.]
While you’re here, it’s a bit of a tangent, but the introductory part of the video talking about lerp reminded me again that not enough people know about (not quite uniformly) interpolating along a circular arc using two lerps and one division:
For complex numbers a (start), m ("midpoint" on the circle), b (end), and t (parameter in [0,1], or in [-∞, ∞] to cover the whole circle),
circle_interp = (a, m, b, t) =>
lerp(a * (b - m), b * (m - a), t) / lerp(b - m, m - a, t)
Conveniently, this works for points in a straight line (a circle of infinite diameter) and we never need to explicitly construct the center or radius of the circle.
I was astonished to find this, and even more astonished to find it had never been clearly published anywhere (at least not that I could find after a lot of searching).
[This parametrization of the circle can equivalently be rewritten as a rational quadratic Bézier, but this formula is IMO a lot clearer to understand.]
I'll let you in on a secret: neither do I. Thankfully, it turns out that "I need to know this to do a thing" is enough to get into it, and teaming up with folks who know way more than you do is basically the perfect learning opportunity =D
(I originally dug into Beziers because I was several levels deep into "Processing.js's text-in-a-box fitting is bad, how can I fix that". Queue learning how OpenType works, how TTF/CFF works, how Beziers work, writing up a code playground tutorial before we really had code playgrounds, and then going "...I can use this for more, can't I?"... And thanks to that I've talked to far smarter people with formal training in both the type design and maths communities. I still consider myself an amateur, but an amateur with expert acquaintances =)
(I originally dug into Beziers because I was several levels deep into "Processing.js's text-in-a-box fitting is bad, how can I fix that". Queue learning how OpenType works, how TTF/CFF works, how Beziers work, writing up a code playground tutorial before we really had code playgrounds, and then going "...I can use this for more, can't I?"... And thanks to that I've talked to far smarter people with formal training in both the type design and maths communities. I still consider myself an amateur, but an amateur with expert acquaintances =)
Oh, I wouldn't worry. What would make a collab video cool is not dazzling people with mathematical BS, but rather visually showing the geometric and physical principles behind the splines, especially their relationship with bending elastic strips. If you want to have a chat to brainstorm (even if nothing comes of it), my contact info should be pretty easy to find.
I’d definitely up my Patreon contributions to see the results of such collaboration.
Truly a masterpiece of technical communication! Mind blowing to think about how much work went into this video.
She made the animation library used to make the presentation https://acegikmo.com/shapes/ How much work indeed!
So. Much. Work. And really well done. I loved the discussion on geometric continuity, starts at around 28 minutes in.
All very calm and cool until "it yeets off into fucking wherever" on C2 continuity. I LOLed at that.
Haha that one caught me way off guard, yeah. Hilarious, but went from a school-safe video to not in 0.1 seconds.
I think the criteria for "school safe" should be changed to accommodate something like this. My high-school kid taught me the word "yeet" and they are all familiar with the F-word enough to be cool with tasteful occasional use like this.
Oh yeah I totally agree; this would make an excellent school video. The swearing might even make the kids more likely to watch. (Actcually my oldest already watches Freya.) My high schoolers throw yeet at me all the time, and they don’t care about swearing at all. Not only is it ubiquitous on TikTok and YouTube, they have a friend with Tourette’s that would make most gangsters blush. Sadly, the school district still would never allow it, probably most places, and I live in a city with more religious parents than a lot of places… c’est la vie.
see this is where I can simply ask them to pay the educational license fee for the censored version of the video
I like it! Have you had any interest from educators?
Random tangent, but I’m glad you joined the discussion! Maybe you’re sick of curves by now, and I realize you said you left out many topics, but I was curious if you’d considered the quadratic B-spline or any other quadratic curves? I feel like we always talk about linear and cubic and hardly anyone considers quadratics. There are good reasons for that, but I like the order-2 B-spline for it’s continuity and because it’s halfway interpolating in the sense that it interpolates every midpoint of the linear skeleton. It’s slightly smoother than the Catmull-Rom (which is a bit lumpy IMO), and I think the continuity is equally good, right?
Random tangent, but I’m glad you joined the discussion! Maybe you’re sick of curves by now, and I realize you said you left out many topics, but I was curious if you’d considered the quadratic B-spline or any other quadratic curves? I feel like we always talk about linear and cubic and hardly anyone considers quadratics. There are good reasons for that, but I like the order-2 B-spline for it’s continuity and because it’s halfway interpolating in the sense that it interpolates every midpoint of the linear skeleton. It’s slightly smoother than the Catmull-Rom (which is a bit lumpy IMO), and I think the continuity is equally good, right?
no educators have reached out yet! As for quadratics, I haven't found much use of them, except in cases where you really need an exact solution for arc length or area. Usually the cubics give you a ton more control for not that much extra cost, they kinda strike that nice balance! And yes, the quadratic B-spline is C1, just like the catrom
That’s fair, compelling uses of quadratics are legitimately hard to find, and usually it’s not significantly more costly to go to cubics. Here are few more reasons I’ve collected: the quadratic is easier to explain and understand, useful from a pedagogical perspective; quadratics, unlike cubics, have an analytic rotation minimizing moving frame (a normal and binormal that minimize twist along the curve); quadratics can be analytically sampled in steps of equal change in tangent angle (very handy for drawing, path rendering, tessellating for GPUs); and quadratics are much easier to ray trace (using a swept-circle or swept-sphere formulation). Ray tracing a swept-sphere cubic is solving an order 10 polynomial, while the quadratic is order 6 - but you can reduce the order to 4 with some constraints, which suddenly allows it to be evaluated analytically (in theory), while the cubic is permanently stuck in iterative numeric methods. One of the reasons I liked investigating the quadratic B-spline is because it suddenly makes clear that the order of a B-spline is nothing more than a smoothing factor. Quadratic and cubic and quartic are all the same curve, more or less, just successively smoother. Maybe that’s unsurprising, but from a practical point of view, it can allow you to reduce or increase the order without changing the high level behavior of your curves. Anyway sorry to geek out, I was just curious - I’ve done some work in ray tracing of hair, which is what led me down this path. I did not use quadratics when I worked in games or films, but looking back on it, I think there might have been good reasons to consider it especially on lower powered hardware, maybe for simulation and procedural animation more than hand-animated stuff…
Is there any general rule that systems that have 'continuity' also having sensitivity to initial conditions? I can't help but think of chaos theory[0] when Freya describes the C2 continuous spline in the section on "Cascading Loss of Control" [1], and how it "yeets off to fucking wherever" (which is a great line).
[0] https://en.wikipedia.org/wiki/Chaos_theory
[1] https://www.youtube.com/watch?v=jvPPXbo87ds&t=1308s
[0] https://en.wikipedia.org/wiki/Chaos_theory
[1] https://www.youtube.com/watch?v=jvPPXbo87ds&t=1308s
Super good question. My thesis has both G2 and G4 continuous splines based on polynomial spirals ("spiro curves"), and the G4 definitely has more "wiggles," ie sensitivity to perturbations of the inputs. I imagine there is likely a general principle trading off locality with continuity, but am not able to quantify that rigorously.
Hey Raph, thanks for the answer! Very interesting!
I think the secret to get the C2 splines that pass through the control points right is to not just increase the degree but also add two more points, i.e. not 4 but 6 segments.
> add two more points, i.e. not 4 but 6 segments.
If I understand your suggestion correctly, I believe what this buys you is directional control of your spline at the spline endpoints and a more constant parameterization (one that doesn’t accelerate or decelerate at the spline endpoints). Perhaps the most common alternative is to insert duplicate knots at the spline endpoints, inserting as many extra knots as you need to reach the support requirements of your segment (degree minus one, right?). The problem with this is that you end up with several segments decreasing in size to zero, so the parameterization decelerates to zero. The derivatives also shrink to zero, which can cause problems depending on what you’re doing. Another common technique is to pretend the control points keep going straight after they end, meaning insert implicit ‘phantom’ control points beyond the first & last control point of a spline that matches the direction & magnitude of the first & last explicit segments. (Freya discusses this at 46 minutes into the video.) If your spline was degree 2 and starts with control point p1, then you could insert the phantom point p0 where p1-p0 = p2-p1. This gives you enough control points to evaluate the spline up to your explicit endpoint p1, but you lose a little bit of control over the tangent at the endpoint. If you wanted a different tangent than p2-p1, then you could, as you suggest, add explicit phantom control points. The continuity is the same in all three cases here, but the direction and tangent magnitude are unique to each approach with your suggestion offering the most control.
If I understand your suggestion correctly, I believe what this buys you is directional control of your spline at the spline endpoints and a more constant parameterization (one that doesn’t accelerate or decelerate at the spline endpoints). Perhaps the most common alternative is to insert duplicate knots at the spline endpoints, inserting as many extra knots as you need to reach the support requirements of your segment (degree minus one, right?). The problem with this is that you end up with several segments decreasing in size to zero, so the parameterization decelerates to zero. The derivatives also shrink to zero, which can cause problems depending on what you’re doing. Another common technique is to pretend the control points keep going straight after they end, meaning insert implicit ‘phantom’ control points beyond the first & last control point of a spline that matches the direction & magnitude of the first & last explicit segments. (Freya discusses this at 46 minutes into the video.) If your spline was degree 2 and starts with control point p1, then you could insert the phantom point p0 where p1-p0 = p2-p1. This gives you enough control points to evaluate the spline up to your explicit endpoint p1, but you lose a little bit of control over the tangent at the endpoint. If you wanted a different tangent than p2-p1, then you could, as you suggest, add explicit phantom control points. The continuity is the same in all three cases here, but the direction and tangent magnitude are unique to each approach with your suggestion offering the most control.
See 'a class of c2 interpolating splines' - http://cemyuksel.com/research/interpolating_splines/
Just take C1 splines and integrate
l(t) = t x0 + (1-t) x1
m(t) = t^2 (x0 - x1) + t x1 + x2
I'm really happy yall like it!
Speaking about this taking her a year to produce, there was a new Unity release last week that effectively preempted her own work on a Spline tool for the asset store where her previous work is quite popular.
I watched the entire video and I absolutely loved it. Great work, good explanation and very elegantly and beautifully done.
Super cool video, it explains a lot of stuff in a nice visual way
This video is fucking amazing.
this is almost a 1:1 copy of the Bezier curve video posted some months ago. how is this video getting attention? Even has the same graphics...
It's the same creator, but longer video.
https://youtu.be/aVwxzDHniEw
I wonder if the beginning can be skipped if the first video was already seen?
https://youtu.be/aVwxzDHniEw
I wonder if the beginning can be skipped if the first video was already seen?
It really isn't. It starts with Bezier curves because that's how you start a talk about splines, and then the majority of the video is new information.
The beginning has a recap of Bezier curves as a refresher before going into splines in more detail.
It looks similar because it's a sequel to the original video.
It looks similar because it's a sequel to the original video.
The primary focus of this video is on continuity, and the various kinds, which wasn’t really touched on in her earlier video.
PS. I would also highly recommend these sources which have been covered before on HN:
Curves and Surfaces by Bartosz Ciechanowski [1]
A Primer on Bézier Curves by Pomax [2]
[0] https://acegikmo.com/
[1] https://ciechanow.ski/curves-and-surfaces/
[2] https://pomax.github.io/bezierinfo/