 Author
 JacquesOlivier Lachaud
 Since
 1.1
Part of Shapes package
This part of the manual describes how to represent and manipulate generic polygonal surfaces embedded in \( \mathbb{R}^3 \). The class SurfaceMesh proposes an indexbased data structure that encodes all topological relations between vertices, edges and faces, even if the mesh presents some non manifold places (like 3 triangles tied along the same edge). Input/output operations to and from OBJ files are provided through classes SurfaceMeshReader and SurfaceMeshWriter. Creation of classical surface 3D shapes (sphere, torus, Schwarz lantern) with groundtruth geometry is provided in SurfaceMeshHelper.
The following programs are related to this documentation:
 See also
 testSurfaceMesh.cpp, exampleSurfaceMesh.cpp
The useful includes are:
#include "DGtal/shapes/SurfaceMesh.h"
#include "DGtal/shapes/SurfaceMeshHelper.h"
#include "DGtal/io/readers/SurfaceMeshReader.h"
#include "DGtal/io/readers/SurfaceMeshWriter.h"
Creating a surface mesh
A surface mesh (class SurfaceMesh) is a template class parameterized by the types chosen for 3D points and 3D vectors. A common choice is PointVector< double, 3 >
for both, or equivalently Z3i::RealPoint
and Z3i::RealVector
. Although the topological part of the class does not impose a 3D embedding, the class SurfaceMesh imposes it since its target is 3D geometry processing. Indeed some geometric operations like computing normals from positions or i/o to OBJ format have meaning only in 3D.
First, write the following typedefs:
typedef SurfaceMesh< RealPoint, RealVector >
SurfMesh;
typedef SurfaceMeshHelper< RealPoint, RealVector > Helper;
SurfaceMesh< RealPoint, RealVector > SurfMesh
Then, there are several ways for creating a surface mesh (see exampleSurfaceMesh.cpp for several examples):
std::vector< RealPoint > positions =
{ { 0, 0, 5 }, { 1, 1, 3 }, { 1, 1, 3 }, { 1, 1, 3 }, { 1, 1, 3 } };
std::vector< Vertices > faces =
{ { 0, 1, 2 }, { 0, 2, 3 }, { 0, 3, 4 }, { 0, 4, 1 }, { 4, 3, 2, 1 } };
auto pyramid_mesh =
SurfMesh( positions.cbegin(), positions.cend(),
faces.cbegin(), faces.cend() );
std::string S = examplesPath + "samples/spot.obj";
std::ifstream input( S.c_str() );
input.close();
trace.
info() <<
"Read " << ( ok_read ?
"OK" :
"ERROR" )
<< " mesh=" << smesh << std::endl;
static bool readOBJ(std::istream &input, SurfaceMesh &smesh)
auto torus_mesh = Helper::makeTorus
( 2.5, 0.5,
RealPoint { 0.0, 0.0, 0.0 }, 40, 40, 0, Helper::NormalsType::NO_NORMALS );
PointVector< 3, double > RealPoint
Creating surface meshes from OBJ file, by specifying vertex/face information or predefined shapes
Topological relations within a surface mesh
All topological relations are precomputed as static arrays in SurfaceMesh class (which is thus not adapted to dynamic topological updates). You may access the number of cells with SurfaceMesh::nbVertices, SurfaceMesh::nbEdges, SurfaceMesh::nbFaces. Note that edge indices corresponds to pairs of vertices (i,j) with i<j.
You may ask for each vertex v:
You may ask for each face f:
You may create an edge index with SurfaceMesh::makeEdge. If the two vertices (i,j) do not form an edge, then the returned index is SurfaceMesh::nbEdges. Note that calling makeEdge(i,j)
or makeEdge(j,i)
returns always the same index, whether valid or invalid.
You may ask for each edge e:
 its two incident vertices with SurfaceMesh::incidentVertices, as pair (i,j) with (i<j).
 its range of bordering faces with SurfaceMesh::edgeFaces (they can be incident clockwise or counterclockwise)
 its range of left bordering faces with SurfaceMesh::edgeLeftFaces (a face to its left, being defined ccw, means that the face is some
(..., i, j, ... )
)
 its range of right bordering faces with SurfaceMesh::edgeRightFaces (a face to its left, being defined ccw, means that the face is some
(..., j, i, ... )
)
All the preceding methods have global variants returning all incident faces, all incident vertices, etc: SurfaceMesh::allIncidentFaces, SurfaceMesh::allIncidentVertices, SurfaceMesh::allNeighborFaces, SurfaceMesh::allNeighborVertices, SurfaceMesh::allEdgeFaces, SurfaceMesh::allEdgeLeftFaces, SurfaceMesh::allEdgeRightFaces.
Since vertices/edges/faces are indices, visiting them is simply a loop from 0 (included) till SurfaceMesh::nbVertices / SurfaceMesh::nbEdges / SurfaceMesh::nbFaces (all excluded).
A surface mesh is a graph
Class SurfaceMesh is a model of concepts::CUndirectedSimpleGraph (see also moduleGraphDefinitions). Hence you can for instance perform a breadth first traversal on its vertices.
#include "DGtal/shapes/SurfaceMesh.h"
#include "DGtal/graph/BreadthFirstVisitor.h"
...
typedef SurfaceMesh< RealPoint, RealVector >
SurfMesh;
BreadthFirstVisitor< SurfMesh > visitor( smesh, 0 );
std::vector<double> distances( smesh.nbVertices() );
double biggest_d = 0.0;
while ( ! visitor.finished() )
{
auto v = visitor.current().first;
auto d = visitor.current().second;
biggest_d = (double) d;
distances[ v ] = biggest_d;
visitor.expand();
}
Getting manifold, boundary and nonmanifold parts
SurfaceMesh can compute range of edges that have the same topology.
 SurfaceMesh::computeManifoldBoundaryEdges returns the edges that lie on the boundary of the mesh, i.e. they have only one incident face.
 SurfaceMesh::computeManifoldInnerEdges returns the edges that lie on the inside of the mesh, with two incident faces, consistently oriented or not.
 SurfaceMesh::computeManifoldInnerConsistentEdges returns the edges that lie on the inside of the mesh, with consistent local orientation, i.e. they have one left incident face, and one right incident face.
 SurfaceMesh::computeManifoldInnerUnconsistentEdges returns the edges that have two incident faces, but not correctly oriented, i.e. they may have two left incident faces and no right incident face, or two right incident faces and no left incident face.
 SurfaceMesh::computeNonManifoldEdges returns the edges that are non manifold, i.e. neither boundary or inner edges: they may have more than two incident faces, or two left incident faces for instance.
