Quick links

Why concepts ?

A concept (as defined by BCCL) is a set of requirements (valid expressions, associated types, semantic invariants, complexity guarantees, etc.) that a type must fulfil to be correctly used as arguments in a call to a generic algorithm. A concept can be thought as a form of API (in the context of generic algorithm).

Concepts can take the informal form of a convention i.e. something concerning template parameters that is collectively known within a community of programmers (and shared through e.g. documentation). It is thus the responsibility of the programmer (both for MEPP2 users and MEPP2 developers) to assert and guarantee that the provided code complies to such informal concepts. But within the context of C++, concepts can also take the precise form of formal concepts (definitions) (refer to the Boost Concept Check Library (BCCL) motivations or to ITK's concept checking introduction). Formal concepts (concept checking) allow to explicitly document the functions/operators required by a template type of an algorithm but also to ease (compile time) syntax debugging and also be used on testing purposes (e.g. CGAL's graph_concept_OpenMesh.cpp or graph_concept_Polyhedron_3.cpp).

Within MEPP2 the concepts, to which the considered set of implementations are complying, are informally defined through the present documentation. Nevertheless concept checking (formal concepts) is internally used within MEPP2 for the limited usage of expressing regression tests.

Concept for vertex access and vertex manipulation

This concept, that focuses on vertex coordinates and its derivative concepts is described on the separate geometry concept page.

CGAL and BGL concepts for surfaces

Among the CGAL community the standard manipulation interface (Create, Read, Update, Delete (CRUD) of polygon mesh (a.k.a. "surfacic mesh") is the HalfEdgeGraph concept. Because a part of the topological aspects of polygon mesh can be described as a graph, the CGAL's HalfEdgeGraph concept was defined as a refinement of BGL's Graph concept. This refinement of BGL's concept conveniently allows to re-use some of BGL algorithms on CGAL surfacic data structures as provided by CGAL's "BGL wrappers").

Once this design choice of the wishful CGAL-BGL connection is recalled, we can now consider the whole set of concepts (of those respective libraries) that are related with CGAL's HalfEdgeGraph and BGL's Graph concepts. The resulting integrated system of concepts is depicted in the following fairly detailed diagram (references: boost::Graph concepts diagram and CGAL and BGL concepts diagram):

Ideally a programmer working on polygon mesh could thus hope to have at hand all the above depicted concepts if he/she wishes to rip the benefit of all the algorithms (CGAL and BGL) based on the availability of such concepts for the considered mesh centric data structures. But the reality of the implementations makes the picture a bit more complicated as some limitations appear. For example:

CGAL's "BGL wrappers" mentions that CGAL provides partial specialisation for the classes CGAL::Surface_mesh, CGAL::Polyhedron_3 and OpenMesh::PolyMesh_ArrayKernelT so that it is a model of the graph concepts BidirectionalGraph and VertexAndEdgeListGraph and of the concept MutableFaceGraph. The key word in the previous sentence is of course "partial"...
CGAL::MutableHalfedgeGraph and boost::MutableGraph concepts differ too much for CGAL::MutableHalfedgeGraph to (fully) refine boost::MutableGraph (refer to the red arrow on above diagram). For example
- CGAL::MutableHalfedgeGraph offers set_target(h, v, g), set_halfedge(v, h, g) and set_next(h1, h2, g) that boost::MutableGraph misses, whereas
- boost::MutableGraph offers add_edge(u, v, g), remove_edge(u, v, g), clear_vertex(u, g), remove_edge(iter, g), remove_edge_if(p, g), remove_out_edge_if(u, p, g) and remove_in_edge_if(u, p, g) and clear_vertex(u, g) that CGAL::MutableHalfedgeGraph misses.
CGAL's Surface Mesh data structure documentation mentions that it is a model of CGAL::MutableFaceGraph and CGAL::FaceListGraph.Yet the "BGL wrappers" do not offer CGAL::Surface_Mesh to be a model of boost::MutableGraph (this limitation is also valid for CGAL::Polyhedron_3).
many of the above mentioned polygon mesh data structures, as well as OpenMesh miss to fully implement the boost::PropertyGraph.

When writing generic algorithm working on polygon mesh, the general approach is thus to use a limited, yet stable, subset of the possibly available concepts (refer to for a summary of concept compliance).

For example when modifying a polygon mesh topology a CGAL programmer will favour the CGAL::MutableHalfedgeGraph concept (that are the reference API for manipulating triangulations within CGAL) possibly together with the Euler operations (as implemented by CGAL) over the boost::MutableGraph concept. Although it might also be that for optimisation reasons a "real" CGAL programmers might also consider that the Euler operators (e.g. CGAL::Euler::collapse_edge(v0v1, g)) is a too high level operations and will resolve to use "under the hood" low level pointer manipulations (e.g. building on MutableHalfedgeGraph::remove_edge(e, g) at the cost of loosing cross data structure (e.g. OpenMesh) portability...

MEPP2 recommended concept usage for polygon mesh

MEPP2 concept usage recommendation boils down to

use MEPP2 proper concepts
use CGAL concepts
use BGL concepts when in the specific graph context which includes using a BGL algorithm
avoid BGL mutability related concepts (whenever if possible)
avoid BGL PropetyGraph concept (and favor FEVV::Property)

This recommendation can be summarised by the following diagram

In turn, this diagram summarizes to the following task oriented ordered list of concepts

for accessing/manipulating the geometry of a surface use the FEVV::Geometry concept
for manipulating associated properties of a surface use the FEVV::Property concept
for reading/walking on the surface use
- Iterators and Circulators (CGAL)
- CGAL::HalfedgeGraph
- CGAL::HalfedgeListGraph (except for AIF for which this concept cannot be applied)
- CGAL::FaceGraph
- CGAL::FaceListGraph
- FEVV::ListGraphExtensions concept
for surface manipulation (mutable operations i.e. creating, modifying or deleting elements of a polygon mesh)
- high level interface (concise code) use the Euler operations
- lower level interface (more verbose code but possibly faster) use the
  - CGAL::MutableHalfedgeGraph concept,
  - CGAL::MutableFaceGraph concept

When in a graph oriented context (you need to write an algorithm that strips down the surface to being a graph) or when you wish to use a BGL provided algorithm) possibly use

boost::Graph concept
boost::IncidenceGraph concept
boost::BidirectionalGraph
boost::VertexListGraph concept
boost::EdgeListGraph concept
boost::VertexAndEdgeListGraph is "purely conceptual" (doesn't offer types nor expressions)

Eventually, and unless some BGL algorithm that you need requires it, avoid writing MEPP2 generic code using the following concepts:

boost::AdjacencyGraph concept

boost::VertexMutableGraph concept

If you are cornered down to using this last category of concepts make sure to check the compliance page since some of those concepts will fail for some or many surface datastructures.

DynamicGraph concept: dynamic mesh

Open question: how is this different from sequences of meshes (with an implicit timestep) or hash tables of meshes with a timestamp key ?

Note

The concept description format follows CGAL's concept template