Closed form arc length parametrization is impossible for quadratic Bézier curves | Hacker News Reader

Closed form arc length parametrization is impossible for quadratic Bézier curves

ninjakoa.la

114 pointsNinjaKoala47 comments

> It is well known in the computer graphics community that the arc length of cubic Bézier curves has no closed form and has to be computed numerically. Sadly, I’ve not yet seen a proof sketch for that, though.

On a somewhat related note: There are of course exceptions to this, such as Pythagorean-Hodograph curves, which do have closed form solutions and would be suitable for a huge number of use-cases. Sadly there's not too many mathematicians working in computer graphics so we just end up with numerical solutions to everything.

Numerical solutions are better. Having a closed form solution is overrated. For example, the closed form solution for arc length of a quadratic Bézier becomes numerically unstable for curves that are close to a straight line. In those cases, you definitely want the numerical approach.

I also think Pythagorean Hodograph curves are overrated. Euler spirals, on the other hand, are extremely easy to work with in an arc length parametrization, it's just that you need to compute a "special function" to get back to parametrized land. Fortunately, that's easy enough to compute very accurately using standard numerical techniques.

Hey I was about to write a comment suggesting Euler spirals may be easier to calculate the arc length because they are literally defined as a curve whose curvature changes linearly with its curve length, and then the Euler spiral guy himself shows up. :)

GPU-Friendly Stroke Expansion - 177 points - 11 days ago - 40 comments https://news.ycombinator.com/item?id=40856431

Numerical solutions are usually much more accurate, yes. However, especially when computing with fragment shaders for example, closed form formulas tend to be faster. But the main reason for looking into it was because i had fun doing it.

This is a little mixed up. If you write the arc length as an elliptic integral and evaluate it using a special function library, you may just be evaluating a Chebyshev series or some rational approximation (or some piecewise combination). It may indeed be quite accurate... but that will be for a general case which may be too heavyweight (e.g. a library function which evaluates a special function for any choice of parameters to 15 digits). It might be that directly approximating the arc length if your particular curve on the fly (a smooth function!) with a Chebyshev series will be faster for the same accuracy, but now you can also reduce the accuracy to get more speed if you like. This is the sense in which numerical methods are almost guaranteed to be the superior tool for the job.

That's a really good reason, and thanks for the writeup!

My main point is that I believe there are tons of excellent numerical techniques just waiting to be discovered. Lately I've been exploring a Chebyshev polynomial basis for the Whewell equation, and I think that'll bear fruit.

Pythagorean hodograph curves may be impractical, but they're a pretty theoretically cute idea. Farouki's book is nice.

(From what I can tell PH curves are rarely if ever used in practice. They were ostensibly developed for CNC machining and robot motion planning, etc., but are there real products or even serious physical research projects implementing them? What they do have going for them is a huge pile of research papers, of highly variable quality – Google Scholar turns up >2,500 entries.)

We're using them in practice for C⁴ corner smoothing in a motion controller [1]. All credit for the actual maths to [2].

[1]: https://github.com/Prunt3D/prunt_notebooks/blob/master/Pytha...

[2]: https://link.springer.com/article/10.1007/s00170-022-09463-y

Thanks for the links! What's Prunt, and does it have a website?

> What's Prunt, and does it have a website?

A motion controller for 3D printers (notably with crackle-constrained trajectory planning), and no website since it is still in the early stages.

Following up on your recent article about stroking: is there any hope for general convolutions (or at least more general ones than with circles) via Euler spirals? Such as for pens in METAFONT and Illustrator and so on.

I think it's a great avenue for research. I'm probably not going to work on it myself any time soon, as I have a very full queue of ideas to pursue.

> any hope for general convolutions (or at least more general ones than with circles)

Interesting question.

Knuth's METAFONT can describe glyphs not simply as filled outlines, but ALSO as strokes of pens shaped by circles, ellipses, and EVEN convex polygons (e.g., a an acute triangular wedge perhaps).

