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