DGtal  1.5.beta
Half-edge data structure, triangulated surfaces and polygonal surfaces
Author
Jacques-Olivier Lachaud
Since
0.9.4

Part of Topology package and Shapes package

This part of the manual describes how to represent combinatorial surfaces, generally embedded in \(\mathbb{R}^3\). The underlying combinatorial topological structure is the classical half-edge data structure (or doubly connected cell list). We also provide a triangulated surface representation that is based on an half-edge data structure. A more general polygonal surface is provided and is also based on the same half-edge data sructure. In the latter case, faces of the surface can be arbitrary simple polygons.

The following programs are related to this documentation:

See also
testHalfEdgeDataStructure.cpp, testTriangulatedSurface.cpp, viewMarchingCubes.cpp, viewPolygonalMarchingCubes.cpp

The half-edge data structure

A half-edge data structure is a way to represent the topology of a combinatorial surface. A combinatoirial surface is a union of vertices, edges (a curve bordered by two vertices), faces (a piece of surface bordered by a sequence of edges). They are often called 0-cells, 1-cells and 2-cells respectively. The half-edge data structure describes which cells are connected to each other. Its principle is to associate two half-edges to each edge. Once this is done, it is easy to tie cells together by simply indicating for each half-edge:

  • its next half-edge (along its face)
  • its opposite half-edge (along the edge, that the half-edge associated to the neighboring face)
  • its associated face
  • its associated vertex (here, we choose the "to" vertex if the half-edge is seen as an arc)
  • its associated edge

The classical half-edge data structure is implemented in the class HalfEdgeDataStructure.

Note
Large parts of this class are taken from https://github.com/yig/halfedge, written by Yotam Gingold.

Creating a half-edge data structure

For now, you only have methods to create a half-edge data structure from a set of triangles and edges. For instance, the following code builds a half-edge data structure representing two triangles tied along one edge:

#include "DGtal/topology/HalfEdgeDataStructure.h"
...
std::vector< Triangle > triangles( 2 );
triangles[0].v = { 0, 1, 2 };
triangles[1].v = { 2, 1, 3 };
HalfEdgeDataStructure mesh;
mesh.build( triangles );
Represents an unoriented triangle as three vertices.

All elements within the half-edge data structure are numbered, starting from 0. Furthermore, the indices of vertices and triangles are the same as the one given at initialization.

So, for instance, in the code above, triangle 0 is incident to vertices 0, 1, 2 and triangle 1 is incident to vertices 2, 1, 3.

Note
Unordered edges may also be numbered according to your preference, but you need to call the other HalfEdgeDataStructure::build method, which takes as input triangles and edges, not only triangles. In this case, this other method builds a half-edge structure that keeps both the numbering of triangles and edges.

Elementary operations

Since half-edges are the basis of the structure, you have operations to get a half-edge from an arc (i.e. a couple of vertices), or from neighboring vertices or faces:

Then, each half-edge can give you its associated vertex, face, edge, opposite and next half-edge:

Illustration of half-edge data structure: each edge corresponds to two half-edges with opposite direction. You have access to the next half-edge along the face or to your opposite half-edge. You can also retrieve your associated face or vertex.

Finally a half-edge data structure can give you all the necessary neighboring information, and can also list the vertices and arcs that lie on the boundary of the data structure:

Details about internal representation

It is worthy to note the following elements in this representation:

  • half-edges, vertices, edges and faces are numbered consecutively from 0.
  • vertices and faces (here triangles) keep their numbering given at initialization.
  • given a vertex index, an edge index, or a face index, you can get an half-edge incident to it in constant time (stored as a vector).
  • given an arc (i.e. a couple of vertices), you can get the corresponding half-edge in logarithmic time (stored as a map).

Modifying operations: flip, split, merge

Since 1.1, there is a limited support for classical flip, split and merge operations. For now, it is limited to triangulated half-edge date structures, i.e. a face is bordered by three half-edges.

There is also a method HalfEdgeDataStructure::isValid that performs a lot of checks on the validity of the data structure.

Note
Methods HalfEdgeDataStructure::isFlippable and HalfEdgeDataStructure::isMergeable has \( O(1) \) time complexity. Methods HalfEdgeDataStructure::flip, HalfEdgeDataStructure::split and HalfEdgeDataStructure::merge have \( O(1) \) time complexity when optimization parameter update_arc2index is false, and \( O(\log n) \) time complexity otherwise, where \( n \) stands for the number of half-edges.

A triangulated surface data structure

