4

A bspline curve of order $k$ is given by $$C(t) = \sum_{i=0}^n P_i N_{i,k}(t).$$ where $P_i$ are the control points and $N_{i,k}(t)$ a basis function defined on a knot vector $$T = (t_0,t_1,...t_{n+k}).$$ with $$N_{i,1}(t) = \begin{cases}1 & t_i \le t \lt t_{i+1} \\ 0 & \text{otherwise} \end{cases}$$ $$N_{i,k}(t) = \frac{t-t_i}{t_{i+k-1}-t_i}N_{i,k-1}(t)+\frac{t_{i+k}-t}{t_{i+k}-t_{i+1}}N_{i+1,k-1}(t).$$

A clamped bspline curve has the additional property that the first and last knot in $T$ are of multiplicity $k$, e.g. $T=(0,0,0,0,0.5, 1,1,1,1)$ for a cubic spline.

(Formulas are based on Shape Interrogation for Computer Aided Design and Manufacturing)

What I don't understand now is why the curve at $t=1$ will coincide with the last control point. If I run the recursive definition of the basis functions, I will always come to the point where $$N_{i,1}(1) = \begin{cases}1 & t_i \le 1 \lt t_{i+1} \\ 0 & \text{otherwise}\end{cases}.$$ In the example above where $T=(0,0,0,0,0.5,1,1,1,1)$, I have the intervals $[0,0),[0,0.5),[0.5,1), [1,1)$. None of these will satisfy the condition $t_i \le 1 \lt t_{i+1}$. So all ends of my recursion will result in 0, and $C(1)=0$.

Where am I wrong? Or is there a special case for intervals of form $[a,a)$ ? I implemented a simple version of the formulas above that I can provide if necessary. For $P = ([0,0], [0,1], [1,1], [1,0])$ and $T=(0,0,0,0,1,1,1,1)$ I got

this result

tsabsch
  • 171

3 Answers3

3

In you example, the b-spline definition only makes sense on the intervals $[0,0.5]$ and $[0.5,1]$. You shouldn't even be considering intervals like $[0,0]$ and $[1,1]$.

There are good explanations in these notes.

For good implementations, look in "The NURBS Book" by Tiller and Piegl.

bubba
  • 43,483
  • 3
  • 61
  • 122
  • Yes, you are right, $[0,0)$ and $[1,1)$ should not be considered. However, the intervals $[0,0.5)$ and $[0.5,1)$ are half-closed, so I still don't understand the behaviour at $t=1$. I'm currently reading "The NURBS book". Thanks for suggesting it. – tsabsch Jul 29 '16 at 14:08
3

Okay, so "The NURBS book" is regarding $t=0$ and $t=1$ explicitly as special cases:

Since we are using intervals of the form $u \in [u_i, u_{i+1})$, a subtle problem in the evaluation of the basis functions is the special case $u=u_m$. It is best to handle this at the lowest level by setting the span index to $n(=m-p-1)$. Hence, in this case $u\in(u_{m-p-1},u_{m-p}]$.

Source: Piegl, L. A., & Tiller, W. (1997). The NURBS book. Berlin: Springer. page 68.

The algorithms A2.1 and A2.4 described below in this chapter also consider the special cases $u=u_m$ and $u=u_0$.

Especially A2.4, "OneBasisFun", which computes a basis function is relevant to me. From the code:

if ((i == 0 && u == U[0]) || (i == m-p-1 && u == U[m])) {
    Nip = 1.0; return;
}

Source: Piegl, L. A., & Tiller, W. (1997). The NURBS book. Berlin: Springer. page 75.

So I will simply regard and treat them as special cases.

tsabsch
  • 171
1

Actually, the value 1.0 will satisfy interval $[1.0,1.0)$. Basically, using your particular example you will get $N_{5,1}(1.0)=N_{6,1}(1.0)=N_{7,1}(1.0)=1.0$. Since $N_{i,k}$ is obtained from a linear combination of $N_{i,k-1}$ and $N_{i+1,k-1}$, you will get $N_{5,2}(1.0)=N_{6,2}(1.0)=1.0$, then $N_{5,3}(1.0)=1.0$ and $N_{4,4}(1.0)=1.0$. This is how you get $C(1.0)$ to fall on the last control point.

Programming wise, you will encounter $0/0$ situations during above evaluation. Therefore, it is often that we treat this as a special case and simply return 1.0 without going through the recursive formula.

fang
  • 3,570
  • I think this depends how you define an interval. To my (and wikipedias) understanding, an interval $[a,a)$ is an empty set. If we would define $a\in[a,a)$ then I'd agree with you. – tsabsch Jul 30 '16 at 11:16
  • If the interval in question were taken to be the empty set, then the spline curve would be undefined at $t=1.0$, which would be particularly unhelpful in the case of, for example, curve subdivision. Rigorously, you're right in that such an interval shouldn't have any elements, but by the same token, a special case is necessary to rid algorithmic evaluation of instances allowing division by zero. Really, it's a complicated way to define a B-spline as beginning and ending at its first and last control points. – Vessel Oct 12 '23 at 12:32