src/BOPAlgo/BOPAlgo_ShellSplitter.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15 // File: BOPAlgo_ShellSplitter.cxx
  16 // Created: Thu Jan 16 08:33:50 2014
  17
  18 #include <BOPAlgo_ShellSplitter.hxx>
  19 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
  20 #include <BOPCol_IndexedMapOfShape.hxx>
  21 #include <BOPCol_MapOfOrientedShape.hxx>
  22 #include <BOPCol_MapOfShape.hxx>
  23 #include <BOPCol_NCVector.hxx>
  24 #include <BOPCol_Parallel.hxx>
  25 #include <BOPTools.hxx>
  26 #include <BOPTools_AlgoTools.hxx>
  27 #include <BOPTools_CoupleOfShape.hxx>
  28 #include <BRep_Builder.hxx>
  29 #include <IntTools_Context.hxx>
  30 #include <TopExp_Explorer.hxx>
  31 #include <TopoDS.hxx>
  32 #include <TopoDS_Edge.hxx>
  33 #include <TopoDS_Shape.hxx>
  34 #include <TopoDS_Shell.hxx>
  35
  36 //
  37 static
  38   void MakeShell(const BOPCol_ListOfShape& ,
  39                  TopoDS_Shell& );
  40 //
  41 static
  42   void RefineShell(TopoDS_Shell& theShell,
  43                    const BOPCol_IndexedDataMapOfShapeListOfShape& theMEF,
  44                    BOPCol_ListOfShape& aLShX);
  45
  46 //=======================================================================
  47 //class    : BOPAlgo_CBK
  48 //purpose  :
  49 //=======================================================================
  50 class BOPAlgo_CBK {
  51  public:
  52   BOPAlgo_CBK() :
  53     myPCB (NULL) {
  54   }
  55   //
  56   ~BOPAlgo_CBK() {
  57   }
  58   //
  59   void SetConnexityBlock (const BOPTools_ConnexityBlock& aCB) {
  60     myPCB=(BOPTools_ConnexityBlock*)&aCB;
  61   }
  62   //
  63   BOPTools_ConnexityBlock& ConnexityBlock () {
  64     return *myPCB;
  65   }
  66   //
  67   void Perform() {
  68     BOPAlgo_ShellSplitter::SplitBlock(*myPCB);
  69   }
  70  protected:
  71   BOPTools_ConnexityBlock *myPCB;
  72 };
  73 //=======================================================================
  74 typedef BOPCol_NCVector
  75   <BOPAlgo_CBK> BOPAlgo_VectorOfCBK;
  76 //
  77 typedef BOPCol_Functor
  78   <BOPAlgo_CBK,
  79   BOPAlgo_VectorOfCBK> BOPAlgo_CBKFunctor;
  80 //
  81 typedef BOPCol_Cnt
  82   <BOPAlgo_CBKFunctor,
  83   BOPAlgo_VectorOfCBK> BOPAlgo_CBKCnt;
  84 //
  85 //=======================================================================
  86 //function :
  87 //purpose  :
  88 //=======================================================================
  89 BOPAlgo_ShellSplitter::BOPAlgo_ShellSplitter()
  90 :
  91   BOPAlgo_Algo(),
  92   myStartShapes(myAllocator),
  93   myShells(myAllocator),
  94   myLCB(myAllocator)
  95 {
  96 }
  97 //=======================================================================
  98 //function :
  99 //purpose  :
 100 //=======================================================================
 101 BOPAlgo_ShellSplitter::BOPAlgo_ShellSplitter
 102   (const Handle(NCollection_BaseAllocator)& theAllocator)
 103 :
 104   BOPAlgo_Algo(theAllocator),
 105   myStartShapes(theAllocator),
 106   myShells(theAllocator),
 107   myLCB(myAllocator)
 108 {
 109 }
 110 //=======================================================================
 111 //function : ~
 112 //purpose  :
 113 //=======================================================================
 114 BOPAlgo_ShellSplitter::~BOPAlgo_ShellSplitter()
 115 {
 116 }
 117 //=======================================================================
 118 //function : AddStartElement
 119 //purpose  :
 120 //=======================================================================
 121 void BOPAlgo_ShellSplitter::AddStartElement(const TopoDS_Shape& aE)
 122 {
 123   myStartShapes.Append(aE);
 124 }
 125 //=======================================================================
 126 //function : StartElements
 127 //purpose  :
 128 //=======================================================================
 129 const BOPCol_ListOfShape& BOPAlgo_ShellSplitter::StartElements()const
 130 {
 131   return myStartShapes;
 132 }
 133 //=======================================================================
 134 //function : Loops
 135 //purpose  :
 136 //=======================================================================
 137 const BOPCol_ListOfShape& BOPAlgo_ShellSplitter::Shells()const
 138 {
 139   return myShells;
 140 }
 141 //=======================================================================
 142 //function : Perform
 143 //purpose  :
 144 //=======================================================================
 145 void BOPAlgo_ShellSplitter::Perform()
 146 {
 147   GetReport()->Clear();
 148   //
 149   BOPTools_AlgoTools::MakeConnexityBlocks
 150     (myStartShapes, TopAbs_EDGE, TopAbs_FACE, myLCB);
 151   //
 152   MakeShells();
 153 }
 154
 155 //=======================================================================
 156 //function : SplitBlock
 157 //purpose  :
 158 //=======================================================================
 159 void BOPAlgo_ShellSplitter::SplitBlock(BOPTools_ConnexityBlock& aCB)
 160 {
 161   Standard_Integer aNbLF, aNbOff, aNbFP;
 162   Standard_Integer i;
 163   TopAbs_Orientation anOr;
 164   TopoDS_Edge aEL;
 165   BRep_Builder aBB;
 166   TopoDS_Iterator aItS;
 167   TopExp_Explorer aExp;
 168   BOPCol_ListIteratorOfListOfShape aItF;
 169   BOPTools_CoupleOfShape aCSOff;
 170   BOPCol_MapOfOrientedShape AddedFacesMap;
 171   BOPCol_IndexedDataMapOfShapeListOfShape aEFMap, aMEFP;
 172   Handle (IntTools_Context) aContext;
 173   //
 174   aContext=new IntTools_Context;
 175   //
 176   const BOPCol_ListOfShape& myShapes=aCB.Shapes();
 177   //
 178   BOPCol_ListOfShape& myLoops=aCB.ChangeLoops();
 179   myLoops.Clear();
 180   //
 181   // Copy faces into the map, for recursive search of free bounds
 182   BOPCol_MapOfOrientedShape aMFaces;
 183   aItF.Initialize (myShapes);
 184   for (; aItF.More(); aItF.Next()) {
 185     aMFaces.Add(aItF.Value());
 186   }
 187   //
 188   // remove the faces with free edges from processing
 189   for (;;) {
 190     // map the shapes
 191     aEFMap.Clear();
 192     aItF.Initialize(myShapes);
 193     for (; aItF.More(); aItF.Next()) {
 194       const TopoDS_Shape& aF = aItF.Value();
 195       if (aMFaces.Contains(aF)) {
 196         BOPTools::MapShapesAndAncestors (aF, TopAbs_EDGE, TopAbs_FACE, aEFMap);
 197       }
 198     }
 199     //
 200     Standard_Integer aNbBegin = aMFaces.Extent();
 201     // check the free edges
 202     Standard_Integer aNbE = aEFMap.Extent();
 203     for (i = 1; i <= aNbE; ++i) {
 204       const TopoDS_Edge& aE = TopoDS::Edge(aEFMap.FindKey(i));
 205       if (!(BRep_Tool::Degenerated(aE) || aE.Orientation() == TopAbs_INTERNAL)) {
 206         const BOPCol_ListOfShape& aLF = aEFMap(i);
 207         if (aLF.Extent() == 1) {
 208           // remove the face
 209           aMFaces.Remove(aLF.First());
 210         }
 211       }
 212     }
 213     //
 214     // check if any faces have been removed
 215     Standard_Integer aNbEnd = aMFaces.Extent();
 216     if ((aNbEnd == aNbBegin) || (aNbEnd == 0)) {
 217       break;
 218     }
 219   }
 220   //
 221   if (aMFaces.IsEmpty()) {
 222     return;
 223   }
 224   //
 225   // use only connected faces
 226   BOPCol_ListOfShape aLFConnected;
 227   aItF.Initialize (myShapes);
 228   for (; aItF.More(); aItF.Next()) {
 229     const TopoDS_Shape& aF = aItF.Value();
 230     if (aMFaces.Contains(aF)) {
 231       aLFConnected.Append(aF);
 232     }
 233   }
 234   //
 235   const Standard_Integer aNbShapes = aLFConnected.Extent();
 236   Standard_Boolean bAllFacesTaken = Standard_False;
 237   //
 238   // Build the shells
 239   aItF.Initialize (aLFConnected);
 240   for (i = 1; aItF.More() && !bAllFacesTaken; aItF.Next(), ++i) {
 241     const TopoDS_Shape& aFF = aItF.Value();
 242     if (!AddedFacesMap.Add(aFF)) {
 243       continue;
 244     }
 245     //
 246     // make a new shell
 247     TopoDS_Shell aShellStart;
 248     aBB.MakeShell(aShellStart);
 249     aBB.Add(aShellStart, aFF);
 250     //
 251     BOPCol_ListOfShape aLShells;
 252     aLShells.Append(aShellStart);
 253     //
 254     BOPCol_ListIteratorOfListOfShape aItLShells(aLShells);
 255     for (; aItLShells.More(); aItLShells.Next()) {
 256       TopoDS_Shell& aShell = TopoDS::Shell(aItLShells.ChangeValue());
 257       //
 258       aMEFP.Clear();
 259       BOPTools::MapShapesAndAncestors(aShell, TopAbs_EDGE, TopAbs_FACE, aMEFP);
 260       //
 261       // loop on faces added to Shell;
 262       // add their neighbor faces to Shell and so on
 263       aItS.Initialize(aShell);
 264       for (; aItS.More(); aItS.Next()) {
 265         const TopoDS_Face& aF = (*(TopoDS_Face*)(&aItS.Value()));
 266         //
 267         // loop on edges of aF; find a good neighbor face of aF by aE
 268         aExp.Init(aF, TopAbs_EDGE);
 269         for (; aExp.More(); aExp.Next()) {
 270           const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
 271           //
 272           // proceed only free edges in this shell
 273           if (aMEFP.Contains(aE)) {
 274             const BOPCol_ListOfShape& aLFP = aMEFP.FindFromKey(aE);
 275             aNbFP = aLFP.Extent();
 276             if (aNbFP > 1) {
 277               continue;
 278             }
 279           }
 280           // avoid processing of internal edges
 281           anOr = aE.Orientation();
 282           if (anOr == TopAbs_INTERNAL) {
 283             continue;
 284           }
 285           // avoid processing of degenerated edges
 286           if (BRep_Tool::Degenerated(aE)) {
 287             continue;
 288           }
 289           //
 290           // candidate faces list
 291           const BOPCol_ListOfShape& aLF = aEFMap.FindFromKey(aE);
 292           aNbLF = aLF.Extent();
 293           if (!aNbLF) {
 294             continue;
 295           }
 296           //
 297           // prepare for selecting the next face
 298           // take only not-processed faces as a candidates
 299           BOPTools_ListOfCoupleOfShape aLCSOff;
 300           //
 301           BOPCol_ListIteratorOfListOfShape aItLF(aLF);
 302           for (; aItLF.More(); aItLF.Next()) {
 303             const TopoDS_Face& aFL = (*(TopoDS_Face*)(&aItLF.Value()));
 304             if (aF.IsSame(aFL) || AddedFacesMap.Contains(aFL)) {
 305               continue;
 306             }
 307             //
 308             // find current edge in the face
 309             if (!BOPTools_AlgoTools::GetEdgeOff(aE, aFL, aEL)) {
 310               continue;
 311             }
 312             //
 313             aCSOff.SetShape1(aEL);
 314             aCSOff.SetShape2(aFL);
 315             aLCSOff.Append(aCSOff);
 316           }//for (; aItLF.More(); aItLF.Next()) {
 317           //
 318           aNbOff = aLCSOff.Extent();
 319           if (!aNbOff){
 320             continue;
 321           }
 322           //
 323           // among all the adjacent faces chose one with the minimal
 324           // angle to the current one
 325           TopoDS_Face aSelF;
 326           if (aNbOff == 1) {
 327             aSelF = (*(TopoDS_Face*)(&aLCSOff.First().Shape2()));
 328           }
 329           else if (aNbOff > 1) {
 330             BOPTools_AlgoTools::GetFaceOff(aE, aF, aLCSOff, aSelF, aContext);
 331           }
 332           //
 333           if (!aSelF.IsNull() && AddedFacesMap.Add(aSelF)) {
 334             aBB.Add(aShell, aSelF);
 335             BOPTools::MapShapesAndAncestors(aSelF, TopAbs_EDGE, TopAbs_FACE, aMEFP);
 336           }
 337         } // for (; aExp.More(); aExp.Next()) {
 338       } // for (; aItS.More(); aItS.Next()) {
 339       //
 340       // split the shell on multi-connected edges
 341       BOPCol_ListOfShape aLShSp;
 342       RefineShell(aShell, aMEFP, aLShSp);
 343       //
 344       // collect the not closed shells for further processing
 345       BOPCol_ListOfShape aLShNC;
 346       //
 347       BOPCol_ListIteratorOfListOfShape aItLShSp(aLShSp);
 348       for (; aItLShSp.More(); aItLShSp.Next()) {
 349         TopoDS_Shell& aShSp = *((TopoDS_Shell*)&aItLShSp.Value());
 350         //
 351         if (BRep_Tool::IsClosed(aShSp)) {
 352           aShSp.Closed(Standard_True);
 353           myLoops.Append(aShSp);
 354         }
 355         else {
 356           aLShNC.Append(aShSp);
 357         }
 358       }
 359       //
 360       bAllFacesTaken = (AddedFacesMap.Extent() == aNbShapes);
 361       if (bAllFacesTaken) {
 362         break;
 363       }
 364       //
 365       if (aLShSp.Extent() == 1) {
 366         // not further processing of not closed shells is needed,
 367         // as it will not bring any new results
 368         continue;
 369       }
 370       //
 371       Standard_Integer aNbShNC = aLShNC.Extent();
 372       if (aNbShNC == 1) {
 373         // try to complete the shell with other faces
 374         aLShells.Append(aLShNC);
 375       }
 376       else if (aNbShNC > 1) {
 377         // remove th faces of not closed shells from the map of processed faces
 378         // and try to rebuild the shells using all not processed faces,
 379         // because faces of one shell might be needed for building the other
 380         BOPCol_ListIteratorOfListOfShape aItLShNC(aLShNC);
 381         for (; aItLShNC.More(); aItLShNC.Next()) {
 382           TopoDS_Iterator aItNC(aItLShNC.Value());
 383           for (; aItNC.More(); aItNC.Next()) {
 384             AddedFacesMap.Remove(aItNC.Value());
 385           }
 386         }
 387       }
 388     }
 389   } // for (; aItF.More(); aItF.Next()) {
 390 }
 391 //=======================================================================
 392 //function : RefineShell
 393 //purpose  :
 394 //=======================================================================
 395 void RefineShell(TopoDS_Shell& theShell,
 396                  const BOPCol_IndexedDataMapOfShapeListOfShape& theMEF,
 397                  BOPCol_ListOfShape& theLShSp)
 398 {
 399   TopoDS_Iterator aIt(theShell);
 400   if(!aIt.More()) {
 401     return;
 402   }
 403   //
 404   // Find edges with more than 2 adjacent faces - branch edges -
 405   // edges on which the input shell should be split
 406   BOPCol_MapOfShape aMEStop;
 407   //
 408   Standard_Integer i, aNbMEF = theMEF.Extent();
 409   for (i = 1; i <= aNbMEF; ++i) {
 410     const TopoDS_Edge& aE = TopoDS::Edge(theMEF.FindKey(i));
 411     const BOPCol_ListOfShape& aLF = theMEF(i);
 412     if (aLF.Extent() > 2) {
 413       aMEStop.Add(aE);
 414       continue;
 415     }
 416     //
 417     // check for internal edges - count faces, in which the edge
 418     // is internal, twice
 419     Standard_Integer aNbF = 0;
 420     BOPCol_ListIteratorOfListOfShape aItLF(aLF);
 421     for (; aItLF.More() && aNbF <= 2; aItLF.Next()) {
 422       const TopoDS_Face& aF = TopoDS::Face(aItLF.Value());
 423       ++aNbF;
 424       TopExp_Explorer aExp(aF, TopAbs_EDGE);
 425       for (; aExp.More(); aExp.Next()) {
 426         const TopoDS_Shape& aEF = aExp.Current();
 427         if (aEF.IsSame(aE)) {
 428           if (aEF.Orientation() == TopAbs_INTERNAL) {
 429             ++aNbF;
 430           }
 431           break;
 432         }
 433       }
 434     }
 435     //
 436     if (aNbF > 2) {
 437       aMEStop.Add(aE);
 438     }
 439   }
 440   //
 441   if (aMEStop.IsEmpty()) {
 442     theLShSp.Append(theShell);
 443     return;
 444   }
 445   //
 446   TopoDS_Builder aBB;
 447   TopExp_Explorer aExp;
 448   BOPCol_IndexedMapOfShape aMFB;
 449   BOPCol_MapOfOrientedShape aMFProcessed;
 450   BOPCol_ListOfShape aLFP, aLFP1;
 451   BOPCol_ListIteratorOfListOfShape aItLF, aItLFP;
 452   //
 453   // The first Face
 454   for (; aIt.More(); aIt.Next()) {
 455     const TopoDS_Shape& aF1 = aIt.Value();
 456     if (!aMFProcessed.Add(aF1)) {
 457       continue;
 458     }
 459     //
 460     aMFB.Clear();
 461     aLFP.Clear();
 462     //
 463     aMFB.Add(aF1);
 464     aLFP.Append(aF1);
 465     //
 466     // Trying to reach the branch point
 467     for (;;) {
 468       aItLFP.Initialize(aLFP);
 469       for (; aItLFP.More(); aItLFP.Next()) {
 470         const TopoDS_Shape& aFP = aItLFP.Value();
 471         //
 472         aExp.Init(aFP, TopAbs_EDGE);
 473         for (; aExp.More(); aExp.Next()) {
 474           const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&aExp.Current()));
 475           if (aMEStop.Contains(aE)) {
 476             continue;
 477           }
 478           //
 479           if (aE.Orientation() == TopAbs_INTERNAL) {
 480             continue;
 481           }
 482           //
 483           if (BRep_Tool::Degenerated(aE)) {
 484             continue;
 485           }
 486           //
 487           const BOPCol_ListOfShape& aLF = theMEF.FindFromKey(aE);
 488           //
 489           aItLF.Initialize(aLF);
 490           for (; aItLF.More(); aItLF.Next()) {
 491             const TopoDS_Shape& aFP1 = aItLF.Value();
 492             if (aFP1.IsSame(aFP)) {
 493               continue;
 494             }
 495             if (aMFB.Contains(aFP1)) {
 496               continue;
 497             }
 498             //
 499             if (aMFProcessed.Add(aFP1)) {
 500               aMFB.Add(aFP1);
 501               aLFP1.Append(aFP1);
 502             }
 503           }// for (; aItLF.More(); aItLF.Next()) {
 504         }// for (; aExp.More(); aExp.Next()) {
 505       } // for (; aItLFP.More(); aItLFP.Next()) {
 506       //
 507       //
 508       if (aLFP1.IsEmpty()) {
 509         break;
 510       }
 511       //
 512       aLFP.Clear();
 513       aLFP.Append(aLFP1);
 514     }// for (;;) {
 515     //
 516     Standard_Integer aNbMFB = aMFB.Extent();
 517     if (aNbMFB) {
 518       TopoDS_Shell aShSp;
 519       aBB.MakeShell(aShSp);
 520       //
 521       for (i = 1; i <= aNbMFB; ++i) {
 522         const TopoDS_Shape& aFB = aMFB(i);
 523         aBB.Add(aShSp, aFB);
 524       }
 525       theLShSp.Append(aShSp);
 526     }
 527   }//for (; aIt.More(); aIt.Next()) {
 528 }
 529 //=======================================================================
 530 //function : MakeShells
 531 //purpose  :
 532 //=======================================================================
 533 void BOPAlgo_ShellSplitter::MakeShells()
 534 {
 535   Standard_Boolean bIsRegular;
 536   Standard_Integer aNbVCBK, k;
 537   BOPTools_ListIteratorOfListOfConnexityBlock aItCB;
 538   BOPCol_ListIteratorOfListOfShape aIt;
 539   BOPAlgo_VectorOfCBK aVCBK;
 540   //
 541   myShells.Clear();
 542   //
 543   aItCB.Initialize(myLCB);
 544   for (; aItCB.More(); aItCB.Next()) {
 545     BOPTools_ConnexityBlock& aCB=aItCB.ChangeValue();
 546     bIsRegular=aCB.IsRegular();
 547     if (bIsRegular) {
 548       TopoDS_Shell aShell;
 549       //
 550       const BOPCol_ListOfShape& aLF=aCB.Shapes();
 551       MakeShell(aLF, aShell);
 552       aShell.Closed(Standard_True);
 553       myShells.Append(aShell);
 554     }
 555     else {
 556       BOPAlgo_CBK& aCBK=aVCBK.Append1();
 557       aCBK.SetConnexityBlock(aCB);
 558     }
 559   }
 560   //
 561   aNbVCBK=aVCBK.Extent();
 562   //===================================================
 563   BOPAlgo_CBKCnt::Perform(myRunParallel, aVCBK);
 564   //===================================================
 565   for (k=0; k<aNbVCBK; ++k) {
 566     BOPAlgo_CBK& aCBK=aVCBK(k);
 567     const BOPTools_ConnexityBlock& aCB=aCBK.ConnexityBlock();
 568     const BOPCol_ListOfShape& aLS=aCB.Loops();
 569     aIt.Initialize(aLS);
 570     for (; aIt.More(); aIt.Next()) {
 571       TopoDS_Shape& aShell=aIt.ChangeValue();
 572       aShell.Closed(Standard_True);
 573       myShells.Append(aShell);
 574     }
 575   }
 576 }
 577 //=======================================================================
 578 //function : MakeShell
 579 //purpose  :
 580 //=======================================================================
 581 void MakeShell(const BOPCol_ListOfShape& aLS,
 582                TopoDS_Shell& aShell)
 583 {
 584   BRep_Builder aBB;
 585   BOPCol_ListIteratorOfListOfShape aIt;
 586   //
 587   aBB.MakeShell(aShell);
 588   //
 589   aIt.Initialize(aLS);
 590   for (; aIt.More(); aIt.Next()) {
 591     const TopoDS_Shape& aF=aIt.Value();
 592     aBB.Add(aShell, aF);
 593   }
 594   //
 595   BOPTools_AlgoTools::OrientFacesOnShell(aShell);
 596 }