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