DGtal 1.3.0

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 halfedge data structure (or doubly connected cell list). We also provide a triangulated surface representation that is based on an halfedge data structure. A more general polygonal surface is provided and is also based on the same halfedge data sructure. In the latter case, faces of the surface can be arbitrary simple polygons.
The following programs are related to this documentation:
A halfedge 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 0cells, 1cells and 2cells respectively. The halfedge data structure describes which cells are connected to each other. Its principle is to associate two halfedges to each edge. Once this is done, it is easy to tie cells together by simply indicating for each halfedge:
The classical halfedge data structure is implemented in the class HalfEdgeDataStructure.
For now, you only have methods to create a halfedge data structure from a set of triangles and edges. For instance, the following code builds a halfedge data structure representing two triangles tied along one edge:
All elements within the halfedge 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.
Since halfedges are the basis of the structure, you have operations to get a halfedge from an arc (i.e. a couple of vertices), or from neighboring vertices or faces:
Then, each halfedge can give you its associated vertex, face, edge, opposite and next halfedge:
Finally a halfedge 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:
It is worthy to note the following elements in this representation:
Since 1.1, there is a limited support for classical flip, split and merge operations. For now, it is limited to triangulated halfedge date structures, i.e. a face is bordered by three halfedges.
There is also a method HalfEdgeDataStructure::isValid that performs a lot of checks on the validity of the data structure.
update_arc2index
is false
, and \( O(\log
n) \) time complexity otherwise, where \( n \) stands for the number of halfedges.A triangulated surface is a twodimensional simplicial complex, with a piecewise linear geometry. We use the halfedge 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).
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.
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:
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.
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:
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.
The class TriangulatedSurface just come with a way to get/set the position of each vertex:
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:
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:
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.
Since 1.1, there is a limited support for classical flip, split and merge operations for triangulated surfaces.
A polygonal surface is a twodimensional 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 halfedge 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).
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.
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:
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.
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:
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.
The class PolygonalSurface juste come with a way to get/set the position of each vertex:
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:
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:
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.