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