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