6 ms·

The Continuity of Splines [video]

192 points by mcorcuera 4y ago

s1mon 4y ago
I’ve been following Freya’s work [0] for a while. She works in the game industry working with Unity, hosts a bunch of Discord channels, and live streams about game math and shaders. This video is relatively long, but it’s one year in the making. If you ever wanted to understand a bit more about Béziers vs B-Splines and G2 vs C2, this is great place to start. 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/ https://acegikmo.com/ [1] https://ciechanow.ski/curves-and-surfaces/ https://ciechanow.ski/curves-and-surfaces/ [2] https://pomax.github.io/bezierinfo/ https://pomax.github.io/bezierinfo/
- TheRealPomax 4y ago
  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.
  - raphlinus 4y ago
    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.
    - TheRealPomax 4y ago
      Indeed, there were a number of places where I had that "...this never occurred to me, this is fantastic" moment, too.
      - jacobolus 4y ago
        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 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 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 https://observablehq.com/@jrus/cubic-spline#parametric_NCS
        raphlinus 4y ago
        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.Control.and.Classification.for.Cubic.Bezier.Curves.pdf https://github.com/paperjs/paper.js/files/752955/A.New.Shape...
adriancarrieres 4y ago
Super cool video, it explains a lot of stuff in a nice visual way
Yenrabbit 4y ago
Truly a masterpiece of technical communication! Mind blowing to think about how much work went into this video.
- corysama 4y ago
  She made the animation library used to make the presentation https://acegikmo.com/shapes/ https://acegikmo.com/shapes/ How much work indeed!
- dahart 4y ago
  So. Much. Work. And really well done. I loved the discussion on geometric continuity, starts at around 28 minutes in.
  - phkahler 4y ago
    All very calm and cool until "it yeets off into fucking wherever" on C2 continuity. I LOLed at that.
    - dahart 4y ago
      Haha that one caught me way off guard, yeah. Hilarious, but went from a school-safe video to not in 0.1 seconds.
      - phkahler 4y ago
        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.
        dahart 4y ago
        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.
jimmySixDOF 4y ago
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.
stkdump 4y ago
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.
- moonchild 4y ago
  See 'a class of c2 interpolating splines' - http://cemyuksel.com/research/interpolating_splines/ http://cemyuksel.com/research/interpolating_splines/
- toxik 4y ago
  Just take C1 splines and integrate l(t) = t x0 + (1-t) x1 m(t) = t^2 (x0 - x1) + t x1 + x2 and so on.
- dahart 4y ago
  > 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.
heywhatupboys 4y ago
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...
- tantalor 4y ago
  It's the same creator, but longer video. https://youtu.be/aVwxzDHniEw https://youtu.be/aVwxzDHniEw I wonder if the beginning can be skipped if the first video was already seen?
- boolemancer 4y ago
  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.
- TheRealPomax 4y ago
  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.
- mcphage 4y ago
  The primary focus of this video is on continuity, and the various kinds, which wasn’t really touched on in her earlier video.
Garlef 4y ago
If all of maths was taught this way, we'd be looking at a bright future (in terms of education).
- danuker 4y ago
  I sure hope YouTube or some other similar video streaming service keeps existing far into the future.
- deleted 4y ago
  [deleted]
chasing 4y ago
This video is fucking amazing.
zengid 4y ago
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 https://en.wikipedia.org/wiki/Chaos_theory [1] https://www.youtube.com/watch?v=jvPPXbo87ds&t=1308s https://www.youtube.com/watch?v=jvPPXbo87ds&t=1308s
- raphlinus 4y ago
  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.
  - zengid 4y ago
    Hey Raph, thanks for the answer! Very interesting!
dyml 4y ago
I watched the entire video and I absolutely loved it. Great work, good explanation and very elegantly and beautifully done.
acegikmo 4y ago
I'm really happy yall like it!

192 points by mcorcuera 4y ago

I’ve been following Freya’s work [0] for a while. She works in the game industry working with Unity, hosts a bunch of Discord channels, and live streams about game math and shaders. This video is relatively long, but it’s one year in the making. If you ever wanted to understand a bit more about Béziers vs B-Splines and G2 vs C2, this is great place to start. 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/ https://acegikmo.com/ [1] https://ciechanow.ski/curves-and-surfaces/ https://ciechanow.ski/curves-and-surfaces/ [2] https://pomax.github.io/bezierinfo/ https://pomax.github.io/bezierinfo/

TheRealPomax 4y ago
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.
- raphlinus 4y ago
  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.
  - TheRealPomax 4y ago
    Indeed, there were a number of places where I had that "...this never occurred to me, this is fantastic" moment, too.
    - jacobolus 4y ago
      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 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 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 https://observablehq.com/@jrus/cubic-spline#parametric_NCS
      - raphlinus 4y ago
        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.Control.and.Classification.for.Cubic.Bezier.Curves.pdf https://github.com/paperjs/paper.js/files/752955/A.New.Shape...

adriancarrieres 4y ago

Super cool video, it explains a lot of stuff in a nice visual way

Yenrabbit 4y ago

Truly a masterpiece of technical communication! Mind blowing to think about how much work went into this video.

corysama 4y ago
She made the animation library used to make the presentation https://acegikmo.com/shapes/ https://acegikmo.com/shapes/ How much work indeed!
dahart 4y ago
So. Much. Work. And really well done. I loved the discussion on geometric continuity, starts at around 28 minutes in.
- phkahler 4y ago
  All very calm and cool until "it yeets off into fucking wherever" on C2 continuity. I LOLed at that.
  - dahart 4y ago
    Haha that one caught me way off guard, yeah. Hilarious, but went from a school-safe video to not in 0.1 seconds.
    - phkahler 4y ago
      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.
      - dahart 4y ago
        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.

jimmySixDOF 4y ago

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.

stkdump 4y ago

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.

moonchild 4y ago
See 'a class of c2 interpolating splines' - http://cemyuksel.com/research/interpolating_splines/ http://cemyuksel.com/research/interpolating_splines/
toxik 4y ago
Just take C1 splines and integrate l(t) = t x0 + (1-t) x1 m(t) = t^2 (x0 - x1) + t x1 + x2 and so on.
dahart 4y ago
> 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.

heywhatupboys 4y ago

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

tantalor 4y ago
It's the same creator, but longer video. https://youtu.be/aVwxzDHniEw https://youtu.be/aVwxzDHniEw I wonder if the beginning can be skipped if the first video was already seen?
boolemancer 4y ago
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.
TheRealPomax 4y ago
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.
mcphage 4y ago
The primary focus of this video is on continuity, and the various kinds, which wasn’t really touched on in her earlier video.

Garlef 4y ago

If all of maths was taught this way, we'd be looking at a bright future (in terms of education).

danuker 4y ago
I sure hope YouTube or some other similar video streaming service keeps existing far into the future.
deleted 4y ago
[deleted]

chasing 4y ago

This video is fucking amazing.

zengid 4y ago

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 https://en.wikipedia.org/wiki/Chaos_theory [1] https://www.youtube.com/watch?v=jvPPXbo87ds&t=1308s https://www.youtube.com/watch?v=jvPPXbo87ds&t=1308s

raphlinus 4y ago
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.
- zengid 4y ago
  Hey Raph, thanks for the answer! Very interesting!

dyml 4y ago

I watched the entire video and I absolutely loved it. Great work, good explanation and very elegantly and beautifully done.

acegikmo 4y ago

I'm really happy yall like it!