How to compute the length of a spline

I needed to calculate the length of a cubic Hermite spline. A quick googling showed me that there is no “closed form” solution. Again, with anything related to spline or Bézier curves, this primer is the go-to resource. You can resort to calculus and try to get the length by integrating the velocity across the curve, but even for quadratic curves, the integral becomes hairy enough so that WolframAlpha nags you to retry with ‘Pro’ computation time:

There is a rough calculation you can use called chorded approximation, where you emulate the original curve with piece-wise linear segments. Given a parametric curve f(t) with its parameter t ranging from 0 to 1, it’s basically calculating:

The bigger the n, the more accurate the result will become and the slower the execution. At first, I implemented this approach and it worked well enough for my use case. Splines’ length data was needed at an export time and the performance wasn’t really a concern. Still, I wanted to learn more about what alternatives mathematics can provide and that’s how I learned Gaussian quadature (or Legendre-Gauss quadrature).

The idea originates from the same idea of the aforementioned velocity integration:

You can utilize one of numerical integration methods, for instance, like doing the sum of discrete intervals:

It’s basically approximating the area under the curve with the sum of the rectangles like below:

You can be a little more clever and use the mid-point of the interval instead:

Or trapezoids instead of rectangles:

These concepts and how Gaussian quadrature improves upon them is well explained in this short youtube video:

If you see the formulas above, you notice they are all of the form:

Given n uniformly divided intervals, you basically have n degrees of freedom in choosing wi’s, where 0 ≤ i ≤ n-1. The gist of Gaussian quadrature is varying xi’s, too, instead of just using uniform intervals, on top of varying wi’s, to maximize the degree of freedom. With n points, you now have 2n degrees of freedom instead of n. Let’s say f(x) is a polynomial of degree m. From its (m+1) polynomial bases, ranging from the constant term to the m-th order term, we get (m+1) equations to satisfy, if you think of the situation as a system of linear equations. The set-up is basically 2n unknowns with (m+1) equations. Let 2n = m+1 and you get to the fact that, with n-point Gaussian quadrature, you can cleverly choose xi’s and wi’s so that it can yield an exact result for polynomials of degree m(=2n-1) or less.

This image I copied from the Wikipedia article demonstrates 2-point Gaussian quadrature. With carefully chosen x0 and x1 and associated weights, it gives a much better result than the trapezoid integration, which is indicated by ‘Trap’ above, (or rather the exact result due to the fact that the sum of two red areas is equal to the green area) for this 3rd order curve.

All these ideas and how you can derive those concrete values for xi, wi yourself to satisfy the aforementioned conditions (rather than resorting to numerous precalculated tables available on the internet), you can check another very helpful youtube video I found:

Does this mean Gaussian quadrature can produce an exact result for cubic splines? No, because the velocity you need to integrate in 2D or 3D space are no longer polynomials. It’s either:

2D

or:

3D

Also note that Gaussian quadrature is explained and derived with the interval of [-1, 1], but you can easily change the interval to something like [0, 1] to get the length of an entire spline segment or any interval like [a, b] for that matter to get the length of a sub-segment. Refer to the wikipedia article (or the last part of Wen Shen’s video) for the details.

By the way, UnrealEngine 4 seems to be using 5-point Gaussian quadrature for its spline length calculation. Here is a C++ code snippet implementing it:

References

1. A Primer on Bézier Curves — 22. Arc length: https://pomax.github.io/bezierinfo/#arclength
2. Finding the Length of a Bezier Cubic Spline and its Subdivisions (pdf): http://www.tinaja.com/glib/nubzlen1.pdf
3. Gaussian quadrature — Wikipedia: https://en.wikipedia.org/wiki/Gaussian_quadrature
4. Linear Algebra 1b: Magic of Gaussian Quadrature — A Billion Times Better than the Next Best Thing: https://youtu.be/k-yUdqRXijo
5. CMPSC/Math 451. Feb 25, 2015. Gaussian Quadrature. Wen Shen: https://youtu.be/uxQCjeo955o
6. How to write mathematics on Medium: https://medium.com/@tylerneylon/how-to-write-mathematics-on-medium-f89aa45c42a0
7. A web tool used to generate LaTex math images in this post: https://www.codecogs.com/latex/eqneditor.php