VCG Library
clean.h
1 /****************************************************************************
2 * VCGLib o o *
3 * Visual and Computer Graphics Library o o *
4 * _ O _ *
5 * Copyright(C) 2004-2016 \/)\/ *
6 * Visual Computing Lab /\/| *
7 * ISTI - Italian National Research Council | *
8 * \ *
9 * All rights reserved. *
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 * This program is distributed in the hope that it will be useful, *
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
20 * for more details. *
21 * *
22 ****************************************************************************/
23 
24 #ifndef __VCGLIB_CLEAN
25 #define __VCGLIB_CLEAN
26 
27 #include <unordered_set>
28 
29 // VCG headers
30 #include <vcg/complex/complex.h>
31 #include <vcg/complex/algorithms/closest.h>
32 #include <vcg/space/index/grid_static_ptr.h>
33 #include <vcg/space/index/spatial_hashing.h>
34 #include <vcg/complex/algorithms/update/normal.h>
35 #include <vcg/space/triangle3.h>
36 #include <vcg/complex/append.h>
37 
38 namespace vcg {
39 namespace tri{
40 
41 template <class ConnectedEdgeMeshType>
42 class EdgeConnectedComponentIterator
43 {
44 public:
45  typedef ConnectedEdgeMeshType MeshType;
46  typedef typename MeshType::VertexType VertexType;
47  typedef typename MeshType::VertexPointer VertexPointer;
48  typedef typename MeshType::VertexIterator VertexIterator;
49  typedef typename MeshType::ScalarType ScalarType;
50  typedef typename MeshType::EdgeType EdgeType;
51  typedef typename MeshType::EdgePointer EdgePointer;
52  typedef typename MeshType::EdgeIterator EdgeIterator;
53  typedef typename MeshType::ConstEdgeIterator ConstEdgeIterator;
54  typedef typename MeshType::EdgeContainer EdgeContainer;
55 
56 public:
57  void operator ++()
58  {
59  EdgePointer ep = se.top();
60  se.pop();
61  for(int i = 0; i < 2; ++i)
62  {
63  edge::VEIterator<EdgeType> vei(ep->V(i));
64  while (!vei.End())
65  {
66  if (!tri::IsMarked(*mp, vei.E()))
67  {
68  tri::Mark(*mp, vei.E());
69  se.push(vei.E());
70  }
71  ++vei;
72  }
73  }
74  }
75 
76  void start(MeshType &m, EdgePointer e)
77  {
78  tri::RequirePerEdgeMark(m);
79  mp=&m;
80 
81  while(!se.empty())
82  se.pop();
83 
84  UnMarkAll(m);
85 
86  tri::Mark(m, e);
87  se.push(e);
88  }
89 
90  bool completed() {
91  return se.empty();
92  }
93 
94  EdgePointer operator *()
95  {
96  return se.top();
97  }
98 private:
99  std::stack<EdgePointer> se;
100  MeshType *mp;
101 };
102 
103 template <class ConnectedMeshType>
104 class ConnectedComponentIterator
105 {
106 public:
107  typedef ConnectedMeshType MeshType;
108  typedef typename MeshType::VertexType VertexType;
109  typedef typename MeshType::VertexPointer VertexPointer;
110  typedef typename MeshType::VertexIterator VertexIterator;
111  typedef typename MeshType::ScalarType ScalarType;
112  typedef typename MeshType::FaceType FaceType;
113  typedef typename MeshType::FacePointer FacePointer;
114  typedef typename MeshType::FaceIterator FaceIterator;
115  typedef typename MeshType::ConstFaceIterator ConstFaceIterator;
116  typedef typename MeshType::FaceContainer FaceContainer;
117 
118 public:
119  void operator ++()
120  {
121  FacePointer fpt=sf.top();
122  sf.pop();
123  for(int j=0; j<fpt->VN(); ++j)
124  if( !face::IsBorder(*fpt,j) )
125  {
126  FacePointer l=fpt->FFp(j);
127  if( !tri::IsMarked(*mp,l) )
128  {
129  tri::Mark(*mp,l);
130  sf.push(l);
131  }
132  }
133  }
134 
135  void start(MeshType &m, FacePointer p)
136  {
137  tri::RequirePerFaceMark(m);
138  mp=&m;
139  while(!sf.empty()) sf.pop();
140  UnMarkAll(m);
141  tri::Mark(m,p);
142  sf.push(p);
143  }
144 
145  bool completed() {
146  return sf.empty();
147  }
148 
149  FacePointer operator *()
150  {
151  return sf.top();
152  }
153 private:
154  std::stack<FacePointer> sf;
155  MeshType *mp;
156 };
157 
158 
160 
162 
163 template <class CleanMeshType>
164 class Clean
165 {
166 
167 public:
168  typedef CleanMeshType MeshType;
169  typedef typename MeshType::VertexType VertexType;
170  typedef typename MeshType::VertexPointer VertexPointer;
171  typedef typename MeshType::VertexIterator VertexIterator;
172  typedef typename MeshType::ConstVertexIterator ConstVertexIterator;
173  typedef typename MeshType::EdgeIterator EdgeIterator;
174  typedef typename MeshType::EdgePointer EdgePointer;
175  typedef typename MeshType::CoordType CoordType;
176  typedef typename MeshType::ScalarType ScalarType;
177  typedef typename MeshType::FaceType FaceType;
178  typedef typename MeshType::FacePointer FacePointer;
179  typedef typename MeshType::FaceIterator FaceIterator;
180  typedef typename MeshType::ConstFaceIterator ConstFaceIterator;
181  typedef typename MeshType::FaceContainer FaceContainer;
182  typedef typename MeshType::TetraType TetraType;
183  typedef typename MeshType::TetraPointer TetraPointer;
184  typedef typename MeshType::TetraIterator TetraIterator;
185  typedef typename MeshType::ConstTetraIterator ConstTetraIterator;
186 
187  typedef typename vcg::Box3<ScalarType> Box3Type;
188 
189  typedef GridStaticPtr<FaceType, ScalarType > TriMeshGrid;
190 
191  /* classe di confronto per l'algoritmo di eliminazione vertici duplicati*/
192  class RemoveDuplicateVert_Compare{
193  public:
194  inline bool operator()(VertexPointer const &a, VertexPointer const &b)
195  {
196  return ((*a).cP() == (*b).cP()) ? (a<b): ((*a).cP() < (*b).cP());
197  }
198  };
199 
200 
205  static int RemoveDuplicateVertex( MeshType & m, bool RemoveDegenerateFlag=true) // V1.0
206  {
207  if(m.vert.size()==0 || m.vn==0) return 0;
208 
209  std::map<VertexPointer, VertexPointer> mp;
210  size_t i,j;
211  VertexIterator vi;
212  int deleted=0;
213  int k=0;
214  size_t num_vert = m.vert.size();
215  std::vector<VertexPointer> perm(num_vert);
216  for(vi=m.vert.begin(); vi!=m.vert.end(); ++vi, ++k)
217  perm[k] = &(*vi);
218 
219  RemoveDuplicateVert_Compare c_obj;
220 
221  std::sort(perm.begin(),perm.end(),c_obj);
222 
223  j = 0;
224  i = j;
225  mp[perm[i]] = perm[j];
226  ++i;
227  for(;i!=num_vert;)
228  {
229  if( (! (*perm[i]).IsD()) &&
230  (! (*perm[j]).IsD()) &&
231  (*perm[i]).P() == (*perm[j]).cP() )
232  {
233  VertexPointer t = perm[i];
234  mp[perm[i]] = perm[j];
235  ++i;
237  deleted++;
238  }
239  else
240  {
241  j = i;
242  ++i;
243  }
244  }
245 
246  for(FaceIterator fi = m.face.begin(); fi!=m.face.end(); ++fi)
247  if( !(*fi).IsD() )
248  for(k = 0; k < (*fi).VN(); ++k)
249  if( mp.find( (typename MeshType::VertexPointer)(*fi).V(k) ) != mp.end() )
250  {
251  (*fi).V(k) = &*mp[ (*fi).V(k) ];
252  }
253 
254 
255  for(EdgeIterator ei = m.edge.begin(); ei!=m.edge.end(); ++ei)
256  if( !(*ei).IsD() )
257  for(k = 0; k < 2; ++k)
258  if( mp.find( (typename MeshType::VertexPointer)(*ei).V(k) ) != mp.end() )
259  {
260  (*ei).V(k) = &*mp[ (*ei).V(k) ];
261  }
262 
263  for (TetraIterator ti = m.tetra.begin(); ti != m.tetra.end(); ++ti)
264  if (!(*ti).IsD())
265  for (k = 0; k < 4; ++k)
266  if (mp.find((typename MeshType::VertexPointer)(*ti).V(k)) != mp.end())
267  (*ti).V(k) = &*mp[ (*ti).V(k) ];
268 
269  if(RemoveDegenerateFlag) RemoveDegenerateFace(m);
270  if(RemoveDegenerateFlag && m.en>0) {
271  RemoveDegenerateEdge(m);
273  }
274  return deleted;
275  }
276 
277  class SortedPair
278  {
279  public:
280  SortedPair() {}
281  SortedPair(unsigned int v0, unsigned int v1, EdgePointer _fp)
282  {
283  v[0]=v0;v[1]=v1;
284  fp=_fp;
285  if(v[0]>v[1]) std::swap(v[0],v[1]);
286  }
287  bool operator < (const SortedPair &p) const
288  {
289  return (v[1]!=p.v[1])?(v[1]<p.v[1]):
290  (v[0]<p.v[0]); }
291 
292  bool operator == (const SortedPair &s) const
293  {
294  if( (v[0]==s.v[0]) && (v[1]==s.v[1]) ) return true;
295  return false;
296  }
297 
298  unsigned int v[2];
299  EdgePointer fp;
300  };
301  class SortedTriple
302  {
303  public:
304  SortedTriple() {}
305  SortedTriple(unsigned int v0, unsigned int v1, unsigned int v2,FacePointer _fp)
306  {
307  v[0]=v0;v[1]=v1;v[2]=v2;
308  fp=_fp;
309  std::sort(v,v+3);
310  }
311  bool operator < (const SortedTriple &p) const
312  {
313  return (v[2]!=p.v[2])?(v[2]<p.v[2]):
314  (v[1]!=p.v[1])?(v[1]<p.v[1]):
315  (v[0]<p.v[0]); }
316 
317  bool operator == (const SortedTriple &s) const
318  {
319  if( (v[0]==s.v[0]) && (v[1]==s.v[1]) && (v[2]==s.v[2]) ) return true;
320  return false;
321  }
322 
323  unsigned int v[3];
324  FacePointer fp;
325  };
326 
327 
333  static int RemoveDuplicateFace( MeshType & m) // V1.0
334  {
335  std::vector<SortedTriple> fvec;
336  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
337  if(!(*fi).IsD())
338  {
339  fvec.push_back(SortedTriple( tri::Index(m,(*fi).V(0)),
340  tri::Index(m,(*fi).V(1)),
341  tri::Index(m,(*fi).V(2)),
342  &*fi));
343  }
344  std::sort(fvec.begin(),fvec.end());
345  int total=0;
346  for(int i=0;i<int(fvec.size())-1;++i)
347  {
348  if(fvec[i]==fvec[i+1])
349  {
350  total++;
351  tri::Allocator<MeshType>::DeleteFace(m, *(fvec[i].fp) );
352  }
353  }
354  return total;
355  }
356 
362  static int RemoveDuplicateEdge( MeshType & m) // V1.0
363  {
364  if (m.en==0) return 0;
365  std::vector<SortedPair> eVec;
366  for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
367  if(!(*ei).IsD())
368  {
369  eVec.push_back(SortedPair( tri::Index(m,(*ei).V(0)), tri::Index(m,(*ei).V(1)), &*ei));
370  }
371  std::sort(eVec.begin(),eVec.end());
372  int total=0;
373  for(int i=0;i<int(eVec.size())-1;++i)
374  {
375  if(eVec[i]==eVec[i+1])
376  {
377  total++;
378  tri::Allocator<MeshType>::DeleteEdge(m, *(eVec[i].fp) );
379  }
380  }
381  return total;
382  }
383 
384  static int CountUnreferencedVertex( MeshType& m)
385  {
386  return RemoveUnreferencedVertex(m,false);
387  }
388 
389 
395  static int RemoveUnreferencedVertex( MeshType& m, bool DeleteVertexFlag=true) // V1.0
396  {
397  tri::RequirePerVertexFlags(m);
398 
399  std::vector<bool> referredVec(m.vert.size(),false);
400  int deleted = 0;
401 
402  for(auto fi = m.face.begin(); fi != m.face.end(); ++fi)
403  if( !(*fi).IsD() )
404  for(auto j=0; j < (*fi).VN(); ++j)
405  referredVec[tri::Index(m, (*fi).V(j))]=true;
406 
407  for(auto ei=m.edge.begin();ei!=m.edge.end();++ei)
408  if( !(*ei).IsD() ){
409  referredVec[tri::Index(m, (*ei).V(0))]=true;
410  referredVec[tri::Index(m, (*ei).V(1))]=true;
411  }
412 
413  for(auto ti=m.tetra.begin(); ti!=m.tetra.end();++ti)
414  if( !(*ti).IsD() ){
415  referredVec[tri::Index(m, (*ti).V(0))]=true;
416  referredVec[tri::Index(m, (*ti).V(1))]=true;
417  referredVec[tri::Index(m, (*ti).V(2))]=true;
418  referredVec[tri::Index(m, (*ti).V(3))]=true;
419  }
420 
421 
422  if(!DeleteVertexFlag)
423  return std::count(referredVec.begin(),referredVec.end(),false);
424 
425  for(auto vi=m.vert.begin();vi!=m.vert.end();++vi)
426  if( (!(*vi).IsD()) && (!referredVec[tri::Index(m,*vi)]) )
427  {
429  ++deleted;
430  }
431  return deleted;
432  }
433 
438  static int RemoveDegenerateVertex(MeshType& m)
439  {
440  VertexIterator vi;
441  int count_vd = 0;
442 
443  for(vi=m.vert.begin(); vi!=m.vert.end();++vi)
444  if(math::IsNAN( (*vi).P()[0]) ||
445  math::IsNAN( (*vi).P()[1]) ||
446  math::IsNAN( (*vi).P()[2]) )
447  {
448  count_vd++;
450  }
451 
452  FaceIterator fi;
453  int count_fd = 0;
454 
455  for(fi=m.face.begin(); fi!=m.face.end();++fi)
456  if(!(*fi).IsD())
457  if( (*fi).V(0)->IsD() ||
458  (*fi).V(1)->IsD() ||
459  (*fi).V(2)->IsD() )
460  {
461  count_fd++;
463  }
464  return count_vd;
465  }
466 
475  static int RemoveDegenerateFace(MeshType& m)
476  {
477  int count_fd = 0;
478 
479  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi)
480  if(!(*fi).IsD())
481  {
482  if((*fi).V(0) == (*fi).V(1) ||
483  (*fi).V(0) == (*fi).V(2) ||
484  (*fi).V(1) == (*fi).V(2) )
485  {
486  count_fd++;
488  }
489  }
490  return count_fd;
491  }
492 
493  static int RemoveDegenerateEdge(MeshType& m)
494  {
495  int count_ed = 0;
496 
497  for(EdgeIterator ei=m.edge.begin(); ei!=m.edge.end();++ei)
498  if(!(*ei).IsD())
499  {
500  if((*ei).V(0) == (*ei).V(1) )
501  {
502  count_ed++;
504  }
505  }
506  return count_ed;
507  }
508 
509  static int RemoveNonManifoldVertex(MeshType& m)
510  {
511  CountNonManifoldVertexFF(m,true);
513  int count_removed = 0;
514  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi)
515  if(!(*fi).IsD() && (*fi).IsS())
516  Allocator<MeshType>::DeleteFace(m,*fi);
517  for(VertexIterator vi=m.vert.begin(); vi!=m.vert.end();++vi)
518  if(!(*vi).IsD() && (*vi).IsS()) {
519  ++count_removed;
521  }
522  return count_removed;
523  }
524 
525 
526  static int SplitSelectedVertexOnEdgeMesh(MeshType& m)
527  {
528  tri::RequireCompactness(m);
529 
530  // count selected vertices references
531  std::unordered_map<size_t,size_t> refCount; // selected vertex index -> reference count
532  size_t countSplit = 0;
533  for (size_t i=0; i<m.edge.size(); ++i)
534  {
535  for (int j=0; j<2; ++j)
536  {
537  const VertexPointer vp = m.edge[i].V(j);
538  if (vp->IsS())
539  {
540  const size_t refs = ++refCount[Index(m, m.edge[i].V(j))];
541  if (refs > 1) {
542  countSplit++;
543  }
544  }
545  }
546  }
547  // actual split
548  if (countSplit > 0)
549  {
550  auto newVertIt = tri::Allocator<MeshType>::AddVertices(m, countSplit);
551  for (size_t i=0; i<m.edge.size(); ++i)
552  {
553  for (int j=0; j<2; ++j)
554  {
555  const VertexPointer vp = m.edge[i].V(j);
556  const size_t vIdx = Index(m, vp);
557  if (vp->IsS())
558  {
559  if (--refCount[vIdx] > 0)
560  {
561  newVertIt->ImportData(*vp);
562  m.edge[i].V(j) = &*(newVertIt++);
563  }
564  }
565  }
566  }
567  }
568  return int(countSplit);
569  }
570 
571 
572  static void SelectNonManifoldVertexOnEdgeMesh(MeshType &m)
573  {
574  tri::RequireCompactness(m);
576  std::vector<int> cnt(m.vn,0);
577 
578  for(size_t i=0;i<m.edge.size();++i)
579  {
580  cnt[tri::Index(m,m.edge[i].V(0))]++;
581  cnt[tri::Index(m,m.edge[i].V(1))]++;
582  }
583  for(size_t i=0;i<m.vert.size();++i)
584  if(cnt[i]>2) m.vert[i].SetS();
585  }
586 
587  static void SelectCreaseVertexOnEdgeMesh(MeshType &m, ScalarType AngleRadThr)
588  {
589  tri::RequireCompactness(m);
590  tri::RequireVEAdjacency(m);
591  tri::UpdateTopology<MeshType>::VertexEdge(m);
593  for(size_t i=0;i<m.vert.size();++i)
594  {
595  std::vector<VertexPointer> VVStarVec;
596  edge::VVStarVE(&(m.vert[i]),VVStarVec);
597  if(VVStarVec.size()==2)
598  {
599  CoordType v0 = m.vert[i].P() - VVStarVec[0]->P();
600  CoordType v1 = m.vert[i].P() - VVStarVec[1]->P();
601  float angle = M_PI-vcg::Angle(v0,v1);
602  if(angle > AngleRadThr) m.vert[i].SetS();
603  }
604  }
605  }
606 
607 
609 
610  // Given a mesh with FF adjacency
611  // it search for non manifold vertices and duplicate them.
612  // Duplicated vertices are moved apart according to the move threshold param.
613  // that is a percentage of the average vector from the non manifold vertex to the barycenter of the incident faces.
614 
615  static int SplitNonManifoldVertex(MeshType& m, ScalarType moveThreshold)
616  {
617  RequireFFAdjacency(m);
618  typedef std::pair<FacePointer,int> FaceInt; // a face and the index of the vertex that we have to change
619  //
620  std::vector<std::pair<VertexPointer, std::vector<FaceInt> > >ToSplitVec;
621 
623  ss.push();
624  CountNonManifoldVertexFF(m,true);
626  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
627  {
628  for (int i=0; i<fi->VN(); i++)
629  if ((*fi).V(i)->IsS() && !(*fi).V(i)->IsV())
630  {
631  (*fi).V(i)->SetV();
632  face::Pos<FaceType> startPos(&*fi,i);
633  face::Pos<FaceType> curPos = startPos;
634  std::set<FaceInt> faceSet;
635  do
636  {
637  faceSet.insert(std::make_pair(curPos.F(),curPos.VInd()));
638  curPos.FlipE();
639  curPos.NextF();
640  } while (curPos != startPos);
641 
642  ToSplitVec.push_back(make_pair((*fi).V(i),std::vector<FaceInt>()));
643 
644  typename std::set<FaceInt>::const_iterator iii;
645 
646  for(iii=faceSet.begin();iii!=faceSet.end();++iii)
647  ToSplitVec.back().second.push_back(*iii);
648  }
649  }
650  ss.pop();
651  // Second step actually add new vertices and split them.
652  typename tri::Allocator<MeshType>::template PointerUpdater<VertexPointer> pu;
653  VertexIterator firstVp = tri::Allocator<MeshType>::AddVertices(m,ToSplitVec.size(),pu);
654  for(size_t i =0;i<ToSplitVec.size();++i)
655  {
656  // qDebug("Splitting Vertex %i",ToSplitVec[i].first-&*m.vert.begin());
657  VertexPointer np=ToSplitVec[i].first;
658  pu.Update(np);
659  firstVp->ImportData(*np);
660  // loop on the face to be changed, and also compute the movement vector;
661  CoordType delta(0,0,0);
662  for(size_t j=0;j<ToSplitVec[i].second.size();++j)
663  {
664  FaceInt ff=ToSplitVec[i].second[j];
665  ff.first->V(ff.second)=&*firstVp;
666  delta+=Barycenter(*(ff.first))-np->cP();
667  }
668  delta /= ToSplitVec[i].second.size();
669  firstVp->P() = firstVp->P() + delta * moveThreshold;
670  firstVp++;
671  }
672 
673  return int(ToSplitVec.size());
674  }
675 
677  static size_t SplitManifoldComponents(MeshType &m)
678  {
679  typedef typename MeshType::FacePointer FacePointer;
680  typedef typename MeshType::FaceIterator FaceIterator;
681  // it also assumes that the FF adjacency is well computed.
682  RequireFFAdjacency(m);
683 
686 
687  MeshType tmpMesh;
688 
689  size_t selCnt=0;
690 
691  for(FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
692  if( !(*fi).IsD() && !(*fi).IsV() && !(*fi).IsS())
693  {
695 
696  std::deque<FacePointer> visitStack;
697  visitStack.push_back(&*fi);
698 
699  (*fi).SetS();
700  (*fi).SetV();
701 
702  while(!visitStack.empty())
703  {
704  FacePointer fp = visitStack.front();
705  visitStack.pop_front();
706 
707  for(int i=0;i<fp->VN();++i) {
708  FacePointer ff = fp->FFp(i);
709 
710  if(face::IsManifold(*fp, i) && !ff->IsS() && !ff->IsV())
711  {
712  ff->SetS();
713  ff->SetV();
714  visitStack.push_back(ff);
715  }
716  }
717  }
718 
719  Append<MeshType, MeshType>::Mesh(tmpMesh, m, true);
720  ++selCnt;
721  }
722 
725  return selCnt;
726  }
727 
728 
729  // Auxiliary function for sorting the non manifold faces according to their area. Used in RemoveNonManifoldFace
730  struct CompareAreaFP {
731  bool operator ()(FacePointer const& f1, FacePointer const& f2) const {
732  return DoubleArea(*f1) < DoubleArea(*f2);
733  }
734  };
735 
737  static int RemoveNonManifoldFace(MeshType& m)
738  {
739  FaceIterator fi;
740  int count_fd = 0;
741  std::vector<FacePointer> ToDelVec;
742 
743  for(fi=m.face.begin(); fi!=m.face.end();++fi)
744  if (!fi->IsD())
745  {
746  if ((!IsManifold(*fi,0))||
747  (!IsManifold(*fi,1))||
748  (!IsManifold(*fi,2)))
749  ToDelVec.push_back(&*fi);
750  }
751 
752  std::sort(ToDelVec.begin(),ToDelVec.end(),CompareAreaFP());
753 
754  for(size_t i=0;i<ToDelVec.size();++i)
755  {
756  if(!ToDelVec[i]->IsD())
757  {
758  FaceType &ff= *ToDelVec[i];
759  if ((!IsManifold(ff,0))||
760  (!IsManifold(ff,1))||
761  (!IsManifold(ff,2)))
762  {
763  for(int j=0;j<3;++j)
764  if(!face::IsBorder<FaceType>(ff,j))
765  vcg::face::FFDetach<FaceType>(ff,j);
766 
768  count_fd++;
769  }
770  }
771  }
772  return count_fd;
773  }
774 
775  /* Remove the faces that are out of a given range of area */
776  static int RemoveFaceOutOfRangeArea(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)(), bool OnlyOnSelected=false)
777  {
778  int count_fd = 0;
779  MinAreaThr*=2;
780  MaxAreaThr*=2;
781  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi){
782  if(!(*fi).IsD())
783  if(!OnlyOnSelected || (*fi).IsS())
784  {
785  const ScalarType doubleArea=DoubleArea<FaceType>(*fi);
786  if((doubleArea<=MinAreaThr) || (doubleArea>=MaxAreaThr) )
787  {
789  count_fd++;
790  }
791  }
792  }
793  return count_fd;
794  }
795 
796  static int RemoveZeroAreaFace(MeshType& m) { return RemoveFaceOutOfRangeArea(m,0);}
797 
798 
799 
803  static bool IsBitQuadOnly(const MeshType &m)
804  {
805  typedef typename MeshType::FaceType F;
806  tri::RequirePerFaceFlags(m);
807  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
808  unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
809  if ( tmp != F::FAUX0 && tmp != F::FAUX1 && tmp != F::FAUX2) return false;
810  }
811  return true;
812  }
813 
814 
815  static bool IsFaceFauxConsistent(MeshType &m)
816  {
817  RequirePerFaceFlags(m);
818  RequireFFAdjacency(m);
819  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
820  {
821  for(int z=0;z<(*fi).VN();++z)
822  {
823  FacePointer fp = fi->FFp(z);
824  int zp = fi->FFi(z);
825  if(fi->IsF(z) != fp->IsF(zp)) return false;
826  }
827  }
828  return true;
829  }
830 
834  static bool IsBitTriOnly(const MeshType &m)
835  {
836  tri::RequirePerFaceFlags(m);
837  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) {
838  if ( !fi->IsD() && fi->IsAnyF() ) return false;
839  }
840  return true;
841  }
842 
843  static bool IsBitPolygonal(const MeshType &m){
844  return !IsBitTriOnly(m);
845  }
846 
851  static bool IsBitTriQuadOnly(const MeshType &m)
852  {
853  tri::RequirePerFaceFlags(m);
854  typedef typename MeshType::FaceType F;
855  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
856  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
857  if ( tmp!=F::FAUX0 && tmp!=F::FAUX1 && tmp!=F::FAUX2 && tmp!=0 ) return false;
858  }
859  return true;
860  }
861 
866  static int CountBitQuads(const MeshType &m)
867  {
868  tri::RequirePerFaceFlags(m);
869  typedef typename MeshType::FaceType F;
870  int count=0;
871  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
872  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
873  if ( tmp==F::FAUX0 || tmp==F::FAUX1 || tmp==F::FAUX2) count++;
874  }
875  return count / 2;
876  }
877 
881  static int CountBitTris(const MeshType &m)
882  {
883  tri::RequirePerFaceFlags(m);
884  int count=0;
885  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
886  if (!(fi->IsAnyF())) count++;
887  }
888  return count;
889  }
890 
895  static int CountBitPolygons(const MeshType &m)
896  {
897  tri::RequirePerFaceFlags(m);
898  int count = 0;
899  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
900  if (fi->IsF(0)) count++;
901  if (fi->IsF(1)) count++;
902  if (fi->IsF(2)) count++;
903  }
904  return m.fn - count/2;
905  }
906 
918  static int CountBitLargePolygons(MeshType &m)
919  {
920  tri::RequirePerFaceFlags(m);
922  // First loop Clear all referenced vertices
923  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
924  if (!fi->IsD())
925  for(int i=0;i<3;++i) fi->V(i)->ClearV();
926 
927 
928  // Second Loop, count (twice) faux edges and mark all vertices touched by non faux edges
929  // (e.g vertexes on the boundary of a polygon)
930  int countE = 0;
931  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
932  if (!fi->IsD()) {
933  for(int i=0;i<3;++i)
934  {
935  if (fi->IsF(i))
936  countE++;
937  else
938  {
939  fi->V0(i)->SetV();
940  fi->V1(i)->SetV();
941  }
942  }
943  }
944  // Third Loop, count the number of referenced vertexes that are completely surrounded by faux edges.
945 
946  int countV = 0;
947  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
948  if (!vi->IsD() && !vi->IsV()) countV++;
949 
950  return m.fn - countE/2 + countV ;
951  }
952 
953 
961  static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
962  {
963  RequireFFAdjacency(m);
964  RequirePerFaceFlags(m);
965 
966  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
967  if(!(*fi).IsD())
968  for (int k=0; k<3; k++)
969  if( ( fi->IsF(k) != fi->cFFp(k)->IsF(fi->cFFi(k)) ) ||
970  ( fi->IsF(k) && face::IsBorder(*fi,k)) )
971  {
972  return false;
973  }
974  return true;
975  }
976 
981  static int CountNonManifoldEdgeEE( MeshType & m, bool SelectFlag=false)
982  {
983  MeshAssert<MeshType>::OnlyEdgeMesh(m);
984  RequireEEAdjacency(m);
986 
987  if(SelectFlag) UpdateSelection<MeshType>::VertexClear(m);
988 
989  int nonManifoldCnt=0;
990  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
991 
992  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
993  EdgeIterator ei;
994  for (ei = m.edge.begin(); ei != m.edge.end(); ++ei) if (!ei->IsD())
995  {
996  TD[(*ei).V(0)]++;
997  TD[(*ei).V(1)]++;
998  }
999 
1001  // Second Loop, Check that each vertex have been seen 1 or 2 times.
1002  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if (!vi->IsD())
1003  {
1004  if( TD[vi] >2 )
1005  {
1006  if(SelectFlag) (*vi).SetS();
1007  nonManifoldCnt++;
1008  }
1009  }
1010  return nonManifoldCnt;
1011  }
1012 
1019  static int CountNonManifoldEdgeFF( MeshType & m, bool SelectFlag=false)
1020  {
1021  RequireFFAdjacency(m);
1022  int nmfBit[3];
1023  nmfBit[0]= FaceType::NewBitFlag();
1024  nmfBit[1]= FaceType::NewBitFlag();
1025  nmfBit[2]= FaceType::NewBitFlag();
1026 
1027 
1028  UpdateFlags<MeshType>::FaceClear(m,nmfBit[0]+nmfBit[1]+nmfBit[2]);
1029 
1030  if(SelectFlag){
1033  }
1034 
1035  int edgeCnt = 0;
1036  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1037  {
1038  if (!fi->IsD())
1039  {
1040  for(int i=0;i<3;++i)
1041  if(!IsManifold(*fi,i))
1042  {
1043  if(!(*fi).IsUserBit(nmfBit[i]))
1044  {
1045  ++edgeCnt;
1046  if(SelectFlag)
1047  {
1048  (*fi).V0(i)->SetS();
1049  (*fi).V1(i)->SetS();
1050  }
1051  // follow the ring of faces incident on edge i;
1052  face::Pos<FaceType> nmf(&*fi,i);
1053  do
1054  {
1055  if(SelectFlag) nmf.F()->SetS();
1056  nmf.F()->SetUserBit(nmfBit[nmf.E()]);
1057  nmf.NextF();
1058  }
1059  while(nmf.f != &*fi);
1060  }
1061  }
1062  }
1063  }
1064  return edgeCnt;
1065  }
1066 
1071  static int CountNonManifoldVertexFF( MeshType & m, bool selectVert = true, bool clearSelection = true)
1072  {
1073  RequireFFAdjacency(m);
1074  if(selectVert && clearSelection) UpdateSelection<MeshType>::VertexClear(m);
1075 
1076  int nonManifoldCnt=0;
1077  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
1078 
1079  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
1080  FaceIterator fi;
1081  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1082  {
1083  for (int k=0; k<fi->VN(); k++)
1084  {
1085  TD[(*fi).V(k)]++;
1086  }
1087  }
1088 
1090  // Second Loop.
1091  // mark out of the game the vertexes that are incident on non manifold edges.
1092  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1093  {
1094  for(int i=0; i<fi->VN(); ++i)
1095  if (!IsManifold(*fi,i))
1096  {
1097  (*fi).V0(i)->SetV();
1098  (*fi).V1(i)->SetV();
1099  }
1100  }
1101  // Third Loop, for safe vertexes, check that the number of faces that you can reach starting
1102  // from it and using FF is the same of the previously counted.
1103  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1104  {
1105  for(int i=0; i<fi->VN(); i++) if (!(*fi).V(i)->IsV())
1106  {
1107  (*fi).V(i)->SetV();
1108  face::Pos<FaceType> pos(&(*fi),i);
1109 
1110  int starSizeFF = pos.NumberOfIncidentFaces();
1111 
1112  if (starSizeFF != TD[(*fi).V(i)])
1113  {
1114  if (selectVert)
1115  (*fi).V(i)->SetS();
1116  nonManifoldCnt++;
1117  }
1118  }
1119  }
1120  return nonManifoldCnt;
1121  }
1129  static bool IsWaterTight(MeshType & m)
1130  {
1131  int edgeNum=0,edgeBorderNum=0,edgeNonManifNum=0;
1132  CountEdgeNum(m, edgeNum, edgeBorderNum,edgeNonManifNum);
1133  return (edgeBorderNum==0) && (edgeNonManifNum==0);
1134  }
1135 
1136  static void CountEdgeNum( MeshType & m, int &total_e, int &boundary_e, int &non_manif_e )
1137  {
1138  std::vector< typename tri::UpdateTopology<MeshType>::PEdge > edgeVec;
1140  sort(edgeVec.begin(), edgeVec.end()); // Lo ordino per vertici
1141  total_e=0;
1142  boundary_e=0;
1143  non_manif_e=0;
1144 
1145  size_t f_on_cur_edge =1;
1146  for(size_t i=0;i<edgeVec.size();++i)
1147  {
1148  if(( (i+1) == edgeVec.size()) || !(edgeVec[i] == edgeVec[i+1]))
1149  {
1150  ++total_e;
1151  if(f_on_cur_edge==1)
1152  ++boundary_e;
1153  if(f_on_cur_edge>2)
1154  ++non_manif_e;
1155  f_on_cur_edge=1;
1156  }
1157  else
1158  {
1159  ++f_on_cur_edge;
1160  }
1161  } // end for
1162  }
1163 
1164 
1165 
1166  static int CountHoles( MeshType & m)
1167  {
1168  UpdateFlags<MeshType>::FaceClearV(m);
1169  int loopNum=0;
1170  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD())
1171  {
1172  for(int j=0;j<3;++j)
1173  {
1174  if(!fi->IsV() && face::IsBorder(*fi,j))
1175  {
1176  face::Pos<FaceType> startPos(&*fi,j);
1177  face::Pos<FaceType> curPos=startPos;
1178  do
1179  {
1180  curPos.NextB();
1181  curPos.F()->SetV();
1182  }
1183  while(curPos!=startPos);
1184  ++loopNum;
1185  }
1186  }
1187  }
1188  return loopNum;
1189  }
1190 
1191  /*
1192  Compute the set of connected components of a given mesh
1193  it fills a vector of pair < int , faceptr > with, for each connecteed component its size and a represnant
1194  */
1195  static int CountConnectedComponents(MeshType &m)
1196  {
1197  std::vector< std::pair<int,FacePointer> > CCV;
1198  return ConnectedComponents(m,CCV);
1199  }
1200 
1201  static int ConnectedComponents(MeshType &m, std::vector< std::pair<int,FacePointer> > &CCV)
1202  {
1203  tri::RequireFFAdjacency(m);
1204  CCV.clear();
1205  tri::UpdateFlags<MeshType>::FaceClearV(m);
1206  std::stack<FacePointer> sf;
1207  FacePointer fpt=&*(m.face.begin());
1208  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1209  {
1210  if(!((*fi).IsD()) && !(*fi).IsV())
1211  {
1212  (*fi).SetV();
1213  CCV.push_back(std::make_pair(0,&*fi));
1214  sf.push(&*fi);
1215  while (!sf.empty())
1216  {
1217  fpt=sf.top();
1218  ++CCV.back().first;
1219  sf.pop();
1220  for(int j=0; j<fpt->VN(); ++j)
1221  {
1222  if( !face::IsBorder(*fpt,j) )
1223  {
1224  FacePointer l = fpt->FFp(j);
1225  if( !(*l).IsV() )
1226  {
1227  (*l).SetV();
1228  sf.push(l);
1229  }
1230  }
1231  }
1232  }
1233  }
1234  }
1235  return int(CCV.size());
1236  }
1237 
1238  static int edgeMeshConnectedComponents(MeshType & poly, std::vector<std::pair<int, typename MeshType::EdgePointer> > &eCC)
1239  {
1240  typedef typename MeshType::EdgePointer EdgePointer;
1241  tri::UpdateTopology<MeshType>::VertexEdge(poly);
1242  tri::UpdateFlags<MeshType>::EdgeClear(poly);
1243  eCC.clear();
1244  std::stack<EdgePointer> stack;
1245 
1246  for (auto ei = poly.edge.begin(); ei != poly.edge.end(); ++ei)
1247  if (!ei->IsD() && !ei->IsV())
1248  {
1249  ei->SetV();
1250 
1251  std::pair<int, EdgePointer> cc(1, &*ei);
1252 
1253  stack.push(&*ei);
1254  while (!stack.empty())
1255  {
1256  EdgePointer ep = stack.top();
1257  stack.pop();
1258 
1259  for (int i = 0; i < 2; ++i)
1260  {
1261  edge::VEIterator<typename MeshType::EdgeType> vei(ep->V(i));
1262  while (!vei.End())
1263  {
1264  if (!vei.E()->IsV())
1265  {
1266  vei.E()->SetV();
1267  stack.push(vei.E());
1268  cc.first += 1;
1269  }
1270  ++vei;
1271  }
1272  }
1273  }
1274  eCC.push_back(cc);
1275  }
1276  return int(eCC.size());
1277  }
1278 
1279  static void ComputeValence( MeshType &m, typename MeshType::PerVertexIntHandle &h)
1280  {
1281  for(VertexIterator vi=m.vert.begin(); vi!= m.vert.end();++vi)
1282  h[vi]=0;
1283 
1284  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1285  {
1286  if(!((*fi).IsD()))
1287  for(int j=0;j<fi->VN();j++)
1288  ++h[tri::Index(m,fi->V(j))];
1289  }
1290  }
1291 
1327  static int MeshGenus(int nvert,int nedges,int nfaces, int numholes, int numcomponents)
1328  {
1329  return -((nvert + nfaces - nedges + numholes - 2 * numcomponents) / 2);
1330  }
1331 
1332  static int MeshGenus(MeshType &m)
1333  {
1334  int nvert=m.vn;
1335  int nfaces=m.fn;
1336  int boundary_e,total_e,nonmanif_e;
1337  CountEdgeNum(m,total_e,boundary_e,nonmanif_e);
1338  int numholes=CountHoles(m);
1339  int numcomponents=CountConnectedComponents(m);
1340  int G=MeshGenus(nvert,total_e,nfaces,numholes,numcomponents);
1341  return G;
1342  }
1343 
1355  static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular)
1356  {
1357  RequireVFAdjacency(m);
1358  Regular = true;
1359 
1360  VertexIterator vi;
1361 
1362  // for each vertex the number of edges are count
1363  for (vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1364  {
1365  if (!vi->IsD())
1366  {
1367  face::Pos<FaceType> he((*vi).VFp(), &*vi);
1368  face::Pos<FaceType> ht = he;
1369 
1370  int n=0;
1371  bool border=false;
1372  do
1373  {
1374  ++n;
1375  ht.NextE();
1376  if (ht.IsBorder())
1377  border=true;
1378  }
1379  while (ht != he);
1380 
1381  if (border)
1382  n = n/2;
1383 
1384  if ((n != 6)&&(!border && n != 4))
1385  {
1386  Regular = false;
1387  break;
1388  }
1389  }
1390  }
1391 
1392  if (!Regular)
1393  Semiregular = false;
1394  else
1395  {
1396  // For now we do not account for semi-regularity
1397  Semiregular = false;
1398  }
1399  }
1400 
1401 
1402  static bool IsCoherentlyOrientedMesh(MeshType &m)
1403  {
1404  RequireFFAdjacency(m);
1405  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1406  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1407  if (!fi->IsD())
1408  for(int i=0;i<3;++i)
1409  if(!face::CheckOrientation(*fi,i))
1410  return false;
1411 
1412  return true;
1413  }
1414 
1415  static void OrientCoherentlyMesh(MeshType &m, bool &_IsOriented, bool &_IsOrientable)
1416  {
1417  RequireFFAdjacency(m);
1418  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1419  bool IsOrientable = true;
1420  bool IsOriented = true;
1421 
1422  UpdateFlags<MeshType>::FaceClearV(m);
1423  std::stack<FacePointer> faces;
1424  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1425  {
1426  if (!fi->IsD() && !fi->IsV())
1427  {
1428  // each face put in the stack is selected (and oriented)
1429  fi->SetV();
1430  faces.push(&(*fi));
1431  while (!faces.empty())
1432  {
1433  FacePointer fp = faces.top();
1434  faces.pop();
1435 
1436  // make consistently oriented the adjacent faces
1437  for (int j = 0; j < 3; j++)
1438  {
1439  if (!face::IsBorder(*fp,j) && face::IsManifold<FaceType>(*fp, j))
1440  {
1441  FacePointer fpaux = fp->FFp(j);
1442  int iaux = fp->FFi(j);
1443  if (!CheckOrientation(*fpaux, iaux))
1444  {
1445  IsOriented = false;
1446 
1447  if (!fpaux->IsV())
1448  face::SwapEdge<FaceType,true>(*fpaux, iaux);
1449  else
1450  {
1451  IsOrientable = false;
1452  break;
1453  }
1454  }
1455  if (!fpaux->IsV())
1456  {
1457  fpaux->SetV();
1458  faces.push(fpaux);
1459  }
1460  }
1461  }
1462  }
1463  }
1464  if (!IsOrientable) break;
1465  }
1466  _IsOriented = IsOriented;
1467  _IsOrientable = IsOrientable;
1468  }
1469 
1470 
1472  static void FlipMesh(MeshType &m, bool selected=false)
1473  {
1474  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if(!(*fi).IsD())
1475  if(!selected || (*fi).IsS())
1476  {
1477  face::SwapEdge<FaceType,false>((*fi), 0);
1478  if (HasPerWedgeTexCoord(m))
1479  std::swap((*fi).WT(0),(*fi).WT(1));
1480  }
1481  }
1487  static bool FlipNormalOutside(MeshType &m)
1488  {
1489  if(m.vert.empty()) return false;
1490 
1493 
1494  std::vector< VertexPointer > minVertVec;
1495  std::vector< VertexPointer > maxVertVec;
1496 
1497  // The set of directions to be choosen
1498  std::vector< CoordType > dirVec;
1499  dirVec.push_back(CoordType(1,0,0));
1500  dirVec.push_back(CoordType(0,1,0));
1501  dirVec.push_back(CoordType(0,0,1));
1502  dirVec.push_back(CoordType( 1, 1,1));
1503  dirVec.push_back(CoordType(-1, 1,1));
1504  dirVec.push_back(CoordType(-1,-1,1));
1505  dirVec.push_back(CoordType( 1,-1,1));
1506  for(size_t i=0;i<dirVec.size();++i)
1507  {
1508  Normalize(dirVec[i]);
1509  minVertVec.push_back(&*m.vert.begin());
1510  maxVertVec.push_back(&*m.vert.begin());
1511  }
1512  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if(!(*vi).IsD())
1513  {
1514  for(size_t i=0;i<dirVec.size();++i)
1515  {
1516  if( (*vi).cP().dot(dirVec[i]) < minVertVec[i]->P().dot(dirVec[i])) minVertVec[i] = &*vi;
1517  if( (*vi).cP().dot(dirVec[i]) > maxVertVec[i]->P().dot(dirVec[i])) maxVertVec[i] = &*vi;
1518  }
1519  }
1520 
1521  int voteCount=0;
1522  ScalarType angleThreshold = cos(math::ToRad(85.0));
1523  for(size_t i=0;i<dirVec.size();++i)
1524  {
1525  // qDebug("Min vert along (%f %f %f) is %f %f %f",dirVec[i][0],dirVec[i][1],dirVec[i][2],minVertVec[i]->P()[0],minVertVec[i]->P()[1],minVertVec[i]->P()[2]);
1526  // qDebug("Max vert along (%f %f %f) is %f %f %f",dirVec[i][0],dirVec[i][1],dirVec[i][2],maxVertVec[i]->P()[0],maxVertVec[i]->P()[1],maxVertVec[i]->P()[2]);
1527  if(minVertVec[i]->N().dot(dirVec[i]) > angleThreshold ) voteCount++;
1528  if(maxVertVec[i]->N().dot(dirVec[i]) < -angleThreshold ) voteCount++;
1529  }
1530  // qDebug("votecount = %i",voteCount);
1531  if(voteCount < int(dirVec.size())/2) return false;
1532  FlipMesh(m);
1533  return true;
1534  }
1535 
1536  // Search and remove small single triangle folds
1537  // - a face has normal opposite to all other faces
1538  // - choose the edge that brings to the face f1 containing the vertex opposite to that edge.
1539  static int RemoveFaceFoldByFlip(MeshType &m, float normalThresholdDeg=175, bool repeat=true)
1540  {
1541  RequireFFAdjacency(m);
1542  RequirePerVertexMark(m);
1543  //Counters for logging and convergence
1544  int count, total = 0;
1545 
1546  do {
1548  tri::UnMarkAll(m);
1549  count = 0;
1550 
1551  ScalarType NormalThrRad = math::ToRad(normalThresholdDeg);
1552  ScalarType eps = ScalarType(0.0001); // this epsilon value is in absolute value. It is a distance from edge in baricentric coords.
1553  //detection stage
1554  for(FaceIterator fi=m.face.begin();fi!= m.face.end();++fi ) if(!(*fi).IsV())
1555  { Point3<ScalarType> NN = vcg::TriangleNormal((*fi)).Normalize();
1556  if( vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(0)).Normalize()) > NormalThrRad &&
1557  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(1)).Normalize()) > NormalThrRad &&
1558  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(2)).Normalize()) > NormalThrRad )
1559  {
1560  (*fi).SetS();
1561  //(*fi).C()=Color4b(Color4b::Red);
1562  // now search the best edge to flip
1563  for(int i=0;i<3;i++)
1564  {
1565  Point3<ScalarType> &p=(*fi).P2(i);
1566  Point3<ScalarType> L;
1567  bool ret = vcg::InterpolationParameters((*(*fi).FFp(i)),TriangleNormal(*(*fi).FFp(i)),p,L);
1568  if(ret && L[0]>eps && L[1]>eps && L[2]>eps)
1569  {
1570  (*fi).FFp(i)->SetS();
1571  (*fi).FFp(i)->SetV();
1572  //(*fi).FFp(i)->C()=Color4b(Color4b::Green);
1573  if(face::CheckFlipEdge<FaceType>( *fi, i )) {
1574  face::FlipEdge<FaceType>( *fi, i );
1575  ++count; ++total;
1576  }
1577  }
1578  }
1579  }
1580  }
1581 
1582  // tri::UpdateNormal<MeshType>::PerFace(m);
1583  }
1584  while( repeat && count );
1585  return total;
1586  }
1587 
1588 
1589  static int RemoveTVertexByFlip(MeshType &m, float threshold=40, bool repeat=true)
1590  {
1591  RequireFFAdjacency(m);
1592  RequirePerVertexMark(m);
1593  //Counters for logging and convergence
1594  int count, total = 0;
1595 
1596  do {
1598  tri::UnMarkAll(m);
1599  count = 0;
1600 
1601  //detection stage
1602  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1603  {
1604  FacePointer f = &(m.face[index]); float sides[3]; CoordType dummy;
1605  sides[0] = Distance(f->P(0), f->P(1));
1606  sides[1] = Distance(f->P(1), f->P(2));
1607  sides[2] = Distance(f->P(2), f->P(0));
1608  // Find largest triangle side
1609  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1610  if( tri::IsMarked(m,f->V2(i) )) continue;
1611 
1612  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1613  {
1614  tri::Mark(m,f->V2(i));
1615  if(face::CheckFlipEdge<FaceType>( *f, i )) {
1616  // Check if EdgeFlipping improves quality
1617  FacePointer g = f->FFp(i); int k = f->FFi(i);
1618  Triangle3<ScalarType> t1(f->P(i), f->P1(i), f->P2(i)), t2(g->P(k), g->P1(k), g->P2(k)),
1619  t3(f->P(i), g->P2(k), f->P2(i)), t4(g->P(k), f->P2(i), g->P2(k));
1620 
1621  if ( std::min( QualityFace(t1), QualityFace(t2) ) < std::min( QualityFace(t3), QualityFace(t4) ))
1622  {
1623  face::FlipEdge<FaceType>( *f, i );
1624  ++count; ++total;
1625  }
1626  }
1627 
1628  }
1629  }
1630 
1631  // tri::UpdateNormal<MeshType>::PerFace(m);
1632  }
1633  while( repeat && count );
1634  return total;
1635  }
1636 
1637  static int RemoveTVertexByCollapse(MeshType &m, float threshold=40, bool repeat=true)
1638  {
1639  RequirePerVertexMark(m);
1640  //Counters for logging and convergence
1641  int count, total = 0;
1642 
1643  do {
1644  tri::UnMarkAll(m);
1645  count = 0;
1646 
1647  //detection stage
1648  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1649  {
1650  FacePointer f = &(m.face[index]);
1651  float sides[3];
1652  CoordType dummy;
1653 
1654  sides[0] = Distance(f->P(0), f->P(1));
1655  sides[1] = Distance(f->P(1), f->P(2));
1656  sides[2] = Distance(f->P(2), f->P(0));
1657  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1658  if( tri::IsMarked(m,f->V2(i) )) continue;
1659 
1660  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1661  {
1662  tri::Mark(m,f->V2(i));
1663 
1664  int j = Distance(dummy,f->P(i))<Distance(dummy,f->P1(i))?i:(i+1)%3;
1665  f->P2(i) = f->P(j); tri::Mark(m,f->V(j));
1666  ++count; ++total;
1667  }
1668  }
1669 
1670 
1674  }
1675  while( repeat && count );
1676 
1677  return total;
1678  }
1679 
1680  static bool SelfIntersections(MeshType &m, std::vector<FaceType*> &ret)
1681  {
1682  RequirePerFaceMark(m);
1683  ret.clear();
1684  int referredBit = FaceType::NewBitFlag();
1685  tri::UpdateFlags<MeshType>::FaceClear(m,referredBit);
1686 
1687  TriMeshGrid gM;
1688  gM.Set(m.face.begin(),m.face.end());
1689 
1690  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
1691  {
1692  (*fi).SetUserBit(referredBit);
1693  Box3< ScalarType> bbox;
1694  (*fi).GetBBox(bbox);
1695  std::vector<FaceType*> inBox;
1696  vcg::tri::GetInBoxFace(m, gM, bbox,inBox);
1697  bool Intersected=false;
1698  typename std::vector<FaceType*>::iterator fib;
1699  for(fib=inBox.begin();fib!=inBox.end();++fib)
1700  {
1701  if(!(*fib)->IsUserBit(referredBit) && (*fib != &*fi) )
1702  if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){
1703  ret.push_back(*fib);
1704  if(!Intersected) {
1705  ret.push_back(&*fi);
1706  Intersected=true;
1707  }
1708  }
1709  }
1710  inBox.clear();
1711  }
1712 
1713  FaceType::DeleteBitFlag(referredBit);
1714  return (ret.size()>0);
1715  }
1716 
1720  static bool IsSizeConsistent(MeshType &m)
1721  {
1722  int DeletedVertNum=0;
1723  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1724  if((*vi).IsD()) DeletedVertNum++;
1725 
1726  int DeletedEdgeNum=0;
1727  for (EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei)
1728  if((*ei).IsD()) DeletedEdgeNum++;
1729 
1730  int DeletedFaceNum=0;
1731  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1732  if((*fi).IsD()) DeletedFaceNum++;
1733 
1734  if(size_t(m.vn+DeletedVertNum) != m.vert.size()) return false;
1735  if(size_t(m.en+DeletedEdgeNum) != m.edge.size()) return false;
1736  if(size_t(m.fn+DeletedFaceNum) != m.face.size()) return false;
1737 
1738  return true;
1739  }
1740 
1745  static bool IsFFAdjacencyConsistent(MeshType &m)
1746  {
1747  RequireFFAdjacency(m);
1748 
1749  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1750  if(!(*fi).IsD())
1751  {
1752  for(int i=0;i<3;++i)
1753  if(!FFCorrectness(*fi, i)) return false;
1754  }
1755  return true;
1756  }
1757 
1761  static bool HasConsistentPerWedgeTexCoord(MeshType &m)
1762  {
1763  tri::RequirePerFaceWedgeTexCoord(m);
1764 
1765  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1766  if(!(*fi).IsD())
1767  { FaceType &f=(*fi);
1768  if( ! ( (f.WT(0).N() == f.WT(1).N()) && (f.WT(0).N() == (*fi).WT(2).N()) ) )
1769  return false; // all the vertices must have the same index.
1770 
1771  if((*fi).WT(0).N() <0) return false; // no undefined texture should be allowed
1772  }
1773  return true;
1774  }
1775 
1779  static bool HasZeroTexCoordFace(MeshType &m)
1780  {
1781  tri::RequirePerFaceWedgeTexCoord(m);
1782 
1783  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1784  if(!(*fi).IsD())
1785  {
1786  if( (*fi).WT(0).P() == (*fi).WT(1).P() && (*fi).WT(0).P() == (*fi).WT(2).P() ) return false;
1787  }
1788  return true;
1789  }
1790 
1791 
1799  static bool TestFaceFaceIntersection(FaceType *f0,FaceType *f1)
1800  {
1801  int sv = face::CountSharedVertex(f0,f1);
1802  if(sv==3) return true;
1803  if(sv==0) return (vcg::IntersectionTriangleTriangle<FaceType>((*f0),(*f1)));
1804  // if the faces share only a vertex, the opposite edge (as a segment) is tested against the face
1805  // to avoid degenerate cases where the two triangles have the opposite edge on a common plane
1806  // we offset the segment to test toward the shared vertex
1807  if(sv==1)
1808  {
1809  int i0,i1; ScalarType a,b;
1810  face::FindSharedVertex(f0,f1,i0,i1);
1811  CoordType shP = f0->V(i0)->P()*0.5;
1812  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f0).V1(i0)->P()*0.5+shP,(*f0).V2(i0)->P()*0.5+shP), *f1, a, b) )
1813  {
1814  // a,b are the param coords of the intersection point of the segment.
1815  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1816  return true;
1817  }
1818  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f1).V1(i1)->P()*0.5+shP,(*f1).V2(i1)->P()*0.5+shP), *f0, a, b) )
1819  {
1820  // a,b are the param coords of the intersection point of the segment.
1821  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1822  return true;
1823  }
1824 
1825  }
1826  return false;
1827  }
1828 
1829 
1830 
1834  static int MergeCloseVertex(MeshType &m, const ScalarType radius)
1835  {
1836  int mergedCnt=0;
1837  mergedCnt = ClusterVertex(m,radius);
1838  RemoveDuplicateVertex(m,true);
1839  return mergedCnt;
1840  }
1841 
1842  static int ClusterVertex(MeshType &m, const ScalarType radius)
1843  {
1844  if(m.vn==0) return 0;
1845  // some spatial indexing structure does not work well with deleted vertices...
1847  typedef vcg::SpatialHashTable<VertexType, ScalarType> SampleSHT;
1848  SampleSHT sht;
1849  tri::EmptyTMark<MeshType> markerFunctor;
1850  std::vector<VertexType*> closests;
1851  int mergedCnt=0;
1852  sht.Set(m.vert.begin(), m.vert.end());
1854  for(VertexIterator viv = m.vert.begin(); viv!= m.vert.end(); ++viv)
1855  if(!(*viv).IsD() && !(*viv).IsV())
1856  {
1857  (*viv).SetV();
1858  Point3<ScalarType> p = viv->cP();
1859  Box3<ScalarType> bb(p-Point3<ScalarType>(radius,radius,radius),p+Point3<ScalarType>(radius,radius,radius));
1860  GridGetInBox(sht, markerFunctor, bb, closests);
1861  // qDebug("Vertex %i has %i closest", &*viv - &*m.vert.begin(),closests.size());
1862  for(size_t i=0; i<closests.size(); ++i)
1863  {
1864  ScalarType dist = Distance(p,closests[i]->cP());
1865  if(dist < radius && !closests[i]->IsV())
1866  {
1867  // printf("%f %f \n",dist,radius);
1868  mergedCnt++;
1869  closests[i]->SetV();
1870  closests[i]->P()=p;
1871  }
1872  }
1873  }
1874  return mergedCnt;
1875  }
1876 
1877 
1878  static std::pair<int,int> RemoveSmallConnectedComponentsSize(MeshType &m, int maxCCSize)
1879  {
1880  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1881  int TotalCC=ConnectedComponents(m, CCV);
1882  int DeletedCC=0;
1883 
1884  ConnectedComponentIterator<MeshType> ci;
1885  for(unsigned int i=0;i<CCV.size();++i)
1886  {
1887  std::vector<typename MeshType::FacePointer> FPV;
1888  if(CCV[i].first<maxCCSize)
1889  {
1890  DeletedCC++;
1891  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1892  FPV.push_back(*ci);
1893 
1894  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1895  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1896  Allocator<MeshType>::DeleteFace(m,(**fpvi));
1897  }
1898  }
1899  return std::make_pair(TotalCC,DeletedCC);
1900  }
1901 
1902 
1904  // it returns a pair with the number of connected components and the number of deleted ones.
1905  static std::pair<int,int> RemoveSmallConnectedComponentsDiameter(MeshType &m, ScalarType maxDiameter)
1906  {
1907  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1908  int TotalCC=ConnectedComponents(m, CCV);
1909  int DeletedCC=0;
1910  tri::ConnectedComponentIterator<MeshType> ci;
1911  for(unsigned int i=0;i<CCV.size();++i)
1912  {
1913  Box3<ScalarType> bb;
1914  std::vector<typename MeshType::FacePointer> FPV;
1915  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1916  {
1917  FPV.push_back(*ci);
1918  bb.Add((*ci)->P(0));
1919  bb.Add((*ci)->P(1));
1920  bb.Add((*ci)->P(2));
1921  }
1922  if(bb.Diag()<maxDiameter)
1923  {
1924  DeletedCC++;
1925  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1926  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1928  }
1929  }
1930  return std::make_pair(TotalCC,DeletedCC);
1931  }
1932 
1934  // it returns a pair with the number of connected components and the number of deleted ones.
1935  static std::pair<int,int> RemoveHugeConnectedComponentsDiameter(MeshType &m, ScalarType minDiameter)
1936  {
1937  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1938  int TotalCC=ConnectedComponents(m, CCV);
1939  int DeletedCC=0;
1940  tri::ConnectedComponentIterator<MeshType> ci;
1941  for(unsigned int i=0;i<CCV.size();++i)
1942  {
1943  Box3f bb;
1944  std::vector<typename MeshType::FacePointer> FPV;
1945  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1946  {
1947  FPV.push_back(*ci);
1948  bb.Add((*ci)->P(0));
1949  bb.Add((*ci)->P(1));
1950  bb.Add((*ci)->P(2));
1951  }
1952  if(bb.Diag()>minDiameter)
1953  {
1954  DeletedCC++;
1955  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1956  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1958  }
1959  }
1960  return std::make_pair(TotalCC,DeletedCC);
1961  }
1962 
1963 
1964 
1971  static void SelectFoldedFaceFromOneRingFaces(MeshType &m, ScalarType cosThreshold)
1972  {
1973  typedef std::unordered_set<VertexPointer> VertexSet;
1974  tri::RequireVFAdjacency(m);
1975  tri::RequirePerFaceNormal(m);
1976  tri::RequirePerVertexNormal(m);
1981  if (cosThreshold > 0)
1982  cosThreshold = 0;
1983 
1984 #pragma omp parallel for schedule(dynamic, 10)
1985  for (int i = 0; i < m.face.size(); i++)
1986  {
1987  VertexSet nearVertex;
1988  std::vector<CoordType> pointVec;
1989  FacePointer f = &m.face[i];
1990  for (int j = 0; j < 3; j++)
1991  {
1992  std::vector<VertexPointer> temp;
1993  vcg::face::VVStarVF<FaceType>(f->V(j), temp);
1994  typename std::vector<VertexPointer>::iterator iter = temp.begin();
1995  for (; iter != temp.end(); iter++)
1996  {
1997  if ((*iter) != f->V1(j) && (*iter) != f->V2(j))
1998  {
1999  if (nearVertex.insert((*iter)).second)
2000  pointVec.push_back((*iter)->P());
2001  }
2002  }
2003  nearVertex.insert(f->V(j));
2004  pointVec.push_back(f->P(j));
2005  }
2006 
2007  if (pointVec.size() > 3)
2008  {
2009  vcg::Plane3<ScalarType> plane;
2010  vcg::FitPlaneToPointSet(pointVec, plane);
2011  float avgDot = 0;
2012  for (auto nvp : nearVertex)
2013  avgDot += plane.Direction().dot(nvp->N());
2014  avgDot /= nearVertex.size();
2015  typename MeshType::VertexType::NormalType normal;
2016  if (avgDot < 0)
2017  normal = -plane.Direction();
2018  else
2019  normal = plane.Direction();
2020  if (normal.dot(f->N()) < cosThreshold)
2021  f->SetS();
2022  }
2023  }
2024  }
2029  static int SelectIntersectingFaces(MeshType &m1, MeshType &m2)
2030  {
2031  RequirePerFaceMark(m2);
2032  RequireCompactness(m1);
2033  RequireCompactness(m2);
2034 
2036 
2037  TriMeshGrid gM;
2038  gM.Set(m2.face.begin(),m2.face.end());
2039  int selCnt=0;
2040  for(auto fi=m1.face.begin();fi!=m1.face.end();++fi)
2041  {
2042  Box3< ScalarType> bbox;
2043  (*fi).GetBBox(bbox);
2044  std::vector<FaceType*> inBox;
2045  vcg::tri::GetInBoxFace(m2, gM, bbox,inBox);
2046  for(auto fib=inBox.begin(); fib!=inBox.end(); ++fib)
2047  {
2049  fi->SetS();
2050  ++selCnt;
2051  }
2052  }
2053  inBox.clear();
2054  }
2055  return selCnt;
2056  }
2057 
2058 }; // end class
2061 } //End Namespace Tri
2062 } // End Namespace vcg
2063 #endif