Potential Division by zero in the construction of NURBS basis functions: how to handle?

766 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.