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