src/PARTITION/Partition_Spliter.cxx

   1 using namespace std;
   2 //  File      : Partition_Spliter.cxx
   3 //  Created   : Thu Aug 02 16:07:39 2001
   4 //  Author    : Benedicte MARTIN
   5 //  Project   : SALOME
   6 //  Module    : SALOMEGUI
   7 //  Copyright : Open CASCADE
   8 //  $Header$
   9
  10 #include "Partition_Spliter.ixx"
  11 #include "Partition_Inter2d.hxx"
  12 #include "Partition_Inter3d.hxx"
  13 #include "Partition_Loop2d.hxx"
  14 #include "Partition_Loop3d.hxx"
  15
  16 #include "utilities.h"
  17
  18 #include <TopExp_Explorer.hxx>
  19 #include <TopExp.hxx>
  20 #include <Precision.hxx>
  21 #include <TopAbs_Orientation.hxx>
  22
  23 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  24 #include <TopTools_DataMapOfShapeListOfShape.hxx>
  25 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
  26 #include <TopTools_IndexedMapOfShape.hxx>
  27 #include <TopTools_ListIteratorOfListOfShape.hxx>
  28 #include <TopTools_ListOfShape.hxx>
  29 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  30 #include <TopTools_SequenceOfShape.hxx>
  31
  32 #include <gp_Pnt2d.hxx>
  33 #include <gp_Pnt.hxx>
  34 #include <gp_Vec.hxx>
  35 #include <Geom2d_Curve.hxx>
  36 #include <Geom_Curve.hxx>
  37 #include <Geom_Surface.hxx>
  38 #include <Geom_TrimmedCurve.hxx>
  39
  40 #include <TopoDS.hxx>
  41 #include <TopoDS_Compound.hxx>
  42 #include <TopoDS_Edge.hxx>
  43 #include <TopoDS_Face.hxx>
  44 #include <TopoDS_Iterator.hxx>
  45 #include <TopoDS_Shell.hxx>
  46 #include <TopoDS_Solid.hxx>
  47 #include <TopoDS_Vertex.hxx>
  48 #include <TopoDS_Wire.hxx>
  49
  50 #include <BRep_Tool.hxx>
  51 #include <BRepLib.hxx>
  52 #include <BRepBndLib.hxx>
  53
  54 #include <stdio.h>
  55 #include <Extrema_ExtPC.hxx>
  56 #include <GeomAdaptor_Curve.hxx>
  57 #include <TopOpeBRepTool_CurveTool.hxx>
  58
  59 #ifdef DEB
  60 #define DRAW 0
  61 #endif
  62
  63 #ifdef DRAW
  64 #include <DBRep.hxx>
  65 Standard_IMPORT Standard_Boolean AffichInter3d ;
  66 Standard_IMPORT Standard_Boolean AffichInter2d ;
  67 Standard_IMPORT Standard_Boolean AffichVertex;
  68 Standard_IMPORT Standard_Boolean AffichFace;
  69 Standard_IMPORT Standard_Boolean AffichWire;
  70 Standard_IMPORT Standard_Boolean SelectFace;
  71
  72 static char* names = new char[100];
  73
  74 #endif
  75
  76 //=======================================================================
  77 //function : Partition_Spliter
  78 //purpose  : constructor
  79 //=======================================================================
  80
  81 Partition_Spliter::Partition_Spliter()
  82 {
  83   myAsDes = new BRepAlgo_AsDes;
  84   Clear();
  85 }
  86
  87 //=======================================================================
  88 //function : AddTool
  89 //purpose  : add cutting tool that will _NOT_ be in result
  90 //=======================================================================
  91
  92 void Partition_Spliter::AddTool(const TopoDS_Shape& S)
  93 {
  94   for (TopExp_Explorer exp(S,TopAbs_FACE); exp.More(); exp.Next())
  95     myMapTools.Add(exp.Current());
  96 }
  97
  98 //=======================================================================
  99 //function : AddShape
 100 //purpose  : add object Shape to be splited
 101 //=======================================================================
 102
 103 void Partition_Spliter::AddShape(const TopoDS_Shape& S)
 104 {
 105   if (S.ShapeType() < TopAbs_SOLID) { // compound or compsolid
 106     TopoDS_Iterator it (S);
 107     for (; it.More(); it.Next())
 108       AddShape( it.Value());
 109     return;
 110   }
 111
 112   TopExp_Explorer exp(S,TopAbs_FACE);
 113   if (!exp.More()) { // do not split edges and vertices
 114     //myBuilder.Add( myShape, S );
 115     return;
 116   }
 117
 118   myListShapes.Append(S);
 119
 120   for (; exp.More(); exp.Next()) {
 121     myFaceShapeMap.Bind( exp.Current(), S );
 122     myMapFaces.Add(exp.Current());
 123     myImagesFaces.SetRoot(exp.Current());
 124   }
 125 }
 126
 127 //=======================================================================
 128 //function : Shape
 129 //purpose  : return resulting compound
 130 //=======================================================================
 131
 132 TopoDS_Shape Partition_Spliter::Shape() const
 133 {
 134   return myShape;
 135 }
 136
 137 //=======================================================================
 138 //function : Clear
 139 //purpose  : clear fields
 140 //=======================================================================
 141
 142 void Partition_Spliter::Clear()
 143 {
 144   myDoneStep = TopAbs_SHAPE;
 145
 146   myListShapes.Clear();
 147   myMapFaces.Clear();
 148   myMapTools.Clear();
 149   myFaceShapeMap.Clear();
 150
 151   myNewSection.Clear();
 152
 153   myAsDes->Clear();
 154   myImagesFaces.Clear();
 155   myImagesEdges.Clear();
 156   myImageShape.Clear();
 157
 158   myInter3d = Partition_Inter3d(myAsDes);
 159
 160   myAddedFacesMap.Clear();
 161
 162   myInternalFaces.Clear();
 163 }
 164
 165 //=======================================================================
 166 //function : Compute
 167 //purpose  : produce a result
 168 //=======================================================================
 169
 170 void Partition_Spliter::Compute(const TopAbs_ShapeEnum Limit)
 171 {
 172   if ((Limit != TopAbs_SHAPE && myDoneStep == Limit) ||
 173       (Limit == TopAbs_SHAPE && myDoneStep == TopAbs_SOLID))
 174     return;
 175
 176   myBuilder.MakeCompound( myShape );
 177
 178   TopTools_MapIteratorOfMapOfShape it;
 179   TopTools_ListIteratorOfListOfShape itl;
 180   TopExp_Explorer exp;
 181
 182   if (myDoneStep > TopAbs_VERTEX) {
 183
 184     TopTools_ListOfShape aListFaces;
 185     aListFaces = myImagesFaces.Roots();
 186     for (it.Initialize(myMapTools); it.More(); it.Next())
 187       aListFaces.Append(it.Key());
 188
 189     //-----------------------------------------------
 190     // Intersection between faces
 191     //-----------------------------------------------
 192     // result is in myAsDes as a map Face - list of new edges;
 193     // special care is done for section edges, same domain faces and vertices:
 194     // data about them is inside myInter3d
 195
 196     myInter3d.CompletPart3d(aListFaces, myFaceShapeMap);
 197
 198     TopTools_MapOfShape& Modif = myInter3d.TouchedFaces();
 199     TopTools_MapOfShape& NewEdges = myInter3d.NewEdges();
 200     Handle(BRepAlgo_AsDes) SectionEdgesAD = myInter3d.SectionEdgesAD();
 201
 202 #ifdef DRAW
 203     if (AffichInter3d) {
 204       Standard_Integer i=0;
 205       for (it.Initialize(NewEdges); it.More(); it.Next(), i++) {
 206         sprintf(names,"e_%d",i);
 207         cout << "donly " << names << endl;
 208         DBRep::Set(names,it.Key());
 209       }
 210     }
 211 #endif
 212     //if (Modif.IsEmpty()) return;
 213
 214     // -----------------------------------------------
 215     // store tools intersecting solids as object shapes,
 216     // they must split into faces too
 217     // -----------------------------------------------
 218
 219     // build edge - face map for tool faces
 220     TopTools_IndexedDataMapOfShapeListOfShape EFM;
 221     for (it.Initialize(myMapTools); it.More(); it.Next())
 222       TopExp::MapShapesAndAncestors( it.Key(), TopAbs_EDGE, TopAbs_FACE, EFM);
 223
 224     TopTools_MapOfShape checkedEdgeMap;
 225     for (itl.Initialize( myListShapes ); itl.More(); itl.Next()) {
 226       TopExp_Explorer expSo (itl.Value(), TopAbs_SOLID);
 227       for (; expSo.More(); expSo.Next()) {
 228
 229         TopTools_ListOfShape checkFL;  // faces to check
 230         for ( exp.Init( expSo.Current(), TopAbs_FACE); exp.More(); exp.Next())
 231           checkFL.Append ( exp.Current());
 232
 233         // iterate a list while appending new items
 234         TopTools_ListIteratorOfListOfShape itF, itCF;
 235         for (itCF.Initialize (checkFL) ; itCF.More(); itCF.Next()) {
 236           const TopoDS_Shape& F = itCF.Value();
 237           if ( myAsDes->HasDescendant( F )) {
 238             // new edges on face to check
 239             const TopTools_ListOfShape& NEL = myAsDes->Descendant( F );
 240             TopTools_ListIteratorOfListOfShape itE (NEL);
 241             for (; itE.More(); itE.Next()) {
 242               if (checkedEdgeMap.Add( itE.Value() )) {
 243                 // intersected faces originating an edge
 244                 itF.Initialize (myAsDes->Ascendant( itE.Value() ));
 245                 for (; itF.More(); itF.Next()) {
 246                   if (!myMapFaces.Contains( itF.Value())) {
 247                     AddShape( itF.Value() );
 248                     checkFL.Append( itF.Value() );
 249                   }
 250                 }
 251                 // faces having section edges on F
 252                 if (EFM.Contains( itE.Value()))
 253                   itF.Initialize ( EFM.FindFromKey (itE.Value()));
 254                 for (; itF.More(); itF.Next()) {
 255                   if (!myMapFaces.Contains( itF.Value())) {
 256                     AddShape( itF.Value() );
 257                     checkFL.Append( itF.Value() );
 258                   }
 259                 }
 260               }
 261             }
 262           }
 263           // find faces cut by edges of F
 264           TopExp_Explorer expE(F, TopAbs_EDGE);
 265           for (; expE.More();expE.Next()) {
 266             if ( SectionEdgesAD->HasAscendant( expE.Current() )
 267                 && checkedEdgeMap.Add( expE.Current() )) {
 268               itF.Initialize( SectionEdgesAD->Ascendant( expE.Current()) );
 269               for (; itF.More(); itF.Next()) {
 270                 if (!myMapFaces.Contains( itF.Value())) {
 271                   AddShape( itF.Value() );
 272                   checkFL.Append( itF.Value() );
 273                 }
 274               }
 275             }
 276           }
 277         }
 278       }
 279     }
 280
 281     //-----------------------------------------------
 282     // Intersection of edges
 283     //-----------------------------------------------
 284
 285     // add existing vertices to edges of object faces in myAsDes
 286     TopTools_MapOfShape DoneEM;
 287     for ( it.Initialize(myMapFaces); it.More(); it.Next()) {
 288       const TopoDS_Shape& F  = it.Key();
 289       TopoDS_Face FForward = TopoDS::Face(F.Oriented(TopAbs_FORWARD));
 290       for (exp.Init(FForward,TopAbs_EDGE); exp.More(); exp.Next()) {
 291         const TopoDS_Edge& E = TopoDS::Edge( exp.Current() );
 292         myAsDes->Add(FForward,E);
 293         if (DoneEM.Add(E)) {
 294           TopoDS_Iterator itV(E);
 295           for (; itV.More(); itV.Next()) {
 296             const TopoDS_Vertex& V = TopoDS::Vertex( itV.Value());
 297             myAsDes->Add(E, myInter3d.ReplaceSameDomainV( V, E ));
 298           }
 299         }
 300       }
 301     }
 302
 303     // intersect edges that are descendants of a face in myAsDes
 304     for ( it.Initialize(Modif); it.More(); it.Next()) {
 305       const TopoDS_Face& F  = TopoDS::Face(it.Key());
 306       Partition_Inter2d::CompletPart2d (myAsDes, F, NewEdges);
 307     }
 308     // now myAsDes contains also new vertices made at edge intersection as
 309     // descendant of edges both new and old
 310
 311     myDoneStep = TopAbs_VERTEX;
 312
 313   } //   if (myDoneStep > TopAbs_VERTEX)
 314
 315   if (Limit == TopAbs_VERTEX) {
 316     // add new vertices to myShape
 317     for ( it.Initialize( myInter3d.NewEdges() ); it.More(); it.Next()) {
 318       if (! myAsDes->HasDescendant( it.Key() ))
 319         continue;
 320       itl.Initialize( myAsDes->Descendant( it.Key() ));
 321       for (; itl.More(); itl.Next())
 322         myBuilder.Add ( myShape, itl.Value() );
 323     }
 324     return;
 325   }
 326
 327   if (myDoneStep > TopAbs_EDGE) {
 328
 329     //-----------------------------------------------
 330     // Reconstruction of all the edges.
 331     //-----------------------------------------------
 332
 333     // Add to myAsDes end vertices of new edges and cut new edges
 334     int j=1;
 335     TopTools_MapOfShape& NewEdges = myInter3d.NewEdges();
 336     TopTools_ListOfShape LSE; // all edge splits
 337     for ( it.Initialize(NewEdges); it.More(); it.Next()) {
 338
 339       TopoDS_Vertex V1,V2;
 340       TopoDS_Edge EE = TopoDS::Edge(it.Key());
 341
 342       TopTools_ListOfShape aListV, aListF;
 343       aListV = myAsDes->Descendant(EE); // intersection vertices
 344       aListF = myAsDes->Ascendant(EE);  // intersected faces
 345
 346       if (aListV.IsEmpty())
 347         continue;  // new edge does not intersect any other edge
 348
 349       // one face is Tool, the other is Shape:
 350       if ( (myMapTools.Contains(aListF.First()) && myMapFaces.Contains(aListF.Last()) ) ||
 351           ( myMapFaces.Contains(aListF.First()) && myMapTools.Contains(aListF.Last()) ) )
 352       {
 353         TopExp::Vertices(EE,V1,V2);
 354         Standard_Real Tol = Max (BRep_Tool::Tolerance( V1 ),
 355                                  BRep_Tool::Tolerance( V2 ));
 356
 357         gp_Pnt P1 = BRep_Tool::Pnt(V1);
 358         gp_Pnt P2 = BRep_Tool::Pnt(V2);
 359         Standard_Boolean AddV1 = Standard_True;
 360         Standard_Boolean AddV2 = Standard_True;
 361
 362         // add only if there is no intersection at end vertex
 363         for (itl.Initialize(aListV); itl.More(); itl.Next()) {
 364           const TopoDS_Vertex& Ve = TopoDS::Vertex(itl.Value()) ;
 365           Standard_Real Tol2 = Max ( Tol, BRep_Tool::Tolerance( Ve ));
 366           Tol2 *= Tol2;
 367           gp_Pnt P = BRep_Tool::Pnt(Ve);
 368           if (AddV1 && P.SquareDistance(P1) <= Tol2)
 369             AddV1 = Standard_False;
 370
 371           if (AddV2 && P.SquareDistance(P2) <= Tol2)
 372             AddV2 = Standard_False;
 373         }
 374
 375         if (AddV1) {
 376           aListV.Append(V1);
 377           myAsDes->Add(EE,V1);
 378         }
 379
 380         if (AddV2) {
 381           aListV.Append(V2);
 382           myAsDes->Add(EE,V2);
 383         }
 384       }
 385 #ifdef DRAW
 386       if (AffichVertex) {
 387         for(itl.Initialize(aListV);itl.More();itl.Next(), j++) {
 388           sprintf(names,"v_%d",j);
 389           cout << "donly " << names << endl;
 390           DBRep::Set(names,itl.Value());
 391         }
 392       }
 393 #endif
 394
 395       Standard_Integer NbV=aListV.Extent() ;
 396       if (NbV>1 || (NbV==1 && V1.IsSame(V2)) ) {
 397         // cut new edges
 398         TopTools_ListOfShape LNE;
 399         MakeEdges (EE,aListV, LNE);
 400         myImagesEdges.Bind(EE,LNE);
 401         LSE.Append( LNE );
 402       }
 403     }
 404
 405     // cut old edges
 406     for ( it.Initialize(myMapFaces); it.More(); it.Next()) {
 407       for (exp.Init( it.Key(), TopAbs_EDGE); exp.More(); exp.Next()) {
 408         const TopoDS_Edge& EE = TopoDS::Edge( exp.Current() );
 409         if ( myImagesEdges.HasImage( EE ))
 410           continue;
 411         TopTools_ListOfShape  LNE;
 412         const TopTools_ListOfShape& aListVV = myAsDes->Descendant(EE);
 413         MakeEdges (EE, aListVV, LNE);
 414         myImagesEdges.Bind(EE,LNE);
 415         LSE.Append( LNE );
 416       }
 417     }
 418
 419     MergeEqualEdges( LSE );
 420
 421     myDoneStep = TopAbs_EDGE;
 422
 423   }  //   if (myDoneStep > TopAbs_EDGE)
 424
 425   if (Limit == TopAbs_EDGE) {
 426     // add splits of old edges
 427     TopTools_ListIteratorOfListOfShape itNE;
 428     for (itl.Initialize( myListShapes );itl.More();itl.Next()) {
 429       for ( exp.Init( itl.Value(), TopAbs_EDGE ); exp.More(); exp.Next()) {
 430         itNE.Initialize( myImagesEdges.Image( exp.Current() ));
 431         for ( ; itNE.More(); itNE.Next())
 432           myBuilder.Add ( myShape, itNE.Value() );
 433       }
 434     }
 435     // add splits of new edges
 436     for ( it.Initialize( myInter3d.NewEdges() ); it.More(); it.Next()) {
 437       itNE.Initialize( myImagesEdges.Image( it.Key() ));
 438       for (; itNE.More(); itNE.Next())
 439         myBuilder.Add ( myShape, itNE.Value() );
 440     }
 441     return;
 442   }
 443
 444   // make faces interfering by section edges share the same splits
 445   //ProcessSectionEdges( SectionEdgesAD );
 446
 447
 448   //-----------------------------------------------
 449   // split faces
 450   //-----------------------------------------------
 451
 452   if (myDoneStep > TopAbs_FACE) {
 453
 454     for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 455       TopoDS_Shape FacesComp = MakeFaces ( itl.Value());
 456       // there is a cunning here: myImagesFaces keeps faces made by Loop2d
 457       // but some of them may be replaced with splits of same domain face
 458       // and myImageShape keeps ultimate result
 459       myImageShape.Bind( itl.Value(), FacesComp );
 460     }
 461
 462     myDoneStep = TopAbs_FACE;
 463   }
 464
 465   if (Limit == TopAbs_WIRE ||
 466       Limit == TopAbs_FACE)   {
 467     for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 468       if ( myMapTools.Contains( itl.Value() ))
 469         continue; // no result needed for a tool face
 470       const TopoDS_Shape& FacesComp = myImageShape.Image( itl.Value() ).First();
 471       for ( exp.Init( FacesComp, Limit); exp.More(); exp.Next())
 472         myBuilder.Add ( myShape, exp.Current());
 473     }
 474     return;
 475   }
 476
 477
 478   //-----------------------------------------------
 479   // split solids
 480   //-----------------------------------------------
 481
 482   // solids must remains closed, so process them first
 483   Standard_Boolean makeSolids = (Limit == TopAbs_SHAPE ||
 484                                  Limit < TopAbs_SHELL);
 485
 486   for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 487     if (itl.Value().ShapeType() == TopAbs_SOLID) {
 488       TopTools_ListOfShape NSL;
 489       MakeShells (itl.Value() , NSL);
 490       TopTools_ListIteratorOfListOfShape itS(NSL);
 491       for ( ; itS.More(); itS.Next())
 492         if (makeSolids) {
 493           // make a solid from a shell
 494           TopoDS_Solid Solid;
 495           myBuilder.MakeSolid( Solid );
 496           myBuilder.Add (Solid, itS.Value());
 497           myBuilder.Add (myShape, Solid);
 498         }
 499         else
 500           myBuilder.Add (myShape, itS.Value());
 501     }
 502   }
 503
 504   //-----------------------------------------------
 505   // split shells
 506   //-----------------------------------------------
 507
 508   for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 509     if (itl.Value().ShapeType() == TopAbs_SHELL) {
 510       TopTools_ListOfShape NSL;
 511       MakeShells (itl.Value() , NSL);
 512       TopTools_ListIteratorOfListOfShape itS(NSL);
 513       for ( ; itS.More(); itS.Next())
 514         myBuilder.Add (myShape, itS.Value());
 515     }
 516   }
 517
 518   //-----------------------------------------------
 519   // add split faces
 520   //-----------------------------------------------
 521
 522   for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 523     const TopoDS_Shape& S = itl.Value();
 524     if (S.ShapeType() != TopAbs_FACE ||
 525         myMapTools.Contains( S ))
 526       continue;
 527     TopoDS_Iterator itS( myImageShape.Image(S).First() );
 528     for (; itS.More(); itS.Next())
 529       if (! myAddedFacesMap.Contains( itS.Value() ))
 530         myBuilder.Add (myShape, itS.Value());
 531   }
 532
 533   myDoneStep = makeSolids ? TopAbs_SOLID : TopAbs_SHELL;
 534
 535 }
 536
 537
 538 //=======================================================================
 539 //function : Tri
 540 //purpose  :
 541 //=======================================================================
 542
 543 static void Tri(const TopoDS_Edge&        E,
 544                 TopTools_SequenceOfShape& Seq)
 545 {
 546   Standard_Boolean Invert   = Standard_True;
 547   Standard_Integer NbPoints = Seq.Length();
 548   Standard_Real    U1,U2;
 549   TopoDS_Vertex    V1,V2;
 550
 551   while (Invert) {
 552     Invert = Standard_False;
 553     for ( Standard_Integer i = 1; i < Seq.Length(); i++) {
 554
 555       V1 = TopoDS::Vertex(Seq.Value(i));
 556       V2 = TopoDS::Vertex(Seq.Value(i+1));
 557
 558       V1.Orientation(TopAbs_INTERNAL);
 559       V2.Orientation(TopAbs_INTERNAL);
 560
 561       U1 = BRep_Tool::Parameter(V1,E);
 562       U2 = BRep_Tool::Parameter(V2,E);
 563
 564       if (IsEqual(U1,U2)) {
 565         Seq.Remove(i);
 566         i--;
 567         continue;
 568       }
 569       if (U2 < U1) {
 570         Seq.Exchange(i,i+1);
 571         Invert = Standard_True;
 572       }
 573     }
 574   }
 575 }
 576
 577 //=======================================================================
 578 //function : MakeEdges
 579 //purpose  : cut E by vertices VOnE, return list of new edges NE
 580 //=======================================================================
 581
 582 void Partition_Spliter::MakeEdges (const TopoDS_Edge& E,
 583                                    const TopTools_ListOfShape& VOnE,
 584                                    TopTools_ListOfShape& NE   ) const
 585 {
 586   TopoDS_Edge WE = E;
 587   WE.Orientation(TopAbs_FORWARD);
 588
 589   TopTools_ListIteratorOfListOfShape itv(VOnE);
 590   TopTools_SequenceOfShape SV;
 591
 592   Standard_Real    U1,U2, f, l;
 593   TopoDS_Vertex    V1,V2,VF,VL;
 594
 595   BRep_Tool::Range(WE,f,l);
 596   TopExp::Vertices(WE,VF,VL);
 597
 598   if (VOnE.Extent() < 3) { // do not rebuild not cut edge
 599     if (( VF.IsSame( VOnE.First() ) && VL.IsSame( VOnE.Last() )) ||
 600         VL.IsSame( VOnE.First() ) && VF.IsSame( VOnE.Last() )  ) {
 601       NE.Append( E );
 602       return;
 603     }
 604   }
 605
 606   for (; itv.More(); itv.Next())
 607     SV.Append(itv.Value());
 608
 609   Tri( WE, SV);
 610
 611   Standard_Integer iVer, NbVer = SV.Length();
 612
 613
 614   //----------------------------------------------------------------
 615   // Construction of the new edges .
 616   //----------------------------------------------------------------
 617
 618   if (VF.IsSame(VL)) { // closed edge
 619     if (NbVer==1)
 620       SV.Append( SV.First() );
 621     else if (!SV.First().IsSame(SV.Last())) {
 622       Standard_Boolean isFirst=0;
 623       Standard_Real    minDU = 1.e10;
 624       TopoDS_Vertex endV = Partition_Inter2d::FindEndVertex(VOnE, f,l, E, isFirst,minDU);
 625       if (endV.IsSame(SV.First()))
 626         SV.Append(endV);
 627       else if (endV.IsSame(SV.Last()))
 628         SV.Prepend(endV);
 629       else
 630         MESSAGE ("END VERTEX IS IN SEQUNCE MIDDLE");
 631     }
 632     NbVer = SV.Length();
 633   }
 634
 635   for (iVer=1; iVer < NbVer; iVer++) {
 636     V1  = TopoDS::Vertex(SV(iVer));
 637     V2  = TopoDS::Vertex(SV(iVer+1));
 638
 639     TopoDS_Shape NewEdge = WE.EmptyCopied();
 640     V1.Orientation(TopAbs_FORWARD);
 641     myBuilder.Add  (NewEdge,V1);
 642     V2.Orientation(TopAbs_REVERSED);
 643     myBuilder.Add  (NewEdge,V2);
 644
 645     if (iVer==1)
 646       U1 = f;
 647     else        {
 648       V1.Orientation(TopAbs_INTERNAL);
 649       U1=BRep_Tool::Parameter(V1,WE);
 650     }
 651     if (iVer+1 == NbVer)
 652       U2 = l;
 653     else        {
 654       V2.Orientation(TopAbs_INTERNAL);
 655       U2=BRep_Tool::Parameter(V2,WE);
 656     }
 657     if (Abs(U1-U2) <= Precision::PConfusion()) {
 658       MESSAGE( "MakeEdges(), EQUAL PARAMETERS OF DIFFERENT VERTICES");
 659       continue;
 660     }
 661     TopoDS_Edge EE=TopoDS::Edge(NewEdge);
 662     myBuilder.Range (EE,U1,U2);
 663
 664     TopoDS_Edge NEdge = TopoDS::Edge(NewEdge);
 665     myBuilder.SameParameter(NEdge,Standard_False);
 666
 667     Standard_Real tol = 1.0e-2;
 668     Standard_Boolean flag = BRep_Tool::SameParameter(NEdge);
 669     if (!flag) {
 670       BRepLib::SameParameter(NEdge,tol);
 671     }
 672     NE.Append(NEdge.Oriented(E.Orientation()));
 673   }
 674 }
 675
 676 //=======================================================================
 677 //function : FindFacesInside
 678 //purpose  : return compound of faces  of other shapes that are
 679 //           inside <S>.
 680 //           <S> is an object shape.
 681 //           <CheckClosed> makes avoid faces that do not form a
 682 //           closed shell
 683 //           <All> makes return already added faces
 684 //=======================================================================
 685
 686 TopoDS_Shape Partition_Spliter::FindFacesInside(const TopoDS_Shape& S,
 687                                                 const Standard_Boolean CheckClosed,
 688                                                 const Standard_Boolean All)
 689 {
 690   if (myInternalFaces.IsBound( S ))
 691     return myInternalFaces.Find ( S );
 692
 693   TopoDS_Compound C;
 694   myBuilder.MakeCompound(C);
 695
 696   const TopoDS_Shape& SS = myImageShape.Image(S).First(); // compound of split faces of S
 697
 698   TopTools_MapOfShape MSE, MPF;
 699   TopTools_DataMapOfShapeListOfShape MEF;
 700   TopTools_MapIteratorOfMapOfShape itm;
 701   TopExp_Explorer expl;
 702   TopTools_ListOfShape Empty;
 703
 704   // MSE filling: map of section edges of SS
 705   for (expl.Init(SS,TopAbs_EDGE); expl.More(); expl.Next()) {
 706     TopoDS_Shape resE = expl.Current() ;
 707     if (myNewSection.Contains( resE ))
 708       MSE.Add(resE);
 709   }
 710
 711   // 1. MPF filling: map of resulting faces except those of S,
 712   // we`ll add to C those of them which are inside SS
 713   // 2. MEF filling: edge of MSE => faces of MPF
 714   TopTools_ListIteratorOfListOfShape itl;
 715   for (itl.Initialize(myListShapes);itl.More();itl.Next()) {
 716     const TopoDS_Shape& SL = itl.Value();
 717     if ( S.IsSame( SL )) continue;
 718     // fill maps
 719     TopoDS_Iterator itF ( myImageShape.Image(SL).First() );
 720     for ( ; itF.More(); itF.Next()) {
 721       const TopoDS_Shape& snf = itF.Value();
 722       MPF.Add(snf);
 723       for (expl.Init( snf, TopAbs_EDGE ); expl.More(); expl.Next()) {
 724         TopoDS_Shape se = expl.Current();
 725         if ( MSE.Contains(se)) {// section edge
 726           if (!MEF.IsBound(se))
 727             MEF.Bind(se,Empty);
 728           MEF(se).Append(snf);
 729         }
 730       }
 731     }
 732   }
 733
 734   // MSEF: map edge of SS - faces of SS
 735   TopTools_IndexedDataMapOfShapeListOfShape MSEF;
 736   TopExp::MapShapesAndAncestors(SS, TopAbs_EDGE, TopAbs_FACE, MSEF);
 737
 738   // find faces inside S
 739
 740   Standard_Boolean skipAlreadyAdded = Standard_False;
 741   Standard_Boolean GoodOri, inside;
 742   Standard_Real dot;
 743   TopTools_ListOfShape KeepFaces;
 744   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
 745
 746   for (Mapit.Initialize(MEF); Mapit.More() ; Mapit.Next() ) {
 747     TopoDS_Edge E = TopoDS::Edge (Mapit.Key());
 748     TopoDS_Edge OrigE = TopoDS::Edge ( myImagesEdges.Root( E ));
 749     Standard_Boolean isSectionE = myInter3d.IsSectionEdge ( OrigE );
 750
 751     TopTools_ListOfShape& EF = MEF.ChangeFind(E);
 752     itl.Initialize( EF );
 753     while (itl.More()) {
 754       TopoDS_Face face1 = TopoDS::Face(itl.Value());
 755       EF.Remove( itl ); // == itl.Next();
 756       if (!MPF.Remove( face1 ))
 757         continue; // was not is MPF ( i.e already checked)
 758       if (!All &&
 759           myAddedFacesMap.Contains( face1 ) &&
 760           myAddedFacesMap.Contains( face1.Reversed() )) {
 761         skipAlreadyAdded = Standard_True;
 762         continue; // already added to 2 shells
 763       }
 764
 765       // find another face which originates from the same face as <face1>
 766       const TopoDS_Shape& origS = myImagesFaces.Root(face1);
 767       TopoDS_Shape face2;
 768       if ( !isSectionE ) {
 769         while (itl.More()) {
 770           face2 = itl.Value();
 771           if (!MPF.Contains( face2 )) {
 772             EF.Remove( itl );
 773             continue;
 774           }
 775           if (origS.IsSame( myImagesFaces.Root( face2 )))
 776             break;
 777           itl.Next();
 778         }
 779         if (itl.More()) { // face2 found
 780           EF.Remove( itl );
 781           MPF.Remove(face2);
 782         }
 783         else
 784           face2.Nullify();
 785         itl.Initialize( EF );
 786       }
 787
 788       // check that origS is not same domain with SS
 789       Standard_Boolean sameDom1 = 0, sameDom2 = 0;
 790       const TopTools_ListOfShape& FL = MSEF.FindFromKey(E); //faces of SS sharing E
 791       const TopoDS_Shape& origF1 = myImagesFaces.Root(FL.First());
 792       const TopoDS_Shape& origF2 = myImagesFaces.Root(FL.Last());
 793       if (origS.IsSame( origF1 ))
 794         sameDom1 = Standard_True;
 795       if ( origS.IsSame( origF2 ))
 796         sameDom2 = Standard_True;
 797       if (!(sameDom1 || sameDom2) && myInter3d.HasSameDomainF( origS )) {
 798         sameDom1 = myInter3d.IsSameDomainF( origS, origF1);
 799         sameDom2 = (origF1 == origF2) ? sameDom1 : myInter3d.IsSameDomainF( origS, origF2);
 800       }
 801       if (sameDom1 && sameDom2)
 802         continue;
 803       if ((sameDom1 || sameDom2)) {
 804         inside = Partition_Loop3d::IsInside (E,
 805                                              TopoDS::Face(FL.First()),
 806                                              TopoDS::Face(FL.Last()),
 807                                              1, dot, GoodOri);
 808         if (inside || (dot + Precision::Angular() >= 1.0))
 809           continue; // E is convex between origF1 and origF2 or they are tangent
 810       }
 811
 812
 813       // keep one of found faces
 814       const TopoDS_Shape& SFace = sameDom1 ? FL.Last() : FL.First(); //face of SS sharing E
 815       inside = Partition_Loop3d::IsInside (E, TopoDS::Face(SFace), face1,
 816                                            1, dot, GoodOri);
 817       if ((dot + Precision::Angular() >= 1.0) &&
 818           !face2.IsNull()) { // face2 position is not clear, it will be analysed alone
 819         MPF.Add( face2 );
 820         EF.Append( face2 );
 821         face2.Nullify();
 822       }
 823       if (inside)
 824         KeepFaces.Append(face1);
 825       else
 826         if (!face2.IsNull())
 827           KeepFaces.Append(face2);
 828     }
 829   }
 830
 831   TopTools_ListOfShape KeptFaces;
 832   if (MPF.IsEmpty())
 833     KeptFaces.Append (KeepFaces);
 834
 835   while (!KeepFaces.IsEmpty()) {
 836     // add to KeepFaces not distributed faces connected with KeepFaces
 837
 838     // KeepEdges : map of edges of kept faces
 839     TopTools_IndexedMapOfShape KeepEdges;
 840     for (itl.Initialize(KeepFaces);itl.More();itl.Next() )
 841       TopExp::MapShapes( itl.Value(), TopAbs_EDGE, KeepEdges);
 842
 843     KeptFaces.Append (KeepFaces); // == KeepFaces.Clear()
 844
 845     // keep faces connected with already kept faces
 846     for (itm.Initialize(MPF);itm.More();itm.Next() ) {
 847       const TopoDS_Shape& PF = itm.Key();
 848       for (expl.Init(PF,TopAbs_EDGE); expl.More(); expl.Next()) {
 849         const TopoDS_Shape& se = expl.Current();
 850         if (!MSE.Contains(se) && KeepEdges.Contains(se) ) {
 851           KeepFaces.Append(PF);
 852           MPF.Remove(PF);
 853           break;
 854         }
 855       }
 856     }
 857   }
 858
 859   // check if kept faces make shell without free edges
 860   MSEF.Clear();  // edge - kept faces
 861   MPF.Clear(); // wrong faces
 862   if (CheckClosed) {
 863     for (itl.Initialize(KeptFaces); itl.More(); itl.Next() )
 864       TopExp::MapShapesAndAncestors(itl.Value(), TopAbs_EDGE, TopAbs_FACE, MSEF);
 865
 866     Standard_Integer i, nb = MSEF.Extent();
 867     Standard_Boolean isClosed = Standard_False;
 868     while (!isClosed) {
 869       isClosed = Standard_True;
 870       for (i=1;  isClosed && i<=nb;  ++i) {
 871         const TopoDS_Shape& E = MSEF.FindKey( i );
 872         if (! MSE.Contains( E ))
 873           isClosed = ( MSEF(i).Extent() != 1 );
 874       }
 875       if (!isClosed) {
 876         const TopoDS_Shape& F = MSEF.FindFromIndex( i-1 ).First(); // bad face
 877         MPF.Add( F );
 878         // remove bad face from MSEF
 879         for (expl.Init( F, TopAbs_EDGE); expl.More(); expl.Next()) {
 880           const TopoDS_Shape& E = expl.Current();
 881           TopTools_ListOfShape& FL = MSEF.ChangeFromKey( E );
 882           for (itl.Initialize( FL ); itl.More(); itl.Next() ) {
 883             if ( F.IsSame( itl.Value() )) {
 884               FL.Remove( itl );
 885               break;
 886             }
 887           }
 888         }
 889       }
 890     }
 891   }
 892
 893   // add to the compound kept faces except bad ones in MPF
 894   if (KeptFaces.Extent() > MPF.Extent()) {
 895     for (itl.Initialize(KeptFaces); itl.More(); itl.Next() )
 896       if (! MPF.Contains( itl.Value() )) {
 897         myBuilder.Add( C, itl.Value());
 898         //myBuilder.Add( C, itl.Value().Reversed());
 899       }
 900   }
 901
 902   if (!skipAlreadyAdded)
 903     myInternalFaces.Bind( S, C );
 904
 905   return C;
 906 }
 907
 908 //=======================================================================
 909 //function : MakeShell
 910 //purpose  : split S into compound of shells
 911 //=======================================================================
 912
 913 void Partition_Spliter::MakeShells(const TopoDS_Shape& S,
 914                                    TopTools_ListOfShape& NS)
 915 {
 916   // check if S is closed shape
 917   Standard_Boolean isClosed = Standard_True;
 918
 919   TopTools_IndexedDataMapOfShapeListOfShape MEF;
 920   Standard_Integer i;
 921   if (S.ShapeType() != TopAbs_SOLID) {
 922     TopExp::MapShapesAndAncestors(S, TopAbs_EDGE, TopAbs_FACE, MEF);
 923     for (i=1;  isClosed && i<=MEF.Extent();  ++i)
 924       isClosed = ( MEF(i).Extent() != 1 );
 925   }
 926   Partition_Loop3d ShellMaker;
 927   // get compound of split faces of S
 928   const TopoDS_Shape& FacesComp = myImageShape.Image(S).First();
 929   ShellMaker.AddConstFaces( FacesComp );
 930   // split faces inside S
 931   if (isClosed) {
 932     TopoDS_Shape InternalFacesComp = FindFacesInside(S, Standard_True);
 933     ShellMaker.AddSectionFaces( InternalFacesComp );
 934 // } else { // a shell may become closed
 935 //     ShellMaker.AddConstFaces( InternalFacesComp );
 936   }
 937
 938   NS = ShellMaker.MakeShells( myAddedFacesMap );
 939
 940   // 1. Add faces added to new shell to myAddedFacesMap:
 941   // avoid rebuilding twice commont part of 2 solids.
 942   // 2. Check shell closeness (DEBUG)
 943   TopTools_ListIteratorOfListOfShape itS(NS);
 944   while ( itS.More()) {
 945 #ifdef DEB
 946     Standard_Boolean checkCloseness = Standard_True;
 947 #endif
 948     TopExp_Explorer expF (itS.Value(), TopAbs_FACE);
 949     for (; expF.More(); expF.Next()) {
 950
 951       myAddedFacesMap.Add (expF.Current());
 952
 953 #ifdef DEB
 954       if (checkCloseness &&
 955           ! myInter3d.HasSameDomainF( myImagesFaces.Root(expF.Current()) ))
 956         checkCloseness = Standard_False;
 957 #endif
 958     }
 959
 960 #ifdef DEB
 961     if (checkCloseness) {
 962       // if S is closed, a new shell must be closed too;
 963       if (isClosed) {
 964         // check that a new shell is closed
 965         MEF.Clear();
 966         TopExp::MapShapesAndAncestors(itS.Value(), TopAbs_EDGE, TopAbs_FACE, MEF);
 967         for (i=1;  isClosed && i<=MEF.Extent();  ++i)
 968           isClosed = ( MEF(i).Extent() != 1 );
 969         if (!isClosed) { // remove not closed shell
 970           MESSAGE (" NOT CLOSED SHELL " );
 971           //NS.Remove( itS );
 972           itS.Next();
 973           continue;
 974         }
 975       }
 976     }
 977 #endif
 978     itS.Next();
 979   } // loop on new shells
 980 }
 981
 982 //=======================================================================
 983 //function : findEqual
 984 //purpose  : compare edges form EL1 against edges from EL2,
 985 //           Result is in EMM binding edge form EL1 to list of equal edges
 986 //           Edges are considered equall only if they have same vertices
 987 //           <addSame>==True makes consider same edges as equal
 988 //           Put in <AllEqMap> all equal edges
 989 //=======================================================================
 990
 991 static void findEqual (const TopTools_ListOfShape& EL1,
 992                        const TopTools_ListOfShape& EL2,
 993                        const Standard_Boolean addSame,
 994                        TopTools_DataMapOfShapeListOfShape& EEM,
 995                        TopTools_MapOfShape& AllEqMap)
 996 {
 997   // map vertices to edges for EL2
 998   TopTools_DataMapOfShapeListOfShape VEM;
 999   TopTools_ListIteratorOfListOfShape itE1, itE2(EL2);
1000   TopoDS_Iterator itV;
1001   TopTools_ListOfShape emptyL;
1002   for (; itE2.More(); itE2.Next()) {
1003     for (itV.Initialize( itE2.Value() ); itV.More(); itV.Next()) {
1004       const TopoDS_Shape& V = itV.Value();
1005       if (! VEM.IsBound( V ) )
1006         VEM.Bind( V, emptyL);
1007       VEM( V ).Append( itE2.Value());
1008     }
1009   }
1010
1011   gp_Vec D1, D2;
1012   gp_Pnt P;
1013   Standard_Real f,l,u,tol;
1014   Handle(Geom_Curve) C1, C2;
1015   Extrema_ExtPC Extrema;
1016   TopoDS_Vertex V1, V2, V3, V4;
1017
1018   AllEqMap.Clear();
1019
1020   for (itE1.Initialize(EL1); itE1.More(); itE1.Next()) {
1021     const TopoDS_Edge& E1 = TopoDS::Edge( itE1.Value());
1022     if (BRep_Tool::Degenerated( E1 ) || AllEqMap.Contains (E1))
1023       continue;
1024     TopExp::Vertices( E1, V1, V2 );
1025
1026     if (VEM.IsBound(V1))
1027       itE2.Initialize( VEM(V1) );
1028     for (; itE2.More(); itE2.Next()) {
1029       const TopoDS_Edge& E2 = TopoDS::Edge( itE2.Value());
1030       if (BRep_Tool::Degenerated( E2 ))
1031         continue;
1032
1033       if (E1.IsSame(E2)) {
1034         if (!addSame)
1035           continue;
1036       }
1037       else {
1038         TopExp::Vertices( E2, V3, V4);
1039         if (!V2.IsSame(V4) && !V2.IsSame(V3))
1040           continue;
1041         // E1 and E2 have same vertices
1042         // check D1 at end points.
1043         C2 = BRep_Tool::Curve( E2, f,l);
1044         C1 = BRep_Tool::Curve( E1, f,l);
1045         u = BRep_Tool::Parameter(V1,E1);
1046         C1->D1(u, P, D1);
1047         u = BRep_Tool::Parameter(V1.IsSame(V3) ? V3 : V4, E2);
1048         C2->D1(u, P, D2);
1049         D1.Normalize(); D2.Normalize();
1050         if (Abs(D1*D2) + Precision::Angular() < 1.0)
1051           continue;
1052         if (! V1.IsSame(V2)) {
1053           u = BRep_Tool::Parameter(V2,E1);
1054           C1->D1(u, P, D1);
1055           u = BRep_Tool::Parameter(V2.IsSame(V3) ? V3 : V4, E2);
1056           C2->D1(u, P, D2);
1057           D1.Normalize(); D2.Normalize();
1058           if (Abs(D1*D2) + Precision::Angular() < 1.0)
1059             continue;
1060         }
1061         // check distance at a couple of internal points
1062         tol = Max(BRep_Tool::Tolerance(E1),
1063                   BRep_Tool::Tolerance(E2));
1064         GeomAdaptor_Curve AC1(C1);
1065         Extrema.Initialize(AC1,f,l);
1066         Standard_Boolean ok = Standard_True, hasMin = Standard_False;
1067         BRep_Tool::Range( E2, f, l);
1068         Standard_Integer i=1, nbi=3;
1069         for (; i<nbi && ok; ++i) {
1070           Extrema.Perform( C2->Value( f+(l-f)*i/nbi ));
1071           Standard_Integer j=1, nbj=Extrema.NbExt();
1072           for (; j<=nbj && ok; ++j) {
1073             if (Extrema.IsMin(j)) {
1074               hasMin = Standard_True;
1075               ok = Extrema.Value(j) <= tol;
1076             }
1077           }
1078         }
1079         if ( !hasMin || !ok)
1080           continue;
1081       }
1082       // bind E2 to E1 in EEM
1083       if (!EEM.IsBound(E1)) {
1084         EEM.Bind (E1, emptyL);
1085         AllEqMap.Add (E1);
1086       }
1087       EEM(E1).Append(E2);
1088       AllEqMap.Add (E2);
1089     }
1090   }
1091 }
1092
1093 //=======================================================================
1094 //function : MakeFaces
1095 //purpose  : split faces of S, return compound of new faces
1096 //=======================================================================
1097
1098 TopoDS_Shape Partition_Spliter::MakeFaces (const TopoDS_Shape& S)
1099 {
1100   TopoDS_Compound C;
1101   myBuilder.MakeCompound(C);
1102
1103   TopTools_ListIteratorOfListOfShape itl, itNE;
1104
1105   TopExp_Explorer exp(S,TopAbs_FACE);
1106   for (; exp.More(); exp.Next()) {
1107
1108     const TopoDS_Face& F = TopoDS::Face(exp.Current());
1109
1110     TopTools_ListOfShape LNF;
1111
1112     if (myImagesFaces.HasImage( F )) {
1113       myImagesFaces.LastImage( F, LNF );
1114       TopAbs_Orientation oriF = F.Orientation();
1115       for ( itl.Initialize( LNF ); itl.More(); itl.Next())
1116         itl.Value().Orientation( oriF );
1117     }
1118     else {
1119
1120       Partition_Loop2d loops;
1121       loops.Init(F);
1122
1123       TopTools_IndexedMapOfShape EM;
1124       TopExp::MapShapes( F, TopAbs_EDGE, EM);
1125
1126       TopTools_MapOfShape AddedEqualM;
1127       Standard_Boolean needRebuild = Standard_False;
1128
1129       // add splits to loops
1130
1131       // LE: old edges + new not splitted edges
1132       const TopTools_ListOfShape& LE = myAsDes->Descendant(F);
1133       for (itl.Initialize(LE); itl.More(); itl.Next()) {
1134         const TopoDS_Edge& E = TopoDS::Edge( itl.Value() );
1135
1136         Standard_Boolean isSectionE = myInter3d.IsSectionEdge(E);
1137         Standard_Boolean isNewE = !EM.Contains( E );
1138
1139         // LSE: list of split edges
1140         TopTools_ListOfShape LSE;
1141         myImagesEdges.LastImage(E,LSE); // splits of E or E itself
1142
1143         for (itNE.Initialize(LSE); itNE.More(); itNE.Next()) {
1144
1145           TopoDS_Edge NE = TopoDS::Edge( itNE.Value() );
1146           Standard_Boolean isSameE = NE.IsSame ( E );
1147
1148           if ( isNewE || isSectionE || !isSameE) {
1149             if (AddedEqualM.Contains( NE ))
1150               continue;
1151
1152             if (isNewE) {
1153               if (isSectionE) {
1154                 if ( ! myInter3d.IsSplitOn( NE, E, F) )
1155                   continue;
1156               }
1157               else {
1158                 TopoDS_Vertex V1,V2;
1159                 TopExp::Vertices(NE,V1,V2);
1160                 const TopTools_ListOfShape& EL1 = myAsDes->Ascendant(V1);
1161                 const TopTools_ListOfShape& EL2 = myAsDes->Ascendant(V2);
1162                 if ( EL1.Extent() < 2 && EL2.Extent() < 2 )
1163                   continue;
1164               }
1165             }
1166             else {
1167               NE.Orientation( E.Orientation());
1168               if (!isSameE) {
1169                 // orient NE because it may be a split of other edge
1170                 Standard_Real f,l,u;
1171                 Handle(Geom_Curve) C3d  = BRep_Tool::Curve( E,f,l );
1172                 Handle(Geom_Curve) NC3d = BRep_Tool::Curve( NE,f,l);
1173                 if ( C3d != NC3d) {
1174                   gp_Vec D1, ND1;  gp_Pnt P;
1175                   TopoDS_Vertex V = TopExp::FirstVertex(NE);
1176                   u = BRep_Tool::Parameter(V,NE);
1177                   NC3d->D1 (u, P, ND1);
1178                   u = BRep_Tool::Parameter(V,E);
1179                   C3d ->D1 (u, P, D1);
1180                   if (ND1.Dot(D1) < 0)
1181                     NE.Reverse();
1182                 }
1183               }
1184             }
1185             if (myEqualEdges.Contains( NE ) && !AddedEqualM.Add( NE ))
1186               continue;
1187
1188             needRebuild = Standard_True;
1189           }
1190
1191           if (isNewE || isSectionE)
1192             myNewSection.Add( NE );
1193
1194           if (isNewE)
1195             loops.AddSectionEdge(NE);
1196           else
1197             loops.AddConstEdge(NE);
1198         }
1199       }
1200
1201       //-------------------
1202       // Build the faces.
1203       //-------------------
1204
1205       if (needRebuild) {
1206
1207         loops.Perform();
1208         loops.WiresToFaces(myImagesEdges);
1209
1210         LNF = loops.NewFaces();
1211
1212         myImagesFaces.Bind(F,LNF);
1213
1214         // replace the result faces that have already been built
1215         // during same domain faces reconstruction
1216         if (myInter3d.HasSameDomainF( F )) {
1217           // build map edge to same domain faces
1218           TopTools_IndexedDataMapOfShapeListOfShape EFM;
1219           TopTools_MapOfShape SDFM; // avoid doubling
1220           itl.Initialize( myInter3d.SameDomain( F ));
1221           for (; itl.More(); itl.Next()) {
1222             if ( !myImagesFaces.HasImage( itl.Value() ))
1223               continue;
1224             TopTools_ListIteratorOfListOfShape itNF;
1225             itNF.Initialize (myImagesFaces.Image( itl.Value() ));
1226             for ( ; itNF.More(); itNF.Next()) {
1227               TopoDS_Shape SDF = itNF.Value();
1228               if (myImagesFaces.HasImage( SDF )) // already replaced
1229                 SDF = myImagesFaces.Image( SDF ).First();
1230               if (SDFM.Add (SDF))
1231                 TopExp::MapShapesAndAncestors(SDF, TopAbs_EDGE, TopAbs_FACE, EFM);
1232             }
1233           }
1234           // do replace
1235           TopTools_ListOfShape LOF;
1236           if ( !EFM.IsEmpty() )
1237             itl.Initialize( LNF );
1238           while (itl.More()) {
1239             const TopoDS_Shape& NF = itl.Value();
1240             TopExp_Explorer expE ( NF, TopAbs_EDGE );
1241             const TopoDS_Edge& E  = TopoDS::Edge (expE.Current());
1242             if (EFM.Contains( E )) {
1243               const TopTools_ListOfShape& SDFL = EFM.FindFromKey( E );
1244               TopoDS_Shape SDF = SDFL.First();
1245               Standard_Boolean GoodOri;
1246               Standard_Real dot;
1247               Partition_Loop3d::IsInside (E, TopoDS::Face(NF), TopoDS::Face(SDF),
1248                                           1, dot, GoodOri);
1249               if (dot < 0) {
1250                 if (SDFL.Extent() == 1) {
1251                   itl.Next();
1252                   continue;
1253                 }
1254                 else
1255                   SDF = SDFL.Last();
1256               }
1257               gp_Vec V1 = Partition_Loop3d::Normal( E, TopoDS::Face( NF ));
1258               gp_Vec V2 = Partition_Loop3d::Normal( E, TopoDS::Face( SDF ));
1259               if (V1*V2 < 0)
1260                 SDF.Reverse();
1261
1262               if (!myImagesFaces.HasImage( NF ))
1263                 myImagesFaces.Bind( NF, SDF );
1264
1265               LOF.Prepend ( SDF );
1266               LNF.Remove (itl);
1267             }
1268             else
1269               itl.Next();
1270           }
1271
1272           LNF.Append (LOF);
1273         }
1274       } // if (needRebuild)
1275
1276       else {
1277         LNF.Append( F );
1278         myImagesFaces.Bind(F,LNF);
1279       }
1280     } // if (myImagesFaces.HasImage( F ))
1281
1282     for (itl.Initialize(LNF); itl.More(); itl.Next())
1283       myBuilder.Add ( C, itl.Value());
1284   } // loop on faces of S
1285
1286   return C;
1287 }
1288
1289 //=======================================================================
1290 //function : MergeEqualEdges
1291 //purpose  : find equal edges,  choose  ones  to  keep and make
1292 //           them have pcurves on all faces they are shared by
1293 //=======================================================================
1294
1295 void Partition_Spliter::MergeEqualEdges (const TopTools_ListOfShape& LSE)
1296 {
1297   // find equal edges
1298   // map: edge - equal edges
1299   TopTools_DataMapOfShapeListOfShape EEM( LSE.Extent() );
1300   findEqual (LSE, LSE, 0, EEM, myEqualEdges);
1301
1302   TopTools_ListOfShape EEL; // list of equal edges
1303   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itM (EEM);
1304   for ( ; itM.More(); itM.Next()) {
1305     EEL = itM.Value();
1306     EEL.Append( itM.Key() );
1307     // choose an edge to keep, section edges have priority
1308     TopoDS_Edge EKeep;
1309     TopTools_ListIteratorOfListOfShape itEE (EEL);
1310     for (; itEE.More(); itEE.Next()) {
1311       EKeep = TopoDS::Edge( itEE.Value() );
1312       const TopoDS_Edge& EKeepOrig = TopoDS::Edge( myImagesEdges.Root( EKeep ));
1313       if (myInter3d.IsSectionEdge( EKeepOrig ))
1314         break;
1315     }
1316
1317     Standard_Real f,l, tol;
1318     for (itEE.Initialize (EEL); itEE.More(); itEE.Next()) {
1319       const TopoDS_Edge& E = TopoDS::Edge( itEE.Value() );
1320       if ( E.IsSame( EKeep ))
1321         continue;
1322       const TopoDS_Edge& EReplOrig = TopoDS::Edge( myImagesEdges.Root( E ));
1323       TopTools_ListOfShape FL;
1324       if (myInter3d.IsSectionEdge( EReplOrig ))
1325         FL = myInter3d.SectionEdgeFaces ( EReplOrig );
1326       else
1327         FL = myAsDes->Ascendant( EReplOrig );
1328
1329       TopTools_ListIteratorOfListOfShape itF (FL);
1330       for ( ; itF.More(); itF.Next()) {
1331         const TopoDS_Face& F = TopoDS::Face( itF.Value());
1332         // build pcurves
1333         Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( EKeep, F, f,l);
1334         if (pc.IsNull()) {
1335           Handle(Geom_Curve) C3d = BRep_Tool::Curve( EKeep, f, l);
1336           C3d = new Geom_TrimmedCurve( C3d, f,l);
1337           pc = TopOpeBRepTool_CurveTool::MakePCurveOnFace (F,C3d,tol);
1338           if (pc.IsNull()) {
1339             MESSAGE (" CANT BUILD PCURVE ");
1340           }
1341           myBuilder.UpdateEdge( EKeep, pc, F, tol);
1342         }
1343       }
1344       // replace edges in faces
1345       if (!myImagesEdges.HasImage( E ))
1346         myImagesEdges.Bind( E, EKeep );
1347     }
1348   }
1349 }
1350
1351 //=======================================================================
1352 //function : KeepShapesInside
1353 //purpose  : remove shapes that are outside of S from resul
1354 //=======================================================================
1355
1356 void Partition_Spliter::KeepShapesInside (const TopoDS_Shape& S)
1357 {
1358   TopoDS_Iterator it;
1359   if (S.ShapeType() < TopAbs_SOLID) { // compound or compsolid
1360     for (it.Initialize( S ); it.More(); it.Next())
1361       KeepShapesInside( it.Value());
1362     return;
1363   }
1364   if (!myImageShape.HasImage( S ) && ! CheckTool( S ))
1365     return;
1366
1367   TopoDS_Shape InsFacesComp = FindFacesInside( S, Standard_False, Standard_True);
1368   TopTools_IndexedMapOfShape MIF; // map of internal faces;
1369   TopExp::MapShapes( InsFacesComp, TopAbs_FACE, MIF );
1370
1371   if (MIF.IsEmpty()) return;
1372
1373   // leave in the result only those shapes having a face in MIF
1374   TopoDS_Compound C;
1375   myBuilder.MakeCompound(C);
1376
1377   for (it.Initialize( myShape ); it.More(); it.Next()) {
1378
1379     TopExp_Explorer expResF( it.Value(), TopAbs_FACE );
1380     for (; expResF.More(); expResF.Next()) {
1381       if ( MIF.Contains( expResF.Current())) {
1382         myBuilder.Add( C, it.Value() );
1383         break;
1384       }
1385     }
1386   }
1387
1388   myShape = C;
1389 }
1390
1391 //=======================================================================
1392 //function : RemoveShapesInside
1393 //purpose  : remove shapes that are inside S from resul
1394 //=======================================================================
1395
1396 void Partition_Spliter::RemoveShapesInside (const TopoDS_Shape& S)
1397 {
1398   TopoDS_Iterator it;
1399   if (S.ShapeType() < TopAbs_SOLID) { // compound or compsolid
1400     for (it.Initialize( S ); it.More(); it.Next())
1401       RemoveShapesInside( it.Value());
1402     return;
1403   }
1404   Standard_Boolean isTool = Standard_False;
1405   if (!myImageShape.HasImage( S )) {
1406     isTool = CheckTool( S );
1407     if (!isTool) return;
1408   }
1409
1410   TopoDS_Shape InsFacesComp = FindFacesInside( S, Standard_False, Standard_True);
1411   TopTools_IndexedMapOfShape MIF; // map of internal faces
1412   TopExp::MapShapes( InsFacesComp, TopAbs_FACE, MIF);
1413
1414   if (MIF.IsEmpty()) return;
1415
1416   // add to MIF split faces of S
1417   if (myImageShape.HasImage( S ))
1418     TopExp::MapShapes( myImageShape.Image(S).First(), TopAbs_FACE, MIF);
1419
1420   // leave in the result only those shapes not having all face in MIF
1421
1422   TopoDS_Compound C;
1423   myBuilder.MakeCompound(C);
1424
1425   // RMF : faces of removed shapes that encounter once
1426   TopTools_MapOfShape RFM;
1427
1428   for (it.Initialize( myShape ); it.More(); it.Next()) {
1429
1430     TopExp_Explorer expResF( it.Value(), TopAbs_FACE );
1431     for (; expResF.More(); expResF.Next())
1432       if (!MIF.Contains( expResF.Current()))
1433         break;
1434
1435     if (expResF.More())
1436       // add shape to result
1437       myBuilder.Add( C, it.Value() );
1438     else
1439       // add faces of a removed shape to RFM
1440       for (expResF.ReInit(); expResF.More(); expResF.Next()) {
1441         const TopoDS_Shape& F = expResF.Current();
1442         if ( ! RFM.Remove ( F ))
1443           RFM.Add( F );
1444       }
1445   }
1446
1447   if (!isTool) {
1448     // rebuild S, it must remain in the result
1449     Standard_Boolean isClosed = Standard_False;
1450     switch (S.ShapeType()) {
1451     case TopAbs_SOLID :
1452       isClosed = Standard_True; break;
1453     case TopAbs_SHELL: {
1454       TopTools_IndexedDataMapOfShapeListOfShape MEF;
1455       Standard_Integer i;
1456       TopExp::MapShapesAndAncestors(S, TopAbs_EDGE, TopAbs_FACE, MEF);
1457       for (i=1;  isClosed && i<=MEF.Extent();  ++i)
1458         isClosed = ( MEF(i).Extent() != 1 );
1459       break;
1460     }
1461     default:
1462       isClosed = Standard_False;
1463     }
1464     if (isClosed) {
1465       // add to a new shape external faces of removed shapes, ie those in RFM
1466       TopoDS_Shell Shell;
1467       myBuilder.MakeShell( Shell );
1468
1469       TopTools_MapIteratorOfMapOfShape itF (RFM);
1470       for ( ; itF.More(); itF.Next())
1471         myBuilder.Add( Shell, itF.Key());
1472
1473       if (S.ShapeType() == TopAbs_SOLID) {
1474         TopoDS_Solid Solid;
1475         myBuilder.MakeSolid( Solid );
1476         myBuilder.Add (Solid, Shell);
1477         myBuilder.Add (C, Solid);
1478       }
1479       else
1480         myBuilder.Add (C, Shell);
1481     }
1482     else {
1483       if (myImageShape.HasImage( S )) {
1484         for (it.Initialize( myImageShape.Image(S).First()); it.More(); it.Next())
1485           myBuilder.Add (C, it.Value());
1486       }
1487     }
1488   }
1489
1490   myShape = C;
1491 }
1492
1493 //=======================================================================
1494 //function : CheckTool
1495 //purpose  : Return True if <S>  is  a tool shape. Prepare tool
1496 //           faces of <S> for the search of internal faces.
1497 //=======================================================================
1498
1499 Standard_Boolean Partition_Spliter::CheckTool(const TopoDS_Shape& S)
1500 {
1501   // suppose S has not an image
1502
1503   Standard_Boolean isTool = Standard_False;
1504   TopoDS_Compound C;
1505   myBuilder.MakeCompound( C );
1506
1507   TopExp_Explorer expF( S, TopAbs_FACE);
1508   for (; expF.More(); expF.Next()) {
1509
1510     const TopoDS_Face& F = TopoDS::Face( expF.Current() );
1511     if (myMapTools.Contains( F ))
1512       isTool = Standard_True;
1513     else
1514       continue;
1515
1516     if (myImagesFaces.HasImage( F )) {
1517       // F has been reconstructed
1518       TopAbs_Orientation Fori = F.Orientation();
1519       TopTools_ListOfShape LNF;
1520       myImagesFaces.LastImage( F, LNF);
1521       TopTools_ListIteratorOfListOfShape itF (LNF);
1522       for ( ; itF.More(); itF.Next())
1523         myBuilder.Add( C, itF.Value().Oriented(Fori) );
1524       continue;
1525     }
1526
1527     Standard_Boolean hasSectionE = myInter3d.HasSectionEdge( F );
1528     Standard_Boolean hasNewE     = myAsDes->HasDescendant( F );
1529     if (!hasSectionE && !hasNewE)
1530       continue; // F intersects nothing
1531
1532     // make an image for F
1533
1534     TopoDS_Face NF = F;
1535     NF.Orientation(TopAbs_FORWARD);
1536     NF = TopoDS::Face( NF.EmptyCopied() ); // make a copy
1537     TopoDS_Wire NW;
1538     myBuilder.MakeWire( NW );
1539
1540     // add edges, as less as possible
1541     TopTools_ListOfShape NEL;
1542     TopTools_ListIteratorOfListOfShape itNE;
1543     if (hasSectionE) {
1544       // add section edges
1545       TopExp_Explorer expE;
1546       for ( ; expE.More(); expE.Next()) {
1547         if (! myImagesEdges.HasImage( expE.Current() ))
1548           continue;
1549         myImagesEdges.LastImage( expE.Current(), NEL );
1550         for ( itNE.Initialize( NEL ); itNE.More(); itNE.Next())
1551           myBuilder.Add ( NW, itNE.Value());
1552       }
1553     }
1554     if (hasNewE) {
1555       // add new adges
1556       NEL = myAsDes->Descendant( F );
1557       for ( itNE.Initialize( NEL ); itNE.More(); itNE.Next()) {
1558         TopTools_ListOfShape SEL; // splits
1559         myImagesEdges.LastImage( itNE.Value(), SEL );
1560         TopTools_ListIteratorOfListOfShape itSE (SEL);
1561         for ( ; itSE.More(); itSE.Next())
1562           myBuilder.Add ( NW, itSE.Value());
1563       }
1564     }
1565     myBuilder.Add( NF, NW );
1566     myBuilder.Add (C, NF);
1567
1568     NF.Orientation( F.Orientation() ); // NF is most probably invalid
1569     myImagesFaces.Bind (F, NF);
1570   }
1571   if (isTool)
1572     myImageShape.Bind (S, C);
1573
1574   return isTool;
1575 }