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, const ScalarType moveThreshold = 0)
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  for (size_t i = 0; i < size_t(tmpMesh.VN()); ++i)
726  {
727  VertexType & v = tmpMesh.vert[i];
728 
729  if (v.IsB())
730  {
731  std::vector<FacePointer> faceVec;
732  std::vector<int> idxVec;
733 
734  vcg::face::VFStarVF(&v, faceVec, idxVec);
735 
736  CoordType delta(0, 0, 0);
737  for (auto fp : faceVec)
738  {
739  delta += vcg::Barycenter(*fp) - v.cP();
740  }
741  delta /= faceVec.size();
742 
743  v.P() += delta * moveThreshold;
744  }
745  }
746 
749  return selCnt;
750  }
751 
752 
753  // Auxiliary function for sorting the non manifold faces according to their area. Used in RemoveNonManifoldFace
754  struct CompareAreaFP {
755  bool operator ()(FacePointer const& f1, FacePointer const& f2) const {
756  return DoubleArea(*f1) < DoubleArea(*f2);
757  }
758  };
759 
761  static int RemoveNonManifoldFace(MeshType& m)
762  {
763  FaceIterator fi;
764  int count_fd = 0;
765  std::vector<FacePointer> ToDelVec;
766 
767  for(fi=m.face.begin(); fi!=m.face.end();++fi)
768  if (!fi->IsD())
769  {
770  if ((!IsManifold(*fi,0))||
771  (!IsManifold(*fi,1))||
772  (!IsManifold(*fi,2)))
773  ToDelVec.push_back(&*fi);
774  }
775 
776  std::sort(ToDelVec.begin(),ToDelVec.end(),CompareAreaFP());
777 
778  for(size_t i=0;i<ToDelVec.size();++i)
779  {
780  if(!ToDelVec[i]->IsD())
781  {
782  FaceType &ff= *ToDelVec[i];
783  if ((!IsManifold(ff,0))||
784  (!IsManifold(ff,1))||
785  (!IsManifold(ff,2)))
786  {
787  for(int j=0;j<3;++j)
788  if(!face::IsBorder<FaceType>(ff,j))
789  vcg::face::FFDetach<FaceType>(ff,j);
790 
792  count_fd++;
793  }
794  }
795  }
796  return count_fd;
797  }
798 
799  /* Remove the faces that are out of a given range of area */
800  static int RemoveFaceOutOfRangeArea(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)(), bool OnlyOnSelected=false)
801  {
802  int count_fd = 0;
803  MinAreaThr*=2;
804  MaxAreaThr*=2;
805  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi){
806  if(!(*fi).IsD())
807  if(!OnlyOnSelected || (*fi).IsS())
808  {
809  const ScalarType doubleArea=DoubleArea<FaceType>(*fi);
810  if((doubleArea<=MinAreaThr) || (doubleArea>=MaxAreaThr) )
811  {
813  count_fd++;
814  }
815  }
816  }
817  return count_fd;
818  }
819 
820  static int RemoveZeroAreaFace(MeshType& m) { return RemoveFaceOutOfRangeArea(m,0);}
821 
822 
823 
827  static bool IsBitQuadOnly(const MeshType &m)
828  {
829  typedef typename MeshType::FaceType F;
830  tri::RequirePerFaceFlags(m);
831  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
832  unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
833  if ( tmp != F::FAUX0 && tmp != F::FAUX1 && tmp != F::FAUX2) return false;
834  }
835  return true;
836  }
837 
838 
839  static bool IsFaceFauxConsistent(MeshType &m)
840  {
841  RequirePerFaceFlags(m);
842  RequireFFAdjacency(m);
843  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
844  {
845  for(int z=0;z<(*fi).VN();++z)
846  {
847  FacePointer fp = fi->FFp(z);
848  int zp = fi->FFi(z);
849  if(fi->IsF(z) != fp->IsF(zp)) return false;
850  }
851  }
852  return true;
853  }
854 
858  static bool IsBitTriOnly(const MeshType &m)
859  {
860  tri::RequirePerFaceFlags(m);
861  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) {
862  if ( !fi->IsD() && fi->IsAnyF() ) return false;
863  }
864  return true;
865  }
866 
867  static bool IsBitPolygonal(const MeshType &m){
868  return !IsBitTriOnly(m);
869  }
870 
875  static bool IsBitTriQuadOnly(const MeshType &m)
876  {
877  tri::RequirePerFaceFlags(m);
878  typedef typename MeshType::FaceType F;
879  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
880  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
881  if ( tmp!=F::FAUX0 && tmp!=F::FAUX1 && tmp!=F::FAUX2 && tmp!=0 ) return false;
882  }
883  return true;
884  }
885 
890  static int CountBitQuads(const MeshType &m)
891  {
892  tri::RequirePerFaceFlags(m);
893  typedef typename MeshType::FaceType F;
894  int count=0;
895  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
896  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
897  if ( tmp==F::FAUX0 || tmp==F::FAUX1 || tmp==F::FAUX2) count++;
898  }
899  return count / 2;
900  }
901 
905  static int CountBitTris(const MeshType &m)
906  {
907  tri::RequirePerFaceFlags(m);
908  int count=0;
909  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
910  if (!(fi->IsAnyF())) count++;
911  }
912  return count;
913  }
914 
919  static int CountBitPolygons(const MeshType &m)
920  {
921  tri::RequirePerFaceFlags(m);
922  int count = 0;
923  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
924  if (fi->IsF(0)) count++;
925  if (fi->IsF(1)) count++;
926  if (fi->IsF(2)) count++;
927  }
928  return m.fn - count/2;
929  }
930 
942  static int CountBitLargePolygons(MeshType &m)
943  {
944  tri::RequirePerFaceFlags(m);
946  // First loop Clear all referenced vertices
947  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
948  if (!fi->IsD())
949  for(int i=0;i<3;++i) fi->V(i)->ClearV();
950 
951 
952  // Second Loop, count (twice) faux edges and mark all vertices touched by non faux edges
953  // (e.g vertexes on the boundary of a polygon)
954  int countE = 0;
955  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
956  if (!fi->IsD()) {
957  for(int i=0;i<3;++i)
958  {
959  if (fi->IsF(i))
960  countE++;
961  else
962  {
963  fi->V0(i)->SetV();
964  fi->V1(i)->SetV();
965  }
966  }
967  }
968  // Third Loop, count the number of referenced vertexes that are completely surrounded by faux edges.
969 
970  int countV = 0;
971  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
972  if (!vi->IsD() && !vi->IsV()) countV++;
973 
974  return m.fn - countE/2 + countV ;
975  }
976 
977 
985  static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
986  {
987  RequireFFAdjacency(m);
988  RequirePerFaceFlags(m);
989 
990  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
991  if(!(*fi).IsD())
992  for (int k=0; k<3; k++)
993  if( ( fi->IsF(k) != fi->cFFp(k)->IsF(fi->cFFi(k)) ) ||
994  ( fi->IsF(k) && face::IsBorder(*fi,k)) )
995  {
996  return false;
997  }
998  return true;
999  }
1000 
1005  static int CountNonManifoldEdgeEE( MeshType & m, bool SelectFlag=false)
1006  {
1007  MeshAssert<MeshType>::OnlyEdgeMesh(m);
1008  RequireEEAdjacency(m);
1010 
1011  if(SelectFlag) UpdateSelection<MeshType>::VertexClear(m);
1012 
1013  int nonManifoldCnt=0;
1014  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
1015 
1016  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
1017  EdgeIterator ei;
1018  for (ei = m.edge.begin(); ei != m.edge.end(); ++ei) if (!ei->IsD())
1019  {
1020  TD[(*ei).V(0)]++;
1021  TD[(*ei).V(1)]++;
1022  }
1023 
1025  // Second Loop, Check that each vertex have been seen 1 or 2 times.
1026  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if (!vi->IsD())
1027  {
1028  if( TD[vi] >2 )
1029  {
1030  if(SelectFlag) (*vi).SetS();
1031  nonManifoldCnt++;
1032  }
1033  }
1034  return nonManifoldCnt;
1035  }
1036 
1043  static int CountNonManifoldEdgeFF( MeshType & m, bool SelectFlag=false)
1044  {
1045  RequireFFAdjacency(m);
1046  int nmfBit[3];
1047  nmfBit[0]= FaceType::NewBitFlag();
1048  nmfBit[1]= FaceType::NewBitFlag();
1049  nmfBit[2]= FaceType::NewBitFlag();
1050 
1051 
1052  UpdateFlags<MeshType>::FaceClear(m,nmfBit[0]+nmfBit[1]+nmfBit[2]);
1053 
1054  if(SelectFlag){
1057  }
1058 
1059  int edgeCnt = 0;
1060  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1061  {
1062  if (!fi->IsD())
1063  {
1064  for(int i=0;i<3;++i)
1065  if(!IsManifold(*fi,i))
1066  {
1067  if(!(*fi).IsUserBit(nmfBit[i]))
1068  {
1069  ++edgeCnt;
1070  if(SelectFlag)
1071  {
1072  (*fi).V0(i)->SetS();
1073  (*fi).V1(i)->SetS();
1074  }
1075  // follow the ring of faces incident on edge i;
1076  face::Pos<FaceType> nmf(&*fi,i);
1077  do
1078  {
1079  if(SelectFlag) nmf.F()->SetS();
1080  nmf.F()->SetUserBit(nmfBit[nmf.E()]);
1081  nmf.NextF();
1082  }
1083  while(nmf.f != &*fi);
1084  }
1085  }
1086  }
1087  }
1088  return edgeCnt;
1089  }
1090 
1095  static int CountNonManifoldVertexFF( MeshType & m, bool selectVert = true, bool clearSelection = true)
1096  {
1097  RequireFFAdjacency(m);
1098  if(selectVert && clearSelection) UpdateSelection<MeshType>::VertexClear(m);
1099 
1100  int nonManifoldCnt=0;
1101  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
1102 
1103  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
1104  FaceIterator fi;
1105  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1106  {
1107  for (int k=0; k<fi->VN(); k++)
1108  {
1109  TD[(*fi).V(k)]++;
1110  }
1111  }
1112 
1114  // Second Loop.
1115  // mark out of the game the vertexes that are incident on non manifold edges.
1116  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1117  {
1118  for(int i=0; i<fi->VN(); ++i)
1119  if (!IsManifold(*fi,i))
1120  {
1121  (*fi).V0(i)->SetV();
1122  (*fi).V1(i)->SetV();
1123  }
1124  }
1125  // Third Loop, for safe vertexes, check that the number of faces that you can reach starting
1126  // from it and using FF is the same of the previously counted.
1127  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1128  {
1129  for(int i=0; i<fi->VN(); i++) if (!(*fi).V(i)->IsV())
1130  {
1131  (*fi).V(i)->SetV();
1132  face::Pos<FaceType> pos(&(*fi),i);
1133 
1134  int starSizeFF = pos.NumberOfIncidentFaces();
1135 
1136  if (starSizeFF != TD[(*fi).V(i)])
1137  {
1138  if (selectVert)
1139  (*fi).V(i)->SetS();
1140  nonManifoldCnt++;
1141  }
1142  }
1143  }
1144  return nonManifoldCnt;
1145  }
1153  static bool IsWaterTight(MeshType & m)
1154  {
1155  int edgeNum=0,edgeBorderNum=0,edgeNonManifNum=0;
1156  CountEdgeNum(m, edgeNum, edgeBorderNum,edgeNonManifNum);
1157  return (edgeBorderNum==0) && (edgeNonManifNum==0);
1158  }
1159 
1160  static void CountEdgeNum( MeshType & m, int &total_e, int &boundary_e, int &non_manif_e )
1161  {
1162  std::vector< typename tri::UpdateTopology<MeshType>::PEdge > edgeVec;
1164  sort(edgeVec.begin(), edgeVec.end()); // Lo ordino per vertici
1165  total_e=0;
1166  boundary_e=0;
1167  non_manif_e=0;
1168 
1169  size_t f_on_cur_edge =1;
1170  for(size_t i=0;i<edgeVec.size();++i)
1171  {
1172  if(( (i+1) == edgeVec.size()) || !(edgeVec[i] == edgeVec[i+1]))
1173  {
1174  ++total_e;
1175  if(f_on_cur_edge==1)
1176  ++boundary_e;
1177  if(f_on_cur_edge>2)
1178  ++non_manif_e;
1179  f_on_cur_edge=1;
1180  }
1181  else
1182  {
1183  ++f_on_cur_edge;
1184  }
1185  } // end for
1186  }
1187 
1188 
1189 
1190  static int CountHoles( MeshType & m)
1191  {
1192  UpdateFlags<MeshType>::FaceClearV(m);
1193  int loopNum=0;
1194  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD())
1195  {
1196  for(int j=0;j<3;++j)
1197  {
1198  if(!fi->IsV() && face::IsBorder(*fi,j))
1199  {
1200  face::Pos<FaceType> startPos(&*fi,j);
1201  face::Pos<FaceType> curPos=startPos;
1202  do
1203  {
1204  curPos.NextB();
1205  curPos.F()->SetV();
1206  }
1207  while(curPos!=startPos);
1208  ++loopNum;
1209  }
1210  }
1211  }
1212  return loopNum;
1213  }
1214 
1215  /*
1216  Compute the set of connected components of a given mesh
1217  it fills a vector of pair < int , faceptr > with, for each connecteed component its size and a represnant
1218  */
1219  static int CountConnectedComponents(MeshType &m)
1220  {
1221  std::vector< std::pair<int,FacePointer> > CCV;
1222  return ConnectedComponents(m,CCV);
1223  }
1224 
1225  static int ConnectedComponents(MeshType &m, std::vector< std::pair<int,FacePointer> > &CCV)
1226  {
1227  tri::RequireFFAdjacency(m);
1228  CCV.clear();
1229  tri::UpdateFlags<MeshType>::FaceClearV(m);
1230  std::stack<FacePointer> sf;
1231  FacePointer fpt=&*(m.face.begin());
1232  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1233  {
1234  if(!((*fi).IsD()) && !(*fi).IsV())
1235  {
1236  (*fi).SetV();
1237  CCV.push_back(std::make_pair(0,&*fi));
1238  sf.push(&*fi);
1239  while (!sf.empty())
1240  {
1241  fpt=sf.top();
1242  ++CCV.back().first;
1243  sf.pop();
1244  for(int j=0; j<fpt->VN(); ++j)
1245  {
1246  if( !face::IsBorder(*fpt,j) )
1247  {
1248  FacePointer l = fpt->FFp(j);
1249  if( !(*l).IsV() )
1250  {
1251  (*l).SetV();
1252  sf.push(l);
1253  }
1254  }
1255  }
1256  }
1257  }
1258  }
1259  return int(CCV.size());
1260  }
1261 
1262  static int edgeMeshConnectedComponents(MeshType & poly, std::vector<std::pair<int, typename MeshType::EdgePointer> > &eCC)
1263  {
1264  typedef typename MeshType::EdgePointer EdgePointer;
1265  tri::UpdateTopology<MeshType>::VertexEdge(poly);
1266  tri::UpdateFlags<MeshType>::EdgeClear(poly);
1267  eCC.clear();
1268  std::stack<EdgePointer> stack;
1269 
1270  for (auto ei = poly.edge.begin(); ei != poly.edge.end(); ++ei)
1271  if (!ei->IsD() && !ei->IsV())
1272  {
1273  ei->SetV();
1274 
1275  std::pair<int, EdgePointer> cc(1, &*ei);
1276 
1277  stack.push(&*ei);
1278  while (!stack.empty())
1279  {
1280  EdgePointer ep = stack.top();
1281  stack.pop();
1282 
1283  for (int i = 0; i < 2; ++i)
1284  {
1285  edge::VEIterator<typename MeshType::EdgeType> vei(ep->V(i));
1286  while (!vei.End())
1287  {
1288  if (!vei.E()->IsV())
1289  {
1290  vei.E()->SetV();
1291  stack.push(vei.E());
1292  cc.first += 1;
1293  }
1294  ++vei;
1295  }
1296  }
1297  }
1298  eCC.push_back(cc);
1299  }
1300  return int(eCC.size());
1301  }
1302 
1303  static void ComputeValence( MeshType &m, typename MeshType::PerVertexIntHandle &h)
1304  {
1305  for(VertexIterator vi=m.vert.begin(); vi!= m.vert.end();++vi)
1306  h[vi]=0;
1307 
1308  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1309  {
1310  if(!((*fi).IsD()))
1311  for(int j=0;j<fi->VN();j++)
1312  ++h[tri::Index(m,fi->V(j))];
1313  }
1314  }
1315 
1351  static int MeshGenus(int nvert,int nedges,int nfaces, int numholes, int numcomponents)
1352  {
1353  return -((nvert + nfaces - nedges + numholes - 2 * numcomponents) / 2);
1354  }
1355 
1356  static int MeshGenus(MeshType &m)
1357  {
1358  int nvert=m.vn;
1359  int nfaces=m.fn;
1360  int boundary_e,total_e,nonmanif_e;
1361  CountEdgeNum(m,total_e,boundary_e,nonmanif_e);
1362  int numholes=CountHoles(m);
1363  int numcomponents=CountConnectedComponents(m);
1364  int G=MeshGenus(nvert,total_e,nfaces,numholes,numcomponents);
1365  return G;
1366  }
1367 
1379  static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular)
1380  {
1381  RequireVFAdjacency(m);
1382  Regular = true;
1383 
1384  VertexIterator vi;
1385 
1386  // for each vertex the number of edges are count
1387  for (vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1388  {
1389  if (!vi->IsD())
1390  {
1391  face::Pos<FaceType> he((*vi).VFp(), &*vi);
1392  face::Pos<FaceType> ht = he;
1393 
1394  int n=0;
1395  bool border=false;
1396  do
1397  {
1398  ++n;
1399  ht.NextE();
1400  if (ht.IsBorder())
1401  border=true;
1402  }
1403  while (ht != he);
1404 
1405  if (border)
1406  n = n/2;
1407 
1408  if ((n != 6)&&(!border && n != 4))
1409  {
1410  Regular = false;
1411  break;
1412  }
1413  }
1414  }
1415 
1416  if (!Regular)
1417  Semiregular = false;
1418  else
1419  {
1420  // For now we do not account for semi-regularity
1421  Semiregular = false;
1422  }
1423  }
1424 
1425 
1426  static bool IsCoherentlyOrientedMesh(MeshType &m)
1427  {
1428  RequireFFAdjacency(m);
1429  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1430  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1431  if (!fi->IsD())
1432  for(int i=0;i<3;++i)
1433  if(!face::CheckOrientation(*fi,i))
1434  return false;
1435 
1436  return true;
1437  }
1438 
1439  static void OrientCoherentlyMesh(MeshType &m, bool &_IsOriented, bool &_IsOrientable)
1440  {
1441  RequireFFAdjacency(m);
1442  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1443  bool IsOrientable = true;
1444  bool IsOriented = true;
1445 
1446  UpdateFlags<MeshType>::FaceClearV(m);
1447  std::stack<FacePointer> faces;
1448  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1449  {
1450  if (!fi->IsD() && !fi->IsV())
1451  {
1452  // each face put in the stack is selected (and oriented)
1453  fi->SetV();
1454  faces.push(&(*fi));
1455  while (!faces.empty())
1456  {
1457  FacePointer fp = faces.top();
1458  faces.pop();
1459 
1460  // make consistently oriented the adjacent faces
1461  for (int j = 0; j < 3; j++)
1462  {
1463  if (!face::IsBorder(*fp,j) && face::IsManifold<FaceType>(*fp, j))
1464  {
1465  FacePointer fpaux = fp->FFp(j);
1466  int iaux = fp->FFi(j);
1467  if (!CheckOrientation(*fpaux, iaux))
1468  {
1469  IsOriented = false;
1470 
1471  if (!fpaux->IsV())
1472  face::SwapEdge<FaceType,true>(*fpaux, iaux);
1473  else
1474  {
1475  IsOrientable = false;
1476  break;
1477  }
1478  }
1479  if (!fpaux->IsV())
1480  {
1481  fpaux->SetV();
1482  faces.push(fpaux);
1483  }
1484  }
1485  }
1486  }
1487  }
1488  if (!IsOrientable) break;
1489  }
1490  _IsOriented = IsOriented;
1491  _IsOrientable = IsOrientable;
1492  }
1493 
1494 
1496  static void FlipMesh(MeshType &m, bool selected=false)
1497  {
1498  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if(!(*fi).IsD())
1499  if(!selected || (*fi).IsS())
1500  {
1501  face::SwapEdge<FaceType,false>((*fi), 0);
1502  if (HasPerWedgeTexCoord(m))
1503  std::swap((*fi).WT(0),(*fi).WT(1));
1504  }
1505  }
1511  static bool FlipNormalOutside(MeshType &m)
1512  {
1513  if(m.vert.empty()) return false;
1514 
1517 
1518  std::vector< VertexPointer > minVertVec;
1519  std::vector< VertexPointer > maxVertVec;
1520 
1521  // The set of directions to be choosen
1522  std::vector< CoordType > dirVec;
1523  dirVec.push_back(CoordType(1,0,0));
1524  dirVec.push_back(CoordType(0,1,0));
1525  dirVec.push_back(CoordType(0,0,1));
1526  dirVec.push_back(CoordType( 1, 1,1));
1527  dirVec.push_back(CoordType(-1, 1,1));
1528  dirVec.push_back(CoordType(-1,-1,1));
1529  dirVec.push_back(CoordType( 1,-1,1));
1530  for(size_t i=0;i<dirVec.size();++i)
1531  {
1532  Normalize(dirVec[i]);
1533  minVertVec.push_back(&*m.vert.begin());
1534  maxVertVec.push_back(&*m.vert.begin());
1535  }
1536  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if(!(*vi).IsD())
1537  {
1538  for(size_t i=0;i<dirVec.size();++i)
1539  {
1540  if( (*vi).cP().dot(dirVec[i]) < minVertVec[i]->P().dot(dirVec[i])) minVertVec[i] = &*vi;
1541  if( (*vi).cP().dot(dirVec[i]) > maxVertVec[i]->P().dot(dirVec[i])) maxVertVec[i] = &*vi;
1542  }
1543  }
1544 
1545  int voteCount=0;
1546  ScalarType angleThreshold = cos(math::ToRad(85.0));
1547  for(size_t i=0;i<dirVec.size();++i)
1548  {
1549  // 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]);
1550  // 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]);
1551  if(minVertVec[i]->N().dot(dirVec[i]) > angleThreshold ) voteCount++;
1552  if(maxVertVec[i]->N().dot(dirVec[i]) < -angleThreshold ) voteCount++;
1553  }
1554  // qDebug("votecount = %i",voteCount);
1555  if(voteCount < int(dirVec.size())/2) return false;
1556  FlipMesh(m);
1557  return true;
1558  }
1559 
1560  // Search and remove small single triangle folds
1561  // - a face has normal opposite to all other faces
1562  // - choose the edge that brings to the face f1 containing the vertex opposite to that edge.
1563  static int RemoveFaceFoldByFlip(MeshType &m, float normalThresholdDeg=175, bool repeat=true)
1564  {
1565  RequireFFAdjacency(m);
1566  RequirePerVertexMark(m);
1567  //Counters for logging and convergence
1568  int count, total = 0;
1569 
1570  do {
1572  tri::UnMarkAll(m);
1573  count = 0;
1574 
1575  ScalarType NormalThrRad = math::ToRad(normalThresholdDeg);
1576  ScalarType eps = ScalarType(0.0001); // this epsilon value is in absolute value. It is a distance from edge in baricentric coords.
1577  //detection stage
1578  for(FaceIterator fi=m.face.begin();fi!= m.face.end();++fi ) if(!(*fi).IsV())
1579  { Point3<ScalarType> NN = vcg::TriangleNormal((*fi)).Normalize();
1580  if( vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(0)).Normalize()) > NormalThrRad &&
1581  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(1)).Normalize()) > NormalThrRad &&
1582  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(2)).Normalize()) > NormalThrRad )
1583  {
1584  (*fi).SetS();
1585  //(*fi).C()=Color4b(Color4b::Red);
1586  // now search the best edge to flip
1587  for(int i=0;i<3;i++)
1588  {
1589  Point3<ScalarType> &p=(*fi).P2(i);
1590  Point3<ScalarType> L;
1591  bool ret = vcg::InterpolationParameters((*(*fi).FFp(i)),TriangleNormal(*(*fi).FFp(i)),p,L);
1592  if(ret && L[0]>eps && L[1]>eps && L[2]>eps)
1593  {
1594  (*fi).FFp(i)->SetS();
1595  (*fi).FFp(i)->SetV();
1596  //(*fi).FFp(i)->C()=Color4b(Color4b::Green);
1597  if(face::CheckFlipEdge<FaceType>( *fi, i )) {
1598  face::FlipEdge<FaceType>( *fi, i );
1599  ++count; ++total;
1600  }
1601  }
1602  }
1603  }
1604  }
1605 
1606  // tri::UpdateNormal<MeshType>::PerFace(m);
1607  }
1608  while( repeat && count );
1609  return total;
1610  }
1611 
1612 
1613  static int RemoveTVertexByFlip(MeshType &m, float threshold=40, bool repeat=true)
1614  {
1615  RequireFFAdjacency(m);
1616  RequirePerVertexMark(m);
1617  //Counters for logging and convergence
1618  int count, total = 0;
1619 
1620  do {
1622  tri::UnMarkAll(m);
1623  count = 0;
1624 
1625  //detection stage
1626  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1627  {
1628  FacePointer f = &(m.face[index]); float sides[3]; CoordType dummy;
1629  sides[0] = Distance(f->P(0), f->P(1));
1630  sides[1] = Distance(f->P(1), f->P(2));
1631  sides[2] = Distance(f->P(2), f->P(0));
1632  // Find largest triangle side
1633  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1634  if( tri::IsMarked(m,f->V2(i) )) continue;
1635 
1636  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1637  {
1638  tri::Mark(m,f->V2(i));
1639  if(face::CheckFlipEdge<FaceType>( *f, i )) {
1640  // Check if EdgeFlipping improves quality
1641  FacePointer g = f->FFp(i); int k = f->FFi(i);
1642  Triangle3<ScalarType> t1(f->P(i), f->P1(i), f->P2(i)), t2(g->P(k), g->P1(k), g->P2(k)),
1643  t3(f->P(i), g->P2(k), f->P2(i)), t4(g->P(k), f->P2(i), g->P2(k));
1644 
1645  if ( std::min( QualityFace(t1), QualityFace(t2) ) < std::min( QualityFace(t3), QualityFace(t4) ))
1646  {
1647  face::FlipEdge<FaceType>( *f, i );
1648  ++count; ++total;
1649  }
1650  }
1651 
1652  }
1653  }
1654 
1655  // tri::UpdateNormal<MeshType>::PerFace(m);
1656  }
1657  while( repeat && count );
1658  return total;
1659  }
1660 
1661  static int RemoveTVertexByCollapse(MeshType &m, float threshold=40, bool repeat=true)
1662  {
1663  RequirePerVertexMark(m);
1664  //Counters for logging and convergence
1665  int count, total = 0;
1666 
1667  do {
1668  tri::UnMarkAll(m);
1669  count = 0;
1670 
1671  //detection stage
1672  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1673  {
1674  FacePointer f = &(m.face[index]);
1675  float sides[3];
1676  CoordType dummy;
1677 
1678  sides[0] = Distance(f->P(0), f->P(1));
1679  sides[1] = Distance(f->P(1), f->P(2));
1680  sides[2] = Distance(f->P(2), f->P(0));
1681  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1682  if( tri::IsMarked(m,f->V2(i) )) continue;
1683 
1684  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1685  {
1686  tri::Mark(m,f->V2(i));
1687 
1688  int j = Distance(dummy,f->P(i))<Distance(dummy,f->P1(i))?i:(i+1)%3;
1689  f->P2(i) = f->P(j); tri::Mark(m,f->V(j));
1690  ++count; ++total;
1691  }
1692  }
1693 
1694 
1698  }
1699  while( repeat && count );
1700 
1701  return total;
1702  }
1703 
1704  static bool SelfIntersections(MeshType &m, std::vector<FaceType*> &ret)
1705  {
1706  RequirePerFaceMark(m);
1707  ret.clear();
1708  int referredBit = FaceType::NewBitFlag();
1709  tri::UpdateFlags<MeshType>::FaceClear(m,referredBit);
1710 
1711  TriMeshGrid gM;
1712  gM.Set(m.face.begin(),m.face.end());
1713 
1714  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
1715  {
1716  (*fi).SetUserBit(referredBit);
1717  Box3< ScalarType> bbox;
1718  (*fi).GetBBox(bbox);
1719  std::vector<FaceType*> inBox;
1720  vcg::tri::GetInBoxFace(m, gM, bbox,inBox);
1721  bool Intersected=false;
1722  typename std::vector<FaceType*>::iterator fib;
1723  for(fib=inBox.begin();fib!=inBox.end();++fib)
1724  {
1725  if(!(*fib)->IsUserBit(referredBit) && (*fib != &*fi) )
1726  if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){
1727  ret.push_back(*fib);
1728  if(!Intersected) {
1729  ret.push_back(&*fi);
1730  Intersected=true;
1731  }
1732  }
1733  }
1734  inBox.clear();
1735  }
1736 
1737  FaceType::DeleteBitFlag(referredBit);
1738  return (ret.size()>0);
1739  }
1740 
1744  static bool IsSizeConsistent(MeshType &m)
1745  {
1746  int DeletedVertNum=0;
1747  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1748  if((*vi).IsD()) DeletedVertNum++;
1749 
1750  int DeletedEdgeNum=0;
1751  for (EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei)
1752  if((*ei).IsD()) DeletedEdgeNum++;
1753 
1754  int DeletedFaceNum=0;
1755  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1756  if((*fi).IsD()) DeletedFaceNum++;
1757 
1758  if(size_t(m.vn+DeletedVertNum) != m.vert.size()) return false;
1759  if(size_t(m.en+DeletedEdgeNum) != m.edge.size()) return false;
1760  if(size_t(m.fn+DeletedFaceNum) != m.face.size()) return false;
1761 
1762  return true;
1763  }
1764 
1769  static bool IsFFAdjacencyConsistent(MeshType &m)
1770  {
1771  RequireFFAdjacency(m);
1772 
1773  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1774  if(!(*fi).IsD())
1775  {
1776  for(int i=0;i<3;++i)
1777  if(!FFCorrectness(*fi, i)) return false;
1778  }
1779  return true;
1780  }
1781 
1785  static bool HasConsistentPerWedgeTexCoord(MeshType &m)
1786  {
1787  tri::RequirePerFaceWedgeTexCoord(m);
1788 
1789  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1790  if(!(*fi).IsD())
1791  { FaceType &f=(*fi);
1792  if( ! ( (f.WT(0).N() == f.WT(1).N()) && (f.WT(0).N() == (*fi).WT(2).N()) ) )
1793  return false; // all the vertices must have the same index.
1794 
1795  if((*fi).WT(0).N() <0) return false; // no undefined texture should be allowed
1796  }
1797  return true;
1798  }
1799 
1803  static bool HasZeroTexCoordFace(MeshType &m)
1804  {
1805  tri::RequirePerFaceWedgeTexCoord(m);
1806 
1807  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1808  if(!(*fi).IsD())
1809  {
1810  if( (*fi).WT(0).P() == (*fi).WT(1).P() && (*fi).WT(0).P() == (*fi).WT(2).P() ) return false;
1811  }
1812  return true;
1813  }
1814 
1815 
1823  static bool TestFaceFaceIntersection(FaceType *f0,FaceType *f1)
1824  {
1825  int sv = face::CountSharedVertex(f0,f1);
1826  if(sv==3) return true;
1827  if(sv==0) return (vcg::IntersectionTriangleTriangle<FaceType>((*f0),(*f1)));
1828  // if the faces share only a vertex, the opposite edge (as a segment) is tested against the face
1829  // to avoid degenerate cases where the two triangles have the opposite edge on a common plane
1830  // we offset the segment to test toward the shared vertex
1831  if(sv==1)
1832  {
1833  int i0,i1; ScalarType a,b;
1834  face::FindSharedVertex(f0,f1,i0,i1);
1835  CoordType shP = f0->V(i0)->P()*0.5;
1836  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f0).V1(i0)->P()*0.5+shP,(*f0).V2(i0)->P()*0.5+shP), *f1, a, b) )
1837  {
1838  // a,b are the param coords of the intersection point of the segment.
1839  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1840  return true;
1841  }
1842  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f1).V1(i1)->P()*0.5+shP,(*f1).V2(i1)->P()*0.5+shP), *f0, a, b) )
1843  {
1844  // a,b are the param coords of the intersection point of the segment.
1845  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1846  return true;
1847  }
1848 
1849  }
1850  return false;
1851  }
1852 
1853 
1854 
1858  static int MergeCloseVertex(MeshType &m, const ScalarType radius)
1859  {
1860  int mergedCnt=0;
1861  mergedCnt = ClusterVertex(m,radius);
1862  RemoveDuplicateVertex(m,true);
1863  return mergedCnt;
1864  }
1865 
1866  static int ClusterVertex(MeshType &m, const ScalarType radius)
1867  {
1868  if(m.vn==0) return 0;
1869  // some spatial indexing structure does not work well with deleted vertices...
1871  typedef vcg::SpatialHashTable<VertexType, ScalarType> SampleSHT;
1872  SampleSHT sht;
1873  tri::EmptyTMark<MeshType> markerFunctor;
1874  std::vector<VertexType*> closests;
1875  int mergedCnt=0;
1876  sht.Set(m.vert.begin(), m.vert.end());
1878  for(VertexIterator viv = m.vert.begin(); viv!= m.vert.end(); ++viv)
1879  if(!(*viv).IsD() && !(*viv).IsV())
1880  {
1881  (*viv).SetV();
1882  Point3<ScalarType> p = viv->cP();
1883  Box3<ScalarType> bb(p-Point3<ScalarType>(radius,radius,radius),p+Point3<ScalarType>(radius,radius,radius));
1884  GridGetInBox(sht, markerFunctor, bb, closests);
1885  // qDebug("Vertex %i has %i closest", &*viv - &*m.vert.begin(),closests.size());
1886  for(size_t i=0; i<closests.size(); ++i)
1887  {
1888  ScalarType dist = Distance(p,closests[i]->cP());
1889  if(dist < radius && !closests[i]->IsV())
1890  {
1891  // printf("%f %f \n",dist,radius);
1892  mergedCnt++;
1893  closests[i]->SetV();
1894  closests[i]->P()=p;
1895  }
1896  }
1897  }
1898  return mergedCnt;
1899  }
1900 
1901 
1902  static std::pair<int,int> RemoveSmallConnectedComponentsSize(MeshType &m, int maxCCSize)
1903  {
1904  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1905  int TotalCC=ConnectedComponents(m, CCV);
1906  int DeletedCC=0;
1907 
1908  ConnectedComponentIterator<MeshType> ci;
1909  for(unsigned int i=0;i<CCV.size();++i)
1910  {
1911  std::vector<typename MeshType::FacePointer> FPV;
1912  if(CCV[i].first<maxCCSize)
1913  {
1914  DeletedCC++;
1915  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1916  FPV.push_back(*ci);
1917 
1918  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1919  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1920  Allocator<MeshType>::DeleteFace(m,(**fpvi));
1921  }
1922  }
1923  return std::make_pair(TotalCC,DeletedCC);
1924  }
1925 
1926 
1928  // it returns a pair with the number of connected components and the number of deleted ones.
1929  static std::pair<int,int> RemoveSmallConnectedComponentsDiameter(MeshType &m, ScalarType maxDiameter)
1930  {
1931  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1932  int TotalCC=ConnectedComponents(m, CCV);
1933  int DeletedCC=0;
1934  tri::ConnectedComponentIterator<MeshType> ci;
1935  for(unsigned int i=0;i<CCV.size();++i)
1936  {
1937  Box3<ScalarType> bb;
1938  std::vector<typename MeshType::FacePointer> FPV;
1939  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1940  {
1941  FPV.push_back(*ci);
1942  bb.Add((*ci)->P(0));
1943  bb.Add((*ci)->P(1));
1944  bb.Add((*ci)->P(2));
1945  }
1946  if(bb.Diag()<maxDiameter)
1947  {
1948  DeletedCC++;
1949  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1950  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1952  }
1953  }
1954  return std::make_pair(TotalCC,DeletedCC);
1955  }
1956 
1958  // it returns a pair with the number of connected components and the number of deleted ones.
1959  static std::pair<int,int> RemoveHugeConnectedComponentsDiameter(MeshType &m, ScalarType minDiameter)
1960  {
1961  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1962  int TotalCC=ConnectedComponents(m, CCV);
1963  int DeletedCC=0;
1964  tri::ConnectedComponentIterator<MeshType> ci;
1965  for(unsigned int i=0;i<CCV.size();++i)
1966  {
1967  Box3f bb;
1968  std::vector<typename MeshType::FacePointer> FPV;
1969  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1970  {
1971  FPV.push_back(*ci);
1972  bb.Add((*ci)->P(0));
1973  bb.Add((*ci)->P(1));
1974  bb.Add((*ci)->P(2));
1975  }
1976  if(bb.Diag()>minDiameter)
1977  {
1978  DeletedCC++;
1979  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1980  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1982  }
1983  }
1984  return std::make_pair(TotalCC,DeletedCC);
1985  }
1986 
1987 
1988 
1995  static void SelectFoldedFaceFromOneRingFaces(MeshType &m, ScalarType cosThreshold)
1996  {
1997  typedef std::unordered_set<VertexPointer> VertexSet;
1998  tri::RequireVFAdjacency(m);
1999  tri::RequirePerFaceNormal(m);
2000  tri::RequirePerVertexNormal(m);
2005  if (cosThreshold > 0)
2006  cosThreshold = 0;
2007 
2008 #pragma omp parallel for schedule(dynamic, 10)
2009  for (int i = 0; i < m.face.size(); i++)
2010  {
2011  VertexSet nearVertex;
2012  std::vector<CoordType> pointVec;
2013  FacePointer f = &m.face[i];
2014  for (int j = 0; j < 3; j++)
2015  {
2016  std::vector<VertexPointer> temp;
2017  vcg::face::VVStarVF<FaceType>(f->V(j), temp);
2018  typename std::vector<VertexPointer>::iterator iter = temp.begin();
2019  for (; iter != temp.end(); iter++)
2020  {
2021  if ((*iter) != f->V1(j) && (*iter) != f->V2(j))
2022  {
2023  if (nearVertex.insert((*iter)).second)
2024  pointVec.push_back((*iter)->P());
2025  }
2026  }
2027  nearVertex.insert(f->V(j));
2028  pointVec.push_back(f->P(j));
2029  }
2030 
2031  if (pointVec.size() > 3)
2032  {
2033  vcg::Plane3<ScalarType> plane;
2034  vcg::FitPlaneToPointSet(pointVec, plane);
2035  float avgDot = 0;
2036  for (auto nvp : nearVertex)
2037  avgDot += plane.Direction().dot(nvp->N());
2038  avgDot /= nearVertex.size();
2039  typename MeshType::VertexType::NormalType normal;
2040  if (avgDot < 0)
2041  normal = -plane.Direction();
2042  else
2043  normal = plane.Direction();
2044  if (normal.dot(f->N()) < cosThreshold)
2045  f->SetS();
2046  }
2047  }
2048  }
2053  static int SelectIntersectingFaces(MeshType &m1, MeshType &m2)
2054  {
2055  RequirePerFaceMark(m2);
2056  RequireCompactness(m1);
2057  RequireCompactness(m2);
2058 
2060 
2061  TriMeshGrid gM;
2062  gM.Set(m2.face.begin(),m2.face.end());
2063  int selCnt=0;
2064  for(auto fi=m1.face.begin();fi!=m1.face.end();++fi)
2065  {
2066  Box3< ScalarType> bbox;
2067  (*fi).GetBBox(bbox);
2068  std::vector<FaceType*> inBox;
2069  vcg::tri::GetInBoxFace(m2, gM, bbox,inBox);
2070  for(auto fib=inBox.begin(); fib!=inBox.end(); ++fib)
2071  {
2073  fi->SetS();
2074  ++selCnt;
2075  }
2076  }
2077  inBox.clear();
2078  }
2079  return selCnt;
2080  }
2081 
2082 }; // end class
2085 } //End Namespace Tri
2086 } // End Namespace vcg
2087 #endif