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