# What would be a good, fast, way to interpolate a point in 3D space

So I have a 3D mesh made of elements with eight nodes, 12 sides per cell, and in the course of my simulations, I would have to interpolate data from those nodes onto a point inside the cell with a given x, y and z value. I know Trilinear Interpolation does the job, but would there be a faster way to do the same, given that the shapes of each cell can be completely different?

Also, is there a simpler, faster way for me to pinpoint the cell in which the given point resides, than looping over all the cells and using inequalities to find the bounds?

• I think you mean six sides per cell, right ? Jun 5 '17 at 16:57
• 12 sides sorry. Edited it now. Jun 5 '17 at 16:58
• 12 sides ? I guess that your element is a hexahedron (deformed cube) with each quadrangular face splitted into two triangles. Is that right ? Jun 5 '17 at 17:01

To locate the cell that contains a given node, I'd suggest using an AABB-Tree (see introduction in ). There is an implementation in the Geogram library  that I'm developping. There is also one in CGAL  (if you love C++ templates).

Once you have located the cell that contains the point, trilinear interpolation (as you suggest) is quite easy to implement (and efficient, does not cost a lot in terms of computation). In general, locating the cell that contains the point dominates computation time.

Edit (one more thought): if the border of your cell is decomposed into triangles (as it seems to be since you got 12 faces per cell), then, to have an interpolation that is coherent with your geometry, it may make more sense to (virtually) decompose the cells into tetrahedra, determine the tetrahedron that contains the point and do linear interpolation in it. It costs more than trilinear interpolation, but trilinear interpolation supposes that faces are bi-linear quads (instead of pairs of linear triangles).

I don't have an answer for your first question, but I have some thoughts for the latter.

To efficiently search and find cells that enclose some point, you can discretize your 3D domain into a set of boxes using something like a spatial hash or quad tree, where each box holds a list of cells that intersect with that box.

You could then efficiently find what box in your data structure enclosed a given point and loop through the small number of cells that intersect with that box to find which encloses your point.

With the above approach, you can greatly reduce the number of cells you check to find one that matches, no matter how unstructured your mesh is.

• If this isn't a core part of the project, then there are libraries out there (eg. VTK) which will implement cell locators for you. Jun 4 '17 at 19:51