A triangulated surface is a two-dimensional simplicial complex, with a piecewise linear geometry. We use the half-edge data structure to represent its topology and its geometry is simply given by precising coordinates for each vertex. The class TriangulatedSurface represents this geometric object. You may also associate other information to each vertex of the surface, through TriangulatedSurface::VertexPropertyMap objects.

A triangulated surface is a model of graph (concepts::CUndirectedSimpleGraph) so you may use graph algorithms to traverse it (see Basic graph definitions and concepts).

Building a triangulated surface

A triangulated surface is parameterized by the type that represents the coordinates of each vertex. Then you simply add vertices by specifying their coordinates, and triangles by giving the indices of the three vertices counterclockwise. Once this is done, you must call TriangulatedSurface::build to finish the construction. The following code creates a tetrahedron.

// The following includes and type definitions will be used everywhere afterwards.
#include "DGtal/shapes/TriangulatedSurface.h"
typedef PointVector<3,double> RealPoint;
typedef TriangulatedSurface< RealPoint > TriMesh;
typedef TriMesh::Arc Arc;
TriMesh mesh;
mesh.addVertex( RealPoint( 0, 0, 0 ) ); // vertex 0
mesh.addVertex( RealPoint( 1, 0, 0 ) ); // vertex 1
mesh.addVertex( RealPoint( 0, 1, 0 ) ); // vertex 2
mesh.addVertex( RealPoint( 1, 1, 1 ) ); // vertex 3
mesh.addTriangle( 0, 1, 2 ); // triangle 0
mesh.addTriangle( 3, 1, 0 ); // triangle 1
mesh.addTriangle( 3, 2, 1 ); // triangle 2
mesh.addTriangle( 3, 0, 2 ); // triangle 3
bool ok = mesh.build(); // should be true
HalfEdgeDataStructure::HalfEdgeIndex Arc
HalfEdgeDataStructure::FaceIndex Face
TriMesh::VertexRange VertexRange
TriMesh::PositionsMap PositionsMap
TriMesh::Face Face
TriangulatedSurface< RealPoint > TriMesh
PointVector< 3, double > RealPoint
TriMesh::ArcRange ArcRange
TriMesh::Vertex Vertex

Note that the topology that ties triangles together is built when calling TriangulatedSurface::build. If the topology is valid, it returns true. This method may return false for instance in the following cases:

  • three triangles sharing an edge,
  • number of vertices given by triangles does not match the number of vertex coordinates,
  • butterfly neighborhoods in the triangulation.

Main topological operations

As a model of graph (more precisely concepts::CUndirectedSimpleGraph), you can get neighbors of vertices, degree and some other operations, as well as iterators for visiting vertices. As a combinatorial surfaces you have a lot of other operations to navigate onto the triangulated surface:

Furthermore you can enumerate all the vertices, arcs and faces with TriangulatedSurface::allVertices, TriangulatedSurface::allArcs, TriangulatedSurface::allFaces.

Boundary of triangulated surface

Some of the edges of the triangulation may not be shared by two triangles, but only one. This set of edges, which may be organized in sequences, forms the boundary of the surface, which may be connected or disconnected. You have some operations to access to the boundary of the surface:

Helpers to convert triangulated surfaces from/to mesh

File MeshHelpers.h provides two methods to convert a Mesh into a TriangulatedSurface and conversely.

You may have a look at example shapes/viewMarchingCubes.cpp to see an example of using MeshHelpers::digitalSurface2DualTriangulatedSurface and MeshHelpers::triangulatedSurface2Mesh.

