grid irregularly spaced data to a regular grid

I’m trying to take data that is irregularly spaced data (say V(x,y,z) where x, y, and z are some floating point coordinates) and find what the value of the data is on a Cartesian coordinate system ( say V(x’, y’, z’) where x’, y’, and z’ integers coordinates)

Now using a texture this is quite straight forward to take regularly spaced data and interpolate it onto whatever coordinates you want, but the opposite situation is not so apparent to me. Maybe using some type of sorting to know how many data points are proximal (euclidean norm?) to a grid point, and manually interpolating from there? Or using some sort of triangulation like qhull does (is there a qhull for CUDA?)?
I’m not sure the best way to go about it. I’m sure somebody’s done it, and I really don’t want to reinvent the wheel here.
Any ideas?


Sibson’s natural neighbour interpolant is probably the best way to do what you want. As you almost guessed, that requires a Voronoi tesselation. I don’t know whether there is an off the shelf CUDA implementation for doing Delanuay triangulations or not. Most of my unstructured mesh work was done “BC” (before CUDA). One of the computational geometers who pass through here might know more.

Thanks avidday. Yes, I was hoping there was a multi dimension Delanuay algorithm out there, but I had only seen this 2-D one on the internets.
The method of populating a regular grid used in the CUDA particles in the SDK could be used for the interpolation, but I’m not sure.


I am also looking for a qhull-like 3D triangulation algorithm in CUDA… it seems that all I can find on the web are 2D implementations of it…