3d surface interpolation

[RichardBallantyne]

Hi folks,

I need to do some 3D surface interpolation.  Koji Ohashi's tripolation vi does not work for my application.  Here is what I need:

Input1: 2D array of containing 3 columns, X, Y, Z.  These are scattered data points (i.e. the points xy do not form any regular grid, and are not equally spaced).

Input2:  x

Input3:  y

Output:  z_estimated

The algorithm will use interpolation on input1 to get z_estimated at coordinates x (input2) and y (input3).  The algorithm must be able to calculate z_estimated even when input2 and input3 are coordinates for locations that are outside the boundaries of the input1 surface.  This is where Koji's tripolation algorithm fails.

Example:

Input1 =

 0  0  5

 2  1  3

-3  4 -10

 6  2  5

 1  3  50

Input2 = -4

Input3 = 5

As you can see, input2 and input3 are coordinates to a location outside the boundaries in Input1 (the closest point is -3,4).  In case you were curious, here is a screenshot of where Koshi's fails.  Here is a screenshot of where my bilinear interpolation succeeds, but the problem with my bilinear interpolation algorithm is that Input1 cannot contain scattered data points.  It is going to be a major pain to rewrite my bilinear interpolation algorithm to accept scattered data points (I don't even know where to start!).  Therefore, I would much rather download someone else's code rather than reinvent the wheel.  Has someone already coded something like this in LabVIEW?

I need this 3D surface interpolation code for the following application:

I have am building an automated probe station.  I need to know exactly how far to lower the probe onto the device pad.  If the probe isn't lower far enough, then there is no electrical contact, and the station halts requiring user input (bad!).  If the probe is lowered too far, then it gouges the DUT and destroys it (very bad!).  So to do this right, I need to know the distance between the probe and the pad.  Typically this distance is between 400 and 600 microns.  This distance varies due to surface height non-uniformity accross the chuck.  I already have some code that quickly measures the height of the chuck at several locations.  Now I need to be able to estimate the height at any other location based on those actual surface height measurements.

Thanks!

Richard Ballantyne

[johnsold]

Richard,

Is linear extrapolation good enough for the points outside the boundaries? If so, locate the three nearest points. Three points define a plane. Fine the altitude of the plane at (Input2, Input3). I have not worked out the equations, but any book on solid analytic geometry should have what you need. (Everybody keeps one of those on his or her desk, right?)

Actaully this would work within the boundaries as well.

Special cases of more than 3 points equidistant from the target point would need to be addressed.

Lynn

[RichardBallantyne]

Hi Lynn,

Thanks for your reply.  Yes, linear interpolation is acceptable for locations that are outside the surface (input1) boundaries.  I like your suggestion about forming a plane using the 3 points nearest to point xy (inputs 2&3).  Then I could just extrapolate z at xy from the equation for that plane.  However, as I was saying, I'd rather not have to write this code myself since it will take time and my boss wanted this done a month ago.  If anyone has code for this, I'd really appreciate you post a link to it on this forum.

Thanks!

Richard

[unclebump]

Try a google search for '3D Scattered Data Interpolation'. It is some neat info.

http://cis.k.hosei.ac.jp/~F-rep/OBS_MultiCSRBF_SMI03.pdf

[unclebump]

Maybe you could download a demo of this program.

http://www.goldensoftware.com/products/surfer/surfer.shtml

[nissen6]

I wrote some programs to calculate intersections between lines and planes in 3D using some vector equations. By defining the plane using the closest three points and defining the line using the points x,y,0 and x,y,1 the intersection of the plane and this line should be at x,y,z where z is the value you are looking for. I have attached a quick and dirty example (LV 7.1).

[Jarrod_S.]

Which version of LabVIEW are you using? LabVIEW 8 has built in functionality for interpolating over a 2D surface. The 2D interpolation methods include bilinear, nearest, bicubic, and bicubic spline. You might check here to see some of the new features available.

[RichardBallantyne]

Hi Jared,

I'm using LabVIEW 7.1.1 here at work.  I have version 8 at home that I am evaluating.  I'll take a look at those 2D interpolation vi's in version 8 when I get home from work today.  If they'll work for my application, I see if it is possible to rewrite them for LabVIEW 7.1.1.  If it is possible, I might just do that depending on how much work is involved.

Also, after thinking about Lynn's suggestion, I realized that it won't work.  If the 3 closest points to xy form a straight line and not a plane, then z_estimate will be wrong.  Dealing with this special case gracefully would really complicate the code I think.

Thanks,

Richard

[RichardBallantyne]

The 2D interpolation vi in LabVIEW 8 will not work because it doesn't accept scattered xyz data points.  If it does, then please show me an example where the inputs are organized as described in my original post.  I also couldn't find a way to convert scattered xyz data points to an array of xyz points where xy are equally spaced.  Converting scattered 2D data (just xy, not xyz) to equally spaced data is simple (just use 1D Interpolation.vi), but that isn't what I need.  The way most 3D data is gathered in the real world is in this format:

x1 y1 z1

x2 y2 z2

.   .   .

.   .   .

xn  yn  xn

...for a total of n 3D points.  Unfortunately, all the 3D vis built into LabVIEW require that the x and y values form a grid.  These restrictions on the inputs to the 3D vis really limits their usefulness.  Its been this way as far back as I can remember (LabVIEW 6).  It would be nice if these vis could be made more flexible.

So far the most helpful reply to this thread has been unclebumps link to:

http://cis.k.hosei.ac.jp/~F-rep/OBS_MultiCSRBF_SMI03.pdf

...page 6 has exactly what I need.

Coding this is going to be a real challenge however.  Basis functions is something I was taught 5 years ago in a linear alegbra course in college...

Cheers,

Richard

[RichardBallantyne · Accepted solution]

I finally found exactly what I needed in this thread!

https://forums.ni.com/t5/LabVIEW/Need-help-with-array/m-p/237887

The code that does this is called:  using3dpolyfitandevaluation.llb

I think something like this should be built into LV because it is extremely useful when working with scattered 3D data.

I've attached the code to this thread in case anyone wants it.  I've seen multiple versions of this code on these forums, but this unmodified version works.  Some of the other versions posted to these forums don't.

Cheers,

Richard C Ballantyne