10 ms·
Beyond Bézier Curves (2013)
- m0ther 7y agohttp://i.stanford.edu/pub/cstr/reports/cs/tr/85/1047/CS-TR-85-1047.pdf http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1047/CS-TR-8...
- joe_the_user 7y agoI always found Bezier curves strange - they seem awful as a way to approximate curves. When you "draw" with a Bezier curve in Illustrator (or Inkscape), the lines tend to fly all over the place - they can be an OK approximation but they're often very unstable. The problem, I think, is that any polynomial or equivalent higher order is going to have this instability property.
- jakear 7y ago> Because they are perfectly compatible with industry-standard Béziers, there is very little disadvantage to be had. Anyone know what "compatible" means as used here? As an aside, I personally prefer NURBS, they feel much more "pure" if that makes any sense. Plus they can produce real circles, which is a pretty nice feature of a curve-system.
- graphpapa 7y agoI interpreted it to mean that they are in fact a subset of Bezier curves. A computed smooth-spline (cant remember what they’re called) is still stored using the exact same information as any other Bézier curve - but the extra rules about its construction just make them smoother than canonical bezier
- delhanty 7y agoThat's right the Hobby splines are a strict subset of the polynomial cubic Béziers. The polynomial cubic Béziers are defined by 4 control points. In 2D that's 4 x 2 = 8 degrees of freedom. In the terminology of HN raphlinus's PhD thesis, we fix the 2 endpoints, which removes 4 degrees of freedom, and they're referred to as a 4-parameter family. In addition to the 2 endpoints, Hobby splines are defined by the start and end tangent angles Θ0 and Θ1, plus a tension parameter τ. If we fix the 2 endpoints and the tension parameter τ, and allow Θ0 and Θ1 to vary, then we have a 2-parameter subspace of the 4-parameter space of polynomial cubic Béziers for 2 fixed endpoints. If we allow the tension parameter τ to vary we have a 3-parameter subspace. So we have lost 1 degree of freedom, but in terms of aesthetics we haven't lost so much because the majority of the splines that we've thrown away are likely uglier than the splines we retained. One TL/DR from HN raphlinus's thesis: Euler spiral splines are about the best you can do for a 2-parameter family that cover all reasonable possibilities for Θ0 and Θ1 with good aesthetics.
- pippy 7y agoA few years back I wrote a basic bezier curve library with boolean operations in C/C++. Bezier curves are fantastic when you get started, they're easy to deal with and the math is well documented online. However the edge cases are nightmares to deal with. Intersection (and similar operations) typically work by approximating via subdivision, so you'll never get an accurate answer, which is important when dealing with boolean operations. You'll wind up piling on hacks. One edge case I wound up being due to a floating point arithmetic error, which was fun because my computer science degree finally wound up coming in handy. It makes me appreciate the work that the guys who made paper.js. They've done some outstanding work, and it's by far the most superior open source vector graphics framework out there.
- chadcmulligan 7y agoAGG is a venerable 2D library, code here https://github.com/ghaerr/agg-2.6 https://github.com/ghaerr/agg-2.6, the front page is here but seems all the links are broken http://antigrain.com http://antigrain.com
- franzb 7y agoSadly the author died years ago (at a fairly young age...)
- chadcmulligan 7y agoI'm sorry to hear that - I learnt so much reading this code.
- pmarreck 7y agoI did not know about paper.js. Holy crap! Looks amazing!
- mkl 7y agoIt does look amazing. I tried using it for a drawing app, though, and found it too slow. Maybe I was using it wrongly, but long or large numbers of strokes caused issues as it seemed to redraw the whole image more than necessary. I had better luck with just plain canvas, but I'd like to investigate CanvasKit (Skia in WASM) as well, as their drawing demo seems very performant.
- delhanty 7y agoFor a technical analysis of Hobby splines I recommend HN raphlinus's PhD thesis Section 4.7 [0] referenced just yesterday in the submission on Google Font Analytics [1]. [0] https://levien.com/phd/thesis.pdf https://levien.com/phd/thesis.pdf [1] https://news.ycombinator.com/item?id=22369500 https://news.ycombinator.com/item?id=22369500
- jacobolus 7y agoAlso read Hobby’s original paper, which is quite good. https://link.springer.com/content/pdf/10.1007/BF02187690.pdf https://link.springer.com/content/pdf/10.1007/BF02187690.pdf
- dicytea 7y agoI wish there was a visual on how this works in practice
- mkl 7y agoHere: https://raphlinus.github.io/curves/2018/12/21/new-spline.html https://raphlinus.github.io/curves/2018/12/21/new-spline.htm... Discussed a while ago: https://news.ycombinator.com/item?id=18738275 https://news.ycombinator.com/item?id=18738275
- steerablesafe 7y agoThat's an unrelated spline algorithm to the article discussed here. Interesting on its own though.
- mkl 7y agoOh, you're right. I'm getting mixed up.
- runxel 7y agoSame. The article seems so unfinished and empty without that. I know Beziers, NURBS, etc, but never had heard of Hobby. A visual would have been great.
- mcphage 7y agoI really prefer Catmull-Rom splines (https://en.wikipedia.org/wiki/Centripetal_Catmull–Rom_spline https://en.wikipedia.org/wiki/Centripetal_Catmull–Rom_spline). They’re not as attractive as Bézier curves, but the curve passes through the control points, which makes them a ton easier to draw.
- jacobolus 7y agoThe same is true for Hobby’s spline, with the advantage that it’s a lot more intuitive to control and easier to get the shape you want.
- mcphage 7y agoAh, thanks—I didn't see that mentioned in the article at all. It definitely seems like the most important property for a curve that someone will be drawing should have.
- starmole 7y agoMuch better curves for editing are k-curves (see http://faculty.cs.tamu.edu/schaefer/research/kcurves.pdf http://faculty.cs.tamu.edu/schaefer/research/kcurves.pdf) which are starting to pop up in all new Adobe tools also.
- jacobolus 7y agoJust be warned that what Adobe ships in their software is completely different than what they describe in their paper or patent.
- raphlinus 7y agoIndeed. The biquadratics aren't particularly smooth, and don't support inflections naturally. See https://raphlinus.github.io/curves/2018/12/21/new-spline.html https://raphlinus.github.io/curves/2018/12/21/new-spline.htm... for more on this.
- delhanty 7y agoAre you able to expand on that statement a little? Your blog post is interesting as always. But I can't seem to find a reference to biquadratic in either the post or the linked Adobe paper.
- jacobolus 7y ago> Our curves consist of one quadratic curve, with control points [...] per interpolated point p_i So what happens is each segment between two knots (in the paper) is made of 2 pieces of parametric quadratic polynomials (i.e. parabolas). Each knot is at the vertex of the same parabola to each side, which can be broken at the vertex into two parts, each of which belongs to one of the adjacent segments. The solver in the paper makes sure that at the joint between two parabolas, the absolute magnitude of curvature matches. This means there aren’t really any smooth inflection points and you always get a discrete jump in curvature at an inflection. This looks bad, so in practice Adobe implemented something different in their software.
- tola19190 7y agoHack seba sami please
- MayeulC 7y agoIs this supported in inkscape? I could see it useful as a way to interpret hand-drawn shapes such as graphs, or even letters.
- montroser 7y agoNo, but Spiro splines are supported, and they have many of the same characteristics (arguably better). The UI to toggle into Spiro mode is a little bit obtuse but once you're in it's pretty cool.
- lentil_soup 7y agoWhen I was fighting some splines at work I found this website very good and very interactive when explaining how Bezier curves work under the hood, a great resource! https://pomax.github.io/bezierinfo/ https://pomax.github.io/bezierinfo/