Locating non manifold vertices (like pinched vertices) requires more work and is not implemented.
Geometric positions and normals, and other information associated to cells
Vertex positions can be accessed and modified through methods SurfaceMesh::positions, or SurfaceMesh::position with a given vertex index.
You may associate normal vectors to the mesh as follows:
Normals are then accessed with SurfaceMesh::vertexNormals for vertices, SurfaceMesh::faceNormals for faces, or per element with SurfaceMesh::vertexNormal and SurfaceMesh::faceNormal.
More generally, you can transfer (by averaging) vector of values:
Further geometric services
The following local geometric services are provided:
The following global geometric services are provided:
You may also perturbate the mesh positions with uniform or non uniform random noise: with SurfaceMesh::perturbateWithUniformRandomNoise and SurfaceMesh::perturbateWithAdaptiveUniformRandomNoise;
Conversion and output to OBJ file format
You can convert a SurfaceMesh to a Mesh object simply by calling MeshHelpers::surfaceMesh2Mesh.
You can also output OBJ file (if available, with vertex normal information) using class SurfaceMeshWriter::writeOBJ, with some specialization allowing you to color faces. Edge lines and isolines can also be output as OBJ in same class.
The snippet below shows how to output the distances computed in A surface mesh is a graph as a surface colored per face with three isolines corresponding to relative distances 0.25, 0.5 and 0.75.
auto face_distances = smesh.computeFaceValuesFromVertexValues( distances );
auto cmap = GradientColorMap< double >( 0.0, biggest_d,
CMAP_JET );
std::vector<Color> face_colors( smesh.nbFaces() );
face_colors[ j ] = cmap( face_distances[ j ] );
typedef SurfaceMeshWriter< RealPoint, RealVector > Writer;
Writer::writeOBJ( "spotbft.obj", smesh, face_colors );
Writer::writeIsoLinesOBJ( "spotiso0_25.obj", smesh,
face_distances, distances, distances.back() * 0.25, 0.2 );
Writer::writeIsoLinesOBJ( "spotiso0_5.obj", smesh,
face_distances, distances, distances.back() * 0.5, 0.2 );
Writer::writeIsoLinesOBJ( "spotiso0_75.obj", smesh,
face_distances, distances, distances.back() * 0.75, 0.2 );
SurfaceMesh faces colored according to distance to bluest vertex and three isodistance lines
Flipping edges
Since 1.4, you may modify a SurfaceMesh through flips. Only (oriented) edges that are incident to a triangle on the right and a triangle on the left are (topologically) flippable. These two triangles form then a quadrilateral, and the edge is one diagonal of this quadrilateral. Flipping the edge means that the quadrilateral is now split only the other diagonal. Flipping twice the same edge restores the original mesh. Flipping edges has meaning only on orientable parts of a surface.
The following methods are useful for flipping an edge:
 SurfaceMesh::isFlippable indicates if a given edge is flippable. An edge is (topologically) flippable iff:
 it does not lie on the boundary,
 it is bordered by two triangles, one that to its right, one to its left,
 the two other vertices of the quad are not already neighbors,
 the edge is not bordered by the same two triangles, in opposite orientation.
 SurfaceMesh::flip performs the flip on a flippable edge
