4
$\begingroup$

Some background context

In reading about NURBS I saw the definition that the B-Spline basis functions are defined by a recurrence relation. $N_{i,n} (u)= f_{i,n}(u) N_{i,n-1}(u) + g_{i+1,n}(u) N_{i+1,n-1}(u) $ with the $ N_{i,0}(u) $ being piecewise constant functions that are $1$ if $k_{i}\le u < k_{i+1} $ and $0$ otherwise. Where $k_{i}$ is the $i$th value of the knot vector.

The $f$ and $g$ functions were defined as $f_{i,n}(u)=\frac{u-k_{i}}{k_{i+n}-k_{i}}$ and $ g_{i,n}(u)=\frac{k_{i+n}-u }{k_{i+n}-k_{i}} $.

Statement of observed problem

Since the degree considered, $n$ for these helper functions is the same as the degree of the $N$ that is being calculated, and $N_{i,n}$ are calculated using these helper functions for $n$ as small as $1$, it follows that if any knots have multiplicity more than $1$ that near that knot $k_{i+1}-k_{i}$ the denominator of the defined helper functions is $0$.

Furthermore the definition of the NURBS curve $C(u)=\frac{\sum_{i=1}^{k}N_{i,n}(u)w_{i}\vec{P}_{i}}{\sum_{i=1}^{k}N_{i,n}(u)w_{i}}$, $f_{i,n}$ is calculated for all $i\in \{ 0,...,k \} $, where $k$ is the number of control points, and $n \in \{1,...,\mbox{Degree of the curve} \} $.

Thus if the knot vector contains a knot with multiplicity greater than $1$ before the $k$th knot then the definition of the curve contains a division by zero.

The conditions which produce this division by zero are more general than what I have shown here, but for the purposes of my question I believe that I only need to show that it can be a problem, not all the possible circumstances in which it can arise.

Requested information

I am hoping that someone can help me to understand how this is dealt with. It must be since NURBS are a common tool in some contexts. If someone can help me understand why I am wrong with this whole observation that would be just fine also.

My thoughts on the problem so far

My intuition would have me guess that setting $f_{i,n}(u)$, and $g_{i,n}(u)$ to $0$ in those cases where the denominator would be zero would work. The reasoning being that we don't need to care about properly interpolating between a point and itself, while $f$ and $g$ are intended as functions for interpolation. I do not, however, have anything more than a vague intuition to support this possibility.

$\endgroup$
1
$\begingroup$

The 0-degree basis function is defined as:

$$N_{i,0}(u) \lbrace^{1:k_i \leq u < k_{i+1}}_{0: otherwise}$$

If $k_i = k_{i+1}$ then $N_{i,0}(u)$ can never return 1, because no number $u$ can simultaneously be greater-or-equal and also less-than some other number.

Therefore in the 1st-degree basis function:

$$N_{i,1}(u) = f_{i,1}(u) \cdot N_{i,0}(u) + g_{i+1,1}(u) \cdot N_{i+1,0}(u)$$

If $f_{i,1}$ or $g_{i,1}$ has a division by zero, then the corresponding $N_{i,0}$ multiplier will = 0.

I suspect that due to the recursive nature of the basis functions, the same thing happens at higher orders. The rule that the multiplicity of a knot cannot be greater than the order of the curve is also probably involved somehow. I'm still learning this though, so I can't offer you a proof for either of these things.

$\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.