0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I think you mean six sides per cell, right ? $\endgroup$
    – BrunoLevy
    Jun 5, 2017 at 16:57
  • $\begingroup$ 12 sides sorry. Edited it now. $\endgroup$
    – Ayush Agrawal
    Jun 5, 2017 at 16:58
  • $\begingroup$ 12 sides ? I guess that your element is a hexahedron (deformed cube) with each quadrangular face splitted into two triangles. Is that right ? $\endgroup$
    – BrunoLevy
    Jun 5, 2017 at 17:01

2 Answers 2

Reset to default
0
$\begingroup$

To locate the cell that contains a given node, I'd suggest using an AABB-Tree (see introduction in [1]). There is an implementation in the Geogram library [2] that I'm developping. There is also one in CGAL [3] (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).

[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

[3] http://doc.cgal.org/4.9/AABB_tree/index.html

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – origimbo
    Jun 4, 2017 at 19:51
  • $\begingroup$ @origimbo maybe you should add this comment to the original post or add your own answer? $\endgroup$
    – spektr
    Jun 4, 2017 at 19:52
  • $\begingroup$ It is a part of the project, and I am constrained in using non standard libraries in my project. $\endgroup$
    – Ayush Agrawal
    Jun 5, 2017 at 17:00
  • $\begingroup$ @AyushAgrawal Seems to me you may want to roll your own code using the tips I mention if you can't easily incorporate a library that already exists for this sort of thing. BrunoLevy's comments might also give you another thought as to how you might approach this problem. $\endgroup$
    – spektr
    Jun 5, 2017 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.