<div dir="ltr">This at least needs to be in a FAQ in gmsh's manual. <div><br></div><div>These kinds of algorithms may be well known to people in mesh generation field, but people starting in numerical methods find it hard because either the software does it all under the hood in the equation solving or it doesn't do at all. It could be useful if there were some software in between or some place to look to find good algorithms.</div><div><br></div><div>My initial objective was not to ask for having this functionality at GMSH's core, but to ask people in the field for a good algorithm because the algorithms that I managed to develop are slow. I could take my time to develop the algorithm from scratch but I think that it's reasonable to consider that someone in the community already has a good algorithm. My algorithm is already very heavy, I am looking anywhere I can to save computational power.</div><div><br></div><div>I will try to implement this algorithm, I wonder if it can be adapted for n-d delaunay triangulations?</div><div><br></div><div>Anyway, maybe a community-driven wiki could be useful for these secondary topics after mesh generation... just a thought.</div><div><br></div><div>Thanks for the help!</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Em sáb, 30 de mar de 2019 às 10:38, Christophe Geuzaine <<a href="mailto:cgeuzaine@uliege.be">cgeuzaine@uliege.be</a>> escreveu:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
Hi guys,<br>
<br>
I think I probably have said this before: each numerical method will have its own needs: you might want neighbouring elements connected by a node, an edge or a face; you might want a single layer or multiple layers; you might want to include elements of lower dimension (boundaries) or not; you might want to go through geometrical entities, or mesh partitions, or not... and so on... So it's really better to compute this in your code to suit your needs.<br>
<br>
Here's a small example in Python, using the Gmsh API to compute neighbouring tetrahedra connected by a face (you can make this code more compact, but this is to illustrate how simple it is):<br>
<br>
```<br>
import gmsh<br>
<br>
gmsh.initialize()<br>
<br>
gmsh.model.add("my test model");<br>
gmsh.model.occ.addBox(0,0,0, 1,1,1);<br>
gmsh.model.occ.synchronize()<br>
gmsh.model.mesh.generate(3)<br>
<br>
# get tets and faces<br>
tets, _ = gmsh.model.mesh.getElementsByType(4)<br>
faces = gmsh.model.mesh.getElementFaceNodes(4, 3)<br>
<br>
# compute face x tet incidence<br>
fxt = {}<br>
for i in range(0, len(faces), 3):<br>
f = tuple(sorted(faces[i:i+3]))<br>
t = tets[i/12]<br>
if not f in fxt:<br>
fxt[f] = [t]<br>
else:<br>
fxt[f].append(t)<br>
<br>
# compute neighbors by face<br>
txt = {}<br>
for i in range(0, len(faces), 3):<br>
f = tuple(sorted(faces[i:i+3]))<br>
t = tets[i/12]<br>
if not t in txt:<br>
txt[t] = set()<br>
for tt in fxt[f]:<br>
if tt != t:<br>
txt[t].add(tt)<br>
<br>
print("neighbors by face: ", txt)<br>
<br>
gmsh.finalize()<br>
<br>
```<br>
<br>
We could add this in the demos/api directory if you think it's useful.<br>
<br>
Christophe<br>
<br>
<br>
<br>
<br>
<br>
> On 30 Mar 2019, at 10:51, Jeremy Theler <<a href="mailto:jeremy@seamplex.com" target="_blank">jeremy@seamplex.com</a>> wrote:<br>
> <br>
> Hey Yuri<br>
> <br>
> I asked the same question back in 2011:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2011/006878.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2011/006878.html</a><br>
> <br>
> All I got is a loose reference to Lohner's book:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2011/006881.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2011/006881.html</a><br>
> <br>
> Someone asked it again in 2012 with no response:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2012/007480.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2012/007480.html</a><br>
> <br>
> I went in again in 2013, again with no luck:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2013/008183.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2013/008183.html</a><br>
> <br>
> Something similar came back in 2014:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2014/008808.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2014/008808.html</a><br>
> <br>
> And again FVM:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2014/008908.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2014/008908.html</a><br>
> <a href="http://onelab.info/pipermail/gmsh/2014/009237.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2014/009237.html</a><br>
> <br>
> In 2017 I already mentioned that this was unsolved:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2017/011248.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2017/011248.html</a><br>
> <br>
> One more time in 2018:<br>
> <br>
> <a href="http://onelab.info/pipermail/gmsh/2018/012120.html" rel="noreferrer" target="_blank">http://onelab.info/pipermail/gmsh/2018/012120.html</a><br>
> <br>
> <br>
> So... is this enough to have something in Gmsh's core?<br>
> I proposed to add an optional section like $ElementNeighbour$ or something like this, listing the tag of the neighbours each elements has (including surface elements for volumetric elements so boundary conditions in FEM can be more efficiently written). I have somewhere a tool that reads a .msh and adds such a section, if somebody is interested I can dig into my archives and prepare a repository.<br>
> <br>
> I bet the neighbour list can be generated in O(n) inside Gmsh, which should beat any complex O(n log n) or naive O(n^2) implementention outside Gmsh.<br>
> <br>
> Regards<br>
> --<br>
> jeremy theler<br>
> <a href="http://www.seamplex.com" rel="noreferrer" target="_blank">www.seamplex.com</a><br>
> <br>
> <br>
> On Fri, 2019-03-29 at 16:00 -0300, Yuri Barros wrote:<br>
>> Hi all,<br>
>> <br>
>> I am trying to optimize my finite volume formulation and one thing that is taking too much computational time is to find adjacent cells. Is there any way I can extract from GMSH the adjacent elements of a given element in the local face order? Or is there any algorithm that people use routinely for this task?<br>
>> <br>
>> Thanks in advance!<br>
>> _______________________________________________<br>
>> gmsh mailing list<br>
>> <br>
>> <a href="mailto:gmsh@onelab.info" target="_blank">gmsh@onelab.info</a><br>
>> <a href="http://onelab.info/mailman/listinfo/gmsh" rel="noreferrer" target="_blank">http://onelab.info/mailman/listinfo/gmsh</a><br>
> _______________________________________________<br>
> gmsh mailing list<br>
> <a href="mailto:gmsh@onelab.info" target="_blank">gmsh@onelab.info</a><br>
> <a href="http://onelab.info/mailman/listinfo/gmsh" rel="noreferrer" target="_blank">http://onelab.info/mailman/listinfo/gmsh</a><br>
<br>
— <br>
Prof. Christophe Geuzaine<br>
University of Liege, Electrical Engineering and Computer Science <br>
<a href="http://www.montefiore.ulg.ac.be/~geuzaine" rel="noreferrer" target="_blank">http://www.montefiore.ulg.ac.be/~geuzaine</a><br>
<br>
<br>
<br>
</blockquote></div>