[Dune] Barycentric coordinates

[Aleksejs Fomins]

Hey Marco,

Have you heard of Octant Trees? You imagine that your grid is contained in a cube, which is split into 8 smaller cubes and so on recursively. Each cube-node knows which tetrahedra belong to it. You refine the cube until the number of entities per cube does not decrease significantly any more. Constructing such a tree is n*log(n) in terms of number of vertices in the grid, and finding an appropriate cube is log(n) for every query. You can then direct-search all the entities within the cube, as there should not be too many of them. I think for 3D grids with reasonably good quality elements (not a=1 b=1000 c=1000 for the sides of the triangle), the number of tetrahedra per leaf of the tree should be around 20.

Technically, you could reduce the search further, by determining the direction to the global coordinate, and compare it with the normals to each neighbor. However, this is also not for free, and usually you will have to check 3 out of 4 neighbors anyway. Since for linear grids isInside is not an expensive check, I do not think there is much advantage to be gained from this optimization if at all.

I already wrote OCTree once for Curvilinear Grid, however, there it is a little more tricky, and I have not yet finished testing it, so it is not officially part of the code just yet. Anyway, at least for linear grids it should not be more than 100 lines of code, so I am sure you can do it yourself ;)

Greetings,
Aleksejs

On 10.02.2016 16:11, Agnese, Marco wrote:
> Hi Oliver,
> 
> thank you very much for the interesting reference.
> 
> 
> Hi Andreas,
> 
> yes I was thinking about it. Nevertheless I figured out that if I compute the local coordinates of a point given in global coordinates using the inverse map g^-1 I directly obtain the barycentric coordinates of the point (the missing barycentric coordinate is simply 1-x1_local-x2_local). So there is no need to add the barycentric coordinates.
> 
> 
> Cheers,
> 
> Marco
> 
> 
> 
> _______________________________________________
> Dune mailing list
> Dune at dune-project.org
> http://lists.dune-project.org/mailman/listinfo/dune
>