所以我有一个由具有八个节点的元素组成的 3D 网格，每个单元有 12 条边，在我的模拟过程中，我必须将来自这些节点的数据插入到单元内具有给定 x、y 和 z 值的点上. 我知道三线性插值可以完成这项工作，但是考虑到每个单元格的形状可能完全不同，是否有更快的方法来做同样的事情？
此外，对于我来说，是否有一种更简单、更快的方法来确定给定点所在的单元格，而不是遍历所有单元格并使用不等式来查找边界？
什么是在 3D 空间中插入一个点的好、快速的方法
计算科学
插值
3d
2021-12-20 02:38:13
2个回答
要定位包含给定节点的单元格，我建议使用 AABB-Tree（参见 [1] 中的介绍）。我正在开发的地理库 [2] 中有一个实现。CGAL [3] 中也有一个（如果您喜欢 C++ 模板）。
一旦您找到了包含该点的单元格，三线性插值（如您所建议的）就很容易实现（并且高效，在计算方面不会花费很多）。通常，定位包含该点的单元格占主导地位的计算时间。
编辑（再想一想）：如果你的单元格的边界被分解成三角形（因为每个单元格有 12 个面，似乎是这样），那么，为了有一个与你的几何图形相一致的插值，它可能更有意义（实际上）将细胞分解为四面体，确定包含该点的四面体并在其中进行线性插值。它比三线性插值花费更多，但三线性插值假设面是双线性四边形（而不是成对的线性三角形）。
[1] http://www.azurefromthetrenches.com/introductory-guide-to-aabb-tree-collision-detection/
[2] http://alice.loria.fr/software/geogram/doc/html/mesh__AABB_8h.html
你的第一个问题我没有答案，但我对后者有一些想法。
为了有效地搜索和查找包含某个点的单元格，您可以使用空间散列或四叉树之类的方法将 3D 域离散化为一组框，其中每个框都包含与该框相交的单元列表。
然后，您可以有效地找到数据结构中的哪个框包含给定点，并遍历与该框相交的少量单元格以找到包含您的点的单元格。
使用上述方法，您可以大大减少您检查以找到匹配的单元格的数量，无论您的网格有多非结构化。