Dune::Functions::Experimental::FaceOrientations< dim > Class Template Reference

A class encoding the orientation of the subentities of an entity. More...

#include <dune/functions/functionspacebases/lagrangebasis.hh>

Public Member Functions
	FaceOrientations ()=default
	Default construct FaceOrientations with index 0.
template<class VertexIds , std::size_t... codims>
	FaceOrientations (const Dune::GeometryType &geometryType, const VertexIds &vertexIds, const Dune::index_constant< codims > &... codimensions)
	Construct FaceOrientations for given vertex ids. More...
std::size_t	faceOrientationIndex (std::size_t subEntity, std::size_t codim) const
	Return index of the orientation for the given face.

Detailed Description

template<std::size_t dim>
class Dune::Functions::Experimental::FaceOrientations< dim >

A class encoding the orientation of the subentities of an entity.

The FaceOrientations class provides the orientation of all faces of a grid element in 2d and 3d relative to their canonical orientation provided by the respective ReferenceElement.

Since 0d-faces (a.k.a. vertices) only have a single orientation this is only relevant for 1d-faces (edges) and 2d faces (triangles and quadrilaterals). Notice that the orientations of a face are the automorphisms of the respective edge graph. I.e. the orientations of an edge are elements from the symmetric group \(S_2\) while the orientations of triangles and quadrilaterals are elements from the dihedral groups \(D_3\) and \(D_4\), respectively. The internal encoding of a face orientation describes how its global orientation can be mapped to its local orientation. These two orientations are defined as follows:

• The ReferenceElement of a grid element provides a canonical local orientation for each face which is induced by the order of the face vertices in the ReferenceElement. This orientation associates zero-based consecutive local indices to the vertices of a face. Since the local orientation depends on the mapping of the element to the ReferenceElement, the same face may have different local orientations when viewed from different adjacent grid elements.
• Given a set of globally unique vertex indices or ids, we can also associate a unique global orientation to each face as follows: We first select the face vertex with the smallest global id and denote it by \(P_0\). Among its neighboring vertices within the face (one for an edge, two for a 2d-face) we again select the one with the smallest global id and denote it by \(P_1\). Then there is a unique automorphisms of the face that maps the edge \((P_0,P_1)\) to the edge with local vertex indices 0 and 1. We identify this automorphism with the face orientation.

Binary encoding of all face orientations

The FaceOrientations class now encodes these automorphisms for all faces of the element in binary form. Since we have \(|S_2|=2\) we can store the edge orientation of each edge in a single bit, while we need three bits to identify one of the \(|D_3|=6\) or \(|D_4|=8\) orientations of a 2d-face. To furthermore distinguish between triangle orientations from \(D_3\) and quadrilateral orientations from \(D_4\) we use another bit indicating if the respective face is a triangle or quadrilateral. Since we have at most 12 edges and 6 2d-faces for elements up to dimension 3 we can use a bitfield with 36 bits as underlying storage. The 12 lowest order bits encode the 1d-face orientations. These are followed by 6 block with 4 bits for the 2d-faces.

• For a 1d-face (edge) the bit is unset if local and global orientation coincide and set if the edge needs to be flipped.
• For a 2d-face (triangle or quadrilateral) the global orientation can be mapped to the local one by first rotating the vertices counter-clockwise and then reflecting the face across the xy-diagonal. The two lowest order bits store the number of counter clockwise rotations and the third is set if a subsequent reflection is required. This encoding makes use of the fact that a generator for the groups \(D_3\) and \(D_4\) is given by \(\{r,s\}\) where \(r\) is an elementary rotation and \(s\) a reflection. In the binary representation of the automorphisms \(a=s^j r^i\) the first two bits encode the exponent \(i\) and the third one the exponent \(j\). The fourth bit is unset for a triangle and set for a quadrilateral. Interpreting the bits from right to left we get:

  \[ (\underbrace{b_4}_{\text{is quadrilateral}}, \underbrace{b_3}_{j = b_3},\underbrace{b_2,b_1}_{i = 2 b_2 + b_1}) \]

The 1 or 4 bits stored for each 1d- or 2d-face can be interpreted as an index from 0,1 or 0,...,15, respectively. This index identifies the orientation of the corresponding face and is unique when viewing the face from different elements. It can e.g. be used for a table lookup of the face DOF permutation required to uniquely identify face DOFs for higher order Lagrange elements.

The following tables depict all possible face orientations for triangle or quadrilateral 2d-faces. Vertices and edges of the face are both enumerated according to the ReferenceElement. The global vertex ids are for simplicity denoted as 0,1,2,3 while any selection of pairwise different less-than comparable ids can be used. The primary edge is the one that induces the global orientations, i.e., connecting the vertex with smallest id to its neighbors with smallest id. The edge orientations in the table indicate if the (globally oriented) edge of the face is flipped with respect to the ReferenceElement.

