src/PARTITION/Partition_Spliter.cxx

   1 //  GEOM PARTITION : partition algorithm
   2 //
   3 //  Copyright (C) 2003  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 //  CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 //  This library is free software; you can redistribute it and/or
   7 //  modify it under the terms of the GNU Lesser General Public
   8 //  License as published by the Free Software Foundation; either
   9 //  version 2.1 of the License.
  10 //
  11 //  This library is distributed in the hope that it will be useful,
  12 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 //  Lesser General Public License for more details.
  15 //
  16 //  You should have received a copy of the GNU Lesser General Public
  17 //  License along with this library; if not, write to the Free Software
  18 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22 //
  23 //
  24 //  File   : Partition_Spliter.cxx
  25 //  Author : Benedicte MARTIN
  26 //  Module : GEOM
  27 //  $Header$
  28
  29 using namespace std;
  30 #include "Partition_Inter2d.hxx"
  31 #include "Partition_Inter3d.hxx"
  32 #include "Partition_Loop2d.hxx"
  33 #include "Partition_Loop3d.hxx"
  34 #include "Partition_Spliter.ixx"
  35
  36 #include "utilities.h"
  37
  38 #include <Precision.hxx>
  39 #include <TopAbs_Orientation.hxx>
  40 #include <TopExp.hxx>
  41 #include <TopExp_Explorer.hxx>
  42
  43 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  44 #include <TopTools_DataMapOfShapeListOfShape.hxx>
  45 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  46 #include <TopTools_IndexedMapOfShape.hxx>
  47 #include <TopTools_ListIteratorOfListOfShape.hxx>
  48 #include <TopTools_ListOfShape.hxx>
  49 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  50 #include <TopTools_SequenceOfShape.hxx>
  51
  52 #include <Geom2d_Curve.hxx>
  53 #include <Geom_Curve.hxx>
  54 #include <Geom_Surface.hxx>
  55 #include <Geom_TrimmedCurve.hxx>
  56 #include <gp_Pnt.hxx>
  57 #include <gp_Pnt2d.hxx>
  58 #include <gp_Vec.hxx>
  59
  60 #include <TopoDS.hxx>
  61 #include <TopoDS_Compound.hxx>
  62 #include <TopoDS_Edge.hxx>
  63 #include <TopoDS_Face.hxx>
  64 #include <TopoDS_Iterator.hxx>
  65 #include <TopoDS_Shell.hxx>
  66 #include <TopoDS_Solid.hxx>
  67 #include <TopoDS_Vertex.hxx>
  68 #include <TopoDS_Wire.hxx>
  69
  70 #include <BRepBndLib.hxx>
  71 #include <BRepClass3d_SolidClassifier.hxx>
  72 #include <BRepLib.hxx>
  73 #include <BRep_Tool.hxx>
  74
  75 #include <Extrema_ExtPC.hxx>
  76 #include <GeomAdaptor_Curve.hxx>
  77 #include <TopOpeBRepTool_CurveTool.hxx>
  78
  79 #ifdef DEB
  80 //# define PART_PERF
  81 #endif
  82
  83 #ifdef PART_PERF
  84 # include <OSD_Chronometer.hxx>
  85 #endif
  86
  87 //=======================================================================
  88 //function : isClosed
  89 //purpose  : check id a shape is closed, ie is a solid or a closed shell
  90 //=======================================================================
  91
  92 static Standard_Boolean isClosed(const TopoDS_Shape& theShape)
  93 {
  94   Standard_Boolean isClosed = (theShape.ShapeType() == TopAbs_SOLID);
  95
  96   if (!isClosed && theShape.ShapeType() == TopAbs_SHELL) {
  97     TopTools_IndexedDataMapOfShapeListOfShape MEF;
  98     TopExp::MapShapesAndAncestors(theShape, TopAbs_EDGE, TopAbs_FACE, MEF);
  99     for (Standard_Integer i=1;  isClosed && i<=MEF.Extent();  ++i)
 100       isClosed = ( MEF(i).Extent() != 1 );
 101   }
 102
 103   return isClosed;
 104 }
 105
 106 //=======================================================================
 107 //function : Partition_Spliter
 108 //purpose  : constructor
 109 //=======================================================================
 110
 111 Partition_Spliter::Partition_Spliter()
 112 {
 113   myAsDes = new BRepAlgo_AsDes;
 114   Clear();
 115 }
 116
 117 //=======================================================================
 118 //function : AddTool
 119 //purpose  : add cutting tool that will _NOT_ be in result
 120 //=======================================================================
 121
 122 void Partition_Spliter::AddTool(const TopoDS_Shape& S)
 123 {
 124   if (S.ShapeType() < TopAbs_SOLID) { // compound or compsolid
 125     TopoDS_Iterator it (S);
 126     for (; it.More(); it.Next())
 127     {
 128       AddTool( it.Value());
 129       myFaceShapeMap.Bind( it.Value(), S ); // to know compound by shape
 130     }
 131     return;
 132   }
 133
 134   for (TopExp_Explorer exp(S,TopAbs_FACE); exp.More(); exp.Next())
 135   {
 136     myMapTools.Add(exp.Current());
 137     myFaceShapeMap.Bind( exp.Current(), S );
 138   }
 139   if (isClosed( S ))
 140     myClosedShapes.Add( S );
 141 }
 142
 143 //=======================================================================
 144 //function : AddShape
 145 //purpose  : add object Shape to be splited
 146 //=======================================================================
 147
 148 void Partition_Spliter::AddShape(const TopoDS_Shape& S)
 149 {
 150   if (S.ShapeType() < TopAbs_SOLID) { // compound or compsolid
 151     TopoDS_Iterator it (S);
 152     for (; it.More(); it.Next())
 153     {
 154       AddShape( it.Value());
 155       myFaceShapeMap.Bind( it.Value(), S ); // to know compound by shape
 156     }
 157     return;
 158   }
 159
 160   TopExp_Explorer exp(S,TopAbs_FACE);
 161   if (!exp.More()) { // do not split edges and vertices
 162     //myBuilder.Add( myShape, S );
 163     return;
 164   }
 165
 166   Standard_Integer nbFacesBefore = myMapFaces.Extent(); // not to add twice the same S
 167   for (; exp.More(); exp.Next()) {
 168     const TopoDS_Shape & aFace = exp.Current();
 169     if ( ! myFaceShapeMap.IsBound( aFace )) // keep shape of tool face added as object
 170       myFaceShapeMap.Bind( aFace, S );
 171     if (myMapFaces.Add( aFace ))
 172       myImagesFaces.SetRoot( aFace );
 173   }
 174
 175   if (nbFacesBefore == myMapFaces.Extent())
 176     return;
 177
 178   // solids must be processed before all
 179   if (S.ShapeType() == TopAbs_SOLID)
 180     myListShapes.Prepend(S);
 181   else
 182     myListShapes.Append(S);
 183
 184   if (isClosed( S ))
 185     myClosedShapes.Add( S );
 186
 187 }
 188
 189 //=======================================================================
 190 //function : Shape
 191 //purpose  : return resulting compound
 192 //=======================================================================
 193
 194 TopoDS_Shape Partition_Spliter::Shape() const
 195 {
 196   return myShape;
 197 }
 198
 199 //=======================================================================
 200 //function : Clear
 201 //purpose  : clear fields
 202 //=======================================================================
 203
 204 void Partition_Spliter::Clear()
 205 {
 206   myDoneStep = TopAbs_SHAPE;
 207
 208   myListShapes.Clear();
 209   myMapFaces.Clear();
 210   myMapTools.Clear();
 211   myEqualEdges.Clear();
 212   myNewSection.Clear();
 213   myClosedShapes.Clear();
 214   mySharedFaces.Clear();
 215   myWrappingSolid.Clear();
 216   myFaceShapeMap.Clear();
 217
 218   myInternalFaces.Clear();
 219   myIntNotClFaces.Clear();
 220
 221   myAsDes->Clear();
 222   myImagesFaces.Clear();
 223   myImagesEdges.Clear();
 224   myImageShape.Clear();
 225
 226   myInter3d = Partition_Inter3d(myAsDes);
 227
 228   myAddedFacesMap.Clear();
 229
 230 }
 231
 232 //=======================================================================
 233 //function : Compute
 234 //purpose  : produce a result
 235 //=======================================================================
 236
 237 void Partition_Spliter::Compute(const TopAbs_ShapeEnum Limit)
 238 {
 239   if ((Limit != TopAbs_SHAPE && myDoneStep == Limit) ||
 240       (Limit == TopAbs_SHAPE && myDoneStep == TopAbs_SOLID))
 241     return;
 242
 243   myBuilder.MakeCompound( myShape );
 244
 245   TopTools_MapIteratorOfMapOfShape it;
 246   TopTools_ListIteratorOfListOfShape itl;
 247   TopExp_Explorer exp;
 248
 249 #ifdef PART_PERF
 250   OSD_Chronometer aCron;
 251 #endif
 252
 253   if (myDoneStep > TopAbs_VERTEX) {
 254
 255     TopTools_ListOfShape aListFaces;
 256     aListFaces = myImagesFaces.Roots();
 257     for (it.Initialize(myMapTools); it.More(); it.Next())
 258       aListFaces.Append(it.Key());
 259
 260 #ifdef PART_PERF
 261     aCron.Start();
 262 #endif
 263
 264     //-----------------------------------------------
 265     // Intersection between faces
 266     //-----------------------------------------------
 267     // result is in myAsDes as a map Face - list of new edges;
 268     // special care is done for section edges, same domain faces and vertices:
 269     // data about them is inside myInter3d
 270     myInter3d.CompletPart3d(aListFaces, myFaceShapeMap);
 271
 272 #ifdef PART_PERF
 273     MESSAGE("+++ CompletPart3d()");
 274     aCron.Show( cout );
 275     aCron.Reset();
 276     aCron.Start();
 277 #endif
 278     //-----------------------------------------------
 279     // Intersection of edges
 280     //-----------------------------------------------
 281
 282     // add tool faces which must be reconstructed to myMapFaces too
 283     FindToolsToReconstruct();
 284
 285 #ifdef PART_PERF
 286     MESSAGE("+++ FindToolsToReconstruct()");
 287     aCron.Show( cout );
 288     aCron.Reset();
 289     aCron.Start();
 290 #endif
 291
 292     // add existing vertices to edges of object faces in myAsDes
 293     TopTools_MapOfShape DoneEM;
 294     for ( it.Initialize(myMapFaces); it.More(); it.Next()) {
 295       const TopoDS_Shape& F  = it.Key();
 296       TopoDS_Face FForward = TopoDS::Face(F.Oriented(TopAbs_FORWARD));
 297       for (exp.Init(FForward,TopAbs_EDGE); exp.More(); exp.Next()) {
 298         const TopoDS_Edge& E = TopoDS::Edge( exp.Current() );
 299         myAsDes->Add(FForward,E);
 300         if (DoneEM.Add(E)) {
 301           TopoDS_Iterator itV(E);
 302           for (; itV.More(); itV.Next()) {
 303             const TopoDS_Vertex& V = TopoDS::Vertex( itV.Value());
 304             myAsDes->Add(E, myInter3d.ReplaceSameDomainV( V, E ));
 305           }
 306         }
 307       }
 308     }
 309
 310     // intersect edges that are descendants of a face in myAsDes
 311     TopTools_MapOfShape& Modif = myInter3d.TouchedFaces();
 312     for ( it.Initialize(Modif); it.More(); it.Next()) {
 313       const TopoDS_Face& F  = TopoDS::Face(it.Key());
 314       Partition_Inter2d::CompletPart2d (myAsDes, F, myInter3d.NewEdges());
 315     }
 316     // now myAsDes contains also new vertices made at edge intersection as
 317     // descendant of edges both new and old
 318
 319     myDoneStep = TopAbs_VERTEX;
 320
 321 #ifdef PART_PERF
 322     MESSAGE("+++ CompletPart2d()");
 323     aCron.Show( cout );
 324     aCron.Reset();
 325     aCron.Start();
 326 #endif
 327   } //   if (myDoneStep > TopAbs_VERTEX)
 328
 329   if (Limit == TopAbs_VERTEX) {
 330     // add new vertices to myShape
 331     for ( it.Initialize( myInter3d.NewEdges() ); it.More(); it.Next()) {
 332       if (! myAsDes->HasDescendant( it.Key() ))
 333         continue;
 334       itl.Initialize( myAsDes->Descendant( it.Key() ));
 335       for (; itl.More(); itl.Next())
 336         myBuilder.Add ( myShape, itl.Value() );
 337     }
 338     return;
 339   }
 340
 341
 342   if (myDoneStep > TopAbs_EDGE) {
 343
 344     //-----------------------------------------------
 345     //-----------------------------------------------
 346     // ------- Reconstruction of all the edges.------
 347     //-----------------------------------------------
 348     //-----------------------------------------------
 349
 350     // ==============
 351     // cut new edges
 352     // ==============
 353     TopTools_ListOfShape LSE; // all edge splits
 354     for ( it.Initialize(myInter3d.NewEdges()); it.More(); it.Next()) {
 355
 356       TopoDS_Vertex V1,V2;
 357       TopoDS_Edge EE = TopoDS::Edge(it.Key());
 358
 359       TopTools_ListOfShape aListV, aListF;
 360       aListV = myAsDes->Descendant(EE); // intersection vertices
 361       aListF = myAsDes->Ascendant(EE);  // intersected faces
 362
 363       if (aListV.IsEmpty())
 364         continue;  // new edge does not intersect any other edge
 365
 366       // Add end vertices to new edges only if
 367       // one face is Tool and the other is Shape
 368       Standard_Boolean isTool1 = ! myMapFaces.Contains( aListF.First() );
 369       Standard_Boolean isTool2 = ! myMapFaces.Contains( aListF.Last() );
 370       if (isTool1 || isTool2)
 371       {
 372         TopExp::Vertices(EE,V1,V2);
 373         Standard_Real Tol = Max (BRep_Tool::Tolerance( V1 ),
 374                                  BRep_Tool::Tolerance( V2 ));
 375
 376         gp_Pnt P1 = BRep_Tool::Pnt(V1);
 377         gp_Pnt P2 = BRep_Tool::Pnt(V2);
 378         Standard_Boolean AddV1 = Standard_True;
 379         Standard_Boolean AddV2 = Standard_True;
 380
 381         // add only if there is no intersection at end vertex
 382         for (itl.Initialize(aListV); itl.More(); itl.Next()) {
 383           const TopoDS_Vertex& Ve = TopoDS::Vertex(itl.Value()) ;
 384           Standard_Real Tol2 = Max ( Tol, BRep_Tool::Tolerance( Ve ));
 385           Tol2 *= Tol2;
 386           gp_Pnt P = BRep_Tool::Pnt(Ve);
 387           if (AddV1 && P.SquareDistance(P1) <= Tol2)
 388             AddV1 = Standard_False;
 389
 390           if (AddV2 && P.SquareDistance(P2) <= Tol2)
 391             AddV2 = Standard_False;
 392         }
 393
 394         if (AddV1) {
 395           aListV.Append(V1);
 396           myAsDes->Add(EE,V1);
 397         }
 398
 399         if (AddV2) {
 400           aListV.Append(V2);
 401           myAsDes->Add(EE,V2);
 402         }
 403       }
 404
 405       // cut new edges
 406       Standard_Integer NbV=aListV.Extent() ;
 407       if (NbV>1 || (NbV==1 && V1.IsSame(V2)) ) {
 408         TopTools_ListOfShape LNE;
 409         MakeEdges (EE,aListV, LNE);
 410         myImagesEdges.Bind(EE,LNE);
 411         LSE.Append( LNE );
 412       }
 413     }
 414
 415     // ==============
 416     // cut old edges
 417     // ==============
 418     for ( it.Initialize(myMapFaces); it.More(); it.Next()) {
 419       for (exp.Init( it.Key(), TopAbs_EDGE); exp.More(); exp.Next()) {
 420         const TopoDS_Edge& EE = TopoDS::Edge( exp.Current() );
 421         if ( myImagesEdges.HasImage( EE ))
 422           continue;
 423         TopTools_ListOfShape  LNE;
 424         const TopTools_ListOfShape& aListVV = myAsDes->Descendant(EE);
 425         MakeEdges (EE, aListVV, LNE);
 426         myImagesEdges.Bind(EE,LNE);
 427         LSE.Append( LNE );
 428       }
 429     }
 430 #ifdef PART_PERF
 431     MESSAGE("+++ Cut Edges");
 432     aCron.Show( cout );
 433     aCron.Reset();
 434     aCron.Start();
 435 #endif
 436
 437     // process same domain section edges
 438     MergeEqualEdges( LSE );
 439
 440     myDoneStep = TopAbs_EDGE;
 441
 442 #ifdef PART_PERF
 443     MESSAGE("+++ MergeEqualEdges()");
 444     aCron.Show( cout );
 445     aCron.Reset();
 446     aCron.Start();
 447 #endif
 448   }  //   if (myDoneStep > TopAbs_EDGE)
 449
 450   if (Limit == TopAbs_EDGE) {
 451     // add splits of old edges
 452     TopTools_ListIteratorOfListOfShape itNE;
 453     for (itl.Initialize( myListShapes );itl.More();itl.Next()) {
 454       if (myMapTools.Contains( itl.Value() ))
 455         continue; // skip tool faces
 456       for ( exp.Init( itl.Value(), TopAbs_EDGE ); exp.More(); exp.Next()) {
 457         itNE.Initialize( myImagesEdges.Image( exp.Current() ));
 458         for ( ; itNE.More(); itNE.Next())
 459           myBuilder.Add ( myShape, itNE.Value() );
 460       }
 461     }
 462     // add splits of new edges
 463     for ( it.Initialize( myInter3d.NewEdges() ); it.More(); it.Next()) {
 464       itNE.Initialize( myImagesEdges.Image( it.Key() ));
 465       for (; itNE.More(); itNE.Next())
 466         myBuilder.Add ( myShape, itNE.Value() );
 467     }
 468     return;
 469   }
 470
 471
 472   //-----------------------------------------------
 473   // split faces
 474   //-----------------------------------------------
 475
 476   if (myDoneStep > TopAbs_FACE) {
 477
 478     for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 479       TopoDS_Shape FacesComp = MakeFaces ( itl.Value());
 480       // there is a cunning here: myImagesFaces keeps faces made by Loop2d
 481       // but some of them may be replaced with splits of same domain face
 482       // and myImageShape keeps ultimate result
 483       myImageShape.Bind( itl.Value(), FacesComp );
 484     }
 485
 486     myDoneStep = TopAbs_FACE;
 487 #ifdef PART_PERF
 488     MESSAGE("+++ MakeFaces()");
 489     aCron.Show( cout );
 490     aCron.Reset();
 491     aCron.Start();
 492 #endif
 493   }
 494
 495   if (Limit == TopAbs_WIRE ||
 496       Limit == TopAbs_FACE)   {
 497     for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 498       if ( myMapTools.Contains( itl.Value() ))
 499         continue; // no result needed for a tool face
 500       const TopoDS_Shape& FacesComp = myImageShape.Image( itl.Value() ).First();
 501       for ( exp.Init( FacesComp, Limit); exp.More(); exp.Next())
 502         myBuilder.Add ( myShape, exp.Current());
 503     }
 504     return;
 505   }
 506
 507
 508   //-----------------------------------------------
 509   // split and add solids and shells
 510   //-----------------------------------------------
 511
 512   Standard_Boolean makeSolids = (Limit == TopAbs_SHAPE ||
 513                                  Limit < TopAbs_SHELL);
 514   for (itl.Initialize(myListShapes);itl.More();itl.Next())
 515   {
 516     const TopoDS_Shape & S = itl.Value();
 517     if (S.ShapeType() > TopAbs_SHELL)
 518       continue;
 519
 520     TopTools_ListOfShape NSL; // new shape list
 521     MakeShells (S , NSL);
 522     if (makeSolids && S.ShapeType() == TopAbs_SOLID )
 523       MakeSolids( S, NSL );
 524
 525     // store new shells or solids
 526     TopTools_ListIteratorOfListOfShape itNSL (NSL);
 527     for ( ; itNSL.More(); itNSL.Next())
 528       myBuilder.Add (myShape, itNSL.Value());
 529   }
 530 #ifdef PART_PERF
 531     MESSAGE("+++ MakeShells()");
 532     aCron.Show( cout );
 533 #endif
 534
 535   //-----------------------------------------------
 536   // add split faces
 537   //-----------------------------------------------
 538
 539   for (itl.Initialize(myListShapes);itl.More();itl.Next())
 540   {
 541     const TopoDS_Shape & S = itl.Value();
 542     if (S.ShapeType() != TopAbs_FACE ||
 543         myMapTools.Contains( S ))
 544       continue;
 545     TopoDS_Iterator itS( myImageShape.Image(S).First() );
 546     for (; itS.More(); itS.Next())
 547       if (! myAddedFacesMap.Contains( itS.Value() ))
 548         myBuilder.Add (myShape, itS.Value());
 549   }
 550
 551   myDoneStep = makeSolids ? TopAbs_SOLID : TopAbs_SHELL;
 552
 553 }
 554
 555 //=======================================================================
 556 //function : MakeSolids
 557 //purpose  : make solids out of Shells
 558 //=======================================================================
 559
 560 void Partition_Spliter::MakeSolids(const TopoDS_Shape &   theSolid,
 561                                    TopTools_ListOfShape & theShellList)
 562 {
 563   // for a solid wrapping other shells or solids without intersection,
 564   // it is necessary to find shells making holes in it
 565
 566   TopTools_ListOfShape aNewSolids; // result
 567   TopTools_ListOfShape aHoleShells;
 568   TopoDS_Shape anInfinitePointShape;
 569
 570   Standard_Boolean isWrapping = myWrappingSolid.Contains( theSolid );
 571   if (!isWrapping && !theShellList.IsEmpty())
 572   {
 573     // check if theSolid initially has internal shells
 574     TopoDS_Iterator aShellExp (theSolid);
 575     aShellExp.Next();
 576     isWrapping = aShellExp.More();
 577   }
 578
 579   TopTools_ListIteratorOfListOfShape aShellIt(theShellList);
 580   for ( ; aShellIt.More(); aShellIt.Next())
 581   {
 582     const TopoDS_Shape & aShell = aShellIt.Value();
 583
 584     // check if a shell is a hole
 585     if (isWrapping && IsInside (anInfinitePointShape, aShell))
 586       aHoleShells.Append( aShell );
 587     else
 588     {
 589       // make a solid from a shell
 590       TopoDS_Solid Solid;
 591       myBuilder.MakeSolid( Solid );
 592       myBuilder.Add (Solid, aShell);
 593
 594       aNewSolids.Append (Solid);
 595     }
 596   }
 597
 598   // find an outer shell most close to each hole shell
 599   TopTools_DataMapOfShapeShape aInOutMap;
 600   for (aShellIt.Initialize( aHoleShells ); aShellIt.More(); aShellIt.Next())
 601   {
 602     const TopoDS_Shape & aHole = aShellIt.Value();
 603     TopTools_ListIteratorOfListOfShape aSolisIt (aNewSolids);
 604     for ( ; aSolisIt.More(); aSolisIt.Next())
 605     {
 606       const TopoDS_Shape & aSolid = aSolisIt.Value();
 607       if (! IsInside( aHole, aSolid ))
 608         continue;
 609
 610       if ( aInOutMap.IsBound (aHole))
 611       {
 612         const TopoDS_Shape & aSolid2 = aInOutMap( aHole );
 613         if ( IsInside( aSolid, aSolid2 ))
 614         {
 615           aInOutMap.UnBind( aHole );
 616           aInOutMap.Bind ( aHole, aSolid );
 617         }
 618       }
 619       else
 620         aInOutMap.Bind ( aHole, aSolid );
 621     }
 622
 623     // add aHole to a solid
 624     if (aInOutMap.IsBound( aHole ))
 625       myBuilder.Add ( aInOutMap( aHole ), aHole );
 626   }
 627
 628   theShellList.Clear();
 629   theShellList.Append( aNewSolids );
 630 }
 631
 632 //=======================================================================
 633 //function : FindFacesInside
 634 //purpose  : return compound of faces  of other shapes that are
 635 //           inside <theShape>.
 636 //           <theShape> is an object shape.
 637 //           <CheckClosed> makes avoid faces that do not form a
 638 //           closed shell
 639 //           <All> makes return already added faces
 640 //=======================================================================
 641
 642 TopoDS_Shape Partition_Spliter::FindFacesInside(const TopoDS_Shape& theShape,
 643                                                 const Standard_Boolean CheckClosed,
 644                                                 const Standard_Boolean All)
 645 {
 646   // ================================================
 647   // check if internal faces have been already found
 648   // ================================================
 649   TopExp_Explorer expl;
 650   if (myInternalFaces.IsBound( theShape ))
 651   {
 652     TopoDS_Shape aIntFComp = myInternalFaces.Find ( theShape );
 653     TopoDS_Shape aIntRemFComp = myIntNotClFaces.Find ( theShape );
 654
 655     expl.Init( aIntRemFComp, TopAbs_FACE);
 656     if (CheckClosed || !expl.More())
 657       return aIntFComp;
 658
 659     TopoDS_Compound C;
 660     myBuilder.MakeCompound( C );
 661     // add removed faces
 662     for (; expl.More(); expl.Next())
 663       myBuilder.Add( C, expl.Current() );
 664     // add good internal faces
 665     for (expl.Init( aIntFComp, TopAbs_FACE); expl.More(); expl.Next())
 666       myBuilder.Add( C, expl.Current() );
 667     return C;
 668   }
 669
 670   // ===================================
 671   // get data for internal faces search
 672   // ===================================
 673
 674   // compound of split faces of theShape
 675   const TopoDS_Shape& CSF = myImageShape.Image(theShape).First();
 676
 677   TopTools_MapOfShape MSE, MFP;
 678   TopTools_DataMapOfShapeListOfShape DMSEFP;
 679   TopTools_MapIteratorOfMapOfShape itm;
 680   TopTools_ListOfShape EmptyL;
 681
 682   // MSE filling: map of new section edges of CSF
 683   for (expl.Init(CSF,TopAbs_EDGE); expl.More(); expl.Next()) {
 684     const TopoDS_Shape & resE = expl.Current() ;
 685     if (myNewSection.Contains( resE )) // only new edges
 686       MSE.Add(resE);
 687   }
 688
 689   // DMEF: map edge of CSF - faces of CSF
 690   TopTools_IndexedDataMapOfShapeListOfShape DMEF;
 691   TopExp::MapShapesAndAncestors(CSF, TopAbs_EDGE, TopAbs_FACE, DMEF);
 692
 693   // Fill
 694   // 1.  MFP - a map of faces to process: map of resulting faces except
 695   // those of theShape; we`ll add to C those of them which are inside CSF
 696   // 2.  DMSEFP - edge of MSE => faces of MFP
 697   TopTools_ListIteratorOfListOfShape itl;
 698   for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 699     const TopoDS_Shape& aShape = itl.Value();
 700     if ( theShape.IsSame( aShape )) continue;
 701     // fill maps
 702     // iterate on split faces of aShape
 703     TopoDS_Iterator itF ( myImageShape.Image(aShape).First() );
 704     for ( ; itF.More(); itF.Next()) {
 705       const TopoDS_Shape& sf = itF.Value();
 706       MFP.Add(sf);
 707       // iterate on edges of split faces of aShape,
 708       // add to DMSEFP edges that are new
 709       for (expl.Init( sf, TopAbs_EDGE ); expl.More(); expl.Next()) {
 710         TopoDS_Shape se = expl.Current();
 711         if ( MSE.Contains(se)) {// section edge
 712           if (!DMSEFP.IsBound(se))
 713             DMSEFP.Bind(se,EmptyL);
 714           DMSEFP(se).Append(sf);
 715         }
 716       }
 717     }
 718   }
 719
 720   // add tool faces having section edges on faces of theShape to MFP and DMSEFP;
 721   // such tool faces need not to be reconstructed and so they are not in myListShapes
 722   for (itm.Initialize(myMapTools); itm.More(); itm.Next())
 723   {
 724     const TopoDS_Shape & aToolFace = itm.Key();
 725     if (myMapFaces.Contains( aToolFace ))
 726       continue;
 727     MFP.Add(aToolFace);
 728     for (expl.Init( aToolFace, TopAbs_EDGE ); expl.More(); expl.Next()) {
 729       TopoDS_Shape se = expl.Current();
 730       if ( MSE.Contains( se )) {// section edge
 731         if (!DMSEFP.IsBound( se ))
 732           DMSEFP.Bind( se, EmptyL );
 733         DMSEFP( se ).Append( aToolFace );
 734       }
 735     }
 736   }
 737
 738
 739   // ===========================
 740   // find faces inside theShape
 741   // ===========================
 742
 743   Standard_Boolean skipAlreadyAdded = Standard_False;
 744   Standard_Boolean GoodOri, inside;
 745   Standard_Real dot;
 746   TopTools_ListOfShape KeepFaces;
 747   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
 748
 749   // iterate on section edges, check faces of other shapes
 750   // sharing section edges and put internal faces to KeepFaces
 751   for (Mapit.Initialize(DMSEFP); Mapit.More() ; Mapit.Next() ) {
 752     // a new edge of theShape
 753     const TopoDS_Edge& E = TopoDS::Edge (Mapit.Key());
 754     // an original edge of which E is a split
 755     const TopoDS_Edge& OrigE = TopoDS::Edge ( myImagesEdges.Root( E ));
 756     // does OrigE itself splits a face
 757     Standard_Boolean isSectionE = myInter3d.IsSectionEdge ( OrigE );
 758
 759     // split faces of other shapes sharing E
 760     TopTools_ListOfShape& LSF = DMSEFP.ChangeFind(E);
 761     itl.Initialize( LSF );
 762     while (itl.More()) {
 763       // a split faces of other shape
 764       TopoDS_Face aFace1 = TopoDS::Face(itl.Value());
 765       // remove aFace1 form DMSEFP and MFP
 766       LSF.Remove( itl ); // == itl.Next();
 767       if (!MFP.Remove( aFace1 ))
 768         continue; // was not is MFP ( i.e already checked)
 769       // check if aFace1 was already added to 2 shells
 770       if (!All &&
 771           myAddedFacesMap.Contains( aFace1 ) &&
 772           myAddedFacesMap.Contains( aFace1.Reversed() )) {
 773         skipAlreadyAdded = Standard_True;
 774         continue;
 775       }
 776
 777       // find another face which originates from the same face as aFace1:
 778       // usually aFace2 is internal if aFace1 is not and vice versa
 779
 780       TopoDS_Shape anOrigFace = aFace1;
 781       if (myImagesFaces.IsImage(aFace1))
 782         anOrigFace = myImagesFaces.Root(aFace1);
 783       TopoDS_Shape aFace2;
 784       if ( !isSectionE ) {
 785         while (itl.More()) {
 786           aFace2 = itl.Value();
 787           if (!MFP.Contains( aFace2 )) {
 788             LSF.Remove( itl );
 789             continue;
 790           }
 791           if (anOrigFace.IsSame( myImagesFaces.Root( aFace2 )))
 792             break;
 793           itl.Next();
 794         }
 795         if (itl.More()) { // aFace2 found, remove it from maps
 796           LSF.Remove( itl );
 797           MFP.Remove(aFace2);
 798         }
 799         else
 800           aFace2.Nullify();
 801         itl.Initialize( LSF );
 802       }
 803
 804       // check that anOrigFace is not same domain with CSF faces it intersects
 805
 806       const TopTools_ListOfShape& FL = DMEF.FindFromKey(E); //faces of CSF sharing E
 807       const TopoDS_Shape& origF1 = myImagesFaces.Root(FL.First());
 808       const TopoDS_Shape& origF2 = myImagesFaces.Root(FL.Last());
 809       Standard_Boolean sameDom1 = anOrigFace.IsSame( origF1 );
 810       Standard_Boolean sameDom2 = anOrigFace.IsSame( origF2 );
 811       if (!(sameDom1 || sameDom2) && myInter3d.HasSameDomainF( anOrigFace )) {
 812         sameDom1 = myInter3d.IsSameDomainF( anOrigFace, origF1);
 813         if (origF1 == origF2)
 814           sameDom2 = sameDom1;
 815         else
 816           myInter3d.IsSameDomainF( anOrigFace, origF2);
 817       }
 818       if (sameDom1 && sameDom2)
 819         continue;
 820       if ((sameDom1 || sameDom2)) {
 821         inside = Partition_Loop3d::IsInside (E,
 822                                              TopoDS::Face(FL.First()),
 823                                              TopoDS::Face(FL.Last()),
 824                                              1, dot, GoodOri);
 825         if (inside || (dot + Precision::Angular() >= 1.0))
 826           continue; // E is convex between origF1 and origF2 or they are tangent
 827       }
 828
 829
 830       // keep one of found faces
 831
 832       //face of CSF sharing E
 833       const TopoDS_Shape& aShapeFace = sameDom1 ? FL.Last() : FL.First();
 834       // analyse aFace1 state
 835       inside = Partition_Loop3d::IsInside (E, TopoDS::Face(aShapeFace), aFace1,
 836                                            1, dot, GoodOri);
 837       if (inside && isSectionE)
 838       {
 839         // aFace1 must be tested with both adjacent faces of CSF
 840         const TopoDS_Shape& aShapeFace2 = sameDom1 ? FL.First() : FL.Last();
 841         if (aShapeFace2 != aShapeFace)
 842           inside = Partition_Loop3d::IsInside (E, TopoDS::Face(aShapeFace2), aFace1,
 843                                                1, dot, GoodOri);
 844       }
 845
 846       // store internal face
 847       if (inside)
 848         KeepFaces.Append(aFace1);
 849
 850       else if (!aFace2.IsNull())
 851       {
 852         if (dot + Precision::Angular() >= 1.0)
 853         {
 854           // aFace2 state is not clear, it will be analysed alone,
 855           // put it back to the maps
 856           MFP.Add( aFace2 );
 857           LSF.Append( aFace2 );
 858         }
 859         else
 860           KeepFaces.Append(aFace2);
 861       }
 862     }
 863   }
 864
 865   // ===================================================
 866   // add not distributed faces connected with KeepFaces
 867   // ===================================================
 868
 869   // ultimate list of internal faces
 870   TopTools_ListOfShape KeptFaces;
 871
 872   // add to MFP not split tool faces as well, they may be connected with
 873   // tool faces interfering with theShape
 874   for ( itm.Initialize(myMapTools); itm.More(); itm.Next() ) {
 875     const TopoDS_Shape& aToolFace = itm.Key();
 876     if (!myImageShape.HasImage(aToolFace))
 877       MFP.Add (aToolFace);
 878   }
 879
 880   if (MFP.IsEmpty())
 881     KeptFaces.Append (KeepFaces);
 882
 883   while (!KeepFaces.IsEmpty())
 884   {
 885     // KeepEdges : map of edges of faces kept last time
 886     TopTools_IndexedMapOfShape KeepEdges;
 887     for ( itl.Initialize(KeepFaces); itl.More(); itl.Next() ) {
 888       TopExp::MapShapes( itl.Value(), TopAbs_EDGE, KeepEdges);
 889       KeptFaces.Append( itl.Value() );
 890     }
 891
 892     KeepFaces.Clear();
 893
 894     // keep faces connected with already kept faces by KeepEdges
 895     for ( itm.Initialize(MFP); itm.More(); itm.Next() ) {
 896       const TopoDS_Shape& FP = itm.Key();
 897       for (expl.Init(FP,TopAbs_EDGE); expl.More(); expl.Next()) {
 898         const TopoDS_Shape& se = expl.Current();
 899         if (!MSE.Contains(se) && KeepEdges.Contains(se) ) {
 900           KeepFaces.Append(FP);
 901           MFP.Remove(FP);
 902           break;
 903         }
 904       }
 905     }
 906   }
 907
 908   // ===============================================================
 909   // here MFP contains faces outer of theShape and those of shapes
 910   // which do not interfere with theShape at all and between which
 911   // there may be those wrapped by theShape and whose faces may be
 912   // needed to be returned as well
 913   // ===============================================================
 914
 915   Standard_Boolean isSolid = (theShape.ShapeType() == TopAbs_SOLID);
 916   if (All || isSolid)  // All is for sub-result removal
 917   {
 918     // loop on not used faces; checked faces will be removed from MFP
 919     // during the loop
 920     for ( itm.Initialize( MFP ); itm.More(); itm.Next() ) {
 921       const TopoDS_Shape & aFace = itm.Key();
 922
 923       // a shape which aFace originates from
 924       TopoDS_Shape anOrigShape = GetOriginalShape( aFace );
 925
 926       // find out if all split faces of anOrigShape are not in MFP
 927       // and by the way remove them from MFP
 928       Standard_Boolean isAllOut = Standard_True;
 929       TopoDS_Shape aSplitFaces = anOrigShape;
 930       if (myImageShape.HasImage(anOrigShape))
 931         aSplitFaces = myImageShape.Image(anOrigShape).First();
 932
 933       TopTools_ListOfShape aSplitFaceL; // faces candidate to be kept
 934       for (expl.Init( aSplitFaces, TopAbs_FACE ); expl.More(); expl.Next())
 935       {
 936         const TopoDS_Shape & aSpFace = expl.Current();
 937         // a tool face which became object has image but the whole tool shape has not
 938         if (myImageShape.HasImage( aSpFace ))
 939         {
 940           TopExp_Explorer exF (myImageShape.Image( aSpFace ).First(), TopAbs_FACE );
 941           for ( ; exF.More(); exF.Next() )
 942           {
 943             aSplitFaceL.Append( exF.Current() );
 944             if ( ! MFP.Remove( exF.Current() ) && isAllOut )
 945               // a shared face might be removed from MFP during a prev loop
 946               isAllOut = mySharedFaces.Contains( exF.Current() );
 947           }
 948         }
 949         else
 950         {
 951           aSplitFaceL.Append( aSpFace );
 952           if ( ! MFP.Remove( aSpFace ) && isAllOut)
 953             // a shared face might be removed from MFP during a prev loop
 954             isAllOut = mySharedFaces.Contains( aSpFace );
 955         }
 956       }
 957       itm.Initialize( MFP ); // iterate remaining faces
 958       if ( !isAllOut )
 959         continue;
 960
 961       // classify anOrigShape against theShape
 962       if (IsInside (anOrigShape, theShape))
 963       {
 964         if (isSolid && myClosedShapes.Contains( anOrigShape ))
 965           // to make a special care at solid reconstruction
 966           myWrappingSolid.Add ( theShape );
 967
 968         // keep faces of an internal shape anOrigShape
 969         KeptFaces.Append( aSplitFaceL );
 970       }
 971     }
 972   }
 973
 974   // ====================================================
 975   // check if kept faces form a shell without free edges
 976   // ====================================================
 977
 978   DMEF.Clear();  // edge - kept faces
 979   MFP.Clear(); // reuse it for wrong faces
 980   if (CheckClosed) {
 981     for (itl.Initialize(KeptFaces); itl.More(); itl.Next() )
 982       TopExp::MapShapesAndAncestors(itl.Value(), TopAbs_EDGE, TopAbs_FACE, DMEF);
 983
 984     Standard_Integer i, nb = DMEF.Extent();
 985     Standard_Boolean isClosed = Standard_False;
 986     while (!isClosed) {
 987       isClosed = Standard_True;
 988       for (i=1;  isClosed && i<=nb;  ++i) {
 989         const TopoDS_Shape& E = DMEF.FindKey( i );
 990         if (! BRep_Tool::Degenerated( TopoDS::Edge( E )) &&
 991             ! MSE.Contains( E ))
 992           isClosed = ( DMEF(i).Extent() != 1 );
 993       }
 994       if (!isClosed) {
 995         const TopoDS_Shape& F = DMEF.FindFromIndex( i-1 ).First(); // bad face
 996         MFP.Add( F );
 997         // remove bad face from DMEF
 998         for (expl.Init( F, TopAbs_EDGE); expl.More(); expl.Next()) {
 999           const TopoDS_Shape& E = expl.Current();
1000           TopTools_ListOfShape& FL = DMEF.ChangeFromKey( E );
1001           for (itl.Initialize( FL ); itl.More(); itl.Next() ) {
1002             if ( F.IsSame( itl.Value() )) {
1003               FL.Remove( itl );
1004               break;
1005             }
1006           }
1007         }
1008       }
1009     }
1010   }
1011
1012   // ==============
1013   // make a result
1014   // ==============
1015
1016   TopoDS_Compound C;
1017   // compound of removed internal faces
1018   TopoDS_Compound CNotCl;
1019
1020   myBuilder.MakeCompound(C);
1021   myBuilder.MakeCompound(CNotCl);
1022
1023   // add to compounds
1024   for (itl.Initialize(KeptFaces); itl.More(); itl.Next() )
1025   {
1026     TopoDS_Shape & aIntFace = itl.Value();
1027     if (! MFP.Contains( aIntFace ))
1028       myBuilder.Add( C, aIntFace);
1029     else
1030       myBuilder.Add( CNotCl, aIntFace);
1031   }
1032
1033   if (!skipAlreadyAdded && CheckClosed)
1034   {
1035     myInternalFaces.Bind( theShape, C );
1036     myIntNotClFaces.Bind( theShape, CNotCl );
1037   }
1038
1039   return C;
1040 }
1041
1042 //=======================================================================
1043 //function : MakeShell
1044 //purpose  : split S into compound of shells
1045 //=======================================================================
1046
1047 void Partition_Spliter::MakeShells(const TopoDS_Shape& S,
1048                                    TopTools_ListOfShape& NS)
1049 {
1050   Partition_Loop3d ShellMaker;
1051   // get compound of split faces of S
1052   const TopoDS_Shape& FacesComp = myImageShape.Image(S).First();
1053   ShellMaker.AddConstFaces( FacesComp );
1054   // add split faces inside S
1055   if (myClosedShapes.Contains( S )) {
1056     TopoDS_Shape InternalFacesComp = FindFacesInside(S, Standard_True);
1057     ShellMaker.AddSectionFaces( InternalFacesComp );
1058   }
1059
1060   NS = ShellMaker.MakeShells( myAddedFacesMap );
1061
1062   // Add faces added to new shell to myAddedFacesMap:
1063   // avoid rebuilding twice commont part of 2 solids.
1064   TopTools_ListIteratorOfListOfShape itS(NS);
1065   while ( itS.More()) {
1066     TopExp_Explorer expF (itS.Value(), TopAbs_FACE);
1067     for (; expF.More(); expF.Next())
1068       myAddedFacesMap.Add (expF.Current());
1069
1070     itS.Next();
1071   }
1072 }
1073
1074 //=======================================================================
1075 //function : findEqual
1076 //purpose  : compare edges of EL1 against edges of EL2,
1077 //           Result is in EMM binding EL1 edges to list of equal edges.
1078 //           Edges are considered equall only if they have same vertices.
1079 //           <addSame>==True makes consider same edges as equal
1080 //           Put in <AllEqMap> all equal edges
1081 //=======================================================================
1082
1083 static void findEqual (const TopTools_ListOfShape& EL1,
1084                        const TopTools_ListOfShape& EL2,
1085                        const Standard_Boolean addSame,
1086                        TopTools_DataMapOfShapeListOfShape& EEM,
1087                        TopTools_MapOfShape& AllEqMap)
1088 {
1089   // map vertices to edges for EL2
1090   TopTools_DataMapOfShapeListOfShape VEM;
1091   TopTools_ListIteratorOfListOfShape itE1, itE2(EL2);
1092   TopoDS_Iterator itV;
1093   TopTools_ListOfShape emptyL;
1094   for (; itE2.More(); itE2.Next()) {
1095     for (itV.Initialize( itE2.Value() ); itV.More(); itV.Next()) {
1096       const TopoDS_Shape& V = itV.Value();
1097       if (! VEM.IsBound( V ) )
1098         VEM.Bind( V, emptyL);
1099       VEM( V ).Append( itE2.Value());
1100     }
1101   }
1102
1103   gp_Vec D1, D2;
1104   gp_Pnt P;
1105   Standard_Real f,l,u,tol;
1106   Handle(Geom_Curve) C1, C2;
1107   Extrema_ExtPC Extrema;
1108   TopoDS_Vertex V1, V2, V3, V4;
1109
1110   AllEqMap.Clear();
1111
1112   for (itE1.Initialize(EL1); itE1.More(); itE1.Next()) {
1113     const TopoDS_Edge& E1 = TopoDS::Edge( itE1.Value());
1114     if (BRep_Tool::Degenerated( E1 ) || AllEqMap.Contains (E1))
1115       continue;
1116     TopExp::Vertices( E1, V1, V2 );
1117
1118     if (VEM.IsBound(V1))
1119       itE2.Initialize( VEM(V1) );
1120     for (; itE2.More(); itE2.Next()) {
1121       const TopoDS_Edge& E2 = TopoDS::Edge( itE2.Value());
1122       if (BRep_Tool::Degenerated( E2 ) || AllEqMap.Contains (E2))
1123         continue;
1124
1125       if (E1.IsSame(E2)) {
1126         if (!addSame)
1127           continue;
1128       }
1129       else {
1130         TopExp::Vertices( E2, V3, V4);
1131         if (!V2.IsSame(V4) && !V2.IsSame(V3))
1132           continue;
1133         // E1 and E2 have same vertices
1134         // check D1 at end points.
1135         C2 = BRep_Tool::Curve( E2, f,l);
1136         C1 = BRep_Tool::Curve( E1, f,l);
1137         u = BRep_Tool::Parameter(V1,E1);
1138         C1->D1(u, P, D1);
1139         u = BRep_Tool::Parameter(V1.IsSame(V3) ? V3 : V4, E2);
1140         C2->D1(u, P, D2);
1141         D1.Normalize(); D2.Normalize();
1142         if (Abs(D1*D2) + Precision::Angular() < 1.0)
1143           continue;
1144         if (! V1.IsSame(V2)) {
1145           u = BRep_Tool::Parameter(V2,E1);
1146           C1->D1(u, P, D1);
1147           u = BRep_Tool::Parameter(V2.IsSame(V3) ? V3 : V4, E2);
1148           C2->D1(u, P, D2);
1149           D1.Normalize(); D2.Normalize();
1150           if (Abs(D1*D2) + Precision::Angular() < 1.0)
1151             continue;
1152         }
1153         // check distance at a couple of internal points
1154         tol = Max(BRep_Tool::Tolerance(E1),
1155                   BRep_Tool::Tolerance(E2));
1156         GeomAdaptor_Curve AC1(C1);
1157         Extrema.Initialize(AC1,f,l);
1158         Standard_Boolean ok = Standard_True, hasMin = Standard_False;
1159         BRep_Tool::Range( E2, f, l);
1160         Standard_Integer i=1, nbi=3;
1161         for (; i<nbi && ok; ++i) {
1162           Extrema.Perform( C2->Value( f+(l-f)*i/nbi ));
1163           Standard_Integer j=1, nbj=Extrema.NbExt();
1164           for (; j<=nbj && ok; ++j) {
1165             if (Extrema.IsMin(j)) {
1166               hasMin = Standard_True;
1167               ok = Extrema.Value(j) <= tol;
1168             }
1169           }
1170         }
1171         if ( !hasMin || !ok)
1172           continue;
1173       }
1174       // bind E2 to E1 in EEM
1175       if (!EEM.IsBound(E1)) {
1176         EEM.Bind (E1, emptyL);
1177         AllEqMap.Add (E1);
1178       }
1179       EEM(E1).Append(E2);
1180       AllEqMap.Add (E2);
1181     }
1182   }
1183 }
1184
1185 //=======================================================================
1186 //function : MakeFaces
1187 //purpose  : split faces of S, return compound of new faces
1188 //=======================================================================
1189
1190 TopoDS_Shape Partition_Spliter::MakeFaces (const TopoDS_Shape& S)
1191 {
1192   TopoDS_Compound C;
1193   myBuilder.MakeCompound(C);
1194
1195   TopTools_ListIteratorOfListOfShape itl, itNE;
1196
1197   TopExp_Explorer exp(S,TopAbs_FACE);
1198   for (; exp.More(); exp.Next()) {
1199
1200     const TopoDS_Face& F = TopoDS::Face(exp.Current());
1201
1202     TopTools_ListOfShape LNF;
1203
1204     if (myImagesFaces.HasImage( F )) {
1205       myImagesFaces.LastImage( F, LNF );
1206       TopAbs_Orientation oriF = F.Orientation();
1207       for ( itl.Initialize( LNF ); itl.More(); itl.Next())
1208         itl.Value().Orientation( oriF );
1209     }
1210     else {
1211
1212       Partition_Loop2d loops;
1213       loops.Init(F);
1214
1215       TopTools_IndexedMapOfShape EM;
1216       TopExp::MapShapes( F, TopAbs_EDGE, EM);
1217
1218       TopTools_MapOfShape AddedEqualM, EqualSeamM;
1219       Standard_Boolean needRebuild = Standard_False;
1220
1221       // add splits to loops
1222
1223       // LE: old edges + new not splitted edges
1224       const TopTools_ListOfShape& LE = myAsDes->Descendant(F);
1225       for (itl.Initialize(LE); itl.More(); itl.Next()) {
1226         const TopoDS_Edge& E = TopoDS::Edge( itl.Value() );
1227
1228         Standard_Boolean isSectionE = myInter3d.IsSectionEdge(E);
1229         Standard_Boolean isNewE = !EM.Contains( E );
1230
1231         // LSE: list of split edges
1232         TopTools_ListOfShape LSE;
1233         myImagesEdges.LastImage(E,LSE); // splits of E or E itself
1234
1235         for (itNE.Initialize(LSE); itNE.More(); itNE.Next()) {
1236
1237           TopoDS_Edge NE = TopoDS::Edge( itNE.Value() );
1238           Standard_Boolean isSameE = NE.IsSame ( E );
1239
1240           if ( isNewE || isSectionE || !isSameE) {
1241             if (AddedEqualM.Contains( NE )) {
1242               // a seam must be twice in a loop
1243               if (!BRep_Tool::IsClosed( E, F ) || !EqualSeamM.Add( NE ))
1244                 continue;
1245             }
1246
1247             if (isNewE) {
1248               if (isSectionE) {
1249                 if ( ! myInter3d.IsSplitOn( NE, E, F) )
1250                   continue;
1251               }
1252               else {
1253                 TopoDS_Vertex V1,V2;
1254                 TopExp::Vertices(NE,V1,V2);
1255                 const TopTools_ListOfShape& EL1 = myAsDes->Ascendant(V1);
1256                 const TopTools_ListOfShape& EL2 = myAsDes->Ascendant(V2);
1257                 if ( EL1.Extent() < 2 && EL2.Extent() < 2 )
1258                   continue;
1259               }
1260             }
1261             else {
1262               NE.Orientation( E.Orientation());
1263               if (!isSameE) {
1264                 // orient NE because it may be a split of other edge
1265                 Standard_Real f,l,u;
1266                 Handle(Geom_Curve) C3d  = BRep_Tool::Curve( E,f,l );
1267                 Handle(Geom_Curve) NC3d = BRep_Tool::Curve( NE,f,l);
1268                 if ( C3d != NC3d) {
1269                   gp_Vec D1, ND1;  gp_Pnt P;
1270                   TopoDS_Vertex V = TopExp::FirstVertex(NE);
1271                   u = BRep_Tool::Parameter(V,NE);
1272                   NC3d->D1 (u, P, ND1);
1273                   u = BRep_Tool::Parameter(V,E);
1274                   C3d ->D1 (u, P, D1);
1275                   if (ND1.Dot(D1) < 0)
1276                     NE.Reverse();
1277                 }
1278               }
1279             }
1280             if (myEqualEdges.Contains( NE ))
1281               AddedEqualM.Add( NE );
1282
1283             needRebuild = Standard_True;
1284           }
1285
1286           if (isNewE || isSectionE)
1287             myNewSection.Add( NE );
1288
1289           if (isNewE)
1290             loops.AddSectionEdge(NE);
1291           else
1292             loops.AddConstEdge(NE);
1293         }
1294       }
1295
1296       //-------------------
1297       // Build the faces.
1298       //-------------------
1299
1300       if (needRebuild) {
1301
1302         loops.Perform();
1303         loops.WiresToFaces(myImagesEdges);
1304
1305         LNF = loops.NewFaces();
1306
1307         myImagesFaces.Bind(F,LNF);
1308
1309         // replace the result faces that have already been built
1310         // during same domain faces reconstruction done earlier
1311         if (myInter3d.HasSameDomainF( F ))
1312         {
1313           // build map edge to same domain faces: EFM
1314           TopTools_IndexedDataMapOfShapeListOfShape EFM;
1315           TopTools_MapOfShape SDFM; // avoid doubling
1316           itl.Initialize( myInter3d.SameDomain( F ));
1317           for (; itl.More(); itl.Next()) {
1318             if ( !myImagesFaces.HasImage( itl.Value() ))
1319               continue;
1320             // loop on splits of a SD face
1321             TopTools_ListIteratorOfListOfShape itNF;
1322             itNF.Initialize (myImagesFaces.Image( itl.Value() ));
1323             for ( ; itNF.More(); itNF.Next()) {
1324               TopoDS_Shape SDF = itNF.Value();
1325               if (myImagesFaces.HasImage( SDF )) // already replaced
1326                 SDF = myImagesFaces.Image( SDF ).First();
1327               if (SDFM.Add (SDF))
1328                 TopExp::MapShapesAndAncestors(SDF, TopAbs_EDGE, TopAbs_FACE, EFM);
1329             }
1330           }
1331           // do replace faces in the LNF
1332           TopTools_ListOfShape LOF;
1333           if ( !EFM.IsEmpty() )
1334             itl.Initialize( LNF );
1335           while (itl.More()) {
1336             const TopoDS_Shape& NF = itl.Value();
1337             TopExp_Explorer expE ( NF, TopAbs_EDGE );
1338             const TopoDS_Edge& E  = TopoDS::Edge (expE.Current());
1339             if (EFM.Contains( E )) {
1340               const TopTools_ListOfShape& SDFL = EFM.FindFromKey( E );
1341               TopoDS_Shape SDF = SDFL.First();
1342               Standard_Boolean GoodOri;
1343               Standard_Real dot;
1344               Partition_Loop3d::IsInside (E, TopoDS::Face(NF), TopoDS::Face(SDF),
1345                                           1, dot, GoodOri);
1346               if (dot < 0)
1347               {
1348                 // NF and SDF are on different side of E
1349                 if (SDFL.Extent() == 1) {
1350                   itl.Next();
1351                   continue;
1352                 }
1353                 else
1354                   SDF = SDFL.Last(); // next face must be on the same side
1355               }
1356               gp_Vec V1 = Partition_Loop3d::Normal( E, TopoDS::Face( NF ));
1357               gp_Vec V2 = Partition_Loop3d::Normal( E, TopoDS::Face( SDF ));
1358               if (V1*V2 < 0)
1359                 SDF.Reverse();
1360
1361               if (!myImagesFaces.HasImage( NF ))
1362                 myImagesFaces.Bind( NF, SDF );
1363
1364               // mySharedFaces is used in FindFacesInside()
1365               mySharedFaces.Add( SDF );
1366
1367               LOF.Prepend ( SDF );
1368               LNF.Remove (itl);
1369             }
1370             else
1371               itl.Next();
1372           }
1373
1374           LNF.Append (LOF);
1375         }
1376       } // if (needRebuild)
1377
1378       else {
1379         LNF.Append( F );
1380         myImagesFaces.Bind(F,LNF);
1381       }
1382     } // if (myImagesFaces.HasImage( F ))
1383
1384     // fill the resulting compound
1385     for (itl.Initialize(LNF); itl.More(); itl.Next())
1386       myBuilder.Add ( C, itl.Value());
1387
1388   } // loop on faces of S
1389
1390   return C;
1391 }
1392
1393
1394 //=======================================================================
1395 //function : Tri
1396 //purpose  :
1397 //=======================================================================
1398
1399 static void Tri(const TopoDS_Edge&        E,
1400                 TopTools_SequenceOfShape& Seq,
1401                 const Partition_Inter3d & theInter3d)
1402 {
1403   Standard_Boolean Invert   = Standard_True;
1404   Standard_Real    U1,U2;
1405   TopoDS_Vertex    V1,V2;
1406
1407   while (Invert) {
1408     Invert = Standard_False;
1409     for ( Standard_Integer i = 1; i < Seq.Length(); i++) {
1410
1411       V1 = TopoDS::Vertex(Seq.Value(i));
1412       V2 = TopoDS::Vertex(Seq.Value(i+1));
1413
1414       V1.Orientation(TopAbs_INTERNAL);
1415       V2.Orientation(TopAbs_INTERNAL);
1416
1417       U1 = BRep_Tool::Parameter(V1,E);
1418       U2 = BRep_Tool::Parameter(V2,E);
1419
1420       if (IsEqual(U1,U2)) {
1421         if (theInter3d.ReplaceSameDomainV( V1, E ).IsSame( V1 ))
1422           Seq.Remove(i+1); // remove V2
1423         else
1424           Seq.Remove(i);
1425         i--;
1426         continue;
1427       }
1428       if (U2 < U1) {
1429         Seq.Exchange(i,i+1);
1430         Invert = Standard_True;
1431       }
1432     }
1433   }
1434 }
1435
1436 //=======================================================================
1437 //function : MakeEdges
1438 //purpose  : cut E by vertices VOnE, return list of new edges NE
1439 //=======================================================================
1440
1441 void Partition_Spliter::MakeEdges (const TopoDS_Edge& E,
1442                                    const TopTools_ListOfShape& VOnE,
1443                                    TopTools_ListOfShape& NE   ) const
1444 {
1445   TopoDS_Edge WE = E;
1446   WE.Orientation(TopAbs_FORWARD);
1447
1448   Standard_Real    U1,U2, f, l;
1449   TopoDS_Vertex    V1,V2,VF,VL;
1450
1451   BRep_Tool::Range(WE,f,l);
1452   TopExp::Vertices(WE,VF,VL);
1453
1454   if (VOnE.Extent() < 3) { // do not rebuild not cut edge
1455     if (( VF.IsSame( VOnE.First() ) && VL.IsSame( VOnE.Last() )) ||
1456         VL.IsSame( VOnE.First() ) && VF.IsSame( VOnE.Last() )  ) {
1457       NE.Append( E );
1458       return;
1459     }
1460   }
1461
1462   TopTools_SequenceOfShape SV;
1463   TopTools_ListIteratorOfListOfShape itv(VOnE);
1464   TopTools_MapOfOrientedShape VM( VOnE.Extent() );
1465   for (; itv.More(); itv.Next())
1466     if ( VM.Add( itv.Value() ))
1467       SV.Append(itv.Value());
1468
1469   Tri( WE, SV, myInter3d );
1470
1471   if (SV.Length() < 3) { // do not rebuild not cut edge
1472     if (( VF.IsSame( SV.First() ) && VL.IsSame( SV.Last() )) ||
1473         VL.IsSame( SV.First() ) && VF.IsSame( SV.Last() )  ) {
1474       NE.Append( E );
1475       return;
1476     }
1477   }
1478
1479   Standard_Integer iVer, NbVer = SV.Length();
1480
1481
1482   //----------------------------------------------------------------
1483   // Construction of the new edges .
1484   //----------------------------------------------------------------
1485
1486   if (VF.IsSame(VL)) { // closed edge
1487     if (NbVer==1)
1488       SV.Append( SV.First() );
1489     else if (!SV.First().IsSame(SV.Last())) {
1490       Standard_Boolean isFirst=0;
1491       Standard_Real    minDU = 1.e10;
1492       TopoDS_Vertex endV = Partition_Inter2d::FindEndVertex(VOnE, f,l, E, isFirst,minDU);
1493       if (endV.IsSame(SV.First()))
1494         SV.Append(endV);
1495       else if (endV.IsSame(SV.Last()))
1496         SV.Prepend(endV);
1497       else
1498         MESSAGE ("END VERTEX IS IN SEQUNCE MIDDLE");
1499     }
1500     NbVer = SV.Length();
1501   }
1502
1503   for (iVer=1; iVer < NbVer; iVer++) {
1504     V1  = TopoDS::Vertex(SV(iVer));
1505     V2  = TopoDS::Vertex(SV(iVer+1));
1506
1507     TopoDS_Shape NewEdge = WE.EmptyCopied();
1508     V1.Orientation(TopAbs_FORWARD);
1509     myBuilder.Add  (NewEdge,V1);
1510     V2.Orientation(TopAbs_REVERSED);
1511     myBuilder.Add  (NewEdge,V2);
1512
1513     if (iVer==1)
1514       U1 = f;
1515     else        {
1516       V1.Orientation(TopAbs_INTERNAL);
1517       U1=BRep_Tool::Parameter(V1,WE);
1518     }
1519     if (iVer+1 == NbVer)
1520       U2 = l;
1521     else        {
1522       V2.Orientation(TopAbs_INTERNAL);
1523       U2=BRep_Tool::Parameter(V2,WE);
1524     }
1525     if (Abs(U1-U2) <= Precision::PConfusion()) {
1526       MESSAGE( "MakeEdges(), EQUAL PARAMETERS OF DIFFERENT VERTICES");
1527       continue;
1528     }
1529     TopoDS_Edge EE=TopoDS::Edge(NewEdge);
1530     myBuilder.Range (EE,U1,U2);
1531
1532     TopoDS_Edge NEdge = TopoDS::Edge(NewEdge);
1533     myBuilder.SameParameter(NEdge,Standard_False);
1534
1535     Standard_Real tol = 1.0e-2;
1536     Standard_Boolean flag = BRep_Tool::SameParameter(NEdge);
1537     if (!flag) {
1538       BRepLib::SameParameter(NEdge,tol);
1539     }
1540     NE.Append(NEdge.Oriented(E.Orientation()));
1541   }
1542 }
1543
1544 //=======================================================================
1545 //function : MergeEqualEdges
1546 //purpose  : find equal edges,  choose  ones  to  keep and make
1547 //           them have pcurves on all faces they are shared by
1548 //=======================================================================
1549
1550 void Partition_Spliter::MergeEqualEdges (const TopTools_ListOfShape& LSE)
1551 {
1552   // find equal edges
1553   // map: edge - equal edges
1554   TopTools_DataMapOfShapeListOfShape EEM( LSE.Extent() );
1555   findEqual (LSE, LSE, 0, EEM, myEqualEdges);
1556
1557   TopTools_ListOfShape EEL; // list of equal edges
1558   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itM (EEM);
1559   for ( ; itM.More(); itM.Next()) {
1560     EEL = itM.Value();
1561     EEL.Append( itM.Key() );
1562
1563     // choose an edge to keep, section edges have priority
1564     TopoDS_Edge EKeep;
1565     TopTools_ListIteratorOfListOfShape itEE (EEL);
1566     for (; itEE.More(); itEE.Next()) {
1567       EKeep = TopoDS::Edge( itEE.Value() );
1568       const TopoDS_Edge& EKeepOrig = TopoDS::Edge( myImagesEdges.Root( EKeep ));
1569       if (myInter3d.IsSectionEdge( EKeepOrig ))
1570         break;
1571     }
1572
1573     // update edge images and build pcurves
1574     Standard_Real f,l, tol;
1575     for (itEE.Initialize (EEL); itEE.More(); itEE.Next()) {
1576       const TopoDS_Edge& E = TopoDS::Edge( itEE.Value() );
1577       if ( E.IsSame( EKeep ))
1578         continue;
1579
1580       // 1. build pcurves of the kept edge on faces where replaced edges exist
1581       const TopoDS_Edge& EReplOrig = TopoDS::Edge( myImagesEdges.Root( E ));
1582       TopTools_ListOfShape FL;
1583       FL = myAsDes->Ascendant( EReplOrig );
1584       Standard_Integer iFace, iFirstSectionFace = FL.Extent() + 1;
1585       // add faces where the replaced edge is a section edge
1586       if (myInter3d.IsSectionEdge( EReplOrig )) {
1587         TopTools_ListIteratorOfListOfShape seIt;
1588         seIt.Initialize( myInter3d.SectionEdgeFaces ( EReplOrig ));
1589         for ( ; seIt.More(); seIt.Next())
1590           FL.Append( seIt.Value() );
1591       }
1592       // loop on faces
1593       TopTools_ListIteratorOfListOfShape itF (FL);
1594       for ( iFace = 1 ; itF.More(); itF.Next(), ++iFace ) {
1595         const TopoDS_Face& F = TopoDS::Face( itF.Value());
1596
1597         Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( EKeep, F, f,l);
1598         if (pc.IsNull()) {
1599           Handle(Geom_Curve) C3d = BRep_Tool::Curve( EKeep, f, l);
1600           C3d = new Geom_TrimmedCurve( C3d, f,l);
1601           pc = TopOpeBRepTool_CurveTool::MakePCurveOnFace (F,C3d,tol);
1602           if (pc.IsNull()) {
1603             MESSAGE (" CANT BUILD PCURVE ");
1604           }
1605           myBuilder.UpdateEdge( EKeep, pc, F, tol);
1606         }
1607
1608         if (iFace >= iFirstSectionFace ||
1609             !BRep_Tool::IsClosed( EReplOrig, F ))
1610           continue;
1611
1612         // build the second pcurve for a seam
1613         TopoDS_Vertex V = TopExp::FirstVertex( EKeep );
1614         Standard_Real Ukeep = BRep_Tool::Parameter( V, EKeep );
1615         Standard_Real Urepl = BRep_Tool::Parameter( V, E );
1616
1617         TopoDS_Edge EReplRev = E;
1618         EReplRev.Reverse();
1619         Handle(Geom2d_Curve) pcRepl1 = BRep_Tool::CurveOnSurface( E, F, f,l);
1620         Handle(Geom2d_Curve) pcRepl2 = BRep_Tool::CurveOnSurface( EReplRev, F, f,l);
1621
1622         gp_Pnt2d p1r, p2r, pk;
1623         p1r = pcRepl1->Value( Urepl );
1624         p2r = pcRepl2->Value( Urepl );
1625         pk  = pc->Value( Ukeep );
1626
1627         // suppose that pk is equal to either p1r or p2r
1628         Standard_Boolean isUPeriod =
1629           ( Abs( p1r.X() - p2r.X() ) > Abs( p1r.Y() - p2r.Y() ));
1630         Standard_Boolean is1Equal;
1631         if (isUPeriod)
1632           is1Equal = ( Abs( p1r.X() - pk.X() ) < Abs( p2r.X() - pk.X() ));
1633         else
1634           is1Equal = ( Abs( p1r.Y() - pk.Y() ) < Abs( p2r.Y() - pk.Y() ));
1635
1636         Handle(Geom2d_Curve) pc2 = Handle(Geom2d_Curve)::DownCast
1637           ( pc->Translated( pk, is1Equal ? p2r : p1r ) );
1638
1639         if (E.Orientation() == TopAbs_REVERSED)
1640           is1Equal = !is1Equal;
1641
1642         if (is1Equal)
1643           myBuilder.UpdateEdge( EKeep, pc, pc2, F, tol);
1644         else
1645           myBuilder.UpdateEdge( EKeep, pc2, pc, F, tol);
1646
1647       } // loop on a Faces where a replaced edge exists
1648
1649
1650       // 2. update edge images according to replacement
1651       if (myImagesEdges.HasImage( E ))
1652         myImagesEdges.Remove( E );
1653       myImagesEdges.Bind( E, EKeep );
1654
1655     } // loop on a list of equal edges EEL
1656   } // loop on a map of equal edges EEM
1657 }
1658
1659 //=======================================================================
1660 //function : KeepShapesInside
1661 //purpose  : remove shapes that are outside of S from resul
1662 //=======================================================================
1663
1664 void Partition_Spliter::KeepShapesInside (const TopoDS_Shape& S)
1665 {
1666   TopoDS_Iterator it;
1667   if (S.ShapeType() < TopAbs_SOLID) { // compound or compsolid
1668     for (it.Initialize( S ); it.More(); it.Next())
1669       KeepShapesInside( it.Value());
1670     return;
1671   }
1672
1673   Standard_Boolean isTool = Standard_False;
1674   if (!myImageShape.HasImage( S )) {
1675     isTool = CheckTool( S );
1676     if (!isTool) return;
1677   }
1678
1679   // build map of internal faces
1680   TopTools_IndexedMapOfShape MIF;
1681   TopoDS_Shape IntFacesComp = FindFacesInside( S, Standard_False, Standard_True);
1682   TopExp::MapShapes( IntFacesComp, TopAbs_FACE, MIF );
1683
1684   TopoDS_Compound C;
1685   myBuilder.MakeCompound(C);
1686
1687   TopAbs_ShapeEnum anInternalShapeType = TopAbs_SHAPE;
1688   if (!MIF.IsEmpty())
1689   {
1690     // leave in the result only those shapes having a face in MIF
1691     for (it.Initialize( myShape ); it.More(); it.Next()) {
1692       const TopoDS_Shape & aResShape = it.Value();
1693       TopExp_Explorer expResF( aResShape, TopAbs_FACE );
1694       for (; expResF.More(); expResF.Next()) {
1695         if ( MIF.Contains( expResF.Current())) {
1696           myBuilder.Add( C, aResShape );
1697           if (aResShape.ShapeType() < anInternalShapeType)
1698             anInternalShapeType = aResShape.ShapeType();
1699           break;
1700         }
1701       }
1702     }
1703   }
1704
1705   // may be S was not split by internal faces then it is missing
1706   // in myShape, add it
1707   if (!isTool &&
1708       (anInternalShapeType > TopAbs_SOLID || S.ShapeType() > TopAbs_SOLID))
1709   {
1710     TopTools_IndexedMapOfShape MSF; // map of split faces of S
1711     TopExp::MapShapes( myImageShape.Image(S).First(), TopAbs_FACE, MSF);
1712
1713     // find a shape having all faces in MSF
1714     for (it.Initialize( myShape ); it.More(); it.Next()) {
1715       TopExp_Explorer expResF( it.Value(), TopAbs_FACE );
1716       for (; expResF.More(); expResF.Next()) {
1717         if (! MSF.Contains( expResF.Current()))
1718           break;
1719       }
1720       if (! expResF.More()) {
1721         myBuilder.Add( C, it.Value() );
1722         break;
1723       }
1724     }
1725   }
1726
1727   myShape = C;
1728 }
1729
1730 //=======================================================================
1731 //function : RemoveShapesInside
1732 //purpose  : remove shapes that are inside S from resul
1733 //=======================================================================
1734
1735 void Partition_Spliter::RemoveShapesInside (const TopoDS_Shape& S)
1736 {
1737   TopoDS_Iterator it;
1738   if (S.ShapeType() < TopAbs_SOLID) { // compound or compsolid
1739     for (it.Initialize( S ); it.More(); it.Next())
1740       RemoveShapesInside( it.Value());
1741     return;
1742   }
1743   Standard_Boolean isTool = Standard_False;
1744   if (!myImageShape.HasImage( S )) {
1745     isTool = CheckTool( S );
1746     if (!isTool) return;
1747   }
1748
1749   TopoDS_Shape IntFacesComp = FindFacesInside( S, Standard_False, Standard_True);
1750   TopTools_IndexedMapOfShape MIF; // map of internal faces
1751   TopExp::MapShapes( IntFacesComp, TopAbs_FACE, MIF);
1752
1753   if (MIF.IsEmpty()) return;
1754
1755   // add to MIF split faces of S
1756   if (myImageShape.HasImage(S))
1757     TopExp::MapShapes( myImageShape.Image(S).First(), TopAbs_FACE, MIF);
1758
1759   // leave in the result only those shapes not having all face in MIF
1760
1761   TopoDS_Compound C;
1762   myBuilder.MakeCompound(C);
1763
1764   // RMF : faces of removed shapes that encounter once
1765   TopTools_MapOfShape RFM;
1766
1767   for (it.Initialize( myShape ); it.More(); it.Next()) {
1768
1769     TopExp_Explorer expResF( it.Value(), TopAbs_FACE );
1770     for (; expResF.More(); expResF.Next())
1771       if (!MIF.Contains( expResF.Current()))
1772         break;
1773
1774     if (expResF.More())
1775       // add shape to result
1776       myBuilder.Add( C, it.Value() );
1777     else
1778       // add faces of a removed shape to RFM
1779       for (expResF.ReInit(); expResF.More(); expResF.Next()) {
1780         const TopoDS_Shape& F = expResF.Current();
1781         if ( ! RFM.Remove ( F ))
1782           RFM.Add( F );
1783       }
1784   }
1785
1786   if (!isTool) {
1787
1788     // rebuild S, it must remain in the result
1789
1790     Standard_Boolean isClosed = Standard_False;
1791     switch (S.ShapeType()) {
1792     case TopAbs_SOLID :
1793       isClosed = Standard_True; break;
1794     case TopAbs_SHELL: {
1795       TopTools_IndexedDataMapOfShapeListOfShape MEF;
1796       TopExp::MapShapesAndAncestors(S, TopAbs_EDGE, TopAbs_FACE, MEF);
1797       Standard_Integer i;
1798       for (i=1;  isClosed && i<=MEF.Extent();  ++i)
1799         isClosed = ( MEF(i).Extent() != 1 );
1800       break;
1801     }
1802     default:
1803       isClosed = Standard_False;
1804     }
1805     if (isClosed) {
1806
1807       // add to a new shape external faces of removed shapes, ie those in RFM
1808
1809       TopoDS_Shell Shell;
1810       myBuilder.MakeShell( Shell );
1811
1812       // exclude redundant internal face with edges encounterd only once
1813       TopTools_IndexedDataMapOfShapeListOfShape MEF;
1814       TopTools_MapIteratorOfMapOfShape itF (RFM);
1815       for ( ; itF.More(); itF.Next())
1816         TopExp::MapShapesAndAncestors(itF.Key(), TopAbs_EDGE, TopAbs_FACE, MEF);
1817
1818       // add only faces forming a closed shell
1819       for (itF.Reset() ; itF.More(); itF.Next())
1820       {
1821         TopExp_Explorer expE (itF.Key(), TopAbs_EDGE);
1822         for (; expE.More(); expE.Next())
1823           if (MEF.FindFromKey(expE.Current()).Extent() == 1)
1824             break;
1825         if (!expE.More())
1826           myBuilder.Add( Shell, itF.Key());
1827       }
1828
1829       if (S.ShapeType() == TopAbs_SOLID) {
1830         TopoDS_Solid Solid;
1831         myBuilder.MakeSolid( Solid );
1832         myBuilder.Add (Solid, Shell);
1833         myBuilder.Add (C, Solid);
1834       }
1835       else
1836         myBuilder.Add (C, Shell);
1837     }
1838     else {
1839       if (myImageShape.HasImage( S )) {
1840         for (it.Initialize( myImageShape.Image(S).First()); it.More(); it.Next())
1841           myBuilder.Add (C, it.Value());
1842       }
1843     }
1844   }
1845
1846   myShape = C;
1847 }
1848
1849 //=======================================================================
1850 //function : CheckTool
1851 //purpose  : Return True if <S>  is  a tool shape. Prepare tool
1852 //           faces of <S> for the search of internal faces.
1853 //=======================================================================
1854
1855 Standard_Boolean Partition_Spliter::CheckTool(const TopoDS_Shape& S)
1856 {
1857   // suppose S has not an image
1858
1859   Standard_Boolean isTool = Standard_False;
1860   TopoDS_Compound C;
1861   myBuilder.MakeCompound( C );
1862
1863   TopExp_Explorer expF( S, TopAbs_FACE);
1864   for (; expF.More(); expF.Next()) {
1865
1866     const TopoDS_Face& F = TopoDS::Face( expF.Current() );
1867     if (myMapTools.Contains( F ))
1868       isTool = Standard_True;
1869     else
1870       continue;
1871
1872     if (myImagesFaces.HasImage( F )) {
1873       // F has been reconstructed
1874       TopAbs_Orientation Fori = F.Orientation();
1875       TopTools_ListOfShape LNF;
1876       myImagesFaces.LastImage( F, LNF);
1877       TopTools_ListIteratorOfListOfShape itF (LNF);
1878       for ( ; itF.More(); itF.Next())
1879         myBuilder.Add( C, itF.Value().Oriented(Fori) );
1880       continue;
1881     }
1882
1883     Standard_Boolean hasSectionE = myInter3d.HasSectionEdge( F );
1884     Standard_Boolean hasNewE     = myAsDes->HasDescendant( F );
1885     if (!hasSectionE && !hasNewE)
1886     {
1887       // F intersects nothing
1888       myBuilder.Add( C, F );
1889       continue;
1890     }
1891
1892     // make an image for F
1893
1894     TopoDS_Face NF = F;
1895     NF.Orientation(TopAbs_FORWARD);
1896     NF = TopoDS::Face( NF.EmptyCopied() ); // make a copy
1897     TopoDS_Wire NW;
1898     myBuilder.MakeWire( NW );
1899
1900     // add edges, as less as possible
1901     TopTools_ListOfShape NEL;
1902     TopTools_ListIteratorOfListOfShape itNE;
1903     if (hasSectionE) {
1904       // add section edges
1905       TopExp_Explorer expE;
1906       for ( ; expE.More(); expE.Next()) {
1907         if (! myImagesEdges.HasImage( expE.Current() ))
1908           continue;
1909         myImagesEdges.LastImage( expE.Current(), NEL );
1910         for ( itNE.Initialize( NEL ); itNE.More(); itNE.Next())
1911           myBuilder.Add ( NW, itNE.Value());
1912       }
1913     }
1914     if (hasNewE) {
1915       // add new adges
1916       NEL = myAsDes->Descendant( F );
1917       for ( itNE.Initialize( NEL ); itNE.More(); itNE.Next()) {
1918         TopTools_ListOfShape SEL; // splits
1919         myImagesEdges.LastImage( itNE.Value(), SEL );
1920         TopTools_ListIteratorOfListOfShape itSE (SEL);
1921         for ( ; itSE.More(); itSE.Next())
1922           myBuilder.Add ( NW, itSE.Value());
1923       }
1924     }
1925     myBuilder.Add( NF, NW );
1926     myBuilder.Add (C, NF);
1927
1928     NF.Orientation( F.Orientation() ); // NF is most probably invalid
1929     myImagesFaces.Bind (F, NF);
1930   }
1931   if (isTool)
1932     myImageShape.Bind (S, C);
1933
1934   return isTool;
1935 }
1936
1937 //=======================================================================
1938 //function : IsInside
1939 //purpose  : Return True if the first vertex of S1 inside S2.
1940 //           If S1.IsNull(), check infinite point against S2.
1941 //=======================================================================
1942
1943 Standard_Boolean Partition_Spliter::IsInside (const TopoDS_Shape& theS1,
1944                                               const TopoDS_Shape& theS2)
1945 {
1946   BRepClass3d_SolidClassifier aClassifier( theS2 );
1947
1948   TopExp_Explorer expl( theS1, TopAbs_VERTEX );
1949   if (!expl.More())
1950     aClassifier.PerformInfinitePoint( ::RealSmall());
1951   else
1952   {
1953     const TopoDS_Vertex & aVertex = TopoDS::Vertex( expl.Current() );
1954     aClassifier.Perform (BRep_Tool::Pnt( aVertex ),
1955                          BRep_Tool::Tolerance( aVertex ));
1956   }
1957
1958   return ( aClassifier.State() == TopAbs_IN );
1959 }
1960
1961 //=======================================================================
1962 //function : GetOriginalShape
1963 //purpose  : Return the  shape  aShape  originates from. aShape
1964 //           should be a face or more complex result shape
1965 //=======================================================================
1966
1967 TopoDS_Shape Partition_Spliter::GetOriginalShape(const TopoDS_Shape& theShape) const
1968 {
1969   TopoDS_Shape anOrigShape;
1970
1971   TopExp_Explorer expl( theShape, TopAbs_FACE);
1972   if (expl.More())
1973   {
1974
1975     TopoDS_Shape aFace = expl.Current();
1976     if (myImagesFaces.IsImage( aFace ))
1977       aFace = myImagesFaces.Root( aFace );
1978     anOrigShape = myFaceShapeMap.Find( aFace );
1979   }
1980   return anOrigShape;
1981 }
1982
1983 //=======================================================================
1984 //function : FindToolsToReconstruct
1985 //purpose  : find and store  as  objects  tools which interfere
1986 //           with  solids   or   are   inside   solids  without
1987 //           an interference
1988 //=======================================================================
1989
1990 void Partition_Spliter::FindToolsToReconstruct()
1991 {
1992   if (myMapTools.IsEmpty())
1993     return;
1994
1995   Standard_Integer nbFoundTools = 0;
1996
1997   // build edge - face map in order to detect interference with section edges
1998   TopTools_IndexedDataMapOfShapeListOfShape EFM;
1999   TopTools_MapIteratorOfMapOfShape aMapIt;
2000   for (aMapIt.Initialize(myMapTools); aMapIt.More(); aMapIt.Next())
2001     TopExp::MapShapesAndAncestors( aMapIt.Key(), TopAbs_EDGE, TopAbs_FACE, EFM);
2002   for (aMapIt.Initialize(myMapFaces); aMapIt.More(); aMapIt.Next())
2003     TopExp::MapShapesAndAncestors( aMapIt.Key(), TopAbs_EDGE, TopAbs_FACE, EFM);
2004
2005   TopTools_MapOfShape aCurrentSolids, aCheckedShapes;
2006
2007   // faces cut by new edges
2008   TopTools_MapOfShape & aSectionFaces = myInter3d.TouchedFaces();
2009
2010   // keep solids interfering with each other in aCurrentSolids map
2011   // and add tool faces intersecting solids as object shapes
2012
2013   TopTools_ListIteratorOfListOfShape itS, itF, itCF, itE;
2014   for (itS.Initialize( myListShapes ); itS.More(); itS.Next()) {
2015     TopExp_Explorer expSo (itS.Value(), TopAbs_SOLID);
2016     for (; expSo.More(); expSo.Next()) {
2017
2018       // check if a solid has been already processed
2019       const TopoDS_Shape & aSo = expSo.Current();
2020       if (!aCheckedShapes.Add( aSo ))
2021         continue;
2022       aCurrentSolids.Add( aSo );
2023
2024       // faces to check
2025       TopTools_ListOfShape aFacesToCheck;
2026       TopExp_Explorer exp( aSo, TopAbs_FACE );
2027       for ( ; exp.More(); exp.Next())
2028         aFacesToCheck.Append ( exp.Current());
2029
2030       // add other shapes interefering with a solid.
2031       // iterate faces to check while appending new ones
2032       for (itCF.Initialize (aFacesToCheck) ; itCF.More(); itCF.Next())
2033       {
2034         const TopoDS_Shape& aCheckFace = itCF.Value();
2035 //         if (!aCheckedShapes.Add( aCheckFace ))
2036 //           continue;
2037
2038         // find faces interfering with aCheckFace
2039         TopTools_ListOfShape anIntFaces;
2040
2041         // ** 1. faces intersecting aCheckFace with creation of new edges on it
2042         if ( myAsDes->HasDescendant( aCheckFace ))
2043         {
2044           // new edges on aCheckFace
2045           const TopTools_ListOfShape& NEL = myAsDes->Descendant( aCheckFace );
2046           for (itE.Initialize( NEL); itE.More(); itE.Next())
2047           {
2048             const TopoDS_Shape & aNewEdge = itE.Value();
2049             if (!aCheckedShapes.Add( aNewEdge ))
2050               continue;
2051
2052             // faces interfering by aNewEdge
2053             itF.Initialize (myAsDes->Ascendant( aNewEdge ));
2054             for (; itF.More(); itF.Next())
2055               if (aCheckFace != itF.Value())
2056                 anIntFaces.Append( itF.Value() );
2057
2058             // ** 2. faces having section edge aNewEdge on aFacesToCheck
2059             if (EFM.Contains( aNewEdge))
2060             {
2061               itF.Initialize ( EFM.FindFromKey (itE.Value()));
2062               for (; itF.More(); itF.Next())
2063                 if (aCheckFace != itF.Value())
2064                   anIntFaces.Append( itF.Value() );
2065             }
2066           }
2067         }
2068
2069         // ** 3. faces cut by edges of aCheckFace
2070         TopExp_Explorer expE (aCheckFace, TopAbs_EDGE);
2071         for ( ; expE.More(); expE.Next())
2072         {
2073           const TopoDS_Shape & aCheckEdge = expE.Current();
2074           if (aCheckedShapes.Add( aCheckEdge ) &&
2075               myInter3d.IsSectionEdge( TopoDS::Edge( aCheckEdge )))
2076           {
2077             itF.Initialize( myInter3d.SectionEdgeFaces( TopoDS::Edge( aCheckEdge )));
2078             for (; itF.More(); itF.Next())
2079               if (aCheckFace != itF.Value())
2080                 anIntFaces.Append( itF.Value() );
2081           }
2082         }
2083
2084         // process faces interfering with aCheckFace and shapes they
2085         // belong to
2086         for (itF.Initialize (anIntFaces); itF.More(); itF.Next())
2087         {
2088           const TopoDS_Shape & F = itF.Value();
2089           if (! aCheckedShapes.Add( F ))
2090             continue;
2091
2092           Standard_Boolean isTool = myMapTools.Contains( F );
2093           if (isTool &&
2094               myFaceShapeMap( aCheckFace ).ShapeType() == TopAbs_SOLID )
2095           {
2096             // a tool interfering with a solid
2097             if (aSectionFaces.Contains( F ))
2098               AddShape( F );
2099             ++ nbFoundTools;
2100             if (nbFoundTools == myMapTools.Extent())
2101               return;
2102           }
2103
2104           const TopoDS_Shape & S = myFaceShapeMap( F );
2105           if (aCheckedShapes.Add( S ))
2106           {
2107             // a new shape interefering with aCurrentSolids is found
2108             if (!isTool && S.ShapeType() == TopAbs_SOLID)
2109               aCurrentSolids.Add ( S );
2110             // add faces to aFacesToCheck list
2111             for ( exp.Init( S, TopAbs_FACE ); exp.More(); exp.Next())
2112               aFacesToCheck.Append ( exp.Current() );
2113           }
2114         }
2115       } // loop on aFacesToCheck
2116
2117       // Here aCurrentSolids contains all solids interfering with each other.
2118       // aCheckedShapes contains all faces belonging to shapes included
2119       // in or interfering with aCurrentSolids or previously checked solids.
2120       // Test if tool faces that do not interefere with other shapes are
2121       // wrapped by any of aCurrentSolids
2122
2123       TopTools_MapIteratorOfMapOfShape aSolidIt (aCurrentSolids);
2124       for ( ; aSolidIt.More(); aSolidIt.Next())
2125       {
2126         const TopoDS_Shape & aSolid = aSolidIt.Key();
2127         TopTools_MapOfShape aCheckedTools( myMapTools.Extent() );
2128
2129         TopTools_MapIteratorOfMapOfShape aToolIt (myMapTools);
2130         for ( ; aToolIt.More(); aToolIt.Next())
2131         {
2132           const TopoDS_Shape & aToolFace = aToolIt.Key();
2133           if (aCheckedShapes.Contains( aToolFace ) || // already found
2134               aCheckedTools.Contains( aToolFace ))    // checked against aSolid
2135             continue;
2136
2137           const TopoDS_Shape & aToolShape = myFaceShapeMap( aToolFace );
2138           TopExp_Explorer aToolFaceIt( aToolShape, TopAbs_FACE );
2139
2140           Standard_Boolean isInside = IsInside( aToolShape, aSolid );
2141           for ( ; aToolFaceIt.More(); aToolFaceIt.Next() )
2142           {
2143             const TopoDS_Shape & aTool = aToolFaceIt.Current();
2144             aCheckedTools.Add( aTool );
2145             if (isInside)
2146             {
2147               if (aSectionFaces.Contains( aTool ))
2148                 AddShape( aTool );
2149               ++ nbFoundTools;
2150               if (nbFoundTools == myMapTools.Extent())
2151                 return;
2152               aCheckedShapes.Add( aTool );
2153             }
2154           }
2155         }
2156       }
2157
2158     } // loop on solid shapes
2159   }
2160 }