[HN Gopher] Closed form arc length parametrization is impossible...
___________________________________________________________________
Closed form arc length parametrization is impossible for quadratic
Bezier curves
Author : NinjaKoala
Score : 103 points
Date : 2024-07-17 22:51 UTC (1 days ago)
(HTM) web link (ninjakoa.la)
(TXT) w3m dump (ninjakoa.la)
| btown wrote:
| I love articles that walk a lay person through a mathematical
| discovery, piece by piece. An incredibly fun read.
| cyanmagenta wrote:
| Unless Schanuel's conjecture is wrong, of course.
| scythmic_waves wrote:
| ... maybe
| magnio wrote:
| > It is well known in the computer graphics community that the
| arc length of cubic Bezier 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 wrote:
| > 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 wrote:
| Second paragraph of the Wikipedia article on elliptic
| integrals: https://en.wikipedia.org/wiki/Elliptic_integral
| kevinventullo wrote:
| 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 wrote:
| 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.
| bubblyworld wrote:
| 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.
| sfpotter wrote:
| 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?
| Dylan16807 wrote:
| 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.
| bubblyworld wrote:
| 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.
| sfpotter wrote:
| 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.
| bubblyworld wrote:
| Okay, I'm not really sure what you're talking about,
| apologies. I don't have anything else to add.
| Joker_vD wrote:
| If they had then the elliptic integrals that they're
| reducible to would also have closed form. They don't
| though.
| bubblyworld wrote:
| 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".
| eigenket wrote:
| This is obvious because a straight line is a (degenerate)
| example of a quadratic or cubic Bezier curve.
| dataflow wrote:
| "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.
| NinjaKoala wrote:
| Yes, you're right. I didn't find a proof for the fact that
| elliptic integrals have no closed form, though.
| nvpr wrote:
| The linked article says:
|
| > The arc length of quadratic Bezier 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 A _t^2
| + B_ t + 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 wrote:
| 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 wrote:
| 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?
| sfpotter wrote:
| 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.
| LiamPowell wrote:
| > It is well known in the computer graphics community that the
| arc length of cubic Bezier 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 wrote:
| Numerical solutions are better. Having a closed form solution
| is overrated. For example, the closed form solution for arc
| length of a quadratic Bezier 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 wrote:
| 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
| jacobolus wrote:
| 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.)
| LiamPowell wrote:
| We're using them in practice for C4 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-0
| 9463-y
| jacobolus wrote:
| Thanks for the links! What's Prunt, and does it have a
| website?
| LiamPowell wrote:
| > 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.
| NinjaKoala wrote:
| 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.
| raphlinus wrote:
| 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.
| sfpotter wrote:
| 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.
| mananaysiempre wrote:
| 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.
| raphlinus wrote:
| 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.
| red_trumpet wrote:
| 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?
| kazinator wrote:
| If the result of any computation is a number like 0.123, that's
| numerical methods.
| a_sync wrote:
| 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.
___________________________________________________________________
(page generated 2024-07-18 23:08 UTC)