DGtal  1.4.beta
SurfaceMesh.h
1 
17 #pragma once
18 
31 #if defined(SurfaceMesh_RECURSES)
32 #error Recursive header files inclusion detected in SurfaceMesh.h
33 #else // defined(SurfaceMesh_RECURSES)
35 #define SurfaceMesh_RECURSES
36 
37 #if !defined SurfaceMesh_h
39 #define SurfaceMesh_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <sstream>
45 #include <string>
46 #include "DGtal/base/Common.h"
47 #include "DGtal/base/IntegerSequenceIterator.h"
48 #include "DGtal/helpers/StdDefs.h"
49 
50 namespace DGtal
51 {
53  // template class SurfaceMesh
90  template < typename TRealPoint, typename TRealVector >
91  struct SurfaceMesh
92  {
93  typedef TRealPoint RealPoint;
94  typedef TRealVector RealVector;
96 
97  static const Dimension dimension = RealPoint::dimension;
99 
100  typedef typename RealVector::Component Scalar;
101  typedef std::vector<Scalar> Scalars;
103  typedef std::size_t Size;
105  typedef std::size_t Index;
106  typedef Index Face;
107  typedef Index Edge;
108  typedef Index Vertex;
109  typedef std::pair< Edge, Scalar > WeightedEdge;
110  typedef std::pair< Face, Scalar > WeightedFace;
112  typedef std::vector< Vertex > Vertices;
114  typedef std::vector< Edge > Edges;
115  typedef std::vector< WeightedEdge > WeightedEdges;
116  typedef std::vector< Face > Faces;
117  typedef std::vector< WeightedFace > WeightedFaces;
118  typedef std::pair< Vertex, Vertex > VertexPair;
119 
120  // Required by CUndirectedSimpleLocalGraph
121  typedef std::set<Vertex> VertexSet;
122  template <typename Value> struct VertexMap {
123  typedef typename std::map<Vertex, Value> Type;
124  };
125 
126  // Required by CUndirectedSimpleGraph
127 
130 
131  //---------------------------------------------------------------------------
132  public:
135 
137  ~SurfaceMesh() = default;
147  SurfaceMesh() = default;
150  SurfaceMesh( const Self& other ) = default;
153  SurfaceMesh( Self&& other ) = default;
157  Self& operator=( const Self& other ) = default;
158 
178  template <typename RealPointIterator, typename VerticesIterator>
179  SurfaceMesh( RealPointIterator itPos, RealPointIterator itPosEnd,
180  VerticesIterator itVertices, VerticesIterator itVerticesEnd );
181 
203  template <typename RealPointIterator, typename VerticesIterator>
204  bool init( RealPointIterator itPos, RealPointIterator itPosEnd,
205  VerticesIterator itVertices, VerticesIterator itVerticesEnd );
206 
208  void clear();
209 
211 
212  //---------------------------------------------------------------------------
213  public:
216 
219  template <typename RealVectorIterator>
220  bool setVertexNormals( RealVectorIterator itN, RealVectorIterator itNEnd );
221 
224  template <typename RealVectorIterator>
225  bool setFaceNormals( RealVectorIterator itN, RealVectorIterator itNEnd );
226 
231 
236 
241 
247 
251  template <typename AnyRing>
253  ( const std::vector<AnyRing>& vvalues ) const;
254 
258  template <typename AnyRing>
260  ( const std::vector<AnyRing>& fvalues ) const;
261 
265  ( const std::vector<RealVector>& vuvectors ) const;
266 
270  ( const std::vector<RealVector>& fuvectors ) const;
271 
273 
274  //---------------------------------------------------------------------------
275  public:
278 
280  Size nbVertices() const
281  { return myIncidentFaces.size(); }
282 
284  Size nbEdges() const
285  { return myEdgeVertices.size(); }
286 
288  Size nbFaces() const
289  { return myIncidentVertices.size(); }
290 
294  long Euler() const
295  { return nbVertices() - nbEdges() + nbFaces(); }
296 
302  Edge makeEdge( Vertex i, Vertex j ) const;
303 
307  const Vertices& incidentVertices( Face f ) const
308  { return myIncidentVertices[ f ]; }
309 
313  const Faces& incidentFaces( Vertex v ) const
314  { return myIncidentFaces[ v ]; }
315 
318  const Faces& neighborFaces( Face f ) const
319  { return myNeighborFaces[ f ]; }
320 
323  const Vertices& neighborVertices( Vertex v ) const
324  { return myNeighborVertices[ v ]; }
325 
329  const VertexPair& edgeVertices( Edge e ) const
330  { return myEdgeVertices[ e ]; }
331 
335  const Faces& edgeFaces( Edge e ) const
336  { return myEdgeFaces[ e ]; }
337 
346  const Faces& edgeRightFaces( Edge e ) const
347  { return myEdgeRightFaces[ e ]; }
348 
357  const Faces& edgeLeftFaces( Edge e ) const
358  { return myEdgeLeftFaces[ e ]; }
359 
362  const std::vector< Vertices >& allIncidentVertices() const
363  { return myIncidentVertices; }
364 
367  const std::vector< Faces >& allIncidentFaces() const
368  { return myIncidentFaces; }
369 
371  const std::vector< Faces >& allNeighborFaces() const
372  { return myNeighborFaces; }
373 
375  const std::vector< Vertices >& allNeighborVertices() const
376  { return myNeighborVertices; }
377 
381  const std::vector< VertexPair >& allEdgeVertices() const
382  { return myEdgeVertices; }
383 
386  const std::vector< Faces >& allEdgeFaces() const
387  { return myEdgeFaces; }
388 
396  const std::vector< Faces >& allEdgeRightFaces() const
397  { return myEdgeRightFaces; }
398 
406  const std::vector< Faces >& allEdgeLeftFaces() const
407  { return myEdgeLeftFaces; }
408 
410 
411  //---------------------------------------------------------------------------
412  public:
415 
438 
446  bool isBoundariesManifold(bool checkClosed = true) const
447  {
448  //computes unordered list of boundary vertices
449  std::map<Vertex,Vertices> adjacent;
450  auto MBE = this->computeManifoldBoundaryEdges();
451  if (MBE.size()==0) return false;
452 
453  for (auto e : MBE)
454  {
455  auto ij = this->edgeVertices(e);
456  adjacent[ij.first].push_back(ij.second);
457  if (adjacent[ij.first].size()>2) return false;
458  adjacent[ij.second].push_back(ij.first);
459  if (adjacent[ij.second].size()>2) return false;
460  }
461  //we may check if all curves are closed.
462  if (checkClosed)
463  for(const auto &adj : adjacent)
464  if (adj.second.size() != 2) return false;
465  return true;
466  }
467 
473  std::vector<Vertices> computeManifoldBoundaryChains() const
474  {
475  std::vector<Vertices> boundaries;
476  Vertices boundary;
477  auto MBE = this->computeManifoldBoundaryEdges();
478  std::map<Vertex,bool> visited;
479  std::map<Vertex,Vertices> adjacent;
480 
481  ASSERT_MSG(MBE.size()>0,"The surface mesh must have boundary edges");
482  ASSERT_MSG(this->isBoundariesManifold(), "The surface mesh mush have manifold boundaries");
483 
484  //Coompute adjecency relationships
485  for (auto e : MBE)
486  {
487  auto ij = this->edgeVertices(e);
488  visited[ij.first] = false;
489  visited[ij.second] = false;
490  adjacent[ij.first].push_back(ij.second);
491  adjacent[ij.second].push_back(ij.first);
492  }
493 
494  auto boundary_it = visited.begin();
495 
496  while(boundary_it != visited.end() )
497  {
498  Vertex first = (*boundary_it).first;
499  visited[first] = true;
500  boundary.clear();
501  boundary.push_back(first);
502 
503  Vertex current = first;
504  size_t nb_iter = 0;
505  bool pushed=false;
506 
507  while ((!pushed) && (nb_iter < MBE.size()*2))
508  {
509  bool ok = false;
510  for (auto other : adjacent[current])
511  if (!visited[other])
512  {
513  boundary.push_back(other);
514  current = other;
515  visited[other] = true;
516  ok = true;
517  break;
518  }
519  if (!ok)
520  {
521  //all neighboors are visited
522  for (auto other : adjacent[current])
523  if (other == first)
524  {
525  boundaries.push_back(boundary);
526  pushed = true;
527  break;
528  }
529  //if first vertex isn't found then this chain is not
530  //homeomorphic to a circle, hence isn't added to boundaries
531  }
532  nb_iter++;
533  }
534  boundary_it = std::find_if(visited.begin(), visited.end(),
535  []
536  (std::pair<Vertex,bool> x){return !x.second;});
537  }
538  return boundaries;
539  }
541 
542  // ----------------------- Undirected simple graph services ----------------------
543  public:
546 
550  Size size() const
551  { return nbVertices(); }
552 
560  { return 8; }
561 
567  Size degree( const Vertex & v ) const
568  { return myNeighborVertices[ v ].size(); }
569 
580  template <typename OutputIterator>
581  void
582  writeNeighbors( OutputIterator &it ,
583  const Vertex & v ) const
584  {
585  for ( auto&& nv : myNeighborVertices[ v ] )
586  *it++ = nv;
587  }
588 
605  template <typename OutputIterator, typename VertexPredicate>
606  void
607  writeNeighbors( OutputIterator &it ,
608  const Vertex & v,
609  const VertexPredicate & pred) const
610  {
611  for ( auto&& nv : myNeighborVertices[ v ] )
612  if ( pred( nv ) ) *it++ = nv;
613  }
614 
617  { return ConstIterator( 0 ); }
618 
621  { return ConstIterator( nbVertices() ); }
622 
624 
625  //---------------------------------------------------------------------------
626  public:
629 
631  const std::vector< RealPoint >& positions() const
632  { return myPositions; }
633 
638  { return myPositions[ v ]; }
639 
643  const RealPoint& position( Vertex v ) const
644  { return myPositions[ v ]; }
645 
647  const std::vector< RealVector >& vertexNormals() const
648  { return myVertexNormals; }
649 
651  std::vector< RealVector >& vertexNormals()
652  { return myVertexNormals; }
653 
658  { return myVertexNormals[ v ]; }
659 
663  const RealVector& vertexNormal( Vertex v ) const
664  { return myVertexNormals[ v ]; }
665 
667  const std::vector< RealVector >& faceNormals() const
668  { return myFaceNormals; }
669 
671  std::vector< RealVector >& faceNormals()
672  { return myFaceNormals; }
673 
678  { return myFaceNormals[ f ]; }
679 
683  const RealVector& faceNormal( Face f ) const
684  { return myFaceNormals[ f ]; }
685 
688 
692  Scalar distance(const Vertex i, const Vertex j) const
693  {
694  //unrolling for compiler optimization
695  const auto p=this->myPositions[ i ];
696  const auto q=this->myPositions[ j ];
697  return std::sqrt( (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1])+ (p[2]-q[2])*(p[2]-q[2]));
698  }
699 
703  Scalar localWindow( Face f ) const;
704 
709 
714 
718 
722 
725  Scalar faceArea( Index f ) const;
726 
731 
753 
776 
792  std::tuple< Vertices, WeightedEdges, WeightedFaces >
794 
811  std::tuple< Vertices, WeightedEdges, WeightedFaces >
813 
828 
843 
854 
856 
857  // ----------------------- Interface --------------------------------------
858  public:
859 
864  void selfDisplay ( std::ostream & out ) const;
865 
870  bool isValid() const;
871 
872  // ------------------------- Protected Datas ------------------------------
873  protected:
875  std::vector< Vertices > myIncidentVertices;
877  std::vector< Faces > myIncidentFaces;
879  std::vector< RealPoint > myPositions;
881  std::vector< RealVector > myVertexNormals;
883  std::vector< RealVector > myFaceNormals;
885  std::vector< Faces > myNeighborFaces;
887  std::vector< Vertices > myNeighborVertices;
889  std::vector< VertexPair > myEdgeVertices;
891  std::vector< Faces > myEdgeFaces;
897  std::vector< Faces > myEdgeRightFaces;
903  std::vector< Faces > myEdgeLeftFaces;
904 
905  // ------------------------- Private Datas --------------------------------
906  private:
907 
908 
909  // ------------------------- Internals ------------------------------------
910  protected:
911 
915  void computeEdges();
916 
918  static Scalar rand01()
919  { return (Scalar) rand() / (Scalar) RAND_MAX; }
920 
921  }; // end of class SurfaceMesh
922 
929  template < typename TRealPoint, typename TRealVector >
930  std::ostream&
931  operator<< ( std::ostream & out,
932  const SurfaceMesh<TRealPoint, TRealVector> & object );
933 
934 } // namespace DGtal
935 
937 // Includes inline functions.
938 #include "SurfaceMesh.ih"
939 // //
941 
942 #endif // !defined SurfaceMesh_h
943 
944 #undef SurfaceMesh_RECURSES
945 #endif // else defined(SurfaceMesh_RECURSES)
Aim: It is a simple class that mimics a (non mutable) iterator over integers. You can increment it,...
TEuclideanRing Component
Type for Vector elements.
Definition: PointVector.h:614
DGtal is the top-level namespace which contains all DGtal functions and types.
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
DGtal::uint32_t Dimension
Definition: Common.h:136
std::map< Vertex, Value > Type
Definition: SurfaceMesh.h:123
Aim: Represents an embedded mesh as faces and a list of vertices. Vertices may be shared among faces ...
Definition: SurfaceMesh.h:92
std::vector< WeightedEdge > WeightedEdges
Definition: SurfaceMesh.h:115
void writeNeighbors(OutputIterator &it, const Vertex &v, const VertexPredicate &pred) const
Definition: SurfaceMesh.h:607
std::vector< RealVector > & faceNormals()
Definition: SurfaceMesh.h:671
WeightedFaces computeFacesInclusionsInBall(Scalar r, Index f, RealPoint p) const
Size size() const
Definition: SurfaceMesh.h:550
const Faces & neighborFaces(Face f) const
Definition: SurfaceMesh.h:318
std::pair< Vertex, Vertex > VertexPair
Definition: SurfaceMesh.h:118
Scalar edgeInclusionRatio(RealPoint p, Scalar r, Index e) const
Edges computeManifoldInnerUnconsistentEdges() const
RealPoint & position(Vertex v)
Definition: SurfaceMesh.h:637
SurfaceMesh(RealPointIterator itPos, RealPointIterator itPosEnd, VerticesIterator itVertices, VerticesIterator itVerticesEnd)
SurfaceMesh(const Self &other)=default
std::vector< RealVector > computeVertexUnitVectorsFromFaceUnitVectors(const std::vector< RealVector > &fuvectors) const
void perturbateWithAdaptiveUniformRandomNoise(Scalar p)
bool setVertexNormals(RealVectorIterator itN, RealVectorIterator itNEnd)
std::vector< Vertex > Vertices
The type that defines a list/range of vertices (e.g. to define faces)
Definition: SurfaceMesh.h:112
Edges computeManifoldInnerEdges() const
std::vector< Faces > myNeighborFaces
For each face, its range of neighbor faces (no particular order)
Definition: SurfaceMesh.h:885
RealPoint faceCentroid(Index f) const
std::vector< Scalar > Scalars
Definition: SurfaceMesh.h:101
static Scalar rand01()
Definition: SurfaceMesh.h:918
const std::vector< Faces > & allEdgeRightFaces() const
Definition: SurfaceMesh.h:396
long Euler() const
Definition: SurfaceMesh.h:294
void computeEdges()
Computes edge information.
SurfaceMesh< RealPoint, RealVector > Self
Definition: SurfaceMesh.h:95
const std::vector< RealVector > & faceNormals() const
Definition: SurfaceMesh.h:667
static const Dimension dimension
Definition: SurfaceMesh.h:97
Scalars getMaxWeights(Index v) const
std::vector< WeightedFace > WeightedFaces
Definition: SurfaceMesh.h:117
const Faces & edgeFaces(Edge e) const
Definition: SurfaceMesh.h:335
Scalar localWindow(Face f) const
void perturbateWithUniformRandomNoise(Scalar p)
TRealPoint RealPoint
Definition: SurfaceMesh.h:93
const std::vector< RealVector > & vertexNormals() const
Definition: SurfaceMesh.h:647
Scalar faceArea(Index f) const
std::vector< Faces > myIncidentFaces
For each vertex, its range of incident faces.
Definition: SurfaceMesh.h:877
void computeFaceNormalsFromPositions()
std::vector< Faces > myEdgeRightFaces
Definition: SurfaceMesh.h:897
std::vector< AnyRing > computeFaceValuesFromVertexValues(const std::vector< AnyRing > &vvalues) const
const std::vector< RealPoint > & positions() const
Definition: SurfaceMesh.h:631
bool isBoundariesManifold(bool checkClosed=true) const
Definition: SurfaceMesh.h:446
RealVector & vertexNormal(Vertex v)
Definition: SurfaceMesh.h:657
SurfaceMesh()=default
ConstIterator begin() const
Definition: SurfaceMesh.h:616
std::vector< AnyRing > computeVertexValuesFromFaceValues(const std::vector< AnyRing > &fvalues) const
void computeVertexNormalsFromFaceNormals()
RealVector & faceNormal(Face f)
Definition: SurfaceMesh.h:677
std::size_t Index
The type used for numbering vertices and faces.
Definition: SurfaceMesh.h:105
std::vector< Vertices > computeManifoldBoundaryChains() const
Definition: SurfaceMesh.h:473
const Vertices & incidentVertices(Face f) const
Definition: SurfaceMesh.h:307
~SurfaceMesh()=default
Default destructor.
const Faces & edgeRightFaces(Edge e) const
Definition: SurfaceMesh.h:346
IntegerSequenceIterator< Vertex > ConstIterator
Non mutable iterator for visiting vertices.
Definition: SurfaceMesh.h:129
std::vector< Vertices > myNeighborVertices
For each vertex, its range of neighbor vertices (no particular order)
Definition: SurfaceMesh.h:887
BOOST_STATIC_ASSERT((dimension==3))
const std::vector< VertexPair > & allEdgeVertices() const
Definition: SurfaceMesh.h:381
std::vector< Edge > Edges
The type that defines a list/range of edges.
Definition: SurfaceMesh.h:114
std::pair< Face, Scalar > WeightedFace
Definition: SurfaceMesh.h:110
const std::vector< Faces > & allEdgeFaces() const
Definition: SurfaceMesh.h:386
const std::vector< Vertices > & allNeighborVertices() const
Definition: SurfaceMesh.h:375
const RealVector & faceNormal(Face f) const
Definition: SurfaceMesh.h:683
std::vector< Faces > myEdgeFaces
For each edge, its faces (one, two, or more if non manifold)
Definition: SurfaceMesh.h:891
Scalar distance(const Vertex i, const Vertex j) const
Definition: SurfaceMesh.h:692
void computeVertexNormalsFromFaceNormalsWithMaxWeights()
std::vector< RealVector > & vertexNormals()
Definition: SurfaceMesh.h:651
std::set< Vertex > VertexSet
Definition: SurfaceMesh.h:121
std::vector< RealVector > computeFaceUnitVectorsFromVertexUnitVectors(const std::vector< RealVector > &vuvectors) const
bool setFaceNormals(RealVectorIterator itN, RealVectorIterator itNEnd)
const RealVector & vertexNormal(Vertex v) const
Definition: SurfaceMesh.h:663
SurfaceMesh(Self &&other)=default
Scalar faceInclusionRatio(RealPoint p, Scalar r, Index f) const
std::size_t Size
The type for counting elements.
Definition: SurfaceMesh.h:103
Self & operator=(const Self &other)=default
Size nbFaces() const
Definition: SurfaceMesh.h:288
std::tuple< Vertices, WeightedEdges, WeightedFaces > computeCellsInclusionsInBall(Scalar r, Index f) const
Size nbEdges() const
Definition: SurfaceMesh.h:284
Edges computeManifoldBoundaryEdges() const
Edges computeManifoldInnerConsistentEdges() const
const std::vector< Faces > & allEdgeLeftFaces() const
Definition: SurfaceMesh.h:406
const VertexPair & edgeVertices(Edge e) const
Definition: SurfaceMesh.h:329
Size bestCapacity() const
Definition: SurfaceMesh.h:559
WeightedFaces computeFacesInclusionsInBall(Scalar r, Index f) const
const std::vector< Vertices > & allIncidentVertices() const
Definition: SurfaceMesh.h:362
const Faces & incidentFaces(Vertex v) const
Definition: SurfaceMesh.h:313
bool init(RealPointIterator itPos, RealPointIterator itPosEnd, VerticesIterator itVertices, VerticesIterator itVerticesEnd)
bool isValid() const
const Faces & edgeLeftFaces(Edge e) const
Definition: SurfaceMesh.h:357
RealVector::Component Scalar
Definition: SurfaceMesh.h:100
Edge makeEdge(Vertex i, Vertex j) const
Size degree(const Vertex &v) const
Definition: SurfaceMesh.h:567
Size nbVertices() const
Definition: SurfaceMesh.h:280
RealPoint edgeCentroid(Index e) const
void computeFaceNormalsFromVertexNormals()
std::vector< VertexPair > myEdgeVertices
For each edge, its two vertices.
Definition: SurfaceMesh.h:889
void clear()
Clears everything. The object is empty.
Edges computeNonManifoldEdges() const
const Vertices & neighborVertices(Vertex v) const
Definition: SurfaceMesh.h:323
std::vector< RealVector > myFaceNormals
For each face, its normal vector.
Definition: SurfaceMesh.h:883
std::tuple< Vertices, WeightedEdges, WeightedFaces > computeCellsInclusionsInBall(Scalar r, Index f, RealPoint p) const
ConstIterator end() const
Definition: SurfaceMesh.h:620
std::vector< Face > Faces
Definition: SurfaceMesh.h:116
std::pair< Edge, Scalar > WeightedEdge
Definition: SurfaceMesh.h:109
void computeNeighbors()
Computes neighboring information.
std::vector< Vertices > myIncidentVertices
For each face, its range of incident vertices.
Definition: SurfaceMesh.h:875
std::vector< Faces > myEdgeLeftFaces
Definition: SurfaceMesh.h:903
std::vector< RealVector > myVertexNormals
For each vertex, its normal vector.
Definition: SurfaceMesh.h:881
const std::vector< Faces > & allNeighborFaces() const
Definition: SurfaceMesh.h:371
TRealVector RealVector
Definition: SurfaceMesh.h:94
std::vector< RealPoint > myPositions
For each vertex, its position.
Definition: SurfaceMesh.h:879
void writeNeighbors(OutputIterator &it, const Vertex &v) const
Definition: SurfaceMesh.h:582
const RealPoint & position(Vertex v) const
Definition: SurfaceMesh.h:643
Scalar averageEdgeLength() const
Scalar vertexInclusionRatio(RealPoint p, Scalar r, Index v) const
const std::vector< Faces > & allIncidentFaces() const
Definition: SurfaceMesh.h:367
void selfDisplay(std::ostream &out) const