Mesh Connectivity

Understanding and computing connectivity relations.

Connectivity describes the topological relationships between polytopes of different dimensions in a mesh. Understanding connectivity is essential for many finite element operations.

Introduction

In finite element analysis, we often need to know how mesh entities relate to each other:

Which cells share a given edge?
What are the faces of a cell?
Which vertices belong to a face?

These relationships are called incidence relations or connectivity.

Mathematical Notation

An incidence relation maps polytopes of dimension to polytopes of dimension that are incident to them.

For example, in a 2D mesh:

: Maps edges to incident cells
: Maps cells to their edges
: Maps vertices to incident cells

Computing Connectivity

Connectivity is not computed by default and must be explicitly requested:

#include <Rodin/Geometry.h>

using namespace Rodin;
using namespace Rodin::Geometry;

int main() {
  Mesh mesh;
  mesh = mesh.UniformGrid(Polytope::Type::Triangle, {16, 16});

  // Compute face-to-cell connectivity
  mesh.getConnectivity().compute(1, 2);

  return 0;
}

Common Connectivity Relations

2D Meshes

For 2D meshes (dimension = 2):

Relation	Description	When Needed
0 → 1	Vertices to edges	Edge operations
0 → 2	Vertices to cells	Vertex-based operations
1 → 0	Edges to vertices	Always available
1 → 1	Edges to adjacent edges	Edge neighbor queries
1 → 2	Edges to cells	Boundary conditions
2 → 0	Cells to vertices	Always available
2 → 1	Cells to edges	Cell neighbor queries
2 → 2	Cells to cells	Cell adjacency

3D Meshes

For 3D meshes (dimension = 3):

Relation	Description	When Needed
0 → 3	Vertices to cells	Vertex-based operations
1 → 3	Edges to cells	Edge operations
2 → 3	Faces to cells	Boundary conditions
3 → 2	Cells to faces	Cell neighbor queries
3 → 1	Cells to edges	Edge-based operations
3 → 0	Cells to vertices	Always available

Boundary Operations

Most important**: For boundary conditions and boundary iterations, you need:

2D meshes: mesh.getConnectivity().compute(1, 2) (edge-to-cell)
3D meshes: mesh.getConnectivity().compute(2, 3) (face-to-cell)

Mesh mesh;
mesh = mesh.UniformGrid(Polytope::Type::Triangle, {16, 16});

// Required for boundary operations in 2D
mesh.getConnectivity().compute(1, 2);

// Now we can iterate over boundary
for (auto it = mesh.getBoundary(); it; ++it) {
  std::cout << "Boundary edge " << it->getIndex() << std::endl;
}

Accessing Connectivity

Once computed, use connectivity to query relationships:

mesh.getConnectivity().compute(1, 2);
mesh.getConnectivity().compute(2, 1);

// Get all edges
for (auto edge = mesh.getFace(); edge; ++edge) {
  // Get cells incident to this edge
  const auto& incidentCells = 
    mesh.getConnectivity().getIncidence({1, edge->getIndex()}, 2);

  std::cout << "Edge " << edge->getIndex() 
            << " has " << incidentCells.size() 
            << " incident cells" << std::endl;
}

Complete Example

#include <Rodin/Geometry.h>

using namespace Rodin;
using namespace Rodin::Geometry;

int main() {
  // Create mesh
  Mesh mesh;
  mesh = mesh.UniformGrid(Polytope::Type::Triangle, {8, 8});

  std::cout << "Mesh info:" << std::endl;
  std::cout << "  Vertices: " << mesh.getVertexCount() << std::endl;
  std::cout << "  Edges: " << mesh.getFaceCount() << std::endl;
  std::cout << "  Cells: " << mesh.getCellCount() << std::endl;

  // Compute connectivity
  mesh.getConnectivity().compute(1, 2);  // Edge to cell
  mesh.getConnectivity().compute(2, 1);  // Cell to edge
  mesh.getConnectivity().compute(2, 2);  // Cell to cell

  // Count boundary edges
  size_t boundaryCount = 0;
  for (auto edge = mesh.getFace(); edge; ++edge) {
    if (mesh.isBoundary(edge->getIndex())) {
      boundaryCount++;
    }
  }
  std::cout << "Boundary edges: " << boundaryCount << std::endl;

  // Find cell neighbors
  auto cell = mesh.getCell(0);  // Get first cell
  for (auto neighbor = cell->getAdjacent(); neighbor; ++neighbor) {
    std::cout << "Cell 0 is adjacent to cell " 
              << neighbor->getIndex() << std::endl;
  }

  return 0;
}

Performance Considerations

Computational Cost

Computing connectivity can be expensive for large meshes:

Compute only what you need
Compute once, use many times
Some relations are computed together (e.g., and )

Timing Example

#include <chrono>

Mesh mesh;
mesh = mesh.UniformGrid(Polytope::Type::Triangle, {1024, 1024});

auto t0 = std::chrono::high_resolution_clock::now();
mesh.getConnectivity().compute(1, 2);
mesh.getConnectivity().compute(2, 1);
mesh.getConnectivity().compute(1, 1);
auto t1 = std::chrono::high_resolution_clock::now();

auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0);
std::cout << "Connectivity computation took " 
          << duration.count() << " ms" << std::endl;

When Is Connectivity Required?

Many operations require specific connectivity to be computed:

Operation	Required Connectivity
Boundary iteration
Dirichlet BC
Cell adjacency
SubMesh creation	Various
Partitioning

If required connectivity is missing, Rodin will raise an exception.