General concepts » Polytopes

Reference shapes, physical cells and their lower-dimensional entities.

Cells and their geometry

A mesh combines vertices, edges, faces and cells through incidence relations. The cells have the mesh's topological dimension; their coordinates lie in the embedding space. A triangular surface mesh therefore has dimension two even when its vertices have three coordinates.

Polytope::Type identifies a reference shape. A concrete Polytope also identifies an entity in a mesh, with its connectivity, attribute and geometric transformation.

Dimension and role

DimensionEntitiesRole
0PointsVertices
1SegmentsEdges; cells of a curve mesh
2Triangles and quadrilateralsFaces; cells of a surface mesh
3Tetrahedra, pyramids, hexahedra and wedgesVolume cells

A facet is an entity of dimension one less than a cell. Facets are edges in a two-dimensional mesh and faces in a three-dimensional mesh.

Supported reference shapes

Polytope::TypeDimensionVerticesReference construction
Point01A point
Segment12Unit interval
Triangle23Unit simplex
Quadrilateral24Product of two unit intervals
Tetrahedron34Unit simplex
Pyramid35Collapsed square cross-sections
Hexahedron38Product of three unit intervals
Wedge36Triangle times unit interval

The figures and tables use the reference vertices returned by Polytope::Traits(type).getVertex(i). The numbered markers identify the zero-based local vertex indices.

Image
Point reference vertex.
Image
Segment reference vertices.
Image
Triangle reference vertices.
Image
Quadrilateral reference vertices.
Image
Tetrahedron reference vertices.
Image
Pyramid reference vertices.
Image
Hexahedron reference vertices.
Image
Wedge reference vertices.

Reference vertices and local ordering

The tables give each reference vertex $\widehat v_i$ in local order. Coordinate tuples have the reference cell's topological dimension.

For a physical cell $K$ with local-to-global vertex connectivity $(I_0,\ldots,I_{n-1})$ , its geometric map satisfies $F_K(\widehat v_i)=x_{I_i}$ . The local index $i$ selects a position in that cell's connectivity; $I_i$ identifies the vertex in the mesh. Preserve this order when constructing connectivity or supplying geometric vertex data.

Point

The reference point is the unique element of $\mathbb R^0$ . Its coordinate vector is empty, written $()$ , and getVertex(0).size() is zero.

Local indexReference coordinates
0 $\widehat v_0=()$

Segment

Local indexReference coordinates
0 $\widehat v_0=(0)$
1 $\widehat v_1=(1)$

Triangle

Local indexReference coordinates
0 $\widehat v_0=(0,0)$
1 $\widehat v_1=(1,0)$
2 $\widehat v_2=(0,1)$

Quadrilateral

Local indexReference coordinates
0 $\widehat v_0=(0,0)$
1 $\widehat v_1=(1,0)$
2 $\widehat v_2=(1,1)$
3 $\widehat v_3=(0,1)$

Tetrahedron

Local indexReference coordinates
0 $\widehat v_0=(0,0,0)$
1 $\widehat v_1=(1,0,0)$
2 $\widehat v_2=(0,1,0)$
3 $\widehat v_3=(0,0,1)$

Pyramid

Vertices zero through three form the square base. The apex is vertex four, directly above vertex zero. Horizontal cross-sections shrink toward that apex.

Local indexReference coordinates
0 $\widehat v_0=(0,0,0)$
1 $\widehat v_1=(1,0,0)$
2 $\widehat v_2=(1,1,0)$
3 $\widehat v_3=(0,1,0)$
4 $\widehat v_4=(0,0,1)$

Hexahedron

Vertices zero through three lie on the bottom face. Vertices four through seven are their corresponding vertices on the top face.

Local indexReference coordinates
0 $\widehat v_0=(0,0,0)$
1 $\widehat v_1=(1,0,0)$
2 $\widehat v_2=(1,1,0)$
3 $\widehat v_3=(0,1,0)$
4 $\widehat v_4=(0,0,1)$
5 $\widehat v_5=(1,0,1)$
6 $\widehat v_6=(1,1,1)$
7 $\widehat v_7=(0,1,1)$

Wedge

Vertices zero through two form the bottom triangle. Vertices three through five are their corresponding vertices on the top triangle.

Local indexReference coordinates
0 $\widehat v_0=(0,0,0)$
1 $\widehat v_1=(1,0,0)$
2 $\widehat v_2=(0,1,0)$
3 $\widehat v_3=(0,0,1)$
4 $\widehat v_4=(1,0,1)$
5 $\widehat v_5=(0,1,1)$

Reference and physical coordinates

A geometric map $F_K:\widehat K\to K$ sends a reference point to a physical point. Reference coordinates determine basis values and reference quadrature samples; the map supplies physical coordinates and derivatives. On a curved cell, the map also depends on its geometric control points.

Reference vertices can be obtained directly from the library.

