VCG Library
Loading...
Searching...
No Matches
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
38namespace vcg {
39namespace tri{
40
41template <class ConnectedEdgeMeshType>
42class EdgeConnectedComponentIterator
43{
44public:
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
56public:
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 }
98private:
99 std::stack<EdgePointer> se;
100 MeshType *mp;
101};
102
103template <class ConnectedMeshType>
104class ConnectedComponentIterator
105{
106public:
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
118public:
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 }
153private:
154 std::stack<FacePointer> sf;
155 MeshType *mp;
156};
157
158
160
163template <class CleanMeshType>
164class Clean
165{
166
167public:
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 // Where each merged vertex went, indexed by vertex; a vertex that stays is left null.
211 // This used to be a std::map holding every vertex, which on a triangle soup -- an STL
212 // file, where every vertex has twins -- made the merge several times slower than
213 // reading the file: 2.6 s against 0.6 s on a 2M-face STL. The result is unchanged.
214 std::vector<VertexPointer> mp(m.vert.size(), nullptr);
215 size_t i,j;
216 VertexIterator vi;
217 int deleted=0;
218 int k=0;
219 size_t num_vert = m.vert.size();
220 std::vector<VertexPointer> perm(num_vert);
221 for(vi=m.vert.begin(); vi!=m.vert.end(); ++vi, ++k)
222 perm[k] = &(*vi);
223
224 RemoveDuplicateVert_Compare c_obj;
225
226 std::sort(perm.begin(),perm.end(),c_obj);
227
228 j = 0;
229 i = j;
230 ++i;
231 for(;i!=num_vert;)
232 {
233 if( (! (*perm[i]).IsD()) &&
234 (! (*perm[j]).IsD()) &&
235 (*perm[i]).P() == (*perm[j]).cP() )
236 {
237 VertexPointer t = perm[i];
238 mp[tri::Index(m, t)] = perm[j];
239 ++i;
240 Allocator<MeshType>::DeleteVertex(m,*t);
241 deleted++;
242 }
243 else
244 {
245 j = i;
246 ++i;
247 }
248 }
249
250 for(FaceIterator fi = m.face.begin(); fi!=m.face.end(); ++fi)
251 if( !(*fi).IsD() )
252 for(k = 0; k < (*fi).VN(); ++k)
253 if( VertexPointer to = mp[tri::Index(m, (*fi).V(k))] )
254 (*fi).V(k) = to;
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( VertexPointer to = mp[tri::Index(m, (*ei).V(k))] )
260 (*ei).V(k) = to;
261
262 for (TetraIterator ti = m.tetra.begin(); ti != m.tetra.end(); ++ti)
263 if (!(*ti).IsD())
264 for (k = 0; k < 4; ++k)
265 if (VertexPointer to = mp[tri::Index(m, (*ti).V(k))])
266 (*ti).V(k) = to;
267
268 if(RemoveDegenerateFlag) RemoveDegenerateFace(m);
269 if(RemoveDegenerateFlag && m.en>0) {
270 RemoveDegenerateEdge(m);
271 RemoveDuplicateEdge(m);
272 }
273 return deleted;
274 }
275
276 class SortedPair
277 {
278 public:
279 SortedPair() {}
280 SortedPair(unsigned int v0, unsigned int v1, EdgePointer _fp)
281 {
282 v[0]=v0;v[1]=v1;
283 fp=_fp;
284 if(v[0]>v[1]) std::swap(v[0],v[1]);
285 }
286 bool operator < (const SortedPair &p) const
287 {
288 return (v[1]!=p.v[1])?(v[1]<p.v[1]):
289 (v[0]<p.v[0]); }
290
291 bool operator == (const SortedPair &s) const
292 {
293 if( (v[0]==s.v[0]) && (v[1]==s.v[1]) ) return true;
294 return false;
295 }
296
297 unsigned int v[2];
298 EdgePointer fp;
299 };
300 class SortedTriple
301 {
302 public:
303 SortedTriple() {}
304 SortedTriple(unsigned int v0, unsigned int v1, unsigned int v2,FacePointer _fp)
305 {
306 v[0]=v0;v[1]=v1;v[2]=v2;
307 fp=_fp;
308 std::sort(v,v+3);
309 }
310 bool operator < (const SortedTriple &p) const
311 {
312 return (v[2]!=p.v[2])?(v[2]<p.v[2]):
313 (v[1]!=p.v[1])?(v[1]<p.v[1]):
314 (v[0]<p.v[0]); }
315
316 bool operator == (const SortedTriple &s) const
317 {
318 if( (v[0]==s.v[0]) && (v[1]==s.v[1]) && (v[2]==s.v[2]) ) return true;
319 return false;
320 }
321
322 unsigned int v[3];
323 FacePointer fp;
324 };
325
326
332 static int RemoveDuplicateFace( MeshType & m) // V1.0
333 {
334 std::vector<SortedTriple> fvec;
335 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
336 if(!(*fi).IsD())
337 {
338 fvec.push_back(SortedTriple( tri::Index(m,(*fi).V(0)),
339 tri::Index(m,(*fi).V(1)),
340 tri::Index(m,(*fi).V(2)),
341 &*fi));
342 }
343 std::sort(fvec.begin(),fvec.end());
344 int total=0;
345 for(int i=0;i<int(fvec.size())-1;++i)
346 {
347 if(fvec[i]==fvec[i+1])
348 {
349 total++;
350 tri::Allocator<MeshType>::DeleteFace(m, *(fvec[i].fp) );
351 }
352 }
353 return total;
354 }
355
361 static int RemoveDuplicateEdge( MeshType & m) // V1.0
362 {
363 if (m.en==0) return 0;
364 std::vector<SortedPair> eVec;
365 for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
366 if(!(*ei).IsD())
367 {
368 eVec.push_back(SortedPair( tri::Index(m,(*ei).V(0)), tri::Index(m,(*ei).V(1)), &*ei));
369 }
370 std::sort(eVec.begin(),eVec.end());
371 int total=0;
372 for(int i=0;i<int(eVec.size())-1;++i)
373 {
374 if(eVec[i]==eVec[i+1])
375 {
376 total++;
377 tri::Allocator<MeshType>::DeleteEdge(m, *(eVec[i].fp) );
378 }
379 }
380 return total;
381 }
382
383 static int CountUnreferencedVertex( MeshType& m)
384 {
385 return RemoveUnreferencedVertex(m,false);
386 }
387
388
394 static int RemoveUnreferencedVertex( MeshType& m, bool DeleteVertexFlag=true) // V1.0
395 {
396 tri::RequirePerVertexFlags(m);
397
398 std::vector<bool> referredVec(m.vert.size(),false);
399 int deleted = 0;
400
401 for(auto fi = m.face.begin(); fi != m.face.end(); ++fi)
402 if( !(*fi).IsD() )
403 for(auto j=0; j < (*fi).VN(); ++j)
404 referredVec[tri::Index(m, (*fi).V(j))]=true;
405
406 for(auto ei=m.edge.begin();ei!=m.edge.end();++ei)
407 if( !(*ei).IsD() ){
408 referredVec[tri::Index(m, (*ei).V(0))]=true;
409 referredVec[tri::Index(m, (*ei).V(1))]=true;
410 }
411
412 for(auto ti=m.tetra.begin(); ti!=m.tetra.end();++ti)
413 if( !(*ti).IsD() ){
414 referredVec[tri::Index(m, (*ti).V(0))]=true;
415 referredVec[tri::Index(m, (*ti).V(1))]=true;
416 referredVec[tri::Index(m, (*ti).V(2))]=true;
417 referredVec[tri::Index(m, (*ti).V(3))]=true;
418 }
419
420
421 if(!DeleteVertexFlag)
422 return std::count(referredVec.begin(),referredVec.end(),false);
423
424 for(auto vi=m.vert.begin();vi!=m.vert.end();++vi)
425 if( (!(*vi).IsD()) && (!referredVec[tri::Index(m,*vi)]) )
426 {
427 Allocator<MeshType>::DeleteVertex(m,*vi);
428 ++deleted;
429 }
430 return deleted;
431 }
432
437 static int RemoveDegenerateVertex(MeshType& m, bool DeleteVertexFlag=true)
438 {
439 VertexIterator vi;
440 int count_vd = 0;
441
442 for(vi=m.vert.begin(); vi!=m.vert.end();++vi)
443 if(math::IsNAN( (*vi).P()[0]) ||
444 math::IsNAN( (*vi).P()[1]) ||
445 math::IsNAN( (*vi).P()[2]) )
446 {
447 count_vd++;
448 if (DeleteVertexFlag)
449 Allocator<MeshType>::DeleteVertex(m,*vi);
450 }
451
452 FaceIterator fi;
453 int count_fd = 0;
454
455 for(fi=m.face.begin(); fi!=m.face.end();++fi)
456 if(!(*fi).IsD())
457 if( (*fi).V(0)->IsD() ||
458 (*fi).V(1)->IsD() ||
459 (*fi).V(2)->IsD() )
460 {
461 count_fd++;
462 if (DeleteVertexFlag)
463 Allocator<MeshType>::DeleteFace(m,*fi);
464 }
465 (void)count_fd;
466 return count_vd;
467 }
468
477 static int RemoveDegenerateFace(MeshType& m, bool DeleteFacesFlag=true)
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 if (DeleteFacesFlag)
490 Allocator<MeshType>::DeleteFace(m,*fi);
491 }
492 }
493 return count_fd;
494 }
495
496 static int RemoveDegenerateEdge(MeshType& m, bool DeleteEdgesFlag=true)
497 {
498 int count_ed = 0;
499
500 for(EdgeIterator ei=m.edge.begin(); ei!=m.edge.end();++ei)
501 if(!(*ei).IsD())
502 {
503 if((*ei).V(0) == (*ei).V(1) )
504 {
505 count_ed++;
506 if (DeleteEdgesFlag)
507 Allocator<MeshType>::DeleteEdge(m,*ei);
508 }
509 }
510 return count_ed;
511 }
512
513 static int RemoveNonManifoldVertex(MeshType& m)
514 {
515 CountNonManifoldVertexFF(m,true);
516 tri::UpdateSelection<MeshType>::FaceFromVertexLoose(m);
517 int count_removed = 0;
518 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi)
519 if(!(*fi).IsD() && (*fi).IsS())
520 Allocator<MeshType>::DeleteFace(m,*fi);
521 for(VertexIterator vi=m.vert.begin(); vi!=m.vert.end();++vi)
522 if(!(*vi).IsD() && (*vi).IsS()) {
523 ++count_removed;
524 Allocator<MeshType>::DeleteVertex(m,*vi);
525 }
526 return count_removed;
527 }
528
529
530 static int SplitSelectedVertexOnEdgeMesh(MeshType& m)
531 {
532 tri::RequireCompactness(m);
533
534 // count selected vertices references
535 std::unordered_map<size_t,size_t> refCount; // selected vertex index -> reference count
536 size_t countSplit = 0;
537 for (size_t i=0; i<m.edge.size(); ++i)
538 {
539 for (int j=0; j<2; ++j)
540 {
541 const VertexPointer vp = m.edge[i].V(j);
542 if (vp->IsS())
543 {
544 const size_t refs = ++refCount[Index(m, m.edge[i].V(j))];
545 if (refs > 1) {
546 countSplit++;
547 }
548 }
549 }
550 }
551 // actual split
552 if (countSplit > 0)
553 {
554 auto newVertIt = tri::Allocator<MeshType>::AddVertices(m, countSplit);
555 for (size_t i=0; i<m.edge.size(); ++i)
556 {
557 for (int j=0; j<2; ++j)
558 {
559 const VertexPointer vp = m.edge[i].V(j);
560 const size_t vIdx = Index(m, vp);
561 if (vp->IsS())
562 {
563 if (--refCount[vIdx] > 0)
564 {
565 newVertIt->ImportData(*vp);
566 m.edge[i].V(j) = &*(newVertIt++);
567 }
568 }
569 }
570 }
571 }
572 return int(countSplit);
573 }
574
575
576 static void SelectNonManifoldVertexOnEdgeMesh(MeshType &m)
577 {
578 tri::RequireCompactness(m);
579 tri::UpdateSelection<MeshType>::VertexClear(m);
580 std::vector<int> cnt(m.vn,0);
581
582 for(size_t i=0;i<m.edge.size();++i)
583 {
584 cnt[tri::Index(m,m.edge[i].V(0))]++;
585 cnt[tri::Index(m,m.edge[i].V(1))]++;
586 }
587 for(size_t i=0;i<m.vert.size();++i)
588 if(cnt[i]>2) m.vert[i].SetS();
589 }
590
593 static void SelectCreaseVertexOnEdgeMeshEE(MeshType &m, ScalarType AngleRadThr)
594 {
595 tri::RequireCompactness(m);
596 tri::RequireEEAdjacency(m);
597 tri::UpdateTopology<MeshType>::EdgeEdge(m);
598 tri::UpdateSelection<MeshType>::VertexClear(m);
599 tri::UpdateFlags<MeshType>::VertexClearV(m);
600 for(size_t i=0;i<m.edge.size();++i)
601 {
602 for(int j=0;j<2;++j)
603 {
604 if(! m.edge[i].V(j)->IsV())
605 {
606 const CoordType &centerV = m.edge[i].V(j)->cP();
607 m.edge[i].V(j)->SetV();
608 std::vector<VertexPointer> VVStarVec;
609 edge::VVStarEE(&(m.edge[i]),j,VVStarVec);
610 if(VVStarVec.size()==2)
611 {
612 CoordType v0 = centerV - VVStarVec[0]->P();
613 CoordType v1 = VVStarVec[1]->P() - centerV;
614 if(vcg::Angle(v0,v1) > AngleRadThr)
615 m.edge[i].V(j)->SetS();
616 }
617 }
618 }
619 }
620 }
623 static void SelectCreaseVertexOnEdgeMeshVE(MeshType &m, ScalarType AngleRadThr)
624 {
625 tri::RequireCompactness(m);
626 tri::RequireVEAdjacency(m);
627 tri::UpdateTopology<MeshType>::VertexEdge(m);
628 tri::UpdateSelection<MeshType>::VertexClear(m);
629 for(size_t i=0;i<m.vert.size();++i)
630 {
631 std::vector<VertexPointer> VVStarVec;
632 edge::VVStarVE(&(m.vert[i]),VVStarVec);
633 if(VVStarVec.size()==2)
634 {
635 CoordType v0 = m.vert[i].P() - VVStarVec[0]->P();
636 CoordType v1 = m.vert[i].P() - VVStarVec[1]->P();
637 float angle = M_PI-vcg::Angle(v0,v1);
638 if(angle > AngleRadThr) m.vert[i].SetS();
639 }
640 }
641 }
642
644
645 // Given a mesh with FF adjacency
646 // it search for non manifold vertices and duplicate them.
647 // Duplicated vertices are moved apart according to the move threshold param.
648 // that is a percentage of the average vector from the non manifold vertex to the barycenter of the incident faces.
649
650 static int SplitNonManifoldVertex(MeshType& m, ScalarType moveThreshold)
651 {
652 RequireFFAdjacency(m);
653 typedef std::pair<FacePointer,int> FaceInt; // a face and the index of the vertex that we have to change
654 //
655 std::vector<std::pair<VertexPointer, std::vector<FaceInt> > >ToSplitVec;
656
657 SelectionStack<MeshType> ss(m);
658 ss.push();
659 CountNonManifoldVertexFF(m,true);
660 UpdateFlags<MeshType>::VertexClearV(m);
661 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
662 {
663 for (int i=0; i<fi->VN(); i++)
664 if ((*fi).V(i)->IsS() && !(*fi).V(i)->IsV())
665 {
666 (*fi).V(i)->SetV();
667 face::Pos<FaceType> startPos(&*fi,i);
668 face::Pos<FaceType> curPos = startPos;
669 std::set<FaceInt> faceSet;
670 do
671 {
672 faceSet.insert(std::make_pair(curPos.F(),curPos.VInd()));
673 curPos.FlipE();
674 curPos.NextF();
675 } while (curPos != startPos);
676
677 ToSplitVec.push_back(make_pair((*fi).V(i),std::vector<FaceInt>()));
678
679 typename std::set<FaceInt>::const_iterator iii;
680
681 for(iii=faceSet.begin();iii!=faceSet.end();++iii)
682 ToSplitVec.back().second.push_back(*iii);
683 }
684 }
685 ss.pop();
686 // Second step actually add new vertices and split them.
687 typename tri::Allocator<MeshType>::template PointerUpdater<VertexPointer> pu;
688 VertexIterator firstVp = tri::Allocator<MeshType>::AddVertices(m,ToSplitVec.size(),pu);
689 for(size_t i =0;i<ToSplitVec.size();++i)
690 {
691 // qDebug("Splitting Vertex %i",ToSplitVec[i].first-&*m.vert.begin());
692 VertexPointer np=ToSplitVec[i].first;
693 pu.Update(np);
694 firstVp->ImportData(*np);
695 // loop on the face to be changed, and also compute the movement vector;
696 CoordType delta(0,0,0);
697 for(size_t j=0;j<ToSplitVec[i].second.size();++j)
698 {
699 FaceInt ff=ToSplitVec[i].second[j];
700 ff.first->V(ff.second)=&*firstVp;
701 delta+=Barycenter(*(ff.first))-np->cP();
702 }
703 delta /= ToSplitVec[i].second.size();
704 firstVp->P() = firstVp->P() + delta * moveThreshold;
705 firstVp++;
706 }
707
708 return int(ToSplitVec.size());
709 }
710
712 static size_t SplitManifoldComponents(MeshType &m, const ScalarType moveThreshold = 0)
713 {
714 typedef typename MeshType::FacePointer FacePointer;
715 typedef typename MeshType::FaceIterator FaceIterator;
716 // it also assumes that the FF adjacency is well computed.
717 RequireFFAdjacency(m);
718
719 UpdateFlags<MeshType>::FaceClearV(m);
720 UpdateFlags<MeshType>::FaceClearS(m);
721
722 MeshType tmpMesh;
723 tmpMesh.vert.EnableVFAdjacency();
724 tmpMesh.face.EnableVFAdjacency();
725
726 if (m.face.IsWedgeTexCoordEnabled())
727 tmpMesh.face.EnableWedgeTexCoord();
728
729 size_t selCnt=0;
730
731 for(FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
732 if( !(*fi).IsD() && !(*fi).IsV() && !(*fi).IsS())
733 {
734 UpdateFlags<MeshType>::FaceClearS(m);
735
736 std::deque<FacePointer> visitStack;
737 visitStack.push_back(&*fi);
738
739 (*fi).SetS();
740 (*fi).SetV();
741
742 while(!visitStack.empty())
743 {
744 FacePointer fp = visitStack.front();
745 visitStack.pop_front();
746
747 for(int i=0;i<fp->VN();++i) {
748 FacePointer ff = fp->FFp(i);
749
750 if(face::IsManifold(*fp, i) && !ff->IsS() && !ff->IsV())
751 {
752 ff->SetS();
753 ff->SetV();
754 visitStack.push_back(ff);
755 }
756 }
757 }
758
759 Append<MeshType, MeshType>::Mesh(tmpMesh, m, true);
760 ++selCnt;
761 }
762
763 vcg::tri::UpdateTopology<MeshType>::VertexFace(tmpMesh);
764 vcg::tri::UpdateFlags<MeshType>::VertexBorderFromNone(tmpMesh);
765 for (size_t i = 0; i < size_t(tmpMesh.VN()); ++i)
766 {
767 VertexType & v = tmpMesh.vert[i];
768
769 if (v.IsB())
770 {
771 std::vector<FacePointer> faceVec;
772 std::vector<int> idxVec;
773
774 vcg::face::VFStarVF(&v, faceVec, idxVec);
775
776 CoordType delta(0, 0, 0);
777 for (auto fp : faceVec)
778 {
779 delta += vcg::Barycenter(*fp) - v.cP();
780 }
781 delta /= faceVec.size();
782
783 v.P() += delta * moveThreshold;
784 }
785 }
786
787 UpdateSelection<MeshType>::Clear(tmpMesh);
788 Append<MeshType, MeshType>::MeshCopy(m, tmpMesh);
789 return selCnt;
790 }
791
792
793 // Auxiliary function for sorting the non manifold faces according to their area. Used in RemoveNonManifoldFace
794 struct CompareAreaFP {
795 bool operator ()(FacePointer const& f1, FacePointer const& f2) const {
796 return DoubleArea(*f1) < DoubleArea(*f2);
797 }
798 };
799
801 static int RemoveNonManifoldFace(MeshType& m, bool DeleteFacesFlag=true)
802 {
803 FaceIterator fi;
804 int count_fd = 0;
805 std::vector<FacePointer> ToDelVec;
806
807 for(fi=m.face.begin(); fi!=m.face.end();++fi)
808 if (!fi->IsD())
809 {
810 if ((!IsManifold(*fi,0))||
811 (!IsManifold(*fi,1))||
812 (!IsManifold(*fi,2)))
813 ToDelVec.push_back(&*fi);
814 }
815
816 if (!DeleteFacesFlag)
817 return ToDelVec.size();
818
819 std::sort(ToDelVec.begin(),ToDelVec.end(),CompareAreaFP());
820
821 for(size_t i=0;i<ToDelVec.size();++i)
822 {
823 if(!ToDelVec[i]->IsD())
824 {
825 FaceType &ff= *ToDelVec[i];
826 if ((!IsManifold(ff,0))||
827 (!IsManifold(ff,1))||
828 (!IsManifold(ff,2)))
829 {
830 for(int j=0;j<3;++j)
831 if(!face::IsBorder<FaceType>(ff,j))
832 vcg::face::FFDetach<FaceType>(ff,j);
833
834 Allocator<MeshType>::DeleteFace(m,ff);
835 count_fd++;
836 }
837 }
838 }
839 return count_fd;
840 }
841
842 /* Remove the faces that are out of a given range of area */
843 static int RemoveFaceOutOfRangeArea(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)(), bool OnlyOnSelected=false, bool DeleteFacesFlag=true)
844 {
845 int count_fd = 0;
846 MinAreaThr*=2;
847 MaxAreaThr*=2;
848 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi){
849 if(!(*fi).IsD())
850 if(!OnlyOnSelected || (*fi).IsS())
851 {
852 const ScalarType doubleArea=DoubleArea<FaceType>(*fi);
853 if((doubleArea<=MinAreaThr) || (doubleArea>=MaxAreaThr) )
854 {
855 if (DeleteFacesFlag)
856 Allocator<MeshType>::DeleteFace(m,*fi);
857 count_fd++;
858 }
859 }
860 }
861 return count_fd;
862 }
863
864 static int RemoveZeroAreaFace(MeshType& m, bool DeleteFacesFlag=true) { return RemoveFaceOutOfRangeArea(m,0, (std::numeric_limits<ScalarType>::max)(), false, DeleteFacesFlag); }
865
866
867
871 static bool IsBitQuadOnly(const MeshType &m)
872 {
873 typedef typename MeshType::FaceType F;
874 tri::RequirePerFaceFlags(m);
875 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
876 unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
877 if ( tmp != F::FAUX0 && tmp != F::FAUX1 && tmp != F::FAUX2) return false;
878 }
879 return true;
880 }
881
882
883 static bool IsFaceFauxConsistent(MeshType &m)
884 {
885 RequirePerFaceFlags(m);
886 RequireFFAdjacency(m);
887 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
888 {
889 for(int z=0;z<(*fi).VN();++z)
890 {
891 FacePointer fp = fi->FFp(z);
892 int zp = fi->FFi(z);
893 if(fi->IsF(z) != fp->IsF(zp)) return false;
894 }
895 }
896 return true;
897 }
898
902 static bool IsBitTriOnly(const MeshType &m)
903 {
904 tri::RequirePerFaceFlags(m);
905 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) {
906 if ( !fi->IsD() && fi->IsAnyF() ) return false;
907 }
908 return true;
909 }
910
911 static bool IsBitPolygonal(const MeshType &m){
912 return !IsBitTriOnly(m);
913 }
914
919 static bool IsBitTriQuadOnly(const MeshType &m)
920 {
921 tri::RequirePerFaceFlags(m);
922 typedef typename MeshType::FaceType F;
923 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
924 unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
925 if ( tmp!=F::FAUX0 && tmp!=F::FAUX1 && tmp!=F::FAUX2 && tmp!=0 ) return false;
926 }
927 return true;
928 }
929
934 static int CountBitQuads(const MeshType &m)
935 {
936 tri::RequirePerFaceFlags(m);
937 typedef typename MeshType::FaceType F;
938 int count=0;
939 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
940 unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2);
941 if ( tmp==F::FAUX0 || tmp==F::FAUX1 || tmp==F::FAUX2) count++;
942 }
943 return count / 2;
944 }
945
949 static int CountBitTris(const MeshType &m)
950 {
951 tri::RequirePerFaceFlags(m);
952 int count=0;
953 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
954 if (!(fi->IsAnyF())) count++;
955 }
956 return count;
957 }
958
963 static int CountBitPolygons(const MeshType &m)
964 {
965 tri::RequirePerFaceFlags(m);
966 int count = 0;
967 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
968 if (fi->IsF(0)) count++;
969 if (fi->IsF(1)) count++;
970 if (fi->IsF(2)) count++;
971 }
972 return m.fn - count/2;
973 }
974
986 static int CountBitLargePolygons(const MeshType &m)
987 {
988 //note - using unordered_map to set visited vertices because
989 //the mesh is const (before, the function used vertex flags...).
990 //could be used std::vector<bool> if the vertex has the Index()
991 //member function...
992 std::unordered_map<ConstVertexPointer, bool> vertVisited;
993 for (ConstVertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
994 if (!vi->IsD()) vertVisited[&(*vi)] = true;
995
996 // First loop Clear all referenced vertices
997 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
998 if (!fi->IsD())
999 for(int i=0;i<3;++i){
1000 vertVisited[fi->V(i)] = false;
1001 }
1002
1003
1004 // Second Loop, count (twice) faux edges and mark all vertices touched by non faux edges
1005 // (e.g vertexes on the boundary of a polygon)
1006 int countE = 0;
1007 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1008 if (!fi->IsD()) {
1009 for(int i=0;i<3;++i)
1010 {
1011 if (fi->IsF(i))
1012 countE++;
1013 else
1014 {
1015 vertVisited[fi->V0(i)] = true;
1016 vertVisited[fi->V1(i)] = true;
1017 }
1018 }
1019 }
1020 // Third Loop, count the number of referenced vertexes that are completely surrounded by faux edges.
1021
1022 int countV = 0;
1023 for (ConstVertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1024 if (!vi->IsD() && !(vertVisited[&(*vi)])) countV++;
1025
1026 return m.fn - countE/2 + countV ;
1027 }
1028
1029
1037 static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
1038 {
1039 RequireFFAdjacency(m);
1040 RequirePerFaceFlags(m);
1041
1042 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1043 if(!(*fi).IsD())
1044 for (int k=0; k<3; k++)
1045 if( ( fi->IsF(k) != fi->cFFp(k)->IsF(fi->cFFi(k)) ) ||
1046 ( fi->IsF(k) && face::IsBorder(*fi,k)) )
1047 {
1048 return false;
1049 }
1050 return true;
1051 }
1052
1057 static int CountNonManifoldEdgeEE( MeshType & m, bool SelectFlag=false)
1058 {
1059 MeshAssert<MeshType>::OnlyEdgeMesh(m);
1060 RequireEEAdjacency(m);
1061 tri::UpdateTopology<MeshType>::EdgeEdge(m);
1062
1063 if(SelectFlag) UpdateSelection<MeshType>::VertexClear(m);
1064
1065 int nonManifoldCnt=0;
1066 SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
1067
1068 // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
1069 EdgeIterator ei;
1070 for (ei = m.edge.begin(); ei != m.edge.end(); ++ei) if (!ei->IsD())
1071 {
1072 TD[(*ei).V(0)]++;
1073 TD[(*ei).V(1)]++;
1074 }
1075
1076 tri::UpdateFlags<MeshType>::VertexClearV(m);
1077 // Second Loop, Check that each vertex have been seen 1 or 2 times.
1078 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if (!vi->IsD())
1079 {
1080 if( TD[vi] >2 )
1081 {
1082 if(SelectFlag) (*vi).SetS();
1083 nonManifoldCnt++;
1084 }
1085 }
1086 return nonManifoldCnt;
1087 }
1088
1095 static int CountNonManifoldEdgeFF( MeshType & m, bool SelectFlag=false)
1096 {
1097 RequireFFAdjacency(m);
1098 int nmfBit[3];
1099 nmfBit[0]= FaceType::NewBitFlag();
1100 nmfBit[1]= FaceType::NewBitFlag();
1101 nmfBit[2]= FaceType::NewBitFlag();
1102
1103
1104 UpdateFlags<MeshType>::FaceClear(m,nmfBit[0]+nmfBit[1]+nmfBit[2]);
1105
1106 if(SelectFlag){
1107 UpdateSelection<MeshType>::VertexClear(m);
1108 UpdateSelection<MeshType>::FaceClear(m);
1109 }
1110
1111 int edgeCnt = 0;
1112 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1113 {
1114 if (!fi->IsD())
1115 {
1116 for(int i=0;i<3;++i)
1117 if(!IsManifold(*fi,i))
1118 {
1119 if(!(*fi).IsUserBit(nmfBit[i]))
1120 {
1121 ++edgeCnt;
1122 if(SelectFlag)
1123 {
1124 (*fi).V0(i)->SetS();
1125 (*fi).V1(i)->SetS();
1126 }
1127 // follow the ring of faces incident on edge i;
1128 face::Pos<FaceType> nmf(&*fi,i);
1129 do
1130 {
1131 if(SelectFlag) nmf.F()->SetS();
1132 nmf.F()->SetUserBit(nmfBit[nmf.E()]);
1133 nmf.NextF();
1134 }
1135 while(nmf.f != &*fi);
1136 }
1137 }
1138 }
1139 }
1140
1141 FaceType::DeleteBitFlag(nmfBit[2]);
1142 FaceType::DeleteBitFlag(nmfBit[1]);
1143 FaceType::DeleteBitFlag(nmfBit[0]);
1144 return edgeCnt;
1145 }
1146
1151 static int CountNonManifoldVertexFF( MeshType & m, bool selectVert = true, bool clearSelection = true)
1152 {
1153 RequireFFAdjacency(m);
1154 if(selectVert && clearSelection) UpdateSelection<MeshType>::VertexClear(m);
1155
1156 int nonManifoldCnt=0;
1157 SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
1158
1159 // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter.
1160 FaceIterator fi;
1161 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1162 {
1163 for (int k=0; k<fi->VN(); k++)
1164 {
1165 TD[(*fi).V(k)]++;
1166 }
1167 }
1168
1169 tri::UpdateFlags<MeshType>::VertexClearV(m);
1170 // Second Loop.
1171 // mark out of the game the vertexes that are incident on non manifold edges.
1172 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1173 {
1174 for(int i=0; i<fi->VN(); ++i)
1175 if (!IsManifold(*fi,i))
1176 {
1177 (*fi).V0(i)->SetV();
1178 (*fi).V1(i)->SetV();
1179 }
1180 }
1181 // Third Loop, for safe vertexes, check that the number of faces that you can reach starting
1182 // from it and using FF is the same of the previously counted.
1183 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
1184 {
1185 for(int i=0; i<fi->VN(); i++) if (!(*fi).V(i)->IsV())
1186 {
1187 (*fi).V(i)->SetV();
1188 face::Pos<FaceType> pos(&(*fi),i);
1189
1190 int starSizeFF = pos.NumberOfIncidentFaces();
1191
1192 if (starSizeFF != TD[(*fi).V(i)])
1193 {
1194 if (selectVert)
1195 (*fi).V(i)->SetS();
1196 nonManifoldCnt++;
1197 }
1198 }
1199 }
1200 return nonManifoldCnt;
1201 }
1209 static bool IsWaterTight(MeshType & m)
1210 {
1211 int edgeNum=0,edgeBorderNum=0,edgeNonManifNum=0;
1212 CountEdgeNum(m, edgeNum, edgeBorderNum,edgeNonManifNum);
1213 return (edgeBorderNum==0) && (edgeNonManifNum==0);
1214 }
1215
1216 static void CountEdgeNum( MeshType & m, int &total_e, int &boundary_e, int &non_manif_e )
1217 {
1218 std::vector< typename tri::UpdateTopology<MeshType>::PEdge > edgeVec;
1219 tri::UpdateTopology<MeshType>::FillEdgeVector(m,edgeVec,true);
1220 sort(edgeVec.begin(), edgeVec.end()); // Lo ordino per vertici
1221 total_e=0;
1222 boundary_e=0;
1223 non_manif_e=0;
1224
1225 size_t f_on_cur_edge =1;
1226 for(size_t i=0;i<edgeVec.size();++i)
1227 {
1228 if(( (i+1) == edgeVec.size()) || !(edgeVec[i] == edgeVec[i+1]))
1229 {
1230 ++total_e;
1231 if(f_on_cur_edge==1)
1232 ++boundary_e;
1233 if(f_on_cur_edge>2)
1234 ++non_manif_e;
1235 f_on_cur_edge=1;
1236 }
1237 else
1238 {
1239 ++f_on_cur_edge;
1240 }
1241 } // end for
1242 }
1243
1244
1245
1251 static int CountHoles( MeshType & m)
1252 {
1253 RequireFFAdjacency(m);
1254 MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1255 // The walk below turns around each boundary vertex through the faces on it
1256 // (Pos::NextB) until it reaches the next border edge. That only comes round when the
1257 // faces around the vertex form a fan: a non-manifold edge on the vertex closes the
1258 // rotation on itself without ever reaching a border, and the walk would not end.
1259 // Only the vertices of border edges are turned around, so mark those on a
1260 // non-manifold edge and give up if a border edge has one.
1261 UpdateFlags<MeshType>::VertexClearV(m);
1262 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD())
1263 for(int j=0;j<3;++j)
1264 if(!face::IsManifold(*fi,j))
1265 {
1266 fi->V(j)->SetV();
1267 fi->V1(j)->SetV();
1268 }
1269 bool wellDefined=true;
1270 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD())
1271 for(int j=0;j<3;++j)
1272 if(face::IsBorder(*fi,j) && (fi->V(j)->IsV() || fi->V1(j)->IsV()))
1273 wellDefined=false;
1274 UpdateFlags<MeshType>::VertexClearV(m);
1275 if(!wellDefined)
1276 return -1;
1277 UpdateFlags<MeshType>::FaceClearV(m);
1278 int loopNum=0;
1279 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD())
1280 {
1281 for(int j=0;j<3;++j)
1282 {
1283 if(!fi->IsV() && face::IsBorder(*fi,j))
1284 {
1285 face::Pos<FaceType> startPos(&*fi,j);
1286 face::Pos<FaceType> curPos=startPos;
1287 do
1288 {
1289 curPos.NextB();
1290 curPos.F()->SetV();
1291 }
1292 while(curPos!=startPos);
1293 ++loopNum;
1294 }
1295 }
1296 }
1297 return loopNum;
1298 }
1299
1300 /*
1301 Compute the set of connected components of a given mesh
1302 it fills a vector of pair < int , faceptr > with, for each connecteed component its size and a represnant
1303 */
1304 static int CountConnectedComponents(MeshType &m)
1305 {
1306 std::vector< std::pair<int,FacePointer> > CCV;
1307 return ConnectedComponents(m,CCV);
1308 }
1309
1310 static int ConnectedComponents(MeshType &m, std::vector< std::pair<int,FacePointer> > &CCV)
1311 {
1312 tri::RequireFFAdjacency(m);
1313 CCV.clear();
1314 tri::UpdateFlags<MeshType>::FaceClearV(m);
1315 std::stack<FacePointer> sf;
1316 FacePointer fpt=&*(m.face.begin());
1317 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1318 {
1319 if(!((*fi).IsD()) && !(*fi).IsV())
1320 {
1321 (*fi).SetV();
1322 CCV.push_back(std::make_pair(0,&*fi));
1323 sf.push(&*fi);
1324 while (!sf.empty())
1325 {
1326 fpt=sf.top();
1327 ++CCV.back().first;
1328 sf.pop();
1329 for(int j=0; j<fpt->VN(); ++j)
1330 {
1331 if( !face::IsBorder(*fpt,j) )
1332 {
1333 FacePointer l = fpt->FFp(j);
1334 if( !(*l).IsV() )
1335 {
1336 (*l).SetV();
1337 sf.push(l);
1338 }
1339 }
1340 }
1341 }
1342 }
1343 }
1344 return int(CCV.size());
1345 }
1346
1347 static int edgeMeshConnectedComponents(MeshType & poly, std::vector<std::pair<int, typename MeshType::EdgePointer> > &eCC)
1348 {
1349 typedef typename MeshType::EdgePointer EdgePointer;
1350 tri::UpdateTopology<MeshType>::VertexEdge(poly);
1351 tri::UpdateFlags<MeshType>::EdgeClear(poly);
1352 eCC.clear();
1353 std::stack<EdgePointer> stack;
1354
1355 for (auto ei = poly.edge.begin(); ei != poly.edge.end(); ++ei)
1356 if (!ei->IsD() && !ei->IsV())
1357 {
1358 ei->SetV();
1359
1360 std::pair<int, EdgePointer> cc(1, &*ei);
1361
1362 stack.push(&*ei);
1363 while (!stack.empty())
1364 {
1365 EdgePointer ep = stack.top();
1366 stack.pop();
1367
1368 for (int i = 0; i < 2; ++i)
1369 {
1370 edge::VEIterator<typename MeshType::EdgeType> vei(ep->V(i));
1371 while (!vei.End())
1372 {
1373 if (!vei.E()->IsV())
1374 {
1375 vei.E()->SetV();
1376 stack.push(vei.E());
1377 cc.first += 1;
1378 }
1379 ++vei;
1380 }
1381 }
1382 }
1383 eCC.push_back(cc);
1384 }
1385 return int(eCC.size());
1386 }
1387
1388 static void ComputeValence( MeshType &m, typename MeshType::PerVertexIntHandle &h)
1389 {
1390 for(VertexIterator vi=m.vert.begin(); vi!= m.vert.end();++vi)
1391 h[vi]=0;
1392
1393 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
1394 {
1395 if(!((*fi).IsD()))
1396 for(int j=0;j<fi->VN();j++)
1397 ++h[tri::Index(m,fi->V(j))];
1398 }
1399 }
1400
1436 static int MeshGenus(int nvert,int nedges,int nfaces, int numholes, int numcomponents)
1437 {
1438 return -((nvert + nfaces - nedges + numholes - 2 * numcomponents) / 2);
1439 }
1440
1441 static int MeshGenus(MeshType &m)
1442 {
1443 int nvert=m.vn;
1444 int nfaces=m.fn;
1445 int boundary_e,total_e,nonmanif_e;
1446 CountEdgeNum(m,total_e,boundary_e,nonmanif_e);
1447 int numholes=CountHoles(m);
1448 int numcomponents=CountConnectedComponents(m);
1449 int G=MeshGenus(nvert,total_e,nfaces,numholes,numcomponents);
1450 return G;
1451 }
1452
1464 static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular)
1465 {
1466 RequireVFAdjacency(m);
1467 Regular = true;
1468
1469 VertexIterator vi;
1470
1471 // for each vertex the number of edges are count
1472 for (vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1473 {
1474 if (!vi->IsD())
1475 {
1476 face::Pos<FaceType> he((*vi).VFp(), &*vi);
1477 face::Pos<FaceType> ht = he;
1478
1479 int n=0;
1480 bool border=false;
1481 do
1482 {
1483 ++n;
1484 ht.NextE();
1485 if (ht.IsBorder())
1486 border=true;
1487 }
1488 while (ht != he);
1489
1490 if (border)
1491 n = n/2;
1492
1493 if ((n != 6)&&(!border && n != 4))
1494 {
1495 Regular = false;
1496 break;
1497 }
1498 }
1499 }
1500
1501 if (!Regular)
1502 Semiregular = false;
1503 else
1504 {
1505 // For now we do not account for semi-regularity
1506 Semiregular = false;
1507 }
1508 }
1509
1510
1511 static bool IsCoherentlyOrientedMesh(MeshType &m)
1512 {
1513 RequireFFAdjacency(m);
1514 MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1515 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1516 if (!fi->IsD())
1517 for(int i=0;i<3;++i)
1518 if(!face::CheckOrientation(*fi,i))
1519 return false;
1520
1521 return true;
1522 }
1523
1524 static void OrientCoherentlyMesh(MeshType &m, bool &_IsOriented, bool &_IsOrientable)
1525 {
1526 RequireFFAdjacency(m);
1527 MeshAssert<MeshType>::FFAdjacencyIsInitialized(m);
1528 bool IsOrientable = true;
1529 bool IsOriented = true;
1530
1531 UpdateFlags<MeshType>::FaceClearV(m);
1532 std::stack<FacePointer> faces;
1533 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1534 {
1535 if (!fi->IsD() && !fi->IsV())
1536 {
1537 // each face put in the stack is selected (and oriented)
1538 fi->SetV();
1539 faces.push(&(*fi));
1540 while (!faces.empty())
1541 {
1542 FacePointer fp = faces.top();
1543 faces.pop();
1544
1545 // make consistently oriented the adjacent faces
1546 for (int j = 0; j < 3; j++)
1547 {
1548 if (!face::IsBorder(*fp,j) && face::IsManifold<FaceType>(*fp, j))
1549 {
1550 FacePointer fpaux = fp->FFp(j);
1551 int iaux = fp->FFi(j);
1552 if (!CheckOrientation(*fpaux, iaux))
1553 {
1554 IsOriented = false;
1555
1556 if (!fpaux->IsV())
1557 face::SwapEdge<FaceType,true>(*fpaux, iaux);
1558 else
1559 {
1560 IsOrientable = false;
1561 break;
1562 }
1563 }
1564 if (!fpaux->IsV())
1565 {
1566 fpaux->SetV();
1567 faces.push(fpaux);
1568 }
1569 }
1570 }
1571 }
1572 }
1573 if (!IsOrientable) break;
1574 }
1575 _IsOriented = IsOriented;
1576 _IsOrientable = IsOrientable;
1577 }
1578
1579
1581 static void FlipMesh(MeshType &m, bool selected=false)
1582 {
1583 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if(!(*fi).IsD())
1584 if(!selected || (*fi).IsS())
1585 {
1586 face::SwapEdge<FaceType,false>((*fi), 0);
1587 if (HasPerWedgeTexCoord(m))
1588 std::swap((*fi).WT(0),(*fi).WT(1));
1589 }
1590 }
1596 static bool FlipNormalOutside(MeshType &m)
1597 {
1598 if(m.vert.empty()) return false;
1599
1600 tri::UpdateNormal<MeshType>::PerVertexAngleWeighted(m);
1601 tri::UpdateNormal<MeshType>::NormalizePerVertex(m);
1602
1603 std::vector< VertexPointer > minVertVec;
1604 std::vector< VertexPointer > maxVertVec;
1605
1606 // The set of directions to be chosen
1607 std::vector< CoordType > dirVec;
1608 dirVec.push_back(CoordType(1,0,0));
1609 dirVec.push_back(CoordType(0,1,0));
1610 dirVec.push_back(CoordType(0,0,1));
1611 dirVec.push_back(CoordType( 1, 1,1));
1612 dirVec.push_back(CoordType(-1, 1,1));
1613 dirVec.push_back(CoordType(-1,-1,1));
1614 dirVec.push_back(CoordType( 1,-1,1));
1615 for(size_t i=0;i<dirVec.size();++i)
1616 {
1617 Normalize(dirVec[i]);
1618 minVertVec.push_back(&*m.vert.begin());
1619 maxVertVec.push_back(&*m.vert.begin());
1620 }
1621 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if(!(*vi).IsD())
1622 {
1623 for(size_t i=0;i<dirVec.size();++i)
1624 {
1625 if( (*vi).cP().dot(dirVec[i]) < minVertVec[i]->P().dot(dirVec[i])) minVertVec[i] = &*vi;
1626 if( (*vi).cP().dot(dirVec[i]) > maxVertVec[i]->P().dot(dirVec[i])) maxVertVec[i] = &*vi;
1627 }
1628 }
1629
1630 int voteCount=0;
1631 ScalarType angleThreshold = cos(math::ToRad(85.0));
1632 for(size_t i=0;i<dirVec.size();++i)
1633 {
1634 // 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]);
1635 // 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]);
1636 if(minVertVec[i]->N().dot(dirVec[i]) > angleThreshold ) voteCount++;
1637 if(maxVertVec[i]->N().dot(dirVec[i]) < -angleThreshold ) voteCount++;
1638 }
1639 // qDebug("votecount = %i",voteCount);
1640 if(voteCount < int(dirVec.size())/2) return false;
1641 FlipMesh(m);
1642 return true;
1643 }
1644
1664 static int RemoveFaceFoldByFlip(
1665 MeshType &m,
1666 float normalThresholdDeg=175,
1667 bool repeat=true,
1668 bool updateTopology=true)
1669 {
1670 RequireFFAdjacency(m);
1671 RequireCompactness(m);
1672 RequirePerFaceNormal(m);
1673 RequireTriangularMesh(m);
1674 if (m.fn == 0 || !IsBitTriOnly(m) || m.face.front().IsWedgeTexCoordEnabled())
1675 return 0;
1676
1677 if (updateTopology)
1678 tri::UpdateTopology<MeshType>::FaceFace(m);
1679 if (CountNonManifoldEdgeFF(m) > 0)
1680 return 0;
1681 UpdateNormal<MeshType>::PerFaceNormalized(m);
1682 const ScalarType thresholdCos = math::Cos(math::ToRad(math::Clamp(
1683 ScalarType(normalThresholdDeg), ScalarType(0), ScalarType(180))));
1684 const ScalarType barycentricEps = ScalarType(0.0001);
1685
1686 auto isFold = [&](const auto &a, const auto &b) {
1687 return a * b < thresholdCos;
1688 };
1689 auto isFoldedAcrossEdge = [&](FaceType &f, int edge, const CoordType &normal) {
1690 if (face::IsBorder(f, edge)) return false;
1691 const auto &adjacentNormal = f.FFp(edge)->N();
1692 return adjacentNormal.SquaredNorm() == ScalarType(0)
1693 || isFold(normal, adjacentNormal);
1694 };
1695
1696 std::vector<size_t> queue(m.fn);
1697 std::vector<unsigned char> queued(m.fn, 1);
1698 for (size_t i = 0; i < queue.size(); ++i) queue[i] = i;
1699 auto enqueue = [&](FacePointer fp) {
1700 const size_t index = tri::Index(m, fp);
1701 if (queued[index]) return;
1702 queued[index] = 1;
1703 queue.push_back(index);
1704 };
1705
1706 int total = 0;
1707 while (!queue.empty()) {
1708 const size_t faceIndex = queue.back();
1709 queue.pop_back();
1710 queued[faceIndex] = 0;
1711 FaceType &f = m.face[faceIndex];
1712
1713 const auto &fNormal = f.N();
1714 if (fNormal.SquaredNorm() == ScalarType(0))
1715 continue;
1716
1717 bool isolatedFold = true;
1718 for (int edge = 0; edge < 3; ++edge) {
1719 if (face::IsBorder(f, edge)) {
1720 isolatedFold = false;
1721 break;
1722 }
1723 const auto &adjacentNormal = f.FFp(edge)->N();
1724 if (adjacentNormal.SquaredNorm() == ScalarType(0)
1725 || !isFold(fNormal, adjacentNormal)) {
1726 isolatedFold = false;
1727 break;
1728 }
1729 }
1730 if (!isolatedFold)
1731 continue;
1732
1733 int flipEdge = -1;
1734 for (int edge = 0; edge < 3; ++edge) {
1735 FacePointer g = f.FFp(edge);
1736 const int oppositeEdge = f.FFi(edge);
1737 if (!face::CheckFlipEdge<FaceType>(f, edge))
1738 continue;
1739
1740 CoordType barycentric;
1741 if (!vcg::InterpolationParameters(
1742 *g, TriangleNormal(*g), f.P2(edge), barycentric))
1743 continue;
1744 if (barycentric[0] <= barycentricEps
1745 || barycentric[1] <= barycentricEps
1746 || barycentric[2] <= barycentricEps)
1747 continue;
1748
1749 const CoordType newFNormal =
1750 Normal(f.P0(edge), g->P2(oppositeEdge), f.P2(edge)).Normalize();
1751 const CoordType newGNormal =
1752 Normal(f.P1(edge), f.P2(edge), g->P2(oppositeEdge)).Normalize();
1753
1754 // After the flip: f-next moves to g, while g-next moves to f.
1755 if (newFNormal.SquaredNorm() == ScalarType(0)
1756 || newGNormal.SquaredNorm() == ScalarType(0)
1757 || isFold(newFNormal, newGNormal)
1758 || isFoldedAcrossEdge(f, f.Next(edge), newGNormal)
1759 || isFoldedAcrossEdge(f, f.Prev(edge), newFNormal)
1760 || isFoldedAcrossEdge(*g, g->Next(oppositeEdge), newFNormal)
1761 || isFoldedAcrossEdge(*g, g->Prev(oppositeEdge), newGNormal))
1762 continue;
1763
1764 flipEdge = edge;
1765 break;
1766 }
1767
1768 if (flipEdge < 0)
1769 continue;
1770
1771 FacePointer g = f.FFp(flipEdge);
1772 const int oppositeEdge = f.FFi(flipEdge);
1773 const bool fNextSelected = f.IsFaceEdgeS(f.Next(flipEdge));
1774 const bool gNextSelected = g->IsFaceEdgeS(g->Next(oppositeEdge));
1775 face::FlipEdge<FaceType>(f, flipEdge);
1776 f.N() = NormalizedTriangleNormal(f);
1777 g->N() = NormalizedTriangleNormal(*g);
1778 // Preserve the four boundary-edge flags; the newly created diagonal is unselected.
1779 if (gNextSelected) f.SetFaceEdgeS(flipEdge); else f.ClearFaceEdgeS(flipEdge);
1780 if (fNextSelected) g->SetFaceEdgeS(oppositeEdge); else g->ClearFaceEdgeS(oppositeEdge);
1781 f.ClearFaceEdgeS(f.Next(flipEdge));
1782 g->ClearFaceEdgeS(g->Next(oppositeEdge));
1783 ++total;
1784 if (repeat) {
1785 enqueue(&f);
1786 enqueue(g);
1787 for (int edge = 0; edge < 3; ++edge) {
1788 enqueue(f.FFp(edge));
1789 enqueue(g->FFp(edge));
1790 }
1791 }
1792 }
1793 return total;
1794 }
1795
1796
1797 static int RemoveTVertexByFlip(MeshType &m, float threshold=40, bool repeat=true)
1798 {
1799 RequireFFAdjacency(m);
1800 RequirePerVertexMark(m);
1801 //Counters for logging and convergence
1802 int count, total = 0;
1803
1804 do {
1805 tri::UpdateTopology<MeshType>::FaceFace(m);
1806 tri::UnMarkAll(m);
1807 count = 0;
1808
1809 //detection stage
1810 for(unsigned int index = 0 ; index < m.face.size(); ++index )
1811 {
1812 FacePointer f = &(m.face[index]); float sides[3]; CoordType dummy;
1813 sides[0] = Distance(f->P(0), f->P(1));
1814 sides[1] = Distance(f->P(1), f->P(2));
1815 sides[2] = Distance(f->P(2), f->P(0));
1816 // Find largest triangle side
1817 int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1818 if( tri::IsMarked(m,f->V2(i) )) continue;
1819
1820 if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1821 {
1822 tri::Mark(m,f->V2(i));
1823 if(face::CheckFlipEdge<FaceType>( *f, i )) {
1824 // Check if EdgeFlipping improves quality
1825 FacePointer g = f->FFp(i); int k = f->FFi(i);
1826 Triangle3<ScalarType> t1(f->P(i), f->P1(i), f->P2(i)), t2(g->P(k), g->P1(k), g->P2(k)),
1827 t3(f->P(i), g->P2(k), f->P2(i)), t4(g->P(k), f->P2(i), g->P2(k));
1828
1829 if ( std::min( QualityFace(t1), QualityFace(t2) ) < std::min( QualityFace(t3), QualityFace(t4) ))
1830 {
1831 face::FlipEdge<FaceType>( *f, i );
1832 ++count; ++total;
1833 }
1834 }
1835
1836 }
1837 }
1838
1839 // tri::UpdateNormal<MeshType>::PerFace(m);
1840 }
1841 while( repeat && count );
1842 return total;
1843 }
1844
1845 static int RemoveTVertexByCollapse(MeshType &m, float threshold=40, bool repeat=true)
1846 {
1847 RequirePerVertexMark(m);
1848 //Counters for logging and convergence
1849 int count, total = 0;
1850
1851 do {
1852 tri::UnMarkAll(m);
1853 count = 0;
1854
1855 //detection stage
1856 for(unsigned int index = 0 ; index < m.face.size(); ++index )
1857 {
1858 FacePointer f = &(m.face[index]);
1859 float sides[3];
1860 CoordType dummy;
1861
1862 sides[0] = Distance(f->P(0), f->P(1));
1863 sides[1] = Distance(f->P(1), f->P(2));
1864 sides[2] = Distance(f->P(2), f->P(0));
1865 int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
1866 if( tri::IsMarked(m,f->V2(i) )) continue;
1867
1868 if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
1869 {
1870 tri::Mark(m,f->V2(i));
1871
1872 int j = Distance(dummy,f->P(i))<Distance(dummy,f->P1(i))?i:(i+1)%3;
1873 f->P2(i) = f->P(j); tri::Mark(m,f->V(j));
1874 ++count; ++total;
1875 }
1876 }
1877
1878
1879 tri::Clean<MeshType>::RemoveDuplicateVertex(m);
1880 tri::Allocator<MeshType>::CompactFaceVector(m);
1881 tri::Allocator<MeshType>::CompactVertexVector(m);
1882 }
1883 while( repeat && count );
1884
1885 return total;
1886 }
1887
1888 static bool SelfIntersections(MeshType &m, std::vector<FaceType*> &ret)
1889 {
1890 RequirePerFaceMark(m);
1891 ret.clear();
1892 int referredBit = FaceType::NewBitFlag();
1893 tri::UpdateFlags<MeshType>::FaceClear(m,referredBit);
1894
1895 TriMeshGrid gM;
1896 gM.Set(m.face.begin(),m.face.end());
1897
1898 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
1899 {
1900 (*fi).SetUserBit(referredBit);
1901 Box3< ScalarType> bbox;
1902 (*fi).GetBBox(bbox);
1903 std::vector<FaceType*> inBox;
1904 vcg::tri::GetInBoxFace(m, gM, bbox,inBox);
1905 bool Intersected=false;
1906 typename std::vector<FaceType*>::iterator fib;
1907 for(fib=inBox.begin();fib!=inBox.end();++fib)
1908 {
1909 if(!(*fib)->IsUserBit(referredBit) && (*fib != &*fi) )
1910 if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){
1911 ret.push_back(*fib);
1912 if(!Intersected) {
1913 ret.push_back(&*fi);
1914 Intersected=true;
1915 }
1916 }
1917 }
1918 inBox.clear();
1919 }
1920
1921 FaceType::DeleteBitFlag(referredBit);
1922 return (ret.size()>0);
1923 }
1924
1928 static bool IsSizeConsistent(MeshType &m)
1929 {
1930 int DeletedVertNum=0;
1931 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
1932 if((*vi).IsD()) DeletedVertNum++;
1933
1934 int DeletedEdgeNum=0;
1935 for (EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei)
1936 if((*ei).IsD()) DeletedEdgeNum++;
1937
1938 int DeletedFaceNum=0;
1939 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1940 if((*fi).IsD()) DeletedFaceNum++;
1941
1942 if(size_t(m.vn+DeletedVertNum) != m.vert.size()) return false;
1943 if(size_t(m.en+DeletedEdgeNum) != m.edge.size()) return false;
1944 if(size_t(m.fn+DeletedFaceNum) != m.face.size()) return false;
1945
1946 return true;
1947 }
1948
1953 static bool IsFFAdjacencyConsistent(MeshType &m)
1954 {
1955 RequireFFAdjacency(m);
1956
1957 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1958 if(!(*fi).IsD())
1959 {
1960 for(int i=0;i<3;++i)
1961 if(!FFCorrectness(*fi, i)) return false;
1962 }
1963 return true;
1964 }
1965
1969 static bool HasConsistentPerWedgeTexCoord(MeshType &m)
1970 {
1971 tri::RequirePerFaceWedgeTexCoord(m);
1972
1973 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1974 if(!(*fi).IsD())
1975 { FaceType &f=(*fi);
1976 if( ! ( (f.WT(0).N() == f.WT(1).N()) && (f.WT(0).N() == (*fi).WT(2).N()) ) )
1977 return false; // all the vertices must have the same index.
1978
1979 if((*fi).WT(0).N() <0) return false; // no undefined texture should be allowed
1980 }
1981 return true;
1982 }
1983
1987 static bool HasZeroTexCoordFace(MeshType &m)
1988 {
1989 tri::RequirePerFaceWedgeTexCoord(m);
1990
1991 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
1992 if(!(*fi).IsD())
1993 {
1994 if( (*fi).WT(0).P() == (*fi).WT(1).P() && (*fi).WT(0).P() == (*fi).WT(2).P() ) return false;
1995 }
1996 return true;
1997 }
1998
1999
2007 static bool TestFaceFaceIntersection(FaceType *f0,FaceType *f1)
2008 {
2009 int sv = face::CountSharedVertex(f0,f1);
2010 if(sv==3) return true;
2011 if(sv==0) return (vcg::IntersectionTriangleTriangle<FaceType>((*f0),(*f1)));
2012 // if the faces share only a vertex, the opposite edge (as a segment) is tested against the face
2013 // to avoid degenerate cases where the two triangles have the opposite edge on a common plane
2014 // we offset the segment to test toward the shared vertex
2015 if(sv==1)
2016 {
2017 int i0,i1; ScalarType a,b;
2018 face::FindSharedVertex(f0,f1,i0,i1);
2019 CoordType shP = f0->V(i0)->P()*0.5;
2020 if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f0).V1(i0)->P()*0.5+shP,(*f0).V2(i0)->P()*0.5+shP), *f1, a, b) )
2021 {
2022 // a,b are the param coords of the intersection point of the segment.
2023 if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
2024 return true;
2025 }
2026 if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f1).V1(i1)->P()*0.5+shP,(*f1).V2(i1)->P()*0.5+shP), *f0, a, b) )
2027 {
2028 // a,b are the param coords of the intersection point of the segment.
2029 if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false;
2030 return true;
2031 }
2032
2033 }
2034 return false;
2035 }
2036
2037
2038
2042 static int MergeCloseVertex(MeshType &m, const ScalarType radius)
2043 {
2044 int mergedCnt=0;
2045 mergedCnt = ClusterVertex(m,radius);
2046 RemoveDuplicateVertex(m,true);
2047 return mergedCnt;
2048 }
2049
2050 static int ClusterVertex(MeshType &m, const ScalarType radius)
2051 {
2052 if(m.vn==0) return 0;
2053 // some spatial indexing structure does not work well with deleted vertices...
2054 tri::Allocator<MeshType>::CompactVertexVector(m);
2055 typedef vcg::SpatialHashTable<VertexType, ScalarType> SampleSHT;
2056 SampleSHT sht;
2057 tri::EmptyTMark<MeshType> markerFunctor;
2058 std::vector<VertexType*> closests;
2059 int mergedCnt=0;
2060 sht.Set(m.vert.begin(), m.vert.end());
2061 UpdateFlags<MeshType>::VertexClearV(m);
2062 for(VertexIterator viv = m.vert.begin(); viv!= m.vert.end(); ++viv)
2063 if(!(*viv).IsD() && !(*viv).IsV())
2064 {
2065 (*viv).SetV();
2066 Point3<ScalarType> p = viv->cP();
2067 Box3<ScalarType> bb(p-Point3<ScalarType>(radius,radius,radius),p+Point3<ScalarType>(radius,radius,radius));
2068 GridGetInBox(sht, markerFunctor, bb, closests);
2069 // qDebug("Vertex %i has %i closest", &*viv - &*m.vert.begin(),closests.size());
2070 for(size_t i=0; i<closests.size(); ++i)
2071 {
2072 ScalarType dist = Distance(p,closests[i]->cP());
2073 if(dist < radius && !closests[i]->IsV())
2074 {
2075 // printf("%f %f \n",dist,radius);
2076 mergedCnt++;
2077 closests[i]->SetV();
2078 closests[i]->P()=p;
2079 }
2080 }
2081 }
2082 return mergedCnt;
2083 }
2084
2085
2086 static std::pair<int,int> RemoveSmallConnectedComponentsSize(MeshType &m, int maxCCSize)
2087 {
2088 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
2089 int TotalCC=ConnectedComponents(m, CCV);
2090 int DeletedCC=0;
2091
2092 ConnectedComponentIterator<MeshType> ci;
2093 for(unsigned int i=0;i<CCV.size();++i)
2094 {
2095 std::vector<typename MeshType::FacePointer> FPV;
2096 if(CCV[i].first<maxCCSize)
2097 {
2098 DeletedCC++;
2099 for(ci.start(m,CCV[i].second);!ci.completed();++ci)
2100 FPV.push_back(*ci);
2101
2102 typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
2103 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
2104 Allocator<MeshType>::DeleteFace(m,(**fpvi));
2105 }
2106 }
2107 return std::make_pair(TotalCC,DeletedCC);
2108 }
2109
2110
2112 // it returns a pair with the number of connected components and the number of deleted ones.
2113 static std::pair<int,int> RemoveSmallConnectedComponentsDiameter(MeshType &m, ScalarType maxDiameter)
2114 {
2115 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
2116 int TotalCC=ConnectedComponents(m, CCV);
2117 int DeletedCC=0;
2118 tri::ConnectedComponentIterator<MeshType> ci;
2119 for(unsigned int i=0;i<CCV.size();++i)
2120 {
2121 Box3<ScalarType> bb;
2122 std::vector<typename MeshType::FacePointer> FPV;
2123 for(ci.start(m,CCV[i].second);!ci.completed();++ci)
2124 {
2125 FPV.push_back(*ci);
2126 bb.Add((*ci)->P(0));
2127 bb.Add((*ci)->P(1));
2128 bb.Add((*ci)->P(2));
2129 }
2130 if(bb.Diag()<maxDiameter)
2131 {
2132 DeletedCC++;
2133 typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
2134 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
2135 tri::Allocator<MeshType>::DeleteFace(m,(**fpvi));
2136 }
2137 }
2138 return std::make_pair(TotalCC,DeletedCC);
2139 }
2140
2142 // it returns a pair with the number of connected components and the number of deleted ones.
2143 static std::pair<int,int> RemoveHugeConnectedComponentsDiameter(MeshType &m, ScalarType minDiameter)
2144 {
2145 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
2146 int TotalCC=ConnectedComponents(m, CCV);
2147 int DeletedCC=0;
2148 tri::ConnectedComponentIterator<MeshType> ci;
2149 for(unsigned int i=0;i<CCV.size();++i)
2150 {
2151 Box3f bb;
2152 std::vector<typename MeshType::FacePointer> FPV;
2153 for(ci.start(m,CCV[i].second);!ci.completed();++ci)
2154 {
2155 FPV.push_back(*ci);
2156 bb.Add((*ci)->P(0));
2157 bb.Add((*ci)->P(1));
2158 bb.Add((*ci)->P(2));
2159 }
2160 if(bb.Diag()>minDiameter)
2161 {
2162 DeletedCC++;
2163 typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
2164 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
2165 tri::Allocator<MeshType>::DeleteFace(m,(**fpvi));
2166 }
2167 }
2168 return std::make_pair(TotalCC,DeletedCC);
2169 }
2170
2171
2172
2179 static void SelectFoldedFaceFromOneRingFaces(MeshType &m, ScalarType cosThreshold)
2180 {
2181 typedef std::unordered_set<VertexPointer> VertexSet;
2182 tri::RequireVFAdjacency(m);
2183 tri::RequirePerFaceNormal(m);
2184 tri::RequirePerVertexNormal(m);
2185 vcg::tri::UpdateSelection<MeshType>::FaceClear(m);
2186 vcg::tri::UpdateNormal<MeshType>::PerFaceNormalized(m);
2187 vcg::tri::UpdateNormal<MeshType>::PerVertexNormalized(m);
2188 vcg::tri::UpdateTopology<MeshType>::VertexFace(m);
2189 if (cosThreshold > 0)
2190 cosThreshold = 0;
2191
2192#pragma omp parallel for schedule(dynamic, 10)
2193 for (int i = 0; i < m.face.size(); i++)
2194 {
2195 VertexSet nearVertex;
2196 std::vector<CoordType> pointVec;
2197 FacePointer f = &m.face[i];
2198 for (int j = 0; j < 3; j++)
2199 {
2200 std::vector<VertexPointer> temp;
2201 vcg::face::VVStarVF<FaceType>(f->V(j), temp);
2202 typename std::vector<VertexPointer>::iterator iter = temp.begin();
2203 for (; iter != temp.end(); iter++)
2204 {
2205 if ((*iter) != f->V1(j) && (*iter) != f->V2(j))
2206 {
2207 if (nearVertex.insert((*iter)).second)
2208 pointVec.push_back((*iter)->P());
2209 }
2210 }
2211 nearVertex.insert(f->V(j));
2212 pointVec.push_back(f->P(j));
2213 }
2214
2215 if (pointVec.size() > 3)
2216 {
2217 vcg::Plane3<ScalarType> plane;
2218 vcg::FitPlaneToPointSet(pointVec, plane);
2219 float avgDot = 0;
2220 for (auto nvp : nearVertex)
2221 avgDot += plane.Direction().dot(nvp->N());
2222 avgDot /= nearVertex.size();
2223 typename MeshType::VertexType::NormalType normal;
2224 if (avgDot < 0)
2225 normal = -plane.Direction();
2226 else
2227 normal = plane.Direction();
2228 if (normal.dot(f->N()) < cosThreshold)
2229 f->SetS();
2230 }
2231 }
2232 }
2237 static int SelectIntersectingFaces(MeshType &m1, MeshType &m2)
2238 {
2239 RequirePerFaceMark(m2);
2240 RequireCompactness(m1);
2241 RequireCompactness(m2);
2242
2243 tri::UpdateSelection<MeshType>::FaceClear(m1);
2244
2245 TriMeshGrid gM;
2246 gM.Set(m2.face.begin(),m2.face.end());
2247 int selCnt=0;
2248 for(auto fi=m1.face.begin();fi!=m1.face.end();++fi)
2249 {
2250 Box3< ScalarType> bbox;
2251 (*fi).GetBBox(bbox);
2252 std::vector<FaceType*> inBox;
2253 vcg::tri::GetInBoxFace(m2, gM, bbox,inBox);
2254 for(auto fib=inBox.begin(); fib!=inBox.end(); ++fib)
2255 {
2256 if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){
2257 fi->SetS();
2258 ++selCnt;
2259 }
2260 }
2261 inBox.clear();
2262 }
2263 return selCnt;
2264 }
2265
2266}; // end class
2269} //End Namespace Tri
2270} // End Namespace vcg
2271#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:1237
vcg::tri::Allocator::DeleteFace
static void DeleteFace(MeshType &m, FaceType &f)
Definition: allocate.h:929
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:1090
vcg::tri::Allocator::DeleteVertex
static void DeleteVertex(MeshType &m, VertexType &v)
Definition: allocate.h:941
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:195
vcg::tri::Allocator::DeleteEdge
static void DeleteEdge(MeshType &m, EdgeType &e)
Definition: allocate.h:952
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:277
vcg::tri::Clean::SortedTriple
Definition: clean.h:301
vcg::tri::Clean
Class of static functions to clean//restore meshs.
Definition: clean.h:165
vcg::tri::Clean::RemoveDegenerateVertex
static int RemoveDegenerateVertex(MeshType &m, bool DeleteVertexFlag=true)
Definition: clean.h:437
vcg::tri::Clean::RemoveFaceFoldByFlip
static int RemoveFaceFoldByFlip(MeshType &m, float normalThresholdDeg=175, bool repeat=true, bool updateTopology=true)
Definition: clean.h:1664
vcg::tri::Clean::RemoveDuplicateFace
static int RemoveDuplicateFace(MeshType &m)
Definition: clean.h:332
vcg::tri::Clean::SelectFoldedFaceFromOneRingFaces
static void SelectFoldedFaceFromOneRingFaces(MeshType &m, ScalarType cosThreshold)
Definition: clean.h:2179
vcg::tri::Clean::FlipNormalOutside
static bool FlipNormalOutside(MeshType &m)
Definition: clean.h:1596
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:1928
vcg::tri::Clean::SelectIntersectingFaces
static int SelectIntersectingFaces(MeshType &m1, MeshType &m2)
Definition: clean.h:2237
vcg::tri::Clean::IsBitTriQuadOnly
static bool IsBitTriQuadOnly(const MeshType &m)
Definition: clean.h:919
vcg::tri::Clean::IsBitTriOnly
static bool IsBitTriOnly(const MeshType &m)
Definition: clean.h:902
vcg::tri::Clean::HasZeroTexCoordFace
static bool HasZeroTexCoordFace(MeshType &m)
Definition: clean.h:1987
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:2113
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:712
vcg::tri::Clean::IsBitQuadOnly
static bool IsBitQuadOnly(const MeshType &m)
Definition: clean.h:871
vcg::tri::Clean::CountNonManifoldEdgeEE
static int CountNonManifoldEdgeEE(MeshType &m, bool SelectFlag=false)
Definition: clean.h:1057
vcg::tri::Clean::RemoveUnreferencedVertex
static int RemoveUnreferencedVertex(MeshType &m, bool DeleteVertexFlag=true)
Definition: clean.h:394
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:650
vcg::tri::Clean::MeshGenus
static int MeshGenus(int nvert, int nedges, int nfaces, int numholes, int numcomponents)
Definition: clean.h:1436
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:2143
vcg::tri::Clean::CountBitLargePolygons
static int CountBitLargePolygons(const MeshType &m)
Definition: clean.h:986
vcg::tri::Clean::HasConsistentPerFaceFauxFlag
static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
Definition: clean.h:1037
vcg::tri::Clean::SelectCreaseVertexOnEdgeMeshVE
static void SelectCreaseVertexOnEdgeMeshVE(MeshType &m, ScalarType AngleRadThr)
Given an edge mesh it selects the vertexes where the edge make an angle greater than AngleRadThr....
Definition: clean.h:623
vcg::tri::Clean::HasConsistentPerWedgeTexCoord
static bool HasConsistentPerWedgeTexCoord(MeshType &m)
Definition: clean.h:1969
vcg::tri::Clean::CountHoles
static int CountHoles(MeshType &m)
Counts the boundary loops of the mesh. Needs FF adjacency.
Definition: clean.h:1251
vcg::tri::Clean::TestFaceFaceIntersection
static bool TestFaceFaceIntersection(FaceType *f0, FaceType *f1)
Definition: clean.h:2007
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:1581
vcg::tri::Clean::CountBitQuads
static int CountBitQuads(const MeshType &m)
Definition: clean.h:934
vcg::tri::Clean::CountBitPolygons
static int CountBitPolygons(const MeshType &m)
Definition: clean.h:963
vcg::tri::Clean::IsWaterTight
static bool IsWaterTight(MeshType &m)
Definition: clean.h:1209
vcg::tri::Clean::RemoveDegenerateFace
static int RemoveDegenerateFace(MeshType &m, bool DeleteFacesFlag=true)
Definition: clean.h:477
vcg::tri::Clean::CountBitTris
static int CountBitTris(const MeshType &m)
Definition: clean.h:949
vcg::tri::Clean::RemoveDuplicateEdge
static int RemoveDuplicateEdge(MeshType &m)
Definition: clean.h:361
vcg::tri::Clean::IsRegularMesh
static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular)
Definition: clean.h:1464
vcg::tri::Clean::CountNonManifoldEdgeFF
static int CountNonManifoldEdgeFF(MeshType &m, bool SelectFlag=false)
Definition: clean.h:1095
vcg::tri::Clean::RemoveNonManifoldFace
static int RemoveNonManifoldFace(MeshType &m, bool DeleteFacesFlag=true)
Removal of faces that were incident on a non manifold edge.
Definition: clean.h:801
vcg::tri::Clean::SelectCreaseVertexOnEdgeMeshEE
static void SelectCreaseVertexOnEdgeMeshEE(MeshType &m, ScalarType AngleRadThr)
Given an edge mesh it selects the vertexes where the edge make an angle greater than AngleRadThr....
Definition: clean.h:593
vcg::tri::Clean::MergeCloseVertex
static int MergeCloseVertex(MeshType &m, const ScalarType radius)
Definition: clean.h:2042
vcg::tri::Clean::CountNonManifoldVertexFF
static int CountNonManifoldVertexFF(MeshType &m, bool selectVert=true, bool clearSelection=true)
Definition: clean.h:1151
vcg::tri::Clean::IsFFAdjacencyConsistent
static bool IsFFAdjacencyConsistent(MeshType &m)
Definition: clean.h:1953
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:471
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: color4.h:30
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:794
Generated by doxygen 1.9.6 on Sun Oct 11 2026 08:44:54