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