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