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