7 ms·

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

114 points by NinjaKoala 2y ago

deleted 2y ago
[deleted]
- deleted 2y ago
  [deleted]
btown 2y ago
I love articles that walk a lay person through a mathematical discovery, piece by piece. An incredibly fun read.
cyanmagenta 2y ago
Unless Schanuel’s conjecture is wrong, of course.
- scythmic_waves 2y ago
  … maybe
magnio 2y ago
> 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. 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.
- dataflow 2y ago
  > 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?
  - sfpotter 2y ago
    Second paragraph of the Wikipedia article on elliptic integrals: https://en.wikipedia.org/wiki/Elliptic_integral https://en.wikipedia.org/wiki/Elliptic_integral
    - kevinventullo 2y ago
      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.
      - sfpotter 2y ago
        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.
        deleted 2y ago
        [deleted]
        bubblyworld 2y ago
        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.
        deleted 2y ago
        [deleted]
        sfpotter 2y ago
        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?
- NinjaKoala 2y ago
  Yes, you're right. I didn't find a proof for the fact that elliptic integrals have no closed form, though.
- deleted 2y ago
  [deleted]
LiamPowell 2y ago
> 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.
- raphlinus 2y ago
  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.
  - infogulch 2y ago
    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 https://news.ycombinator.com/item?id=40856431
  - jacobolus 2y ago
    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.)
nvpr 2y ago
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/gamegraphics/files/opengl/gpupathrender.pdf 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.
- NinjaKoala 2y ago
  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.
  - phkahler 2y ago
    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?
- deleted 2y ago
  [deleted]
sfpotter 2y ago
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.
ForOldHack 2y ago
[flagged]
- ForOldHack 2y ago
  Sum of Two Irrational Numbers Statement: The sum of two irrational numbers may be rational or irrational. Like the product of two irrational numbers, the sum of two irrational numbers will also result in a rational or irrational number. For example, if we add two irrational numbers, say 3√2+ 4√3, a sum is an irrational number. But, let us consider another example, (3+4√2) + (-4√2 ), the sum is 3, which is a rational number. So, we should be very careful while adding and multiplying two irrational numbers, because it might result in an irrational number or a rational number.
- thaumasiotes 2y ago
  > If two irrational numbers have no rational cofactors What's this supposed to mean? I was unable to document the existence of any term "cofactor" that might apply to irrational numbers. All pairs of irrational numbers share rational factors, to the extent that it makes sense to talk about factors of non-integral numbers, which it doesn't.
- deleted 2y ago
  [deleted]
- deleted 2y ago
  [deleted]
red_trumpet 2y ago
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?
- deleted 2y ago
  [deleted]
- kazinator 2y ago
  If the result of any computation is a number like 0.123, that's numerical methods.
a_sync 2y ago
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.

114 points by NinjaKoala 2y ago

deleted 2y ago

[deleted]

deleted 2y ago
[deleted]

btown 2y ago

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

cyanmagenta 2y ago

Unless Schanuel’s conjecture is wrong, of course.

scythmic_waves 2y ago
… maybe

magnio 2y ago

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

dataflow 2y ago
> 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?
- sfpotter 2y ago
  Second paragraph of the Wikipedia article on elliptic integrals: https://en.wikipedia.org/wiki/Elliptic_integral https://en.wikipedia.org/wiki/Elliptic_integral
  - kevinventullo 2y ago
    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.
    - sfpotter 2y ago
      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.
      - deleted 2y ago
        [deleted]
      - bubblyworld 2y ago
        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.
        deleted 2y ago
        [deleted]
        sfpotter 2y ago
        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?
NinjaKoala 2y ago
Yes, you're right. I didn't find a proof for the fact that elliptic integrals have no closed form, though.
deleted 2y ago
[deleted]

LiamPowell 2y ago

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

raphlinus 2y ago
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.
- infogulch 2y ago
  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 https://news.ycombinator.com/item?id=40856431
- jacobolus 2y ago
  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.)

nvpr 2y ago

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/gamegraphics/files/opengl/gpupathrender.pdf 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.

NinjaKoala 2y ago
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.
- phkahler 2y ago
  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?
deleted 2y ago
[deleted]

sfpotter 2y ago

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.

ForOldHack 2y ago

[flagged]

ForOldHack 2y ago
Sum of Two Irrational Numbers Statement: The sum of two irrational numbers may be rational or irrational. Like the product of two irrational numbers, the sum of two irrational numbers will also result in a rational or irrational number. For example, if we add two irrational numbers, say 3√2+ 4√3, a sum is an irrational number. But, let us consider another example, (3+4√2) + (-4√2 ), the sum is 3, which is a rational number. So, we should be very careful while adding and multiplying two irrational numbers, because it might result in an irrational number or a rational number.
thaumasiotes 2y ago
> If two irrational numbers have no rational cofactors What's this supposed to mean? I was unable to document the existence of any term "cofactor" that might apply to irrational numbers. All pairs of irrational numbers share rational factors, to the extent that it makes sense to talk about factors of non-integral numbers, which it doesn't.
deleted 2y ago
[deleted]
deleted 2y ago
[deleted]

red_trumpet 2y ago

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?

deleted 2y ago
[deleted]
kazinator 2y ago
If the result of any computation is a number like 0.123, that's numerical methods.

a_sync 2y ago

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.