$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  return count_vd;
466  }
467 
476  static int RemoveDegenerateFace(MeshType& m)
477  {
478  int count_fd = 0;
479 
480  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi)
481  if(!(*fi).IsD())
482  {
483  if((*fi).V(0) == (*fi).V(1) ||
484  (*fi).V(0) == (*fi).V(2) ||
485  (*fi).V(1) == (*fi).V(2) )
486  {
487  count_fd++;
488  Allocator<MeshType>::DeleteFace(m,*fi);
489  }
490  }
491  return count_fd;
492  }
493 
494  static int RemoveDegenerateEdge(MeshType& m)
495  {
496  int count_ed = 0;
497 
498  for(EdgeIterator ei=m.edge.begin(); ei!=m.edge.end();++ei)
499  if(!(*ei).IsD())
500  {
501  if((*ei).V(0) == (*ei).V(1) )
502  {
503  count_ed++;
504  Allocator<MeshType>::DeleteEdge(m,*ei);
505  }
506  }
507  return count_ed;
508  }
509 
510  static int RemoveNonManifoldVertex(MeshType& m)
511  {
512  CountNonManifoldVertexFF(m,true);
513  tri::UpdateSelection<MeshType>::FaceFromVertexLoose(m);
514  int count_removed = 0;
515  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi)
516  if(!(*fi).IsD() && (*fi).IsS())
517  Allocator<MeshType>::DeleteFace(m,*fi);
518  for(VertexIterator vi=m.vert.begin(); vi!=m.vert.end();++vi)
519  if(!(*vi).IsD() && (*vi).IsS()) {
520  ++count_removed;
521  Allocator<MeshType>::DeleteVertex(m,*vi);
522  }
523  return count_removed;
524  }
525 
526 
527  static int SplitSelectedVertexOnEdgeMesh(MeshType& m)
528  {
529  tri::RequireCompactness(m);
530 
531  // count selected vertices references
532  std::unordered_map<size_t,size_t> refCount; // selected vertex index -> reference count
533  size_t countSplit = 0;
534  for (size_t i=0; i<m.edge.size(); ++i)
535  {
536  for (int j=0; j<2; ++j)
537  {
538  const VertexPointer vp = m.edge[i].V(j);
539  if (vp->IsS())
540  {
541  const size_t refs = ++refCount[Index(m, m.edge[i].V(j))];
542  if (refs > 1) {
543  countSplit++;
544  }
545  }
546  }
547  }
548  // actual split
549  if (countSplit > 0)
550  {
551  auto newVertIt = tri::Allocator<MeshType>::AddVertices(m, countSplit);
552  for (size_t i=0; i<m.edge.size(); ++i)
553  {
554  for (int j=0; j<2; ++j)
555  {
556  const VertexPointer vp = m.edge[i].V(j);
557  const size_t vIdx = Index(m, vp);
558  if (vp->IsS())
559  {
560  if (--refCount[vIdx] > 0)
561  {
562  newVertIt->ImportData(*vp);
563  m.edge[i].V(j) = &*(newVertIt++);
564  }
565  }
566  }
567  }
568  }
569  return int(countSplit);
570  }
571 
572 
573  static void SelectNonManifoldVertexOnEdgeMesh(MeshType &m)
574  {
575  tri::RequireCompactness(m);
576  tri::UpdateSelection<MeshType>::VertexClear(m);
577  std::vector<int> cnt(m.vn,0);
578 
579  for(size_t i=0;i<m.edge.size();++i)
580  {
581  cnt[tri::Index(m,m.edge[i].V(0))]++;
582  cnt[tri::Index(m,m.edge[i].V(1))]++;
583  }
584  for(size_t i=0;i<m.vert.size();++i)
585  if(cnt[i]>2) m.vert[i].SetS();
586  }
587 
588  static void SelectCreaseVertexOnEdgeMesh(MeshType &m, ScalarType AngleRadThr)
589  {
590  tri::RequireCompactness(m);
591  tri::RequireVEAdjacency(m);
592  tri::UpdateTopology<MeshType>::VertexEdge(m);
593  tri::UpdateSelection<MeshType>::VertexClear(m);
594  for(size_t i=0;i<m.vert.size();++i)
595  {
596  std::vector<VertexPointer> VVStarVec;
597  edge::VVStarVE(&(m.vert[i]),VVStarVec);
598  if(VVStarVec.size()==2)
599  {
600  CoordType v0 = m.vert[i].P() - VVStarVec[0]->P();
601  CoordType v1 = m.vert[i].P() - VVStarVec[1]->P();
602  float angle = M_PI-vcg::Angle(v0,v1);
603  if(angle > AngleRadThr) m.vert[i].SetS();
604  }
605  }
606  }
607 
608 
610 
611  // Given a mesh with FF adjacency
612  // it search for non manifold vertices and duplicate them.
613  // Duplicated vertices are moved apart according to the move threshold param.
614  // that is a percentage of the average vector from the non manifold vertex to the barycenter of the incident faces.
615 
616  static int SplitNonManifoldVertex(MeshType& m, ScalarType moveThreshold)
617  {
618  RequireFFAdjacency(m);
619  typedef std::pair<FacePointer,int> FaceInt; // a face and the index of the vertex that we have to change
620  //
621  std::vector<std::pair<VertexPointer, std::vector<FaceInt> > >ToSplitVec;
622 
623  SelectionStack<MeshType> ss(m);
624  ss.push();
625  CountNonManifoldVertexFF(m,true);
626  UpdateFlags<MeshType>::VertexClearV(m);
627  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
628  {
629  for (int i=0; i<fi->VN(); i++)
630  if ((*fi).V(i)->IsS() && !(*fi).V(i)->IsV())
631  {
632  (*fi).V(i)->SetV();
633  face::Pos<FaceType> startPos(&*fi,i);
634  face::Pos<FaceType> curPos = startPos;
635  std::set<FaceInt> faceSet;
636  do
637  {
638  faceSet.insert(std::make_pair(curPos.F(),curPos.VInd()));
639  curPos.FlipE();
640  curPos.NextF();
641  } while (curPos != startPos);
642 
643  ToSplitVec.push_back(make_pair((*fi).V(i),std::vector<FaceInt>()));
644 
645  typename std::set<FaceInt>::const_iterator iii;
646 
647  for(iii=faceSet.begin();iii!=faceSet.end();++iii)
648  ToSplitVec.back().second.push_back(*iii);
649  }
650  }
651  ss.pop();
652  // Second step actually add new vertices and split them.
653  typename tri::Allocator<MeshType>::template PointerUpdater<VertexPointer> pu;
654  VertexIterator firstVp = tri::Allocator<MeshType>::AddVertices(m,ToSplitVec.size(),pu);
655  for(size_t i =0;i<ToSplitVec.size();++i)
656  {
657  // qDebug("Splitting Vertex %i",ToSplitVec[i].first-&*m.vert.begin());
658  VertexPointer np=ToSplitVec[i].first;
659  pu.Update(np);
660  firstVp->ImportData(*np);
661  // loop on the face to be changed, and also compute the movement vector;
662  CoordType delta(0,0,0);
663  for(size_t j=0;j<ToSplitVec[i].second.size();++j)
664  {
665  FaceInt ff=ToSplitVec[i].second[j];
666  ff.first->V(ff.second)=&*firstVp;
667  delta+=Barycenter(*(ff.first))-np->cP();
668  }
669  delta /= ToSplitVec[i].second.size();
670  firstVp->P() = firstVp->P() + delta * moveThreshold;
671  firstVp++;
672  }
673 
674  return int(ToSplitVec.size());
675  }
676 
678  static size_t SplitManifoldComponents(MeshType &m, const ScalarType moveThreshold = 0)
679  {
680  typedef typename MeshType::FacePointer FacePointer;
681  typedef typename MeshType::FaceIterator FaceIterator;
682  // it also assumes that the FF adjacency is well computed.
683  RequireFFAdjacency(m);
684 
685  UpdateFlags<MeshType>::FaceClearV(m);
686  UpdateFlags<MeshType>::FaceClearS(m);
687 
688  MeshType tmpMesh;
689  tmpMesh.vert.EnableVFAdjacency();
690  tmpMesh.face.EnableVFAdjacency();
691 
692  if (m.face.IsWedgeTexCoordEnabled())
693  tmpMesh.face.EnableWedgeTexCoord();
694 
695  size_t selCnt=0;
696 
697  for(FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
698  if( !(*fi).IsD() && !(*fi).IsV() && !(*fi).IsS())
699  {
700  UpdateFlags<MeshType>::FaceClearS(m);
701 
702  std::deque<FacePointer> visitStack;
703  visitStack.push_back(&*fi);
704 
705  (*fi).SetS();
706  (*fi).SetV();
707 
708  while(!visitStack.empty())
709  {
710  FacePointer fp = visitStack.front();
711  visitStack.pop_front();
712 
713  for(int i=0;i<fp->VN();++i) {
714  FacePointer ff = fp->FFp(i);
715 
716  if(face::IsManifold(*fp, i) && !ff->IsS() && !ff->IsV())
717  {
718  ff->SetS();
719  ff->SetV();
720  visitStack.push_back(ff);
721  }
722  }
723  }
724 
725  Append<MeshType, MeshType>::Mesh(tmpMesh, m, true);
726  ++selCnt;
727  }
728 
729  vcg::tri::UpdateTopology<MeshType>::VertexFace(tmpMesh);
730  vcg::tri::UpdateFlags<MeshType>::VertexBorderFromNone(tmpMesh);
731  for (size_t i = 0; i < size_t(tmpMesh.VN()); ++i)
732  {
733  VertexType & v = tmpMesh.vert[i];
734 
735  if (v.IsB())
736  {
737  std::vector<FacePointer> faceVec;
738  std::vector<int> idxVec;
739 
740  vcg::face::VFStarVF(&v, faceVec, idxVec);
741 
742  CoordType delta(0, 0, 0);
743  for (auto fp : faceVec)
744  {
745  delta += vcg::Barycenter(*fp) - v.cP();
746  }
747  delta /= faceVec.size();
748 
749  v.P() += delta * moveThreshold;
750  }
751  }
752 
753  UpdateSelection<MeshType>::Clear(tmpMesh);
754  Append<MeshType, MeshType>::MeshCopy(m, tmpMesh);
755  return selCnt;
756  }
757 
758 
759  // Auxiliary function for sorting the non manifold faces according to their area. Used in RemoveNonManifoldFace
760  struct CompareAreaFP {
761  bool operator ()(FacePointer const& f1, FacePointer const& f2) const {
762  return DoubleArea(*f1) < DoubleArea(*f2);
763  }
764  };
765 
767  static int RemoveNonManifoldFace(MeshType& m)
768  {
769  FaceIterator fi;
770  int count_fd = 0;
771  std::vector<FacePointer> ToDelVec;
772 
773  for(fi=m.face.begin(); fi!=m.face.end();++fi)
774  if (!fi->IsD())
775  {
776  if ((!IsManifold(*fi,0))||
777  (!IsManifold(*fi,1))||
778  (!IsManifold(*fi,2)))
779  ToDelVec.push_back(&*fi);
780  }
781 
782  std::sort(ToDelVec.begin(),ToDelVec.end(),CompareAreaFP());
783 
784  for(size_t i=0;i<ToDelVec.size();++i)
785  {
786  if(!ToDelVec[i]->IsD())
787  {
788  FaceType &ff= *ToDelVec[i];
789  if ((!IsManifold(ff,0))||
790  (!IsManifold(ff,1))||
791  (!IsManifold(ff,2)))
792  {
793  for(int j=0;j<3;++j)
794  if(!face::IsBorder<FaceType>(ff,j))
795  vcg::face::FFDetach<FaceType>(ff,j);
796 
797  Allocator<MeshType>::DeleteFace(m,ff);
798  count_fd++;
799  }
800  }
801  }
802  return count_fd;
803  }
804 
805  /* Remove the faces that are out of a given range of area */
806  static int RemoveFaceOutOfRangeArea(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)(), bool OnlyOnSelected=false)
807  {
808  int count_fd = 0;
809  MinAreaThr*=2;
810  MaxAreaThr*=2;
811  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi){
812  if(!(*fi).IsD())
813  if(!OnlyOnSelected || (*fi).IsS())
814  {
815  const ScalarType doubleArea=DoubleArea<FaceType>(*fi);
816  if((doubleArea<=MinAreaThr) || (doubleArea>=MaxAreaThr) )
817  {
818  Allocator<MeshType>::DeleteFace(m,*fi);
819  count_fd++;
820  }
821  }
822  }
823  return count_fd;
824  }
825 
826  static int RemoveZeroAreaFace(MeshType& m) { return RemoveFaceOutOfRangeArea(m,0);}
827 
828 
829 
833  static bool IsBitQuadOnly(const MeshType &m)
834  {
835  typedef typename MeshType::FaceType F;
836  tri::RequirePerFaceFlags(m);
837  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
838  unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
839  if ( tmp != F::FAUX0 && tmp != F::FAUX1 && tmp != F::FAUX2) return false;
840  }
841  return true;
842  }
843 
844 
845  static bool IsFaceFauxConsistent(MeshType &m)
846  {
847  RequirePerFaceFlags(m);
848  RequireFFAdjacency(m);
849  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
850  {
851  for(int z=0;z<(*fi).VN();++z)
852  {
853  FacePointer fp = fi->FFp(z);
854  int zp = fi->FFi(z);
855  if(fi->IsF(z) != fp->IsF(zp)) return false;
856  }
857  }
858  return true;
859  }
860 
864  static bool IsBitTriOnly(const MeshType &m)
865  {
866  tri::RequirePerFaceFlags(m);
867  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) {
868  if ( !fi->IsD() && fi->IsAnyF() ) return false;
869  }
870  return true;
871  }
872 
873  static bool IsBitPolygonal(const MeshType &m){
874  return !IsBitTriOnly(m);
875  }
876 
881  static bool IsBitTriQuadOnly(const MeshType &m)
882  {
883  tri::RequirePerFaceFlags(m);
884  typedef typename MeshType::FaceType F;
885  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
886  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
887  if ( tmp!=F::FAUX0 && tmp!=F::FAUX1 && tmp!=F::FAUX2 && tmp!=0 ) return false;
888  }
889  return true;
890  }
891 
896  static int CountBitQuads(const MeshType &m)
897  {
898  tri::RequirePerFaceFlags(m);
899  typedef typename MeshType::FaceType F;
900  int count=0;
901  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
902  unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
903  if ( tmp==F::FAUX0 || tmp==F::FAUX1 || tmp==F::FAUX2) count++;
904  }
905  return count / 2;
906  }
907 
911  static int CountBitTris(const MeshType &m)
912  {
913  tri::RequirePerFaceFlags(m);
914  int count=0;
915  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
916  if (!(fi->IsAnyF())) count++;
917  }
918  return count;
919  }
920 
925  static int CountBitPolygons(const MeshType &m)
926  {
927  tri::RequirePerFaceFlags(m);
928  int count = 0;
929  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
930  if (fi->IsF(0)) count++;
931  if (fi->IsF(1)) count++;
932  if (fi->IsF(2)) count++;
933  }
934  return m.fn - count/2;
935  }
936 
948  static int CountBitLargePolygons(const MeshType &m)
949  {
950  //note - using unordered_map to set visited vertices because
951  //the mesh is const (before, the function used vertex flags...).
952  //could be used std::vector<bool> if the vertex has the Index()
953  //member function...
954  std::unordered_map<ConstVertexPointer, bool> vertVisited;
955  for (ConstVertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
956  if (!vi->IsD()) vertVisited[&(*vi)] = true;
957 
958  // First loop Clear all referenced vertices
959  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
960  if (!fi->IsD())
961  for(int i=0;i<3;++i){
962  vertVisited[fi->V(i)] = false;
963  }
964 
965 
966  // Second Loop, count (twice) faux edges and mark all vertices touched by non faux edges
967  // (e.g vertexes on the boundary of a polygon)
968  int countE = 0;
969  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
970  if (!fi->IsD()) {
971  for(int i=0;i<3;++i)
972  {
973  if (fi->IsF(i))
974  countE++;
975  else
976  {
977  vertVisited[fi->V0(i)] = true;
978  vertVisited[fi->V1(i)] = true;
979  }
980  }
981  }
982  // Third Loop, count the number of referenced vertexes that are completely surrounded by faux edges.
983 
984  int countV = 0;
985  for (ConstVertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
986  if (!vi->IsD() && !(vertVisited[&(*vi)])) countV++;
987 
988  return m.fn - countE/2 + countV ;
989  }
990 
991 
999  static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
1000  {
1001  RequireFFAdjacency(m);
1002  RequirePerFaceFlags(m);
1003 
1004  for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1005  if(!(*fi).IsD())
1006  for (int k=0; k<3; k++)
1007  if( ( fi->IsF(k) != fi->cFFp(k)->IsF(fi->cFFi(k)) ) ||
1008  ( fi->IsF(k) && face::IsBorder(*fi,k)) )
1009  {
1010  return false;
1011  }
1012  return true;
1013  }
1014 
1019  static int CountNonManifoldEdgeEE( MeshType & m, bool SelectFlag=false)
1020  {
1021  MeshAssert<MeshType>::OnlyEdgeMesh(m);
1022  RequireEEAdjacency(m);
1023  tri::UpdateTopology<MeshType>::EdgeEdge(m);
1024 
1025  if(SelectFlag) UpdateSelection<MeshType>::VertexClear(m);
1026 
1027  int nonManifoldCnt=0;
1028  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
1029 
1030  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
1031  EdgeIterator ei;
1032  for (ei = m.edge.begin(); ei != m.edge.end(); ++ei) if (!ei->IsD())
1033  {
1034  TD[(*ei).V(0)]++;
1035  TD[(*ei).V(1)]++;
1036  }
1037 
1038  tri::UpdateFlags<MeshType>::VertexClearV(m);
1039  // Second Loop, Check that each vertex have been seen 1 or 2 times.
1040  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if (!vi->IsD())
1041  {
1042  if( TD[vi] >2 )
1043  {
1044  if(SelectFlag) (*vi).SetS();
1045  nonManifoldCnt++;
1046  }
1047  }
1048  return nonManifoldCnt;
1049  }
1050 
1057  static int CountNonManifoldEdgeFF( MeshType & m, bool SelectFlag=false)
1058  {
1059  RequireFFAdjacency(m);
1060  int nmfBit[3];
1061  nmfBit[0]= FaceType::NewBitFlag();
1062  nmfBit[1]= FaceType::NewBitFlag();
1063  nmfBit[2]= FaceType::NewBitFlag();
1064 
1065 
1066  UpdateFlags<MeshType>::FaceClear(m,nmfBit[0]+nmfBit[1]+nmfBit[2]);
1067 
1068  if(SelectFlag){
1069  UpdateSelection<MeshType>::VertexClear(m);
1070  UpdateSelection<MeshType>::FaceClear(m);
1071  }
1072 
1073  int edgeCnt = 0;
1074  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1075  {
1076  if (!fi->IsD())
1077  {
1078  for(int i=0;i<3;++i)
1079  if(!IsManifold(*fi,i))
1080  {
1081  if(!(*fi).IsUserBit(nmfBit[i]))
1082  {
1083  ++edgeCnt;
1084  if(SelectFlag)
1085  {
1086  (*fi).V0(i)->SetS();
1087  (*fi).V1(i)->SetS();
1088  }
1089  // follow the ring of faces incident on edge i;
1090  face::Pos<FaceType> nmf(&*fi,i);
1091  do
1092  {
1093  if(SelectFlag) nmf.F()->SetS();
1094  nmf.F()->SetUserBit(nmfBit[nmf.E()]);
1095  nmf.NextF();
1096  }
1097  while(nmf.f != &*fi);
1098  }
1099  }
1100  }
1101  }
1102  return edgeCnt;
1103  }
1104 
1109  static int CountNonManifoldVertexFF( MeshType & m, bool selectVert = true, bool clearSelection = true)
1110  {
1111  RequireFFAdjacency(m);
1112  if(selectVert && clearSelection) UpdateSelection<MeshType>::VertexClear(m);
1113 
1114  int nonManifoldCnt=0;
1115  SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
1116 
1117  // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
1118  FaceIterator fi;
1119  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1120  {
1121  for (int k=0; k<fi->VN(); k++)
1122  {
1123  TD[(*fi).V(k)]++;
1124  }
1125  }
1126 
1127  tri::UpdateFlags<MeshType>::VertexClearV(m);
1128  // Second Loop.
1129  // mark out of the game the vertexes that are incident on non manifold edges.
1130  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1131  {
1132  for(int i=0; i<fi->VN(); ++i)
1133  if (!IsManifold(*fi,i))
1134  {
1135  (*fi).V0(i)->SetV();
1136  (*fi).V1(i)->SetV();
1137  }
1138  }
1139  // Third Loop, for safe vertexes, check that the number of faces that you can reach starting
1140  // from it and using FF is the same of the previously counted.
1141  for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1142  {
1143  for(int i=0; i<fi->VN(); i++) if (!(*fi).V(i)->IsV())
1144  {
1145  (*fi).V(i)->SetV();
1146  face::Pos<FaceType> pos(&(*fi),i);
1147 
1148  int starSizeFF = pos.NumberOfIncidentFaces();
1149 
1150  if (starSizeFF != TD[(*fi).V(i)])
1151  {
1152  if (selectVert)
1153  (*fi).V(i)->SetS();
1154  nonManifoldCnt++;
1155  }
1156  }
1157  }
1158  return nonManifoldCnt;
1159  }
1167  static bool IsWaterTight(MeshType & m)
1168  {
1169  int edgeNum=0,edgeBorderNum=0,edgeNonManifNum=0;
1170  CountEdgeNum(m, edgeNum, edgeBorderNum,edgeNonManifNum);
1171  return (edgeBorderNum==0) && (edgeNonManifNum==0);
1172  }
1173 
1174  static void CountEdgeNum( MeshType & m, int &total_e, int &boundary_e, int &non_manif_e )
1175  {
1176  std::vector< typename tri::UpdateTopology<MeshType>::PEdge > edgeVec;
1177  tri::UpdateTopology<MeshType>::FillEdgeVector(m,edgeVec,true);
1178  sort(edgeVec.begin(), edgeVec.end()); // Lo ordino per vertici
1179  total_e=0;
1180  boundary_e=0;
1181  non_manif_e=0;
1182 
1183  size_t f_on_cur_edge =1;
1184  for(size_t i=0;i<edgeVec.size();++i)
1185  {
1186  if(( (i+1) == edgeVec.size()) || !(edgeVec[i] == edgeVec[i+1]))
1187  {
1188  ++total_e;
1189  if(f_on_cur_edge==1)
1190  ++boundary_e;
1191  if(f_on_cur_edge>2)
1192  ++non_manif_e;
1193  f_on_cur_edge=1;
1194  }
1195  else
1196  {
1197  ++f_on_cur_edge;
1198  }
1199  } // end for
1200  }
1201 
1202 
1203 
1204  static int CountHoles( MeshType & m)
1205  {
1206  UpdateFlags<MeshType>::FaceClearV(m);
1207  int loopNum=0;
1208  for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD())
1209  {
1210  for(int j=0;j<3;++j)
1211  {
1212  if(!fi->IsV() && face::IsBorder(*fi,j))
1213  {
1214  face::Pos<FaceType> startPos(&*fi,j);
1215  face::Pos<FaceType> curPos=startPos;
1216  do
1217  {
1218  curPos.NextB();
1219  curPos.F()->SetV();
1220  }
1221  while(curPos!=startPos);
1222  ++loopNum;
1223  }
1224  }
1225  }
1226  return loopNum;
1227  }
1228 
1229  /*
1230  Compute the set of connected components of a given mesh
1231  it fills a vector of pair < int , faceptr > with, for each connecteed component its size and a represnant
1232  */
1233  static int CountConnectedComponents(MeshType &m)
1234  {
1235  std::vector< std::pair<int,FacePointer> > CCV;
1236  return ConnectedComponents(m,CCV);
1237  }
1238 
1239  static int ConnectedComponents(MeshType &m, std::vector< std::pair<int,FacePointer> > &CCV)
1240  {
1241  tri::RequireFFAdjacency(m);
1242  CCV.clear();
1243  tri::UpdateFlags<MeshType>::FaceClearV(m);
1244  std::stack<FacePointer> sf;
1245  FacePointer fpt=&*(m.face.begin());
1246  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1247  {
1248  if(!((*fi).IsD()) && !(*fi).IsV())
1249  {
1250  (*fi).SetV();
1251  CCV.push_back(std::make_pair(0,&*fi));
1252  sf.push(&*fi);
1253  while (!sf.empty())
1254  {
1255  fpt=sf.top();
1256  ++CCV.back().first;
1257  sf.pop();
1258  for(int j=0; j<fpt->VN(); ++j)
1259  {
1260  if( !face::IsBorder(*fpt,j) )
1261  {
1262  FacePointer l = fpt->FFp(j);
1263  if( !(*l).IsV() )
1264  {
1265  (*l).SetV();
1266  sf.push(l);
1267  }
1268  }
1269  }
1270  }
1271  }
1272  }
1273  return int(CCV.size());
1274  }
1275 
1276  static int edgeMeshConnectedComponents(MeshType & poly, std::vector<std::pair<int, typename MeshType::EdgePointer> > &eCC)
1277  {
1278  typedef typename MeshType::EdgePointer EdgePointer;
1279  tri::UpdateTopology<MeshType>::VertexEdge(poly);
1280  tri::UpdateFlags<MeshType>::EdgeClear(poly);
1281  eCC.clear();
1282  std::stack<EdgePointer> stack;
1283 
1284  for (auto ei = poly.edge.begin(); ei != poly.edge.end(); ++ei)
1285  if (!ei->IsD() && !ei->IsV())
1286  {
1287  ei->SetV();
1288 
1289  std::pair<int, EdgePointer> cc(1, &*ei);
1290 
1291  stack.push(&*ei);
1292  while (!stack.empty())
1293  {
1294  EdgePointer ep = stack.top();
1295  stack.pop();
1296 
1297  for (int i = 0; i < 2; ++i)
1298  {
1299  edge::VEIterator<typename MeshType::EdgeType> vei(ep->V(i));
1300  while (!vei.End())
1301  {
1302  if (!vei.E()->IsV())
1303  {
1304  vei.E()->SetV();
1305  stack.push(vei.E());
1306  cc.first += 1;
1307  }
1308  ++vei;
1309  }
1310  }
1311  }
1312  eCC.push_back(cc);
1313  }
1314  return int(eCC.size());
1315  }
1316 
1317  static void ComputeValence( MeshType &m, typename MeshType::PerVertexIntHandle &h)
1318  {
1319  for(VertexIterator vi=m.vert.begin(); vi!= m.vert.end();++vi)
1320  h[vi]=0;
1321 
1322  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1323  {
1324  if(!((*fi).IsD()))
1325  for(int j=0;j<fi->VN();j++)
1326  ++h[tri::Index(m,fi->V(j))];
1327  }
1328  }
1329 
1365  static int MeshGenus(int nvert,int nedges,int nfaces, int numholes, int numcomponents)
1366  {
1367  return -((nvert + nfaces - nedges + numholes - 2 * numcomponents) / 2);
1368  }
1369 
1370  static int MeshGenus(MeshType &m)
1371  {
1372  int nvert=m.vn;
1373  int nfaces=m.fn;
1374  int boundary_e,total_e,nonmanif_e;
1375  CountEdgeNum(m,total_e,boundary_e,nonmanif_e);
1376  int numholes=CountHoles(m);
1377  int numcomponents=CountConnectedComponents(m);
1378  int G=MeshGenus(nvert,total_e,nfaces,numholes,numcomponents);
1379  return G;
1380  }
1381 
1393  static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular)
1394  {
1395  RequireVFAdjacency(m);
1396  Regular = true;
1397 
1398  VertexIterator vi;
1399 
1400  // for each vertex the number of edges are count
1401  for (vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1402  {
1403  if (!vi->IsD())
1404  {
1405  face::Pos<FaceType> he((*vi).VFp(), &*vi);
1406  face::Pos<FaceType> ht = he;
1407 
1408  int n=0;
1409  bool border=false;
1410  do
1411  {
1412  ++n;
1413  ht.NextE();
1414  if (ht.IsBorder())
1415  border=true;
1416  }
1417  while (ht != he);
1418 
1419  if (border)
1420  n = n/2;
1421 
1422  if ((n != 6)&&(!border && n != 4))
1423  {
1424  Regular = false;
1425  break;
1426  }
1427  }
1428  }
1429 
1430  if (!Regular)
1431  Semiregular = false;
1432  else
1433  {
1434  // For now we do not account for semi-regularity
1435  Semiregular = false;
1436  }
1437  }
1438 
1439 
1440  static bool IsCoherentlyOrientedMesh(MeshType &m)
1441  {
1442  RequireFFAdjacency(m);
1443  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1444  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1445  if (!fi->IsD())
1446  for(int i=0;i<3;++i)
1447  if(!face::CheckOrientation(*fi,i))
1448  return false;
1449 
1450  return true;
1451  }
1452 
1453  static void OrientCoherentlyMesh(MeshType &m, bool &_IsOriented, bool &_IsOrientable)
1454  {
1455  RequireFFAdjacency(m);
1456  MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1457  bool IsOrientable = true;
1458  bool IsOriented = true;
1459 
1460  UpdateFlags<MeshType>::FaceClearV(m);
1461  std::stack<FacePointer> faces;
1462  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1463  {
1464  if (!fi->IsD() && !fi->IsV())
1465  {
1466  // each face put in the stack is selected (and oriented)
1467  fi->SetV();
1468  faces.push(&(*fi));
1469  while (!faces.empty())
1470  {
1471  FacePointer fp = faces.top();
1472  faces.pop();
1473 
1474  // make consistently oriented the adjacent faces
1475  for (int j = 0; j < 3; j++)
1476  {
1477  if (!face::IsBorder(*fp,j) && face::IsManifold<FaceType>(*fp, j))
1478  {
1479  FacePointer fpaux = fp->FFp(j);
1480  int iaux = fp->FFi(j);
1481  if (!CheckOrientation(*fpaux, iaux))
1482  {
1483  IsOriented = false;
1484 
1485  if (!fpaux->IsV())
1486  face::SwapEdge<FaceType,true>(*fpaux, iaux);
1487  else
1488  {
1489  IsOrientable = false;
1490  break;
1491  }
1492  }
1493  if (!fpaux->IsV())
1494  {
1495  fpaux->SetV();
1496  faces.push(fpaux);
1497  }
1498  }
1499  }
1500  }
1501  }
1502  if (!IsOrientable) break;
1503  }
1504  _IsOriented = IsOriented;
1505  _IsOrientable = IsOrientable;
1506  }
1507 
1508 
1510  static void FlipMesh(MeshType &m, bool selected=false)
1511  {
1512  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if(!(*fi).IsD())
1513  if(!selected || (*fi).IsS())
1514  {
1515  face::SwapEdge<FaceType,false>((*fi), 0);
1516  if (HasPerWedgeTexCoord(m))
1517  std::swap((*fi).WT(0),(*fi).WT(1));
1518  }
1519  }
1525  static bool FlipNormalOutside(MeshType &m)
1526  {
1527  if(m.vert.empty()) return false;
1528 
1529  tri::UpdateNormal<MeshType>::PerVertexAngleWeighted(m);
1530  tri::UpdateNormal<MeshType>::NormalizePerVertex(m);
1531 
1532  std::vector< VertexPointer > minVertVec;
1533  std::vector< VertexPointer > maxVertVec;
1534 
1535  // The set of directions to be chosen
1536  std::vector< CoordType > dirVec;
1537  dirVec.push_back(CoordType(1,0,0));
1538  dirVec.push_back(CoordType(0,1,0));
1539  dirVec.push_back(CoordType(0,0,1));
1540  dirVec.push_back(CoordType( 1, 1,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  for(size_t i=0;i<dirVec.size();++i)
1545  {
1546  Normalize(dirVec[i]);
1547  minVertVec.push_back(&*m.vert.begin());
1548  maxVertVec.push_back(&*m.vert.begin());
1549  }
1550  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if(!(*vi).IsD())
1551  {
1552  for(size_t i=0;i<dirVec.size();++i)
1553  {
1554  if( (*vi).cP().dot(dirVec[i]) < minVertVec[i]->P().dot(dirVec[i])) minVertVec[i] = &*vi;
1555  if( (*vi).cP().dot(dirVec[i]) > maxVertVec[i]->P().dot(dirVec[i])) maxVertVec[i] = &*vi;
1556  }
1557  }
1558 
1559  int voteCount=0;
1560  ScalarType angleThreshold = cos(math::ToRad(85.0));
1561  for(size_t i=0;i<dirVec.size();++i)
1562  {
1563  // 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]);
1564  // 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]);
1565  if(minVertVec[i]->N().dot(dirVec[i]) > angleThreshold ) voteCount++;
1566  if(maxVertVec[i]->N().dot(dirVec[i]) < -angleThreshold ) voteCount++;
1567  }
1568  // qDebug("votecount = %i",voteCount);
1569  if(voteCount < int(dirVec.size())/2) return false;
1570  FlipMesh(m);
1571  return true;
1572  }
1573 
1574  // Search and remove small single triangle folds
1575  // - a face has normal opposite to all other faces
1576  // - choose the edge that brings to the face f1 containing the vertex opposite to that edge.
1577  static int RemoveFaceFoldByFlip(MeshType &m, float normalThresholdDeg=175, bool repeat=true)
1578  {
1579  RequireFFAdjacency(m);
1580  RequirePerVertexMark(m);
1581  //Counters for logging and convergence
1582  int count, total = 0;
1583 
1584  do {
1585  tri::UpdateTopology<MeshType>::FaceFace(m);
1586  tri::UnMarkAll(m);
1587  count = 0;
1588 
1589  ScalarType NormalThrRad = math::ToRad(normalThresholdDeg);
1590  ScalarType eps = ScalarType(0.0001); // this epsilon value is in absolute value. It is a distance from edge in baricentric coords.
1591  //detection stage
1592  for(FaceIterator fi=m.face.begin();fi!= m.face.end();++fi ) if(!(*fi).IsV())
1593  { Point3<ScalarType> NN = vcg::TriangleNormal((*fi)).Normalize();
1594  if( vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(0)).Normalize()) > NormalThrRad &&
1595  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(1)).Normalize()) > NormalThrRad &&
1596  vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(2)).Normalize()) > NormalThrRad )
1597  {
1598  (*fi).SetS();
1599  //(*fi).C()=Color4b(Color4b::Red);
1600  // now search the best edge to flip
1601  for(int i=0;i<3;i++)
1602  {
1603  Point3<ScalarType> &p=(*fi).P2(i);
1604  Point3<ScalarType> L;
1605  bool ret = vcg::InterpolationParameters((*(*fi).FFp(i)),TriangleNormal(*(*fi).FFp(i)),p,L);
1606  if(ret && L[0]>eps && L[1]>eps && L[2]>eps)
1607  {
1608  (*fi).FFp(i)->SetS();
1609  (*fi).FFp(i)->SetV();
1610  //(*fi).FFp(i)->C()=Color4b(Color4b::Green);
1611  if(face::CheckFlipEdge<FaceType>( *fi, i )) {
1612  face::FlipEdge<FaceType>( *fi, i );
1613  ++count; ++total;
1614  }
1615  }
1616  }
1617  }
1618  }
1619 
1620  // tri::UpdateNormal<MeshType>::PerFace(m);
1621  }
1622  while( repeat && count );
1623  return total;
1624  }
1625 
1626 
1627  static int RemoveTVertexByFlip(MeshType &m, float threshold=40, bool repeat=true)
1628  {
1629  RequireFFAdjacency(m);
1630  RequirePerVertexMark(m);
1631  //Counters for logging and convergence
1632  int count, total = 0;
1633 
1634  do {
1635  tri::UpdateTopology<MeshType>::FaceFace(m);
1636  tri::UnMarkAll(m);
1637  count = 0;
1638 
1639  //detection stage
1640  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1641  {
1642  FacePointer f = &(m.face[index]); float sides[3]; CoordType dummy;
1643  sides[0] = Distance(f->P(0), f->P(1));
1644  sides[1] = Distance(f->P(1), f->P(2));
1645  sides[2] = Distance(f->P(2), f->P(0));
1646  // Find largest triangle side
1647  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1648  if( tri::IsMarked(m,f->V2(i) )) continue;
1649 
1650  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1651  {
1652  tri::Mark(m,f->V2(i));
1653  if(face::CheckFlipEdge<FaceType>( *f, i )) {
1654  // Check if EdgeFlipping improves quality
1655  FacePointer g = f->FFp(i); int k = f->FFi(i);
1656  Triangle3<ScalarType> t1(f->P(i), f->P1(i), f->P2(i)), t2(g->P(k), g->P1(k), g->P2(k)),
1657  t3(f->P(i), g->P2(k), f->P2(i)), t4(g->P(k), f->P2(i), g->P2(k));
1658 
1659  if ( std::min( QualityFace(t1), QualityFace(t2) ) < std::min( QualityFace(t3), QualityFace(t4) ))
1660  {
1661  face::FlipEdge<FaceType>( *f, i );
1662  ++count; ++total;
1663  }
1664  }
1665 
1666  }
1667  }
1668 
1669  // tri::UpdateNormal<MeshType>::PerFace(m);
1670  }
1671  while( repeat && count );
1672  return total;
1673  }
1674 
1675  static int RemoveTVertexByCollapse(MeshType &m, float threshold=40, bool repeat=true)
1676  {
1677  RequirePerVertexMark(m);
1678  //Counters for logging and convergence
1679  int count, total = 0;
1680 
1681  do {
1682  tri::UnMarkAll(m);
1683  count = 0;
1684 
1685  //detection stage
1686  for(unsigned int index = 0 ; index < m.face.size(); ++index )
1687  {
1688  FacePointer f = &(m.face[index]);
1689  float sides[3];
1690  CoordType dummy;
1691 
1692  sides[0] = Distance(f->P(0), f->P(1));
1693  sides[1] = Distance(f->P(1), f->P(2));
1694  sides[2] = Distance(f->P(2), f->P(0));
1695  int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1696  if( tri::IsMarked(m,f->V2(i) )) continue;
1697 
1698  if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1699  {
1700  tri::Mark(m,f->V2(i));
1701 
1702  int j = Distance(dummy,f->P(i))<Distance(dummy,f->P1(i))?i:(i+1)%3;
1703  f->P2(i) = f->P(j); tri::Mark(m,f->V(j));
1704  ++count; ++total;
1705  }
1706  }
1707 
1708 
1709  tri::Clean<MeshType>::RemoveDuplicateVertex(m);
1710  tri::Allocator<MeshType>::CompactFaceVector(m);
1711  tri::Allocator<MeshType>::CompactVertexVector(m);
1712  }
1713  while( repeat && count );
1714 
1715  return total;
1716  }
1717 
1718  static bool SelfIntersections(MeshType &m, std::vector<FaceType*> &ret)
1719  {
1720  RequirePerFaceMark(m);
1721  ret.clear();
1722  int referredBit = FaceType::NewBitFlag();
1723  tri::UpdateFlags<MeshType>::FaceClear(m,referredBit);
1724 
1725  TriMeshGrid gM;
1726  gM.Set(m.face.begin(),m.face.end());
1727 
1728  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
1729  {
1730  (*fi).SetUserBit(referredBit);
1731  Box3< ScalarType> bbox;
1732  (*fi).GetBBox(bbox);
1733  std::vector<FaceType*> inBox;
1734  vcg::tri::GetInBoxFace(m, gM, bbox,inBox);
1735  bool Intersected=false;
1736  typename std::vector<FaceType*>::iterator fib;
1737  for(fib=inBox.begin();fib!=inBox.end();++fib)
1738  {
1739  if(!(*fib)->IsUserBit(referredBit) && (*fib != &*fi) )
1740  if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){
1741  ret.push_back(*fib);
1742  if(!Intersected) {
1743  ret.push_back(&*fi);
1744  Intersected=true;
1745  }
1746  }
1747  }
1748  inBox.clear();
1749  }
1750 
1751  FaceType::DeleteBitFlag(referredBit);
1752  return (ret.size()>0);
1753  }
1754 
1758  static bool IsSizeConsistent(MeshType &m)
1759  {
1760  int DeletedVertNum=0;
1761  for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1762  if((*vi).IsD()) DeletedVertNum++;
1763 
1764  int DeletedEdgeNum=0;
1765  for (EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei)
1766  if((*ei).IsD()) DeletedEdgeNum++;
1767 
1768  int DeletedFaceNum=0;
1769  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1770  if((*fi).IsD()) DeletedFaceNum++;
1771 
1772  if(size_t(m.vn+DeletedVertNum) != m.vert.size()) return false;
1773  if(size_t(m.en+DeletedEdgeNum) != m.edge.size()) return false;
1774  if(size_t(m.fn+DeletedFaceNum) != m.face.size()) return false;
1775 
1776  return true;
1777  }
1778 
1783  static bool IsFFAdjacencyConsistent(MeshType &m)
1784  {
1785  RequireFFAdjacency(m);
1786 
1787  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1788  if(!(*fi).IsD())
1789  {
1790  for(int i=0;i<3;++i)
1791  if(!FFCorrectness(*fi, i)) return false;
1792  }
1793  return true;
1794  }
1795 
1799  static bool HasConsistentPerWedgeTexCoord(MeshType &m)
1800  {
1801  tri::RequirePerFaceWedgeTexCoord(m);
1802 
1803  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1804  if(!(*fi).IsD())
1805  { FaceType &f=(*fi);
1806  if( ! ( (f.WT(0).N() == f.WT(1).N()) && (f.WT(0).N() == (*fi).WT(2).N()) ) )
1807  return false; // all the vertices must have the same index.
1808 
1809  if((*fi).WT(0).N() <0) return false; // no undefined texture should be allowed
1810  }
1811  return true;
1812  }
1813 
1817  static bool HasZeroTexCoordFace(MeshType &m)
1818  {
1819  tri::RequirePerFaceWedgeTexCoord(m);
1820 
1821  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1822  if(!(*fi).IsD())
1823  {
1824  if( (*fi).WT(0).P() == (*fi).WT(1).P() && (*fi).WT(0).P() == (*fi).WT(2).P() ) return false;
1825  }
1826  return true;
1827  }
1828 
1829 
1837  static bool TestFaceFaceIntersection(FaceType *f0,FaceType *f1)
1838  {
1839  int sv = face::CountSharedVertex(f0,f1);
1840  if(sv==3) return true;
1841  if(sv==0) return (vcg::IntersectionTriangleTriangle<FaceType>((*f0),(*f1)));
1842  // if the faces share only a vertex, the opposite edge (as a segment) is tested against the face
1843  // to avoid degenerate cases where the two triangles have the opposite edge on a common plane
1844  // we offset the segment to test toward the shared vertex
1845  if(sv==1)
1846  {
1847  int i0,i1; ScalarType a,b;
1848  face::FindSharedVertex(f0,f1,i0,i1);
1849  CoordType shP = f0->V(i0)->P()*0.5;
1850  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f0).V1(i0)->P()*0.5+shP,(*f0).V2(i0)->P()*0.5+shP), *f1, a, b) )
1851  {
1852  // a,b are the param coords of the intersection point of the segment.
1853  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1854  return true;
1855  }
1856  if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f1).V1(i1)->P()*0.5+shP,(*f1).V2(i1)->P()*0.5+shP), *f0, a, b) )
1857  {
1858  // a,b are the param coords of the intersection point of the segment.
1859  if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
1860  return true;
1861  }
1862 
1863  }
1864  return false;
1865  }
1866 
1867 
1868 
1872  static int MergeCloseVertex(MeshType &m, const ScalarType radius)
1873  {
1874  int mergedCnt=0;
1875  mergedCnt = ClusterVertex(m,radius);
1876  RemoveDuplicateVertex(m,true);
1877  return mergedCnt;
1878  }
1879 
1880  static int ClusterVertex(MeshType &m, const ScalarType radius)
1881  {
1882  if(m.vn==0) return 0;
1883  // some spatial indexing structure does not work well with deleted vertices...
1884  tri::Allocator<MeshType>::CompactVertexVector(m);
1885  typedef vcg::SpatialHashTable<VertexType, ScalarType> SampleSHT;
1886  SampleSHT sht;
1887  tri::EmptyTMark<MeshType> markerFunctor;
1888  std::vector<VertexType*> closests;
1889  int mergedCnt=0;
1890  sht.Set(m.vert.begin(), m.vert.end());
1891  UpdateFlags<MeshType>::VertexClearV(m);
1892  for(VertexIterator viv = m.vert.begin(); viv!= m.vert.end(); ++viv)
1893  if(!(*viv).IsD() && !(*viv).IsV())
1894  {
1895  (*viv).SetV();
1896  Point3<ScalarType> p = viv->cP();
1897  Box3<ScalarType> bb(p-Point3<ScalarType>(radius,radius,radius),p+Point3<ScalarType>(radius,radius,radius));
1898  GridGetInBox(sht, markerFunctor, bb, closests);
1899  // qDebug("Vertex %i has %i closest", &*viv - &*m.vert.begin(),closests.size());
1900  for(size_t i=0; i<closests.size(); ++i)
1901  {
1902  ScalarType dist = Distance(p,closests[i]->cP());
1903  if(dist < radius && !closests[i]->IsV())
1904  {
1905  // printf("%f %f \n",dist,radius);
1906  mergedCnt++;
1907  closests[i]->SetV();
1908  closests[i]->P()=p;
1909  }
1910  }
1911  }
1912  return mergedCnt;
1913  }
1914 
1915 
1916  static std::pair<int,int> RemoveSmallConnectedComponentsSize(MeshType &m, int maxCCSize)
1917  {
1918  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1919  int TotalCC=ConnectedComponents(m, CCV);
1920  int DeletedCC=0;
1921 
1922  ConnectedComponentIterator<MeshType> ci;
1923  for(unsigned int i=0;i<CCV.size();++i)
1924  {
1925  std::vector<typename MeshType::FacePointer> FPV;
1926  if(CCV[i].first<maxCCSize)
1927  {
1928  DeletedCC++;
1929  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1930  FPV.push_back(*ci);
1931 
1932  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1933  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1934  Allocator<MeshType>::DeleteFace(m,(**fpvi));
1935  }
1936  }
1937  return std::make_pair(TotalCC,DeletedCC);
1938  }
1939 
1940 
1942  // it returns a pair with the number of connected components and the number of deleted ones.
1943  static std::pair<int,int> RemoveSmallConnectedComponentsDiameter(MeshType &m, ScalarType maxDiameter)
1944  {
1945  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1946  int TotalCC=ConnectedComponents(m, CCV);
1947  int DeletedCC=0;
1948  tri::ConnectedComponentIterator<MeshType> ci;
1949  for(unsigned int i=0;i<CCV.size();++i)
1950  {
1951  Box3<ScalarType> bb;
1952  std::vector<typename MeshType::FacePointer> FPV;
1953  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1954  {
1955  FPV.push_back(*ci);
1956  bb.Add((*ci)->P(0));
1957  bb.Add((*ci)->P(1));
1958  bb.Add((*ci)->P(2));
1959  }
1960  if(bb.Diag()<maxDiameter)
1961  {
1962  DeletedCC++;
1963  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1964  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1965  tri::Allocator<MeshType>::DeleteFace(m,(**fpvi));
1966  }
1967  }
1968  return std::make_pair(TotalCC,DeletedCC);
1969  }
1970 
1972  // it returns a pair with the number of connected components and the number of deleted ones.
1973  static std::pair<int,int> RemoveHugeConnectedComponentsDiameter(MeshType &m, ScalarType minDiameter)
1974  {
1975  std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
1976  int TotalCC=ConnectedComponents(m, CCV);
1977  int DeletedCC=0;
1978  tri::ConnectedComponentIterator<MeshType> ci;
1979  for(unsigned int i=0;i<CCV.size();++i)
1980  {
1981  Box3f bb;
1982  std::vector<typename MeshType::FacePointer> FPV;
1983  for(ci.start(m,CCV[i].second);!ci.completed();++ci)
1984  {
1985  FPV.push_back(*ci);
1986  bb.Add((*ci)->P(0));
1987  bb.Add((*ci)->P(1));
1988  bb.Add((*ci)->P(2));
1989  }
1990  if(bb.Diag()>minDiameter)
1991  {
1992  DeletedCC++;
1993  typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
1994  for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
1995  tri::Allocator<MeshType>::DeleteFace(m,(**fpvi));
1996  }
1997  }
1998  return std::make_pair(TotalCC,DeletedCC);
1999  }
2000 
2001 
2002 
2009  static void SelectFoldedFaceFromOneRingFaces(MeshType &m, ScalarType cosThreshold)
2010  {
2011  typedef std::unordered_set<VertexPointer> VertexSet;
2012  tri::RequireVFAdjacency(m);
2013  tri::RequirePerFaceNormal(m);
2014  tri::RequirePerVertexNormal(m);
2015  vcg::tri::UpdateSelection<MeshType>::FaceClear(m);
2016  vcg::tri::UpdateNormal<MeshType>::PerFaceNormalized(m);
2017  vcg::tri::UpdateNormal<MeshType>::PerVertexNormalized(m);
2018  vcg::tri::UpdateTopology<MeshType>::VertexFace(m);
2019  if (cosThreshold > 0)
2020  cosThreshold = 0;
2021 
2022 #pragma omp parallel for schedule(dynamic, 10)
2023  for (int i = 0; i < m.face.size(); i++)
2024  {
2025  VertexSet nearVertex;
2026  std::vector<CoordType> pointVec;
2027  FacePointer f = &m.face[i];
2028  for (int j = 0; j < 3; j++)
2029  {
2030  std::vector<VertexPointer> temp;
2031  vcg::face::VVStarVF<FaceType>(f->V(j), temp);
2032  typename std::vector<VertexPointer>::iterator iter = temp.begin();
2033  for (; iter != temp.end(); iter++)
2034  {
2035  if ((*iter) != f->V1(j) && (*iter) != f->V2(j))
2036  {
2037  if (nearVertex.insert((*iter)).second)
2038  pointVec.push_back((*iter)->P());
2039  }
2040  }
2041  nearVertex.insert(f->V(j));
2042  pointVec.push_back(f->P(j));
2043  }
2044 
2045  if (pointVec.size() > 3)
2046  {
2047  vcg::Plane3<ScalarType> plane;
2048  vcg::FitPlaneToPointSet(pointVec, plane);
2049  float avgDot = 0;
2050  for (auto nvp : nearVertex)
2051  avgDot += plane.Direction().dot(nvp->N());
2052  avgDot /= nearVertex.size();
2053  typename MeshType::VertexType::NormalType normal;
2054  if (avgDot < 0)
2055  normal = -plane.Direction();
2056  else
2057  normal = plane.Direction();
2058  if (normal.dot(f->N()) < cosThreshold)
2059  f->SetS();
2060  }
2061  }
2062  }
2067  static int SelectIntersectingFaces(MeshType &m1, MeshType &m2)
2068  {
2069  RequirePerFaceMark(m2);
2070  RequireCompactness(m1);
2071  RequireCompactness(m2);
2072 
2073  tri::UpdateSelection<MeshType>::FaceClear(m1);
2074 
2075  TriMeshGrid gM;
2076  gM.Set(m2.face.begin(),m2.face.end());
2077  int selCnt=0;
2078  for(auto fi=m1.face.begin();fi!=m1.face.end();++fi)
2079  {
2080  Box3< ScalarType> bbox;
2081  (*fi).GetBBox(bbox);
2082  std::vector<FaceType*> inBox;
2083  vcg::tri::GetInBoxFace(m2, gM, bbox,inBox);
2084  for(auto fib=inBox.begin(); fib!=inBox.end(); ++fib)
2085  {
2086  if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){
2087  fi->SetS();
2088  ++selCnt;
2089  }
2090  }
2091  inBox.clear();
2092  }
2093  return selCnt;
2094  }
2095 
2096 }; // end class
2099 } //End Namespace Tri
2100 } // End Namespace vcg
2101 #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:476
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:2009
vcg::tri::Clean::FlipNormalOutside
static bool FlipNormalOutside(MeshType &m)
Definition: clean.h:1525
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:1758
vcg::tri::Clean::SelectIntersectingFaces
static int SelectIntersectingFaces(MeshType &m1, MeshType &m2)
Definition: clean.h:2067
vcg::tri::Clean::IsBitTriQuadOnly
static bool IsBitTriQuadOnly(const MeshType &m)
Definition: clean.h:881
vcg::tri::Clean::IsBitTriOnly
static bool IsBitTriOnly(const MeshType &m)
Definition: clean.h:864
vcg::tri::Clean::HasZeroTexCoordFace
static bool HasZeroTexCoordFace(MeshType &m)
Definition: clean.h:1817
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:1943
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:678
vcg::tri::Clean::IsBitQuadOnly
static bool IsBitQuadOnly(const MeshType &m)
Definition: clean.h:833
vcg::tri::Clean::CountNonManifoldEdgeEE
static int CountNonManifoldEdgeEE(MeshType &m, bool SelectFlag=false)
Definition: clean.h:1019
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:616
vcg::tri::Clean::MeshGenus
static int MeshGenus(int nvert, int nedges, int nfaces, int numholes, int numcomponents)
Definition: clean.h:1365
vcg::tri::Clean::CountBitLargePolygons
static int CountBitLargePolygons(const MeshType &m)
Definition: clean.h:948
vcg::tri::Clean::HasConsistentPerFaceFauxFlag
static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
Definition: clean.h:999
vcg::tri::Clean::HasConsistentPerWedgeTexCoord
static bool HasConsistentPerWedgeTexCoord(MeshType &m)
Definition: clean.h:1799
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:1973
vcg::tri::Clean::TestFaceFaceIntersection
static bool TestFaceFaceIntersection(FaceType *f0, FaceType *f1)
Definition: clean.h:1837
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:1510
vcg::tri::Clean::CountBitQuads
static int CountBitQuads(const MeshType &m)
Definition: clean.h:896
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:925
vcg::tri::Clean::IsWaterTight
static bool IsWaterTight(MeshType &m)
Definition: clean.h:1167
vcg::tri::Clean::CountBitTris
static int CountBitTris(const MeshType &m)
Definition: clean.h:911
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:1393
vcg::tri::Clean::CountNonManifoldEdgeFF
static int CountNonManifoldEdgeFF(MeshType &m, bool SelectFlag=false)
Definition: clean.h:1057
vcg::tri::Clean::RemoveNonManifoldFace
static int RemoveNonManifoldFace(MeshType &m)
Removal of faces that were incident on a non manifold edge.
Definition: clean.h:767
vcg::tri::Clean::MergeCloseVertex
static int MergeCloseVertex(MeshType &m, const ScalarType radius)
Definition: clean.h:1872
vcg::tri::Clean::CountNonManifoldVertexFF
static int CountNonManifoldVertexFF(MeshType &m, bool selectVert=true, bool clearSelection=true)
Definition: clean.h:1109
vcg::tri::Clean::IsFFAdjacencyConsistent
static bool IsFFAdjacencyConsistent(MeshType &m)
Definition: clean.h:1783
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:469
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:397
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:1261
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:383
vcg::face::FindSharedVertex
bool FindSharedVertex(FaceType *f0, FaceType *f1, int &i, int &j)
Definition: topology.h:1279
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:981
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:760
Generated by doxygen 1.9.1 on Fri Mar 24 2023 16:13:24