And the description of a METAFONT glyph is all parameterized (it's really a program! -- hence the META) so there's not even an actual outline for a glyph but a tunable family of glyph variations.

METAFONT's model is humanistic as human ideographs and letter forms were (once) scratchings, engravings, and pen strokes. However the shape of movable type, as captured with Bezier splines by TrueType and Postscript outline glyphs, lack a first-class stroking capability.

So could you support the humanistic METAFONT-style approach efficiently in today's world of GPU rendering? Yes, if you could, as suggested above, efficiently convolve a pen's shape with a stroke trajectory.

Circles for pens are no problem; and ellipses are just squished transforms of circular stroking. But (convex) polygonal pens for stroking?

Polar stroking provides a starting framework for such a convolution approach for convex polygonal pens (say, a triangular wedge or other convex polygonal shape). Step in small changes in gradient direction change. Rather than assuming a conventional circular or nib pen shape, snap each tessellated rib to the closest polygonal pen vertex. The result is the polygonal convolution you seek.

So a question almost nobody is asking: What if we could revive METAFONT for the 21st century?

Imagine a Jurassic Park scenario applied -- not to dinosaurs -- but rather to Knuth's Computer Modern.

https://en.m.wikipedia.org/wiki/Computer_Modern

"Your scientists were so preoccupied with whether or not they could, they didn't stop to think if they should."

The linked article says:

> The arc length of quadratic Bézier curves actually can be computed with a closed form expression.

While indeed true, the article doesn't provide the closed form expression. The curious or unsatisfied reader can find the solution for the 2D case at the top of page 7 of this SIGGRAPH paper:

https://developer.download.nvidia.com/devzone/devcenter/game...

The quadratic function Q(t)=(x,y) is of the monomial form At^2 + Bt + C where A, B, and C are 2D coefficients (see page 5) where A is non-zero.

Simply convert your Bezier quadratic form to monomial form to apply this equation.

This equation still doesn't provide an arc length parameterization, the article's actual focus.

But if you did, say, want to move 26% (or N%, more generally) of the arc length along a quadratic Bezier segment, first compute the total (100%) arc length with the paper's formula (take care doing so as the paper suggests). Then split the Bezier at a halfway guess (try t=0.5). Again use the formula to evaluate the split quadratic. Repeating this in a divide and conquer fashion, you narrow in on the t value very close to 26% (or N%) of the arc length.

2D vector graphics standards expect to dash cubic & quadratic Bezier segments so some practical strategy to provide an arc length parameterization -- even if unavailable in closed form.

Yes, the procedure you mention works, but it's a numerical method. I'm not saying such numerical method's are impractical or something, but depending on your general setup, closed form formulas might be faster.

You could also split the curve at an arbitrary value of the parameter t. Then find the length of that entire curve. Splitting at a specific value is straight forward.

Edit: or were they talking about 26 percent of the length as opposed to t = 0.26? that's a different story.

Edit2: Oh, that's just 0.26 times the total length. What am I missing?

A cubic Bezier curve B(t) is a cubic polynomial of t in [0, 1], parameterized by the four control points. Since it is continuously differentiable, its length is the integral from 0 to 1 of the square root of (1 + (B')^2), a quartic. Such an integral is well known to be reducible to the elliptic integrals, which have no closed form.

> Such an integral is well known to be reducible to the elliptic integrals, which have no closed form.

I believe you're stating the reduction in the wrong direction?

Second paragraph of the Wikipedia article on elliptic integrals: https://en.wikipedia.org/wiki/Elliptic_integral

The point is that the general non-reducibility of elliptic integrals to closed form does not preclude the possibility of reducing to closed form some particular elliptic integral or combination thereof.

This is obvious because a straight line is a (degenerate) example of a quadratic or cubic Bezier curve.

The specific form in question is basically sqrt(any quartic). Seems like almost all of these will be able to be expressed in terms of elliptic integrals and that's it. Outer post summarizes this just fine.

They're just pointing out that strictly speaking this is not a valid proof that these integrals have no closed form.

Compare: halting problem being uncomputable tells you nothing about whether you can solve it for a subset of valid programs.

We're talking about Bezier curves in the context of CAD and graphics. In this case, I believe there is no reason to assume that these curves will have a more special form than sqrt(arbitrary quartic). Do you think that they do have a more special form, and that this form will simplify nicely? Or are you suggesting that sqrt(abrbitrary quartic) might simplify more?

If I may, your confusion seems to come from the meaning of "elliptic curves in general have no closed form".

You seem to interpret that as "given any elliptic integral A, there is no closed form for the solution of A". This is false (there are many counterexamples).

What it actually means is "there is no single closed-form that produces the solution of any given elliptic integral". The quantifiers are the other way around.

This is why I brought up the halting problem. There's a similar confusion that often comes up, where people think that it means there's no way to determine if any given program halts. But this is false - the program "let X=5*6" trivially halts, for instance.

What it actually means is that there's no single program that can uniformly determine whether any given input program halts. It's exactly the same situation.

No, I'm not getting this confused at all. I understand the point. What I'm saying is that because the general elliptic integral corresponding to sqrt(quartic) doesn't have a closed form, and because this (or maybe a slightly more specific form) is what's of interest in this context (CAD), saying something about the closed form of specific sqrt(quartic) elliptic integrals isn't very interesting as far as I can see.

  the general elliptic integral corresponding to sqrt(quartic) doesn't have a closed form

I see, so you’re claiming that there is no closed form for the integral of sqrt(quartic). That is a different statement that neither directly implies nor is implied by the statement in the Wikipedia article. Maybe it is true and has been proven though, I don’t know!

Okay, I'm not really sure what you're talking about, apologies. I don't have anything else to add.

You're getting hung up on a logical point which, while correct, isn't particularly salient to the context in which this conversation is occurring (CAD and graphics). The original article, while mathematically interesting, is also not particularly salient within that context.

Don't tell people how to take their drugs =) I'm personally more interested in the maths.

Take whatever drugs you like. You just seem a little bewildered why people aren't more fired up about what you have to say about the halting problem. Just trying to suggest that it may be because this isn't the right venue for it. I wish you many happy mathematical returns. :-)

The issue is that "sqrt(arbitrary quartic)" is already more specialized than "elliptic integral". So we can't just talk about elliptic integrals in general, we need proof that this specialization doesn't give rise to closed forms.

If they had then the elliptic integrals that they're reducible to would also have closed form. They don't though.

Yes, if they had then those particular elliptic integrals would have a closed form. Some degenerate classes of elliptic integrals do have closed forms, in precisely the same way that you can determine whether certain subsets of programs halt despite the halting problem in general being insoluble! I think you misunderstand what is meant by the statement "elliptic integrals in general have no closed form".

No, I don't think I misunderstand, and I don't think my reduction is invalid. I take a Bezier curve, and reduce the expression of its arc length to an elliptic integral. If this particular elliptic integral has no closed form, that means that this particular Bezier curve doesn't have closed form arc length parametrization and also that Bezier curves in general don't admit such parametrization. Because that's what "X in general is not Y" means: that there is at least one X which is not Y.

I agree with everything you've written in this reply, but originally you were appealing to the fact that elliptic curves in general don't have closed forms ("they don't, though") to prove your point, which isn't valid because we're talking about a strict subset of them here.

"every elliptic integral can be brought into a form that [...]"

Yes? That is a reduction in the other direction. It starts off with an elliptical integral, then reduces it to something else. Not the other way around.

Yes, you're right. I didn't find a proof for the fact that elliptic integrals have no closed form, though.

I love articles that walk a lay person through a mathematical discovery, piece by piece. An incredibly fun read.

Interesting topic!

However, I would like to point out that the dichotomy closed form <-> numerical methods is somewhat artificial. Even if one could express an arc length parametrization using exp and log, one would still need numerical methods to compute exp and log.

This somehow leads to the next question: What kind of functions are suitable to describe the arc length?

If the result of any computation is a number like 0.123, that's numerical methods.

I'm not sure how much more "closed form" you need than elliptic integrals.

For another approach, expand sqrt(1 + B'(t)^2) in a Chebyshev series and you're off to the races.

Unless Schanuel’s conjecture is wrong, of course.

… maybe

Yeah, interesting stuff. So, the whole debate between closed forms and numerical methods is kind of overplayed. Even if you had a closed form for arc length, you’d still need numerical methods to compute exp and log. What functions actually work best for arc length? That’s the real question.

Also, while some folks are hyped about Pythagorean-Hodograph curves, I think they’re kinda niche. Euler spirals seem more practical, even if you have to compute a special function for them. Numerical solutions tend to be more stable anyway, especially in cases where a closed form might break down, like near straight lines.

Reply on news.ycombinator.com