Triangle orientations

Global vertex ids	edge orientations	primary edge	rotations	reflection	automorphism	is quadrilateral	bit-encoding	index
0,1,2	0,0,0	0->1	0	no	\(s^0 r^0\)	no	0000	0
1,2,0	0,1,1	2->0	1	no	\(s^0 r^1\)	no	0001	1
2,0,1	1,1,0	1->0	2	no	\(s^0 r^2\)	no	0010	2
unused			3	no	\(s^0 r^3\)	no	0011	3
0,2,1	0,0,1	0->2	0	yes	\(s^1 r^0\)	no	0100	4
2,1,0	1,1,1	2->1	1	yes	\(s^1 r^1\)	no	0101	5
1,0,2	1,0,0	1->0	2	yes	\(s^1 r^2\)	no	0110	6
unused			3	yes	\(s^1 r^3\)	no	0111	7

Notice that using 4 bits is redundant for a triangle since only 0,1, or 2 rotations are relevant leading to the unused indices 3 and 7. Similarly only six combinations of edge orientations are possible for triangle

Quadrilateral orientations

Global vertex ids	edge orientations	primary edge	rotations	reflection	automorphism	is quadrilateral	bit-encoding	index
0,1,2,3	0,0,0,0	0->1	0	no	\(s^0 r^0\)	yes	1000	8
0,1,3,2	0,0,0,1
0,2,3,1	0,1,0,1
1,2,0,3	1,0,0,0	2->0	1	no	\(s^0 r^1\)	yes	1001	9
1,3,0,2	1,1,0,0
2,1,0,3	1,0,1,0
2,3,1,0	1,1,0,1	3->2	2	no	\(s^0 r^2\)	yes	1010	10
3,2,1,0	1,1,1,1
1,3,2,0	0,1,0,1
2,0,3,1	0,0,1,1	1->3	3	no	\(s^0 r^3\)	yes	1011	11
3,0,2,1	1,0,1,1
3,0,1,2	1,0,1,0
0,2,1,3	0,0,0,0	0->2	0	yes	\(s^1 r^0\)	yes	1100	12
0,3,1,2	0,1,0,0
0,3,2,1	0,1,0,1
2,3,0,1	1,1,0,0	2->3	1	yes	\(s^1 r^1\)	yes	1101	13
3,2,0,1	1,1,1,0
3,1,0,2	1,0,1,0
2,1,3,0	0,1,1,1	3->1	2	yes	\(s^1 r^2\)	yes	1110	14
3,1,2,0	1,1,1,1
1,2,3,0	0,1,0,1
1,0,2,3	0,0,1,0	1->0	3	yes	\(s^1 r^3\)	yes	1111	15
1,0,3,2	0,0,1,1
2,0,1,3	1,0,1,0

Notice that there are always three possible permutations of vertex ids for a quadrilateral that lead to the same primary edge and thus the same orientation. This corresponds to the fact that the dihedral group \(D_4\) of quadrilateral automorphisms is a subgroup of the symmetric group \(S_4\) of all vertex permutations. Furthermore for a quadrilateral the face orientation cannot be deduced from the edge orientations alone.

Complexity bounds

The algorithm to compute the orientations of the faces uses in the constructor of FaceOrientations tries to minimize the number of vertex index comparisons while preventing the use of full lookup tables because the latter can become very large in 3d. In general we need one comparison per edge and additional one or two comparisons per quadrilateral face. The following table lists the number of minimal an maximal number of comparisons of the implemented algorithm for the respective geometry types. For comparison this also lists the number of comparisons in an optimal sorting network of appropriate size.

Geometry type	number of vertices	min. index comparisons	max. index comparisons	optimal sorting network
line	2	0	0	1
triangle	3	3	3	3
quadrilateral	4	5	6	5
tetrahedron	4	6	6	5
pyramid	5	9	10	9
prism	6	>=12	<=15	12
hexahedron	8	>=18	<=24	19

Constructor & Destructor Documentation

FaceOrientations()

template<std::size_t dim>

template<class VertexIds , std::size_t... codims>

Dune::Functions::Experimental::FaceOrientations< dim >::FaceOrientations ( const Dune::GeometryType &  geometryType, const VertexIds &  vertexIds, const Dune::index_constant< codims > &...  codimensions  )

inline

Construct FaceOrientations for given vertex ids.

Parameters

geometryType	GeometryType of the element
vertexIds	Range of global vertex ids for all element vertices
codimensions	Dune::index_constants for all requested codimensions

The orientation will only be computed for sub-entities of the requested codimensions. Codimensions larger than the grid dimension will be ignored.

References Dune::power(), Dune::range(), and Dune::transformedRangeView().

---

The documentation for this class was generated from the following file:

• dune/functions/functionspacebases/lagrangebasis.hh