src/PARTITION/Partition_Inter2d.cxx

   1 using namespace std;
   2 //  File      : Partition_Inter2d.cxx
   3 //  Created   : Thu Aug 02 16:17:31 2001
   4 //  Author    : Benedicte MARTIN
   5 //  Project   : SALOME
   6 //  Module    : PARTITION
   7 //  Copyright : Open CASCADE
   8 //  $Header$
   9
  10 #include "Partition_Inter2d.ixx"
  11
  12 #include "utilities.h"
  13
  14 #include <TopExp.hxx>
  15 #include <TopExp_Explorer.hxx>
  16
  17 #include <BRepAlgo_AsDes.hxx>
  18
  19 #include <BRep_Builder.hxx>
  20 #include <BRep_Tool.hxx>
  21 #include <BRepLib_MakeVertex.hxx>
  22 #include <BRepAdaptor_Curve.hxx>
  23
  24 #include <gp_Pnt.hxx>
  25 #include <TopoDS.hxx>
  26 #include <TopoDS_Edge.hxx>
  27 #include <TopoDS_Vertex.hxx>
  28 #include <TopOpeBRep_EdgesIntersector.hxx>
  29 #include <TopOpeBRep_Point2d.hxx>
  30 #include <TopOpeBRepDS_Transition.hxx>
  31 #include <TopTools_ListOfShape.hxx>
  32 #include <TopTools_ListIteratorOfListOfShape.hxx>
  33 #include <TopTools_MapOfShape.hxx>
  34 #include <TopTools_MapIteratorOfMapOfShape.hxx>
  35
  36 #include <stdio.h>
  37 #include <Precision.hxx>
  38
  39 #ifdef DEB
  40 static Standard_Boolean TestEdges = 0;
  41 static Standard_Integer NbF2d = 0;
  42 static Standard_Integer NbE2d = 0;
  43 #endif
  44
  45 //=======================================================================
  46 //function : StorePart2d
  47 //purpose  :
  48 //=======================================================================
  49
  50 // static void  StorePart2d (const TopoDS_Edge&       E1,
  51 //                        const TopoDS_Edge&       E2,
  52 //                        TopTools_ListOfShape&    LV1,
  53 //                        TopTools_ListOfShape&    LV2,
  54 //                        Handle(BRepAlgo_AsDes)   AsDes,
  55 //                        Standard_Real            Tol)
  56 TopoDS_Vertex Partition_Inter2d::AddVonE(const TopoDS_Vertex& theV,
  57                                          const TopoDS_Edge&   E1,
  58                                          const TopoDS_Edge&   E2,
  59                                          const Handle(BRepAlgo_AsDes)& AsDes)
  60
  61 {
  62   //-------------------------------------------------------------
  63   // test if the points of intersection already exist. If not,
  64   // add as descendants of the edges.
  65   // nb: theses points are only vertices of intersection.
  66   //-------------------------------------------------------------
  67   const TopTools_ListOfShape& VOnE1 = AsDes->Descendant(E1);
  68   const TopTools_ListOfShape& VOnE2 = AsDes->Descendant(E2);
  69   TopTools_ListOfShape        NewVOnE1;
  70   TopTools_ListOfShape        NewVOnE2;
  71   gp_Pnt                      P1,P2;
  72   TopoDS_Vertex               V1,V2;
  73   TopTools_ListIteratorOfListOfShape it, itLV1, itLV2;
  74   BRep_Builder                       B;
  75   TopAbs_Orientation                 O1,O2;
  76   Standard_Real                      U1,U2;
  77   Standard_Real                      Tol,Tol1,Tol2;
  78   Standard_Boolean                   OnE1,OnE2;
  79
  80 //   for (itLV1.Initialize(LV1),itLV2.Initialize(LV2);
  81 //        itLV1.More();
  82 //        itLV1.Next()  ,itLV2.Next()) {
  83
  84     TopoDS_Vertex V    = theV;
  85 //     TopoDS_Vertex V    = TopoDS::Vertex(itLV1.Value());
  86
  87     U1 = BRep_Tool::Parameter(V,E1);
  88     U2 = BRep_Tool::Parameter(V,E2);
  89     O1 = V.Orientation();
  90     O2 = O1;///itLV2.Value().Orientation();
  91     P1  = BRep_Tool::Pnt(V);
  92     Tol = BRep_Tool::Tolerance( V );
  93     OnE1 = OnE2 = Standard_False;
  94
  95     //-----------------------------------------------------------------
  96     // Search if the point of intersection is a vertex of E1.
  97     //-----------------------------------------------------------------
  98     for (it.Initialize(VOnE1); it.More(); it.Next()) {
  99       const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
 100       if (V.IsSame( CV )) {
 101         V1   = V;
 102         OnE1 = Standard_True;
 103         break;
 104       }
 105       P2 = BRep_Tool::Pnt( CV );
 106       Tol1 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
 107       if (P1.SquareDistance(P2) <= Tol1*Tol1) {
 108         V    = CV;
 109         V1   = V;
 110         OnE1 = Standard_True;
 111         break;
 112       }
 113     }
 114     if (OnE1) {
 115       //-----------------------------------------------------------------
 116       // Search if the vertex found is still on E2.
 117       //-----------------------------------------------------------------
 118       for (it.Initialize(VOnE2); it.More(); it.Next()) {
 119         if (V.IsSame( it.Value() )) {
 120           OnE2 = Standard_True;
 121           V2   = V;
 122           break;
 123         }
 124       }
 125     }
 126     if (!OnE2) {
 127       for (it.Initialize(VOnE2); it.More(); it.Next()) {
 128         //-----------------------------------------------------------------
 129         // Search if the point of intersection is a vertex of E2.
 130         //-----------------------------------------------------------------
 131         const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
 132         P2 = BRep_Tool::Pnt( CV );
 133         Tol2 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
 134         if (P1.SquareDistance(P2) <= Tol2*Tol2) {
 135           V  = CV;
 136           V2 = V;
 137           OnE2 = Standard_True;
 138           break;
 139         }
 140       }
 141     }
 142     if (OnE1 && OnE2) {
 143       if (!V1.IsSame(V2)) {
 144         Standard_Real UV2;
 145         TopoDS_Edge   EWE2;
 146         TopoDS_Vertex VI;
 147         const TopTools_ListOfShape& EdgeWithV2 = AsDes->Ascendant(V2);
 148
 149         for (it.Initialize(EdgeWithV2); it.More(); it.Next()) {
 150           EWE2  = TopoDS::Edge(it.Value());
 151           VI = V2;
 152           VI.Orientation(TopAbs_INTERNAL);
 153           UV2 = BRep_Tool::Parameter(VI,EWE2);
 154           VI = V1;
 155           VI.Orientation(TopAbs_INTERNAL);
 156           B.UpdateVertex(VI,UV2,EWE2, Max(Tol1,Tol2));
 157         }
 158         AsDes->Replace(V2,V1);
 159       }
 160     }
 161     // add existing vertices instead of new ones
 162     if (!OnE1) {
 163       if (OnE2) {
 164         V.Orientation(TopAbs_INTERNAL);
 165         B.UpdateVertex(V,U1,E1, Tol2);
 166       }
 167       V.Orientation(O1);
 168       NewVOnE1.Prepend(V);
 169     }
 170     if (!OnE2) {
 171       if (OnE1) {
 172         V.Orientation(TopAbs_INTERNAL);
 173         B.UpdateVertex(V,U2,E2, Tol1);
 174       }
 175       V.Orientation(O2);
 176       NewVOnE2.Prepend(V);
 177     }
 178 //  }
 179
 180   if (!NewVOnE1.IsEmpty()) AsDes->Add(E1,NewVOnE1);
 181   if (!NewVOnE2.IsEmpty()) AsDes->Add(E2,NewVOnE2);
 182
 183   return V;
 184 }
 185
 186 //=======================================================================
 187 //function : FindEndVertex
 188 //purpose  : Returns a vertex  from  <VertList> having parameter on
 189 //           <E>  closest  to  <f>  or  <l>.  <isFirst>  is True if
 190 //           found vertex is closer  to <f>. <DU> returns parameter
 191 //           difference.
 192 //=======================================================================
 193
 194 TopoDS_Vertex Partition_Inter2d::FindEndVertex(const TopTools_ListOfShape& LV,
 195                                                const Standard_Real f,
 196                                                const Standard_Real l,
 197                                                const TopoDS_Edge&  E,
 198                                                Standard_Boolean&   isFirst,
 199                                                Standard_Real&      minDU)
 200 {
 201   TopoDS_Vertex endV;
 202   Standard_Real U, endU, min;
 203   minDU = 1.e10;
 204
 205   TopTools_ListIteratorOfListOfShape it;
 206   it.Initialize(LV);
 207   for (; it.More(); it.Next()) {
 208     const TopoDS_Vertex& v = TopoDS::Vertex(it.Value());
 209     U = BRep_Tool::Parameter(v, E);
 210     min = Min( Abs(U-f), Abs(U-l) );
 211     if (min < minDU) {
 212       endV = v;
 213       endU = U;
 214       minDU = min;
 215     }
 216   }
 217   if (Abs(endU-f) < Abs(endU-l))
 218     isFirst = Standard_True;
 219   else
 220     isFirst = Standard_False;
 221
 222   return endV;
 223 }
 224
 225 //=======================================================================
 226 //function : treatClosed
 227 //purpose  : add second vertex to closed edge. Vertex is one of <LV1>
 228 //=======================================================================
 229
 230 static void treatClosed (const TopoDS_Edge& E1,
 231                           const Standard_Real f,
 232                           const Standard_Real l,
 233                           TopTools_ListOfShape& LV1,
 234                           TopTools_ListOfShape& /*LV2*/)
 235 {
 236   Standard_Boolean isFirst=0;
 237   Standard_Real    minDU = 1.e10;
 238   TopoDS_Vertex endV;
 239   endV = Partition_Inter2d::FindEndVertex(LV1, f,l, E1, isFirst,minDU);
 240
 241   if (minDU > Precision::PConfusion())
 242     return; // not end point
 243
 244   Standard_Real newU;
 245   if (isFirst)
 246     newU = f + (l - f);
 247   else
 248     newU = l - (l - f);
 249
 250   // update end parameter
 251   BRep_Builder B;
 252   endV.Orientation(TopAbs_INTERNAL);
 253   B.UpdateVertex(endV,newU,E1,BRep_Tool::Tolerance(endV));
 254 }
 255
 256 //=======================================================================
 257 //function : EdgesPartition
 258 //purpose  :
 259 //=======================================================================
 260
 261 static void EdgesPartition(const TopoDS_Face&            F,
 262                            const TopoDS_Edge&            E1,
 263                            const TopoDS_Edge&            E2,
 264                            const Handle(BRepAlgo_AsDes)& AsDes,
 265                            const TopTools_MapOfShape&    NewEdges,
 266                            const Standard_Boolean        WithOri)
 267 {
 268
 269   Standard_Real f[3],l[3];
 270   Standard_Real MilTol2;
 271   Standard_Real Tol = Max (BRep_Tool::Tolerance(E1),
 272                            BRep_Tool::Tolerance(E2));
 273   MilTol2 = Tol * Tol * 10;
 274
 275   BRep_Tool::Range(E1, f[1], l[1]);
 276   BRep_Tool::Range(E2, f[2], l[2]);
 277
 278   BRepAdaptor_Curve CE1(E1,F);
 279   BRepAdaptor_Curve CE2(E2,F);
 280
 281   TopoDS_Edge                 EI[3]; EI[1] = E1; EI[2] = E2;
 282   TopTools_ListOfShape        LV1; // new vertices at intersections on E1
 283   TopTools_ListOfShape        LV2; // ... on E2
 284   BRep_Builder                B;
 285
 286   // if E1 and E2 are results of intersection of F and two connex faces then
 287   // no need to intersect edges, they can contact by vertices only
 288   // (encounted an exception in TopOpeBRep_EdgesIntersector in such a case)
 289   Standard_Boolean intersect = Standard_True;
 290   TopTools_IndexedMapOfShape ME;
 291   TopExp::MapShapes(F, TopAbs_EDGE, ME);
 292   if (!ME.Contains(E1) && ! ME.Contains(E2)) { // if E1 and E2 are new on F
 293     TopoDS_Shape F1, F2;
 294     const TopTools_ListOfShape& LF1 = AsDes->Ascendant( E1 );
 295     F1 = F.IsSame( LF1.First() ) ? LF1.Last() : LF1.First();
 296     const TopTools_ListOfShape& LF2 = AsDes->Ascendant( E2 );
 297     F2 = F.IsSame( LF2.First() ) ? LF2.Last() : LF2.First();
 298     if (!F.IsSame(F2) && !F.IsSame(F1) ) {
 299       TopExp_Explorer exp(F2, TopAbs_EDGE);
 300       TopExp::MapShapes(F1, TopAbs_EDGE, ME);
 301       for (; exp.More(); exp.Next()) {
 302         if (ME.Contains( exp.Current())) {
 303           intersect = Standard_False;
 304           break;
 305         }
 306       }
 307     }
 308   }
 309
 310   if (intersect) {
 311     //------------------------------------------------------
 312     // compute the points of Intersection in 2D
 313     //-----------------------------------------------------
 314     // i.e. fill LV1 and LV2
 315     TopOpeBRep_EdgesIntersector EInter;
 316     EInter.SetFaces(F,F);
 317     Standard_Real TolDub = 1.e-7;
 318     EInter.ForceTolerances(TolDub,TolDub);
 319     Standard_Boolean reducesegments = Standard_False;
 320     EInter.Perform (E1,E2,reducesegments);
 321
 322     Standard_Boolean rejectreducedsegmentpoints = Standard_False;
 323     EInter.InitPoint(rejectreducedsegmentpoints);
 324     for (;EInter.MorePoint();EInter.NextPoint()) {
 325       const TopOpeBRep_Point2d& P2D = EInter.Point();
 326       const gp_Pnt&    P    = P2D.Value();
 327       TopoDS_Vertex    V    = BRepLib_MakeVertex(P);
 328
 329       //-------------------------
 330       // control the point found.
 331       //-------------------------
 332       gp_Pnt P1 = CE1.Value(P2D.Parameter(1));
 333       gp_Pnt P2 = CE2.Value(P2D.Parameter(2));
 334       Standard_Real sqd1 = P1.SquareDistance(P);
 335       Standard_Real sqd2 = P2.SquareDistance(P);
 336       if (sqd1 > MilTol2 || sqd2 > MilTol2  ) {
 337         //MESSAGE ( "Inter2d : Solution rejected, dist: " << sqrt(Max(sqd1,sqd2)) )
 338 #ifdef DEB
 339         if (TestEdges) {
 340           MESSAGE ( " edges : E2d_"<<NbE2d-2<<" E2d_"<<NbE2d-1 ); }
 341 #endif
 342         continue;
 343       }
 344
 345       // add a new vertex to the both edges
 346       Standard_Real toler = 1.5 * Max (Tol, sqrt(Max(sqd1,sqd2)) );
 347       Standard_Integer i;
 348       for (i = 1; i <= 2; i++) {
 349         Standard_Real U = P2D.Parameter(i);
 350 #ifdef DEB
 351         if (U < f[i]-Tol  || U > l[i]+Tol) {
 352           MESSAGE ( "out" );
 353         }
 354 #endif
 355         V.Orientation(TopAbs_INTERNAL);
 356         B.UpdateVertex( V,U,EI[i], toler);
 357         TopAbs_Orientation OO = TopAbs_REVERSED;
 358         if (WithOri) {
 359           if (P2D.IsVertex(i))
 360             OO = P2D.Vertex(i).Orientation();
 361           else if (P2D.Transition(i).Before() == TopAbs_OUT) {
 362             OO = TopAbs_FORWARD;
 363           }
 364           V.Orientation(OO);
 365           if (i == 1) LV1.Append(V);
 366           else        LV2.Append(V);
 367         }
 368       }
 369     }
 370   } // if (intersect)
 371
 372   //----------------------------------
 373   // Test the extremities of the edges.
 374   //----------------------------------
 375   // add to LV* vertices for vertex-vertex closeness
 376   Standard_Real U1,U2;
 377   Standard_Real TolConf2, TolConf;
 378   TopoDS_Vertex V1[2],V2[2];
 379   TopExp::Vertices(E1,V1[0],V1[1]);
 380   TopExp::Vertices(E2,V2[0],V2[1]);
 381
 382   Standard_Integer i,j,k;
 383   for (j = 0; j < 2; j++) {
 384     if (V1[j].IsNull()) continue;
 385     for ( k = 0; k < 2; k++) {
 386       if (V2[k].IsNull()) continue;
 387       gp_Pnt P1 = BRep_Tool::Pnt(V1[j]);
 388       gp_Pnt P2 = BRep_Tool::Pnt(V2[k]);
 389       TolConf = BRep_Tool::Tolerance(V1[j]) + BRep_Tool::Tolerance(V2[k]);
 390       TolConf = Max (Tol, TolConf);
 391       TolConf2 = TolConf * TolConf;
 392       if (!intersect)
 393         TolConf2 *= 100;
 394       Standard_Real SqDist = P1.SquareDistance(P2);
 395
 396       if (SqDist <= TolConf2) {
 397         TopoDS_Vertex V = BRepLib_MakeVertex(P1);
 398         V.Orientation(TopAbs_INTERNAL);
 399         U1 = (j == 0) ? f[1] : l[1];
 400         U2 = (k == 0) ? f[2] : l[2];
 401         B.UpdateVertex(V,U1,E1,TolConf);
 402         B.UpdateVertex(V,U2,E2,TolConf);
 403         LV1.Prepend(V.Oriented(V1[j].Orientation()));
 404         LV2.Prepend(V.Oriented(V2[k].Orientation()));
 405       }
 406     }
 407   }
 408
 409   Standard_Boolean AffichPurge = Standard_False;
 410
 411   if ( LV1.IsEmpty()) return;
 412
 413   //----------------------------------
 414   // Purge of all the vertices.
 415   //----------------------------------
 416   // remove one of close vertices
 417   TopTools_ListIteratorOfListOfShape it1LV1,it1LV2,it2LV1;
 418   gp_Pnt P1,P2;
 419   Standard_Boolean Purge = Standard_True;
 420
 421   while (Purge) {
 422     i = 1;
 423     Purge = Standard_False;
 424     for (it1LV1.Initialize(LV1),it1LV2.Initialize(LV2);
 425          it1LV1.More(); it1LV1.Next(),it1LV2.Next()) {
 426       j = 1;
 427       it2LV1.Initialize(LV1);
 428       while (j < i) {
 429         const TopoDS_Vertex& VE1 = TopoDS::Vertex(it1LV1.Value());
 430         const TopoDS_Vertex& VE2 = TopoDS::Vertex(it2LV1.Value());
 431         Standard_Real Tol1 = BRep_Tool::Tolerance( VE1 );
 432         Standard_Real Tol2 = BRep_Tool::Tolerance( VE2 );
 433         P1 = BRep_Tool::Pnt( VE1 );
 434         P2 = BRep_Tool::Pnt( VE2 );
 435         if (P1.IsEqual(P2, Tol1 + Tol2)) {
 436           LV1.Remove(it1LV1);
 437           LV2.Remove(it1LV2);
 438           if (AffichPurge) {
 439             MESSAGE ("Vertices confused purged in EdgeInter.")
 440             }
 441           Purge = Standard_True;
 442           break;
 443         }
 444         j++;
 445         it2LV1.Next();
 446       }
 447       if (Purge) break;
 448       i++;
 449     }
 450   }
 451
 452   // care of new closed edges, they always intersect with seam at end
 453   if (V1[0].IsSame( V1[1] ) && NewEdges.Contains(E1) )
 454     treatClosed (E1,f[1],l[1],LV1,LV2);
 455   if (V2[0].IsSame( V2[1] ) && NewEdges.Contains(E2) )
 456     treatClosed (E2,f[2],l[2],LV2,LV1);
 457
 458   //---------------------------------
 459   // Stocking vertex .
 460   //---------------------------------
 461
 462   //StorePart2d (E1,E2,LV1,LV2,AsDes,Tol);
 463   for ( it1LV1.Initialize( LV1 ); it1LV1.More(); it1LV1.Next())
 464     Partition_Inter2d::AddVonE ( TopoDS::Vertex( it1LV1.Value()), E1,E2,AsDes);
 465 }
 466
 467 //=======================================================================
 468 //function : CompletPart2d
 469 //purpose  : Computes the intersections between the edges stored
 470 //           is AsDes as descendants of <F> . Intersections is computed
 471 //           between two edges if one of them is bound in NewEdges.
 472 //=======================================================================
 473
 474 void Partition_Inter2d::CompletPart2d (const Handle(BRepAlgo_AsDes)&   AsDes,
 475                                        const TopoDS_Face&              F,
 476                                        const TopTools_MapOfShape&      NewEdges)
 477 {
 478
 479 #ifdef DEB
 480   NbF2d++;
 481   NbE2d = 0;
 482 #endif
 483
 484   //Do not intersect the edges of a face
 485   TopTools_IndexedMapOfShape EdgesOfFace;
 486   TopExp::MapShapes( F, TopAbs_EDGE , EdgesOfFace);
 487
 488   //-------------------------------------------------------------------
 489   // compute the intersection2D on the faces touched by the intersection3D
 490   //-------------------------------------------------------------------
 491   TopTools_ListIteratorOfListOfShape it1LE ;
 492   TopTools_ListIteratorOfListOfShape it2LE ;
 493
 494   //-----------------------------------------------
 495   // Intersection edge-edge.
 496   //-----------------------------------------------
 497   const TopTools_ListOfShape&        LE = AsDes->Descendant(F);
 498   TopoDS_Vertex                      V1,V2;
 499   Standard_Integer                   j, i = 1;
 500
 501   TopoDS_Face FF = F;
 502   FF.Orientation(TopAbs_FORWARD);
 503
 504   for ( it1LE.Initialize(LE) ; it1LE.More(); it1LE.Next()) {
 505     const TopoDS_Edge& E1 = TopoDS::Edge(it1LE.Value());
 506     j = 1;
 507     it2LE.Initialize(LE);
 508
 509     while (j < i && it2LE.More()) {
 510       const TopoDS_Edge& E2 = TopoDS::Edge(it2LE.Value());
 511       //----------------------------------------------------------
 512       // Intersections of the new edges obtained by intersection
 513       // between them and with the restrictions edges
 514       //----------------------------------------------------------
 515       if ( (!EdgesOfFace.Contains(E1) || !EdgesOfFace.Contains(E2)) &&
 516            (NewEdges.Contains(E1) || NewEdges.Contains(E2)) ) {
 517         EdgesPartition(FF,E1,E2,AsDes,NewEdges,Standard_True);
 518       }
 519       it2LE.Next();
 520       j++;
 521     }
 522     i++;
 523   }
 524 }
 525