I'm working on a project where I'll need to be able to interpolate scalar potential values at arbitrary points in a 3-D box from a large (potentially millions to billions of points) collection of values that were calculated at points of convenience (roughly randomly and uniformly distributed) that are not on a regular grid. I'll be computing a trajectory and interpolating values of this potential at points along along the trajectory, so my queries will consistently be at points near the most recently used point.
Without much background in this area, my initial idea would be to put the known points into a k-d tree and access the tree each time I need to interpolate a value. An alternative would be to sort and bin the points and then use them to interpolate values onto a rectangular grid, and then interpolate from the regular grid as needed.
Are there other more specialized data structures and interpolation methods that might be useful for this task?