I would like to know a good method for interpolating data between two unstructured grids, where one grid is a coarser version of the other.Efficiency is very important to me since I'm solving a transient PDE problem where I need to transfer data between the grids at every time step of the solution.I thought about using kd-tree for searching the nearest node of a given point, then I would use the shape functions of that element (FEM simulation) to interpolate the data. Is this a good solution? Are there better ones?Do you also know any robust and reliable library in C/C++ for this task?*I know there is a similar question, but it asks for the most accurate method on a structured grid.
Efficient interpolation method for unstructured grids?
interpolation
Unstructured grids have their place.You may want to look at the Earth System Modeling Framework (ESMF). They have some code for re-gridding -- specifically for this purpose -- and they've done some nifty stuff with parallel code, too. The whole system is designed to couple models, so there may be other useful stuff there as well.Some other notes:no way to do this efficiently for any significant number of pointswell, efficient is a relative thing -- once you've got the grid in a tree structure, you can search it in O(logn), which can be pretty darn fast, though not O(1), as searching a regular grid is.Also, it sounds like while the interpolation needs to be done at every time step, if the grids aren't adapting, then the mapping from one grid to another remains constant. So you can compute that mapping (i.e. which element in each grid corresponds to which element in the other) in whatever way is convenient, store it, and then you never need to compute it agin (until the grids change).That leaves you with the interpolation code -- where you will want to balance accuracy with performance -- simple linear interpolation across a triangle is fast, and may be good enough.I thought about using kd-tree for searching the nearest node of a given point, then I would use the shape functions of that elementremember that the nearest node doesn't get you the element -- so you'll want to do a bit more to find the element you want. One option would be to use an rtree instead, which stores/searches by bounding box -- you'll get more than one element with each search, but you can then check which of those is correct directly.