2
$\begingroup$

I've been reading all possible papers about splines for a couple of days now and couldn't answer my own question.

  • All papers I was able to find start the definition of Bezier Curve by either introducing it's parametric form with known positions of control points. Wikipedia.
  • Or by fitting natural splines to the curve

None of the above actually covers my problem, which is, simply put: I have the numerical values of coordinates $(x, f(x))$ of a curve and I need to find the positions of control points.

So basically I want to find the position of control points so that the generated spline would fit perfectly over my coordinates. I'd also need knots values, obviously. Any ideas?

$\endgroup$
  • $\begingroup$ There are many ways to create a spline interpolating given set of data points. Do you really need a B-spline or you are ok with multiple cubic Bezier curves? $\endgroup$ – fang Jan 12 '18 at 1:16
2
$\begingroup$

It is not clear whether the "control points" you need is for Bezier curve or for B-spline curve. Since many graphic toolkits only take quadratic/cubic Bezier curves, I will assume this is what you want.

For creating multiple Bezier curves interpolating a given set of data points, you can go with Catmull-Rom spline interpolation or natural spline interpolation. Both schemes will produce a cubic Bezier curve in between each two data points but the natural spline interpolation will require solving a linear equation set.

If you really want to do B-spline interpolation, please refer this link for more details. You will have to decide a knot vector in advance, which is typically derived from the parameters for the points so that the linear equation matrix is not ill-conditioned.

$\endgroup$
1
$\begingroup$

Check David Eberly's "Least-Squares Fitting of Data with B-Spline Curves":

https://www.google.com.ar/url?sa=t&source=web&rct=j&url=https://pdfs.semanticscholar.org/c285/3cda7a849fee18bcc8bbf2136b1493acb92a.pdf&ved=2ahUKEwiUsvzRutHYAhVFlJAKHUpiCOMQFjAGegQIDRAB&usg=AOvVaw3cMGSLne8D5W2ly8X-Bghf

It is one of the best explanations that I have seen. The C++ implementation is given in his Open Source software library named Geometric Tools.

Basically you have your sample points $P_k$ and you want to compute the control points $Q_i$ such that:

$ \sum_i^n {N_i(t_k) Q_i} = P_k$

This system can be writen in matrix form. Let us define the column vector $\textbf Q = \{ Q_0, ..., Q_n \}$, the column vector $\textbf P= \{ P_0, ..., P_m \}$ and the matrix $\textbf A = \{ a_{ij} = N_j(t_i) \}$ the system is:

$\textbf A \textbf Q = \textbf P$

The system need to be solved once per component of $\textbf Q$, so matrix decomposition is best suited in terms of performance and accuracy. The matrix $\textbf A$ is sparse and banded so can be efficiently pre-factored. However, often its condition number is high so numerical precision is needed (avoid gaussian elimination).

If you have more sample points than control points (as is usually the case $m > n$) then the matrix $\textbf A$ is skinny (the system is overdetermined) and the best solution can be found in the least squares sense as:

$(\textbf A^T \textbf A) \textbf Q =\textbf A^T \textbf P$

Knot vector can be chosen Uniform as Dr Eberly suggest in his paper.

$\endgroup$
  • $\begingroup$ Please note that LS fitting does not force the spline to pass thru the data points exactly. $\endgroup$ – fang Jan 13 '18 at 21:06
1
$\begingroup$

If you want your curve to exactly pass through the given data points, then you are doing spline interpolation. If you look up this term, you will find lots of material.

For each data point that's interpolated, you get a linear equation involving the (unknown) control points. Combining these equations, you get a linear system that you can solve to get the control points.

There's a good description on this web page.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.