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.

  • $\begingroup$ 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. $\endgroup$ Commented Dec 30, 2016 at 23:52
  • $\begingroup$ 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. $\endgroup$
    – VorKir
    Commented Dec 31, 2016 at 1:35
  • $\begingroup$ 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. $\endgroup$ Commented Jan 1, 2017 at 2:47

1 Answer 1


Given for each element the indices of its vertices, you can efficiently retrieve face adjacencies by sorting the faces lexicographically, then the pairs of elements that share a face are contiguous in the sorted facet list. The boundary elements are those that have a facet that appears only once in the list.

The more detailed procedure is given in my answer to this question [1] (for surfacic meshes, can be easily adapted to volumetric meshes).

[1] Meshing options to generate number of the sides of and element (tetgen-triangle)

  • $\begingroup$ 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. $\endgroup$
    – VorKir
    Commented Jan 1, 2017 at 22:23
  • $\begingroup$ 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). $\endgroup$
    – BrunoLevy
    Commented Jan 2, 2017 at 11:17

Your Answer

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

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