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