src/PARTITION/Partition_Spliter.cxx

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