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 
37 namespace vcg {
38 namespace tri{
39 
40 template <class ConnectedMeshType>
41 class ConnectedComponentIterator
42 {
43 public:
44  typedef ConnectedMeshType MeshType;
45  typedef typename MeshType::VertexType VertexType;
46  typedef typename MeshType::VertexPointer VertexPointer;
47  typedef typename MeshType::VertexIterator VertexIterator;
48  typedef typename MeshType::ScalarType ScalarType;
49  typedef typename MeshType::FaceType FaceType;
50  typedef typename MeshType::FacePointer FacePointer;
51  typedef typename MeshType::FaceIterator FaceIterator;
52  typedef typename MeshType::ConstFaceIterator ConstFaceIterator;
53  typedef typename MeshType::FaceContainer FaceContainer;
54 
55 public:
56  void operator ++()
57  {
58  FacePointer fpt=sf.top();
59  sf.pop();
60  for(int j=0; j<fpt->VN(); ++j)
61  if( !face::IsBorder(*fpt,j) )
62  {
63  FacePointer l=fpt->FFp(j);
64  if( !tri::IsMarked(*mp,l) )
65  {
66  tri::Mark(*mp,l);
67  sf.push(l);
68  }
69  }
70  }
71 
72  void start(MeshType &m, FacePointer p)
73  {
74  tri::RequirePerFaceMark(m);
75  mp=&m;
76  while(!sf.empty()) sf.pop();
77  UnMarkAll(m);
78  tri::Mark(m,p);
79  sf.push(p);
80  }
81 
82  bool completed() {
83  return sf.empty();
84  }
85 
86  FacePointer operator *()
87  {
88  return sf.top();
89  }
90 private:
91  std::stack<FacePointer> sf;
92  MeshType *mp;
93 };
94 
95 
97 
99 
100 template <class CleanMeshType>
101 class Clean
102 {
103 
104 public:
105  typedef CleanMeshType MeshType;
106  typedef typename MeshType::VertexType VertexType;
107  typedef typename MeshType::VertexPointer VertexPointer;
108  typedef typename MeshType::VertexIterator VertexIterator;
109  typedef typename MeshType::ConstVertexIterator ConstVertexIterator;
110  typedef typename MeshType::EdgeIterator EdgeIterator;
111  typedef typename MeshType::EdgePointer EdgePointer;
112  typedef typename MeshType::CoordType CoordType;
113  typedef typename MeshType::ScalarType ScalarType;
114  typedef typename MeshType::FaceType FaceType;
115  typedef typename MeshType::FacePointer FacePointer;
116  typedef typename MeshType::FaceIterator FaceIterator;
117  typedef typename MeshType::ConstFaceIterator ConstFaceIterator;
118  typedef typename MeshType::FaceContainer FaceContainer;
119  typedef typename MeshType::TetraType TetraType;
120  typedef typename MeshType::TetraPointer TetraPointer;
121  typedef typename MeshType::TetraIterator TetraIterator;
122  typedef typename MeshType::ConstTetraIterator ConstTetraIterator;
123 
124  typedef typename vcg::Box3<ScalarType> Box3Type;
125 
126  typedef GridStaticPtr<FaceType, ScalarType > TriMeshGrid;
127 
128  /* classe di confronto per l'algoritmo di eliminazione vertici duplicati*/
129  class RemoveDuplicateVert_Compare{
130  public:
131  inline bool operator()(VertexPointer const &a, VertexPointer const &b)
132  {
133  return ((*a).cP() == (*b).cP()) ? (a<b): ((*a).cP() < (*b).cP());
134  }
135  };
136 
137 
142  static int RemoveDuplicateVertex( MeshType & m, bool RemoveDegenerateFlag=true) // V1.0
143  {
144  if(m.vert.size()==0 || m.vn==0) return 0;
145 
146  std::map<VertexPointer, VertexPointer> mp;
147  size_t i,j;
148  VertexIterator vi;
149  int deleted=0;
150  int k=0;
151  size_t num_vert = m.vert.size();
152  std::vector<VertexPointer> perm(num_vert);
153  for(vi=m.vert.begin(); vi!=m.vert.end(); ++vi, ++k)
154  perm[k] = &(*vi);
155 
156  RemoveDuplicateVert_Compare c_obj;
157 
158  std::sort(perm.begin(),perm.end(),c_obj);
159 
160  j = 0;
161  i = j;
162  mp[perm[i]] = perm[j];
163  ++i;
164  for(;i!=num_vert;)
165  {
166  if( (! (*perm[i]).IsD()) &&
167  (! (*perm[j]).IsD()) &&
168  (*perm[i]).P() == (*perm[j]).cP() )
169  {
170  VertexPointer t = perm[i];
171  mp[perm[i]] = perm[j];
172  ++i;
174  deleted++;
175  }
176  else
177  {
178  j = i;
179  ++i;
180  }
181  }
182 
183  for(FaceIterator fi = m.face.begin(); fi!=m.face.end(); ++fi)
184  if( !(*fi).IsD() )
185  for(k = 0; k < (*fi).VN(); ++k)
186  if( mp.find( (typename MeshType::VertexPointer)(*fi).V(k) ) != mp.end() )
187  {
188  (*fi).V(k) = &*mp[ (*fi).V(k) ];
189  }
190 
191 
192  for(EdgeIterator ei = m.edge.begin(); ei!=m.edge.end(); ++ei)
193  if( !(*ei).IsD() )
194  for(k = 0; k < 2; ++k)
195  if( mp.find( (typename MeshType::VertexPointer)(*ei).V(k) ) != mp.end() )
196  {
197  (*ei).V(k) = &*mp[ (*ei).V(k) ];
198  }
199 
200  for (TetraIterator ti = m.tetra.begin(); ti != m.tetra.end(); ++ti)
201  if (!(*ti).IsD())
202  for (k = 0; k < 4; ++k)
203  if (mp.find((typename MeshType::VertexPointer)(*ti).V(k)) != mp.end())
204  (*ti).V(k) = &*mp[ (*ti).V(k) ];
205 
206  if(RemoveDegenerateFlag) RemoveDegenerateFace(m);
207  if(RemoveDegenerateFlag && m.en>0) {
208  RemoveDegenerateEdge(m);
210  }
211  return deleted;
212  }
213 
214  class SortedPair
215  {
216  public:
217  SortedPair() {}
218  SortedPair(unsigned int v0, unsigned int v1, EdgePointer _fp)
219  {
220  v[0]=v0;v[1]=v1;
221  fp=_fp;
222  if(v[0]>v[1]) std::swap(v[0],v[1]);
223  }
224  bool operator < (const SortedPair &p) const
225  {
226  return (v[1]!=p.v[1])?(v[1]<p.v[1]):
227  (v[0]<p.v[0]); }
228 
229  bool operator == (const SortedPair &s) const
230  {
231  if( (v[0]==s.v[0]) && (v[1]==s.v[1]) ) return true;
232  return false;
233  }
234 
235  unsigned int v[2];
236  EdgePointer fp;
237  };
238  class SortedTriple
239  {
240  public:
241  SortedTriple() {}
242  SortedTriple(unsigned int v0, unsigned int v1, unsigned int v2,FacePointer _fp)
243  {
244  v[0]=v0;v[1]=v1;v[2]=v2;
245  fp=_fp;
246  std::sort(v,v+3);
247  }
248  bool operator < (const SortedTriple &p) const
249  {
250  return (v[2]!=p.v[2])?(v[2]<p.v[2]):
251  (v[1]!=p.v[1])?(v[1]<p.v[1]):
252  (v[0]<p.v[0]); }
253 
254  bool operator == (const SortedTriple &s) const
255  {
256  if( (v[0]==s.v[0]) && (v[1]==s.v[1]) && (v[2]==s.v[2]) ) return true;
257  return false;
258  }
259 
260  unsigned int v[3];
261  FacePointer fp;
262  };
263 
264 
270  static int RemoveDuplicateFace( MeshType & m) // V1.0
271  {
272  std::vector<SortedTriple> fvec;
273  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
274  if(!(*fi).IsD())
275  {
276  fvec.push_back(SortedTriple( tri::Index(m,(*fi).V(0)),
277  tri::Index(m,(*fi).V(1)),
278  tri::Index(m,(*fi).V(2)),
279  &*fi));
280  }
281  std::sort(fvec.begin(),fvec.end());
282  int total=0;
283  for(int i=0;i<int(fvec.size())-1;++i)
284  {
285  if(fvec[i]==fvec[i+1])
286  {
287  total++;
288  tri::Allocator<MeshType>::DeleteFace(m, *(fvec[i].fp) );
289  }
290  }
291  return total;
292  }
293 
299  static int RemoveDuplicateEdge( MeshType & m) // V1.0
300  {
301  if (m.en==0) return 0;
302  std::vector<SortedPair> eVec;
303  for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
304  if(!(*ei).IsD())
305  {
306  eVec.push_back(SortedPair( tri::Index(m,(*ei).V(0)), tri::Index(m,(*ei).V(1)), &*ei));
307  }
308  std::sort(eVec.begin(),eVec.end());
309  int total=0;
310  for(int i=0;i<int(eVec.size())-1;++i)
311  {
312  if(eVec[i]==eVec[i+1])
313  {
314  total++;
315  tri::Allocator<MeshType>::DeleteEdge(m, *(eVec[i].fp) );
316  }
317  }
318  return total;
319  }
320 
321  static int CountUnreferencedVertex( MeshType& m)
322  {
323  return RemoveUnreferencedVertex(m,false);
324  }
325 
326 
332  static int RemoveUnreferencedVertex( MeshType& m, bool DeleteVertexFlag=true) // V1.0
333  {
334  tri::RequirePerVertexFlags(m);
335 
336  std::vector<bool> referredVec(m.vert.size(),false);
337  int deleted = 0;
338 
339  for(auto fi=m.face.begin();fi!=m.face.end();++fi)
340  if( !(*fi).IsD() )
341  for(auto j=0;j<(*fi).VN();++j)
342  referredVec[tri::Index(m,(*fi).V(j))]=true;
343 
344  for(auto ei=m.edge.begin();ei!=m.edge.end();++ei)
345  if( !(*ei).IsD() ){
346  referredVec[tri::Index(m,(*ei).V(0))]=true;
347  referredVec[tri::Index(m,(*ei).V(1))]=true;
348  }
349 
350  if(!DeleteVertexFlag)
351  return std::count(referredVec.begin(),referredVec.end(),true);
352 
353  for(auto vi=m.vert.begin();vi!=m.vert.end();++vi)
354  if( (!(*vi).IsD()) && (!referredVec[tri::Index(m,*vi)]) )
355  {
357  ++deleted;
358  }
359  return deleted;
360  }
361 
366  static int RemoveDegenerateVertex(MeshType& m)
367  {
368  VertexIterator vi;
369  int count_vd = 0;
370 
371  for(vi=m.vert.begin(); vi!=m.vert.end();++vi)
372  if(math::IsNAN( (*vi).P()[0]) ||
373  math::IsNAN( (*vi).P()[1]) ||
374  math::IsNAN( (*vi).P()[2]) )
375  {
376  count_vd++;
378  }
379 
380  FaceIterator fi;
381  int count_fd = 0;
382 
383  for(fi=m.face.begin(); fi!=m.face.end();++fi)
384  if(!(*fi).IsD())
385  if( (*fi).V(0)->IsD() ||
386  (*fi).V(1)->IsD() ||
387  (*fi).V(2)->IsD() )
388  {
389  count_fd++;
391  }
392  return count_vd;
393  }
394 
403  static int RemoveDegenerateFace(MeshType& m)
404  {
405  int count_fd = 0;
406 
407  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi)
408  if(!(*fi).IsD())
409  {
410  if((*fi).V(0) == (*fi).V(1) ||
411  (*fi).V(0) == (*fi).V(2) ||
412  (*fi).V(1) == (*fi).V(2) )
413  {
414  count_fd++;
416  }
417  }
418  return count_fd;
419  }
420 
421  static int RemoveDegenerateEdge(MeshType& m)
422  {
423  int count_ed = 0;
424 
425  for(EdgeIterator ei=m.edge.begin(); ei!=m.edge.end();++ei)
426  if(!(*ei).IsD())
427  {
428  if((*ei).V(0) == (*ei).V(1) )
429  {
430  count_ed++;
432  }
433  }
434  return count_ed;
435  }
436 
437  static int RemoveNonManifoldVertex(MeshType& m)
438  {
439  CountNonManifoldVertexFF(m,true);
441  int count_removed = 0;
442  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi)
443  if(!(*fi).IsD() && (*fi).IsS())
444  Allocator<MeshType>::DeleteFace(m,*fi);
445  for(VertexIterator vi=m.vert.begin(); vi!=m.vert.end();++vi)
446  if(!(*vi).IsD() && (*vi).IsS()) {
447  ++count_removed;
449  }
450  return count_removed;
451  }
452 
453 
454  static int SplitSelectedVertexOnEdgeMesh(MeshType& m)
455  {
456  tri::RequireCompactness(m);
457 
458  // count selected vertices references
459  std::unordered_map<size_t,size_t> refCount; // selected vertex index -> reference count
460  size_t countSplit = 0;
461  for (size_t i=0; i<m.edge.size(); ++i)
462  {
463  for (int j=0; j<2; ++j)
464  {
465  const VertexPointer vp = m.edge[i].V(j);
466  if (vp->IsS())
467  {
468  const size_t refs = ++refCount[Index(m, m.edge[i].V(j))];
469  if (refs > 1) {
470  countSplit++;
471  }
472  }
473  }
474  }
475  // actual split
476  if (countSplit > 0)
477  {
478  auto newVertIt = tri::Allocator<MeshType>::AddVertices(m, countSplit);
479  for (size_t i=0; i<m.edge.size(); ++i)
480  {
481  for (int j=0; j<2; ++j)
482  {
483  const VertexPointer vp = m.edge[i].V(j);
484  const size_t vIdx = Index(m, vp);
485  if (vp->IsS())
486  {
487  if (--refCount[vIdx] > 0)
488  {
489  newVertIt->ImportData(*vp);
490  m.edge[i].V(j) = &*(newVertIt++);
491  }
492  }
493  }
494  }
495  }
496  return int(countSplit);
497  }
498 
499 
500  static void SelectNonManifoldVertexOnEdgeMesh(MeshType &m)
501  {
502  tri::RequireCompactness(m);
504  std::vector<int> cnt(m.vn,0);
505 
506  for(size_t i=0;i<m.edge.size();++i)
507  {
508  cnt[tri::Index(m,m.edge[i].V(0))]++;
509  cnt[tri::Index(m,m.edge[i].V(1))]++;
510  }
511  for(size_t i=0;i<m.vert.size();++i)
512  if(cnt[i]>2) m.vert[i].SetS();
513  }
514 
515  static void SelectCreaseVertexOnEdgeMesh(MeshType &m, ScalarType AngleRadThr)
516  {
517  tri::RequireCompactness(m);
518  tri::RequireVEAdjacency(m);
519  tri::UpdateTopology<MeshType>::VertexEdge(m);
521  for(size_t i=0;i<m.vert.size();++i)
522  {
523  std::vector<VertexPointer> VVStarVec;
524  edge::VVStarVE(&(m.vert[i]),VVStarVec);
525  if(VVStarVec.size()==2)
526  {
527  CoordType v0 = m.vert[i].P() - VVStarVec[0]->P();
528  CoordType v1 = m.vert[i].P() - VVStarVec[1]->P();
529  float angle = M_PI-vcg::Angle(v0,v1);
530  if(angle > AngleRadThr) m.vert[i].SetS();
531  }
532  }
533  }
534 
535 
537 
538  // Given a mesh with FF adjacency
539  // it search for non manifold vertices and duplicate them.
540  // Duplicated vertices are moved apart according to the move threshold param.
541  // that is a percentage of the average vector from the non manifold vertex to the barycenter of the incident faces.
542 
543  static int SplitNonManifoldVertex(MeshType& m, ScalarType moveThreshold)
544  {
545  RequireFFAdjacency(m);
546  typedef std::pair<FacePointer,int> FaceInt; // a face and the index of the vertex that we have to change
547  //
548  std::vector<std::pair<VertexPointer, std::vector<FaceInt> > >ToSplitVec;
549 
551  ss.push();
552  CountNonManifoldVertexFF(m,true);
554  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
555  {
556  for (int i=0; i<fi->VN(); i++)
557  if ((*fi).V(i)->IsS() && !(*fi).V(i)->IsV())
558  {
559  (*fi).V(i)->SetV();
560  face::Pos<FaceType> startPos(&*fi,i);
561  face::Pos<FaceType> curPos = startPos;
562  std::set<FaceInt> faceSet;
563  do
564  {
565  faceSet.insert(std::make_pair(curPos.F(),curPos.VInd()));
566  curPos.NextE();
567  } while (curPos != startPos);
568 
569  ToSplitVec.push_back(make_pair((*fi).V(i),std::vector<FaceInt>()));
570 
571  typename std::set<FaceInt>::const_iterator iii;
572 
573  for(iii=faceSet.begin();iii!=faceSet.end();++iii)
574  ToSplitVec.back().second.push_back(*iii);
575  }
576  }
577  ss.pop();
578  // Second step actually add new vertices and split them.
579  typename tri::Allocator<MeshType>::template PointerUpdater<VertexPointer> pu;
580  VertexIterator firstVp = tri::Allocator<MeshType>::AddVertices(m,ToSplitVec.size(),pu);
581  for(size_t i =0;i<ToSplitVec.size();++i)
582  {
583  // qDebug("Splitting Vertex %i",ToSplitVec[i].first-&*m.vert.begin());
584  VertexPointer np=ToSplitVec[i].first;
585  pu.Update(np);
586  firstVp->ImportData(*np);
587  // loop on the face to be changed, and also compute the movement vector;
588  CoordType delta(0,0,0);
589  for(size_t j=0;j<ToSplitVec[i].second.size();++j)
590  {
591  FaceInt ff=ToSplitVec[i].second[j];
592  ff.first->V(ff.second)=&*firstVp;
593  delta+=Barycenter(*(ff.first))-np->cP();
594  }
595  delta /= ToSplitVec[i].second.size();
596  firstVp->P() = firstVp->P() + delta * moveThreshold;
597  firstVp++;
598  }
599 
600  return int(ToSplitVec.size());
601  }
602 
603 
604  // Auxiliary function for sorting the non manifold faces according to their area. Used in RemoveNonManifoldFace
605  struct CompareAreaFP {
606  bool operator ()(FacePointer const& f1, FacePointer const& f2) const {
607  return DoubleArea(*f1) < DoubleArea(*f2);
608  }
609  };
610 
612  static int RemoveNonManifoldFace(MeshType& m)
613  {
614  FaceIterator fi;
615  int count_fd = 0;
616  std::vector<FacePointer> ToDelVec;
617 
618  for(fi=m.face.begin(); fi!=m.face.end();++fi)
619  if (!fi->IsD())
620  {
621  if ((!IsManifold(*fi,0))||
622  (!IsManifold(*fi,1))||
623  (!IsManifold(*fi,2)))
624  ToDelVec.push_back(&*fi);
625  }
626 
627  std::sort(ToDelVec.begin(),ToDelVec.end(),CompareAreaFP());
628 
629  for(size_t i=0;i<ToDelVec.size();++i)
630  {
631  if(!ToDelVec[i]->IsD())
632  {
633  FaceType &ff= *ToDelVec[i];
634  if ((!IsManifold(ff,0))||
635  (!IsManifold(ff,1))||
636  (!IsManifold(ff,2)))
637  {
638  for(int j=0;j<3;++j)
639  if(!face::IsBorder<FaceType>(ff,j))
640  vcg::face::FFDetach<FaceType>(ff,j);
641 
643  count_fd++;
644  }
645  }
646  }
647  return count_fd;
648  }
649 
650  /* Remove the faces that are out of a given range of area */
651  static int RemoveFaceOutOfRangeArea(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)(), bool OnlyOnSelected=false)
652  {
653  int count_fd = 0;
654  MinAreaThr*=2;
655  MaxAreaThr*=2;
656  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi){
657  if(!(*fi).IsD())
658  if(!OnlyOnSelected || (*fi).IsS())
659  {
660  const ScalarType doubleArea=DoubleArea<FaceType>(*fi);
661  if((doubleArea<=MinAreaThr) || (doubleArea>=MaxAreaThr) )
662  {
664  count_fd++;
665  }
666  }
667  }
668  return count_fd;
669  }
670 
671  static int RemoveZeroAreaFace(MeshType& m) { return RemoveFaceOutOfRangeArea(m,0);}
672 
673 
674 
678  static bool IsBitQuadOnly(const MeshType &m)
679  {
680  typedef typename MeshType::FaceType F;
681  tri::RequirePerFaceFlags(m);
682  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
683  unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
684  if ( tmp != F::FAUX0 && tmp != F::FAUX1 && tmp != F::FAUX2) return false;
685  }
686  return true;
687  }
688 
689 
690  static bool IsFaceFauxConsistent(MeshType &m)
691  {
692  RequirePerFaceFlags(m);
693  RequireFFAdjacency(m);
694  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
695  {
696  for(int z=0;z<(*fi).VN();++z)
697  {
698  FacePointer fp = fi->FFp(z);
699  int zp = fi->FFi(z);
700  if(fi->IsF(z) != fp->IsF(zp)) return false;
701  }
702  }
703  return true;
704  }
705 
709  static bool IsBitTriOnly(const MeshType &m)
710  {
711  tri::RequirePerFaceFlags(m);
712  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) {
713  if ( !fi->IsD() && fi->IsAnyF() ) return false;
714  }
715  return true;
716  }
717 
718  static bool IsBitPolygonal(const MeshType &m){
719  return !IsBitTriOnly(m);
720  }
721 
726  static bool IsBitTriQuadOnly(const MeshType &m)
727  {
728  tri::RequirePerFaceFlags(m);
729  typedef typename MeshType::FaceType F;
730  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
731  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
732  if ( tmp!=F::FAUX0 && tmp!=F::FAUX1 && tmp!=F::FAUX2 && tmp!=0 ) return false;
733  }
734  return true;
735  }
736 
741  static int CountBitQuads(const MeshType &m)
742  {
743  tri::RequirePerFaceFlags(m);
744  typedef typename MeshType::FaceType F;
745  int count=0;
746  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
747  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
748  if ( tmp==F::FAUX0 || tmp==F::FAUX1 || tmp==F::FAUX2) count++;
749  }
750  return count / 2;
751  }
752 
756  static int CountBitTris(const MeshType &m)
757  {
758  tri::RequirePerFaceFlags(m);
759  int count=0;
760  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
761  if (!(fi->IsAnyF())) count++;
762  }
763  return count;
764  }
765 
770  static int CountBitPolygons(const MeshType &m)
771  {
772  tri::RequirePerFaceFlags(m);
773  int count = 0;
774  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
775  if (fi->IsF(0)) count++;
776  if (fi->IsF(1)) count++;
777  if (fi->IsF(2)) count++;
778  }
779  return m.fn - count/2;
780  }
781 
793  static int CountBitLargePolygons(MeshType &m)
794  {
795  tri::RequirePerFaceFlags(m);
797  // First loop Clear all referenced vertices
798  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
799  if (!fi->IsD())
800  for(int i=0;i<3;++i) fi->V(i)->ClearV();
801 
802 
803  // Second Loop, count (twice) faux edges and mark all vertices touched by non faux edges
804  // (e.g vertexes on the boundary of a polygon)
805  int countE = 0;
806  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
807  if (!fi->IsD()) {
808  for(int i=0;i<3;++i)
809  {
810  if (fi->IsF(i))
811  countE++;
812  else
813  {
814  fi->V0(i)->SetV();
815  fi->V1(i)->SetV();
816  }
817  }
818  }
819  // Third Loop, count the number of referenced vertexes that are completely surrounded by faux edges.
820 
821  int countV = 0;
822  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
823  if (!vi->IsD() && !vi->IsV()) countV++;
824 
825  return m.fn - countE/2 + countV ;
826  }
827 
828 
836  static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
837  {
838  RequireFFAdjacency(m);
839  RequirePerFaceFlags(m);
840 
841  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
842  if(!(*fi).IsD())
843  for (int k=0; k<3; k++)
844  if( ( fi->IsF(k) != fi->cFFp(k)->IsF(fi->cFFi(k)) ) ||
845  ( fi->IsF(k) && face::IsBorder(*fi,k)) )
846  {
847  return false;
848  }
849  return true;
850  }
851 
856  static int CountNonManifoldEdgeEE( MeshType & m, bool SelectFlag=false)
857  {
858  MeshAssert<MeshType>::OnlyEdgeMesh(m);
859  RequireEEAdjacency(m);
861 
862  if(SelectFlag) UpdateSelection<MeshType>::VertexClear(m);
863 
864  int nonManifoldCnt=0;
865  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
866 
867  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
868  EdgeIterator ei;
869  for (ei = m.edge.begin(); ei != m.edge.end(); ++ei) if (!ei->IsD())
870  {
871  TD[(*ei).V(0)]++;
872  TD[(*ei).V(1)]++;
873  }
874 
876  // Second Loop, Check that each vertex have been seen 1 or 2 times.
877  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if (!vi->IsD())
878  {
879  if( TD[vi] >2 )
880  {
881  if(SelectFlag) (*vi).SetS();
882  nonManifoldCnt++;
883  }
884  }
885  return nonManifoldCnt;
886  }
887 
894  static int CountNonManifoldEdgeFF( MeshType & m, bool SelectFlag=false)
895  {
896  RequireFFAdjacency(m);
897  int nmfBit[3];
898  nmfBit[0]= FaceType::NewBitFlag();
899  nmfBit[1]= FaceType::NewBitFlag();
900  nmfBit[2]= FaceType::NewBitFlag();
901 
902 
903  UpdateFlags<MeshType>::FaceClear(m,nmfBit[0]+nmfBit[1]+nmfBit[2]);
904 
905  if(SelectFlag){
908  }
909 
910  int edgeCnt = 0;
911  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
912  {
913  if (!fi->IsD())
914  {
915  for(int i=0;i<3;++i)
916  if(!IsManifold(*fi,i))
917  {
918  if(!(*fi).IsUserBit(nmfBit[i]))
919  {
920  ++edgeCnt;
921  if(SelectFlag)
922  {
923  (*fi).V0(i)->SetS();
924  (*fi).V1(i)->SetS();
925  }
926  // follow the ring of faces incident on edge i;
927  face::Pos<FaceType> nmf(&*fi,i);
928  do
929  {
930  if(SelectFlag) nmf.F()->SetS();
931  nmf.F()->SetUserBit(nmfBit[nmf.E()]);
932  nmf.NextF();
933  }
934  while(nmf.f != &*fi);
935  }
936  }
937  }
938  }
939  return edgeCnt;
940  }
941 
946  static int CountNonManifoldVertexFF( MeshType & m, bool selectVert = true )
947  {
948  RequireFFAdjacency(m);
949  if(selectVert) UpdateSelection<MeshType>::VertexClear(m);
950 
951  int nonManifoldCnt=0;
952  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
953 
954  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
955  FaceIterator fi;
956  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
957  {
958  for (int k=0; k<fi->VN(); k++)
959  {
960  TD[(*fi).V(k)]++;
961  }
962  }
963 
965  // Second Loop.
966  // mark out of the game the vertexes that are incident on non manifold edges.
967  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
968  {
969  for(int i=0; i<fi->VN(); ++i)
970  if (!IsManifold(*fi,i))
971  {
972  (*fi).V0(i)->SetV();
973  (*fi).V1(i)->SetV();
974  }
975  }
976  // Third Loop, for safe vertexes, check that the number of faces that you can reach starting
977  // from it and using FF is the same of the previously counted.
978  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
979  {
980  for(int i=0; i<fi->VN(); i++) if (!(*fi).V(i)->IsV())
981  {
982  (*fi).V(i)->SetV();
983  face::Pos<FaceType> pos(&(*fi),i);
984 
985  int starSizeFF = pos.NumberOfIncidentFaces();
986 
987  if (starSizeFF != TD[(*fi).V(i)])
988  {
989  if (selectVert)
990  (*fi).V(i)->SetS();
991  nonManifoldCnt++;
992  }
993  }
994  }
995  return nonManifoldCnt;
996  }
1004  static bool IsWaterTight(MeshType & m)
1005  {
1006  int edgeNum=0,edgeBorderNum=0,edgeNonManifNum=0;
1007  CountEdgeNum(m, edgeNum, edgeBorderNum,edgeNonManifNum);
1008  return (edgeBorderNum==0) && (edgeNonManifNum==0);
1009  }
1010 
1011  static void CountEdgeNum( MeshType & m, int &total_e, int &boundary_e, int &non_manif_e )
1012  {
1013  std::vector< typename tri::UpdateTopology<MeshType>::PEdge > edgeVec;
1015  sort(edgeVec.begin(), edgeVec.end()); // Lo ordino per vertici
1016  total_e=0;
1017  boundary_e=0;
1018  non_manif_e=0;
1019 
1020  size_t f_on_cur_edge =1;
1021  for(size_t i=0;i<edgeVec.size();++i)
1022  {
1023  if(( (i+1) == edgeVec.size()) || !(edgeVec[i] == edgeVec[i+1]))
1024  {
1025  ++total_e;
1026  if(f_on_cur_edge==1)
1027  ++boundary_e;
1028  if(f_on_cur_edge>2)
1029  ++non_manif_e;
1030  f_on_cur_edge=1;
1031  }
1032  else
1033  {
1034  ++f_on_cur_edge;
1035  }
1036  } // end for
1037  }
1038 
1039 
1040 
1041  static int CountHoles( MeshType & m)
1042  {
1043  UpdateFlags<MeshType>::FaceClearV(m);
1044  int loopNum=0;
1045  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD())
1046  {
1047  for(int j=0;j<3;++j)
1048  {
1049  if(!fi->IsV() && face::IsBorder(*fi,j))
1050  {
1051  face::Pos<FaceType> startPos(&*fi,j);
1052  face::Pos<FaceType> curPos=startPos;
1053  do
1054  {
1055  curPos.NextB();
1056  curPos.F()->SetV();
1057  }
1058  while(curPos!=startPos);
1059  ++loopNum;
1060  }
1061  }
1062  }
1063  return loopNum;
1064  }
1065 
1066  /*
1067  Compute the set of connected components of a given mesh
1068  it fills a vector of pair < int , faceptr > with, for each connecteed component its size and a represnant
1069  */
1070  static int CountConnectedComponents(MeshType &m)
1071  {
1072  std::vector< std::pair<int,FacePointer> > CCV;
1073  return ConnectedComponents(m,CCV);
1074  }
1075 
1076  static int ConnectedComponents(MeshType &m, std::vector< std::pair<int,FacePointer> > &CCV)
1077  {
1078  tri::RequireFFAdjacency(m);
1079  CCV.clear();
1080  tri::UpdateFlags<MeshType>::FaceClearV(m);
1081  std::stack<FacePointer> sf;
1082  FacePointer fpt=&*(m.face.begin());
1083  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1084  {
1085  if(!((*fi).IsD()) && !(*fi).IsV())
1086  {
1087  (*fi).SetV();
1088  CCV.push_back(std::make_pair(0,&*fi));
1089  sf.push(&*fi);
1090  while (!sf.empty())
1091  {
1092  fpt=sf.top();
1093  ++CCV.back().first;
1094  sf.pop();
1095  for(int j=0; j<fpt->VN(); ++j)
1096  {
1097  if( !face::IsBorder(*fpt,j) )
1098  {
1099  FacePointer l = fpt->FFp(j);
1100  if( !(*l).IsV() )
1101  {
1102  (*l).SetV();
1103  sf.push(l);
1104  }
1105  }
1106  }
1107  }
1108  }
1109  }
1110  return int(CCV.size());
1111  }
1112 
1113  static void ComputeValence( MeshType &m, typename MeshType::PerVertexIntHandle &h)
1114  {
1115  for(VertexIterator vi=m.vert.begin(); vi!= m.vert.end();++vi)
1116  h[vi]=0;
1117 
1118  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1119  {
1120  if(!((*fi).IsD()))
1121  for(int j=0;j<fi->VN();j++)
1122  ++h[tri::Index(m,fi->V(j))];
1123  }
1124  }
1125 
1161  static int MeshGenus(int nvert,int nedges,int nfaces, int numholes, int numcomponents)
1162  {
1163  return -((nvert + nfaces - nedges + numholes - 2 * numcomponents) / 2);
1164  }
1165 
1166  static int MeshGenus(MeshType &m)
1167  {
1168  int nvert=m.vn;
1169  int nfaces=m.fn;
1170  int boundary_e,total_e,nonmanif_e;
1171  CountEdgeNum(m,total_e,boundary_e,nonmanif_e);
1172  int numholes=CountHoles(m);
1173  int numcomponents=CountConnectedComponents(m);
1174  int G=MeshGenus(nvert,total_e,nfaces,numholes,numcomponents);
1175  return G;
1176  }
1177 
1189  static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular)
1190  {
1191  RequireVFAdjacency(m);
1192  Regular = true;
1193 
1194  VertexIterator vi;
1195 
1196  // for each vertex the number of edges are count
1197  for (vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1198  {
1199  if (!vi->IsD())
1200  {
1201  face::Pos<FaceType> he((*vi).VFp(), &*vi);
1202  face::Pos<FaceType> ht = he;
1203 
1204  int n=0;
1205  bool border=false;
1206  do
1207  {
1208  ++n;
1209  ht.NextE();
1210  if (ht.IsBorder())
1211  border=true;
1212  }
1213  while (ht != he);
1214 
1215  if (border)
1216  n = n/2;
1217 
1218  if ((n != 6)&&(!border && n != 4))
1219  {
1220  Regular = false;
1221  break;
1222  }
1223  }
1224  }
1225 
1226  if (!Regular)
1227  Semiregular = false;
1228  else
1229  {
1230  // For now we do not account for semi-regularity
1231  Semiregular = false;
1232  }
1233  }
1234 
1235 
1236  static bool IsCoherentlyOrientedMesh(MeshType &m)
1237  {
1238  RequireFFAdjacency(m);
1239  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1240  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1241  if (!fi->IsD())
1242  for(int i=0;i<3;++i)
1243  if(!face::CheckOrientation(*fi,i))
1244  return false;
1245 
1246  return true;
1247  }
1248 
1249  static void OrientCoherentlyMesh(MeshType &m, bool &_IsOriented, bool &_IsOrientable)
1250  {
1251  RequireFFAdjacency(m);
1252  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1253  bool IsOrientable = true;
1254  bool IsOriented = true;
1255 
1256  UpdateFlags<MeshType>::FaceClearV(m);
1257  std::stack<FacePointer> faces;
1258  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1259  {
1260  if (!fi->IsD() && !fi->IsV())
1261  {
1262  // each face put in the stack is selected (and oriented)
1263  fi->SetV();
1264  faces.push(&(*fi));
1265  while (!faces.empty())
1266  {
1267  FacePointer fp = faces.top();
1268  faces.pop();
1269 
1270  // make consistently oriented the adjacent faces
1271  for (int j = 0; j < 3; j++)
1272  {
1273  if (!face::IsBorder(*fp,j) && face::IsManifold<FaceType>(*fp, j))
1274  {
1275  FacePointer fpaux = fp->FFp(j);
1276  int iaux = fp->FFi(j);
1277  if (!CheckOrientation(*fpaux, iaux))
1278  {
1279  IsOriented = false;
1280 
1281  if (!fpaux->IsV())
1282  face::SwapEdge<FaceType,true>(*fpaux, iaux);
1283  else
1284  {
1285  IsOrientable = false;
1286  break;
1287  }
1288  }
1289  if (!fpaux->IsV())
1290  {
1291  fpaux->SetV();
1292  faces.push(fpaux);
1293  }
1294  }
1295  }
1296  }
1297  }
1298  if (!IsOrientable) break;
1299  }
1300  _IsOriented = IsOriented;
1301  _IsOrientable = IsOrientable;
1302  }
1303 
1304 
1306  static void FlipMesh(MeshType &m, bool selected=false)
1307  {
1308  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if(!(*fi).IsD())
1309  if(!selected || (*fi).IsS())
1310  {
1311  face::SwapEdge<FaceType,false>((*fi), 0);
1312  if (HasPerWedgeTexCoord(m))
1313  std::swap((*fi).WT(0),(*fi).WT(1));
1314  }
1315  }
1321  static bool FlipNormalOutside(MeshType &m)
1322  {
1323  if(m.vert.empty()) return false;
1324 
1327 
1328  std::vector< VertexPointer > minVertVec;
1329  std::vector< VertexPointer > maxVertVec;
1330 
1331  // The set of directions to be choosen
1332  std::vector< CoordType > dirVec;
1333  dirVec.push_back(CoordType(1,0,0));
1334  dirVec.push_back(CoordType(0,1,0));
1335  dirVec.push_back(CoordType(0,0,1));
1336  dirVec.push_back(CoordType( 1, 1,1));
1337  dirVec.push_back(CoordType(-1, 1,1));
1338  dirVec.push_back(CoordType(-1,-1,1));
1339  dirVec.push_back(CoordType( 1,-1,1));
1340  for(size_t i=0;i<dirVec.size();++i)
1341  {
1342  Normalize(dirVec[i]);
1343  minVertVec.push_back(&*m.vert.begin());
1344  maxVertVec.push_back(&*m.vert.begin());
1345  }
1346  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if(!(*vi).IsD())
1347  {
1348  for(size_t i=0;i<dirVec.size();++i)
1349  {
1350  if( (*vi).cP().dot(dirVec[i]) < minVertVec[i]->P().dot(dirVec[i])) minVertVec[i] = &*vi;
1351  if( (*vi).cP().dot(dirVec[i]) > maxVertVec[i]->P().dot(dirVec[i])) maxVertVec[i] = &*vi;
1352  }
1353  }
1354 
1355  int voteCount=0;
1356  ScalarType angleThreshold = cos(math::ToRad(85.0));
1357  for(size_t i=0;i<dirVec.size();++i)
1358  {
1359  // 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]);
1360  // 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]);
1361  if(minVertVec[i]->N().dot(dirVec[i]) > angleThreshold ) voteCount++;
1362  if(maxVertVec[i]->N().dot(dirVec[i]) < -angleThreshold ) voteCount++;
1363  }
1364  // qDebug("votecount = %i",voteCount);
1365  if(voteCount < int(dirVec.size())/2) return false;
1366  FlipMesh(m);
1367  return true;
1368  }
1369 
1370  // Search and remove small single triangle folds
1371  // - a face has normal opposite to all other faces
1372  // - choose the edge that brings to the face f1 containing the vertex opposite to that edge.
1373  static int RemoveFaceFoldByFlip(MeshType &m, float normalThresholdDeg=175, bool repeat=true)
1374  {
1375  RequireFFAdjacency(m);
1376  RequirePerVertexMark(m);
1377  //Counters for logging and convergence
1378  int count, total = 0;
1379 
1380  do {
1382  tri::UnMarkAll(m);
1383  count = 0;
1384 
1385  ScalarType NormalThrRad = math::ToRad(normalThresholdDeg);
1386  ScalarType eps = ScalarType(0.0001); // this epsilon value is in absolute value. It is a distance from edge in baricentric coords.
1387  //detection stage
1388  for(FaceIterator fi=m.face.begin();fi!= m.face.end();++fi ) if(!(*fi).IsV())
1389  { Point3<ScalarType> NN = vcg::TriangleNormal((*fi)).Normalize();
1390  if( vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(0)).Normalize()) > NormalThrRad &&
1391  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(1)).Normalize()) > NormalThrRad &&
1392  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(2)).Normalize()) > NormalThrRad )
1393  {
1394  (*fi).SetS();
1395  //(*fi).C()=Color4b(Color4b::Red);
1396  // now search the best edge to flip
1397  for(int i=0;i<3;i++)
1398  {
1399  Point3<ScalarType> &p=(*fi).P2(i);
1400  Point3<ScalarType> L;
1401  bool ret = vcg::InterpolationParameters((*(*fi).FFp(i)),TriangleNormal(*(*fi).FFp(i)),p,L);
1402  if(ret && L[0]>eps && L[1]>eps && L[2]>eps)
1403  {
1404  (*fi).FFp(i)->SetS();
1405  (*fi).FFp(i)->SetV();
1406  //(*fi).FFp(i)->C()=Color4b(Color4b::Green);
1407  if(face::CheckFlipEdge<FaceType>( *fi, i )) {
1408  face::FlipEdge<FaceType>( *fi, i );
1409  ++count; ++total;
1410  }
1411  }
1412  }
1413  }
1414  }
1415 
1416  // tri::UpdateNormal<MeshType>::PerFace(m);
1417  }
1418  while( repeat && count );
1419  return total;
1420  }
1421 
1422 
1423  static int RemoveTVertexByFlip(MeshType &m, float threshold=40, bool repeat=true)
1424  {
1425  RequireFFAdjacency(m);
1426  RequirePerVertexMark(m);
1427  //Counters for logging and convergence
1428  int count, total = 0;
1429 
1430  do {
1432  tri::UnMarkAll(m);
1433  count = 0;
1434 
1435  //detection stage
1436  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1437  {
1438  FacePointer f = &(m.face[index]); float sides[3]; CoordType dummy;
1439  sides[0] = Distance(f->P(0), f->P(1));
1440  sides[1] = Distance(f->P(1), f->P(2));
1441  sides[2] = Distance(f->P(2), f->P(0));
1442  // Find largest triangle side
1443  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1444  if( tri::IsMarked(m,f->V2(i) )) continue;
1445 
1446  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1447  {
1448  tri::Mark(m,f->V2(i));
1449  if(face::CheckFlipEdge<FaceType>( *f, i )) {
1450  // Check if EdgeFlipping improves quality
1451  FacePointer g = f->FFp(i); int k = f->FFi(i);
1452  Triangle3<ScalarType> t1(f->P(i), f->P1(i), f->P2(i)), t2(g->P(k), g->P1(k), g->P2(k)),
1453  t3(f->P(i), g->P2(k), f->P2(i)), t4(g->P(k), f->P2(i), g->P2(k));
1454 
1455  if ( std::min( QualityFace(t1), QualityFace(t2) ) < std::min( QualityFace(t3), QualityFace(t4) ))
1456  {
1457  face::FlipEdge<FaceType>( *f, i );
1458  ++count; ++total;
1459  }
1460  }
1461 
1462  }
1463  }
1464 
1465  // tri::UpdateNormal<MeshType>::PerFace(m);
1466  }
1467  while( repeat && count );
1468  return total;
1469  }
1470 
1471  static int RemoveTVertexByCollapse(MeshType &m, float threshold=40, bool repeat=true)
1472  {
1473  RequirePerVertexMark(m);
1474  //Counters for logging and convergence
1475  int count, total = 0;
1476 
1477  do {
1478  tri::UnMarkAll(m);
1479  count = 0;
1480 
1481  //detection stage
1482  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1483  {
1484  FacePointer f = &(m.face[index]);
1485  float sides[3];
1486  CoordType dummy;
1487 
1488  sides[0] = Distance(f->P(0), f->P(1));
1489  sides[1] = Distance(f->P(1), f->P(2));
1490  sides[2] = Distance(f->P(2), f->P(0));
1491  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1492  if( tri::IsMarked(m,f->V2(i) )) continue;
1493 
1494  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1495  {
1496  tri::Mark(m,f->V2(i));
1497 
1498  int j = Distance(dummy,f->P(i))<Distance(dummy,f->P1(i))?i:(i+1)%3;
1499  f->P2(i) = f->P(j); tri::Mark(m,f->V(j));
1500  ++count; ++total;
1501  }
1502  }
1503 
1504 
1508  }
1509  while( repeat && count );
1510 
1511  return total;
1512  }
1513 
1514  static bool SelfIntersections(MeshType &m, std::vector<FaceType*> &ret)
1515  {
1516  RequirePerFaceMark(m);
1517  ret.clear();
1518  int referredBit = FaceType::NewBitFlag();
1519  tri::UpdateFlags<MeshType>::FaceClear(m,referredBit);
1520 
1521  TriMeshGrid gM;
1522  gM.Set(m.face.begin(),m.face.end());
1523 
1524  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
1525  {
1526  (*fi).SetUserBit(referredBit);
1527  Box3< ScalarType> bbox;
1528  (*fi).GetBBox(bbox);
1529  std::vector<FaceType*> inBox;
1530  vcg::tri::GetInBoxFace(m, gM, bbox,inBox);
1531  bool Intersected=false;
1532  typename std::vector<FaceType*>::iterator fib;
1533  for(fib=inBox.begin();fib!=inBox.end();++fib)
1534  {
1535  if(!(*fib)->IsUserBit(referredBit) && (*fib != &*fi) )
1536  if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){
1537  ret.push_back(*fib);
1538  if(!Intersected) {
1539  ret.push_back(&*fi);
1540  Intersected=true;
1541  }
1542  }
1543  }
1544  inBox.clear();
1545  }
1546 
1547  FaceType::DeleteBitFlag(referredBit);
1548  return (ret.size()>0);
1549  }
1550 
1554  static bool IsSizeConsistent(MeshType &m)
1555  {
1556  int DeletedVertNum=0;
1557  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1558  if((*vi).IsD()) DeletedVertNum++;
1559 
1560  int DeletedEdgeNum=0;
1561  for (EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei)
1562  if((*ei).IsD()) DeletedEdgeNum++;
1563 
1564  int DeletedFaceNum=0;
1565  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1566  if((*fi).IsD()) DeletedFaceNum++;
1567 
1568  if(size_t(m.vn+DeletedVertNum) != m.vert.size()) return false;
1569  if(size_t(m.en+DeletedEdgeNum) != m.edge.size()) return false;
1570  if(size_t(m.fn+DeletedFaceNum) != m.face.size()) return false;
1571 
1572  return true;
1573  }
1574 
1579  static bool IsFFAdjacencyConsistent(MeshType &m)
1580  {
1581  RequireFFAdjacency(m);
1582 
1583  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1584  if(!(*fi).IsD())
1585  {
1586  for(int i=0;i<3;++i)
1587  if(!FFCorrectness(*fi, i)) return false;
1588  }
1589  return true;
1590  }
1591 
1595  static bool HasConsistentPerWedgeTexCoord(MeshType &m)
1596  {
1597  tri::RequirePerFaceWedgeTexCoord(m);
1598 
1599  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1600  if(!(*fi).IsD())
1601  { FaceType &f=(*fi);
1602  if( ! ( (f.WT(0).N() == f.WT(1).N()) && (f.WT(0).N() == (*fi).WT(2).N()) ) )
1603  return false; // all the vertices must have the same index.
1604 
1605  if((*fi).WT(0).N() <0) return false; // no undefined texture should be allowed
1606  }
1607  return true;
1608  }
1609 
1613  static bool HasZeroTexCoordFace(MeshType &m)
1614  {
1615  tri::RequirePerFaceWedgeTexCoord(m);
1616 
1617  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1618  if(!(*fi).IsD())
1619  {
1620  if( (*fi).WT(0).P() == (*fi).WT(1).P() && (*fi).WT(0).P() == (*fi).WT(2).P() ) return false;
1621  }
1622  return true;
1623  }
1624 
1625 
1633  static bool TestFaceFaceIntersection(FaceType *f0,FaceType *f1)
1634  {
1635  int sv = face::CountSharedVertex(f0,f1);
1636  if(sv==3) return true;
1637  if(sv==0) return (vcg::IntersectionTriangleTriangle<FaceType>((*f0),(*f1)));
1638  // if the faces share only a vertex, the opposite edge (as a segment) is tested against the face
1639  // to avoid degenerate cases where the two triangles have the opposite edge on a common plane
1640  // we offset the segment to test toward the shared vertex
1641  if(sv==1)
1642  {
1643  int i0,i1; ScalarType a,b;
1644  face::FindSharedVertex(f0,f1,i0,i1);
1645  CoordType shP = f0->V(i0)->P()*0.5;
1646  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f0).V1(i0)->P()*0.5+shP,(*f0).V2(i0)->P()*0.5+shP), *f1, a, b) )
1647  {
1648  // a,b are the param coords of the intersection point of the segment.
1649  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1650  return true;
1651  }
1652  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f1).V1(i1)->P()*0.5+shP,(*f1).V2(i1)->P()*0.5+shP), *f0, a, b) )
1653  {
1654  // a,b are the param coords of the intersection point of the segment.
1655  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1656  return true;
1657  }
1658 
1659  }
1660  return false;
1661  }
1662 
1663 
1664 
1668  static int MergeCloseVertex(MeshType &m, const ScalarType radius)
1669  {
1670  int mergedCnt=0;
1671  mergedCnt = ClusterVertex(m,radius);
1672  RemoveDuplicateVertex(m,true);
1673  return mergedCnt;
1674  }
1675 
1676  static int ClusterVertex(MeshType &m, const ScalarType radius)
1677  {
1678  if(m.vn==0) return 0;
1679  // some spatial indexing structure does not work well with deleted vertices...
1681  typedef vcg::SpatialHashTable<VertexType, ScalarType> SampleSHT;
1682  SampleSHT sht;
1683  tri::EmptyTMark<MeshType> markerFunctor;
1684  std::vector<VertexType*> closests;
1685  int mergedCnt=0;
1686  sht.Set(m.vert.begin(), m.vert.end());
1688  for(VertexIterator viv = m.vert.begin(); viv!= m.vert.end(); ++viv)
1689  if(!(*viv).IsD() && !(*viv).IsV())
1690  {
1691  (*viv).SetV();
1692  Point3<ScalarType> p = viv->cP();
1693  Box3<ScalarType> bb(p-Point3<ScalarType>(radius,radius,radius),p+Point3<ScalarType>(radius,radius,radius));
1694  GridGetInBox(sht, markerFunctor, bb, closests);
1695  // qDebug("Vertex %i has %i closest", &*viv - &*m.vert.begin(),closests.size());
1696  for(size_t i=0; i<closests.size(); ++i)
1697  {
1698  ScalarType dist = Distance(p,closests[i]->cP());
1699  if(dist < radius && !closests[i]->IsV())
1700  {
1701  // printf("%f %f \n",dist,radius);
1702  mergedCnt++;
1703  closests[i]->SetV();
1704  closests[i]->P()=p;
1705  }
1706  }
1707  }
1708  return mergedCnt;
1709  }
1710 
1711 
1712  static std::pair<int,int> RemoveSmallConnectedComponentsSize(MeshType &m, int maxCCSize)
1713  {
1714  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1715  int TotalCC=ConnectedComponents(m, CCV);
1716  int DeletedCC=0;
1717 
1718  ConnectedComponentIterator<MeshType> ci;
1719  for(unsigned int i=0;i<CCV.size();++i)
1720  {
1721  std::vector<typename MeshType::FacePointer> FPV;
1722  if(CCV[i].first<maxCCSize)
1723  {
1724  DeletedCC++;
1725  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1726  FPV.push_back(*ci);
1727 
1728  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1729  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1730  Allocator<MeshType>::DeleteFace(m,(**fpvi));
1731  }
1732  }
1733  return std::make_pair(TotalCC,DeletedCC);
1734  }
1735 
1736 
1738  // it returns a pair with the number of connected components and the number of deleted ones.
1739  static std::pair<int,int> RemoveSmallConnectedComponentsDiameter(MeshType &m, ScalarType maxDiameter)
1740  {
1741  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1742  int TotalCC=ConnectedComponents(m, CCV);
1743  int DeletedCC=0;
1744  tri::ConnectedComponentIterator<MeshType> ci;
1745  for(unsigned int i=0;i<CCV.size();++i)
1746  {
1747  Box3<ScalarType> bb;
1748  std::vector<typename MeshType::FacePointer> FPV;
1749  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1750  {
1751  FPV.push_back(*ci);
1752  bb.Add((*ci)->P(0));
1753  bb.Add((*ci)->P(1));
1754  bb.Add((*ci)->P(2));
1755  }
1756  if(bb.Diag()<maxDiameter)
1757  {
1758  DeletedCC++;
1759  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1760  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1762  }
1763  }
1764  return std::make_pair(TotalCC,DeletedCC);
1765  }
1766 
1768  // it returns a pair with the number of connected components and the number of deleted ones.
1769  static std::pair<int,int> RemoveHugeConnectedComponentsDiameter(MeshType &m, ScalarType minDiameter)
1770  {
1771  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1772  int TotalCC=ConnectedComponents(m, CCV);
1773  int DeletedCC=0;
1774  tri::ConnectedComponentIterator<MeshType> ci;
1775  for(unsigned int i=0;i<CCV.size();++i)
1776  {
1777  Box3f bb;
1778  std::vector<typename MeshType::FacePointer> FPV;
1779  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1780  {
1781  FPV.push_back(*ci);
1782  bb.Add((*ci)->P(0));
1783  bb.Add((*ci)->P(1));
1784  bb.Add((*ci)->P(2));
1785  }
1786  if(bb.Diag()>minDiameter)
1787  {
1788  DeletedCC++;
1789  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1790  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1792  }
1793  }
1794  return std::make_pair(TotalCC,DeletedCC);
1795  }
1796 
1797 
1798 
1805  static void SelectFoldedFaceFromOneRingFaces(MeshType &m, ScalarType cosThreshold)
1806  {
1807  typedef std::unordered_set<VertexPointer> VertexSet;
1808  tri::RequireVFAdjacency(m);
1809  tri::RequirePerFaceNormal(m);
1810  tri::RequirePerVertexNormal(m);
1815  if (cosThreshold > 0)
1816  cosThreshold = 0;
1817 
1818 #pragma omp parallel for schedule(dynamic, 10)
1819  for (int i = 0; i < m.face.size(); i++)
1820  {
1821  VertexSet nearVertex;
1822  std::vector<CoordType> pointVec;
1823  FacePointer f = &m.face[i];
1824  for (int j = 0; j < 3; j++)
1825  {
1826  std::vector<VertexPointer> temp;
1827  vcg::face::VVStarVF<FaceType>(f->V(j), temp);
1828  typename std::vector<VertexPointer>::iterator iter = temp.begin();
1829  for (; iter != temp.end(); iter++)
1830  {
1831  if ((*iter) != f->V1(j) && (*iter) != f->V2(j))
1832  {
1833  if (nearVertex.insert((*iter)).second)
1834  pointVec.push_back((*iter)->P());
1835  }
1836  }
1837  nearVertex.insert(f->V(j));
1838  pointVec.push_back(f->P(j));
1839  }
1840 
1841  if (pointVec.size() > 3)
1842  {
1843  vcg::Plane3<ScalarType> plane;
1844  vcg::FitPlaneToPointSet(pointVec, plane);
1845  float avgDot = 0;
1846  for (auto nvp : nearVertex)
1847  avgDot += plane.Direction().dot(nvp->N());
1848  avgDot /= nearVertex.size();
1849  typename MeshType::VertexType::NormalType normal;
1850  if (avgDot < 0)
1851  normal = -plane.Direction();
1852  else
1853  normal = plane.Direction();
1854  if (normal.dot(f->N()) < cosThreshold)
1855  f->SetS();
1856  }
1857  }
1858  }
1863  static int SelectIntersectingFaces(MeshType &m1, MeshType &m2)
1864  {
1865  RequirePerFaceMark(m2);
1866  RequireCompactness(m1);
1867  RequireCompactness(m2);
1868 
1870 
1871  TriMeshGrid gM;
1872  gM.Set(m2.face.begin(),m2.face.end());
1873  int selCnt=0;
1874  for(auto fi=m1.face.begin();fi!=m1.face.end();++fi)
1875  {
1876  Box3< ScalarType> bbox;
1877  (*fi).GetBBox(bbox);
1878  std::vector<FaceType*> inBox;
1879  vcg::tri::GetInBoxFace(m2, gM, bbox,inBox);
1880  for(auto fib=inBox.begin(); fib!=inBox.end(); ++fib)
1881  {
1883  fi->SetS();
1884  ++selCnt;
1885  }
1886  }
1887  inBox.clear();
1888  }
1889  return selCnt;
1890  }
1891 
1892 }; // end class
1895 } //End Namespace Tri
1896 } // End Namespace vcg
1897 #endif