3. Meshes¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
When employing the finite element method, we represent the domain on which we wish to solve our PDE as a mesh. In order to work with meshes, we need to have a somewhat more formal mathematical notion of a mesh. The mesh concepts we will employ here are loosely based on those in [Log09], and are typical of mesh representations for the finite element method.
3.1. Mesh entities¶
A mesh is composed of topological entities, such as vertices, edges, polygons and polyhedra.
The (topological) dimension of a mesh is the largest dimension among all of the topological entities in a mesh.
In this course we will not consider meshes of manifolds immersed in higher dimensional spaces (for example the surface of a sphere immersed in \(\mathbb{R}^3\)) so the topological dimension of the mesh will always match the geometric dimension of space in which we are working, so we will simply refer to the dimension of the mesh.
A topological entity of codimension \(n\) is a topological entity of dimension \(dn\) where \(d\) is the dimension of the mesh.
Armed with these definitions we are able to define names for topological entities of various dimension and codimension:
entity name 
dimension 
codimension 

vertex 
0 

edge 
1 

face 
2 

facet 
1 

cell 
0 
The cells of a mesh can be polygons or polyhedra of any shape, however in this course we will restrict ourselves to meshes whose cells are intervals or triangles. The only other twodimensional cells frequently employed are quadrilaterals.
The topological entities of each dimension will be given unique numbers in order that degrees of freedom can later be associated with them. We will identify topological entities by an index pair \((d, i)\) where \(i\) is the index of the entity within the set of \(d\)dimensional entities. For example, entity \((0, 10)\) is vertex number 10, and entity \((1, 10)\) is edge 10. Fig. 3.1 shows an example mesh with the topological entities labelled.
3.2. Reference cell entities¶
The reference cells similarly have locally numbered topological entities, these are shown in Fig. 3.2. The numbering is a matter of convention: that adopted here is that edges share the number of the opposite vertex. The orientation of the edges is also shown, this is always from the lower numbered vertex to the higher numbered one.
The ReferenceCell
class stores the
local topology of the reference cell. Read the source and ensure that you
understand the way in which this information is encoded.
The following animation of the numbering of the topological entities on the reference cell may help in understanding this.
3.3. Adjacency¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
In order to implement the finite element method, we need to integrate functions over cells, which means knowing which basis functions are nonzero in a given cell. For the function spaces used in the finite element method, these basis functions will be the ones whose nodes lie on the topological entities adjacent to the cell. That is, the vertices, edges and (in 3D) the faces making up the cell, as well as the cell itself. One of the roles of the mesh is therefore to provide a lookup facility for the lowerdimensional mesh entities adjacent to a given cell.
Given a mesh \(M\), then for each \(\dim(M) \geq d_1 > d_2 \geq 0\) the adjacency function \(\operatorname{Adj}_{d_1,d_2}:\, \mathbb{N}\rightarrow \mathbb{N}^k\) is the function such that:
where \((d_1, i)\) is a topological entity and \((d_2, i_0), \ldots, (d_2, i_k)\) are the adjacent \(d_2\)dimensional topological entities numbered in the corresponding reference cell order. If every cell in the mesh has the same topology then \(k\) will be fixed for each \((d_1, d_2)\) pair. The correspondence between the orientation of the entity \((d_1, i)\) and the reference cell of dimension \(d_1\) is established by specifying that the vertices are numbered in ascending order 1. That is, for any entity \((d_1, i)\):
A consequence of this convention is that the global orientation of all the entities making up a cell also matches their local orientation.
In the mesh shown in Fig. 3.1 we have:
In other words, vertices 1, 5 and 8 are adjacent to cell 3. Similarly:
Edges 11, 5, and 9 are local edges 0, 1, and 2 of cell 3.
3.4. Mesh geometry¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
The features of meshes we have so far considered are purely topological: they deal with the adjacency relationships between topological entities, but do not describe the locations of those entities in space. Provided we restrict our attention to meshes in which the element edges are straight (ie not curved), we can represent the geometry of the mesh by simply recording the coordinates of the vertices. The positions of the higher dimensional entities then just interpolate the vertices of which they are composed. We will later observe that this is equivalent to representing the geometry in a vectorvalued piecewise linear finite element space.
3.5. A mesh implementation in Python¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
The Mesh
class provides an implementation of
mesh objects in 1 and 2 dimensions. Given the list of vertices making
up each cell, it constructs the rest of the adjacency function. It
also records the coordinates of the vertices.
The UnitSquareMesh
class creates a
Mesh
object corresponding to a regular
triangular mesh of a unit square. Similarly, the
UnitIntervalMesh
class performs the
corresponding (rather trivial) function for a unit one dimensional
mesh.
You can observe the numbering of mesh entities in these meshes using
the plot_mesh
script. Run:
plot_mesh h
for usage instructions.
Footnotes
 1
The numbering convention adopted here is very convenient, but only works for meshes composed of simplices (vertices, intervals, triangles and tetrahedra). A more complex convention would be required to support quadrilateral meshes.