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