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