DGtal  1.5.beta
Surface mesh data structure for representing manifold or non-manifold polygonal surfaces in R3
Author
Jacques-Olivier 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 index-based 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" // main class
#include "DGtal/shapes/SurfaceMeshHelper.h" // creation/conversion
#include "DGtal/io/readers/SurfaceMeshReader.h" // input from OBJ file
#include "DGtal/io/readers/SurfaceMeshWriter.h" // output to OBJ file

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:

// The following typedefs are useful
typedef SurfaceMesh< RealPoint, RealVector > SurfMesh;
typedef SurfaceMeshHelper< RealPoint, RealVector > Helper;
SurfaceMesh< RealPoint, RealVector > SurfMesh
SMesh::Vertices Vertices

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() );
SurfMesh smesh;
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;
std::ostream & info()
Trace trace
Definition: Common.h:153
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:

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;
SurfMesh smesh;
BreadthFirstVisitor< SurfMesh > visitor( smesh, 0 );
std::vector<double> distances( smesh.nbVertices() );
double biggest_d = 0.0;
while ( ! visitor.finished() )
{
auto v = visitor.current().first; // current vertex
auto d = visitor.current().second; // current distance
biggest_d = (double) d;
distances[ v ] = biggest_d;
visitor.expand();
}

Getting manifold, boundary and non-manifold parts

SurfaceMesh can compute range of edges that have the same topology.

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 iso-lines 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.

// Displaying faces colored by their distance to vertex 0.
auto face_distances = smesh.computeFaceValuesFromVertexValues( distances );
auto cmap = GradientColorMap< double >( 0.0, biggest_d, CMAP_JET );
std::vector<Color> face_colors( smesh.nbFaces() );
for ( SurfMesh::Face j = 0; j < smesh.nbFaces(); ++j )
face_colors[ j ] = cmap( face_distances[ j ] );
typedef SurfaceMeshWriter< RealPoint, RealVector > Writer;
Writer::writeOBJ( "spot-bft.obj", smesh, face_colors );
// Displaying three isolines.
Writer::writeIsoLinesOBJ( "spot-iso-0_25.obj", smesh,
face_distances, distances, distances.back() * 0.25, 0.2 );
Writer::writeIsoLinesOBJ( "spot-iso-0_5.obj", smesh,
face_distances, distances, distances.back() * 0.5, 0.2 );
Writer::writeIsoLinesOBJ( "spot-iso-0_75.obj", smesh,
face_distances, distances, distances.back() * 0.75, 0.2 );
TriMesh::Face Face
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:
    1. it does not lie on the boundary,
    2. it is bordered by two triangles, one that to its right, one to its left,
    3. the two other vertices of the quad are not already neighbors,
    4. 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 PointVector<3,double> RealPoint;
typedef PointVector<3,double> RealVector;
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( "flipped-lantern.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