1 /**************************************************************************** 2 * VCGLib o o * 3 * Visual and Computer Graphics Library o o * 4 * _ O _ * 5 * Copyright(C) 2004 \/)\/ * 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 HOLE_H 25 #define HOLE_H 26 27 #include <utility> 28 #include <vector> 29 #include <qstring.h> 30 #include <float.h> 31 #include <GL/glew.h> 32 #include "vcg/simplex/face/pos.h" 33 #include "vcg/space/point3.h" 34 #include "vcg/complex/algorithms/clean.h" 35 #include "vcg/complex/algorithms/hole.h" 36 #include <vcg/complex/algorithms/closest.h> 37 #include <vcg/space/index/grid_static_ptr.h> 38 #include "vcg/space/color4.h" 39 #include "holeSetManager.h" 40 41 /** An hole type, extends vcg::tri::Hole<MESH>::Info adding more information 42 * as filling, selection, filing autocompenetration and non manifoldness. 43 * This class also allows one to fill (and restore) an hole using different criteria. 44 * 45 * FgtHole uses meshe's additional data to mark interesting face, so surfing 46 * the hole faces is driven by face-face ajacency and mark meaning. 47 * Additional data are accessible for an hole by parentManager (HoleSetManager) 48 * which links hole to a mesh. 49 * Characteristic faces for an hole are marked as: 50 * - HoleBorderFace: face which initially (before filling) have 1 or 2 border edge. 51 * - HolePatchFace: faces added to fill the hole 52 * - PatchCompFace: patch faces which are selfintersected with mesh. 53 * - BridgeFace: faces added to edit hole (unify 2 holes, subdivide an hole, partitioning a 54 * non-manifold hole in more manifold ones) 55 * - BridgeFace + HolePatchFace: this combo is used to individuate faces added to subdivide 56 * a non manifold hole and also close a non manifold hole, ie an hole made up from only 3 edge 57 * 58 * --------+-------+----+-----| --------+-------+----+------| 59 * hole /\ hole /\ hole | hole /\ f0 /\ f1| hole | f0: BridgeFace + PatchFace 60 * A / \ A / \ A | A / \ / \ | B | f1: BridgeFace 61 * / \ / \ | / \ / \ | | 62 * ______/ \/ \______| ______/ \/ \|______| 63 */ 64 template <class MESH> 65 class FgtHole : public vcg::tri::Hole<MESH>::Info 66 { 67 public: 68 69 private: 70 enum State 71 { 72 NONE = 0x0000, 73 SELECTED = 0x0001, 74 FILLED = 0x0002, 75 ACCEPTED = 0x0004, 76 COMPENET = 0x0008, 77 NONMANIF = 0x0010, 78 BRIDGED = 0x0020 79 }; 80 81 public: 82 enum FillerMode 83 { 84 Trivial, MinimumWeight, SelfIntersection 85 }; 86 87 typedef typename MESH::FaceType FaceType; 88 typedef typename MESH::FacePointer FacePointer; 89 typedef typename std::vector<FacePointer> FacePointerVector; 90 typedef typename MESH::VertexType VertexType; 91 typedef typename MESH::ScalarType ScalarType; 92 typedef typename vcg::face::Pos<FaceType> PosType; 93 typedef typename std::vector< PosType > PosVector; 94 typedef typename vcg::tri::Hole<MESH> vcgHole; 95 typedef typename vcgHole::Info HoleInfo; 96 typedef typename std::vector< FgtHole<MESH> > HoleVector; 97 typedef typename HoleVector::iterator HoleIterator; 98 typedef typename vcg::tri::TrivialEar<MESH> TrivialEar; 99 typedef typename vcg::tri::MinimumWeightEar<MESH> MinimumWeightEar; 100 typedef typename vcg::tri::SelfIntersectionEar<MESH> SelfIntersectionEar; 101 FgtHole(HoleInfo & hi,QString holeName,HoleSetManager<MESH> * parent)102 FgtHole(HoleInfo &hi, QString holeName, HoleSetManager<MESH> *parent) : 103 HoleInfo(hi.p, hi.size, hi.bb) 104 { 105 parentManager = parent; 106 name = holeName; 107 _state = ACCEPTED; 108 perimeter = HoleInfo::Perimeter(); 109 findNonManifoldness(); 110 }; 111 FgtHole(PosType startPos,QString holeName,HoleSetManager<MESH> * parent)112 FgtHole(PosType startPos, QString holeName, HoleSetManager<MESH> *parent) 113 { 114 assert(startPos.IsBorder()); 115 parentManager = parent; 116 name = holeName; 117 _state = ACCEPTED; 118 this->p = startPos; 119 updateInfo(); 120 }; 121 ~FgtHole()122 ~FgtHole() {}; 123 Size()124 inline int Size() const { return this->size; }; Perimeter()125 inline ScalarType Perimeter() const { return this->perimeter; }; IsFilled()126 inline bool IsFilled() const { return (_state & FILLED) != 0; }; IsSelected()127 inline bool IsSelected() const { return (_state & SELECTED) != 0; }; IsCompenetrating()128 inline bool IsCompenetrating() const { return IsFilled() && (_state & COMPENET) != 0; }; IsAccepted()129 inline bool IsAccepted() const { return !IsFilled() || ( (_state & ACCEPTED) != 0); }; IsNonManifold()130 inline bool IsNonManifold() const { return (_state & NONMANIF) != 0; }; IsBridged()131 inline bool IsBridged() const { return (_state & BRIDGED) != 0;; }; SetBridged(bool val)132 inline void SetBridged(bool val) 133 { 134 if(val) _state |= BRIDGED; 135 else _state &= (~BRIDGED); 136 }; 137 SetSelect(bool val)138 void SetSelect(bool val) 139 { 140 bool oldVal = IsSelected(); 141 if(val) _state |= SELECTED; 142 else _state &= (~SELECTED); 143 if(oldVal != val) 144 { 145 if(val) parentManager->nSelected++; 146 else parentManager->nSelected--; 147 } 148 }; 149 SetAccepted(bool val)150 void SetAccepted(bool val) 151 { 152 bool oldVal = IsAccepted(); 153 if(val) _state |= ACCEPTED; 154 else _state &= (~ACCEPTED); 155 if(oldVal != val) 156 { 157 if(val) parentManager->nAccepted++; 158 else parentManager->nAccepted--; 159 } 160 }; 161 SetStartPos(PosType initP)162 inline void SetStartPos(PosType initP) 163 { 164 assert(!IsFilled()); 165 this->p = initP; 166 assert(this->p.IsBorder()); 167 updateInfo(); 168 }; 169 Draw()170 void Draw() const 171 { 172 typename PosVector::const_iterator it = borderPos.begin(); 173 glBegin(GL_LINE_LOOP); 174 for( ; it != borderPos.end(); it++) 175 glVertex( it->v->P() ); 176 glEnd(); 177 }; 178 DrawCompenetratingFace(GLenum glmode)179 void DrawCompenetratingFace(GLenum glmode) const 180 { 181 assert(IsCompenetrating()); 182 183 typename std::vector<FacePointer>::const_iterator it; 184 185 glBegin(glmode); 186 for( it=patches.begin(); it != patches.end(); it++) 187 if( parentManager->IsCompFace(*it) ) 188 { 189 glVertex( (*it)->V(0)->P() ); 190 glVertex( (*it)->V(1)->P() ); 191 glVertex( (*it)->V(2)->P() ); 192 } 193 194 glEnd(); 195 } 196 197 /* Reset flags used by this plugin (holeBorder and patch) to unmark this hole and its patch. 198 */ ResetFlag()199 void ResetFlag() 200 { 201 std::vector<FacePointer> bridgesFaces; 202 if( IsFilled() ) 203 { 204 typename std::vector<FacePointer>::iterator it; 205 206 while(patches.size()>0) 207 { 208 FacePointer f = patches.back(); 209 patches.pop_back(); 210 parentManager->ClearPatchAttr(f); 211 parentManager->ClearCompAttr(f); 212 213 for(int i=0; i<3; i++) 214 { 215 FacePointer adjF = f->FFp(i); 216 parentManager->ClearHoleBorderAttr(adjF); 217 } 218 } 219 } 220 else 221 { 222 // we can walk the border to find hole's faces added by bridges 223 PosType curPos = this->p; 224 do{ 225 parentManager->ClearHoleBorderAttr(curPos.f); 226 curPos.NextB(); 227 }while( curPos != this->p ); 228 } 229 }; 230 231 232 /* Restore hole, remove patch faces applied to mesh to fill this hole. */ RestoreHole()233 void RestoreHole() 234 { 235 assert( IsFilled() ); 236 _state &= (~FILLED); 237 238 typename std::vector<FacePointer>::iterator it; 239 for(it = patches.begin(); it!=patches.end(); it++) 240 { 241 // PathcHoleFlag+BridgeFaceFlag is special case 242 if(parentManager->IsBridgeFace(*it)) continue; 243 244 assert(parentManager->IsPatchFace(*it)); 245 for(int e=0; e<3; e++) 246 { 247 if(!IsBorder(**it, e)) 248 { 249 FacePointer adjF = (*it)->FFp(e); 250 if(!parentManager->IsPatchFace(adjF)) 251 { 252 int adjEI = (*it)->FFi(e); 253 adjF->FFp( adjEI ) = adjF; 254 adjF->FFi( adjEI ) = adjEI; 255 assert(IsBorder(*adjF, adjEI)); 256 } 257 } 258 } 259 if(!(**it).IsD()) 260 vcg::tri::Allocator<MESH>::DeleteFace(*parentManager->mesh, **it); 261 } 262 patches.clear(); 263 }; 264 Fill(FillerMode mode,MESH & mesh,std::vector<FacePointer * > & local_facePointer)265 void Fill(FillerMode mode, MESH &mesh, std::vector<FacePointer * > &local_facePointer) 266 { 267 assert(!IsFilled()); 268 assert(this->p.IsBorder()); 269 switch(mode) 270 { 271 case FgtHole<MESH>::Trivial: 272 vcgHole::template FillHoleEar< TrivialEar >(mesh, this->p, local_facePointer); 273 break; 274 case FgtHole<MESH>::MinimumWeight: 275 vcgHole::template FillHoleEar< MinimumWeightEar >(mesh, this->p, local_facePointer); 276 break; 277 case FgtHole<MESH>::SelfIntersection: 278 std::vector<FacePointer * > vfp = local_facePointer; 279 SelfIntersectionEar::AdjacencyRing().clear(); 280 PosType ip = this->p; 281 do 282 { 283 PosType inp = ip; 284 do 285 { 286 inp.FlipE(); 287 inp.FlipF(); 288 SelfIntersectionEar::AdjacencyRing().push_back(inp.f); 289 } while(!inp.IsBorder()); 290 ip.NextB(); 291 }while(ip != this->p); 292 293 typename std::vector<FacePointer>::iterator fpi = SelfIntersectionEar::AdjacencyRing().begin(); 294 for( ; fpi != SelfIntersectionEar::AdjacencyRing().end(); ++fpi) 295 vfp.push_back( &*fpi ); 296 297 vcgHole::template FillHoleEar< SelfIntersectionEar >(mesh, this->p, vfp); 298 SelfIntersectionEar::AdjacencyRing().clear(); 299 break; 300 } 301 302 // hole filling leaves V flag to border vertex... resetting! 303 typename PosVector::const_iterator it = borderPos.begin(); 304 for( ;it!=borderPos.end(); it++) 305 it->v->ClearV(); 306 307 parentManager->faceAttr->UpdateSize(); 308 309 _state |= FILLED; 310 _state |= ACCEPTED; 311 _state &= (~COMPENET); 312 } 313 314 /* Check if face is a border face of this hole */ HaveBorderFace(FacePointer bFace)315 bool HaveBorderFace(FacePointer bFace) const 316 { 317 assert(parentManager->IsHoleBorderFace(bFace)); 318 typename PosVector::const_iterator it; 319 for(it=borderPos.begin(); it!= borderPos.end(); it++) 320 if( bFace == it->f ) 321 return true; 322 return false; 323 } 324 325 /* Check if pFace is a patch face of this hole */ HavePatchFace(FacePointer pFace)326 bool HavePatchFace(FacePointer pFace) const 327 { 328 assert( parentManager->IsPatchFace(pFace) ); 329 if( !IsFilled() ) 330 return false; 331 332 typename std::vector<FacePointer>::const_iterator it; 333 for(it = patches.begin(); it!=patches.end(); it++) 334 if(pFace == *it) 335 return true; 336 return false; 337 }; 338 339 /* walk over hole border, watching each adiacent faces to its vertex 340 * looking for bridge faces. 341 */ UpdateBridgingStatus()342 void UpdateBridgingStatus() 343 { 344 assert(!IsFilled()); 345 PosType curPos = this->p; 346 do{ 347 do{ 348 if( parentManager->IsBridgeFace(curPos.f) ) 349 { 350 SetBridged(true); 351 return; 352 } 353 curPos.FlipE(); 354 curPos.FlipF(); 355 }while(!curPos.IsBorder()); 356 curPos.FlipV(); 357 }while(curPos != this->p); 358 SetBridged(false); 359 }; 360 361 // concats its face reference to a vector AddFaceReference(std::vector<FacePointer * > & facesReferences)362 void AddFaceReference(std::vector<FacePointer*> &facesReferences) 363 { 364 facesReferences.push_back(&this->p.f); 365 366 typename PosVector::iterator pit; 367 for(pit=borderPos.begin(); pit != borderPos.end(); pit++) 368 facesReferences.push_back( &pit->f ); 369 370 typename std::vector<FacePointer>::iterator fit; 371 for(fit=patches.begin(); fit!=patches.end(); fit++) 372 facesReferences.push_back(&*fit); 373 }; 374 375 private: 376 377 /* Walking the hole computing vcgHole::Info data and other info */ updateInfo()378 void updateInfo() 379 { 380 assert(!IsFilled()); 381 borderPos.clear(); 382 _state &= (~NONMANIF); 383 this->bb.SetNull(); 384 this->size = 0; 385 386 PosType curPos = this->p; 387 do{ 388 assert(!curPos.f->IsD()); 389 borderPos.push_back(curPos); 390 parentManager->SetHoleBorderAttr(curPos.f); 391 this->bb.Add(curPos.v->cP()); 392 ++this->size; 393 if(curPos.v->IsV()) 394 _state |= NONMANIF; 395 else 396 curPos.v->SetV(); 397 curPos.NextB(); 398 assert(curPos.IsBorder()); 399 }while( curPos != this->p ); 400 401 curPos = this->p; 402 do{ 403 curPos.v->ClearV(); 404 curPos.NextB(); 405 }while( curPos != this->p ); 406 407 perimeter = HoleInfo::Perimeter(); 408 }; 409 410 /* Walking the hole storing vertices and finding non manifold one */ findNonManifoldness()411 void findNonManifoldness() 412 { 413 assert(!IsFilled()); 414 _state &= (~NONMANIF); 415 PosType curPos = this->p; 416 do{ 417 borderPos.push_back(curPos); 418 if(curPos.v->IsV()) 419 _state |= NONMANIF; 420 else 421 curPos.v->SetV(); 422 curPos.NextB(); 423 }while( curPos != this->p ); 424 425 curPos = this->p; 426 do{ 427 curPos.v->ClearV(); 428 curPos.NextB(); 429 }while( curPos != this->p ); 430 }; 431 432 /* set patch flag and auto-compenetration flag when needed */ updatePatchState(int patchFlag)433 void updatePatchState(int patchFlag) 434 { 435 assert( IsFilled() ); 436 _state &= (~COMPENET); 437 vcg::GridStaticPtr<FaceType, ScalarType > gM; 438 gM.Set(parentManager->mesh->face.begin(),parentManager->mesh->face.end()); 439 440 std::vector<FaceType*> inBox; 441 vcg::Box3< ScalarType> bbox; 442 getPatchFaces(patchFlag); 443 typename FacePointerVector::iterator pi = patches.begin(); 444 for( ; pi!=patches.end(); ++pi) 445 { 446 FacePointer f = *pi; 447 if(TestFaceMeshCompenetration(*parentManager->mesh, gM, f)) 448 { 449 _state |= COMPENET; 450 parentManager->SetCompAttr(f); 451 } 452 (*pi)->ClearUserBit(patchFlag); 453 parentManager->SetPatchAttr(*pi); 454 } 455 }; 456 457 458 /* First patch face is the adjacent one to initial Pos ("p" field of Hole::Info) 459 * Other patch face are found looking adjacent face on each vertex of known patch faces. 460 * NB: looking adjacent faces to vertices it can find patches also for non manifold hole. 461 */ getPatchFaces(int patchFlag)462 void getPatchFaces(int patchFlag) 463 { 464 assert( IsFilled() ); 465 patches.clear(); 466 std::vector<FacePointer> stack; 467 PosType pos = this->p; 468 pos.FlipF(); 469 assert(pos.f->IsUserBit(patchFlag)); 470 pos.f->SetV(); 471 stack.push_back(pos.f); 472 while(stack.size()>0) 473 { 474 FacePointer f = stack.back(); 475 stack.pop_back(); 476 patches.push_back(f); 477 478 // visit faces adjacent to f's vertices 479 for(int v=0; v<3; v++) 480 { 481 pos = PosType(f, v); 482 do{ 483 pos.FlipF(); 484 pos.FlipE(); 485 if(pos.f->IsUserBit(patchFlag) && !pos.f->IsV()) 486 { 487 pos.f->SetV(); 488 stack.push_back(pos.f); 489 } 490 }while(pos.f != f); 491 } 492 } 493 494 typename std::vector<FacePointer>::iterator it; 495 for(it=patches.begin(); it!=patches.end(); ++it) 496 (*it)->ClearV(); 497 }; 498 499 /********* Static functions **********/ 500 public: 501 TestFaceMeshCompenetration(MESH & mesh,vcg::GridStaticPtr<FaceType,ScalarType> & gM,const FacePointer f)502 static bool TestFaceMeshCompenetration(MESH &mesh, vcg::GridStaticPtr<FaceType, ScalarType > &gM, 503 const FacePointer f) 504 { 505 std::vector<FaceType*> inBox; 506 vcg::Box3< ScalarType> bbox; 507 508 f->GetBBox(bbox); 509 vcg::tri::GetInBoxFace(mesh, gM, bbox,inBox); 510 511 typename std::vector<FaceType*>::iterator fib; 512 for(fib=inBox.begin();fib!=inBox.end();++fib) 513 { 514 if (f != *fib) 515 { 516 if(vcg::tri::Clean<MESH>::TestFaceFaceIntersection( *fib, f )) 517 return true; 518 } 519 } 520 return false; 521 }; 522 523 524 public: HoleId()525 static int &HoleId(){static int _holeId=0; return _holeId;}; ResetHoleId()526 static void ResetHoleId() { HoleId()=0; }; GetHoleId()527 static int GetHoleId() { return ++HoleId(); }; 528 QString name; 529 530 public: 531 HoleSetManager<MESH>* parentManager; 532 std::vector<FacePointer> patches; 533 534 private: 535 int _state; 536 ScalarType perimeter; 537 538 std::vector<PosType> borderPos; 539 540 }; 541 542 #endif 543