src/BOPAlgo/BOPAlgo_BOP.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15
  16 #include <BOPAlgo_BOP.hxx>
  17 #include <BOPAlgo_BuilderSolid.hxx>
  18 #include <BOPAlgo_PaveFiller.hxx>
  19 #include <BOPAlgo_Tools.hxx>
  20 #include <BOPAlgo_Alerts.hxx>
  21 #include <BOPDS_DS.hxx>
  22 #include <BOPTools_AlgoTools.hxx>
  23 #include <BOPTools_AlgoTools3D.hxx>
  24 #include <BOPTools_IndexedDataMapOfSetShape.hxx>
  25 #include <BOPTools_Set.hxx>
  26 #include <BRep_Builder.hxx>
  27 #include <BRep_Tool.hxx>
  28 #include <NCollection_DataMap.hxx>
  29 #include <TopAbs_ShapeEnum.hxx>
  30 #include <TopExp.hxx>
  31 #include <TopExp_Explorer.hxx>
  32 #include <TopoDS.hxx>
  33 #include <TopoDS_Compound.hxx>
  34 #include <TopoDS_Edge.hxx>
  35 #include <TopoDS_Iterator.hxx>
  36 #include <TopoDS_Shape.hxx>
  37 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  38 #include <TopTools_IndexedMapOfShape.hxx>
  39 #include <TopTools_ListOfShape.hxx>
  40 #include <TopTools_MapOfShape.hxx>
  41
  42 static
  43   TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim);
  44 //
  45 static
  46   void CollectContainers(const TopoDS_Shape& theS,
  47                          TopTools_ListOfShape& theLSC);
  48 //
  49 static
  50   void RemoveDuplicates(TopTools_ListOfShape& theContainers);
  51 //
  52 static
  53   void RemoveDuplicates(TopTools_ListOfShape& theContainers,
  54                         const TopAbs_ShapeEnum theType);
  55 //
  56 static
  57   Standard_Integer NbCommonItemsInMap(const TopTools_MapOfShape& theM1,
  58                                       const TopTools_MapOfShape& theM2);
  59 //
  60 static
  61   void MapFacesToBuildSolids(const TopoDS_Shape& theSol,
  62                              TopTools_IndexedDataMapOfShapeListOfShape& theMFS);
  63
  64 //=======================================================================
  65 //function :
  66 //purpose  :
  67 //=======================================================================
  68 BOPAlgo_BOP::BOPAlgo_BOP()
  69 : BOPAlgo_ToolsProvider()
  70 {
  71   Clear();
  72 }
  73 //=======================================================================
  74 //function :
  75 //purpose  :
  76 //=======================================================================
  77 BOPAlgo_BOP::BOPAlgo_BOP(const Handle(NCollection_BaseAllocator)& theAllocator)
  78 : BOPAlgo_ToolsProvider(theAllocator)
  79 {
  80   Clear();
  81 }
  82 //=======================================================================
  83 //function : ~
  84 //purpose  :
  85 //=======================================================================
  86 BOPAlgo_BOP::~BOPAlgo_BOP()
  87 {
  88 }
  89 //=======================================================================
  90 //function : Clear
  91 //purpose  :
  92 //=======================================================================
  93 void BOPAlgo_BOP::Clear()
  94 {
  95   myOperation=BOPAlgo_UNKNOWN;
  96   myDims[0]=-1;
  97   myDims[1]=-1;
  98
  99   BOPAlgo_ToolsProvider::Clear();
 100 }
 101 //=======================================================================
 102 //function : SetOperation
 103 //purpose  :
 104 //=======================================================================
 105 void BOPAlgo_BOP::SetOperation(const BOPAlgo_Operation theOperation)
 106 {
 107   myOperation=theOperation;
 108 }
 109 //=======================================================================
 110 //function : Operation
 111 //purpose  :
 112 //=======================================================================
 113 BOPAlgo_Operation BOPAlgo_BOP::Operation()const
 114 {
 115   return myOperation;
 116 }
 117 //=======================================================================
 118 //function : CheckData
 119 //purpose  :
 120 //=======================================================================
 121 void BOPAlgo_BOP::CheckData()
 122 {
 123   Standard_Integer i, j, aNbArgs, aNbTools;
 124   Standard_Boolean bFuse;
 125   TopTools_ListIteratorOfListOfShape aItLS;
 126   //
 127   if (!(myOperation==BOPAlgo_COMMON ||
 128         myOperation==BOPAlgo_FUSE ||
 129         myOperation==BOPAlgo_CUT||
 130         myOperation==BOPAlgo_CUT21)) {
 131     // non-licit operation
 132     AddError (new BOPAlgo_AlertBOPNotSet);
 133     return;
 134   }
 135   //
 136   aNbArgs=myArguments.Extent();
 137   if (!aNbArgs) {
 138     // invalid number of Arguments
 139     AddError (new BOPAlgo_AlertTooFewArguments);
 140     return;
 141   }
 142   //
 143   aNbTools=myTools.Extent();
 144   if (!aNbTools) {
 145     // invalid number of Tools
 146     AddError (new BOPAlgo_AlertTooFewArguments);
 147     return;
 148   }
 149   //
 150   CheckFiller();
 151   if (HasErrors()) {
 152     return;
 153   }
 154   //
 155   bFuse = (myOperation == BOPAlgo_FUSE);
 156   //
 157   // The rules for different types of operations are the following:
 158   // 1. FUSE:   All arguments and tools should have the same dimension;
 159   // 2. CUT:    The MAXIMAL dimension of the ARGUMENTS should be less
 160   //            or equal to the MINIMAL dimension of the TOOLS;
 161   // 3. CUT21:  The MINIMAL dimension of ARGUMENTS should be grater
 162   //            or equal to the MAXIMAL dimension of the TOOLS;
 163   // 4. COMMON: The arguments and tools could have any dimensions.
 164   //
 165   Standard_Integer iDimMin[2] = { 3, 3 },
 166                    iDimMax[2] = { 0, 0 };
 167   Standard_Boolean bHasValid[2] = {Standard_False, Standard_False};
 168   //
 169   for (i=0; i<2; ++i) {
 170     const TopTools_ListOfShape& aLS=(!i)? myArguments : myTools;
 171     aItLS.Initialize(aLS);
 172     for (j=0; aItLS.More(); aItLS.Next(), ++j) {
 173       const TopoDS_Shape& aS=aItLS.Value();
 174       Standard_Boolean bIsEmpty = BOPTools_AlgoTools3D::IsEmptyShape(aS);
 175       if (bIsEmpty)
 176       {
 177         AddWarning(new BOPAlgo_AlertEmptyShape (aS));
 178         continue;
 179       }
 180
 181       Standard_Integer iDMin, iDMax;
 182       BOPTools_AlgoTools::Dimensions(aS, iDMin, iDMax);
 183
 184       if (iDMin < iDimMin[i])
 185         iDimMin[i] = iDMin;
 186       if (iDMax > iDimMax[i])
 187         iDimMax[i] = iDMax;
 188
 189       if (bFuse && (iDimMin[i] != iDimMax[i]))
 190       {
 191         // non-homogeneous argument
 192         AddError (new BOPAlgo_AlertBOPNotAllowed);
 193         return;
 194       }
 195       bHasValid[i] = Standard_True;
 196     }
 197   }
 198   //
 199   if (bHasValid[0] && bHasValid[1]) {
 200     if (((myOperation == BOPAlgo_FUSE)  && (iDimMax[0] != iDimMax[1])) ||
 201         ((myOperation == BOPAlgo_CUT)   && (iDimMax[0] >  iDimMin[1])) ||
 202         ((myOperation == BOPAlgo_CUT21) && (iDimMin[0] <  iDimMax[1])) )
 203     {
 204       // non-licit operation for the arguments
 205       AddError (new BOPAlgo_AlertBOPNotAllowed);
 206       return;
 207     }
 208   }
 209
 210   if (bHasValid[0] || bHasValid[1])
 211   {
 212     // In case of all empty shapes in one of the groups
 213     // this group acquires the dimension of other group
 214     myDims[0] = bHasValid[0] ? iDimMin[0] : iDimMin[1];
 215     myDims[1] = bHasValid[1] ? iDimMin[1] : iDimMin[0];
 216   }
 217 }
 218 //=======================================================================
 219 //function : TreatEmtpyShape
 220 //purpose  :
 221 //=======================================================================
 222 Standard_Boolean BOPAlgo_BOP::TreatEmptyShape()
 223 {
 224   if (! GetReport()->HasAlert (STANDARD_TYPE(BOPAlgo_AlertEmptyShape)))
 225   {
 226     return Standard_False;
 227   }
 228   //
 229   // Find non-empty objects
 230   TopTools_ListOfShape aLValidObjs;
 231   TopTools_ListIteratorOfListOfShape aItLS(myArguments);
 232   for (; aItLS.More(); aItLS.Next()) {
 233     if (!BOPTools_AlgoTools3D::IsEmptyShape(aItLS.Value())) {
 234       aLValidObjs.Append(aItLS.Value());
 235     }
 236   }
 237   //
 238   // Find non-empty tools
 239   TopTools_ListOfShape aLValidTools;
 240   aItLS.Initialize(myTools);
 241   for (; aItLS.More() ; aItLS.Next()) {
 242     if (!BOPTools_AlgoTools3D::IsEmptyShape(aItLS.Value())) {
 243       aLValidTools.Append(aItLS.Value());
 244     }
 245   }
 246   //
 247   Standard_Boolean bHasValidObj  = (aLValidObjs .Extent() > 0);
 248   Standard_Boolean bHasValidTool = (aLValidTools.Extent() > 0);
 249   //
 250   if (bHasValidObj && bHasValidTool) {
 251     // We need to continue the operation to obtain the result
 252     return Standard_False;
 253   }
 254   //
 255   if (!bHasValidObj && !bHasValidTool) {
 256     // All shapes are empty shapes, the result will always be empty shape
 257     return Standard_True;
 258   }
 259   //
 260   // One of the groups of arguments consists of empty shapes only,
 261   // so we can build the result of operation right away just by
 262   // choosing the list of shapes to add to result, depending on
 263   // the type of the operation.
 264   // Although, if the group with valid shapes consists from more
 265   // than just one shape, depending on the operation type we may need
 266   // to split the shapes in this group before adding them into result.
 267
 268   TopTools_ListOfShape *pLResult = NULL;
 269   //
 270   switch (myOperation) {
 271     case BOPAlgo_FUSE:
 272     {
 273       if (aLValidObjs.Extent() + aLValidTools.Extent() > 1)
 274         // The arguments must be split before adding into result
 275         return Standard_False;
 276
 277       // Add not empty shapes into result
 278       pLResult = bHasValidObj ? &aLValidObjs : &aLValidTools;
 279       break;
 280     }
 281     case BOPAlgo_CUT:
 282     {
 283       if (aLValidObjs.Extent() > 1)
 284         // The objects must be split before adding into result
 285         return Standard_False;
 286
 287       // Add objects into result
 288       pLResult = &aLValidObjs;
 289       break;
 290     }
 291     case BOPAlgo_CUT21:
 292     {
 293       if (aLValidTools.Extent() > 1)
 294         // The tools must be split before adding into result
 295         return Standard_False;
 296
 297       // Add tools into result
 298       pLResult = &aLValidTools;
 299       break;
 300     }
 301     case BOPAlgo_COMMON:
 302       // Common will always be empty
 303       break;
 304     default:
 305       break;
 306   }
 307   //
 308   if (pLResult) {
 309     aItLS.Initialize(*pLResult);
 310     for (; aItLS.More(); aItLS.Next()) {
 311       BRep_Builder().Add(myShape, aItLS.Value());
 312     }
 313   }
 314   return Standard_True;
 315 }
 316 //=======================================================================
 317 //function : BuildResult
 318 //purpose  :
 319 //=======================================================================
 320 void BOPAlgo_BOP::BuildResult(const TopAbs_ShapeEnum theType)
 321 {
 322   TopAbs_ShapeEnum aType;
 323   BRep_Builder aBB;
 324   TopTools_MapOfShape aM;
 325   TopTools_ListIteratorOfListOfShape aIt, aItIm;
 326   //
 327   const TopTools_ListOfShape& aLA=myDS->Arguments();
 328   aIt.Initialize(aLA);
 329   for (; aIt.More(); aIt.Next()) {
 330     const TopoDS_Shape& aS=aIt.Value();
 331     aType=aS.ShapeType();
 332     if (aType==theType) {
 333       if (myImages.IsBound(aS)){
 334         const TopTools_ListOfShape& aLSIm=myImages.Find(aS);
 335         aItIm.Initialize(aLSIm);
 336         for (; aItIm.More(); aItIm.Next()) {
 337           const TopoDS_Shape& aSIm=aItIm.Value();
 338           if (aM.Add(aSIm)) {
 339             aBB.Add(myShape, aSIm);
 340           }
 341         }
 342       }
 343       else {
 344         if (aM.Add(aS)) {
 345           aBB.Add(myShape, aS);
 346         }
 347       }
 348     }
 349   }
 350 }
 351 //=======================================================================
 352 //function : Perform
 353 //purpose  :
 354 //=======================================================================
 355 void BOPAlgo_BOP::Perform(const Message_ProgressRange& theRange)
 356 {
 357   Handle(NCollection_BaseAllocator) aAllocator;
 358   BOPAlgo_PaveFiller* pPF;
 359   TopTools_ListIteratorOfListOfShape aItLS;
 360   //
 361   GetReport()->Clear();
 362   //
 363   if (myEntryPoint==1) {
 364     if (myPaveFiller) {
 365       delete myPaveFiller;
 366       myPaveFiller=NULL;
 367     }
 368   }
 369   //
 370   aAllocator=
 371     NCollection_BaseAllocator::CommonBaseAllocator();
 372   TopTools_ListOfShape aLS(aAllocator);
 373   //
 374   aItLS.Initialize(myArguments);
 375   for (; aItLS.More(); aItLS.Next()) {
 376     const TopoDS_Shape& aS=aItLS.Value();
 377     aLS.Append(aS);
 378   }
 379   //
 380   aItLS.Initialize(myTools);
 381   for (; aItLS.More(); aItLS.Next()) {
 382     const TopoDS_Shape& aS=aItLS.Value();
 383     aLS.Append(aS);
 384   }
 385   //
 386   pPF=new BOPAlgo_PaveFiller(aAllocator);
 387   pPF->SetArguments(aLS);
 388   pPF->SetRunParallel(myRunParallel);
 389   Message_ProgressScope aPS(theRange, "Performing Boolean operation", 10);
 390
 391   pPF->SetFuzzyValue(myFuzzyValue);
 392   pPF->SetNonDestructive(myNonDestructive);
 393   pPF->SetGlue(myGlue);
 394   pPF->SetUseOBB(myUseOBB);
 395   //
 396   pPF->Perform(aPS.Next(9));
 397   //
 398   myEntryPoint=1;
 399   PerformInternal(*pPF, aPS.Next());
 400 }
 401
 402 //=======================================================================
 403 // function: fillPIConstants
 404 // purpose:
 405 //=======================================================================
 406 void BOPAlgo_BOP::fillPIConstants (const Standard_Real theWhole, BOPAlgo_PISteps& theSteps) const
 407 {
 408   BOPAlgo_Builder::fillPIConstants(theWhole, theSteps);
 409   theSteps.SetStep (PIOperation_BuildShape, (myOperation == BOPAlgo_FUSE ? 10. : 5.) * theWhole / 100.);
 410 }
 411
 412 //=======================================================================
 413 //function : PerformInternal1
 414 //purpose  :
 415 //=======================================================================
 416 void BOPAlgo_BOP::PerformInternal1(const BOPAlgo_PaveFiller& theFiller,
 417                                    const Message_ProgressRange& theRange)
 418 {
 419   myPaveFiller=(BOPAlgo_PaveFiller*)&theFiller;
 420   myDS=myPaveFiller->PDS();
 421   myContext=myPaveFiller->Context();
 422   myFuzzyValue = myPaveFiller->FuzzyValue();
 423   myNonDestructive = myPaveFiller->NonDestructive();
 424   //
 425   // 1. CheckData
 426   CheckData();
 427   if (HasErrors()) {
 428     return;
 429   }
 430   //
 431   // 2. Prepare
 432   Prepare();
 433   if (HasErrors()) {
 434     return;
 435   }
 436   //
 437   if (GetReport()->HasAlert (STANDARD_TYPE(BOPAlgo_AlertEmptyShape)))
 438   {
 439     Standard_Boolean bDone = TreatEmptyShape();
 440     if (bDone) {
 441       PrepareHistory (theRange);
 442       return;
 443     }
 444   }
 445   Message_ProgressScope aPS(theRange, "Building the result of Boolean operation", 100);
 446   //
 447   BOPAlgo_PISteps aSteps (PIOperation_Last);
 448   analyzeProgress (100, aSteps);
 449
 450   // 3. Fill Images
 451   // 3.1 Vertices
 452   FillImagesVertices(aPS.Next(aSteps.GetStep(PIOperation_TreatVertices)));
 453   if (HasErrors()) {
 454     return;
 455   }
 456   //
 457   BuildResult(TopAbs_VERTEX);
 458   if (HasErrors()) {
 459     return;
 460   }
 461   // 3.2 Edges
 462   FillImagesEdges(aPS.Next(aSteps.GetStep(PIOperation_TreatEdges)));
 463   if (HasErrors()) {
 464     return;
 465   }
 466   //
 467   BuildResult(TopAbs_EDGE);
 468   if (HasErrors()) {
 469     return;
 470   }
 471   //
 472   // 3.3 Wires
 473   FillImagesContainers(TopAbs_WIRE, aPS.Next(aSteps.GetStep(PIOperation_TreatWires)));
 474   if (HasErrors()) {
 475     return;
 476   }
 477   //
 478   BuildResult(TopAbs_WIRE);
 479   if (HasErrors()) {
 480     return;
 481   }
 482   //
 483   // 3.4 Faces
 484   FillImagesFaces(aPS.Next(aSteps.GetStep(PIOperation_TreatFaces)));
 485   if (HasErrors()) {
 486     return;
 487   }
 488
 489   BuildResult(TopAbs_FACE);
 490   if (HasErrors()) {
 491     return;
 492   }
 493   //
 494   // 3.5 Shells
 495   FillImagesContainers(TopAbs_SHELL, aPS.Next(aSteps.GetStep(PIOperation_TreatShells)));
 496   if (HasErrors()) {
 497     return;
 498   }
 499   //
 500   BuildResult(TopAbs_SHELL);
 501   if (HasErrors()) {
 502     return;
 503   }
 504   //
 505   // 3.6 Solids
 506   FillImagesSolids(aPS.Next(aSteps.GetStep(PIOperation_TreatSolids)));
 507   if (HasErrors()) {
 508     return;
 509   }
 510   //
 511   BuildResult(TopAbs_SOLID);
 512   if (HasErrors()) {
 513     return;
 514   }
 515   //
 516   // 3.7 CompSolids
 517   FillImagesContainers(TopAbs_COMPSOLID, aPS.Next(aSteps.GetStep(PIOperation_TreatCompsolids)));
 518   if (HasErrors()) {
 519     return;
 520   }
 521   //
 522   BuildResult(TopAbs_COMPSOLID);
 523   if (HasErrors()) {
 524     return;
 525   }
 526   //
 527   // 3.8 Compounds
 528   FillImagesCompounds(aPS.Next(aSteps.GetStep(PIOperation_TreatCompounds)));
 529   if (HasErrors()) {
 530     return;
 531   }
 532   //
 533   BuildResult(TopAbs_COMPOUND);
 534   if (HasErrors()) {
 535     return;
 536   }
 537   //
 538   // 4.BuildShape;
 539   BuildShape(aPS.Next(aSteps.GetStep(PIOperation_BuildShape)));
 540   if (HasErrors()) {
 541     return;
 542   }
 543   //
 544   // 5.History
 545   PrepareHistory(aPS.Next(aSteps.GetStep(PIOperation_FillHistory)));
 546   if (HasErrors()) {
 547     return;
 548   }
 549   //
 550   // 6 Post-treatment
 551   PostTreat(aPS.Next(aSteps.GetStep(PIOperation_PostTreat)));
 552 }
 553 //=======================================================================
 554 //function : BuildRC
 555 //purpose  :
 556 //=======================================================================
 557 void BOPAlgo_BOP::BuildRC(const Message_ProgressRange& theRange)
 558 {
 559   Message_ProgressScope aPS(theRange, NULL, 1);
 560
 561   TopAbs_ShapeEnum aType;
 562   TopoDS_Compound aC;
 563   BRep_Builder aBB;
 564   //
 565   aBB.MakeCompound(aC);
 566   //
 567   // A. Fuse
 568   if (myOperation == BOPAlgo_FUSE) {
 569     TopTools_MapOfShape aMFence;
 570     aType = TypeToExplore(myDims[0]);
 571     TopExp_Explorer aExp(myShape, aType);
 572     for (; aExp.More(); aExp.Next()) {
 573       const TopoDS_Shape& aS = aExp.Current();
 574       if (aMFence.Add(aS)) {
 575         aBB.Add(aC, aS);
 576       }
 577     }
 578     myRC = aC;
 579     return;
 580   }
 581   //
 582   if (UserBreak(aPS))
 583   {
 584     return;
 585   }
 586   // B. Common, Cut, Cut21
 587   //
 588   Standard_Integer i, j, aNb, iDim;
 589   Standard_Boolean bCheckEdges, bContains, bCut21, bCommon;
 590   TopTools_ListIteratorOfListOfShape aItLS;
 591   //
 592   // prepare the building elements of arguments to get its splits
 593   TopTools_IndexedMapOfShape aMArgs, aMTools;
 594   for (i = 0; i < 2; ++i) {
 595     const TopTools_ListOfShape& aLS = !i ? myArguments : myTools;
 596     TopTools_IndexedMapOfShape& aMS = !i ? aMArgs : aMTools;
 597     aItLS.Initialize(aLS);
 598     for (; aItLS.More(); aItLS.Next()) {
 599       const TopoDS_Shape& aS = aItLS.Value();
 600       TopTools_ListOfShape aList;
 601       BOPTools_AlgoTools::TreatCompound (aS, aList);
 602       for (TopTools_ListOfShape::Iterator itList (aList); itList.More(); itList.Next())
 603       {
 604         const TopoDS_Shape& aSS = itList.Value();
 605         iDim = BOPTools_AlgoTools::Dimension (aSS);
 606         if (iDim < 0)
 607           continue;
 608         aType = TypeToExplore (iDim);
 609         TopExp::MapShapes (aSS, aType, aMS);
 610       }
 611     }
 612   }
 613   //
 614   if (UserBreak(aPS))
 615   {
 616     return;
 617   }
 618   //
 619   bCheckEdges = Standard_False;
 620   //
 621   // get splits of building elements
 622   TopTools_IndexedMapOfShape aMArgsIm, aMToolsIm;
 623   BOPTools_IndexedDataMapOfSetShape aMSetArgs, aMSetTools;
 624
 625   for (i = 0; i < 2; ++i) {
 626     const TopTools_IndexedMapOfShape& aMS = !i ? aMArgs : aMTools;
 627     TopTools_IndexedMapOfShape& aMSIm = !i ? aMArgsIm : aMToolsIm;
 628     BOPTools_IndexedDataMapOfSetShape& aMSet = !i ? aMSetArgs : aMSetTools;
 629     //
 630     aNb = aMS.Extent();
 631     for (j = 1; j <= aNb; ++j) {
 632       const TopoDS_Shape& aS = aMS(j);
 633       aType = aS.ShapeType();
 634       if (aType == TopAbs_EDGE) {
 635         const TopoDS_Edge& aE = *(TopoDS_Edge*)&aS;
 636         bCheckEdges = Standard_True;
 637         if (BRep_Tool::Degenerated(aE)) {
 638           continue;
 639         }
 640       }
 641       //
 642       if (myImages.IsBound(aS)) {
 643         const TopTools_ListOfShape& aLSIm = myImages.Find(aS);
 644         aItLS.Initialize(aLSIm);
 645         for (; aItLS.More(); aItLS.Next()) {
 646           const TopoDS_Shape& aSIm = aItLS.Value();
 647           aMSIm.Add(aSIm);
 648         }
 649       }
 650       else {
 651         aMSIm.Add(aS);
 652         if (aS.ShapeType() == TopAbs_SOLID) {
 653           BOPTools_Set aST;
 654           aST.Add(aS, TopAbs_FACE);
 655           if (!aMSet.Contains(aST)) {
 656             aMSet.Add(aST, aS);
 657           }
 658         }
 659       }
 660     }
 661   }
 662   //
 663   // compare the maps and make the result
 664   //
 665   Standard_Integer iDimMin, iDimMax;
 666   //
 667   iDimMin = Min(myDims[0], myDims[1]);
 668   bCommon = (myOperation == BOPAlgo_COMMON);
 669   bCut21  = (myOperation == BOPAlgo_CUT21);
 670   //
 671   const TopTools_IndexedMapOfShape& aMIt = bCut21 ? aMToolsIm : aMArgsIm;
 672   const TopTools_IndexedMapOfShape& aMCheck = bCut21 ? aMArgsIm : aMToolsIm;
 673   const BOPTools_IndexedDataMapOfSetShape& aMSetCheck = bCut21 ? aMSetArgs : aMSetTools;
 674   //
 675   TopTools_IndexedMapOfShape aMCheckExp, aMItExp;
 676   //
 677   if (bCommon) {
 678     aNb = aMIt.Extent();
 679     for (i = 1; i <= aNb; ++i) {
 680       const TopoDS_Shape& aS = aMIt(i);
 681       iDimMax = BOPTools_AlgoTools::Dimension(aS);
 682       for (iDim = iDimMin; iDim < iDimMax; ++iDim) {
 683         aType = TypeToExplore(iDim);
 684         TopExp::MapShapes(aS, aType, aMItExp);
 685       }
 686       aMItExp.Add(aS);
 687     }
 688   }
 689   else {
 690     aMItExp = aMIt;
 691   }
 692   //
 693   aNb = aMCheck.Extent();
 694   for (i = 1; i <= aNb; ++i) {
 695     const TopoDS_Shape& aS = aMCheck(i);
 696     iDimMax = BOPTools_AlgoTools::Dimension(aS);
 697     for (iDim = iDimMin; iDim < iDimMax; ++iDim) {
 698       aType = TypeToExplore(iDim);
 699       TopExp::MapShapes(aS, aType, aMCheckExp);
 700     }
 701     aMCheckExp.Add(aS);
 702   }
 703   //
 704   aNb = aMItExp.Extent();
 705   for (i = 1; i <= aNb; ++i) {
 706     const TopoDS_Shape& aS = aMItExp(i);
 707     //
 708     bContains = aMCheckExp.Contains(aS);
 709     if (!bContains && aS.ShapeType() == TopAbs_SOLID) {
 710       BOPTools_Set aST;
 711       aST.Add(aS, TopAbs_FACE);
 712       bContains = aMSetCheck.Contains(aST);
 713     }
 714     //
 715     if (bCommon) {
 716       if (bContains) {
 717         aBB.Add(aC, aS);
 718       }
 719     }
 720     else {
 721       if (!bContains) {
 722         aBB.Add(aC, aS);
 723       }
 724     }
 725   }
 726   //
 727   // filter result for COMMON operation
 728   if (bCommon) {
 729     TopTools_MapOfShape aMFence;
 730     TopExp_Explorer aExp;
 731     TopoDS_Compound aCx;
 732     aBB.MakeCompound(aCx);
 733     //
 734     for (iDim = 3; iDim >= iDimMin; --iDim) {
 735       aType = TypeToExplore(iDim);
 736       aExp.Init(aC, aType);
 737       for (; aExp.More(); aExp.Next()) {
 738         const TopoDS_Shape& aS = aExp.Current();
 739         if (aMFence.Add(aS)) {
 740           aBB.Add(aCx, aS);
 741           TopExp::MapShapes(aS, aMFence);
 742         }
 743       }
 744     }
 745     aC = aCx;
 746   }
 747   //
 748   if (!bCheckEdges) {
 749     myRC = aC;
 750     return;
 751   }
 752   //
 753   if (UserBreak(aPS))
 754   {
 755     return;
 756   }
 757   // The squats around degenerated edges
 758   Standard_Integer nVD;
 759   TopTools_IndexedMapOfShape aMVC;
 760   //
 761   // 1. Vertices of aC
 762   TopExp::MapShapes(aC, TopAbs_VERTEX, aMVC);
 763   //
 764   // 2. DE candidates
 765   aNb = myDS->NbSourceShapes();
 766   for (i = 0; i < aNb; ++i) {
 767     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
 768     aType = aSI.ShapeType();
 769     if (aType != TopAbs_EDGE) {
 770       continue;
 771     }
 772     //
 773     const TopoDS_Edge& aE = *((TopoDS_Edge*)&aSI.Shape());
 774     if (!BRep_Tool::Degenerated(aE)) {
 775       continue;
 776     }
 777     //
 778     nVD = aSI.SubShapes().First();
 779     const TopoDS_Shape& aVD = myDS->Shape(nVD);
 780     //
 781     if (!aMVC.Contains(aVD)) {
 782       continue;
 783     }
 784     //
 785     if (myDS->IsNewShape(nVD)) {
 786       continue;
 787     }
 788     //
 789     if (myDS->HasInterf(nVD)) {
 790       continue;
 791     }
 792     //
 793     aBB.Add(aC, aE);
 794   }
 795   //
 796   myRC=aC;
 797 }
 798 //=======================================================================
 799 //function : BuildShape
 800 //purpose  :
 801 //=======================================================================
 802 void BOPAlgo_BOP::BuildShape(const Message_ProgressRange& theRange)
 803 {
 804   Message_ProgressScope aPS(theRange, NULL, 10.);
 805
 806   if (myDims[0] == 3 && myDims[1] == 3)
 807   {
 808     // For the Boolean operation on solids we need to check first
 809     // if we are dealing with closed solids, because for open solids
 810     // we cannot expect the BuilderSolid algorithm to produce good
 811     // splits for them and have to try the alternative approach for
 812     // building the result shape.
 813     // This approach is not used by default as it will loose the
 814     // modification history for solids, because the result solid
 815     // will be built from scratch using the splits of faces.
 816     Standard_Boolean hasNotClosedSolids = CheckArgsForOpenSolid();
 817     if (hasNotClosedSolids)
 818     {
 819       Handle(Message_Report) aReport = new Message_Report();
 820       BuildBOP(myArguments, myTools, myOperation, Message_ProgressRange(), aReport);
 821       if (aReport->GetAlerts(Message_Fail).IsEmpty())
 822       {
 823         // Success. Merge the report into the main report.
 824         myReport->Merge(aReport);
 825         return;
 826       }
 827     }
 828   }
 829
 830   // Build the result using splits of arguments.
 831   BuildRC(aPS.Next(2.));
 832   //
 833   if ((myOperation == BOPAlgo_FUSE) && (myDims[0] == 3)) {
 834     BuildSolid(aPS.Next(8.));
 835     return;
 836   }
 837
 838   // Check for user break
 839   if (UserBreak(aPS))
 840   {
 841     return;
 842   }
 843   //
 844   Standard_Integer i;
 845   TopAbs_ShapeEnum aType, aT1, aT2;
 846   TopTools_ListOfShape aLSC, aLCB;
 847   TopTools_ListIteratorOfListOfShape aItLS, aItLSIm, aItLCB;
 848   TopoDS_Iterator aIt;
 849   BRep_Builder aBB;
 850   TopoDS_Shape aRC, aRCB;
 851   //
 852   TopTools_MapOfShape aMSRC;
 853   TopExp::MapShapes(myRC, aMSRC);
 854   //
 855   // collect images of containers
 856   for (i = 0; i < 2; ++i) {
 857     const TopTools_ListOfShape& aLS = !i ? myArguments : myTools;
 858     //
 859     aItLS.Initialize(aLS);
 860     for (; aItLS.More(); aItLS.Next()) {
 861       const TopoDS_Shape& aS = aItLS.Value();
 862       //
 863       CollectContainers(aS, aLSC);
 864     }
 865   }
 866   // Check for user break
 867   if (UserBreak(aPS))
 868   {
 869     return;
 870   }
 871   // make containers
 872   TopTools_ListOfShape aLCRes;
 873   TopTools_MapOfShape aMInpFence;
 874   aItLS.Initialize(aLSC);
 875   for (; aItLS.More(); aItLS.Next()) {
 876     const TopoDS_Shape& aSC = aItLS.Value();
 877     aMInpFence.Add(aSC);
 878     //
 879     BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
 880     //
 881     aIt.Initialize(aSC);
 882     for (; aIt.More(); aIt.Next()) {
 883       const TopoDS_Shape& aS = aIt.Value();
 884       if (myImages.IsBound(aS)) {
 885         const TopTools_ListOfShape& aLSIm = myImages.Find(aS);
 886         //
 887         aItLSIm.Initialize(aLSIm);
 888         for (; aItLSIm.More(); aItLSIm.Next()) {
 889           const TopoDS_Shape& aSIm = aItLSIm.Value();
 890           if (aMSRC.Contains(aSIm)) {
 891             aBB.Add(aRC, aSIm);
 892           }
 893         }
 894       }
 895       else if (aMSRC.Contains(aS)) {
 896         aBB.Add(aRC, aS);
 897       }
 898     }
 899     //
 900     aType = aSC.ShapeType();
 901     switch (aType) {
 902       case TopAbs_WIRE: {
 903         aT1 = TopAbs_VERTEX;
 904         aT2 = TopAbs_EDGE;
 905         break;
 906       }
 907       case TopAbs_SHELL: {
 908         aT1 = TopAbs_EDGE;
 909         aT2 = TopAbs_FACE;
 910         break;
 911       }
 912       default: {
 913         aT1 = TopAbs_FACE;
 914         aT2 = TopAbs_SOLID;
 915       }
 916     }
 917     //
 918     aLCB.Clear();
 919     BOPTools_AlgoTools::MakeConnexityBlocks(aRC, aT1, aT2, aLCB);
 920     if (aLCB.IsEmpty()) {
 921       continue;
 922     }
 923     //
 924     aItLCB.Initialize(aLCB);
 925     for (; aItLCB.More(); aItLCB.Next()) {
 926       BOPTools_AlgoTools::MakeContainer(aType, aRCB);
 927       //
 928       const TopoDS_Shape& aCB = aItLCB.Value();
 929       aIt.Initialize(aCB);
 930       for (; aIt.More(); aIt.Next()) {
 931         const TopoDS_Shape& aCBS = aIt.Value();
 932         aBB.Add(aRCB, aCBS);
 933       }
 934       //
 935       if (aType == TopAbs_WIRE) {
 936         // reorient wire
 937         BOPTools_AlgoTools::OrientEdgesOnWire(aRCB);
 938       }
 939       else if (aType == TopAbs_SHELL) {
 940         BOPTools_AlgoTools::OrientFacesOnShell(aRCB);
 941       }
 942       //
 943       aRCB.Orientation(aSC.Orientation());
 944       //
 945       aLCRes.Append(aRCB);
 946     }
 947   }
 948   //
 949   RemoveDuplicates(aLCRes);
 950
 951   // Check for user break
 952   if (UserBreak(aPS))
 953   {
 954     return;
 955   }
 956   //
 957   // add containers to result
 958   TopoDS_Compound aResult;
 959   aBB.MakeCompound(aResult);
 960   //
 961   aItLS.Initialize(aLCRes);
 962   for (; aItLS.More(); aItLS.Next()) {
 963     aBB.Add(aResult, aItLS.Value());
 964   }
 965
 966   // create map of containers
 967   TopTools_MapOfShape aMSResult;
 968   TopExp::MapShapes(aResult, aMSResult);
 969
 970   // get input non-container shapes
 971   TopTools_ListOfShape aLSNonCont;
 972   for (i = 0; i < 2; ++i)
 973   {
 974     const TopTools_ListOfShape& aLS = !i ? myArguments : myTools;
 975     aItLS.Initialize(aLS);
 976     for (; aItLS.More(); aItLS.Next())
 977     {
 978       const TopoDS_Shape& aS = aItLS.Value();
 979       BOPTools_AlgoTools::TreatCompound(aS, aLSNonCont, &aMInpFence);
 980     }
 981   }
 982
 983   // put non-container shapes in the result
 984   aItLS.Initialize(aLSNonCont);
 985   for (; aItLS.More(); aItLS.Next())
 986   {
 987     const TopoDS_Shape& aS = aItLS.Value();
 988     if (myImages.IsBound(aS))
 989     {
 990       const TopTools_ListOfShape& aLSIm = myImages.Find(aS);
 991       aItLSIm.Initialize(aLSIm);
 992       for (; aItLSIm.More(); aItLSIm.Next())
 993       {
 994         const TopoDS_Shape& aSIm = aItLSIm.Value();
 995         if (aMSRC.Contains(aSIm) && aMSResult.Add(aSIm))
 996           aBB.Add(aResult, aSIm);
 997       }
 998     }
 999     else if (aMSRC.Contains(aS) && aMSResult.Add(aS))
1000       aBB.Add(aResult, aS);
1001   }
1002
1003   myShape = aResult;
1004 }
1005 //=======================================================================
1006 //function : BuildSolid
1007 //purpose  :
1008 //=======================================================================
1009 void BOPAlgo_BOP::BuildSolid(const Message_ProgressRange& theRange)
1010 {
1011   Message_ProgressScope aPS(theRange, NULL, 10.);
1012   // Containers
1013   TopTools_ListOfShape aLSC;
1014   //
1015   TopTools_ListIteratorOfListOfShape aItLS;
1016   TopExp_Explorer aExp;
1017   BRep_Builder aBB;
1018   //
1019   // Get solids from input arguments
1020   TopTools_MapOfShape aMSA;
1021   // Map the arguments to find shared faces
1022   TopTools_IndexedDataMapOfShapeListOfShape aMFS;
1023   for (Standard_Integer i = 0; i < 2; ++i) {
1024     const TopTools_ListOfShape& aLSA = (i) ? myArguments : myTools;
1025     aItLS.Initialize(aLSA);
1026     for (; aItLS.More(); aItLS.Next()) {
1027       const TopoDS_Shape& aSA = aItLS.Value();
1028       aExp.Init(aSA, TopAbs_SOLID);
1029       for (; aExp.More(); aExp.Next()) {
1030         const TopoDS_Shape& aSol = aExp.Current();
1031         aMSA.Add(aSol);
1032         TopExp::MapShapesAndAncestors(aSol, TopAbs_FACE, TopAbs_SOLID, aMFS);
1033       }
1034       //
1035       // get Compsolids from input arguments
1036       CollectContainers(aSA, aLSC);
1037     }
1038   }
1039   // Check for user break
1040   if (UserBreak(aPS))
1041   {
1042     return;
1043   }
1044   //
1045   // Find solids in input arguments sharing faces with other solids
1046   TopTools_MapOfShape aMTSols;
1047   Standard_Integer i, aNb = aMFS.Extent();
1048   for (i = 1; i < aNb; ++i) {
1049     const TopTools_ListOfShape& aLSols = aMFS(i);
1050     if (aLSols.Extent() > 1) {
1051       aItLS.Initialize(aLSols);
1052       for(; aItLS.More(); aItLS.Next()) {
1053         aMTSols.Add(aItLS.Value());
1054       }
1055     }
1056   }
1057   //
1058   // Possibly untouched solids - to be added to results as is
1059   TopTools_IndexedMapOfShape aMUSols;
1060   // Use map to chose the most outer faces to build result solids
1061   aMFS.Clear();
1062   //
1063   TopoDS_Iterator aIt(myRC);
1064   for (; aIt.More(); aIt.Next()) {
1065     const TopoDS_Shape& aSx = aIt.Value();
1066     if (aMSA.Contains(aSx)) {
1067       if (!aMTSols.Contains(aSx)) {
1068         aMUSols.Add(aSx);
1069         continue;
1070       }
1071     }
1072     //
1073     MapFacesToBuildSolids(aSx, aMFS);
1074   } // for (; aIt.More(); aIt.Next()) {
1075   //
1076   // Process possibly untouched solids.
1077   // Really untouched solids will be added into result as is.
1078   // Others will be processed by BuilderSolid.
1079   BOPTools_IndexedDataMapOfSetShape aDMSTS;
1080   //
1081   aNb = aMUSols.Extent();
1082   for (i = 1; i <= aNb; ++i) {
1083     const TopoDS_Shape& aSx = aMUSols(i);
1084     //
1085     aExp.Init(aSx, TopAbs_FACE);
1086     for (; aExp.More(); aExp.Next()) {
1087       if (aMFS.Contains(aExp.Current())) {
1088         break;
1089       }
1090     }
1091     //
1092     if (aExp.More()) {
1093       MapFacesToBuildSolids(aSx, aMFS);
1094     }
1095     else {
1096       BOPTools_Set aST;
1097       aST.Add(aSx, TopAbs_FACE);
1098       if (!aDMSTS.Contains(aST)) {
1099         aDMSTS.Add(aST, aSx);
1100       }
1101     }
1102   }
1103   // Check for user break
1104   if (UserBreak(aPS))
1105   {
1106     return;
1107   }
1108   //
1109   TopTools_IndexedDataMapOfShapeListOfShape aMEF;
1110   // Fill the list of faces to build the result solids
1111   TopTools_ListOfShape aSFS;
1112   aNb = aMFS.Extent();
1113   for (i = 1; i <= aNb; ++i) {
1114     const TopTools_ListOfShape& aLSx = aMFS(i);
1115     if (aLSx.Extent() == 1) {
1116       const TopoDS_Shape& aFx = aMFS.FindKey(i);
1117       TopExp::MapShapesAndAncestors(aFx, TopAbs_EDGE, TopAbs_FACE, aMEF);
1118       aSFS.Append(aFx);
1119     }
1120   }
1121   //
1122   TopoDS_Shape aRC;
1123   BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aRC);
1124   if (aSFS.Extent()) {
1125     // Build solids from set of faces
1126     BOPAlgo_BuilderSolid aBS;
1127     aBS.SetContext(myContext);
1128     aBS.SetShapes(aSFS);
1129     aBS.SetAvoidInternalShapes (Standard_True);
1130     aBS.Perform(aPS.Next(8.));
1131     if (aBS.HasErrors()) {
1132       AddError (new BOPAlgo_AlertSolidBuilderFailed); // SolidBuilder failed
1133       return;
1134     }
1135
1136     myReport->Merge(aBS.GetReport());
1137
1138     // new solids
1139     const TopTools_ListOfShape& aLSR = aBS.Areas();
1140     //
1141     // add new solids to result
1142     aItLS.Initialize(aLSR);
1143     for (; aItLS.More(); aItLS.Next()) {
1144       const TopoDS_Shape& aSR = aItLS.Value();
1145       aBB.Add(aRC, aSR);
1146     }
1147   }
1148   //
1149   // add untouched solids to result
1150   aNb = aDMSTS.Extent();
1151   for (i = 1; i <= aNb; ++i) {
1152     const TopoDS_Shape& aSx = aDMSTS(i);
1153     aBB.Add(aRC, aSx);
1154   }
1155   //
1156   if (aLSC.IsEmpty()) {
1157     // no Compsolids in arguments
1158     myShape = aRC;
1159     return;
1160   }
1161   //
1162   // build new Compsolids from new solids containing splits
1163   // of faces from arguments of type Compsolid
1164   //
1165   TopoDS_Shape aResult;
1166   BOPTools_AlgoTools::MakeContainer(TopAbs_COMPOUND, aResult);
1167   //
1168
1169   aIt.Initialize(aRC);
1170   if (!aIt.More()) {
1171     // no solids in the result
1172     myShape = aRC;
1173     return;
1174   }
1175   //
1176   const TopoDS_Shape& aSol1 = aIt.Value();
1177   aIt.Next();
1178   //
1179   // optimization for one solid in the result
1180   if (!aIt.More()) {
1181     TopoDS_Shape aCS;
1182     BOPTools_AlgoTools::MakeContainer(TopAbs_COMPSOLID, aCS);
1183     aBB.Add(aCS, aSol1);
1184     //
1185     aBB.Add(aResult, aCS);
1186     myShape = aResult;
1187     return;
1188   }
1189   //
1190   // get splits of faces of the Compsolid arguments
1191   TopTools_MapOfShape aMFCs;
1192   aItLS.Initialize(aLSC);
1193   for (; aItLS.More(); aItLS.Next()) {
1194     const TopoDS_Shape& aCs = aItLS.Value();
1195     aExp.Init(aCs, TopAbs_FACE);
1196     for (; aExp.More(); aExp.Next()) {
1197       const TopoDS_Shape& aF = aExp.Current();
1198       const TopTools_ListOfShape* pLFIm = myImages.Seek(aF);
1199       if (!pLFIm) {
1200         aMFCs.Add(aF);
1201       }
1202       else {
1203         TopTools_ListIteratorOfListOfShape aItLFIm(*pLFIm);
1204         for (; aItLFIm.More(); aItLFIm.Next()) {
1205           aMFCs.Add(aItLFIm.Value());
1206         }
1207       }
1208     }
1209   }
1210   //
1211   // Check for user break
1212   if (UserBreak(aPS))
1213   {
1214     return;
1215   }
1216   // build connexity blocks from new solids
1217   TopTools_ListOfShape aLCBS;
1218   BOPTools_AlgoTools::MakeConnexityBlocks(aRC, TopAbs_FACE, TopAbs_SOLID, aLCBS);
1219   //
1220   aItLS.Initialize(aLCBS);
1221   for (; aItLS.More(); aItLS.Next()) {
1222     const TopoDS_Shape& aCB = aItLS.Value();
1223     //
1224     // check if the Compsolid should be created
1225     aExp.Init(aCB, TopAbs_FACE);
1226     for (; aExp.More(); aExp.Next()) {
1227       if (aMFCs.Contains(aExp.Current())) {
1228         break;
1229       }
1230     }
1231     //
1232     if (!aExp.More()) {
1233       // add solids directly into result as their origins are not Compsolids
1234       for (aIt.Initialize(aCB); aIt.More(); aIt.Next()) {
1235         aBB.Add(aResult, aIt.Value());
1236       }
1237       continue;
1238     }
1239     //
1240     // make Compsolid
1241     TopoDS_Shape aCS;
1242     BOPTools_AlgoTools::MakeContainer(TopAbs_COMPSOLID, aCS);
1243     //
1244     aIt.Initialize(aCB);
1245     for (; aIt.More(); aIt.Next()) {
1246       aBB.Add(aCS, aIt.Value());
1247     }
1248     //
1249     aBB.Add(aResult, aCS);
1250   }
1251   //
1252   myShape = aResult;
1253 }
1254
1255 //=======================================================================
1256 //function : CheckArgsForOpenSolid
1257 //purpose  :
1258 //=======================================================================
1259 Standard_Boolean BOPAlgo_BOP::CheckArgsForOpenSolid()
1260 {
1261   // Analyze the report to find if BuilderSolid has generated warnings
1262   // for any of the solids and collect these solids to check if they are open.
1263   TopTools_MapOfShape aFailedSolids;
1264   {
1265     const Message_ListOfAlert& aList = myReport->GetAlerts(Message_Warning);
1266     for (Message_ListOfAlert::Iterator aIt(aList); aIt.More(); aIt.Next())
1267     {
1268       const Handle(Standard_Type)& aType = aIt.Value()->DynamicType();
1269       if (aType != STANDARD_TYPE(BOPAlgo_AlertSolidBuilderUnusedFaces))
1270         continue;
1271
1272       Handle(TopoDS_AlertWithShape) aShapeAlert = Handle(TopoDS_AlertWithShape)::DownCast(aIt.Value());
1273       if (!aShapeAlert.IsNull())
1274       {
1275         const TopoDS_Shape& aWarnShape = aShapeAlert->GetShape();
1276         if (!aWarnShape.IsNull())
1277         {
1278           TopExp_Explorer expS(aWarnShape, TopAbs_SOLID);
1279           for (; expS.More(); expS.Next())
1280             aFailedSolids.Add(expS.Current());
1281         }
1282       }
1283     }
1284   }
1285
1286   // Iterate on all solids from the arguments and check if any
1287   // of them are not closed.
1288   // At the same time, collect all internal faces of the input solids
1289   // to check if the splits of open solids did not acquire any new
1290   // internal faces.
1291
1292   const Standard_Integer aNbS = myDS->NbSourceShapes();
1293   for (Standard_Integer i = 0; i < aNbS; ++i)
1294   {
1295     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
1296     if (aSI.ShapeType() != TopAbs_SOLID)
1297       continue;
1298
1299     const TopoDS_Shape& aSolid = aSI.Shape();
1300
1301     // Check that not INTERNAL faces create closed loops
1302     TopTools_IndexedDataMapOfShapeListOfShape aMEF;
1303     // Collect all splits of internal faces
1304     TopTools_MapOfShape aMFInternal;
1305
1306     for (TopoDS_Iterator itSh(aSolid); itSh.More(); itSh.Next())
1307     {
1308       const TopoDS_Shape& aSh = itSh.Value();
1309       if (aSh.ShapeType() != TopAbs_SHELL)
1310         continue;
1311
1312       for (TopoDS_Iterator itF(aSh); itF.More(); itF.Next())
1313       {
1314         const TopoDS_Shape& aF = itF.Value();
1315         if (aF.Orientation() == TopAbs_INTERNAL)
1316         {
1317           const TopTools_ListOfShape* pLFIm = myImages.Seek(aF);
1318           if (pLFIm)
1319           {
1320             TopTools_ListOfShape::Iterator itLFIm(*pLFIm);
1321             for (; itLFIm.More(); itLFIm.Next())
1322               aMFInternal.Add(itLFIm.Value());
1323           }
1324           else
1325             aMFInternal.Add(aF);
1326         }
1327         else
1328           TopExp::MapShapesAndAncestors(aF, TopAbs_EDGE, TopAbs_FACE, aMEF);
1329       }
1330     }
1331
1332     // Analyze the Edge-Face connection map on free edges
1333     Standard_Boolean isClosed = Standard_True;
1334     const Standard_Integer aNbE = aMEF.Extent();
1335     for (Standard_Integer j = 1; j <= aNbE && isClosed; ++j)
1336     {
1337       const TopoDS_Edge& aE = TopoDS::Edge(aMEF.FindKey(j));
1338       if (BRep_Tool::Degenerated(aE))
1339         // Skip degenerated edges
1340         continue;
1341
1342       isClosed = (aMEF(j).Extent() > 1);
1343       if (!isClosed)
1344       {
1345         const TopoDS_Face& aF = TopoDS::Face(aMEF(j).First());
1346         isClosed = BRep_Tool::IsClosed(aE, aF); // Check for seam edges
1347         if (!isClosed)
1348         {
1349           // Check if the edge is not internal in the face
1350           TopExp_Explorer expE(aF, TopAbs_EDGE);
1351           for (; expE.More(); expE.Next())
1352           {
1353             if (expE.Current().IsSame(aE))
1354             {
1355               isClosed = (expE.Current().Orientation() == TopAbs_INTERNAL);
1356               break;
1357             }
1358           }
1359         }
1360       }
1361     }
1362
1363     if (isClosed)
1364       continue;
1365
1366     // Not closed solid is found
1367
1368     if (aFailedSolids.Contains(aSolid))
1369       // Warning has been generated for this solid, return positive result right away.
1370       return Standard_True;
1371
1372
1373     // Check the splits not to acquire new INTERNAL faces
1374     const TopTools_ListOfShape *pLSIm = myImages.Seek(aSolid);
1375     if (!pLSIm)
1376       continue;
1377
1378     TopTools_ListOfShape::Iterator itLSIm(*pLSIm);
1379     for (; itLSIm.More(); itLSIm.Next())
1380     {
1381       const TopoDS_Shape& aSIm = itLSIm.Value();
1382       for (TopoDS_Iterator itSh(aSIm); itSh.More(); itSh.Next())
1383       {
1384         const TopoDS_Shape& aSh = itSh.Value();
1385         if (aSh.ShapeType() != TopAbs_SHELL)
1386           continue;
1387
1388         for (TopoDS_Iterator itF(aSh); itF.More(); itF.Next())
1389         {
1390           const TopoDS_Shape& aF = itF.Value();
1391           if (aF.Orientation() == TopAbs_INTERNAL)
1392           {
1393             if (!aMFInternal.Contains(aF))
1394               // New internal face is found
1395               return Standard_True;
1396           }
1397         }
1398       }
1399     }
1400   }
1401
1402   return Standard_False;
1403 }
1404
1405 //=======================================================================
1406 //function : TypeToExplore
1407 //purpose  :
1408 //=======================================================================
1409 TopAbs_ShapeEnum TypeToExplore(const Standard_Integer theDim)
1410 {
1411   TopAbs_ShapeEnum aRet;
1412   //
1413   switch(theDim) {
1414   case 0:
1415     aRet=TopAbs_VERTEX;
1416     break;
1417   case 1:
1418     aRet=TopAbs_EDGE;
1419     break;
1420   case 2:
1421     aRet=TopAbs_FACE;
1422     break;
1423   case 3:
1424     aRet=TopAbs_SOLID;
1425     break;
1426   default:
1427     aRet=TopAbs_SHAPE;
1428     break;
1429   }
1430   return aRet;
1431 }
1432 //=======================================================================
1433 //function : CollectContainers
1434 //purpose  :
1435 //=======================================================================
1436 void CollectContainers(const TopoDS_Shape& theS,
1437                        TopTools_ListOfShape& theLSC)
1438 {
1439   TopAbs_ShapeEnum aType = theS.ShapeType();
1440   if (aType == TopAbs_WIRE ||
1441       aType == TopAbs_SHELL ||
1442       aType == TopAbs_COMPSOLID) {
1443     theLSC.Append(theS);
1444     return;
1445   }
1446   //
1447   if (aType != TopAbs_COMPOUND) {
1448     return;
1449   }
1450   //
1451   TopoDS_Iterator aIt(theS);
1452   for (; aIt.More(); aIt.Next()) {
1453     const TopoDS_Shape& aS = aIt.Value();
1454     CollectContainers(aS, theLSC);
1455   }
1456 }
1457
1458 //=======================================================================
1459 //function : RemoveDuplicates
1460 //purpose  : Filters the containers with identical contents
1461 //=======================================================================
1462 void RemoveDuplicates(TopTools_ListOfShape& theContainers)
1463 {
1464   RemoveDuplicates(theContainers, TopAbs_WIRE);
1465   RemoveDuplicates(theContainers, TopAbs_SHELL);
1466   RemoveDuplicates(theContainers, TopAbs_COMPSOLID);
1467 }
1468
1469 //=======================================================================
1470 //function : RemoveDuplicates
1471 //purpose  : Filters the containers of given type with identical contents
1472 //=======================================================================
1473 void RemoveDuplicates(TopTools_ListOfShape& theContainers,
1474                       const TopAbs_ShapeEnum theType)
1475 {
1476   // get containers of given type
1477   TopTools_ListOfShape aLC;
1478   TopTools_ListIteratorOfListOfShape aItLC(theContainers);
1479   for (; aItLC.More(); aItLC.Next()) {
1480     const TopoDS_Shape& aC = aItLC.Value();
1481     if (aC.ShapeType() == theType) {
1482       aLC.Append(aC);
1483     }
1484   }
1485   //
1486   if (aLC.IsEmpty()) {
1487     return;
1488   }
1489   //
1490   // map containers to compare its contents
1491   NCollection_IndexedDataMap<TopoDS_Shape, TopTools_MapOfShape> aContents;
1492   //
1493   aItLC.Initialize(aLC);
1494   for (; aItLC.More(); aItLC.Next()) {
1495     const TopoDS_Shape& aC = aItLC.Value();
1496     //
1497     TopTools_MapOfShape& aMC = aContents(aContents.Add(aC, TopTools_MapOfShape()));
1498     //
1499     TopoDS_Iterator aIt(aC);
1500     for (; aIt.More(); aIt.Next()) {
1501       aMC.Add(aIt.Value());
1502     }
1503   }
1504   //
1505   // compare the contents of the containers and find duplicates
1506   TopTools_MapOfShape aDuplicates;
1507   //
1508   Standard_Integer i, j, aNb = aContents.Extent();
1509   for (i = 1; i <= aNb; ++i) {
1510     const TopoDS_Shape& aCi = aContents.FindKey(i);
1511     if (aDuplicates.Contains(aCi)) {
1512       continue;
1513     }
1514     const TopTools_MapOfShape& aMi = aContents(i);
1515     Standard_Integer aNbi = aMi.Extent();
1516     //
1517     for (j = i + 1; j <= aNb; ++j) {
1518       const TopoDS_Shape& aCj = aContents.FindKey(j);
1519       if (aDuplicates.Contains(aCj)) {
1520         continue;
1521       }
1522       const TopTools_MapOfShape& aMj = aContents(j);
1523       Standard_Integer aNbj = aMj.Extent();
1524       //
1525       Standard_Integer aNbCommon = NbCommonItemsInMap(aMi, aMj);
1526       //
1527       if (aNbj == aNbCommon) {
1528         aDuplicates.Add(aCj);
1529         continue;
1530       }
1531       //
1532       if (aNbi == aNbCommon) {
1533         aDuplicates.Add(aCi);
1534         break;
1535       }
1536     }
1537   }
1538   //
1539   if (aDuplicates.IsEmpty()) {
1540     return;
1541   }
1542   //
1543   // remove duplicating containers
1544   aItLC.Initialize(theContainers);
1545   for (; aItLC.More(); ) {
1546     const TopoDS_Shape& aC = aItLC.Value();
1547     if (aDuplicates.Contains(aC)) {
1548       theContainers.Remove(aItLC);
1549       continue;
1550     }
1551     aItLC.Next();
1552   }
1553 }
1554
1555 //=======================================================================
1556 //function : NbCommonItemsInMap
1557 //purpose  : Counts the items contained in both maps
1558 //=======================================================================
1559 Standard_Integer NbCommonItemsInMap(const TopTools_MapOfShape& theM1,
1560                                     const TopTools_MapOfShape& theM2)
1561 {
1562   const TopTools_MapOfShape* aMap1 = &theM1;
1563   const TopTools_MapOfShape* aMap2 = &theM2;
1564   //
1565   if (theM2.Extent() < theM1.Extent()) {
1566     aMap1 = &theM2;
1567     aMap2 = &theM1;
1568   }
1569   //
1570   Standard_Integer iCommon = 0;
1571   for (TopTools_MapIteratorOfMapOfShape aIt(*aMap1); aIt.More(); aIt.Next()) {
1572     if (aMap2->Contains(aIt.Value())) {
1573       ++iCommon;
1574     }
1575   }
1576   return iCommon;
1577 }
1578 //=======================================================================
1579 //function : MapFacesToBuildSolids
1580 //purpose  : Stores the faces of the given solid into outgoing maps:
1581 //           <theMFS> - not internal faces with reference to solid.
1582 //=======================================================================
1583 void MapFacesToBuildSolids(const TopoDS_Shape& theSol,
1584                            TopTools_IndexedDataMapOfShapeListOfShape& theMFS)
1585 {
1586   TopExp_Explorer aExp(theSol, TopAbs_FACE);
1587   for (; aExp.More(); aExp.Next()) {
1588     const TopoDS_Shape& aF = aExp.Current();
1589     //
1590     if (aF.Orientation() == TopAbs_INTERNAL) {
1591       continue;
1592     }
1593     //
1594     TopTools_ListOfShape* pLSol = theMFS.ChangeSeek(aF);
1595     if (!pLSol) {
1596       pLSol = &theMFS(theMFS.Add(aF, TopTools_ListOfShape()));
1597       pLSol->Append(theSol);
1598     }
1599     else {
1600       const TopoDS_Shape& aF1 = theMFS.FindKey(theMFS.FindIndex(aF));
1601       if (aF1.Orientation() != aF.Orientation()) {
1602         pLSol->Append(theSol);
1603       }
1604     }
1605   }
1606 }