Marching cubes surface of anti-aliased vol file chinese-dragon-512 (see https://github.com/JacquesOlivierLachaud/AAVolGallery)
Close-up on Marching cubes surface of anti-aliased vol file chinese-dragon-512 (see https://github.com/JacquesOlivierLachaud/AAVolGallery)

Geometrical operations

The class TriangulatedSurface just come with a way to get/set the position of each vertex:

Associating data to vertices, edges, faces

The easiest way to associate data to vertices, edges or faces is to create a relevant TriangulatedSurface::IndexedPropertyMap. In fact, this is the mechanism used by the class TriangulatedSurface to store positions. The lines below show how to build a map associated an integer to each face:

TriangulatedSurface<RealPoint> mesh;
...
auto face_normal_map = mesh.makeFaceMap<int>( 0 ); // 0 is default value
for ( int i = 0; i < mesh.nbFaces(); ++i )
{
face_normal_map[ i ] = i; // each face is labelled with its own index.
}

Any TriangulatedSurface::IndexedPropertyMap is in fact a vector of value, the size of which depends on the number of vertices / edges / face. We exploit the fact that vertices, edges and faces are all numbered consecutively starting from 0. The following methods returns property maps:

Triangulated surface I/O and visualization

You have methods to export a triangulated surface as an OBJ file: MeshHelpers::exportOBJ or the more complete MeshHelpers::exportOBJwithFaceNormalAndColor.

In its present form, class TriangulatedSurface does not provide any visualization methods. However it is simpler to convert a TriangulatedSurface to/from a Mesh for I/O or for visualization (see Helpers to convert triangulated surfaces from/to mesh).

You may input or output a Mesh as an OFF/OFS/OBJ file, see Mesh IO. More precisely, class MeshWriter allows you to output a Mesh as an OFF/OFS/OBJ file while class MeshReader can input an OFF/OFS file into a Mesh.

For visualization, you may also directly stream a Mesh into a Viewer3D.

#include "DGtal/shapes/TriangulatedSurface.h"
#include "DGtal/shapes/Mesh.h"
#include "DGtal/shapes/MeshHelpers.h"
...
typedef TriangulatedSurface< RealPoint > TriMesh;
typedef Mesh< RealPoint > ViewMesh;
// Creates two triangles glued together.
TriMesh tmesh;
tmesh.addVertex( RealPoint( 0, 0, 0 ) );
tmesh.addVertex( RealPoint( 1, 0, 0 ) );
tmesh.addVertex( RealPoint( 0, 1, 0 ) );
tmesh.addVertex( RealPoint( 1, 1, 1 ) );
tmesh.addTriangle( 0, 1, 2 );
tmesh.addTriangle( 2, 1, 3 );
tmesh.build();
// Convert it to a mesh
ViewMesh mesh;
// View it
Viewer3D<> viewer;
viewer.show();
viewer.setLineColor(Color(150,0,0,254));
viewer << mesh;
viewer << Viewer3D<>::updateDisplay;
application.exec();
static void triangulatedSurface2Mesh(const TriangulatedSurface< Point > &trisurf, Mesh< Point > &mesh)

Modifying operations: flip, split, merge

Since 1.1, there is a limited support for classical flip, split and merge operations for triangulated surfaces.

  • TriangulatedSurface::isFlippable tells if some edge is flippable, i.e. it is bordered by two valid triangles;
  • TriangulatedSurface::flip flips the given edge if the edge is flippable, so that the edge now connects the two other vertices of the bordering two triangles;
  • TriangulatedSurface::split splits the given edge if the edge is flippable, i.e. creates a new vertex on this edge and two new triangles;
  • TriangulatedSurface::isMergeable tells if some edge is mergeable, i.e. (1) it is bordered by two triangles, (2) there is no boundary vertex in the two triangles bordering the edge;
  • TriangulatedSurface::merge merges the given edge and the two bordering triangles, leaving only one vertex and two edges, only if the edge is mergeable.
Note
These methods only checks that these operations are topologically valid. They do not check if the geometry of the resulting surface is valid, for instance that there is no self-intersections.
Methods TriangulatedSurface::isFlippable, TriangulatedSurface::isMergeable, TriangulatedSurface::flip, TriangulatedSurface::split and TriangulatedSurface::merge have all \( O(1) \) time complexity.

A polygonal surface data structure

A polygonal surface is a two-dimensional simplicial complex, with a piecewise linear geometry per face. Contrary to class TriangulatedSurface, faces are not restricted to triangles but may be arbitrary simple polygons. We use the half-edge data structure to represent its topology and its geometry is simply given by precising coordinates for each vertex. The class PolygonalSurface represents this geometric object. You may also associate other information to each vertex of the surface, through PolygonalSurface::VertexPropertyMap objects.

A polygonal surface is a model of graph (concepts::CUndirectedSimpleGraph) so you may use graph algorithms to traverse it (see Basic graph definitions and concepts).

Building a polygonal surface

A polygonal surface is parameterized by the type that represents the coordinates of each vertex. Then you simply add vertices by specifying their coordinates, and triangles by giving the indices of the three vertices counterclockwise. Once this is done, you must call PolygonalSurface::build to finish the construction. The following code creates a pyramid.

// The following includes and type definitions will be used everywhere afterwards.
#include "DGtal/shapes/PolygonalSurface.h"
typedef PointVector<3,double> RealPoint;
typedef PolygonalSurface< RealPoint > PolyMesh;
typedef PolyMesh::Arc Arc;
PolyMesh mesh;
mesh.addVertex( RealPoint( 0, 0, 0 ) ); // vertex 0
mesh.addVertex( RealPoint( 1, 0, 0 ) ); // vertex 1
mesh.addVertex( RealPoint( 0, 1, 0 ) ); // vertex 2
mesh.addVertex( RealPoint( 1, 1, 0 ) ); // vertex 3
mesh.addVertex( RealPoint( 0.5, 0.5, 1 ) ); // vertex 4
mesh.addTriangle( 0, 1, 4 ); // triangle 0
mesh.addTriangle( 1, 3, 4 ); // triangle 1
mesh.addTriangle( 3, 2, 4 ); // triangle 2
mesh.addTriangle( 2, 0, 4 ); // triangle 3
mesh.addQuadrangle( 1, 0, 2, 3 ); // quadrangle 4
bool ok = mesh.build(); // should be true

Note that the topology that ties faces together is built when calling PolygonalSurface::build. If the topology is valid, it returns true. This method may return false for instance in the following cases:

  • three faces sharing an edge,
  • number of vertices given by faces does not match the number of vertex coordinates,
  • butterfly neighborhoods in the triangulation.

Main topological operations

As a model of graph (more precisely concepts::CUndirectedSimpleGraph), you can get neighbors of vertices, degree and some other operations, as well as iterators for visiting vertices. As a combinatorial surfaces you have a lot of other operations to navigate onto the polygonal surface:

Furthermore you can enumerate all the vertices, arcs and faces with PolygonalSurface::allVertices, PolygonalSurface::allArcs, PolygonalSurface::allFaces.

Boundary of polygonal surface

Some of the edges of the combinatorial surface may not be shared by two triangles, but only one. This set of edges, which may be organized in sequences, forms the boundary of the surface, which may be connected or disconnected. You have some operations to access to the boundary of the surface:

Helpers to convert polygonal surfaces from/to mesh

File MeshHelpers.h provides two methods to convert a Mesh into a PolygonalSurface and conversely.

You may have a look at example shapes/viewPolygonalMarchingCubes.cpp to see an example of using MeshHelpers::digitalSurface2DualPolygonalSurface and MeshHelpers::polygonalSurface2Mesh.

Geometrical operations

The class PolygonalSurface juste come with a way to get/set the position of each vertex:

Associating data to vertices, edges, faces

The easiest way to associate data to vertices, edges or faces is to create a relevant PolygonalSurface::IndexedPropertyMap. In fact, this is the mechanism used by the class PolygonalSurface to store positions. The lines below show how to build a map associating an integer to each face:

PolygonalSurface<RealPoint> mesh;
...
auto face_normal_map = mesh.makeFaceMap<int>( 0 ); // 0 is default value
for ( int i = 0; i < mesh.nbFaces(); ++i )
{
face_normal_map[ i ] = i; // each face is labelled with its own index.
}

Any PolygonalSurface::IndexedPropertyMap is in fact a vector of value, the size of which depends on the number of vertices / edges / face. We exploit the fact that vertices, edges and faces are all numbered consecutively starting from 0. The following methods returns property maps:

Polygonal surface I/O and visualization

You have methods to export a polygonal surface as an OBJ file: MeshHelpers::exportOBJ or the more complete MeshHelpers::exportOBJwithFaceNormalAndColor.

In its present form, class PolygonalSurface does not provide any visualization methods. However it is simpler to convert a PolygonalSurface to/from a Mesh for I/O or for visualization (see Helpers to convert polygonal surfaces from/to mesh).

You may input or output a Mesh as an OFF/OFS/OBJ file, see Mesh IO. More precisely, class MeshWriter allows you to output a Mesh as an OFF/OFS/OBJ file while class MeshReader can input an OFF/OFS file into a Mesh.

For visualization, you may also directly stream a Mesh into a Viewer3D.

#include "DGtal/shapes/PolygonalSurface.h"
#include "DGtal/shapes/Mesh.h"
#include "DGtal/shapes/MeshHelpers.h"
...
typedef PolygonalSurface< RealPoint > PolyMesh;
typedef Mesh< RealPoint > ViewMesh;
// Creates two triangles glued together.
PolyMesh tmesh;
tmesh.addVertex( RealPoint( 0, 0, 0 ) );
tmesh.addVertex( RealPoint( 1, 0, 0 ) );
tmesh.addVertex( RealPoint( 0, 1, 0 ) );
tmesh.addVertex( RealPoint( 1, 1, 1 ) );
tmesh.addTriangle( 0, 1, 2 );
tmesh.addTriangle( 2, 1, 3 );
tmesh.build();
// Convert it to a mesh
ViewMesh mesh;
// View it
Viewer3D<> viewer;
viewer.show();
viewer.setLineColor(Color(150,0,0,254));
viewer << mesh;
viewer << Viewer3D<>::updateDisplay;
application.exec();
static void polygonalSurface2Mesh(const PolygonalSurface< Point > &polysurf, Mesh< Point > &mesh)