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