src/NMTAlgo/NMTAlgo_Splitter_1.cxx

   1 // Copyright (C) 2005  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   2 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   3 //
   4 // This library is free software; you can redistribute it and/or
   5 // modify it under the terms of the GNU Lesser General Public
   6 // License as published by the Free Software Foundation; either
   7 // version 2.1 of the License.
   8 //
   9 // This library is distributed in the hope that it will be useful
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 // Lesser General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Lesser General Public
  15 // License along with this library; if not, write to the Free Software
  16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  17 //
  18 // See http://www.salome-platform.org/
  19 //
  20 // File:        NMTAlgo_Splitter_1.cxx
  21 // Created:     Mon Feb  2 14:58:54 2004
  22 // Author:      Peter KURNEV
  23 //              <pkv@irinox>
  24
  25
  26 #include <NMTAlgo_Splitter.ixx>
  27
  28 #include <Precision.hxx>
  29
  30 #include <gp_Pnt.hxx>
  31
  32 #include <TopAbs_ShapeEnum.hxx>
  33
  34 #include <TopoDS.hxx>
  35 #include <TopoDS_Edge.hxx>
  36 #include <TopoDS_Face.hxx>
  37 #include <TopoDS_Shape.hxx>
  38 #include <TopoDS_Compound.hxx>
  39 #include <TopoDS_Solid.hxx>
  40 #include <TopoDS_Iterator.hxx>
  41
  42 #include <TopExp.hxx>
  43 #include <TopExp_Explorer.hxx>
  44
  45 #include <TopTools_MapOfShape.hxx>
  46 #include <TopTools_DataMapOfShapeListOfShape.hxx>
  47 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  48 #include <TopTools_ListOfShape.hxx>
  49 #include <TopTools_ListIteratorOfListOfShape.hxx>
  50 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  51 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
  52 #include <TopTools_IndexedMapOfShape.hxx>
  53 #include <TopTools_IndexedDataMapOfShapeShape.hxx>
  54
  55 #include <BRep_Tool.hxx>
  56 #include <BRepClass3d_SolidClassifier.hxx>
  57
  58 #include <NMTAlgo_Loop3d.hxx>
  59 //
  60 #include <BOPTools_Tools2D.hxx>
  61 #include <Geom_Curve.hxx>
  62 #include <TopAbs_Orientation.hxx>
  63 #include <TopTools_ListOfShape.hxx>
  64 #include <TopTools_ListIteratorOfListOfShape.hxx>
  65 #include <gp_Dir.hxx>
  66 #include <gp_Pnt.hxx>
  67 #include <BOPTools_Tools3D.hxx>
  68 #include <TopoDS.hxx>
  69 #include <BRep_Tool.hxx>
  70 #include <gp_Pln.hxx>
  71 #include <TopAbs_State.hxx>
  72
  73 //
  74 static
  75   void RefineShells(const TopoDS_Shape& ,
  76                     TopTools_ListOfShape&);
  77 static
  78   void RefineSolids(const TopoDS_Shape& ,
  79                     TopTools_ListOfShape&);
  80
  81 //modified by NIZNHY-PKV Fri Feb 25 17:19:39 2005f XX
  82 static
  83   void GetPlanes (const TopoDS_Edge& anEx,
  84                 const TopTools_IndexedDataMapOfShapeListOfShape& anEFMapx,
  85                 const TopoDS_Face& aF1,
  86                 TopAbs_State& aStPF1);
  87 //modified by NIZNHY-PKV Fri Feb 25 17:19:44 2005t XX
  88
  89 //=======================================================================
  90 //function : ShellsAndSolids
  91 //purpose  :
  92 //=======================================================================
  93  void NMTAlgo_Splitter::ShellsAndSolids()
  94 {
  95   Standard_Boolean bMakeSolids;
  96   TopAbs_ShapeEnum aType;
  97   TopTools_ListIteratorOfListOfShape aItS;
  98   TopTools_ListOfShape aLNS;
  99   //
 100   myAddedFacesMap.Clear();
 101   bMakeSolids=(myLimit==TopAbs_SHAPE || myLimit<TopAbs_SHELL);
 102   //
 103   //modified by NIZNHY-PKV Thu Feb 24 17:22:32 2005 f XX
 104   myInternalFaces.Clear(); // remove it after all modifs
 105   //modified by NIZNHY-PKV Thu Feb 24 17:22:56 2005 t XX
 106   aItS.Initialize(myListShapes);
 107   for ( ;aItS.More(); aItS.Next()) {
 108     const TopoDS_Shape& aS=aItS.Value();
 109     //
 110     if (myToolShapes.Contains(aS)) {
 111       continue;
 112     }
 113     //
 114     aType=aS.ShapeType();
 115     if (aType > TopAbs_SHELL) {
 116       continue;//face,wire,...
 117     }
 118     //
 119     aLNS.Clear();
 120     //
 121     MakeShells (aS, aLNS);
 122     //
 123     if (bMakeSolids && aType==TopAbs_SOLID) {
 124       MakeSolids(aS, aLNS);
 125     }
 126     //
 127     TopTools_ListIteratorOfListOfShape it (aLNS);
 128     for (; it.More(); it.Next()) {
 129       myBuilder.Add (myShape, it.Value());
 130     }
 131   }
 132   //
 133   // add split faces
 134   aItS.Initialize(myListShapes);
 135   for ( ;aItS.More(); aItS.Next()) {
 136     const TopoDS_Shape& aS=aItS.Value();
 137     //
 138     aType=aS.ShapeType();
 139     if (aType!=TopAbs_FACE || myMapTools.Contains(aS)) {
 140       continue;
 141     }
 142     //
 143     const TopoDS_Shape& aCSF=myImageShape.Image(aS).First();
 144     TopoDS_Iterator itS(aCSF);
 145     for (; itS.More(); itS.Next()){
 146       const TopoDS_Shape& aF=itS.Value();
 147       if (!myAddedFacesMap.Contains(aF)){
 148         myBuilder.Add (myShape, aF);
 149       }
 150     }
 151   }
 152 }
 153 //=======================================================================
 154 //function : MakeShells
 155 //purpose  : split S into compound of shells
 156 //=======================================================================
 157 void NMTAlgo_Splitter::MakeShells(const TopoDS_Shape& aS,
 158                                   TopTools_ListOfShape& aLNS)
 159 {
 160   NMTAlgo_Loop3d aShellMaker;
 161   //
 162   // get compound of split faces of aS
 163   const TopoDS_Shape& aFC=myImageShape.Image(aS).First();
 164   aShellMaker.AddConstFaces(aFC);
 165   //
 166   // add split faces inside aS
 167   if (myClosedShapes.Contains(aS)) {
 168     //
 169     // internal faces compound
 170     TopoDS_Shape aIFC=FindFacesInside(aS, Standard_True);
 171     aShellMaker.AddSectionFaces(aIFC);
 172   }
 173   //
 174   aLNS=aShellMaker.MakeShells(myAddedFacesMap);
 175   //
 176   RefineShells(aS, aLNS);
 177   //
 178   // Add faces added to new shell to myAddedFacesMap:
 179   // avoid rebuilding twice common part of 2 solids.
 180
 181   TopTools_ListIteratorOfListOfShape itS(aLNS);
 182   TopExp_Explorer expF;
 183   for (; itS.More(); itS.Next()) {
 184     const TopoDS_Shape& aSh=itS.Value();
 185     expF.Init (aSh, TopAbs_FACE);
 186     for (; expF.More(); expF.Next()){
 187       myAddedFacesMap.Add (expF.Current());
 188     }
 189   }
 190
 191 }
 192 //=======================================================================
 193 //function : MakeSolids
 194 //purpose  : make solids out of Shells
 195 //=======================================================================
 196 void NMTAlgo_Splitter::MakeSolids(const TopoDS_Shape&   theSolid,
 197                                   TopTools_ListOfShape& theShellList)
 198 {
 199   // for a solid wrapping other shells or solids without intersection,
 200   // it is necessary to find shells making holes in it
 201   Standard_Boolean isWrapping;
 202   TopTools_ListOfShape aNewSolids; // result
 203   TopTools_ListOfShape aHoleShells;
 204   TopoDS_Shape anInfinitePointShape;
 205   TopTools_DataMapOfShapeShape aInOutMap;
 206   TopTools_ListIteratorOfListOfShape aShellIt, aSolisIt;
 207   //
 208   isWrapping = myWrappingSolid.Contains(theSolid);
 209   if (!isWrapping && !theShellList.IsEmpty())  {
 210     // check if theSolid initially has internal shells
 211     TopoDS_Iterator aShellExp (theSolid);
 212     aShellExp.Next();
 213     isWrapping = aShellExp.More();
 214   }
 215   //
 216   aShellIt.Initialize(theShellList);
 217   for ( ; aShellIt.More(); aShellIt.Next()) {
 218     const TopoDS_Shape & aShell = aShellIt.Value();
 219     // check if a shell is a hole of theSolid
 220     if (isWrapping && IsInside(anInfinitePointShape, aShell)){
 221       aHoleShells.Append(aShell);
 222     }
 223     else {
 224       // make a solid from a shell
 225       TopoDS_Solid Solid;
 226       myBuilder.MakeSolid( Solid );
 227       myBuilder.Add (Solid, aShell);
 228
 229       aNewSolids.Append (Solid);
 230     }
 231   }
 232   //
 233   // find outer a shell most close to each hole shell
 234   aShellIt.Initialize(aHoleShells);
 235   for (; aShellIt.More(); aShellIt.Next()){
 236     const TopoDS_Shape & aHole = aShellIt.Value();
 237     //
 238     aSolisIt.Initialize(aNewSolids);
 239     for ( ; aSolisIt.More(); aSolisIt.Next())    {
 240       const TopoDS_Shape & aSolid = aSolisIt.Value();
 241       //
 242       if (! IsInside(aHole, aSolid)){
 243         continue;
 244       }
 245       //
 246       if ( aInOutMap.IsBound (aHole)){
 247         const TopoDS_Shape & aSolid2 = aInOutMap( aHole );
 248         if ( IsInside( aSolid, aSolid2 )) {
 249           aInOutMap.UnBind( aHole );
 250           aInOutMap.Bind ( aHole, aSolid );
 251         }
 252       }
 253       else{
 254         aInOutMap.Bind (aHole, aSolid);
 255       }
 256     }
 257     //
 258     // add aHole to a solid
 259     if (aInOutMap.IsBound( aHole )){
 260       TopoDS_Shape & aSolid=aInOutMap(aHole);
 261       myBuilder.Add (aSolid, aHole);
 262     }
 263   }
 264   //
 265   theShellList.Clear();
 266   //
 267   RefineSolids(theSolid, aNewSolids);
 268   //
 269   theShellList.Append(aNewSolids);
 270 }
 271
 272 //=======================================================================
 273 //function : FindFacesInside
 274 //purpose  : return compound of faces  of other shapes that are
 275 //           inside <theShape>.
 276 //           <theShape> is an object shape.
 277 //           <CheckClosed> makes avoid faces that do not form a
 278 //           closed shell
 279 //           <All> makes return already added faces
 280 //=======================================================================
 281   TopoDS_Shape NMTAlgo_Splitter::FindFacesInside(const TopoDS_Shape& theShape,
 282                                                 const Standard_Boolean CheckClosed,
 283                                                 const Standard_Boolean All)
 284 {
 285   TopExp_Explorer expl;
 286   TopAbs_State aState;
 287   //
 288   // ================================================
 289   // check if internal faces have been already found
 290   // ================================================
 291   if (myInternalFaces.IsBound(theShape)) {
 292     TopoDS_Shape aIntFComp = myInternalFaces.Find (theShape);
 293     TopoDS_Shape aIntRemFComp = myIntNotClFaces.Find (theShape);
 294
 295     expl.Init( aIntRemFComp, TopAbs_FACE);
 296     if (CheckClosed || !expl.More()){
 297       return aIntFComp;
 298     }
 299     //
 300     TopoDS_Compound C;
 301     myBuilder.MakeCompound( C );
 302     // add removed faces
 303     for (; expl.More(); expl.Next()){
 304       myBuilder.Add( C, expl.Current() );
 305     }
 306     // add good internal faces
 307     expl.Init( aIntFComp, TopAbs_FACE);
 308     for (; expl.More(); expl.Next()) {
 309       myBuilder.Add( C, expl.Current() );
 310     }
 311     //
 312     return C;
 313   }
 314
 315   // ===================================
 316   // get data for internal faces search
 317   // ===================================
 318   //
 319   // compound of split faces of theShape
 320   const TopoDS_Shape& CSF = myImageShape.Image(theShape).First();
 321   //
 322   TopTools_MapOfShape MSE, MFP;
 323   TopTools_DataMapOfShapeListOfShape DMSEFP;
 324   TopTools_MapIteratorOfMapOfShape itm;
 325   TopTools_ListOfShape EmptyL;
 326   TopTools_ListIteratorOfListOfShape itl;
 327
 328   // MSE filling: map of new section edges of CSF
 329   expl.Init(CSF, TopAbs_EDGE);
 330   for (; expl.More(); expl.Next()) {
 331     const TopoDS_Shape& aE = expl.Current() ;
 332     MSE.Add(aE);
 333   }
 334   //
 335   // DMEF: map edge of CSF - faces of CSF
 336   TopTools_IndexedDataMapOfShapeListOfShape DMEF;
 337   TopExp::MapShapesAndAncestors(CSF, TopAbs_EDGE, TopAbs_FACE, DMEF);
 338   //
 339   // Fill
 340   // 1.  MFP - a map of faces to process: map of resulting faces except
 341   // those of theShape; we`ll add to C those of them which are inside CSF
 342   // 2.  DMSEFP - edge of MSE => faces of MFP
 343   //
 344   itl.Initialize(myListShapes);
 345   for (;itl.More(); itl.Next()) {
 346     const TopoDS_Shape& aShape = itl.Value();
 347     //
 348     if ( theShape.IsSame(aShape)) {
 349       continue;
 350     }
 351     // fill maps
 352     // iterate on split faces of aShape
 353     const TopoDS_Shape& CSF1 = myImageShape.Image(aShape).First();
 354     TopoDS_Iterator itF (CSF1);
 355     for ( ; itF.More(); itF.Next()) {
 356       const TopoDS_Shape& aF1 = itF.Value();
 357       MFP.Add(aF1);
 358       // iterate on edges of split faces of aShape,
 359       // add to DMSEFP edges that are new
 360       expl.Init(aF1, TopAbs_EDGE);
 361       for (; expl.More(); expl.Next()) {
 362         TopoDS_Shape aE1 = expl.Current();
 363         if ( MSE.Contains(aE1)) {// section edge
 364           if (!DMSEFP.IsBound(aE1)) {
 365             DMSEFP.Bind(aE1, EmptyL);
 366           }
 367           DMSEFP(aE1).Append(aF1);
 368         }
 369       }
 370     }
 371   }//for (;itl.More(); itl.Next())
 372   //
 373   // add tool faces... (is absent)
 374   //
 375   // ===========================
 376   // find faces inside theShape
 377   // ===========================
 378   Standard_Boolean sameDom1, sameDom2;
 379   Standard_Boolean skipAlreadyAdded = Standard_False;
 380   Standard_Boolean GoodOri, inside;
 381   Standard_Real dot;
 382   TopTools_ListOfShape KeepFaces;
 383   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
 384
 385   // iterate on section edges, check faces of other shapes
 386   // sharing section edges and put internal faces to KeepFaces
 387   Mapit.Initialize(DMSEFP);
 388   for (; Mapit.More() ; Mapit.Next()) {
 389     // a new edge of theShape
 390     const TopoDS_Edge& E = TopoDS::Edge (Mapit.Key());
 391     //
 392     //Standard_Boolean isSectionE=IsSectionEdge(E);//(OrigE);
 393     //
 394     // split faces of other shapes sharing E
 395     TopTools_ListOfShape& LSF = DMSEFP.ChangeFind(E);
 396     //
 397     itl.Initialize( LSF );
 398     while (itl.More()) {
 399       // a split faces of other shape
 400       TopoDS_Face aFace1 = TopoDS::Face(itl.Value());
 401       // remove aFace1 form DMSEFP and MFP
 402       LSF.Remove( itl ); // == itl.Next();
 403       if (!MFP.Remove(aFace1))
 404         continue; // was not is MFP (i.e already checked)
 405       //
 406       // check if aFace1 was already added to 2 shells
 407       if (!All &&
 408           myAddedFacesMap.Contains(aFace1) &&
 409           myAddedFacesMap.Contains(aFace1.Reversed())) {
 410         skipAlreadyAdded = Standard_True;
 411       }
 412       //
 413       TopoDS_Shape anOrigFace = aFace1;
 414       if (myImagesFaces.IsImage(aFace1)){
 415         anOrigFace = myImagesFaces.Root(aFace1);
 416       }
 417       //
 418       // <- A was here
 419       //
 420       // check that anOrigFace is not same domain with CSF faces it intersects
 421       //
 422       const TopTools_ListOfShape& FL = DMEF.FindFromKey(E); //faces of CSF sharing E
 423       //
 424       const TopoDS_Shape& origF1 = myImagesFaces.IsImage(FL.First()) ?
 425         myImagesFaces.Root(FL.First()) : FL.First();
 426       //
 427       const TopoDS_Shape& origF2 = myImagesFaces.IsImage(FL.Last()) ?
 428         myImagesFaces.Root(FL.Last()) : FL.Last();
 429       //
 430       sameDom1 = anOrigFace.IsSame( origF1 );
 431       sameDom2 = anOrigFace.IsSame( origF2 );
 432       //
 433       if (!(sameDom1 || sameDom2) && HasSameDomainF( TopoDS::Face(anOrigFace) )) {
 434         sameDom1 = IsSameDomainF( TopoDS::Face(anOrigFace), TopoDS::Face(origF1));
 435         if (origF1 == origF2) {
 436           sameDom2 = sameDom1;
 437         }
 438       }
 439       if (sameDom1 && sameDom2){
 440         continue;
 441       }
 442       //
 443       if (sameDom1 || sameDom2) {
 444         inside = NMTAlgo_Loop3d::IsInside (E,
 445                                            TopoDS::Face(FL.First()),
 446                                            TopoDS::Face(FL.Last()),
 447                                            1, dot, GoodOri);
 448         if (inside || (dot + Precision::Angular() >= 1.0)) {
 449           continue; // E is convex between origF1 and origF2 or they are tangent
 450         }
 451       }
 452       //
 453       GetPlanes(E, DMEF, aFace1, aState);
 454       if (aState==TopAbs_IN) {
 455         KeepFaces.Append(aFace1);
 456       }
 457     } //while (itl.More()) {
 458   } //for (; Mapit.More() ; Mapit.Next() )
 459
 460   // ===================================================
 461   // add not distributed faces connected with KeepFaces
 462   // ===================================================
 463
 464   // ultimate list of internal faces
 465   TopTools_ListOfShape KeptFaces;
 466   //
 467   // add to MFP not split tool faces as well, they may be connected with
 468   // tool faces interfering with theShape
 469   /*
 470   itm.Initialize(myMapTools);
 471   for (; itm.More(); itm.Next() ) {
 472     const TopoDS_Shape& aToolFace = itm.Key();
 473     if (!myImageShape.HasImage(aToolFace)){
 474       MFP.Add (aToolFace);
 475     }
 476   }
 477   */
 478   //
 479   if (MFP.IsEmpty())
 480     KeptFaces.Append (KeepFaces);
 481   //
 482   while (!KeepFaces.IsEmpty()) {
 483     // KeepEdges : map of edges of faces kept last time
 484     TopTools_IndexedMapOfShape KeepEdges;
 485     for ( itl.Initialize(KeepFaces); itl.More(); itl.Next() ) {
 486       TopExp::MapShapes( itl.Value(), TopAbs_EDGE, KeepEdges);
 487       KeptFaces.Append( itl.Value() );
 488     }
 489     //
 490     KeepFaces.Clear();
 491     //
 492     // keep faces connected with already kept faces by KeepEdges
 493     for ( itm.Initialize(MFP); itm.More(); itm.Next() ) {
 494       const TopoDS_Shape& FP = itm.Key();
 495       for (expl.Init(FP,TopAbs_EDGE); expl.More(); expl.Next()) {
 496         const TopoDS_Shape& se = expl.Current();
 497         if (!MSE.Contains(se) && KeepEdges.Contains(se) ) {
 498           KeepFaces.Append(FP);
 499           MFP.Remove(FP);
 500           break;
 501         }
 502       }
 503     }
 504   }
 505
 506   // ===============================================================
 507   // here MFP contains faces outer of theShape and those of shapes
 508   // which do not interfere with theShape at all and between which
 509   // there may be those wrapped by theShape and whose faces may be
 510   // needed to be returned as well
 511   // ===============================================================
 512
 513   Standard_Boolean isSolid = (theShape.ShapeType() == TopAbs_SOLID);
 514   if (All || isSolid)  // All is for sub-result removal
 515   {
 516     for ( itm.Initialize( MFP ); itm.More(); itm.Next() ) {
 517       TopoDS_Shape aFace = itm.Key();
 518
 519       // find a shape aFace originates from
 520       TopoDS_Shape anOrigShape = GetOriginalShape( aFace );
 521
 522       // find out if all faces of anOrigShape are not in MFP
 523       // and by the way remove them from MFP
 524       Standard_Boolean isAllOut = Standard_True;
 525       TopoDS_Shape aSplitFaces = anOrigShape;
 526       if (myImageShape.HasImage(anOrigShape))
 527         aSplitFaces = myImageShape.Image(anOrigShape).First();
 528
 529       TopTools_ListOfShape aSplitFaceL;
 530       for (expl.Init( aSplitFaces, TopAbs_FACE ); expl.More(); expl.Next())
 531       {
 532         const TopoDS_Shape & aSpFace = expl.Current();
 533         // a tool face which become object has image but the whole tool shape has not
 534         if (myImageShape.HasImage( aSpFace ))
 535         {
 536           TopExp_Explorer exF (myImageShape.Image( aSpFace ).First(), TopAbs_FACE );
 537           for ( ; exF.More(); exF.Next() )
 538           {
 539             aSplitFaceL.Append( exF.Current() );
 540             if ( ! MFP.Remove( exF.Current() ))
 541               isAllOut = Standard_False;
 542           }
 543         }
 544         else
 545         {
 546           aSplitFaceL.Append( aSpFace );
 547           if ( ! MFP.Remove( aSpFace ))
 548             isAllOut = Standard_False;
 549         }
 550       }
 551       itm.Initialize( MFP );
 552       if ( !isAllOut )
 553         continue;
 554
 555       // classify anOrigShape against theShape
 556       if (IsInside (anOrigShape, theShape)) {
 557         if (isSolid && myClosedShapes.Contains(anOrigShape)) {
 558           // to make a special care at solid reconstruction
 559           myWrappingSolid.Add ( theShape );
 560         }
 561         // keep faces of an internal shape anOrigShape
 562         KeptFaces.Append( aSplitFaceL );
 563       }
 564     }
 565   }
 566
 567   // ====================================================
 568   // check if kept faces form a shell without free edges
 569   // ====================================================
 570
 571   DMEF.Clear();  // edge - kept faces
 572   MFP.Clear(); // reuse it for wrong faces
 573   if (CheckClosed) {
 574     for (itl.Initialize(KeptFaces); itl.More(); itl.Next() )
 575       TopExp::MapShapesAndAncestors(itl.Value(), TopAbs_EDGE, TopAbs_FACE, DMEF);
 576
 577     Standard_Integer i, nb = DMEF.Extent();
 578     Standard_Boolean isClosed = Standard_False;
 579     while (!isClosed) {
 580       isClosed = Standard_True;
 581       for (i=1;  isClosed && i<=nb;  ++i) {
 582         const TopoDS_Shape& E = DMEF.FindKey( i );
 583         if (! BRep_Tool::Degenerated( TopoDS::Edge( E )) &&
 584             ! MSE.Contains( E ))
 585           isClosed = ( DMEF(i).Extent() != 1 );
 586       }
 587       if (!isClosed) {
 588         const TopoDS_Shape& F = DMEF.FindFromIndex( i-1 ).First(); // bad face
 589         MFP.Add( F );
 590         // remove bad face from DMEF
 591         for (expl.Init( F, TopAbs_EDGE); expl.More(); expl.Next()) {
 592           const TopoDS_Shape& E = expl.Current();
 593           TopTools_ListOfShape& FL = DMEF.ChangeFromKey( E );
 594           for (itl.Initialize( FL ); itl.More(); itl.Next() ) {
 595             if ( F.IsSame( itl.Value() )) {
 596               FL.Remove( itl );
 597               break;
 598             }
 599           }
 600         }
 601       }
 602     }
 603   }
 604
 605   // ==============
 606   // make a result
 607   // ==============
 608
 609   TopoDS_Compound C;
 610   // compound of removed internal faces
 611   TopoDS_Compound CNotCl;
 612
 613   myBuilder.MakeCompound(C);
 614   myBuilder.MakeCompound(CNotCl);
 615
 616   // add to compounds
 617   itl.Initialize(KeptFaces);
 618   for (; itl.More(); itl.Next() ) {
 619     TopoDS_Shape & aIntFace = itl.Value();
 620     //
 621     if (!All &&
 622         myAddedFacesMap.Contains(aIntFace) &&
 623         myAddedFacesMap.Contains(aIntFace.Reversed())) {
 624       continue;
 625     }
 626     //
 627     if (! MFP.Contains( aIntFace )){
 628       myBuilder.Add(C, aIntFace);
 629     }
 630     else{
 631       myBuilder.Add(CNotCl, aIntFace);
 632     }
 633   }
 634   //
 635   if (!skipAlreadyAdded && CheckClosed) {
 636     myInternalFaces.Bind(theShape, C);
 637     myIntNotClFaces.Bind(theShape, CNotCl);
 638   }
 639   //
 640   //
 641   if (!myMapSIFC.IsBound(theShape)) {
 642     TopoDS_Compound aCIF;
 643     myBuilder.MakeCompound(aCIF);
 644     //
 645     itl.Initialize(KeptFaces);
 646     for (; itl.More(); itl.Next() ) {
 647       TopoDS_Shape & aIntFace = itl.Value();
 648       if (! MFP.Contains(aIntFace )){
 649         myBuilder.Add(aCIF, aIntFace);
 650       }
 651     }
 652     myMapSIFC.Bind(theShape, aCIF);
 653   }
 654   //
 655   return C;
 656 }
 657 //=======================================================================
 658 //function : IsInside
 659 //purpose  : Return True if the first vertex of S1 inside S2.
 660 //           If S1.IsNull(), check infinite point against S2.
 661 //=======================================================================
 662 Standard_Boolean NMTAlgo_Splitter::IsInside (const TopoDS_Shape& theS1,
 663                                              const TopoDS_Shape& theS2)
 664 {
 665   BRepClass3d_SolidClassifier aClassifier( theS2 );
 666   //
 667   TopExp_Explorer expl(theS1, TopAbs_VERTEX);
 668   //
 669   if (!expl.More()){
 670     aClassifier.PerformInfinitePoint( ::RealSmall());
 671   }
 672   else  {
 673     const TopoDS_Vertex & aVertex = TopoDS::Vertex( expl.Current() );
 674     aClassifier.Perform (BRep_Tool::Pnt( aVertex ),
 675                          BRep_Tool::Tolerance( aVertex ));
 676   }
 677   //
 678   return ( aClassifier.State() == TopAbs_IN );
 679 }
 680 //=======================================================================
 681 //function : GetOriginalShape
 682 //purpose  : Return the  shape  aShape  originates from. aShape
 683 //           should be a face or more complex result shape
 684 //=======================================================================
 685 TopoDS_Shape NMTAlgo_Splitter::GetOriginalShape(const TopoDS_Shape& theShape) const
 686 {
 687   TopoDS_Shape anOrigShape;
 688
 689   TopExp_Explorer expl( theShape, TopAbs_FACE);
 690   if (expl.More()) {
 691     TopoDS_Shape aFace = expl.Current();
 692     if (myImagesFaces.IsImage( aFace ))
 693       aFace = myImagesFaces.Root( aFace );
 694     anOrigShape = myFaceShapeMap.Find( aFace );
 695   }
 696   return anOrigShape;
 697 }
 698 //=======================================================================
 699 //function :RefineShells
 700 //purpose  :
 701 //=======================================================================
 702 void RefineShells(const TopoDS_Shape& aS,
 703                   TopTools_ListOfShape& aLNS)
 704 {
 705   Standard_Boolean bFound;
 706   Standard_Integer iS, jS, aNbSOrs, aNbSIms, aNbFOrs, aNbFIms, kFOrs, aNb;
 707   TopTools_ListIteratorOfListOfShape aIt;
 708   TopTools_IndexedMapOfShape aMSOrs, aMSIms, aMFOrs, aMFIms;
 709   TopTools_IndexedDataMapOfShapeShape aMImOr;
 710   TopTools_ListOfShape aLS;
 711   //
 712   TopExp::MapShapes(aS, TopAbs_SHELL, aMSOrs);
 713   aIt.Initialize(aLNS);
 714   for (;aIt.More(); aIt.Next()) {
 715     const TopoDS_Shape& aSh=aIt.Value();
 716     aMSIms.Add(aSh);
 717   }
 718   //
 719   aNbSOrs=aMSOrs.Extent();
 720   aNbSIms=aMSIms.Extent();
 721   //
 722   for (iS=1; iS<=aNbSOrs; ++iS) {
 723     const TopoDS_Shape& aSOr=aMSOrs(iS);
 724     aMFOrs.Clear();
 725     TopExp::MapShapes(aSOr, TopAbs_FACE, aMFOrs);
 726     aNbFOrs=aMFOrs.Extent();
 727     //
 728     for (jS=1; jS<=aNbSIms; ++jS) {
 729       const TopoDS_Shape& aSIm=aMSIms(jS);
 730       if (aMImOr.Contains(aSIm)) {
 731         continue;
 732       }
 733       //
 734       aMFIms.Clear();
 735       TopExp::MapShapes(aSIm, TopAbs_FACE, aMFIms);
 736       aNbFIms=aMFIms.Extent();
 737       //
 738       if (aNbFIms==aNbFOrs) {
 739         bFound=Standard_True;
 740         for (kFOrs=1; kFOrs<=aNbFOrs; ++kFOrs) {
 741           const TopoDS_Shape& aFOr=aMFOrs(kFOrs);
 742           if (!aMFIms.Contains(aFOr)) {
 743             bFound=Standard_False;
 744             break; //next aSIm
 745           }
 746         }
 747         if (bFound){
 748           aMImOr.Add(aSIm, aSOr);
 749           break; //next aSOr
 750         }
 751       } //if (aNbFIms==aNbFOrs)
 752     }
 753   }
 754   //
 755   aNb=aMImOr.Extent();
 756   aIt.Initialize(aLNS);
 757   for (;aIt.More(); aIt.Next()) {
 758     const TopoDS_Shape& aSh=aIt.Value();
 759     if (aMImOr.Contains(aSh)) {
 760       const TopoDS_Shape& aSOr=aMImOr.FindFromKey(aSh);
 761       aLS.Append(aSOr);
 762     }
 763     else {
 764       aLS.Append(aSh);
 765     }
 766   }
 767   //
 768   aLNS.Clear();
 769   aLNS.Append(aLS);
 770 }
 771
 772 //=======================================================================
 773 //function :RefineSolids
 774 //purpose  :
 775 //=======================================================================
 776 void RefineSolids(const TopoDS_Shape& aSolidOr,
 777                   TopTools_ListOfShape& aLNS)
 778 {
 779   Standard_Integer aNb, iS,  aNbSOrs, aNbSIms;
 780   TopoDS_Shape aSolidIm;
 781   TopTools_IndexedMapOfShape aMSOrs, aMSIms;
 782   //
 783   aNb=aLNS.Extent();
 784   if (aNb!=1) {
 785     return;
 786   }
 787   //
 788   aSolidIm=aLNS.First();
 789
 790   TopExp::MapShapes(aSolidOr, TopAbs_SHELL, aMSOrs);
 791   TopExp::MapShapes(aSolidIm, TopAbs_SHELL, aMSIms);
 792   aNbSOrs=aMSOrs.Extent();
 793   aNbSIms=aMSIms.Extent();
 794   if (aNbSOrs!=aNbSIms) {
 795     return;
 796   }
 797   //
 798   for (iS=1; iS<=aNbSOrs; ++iS) {
 799     const TopoDS_Shape& aSOr=aMSOrs(iS);
 800     if (!aMSIms.Contains(aSOr)) {
 801       return;
 802     }
 803   }
 804   //
 805   aLNS.Clear();
 806   aLNS.Append(aSolidOr);
 807 }
 808 //modified by NIZNHY-PKV Fri Feb 25 16:59:57 2005f XX
 809 //=======================================================================
 810 //function : GetPlanes
 811 //purpose  :
 812 //=======================================================================
 813 void GetPlanes (const TopoDS_Edge& anEx,
 814                 const TopTools_IndexedDataMapOfShapeListOfShape& anEFMapx,
 815                 const TopoDS_Face& aF1,
 816                 TopAbs_State& aStPF1)
 817
 818 {
 819   Standard_Boolean bIsAdjExists;
 820   Standard_Real aT, aT1, aT2;
 821   TopAbs_Orientation anOrEx, anOr;
 822   gp_Dir aDNFx1, aDNFx2, aDNF1;
 823   gp_Pnt aPx, aPx1, aPx2, aPF1;
 824   TopoDS_Edge aERight, aSpxSimm;
 825   TopoDS_Face aFx1, aFx2, aFF1;
 826   TopTools_ListIteratorOfListOfShape anIt;
 827   //
 828   // Point on Edge
 829   Handle(Geom_Curve)aC3D =BRep_Tool::Curve(anEx, aT1, aT2);
 830   aT=BOPTools_Tools2D::IntermediatePoint(aT1, aT2);
 831
 832   aC3D->D0(aT, aPx);
 833   //
 834   anOrEx=anEx.Orientation();
 835
 836   aSpxSimm=anEx;
 837   if (anOrEx==TopAbs_FORWARD) {
 838     aSpxSimm.Orientation(TopAbs_REVERSED);
 839   }
 840   else if (anOrEx==TopAbs_REVERSED){
 841     aSpxSimm.Orientation(TopAbs_FORWARD);
 842   }
 843   //
 844   const TopTools_ListOfShape& aLF=anEFMapx.FindFromKey(anEx);
 845   anIt.Initialize(aLF);
 846   for (; anIt.More(); anIt.Next()) {
 847     const TopoDS_Shape& aFE=anIt.Value();
 848     aFx1=TopoDS::Face(aFE);
 849     anOr=BOPTools_Tools3D::Orientation(anEx, aFx1);
 850     if (anOr==anOrEx){
 851       break;
 852     }
 853   }
 854   //
 855   BOPTools_Tools3D::GetApproxNormalToFaceOnEdge (anEx, aFx1, aT, aPx1, aDNFx1);
 856   //
 857   bIsAdjExists=BOPTools_Tools3D::GetAdjacentFace (aFx1, anEx, anEFMapx, aFx2);
 858   if (!bIsAdjExists) {
 859     BOPTools_Tools3D::GetApproxNormalToFaceOnEdge (aSpxSimm, aFx1, aT, aPx2, aDNFx2);
 860   }
 861   else {
 862     BOPTools_Tools3D::GetApproxNormalToFaceOnEdge (aSpxSimm, aFx2, aT, aPx2, aDNFx2);
 863   }
 864   //
 865   aFF1=aF1;
 866   aFF1.Orientation(TopAbs_FORWARD);
 867   BOPTools_Tools3D::OrientEdgeOnFace (anEx, aFF1, aERight);
 868   BOPTools_Tools3D::GetApproxNormalToFaceOnEdge (aERight, aFF1, aT, aPF1, aDNF1);
 869   //
 870   {
 871     Standard_Real d12, d1, anAlfa12, anAlfa1, aTwoPI;
 872
 873     aTwoPI=Standard_PI+Standard_PI;
 874
 875     gp_Vec aVx1(aPx, aPx1);
 876     gp_Dir aDBx1 (aVx1);
 877     gp_Pln aPlnToCompare (aPx, aDNFx1);
 878
 879     gp_Vec aVx2(aPx, aPx2);
 880     gp_Dir aDBx2 (aVx2);
 881
 882     anAlfa12=aDBx1.Angle(aDBx2);
 883     d12=BOPTools_Tools3D::SignDistance(aPx2, aPlnToCompare);
 884     if (d12 < 0.) {
 885       anAlfa12=aTwoPI-anAlfa12;
 886     }
 887
 888     gp_Vec aVF1(aPx, aPF1);
 889     gp_Dir aDBF1 (aVF1);
 890     anAlfa1=aDBx1.Angle(aDBF1);
 891     d1=BOPTools_Tools3D::SignDistance(aPF1, aPlnToCompare);
 892     if (d1 < 0.) {
 893       anAlfa1=aTwoPI-anAlfa1;
 894     }
 895
 896     aStPF1=TopAbs_OUT;
 897     if (anAlfa1 > anAlfa12) {
 898       aStPF1=TopAbs_IN;
 899     }
 900   }
 901 }
 902 //modified by NIZNHY-PKV Fri Feb 25 17:00:03 2005t XX
 903 /*
 904          A
 905       //
 906       TopoDS_Shape aFace2;
 907       if ( !isSectionE ) {
 908         while (itl.More()) {
 909           aFace2 = itl.Value();
 910           //
 911            TopoDS_Shape anOrigFace2 = aFace2;
 912           if (myImagesFaces.IsImage(aFace2)) {
 913             anOrigFace2 = myImagesFaces.Root(aFace2);
 914           }
 915           //
 916           if (!MFP.Contains( aFace2 )) {
 917             LSF.Remove( itl );
 918             continue;
 919           }
 920           //if (anOrigFace.IsSame( myImagesFaces.Root( aFace2 )))
 921           if (anOrigFace.IsSame(anOrigFace2)) {
 922             break;
 923           }
 924           itl.Next();
 925         }
 926         if (itl.More()) { // aFace2 found, remove it from maps
 927           LSF.Remove( itl );
 928           MFP.Remove(aFace2);
 929         }
 930         else{
 931           aFace2.Nullify();
 932         }
 933         itl.Initialize( LSF );
 934       }
 935       */