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 // VCG headers 28 #include <vcg/complex/complex.h> 29 #include <vcg/simplex/face/pos.h> 30 #include <vcg/simplex/face/topology.h> 31 #include <vcg/simplex/edge/topology.h> 32 #include <vcg/complex/algorithms/closest.h> 33 #include <vcg/space/index/grid_static_ptr.h> 34 #include <vcg/space/index/spatial_hashing.h> 35 #include <vcg/complex/algorithms/update/selection.h> 36 #include <vcg/complex/algorithms/update/flag.h> 37 #include <vcg/complex/algorithms/update/normal.h> 38 #include <vcg/complex/algorithms/update/topology.h> 39 #include <vcg/space/triangle3.h> 40 41 namespace vcg { 42 namespace tri{ 43 44 template <class ConnectedMeshType> 45 class ConnectedComponentIterator 46 { 47 public: 48 typedef ConnectedMeshType MeshType; 49 typedef typename MeshType::VertexType VertexType; 50 typedef typename MeshType::VertexPointer VertexPointer; 51 typedef typename MeshType::VertexIterator VertexIterator; 52 typedef typename MeshType::ScalarType ScalarType; 53 typedef typename MeshType::FaceType FaceType; 54 typedef typename MeshType::FacePointer FacePointer; 55 typedef typename MeshType::FaceIterator FaceIterator; 56 typedef typename MeshType::ConstFaceIterator ConstFaceIterator; 57 typedef typename MeshType::FaceContainer FaceContainer; 58 59 public: 60 void operator ++() 61 { 62 FacePointer fpt=sf.top(); 63 sf.pop(); 64 for(int j=0;j<3;++j) 65 if( !face::IsBorder(*fpt,j) ) 66 { 67 FacePointer l=fpt->FFp(j); 68 if( !tri::IsMarked(*mp,l) ) 69 { 70 tri::Mark(*mp,l); 71 sf.push(l); 72 } 73 } 74 } 75 start(MeshType & m,FacePointer p)76 void start(MeshType &m, FacePointer p) 77 { 78 tri::RequirePerFaceMark(m); 79 mp=&m; 80 while(!sf.empty()) sf.pop(); 81 UnMarkAll(m); 82 tri::Mark(m,p); 83 sf.push(p); 84 } 85 completed()86 bool completed() { 87 return sf.empty(); 88 } 89 90 FacePointer operator *() 91 { 92 return sf.top(); 93 } 94 private: 95 std::stack<FacePointer> sf; 96 MeshType *mp; 97 }; 98 99 100 /// 101 /** \addtogroup trimesh */ 102 /*@{*/ 103 /// Class of static functions to clean//restore meshs. 104 template <class CleanMeshType> 105 class Clean 106 { 107 108 public: 109 typedef CleanMeshType MeshType; 110 typedef typename MeshType::VertexType VertexType; 111 typedef typename MeshType::VertexPointer VertexPointer; 112 typedef typename MeshType::VertexIterator VertexIterator; 113 typedef typename MeshType::ConstVertexIterator ConstVertexIterator; 114 typedef typename MeshType::EdgeIterator EdgeIterator; 115 typedef typename MeshType::EdgePointer EdgePointer; 116 typedef typename MeshType::CoordType CoordType; 117 typedef typename MeshType::ScalarType ScalarType; 118 typedef typename MeshType::FaceType FaceType; 119 typedef typename MeshType::FacePointer FacePointer; 120 typedef typename MeshType::FaceIterator FaceIterator; 121 typedef typename MeshType::ConstFaceIterator ConstFaceIterator; 122 typedef typename MeshType::FaceContainer FaceContainer; 123 typedef typename vcg::Box3<ScalarType> Box3Type; 124 125 typedef GridStaticPtr<FaceType, ScalarType > TriMeshGrid; 126 127 /* classe di confronto per l'algoritmo di eliminazione vertici duplicati*/ 128 class RemoveDuplicateVert_Compare{ 129 public: operator()130 inline bool operator()(VertexPointer const &a, VertexPointer const &b) 131 { 132 return ((*a).cP() == (*b).cP()) ? (a<b): ((*a).cP() < (*b).cP()); 133 } 134 }; 135 136 137 /** This function removes all duplicate vertices of the mesh by looking only at their spatial positions. 138 * Note that it does not update any topology relation that could be affected by this like the VT or TT relation. 139 * the reason this function is usually performed BEFORE building any topology information. 140 */ 141 static int RemoveDuplicateVertex( MeshType & m, bool RemoveDegenerateFlag=true) // V1.0 142 { 143 if(m.vert.size()==0 || m.vn==0) return 0; 144 145 std::map<VertexPointer, VertexPointer> mp; 146 size_t i,j; 147 VertexIterator vi; 148 int deleted=0; 149 int k=0; 150 size_t num_vert = m.vert.size(); 151 std::vector<VertexPointer> perm(num_vert); 152 for(vi=m.vert.begin(); vi!=m.vert.end(); ++vi, ++k) 153 perm[k] = &(*vi); 154 155 RemoveDuplicateVert_Compare c_obj; 156 157 std::sort(perm.begin(),perm.end(),c_obj); 158 159 j = 0; 160 i = j; 161 mp[perm[i]] = perm[j]; 162 ++i; 163 for(;i!=num_vert;) 164 { 165 if( (! (*perm[i]).IsD()) && 166 (! (*perm[j]).IsD()) && 167 (*perm[i]).P() == (*perm[j]).cP() ) 168 { 169 VertexPointer t = perm[i]; 170 mp[perm[i]] = perm[j]; 171 ++i; 172 Allocator<MeshType>::DeleteVertex(m,*t); 173 deleted++; 174 } 175 else 176 { 177 j = i; 178 ++i; 179 } 180 } 181 182 for(FaceIterator fi = m.face.begin(); fi!=m.face.end(); ++fi) 183 if( !(*fi).IsD() ) 184 for(k = 0; k < (*fi).VN(); ++k) 185 if( mp.find( (typename MeshType::VertexPointer)(*fi).V(k) ) != mp.end() ) 186 { 187 (*fi).V(k) = &*mp[ (*fi).V(k) ]; 188 } 189 190 191 for(EdgeIterator ei = m.edge.begin(); ei!=m.edge.end(); ++ei) 192 if( !(*ei).IsD() ) 193 for(k = 0; k < 2; ++k) 194 if( mp.find( (typename MeshType::VertexPointer)(*ei).V(k) ) != mp.end() ) 195 { 196 (*ei).V(k) = &*mp[ (*ei).V(k) ]; 197 } 198 if(RemoveDegenerateFlag) RemoveDegenerateFace(m); 199 if(RemoveDegenerateFlag && m.en>0) { 200 RemoveDegenerateEdge(m); 201 RemoveDuplicateEdge(m); 202 } 203 return deleted; 204 } 205 206 class SortedPair 207 { 208 public: SortedPair()209 SortedPair() {} SortedPair(unsigned int v0,unsigned int v1,EdgePointer _fp)210 SortedPair(unsigned int v0, unsigned int v1, EdgePointer _fp) 211 { 212 v[0]=v0;v[1]=v1; 213 fp=_fp; 214 if(v[0]>v[1]) std::swap(v[0],v[1]); 215 } 216 bool operator < (const SortedPair &p) const 217 { 218 return (v[1]!=p.v[1])?(v[1]<p.v[1]): 219 (v[0]<p.v[0]); } 220 221 bool operator == (const SortedPair &s) const 222 { 223 if( (v[0]==s.v[0]) && (v[1]==s.v[1]) ) return true; 224 return false; 225 } 226 227 unsigned int v[2]; 228 EdgePointer fp; 229 }; 230 class SortedTriple 231 { 232 public: SortedTriple()233 SortedTriple() {} SortedTriple(unsigned int v0,unsigned int v1,unsigned int v2,FacePointer _fp)234 SortedTriple(unsigned int v0, unsigned int v1, unsigned int v2,FacePointer _fp) 235 { 236 v[0]=v0;v[1]=v1;v[2]=v2; 237 fp=_fp; 238 std::sort(v,v+3); 239 } 240 bool operator < (const SortedTriple &p) const 241 { 242 return (v[2]!=p.v[2])?(v[2]<p.v[2]): 243 (v[1]!=p.v[1])?(v[1]<p.v[1]): 244 (v[0]<p.v[0]); } 245 246 bool operator == (const SortedTriple &s) const 247 { 248 if( (v[0]==s.v[0]) && (v[1]==s.v[1]) && (v[2]==s.v[2]) ) return true; 249 return false; 250 } 251 252 unsigned int v[3]; 253 FacePointer fp; 254 }; 255 256 257 /** This function removes all duplicate faces of the mesh by looking only at their vertex reference. 258 So it should be called after unification of vertices. 259 Note that it does not update any topology relation that could be affected by this like the VT or TT relation. 260 the reason this function is usually performed BEFORE building any topology information. 261 */ RemoveDuplicateFace(MeshType & m)262 static int RemoveDuplicateFace( MeshType & m) // V1.0 263 { 264 std::vector<SortedTriple> fvec; 265 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) 266 if(!(*fi).IsD()) 267 { 268 fvec.push_back(SortedTriple( tri::Index(m,(*fi).V(0)), 269 tri::Index(m,(*fi).V(1)), 270 tri::Index(m,(*fi).V(2)), 271 &*fi)); 272 } 273 std::sort(fvec.begin(),fvec.end()); 274 int total=0; 275 for(int i=0;i<int(fvec.size())-1;++i) 276 { 277 if(fvec[i]==fvec[i+1]) 278 { 279 total++; 280 tri::Allocator<MeshType>::DeleteFace(m, *(fvec[i].fp) ); 281 } 282 } 283 return total; 284 } 285 286 /** This function removes all duplicate faces of the mesh by looking only at their vertex reference. 287 So it should be called after unification of vertices. 288 Note that it does not update any topology relation that could be affected by this like the VT or TT relation. 289 the reason this function is usually performed BEFORE building any topology information. 290 */ RemoveDuplicateEdge(MeshType & m)291 static int RemoveDuplicateEdge( MeshType & m) // V1.0 292 { 293 if (m.en==0) return 0; 294 std::vector<SortedPair> eVec; 295 for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei) 296 if(!(*ei).IsD()) 297 { 298 eVec.push_back(SortedPair( tri::Index(m,(*ei).V(0)), tri::Index(m,(*ei).V(1)), &*ei)); 299 } 300 std::sort(eVec.begin(),eVec.end()); 301 int total=0; 302 for(int i=0;i<int(eVec.size())-1;++i) 303 { 304 if(eVec[i]==eVec[i+1]) 305 { 306 total++; 307 tri::Allocator<MeshType>::DeleteEdge(m, *(eVec[i].fp) ); 308 } 309 } 310 return total; 311 } 312 CountUnreferencedVertex(MeshType & m)313 static int CountUnreferencedVertex( MeshType& m) 314 { 315 return RemoveUnreferencedVertex(m,false); 316 } 317 318 319 /** This function removes that are not referenced by any face. The function updates the vn counter. 320 @param m The mesh 321 @return The number of removed vertices 322 */ 323 static int RemoveUnreferencedVertex( MeshType& m, bool DeleteVertexFlag=true) // V1.0 324 { 325 FaceIterator fi; 326 EdgeIterator ei; 327 VertexIterator vi; 328 int referredBit = VertexType::NewBitFlag(); 329 330 int j; 331 int deleted = 0; 332 333 for(vi=m.vert.begin();vi!=m.vert.end();++vi) 334 (*vi).ClearUserBit(referredBit); 335 336 for(fi=m.face.begin();fi!=m.face.end();++fi) 337 if( !(*fi).IsD() ) 338 for(j=0;j<(*fi).VN();++j) 339 (*fi).V(j)->SetUserBit(referredBit); 340 341 for(ei=m.edge.begin();ei!=m.edge.end();++ei) 342 if( !(*ei).IsD() ){ 343 (*ei).V(0)->SetUserBit(referredBit); 344 (*ei).V(1)->SetUserBit(referredBit); 345 } 346 347 for(vi=m.vert.begin();vi!=m.vert.end();++vi) 348 if( (!(*vi).IsD()) && (!(*vi).IsUserBit(referredBit))) 349 { 350 if(DeleteVertexFlag) Allocator<MeshType>::DeleteVertex(m,*vi); 351 ++deleted; 352 } 353 VertexType::DeleteBitFlag(referredBit); 354 return deleted; 355 } 356 357 /** 358 Degenerate vertices are vertices that have coords with invalid floating point values, 359 All the faces incident on deleted vertices are also deleted 360 */ RemoveDegenerateVertex(MeshType & m)361 static int RemoveDegenerateVertex(MeshType& m) 362 { 363 VertexIterator vi; 364 int count_vd = 0; 365 366 for(vi=m.vert.begin(); vi!=m.vert.end();++vi) 367 if(math::IsNAN( (*vi).P()[0]) || 368 math::IsNAN( (*vi).P()[1]) || 369 math::IsNAN( (*vi).P()[2]) ) 370 { 371 count_vd++; 372 Allocator<MeshType>::DeleteVertex(m,*vi); 373 } 374 375 FaceIterator fi; 376 int count_fd = 0; 377 378 for(fi=m.face.begin(); fi!=m.face.end();++fi) 379 if(!(*fi).IsD()) 380 if( (*fi).V(0)->IsD() || 381 (*fi).V(1)->IsD() || 382 (*fi).V(2)->IsD() ) 383 { 384 count_fd++; 385 Allocator<MeshType>::DeleteFace(m,*fi); 386 } 387 return count_vd; 388 } 389 390 /** 391 Degenerate faces are faces that are Topologically degenerate, 392 i.e. have two or more vertex reference that link the same vertex 393 (and not only two vertexes with the same coordinates). 394 All Degenerate faces are zero area faces BUT not all zero area faces are degenerate. 395 We do not take care of topology because when we have degenerate faces the 396 topology calculation functions crash. 397 */ RemoveDegenerateFace(MeshType & m)398 static int RemoveDegenerateFace(MeshType& m) 399 { 400 int count_fd = 0; 401 402 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) 403 if(!(*fi).IsD()) 404 { 405 if((*fi).V(0) == (*fi).V(1) || 406 (*fi).V(0) == (*fi).V(2) || 407 (*fi).V(1) == (*fi).V(2) ) 408 { 409 count_fd++; 410 Allocator<MeshType>::DeleteFace(m,*fi); 411 } 412 } 413 return count_fd; 414 } 415 RemoveDegenerateEdge(MeshType & m)416 static int RemoveDegenerateEdge(MeshType& m) 417 { 418 int count_ed = 0; 419 420 for(EdgeIterator ei=m.edge.begin(); ei!=m.edge.end();++ei) 421 if(!(*ei).IsD()) 422 { 423 if((*ei).V(0) == (*ei).V(1) ) 424 { 425 count_ed++; 426 Allocator<MeshType>::DeleteEdge(m,*ei); 427 } 428 } 429 return count_ed; 430 } 431 RemoveNonManifoldVertex(MeshType & m)432 static int RemoveNonManifoldVertex(MeshType& m) 433 { 434 CountNonManifoldVertexFF(m,true); 435 tri::UpdateSelection<MeshType>::FaceFromVertexLoose(m); 436 int count_removed = 0; 437 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) 438 if(!(*fi).IsD() && (*fi).IsS()) 439 Allocator<MeshType>::DeleteFace(m,*fi); 440 for(VertexIterator vi=m.vert.begin(); vi!=m.vert.end();++vi) 441 if(!(*vi).IsD() && (*vi).IsS()) { 442 ++count_removed; 443 Allocator<MeshType>::DeleteVertex(m,*vi); 444 } 445 return count_removed; 446 } 447 SplitSelectedVertexOnEdgeMesh(MeshType & m)448 static int SplitSelectedVertexOnEdgeMesh(MeshType& m) 449 { 450 tri::RequireCompactness(m); 451 tri::UpdateFlags<MeshType>::VertexClearV(m); 452 int count_split = 0; 453 for(size_t i=0;i<m.edge.size();++i) 454 { 455 for(int j=0;j<2;++j) 456 { 457 VertexPointer vp = m.edge[i].V(j); 458 if(vp->IsS()) 459 { 460 if(!vp->IsV()) 461 { 462 m.edge[i].V(j) = &*(tri::Allocator<MeshType>::AddVertex(m,vp->P())); 463 ++count_split; 464 } 465 else 466 { 467 vp->SetV(); 468 } 469 470 } 471 } 472 } 473 return count_split; 474 } 475 476 SelectNonManifoldVertexOnEdgeMesh(MeshType & m)477 static void SelectNonManifoldVertexOnEdgeMesh(MeshType &m) 478 { 479 tri::RequireCompactness(m); 480 tri::UpdateSelection<MeshType>::VertexClear(m); 481 std::vector<int> cnt(m.vn,0); 482 483 for(size_t i=0;i<m.edge.size();++i) 484 { 485 cnt[tri::Index(m,m.edge[i].V(0))]++; 486 cnt[tri::Index(m,m.edge[i].V(1))]++; 487 } 488 for(size_t i=0;i<m.vert.size();++i) 489 if(cnt[i]>2) m.vert[i].SetS(); 490 } 491 SelectCreaseVertexOnEdgeMesh(MeshType & m,ScalarType AngleRadThr)492 static void SelectCreaseVertexOnEdgeMesh(MeshType &m, ScalarType AngleRadThr) 493 { 494 tri::RequireCompactness(m); 495 tri::RequireVEAdjacency(m); 496 tri::UpdateTopology<MeshType>::VertexEdge(m); 497 for(size_t i=0;i<m.vert.size();++i) 498 { 499 std::vector<VertexPointer> VVStarVec; 500 edge::VVStarVE(&(m.vert[i]),VVStarVec); 501 if(VVStarVec.size()==2) 502 { 503 CoordType v0 = m.vert[i].P() - VVStarVec[0]->P(); 504 CoordType v1 = m.vert[i].P() - VVStarVec[1]->P(); 505 float angle = M_PI-vcg::Angle(v0,v1); 506 if(angle > AngleRadThr) m.vert[i].SetS(); 507 } 508 } 509 } 510 511 512 /// Removal of faces that were incident on a non manifold edge. 513 514 // Given a mesh with FF adjacency 515 // it search for non manifold vertices and duplicate them. 516 // Duplicated vertices are moved apart according to the move threshold param. 517 // that is a percentage of the average vector from the non manifold vertex to the barycenter of the incident faces. 518 SplitNonManifoldVertex(MeshType & m,ScalarType moveThreshold)519 static int SplitNonManifoldVertex(MeshType& m, ScalarType moveThreshold) 520 { 521 RequireFFAdjacency(m); 522 typedef std::pair<FacePointer,int> FaceInt; // a face and the index of the vertex that we have to change 523 // 524 std::vector<std::pair<VertexPointer, std::vector<FaceInt> > >ToSplitVec; 525 526 SelectionStack<MeshType> ss(m); 527 ss.push(); 528 CountNonManifoldVertexFF(m,true); 529 UpdateFlags<MeshType>::VertexClearV(m); 530 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) 531 { 532 for(int i=0;i<3;i++) 533 if((*fi).V(i)->IsS() && !(*fi).V(i)->IsV()) 534 { 535 (*fi).V(i)->SetV(); 536 face::Pos<FaceType> startPos(&*fi,i); 537 face::Pos<FaceType> curPos = startPos; 538 std::set<FaceInt> faceSet; 539 do 540 { 541 faceSet.insert(std::make_pair(curPos.F(),curPos.VInd())); 542 curPos.NextE(); 543 } while (curPos != startPos); 544 545 ToSplitVec.push_back(make_pair((*fi).V(i),std::vector<FaceInt>())); 546 547 typename std::set<FaceInt>::const_iterator iii; 548 549 for(iii=faceSet.begin();iii!=faceSet.end();++iii) 550 ToSplitVec.back().second.push_back(*iii); 551 } 552 } 553 ss.pop(); 554 // Second step actually add new vertices and split them. 555 typename tri::Allocator<MeshType>::template PointerUpdater<VertexPointer> pu; 556 VertexIterator firstVp = tri::Allocator<MeshType>::AddVertices(m,ToSplitVec.size(),pu); 557 for(size_t i =0;i<ToSplitVec.size();++i) 558 { 559 // qDebug("Splitting Vertex %i",ToSplitVec[i].first-&*m.vert.begin()); 560 VertexPointer np=ToSplitVec[i].first; 561 pu.Update(np); 562 firstVp->ImportData(*np); 563 // loop on the face to be changed, and also compute the movement vector; 564 CoordType delta(0,0,0); 565 for(size_t j=0;j<ToSplitVec[i].second.size();++j) 566 { 567 FaceInt ff=ToSplitVec[i].second[j]; 568 ff.first->V(ff.second)=&*firstVp; 569 delta+=Barycenter(*(ff.first))-np->cP(); 570 } 571 delta /= ToSplitVec[i].second.size(); 572 firstVp->P() = firstVp->P() + delta * moveThreshold; 573 firstVp++; 574 } 575 576 return ToSplitVec.size(); 577 } 578 579 580 // Auxiliary function for sorting the non manifold faces according to their area. Used in RemoveNonManifoldFace 581 struct CompareAreaFP { operatorCompareAreaFP582 bool operator ()(FacePointer const& f1, FacePointer const& f2) const { 583 return DoubleArea(*f1) < DoubleArea(*f2); 584 } 585 }; 586 587 /// Removal of faces that were incident on a non manifold edge. RemoveNonManifoldFace(MeshType & m)588 static int RemoveNonManifoldFace(MeshType& m) 589 { 590 FaceIterator fi; 591 int count_fd = 0; 592 std::vector<FacePointer> ToDelVec; 593 594 for(fi=m.face.begin(); fi!=m.face.end();++fi) 595 if (!fi->IsD()) 596 { 597 if ((!IsManifold(*fi,0))|| 598 (!IsManifold(*fi,1))|| 599 (!IsManifold(*fi,2))) 600 ToDelVec.push_back(&*fi); 601 } 602 603 std::sort(ToDelVec.begin(),ToDelVec.end(),CompareAreaFP()); 604 605 for(size_t i=0;i<ToDelVec.size();++i) 606 { 607 if(!ToDelVec[i]->IsD()) 608 { 609 FaceType &ff= *ToDelVec[i]; 610 if ((!IsManifold(ff,0))|| 611 (!IsManifold(ff,1))|| 612 (!IsManifold(ff,2))) 613 { 614 for(int j=0;j<3;++j) 615 if(!face::IsBorder<FaceType>(ff,j)) 616 vcg::face::FFDetach<FaceType>(ff,j); 617 618 Allocator<MeshType>::DeleteFace(m,ff); 619 count_fd++; 620 } 621 } 622 } 623 return count_fd; 624 } 625 626 /* Remove the faces that are out of a given range of area */ 627 static int RemoveFaceOutOfRangeArea(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)(), bool OnlyOnSelected=false) 628 { 629 int count_fd = 0; 630 MinAreaThr*=2; 631 MaxAreaThr*=2; 632 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi){ 633 if(!(*fi).IsD()) 634 if(!OnlyOnSelected || (*fi).IsS()) 635 { 636 const ScalarType doubleArea=DoubleArea<FaceType>(*fi); 637 if((doubleArea<=MinAreaThr) || (doubleArea>=MaxAreaThr) ) 638 { 639 Allocator<MeshType>::DeleteFace(m,*fi); 640 count_fd++; 641 } 642 } 643 } 644 return count_fd; 645 } 646 RemoveZeroAreaFace(MeshType & m)647 static int RemoveZeroAreaFace(MeshType& m) { return RemoveFaceOutOfRangeArea(m,0);} 648 649 650 651 /** 652 * Is the mesh only composed by quadrilaterals? 653 */ IsBitQuadOnly(const MeshType & m)654 static bool IsBitQuadOnly(const MeshType &m) 655 { 656 typedef typename MeshType::FaceType F; 657 tri::RequirePerFaceFlags(m); 658 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) { 659 unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2); 660 if ( tmp != F::FAUX0 && tmp != F::FAUX1 && tmp != F::FAUX2) return false; 661 } 662 return true; 663 } 664 665 IsFaceFauxConsistent(MeshType & m)666 static bool IsFaceFauxConsistent(MeshType &m) 667 { 668 RequirePerFaceFlags(m); 669 RequireFFAdjacency(m); 670 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD()) 671 { 672 for(int z=0;z<(*fi).VN();++z) 673 { 674 FacePointer fp = fi->FFp(z); 675 int zp = fi->FFi(z); 676 if(fi->IsF(z) != fp->IsF(zp)) return false; 677 } 678 } 679 return true; 680 } 681 682 /** 683 * Is the mesh only composed by triangles? (non polygonal faces) 684 */ IsBitTriOnly(const MeshType & m)685 static bool IsBitTriOnly(const MeshType &m) 686 { 687 tri::RequirePerFaceFlags(m); 688 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) { 689 if ( !fi->IsD() && fi->IsAnyF() ) return false; 690 } 691 return true; 692 } 693 IsBitPolygonal(const MeshType & m)694 static bool IsBitPolygonal(const MeshType &m){ 695 return !IsBitTriOnly(m); 696 } 697 698 /** 699 * Is the mesh only composed by quadrilaterals and triangles? (no pentas, etc) 700 * It assumes that the bits are consistent. In that case there can be only a single faux edge. 701 */ IsBitTriQuadOnly(const MeshType & m)702 static bool IsBitTriQuadOnly(const MeshType &m) 703 { 704 tri::RequirePerFaceFlags(m); 705 typedef typename MeshType::FaceType F; 706 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) { 707 unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2); 708 if ( tmp!=F::FAUX0 && tmp!=F::FAUX1 && tmp!=F::FAUX2 && tmp!=0 ) return false; 709 } 710 return true; 711 } 712 713 /** 714 * How many quadrilaterals? 715 * It assumes that the bits are consistent. In that case we count the tris with a single faux edge and divide by two. 716 */ CountBitQuads(const MeshType & m)717 static int CountBitQuads(const MeshType &m) 718 { 719 tri::RequirePerFaceFlags(m); 720 typedef typename MeshType::FaceType F; 721 int count=0; 722 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) { 723 unsigned int tmp = fi->cFlags()&(F::FAUX0|F::FAUX1|F::FAUX2); 724 if ( tmp==F::FAUX0 || tmp==F::FAUX1 || tmp==F::FAUX2) count++; 725 } 726 return count / 2; 727 } 728 729 /** 730 * How many triangles? (non polygonal faces) 731 */ CountBitTris(const MeshType & m)732 static int CountBitTris(const MeshType &m) 733 { 734 tri::RequirePerFaceFlags(m); 735 int count=0; 736 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) { 737 if (!(fi->IsAnyF())) count++; 738 } 739 return count; 740 } 741 742 /** 743 * How many polygons of any kind? (including triangles) 744 * it assumes that there are no faux vertexes (e.g vertices completely surrounded by faux edges) 745 */ CountBitPolygons(const MeshType & m)746 static int CountBitPolygons(const MeshType &m) 747 { 748 tri::RequirePerFaceFlags(m); 749 int count = 0; 750 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) { 751 if (fi->IsF(0)) count++; 752 if (fi->IsF(1)) count++; 753 if (fi->IsF(2)) count++; 754 } 755 return m.fn - count/2; 756 } 757 758 /** 759 * The number of polygonal faces is 760 * FN - EN_f (each faux edge hides exactly one triangular face or in other words a polygon of n edges has n-3 faux edges.) 761 * In the general case where a The number of polygonal faces is 762 * FN - EN_f + VN_f 763 * where: 764 * EN_f is the number of faux edges. 765 * VN_f is the number of faux vertices (e.g vertices completely surrounded by faux edges) 766 * as a intuitive proof think to a internal vertex that is collapsed onto a border of a polygon: 767 * it deletes 2 faces, 1 faux edges and 1 vertex so to keep the balance you have to add back the removed vertex. 768 */ CountBitLargePolygons(MeshType & m)769 static int CountBitLargePolygons(MeshType &m) 770 { 771 tri::RequirePerFaceFlags(m); 772 UpdateFlags<MeshType>::VertexSetV(m); 773 // First loop Clear all referenced vertices 774 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 775 if (!fi->IsD()) 776 for(int i=0;i<3;++i) fi->V(i)->ClearV(); 777 778 779 // Second Loop, count (twice) faux edges and mark all vertices touched by non faux edges 780 // (e.g vertexes on the boundary of a polygon) 781 int countE = 0; 782 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 783 if (!fi->IsD()) { 784 for(int i=0;i<3;++i) 785 { 786 if (fi->IsF(i)) 787 countE++; 788 else 789 { 790 fi->V0(i)->SetV(); 791 fi->V1(i)->SetV(); 792 } 793 } 794 } 795 // Third Loop, count the number of referenced vertexes that are completely surrounded by faux edges. 796 797 int countV = 0; 798 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) 799 if (!vi->IsD() && !vi->IsV()) countV++; 800 801 return m.fn - countE/2 + countV ; 802 } 803 804 805 /** 806 * Checks that the mesh has consistent per-face faux edges 807 * (the ones that merges triangles into larger polygons). 808 * A border edge should never be faux, and faux edges should always be 809 * reciprocated by another faux edges. 810 * It requires FF adjacency. 811 */ HasConsistentPerFaceFauxFlag(const MeshType & m)812 static bool HasConsistentPerFaceFauxFlag(const MeshType &m) 813 { 814 RequireFFAdjacency(m); 815 RequirePerFaceFlags(m); 816 817 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 818 if(!(*fi).IsD()) 819 for (int k=0; k<3; k++) 820 if( ( fi->IsF(k) != fi->cFFp(k)->IsF(fi->cFFi(k)) ) || 821 ( fi->IsF(k) && face::IsBorder(*fi,k)) ) 822 { 823 return false; 824 } 825 return true; 826 } 827 828 /** 829 * Count the number of non manifold edges in a polylinemesh, e.g. the edges where there are more than 2 incident faces. 830 * 831 */ 832 static int CountNonManifoldEdgeEE( MeshType & m, bool SelectFlag=false) 833 { 834 MeshAssert<MeshType>::OnlyEdgeMesh(m); 835 RequireEEAdjacency(m); 836 tri::UpdateTopology<MeshType>::EdgeEdge(m); 837 838 if(SelectFlag) UpdateSelection<MeshType>::VertexClear(m); 839 840 int nonManifoldCnt=0; 841 SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0); 842 843 // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter. 844 EdgeIterator ei; 845 for (ei = m.edge.begin(); ei != m.edge.end(); ++ei) if (!ei->IsD()) 846 { 847 TD[(*ei).V(0)]++; 848 TD[(*ei).V(1)]++; 849 } 850 851 tri::UpdateFlags<MeshType>::VertexClearV(m); 852 // Second Loop, Check that each vertex have been seen 1 or 2 times. 853 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if (!vi->IsD()) 854 { 855 if( TD[vi] >2 ) 856 { 857 if(SelectFlag) (*vi).SetS(); 858 nonManifoldCnt++; 859 } 860 } 861 return nonManifoldCnt; 862 } 863 864 /** 865 * Count the number of non manifold edges in a mesh, e.g. the edges where there are more than 2 incident faces. 866 * 867 * Note that this test is not enough to say that a mesh is two manifold, 868 * you have to count also the non manifold vertexes. 869 */ 870 static int CountNonManifoldEdgeFF( MeshType & m, bool SelectFlag=false) 871 { 872 RequireFFAdjacency(m); 873 int nmfBit[3]; 874 nmfBit[0]= FaceType::NewBitFlag(); 875 nmfBit[1]= FaceType::NewBitFlag(); 876 nmfBit[2]= FaceType::NewBitFlag(); 877 878 879 UpdateFlags<MeshType>::FaceClear(m,nmfBit[0]+nmfBit[1]+nmfBit[2]); 880 881 if(SelectFlag){ 882 UpdateSelection<MeshType>::VertexClear(m); 883 UpdateSelection<MeshType>::FaceClear(m); 884 } 885 886 int edgeCnt = 0; 887 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 888 { 889 if (!fi->IsD()) 890 { 891 for(int i=0;i<3;++i) 892 if(!IsManifold(*fi,i)) 893 { 894 if(!(*fi).IsUserBit(nmfBit[i])) 895 { 896 ++edgeCnt; 897 if(SelectFlag) 898 { 899 (*fi).V0(i)->SetS(); 900 (*fi).V1(i)->SetS(); 901 } 902 // follow the ring of faces incident on edge i; 903 face::Pos<FaceType> nmf(&*fi,i); 904 do 905 { 906 if(SelectFlag) nmf.F()->SetS(); 907 nmf.F()->SetUserBit(nmfBit[nmf.E()]); 908 nmf.NextF(); 909 } 910 while(nmf.f != &*fi); 911 } 912 } 913 } 914 } 915 return edgeCnt; 916 } 917 918 /** Count (and eventually select) non 2-Manifold vertexes of a mesh 919 * e.g. the vertices with a non 2-manif. neighbourhood but that do not belong to not 2-manif edges. 920 * typical situation two cones connected by one vertex. 921 */ 922 static int CountNonManifoldVertexFF( MeshType & m, bool selectVert = true ) 923 { 924 RequireFFAdjacency(m); 925 if(selectVert) UpdateSelection<MeshType>::VertexClear(m); 926 927 int nonManifoldCnt=0; 928 SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0); 929 930 // First Loop, just count how many faces are incident on a vertex and store it in the TemporaryData Counter. 931 FaceIterator fi; 932 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) 933 { 934 TD[(*fi).V(0)]++; 935 TD[(*fi).V(1)]++; 936 TD[(*fi).V(2)]++; 937 } 938 939 tri::UpdateFlags<MeshType>::VertexClearV(m); 940 // Second Loop. 941 // mark out of the game the vertexes that are incident on non manifold edges. 942 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) 943 { 944 for(int i=0;i<3;++i) 945 if (!IsManifold(*fi,i)) { 946 (*fi).V0(i)->SetV(); 947 (*fi).V1(i)->SetV(); 948 } 949 } 950 // Third Loop, for safe vertexes, check that the number of faces that you can reach starting 951 // from it and using FF is the same of the previously counted. 952 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) 953 { 954 for(int i=0;i<3;i++) if(!(*fi).V(i)->IsV()){ 955 (*fi).V(i)->SetV(); 956 face::Pos<FaceType> pos(&(*fi),i); 957 958 int starSizeFF = pos.NumberOfIncidentFaces(); 959 960 if (starSizeFF != TD[(*fi).V(i)]) 961 { 962 if(selectVert) (*fi).V(i)->SetS(); 963 nonManifoldCnt++; 964 } 965 } 966 } 967 return nonManifoldCnt; 968 } 969 /// Very simple test of water tightness. No boundary and no non manifold edges. 970 /// Assume that it is orientable. 971 /// It could be debated if a closed non orientable surface is watertight or not. 972 /// 973 /// The rationale of not testing orientability here is that 974 /// it requires FFAdj while this test do not require any adjacency. 975 /// IsWaterTight(MeshType & m)976 static bool IsWaterTight(MeshType & m) 977 { 978 int edgeNum=0,edgeBorderNum=0,edgeNonManifNum=0; 979 CountEdgeNum(m, edgeNum, edgeBorderNum,edgeNonManifNum); 980 return (edgeBorderNum==0) && (edgeNonManifNum==0); 981 } 982 CountEdgeNum(MeshType & m,int & total_e,int & boundary_e,int & non_manif_e)983 static void CountEdgeNum( MeshType & m, int &total_e, int &boundary_e, int &non_manif_e ) 984 { 985 std::vector< typename tri::UpdateTopology<MeshType>::PEdge > edgeVec; 986 tri::UpdateTopology<MeshType>::FillEdgeVector(m,edgeVec,true); 987 sort(edgeVec.begin(), edgeVec.end()); // Lo ordino per vertici 988 total_e=0; 989 boundary_e=0; 990 non_manif_e=0; 991 992 size_t f_on_cur_edge =1; 993 for(size_t i=0;i<edgeVec.size();++i) 994 { 995 if(( (i+1) == edgeVec.size()) || !(edgeVec[i] == edgeVec[i+1])) 996 { 997 ++total_e; 998 if(f_on_cur_edge==1) 999 ++boundary_e; 1000 if(f_on_cur_edge>2) 1001 ++non_manif_e; 1002 f_on_cur_edge=1; 1003 } 1004 else 1005 { 1006 ++f_on_cur_edge; 1007 } 1008 } // end for 1009 } 1010 1011 1012 CountHoles(MeshType & m)1013 static int CountHoles( MeshType & m) 1014 { 1015 UpdateFlags<MeshType>::FaceClearV(m); 1016 int loopNum=0; 1017 for(FaceIterator fi=m.face.begin(); fi!=m.face.end();++fi) if(!fi->IsD()) 1018 { 1019 for(int j=0;j<3;++j) 1020 { 1021 if(!fi->IsV() && face::IsBorder(*fi,j)) 1022 { 1023 face::Pos<FaceType> startPos(&*fi,j); 1024 face::Pos<FaceType> curPos=startPos; 1025 do 1026 { 1027 curPos.NextB(); 1028 curPos.F()->SetV(); 1029 } 1030 while(curPos!=startPos); 1031 ++loopNum; 1032 } 1033 } 1034 } 1035 return loopNum; 1036 } 1037 1038 /* 1039 Compute the set of connected components of a given mesh 1040 it fills a vector of pair < int , faceptr > with, for each connecteed component its size and a represnant 1041 */ CountConnectedComponents(MeshType & m)1042 static int CountConnectedComponents(MeshType &m) 1043 { 1044 std::vector< std::pair<int,FacePointer> > CCV; 1045 return ConnectedComponents(m,CCV); 1046 } 1047 ConnectedComponents(MeshType & m,std::vector<std::pair<int,FacePointer>> & CCV)1048 static int ConnectedComponents(MeshType &m, std::vector< std::pair<int,FacePointer> > &CCV) 1049 { 1050 tri::RequireFFAdjacency(m); 1051 CCV.clear(); 1052 tri::UpdateFlags<MeshType>::FaceClearV(m); 1053 std::stack<FacePointer> sf; 1054 FacePointer fpt=&*(m.face.begin()); 1055 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) 1056 { 1057 if(!((*fi).IsD()) && !(*fi).IsV()) 1058 { 1059 (*fi).SetV(); 1060 CCV.push_back(std::make_pair(0,&*fi)); 1061 sf.push(&*fi); 1062 while (!sf.empty()) 1063 { 1064 fpt=sf.top(); 1065 ++CCV.back().first; 1066 sf.pop(); 1067 for(int j=0;j<3;++j) 1068 { 1069 if( !face::IsBorder(*fpt,j) ) 1070 { 1071 FacePointer l = fpt->FFp(j); 1072 if( !(*l).IsV() ) 1073 { 1074 (*l).SetV(); 1075 sf.push(l); 1076 } 1077 } 1078 } 1079 } 1080 } 1081 } 1082 return int(CCV.size()); 1083 } 1084 ComputeValence(MeshType & m,typename MeshType::PerVertexIntHandle & h)1085 static void ComputeValence( MeshType &m, typename MeshType::PerVertexIntHandle &h) 1086 { 1087 for(VertexIterator vi=m.vert.begin(); vi!= m.vert.end();++vi) 1088 h[vi]=0; 1089 1090 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) 1091 { 1092 if(!((*fi).IsD())) 1093 for(int j=0;j<fi->VN();j++) 1094 ++h[tri::Index(m,fi->V(j))]; 1095 } 1096 } 1097 1098 /** 1099 GENUS. 1100 1101 A topologically invariant property of a surface defined as 1102 the largest number of non-intersecting simple closed curves that can be 1103 drawn on the surface without separating it. 1104 1105 Roughly speaking, it is the number of holes in a surface. 1106 The genus g of a closed surface, also called the geometric genus, is related to the 1107 Euler characteristic by the relation $chi$ by $chi==2-2g$. 1108 1109 The genus of a connected, orientable surface is an integer representing the maximum 1110 number of cuttings along closed simple curves without rendering the resultant 1111 manifold disconnected. It is equal to the number of handles on it. 1112 1113 For general polyhedra the <em>Euler Formula</em> is: 1114 1115 V - E + F = 2 - 2G - B 1116 1117 where V is the number of vertices, F is the number of faces, E is the 1118 number of edges, G is the genus and B is the number of <em>boundary polygons</em>. 1119 1120 The above formula is valid for a mesh with one single connected component. 1121 By considering multiple connected components the formula becomes: 1122 1123 V - E + F = 2C - 2Gs - B -> 2Gs = - ( V-E+F +B -2C) 1124 1125 where C is the number of connected components and Gs is the sum of 1126 the genus of all connected components. 1127 1128 Note that in the case of a mesh with boundaries the intuitive meaning of Genus is less intuitive that it could seem. 1129 A closed sphere, a sphere with one hole (e.g. a disk) and a sphere with two holes (e.g. a tube) all of them have Genus == 0 1130 1131 */ 1132 MeshGenus(int nvert,int nedges,int nfaces,int numholes,int numcomponents)1133 static int MeshGenus(int nvert,int nedges,int nfaces, int numholes, int numcomponents) 1134 { 1135 return -((nvert + nfaces - nedges + numholes - 2 * numcomponents) / 2); 1136 } 1137 MeshGenus(MeshType & m)1138 static int MeshGenus(MeshType &m) 1139 { 1140 int nvert=m.vn; 1141 int nfaces=m.fn; 1142 int boundary_e,total_e,nonmanif_e; 1143 CountEdgeNum(m,total_e,boundary_e,nonmanif_e); 1144 int numholes=CountHoles(m); 1145 int numcomponents=CountConnectedComponents(m); 1146 int G=MeshGenus(nvert,total_e,nfaces,numholes,numcomponents); 1147 return G; 1148 } 1149 1150 /** 1151 * Check if the given mesh is regular, semi-regular or irregular. 1152 * 1153 * Each vertex of a \em regular mesh has valence 6 except for border vertices 1154 * which have valence 4. 1155 * 1156 * A \em semi-regular mesh is derived from an irregular one applying 1157 * 1-to-4 subdivision recursively. (not checked for now) 1158 * 1159 * All other meshes are \em irregular. 1160 */ IsRegularMesh(MeshType & m,bool & Regular,bool & Semiregular)1161 static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular) 1162 { 1163 RequireVFAdjacency(m); 1164 Regular = true; 1165 1166 VertexIterator vi; 1167 1168 // for each vertex the number of edges are count 1169 for (vi = m.vert.begin(); vi != m.vert.end(); ++vi) 1170 { 1171 if (!vi->IsD()) 1172 { 1173 face::Pos<FaceType> he((*vi).VFp(), &*vi); 1174 face::Pos<FaceType> ht = he; 1175 1176 int n=0; 1177 bool border=false; 1178 do 1179 { 1180 ++n; 1181 ht.NextE(); 1182 if (ht.IsBorder()) 1183 border=true; 1184 } 1185 while (ht != he); 1186 1187 if (border) 1188 n = n/2; 1189 1190 if ((n != 6)&&(!border && n != 4)) 1191 { 1192 Regular = false; 1193 break; 1194 } 1195 } 1196 } 1197 1198 if (!Regular) 1199 Semiregular = false; 1200 else 1201 { 1202 // For now we do not account for semi-regularity 1203 Semiregular = false; 1204 } 1205 } 1206 1207 IsCoherentlyOrientedMesh(MeshType & m)1208 static bool IsCoherentlyOrientedMesh(MeshType &m) 1209 { 1210 RequireFFAdjacency(m); 1211 MeshAssert<MeshType>::FFAdjacencyIsInitialized(m); 1212 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 1213 if (!fi->IsD()) 1214 for(int i=0;i<3;++i) 1215 if(!face::CheckOrientation(*fi,i)) 1216 return false; 1217 1218 return true; 1219 } 1220 OrientCoherentlyMesh(MeshType & m,bool & _IsOriented,bool & _IsOrientable)1221 static void OrientCoherentlyMesh(MeshType &m, bool &_IsOriented, bool &_IsOrientable) 1222 { 1223 RequireFFAdjacency(m); 1224 MeshAssert<MeshType>::FFAdjacencyIsInitialized(m); 1225 bool IsOrientable = true; 1226 bool IsOriented = true; 1227 1228 UpdateFlags<MeshType>::FaceClearV(m); 1229 std::stack<FacePointer> faces; 1230 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 1231 { 1232 if (!fi->IsD() && !fi->IsV()) 1233 { 1234 // each face put in the stack is selected (and oriented) 1235 fi->SetV(); 1236 faces.push(&(*fi)); 1237 while (!faces.empty()) 1238 { 1239 FacePointer fp = faces.top(); 1240 faces.pop(); 1241 1242 // make consistently oriented the adjacent faces 1243 for (int j = 0; j < 3; j++) 1244 { 1245 if (!face::IsBorder(*fp,j) && face::IsManifold<FaceType>(*fp, j)) 1246 { 1247 FacePointer fpaux = fp->FFp(j); 1248 int iaux = fp->FFi(j); 1249 if (!CheckOrientation(*fpaux, iaux)) 1250 { 1251 IsOriented = false; 1252 1253 if (!fpaux->IsV()) 1254 face::SwapEdge<FaceType,true>(*fpaux, iaux); 1255 else 1256 { 1257 IsOrientable = false; 1258 break; 1259 } 1260 } 1261 if (!fpaux->IsV()) 1262 { 1263 fpaux->SetV(); 1264 faces.push(fpaux); 1265 } 1266 } 1267 } 1268 } 1269 } 1270 if (!IsOrientable) break; 1271 } 1272 _IsOriented = IsOriented; 1273 _IsOrientable = IsOrientable; 1274 } 1275 1276 1277 /// Flip the orientation of the whole mesh flipping all the faces (by swapping the first two vertices) 1278 static void FlipMesh(MeshType &m, bool selected=false) 1279 { 1280 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if(!(*fi).IsD()) 1281 if(!selected || (*fi).IsS()) 1282 { 1283 face::SwapEdge<FaceType,false>((*fi), 0); 1284 if (HasPerWedgeTexCoord(m)) 1285 std::swap((*fi).WT(0),(*fi).WT(1)); 1286 } 1287 } 1288 /// Flip a mesh so that its normals are orented outside. 1289 /// Just for safety it uses a voting scheme. 1290 /// It assumes that 1291 /// mesh has already has coherent normals. 1292 /// mesh is watertight and signle component. FlipNormalOutside(MeshType & m)1293 static bool FlipNormalOutside(MeshType &m) 1294 { 1295 if(m.vert.empty()) return false; 1296 1297 tri::UpdateNormal<MeshType>::PerVertexAngleWeighted(m); 1298 tri::UpdateNormal<MeshType>::NormalizePerVertex(m); 1299 1300 std::vector< VertexPointer > minVertVec; 1301 std::vector< VertexPointer > maxVertVec; 1302 1303 // The set of directions to be choosen 1304 std::vector< CoordType > dirVec; 1305 dirVec.push_back(CoordType(1,0,0)); 1306 dirVec.push_back(CoordType(0,1,0)); 1307 dirVec.push_back(CoordType(0,0,1)); 1308 dirVec.push_back(CoordType( 1, 1,1)); 1309 dirVec.push_back(CoordType(-1, 1,1)); 1310 dirVec.push_back(CoordType(-1,-1,1)); 1311 dirVec.push_back(CoordType( 1,-1,1)); 1312 for(size_t i=0;i<dirVec.size();++i) 1313 { 1314 Normalize(dirVec[i]); 1315 minVertVec.push_back(&*m.vert.begin()); 1316 maxVertVec.push_back(&*m.vert.begin()); 1317 } 1318 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) if(!(*vi).IsD()) 1319 { 1320 for(size_t i=0;i<dirVec.size();++i) 1321 { 1322 if( (*vi).cP().dot(dirVec[i]) < minVertVec[i]->P().dot(dirVec[i])) minVertVec[i] = &*vi; 1323 if( (*vi).cP().dot(dirVec[i]) > maxVertVec[i]->P().dot(dirVec[i])) maxVertVec[i] = &*vi; 1324 } 1325 } 1326 1327 int voteCount=0; 1328 ScalarType angleThreshold = cos(math::ToRad(85.0)); 1329 for(size_t i=0;i<dirVec.size();++i) 1330 { 1331 // 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]); 1332 // 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]); 1333 if(minVertVec[i]->N().dot(dirVec[i]) > angleThreshold ) voteCount++; 1334 if(maxVertVec[i]->N().dot(dirVec[i]) < -angleThreshold ) voteCount++; 1335 } 1336 // qDebug("votecount = %i",voteCount); 1337 if(voteCount < int(dirVec.size())/2) return false; 1338 FlipMesh(m); 1339 return true; 1340 } 1341 1342 // Search and remove small single triangle folds 1343 // - a face has normal opposite to all other faces 1344 // - choose the edge that brings to the face f1 containing the vertex opposite to that edge. 1345 static int RemoveFaceFoldByFlip(MeshType &m, float normalThresholdDeg=175, bool repeat=true) 1346 { 1347 RequireFFAdjacency(m); 1348 RequirePerVertexMark(m); 1349 //Counters for logging and convergence 1350 int count, total = 0; 1351 1352 do { 1353 tri::UpdateTopology<MeshType>::FaceFace(m); 1354 tri::UnMarkAll(m); 1355 count = 0; 1356 1357 ScalarType NormalThrRad = math::ToRad(normalThresholdDeg); 1358 ScalarType eps = 0.0001; // this epsilon value is in absolute value. It is a distance from edge in baricentric coords. 1359 //detection stage 1360 for(FaceIterator fi=m.face.begin();fi!= m.face.end();++fi ) if(!(*fi).IsV()) 1361 { Point3<ScalarType> NN = vcg::TriangleNormal((*fi)).Normalize(); 1362 if( vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(0)).Normalize()) > NormalThrRad && 1363 vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(1)).Normalize()) > NormalThrRad && 1364 vcg::AngleN(NN,TriangleNormal(*(*fi).FFp(2)).Normalize()) > NormalThrRad ) 1365 { 1366 (*fi).SetS(); 1367 //(*fi).C()=Color4b(Color4b::Red); 1368 // now search the best edge to flip 1369 for(int i=0;i<3;i++) 1370 { 1371 Point3<ScalarType> &p=(*fi).P2(i); 1372 Point3<ScalarType> L; 1373 bool ret = vcg::InterpolationParameters((*(*fi).FFp(i)),TriangleNormal(*(*fi).FFp(i)),p,L); 1374 if(ret && L[0]>eps && L[1]>eps && L[2]>eps) 1375 { 1376 (*fi).FFp(i)->SetS(); 1377 (*fi).FFp(i)->SetV(); 1378 //(*fi).FFp(i)->C()=Color4b(Color4b::Green); 1379 if(face::CheckFlipEdge<FaceType>( *fi, i )) { 1380 face::FlipEdge<FaceType>( *fi, i ); 1381 ++count; ++total; 1382 } 1383 } 1384 } 1385 } 1386 } 1387 1388 // tri::UpdateNormal<MeshType>::PerFace(m); 1389 } 1390 while( repeat && count ); 1391 return total; 1392 } 1393 1394 1395 static int RemoveTVertexByFlip(MeshType &m, float threshold=40, bool repeat=true) 1396 { 1397 RequireFFAdjacency(m); 1398 RequirePerVertexMark(m); 1399 //Counters for logging and convergence 1400 int count, total = 0; 1401 1402 do { 1403 tri::UpdateTopology<MeshType>::FaceFace(m); 1404 tri::UnMarkAll(m); 1405 count = 0; 1406 1407 //detection stage 1408 for(unsigned int index = 0 ; index < m.face.size(); ++index ) 1409 { 1410 FacePointer f = &(m.face[index]); float sides[3]; CoordType dummy; 1411 sides[0] = Distance(f->P(0), f->P(1)); 1412 sides[1] = Distance(f->P(1), f->P(2)); 1413 sides[2] = Distance(f->P(2), f->P(0)); 1414 // Find largest triangle side 1415 int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides); 1416 if( tri::IsMarked(m,f->V2(i) )) continue; 1417 1418 if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] ) 1419 { 1420 tri::Mark(m,f->V2(i)); 1421 if(face::CheckFlipEdge<FaceType>( *f, i )) { 1422 // Check if EdgeFlipping improves quality 1423 FacePointer g = f->FFp(i); int k = f->FFi(i); 1424 Triangle3<ScalarType> t1(f->P(i), f->P1(i), f->P2(i)), t2(g->P(k), g->P1(k), g->P2(k)), 1425 t3(f->P(i), g->P2(k), f->P2(i)), t4(g->P(k), f->P2(i), g->P2(k)); 1426 1427 if ( std::min( QualityFace(t1), QualityFace(t2) ) < std::min( QualityFace(t3), QualityFace(t4) )) 1428 { 1429 face::FlipEdge<FaceType>( *f, i ); 1430 ++count; ++total; 1431 } 1432 } 1433 1434 } 1435 } 1436 1437 // tri::UpdateNormal<MeshType>::PerFace(m); 1438 } 1439 while( repeat && count ); 1440 return total; 1441 } 1442 1443 static int RemoveTVertexByCollapse(MeshType &m, float threshold=40, bool repeat=true) 1444 { 1445 RequirePerVertexMark(m); 1446 //Counters for logging and convergence 1447 int count, total = 0; 1448 1449 do { 1450 tri::UnMarkAll(m); 1451 count = 0; 1452 1453 //detection stage 1454 for(unsigned int index = 0 ; index < m.face.size(); ++index ) 1455 { 1456 FacePointer f = &(m.face[index]); 1457 float sides[3]; 1458 CoordType dummy; 1459 1460 sides[0] = Distance(f->P(0), f->P(1)); 1461 sides[1] = Distance(f->P(1), f->P(2)); 1462 sides[2] = Distance(f->P(2), f->P(0)); 1463 int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides); 1464 if( tri::IsMarked(m,f->V2(i) )) continue; 1465 1466 if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] ) 1467 { 1468 tri::Mark(m,f->V2(i)); 1469 1470 int j = Distance(dummy,f->P(i))<Distance(dummy,f->P1(i))?i:(i+1)%3; 1471 f->P2(i) = f->P(j); tri::Mark(m,f->V(j)); 1472 ++count; ++total; 1473 } 1474 } 1475 1476 1477 tri::Clean<MeshType>::RemoveDuplicateVertex(m); 1478 tri::Allocator<MeshType>::CompactFaceVector(m); 1479 tri::Allocator<MeshType>::CompactVertexVector(m); 1480 } 1481 while( repeat && count ); 1482 1483 return total; 1484 } 1485 SelfIntersections(MeshType & m,std::vector<FaceType * > & ret)1486 static bool SelfIntersections(MeshType &m, std::vector<FaceType*> &ret) 1487 { 1488 RequirePerFaceMark(m); 1489 ret.clear(); 1490 int referredBit = FaceType::NewBitFlag(); 1491 tri::UpdateFlags<MeshType>::FaceClear(m,referredBit); 1492 1493 TriMeshGrid gM; 1494 gM.Set(m.face.begin(),m.face.end()); 1495 1496 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD()) 1497 { 1498 (*fi).SetUserBit(referredBit); 1499 Box3< ScalarType> bbox; 1500 (*fi).GetBBox(bbox); 1501 std::vector<FaceType*> inBox; 1502 vcg::tri::GetInBoxFace(m, gM, bbox,inBox); 1503 bool Intersected=false; 1504 typename std::vector<FaceType*>::iterator fib; 1505 for(fib=inBox.begin();fib!=inBox.end();++fib) 1506 { 1507 if(!(*fib)->IsUserBit(referredBit) && (*fib != &*fi) ) 1508 if(Clean<MeshType>::TestFaceFaceIntersection(&*fi,*fib)){ 1509 ret.push_back(*fib); 1510 if(!Intersected) { 1511 ret.push_back(&*fi); 1512 Intersected=true; 1513 } 1514 } 1515 } 1516 inBox.clear(); 1517 } 1518 1519 FaceType::DeleteBitFlag(referredBit); 1520 return (ret.size()>0); 1521 } 1522 1523 /** 1524 This function simply test that the vn and fn counters be consistent with the size of the containers and the number of deleted simplexes. 1525 */ IsSizeConsistent(MeshType & m)1526 static bool IsSizeConsistent(MeshType &m) 1527 { 1528 int DeletedVertNum=0; 1529 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi) 1530 if((*vi).IsD()) DeletedVertNum++; 1531 1532 int DeletedEdgeNum=0; 1533 for (EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei) 1534 if((*ei).IsD()) DeletedEdgeNum++; 1535 1536 int DeletedFaceNum=0; 1537 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 1538 if((*fi).IsD()) DeletedFaceNum++; 1539 1540 if(size_t(m.vn+DeletedVertNum) != m.vert.size()) return false; 1541 if(size_t(m.en+DeletedEdgeNum) != m.edge.size()) return false; 1542 if(size_t(m.fn+DeletedFaceNum) != m.face.size()) return false; 1543 1544 return true; 1545 } 1546 1547 /** 1548 This function simply test that all the faces have a consistent face-face topology relation. 1549 useful for checking that a topology modifying algorithm does not mess something. 1550 */ IsFFAdjacencyConsistent(MeshType & m)1551 static bool IsFFAdjacencyConsistent(MeshType &m) 1552 { 1553 RequireFFAdjacency(m); 1554 1555 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 1556 if(!(*fi).IsD()) 1557 { 1558 for(int i=0;i<3;++i) 1559 if(!FFCorrectness(*fi, i)) return false; 1560 } 1561 return true; 1562 } 1563 1564 /** 1565 This function simply test that a mesh has some reasonable tex coord. 1566 */ HasConsistentPerWedgeTexCoord(MeshType & m)1567 static bool HasConsistentPerWedgeTexCoord(MeshType &m) 1568 { 1569 tri::RequirePerFaceWedgeTexCoord(m); 1570 1571 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 1572 if(!(*fi).IsD()) 1573 { FaceType &f=(*fi); 1574 if( ! ( (f.WT(0).N() == f.WT(1).N()) && (f.WT(0).N() == (*fi).WT(2).N()) ) ) 1575 return false; // all the vertices must have the same index. 1576 1577 if((*fi).WT(0).N() <0) return false; // no undefined texture should be allowed 1578 } 1579 return true; 1580 } 1581 1582 /** 1583 Simple check that there are no face with all collapsed tex coords. 1584 */ HasZeroTexCoordFace(MeshType & m)1585 static bool HasZeroTexCoordFace(MeshType &m) 1586 { 1587 tri::RequirePerFaceWedgeTexCoord(m); 1588 1589 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) 1590 if(!(*fi).IsD()) 1591 { 1592 if( (*fi).WT(0).P() == (*fi).WT(1).P() && (*fi).WT(0).P() == (*fi).WT(2).P() ) return false; 1593 } 1594 return true; 1595 } 1596 1597 1598 /** 1599 This function test if two triangular faces of a mesh intersect. 1600 It assumes that the faces (as storage) are different (e.g different address) 1601 If the two faces are different but coincident (same set of vertexes) return true. 1602 if the faces share an edge no test is done. 1603 if the faces share only a vertex, the opposite edge is tested against the face 1604 */ TestFaceFaceIntersection(FaceType * f0,FaceType * f1)1605 static bool TestFaceFaceIntersection(FaceType *f0,FaceType *f1) 1606 { 1607 int sv = face::CountSharedVertex(f0,f1); 1608 if(sv==3) return true; 1609 if(sv==0) return (vcg::IntersectionTriangleTriangle<FaceType>((*f0),(*f1))); 1610 // if the faces share only a vertex, the opposite edge (as a segment) is tested against the face 1611 // to avoid degenerate cases where the two triangles have the opposite edge on a common plane 1612 // we offset the segment to test toward the shared vertex 1613 if(sv==1) 1614 { 1615 int i0,i1; ScalarType a,b; 1616 face::FindSharedVertex(f0,f1,i0,i1); 1617 CoordType shP = f0->V(i0)->P()*0.5; 1618 if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f0).V1(i0)->P()*0.5+shP,(*f0).V2(i0)->P()*0.5+shP), *f1, a, b) ) 1619 { 1620 // a,b are the param coords of the intersection point of the segment. 1621 if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false; 1622 return true; 1623 } 1624 if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f1).V1(i1)->P()*0.5+shP,(*f1).V2(i1)->P()*0.5+shP), *f0, a, b) ) 1625 { 1626 // a,b are the param coords of the intersection point of the segment. 1627 if(a+b>=1 || a<=EPSIL || b<=EPSIL ) return false; 1628 return true; 1629 } 1630 1631 } 1632 return false; 1633 } 1634 1635 1636 1637 /** 1638 This function merge all the vertices that are closer than the given radius 1639 */ MergeCloseVertex(MeshType & m,const ScalarType radius)1640 static int MergeCloseVertex(MeshType &m, const ScalarType radius) 1641 { 1642 int mergedCnt=0; 1643 mergedCnt = ClusterVertex(m,radius); 1644 RemoveDuplicateVertex(m,true); 1645 return mergedCnt; 1646 } 1647 ClusterVertex(MeshType & m,const ScalarType radius)1648 static int ClusterVertex(MeshType &m, const ScalarType radius) 1649 { 1650 if(m.vn==0) return 0; 1651 // some spatial indexing structure does not work well with deleted vertices... 1652 tri::Allocator<MeshType>::CompactVertexVector(m); 1653 typedef vcg::SpatialHashTable<VertexType, ScalarType> SampleSHT; 1654 SampleSHT sht; 1655 tri::EmptyTMark<MeshType> markerFunctor; 1656 std::vector<VertexType*> closests; 1657 int mergedCnt=0; 1658 sht.Set(m.vert.begin(), m.vert.end()); 1659 UpdateFlags<MeshType>::VertexClearV(m); 1660 for(VertexIterator viv = m.vert.begin(); viv!= m.vert.end(); ++viv) 1661 if(!(*viv).IsD() && !(*viv).IsV()) 1662 { 1663 (*viv).SetV(); 1664 Point3<ScalarType> p = viv->cP(); 1665 Box3<ScalarType> bb(p-Point3<ScalarType>(radius,radius,radius),p+Point3<ScalarType>(radius,radius,radius)); 1666 GridGetInBox(sht, markerFunctor, bb, closests); 1667 // qDebug("Vertex %i has %i closest", &*viv - &*m.vert.begin(),closests.size()); 1668 for(size_t i=0; i<closests.size(); ++i) 1669 { 1670 ScalarType dist = Distance(p,closests[i]->cP()); 1671 if(dist < radius && !closests[i]->IsV()) 1672 { 1673 // printf("%f %f \n",dist,radius); 1674 mergedCnt++; 1675 closests[i]->SetV(); 1676 closests[i]->P()=p; 1677 } 1678 } 1679 } 1680 return mergedCnt; 1681 } 1682 1683 RemoveSmallConnectedComponentsSize(MeshType & m,int maxCCSize)1684 static std::pair<int,int> RemoveSmallConnectedComponentsSize(MeshType &m, int maxCCSize) 1685 { 1686 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV; 1687 int TotalCC=ConnectedComponents(m, CCV); 1688 int DeletedCC=0; 1689 1690 ConnectedComponentIterator<MeshType> ci; 1691 for(unsigned int i=0;i<CCV.size();++i) 1692 { 1693 std::vector<typename MeshType::FacePointer> FPV; 1694 if(CCV[i].first<maxCCSize) 1695 { 1696 DeletedCC++; 1697 for(ci.start(m,CCV[i].second);!ci.completed();++ci) 1698 FPV.push_back(*ci); 1699 1700 typename std::vector<typename MeshType::FacePointer>::iterator fpvi; 1701 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi) 1702 Allocator<MeshType>::DeleteFace(m,(**fpvi)); 1703 } 1704 } 1705 return std::make_pair(TotalCC,DeletedCC); 1706 } 1707 1708 1709 /// Remove the connected components smaller than a given diameter 1710 // it returns a pair with the number of connected components and the number of deleted ones. RemoveSmallConnectedComponentsDiameter(MeshType & m,ScalarType maxDiameter)1711 static std::pair<int,int> RemoveSmallConnectedComponentsDiameter(MeshType &m, ScalarType maxDiameter) 1712 { 1713 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV; 1714 int TotalCC=ConnectedComponents(m, CCV); 1715 int DeletedCC=0; 1716 tri::ConnectedComponentIterator<MeshType> ci; 1717 for(unsigned int i=0;i<CCV.size();++i) 1718 { 1719 Box3<ScalarType> bb; 1720 std::vector<typename MeshType::FacePointer> FPV; 1721 for(ci.start(m,CCV[i].second);!ci.completed();++ci) 1722 { 1723 FPV.push_back(*ci); 1724 bb.Add((*ci)->P(0)); 1725 bb.Add((*ci)->P(1)); 1726 bb.Add((*ci)->P(2)); 1727 } 1728 if(bb.Diag()<maxDiameter) 1729 { 1730 DeletedCC++; 1731 typename std::vector<typename MeshType::FacePointer>::iterator fpvi; 1732 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi) 1733 tri::Allocator<MeshType>::DeleteFace(m,(**fpvi)); 1734 } 1735 } 1736 return std::make_pair(TotalCC,DeletedCC); 1737 } 1738 1739 /// Remove the connected components greater than a given diameter 1740 // it returns a pair with the number of connected components and the number of deleted ones. RemoveHugeConnectedComponentsDiameter(MeshType & m,ScalarType minDiameter)1741 static std::pair<int,int> RemoveHugeConnectedComponentsDiameter(MeshType &m, ScalarType minDiameter) 1742 { 1743 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV; 1744 int TotalCC=ConnectedComponents(m, CCV); 1745 int DeletedCC=0; 1746 tri::ConnectedComponentIterator<MeshType> ci; 1747 for(unsigned int i=0;i<CCV.size();++i) 1748 { 1749 Box3f bb; 1750 std::vector<typename MeshType::FacePointer> FPV; 1751 for(ci.start(m,CCV[i].second);!ci.completed();++ci) 1752 { 1753 FPV.push_back(*ci); 1754 bb.Add((*ci)->P(0)); 1755 bb.Add((*ci)->P(1)); 1756 bb.Add((*ci)->P(2)); 1757 } 1758 if(bb.Diag()>minDiameter) 1759 { 1760 DeletedCC++; 1761 typename std::vector<typename MeshType::FacePointer>::iterator fpvi; 1762 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi) 1763 tri::Allocator<MeshType>::DeleteFace(m,(**fpvi)); 1764 } 1765 } 1766 return std::make_pair(TotalCC,DeletedCC); 1767 } 1768 1769 1770 1771 /** 1772 Select the folded faces using an angle threshold on the face normal. 1773 The face is selected if the dot product between the face normal and the normal of the plane fitted 1774 using the vertices of the one ring faces is below the cosThreshold. 1775 The cosThreshold requires a negative cosine value (a positive value is clamp to zero). 1776 */ SelectFoldedFaceFromOneRingFaces(MeshType & m,ScalarType cosThreshold)1777 static void SelectFoldedFaceFromOneRingFaces(MeshType &m, ScalarType cosThreshold) 1778 { 1779 tri::RequireVFAdjacency(m); 1780 tri::RequirePerFaceNormal(m); 1781 tri::RequirePerVertexNormal(m); 1782 vcg::tri::UpdateSelection<MeshType>::FaceClear(m); 1783 vcg::tri::UpdateNormal<MeshType>::PerFaceNormalized(m); 1784 vcg::tri::UpdateNormal<MeshType>::PerVertexNormalized(m); 1785 vcg::tri::UpdateTopology<MeshType>::VertexFace(m); 1786 if (cosThreshold > 0) 1787 cosThreshold = 0; 1788 1789 #pragma omp parallel for schedule(dynamic, 10) 1790 for (int i = 0; i < m.face.size(); i++) 1791 { 1792 std::vector<typename MeshType::VertexPointer> nearVertex; 1793 std::vector<typename MeshType::CoordType> point; 1794 typename MeshType::FacePointer f = &m.face[i]; 1795 for (int j = 0; j < 3; j++) 1796 { 1797 std::vector<typename MeshType::VertexPointer> temp; 1798 vcg::face::VVStarVF<typename MeshType::FaceType>(f->V(j), temp); 1799 typename std::vector<typename MeshType::VertexPointer>::iterator iter = temp.begin(); 1800 for (; iter != temp.end(); iter++) 1801 { 1802 if ((*iter) != f->V1(j) && (*iter) != f->V2(j)) 1803 { 1804 nearVertex.push_back((*iter)); 1805 point.push_back((*iter)->P()); 1806 } 1807 } 1808 nearVertex.push_back(f->V(j)); 1809 point.push_back(f->P(j)); 1810 } 1811 1812 if (point.size() > 3) 1813 { 1814 vcg::Plane3<typename MeshType::ScalarType> plane; 1815 vcg::FitPlaneToPointSet(point, plane); 1816 float avgDot = 0; 1817 for (int j = 0; j < nearVertex.size(); j++) 1818 avgDot += plane.Direction().dot(nearVertex[j]->N()); 1819 avgDot /= nearVertex.size(); 1820 typename MeshType::VertexType::NormalType normal; 1821 if (avgDot < 0) 1822 normal = -plane.Direction(); 1823 else 1824 normal = plane.Direction(); 1825 if (normal.dot(f->N()) < cosThreshold) 1826 f->SetS(); 1827 } 1828 } 1829 } 1830 1831 }; // end class 1832 /*@}*/ 1833 1834 } //End Namespace Tri 1835 } // End Namespace vcg 1836 #endif 1837