const Polytope::Traits traits(Polytope::Type::Pyramid);
for (size_t i = 0; i < traits.getVertexCount(); ++i)
{
  const auto& reference = traits.getVertex(i);
  // Use reference coordinates in the order defined by the element.
}

A Geometry::Point combines a cell with reference coordinates. Its Jacobian has embedding dimension rows and cell dimension columns. For surface meshes it is rectangular. The quadrature guide explains the corresponding measure factors in a complete checked example.

Generate a mesh

Uniform grids are available for supported volume-cell shapes. Axis counts specify vertices; coordinates initially have unit spacing. Selecting a reference shape and selecting the physical domain are separate choices. Scale the generated coordinates to obtain a unit domain.

Lower-dimensional entities

A triangle has three edges and three vertices; a tetrahedron has four faces, six edges and four vertices. The mesh stores these incidences through Connectivity. Relations are computed on demand. For example, compute(1, 2) discovers edges and associates each edge with its incident cells in a triangular mesh.

Inspect cell-induced ordering

getSubPolytopes(entities, cellIndex, d) enumerates a cell's $d$ -dimensional sub-entities in their local order. Each result contains a geometry type and an ordered vertex key. The key contains mesh vertex indices in the order induced by the parent cell.

For a pyramid with cell vertex key $(I_0,I_1,I_2,I_3,I_4)$ , the face sequence uses the following positions in that key.

Local faceShapeParent-cell vertex positions
0Quadrilateral $(0,1,2,3)$
1Triangle $(0,1,4)$
2Triangle $(1,2,4)$
3Triangle $(2,3,4)$
4Triangle $(3,0,4)$

The edge sequence follows the base loop $(0,1),(1,2),(2,3),(3,0)$ , followed by the apex edges $(0,4),(1,4),(2,4),(3,4)$ .

Inspect stored connectivity

compute(D, d) builds the cell-to-entity relation for a mesh of topological dimension $D$ . compute(d, D) builds the reverse relation, listing the cells incident to each entity. getIndex(d, key) resolves a vertex key to the entity's mesh index, and getPolytope(d, index) exposes its stored vertex order.

The following code inspects the edges and faces of cell zero in a small pyramid mesh. It uses Rodin::Geometry, Rodin::Context, <iostream> and <vector>.

Mesh mesh = Mesh().UniformGrid(Polytope::Type::Pyramid, {2, 2, 2});
auto& connectivity = mesh.getConnectivity();
const size_t D = mesh.getDimension();
const Index cellIndex = 0;

std::cout << "Cell vertices";
for (Index vertex : connectivity.getPolytope(D, cellIndex))
  std::cout << ' ' << vertex;
std::cout << '\n';

for (size_t d : {size_t{1}, size_t{2}})
{
  connectivity.compute(D, d);
  connectivity.compute(d, D);
  std::vector<Connectivity<Context::Local>::SubPolytope> entities;
  connectivity.getSubPolytopes(entities, cellIndex, d);

  for (size_t local = 0; local < entities.size(); ++local)
  {
    const auto& induced = entities[local].vertices;
    const auto index = connectivity.getIndex(d, induced);
    std::cout << "Dimension " << d << ", local " << local
              << ", mesh index " << *index << '\n';
    std::cout << "  Cell-induced vertices";
    for (Index vertex : induced)
      std::cout << ' ' << vertex;
    std::cout << "\n  Stored vertices";
    for (Index vertex : connectivity.getPolytope(d, *index))
      std::cout << ' ' << vertex;
    std::cout << "\n  Incident cells";
    for (Index cell : connectivity.getIncidence({d, D}, *index))
      std::cout << ' ' << cell;
    std::cout << '\n';
  }
}

This cell has eight edges and five faces. The reverse incidence lists expose which entities are shared with neighboring cells.

The entries returned by getIncidence({D, d}, cellIndex) are mesh indices of the incident entities. Each index is resolved through getPolytope(d, index) when its vertex order is needed.

A shared edge or face has one stored vertex order. An incident cell can induce a different order on that same entity. Comparing the two ordered keys gives the vertex permutation needed to align traces or local facet data. Oriented integration additionally requires the appropriate normal convention for each incident cell. The interface traces tutorial demonstrates two-sided values on a shared edge.

Traverse mesh entities

The iteration guide describes the cell, vertex and facet iterators. Entity indices belong to their own dimension; edge index zero and cell index zero identify different objects.

Select a cell family

Cell shape, geometric mapping, finite element family and polynomial degree jointly determine approximation properties. Triangles and tetrahedra are simplices; quadrilaterals and hexahedra support tensor-product constructions; wedges combine a triangular section with an interval. Pyramids connect quadrilateral and triangular faces and require their own reference basis. Accuracy comparisons should keep the problem, degrees of freedom, quadrature and mesh quality explicit.

Continue