2

I need to construct a 3D B-spline surface and sample it multiple times at various parametric coordinates. The nearest solution I found was to use bisplev, which expects a tck input calculated by bsplprep. Unfortunately i cannot use that tck component because it produces a surface that passes through the control points, while what I want is a surfaces computed in the B-spline basis. So I manually construct the tck input bsplev can use to produce the desired surface.

Unfortunately, I can't figure out how to do this without using 2 nested loops: 1 for each uv query, and one for each spacial component. The latter is acceptable but the former is very slow when dealing with very large query arrays.

Here's the code:

import numpy as np
import scipy.interpolate as si

def bivariate_bspline(cv,u,v,uCount,vCount,uDegree,vDegree):
    # cv = grid of control vertices
    # u,v = list of u,v component queries
    # uCount, vCount = number of control points along the u and v directions
    # uDegree, vDegree = curve degree along the u and v directions
    
    uMax = uCount-uDegree # Max u parameter
    vMax = vCount-vDegree # Max v parameter
    
    # Calculate knot vectors for both u and v
    u_kv = np.clip(np.arange(uCount+uDegree+1)-uDegree,0,uCount-uDegree) # knot vector in the u direction
    v_kv = np.clip(np.arange(vCount+vDegree+1)-vDegree,0,vCount-vDegree) # knot vector in the v direction
    
    # Compute queries
    position = np.empty((u.shape[0], cv.shape[1]))
    for i in xrange(cv.shape[1]):
        tck = (u_kv, v_kv, cv[:,i], uDegree,vDegree)
        
        for j in xrange(u.shape[0]):
            position[j,i] = si.bisplev(u[j],v[j], tck)

    return position

Test:

# A test grid of control vertices
cv = np.array([[-0.5       , -0.  ,        0.5       ],
               [-0.5       , -0.  ,        0.33333333],
               [-0.5       , -0.  ,        0.        ],
               [-0.5       ,  0.  ,       -0.33333333],
               [-0.5       ,  0.  ,       -0.5       ],
               [-0.16666667,  1.  ,        0.5       ],
               [-0.16666667, -0.  ,        0.33333333],
               [-0.16666667,  0.5 ,        0.        ],
               [-0.16666667,  0.5 ,       -0.33333333],
               [-0.16666667,  0.  ,       -0.5       ],
               [ 0.16666667, -0.  ,        0.5       ],
               [ 0.16666667, -0.  ,        0.33333333],
               [ 0.16666667, -0.  ,        0.        ],
               [ 0.16666667,  0.  ,       -0.33333333],
               [ 0.16666667,  0.  ,       -0.5       ],
               [ 0.5       , -0.  ,        0.5       ],
               [ 0.5       , -0.  ,        0.33333333],
               [ 0.5       , -0.5 ,        0.        ],
               [ 0.5       ,  0.  ,       -0.33333333],
               [ 0.5       ,  0.  ,       -0.5       ]])

uCount = 4
vCount = 5
uDegree = 3
vDegree = 3

n = 10**4 # make 10k random queries
u = np.random.random(n) * (uCount-uDegree) 
v = np.random.random(n) * (vCount-vDegree) 
bivariate_bspline(cv,u,v,uCount,vCount,uDegree,vDegree) # will return n correct samples on a b-spline basis surface

Speed test:

import cProfile
cProfile.run('bivariate_bspline(cv,u,v,uCount,vCount,uDegree,vDegree)') # 0.929 seconds

So nearly 1 sec for 10k samples, where the bisplev call takes the lion's share of computation time because it's being called 10k times for each space component.

I did try to replace the for j in xrange(u.shape[0]): loop with a single bisplev call giving it the u and v arrays in one go, but that raises a ValueError: Invalid input data at scipy\interpolate\_fitpack_impl.py", line 1048, in bisplev.

Question

Is there a way to get rid both, or at minimum the uv query loop and do all the uv queries in a single vectorized operation?

Community
  • 1
  • 1
Fnord
  • 5,365
  • 4
  • 31
  • 48
  • What goes wrong if you try `si.bisplev(u, v, tck)`? The method `bisplev` is supposed to accept arrays. –  Oct 27 '17 at 21:17
  • @Desire it raises a `ValueError("Invalid input data")` at `scipy\interpolate\_fitpack_impl.py", line 1048, in bisplev raise ValueError("Invalid input data")` – Fnord Oct 27 '17 at 22:40

1 Answers1

2

Short answer: replace

for i in xrange(cv.shape[1]):
    tck = (u_kv, v_kv, cv[:,i], uDegree,vDegree)
    for j in xrange(u.shape[0]):
        position[j,i] = si.bisplev(u[j],v[j], tck)

with

for i in xrange(cv.shape[1]):
    position[:, i] = si.dfitpack.bispeu(u_kv, v_kv, cv[:,i], uDegree, vDegree, u, v)[0]

Explanation

bisplev does accept arrays as si.bisplev(u, v, tck), but it interprets them as defining an xy-grid. Hence, u and v must be sorted in ascending order, and evaluation will be performed on all pairs (u[j], v[k]), the output being a 2D array of values. This is not what you want; squaring the number of evaluations is probably bad, and it's not going to be easy to extract the values you actually want from the 2D array returned (they are not necessarily on the diagonal, since your u, v were not sorted to begin with).

But the call method of SmoothBivariateSpline includes a boolean parameter grid, setting which to False makes it just evaluate the spline at (u[j], v[j]) pairs. The vectors u, v no longer need to be sorted, but now they must be of the same size.

But you are preparing your own tck. This presents two approaches: seek to instantiate SmoothBivariateSpline with hand-made tck; or read the source of its call method and do what it does when the parameter grid is set to False. I went with the latter approach.

  • thanks you!!! huge performance improvement! unless there's a way to also get rid of the loop for each space dimension, this wins! – Fnord Oct 29 '17 at 04:15
  • @user6655984 would this work then: `tck = si.bisplrep(x,y,z); tx, ty, c, kx, ky = tck; z_q = si.dfitpack.bispeu(tx, ty, c, kx, ky, x_q, y_z)[0]` for `x_q, y_q` the query vectors? – roshambo Dec 01 '22 at 18:25