# Meshing software: connectivity between elements and boundary

I am implementing an algorithm which produces a 4d mesh for a cylinder with a given 3d base. This means, I have a 3d mesh and I want to generate a 4d mesh for the corresponding space-time cylinder. Currently I am using netgen for 3d mesh. I am able to generate the 4d vertices and the new 4d elements (pentatopes). This is done by applying a sort of the element-wise procedure for each 3d element. However, I also need boundary elements (which are tetrahedrons in 4d case).

The problem is that the boundary elements of the 3d mesh as produced by netgen are not connected to the 3d elements. I just have a set of triangle indices.

But what I need is to know whether a given 3d element has some of its faces at the boundary (and which one). If I know this, I could use it in the element-wise procedure and create a list of 4d boundary elements as well. But by know I only have a list of 3d boundary elements which contains vertex indices for each boundary triangle of the 3d mesh.

Can anyone give a hint of how one can do that, probably with another meshing software, or somehow?

Or probably there is a software which can generate 4d meshes for a space-time cylinders with, e.g., 3d sphere as a base?

I would appreciate any comments.

• Since you have the 3 vertex indices of each boundary triangle, find the tetrahedral cell that has these 3 vertices among its 4 vertices -- the triangle is a face of this tetrahedron. – Wolfgang Bangerth Dec 30 '16 at 23:52
• Thanks for the comment. But what you suggest means a large look-up - for each boundary triangle I'll look inside each tetrahedral cell, comparing indices. Seems that it is bad from the viewpoint of implementation. – VorKir Dec 31 '16 at 1:35
• Well, your comment is all nice and good, but if there is no mapping from faces to cells, then you need to construct one. You can make this more efficient by first constructing a mapping from vertices to cells, for example, or from cells to (boundary) faces and then build the queries you care about from these data structures. – Wolfgang Bangerth Jan 1 '17 at 2:47

• Thank you for this idea! Though it requires an array of size ~ O(number of all 4d faces) if I got it right. Which can be quite a lot of memory. Maybe, a more efficient way in my case would be to use a a set of boundary triangles of 3d mesh, which will lead to $O(N log M)$ additional operations (for each 3d face I will do a $log M$ search in the set of boundary 3D faces) where $M$ is the number of 3d boundary triangles and $N$ is the number of all 3D faces. – VorKir Jan 1 '17 at 22:23
• Yes, in your case you can probably reconstruct adjacency information in 3D, and deduce the 4D information from the 3D (since your 4D is an "extrusion" if I got it right). Then if you are in 3D, mem storage remains reasonable (and to avoid the $logM$ search, I'd rather attach face adjacency information to each cell). – BrunoLevy Jan 2 '17 at 11:17