src/PARTITION/Partition_Inter3d.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_Inter3d.cxx
  25 //  Author : Benedicte MARTIN
  26 //  Module : GEOM
  27 //  $Header$
  28
  29 #include "Partition_Inter2d.hxx"
  30 #include "Partition_Inter3d.ixx"
  31 #include "utilities.h"
  32
  33 #include <BRepAlgo_AsDes.hxx>
  34 #include <BRepAlgo_Image.hxx>
  35 #include <BRepLib.hxx>
  36 #include <BRepOffset_Tool.hxx>
  37 #include <BRep_Builder.hxx>
  38 #include <BRep_Tool.hxx>
  39
  40 #include <TopExp.hxx>
  41 #include <TopExp_Explorer.hxx>
  42
  43 #include <TopOpeBRepTool_BoxSort.hxx>
  44 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  45 #include <TopTools_ListIteratorOfListOfShape.hxx>
  46 #include <TopTools_ListOfShape.hxx>
  47 #include <TopoDS.hxx>
  48 #include <TopoDS_Compound.hxx>
  49 #include <TopoDS_Edge.hxx>
  50 #include <TopoDS_Face.hxx>
  51 #include <TopoDS_Vertex.hxx>
  52
  53 #ifdef DEB
  54 #include <DBRep.hxx>
  55 #endif
  56
  57 #include <BRepLib_MakeVertex.hxx>
  58 #include <BRepTools.hxx>
  59 #include <Extrema_ExtPS.hxx>
  60 #include <Extrema_POnSurf.hxx>
  61 #include <Geom2dAPI_ProjectPointOnCurve.hxx>
  62 #include <Geom2d_Curve.hxx>
  63 #include <GeomAPI_ProjectPointOnCurve.hxx>
  64 #include <GeomAdaptor_Surface.hxx>
  65 #include <Geom_Curve.hxx>
  66 #include <Geom_RectangularTrimmedSurface.hxx>
  67 #include <Geom_SphericalSurface.hxx>
  68 #include <Geom_Surface.hxx>
  69 #include <Geom_TrimmedCurve.hxx>
  70 #include <Precision.hxx>
  71 #include <TColStd_MapOfInteger.hxx>
  72 #include <TopOpeBRepBuild_Builder.hxx>
  73 #include <TopOpeBRepDS_BuildTool.hxx>
  74 #include <TopOpeBRepDS_CurveExplorer.hxx>
  75 #include <TopOpeBRepDS_HDataStructure.hxx>
  76 #include <TopOpeBRepDS_Interference.hxx>
  77 #include <TopOpeBRepDS_PointIterator.hxx>
  78 #include <TopOpeBRepDS_Transition.hxx>
  79 #include <TopOpeBRepTool_CurveTool.hxx>
  80 #include <TopOpeBRepTool_GeomTool.hxx>
  81 #include <TopOpeBRepTool_OutCurveType.hxx>
  82 #include <TopOpeBRep_DSFiller.hxx>
  83 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
  84 #include <stdio.h>
  85
  86 using namespace std;
  87
  88 //=======================================================================
  89 //function : Partition_Inter3d
  90 //purpose  :
  91 //=======================================================================
  92
  93 Partition_Inter3d::Partition_Inter3d()
  94 {
  95 }
  96 //=======================================================================
  97 //function : Partition_Inter3d
  98 //purpose  :
  99 //=======================================================================
 100
 101 Partition_Inter3d::Partition_Inter3d(const Handle(BRepAlgo_AsDes)& AsDes)
 102   :myAsDes(AsDes)
 103 {
 104   mySectionEdgesAD = new BRepAlgo_AsDes;
 105 }
 106
 107 //=======================================================================
 108 //function : CompletPart3d
 109 //purpose  : FaceShapeMap is just to know the shape a face belongs to
 110 //=======================================================================
 111
 112 void Partition_Inter3d::CompletPart3d(const TopTools_ListOfShape& SetOfFaces1,
 113                                       const TopTools_DataMapOfShapeShape& FaceShapeMap)
 114 {
 115   if (myAsDes.IsNull())
 116     myAsDes = new BRepAlgo_AsDes;
 117
 118   TopTools_ListIteratorOfListOfShape it;
 119
 120   //---------------------------------------------------------------
 121   // Construction of bounding boxes.
 122   //---------------------------------------------------------------
 123
 124   BRep_Builder B;
 125   TopoDS_Compound CompOS;
 126   B.MakeCompound(CompOS);
 127   for (it.Initialize(SetOfFaces1); it.More(); it.Next())
 128     B.Add(CompOS, it.Value());
 129
 130   TopOpeBRepTool_BoxSort BOS;
 131   BOS.AddBoxesMakeCOB(CompOS,TopAbs_FACE);
 132
 133   for (it.Initialize(SetOfFaces1); it.More(); it.Next()) {
 134     TopoDS_Face F1 = TopoDS::Face(it.Value());
 135
 136     // avoid intersecting faces of one shape
 137     TopoDS_Shape S1;
 138     if (FaceShapeMap.IsBound(F1)) S1 = FaceShapeMap.Find(F1);
 139
 140     // to filter faces sharing an edge
 141     TopTools_IndexedMapOfShape EM;
 142     TopExp::MapShapes( F1, TopAbs_EDGE, EM);
 143
 144     TColStd_ListIteratorOfListOfInteger itLI = BOS.Compare(F1);
 145     for (; itLI.More(); itLI.Next()) {
 146       TopoDS_Face F2 = TopoDS::Face(BOS.TouchedShape(itLI));
 147       if (F1.IsSame(F2) || IsDone(F1,F2))
 148         continue;
 149
 150       TopoDS_Shape S2;
 151       if (FaceShapeMap.IsBound(F2)) S2 = FaceShapeMap.Find(F2);
 152       if (!S1.IsNull() && S1.IsSame(S2))
 153         continue; // descendants of one shape
 154
 155       TopExp_Explorer expE (F2, TopAbs_EDGE);
 156       for ( ; expE.More(); expE.Next())
 157         if (EM.Contains( expE.Current() ))
 158           break;
 159       if (expE.More())
 160       {
 161         // faces have a common edge, check if they are a tool and a face
 162         // generated by the tool in another shape; in that case they are
 163         // to be intersected
 164         TopLoc_Location L1, L2;
 165         Handle(Geom_Surface) S1 = BRep_Tool::Surface( F1, L1 );
 166         Handle(Geom_Surface) S2 = BRep_Tool::Surface( F2, L2 );
 167         if ( S1 != S2 || L1 != L2 )
 168           continue;
 169       }
 170
 171       F1.Orientation(TopAbs_FORWARD);
 172       F2.Orientation(TopAbs_FORWARD);
 173       FacesPartition(F1,F2);
 174     }
 175
 176     // mark as modified a face which has at least one new edge
 177     if (!myAsDes->HasDescendant( F1 ))
 178       continue;
 179     TopTools_ListIteratorOfListOfShape itE (myAsDes->Descendant( F1 ));
 180     for ( ; itE.More(); itE.Next()) {
 181       if (myNewEdges.Contains( itE.Value())) {
 182         myTouched.Add( F1 );
 183         break;
 184       }
 185     }
 186   }
 187 }
 188
 189 //=======================================================================
 190 //function : PutInBounds
 191 //purpose  :
 192 //=======================================================================
 193
 194 static void PutInBounds (const TopoDS_Face&          F,
 195                          const TopoDS_Edge&          E,
 196                          Handle(Geom2d_Curve)&       C2d)
 197 {
 198   Standard_Real   umin,umax,vmin,vmax;
 199   Standard_Real   f,l;
 200   BRep_Tool::Range(E,f,l);
 201
 202   TopLoc_Location L; // Recup S avec la location pour eviter la copie.
 203   Handle (Geom_Surface) S   = BRep_Tool::Surface(F,L);
 204
 205   if (S->IsKind(STANDARD_TYPE(Geom_RectangularTrimmedSurface))) {
 206     S = (*(Handle_Geom_RectangularTrimmedSurface*)&S)->BasisSurface();
 207   }
 208   if (!S->IsUPeriodic() && !S->IsVPeriodic())
 209     return;
 210
 211   BRepTools::UVBounds(F,umin,umax,vmin,vmax);
 212
 213   gp_Pnt2d Pf = C2d->Value(f);
 214   gp_Pnt2d Pl = C2d->Value(l);
 215   const Standard_Real Um = 0.34*f + 0.66*l;
 216   gp_Pnt2d Pm = C2d->Value( Um );
 217
 218   // sometimes on shpere, pcurve is out of domain by V though S is
 219   // UPeriodic, sometimes it is in domain but nontheless it has
 220   // wrong position.
 221   // Check pcurve position by 3D point
 222   if (S->IsKind(STANDARD_TYPE( Geom_SphericalSurface )))
 223   {
 224     // get point on the surface
 225     gp_Pnt Ps = S->Value( Pm.X(), Pm.Y() );
 226     // get point on the edge
 227     Handle(Geom_Curve) C = BRep_Tool::Curve( E, f, l );
 228     gp_Pnt Pc = C->Value( Um );
 229     // compare points
 230     Standard_Real TolE = BRep_Tool::Tolerance( E );
 231     if ( Pc.SquareDistance( Ps ) * 0.95 < TolE * TolE )
 232       return; // OK
 233
 234     // find good UV for Pc: project Pc on S
 235     GeomAdaptor_Surface  SA (S);
 236     Extrema_ExtPS anExtPS (Pc, SA,
 237                            SA.UResolution( TolE ), SA.VResolution( TolE ));
 238     if (anExtPS.IsDone())
 239     {
 240       Standard_Integer i, nbExt = anExtPS.NbExt();
 241       Extrema_POnSurf aPOnSurf;
 242       for (i = 1; i <= nbExt; ++i )
 243         if (anExtPS.Value( i ) <= TolE) {
 244           aPOnSurf = anExtPS.Point( i );
 245           break;
 246         }
 247       if (i <= nbExt) {
 248         // a point found
 249         Standard_Real u, v;
 250         aPOnSurf.Parameter( u, v );
 251         gp_Pnt2d aGoodPm ( u, v );
 252         C2d->Translate( Pm , aGoodPm );
 253       }
 254     }
 255   }
 256
 257   //---------------
 258   // Recadre en U.
 259   //---------------
 260   if (S->IsUPeriodic()) {
 261     Standard_Real period  = S->UPeriod();
 262     Standard_Real eps     = period*1.e-6;
 263     Standard_Real minC    = Min(Pf.X(),Pl.X()); minC = Min(minC,Pm.X());
 264     Standard_Real maxC    = Max(Pf.X(),Pl.X()); maxC = Max(maxC,Pm.X());
 265     Standard_Real du = 0.;
 266     if (minC< umin - eps) {
 267       du = (int((umin - minC)/period) + 1)*period;
 268     }
 269     if (minC > umax + eps) {
 270       du = -(int((minC - umax)/period) + 1)*period;
 271     }
 272     if (du != 0) {
 273       gp_Vec2d T1(du,0.);
 274       C2d->Translate(T1);
 275       minC += du; maxC += du;
 276     }
 277     // Ajuste au mieux la courbe dans le domaine.
 278     if (maxC > umax +100*eps) {
 279       Standard_Real d1 = maxC - umax;
 280       Standard_Real d2 = umin - minC + period;
 281       if (d2 < d1) du =-period;
 282       if ( du != 0.) {
 283         gp_Vec2d T2(du,0.);
 284         C2d->Translate(T2);
 285       }
 286     }
 287   }
 288   //------------------
 289   // Recadre en V.
 290   //------------------
 291   if (S->IsVPeriodic()) {
 292     Standard_Real period  = S->VPeriod();
 293     Standard_Real eps     = period*1.e-6;
 294     Standard_Real minC    = Min(Pf.Y(),Pl.Y()); minC = Min(minC,Pm.Y());
 295     Standard_Real maxC    = Max(Pf.Y(),Pl.Y()); maxC = Max(maxC,Pm.Y());
 296     Standard_Real dv = 0.;
 297     if (minC< vmin - eps) {
 298       dv = (int((vmin - minC)/period) + 1)*period;
 299     }
 300     if (minC > vmax + eps) {
 301       dv = -(int((minC - vmax)/period) + 1)*period;
 302     }
 303     if (dv != 0) {
 304       gp_Vec2d T1(0.,dv);
 305       C2d->Translate(T1);
 306       minC += dv; maxC += dv;
 307     }
 308     // Ajuste au mieux la courbe dans le domaine.
 309     if (maxC > vmax +100*eps) {
 310       Standard_Real d1 = maxC - vmax;
 311       Standard_Real d2 = vmin - minC + period;
 312       if (d2 < d1) dv =-period;
 313       if ( dv != 0.) {
 314         gp_Vec2d T2(0.,dv);
 315         C2d->Translate(T2);
 316       }
 317     }
 318   }
 319 }
 320
 321 //=======================================================================
 322 //function : Inter3D
 323 //purpose  :
 324 //=======================================================================
 325
 326 void Partition_Inter3d::Inter3D(const TopoDS_Face& F1,
 327                                 const TopoDS_Face& F2,
 328                                 TopTools_ListOfShape& L)
 329 {
 330   BRep_Builder B;
 331
 332   // fill the data Structure
 333   Handle(TopOpeBRepDS_HDataStructure) DatStr = new TopOpeBRepDS_HDataStructure();
 334   TopOpeBRep_DSFiller DSFiller;
 335   DSFiller.Insert(F1,F2,DatStr);
 336
 337   // define the GeomTool used by the DSFiller :
 338   // compute BSpline of degree 1 on intersection curves.
 339   Standard_Real tol3dAPPROX = 1e-7;
 340   Standard_Real tol2dAPPROX = 1e-7;
 341   TopOpeBRepTool_GeomTool GT2 (TopOpeBRepTool_APPROX);
 342   GT2.SetTolerances(tol3dAPPROX,tol2dAPPROX);
 343   TopOpeBRepDS_BuildTool  BT(GT2);
 344
 345   // Perform Section
 346   TopOpeBRepBuild_Builder TopB(BT);
 347   TopB.Perform(DatStr);
 348
 349   // ===============
 350   // Store new edges
 351   // ===============
 352
 353   L.Clear();
 354   TopOpeBRepDS_CurveExplorer cex(DatStr->DS());
 355   for (; cex.More(); cex.Next()) {
 356     const TopOpeBRepDS_Curve& CDS = cex.Curve();
 357     Standard_Integer ic = cex.Index();
 358     Handle(Geom2d_Curve) pc1 = CDS.Curve1();
 359     Handle(Geom2d_Curve) pc2 = CDS.Curve2();
 360
 361     TopTools_ListIteratorOfListOfShape itLE = TopB.NewEdges(ic);
 362     while (itLE.More()) {
 363       TopoDS_Edge E = TopoDS::Edge(itLE.Value());
 364
 365       PutInBounds (F1,E,pc1);
 366       PutInBounds (F2,E,pc2);
 367
 368       B.UpdateEdge (E,pc1,F1,0.);
 369       B.UpdateEdge (E,pc2,F2,0.);
 370
 371       L.Append (E);
 372
 373       itLE.Next();
 374       if (itLE.More()) {
 375         pc1 = Handle(Geom2d_Curve)::DownCast(pc1->Copy());
 376         pc2 = Handle(Geom2d_Curve)::DownCast(pc2->Copy());
 377       }
 378     }
 379   }
 380
 381   // ========================
 382   // store same domain faces
 383   // ========================
 384
 385
 386   if ( DatStr->HasSameDomain( F1 ))
 387   {
 388     TopTools_ListOfShape emptyList;
 389     if (!mySameDomainFM.IsBound(F1))
 390       mySameDomainFM.Bind(F1,emptyList);
 391     if (!mySameDomainFM.IsBound(F2))
 392       mySameDomainFM.Bind(F2,emptyList);
 393     mySameDomainFM(F1).Append(F2);
 394     mySameDomainFM(F2).Append(F1);
 395   }
 396
 397   // ====================
 398   // Store section edges
 399   // ====================
 400
 401   const TopOpeBRepDS_DataStructure& DS = DatStr->DS();
 402   Standard_Integer j,i,nse = DS.NbSectionEdges();
 403   if (nse == 0) return;
 404
 405
 406   TopoDS_Vertex V, sdeV1, sdeV2;
 407   TopTools_MapOfShape MV;
 408   TopTools_ListOfShape LSE; // list of section edges
 409   TopoDS_Face dummyF;
 410
 411   for (i = 1; i <= nse; i++)
 412   {
 413     const TopoDS_Edge & se = DS.SectionEdge(i);
 414     if (! TopB.IsSplit(se,TopAbs_ON))
 415       continue;
 416     LSE.Append( se );
 417
 418     // add vertices where section edges interferes with other
 419     // edges as its descendant in myAsDes
 420
 421     TopoDS_Edge sde, oe; // same domain, other edge
 422     if (DatStr->HasSameDomain(se)) {
 423       sde = TopoDS::Edge( DatStr->SameDomain(se).Value() );
 424       TopExp::Vertices( sde, sdeV1, sdeV2);
 425     }
 426     TColStd_MapOfInteger MIV; // indices of added edges
 427     TopOpeBRepDS_PointIterator itP (DS.ShapeInterferences( se ));
 428     itP.SupportKind( TopOpeBRepDS_EDGE );
 429     // loop on intersections of se
 430     for (; itP.More(); itP.Next()) {
 431       oe = TopoDS::Edge( DS.Shape( itP.Support()));
 432       if (itP.IsVertex()) {
 433         // there is a vertex at intersection
 434         if ( !MIV.Add( itP.Current() ))
 435           continue;
 436         V = TopoDS::Vertex( DS.Shape( itP.Current()));
 437         if ( !sde.IsNull() && (V.IsSame(sdeV1) || V.IsSame(sdeV2)) )
 438           oe = sde;
 439         V = ReplaceSameDomainV( V , oe );
 440         V.Orientation( TopAbs_INTERNAL);
 441         B.UpdateVertex( V, itP.Parameter(), se, 0.); // AddVonE() sets real U
 442       }
 443       else {
 444         // create a new vertex at the intersection point
 445         const TopOpeBRepDS_Point& DSP = DS.Point( itP.Current());
 446         V = BRepLib_MakeVertex( DSP.Point() );
 447         V.Orientation( TopAbs_INTERNAL);
 448         B.UpdateVertex( V, itP.Parameter(), se, DSP.Tolerance());
 449         // make V be on the other edge
 450         TopOpeBRepDS_PointIterator itOP (DS.ShapeInterferences( oe ));
 451         for (; itOP.More(); itOP.Next()) {
 452           const TopOpeBRepDS_Point& ODSP = DS.Point( itOP.Current());
 453           if ( DSP.IsEqual (ODSP)) {
 454             B.UpdateVertex( V, itOP.Parameter(), TopoDS::Edge(oe), ODSP.Tolerance());
 455             break;
 456           }
 457         }
 458       }
 459       // add V on the both intersecting edges
 460       TopoDS_Vertex addedV = Partition_Inter2d::AddVonE( V,se,oe,myAsDes,dummyF);
 461       if (!addedV.IsSame( V ))
 462         mySameDomainVM.Bind (V, addedV); // equal vertex is already there
 463
 464       MV.Add( addedV ); // to ease storage of vertices of ON splits
 465     }
 466   }
 467
 468   // add section edge to the face it intersects and find
 469   // splits ON that do not have same domain pair
 470
 471   TopB.SplitSectionEdges(); // let TopB find ON splits
 472
 473   TopTools_MapOfShape SPM; // map of ON splits
 474   TopTools_IndexedMapOfShape ME[2];
 475   TopExp::MapShapes( F1, TopAbs_EDGE, ME[1]);
 476   TopExp::MapShapes( F2, TopAbs_EDGE, ME[0]);
 477
 478   TopTools_ListIteratorOfListOfShape itSP, itLSE (LSE);
 479   while ( itLSE.More() ) {
 480
 481     TopoDS_Edge se = TopoDS::Edge( itLSE.Value() );
 482
 483     // move itLSE to the next se
 484     Standard_Integer ancRank = DS.AncestorRank(se);
 485     if (ME[ancRank-1].Contains( se ))
 486     {
 487       LSE.Remove( itLSE ); // se is an edge of face it intersects
 488       continue;
 489     }
 490     else
 491     {
 492       itLSE.Next();
 493     }
 494
 495     const TopoDS_Face& F = (ancRank == 1) ? F2 : F1;
 496
 497     // add se to face but dont add twice
 498     TopTools_ListIteratorOfListOfShape itE( myAsDes->Descendant( F ));
 499     if (myAsDes->HasDescendant( F )) {
 500       for ( ; itE.More(); itE.Next())
 501         if (se.IsSame( itE.Value() ))
 502           break;
 503     }
 504     if (!itE.More())
 505     {
 506       myAsDes->Add( F, se );
 507
 508       // check se pcurve on F
 509       Standard_Real tol, f,l, umin=1e100, umax=-1e100;
 510       Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( se, F, f,l);
 511       if (pc.IsNull()) {
 512         itSP.Initialize( TopB.Splits(se,TopAbs_ON) );
 513         for ( ; itSP.More(); itSP.Next()) {
 514           const TopoDS_Edge& E = TopoDS::Edge ( itSP.Value());
 515           BRep_Tool::Range(E, f, l);
 516           umin = Min( umin, f);
 517           umax = Max( umax, l);
 518         }
 519         Handle(Geom_Curve) C3d = BRep_Tool::Curve( se, f, l);
 520         if (umin < umax) // sometimes umin == umax for closed edge
 521           C3d = new Geom_TrimmedCurve( C3d, umin, umax);
 522         pc = TopOpeBRepTool_CurveTool::MakePCurveOnFace (F,C3d,tol);
 523         if (pc.IsNull()) {
 524           MESSAGE (" CANT BUILD PCURVE ");
 525         }
 526         B.UpdateEdge( se, pc, F, tol);
 527       }
 528     }
 529
 530     // to detect splits that do not have same domain pair
 531     // ie which split a face into parts and not pass by its boundary
 532     itSP.Initialize( TopB.Splits(se,TopAbs_ON) );
 533     for ( ; itSP.More(); itSP.Next()) {
 534       const TopoDS_Shape& SP = itSP.Value();
 535       if (!SPM.Add( SP ))
 536         SPM.Remove( SP );
 537     }
 538   }
 539
 540   // store vertices of ON splits and bind section edges to faces
 541
 542   for (itLSE.Initialize (LSE); itLSE.More(); itLSE.Next())
 543   {
 544     const TopoDS_Shape& se = itLSE.Value();
 545
 546     Standard_Integer ancRank = DS.AncestorRank(se);
 547     TopoDS_Face F = (ancRank == 1) ? F2 : F1;
 548
 549     // add vertices of ON splits which have no same domain pair
 550     Standard_Boolean added = Standard_False;
 551     itSP.Initialize( TopB.Splits(se,TopAbs_ON) );
 552     for ( ; itSP.More(); itSP.Next())
 553     {
 554       if (!SPM.Contains( itSP.Value() ))
 555         continue;
 556
 557       const TopoDS_Edge& S = TopoDS::Edge ( itSP.Value());
 558
 559       added = Standard_True;
 560       mySectionEdgesAD->Add( F, se );
 561
 562       TopoDS_Vertex VS[2];
 563       TopExp::Vertices (S, VS[0], VS[1]);
 564       for (j=0; j<2; ++j)
 565       {
 566         if (mySameDomainVM.IsBound( VS[j] ))
 567           VS[j] = TopoDS::Vertex( mySameDomainVM( VS[j] ));
 568         if ( !MV.Contains( VS[j] )) {
 569           // find equal vertex on se - point interference
 570           gp_Pnt P1 = BRep_Tool::Pnt( VS[j] );
 571           TopTools_ListIteratorOfListOfShape itV( myAsDes->Descendant(se) );
 572           for (; itV.More(); itV.Next()) {
 573             V = TopoDS::Vertex( itV.Value() );
 574             if ( V.IsSame( VS[j] ))
 575               break;
 576             gp_Pnt P2 = BRep_Tool::Pnt( V );
 577             if (P1.IsEqual( P2, Precision::Confusion())) {
 578               mySameDomainVM.Bind (VS[j], V);
 579               VS[j] = V;
 580               break;
 581             }
 582           }
 583           if (!itV.More())  // no interferences with edges
 584             myAsDes->Add( se, VS[j]);
 585         }
 586
 587         // add ends of ON splits to F in order to detect later
 588         // if a split is on face in IsSplitOn()
 589         mySectionEdgesAD->Add( F, VS[j]);
 590       }
 591       // in the descendants of F, first go ends of an ON split and
 592       // then a split itself
 593       mySectionEdgesAD->Add( F, S );
 594     }
 595     if (!added)
 596       mySectionEdgesAD->Add( F, se );
 597
 598     myNewEdges.Add( se );
 599   }
 600 }
 601
 602 //=======================================================================
 603 //function : FacesPartition
 604 //purpose  :
 605 //=======================================================================
 606
 607 void Partition_Inter3d::FacesPartition(const TopoDS_Face& F1,
 608                                        const TopoDS_Face& F2)
 609      //(const TopTools_DataMapOfShapeListOfShape& /*SetOfFaces2*/)
 610 {
 611   TopTools_ListOfShape LInt;
 612
 613   Inter3D (F1,F2,LInt);
 614
 615   StorePart3d (F1,F2,LInt);
 616 }
 617
 618 //=======================================================================
 619 //function : SetDone
 620 //purpose  :
 621 //=======================================================================
 622
 623 void Partition_Inter3d::SetDone(const TopoDS_Face& F1,
 624                                 const TopoDS_Face& F2)
 625 {
 626   if (!myDone.IsBound(F1)) {
 627     TopTools_ListOfShape emptyList;
 628     myDone.Bind(F1,emptyList);
 629   }
 630   myDone(F1).Append(F2);
 631   if (!myDone.IsBound(F2)) {
 632     TopTools_ListOfShape emptyList;
 633     myDone.Bind(F2,emptyList);
 634   }
 635   myDone(F2).Append(F1);
 636 }
 637
 638 //=======================================================================
 639 //function : IsDone
 640 //purpose  :
 641 //=======================================================================
 642
 643 Standard_Boolean Partition_Inter3d::IsDone(const TopoDS_Face& F1,
 644                                            const TopoDS_Face& F2)
 645
 646   const
 647 {
 648   if (myDone.IsBound(F1)) {
 649     TopTools_ListIteratorOfListOfShape it (myDone(F1));
 650     for (; it.More(); it.Next()) {
 651       if (it.Value().IsSame(F2)) return Standard_True;
 652     }
 653   }
 654   return Standard_False;
 655 }
 656
 657 //=======================================================================
 658 //function : StorePart3d
 659 //purpose  :
 660 //=======================================================================
 661
 662 void Partition_Inter3d::StorePart3d(const TopoDS_Face& F1,
 663                                     const TopoDS_Face& F2,
 664                                     const TopTools_ListOfShape& LInt)
 665 {
 666   if (!LInt.IsEmpty()) {
 667     myAsDes->Add( F1,LInt);
 668     myAsDes->Add( F2,LInt);
 669
 670     TopTools_ListIteratorOfListOfShape it(LInt);
 671     for (; it.More(); it.Next()) {
 672
 673       TopoDS_Edge E = TopoDS::Edge(it.Value());
 674
 675       BRep_Builder B;
 676       B.SameParameter(E,Standard_False);
 677       BRepLib::SameParameter(E,1.0e-7);
 678
 679       myNewEdges.Add(E);
 680     }
 681   }
 682   SetDone(F1,F2);
 683 }
 684
 685 //=======================================================================
 686 //function : TouchedFaces
 687 //purpose  :
 688 //=======================================================================
 689
 690 TopTools_MapOfShape& Partition_Inter3d::TouchedFaces()
 691 {
 692   return myTouched;
 693 }
 694
 695 //=======================================================================
 696 //function : AsDes
 697 //purpose  :
 698 //=======================================================================
 699
 700 Handle(BRepAlgo_AsDes) Partition_Inter3d::AsDes() const
 701 {
 702   return myAsDes;
 703 }
 704
 705 //=======================================================================
 706 //function : NewEdges
 707 //purpose  :
 708 //=======================================================================
 709
 710 TopTools_MapOfShape& Partition_Inter3d::NewEdges()
 711 {
 712   return myNewEdges;
 713 }
 714
 715 //=======================================================================
 716 //function : Affiche
 717 //purpose  :
 718 //=======================================================================
 719
 720 void Partition_Inter3d::Affiche(const TopTools_ListOfShape& SetOfFaces) const
 721 {
 722 #ifdef DEB
 723   char PSection[1024];
 724   char *section=PSection;
 725   Standard_Integer i = 0;
 726   Standard_Real j=1;
 727   TopTools_ListOfShape aList;
 728   TopTools_ListIteratorOfListOfShape it;
 729   for (it.Initialize(SetOfFaces); it.More(); it.Next()) {
 730     const TopoDS_Shape& OS = it.Value();
 731     aList=myAsDes->Descendant(OS);
 732     MESSAGE ( " the number of items stored in the list " << j << " :  " << aList.Extent() )
 733     j++;
 734     TopTools_ListIteratorOfListOfShape itaList;
 735     for (itaList.Initialize(aList); itaList.More(); itaList.Next()) {
 736       const TopoDS_Shape& SS = itaList.Value();
 737       i++;
 738       sprintf(PSection,"section_%d",i);
 739       DBRep::Set(section,SS);
 740     }
 741   }
 742 #endif
 743 }
 744
 745 //=======================================================================
 746 //function : SameDomain
 747 //purpose  :
 748 //=======================================================================
 749
 750 const TopTools_ListOfShape& Partition_Inter3d::SameDomain(const TopoDS_Face& F) const
 751 {
 752   if (mySameDomainFM.IsBound( F ))
 753     return mySameDomainFM (F);
 754
 755   static TopTools_ListOfShape emptyList;
 756   return emptyList;
 757 }
 758
 759 //=======================================================================
 760 //function : HasSameDomainF
 761 //purpose  : Return true if F has same domain faces
 762 //=======================================================================
 763
 764 Standard_Boolean Partition_Inter3d::HasSameDomainF(const TopoDS_Shape& F) const
 765 {
 766   return mySameDomainFM.IsBound( F );
 767 }
 768
 769 //=======================================================================
 770 //function : IsSameDomain
 771 //purpose  : Return true if F1 and F2 are same domain faces
 772 //=======================================================================
 773
 774 Standard_Boolean Partition_Inter3d::IsSameDomainF(const TopoDS_Shape& F1,
 775                                                  const TopoDS_Shape& F2) const
 776 {
 777   if (mySameDomainFM.IsBound( F1 )) {
 778     TopTools_ListIteratorOfListOfShape it (mySameDomainFM( F1 ));
 779     for (; it.More(); it.Next())
 780       if (F2.IsSame( it.Value()))
 781         return Standard_True;
 782   }
 783   return F1.IsSame( F2 );
 784 }
 785
 786 //=======================================================================
 787 //function : ReplaceSameDomainV
 788 //purpose  : return same domain vertex of  V if it was replaced
 789 //           and make this vertex to be on E too, else return V
 790 //=======================================================================
 791
 792 TopoDS_Vertex Partition_Inter3d::ReplaceSameDomainV(const TopoDS_Vertex& V,
 793                                                     const TopoDS_Edge&   E) const
 794 {
 795   TopoDS_Vertex SDV = V;
 796   if (mySameDomainVM.IsBound( V )) {
 797
 798     TopoDS_Vertex V1,V2;
 799     TopExp::Vertices(E,V1,V2);
 800     Standard_Boolean isClosed = V1.IsSame( V2 ) && V.IsSame(V1);
 801
 802     SDV = TopoDS::Vertex( mySameDomainVM(V) );
 803     Standard_Real tol = BRep_Tool::Tolerance( V );
 804     BRep_Builder B;
 805     SDV.Orientation( V.Orientation());
 806
 807     if (isClosed) {
 808       Standard_Real f, l;
 809       BRep_Tool::Range (E, f, l);
 810       Standard_Boolean isFirst = IsEqual( BRep_Tool::Parameter(V,E), f );
 811       B.UpdateVertex(SDV, (isFirst ? f : l), E, tol);
 812       SDV.Reverse();
 813       B.UpdateVertex(SDV, (isFirst ? l : f), E, tol);
 814     }
 815     else
 816       B.UpdateVertex (SDV, BRep_Tool::Parameter(V,E), E, tol);
 817
 818   }
 819   return SDV;
 820 }
 821
 822 //=======================================================================
 823 //function : SectionEdgesAD
 824 //purpose  :
 825 //=======================================================================
 826
 827 Handle(BRepAlgo_AsDes) Partition_Inter3d::SectionEdgesAD() const
 828 {
 829   return mySectionEdgesAD;
 830 }
 831
 832 //=======================================================================
 833 //function : IsSectionEdge
 834 //purpose  : return True if  E  is  an  edge  of  a face and it
 835 //           intersects an other face
 836 //=======================================================================
 837
 838 Standard_Boolean
 839   Partition_Inter3d::IsSectionEdge(const TopoDS_Edge& E) const
 840 {
 841   return mySectionEdgesAD->HasAscendant(E);
 842 }
 843
 844 //=======================================================================
 845 //function : HasSectionEdge
 846 //purpose  : return True if an  edge  of  F intersects an other
 847 //           face or F is intersected by edge of an other face
 848 //=======================================================================
 849
 850 Standard_Boolean
 851   Partition_Inter3d::HasSectionEdge(const TopoDS_Face& F) const
 852 {
 853   return mySectionEdgesAD->HasDescendant(F);
 854 }
 855
 856 //=======================================================================
 857 //function : IsSplitOn
 858 //purpose  : return True if NewE is split of OldE on F
 859 //=======================================================================
 860
 861 Standard_Boolean
 862   Partition_Inter3d::IsSplitOn(const TopoDS_Edge& NewE,
 863                                const TopoDS_Edge& OldE,
 864                                const TopoDS_Face& F) const
 865 {
 866   if (! mySectionEdgesAD->HasDescendant(F))
 867     return Standard_False;
 868
 869   TopTools_ListIteratorOfListOfShape itE ( mySectionEdgesAD->Descendant(F) );
 870   for ( ; itE.More(); itE.Next()) {
 871     if ( itE.Value().ShapeType() != TopAbs_EDGE ||
 872         ! OldE.IsSame ( itE.Value() ))
 873       continue;
 874     // an edge encountered, its vertices and a split come next
 875     itE.Next();
 876     if (!itE.More()) break;
 877     const TopoDS_Shape& V3 = itE.Value();
 878     if (V3.ShapeType() != TopAbs_VERTEX) continue;
 879     itE.Next();
 880     if (!itE.More()) break;
 881     const TopoDS_Shape& V4 = itE.Value();
 882     if (V4.ShapeType() != TopAbs_VERTEX) continue;
 883
 884     TopoDS_Vertex V1, V2;
 885     TopExp::Vertices( OldE, V1, V2);
 886
 887     if ( V1.IsSame(V2) &&
 888         (V1.IsSame(V3) || V1.IsSame(V4)) ) {
 889       // closed old edge; use the split for the test
 890       itE.Next();
 891       if (!itE.More()) break;
 892       const TopoDS_Edge& split = TopoDS::Edge( itE.Value() );
 893       // check distance at middle point of NewE
 894       Standard_Real f1,l1, f2,l2;
 895       Handle(Geom2d_Curve) PC1 = BRep_Tool::CurveOnSurface( split, F ,f1,l1);
 896       if (!PC1.IsNull()) {
 897         Handle(Geom2d_Curve) PC2 = BRep_Tool::CurveOnSurface(NewE, F ,f2,l2);
 898         gp_Pnt2d P = PC2->Value( 0.5*(f2+l2) );
 899         Geom2dAPI_ProjectPointOnCurve proj (P, PC1, f1, l1);
 900         if (proj.NbPoints() &&
 901             proj.LowerDistance() <= Precision::Confusion())
 902           return Standard_True;
 903       }
 904       else {
 905         Handle(Geom_Curve) C1 = BRep_Tool::Curve( split ,f1,l1);
 906         Handle(Geom_Curve) C2 = BRep_Tool::Curve( NewE  ,f2,l2);
 907         gp_Pnt P = C2->Value( 0.5*(f2+l2) );
 908         GeomAPI_ProjectPointOnCurve proj (P, C1, f1, l1);
 909         if (proj.NbPoints() &&
 910             proj.LowerDistance() <= Precision::Confusion())
 911           return Standard_True;
 912       }
 913     }
 914     else {
 915       Standard_Real u3 = BRep_Tool::Parameter( TopoDS::Vertex(V3), OldE);
 916       Standard_Real u4 = BRep_Tool::Parameter( TopoDS::Vertex(V4), OldE);
 917
 918       Standard_Real f,l, u;
 919       BRep_Tool::Range( NewE, f,l);
 920       u = 0.5*(f+l);
 921       f = Min(u3,u4);
 922       l = Max(u3,u4);
 923
 924       if (u <= l && u >= f)
 925         return Standard_True;
 926     }
 927   }
 928   return Standard_False;
 929 }
 930
 931 //=======================================================================
 932 //function : SectionEdgeFaces
 933 //purpose  : return faces cut by section edge
 934 //=======================================================================
 935
 936 const TopTools_ListOfShape&
 937   Partition_Inter3d::SectionEdgeFaces(const TopoDS_Edge& SecE) const
 938 {
 939   return mySectionEdgesAD->Ascendant( SecE );
 940 }