非结构化网格占有一席之地。

您可能想查看地球系统建模框架 (ESMF)。他们有一些重新网格化的代码——特别是为此目的——他们也用并行代码做了一些漂亮的事情。整个系统旨在耦合模型，因此那里可能还有其他有用的东西。

其他一些注意事项：

“没有办法有效地为任何重要数量的点做到这一点”

好吧，效率是一个相对的东西——一旦你在树结构中得到了网格，你可以在 O(logn) 中搜索它，虽然不是 O(1)，但它可以非常快，就像搜索常规网格一样是。

此外，听起来虽然需要在每个时间步进行插值，但如果网格不适应，那么从一个网格到另一个网格的映射保持不变。因此，您可以以任何方便的方式计算该映射（即每个网格中的哪个元素对应于另一个网格中的哪个元素），存储它，然后您无需再次计算它（直到网格更改）。

这给您留下了插值代码 - 您将希望在其中平衡精度和性能 - 三角形上的简单线性插值很快，并且可能足够好。

“我考虑过使用 kd-tree 搜索给定点的最近节点，然后我会使用该元素的形状函数”

请记住，最近的节点不会为您提供元素 - 因此您需要做更多的事情来找到您想要的元素。一种选择是使用 rtree 代替，它通过边界框存储/搜索 - 每次搜索都会获得多个元素，但您可以直接检查其中哪些是正确的。

如果我理解正确，您想通过在较粗的网格上插值来填充较细网格的值。在非结构化网格上进行线性插值的一种方法是使用 Delaunay 三角剖分（这就是 Matlab 的 griddata 和 TriScatteredInterp 命令的实现方式）。在构建网格点的三角剖分后，插值归结为定位包含目标点的三角形，计算其重心坐标，并使用顶点处的函数值来计算插值。 CGAL可以构造 n 维三角剖分（对于介质 n），并且还具有内置的2d 插值模块。

这就是我目前正在做的事情，除了我在正交点而不是节点处传输函数值。我在这里实现了我的问题的选择答案中解释的技术：Finding which triangles points are in。

基本上，假设你有 2 个网格$A$和$B$，并想从网格中传递信息$A$到网格$B$

1. 基于网格中的节点或正交点$B$, 构造一个点列表$p_i$在网格中进行评估$A$,
2. 排序评估点$p_i$基于希尔伯特曲线，
3. 构造网格的约束 Delaunay 扩展$A$（所有三角形在$A$，再加上一些外部三角形使形状凸出）
4. 从扩展版本的三角形开始$A$，在点的“大方向”上随机从一个三角形走到另一个三角形$p_1$直到你到达那里。然后继续往前走$p2$,$p3$等，直到你找到了哪些三角形$A$包含所有评估点。

如果你有$N$评价点和$M$扩展版中的三角形$A$，并且如果您忽略希尔伯特曲线排序，并且您确定性地行走，最坏的情况可能是$O(N \sqrt{M})$. 包括希尔伯特曲线排序和随机行走，我在实践中看到了更有效的结果，更像$O(max(N,M))$.

这是您真正希望避免使用非结构化网格的工作，因为对于任何大量的点都无法有效地执行此操作。您应该考虑使用至少以某种方式与每个网格相关的网格。例如，如果它们都是从粗网格的层次细化中获得的，那么您可以相对容易且有效地找出一个网格的插值点在另一个网格上的位置。