src/BOPAlgo/BOPAlgo_CellsBuilder.cxx

   1 // Created by: Eugeny MALTCHIKOV
   2 // Copyright (c) 2015 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
  16 #include <BOPAlgo_CellsBuilder.hxx>
  17
  18 #include <BOPAlgo_Alerts.hxx>
  19 #include <BOPAlgo_BuilderSolid.hxx>
  20 #include <BOPDS_DS.hxx>
  21 #include <BOPTools_AlgoTools.hxx>
  22 #include <BRep_Builder.hxx>
  23 #include <ShapeUpgrade_UnifySameDomain.hxx>
  24 #include <TColStd_MapOfInteger.hxx>
  25 #include <TopExp.hxx>
  26 #include <TopExp_Explorer.hxx>
  27 #include <TopoDS_Compound.hxx>
  28
  29
  30 static
  31   TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim);
  32
  33 static
  34   void MakeTypedContainers(const TopoDS_Shape& theSC,
  35                            TopoDS_Shape& theResult);
  36
  37 static void CollectMaterialBoundaries(const TopTools_ListOfShape& theLS,
  38                                       TopTools_MapOfShape& theMapKeepBnd);
  39
  40 //=======================================================================
  41 //function : empty constructor
  42 //purpose  :
  43 //=======================================================================
  44 BOPAlgo_CellsBuilder::BOPAlgo_CellsBuilder()
  45 :
  46   BOPAlgo_Builder(),
  47   myIndex(100, myAllocator),
  48   myMaterials(100, myAllocator),
  49   myShapeMaterial(100, myAllocator),
  50   myMapModified(100, myAllocator)
  51 {
  52 }
  53
  54 //=======================================================================
  55 //function : empty constructor
  56 //purpose  :
  57 //=======================================================================
  58 BOPAlgo_CellsBuilder::BOPAlgo_CellsBuilder
  59   (const Handle(NCollection_BaseAllocator)& theAllocator)
  60 :
  61   BOPAlgo_Builder(theAllocator),
  62   myIndex(100, myAllocator),
  63   myMaterials(100, myAllocator),
  64   myShapeMaterial(100, myAllocator),
  65   myMapModified(100, myAllocator)
  66 {
  67 }
  68
  69 //=======================================================================
  70 //function : ~
  71 //purpose  :
  72 //=======================================================================
  73 BOPAlgo_CellsBuilder::~BOPAlgo_CellsBuilder()
  74 {
  75   Clear();
  76 }
  77
  78 //=======================================================================
  79 //function : Clear
  80 //purpose  :
  81 //=======================================================================
  82 void BOPAlgo_CellsBuilder::Clear()
  83 {
  84   BOPAlgo_Builder::Clear();
  85   myIndex.Clear();
  86   myMaterials.Clear();
  87   myShapeMaterial.Clear();
  88   myMapModified.Clear();
  89 }
  90
  91 //=======================================================================
  92 //function : GetAllParts
  93 //purpose  :
  94 //=======================================================================
  95 const TopoDS_Shape& BOPAlgo_CellsBuilder::GetAllParts() const
  96 {
  97   return myAllParts;
  98 }
  99
 100 //=======================================================================
 101 //function : PerformInternal1
 102 //purpose  :
 103 //=======================================================================
 104 void BOPAlgo_CellsBuilder::PerformInternal1(const BOPAlgo_PaveFiller& theFiller, const Message_ProgressRange& theRange)
 105 {
 106   // Avoid filling history after GF operation as later
 107   // in this method the result shape will be nullified
 108   Standard_Boolean isHistory = HasHistory();
 109   SetToFillHistory(Standard_False);
 110   // Perform splitting of the arguments
 111   Message_ProgressScope aPS(theRange, "Performing MakeCells operation", 1);
 112   BOPAlgo_Builder::PerformInternal1(theFiller, aPS.Next());
 113   if (HasErrors()) {
 114     return;
 115   }
 116
 117   // index all the parts to its origins
 118   IndexParts();
 119
 120   // and nullify <myShape> for building the result;
 121   RemoveAllFromResult();
 122
 123   // Restore user's history settings
 124   SetToFillHistory(isHistory);
 125 }
 126
 127 //=======================================================================
 128 //function : IndexParts
 129 //purpose  :
 130 //=======================================================================
 131 void BOPAlgo_CellsBuilder::IndexParts()
 132 {
 133   BRep_Builder aBB;
 134   // all split parts of the shapes
 135   TopoDS_Compound anAllParts;
 136   aBB.MakeCompound(anAllParts);
 137   //
 138   TopTools_MapOfShape aMFence;
 139   TColStd_MapOfInteger aMDims;
 140   //
 141   TopTools_ListIteratorOfListOfShape aIt(myArguments);
 142   for (; aIt.More(); aIt.Next()) {
 143     const TopoDS_Shape& aS = aIt.Value();
 144
 145     TopTools_ListOfShape aLSubS;
 146     BOPTools_AlgoTools::TreatCompound (aS, aLSubS);
 147     for (TopTools_ListOfShape::Iterator itSub (aLSubS); itSub.More(); itSub.Next())
 148     {
 149       const TopoDS_Shape& aSS = itSub.Value();
 150       Standard_Integer iDim = BOPTools_AlgoTools::Dimension (aSS);
 151       aMDims.Add(iDim);
 152       TopAbs_ShapeEnum aType = TypeToExplore (iDim);
 153       TopExp_Explorer aExp (aSS, aType);
 154       for (; aExp.More(); aExp.Next())
 155       {
 156         const TopoDS_Shape& aST = aExp.Current();
 157         const TopTools_ListOfShape* pLSIm = myImages.Seek(aST);
 158         if (!pLSIm) {
 159           TopTools_ListOfShape* pLS = myIndex.ChangeSeek(aST);
 160           if (!pLS) {
 161             pLS = &myIndex(myIndex.Add(aST, TopTools_ListOfShape()));
 162           }
 163           pLS->Append(aS);
 164           //
 165           if (aMFence.Add(aST)) {
 166             aBB.Add(anAllParts, aST);
 167           }
 168           //
 169           continue;
 170         }
 171         //
 172         TopTools_ListIteratorOfListOfShape aItIm(*pLSIm);
 173         for (; aItIm.More(); aItIm.Next()) {
 174           const TopoDS_Shape& aSTIm = aItIm.Value();
 175           //
 176           TopTools_ListOfShape* pLS = myIndex.ChangeSeek(aSTIm);
 177           if (!pLS) {
 178             pLS = &myIndex(myIndex.Add(aSTIm, TopTools_ListOfShape()));
 179           }
 180           pLS->Append(aS);
 181           //
 182           if (aMFence.Add(aSTIm)) {
 183             aBB.Add(anAllParts, aSTIm);
 184           }
 185         } // for (; aItIm.More(); aItIm.Next()) {
 186       } // for (; aExp.More(); aExp.Next()) {
 187     } // for (; itSub.More(); itSub.Next())
 188   } // for (; aIt.More(); aIt.Next()) {
 189   //
 190   myAllParts = anAllParts;
 191   //
 192   if (aMDims.Extent() == 1) {
 193     return;
 194   }
 195   //
 196   // for the multi-dimensional case
 197   // add sub-shapes of the splits into the <myIndex> map
 198   //
 199   Standard_Integer i, aNbS = myIndex.Extent();
 200   for (i = 1; i <= aNbS; ++i) {
 201     const TopoDS_Shape& aSP = myIndex.FindKey(i);
 202     const TopTools_ListOfShape& aLSOr = myIndex(i);
 203     //
 204     Standard_Integer iType = BOPTools_AlgoTools::Dimension(aSP);
 205     TColStd_MapIteratorOfMapOfInteger aItM(aMDims);
 206     for (; aItM.More(); aItM.Next()) {
 207       Standard_Integer k = aItM.Value();
 208       if (k >= iType) {
 209         continue;
 210       }
 211       //
 212       TopExp_Explorer aExp(aSP, TypeToExplore(k));
 213       for (; aExp.More(); aExp.Next()) {
 214         const TopoDS_Shape& aSS = aExp.Current();
 215         TopTools_ListOfShape* pLSSOr = myIndex.ChangeSeek(aSS);
 216         if (!pLSSOr) {
 217           myIndex.Add(aSS, aLSOr);
 218           continue;
 219         }
 220         // add ancestors of the shape to the ancestors of the sub-shape
 221         TopTools_ListIteratorOfListOfShape aItLS(aLSOr);
 222         for (; aItLS.More(); aItLS.Next()) {
 223           const TopoDS_Shape& aSOr = aItLS.Value();
 224           // provide uniqueness of the ancestors
 225           TopTools_ListIteratorOfListOfShape aItLSS(*pLSSOr);
 226           for (; aItLSS.More(); aItLSS.Next()) {
 227             if (aSOr.IsSame(aItLSS.Value())) {
 228               break;
 229             }
 230           }
 231           //
 232           if (!aItLSS.More()) {
 233             pLSSOr->Append(aSOr);
 234           }
 235         }
 236       }
 237     }
 238   }
 239 }
 240
 241 //=======================================================================
 242 //function : AddToResult
 243 //purpose  :
 244 //=======================================================================
 245 void BOPAlgo_CellsBuilder::AddToResult(const TopTools_ListOfShape& theLSToTake,
 246                                        const TopTools_ListOfShape& theLSToAvoid,
 247                                        const Standard_Integer theMaterial,
 248                                        const Standard_Boolean theUpdate)
 249 {
 250   // find parts
 251   TopTools_ListOfShape aParts;
 252   FindParts(theLSToTake, theLSToAvoid, aParts);
 253   if (aParts.IsEmpty()) {
 254     return;
 255   }
 256   //
 257   // collect result parts to avoid multiple adding of the same parts
 258   TopTools_MapOfShape aResParts;
 259   TopoDS_Iterator aIt(myShape);
 260   for (; aIt.More(); aIt.Next()) {
 261     aResParts.Add(aIt.Value());
 262   }
 263   //
 264   Standard_Boolean bChanged = Standard_False;
 265   // add parts to result
 266   TopTools_ListIteratorOfListOfShape aItLP(aParts);
 267   for (; aItLP.More(); aItLP.Next()) {
 268     const TopoDS_Shape& aPart = aItLP.Value();
 269     // provide uniqueness of the parts
 270     if (aResParts.Add(aPart) && !myShapeMaterial.IsBound(aPart)) {
 271       BRep_Builder().Add(myShape, aPart);
 272       bChanged = Standard_True;
 273     }
 274   }
 275   //
 276   // update the material
 277   if (theMaterial != 0) {
 278     TopTools_ListOfShape aLSP;
 279     aItLP.Initialize(aParts);
 280     for (; aItLP.More(); aItLP.Next()) {
 281       const TopoDS_Shape& aPart = aItLP.Value();
 282       if (!myShapeMaterial.IsBound(aPart)) {
 283         myShapeMaterial.Bind(aPart, theMaterial);
 284         aLSP.Append(aPart);
 285       }
 286     } // for (; aIt.More(); aIt.Next()) {
 287     //
 288     if (aLSP.Extent()) {
 289       TopTools_ListOfShape* pLS = myMaterials.ChangeSeek(theMaterial);
 290       if (!pLS) {
 291         pLS = myMaterials.Bound(theMaterial, TopTools_ListOfShape());
 292       }
 293       pLS->Append(aLSP);
 294     } // if (aLSP.Extent()) {
 295   } // if (theMaterial != 0) {
 296   //
 297   if (!theUpdate) {
 298     if (bChanged) {
 299       PrepareHistory(Message_ProgressRange());
 300     }
 301   }
 302   else {
 303     RemoveInternalBoundaries();
 304   }
 305 }
 306
 307 //=======================================================================
 308 //function : AddAllToResult
 309 //purpose  :
 310 //=======================================================================
 311 void BOPAlgo_CellsBuilder::AddAllToResult(const Standard_Integer theMaterial,
 312                                           const Standard_Boolean theUpdate)
 313 {
 314   myShapeMaterial.Clear();
 315   myMaterials.Clear();
 316   myMapModified.Clear();
 317   //
 318   myShape = myAllParts;
 319   //
 320   if (theMaterial != 0) {
 321     TopTools_ListOfShape* pLSM = myMaterials.Bound(theMaterial, TopTools_ListOfShape());
 322     //
 323     TopoDS_Iterator aIt(myAllParts);
 324     for (; aIt.More(); aIt.Next()) {
 325       const TopoDS_Shape& aPart = aIt.Value();
 326       myShapeMaterial.Bind(aPart, theMaterial);
 327       pLSM->Append(aPart);
 328     }
 329   }
 330   //
 331   if (!theUpdate) {
 332     PrepareHistory(Message_ProgressRange());
 333   }
 334   else {
 335     RemoveInternalBoundaries();
 336   }
 337 }
 338
 339 //=======================================================================
 340 //function : RemoveFromResult
 341 //purpose  :
 342 //=======================================================================
 343 void BOPAlgo_CellsBuilder::RemoveFromResult(const TopTools_ListOfShape& theLSToTake,
 344                                             const TopTools_ListOfShape& theLSToAvoid)
 345 {
 346   // find parts
 347   TopTools_ListOfShape aParts;
 348   FindParts(theLSToTake, theLSToAvoid, aParts);
 349   if (aParts.IsEmpty()) {
 350     return;
 351   }
 352   //
 353   // collect parts into the map and remove parts from materials
 354   TopTools_MapOfShape aPartsToRemove;
 355   TopTools_ListIteratorOfListOfShape aItP(aParts);
 356   for (; aItP.More(); aItP.Next()) {
 357     const TopoDS_Shape& aPart = aItP.Value();
 358     aPartsToRemove.Add(aPart);
 359     //
 360     const Standard_Integer* pMaterial = myShapeMaterial.Seek(aPart);
 361     if (pMaterial) {
 362       TopTools_ListOfShape* pLSM = myMaterials.ChangeSeek(*pMaterial);
 363       if (pLSM) {
 364         TopTools_ListIteratorOfListOfShape aItM(*pLSM);
 365         for (; aItM.More(); aItM.Next()) {
 366           if (aPart.IsSame(aItM.Value())) {
 367             pLSM->Remove(aItM);
 368             break;
 369           }
 370         }
 371       }
 372       myShapeMaterial.UnBind(aPart);
 373     }
 374   }
 375   //
 376   BRep_Builder aBB;
 377   TopoDS_Compound aResult;
 378   aBB.MakeCompound(aResult);
 379   Standard_Boolean bChanged = Standard_False;
 380   //
 381   TopoDS_Iterator aIt(myShape);
 382   for (; aIt.More(); aIt.Next()) {
 383     const TopoDS_Shape& aS = aIt.Value();
 384     TopAbs_ShapeEnum aType = aS.ShapeType();
 385     if (aType != TopAbs_WIRE &&
 386         aType != TopAbs_SHELL &&
 387         aType != TopAbs_COMPSOLID) {
 388       // basic element
 389       if (aPartsToRemove.Contains(aS)) {
 390         bChanged = Standard_True;
 391         continue;
 392       }
 393       aBB.Add(aResult, aS);
 394     }
 395     else {
 396       // container
 397       TopoDS_Compound aSC;
 398       aBB.MakeCompound(aSC);
 399       Standard_Boolean bSCNotEmpty = Standard_False;
 400       //
 401       TopoDS_Iterator aItSC(aS);
 402       for (; aItSC.More(); aItSC.Next()) {
 403         const TopoDS_Shape& aSS = aItSC.Value();
 404         if (aPartsToRemove.Contains(aSS)) {
 405           bChanged = Standard_True;
 406           continue;
 407         }
 408         //
 409         bSCNotEmpty = Standard_True;
 410         aBB.Add(aSC, aSS);
 411       }
 412       //
 413       if (bSCNotEmpty) {
 414         MakeTypedContainers(aSC, aResult);
 415       }
 416     }
 417   }
 418   //
 419   if (bChanged) {
 420     myShape = aResult;
 421     //
 422     PrepareHistory(Message_ProgressRange());
 423   }
 424 }
 425
 426 //=======================================================================
 427 //function : RemoveAllFromResult
 428 //purpose  :
 429 //=======================================================================
 430 void BOPAlgo_CellsBuilder::RemoveAllFromResult()
 431 {
 432   // empty compound
 433   TopoDS_Compound aC;
 434   BRep_Builder().MakeCompound(aC);
 435   myShape = aC;
 436   //
 437   myMaterials.Clear();
 438   myShapeMaterial.Clear();
 439   myMapModified.Clear();
 440   //
 441   PrepareHistory(Message_ProgressRange());
 442 }
 443
 444 //=======================================================================
 445 //function : RemoveInternalBoundaries
 446 //purpose  :
 447 //=======================================================================
 448 void BOPAlgo_CellsBuilder::RemoveInternalBoundaries()
 449 {
 450   if (myMaterials.IsEmpty()) {
 451     return;
 452   }
 453   //
 454   BRep_Builder aBB;
 455   TopoDS_Compound aResult;
 456   aBB.MakeCompound(aResult);
 457   //
 458   Standard_Boolean bChanged = Standard_False;
 459   // try to remove the internal boundaries between the
 460   // shapes of the same material
 461   TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape aItM(myMaterials);
 462   TopTools_ListOfShape aLSUnify[2];
 463   TopTools_MapOfShape aKeepMap[2];
 464   for (; aItM.More(); aItM.Next()) {
 465     Standard_Integer iMaterial = aItM.Key();
 466     TopTools_ListOfShape& aLS = aItM.ChangeValue();
 467     //
 468     if (aLS.IsEmpty()) {
 469       continue;
 470     }
 471     //
 472     if (aLS.Extent() == 1) {
 473       TopAbs_ShapeEnum aType = aLS.First().ShapeType();
 474       if (aType != TopAbs_WIRE &&
 475           aType != TopAbs_SHELL &&
 476           aType != TopAbs_COMPSOLID) {
 477         aBB.Add(aResult, aLS.First());
 478         continue;
 479       }
 480     }
 481     //
 482     // check the shapes of the same material to be of the same type
 483     TopTools_ListIteratorOfListOfShape aItLS(aLS);
 484     TopAbs_ShapeEnum aType = aItLS.Value().ShapeType();
 485     for (aItLS.Next(); aItLS.More(); aItLS.Next()) {
 486       if (aType != aItLS.Value().ShapeType()) {
 487         break;
 488       }
 489     }
 490
 491     if (aItLS.More())
 492     {
 493       // add the warning
 494       TopoDS_Compound aMultiDimS;
 495       aBB.MakeCompound(aMultiDimS);
 496       aBB.Add(aMultiDimS, aLS.First());
 497       aBB.Add(aMultiDimS, aItLS.Value());
 498       AddWarning(new BOPAlgo_AlertRemovalOfIBForMDimShapes(aMultiDimS));
 499     }
 500     else
 501     {
 502       if (aType == TopAbs_EDGE || aType == TopAbs_FACE)
 503       {
 504         // for edges and faces, just collect shapes to unify them later after exiting the loop;
 505         // collect boundaries of shapes of current material in the keep map
 506         Standard_Integer iType = (aType == TopAbs_EDGE ? 0 : 1);
 507         CollectMaterialBoundaries(aLS, aKeepMap[iType]);
 508         // save shapes to unify later
 509         TopTools_ListOfShape aCopy(aLS);
 510         aLSUnify[iType].Append(aCopy);
 511         continue;
 512       }
 513       else
 514       {
 515         // aType is Solid;
 516         // remove internal faces between solids of the same material just now
 517         TopTools_ListOfShape aLSNew;
 518         if (RemoveInternals(aLS, aLSNew))
 519         {
 520           bChanged = Standard_True;
 521           // update materials maps
 522           for (aItLS.Initialize(aLSNew); aItLS.More(); aItLS.Next()) {
 523             const TopoDS_Shape& aS = aItLS.Value();
 524             myShapeMaterial.Bind(aS, iMaterial);
 525           }
 526           aLS.Assign(aLSNew);
 527         }
 528       }
 529     }
 530     // add shapes to result (multidimensional and solids)
 531     for (aItLS.Initialize(aLS); aItLS.More(); aItLS.Next()) {
 532       const TopoDS_Shape& aS = aItLS.Value();
 533       aBB.Add(aResult, aS);
 534     }
 535   }
 536
 537   // remove internal boundaries for edges and faces
 538   for (Standard_Integer iType = 0; iType < 2; ++iType)
 539   {
 540     if (aLSUnify[iType].IsEmpty())
 541       continue;
 542     TopTools_ListOfShape aLSN;
 543     if (RemoveInternals(aLSUnify[iType], aLSN, aKeepMap[iType]))
 544       bChanged = Standard_True;
 545     // add shapes to result ([unified] edges or faces)
 546     for (TopTools_ListIteratorOfListOfShape aItLS(aLSN); aItLS.More(); aItLS.Next()) {
 547       const TopoDS_Shape& aS = aItLS.Value();
 548       aBB.Add(aResult, aS);
 549     }
 550   }
 551   //
 552   if (bChanged) {
 553     // add shapes without material into result
 554     TopoDS_Iterator aIt(myShape);
 555     for (; aIt.More(); aIt.Next()) {
 556       const TopoDS_Shape& aS = aIt.Value();
 557       //
 558       if (myShapeMaterial.IsBound(aS)) {
 559         continue;
 560       }
 561       //
 562       // check if it is not a collection
 563       TopAbs_ShapeEnum aType = aS.ShapeType();
 564       if (aType != TopAbs_WIRE &&
 565           aType != TopAbs_SHELL &&
 566           aType != TopAbs_COMPSOLID) {
 567         aBB.Add(aResult, aS);
 568       }
 569       else {
 570         TopoDS_Compound aSC;
 571         aBB.MakeCompound(aSC);
 572         Standard_Boolean bSCEmpty(Standard_True), bSCChanged(Standard_False);
 573         //
 574         TopoDS_Iterator aItSC(aS);
 575         for (; aItSC.More(); aItSC.Next()) {
 576           const TopoDS_Shape& aSS = aItSC.Value();
 577           if (!myShapeMaterial.IsBound(aSS)) {
 578             aBB.Add(aSC, aSS);
 579             bSCEmpty = Standard_False;
 580           }
 581           else {
 582             bSCChanged = Standard_True;
 583           }
 584         }
 585         //
 586         if (bSCEmpty) {
 587           continue;
 588         }
 589         //
 590         if (bSCChanged) {
 591           MakeTypedContainers(aSC, aResult);
 592         }
 593         else {
 594           aBB.Add(aResult, aS);
 595         }
 596       }
 597     }
 598     //
 599     myShape = aResult;
 600     //
 601     PrepareHistory(Message_ProgressRange());
 602   }
 603 }
 604
 605 //=======================================================================
 606 //function : FindPart
 607 //purpose  :
 608 //=======================================================================
 609 void BOPAlgo_CellsBuilder::FindParts(const TopTools_ListOfShape& theLSToTake,
 610                                      const TopTools_ListOfShape& theLSToAvoid,
 611                                      TopTools_ListOfShape& theParts)
 612 {
 613   if (theLSToTake.IsEmpty()) {
 614     return;
 615   }
 616   //
 617   // map shapes to avoid
 618   TopTools_MapOfShape aMSToAvoid;
 619   TopTools_ListIteratorOfListOfShape aItArgs(theLSToAvoid);
 620   for (; aItArgs.More(); aItArgs.Next()) {
 621     const TopoDS_Shape& aS = aItArgs.Value();
 622     aMSToAvoid.Add(aS);
 623   }
 624   //
 625   // map shapes to be taken
 626   TopTools_MapOfShape aMSToTake;
 627   aItArgs.Initialize(theLSToTake);
 628   for (; aItArgs.More(); aItArgs.Next()) {
 629     const TopoDS_Shape& aS = aItArgs.Value();
 630     aMSToTake.Add(aS);
 631   }
 632   //
 633   Standard_Integer aNbS = aMSToTake.Extent();
 634   //
 635   // among the shapes to be taken into result, find any one
 636   // of minimal dimension
 637   Standard_Integer iDimMin = 10;
 638   TopoDS_Shape aSMin;
 639   //
 640   aItArgs.Initialize(theLSToTake);
 641   for (; aItArgs.More(); aItArgs.Next()) {
 642     const TopoDS_Shape& aS = aItArgs.Value();
 643     Standard_Integer iDim = BOPTools_AlgoTools::Dimension(aS);
 644     if (iDim < iDimMin) {
 645       iDimMin = iDim;
 646       aSMin = aS;
 647     }
 648   }
 649   //
 650   // among the split parts of the shape of minimal dimension
 651   // look for the parts to be taken into result
 652   TopAbs_ShapeEnum aType = TypeToExplore(iDimMin);
 653   TopExp_Explorer aExp(aSMin, aType);
 654   for (; aExp.More(); aExp.Next()) {
 655     const TopoDS_Shape& aST = aExp.Current();
 656     // get split parts of the shape
 657     TopTools_ListOfShape aLSTIm;
 658     if (!myImages.IsBound(aST)) {
 659       aLSTIm.Append(aST);
 660     } else {
 661       aLSTIm = myImages.Find(aST);
 662     }
 663     //
 664     TopTools_ListIteratorOfListOfShape aItIm(aLSTIm);
 665     for (; aItIm.More(); aItIm.Next()) {
 666       const TopoDS_Shape& aPart = aItIm.Value();
 667       //
 668       if (!myIndex.Contains(aPart)) {
 669         continue;
 670       }
 671       //
 672       // get input shapes in which the split part is contained
 673       const TopTools_ListOfShape& aLS = myIndex.FindFromKey(aPart);
 674       if (aLS.Extent() < aNbS) {
 675         continue;
 676       }
 677       //
 678       // check that input shapes containing the part should not be avoided
 679       TopTools_MapOfShape aMS;
 680       aItArgs.Initialize(aLS);
 681       for (; aItArgs.More(); aItArgs.Next()) {
 682         const TopoDS_Shape& aS = aItArgs.Value();
 683         aMS.Add(aS);
 684         if (aMSToAvoid.Contains(aS)) {
 685           break;
 686         }
 687       }
 688       //
 689       if (aItArgs.More()) {
 690         continue;
 691       }
 692       //
 693       // check that all shapes which should be taken contain the part
 694       aItArgs.Initialize(theLSToTake);
 695       for (; aItArgs.More(); aItArgs.Next()) {
 696         if (!aMS.Contains(aItArgs.Value())) {
 697           break;
 698         }
 699       }
 700       //
 701       if (!aItArgs.More()) {
 702         theParts.Append(aPart);
 703       }
 704     }
 705   }
 706 }
 707
 708 //=======================================================================
 709 //function : MakeContainers
 710 //purpose  :
 711 //=======================================================================
 712 void BOPAlgo_CellsBuilder::MakeContainers()
 713 {
 714   BRep_Builder aBB;
 715   TopoDS_Compound aResult;
 716   aBB.MakeCompound(aResult);
 717   //
 718   // basic elements of type EDGE, FACE and SOLID added into result
 719   TopTools_ListOfShape aLS[3];
 720   //
 721   TopoDS_Iterator aIt(myShape);
 722   for (; aIt.More(); aIt.Next()) {
 723     const TopoDS_Shape& aS = aIt.Value();
 724     //
 725     Standard_Integer iDim = BOPTools_AlgoTools::Dimension(aS);
 726     if (iDim <= 0) {
 727       aBB.Add(aResult, aS);
 728       continue;
 729     }
 730     //
 731     aLS[iDim-1].Append(aS);
 732   }
 733   //
 734   for (Standard_Integer i = 0; i < 3; ++i) {
 735     if (aLS[i].IsEmpty()) {
 736       continue;
 737     }
 738     //
 739     TopoDS_Compound aC;
 740     aBB.MakeCompound(aC);
 741     TopTools_ListIteratorOfListOfShape aItLS(aLS[i]);
 742     for (; aItLS.More(); aItLS.Next()) {
 743       aBB.Add(aC, aItLS.Value());
 744     }
 745     //
 746     MakeTypedContainers(aC, aResult);
 747   }
 748   myShape = aResult;
 749 }
 750
 751 //=======================================================================
 752 //function : RemoveInternals
 753 //purpose  :
 754 //=======================================================================
 755 Standard_Boolean BOPAlgo_CellsBuilder::RemoveInternals(const TopTools_ListOfShape& theLS,
 756                                                        TopTools_ListOfShape& theLSNew,
 757                                                        const TopTools_MapOfShape& theMapKeepBnd)
 758 {
 759   Standard_Boolean bRemoved = Standard_False;
 760   if (theLS.Extent() < 2) {
 761     theLSNew = theLS;
 762     return bRemoved;
 763   }
 764   //
 765   TopAbs_ShapeEnum aType = theLS.First().ShapeType();
 766   //
 767   if (aType == TopAbs_EDGE ||
 768       aType == TopAbs_FACE) {
 769     //
 770     // make container
 771     BRep_Builder aBB;
 772     TopoDS_Shape aShape;
 773     //
 774     BOPTools_AlgoTools::MakeContainer
 775       ((aType == TopAbs_FACE) ? TopAbs_SHELL : TopAbs_WIRE, aShape);
 776     //
 777     for (TopTools_ListIteratorOfListOfShape aIt(theLS); aIt.More(); aIt.Next()) {
 778       const TopoDS_Shape& aS = aIt.Value();
 779       aBB.Add(aShape, aS);
 780     }
 781     //
 782     // Unify same domain
 783     Standard_Boolean bFaces, bEdges;
 784     //
 785     bFaces = (aType == TopAbs_FACE);
 786     bEdges = (aType == TopAbs_EDGE);
 787     ShapeUpgrade_UnifySameDomain anUnify (aShape, bEdges, bFaces);
 788     anUnify.KeepShapes(theMapKeepBnd);
 789     anUnify.Build();
 790     const TopoDS_Shape& aSNew = anUnify.Shape();
 791     //
 792     TopExp_Explorer aExp(aSNew, aType);
 793     for (; aExp.More(); aExp.Next()) {
 794       const TopoDS_Shape& aSn = aExp.Current();
 795       theLSNew.Append(aSn);
 796     }
 797     //
 798     if (theLSNew.IsEmpty()) {
 799       // add the warning
 800       if (bFaces)
 801         AddWarning (new BOPAlgo_AlertRemovalOfIBForFacesFailed (aShape));
 802       else
 803         AddWarning (new BOPAlgo_AlertRemovalOfIBForEdgesFailed (aShape));
 804       //
 805       theLSNew.Assign(theLS);
 806       return bRemoved;
 807     }
 808     //
 809     // fill map of modified shapes
 810     TopTools_IndexedMapOfShape aMG;
 811     Standard_Integer i, aNb;
 812     //
 813     TopExp::MapShapes(aShape, TopAbs_VERTEX, aMG);
 814     TopExp::MapShapes(aShape, TopAbs_EDGE,   aMG);
 815     TopExp::MapShapes(aShape, TopAbs_FACE,   aMG);
 816     //
 817     aNb = aMG.Extent();
 818     for (i = 1; i <= aNb; ++i) {
 819       const TopoDS_Shape& aSS = aMG(i);
 820       const Standard_Integer* pMaterial = myShapeMaterial.Seek(aSS);
 821       const TopTools_ListOfShape& aLSMod = anUnify.History()->Modified(aSS);
 822       TopTools_ListIteratorOfListOfShape aIt(aLSMod);
 823       for (; aIt.More(); aIt.Next()) {
 824         const TopoDS_Shape& aSU = aIt.Value();
 825         myMapModified.Bind(aSS, aSU);
 826         bRemoved = Standard_True;
 827         if (pMaterial && !myShapeMaterial.IsBound(aSU))
 828           myShapeMaterial.Bind(aSU, *pMaterial);
 829       }
 830     }
 831   }
 832   else if (aType == TopAbs_SOLID) {
 833     BRep_Builder aBB;
 834     TopoDS_Compound aSolids;
 835     aBB.MakeCompound(aSolids);
 836     //
 837     TopTools_ListIteratorOfListOfShape aItLS(theLS);
 838     for (; aItLS.More(); aItLS.Next()) {
 839       const TopoDS_Shape& aSol = aItLS.Value();
 840       aBB.Add(aSolids, aSol);
 841     }
 842     //
 843     // Make connexity blocks of solids to create from each isolated block one solid.
 844     // It will allow attaching internal entities of the solids to new solid.
 845     TopTools_ListOfShape aLCB;
 846     BOPTools_AlgoTools::MakeConnexityBlocks(aSolids, TopAbs_FACE, TopAbs_SOLID, aLCB);
 847     //
 848     // for each block remove internal faces
 849     TopTools_ListIteratorOfListOfShape aItLCB(aLCB);
 850     for (; aItLCB.More(); aItLCB.Next()) {
 851       const TopoDS_Shape& aCB = aItLCB.Value();
 852       //
 853       // Map faces and solids to find boundary faces that can be removed
 854       TopTools_IndexedDataMapOfShapeListOfShape aDMFS;
 855       // internal entities
 856       TopTools_ListOfShape aLSInt;
 857       //
 858       TopoDS_Iterator aItS(aCB);
 859       for (; aItS.More(); aItS.Next()) {
 860         const TopoDS_Shape& aSol = aItS.Value();
 861         //
 862         TopoDS_Iterator aItIS(aSol);
 863         for (; aItIS.More(); aItIS.Next()) {
 864           const TopoDS_Shape& aSI = aItIS.Value();
 865           if (aSI.Orientation() == TopAbs_INTERNAL) {
 866             aLSInt.Append(aSI);
 867           }
 868           else {
 869             TopoDS_Iterator aItF(aSI);
 870             for (; aItF.More(); aItF.Next()) {
 871               const TopoDS_Shape& aF = aItF.Value();
 872               TopTools_ListOfShape *pLSols = aDMFS.ChangeSeek(aF);
 873               if (!pLSols) {
 874                 pLSols = &aDMFS(aDMFS.Add(aF, TopTools_ListOfShape()));
 875               }
 876               pLSols->Append(aSol);
 877             }
 878           }
 879         }
 880       }
 881       //
 882       // to build unified solid, select only faces attached to only one solid
 883       TopTools_ListOfShape aLFUnique;
 884       Standard_Integer i, aNb = aDMFS.Extent();
 885       for (i = 1; i <= aNb; ++i) {
 886         if (aDMFS(i).Extent() == 1) {
 887           aLFUnique.Append(aDMFS.FindKey(i));
 888         }
 889       }
 890       //
 891       if (aNb == aLFUnique.Extent()) {
 892         // no faces to remove
 893         aItS.Initialize(aCB);
 894         for (; aItS.More(); aItS.Next()) {
 895           theLSNew.Append(aItS.Value());
 896         }
 897         continue;
 898       }
 899       //
 900       // build new solid
 901       BOPAlgo_BuilderSolid aBS;
 902       aBS.SetShapes(aLFUnique);
 903       aBS.Perform();
 904       //
 905       if (aBS.HasErrors() || aBS.Areas().Extent() != 1) {
 906         // add the warning
 907         {
 908           TopoDS_Compound aUniqeFaces;
 909           aBB.MakeCompound(aUniqeFaces);
 910           TopTools_ListIteratorOfListOfShape aItLFUniqe(aLFUnique);
 911           for (; aItLFUniqe.More(); aItLFUniqe.Next()) {
 912             aBB.Add(aUniqeFaces, aItLFUniqe.Value());
 913           }
 914           //
 915           AddWarning (new BOPAlgo_AlertRemovalOfIBForSolidsFailed (aUniqeFaces));
 916         }
 917         //
 918         aItS.Initialize(aCB);
 919         for (; aItS.More(); aItS.Next()) {
 920           theLSNew.Append(aItS.Value());
 921         }
 922         continue;
 923       }
 924       //
 925       myReport->Merge(aBS.GetReport());
 926       //
 927       TopoDS_Solid& aSNew = *(TopoDS_Solid*)&aBS.Areas().First();
 928       //
 929       // put all internal parts into new solid
 930       aSNew.Free(Standard_True);
 931       TopTools_ListIteratorOfListOfShape aItLSI(aLSInt);
 932       for (; aItLSI.More(); aItLSI.Next()) {
 933         aBB.Add(aSNew, aItLSI.Value());
 934       }
 935       aSNew.Free(Standard_False);
 936       //
 937       theLSNew.Append(aSNew);
 938       bRemoved = Standard_True;
 939
 940       // Save information about the fuse of the solids into a history map
 941       aItS.Initialize(aCB);
 942       for (; aItS.More(); aItS.Next())
 943         myMapModified.Bind(aItS.Value(), aSNew);
 944     }
 945   }
 946   return bRemoved;
 947 }
 948
 949 //=======================================================================
 950 //function : LocModified
 951 //purpose  :
 952 //=======================================================================
 953 const TopTools_ListOfShape* BOPAlgo_CellsBuilder::LocModified(const TopoDS_Shape& theS)
 954 {
 955   // Get shape's modification coming from GF operation
 956   const TopTools_ListOfShape* pLSp = BOPAlgo_Builder::LocModified(theS);
 957   if (myMapModified.IsEmpty())
 958     // No local modifications
 959     return pLSp;
 960
 961   myHistShapes.Clear();
 962
 963   // Check if the shape (or its splits) has participated in unification
 964   if (!pLSp)
 965   {
 966     // No splits from GF operation.
 967     // Check if the shape has been unified with other shapes
 968     const TopoDS_Shape* pSU = myMapModified.Seek(theS);
 969     if (!pSU)
 970       return NULL;
 971
 972     myHistShapes.Append(*pSU);
 973   }
 974   else
 975   {
 976     TopTools_MapOfShape aMFence;
 977     // Process all GF splits and check them for local unification with other shapes
 978     TopTools_ListIteratorOfListOfShape aIt(*pLSp);
 979     for (; aIt.More(); aIt.Next())
 980     {
 981       const TopoDS_Shape* pSp = &aIt.Value();
 982       const TopoDS_Shape* pSU = myMapModified.Seek(*pSp);
 983       if (pSU) pSp = pSU;
 984       if (aMFence.Add(*pSp))
 985         myHistShapes.Append(*pSp);
 986     }
 987   }
 988   return &myHistShapes;
 989 }
 990
 991 //=======================================================================
 992 //function : MakeTypedContainers
 993 //purpose  :
 994 //=======================================================================
 995 void MakeTypedContainers(const TopoDS_Shape& theSC,
 996                          TopoDS_Shape& theResult)
 997 {
 998   TopAbs_ShapeEnum aContainerType, aConnexityType, aPartType;
 999   //
1000   aPartType = TypeToExplore(BOPTools_AlgoTools::Dimension(theSC));
1001   switch (aPartType) {
1002     case TopAbs_EDGE: {
1003       aContainerType = TopAbs_WIRE;
1004       aConnexityType = TopAbs_VERTEX;
1005       break;
1006     }
1007     case TopAbs_FACE: {
1008       aContainerType = TopAbs_SHELL;
1009       aConnexityType = TopAbs_EDGE;
1010       break;
1011     }
1012     case TopAbs_SOLID: {
1013       aContainerType = TopAbs_COMPSOLID;
1014       aConnexityType = TopAbs_FACE;
1015       break;
1016     }
1017     default:
1018       return;
1019   }
1020   //
1021   TopTools_ListOfShape aLCB;
1022   BOPTools_AlgoTools::MakeConnexityBlocks(theSC, aConnexityType, aPartType, aLCB);
1023   if (aLCB.IsEmpty()) {
1024     return;
1025   }
1026   //
1027   BRep_Builder aBB;
1028   TopExp_Explorer aExp;
1029   TopTools_ListIteratorOfListOfShape aItCB;
1030   //
1031   aItCB.Initialize(aLCB);
1032   for (; aItCB.More(); aItCB.Next()) {
1033     TopoDS_Shape aRCB;
1034     BOPTools_AlgoTools::MakeContainer(aContainerType, aRCB);
1035     //
1036     const TopoDS_Shape& aCB = aItCB.Value();
1037     aExp.Init(aCB, aPartType);
1038     for (; aExp.More(); aExp.Next()) {
1039       const TopoDS_Shape& aCBS = aExp.Current();
1040       aBB.Add(aRCB, aCBS);
1041     }
1042     //
1043     if (aContainerType == TopAbs_SHELL) {
1044       BOPTools_AlgoTools::OrientFacesOnShell(aRCB);
1045     }
1046     //
1047     aBB.Add(theResult, aRCB);
1048   }
1049 }
1050
1051 //=======================================================================
1052 //function : CollectMaterialBoundaries
1053 //purpose  : Add to theMapKeepBnd the boundary shapes of the area defined by shapes from the list
1054 //=======================================================================
1055 static void CollectMaterialBoundaries(const TopTools_ListOfShape& theLS,
1056                                       TopTools_MapOfShape& theMapKeepBnd)
1057 {
1058   TopAbs_ShapeEnum aType = theLS.First().ShapeType();
1059   TopAbs_ShapeEnum aTypeSubsh = (aType == TopAbs_FACE ? TopAbs_EDGE : TopAbs_VERTEX);
1060   TopTools_IndexedDataMapOfShapeListOfShape aMapSubSh;
1061   TopTools_ListIteratorOfListOfShape anIt(theLS);
1062   for (; anIt.More(); anIt.Next())
1063   {
1064     const TopoDS_Shape& aS = anIt.Value();
1065     TopExp::MapShapesAndAncestors(aS, aTypeSubsh, aType, aMapSubSh);
1066   }
1067   for (int i = 1; i <= aMapSubSh.Extent(); i++)
1068   {
1069     // check if the subshape belongs to boundary of the area
1070     if (aMapSubSh(i).Extent() == 1)
1071     {
1072       // add to theMapKeepBnd
1073       theMapKeepBnd.Add(aMapSubSh.FindKey(i));
1074     }
1075   }
1076 }
1077
1078 //=======================================================================
1079 //function : TypeToExplore
1080 //purpose  :
1081 //=======================================================================
1082 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim)
1083 {
1084   TopAbs_ShapeEnum aRet;
1085   //
1086   switch(theDim) {
1087   case 0:
1088     aRet=TopAbs_VERTEX;
1089     break;
1090   case 1:
1091     aRet=TopAbs_EDGE;
1092     break;
1093   case 2:
1094     aRet=TopAbs_FACE;
1095     break;
1096   case 3:
1097     aRet=TopAbs_SOLID;
1098     break;
1099   default:
1100     aRet=TopAbs_SHAPE;
1101     break;
1102   }
1103   return aRet;
1104 }