How to get a map which relates the new vertices to the old triangles?

User Help Library User Help
#1

Hi all,

I have a question regarding a functionality which I don’t know if it is available in MMG or not.
After a mesh adaptation process one may want to interpolate a FEM function over the new created mesh. For this purpose, it would be computationally advantageous to know in advance the triangle index of the old mesh which contains a new created vertex in the new mesh. Is it possible to do that in MMG 2D?

If not: would it be computationally advantageous to take track of edge splitting-coarsening-swapping and so modify such map for each of this operation inside MMG, with respect to usual algorithms to find the triangle containing a vertex? If yes, any tips on how to do that?

Thanks in advance for any help.

ps. I refer to P1 FEM functions

#2

Hi Marcus,

Welcome to this forum.

Mmg doesn’t compute the location of the new vertices within the old mesh but you are right, it will probably be easier for us to give this data than for an external user. However, I am not sure that it will be very efficient because Mmg uses an iterative process that pass through a large amount of transitionnal operators (splits, collapses…). You can see the number of each call if you raise the Mmg verbosity to 5 (-v 5).

Moreover, we choose to not provide the node location because the needed data depends on the method of interpolation that the user will use.
For example: the location of the new nodes within the old mesh is sufficient for non-conservative interpolation but for conservative interpolation, you will need to know the supermesh of the old and new meshes.

  • If you don’t want to code the P1 interpolation by yourself you can use the mshint software available within the https://github.com/ISCDtoolbox/AdaptTools repository (developped by Pascal Frey): it uses the same file format than Mmg (the Medit file format).

  • Otherwise, a way to find the location of a point inside a mesh is to start from a random triangle and to compute the barycentric coordinates of the point inside this triangle. These coordinates will allow to know if the point is inside the triangle or, if it is outside, in which direction you will need to travel (following the adjacency relationships and the barycentric coor in the successive triangles you will find the suitable triangle).

I hope that it will help you.
Regards,

Algiane

#3

Hi, Algiane,

Thanks for your reply. I have the same question as Marcus.
Because I want to use the new mesh generated by MMG for the next step calculation, I used the explicit algorithm for the FEM calculation, therefore, the nodal mapping is required for the calculation after refinement. I know Kratos used MMG as a third package, but I failed to find some information how did they map the nodal information (maybe they use the implicit algorithm and recalculate the case totally again).
I am also trying to add functions to judge the whether the node is in one element, actually it will cost very long extra time to do this work, e.g. if the new node number is n, and the old element number is M, the total times for the judgment maybe over O(M*n).
I am just wondering whether there is new update about this functionality?
Many thanks.
Kind regards

#4

Hi @jasonr ,

I don’t know how if and how the solution interpolation is done within Kratos, you can maybe contact the developers to get some information about that?

Regarding the process of localization, to my knowledge, there are at least two big classes of methods:

  • the localisation using buckets (==grid) or octree : you create a grid (that I will call a bucket) or an octree and you store the elements of the initial mesh in the suitable cell of the bucket/octree. Then, when you search to localize a point of the adapted mesh into the initial one, you just have to localize the point inside the bucket/octree and to search if it belongs to the element of the input mesh stored in this cell (it may be needed to search also in neighbouring cells, depending on the implementation). This method is robust to the non convexity of meshes but buckets are not very well adapted to the case where you have a very tiny object inside a large domain (most of meshes elements fall in the same few cells of the bucket so the research maybe exhaustive). Octrees work pretty well in any cases but require a little more time and effort to code.

  • the localization using the barycentric coordinates of the points of the adapted mesh into the elements of the initial one: you start from an arbitrary element (let say the element of index 1), barycentric coordinates gives you the direction in which you have to travel and you travel the element by adjacency relationships. If point localization fail (due to non convexity of the mesh), you start again from a new element that has not yet been processed. In the worst case, you have to precess your entire mesh to find the point but it is very rare. My memory may be wrong and I did not find papers that confirm this but I believe that the algo is in n log(n) in most cases. It is this algo that is implemented in mshint.
    If you choose to implement your own localization method using a barycentric localization you can enable the USE_POINTMAP CMake flag of Mmg. It adds a src field to mesh points and when you get your adapted mesh, this field contains the index of an element of the input mesh not too far from the point (but we don’t ensure that the element contains the point). Normally it allows to speed up the point localization. Just note that it has been developped for internal use only (and it is still experimental) so we don’t provide API to get this field and we don’t guarantee the results ;-).

Of course, you can also couple both methods and there must be other ways of doing the localization…

Sorry to not be more helpful but localization / interpolation methods (as metric computation) are in fact research field different from adaptation methods, even if very close and if each brick is needed to do mesh adaptation inside a solver.

Regards,
Algiane

#6

Hi, Algiane,

Thanks for your reply. Your answer is very helpful to me to understand the interpolation before and after refinement.

Kratos uses closest point transfer (similar to you mentioned barycentric way), shape function projection transfer and least-square projection transfer to interpolate the internal variables. See Combination of an adaptive remeshing technique with a coupled FEM–DEM approach for analysis of crack propagation problems | SpringerLink. I found the adaptive mesh refinement strategy (AMR) in Kratos is only compatible with static problem (from their examples), therefore only the history dependent internal variables, e.g., damage value and plastic are required to be transferred to new mesh.

My code is a kind of explicit method using the central difference integration. Many variables such as displacement, velocity and internal stress should be inherited by the new mesh if I want to continue the calculation for the new mesh based on the results from the last step. I tried the shape function projection transfer method, but it seems the unbalance force before and after remesh will disturb the computation in the new mesh. This paper (https://link.springer.com/content/pdf/10.1007/s10915-021-01414-1.pdf) implies that an extra balancing stage should be considered for the AMR to get a stable dynamic transfer.

Therefore, whether the interpolation is not essential for AMR if I use implicit scheme or for the dynamic scheme, if I recalculate the models from t0 after each mesh refinement (of course this way will cost more time)? How did you solve this problem in the Lagrangian motion example? (I tried to use the Lag module, but I got error when I install LinearElsticity)

Thanks in advance for any help.

Regards,
Jason

#7

Hi,

I don’t have a great knowledge of interpolation technics in fact (since multiple years, I am working only on Mmg robustification and user support).

  1. In fact, in my previous answer, I have decoupled the problem of point localization between meshes and solution transfer: when I was speaking about barycentric coordinates, I was only speaking about localization. After that, you can apply multiple technics of solution transfer.

  2. To avoid the introduction of too large errors when transfering your solution from one mesh to another one, I think that you have to identify which important properties on your solution field you need to preserve during the solution transfer and to search if it already exists some technic to preserve it while transferring your solution. For example, lot of methods asks for the mass conservation, in this case, you can perform conservative interpolation (https://hal.inria.fr/inria-00354509/document).

  3. For transient problem, indeed, it would be inefficient to recompute the models after each mesh refinment. Instead, you can use some adaptation scheme that takes into account the time evolution of your solution (see https://www.ljll.math.upmc.fr/frey/publications/ijnmf.pdf for example).

  4. I am not sure of which example of lagrangian motion you are speaking, but either the technic of 3. has been used (if the example is a complete simulation of a physical problem), either the example is a basic call of Mmg and, in this case, we just apply the maximal possible displacement wihtout any interpolation.

I am sorry to not be more helpful,

Best Regards,
Algiane