deBoor algorithm, split spline in segments

Question

I am still struggling with my current project, so after hours of thinking Ive decided to ask another question to you guys again. For my current project, I am implementing a software which interpolates a spline with given vertices. For this, I am using the deBoor algorithm with uniformed vector knots (3rd degree).

Since I am reproducing the behaviour of another software (basically I am creating an open source version of it), I want to analyse and know how certain things are implemented on his software.

Imagine you have 6 vertices, so there are 5 Segments (t 0..1, t 1..2, t 2..3, t 3..4, t 4..5). I want to know the lenghts of each segment, which is generated in that software (but can´t figure out how he calculates the segment lengths). Thats my question. Based on following example data, how did he calculated those segment lengths? What do you guys think?

Here, some example data, from the other software.

P0 (0, 0)
P1 (10, 10)
P2 (0, -10)
P3 (50, 10)
P4 (30, -10)
P5 (20, -10)

Which results following Segment lengths:

S0 7,86m
S1 7,9m
S2 26,33m
S3 11,28m
S4 11,39m

These are the Choord lengths of the segments:

C0 14,1421m
C1 22,3606m
C2 53,8609m
C3 28,302m
C4 10mm

Spline length:

64.76m

Here is an example plot (shows how the spline is subdevided into those segments):

Maybe this graph also helps to visualize how the segments are splitted (on straight line, so ignore y axis):

**Here is another example with 12 vertices (11 segments) **

P00 (0, 0)
P01 (10, 50)
P02 (10, -10)
P03 (30, 40)
P04 (30, 10)
P05 (20, 0)
P06 (20, -10)
P07 (40, -30)
P08 (49, -20)
P09 (50, 30)
P10 (39, 20)
P11 (39, 70)

Which results following Segment lengths:

S0 23.06m
S1 23.04m
S2 21.83m
S3 15.92m
S4 14.93m
S5 12.66m
S6 20.3m
S7 17.66m 
S8 32.8m
S9 26.11m
S10 26.2m

These are the Choord lengths of the segments:

C0 10m
C1 22.3607m
C2 53.8609m
C3 30.0167m
C4 14.1421m
C5 10m
C6 28.2843m
C7 14.1421m
C8 50m
C9 14.1421m
C10 50m

Spline length:

234.51m

Answer 1

First, let's try to get some terminology straight. On a cubic b-spline curve, there are four important types of points:

1. Interpolation points (which I will call i-points, for short). These are the points we want the spline to interpolate (i.e. pass through). Sometimes called the "data points".
2. Knot points. These are the points where adjacent cubic segments join. In many cubic spline implementations, these are the same as the i-points, but they don't have to be.
3. B-spline control points. These are the coefficients in the b-spline equation. They are sometimes called "control points", or "control vertices", or CVs, or deBoor points.
4. The Bezier control points of the cubic segments. There are four of these for each cubic segment.

When you use the word "vertices", I can't tell which kind of points you're talking about.

Then, there are two important sets of real numbers:

1. The knot sequence. These are the numbers that are used to construct the b-spline basis functions. These are also the parameter values at the knot points. When constructing cubic splines, people sometimes use knot values that are equally spaced; these are called "uniform" knots.
2. The "interpolation values" or "nodes". These are the parameter values at which the curve passes through the i-points. So, if $\tau_i$ is the i-th node and $Q_i$ is the i-th interpolation point, we have $C(\tau_i) = Q_i$. In most implementations of cubic splines, the node values are the same as the knot values.

To construct a b-spline curve that interpolates a given set of i-points, you just have to solve a linear system of equations to calculate the deBoor points. But, before you can do this, you have to decide what nodes and knots you're going to use. As I said above, most people make the nodes and the knots the same on cubic splines. In fact any increasing set of values will work as nodes, but the values are usually chosen so that their differences are somehow related to chord lengths (i.e distances between the i-points). The choice will dramatically change the shape of the resulting curve. There is a good discussion in these notes.

Your problem, as I understand it, is this: you are trying to guess what algorithm is being used to assign node values in some piece of software. That way, you can construct curves with the same shapes yourself.

You seem to be referring to the node values (or their differences, actually) as "segment lengths", or "chord lengths". But, in the pictures you showed, it appears to me that the node and knot values that are being used are just equally spaced, and are not related to any sort of length. See here for a discussion.

The other area of freedom in constructing b-spline curves is the end-conditions. Common techniques are "natural", "clamped", and "not-a-knot". I can't tell which of these is being used in your examples.

Answer 2

From all the data shown in the post, here is what I can deduct:

1. The P0, P1, P2,....appears to be the control points of the spline, not the interpolating points as they generally do not lie on the spline except the first and the last point.
2. The C0,C1,C2,...values are the segment length of the control point polygon.
3. The S0,S1,S2,...values are the spline's arc length within a certain parameter interval as they sum up to the spline's length.

Therefore, it seems the software (which you are mimicking the behavior) simply computes the arc length of the spline by dividing them into (N-1) segments (where N is the number of control points) uniformly in the parameter space and then compute the length of each segment. That is all.

If you want to know how to compute the arc length of a spline, you should be able to find some related articles in SO.

Answer 3

Another attempt at figuring out what your question is, and answering it ...

Maybe what you want to know is how to calculate the arclength of each segment of a cubic spline curve.

When I say a "segment", I mean a portion of the curve between two consecutive knot values (or knot points). A knot point is a location on the spline where two cubic segments join together. These are shown as small blue circles with red outlines in your picture. Let's call the two consecutive knot values $a = t_i$ and $b = t_{i+1}$.

I will assume you already have a function that gives you the point $C(t)$ on the curve corresponding to any given parameter value $t$. Then a nice simple way to calculate arclength (roughly) is by polyline approximation:

n = 50;
dt = (b - a)/(n - 1);
arclength = 0;

for (i = 0 ; i < n ; i++)
{
   t0 = a + i*dt;     p0 = C(t0) ;
   t1 = t0 + dt;      p1 = C(t1) ;
   arclength = arclength + distance(p0,p1);
}

The $n=50$ choice is somewhat arbitrary. Making it larger will give a more accurate arclength (up to a point), but will slow down the code.