2
$\begingroup$

I am following this paper Approximate Arc Length Parametrization, M. Walter & A. Fournier, 1996 and have succesfully implemented the direct solution, as in finding the length $s(t)$ given $t$. This algorithm calculates the length of a curve given by $B(t)=f(P_0, P_1, P_2, P_3, t)$ at three different points ($t_1=\frac{1}{3}$, $t_2=\frac{2}{3}$, $t_3=1$), namely $s_1=s(\frac{1}{3})$, $s_2=s(\frac{2}{3})$ and $s_3=s(1)$. The length is approximated using Gauss-Legendre integration along the curve. Using these three points (and $t_0=0\Rightarrow s_0=s(0)=0$) we construct a polynomial of degree $n=3$ of the form $\hat{s}(t)=a_tt^3+b_tt^2+c_tt$ that approximates $s(t)$. This is used to lookup curve lengths at any point along the curve.

However, ideally I'd like to reverse this lookup, which the paper says is fairly easy. Just swap $t$ and $s(t)$ in the algorithm and that's it. We construct a polynomial ($n=3$) of the form $\hat{t}(s)=a_ss^3+b_ss^2+c_ss$. I found two ways this can be implemented:

1. Pick points at certain $s$

Calculate $s_3=s(1)$ (ie. the total curve length) and set $s_1=\frac{1}{3}s_3$ and $s_2=\frac{2}{3}s_3$. Now calculate the corresponding $t_1$, $t_2$, and $t_3=1$. The solution will be:

$\begin{bmatrix}t_1\\t_2\\1\end{bmatrix}=\begin{bmatrix}s_1^3&s_1^2&s_1\\s_2^3&s_2^2&s_2\\s_3^3&s_3^2&s_3\end{bmatrix}\begin{bmatrix}a_s\\b_s\\c_s\end{bmatrix}=\begin{bmatrix}\frac{1}{27}s_3^3&\frac{1}{9}s_3^2&\frac{1}{3}s_3\\\frac{8}{27}s_3^3&\frac{4}{9}s_3^2&\frac{2}{3}s_3\\s_3^3&s_3^2&s_3\end{bmatrix}\begin{bmatrix}a_s\\b_s\\c_s\end{bmatrix}$

$\Rightarrow\begin{bmatrix}a_s\\b_s\\c_s\end{bmatrix}= \left(\begin{bmatrix}\frac{1}{27}s_3^3&\frac{1}{9}s_3^2&\frac{1}{3}s_3\\\frac{8}{27}s_3^3&\frac{4}{9}s_3^2&\frac{2}{3}s_3\\s_3^3&s_3^2&s_3\end{bmatrix}\right)^{-1}\begin{bmatrix}t_1\\t_2\\1\end{bmatrix}$

This gives a fairly nice determinant for the matrix inverse, and we can obtain $t_1$ and $t_2$ using the bisection method on the Gauss-Legendre quadrature.

2. Pick points at certain $t$

Calculate $s_1=s(\frac{1}{3})$, $s_2=s(\frac{2}{3})$ and $s_3=s(1)$. Then solve for $a_s$, $b_s$ and $c_s$:

$\begin{bmatrix}t_1\\t_2\\t_3\end{bmatrix}=\begin{bmatrix}\frac{1}{3}\\\frac{2}{3}\\1\end{bmatrix}=\begin{bmatrix}s_1^3&s_1^2&s_1\\s_2^3&s_2^2&s_2\\s_3^3&s_3^2&s_3\end{bmatrix}\begin{bmatrix}a_s\\b_s\\c_s\end{bmatrix}$

$\Rightarrow\begin{bmatrix}a_s\\b_s\\c_s\end{bmatrix}=\begin{bmatrix}s_1^3&s_1^2&s_1\\s_2^3&s_2^2&s_2\\s_3^3&s_3^2&s_3\end{bmatrix}^{-1}\begin{bmatrix}\frac{1}{3}\\\frac{2}{3}\\1\end{bmatrix}$

This should in my opinion give valid results, but unless my implementation is wrong (I double checked most of it!), I'm wondering if there is a misstep in thought?

EDIT

Looks like I was implementing the inverse matrix wrong...seems to work now. I've chosen approach 1 as this will give an equal spacing along the known variable $s$ as the interpolation points. Approach 2 could, as I presume, in interpolation point that are too close to each other to realistically approach the real $t(s)$ function.

$\endgroup$
  • $\begingroup$ This is a fantasic write up as I was looking for exactly the same 'inverse' problem. I was able to make method (2) work but was wondering if you could expand a bit on your first method, specifically the method on obtaining t1 and t2: > This gives a fairly nice determinant for the matrix inverse, and we can obtain t1 and t2 using the bisection method on the Gauss-Legendre quadrature. $\endgroup$ – kuwerty Jan 3 at 11:42
  • 1
    $\begingroup$ Basically you use the bisection method to find $t_1$ and $t_2$. Ie. we know $s_1 = \frac{1}{3} s_3$, so we use a root finding algorithm to find $t_1$ for which $s(t_1) = s_1$ is satisfied. It is a numerical method that works well for this monotonically increasing function. For a reference implementation in Go, see github.com/tdewolff/canvas/blob/master/path_util.go#L170 $\endgroup$ – Taco de Wolff Jan 4 at 1:33
  • 1
    $\begingroup$ I've written an article covering this topic if it suits anybody: tacodewolff.nl/posts/20190525-arc-length $\endgroup$ – Taco de Wolff May 25 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.