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 BRIDGE_H 25 #define BRIDGE_H 26 27 #include <qstring.h> 28 #include <utility> 29 #include <vcg/simplex/face/topology.h> 30 #include "vcg/space/line2.h" 31 #include "vcg/space/triangle3.h" 32 #include "fgtHole.h" 33 #include "holeSetManager.h" 34 #include <ctime> 35 36 template <class MESH> class FgtHole; 37 template <class MESH> class HoleSetManager; 38 39 /* Struct rappresenting the mesh edge where the bridge starts/ends. */ 40 template <class MESH> 41 struct BridgeAbutment 42 { 43 public: BridgeAbutmentBridgeAbutment44 BridgeAbutment() { f=0; z=0; h=0; }; 45 BridgeAbutmentBridgeAbutment46 BridgeAbutment(typename MESH::FacePointer pface, int edgeIndex, FgtHole<MESH>* phole) 47 { 48 f = pface; 49 z = edgeIndex; 50 h = phole; 51 }; 52 SetNullBridgeAbutment53 inline void SetNull() { f=0; }; IsNullBridgeAbutment54 inline bool IsNull() const { return f==0; }; 55 56 typename MESH::FacePointer f; 57 int z; 58 FgtHole<MESH>* h; 59 }; 60 61 /* Class rappresenting callback for feedback while auto bridging is running. 62 * It's necessary because auto bridging can spent a lot of time computing 63 * and user must know it is working. 64 */ 65 class AutoBridgingCallback 66 { 67 public: GetOffset()68 inline int GetOffset() const { return offset; }; 69 virtual void Invoke(int) = 0; 70 71 protected: 72 int offset; // minor time before 2 calling (in ms) 73 }; 74 75 template <class MESH> 76 class FgtBridgeBase 77 { 78 public: 79 typedef typename MESH::FaceType FaceType; 80 typedef typename MESH::FacePointer FacePointer; 81 typedef typename vcg::face::Pos<FaceType> PosType; 82 83 public: 84 virtual ~FgtBridgeBase() = default; 85 virtual PosType GetAbutmentA() const =0; 86 virtual PosType GetAbutmentB() const =0; 87 88 virtual void ResetFlag() = 0; 89 virtual void DeleteFromMesh() = 0; AddFaceReference(std::vector<FacePointer * > &)90 virtual inline void AddFaceReference(std::vector<FacePointer*> & /* facesReferences */) {}; 91 92 virtual inline bool IsNull() const = 0; 93 virtual inline bool IsDeleted() const = 0; 94 95 protected: 96 HoleSetManager<MESH>* parentManager; 97 }; 98 99 100 /** Bridge between different FgtHoles or into the same one. 101 * Bridges rapresent connection between two border edges of different faces. 102 * Connection consists in 2 face adjcent each other over an edge and adjcent 103 * with a mesh face over another edge, so both faces have a border edge. 104 * 105 * Bridge can connect 2 edge belong the same hole, result are 2 new holes. 106 * In this case bridge could be adjacent to mesh if edge are next, so this 107 * bridge could not been build. 108 * 109 * Bridge can also connect 2 or more different holes in only one hole. 110 * 111 * \ / B \ / \ / B \ / 112 * +------+-----+------+ +------+-----+------+ 113 * | | | |\ f1 | | 114 * | | | | \ | | 115 * | hole | | hole | \ | hole | 116 * | | | | \ | | 117 * | | | | f0 \| | 118 * +------+-----+------+ +------+-----+------+ 119 * / \ A / \ / \ A / \ 120 * GOOD BRIDGE 121 * f0 and f1 are adjacent only with one mesh face 122 * 123 * \ / B \ / \ / B \ / | 124 * +-----+--- +-----+--- | ---+------+------ ---+------+-------- 125 * /| /| f1 /| | \ A / \ A /|\ 126 * / | / | / | | \ / \ / | \ 127 * C | hole C | / | hole | hole \/ hole hole \/ | \ hole 128 * \ | \ | / | | /\ /\f0| \ 129 * \| \|/ f0 | | / \ / \ | f1 \ 130 * +-----+--- +-----+--- | / B \ / B \| \ 131 * / \ A / \ / \ A / \ | ---+------+------ ---+------+------+--- 132 * NO GOOD BRIDGE | Hole Non-Manifold NO GOOD BRIDGE 133 * f1 adjacent to B and C f0 adjacent to A and B 134 */ 135 136 #define SIDE_EDGE_OPTA 2 137 #define ADJ_EDGE_OPTA 1 138 139 #define SIDE_EDGE_OPTB 1 140 #define ADJ_EDGE_OPTB 2 141 142 template <class MESH> 143 class FgtBridge: public FgtBridgeBase<MESH> 144 { 145 typedef BridgeAbutment<MESH> AbutmentType; 146 typedef typename MESH::FaceType FaceType; 147 typedef typename MESH::ScalarType ScalarType; 148 typedef typename vcg::face::Pos<FaceType> PosType; 149 typedef FgtHole<MESH> HoleType; 150 typedef typename std::vector<HoleType> HoleVector; 151 typedef typename MESH::FacePointer FacePointer; 152 typedef typename MESH::FaceIterator FaceIterator; 153 typedef typename vcg::GridStaticPtr<FaceType, ScalarType > GridType; 154 typedef typename std::vector< FgtBridge<MESH> > BridgeVector; 155 typedef typename BridgeVector::iterator BridgeIterator; 156 typedef typename MESH::VertexType VertexType; 157 158 public: 159 enum BridgeOption {NoOne, OptA, OptB}; 160 FgtBridge(HoleSetManager<MESH> * parent)161 FgtBridge(HoleSetManager<MESH>* parent) 162 { 163 f0=0; 164 f0=0; 165 this->parentManager = parent; 166 }; 167 AddFaceReference(std::vector<FacePointer * > & facesReferences)168 inline void AddFaceReference(std::vector<FacePointer*> &facesReferences) 169 { 170 assert(!IsNull()); 171 assert(!IsDeleted()); 172 facesReferences.push_back(&f0); 173 facesReferences.push_back(&f1); 174 }; 175 GetAbutmentA()176 inline PosType GetAbutmentA() const { 177 return PosType( f0->FFp(0), f0->FFi(0) ); 178 }; GetAbutmentB()179 inline PosType GetAbutmentB() const { 180 return PosType( f1->FFp(0), f1->FFi(0) ); 181 }; 182 GetSideA()183 inline PosType GetSideA() const{ 184 if( opt==OptA ) return PosType(f0, SIDE_EDGE_OPTA); 185 else return PosType(f0, SIDE_EDGE_OPTB); 186 }; 187 GetSideB()188 inline PosType GetSideB() const{ 189 if( opt==OptA ) return PosType(f1, SIDE_EDGE_OPTA); 190 else return PosType(f1, SIDE_EDGE_OPTB); 191 }; 192 IsNull()193 inline bool IsNull() const { return f0==0 && f1==0; }; IsDeleted()194 inline bool IsDeleted() const { return f0->IsD() && f1->IsD(); }; 195 ResetFlag()196 void ResetFlag() 197 { 198 assert( !IsNull() ); 199 assert( this->parentManager->IsBridgeFace( f0 ) ); 200 assert( this->parentManager->IsBridgeFace( f1 ) ); 201 202 this->parentManager->ClearBridgeAttr( f0 ); 203 this->parentManager->ClearBridgeAttr( f1 ); 204 }; 205 DeleteFromMesh()206 void DeleteFromMesh() 207 { 208 assert(!IsNull() && !IsDeleted()); 209 if( !f0->IsD() ) 210 vcg::tri::Allocator<MESH>::DeleteFace(*this->parentManager->mesh, *f0); 211 if( !f1->IsD() ) 212 vcg::tri::Allocator<MESH>::DeleteFace(*this->parentManager->mesh, *f1); 213 214 // update mesh topology after bridge faces removal, restore border 215 for(int e=0; e<3; e++) 216 { 217 if(!vcg::face::IsBorder<FaceType>(*f0, e)) 218 { 219 FacePointer adjF = f0->FFp(e); 220 if(!this->parentManager->IsBridgeFace(adjF)) 221 { 222 int adjEI = f0->FFi(e); 223 adjF->FFp( adjEI ) = adjF; 224 adjF->FFi( adjEI ) = adjEI; 225 assert(vcg::face::IsBorder<FaceType>(*adjF, adjEI)); 226 } 227 } 228 229 if(!vcg::face::IsBorder<FaceType>(*f1, e)) 230 { 231 FacePointer adjF = f1->FFp(e); 232 if(!this->parentManager->IsBridgeFace(adjF)) 233 { 234 int adjEI = f1->FFi(e); 235 adjF->FFp( adjEI ) = adjF; 236 adjF->FFi( adjEI ) = adjEI; 237 assert(vcg::face::IsBorder<FaceType>(*adjF, adjEI)); 238 } 239 } 240 } 241 }; 242 243 private: 244 245 void build(AbutmentType sideA, AbutmentType sideB, BridgeOption o, std::vector<FacePointer *> &app, bool test=false) 246 { 247 opt = o; 248 if(test) 249 if(!testAbutmentDistance(sideA, sideB) && (opt=computeBestBridgeOpt(sideA, sideB)) == NoOne) 250 { 251 f0 = 0; f1 = 0; 252 opt = NoOne; 253 return; 254 } 255 256 assert(testAbutmentDistance(sideA, sideB)); 257 assert(opt!=NoOne); 258 259 app.push_back(&sideA.f); 260 app.push_back(&sideB.f); 261 FaceIterator fit = vcg::tri::Allocator<MESH>::AddFaces(*this->parentManager->mesh, 2, app); 262 this->parentManager->faceAttr->UpdateSize(); 263 app.pop_back(); 264 app.pop_back(); 265 266 f0 = &*fit; 267 f1 = &*(fit+1); 268 269 this->parentManager->SetBridgeAttr(f0); 270 this->parentManager->SetBridgeAttr(f1); 271 this->parentManager->SetHoleBorderAttr(f0); 272 this->parentManager->SetHoleBorderAttr(f1); 273 274 this->parentManager->ClearHoleBorderAttr(sideA.f); 275 this->parentManager->ClearHoleBorderAttr(sideB.f); 276 277 // the index of edge adjacent between new 2 face, is the same for both new faces 278 int adjEdgeIndex = -1; 279 280 // the index of edge adjacent between new 2 face, is the same for both new faces 281 int sideEdgeIndex = -1; 282 283 setVertexByOption(sideA, sideB, opt, *f0, *f1); 284 if( opt == OptA ) 285 { 286 adjEdgeIndex = ADJ_EDGE_OPTA; 287 sideEdgeIndex = SIDE_EDGE_OPTA; 288 } 289 else 290 { 291 adjEdgeIndex = ADJ_EDGE_OPTB; 292 sideEdgeIndex = SIDE_EDGE_OPTB; 293 } 294 295 f0->N() = vcg::TriangleNormal(*f0); 296 f1->N() = vcg::TriangleNormal(*f1); 297 298 //edges delle facce adiacenti alla mesh 299 f0->FFp(0) = sideA.f; 300 f0->FFi(0) = sideA.z; 301 f1->FFp(0) = sideB.f; 302 f1->FFi(0) = sideB.z; 303 304 sideA.f->FFp(sideA.z) = f0; 305 sideA.f->FFi(sideA.z) = 0; 306 sideB.f->FFp(sideB.z) = f1; 307 sideB.f->FFi(sideB.z) = 0; 308 309 // edges adiacenti tra le 2 facce appena inserite, edge "condiviso" 310 f0->FFp(adjEdgeIndex) = f1; 311 f0->FFi(adjEdgeIndex) = adjEdgeIndex; 312 f1->FFp(adjEdgeIndex) = f0; 313 f1->FFi(adjEdgeIndex) = adjEdgeIndex; 314 315 //edges laterali del ponte, quelli che restano di bordo 316 f0->FFp(sideEdgeIndex) = f0; 317 f0->FFi(sideEdgeIndex) = sideEdgeIndex; 318 f1->FFp(sideEdgeIndex) = f1; 319 f1->FFi(sideEdgeIndex) = sideEdgeIndex; 320 321 assert( vcg::face::BorderCount(*f0)==1 ); 322 assert( vcg::face::BorderCount(*f1)==1 ); 323 assert( this->parentManager->IsBridgeFace( f0 ) ); 324 assert( this->parentManager->IsBridgeFace( f1 ) ); 325 }; 326 327 /*** funzioni statiche ***/ 328 329 public: 330 331 /* Build a bridge between 2 border edge. 332 * If the bridge is inside the same hole it cannot be adjacent the hole border, 333 * this means fill another sub hole. 334 */ CreateBridge(AbutmentType & sideA,AbutmentType & sideB,HoleSetManager<MESH> * holesManager,QString & err)335 static bool CreateBridge(AbutmentType &sideA, AbutmentType &sideB, HoleSetManager<MESH>* holesManager, QString &err) 336 { 337 assert( vcg::face::IsBorder<FaceType>(*sideA.f, sideA.z) && 338 vcg::face::IsBorder<FaceType>(*sideB.f, sideB.z)); 339 assert(!sideA.h->IsFilled() && !sideB.h->IsFilled()); 340 341 std::vector<FacePointer *> tmpFaceRef; 342 //if(app!=0) 343 // tmpFaceRef.insert(tmpFaceRef.end(), app->begin(), app->end()); 344 //holesManager->AddFaceReference(tmpFaceRef); 345 346 ScalarType q; 347 BridgeOption opt = computeBestBridgeOpt(sideA, sideB, &q); 348 if(opt == NoOne) 349 { 350 err = QString("Bridge is compenetrating with mesh."); 351 return false; 352 } 353 354 if(sideA.h == sideB.h) 355 { 356 if( testAbutmentDistance(sideA, sideB) ) 357 subdivideHoleWithBridge(sideA, sideB, opt, holesManager, tmpFaceRef); 358 else 359 { 360 err = QString("Bridge has sides adjacent to mesh."); 361 return false; 362 } 363 } 364 else 365 unifyHolesWithBridge(sideA, sideB, opt, holesManager, tmpFaceRef); 366 return true; 367 }; 368 369 370 /* Build a bridge inner to the same hole. It chooses the best bridge computing quality 371 * of 2 faces and similarity (as number of edge) of two next hole. Bridge is build follow 372 * bridge's rule, bridge must have 2 border edge. 373 * infoLabel parameter is used to show work progress. 374 * Return number of bridge built. 375 */ 376 static bool AutoSelfBridging(HoleSetManager<MESH>* holesManager, double dist_coeff=0.0, std::vector<FacePointer *> *app=0) 377 { 378 bool err = false; 379 time_t timer; 380 if(holesManager->autoBridgeCB != 0) 381 { 382 holesManager->autoBridgeCB->Invoke(0); 383 timer = clock(); 384 } 385 GridType gM; 386 gM.Set(holesManager->mesh->face.begin(),holesManager->mesh->face.end()); 387 388 std::vector<FacePointer *> tmpFaceRef; 389 AbutmentType sideA, sideB; 390 BridgeOption bestOpt; 391 392 int nh = holesManager->holes.size(); 393 for(int h=0; h<nh; ++h) 394 { 395 HoleType &thehole = holesManager->holes.at(h); 396 if(!thehole.IsSelected() || thehole.Size()<6 ) 397 continue; 398 assert(!thehole.IsFilled()); 399 400 ScalarType maxQuality = -1; 401 402 // initP: first bridge abutment 403 PosType initP = thehole.p; 404 for(int i=0; i<thehole.Size();i++) 405 { 406 // initP: second bridge abutment 407 PosType endP = initP; 408 endP.NextB();endP.NextB(); 409 for(int j=3; j<=thehole.Size()/2; j++) 410 { 411 endP.NextB(); 412 413 // two edge used as bridge abutment are adjacent to the same face... bridge can't be build 414 // i due edge di bordo sono gia' collegati da 2 triangoli adiacenti, 415 // il bridge si sovrapporrebbe a questi 2 triangoli 416 if( endP.f->FFp(0) == initP.f || 417 endP.f->FFp(1) == initP.f || 418 endP.f->FFp(2) == initP.f ) 419 continue; 420 421 AbutmentType a(initP.f, initP.z, &thehole); 422 AbutmentType b(endP.f, endP.z, &thehole); 423 if(!testAbutmentDistance(a,b)) 424 continue; 425 426 ScalarType q; 427 BridgeOption opt = computeBestBridgeOpt(a, b, &q, &gM); 428 if(opt != NoOne) 429 { 430 q += dist_coeff * j; // add distance weight 431 if( q > maxQuality) 432 { 433 maxQuality = q; 434 bestOpt = opt; 435 sideA.f=initP.f; sideA.z=initP.z; sideA.h=&thehole; 436 sideB.f=endP.f; sideB.z=endP.z; sideB.h=&thehole; 437 } 438 } 439 440 if(holesManager->autoBridgeCB != 0) 441 { 442 if(int(clock()) - timer > holesManager->autoBridgeCB->GetOffset()) 443 { 444 float progress = (float)(((float)( ((float)j/(thehole.Size()-3)) + i) / thehole.Size()) + h) / nh; 445 holesManager->autoBridgeCB->Invoke(progress*100); 446 timer = clock(); 447 } 448 } 449 }// scansione del edge di arrivo 450 451 initP.NextB(); 452 }// scansione dell'edge di partenza 453 454 assert(vcg::face::IsBorder<FaceType>(*sideA.f, sideA.z)); 455 assert(vcg::face::IsBorder<FaceType>(*sideB.f, sideB.z)); 456 457 if( maxQuality > -1) 458 { 459 tmpFaceRef.clear(); 460 if(app!=0) 461 tmpFaceRef.insert(tmpFaceRef.end(), app->begin(), app->end()); 462 holesManager->AddFaceReference(tmpFaceRef); 463 subdivideHoleWithBridge(sideA, sideB, bestOpt, holesManager, tmpFaceRef); 464 gM.Set(holesManager->mesh->face.begin(), holesManager->mesh->face.end()); 465 } 466 else 467 err = true; 468 } //scansione degli holes 469 if(err) return false; 470 else return true; 471 }; 472 473 474 /* It connects iteratively selected holes with the best bridge. 475 * Result is unique hole instead of init holes. 476 * Return number of bridges built. 477 */ 478 static void AutoMultiBridging(HoleSetManager<MESH>* holesManager, std::vector<FacePointer *> *app=0 ) 479 { 480 int timer; 481 if(holesManager->autoBridgeCB != 0) 482 { 483 holesManager->autoBridgeCB->Invoke(0); 484 timer = clock(); 485 } 486 487 GridType gM; 488 489 std::vector<FacePointer *> tmpFaceRef; 490 AbutmentType sideA, sideB; 491 BridgeOption bestOpt; 492 493 std::vector<HoleType*> selectedHoles; 494 typename std::vector<HoleType*>::iterator shit1, shit2; 495 typename HoleVector::iterator hit; 496 497 int nIteration = -1; 498 int iteration = 0; 499 // iterate, unify holes, until selected hole is only one 500 do{ 501 sideA.SetNull(); 502 sideB.SetNull(); 503 504 // prendo gli hole selezionati 505 selectedHoles.clear(); 506 for(hit=holesManager->holes.begin(); hit!=holesManager->holes.end(); hit++) 507 if(hit->IsSelected()) 508 selectedHoles.push_back(&*hit); 509 510 if(selectedHoles.size() < 2) 511 return; 512 gM.Set(holesManager->mesh->face.begin(),holesManager->mesh->face.end()); 513 514 float casesViewed = 0, cases2View = 0; 515 for(shit1=selectedHoles.begin(); shit1!=selectedHoles.end(); shit1++) 516 for(shit2=shit1+1; shit2!=selectedHoles.end(); shit2++) 517 cases2View += (*shit1)->Size() * (*shit2)->Size(); 518 519 if(nIteration == -1) 520 nIteration = selectedHoles.size()-1; 521 522 // cerco la miglior combinazione tra le facce di un hole con quelle di un'altro 523 ScalarType maxQuality = -1; 524 for(shit1=selectedHoles.begin(); shit1!=selectedHoles.end(); shit1++) 525 { 526 for(shit2=shit1+1; shit2!=selectedHoles.end(); shit2++) 527 { 528 PosType ph1((*shit1)->p.f, (*shit1)->p.z); 529 PosType ph2((*shit2)->p.f, (*shit2)->p.z); 530 do{ //scansione edge di bordo del primo buco 531 do{ 532 ScalarType q; 533 AbutmentType a( ph1.f, ph1.z, *shit1 ); 534 AbutmentType b( ph2.f, ph2.z, *shit2 ); 535 BridgeOption opt = computeBestBridgeOpt(a, b, &q, &gM); 536 if(opt != NoOne) 537 if(q > maxQuality) 538 { 539 maxQuality = q; 540 sideA = a; 541 sideB = b; 542 bestOpt = opt; 543 } 544 545 if(holesManager->autoBridgeCB != 0) 546 { 547 if(int(clock()) - timer > holesManager->autoBridgeCB->GetOffset()) 548 { 549 int progress = ( (100 * ( iteration +(casesViewed/cases2View)))/nIteration ); 550 holesManager->autoBridgeCB->Invoke(progress); 551 timer = clock(); 552 } 553 } 554 555 casesViewed++; 556 ph2.NextB(); 557 }while(ph2 != (*shit2)->p); 558 559 ph1.NextB(); 560 }while(ph1 != (*shit1)->p); 561 } // for(shit2=shit1+1; shit2!=selectedHoles.end(); shit2++) 562 } 563 564 // adesso ho la miglior coppia di edge si deve creare il bridge 565 assert(!sideA.IsNull() && !sideB.IsNull()); 566 567 // la rimozione di hole dovuta alla unifyHoles.. provoca l'aggiornamento della lista di holes 568 // pertanto si deve avere sempre aggiornata la lista dei riferimenti alle facce 569 // la quale dipende anche dagli holes 570 tmpFaceRef.clear(); 571 if(app!=0) 572 tmpFaceRef.insert(tmpFaceRef.end(), app->begin(), app->end()); 573 holesManager->AddFaceReference(tmpFaceRef); 574 575 if(maxQuality > -1) 576 unifyHolesWithBridge(sideA, sideB, bestOpt, holesManager, tmpFaceRef); 577 else 578 return; 579 iteration ++; 580 }while(true); 581 return; 582 }; 583 584 585 private: 586 /* Compute distance between bridge side to allow no bridge adjacent to hole border. 587 * A bridge must have 2 border faces. 588 */ testAbutmentDistance(const AbutmentType & sideA,const AbutmentType & sideB)589 static bool testAbutmentDistance(const AbutmentType &sideA, const AbutmentType &sideB) 590 { 591 if(sideA.h != sideB.h) return true; 592 593 // at least 2 edges have to be between 2 bridge side. 594 if(!sideA.h->IsNonManifold()) 595 { 596 // so adjacent edges of a side haven't to share a vertex with other side. 597 PosType pos(sideA.f, sideA.z); 598 assert(pos.IsBorder()); 599 pos.NextB(); 600 if(pos.v == sideB.f->V0(sideB.z)) return false; 601 if(pos.v == sideB.f->V1(sideB.z)) return false; 602 603 pos = PosType(sideA.f, sideA.z); 604 pos.FlipV(); 605 pos.NextB(); 606 if(pos.v == sideB.f->V0(sideB.z)) return false; 607 if(pos.v == sideB.f->V1(sideB.z)) return false; 608 } 609 else 610 { 611 // if exist a face which share a vertex with each side then the bridge cannot be built 612 PosType initPos(sideA.f, sideA.z); 613 PosType curPos=initPos; 614 615 VertexType* va0=sideA.f->V0(sideA.z); 616 VertexType* va1=sideA.f->V1(sideA.z); 617 VertexType* vb0=sideB.f->V0(sideB.z); 618 VertexType* vb1=sideB.f->V1(sideB.z); 619 620 do{ 621 VertexType* cv0=curPos.f->V0(curPos.z); 622 VertexType* cv1=curPos.f->V1(curPos.z); 623 if( cv0 == va0 || cv1 == va0 || 624 cv0 == va1 || cv1 == va1 ) 625 if( cv0 == vb0 || cv1 == vb0 || 626 cv0 == vb1 || cv1 == vb1 ) 627 return false; 628 629 curPos.NextB(); 630 }while( curPos != initPos ); 631 } 632 return true; 633 }; 634 subdivideHoleWithBridge(AbutmentType & sideA,AbutmentType & sideB,BridgeOption bo,HoleSetManager<MESH> * holesManager,std::vector<FacePointer * > & app)635 static void subdivideHoleWithBridge(AbutmentType &sideA, AbutmentType &sideB, 636 BridgeOption bo, HoleSetManager<MESH>* holesManager, std::vector<FacePointer *> &app) 637 { 638 assert(sideA.h==sideB.h); 639 assert(testAbutmentDistance(sideA, sideB)); 640 FgtBridge<MESH>* b = new FgtBridge<MESH>(holesManager); 641 b->build(sideA, sideB, bo, app); 642 holesManager->bridges.push_back(b); 643 644 sideA.h->SetStartPos(b->GetSideA()); 645 sideA.h->SetBridged(true); 646 FgtHole<MESH> newHole(b->GetSideB(), QString("Hole_%1").arg(HoleType::GetHoleId(),3,10,QChar('0')), holesManager); 647 if(sideA.h->IsSelected()) 648 newHole.SetSelect(true); 649 newHole.SetBridged(true); 650 holesManager->holes.push_back( newHole ); 651 }; 652 unifyHolesWithBridge(AbutmentType & sideA,AbutmentType & sideB,BridgeOption bo,HoleSetManager<MESH> * holesManager,std::vector<FacePointer * > & app)653 static void unifyHolesWithBridge(AbutmentType &sideA, AbutmentType &sideB, 654 BridgeOption bo, HoleSetManager<MESH>* holesManager, std::vector<FacePointer *> &app) 655 { 656 assert(vcg::face::IsBorder<FaceType>(*sideA.f, sideA.z)); 657 assert(vcg::face::IsBorder<FaceType>(*sideB.f, sideB.z)); 658 assert( sideA.h!=sideB.h); 659 660 FgtBridge<MESH>* b = new FgtBridge<MESH>(holesManager); 661 b->build(sideA, sideB, bo, app); 662 holesManager->bridges.push_back(b); 663 664 sideA.h->SetStartPos(b->GetSideA()); 665 assert( sideA.h->p.IsBorder() ); 666 if(sideB.h->IsSelected()) 667 sideA.h->SetSelect(true); 668 sideA.h->SetBridged(true); 669 typename HoleVector::iterator hit = holesManager->holes.begin(); 670 //for(hit=holesManager->holes.begin(); hit!=holesManager->holes.end(); ++hit) 671 while(hit!=holesManager->holes.end()) 672 { 673 if(&*hit == sideB.h) 674 { 675 holesManager->holes.erase(hit++); 676 return; 677 } 678 else 679 hit++; 680 } 681 }; 682 683 /* Set bridge vertices according bridge build option 684 */ setVertexByOption(AbutmentType & sideA,AbutmentType & sideB,BridgeOption o,FaceType & bf0,FaceType & bf1)685 static void setVertexByOption(AbutmentType &sideA, AbutmentType &sideB, BridgeOption o, 686 FaceType &bf0, FaceType &bf1) 687 { 688 VertexType* vA0 = sideA.f->V0( sideA.z ); // first vertex of pos' 1-edge 689 VertexType* vA1 = sideA.f->V1( sideA.z ); // second vertex of pos' 1-edge 690 VertexType* vB0 = sideB.f->V0( sideB.z ); // first vertex of pos' 2-edge 691 VertexType* vB1 = sideB.f->V1( sideB.z ); // second vertex of pos' 2-edge 692 693 // Quality 694 if(o==OptA) 695 { 696 bf0.V(0) = vA1; bf0.V(1) = vA0; bf0.V(2) = vB0; 697 bf1.V(0) = vB1; bf1.V(1) = vB0; bf1.V(2) = vA0; 698 } 699 else 700 { 701 bf0.V(0) = vA1; bf0.V(1) = vA0; bf0.V(2) = vB1; 702 bf1.V(0) = vB1; bf1.V(1) = vB0; bf1.V(2) = vA1; 703 } 704 } 705 706 /* Find how triangolate two bridge faces. 707 * If return "NoOne" means bridge is compenetrating with mesh for both option 708 */ 709 static BridgeOption computeBestBridgeOpt(AbutmentType sideA, 710 AbutmentType sideB, ScalarType* quality=0, GridType* gM=0) 711 { 712 HoleSetManager<MESH>* hm = sideA.h->parentManager; 713 bool delgm = false; 714 if(gM==0) 715 { 716 gM = new GridType(); 717 gM->Set(hm->mesh->face.begin(),hm->mesh->face.end()); 718 delgm = true; 719 } 720 721 FaceType bf0, bf1; 722 ScalarType qA = -1; 723 // Caso A 724 setVertexByOption(sideA, sideB, OptA, bf0, bf1); 725 if( !HoleType::TestFaceMeshCompenetration(*hm->mesh, *gM, &bf0) && 726 !HoleType::TestFaceMeshCompenetration(*hm->mesh, *gM, &bf1) ) 727 qA = QualityFace(bf0)+ QualityFace(bf1); 728 729 // Caso B 730 ScalarType qB = -1; 731 setVertexByOption(sideA, sideB, OptB, bf0, bf1); 732 if( !HoleType::TestFaceMeshCompenetration(*hm->mesh, *gM, &bf0) && 733 !HoleType::TestFaceMeshCompenetration(*hm->mesh, *gM, &bf1) ) 734 qB = QualityFace(bf0)+ QualityFace(bf1); 735 736 if(delgm) 737 { 738 delete gM; 739 gM=0; 740 } 741 742 if(quality!=0) 743 { 744 if(qA>qB) *quality = qA; 745 else *quality = qB; 746 } 747 748 if(qA==-1 && qB==-1) 749 return NoOne; // both autocompenetrant with mesh 750 else if(qA>qB) 751 return OptA; 752 else 753 return OptB; 754 }; 755 756 757 private: 758 BridgeOption opt; 759 760 public: 761 FacePointer f0; 762 FacePointer f1; 763 }; 764 765 766 767 /* "Bridge" (face) added to close non manifold holes 768 * 769 * 770 * -----+------+------ ----+------+-------- 771 * \ A / \ A /| 772 * \ / \ / | 773 * holeX \/ holeX holeX \/ | holeY 774 * /\ /\f0| 775 * / \ / \ | 776 * / B \ / B \| 777 * -----+------+------ ----+------+-------- 778 * HoleX is Non-Manifold HoleX and HoleY aren't 779 * Non-Manifold 780 */ 781 template <class MESH> 782 class FgtNMBridge: public FgtBridgeBase<MESH> 783 { 784 typedef typename MESH::FaceType FaceType; 785 typedef typename MESH::FacePointer FacePointer; 786 typedef typename vcg::face::Pos<FaceType> PosType; 787 typedef FgtHole<MESH> HoleType; 788 typedef typename MESH::FaceIterator FaceIterator; 789 790 public: 791 FgtNMBridge(FacePointer f,HoleSetManager<MESH> * parent)792 FgtNMBridge(FacePointer f, HoleSetManager<MESH>* parent) 793 { 794 f0 = f; 795 this->parentManager = parent; 796 }; 797 GetAbutmentA()798 inline PosType GetAbutmentA() const { 799 return PosType( f0->FFp(0), f0->FFi(0)); 800 }; GetAbutmentB()801 inline PosType GetAbutmentB() const { 802 return PosType( f0->FFp(2), f0->FFi(2)); 803 }; 804 IsNull()805 inline bool IsNull() const { return f0==0; }; IsDeleted()806 inline bool IsDeleted() const { return f0->IsD(); }; 807 AddFaceReference(std::vector<FacePointer * > & facesReferences)808 inline void AddFaceReference(std::vector<FacePointer*> &facesReferences) 809 { 810 assert(!IsNull()); 811 assert(!IsDeleted()); 812 facesReferences.push_back(&f0); 813 }; 814 815 ResetFlag()816 void ResetFlag() 817 { 818 assert( !IsNull() ); 819 assert(this->parentManager->IsBridgeFace(f0) ); 820 this->parentManager->ClearBridgeAttr(f0); 821 }; 822 DeleteFromMesh()823 void DeleteFromMesh() 824 { 825 assert( !IsNull() ); 826 assert( this->parentManager->IsBridgeFace(f0) ); 827 if( !f0->IsD() ) 828 vcg::tri::Allocator<MESH>::DeleteFace(*this->parentManager->mesh, *f0); 829 830 // update mesh topology after bridge faces removal, restore border 831 for(int e=0; e<3; e++) 832 { 833 if(!vcg::face::IsBorder<FaceType>(*f0, e)) 834 { 835 FacePointer adjF = f0->FFp(e); 836 if(!this->parentManager->IsBridgeFace(adjF)) 837 { 838 int adjEI = f0->FFi(e); 839 adjF->FFp( adjEI ) = adjF; 840 adjF->FFi( adjEI ) = adjEI; 841 assert(vcg::face::IsBorder<FaceType>(*adjF, adjEI)); 842 } 843 } 844 } 845 }; 846 847 /* Walk over selected non-manifold holes, find vertex visited more times, 848 * add face adjacent to non-manifold vertex. 849 */ 850 static void CloseNonManifoldVertex(HoleSetManager<MESH>* holesManager, std::vector<FacePointer *> *app=0) 851 { 852 int startNholes = holesManager->holes.size(); 853 854 std::vector<FacePointer *> tmpFaceRef; 855 856 for(int i=0; i<startNholes; i++) 857 { 858 HoleType *h = &holesManager->holes.at(i); 859 if(!(h->IsNonManifold() && h->IsSelected())) 860 continue; 861 862 // walk the border, mark as visit each vertex. If walk twice over the same vertex go back over the border 863 // to find other edge sharing this vertex 864 PosType curPos = h->p; 865 assert(curPos.IsBorder()); 866 assert(!h->IsFilled()); 867 PosType p0, p1; 868 p0.SetNull(); 869 p1.SetNull(); 870 do{ 871 assert(p0.IsNull()); 872 if(curPos.v->IsV()) 873 p0.Set(curPos.f, curPos.z, curPos.v); 874 else 875 curPos.v->SetV(); 876 curPos.NextB(); 877 assert(curPos.IsBorder()); 878 879 if(!p0.IsNull()) 880 { 881 tmpFaceRef.clear(); 882 if(app!=0) 883 tmpFaceRef.insert(tmpFaceRef.end(), app->begin(), app->end()); 884 holesManager->AddFaceReference(tmpFaceRef); 885 886 // faces allocation and local face reference management 887 tmpFaceRef.push_back(&p0.f); 888 tmpFaceRef.push_back(&curPos.f); 889 FaceIterator fit = vcg::tri::Allocator<MESH>::AddFaces(*holesManager->mesh, 1, tmpFaceRef); 890 holesManager->faceAttr->UpdateSize(); 891 tmpFaceRef.pop_back(); 892 tmpFaceRef.pop_back(); 893 894 895 // non-manifold vertex found, go back over the border to find other edge share the vertex with p0 896 int dist = 0; 897 p1 = p0; 898 p1.FlipV(); 899 do{ 900 dist++; 901 p1.v->ClearV(); 902 p1.NextB(); 903 }while(p0.v != p1.v); 904 905 // p2 is used only in case face added close sub-hole, sub-hole distance is 2 906 // p2 is half-edge adjcent to connect to patch edge which usually is border 907 PosType p2 = p0; 908 p2.FlipV(); 909 p2.NextB(); 910 911 // face is build to have as vertex 0 the non-manifold vertex, so it have adge 1 as border edge 912 fit->V(0) = p0.v; 913 if( p0.VInd() == p0.z) 914 { 915 fit->V(1) = p1.f->V(p1.z); 916 fit->V(2) = p0.f->V1(p0.z); 917 918 fit->FFp(0) = p1.f; 919 fit->FFi(0) = p1.z; 920 fit->FFp(2) = p0.f; 921 fit->FFi(2) = p0.z; 922 923 p0.f->FFp(p0.z) = &*fit; 924 p0.f->FFi(p0.z) = 2; 925 p1.f->FFp(p1.z) = &*fit; 926 p1.f->FFi(p1.z) = 0; 927 } 928 else 929 { 930 fit->V(1) = p0.f->V(p0.z); 931 fit->V(2) = p1.f->V1(p1.z); 932 933 fit->FFp(0) = p0.f; 934 fit->FFi(0) = p0.z; 935 fit->FFp(2) = p1.f; 936 fit->FFi(2) = p1.z; 937 938 p0.f->FFp(p0.z) = &*fit; 939 p0.f->FFi(p0.z) = 0; 940 p1.f->FFp(p1.z) = &*fit; 941 p1.f->FFi(p1.z) = 2; 942 } 943 944 fit->N() = TriangleNormal(*fit); 945 946 holesManager->SetBridgeAttr(&*fit); 947 holesManager->bridges.push_back( new FgtNMBridge(&*fit, holesManager) ); 948 949 if(dist==2) 950 { 951 // face used to close non-manifold holes, close entirely a "sub-hole" (sub-hole has 952 // only 3 border edge). This face become a patch face which fill an invisible subhole. 953 holesManager->SetPatchAttr(&*fit); 954 fit->FFp(1) = p2.f; 955 fit->FFi(1) = p2.z; 956 p2.f->FFp(p2.z) = &*fit; 957 p2.f->FFi(p2.z) = 1; 958 } 959 else 960 { 961 fit->FFp(1) = &*fit; 962 fit->FFi(1) = 1; 963 964 HoleType newhole(PosType(&*fit, 1), QString("Hole_%1").arg(HoleType::GetHoleId(),3,10,QChar('0')), holesManager); 965 if(h->IsSelected()) 966 newhole.SetSelect(true); 967 newhole.SetBridged(true); 968 holesManager->holes.push_back(newhole); 969 } 970 p0.SetNull(); 971 } 972 }while( curPos != h->p ); 973 974 // hole now is divided intosub hole 975 curPos = h->p; 976 do{ 977 curPos.v->ClearV(); 978 curPos.NextB(); 979 }while( curPos!= h->p); 980 981 //forzo l'aggiornamento delle info dell'hole 982 h->SetStartPos(h->p); 983 h->SetBridged(true); 984 }// for(int i=0; i<startNholes... 985 }; 986 987 public: 988 FacePointer f0; 989 }; 990 991 #endif 992