Enumerating hexahedral cell vertices and faces in arbitrary dimension

Question

I have a Cartesian mesh in $d$ dimensions, and I would like to enumerate all the subcells of a given hexahedral cell. If I am just enumerating the vertices of a cell (or cells that contain a vertex) I can use Gray code, here is my code doing that.

You can see that this works because the Gray code sequence traverses the vertices of a hypercube, which is exactly what a $d$-dimensional hexahedralcell is. If the mesh is a tensor product (Cartesian), then the dual mesh is also made up of hypercubes and we can traverse cells around a vertex using the same algorithm.

How can this strategy be extended to handle edges and faces? Or, what strategy could handle them in a dimension independent way?

Answer 1

As you suggest, the binary representation works because the binary numbers with $d$ digits can be thought of as vectors representing the coordinates of the vertices of the $d$-dimensional hypercube. Now notice that the coordinates of an edge midpoint can be obtained by averaging the coordinates of two (adjacent) vertices and the coordinates of a face midpoint can be obtained by averaging the coordinates of two edge midpoints.

This suggests using a ternary (base 3) system, with each digit equal to 0, 1, or 2. Consider a hypercube whose volume is the tensor product of the intervals $[0,2]$. Then the coordinates of the vertices are all the $d$-digit ternary numbers with each digit equal to 0 or 2. The edge midpoint coordinates are all the $d$-digit ternary numbers with one digit equal to 1 and the remaining digits equal to 0 or 2. The face midpoint coordinates are all the $d$-digit ternary numbers with two digits equal to to 1 and the remaining digits equal to 0 or 2. This extends in the obvious way to higher-dimensional analogues of faces.

So for instance, the vertices of a cube ($d=3$) are

(0,0,0)
(0,0,2)
(0,2,0)
(2,0,0)
(0,2,2)
(2,0,2)
(2,2,0)
(2,2,2)

The edges are

(0,0,1)
(2,0,1)
(0,2,1)
(2,2,1)
(0,1,0)
(2,1,0)
(0,1,2)
(2,1,2)
(1,0,0)
(1,0,2)
(1,2,2)
(1,2,0)

and the faces are

(1,1,0)
(1,1,2)
(1,0,1)
(1,2,1)
(0,1,1)
(2,1,1)

Thinking about these coordinates even gives a simple way even to determine the number of $n$-faces of a $d$-dimensional hypercube. These correspond to all $d$-digit ternary numbers with $n$ digits equal to 1 and the remaining digits equal to 0 or 2, so there are $2^{d-n}\cdot {d\choose{n}}$ of them.

Two things I haven't addressed are:

1. Ordering; the Gray code's ingenuity is that adjacent vertices in the list are adjacent in space. I think you could achieve this with the representation I've described using an approach similar to Gray's, but the question doesn't specifically mention ordering so I didn't worry about it.

2. How to code this up. This is more of a programming question, and shouldn't be too difficult.

Answer 2

In addition to labeling all edges and faces there are also other questions I have found important in the same context:

• Numbering them in some particular way. deal.II uses a numbering where we first consider all edges that are parallel to the x-axis and sort them by their y,z-values (either 0 or 1) in lexicographic order, then all edges parallel to the y-axis and numbering them by their x,z-values, etc.

• As for the total number: In 1d, there are ne_1=1 edge. In 2d, the square is formed by replicating the 1d line twice at y=0 and y=1, making for two lines, but then we also have to connect all nv_1=2 vertices of old and replicated line, so ne_2=2*ne_1+nv_1=2+2=4. Then construct the cube by replicating the two squares and connecting all vertices, so ne_3=2*ne_2+nv_2=2*4+4=12. You get the recursion.