At the bottom of De Boor’s Algorithm, it is said that
De Boor’s algorithm also works for NURBS curves. We just multiply every control point by its weight converting the NURBS curve to a 4D B-spline curve, perform de Boor’s algorithm on this 4D B-spline curve, and then project the resulting curve back by dividing the first three components with the fourth and keeping the fourth component as its new weight.
Then modifying the code from B-Spline derivative using de Boor’s algorithm, I came up with the following.
import numpy as np
import math as m
weights = [0.3, 1, 1, 2, 1, 1, 0.5, 1, 1, 3, 1]
def deBoor(k, x, t, c_, p):
c = []
for point, w in zip(c_, weights):
c.append([point[0]*w, point[1]*w, point[2]*w, w])
c = np.array(c)
d = [c[j + k - p] for j in range(0, p+1)]
for r in range(1, p+1):
for j in range(p, r-1, -1):
alpha = (x - t[j+k-p]) / (t[j+1+k-r] - t[j+k-p])
d[j] = (1.0 - alpha) * d[j-1] + alpha * d[j]
return np.array([
d[p][0] / d[p][3],
d[p][1] / d[p][3],
d[p][2] / d[p][3]
])
def deBoorDerivative(k, x, t, c_, p):
c = []
for point, w in zip(c_, weights):
c.append([point[0]*w, point[1]*w, point[2]*w, w])
c = np.array(c)
q = [p * (c[j+k-p+1] - c[j+k-p]) / (t[j+k+1] - t[j+k-p+1]) for j in range(0, p)]
for r in range(1, p):
for j in range(p-1, r-1, -1):
right = j+1+k-r
left = j+k-(p-1)
alpha = (x - t[left]) / (t[right] - t[left])
q[j] = (1.0 - alpha) * q[j-1] + alpha * q[j]
return np.array([
q[p-1][0] / q[p-1][3],
q[p-1][1] / q[p-1][3],
q[p-1][2] / q[p-1][3]
])
def finiteDifferenceDerivative(k, x, t, c, p):
f = lambda xx : deBoor(k, xx, t, c, p)
dx = 1e-7
return (- f(x + 2 * dx) \
+ 8 * f(x + dx) \
- 8 * f(x - dx) \
+ f(x - 2 * dx)) / ( 12 * dx )
points = np.array([[i, m.sin(i / 3.0), m.cos(i / 2)] for i in range(0, 11)])
knots = np.array([0, 0, 0, 0, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 1.0, 1.0, 1.0, 1.0])
a = deBoorDerivative(7, 0.44, knots, points, 3)
b = finiteDifferenceDerivative(7, 0.44, knots, points, 3)
print(a)
print(b)
Although the derivative calculated from finite difference is not the same as the one when using deboors algorithm.
[ 9.125 1.02221755 -2.22839545]
[16.85238398 0.14138772 -5.90135073]