e=(i,j)
. The flipped edge keeps the same index as the original edge. You may choose whether or not you update locally the face normals.
l l
/ \ /\
/ \ /  \
/ \ /  \
/ lf \ /  \
/ \ /  \
i  e  j ==> i lf e rf j if k < l otherwise rf and lf are swapped
\ / \  /
\ rf / \  /
\ / \  /
\ / \  /
\ / \/
k k
 Note
 Almost all information is recomputed locally. Only vertex normals are not updated after a flip, as well as neighbor faces of faces are not recomputed. You may recompute face neighborhoods at the end of a sequence of flips by calling SurfaceMesh::computeNeighbors. You may for instance recompute vertex normals from face normals by a call to SurfaceMesh::computeVertexNormalsFromFaceNormals.
 SurfaceMesh::otherDiagonal returns, given a flippable edge, the two other vertices of the quadrilateral. So in the flip example above, it returns (k,l) if k < l or (l,k) otherwise.
The following code builds a Schwarz lantern, and then flips all flippable edges that are longer than their flipped edge.
typedef SurfaceMesh< RealPoint, RealVector > PolygonMesh;
typedef SurfaceMeshHelper< RealPoint, RealVector > PolygonMeshHelper;
typedef SurfaceMeshWriter< RealPoint, RealVector > PolygonMeshWriter;
typedef PolygonMeshHelper::NormalsType NormalsType;
auto meshLantern = PolygonMeshHelper::makeLantern( 3.0, 3.0, RealPoint::zero,
10, 10, NormalsType::NO_NORMALS );
{
std::ofstream output( "lantern.obj" );
bool okw = PolygonMeshWriter::writeOBJ( output, meshLantern );
output.close();
}
auto nb_flipped = 0;
const auto& X = meshLantern.positions();
for ( auto e = 0; e < meshLantern.nbEdges(); e++ )
{
if ( meshLantern.isFlippable( e ) )
{
auto ij = meshLantern.edgeVertices ( e );
auto kl = meshLantern.otherDiagonal( e );
double l2_ij = ( X[ ij.first ]  X[ ij.second ] ).
squaredNorm();
double l2_kl = ( X[ kl.first ]  X[ kl.second ] ).
squaredNorm();
if ( l2_kl < l2_ij )
{
meshLantern.flip( e, false );
nb_flipped++;
}
}
}
{
std::ofstream output( "flippedlantern.obj" );
bool okw = PolygonMeshWriter::writeOBJ( output, meshLantern );
output.close();
}
Space::RealVector RealVector
Point::Coordinate squaredNorm(Point const &aPoint)
Schwarz lantern before flip

Schwarz lantern after flip: a nicer cylinder
