How to interpolate partially gridded intput?

If you had a griddedInterpolant defined by two vectors of coordinates:

x       = [1:10]'; % x coordinates
y       = [10:100]'; % y coordinates
[xg,yg] = ndgrid(x,y); % Grid over x and y coordinates
zg      = xg.^2 + 3*yg; % Value of z at grid coordinates
F       = griddedInterpolant({x,y},zg); % Interpolant of z given x and y

then you could interpolate all possible combinations of the vectors:

xi = rand(1000,1)*max(x); % Values to interpolate in x dimension
yi = rand(1000,1)*max(y); % Values to interpolate in y dimension

using:

zgi = F({xi,yi}); % Interpolated values of z given xi and yi

One could also create all pairs of xi and yi, and then interpolate, by doing:

% Enumerate all possible combinations of xi and yi
temp  = combvec(xi',yi')';
xvi   = temp(:,1);
yvi   = temp(:,2);

% Interpolate
zvi = F(xvi,yvi);

In the end, we would have no difference between these methods, i.e.

max(abs(zi(:)-zvi)) = 0

However, the first method is faster. Now I have a problem. I have have the vectors:

x1 = [x1_1 x1_2]';
x2 = [x2_1 x2_2]';
x3 = [x3_1 x3_2]';
x4 = [x4_1 x4_2]';

I would like to interpolate all possible combinations of {x1,x2,[x3 x4]}, that is:

x1_1 x2_1 x3_1 x4_1
x1_1 x2_1 x3_2 x4_2
x1_1 x2_2 x3_1 x4_1
x1_1 x2_2 x3_2 x4_2
x2_1 x2_1 x3_1 x4_1
x2_1 x2_1 x3_2 x4_2
x2_1 x2_2 x3_1 x4_1
x2_1 x2_2 x3_2 x4_2

Notice I never wanted to interpolate a combination that contained (x3_1,x4_2) or (x3_2,x4_1). Is there a way I can smartly interpolate the above where I still use grid vectors for x1 and x2 (which corresponds to the faster method of interpolation in my original example). If I enumerate all the possible combinations that I want to interpolate (which corresponds to the slower method of interpolation in my original example), the griddedInterpolant evaluation will be slower because (for example) it will not know that when it interpolates (x1_1,x2_1,x3_1,x4_1) and (x1_1,x2_1,x3_2,x4_2) to reuse the information about (x1_1,x2_1) from the first evaluation in the second.

Please let me know if any of this is unclear and thanks in advance for any help.

[Adam]

There is a scatteredInterpolant too, although I have never used it. Not sure if it would be any help in this case though.

[Philip]

Thanks. I would like to use griddedInterpolant because it is much faster than scatteredInterpolant. However, depending on how you use it, it can be even faster (i.e. using grid vectors as an in the original method above). I was just wondering if I could still use grid vectors in a smart way.