src/BRepMesh/BRepMesh_FastDiscret.cxx

   1 // File:        BRepMesh_FastDiscret.cxx
   2 // Created:     Tue Feb 27 16:39:53 1996
   3 // Author:      Ekaterina SMIRNOVA
   4 // Copyright: Open CASCADE SAS 2008
   5
   6 #include <BRepMesh_FastDiscret.ixx>
   7
   8 #include <BRepMesh_FastDiscretFace.hxx>
   9 #include <BRepMesh_FaceAttribute.hxx>
  10 #include <BRepMesh_DataStructureOfDelaun.hxx>
  11 #include <BRepMesh_ClassifierPtr.hxx>
  12 #include <BRepMesh_GeomTool.hxx>
  13 #include <BRepMesh_PairOfPolygon.hxx>
  14 #include <BRepMesh_DataMapOfShapePairOfPolygon.hxx>
  15 #include <BRepMesh_DataMapIteratorOfDataMapOfShapePairOfPolygon.hxx>
  16 #include <GeomAbs_IsoType.hxx>
  17 #include <GeomAbs_SurfaceType.hxx>
  18 #include <TopAbs.hxx>
  19 #include <TColStd_HArray1OfReal.hxx>
  20 #include <Precision.hxx>
  21
  22 #include <BRep_Builder.hxx>
  23 #include <BRep_Tool.hxx>
  24 #include <Poly_Triangulation.hxx>
  25 #include <Poly_PolygonOnTriangulation.hxx>
  26 #include <Poly_Connect.hxx>
  27 #include <TColStd_SequenceOfInteger.hxx>
  28 #include <TColStd_Array1OfInteger.hxx>
  29 #include <TColStd_HArray1OfInteger.hxx>
  30
  31 #include <TColgp_Array1OfPnt.hxx>
  32 #include <TColgp_Array1OfPnt2d.hxx>
  33 #include <Precision.hxx>
  34
  35 #include <BRepAdaptor_Curve.hxx>
  36 #include <BRepAdaptor_Surface.hxx>
  37 #include <BRepAdaptor_HSurface.hxx>
  38 #include <BRepTools.hxx>
  39 #include <BndLib_Add3dCurve.hxx>
  40 #include <BRepBndLib.hxx>
  41 #include <Bnd_Box.hxx>
  42 #include <TopoDS.hxx>
  43 #include <TopExp.hxx>
  44 #include <TopExp_Explorer.hxx>
  45
  46 #include <Geom2d_Curve.hxx>
  47
  48 #include <TColStd_DataMapOfIntegerInteger.hxx>
  49 #include <BRepMesh_ShapeTool.hxx>
  50 #include <ElSLib.hxx>
  51 #include <Geom_Surface.hxx>
  52 #include <Adaptor3d_IsoCurve.hxx>
  53 #include <BRepMesh_IndexedMapOfVertex.hxx>
  54 #include <Extrema_LocateExtPC.hxx>
  55
  56 #include <BRepMesh_ListOfXY.hxx>
  57 #include <BRepMesh_ListIteratorOfListOfXY.hxx>
  58
  59 #include <TColStd_Array1OfInteger.hxx>
  60 #include <BRepMesh_IDMapOfNodeOfDataStructureOfDelaun.hxx>
  61 #include <Standard_ErrorHandler.hxx>
  62 #include <Standard_Failure.hxx>
  63 //#include <TColStd_DataMapOfInteger.hxx>
  64 #include <TColGeom2d_SequenceOfCurve.hxx>
  65 #include <TopTools_SequenceOfShape.hxx>
  66 #include <NCollection_IncAllocator.hxx>
  67
  68 #include <BRep_ListIteratorOfListOfPointRepresentation.hxx>
  69 #include <BRep_PointRepresentation.hxx>
  70 #include <BRep_TVertex.hxx>
  71 #include <TColStd_MapOfInteger.hxx>
  72 #include <SortTools_ShellSortOfReal.hxx>
  73 #include <TCollection_CompareOfReal.hxx>
  74
  75 #include <TopTools_HArray1OfShape.hxx>
  76 #include <TopTools_ListIteratorOfListOfShape.hxx>
  77
  78 #include <vector>
  79
  80 // NOTE: replaced by more correct check
  81 // #if defined(WNT) || defined(LIN)
  82 // #define HAVE_TBB 1
  83 // #endif
  84
  85 // paralleling with Intel TBB
  86 #ifdef HAVE_TBB
  87 #include <tbb/parallel_for_each.h>
  88 #endif
  89
  90 inline Standard_Real MaxFaceTol (const TopoDS_Face& theFace)
  91 {
  92   Standard_Real T, TMax = BRep_Tool::Tolerance(theFace);
  93   TopExp_Explorer Ex;
  94
  95   for (Ex.Init(theFace,TopAbs_EDGE); Ex.More(); Ex.Next())
  96   {
  97     T = BRep_Tool::Tolerance(TopoDS::Edge(Ex.Current()));
  98     if (T > TMax) TMax = T;
  99   }
 100
 101   for (Ex.Init(theFace,TopAbs_VERTEX); Ex.More(); Ex.Next())
 102   {
 103     T = BRep_Tool::Tolerance(TopoDS::Vertex(Ex.Current()));
 104     if (T > TMax) TMax = T;
 105   }
 106
 107   return TMax;
 108 }
 109
 110
 111 //=======================================================================
 112 //function : BRepMesh_FastDiscret
 113 //purpose  :
 114 //=======================================================================
 115 BRepMesh_FastDiscret::BRepMesh_FastDiscret(const Standard_Real    theDefle,
 116                                            const Standard_Real    theAngl,
 117                                            const Bnd_Box&         theBox,
 118                                            const Standard_Boolean theWithShare,
 119                                            const Standard_Boolean theInshape,
 120                                            const Standard_Boolean theRelative,
 121                                            const Standard_Boolean theShapetrigu) :
 122   myAngle(theAngl), myDeflection(theDefle),myWithShare(theWithShare),
 123   myNbLocat(0), myRelative(theRelative), myShapetrigu(theShapetrigu),
 124   myInshape(theInshape)
 125 {
 126   myAllocator = new NCollection_IncAllocator(64000);
 127   if (theRelative)
 128   {
 129     Standard_Real TXmin, TYmin, TZmin, TXmax, TYmax, TZmax;
 130     theBox.Get(TXmin, TYmin, TZmin, TXmax, TYmax, TZmax);
 131     myDtotale = TXmax-TXmin;
 132     const Standard_Real dy = TYmax-TYmin;
 133     const Standard_Real dz = TZmax-TZmin;
 134     if (dy > myDtotale) myDtotale = dy;
 135     if (dz > myDtotale) myDtotale = dz;
 136   }
 137 }
 138
 139 //=======================================================================
 140 //function : BRepMesh_FastDiscret
 141 //purpose  :
 142 //=======================================================================
 143
 144 BRepMesh_FastDiscret::BRepMesh_FastDiscret(const Standard_Real    theDefle,
 145                                            const TopoDS_Shape&    theShape,
 146                                            const Bnd_Box&         theBox,
 147                                            const Standard_Real    theAngl,
 148                                            const Standard_Boolean theWithShare,
 149                                            const Standard_Boolean theInshape,
 150                                            const Standard_Boolean theRelative,
 151                                            const Standard_Boolean theShapetrigu):
 152   myAngle(theAngl), myDeflection(theDefle),myWithShare(theWithShare),
 153   myNbLocat(0), myRelative(theRelative), myShapetrigu(theShapetrigu),
 154   myInshape(theInshape)
 155 {
 156   myAllocator = new NCollection_IncAllocator(64000);
 157   if (theRelative)
 158   {
 159     Standard_Real TXmin, TYmin, TZmin, TXmax, TYmax, TZmax;
 160     theBox.Get(TXmin, TYmin, TZmin, TXmax, TYmax, TZmax);
 161     myDtotale = TXmax-TXmin;
 162     const Standard_Real dy = TYmax-TYmin;
 163     const Standard_Real dz = TZmax-TZmin;
 164     if (dy > myDtotale) myDtotale = dy;
 165     if (dz > myDtotale) myDtotale = dz;
 166   }
 167   Perform(theShape);
 168 }
 169
 170 //=======================================================================
 171 //function : Perform(shape)
 172 //purpose  :
 173 //=======================================================================
 174
 175 void BRepMesh_FastDiscret::Perform(const TopoDS_Shape& theShape)
 176 {
 177   std::vector<TopoDS_Face> aFaces;
 178   for (TopExp_Explorer ex(theShape, TopAbs_FACE); ex.More(); ex.Next()) {
 179     TopoDS_Face aF = TopoDS::Face(ex.Current());
 180     Add(aF);
 181     aFaces.push_back(aF);
 182   }
 183
 184   // mesh faces in parallel threads using TBB
 185 #ifdef HAVE_TBB
 186   if (Standard::IsReentrant())
 187     tbb::parallel_for_each (aFaces.begin(), aFaces.end(), *this);
 188   else
 189 #endif
 190   for (std::vector<TopoDS_Face>::iterator it(aFaces.begin()); it != aFaces.end(); it++)
 191     Process (*it);
 192 }
 193
 194
 195 //=======================================================================
 196 //function : Process
 197 //purpose  :
 198 //=======================================================================
 199
 200 void BRepMesh_FastDiscret::Process(const TopoDS_Face& theFace) const
 201 {
 202   //cout << "START face " << theFace.TShape().operator->() << endl << flush;
 203   Handle(BRepMesh_FaceAttribute) fattribute;
 204   if ( GetFaceAttribute (theFace, fattribute) )
 205   {
 206     BRepMesh_FastDiscretFace aTool (GetAngle(), WithShare());
 207     aTool.Add (theFace, fattribute, GetMapOfDefEdge());
 208   }
 209   //cout << "END   face " << theFace.TShape().operator->() << endl << flush;
 210 }
 211
 212 //=======================================================================
 213 //function : Add(face)
 214 //purpose  :
 215 //=======================================================================
 216
 217 #define MESH_FAILURE(theface)        \
 218 {                                    \
 219   myFacestate = BRepMesh_Failure;    \
 220   myNottriangulated.Append(theface); \
 221   return;                            \
 222 }
 223
 224 void BRepMesh_FastDiscret::Add(const TopoDS_Face& theface)
 225 {
 226 #ifndef DEB_MESH
 227   try
 228   {
 229     OCC_CATCH_SIGNALS
 230 #endif
 231   TopoDS_Face face = theface;
 232   BRepTools::Update(face);
 233   face.Orientation(TopAbs_FORWARD);
 234   myStructure.Nullify();
 235   Handle(NCollection_IncAllocator) anAlloc = Handle(NCollection_IncAllocator)::DownCast(myAllocator);
 236   anAlloc->Reset(Standard_False);
 237   myStructure=new BRepMesh_DataStructureOfDelaun(anAlloc);
 238   BRepAdaptor_Surface  BS(face, Standard_False);
 239   Handle(BRepAdaptor_HSurface) gFace = new BRepAdaptor_HSurface(BS);
 240
 241   GeomAbs_SurfaceType thetype;
 242   thetype = BS.GetType();
 243
 244   gp_Pnt2d uvFirst, uvLast;
 245
 246   TopAbs_Orientation orFace = face.Orientation();
 247   Handle(Poly_Triangulation) T;
 248   TopLoc_Location loc;
 249
 250   if (!myWithShare) {
 251     myVertices.Clear();
 252     myEdges.Clear();
 253   }
 254
 255   myVemap.Clear();
 256   myLocation2d.Clear();
 257   myInternaledges.Clear();
 258
 259   Standard_Integer i;
 260   i = 1;
 261
 262   Standard_Real defedge, defface;
 263   Standard_Real aXmin, aYmin, aZmin, aXmax, aYmax, aZmax, dx, dy, dz;
 264   Standard_Integer nbEdge = 0;
 265   Standard_Real savangle = myAngle;
 266   Standard_Real cdef;
 267   Standard_Real maxdef = 2.* MaxFaceTol(theface);
 268   defface = 0.;
 269
 270   if (!myRelative) defface = Max(myDeflection, maxdef);
 271
 272   TColStd_SequenceOfReal aFSeq, aLSeq;
 273   TColGeom2d_SequenceOfCurve aCSeq;
 274   TopTools_SequenceOfShape aShSeq;
 275
 276   TopoDS_Iterator exW(face);
 277
 278   for (; exW.More(); exW.Next()) {
 279     const TopoDS_Shape& aWire = exW.Value();
 280     if (aWire.ShapeType() != TopAbs_WIRE)
 281       continue;
 282     TopoDS_Iterator ex(aWire);
 283     for(; ex.More(); ex.Next()) {
 284       const TopoDS_Edge& edge = TopoDS::Edge(ex.Value());
 285       nbEdge++;
 286       if (!myMapdefle.IsBound(edge)) {
 287         if (myRelative) {
 288           if (myEdges.IsBound(edge)) {
 289             const BRepMesh_PairOfPolygon& pair = myEdges.Find(edge);
 290             const Handle(Poly_PolygonOnTriangulation)& P = pair.First();
 291             defedge = P->Deflection();
 292           }
 293           else {
 294             Bnd_Box B;
 295             BRepBndLib::Add(edge, B);
 296             B.Get(aXmin, aYmin, aZmin, aXmax, aYmax, aZmax);
 297             dx = aXmax-aXmin;
 298             dy = aYmax-aYmin;
 299             dz = aZmax-aZmin;
 300             defedge = dx;
 301             if (defedge < dy) defedge = dy;
 302             if (defedge < dz) defedge = dz;
 303             // adjusted in relation to the total size:
 304             cdef = myDtotale/(2*defedge);
 305             if (cdef < 0.5) cdef = 0.5;
 306             if (cdef > 2.) cdef = 2.;
 307             defedge = cdef * defedge * myDeflection;
 308             myAngle = savangle * cdef;
 309           }
 310           defface = defface + defedge;
 311           defface = Max(maxdef, defface);
 312         }
 313         else defedge = myDeflection;
 314
 315         defedge = Max(maxdef, defedge);
 316         defedge = Max(1.e-05 , defedge);
 317         myMapdefle.Bind(edge, defedge);
 318       }
 319       else{
 320         defedge = myMapdefle(edge);
 321         if (myRelative) {defface = defface + defedge; defface = Max(maxdef, defface);}
 322       }
 323       Standard_Real f1,l1;
 324       Handle(Geom2d_Curve) C = BRep_Tool::CurveOnSurface(edge, face, f1, l1);
 325       if (C.IsNull()) continue;
 326
 327       aFSeq.Append(f1);
 328       aLSeq.Append(l1);
 329       aCSeq.Append(C);
 330       aShSeq.Append(edge);
 331       Add(edge, face, gFace, C, defedge, f1, l1);
 332       myAngle = savangle;
 333     }
 334   }
 335
 336   if (nbEdge == 0 || myVemap.Extent() < 3)
 337   {
 338       MESH_FAILURE(theface);
 339   }
 340
 341   if (myRelative ) defface = defface / nbEdge;
 342   else             defface = myDeflection;
 343
 344   if (myWithShare) defface = Max(maxdef, defface);
 345
 346   T = BRep_Tool::Triangulation(face, loc);
 347
 348   if (!myShapetrigu || T.IsNull()) {
 349
 350     Standard_Real xCur, yCur;
 351     Standard_Real maxX, minX, maxY, minY;
 352     minX=minY=1.e100;
 353     maxX=maxY=-1.e100;
 354
 355     Standard_Integer ipn = 0;
 356     Standard_Integer i1 =1;
 357     for (i1 = 1; i1 <= myVemap.Extent(); i1++) {
 358       const BRepMesh_Vertex& aV = myStructure->GetNode(myVemap.FindKey(i1));
 359       ipn++;
 360       xCur=aV.Coord().X();
 361       yCur=aV.Coord().Y();
 362       minX=Min(xCur, minX);
 363       maxX=Max(xCur, maxX);
 364       minY=Min(yCur, minY);
 365       maxY=Max(yCur, maxY);
 366     }
 367     Standard_Real myumin = minX;
 368     Standard_Real myumax = maxX;
 369     Standard_Real myvmin = minY;
 370     Standard_Real myvmax = maxY;
 371
 372     const Standard_Real umin = BS.FirstUParameter();
 373     const Standard_Real umax = BS.LastUParameter();
 374     const Standard_Real vmin = BS.FirstVParameter();
 375     const Standard_Real vmax = BS.LastVParameter();
 376
 377     if (myumin < umin || myumax > umax)
 378     {
 379       if (BS.IsUPeriodic())
 380       {
 381         if ((myumax - myumin) > (umax - umin))
 382         {
 383           myumax = myumin + (umax - umin);
 384         }
 385       }
 386       else
 387       {
 388         if (umin > myumin) myumin = umin;
 389         if (umax < myumax) myumax = umax;
 390       }
 391     }
 392
 393     if (myvmin < vmin || myvmax > vmax)
 394     {
 395       if (BS.IsVPeriodic())
 396       {
 397         if ((myvmax - myvmin) > (vmax - vmin))
 398         {
 399           myvmax = myvmin + (vmax - vmin);
 400         }
 401       }
 402       else
 403       {
 404         if (vmin > myvmin) myvmin = vmin;
 405         if (vmax < myvmax) myvmax = vmax;
 406       }
 407     }
 408
 409     // fast verification of the validity of calculated limits. If wrong,
 410     // sure a problem of pcurve.
 411     if (thetype == GeomAbs_BezierSurface &&
 412         (myumin < -0.5 || myumax > 1.5 || myvmin < -0.5 || myvmax > 1.5))
 413     {
 414       MESH_FAILURE(theface);
 415     }
 416
 417     //define parameters for correct parametrics
 418
 419     Standard_Real deltaX = 1.0;
 420     Standard_Real deltaY = 1.0;
 421     Standard_Integer nbVertices = myVemap.Extent();
 422     const Standard_Real tolclass = Precision::PConfusion(); //0.03*Max(myumax-myumin, myvmax-myvmin);
 423
 424     BRepMesh_ClassifierPtr classifier (
 425       new BRepMesh_Classifier(face, tolclass,  myInternaledges, myVemap,
 426                               myStructure, myumin, myumax, myvmin, myvmax) );
 427
 428     myFacestate = classifier->State();
 429     if (myFacestate == BRepMesh_SelfIntersectingWire)
 430     {
 431       Standard_Integer nbmaill = 0;
 432       Standard_Real eps = Precision::Confusion();
 433       while (nbmaill < 5 && myFacestate != BRepMesh_ReMesh)
 434       {
 435         nbmaill++;
 436
 437         //clear the structure of links
 438         myStructure.Nullify();
 439         myStructure = new BRepMesh_DataStructureOfDelaun(anAlloc);
 440
 441         myVemap.Clear();
 442         myLocation2d.Clear();
 443         myInternaledges.Clear();
 444
 445         Standard_Integer j1;
 446         for(j1 = 1; j1 <= aShSeq.Length(); j1++)
 447         {
 448           const TopoDS_Edge& edge = TopoDS::Edge(aShSeq.Value(j1));
 449           if (myEdges.IsBound(edge))
 450           {
 451             myEdges.UnBind(edge);
 452             myInternaledges.UnBind(edge);
 453           }
 454         }
 455
 456
 457         for( j1 = 1; j1 <= aShSeq.Length(); j1++)
 458         {
 459           const TopoDS_Edge& edge = TopoDS::Edge(aShSeq.Value(j1));
 460           defedge = myMapdefle(edge) / 3.;
 461           defedge = Max(defedge, eps);
 462           myMapdefle.Bind(edge, defedge);
 463           const Handle(Geom2d_Curve)& C = aCSeq.Value(j1);
 464           Add(edge, face, gFace, C, defedge, aFSeq.Value(j1), aLSeq.Value(j1));
 465         }
 466
 467         classifier.Nullify();
 468
 469         classifier = new BRepMesh_Classifier(face, tolclass, myInternaledges, myVemap,
 470                                              myStructure, myumin, myumax, myvmin, myvmax);
 471
 472         if (classifier->State() == BRepMesh_NoError)
 473         {
 474           myFacestate = BRepMesh_ReMesh;
 475         }
 476         nbVertices = myVemap.Extent();
 477       }
 478     }
 479
 480     if (myFacestate != BRepMesh_NoError && myFacestate != BRepMesh_ReMesh)
 481     {
 482       myNottriangulated.Append(face);
 483       classifier.Nullify();
 484       return;
 485     }
 486
 487     // try to find the real length:
 488     // akm (bug OCC16) : We must calculate these measures in non-singular
 489     //     parts of face. Let's try to compute average value of three
 490     //     (umin, (umin+umax)/2, umax), and respectively for v.
 491     //                 vvvvv
 492     Standard_Real longu = 0.0, longv = 0.0; //, last , first;
 493     gp_Pnt P11, P12, P21, P22, P31, P32;
 494
 495     Standard_Real du = (myumax-myumin)/20;
 496     Standard_Real dv = (myvmax-myvmin)/20;
 497     Standard_Real dfuave=(myumin+myumax)/2, dfucur;
 498     Standard_Real dfvave=(myvmin+myvmax)/2, dfvcur;
 499     // U loop
 500     BS.D0 (myumin, myvmin, P11);
 501     BS.D0 (myumin, dfvave, P21);
 502     BS.D0 (myumin, myvmax, P31);
 503     for (i1=0, dfucur=myumin; i1 <= 20; i1++, dfucur+=du)  {
 504       BS.D0 (dfucur, myvmin, P12);
 505       BS.D0 (dfucur, dfvave, P22);
 506       BS.D0 (dfucur, myvmax, P32);
 507       longu += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
 508       P11 = P12;
 509       P21 = P22;
 510       P31 = P32;
 511     }
 512     // V loop
 513     BS.D0(myumin, myvmin, P11);
 514     BS.D0(dfuave, myvmin, P21);
 515     BS.D0(myumax, myvmin, P31);
 516     for (i1=0, dfvcur=myvmin; i1 <= 20; i1++, dfvcur+=dv) {
 517       BS.D0 (myumin, dfvcur, P12);
 518       BS.D0 (dfuave, dfvcur, P22);
 519       BS.D0 (myumax, dfvcur, P32);
 520       longv += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
 521       P11 = P12;
 522       P21 = P22;
 523       P31 = P32;
 524     }
 525     longu /= 3.;
 526     longv /= 3.;
 527     // akm (bug OCC16) ^^^^^
 528
 529     if (longu <= 1.e-16 || longv <= 1.e-16) {
 530       //yes, it is seen!!
 531 #ifdef DEB_MESH_CHRONO
 532       chMaillEdges.Stop();
 533       MESH_CHRONO_TSTOP(thetype);
 534 #endif
 535       MESH_FAILURE(theface);
 536     }
 537
 538
 539     if (thetype == GeomAbs_Torus)  {
 540       gp_Torus Tor = BS.Torus();
 541       Standard_Real r = Tor.MinorRadius(), R = Tor.MajorRadius();
 542       Standard_Real Du, Dv;//, pasu, pasv;
 543
 544       Dv = Max(1.0e0 - (defface/r),0.0e0) ;
 545       Standard_Real oldDv = 2.0 * ACos (Dv);
 546       oldDv = Min(oldDv, myAngle);
 547       Dv  =  0.9*oldDv; //TWOTHIRD * oldDv;
 548       Dv = oldDv;
 549
 550       Standard_Integer nbV = Max((Standard_Integer)((myvmax-myvmin)/Dv), 2);
 551       Dv = (myvmax-myvmin)/(nbV+1);
 552
 553       Standard_Real ru = R + r;
 554       if (ru > 1.e-16) {
 555         Du = Max(1.0e0 - (defface/ru),0.0e0);
 556         Du  = (2.0 * ACos (Du));
 557         Du = Min(Du, myAngle);
 558         Standard_Real aa = sqrt(Du*Du + oldDv*oldDv);
 559         if(aa < gp::Resolution())
 560           return;
 561
 562         Du = Du * Min(oldDv, Du) / aa;
 563       }
 564       else Du = Dv;
 565
 566       Standard_Integer nbU = Max((Standard_Integer)((myumax-myumin)/Du), 2);
 567       nbU = Max(nbU, (Standard_Integer)(nbV*(myumax-myumin)*R/((myvmax-myvmin)*r)/5.));
 568
 569       Du = (myumax-myumin)/(nbU+1);
 570       //-- DeltaX and DeltaY are chosen so that to avoid "jumping"
 571       //-- of points on the grid
 572       deltaX = Du;
 573       deltaY = Dv;
 574     }
 575     else if (thetype == GeomAbs_Cylinder) {
 576       /*Standard_Real aMax = Max(myumax,myvmax);
 577       deltaX = 0.01;  //1./aMax; //0.01;
 578       deltaY = 1.0;*/
 579       gp_Cylinder Cyl = BS.Cylinder();
 580       Standard_Real R = Cyl.Radius();
 581       // Calculate parameters for iteration in U direction
 582       Standard_Real Du = 1.0 - (defface/R);
 583       if (Du < 0.0) Du = 0.0;
 584       Du = 2.0 * ACos (Du);
 585       if (Du > GetAngle()) Du = GetAngle();
 586       deltaX = Du/longv;
 587       deltaY = 1.;
 588     }
 589     else {
 590       deltaX = (myumax-myumin)/longu;
 591       deltaY = (myvmax-myvmin)/longv;
 592     }
 593
 594     if(!myMapattrib.IsBound(theface))
 595     {
 596       Handle(BRepMesh_FaceAttribute) aFA = new BRepMesh_FaceAttribute();
 597       aFA->GetDefFace() = defface;
 598       aFA->GetUMax() = myumax;
 599       aFA->GetVMax() = myvmax;
 600       aFA->GetUMin() = myumin;
 601       aFA->GetVMin() = myvmin;
 602       aFA->GetDeltaX() = deltaX;
 603       aFA->GetDeltaY() = deltaY;
 604       aFA->GetMinX() = minX;
 605       aFA->GetMinY() = minY;
 606       aFA->GetClassifier() = classifier;
 607       myMapattrib.Bind(theface, aFA);
 608     }
 609
 610     //Standard_Integer nbVertices = myVemap.Extent();
 611     T = new Poly_Triangulation(nbVertices, 1, Standard_True);
 612     TColgp_Array1OfPnt&  Nodes = T->ChangeNodes();
 613     TColgp_Array1OfPnt2d& Nodes2d = T->ChangeUVNodes();
 614
 615     Standard_Integer index;
 616     for (i = 1; i <= nbVertices; i++) {
 617       index = myVemap.FindKey(i);
 618       Nodes(i) = Pnt(index);
 619       Nodes2d(i).SetXY(Vertex(index).Coord());
 620     }
 621
 622     // storage of triangulation in the BRep.
 623     //TopLoc_Location loc = face.Location();
 624     if (!loc.IsIdentity()) {
 625       gp_Trsf tr = loc.Transformation();
 626       tr.Invert();
 627       for (i = Nodes.Lower(); i <= Nodes.Upper(); i++)
 628         Nodes(i).Transform(tr);
 629     }
 630
 631     BRep_Builder B;
 632     B.UpdateFace(face, T);
 633
 634     BRepMesh_DataMapIteratorOfDataMapOfShapePairOfPolygon It(myInternaledges);
 635     for (; It.More(); It.Next()) {
 636       const BRepMesh_PairOfPolygon& pair = It.Value();
 637       const Handle(Poly_PolygonOnTriangulation)& NOD1 = pair.First();
 638       const Handle(Poly_PolygonOnTriangulation)& NOD2 = pair.Last();
 639       if ( NOD1 == NOD2 )
 640         B.UpdateEdge(TopoDS::Edge(It.Key()), NOD1, T, loc);
 641       else
 642         B.UpdateEdge(TopoDS::Edge(It.Key()), NOD1, NOD2, T, loc);
 643     }
 644   }
 645
 646 #ifndef DEB_MESH
 647   }
 648   catch(Standard_Failure)
 649   {
 650     MESH_FAILURE(theface);
 651   }
 652 #endif // DEB_MESH
 653   myStructure.Nullify();
 654 }
 655
 656
 657 //=======================================================================
 658 //function : Add
 659 //purpose  :
 660 //=======================================================================
 661 void BRepMesh_FastDiscret::Add( const TopoDS_Edge&                  theEdge,
 662                                 const TopoDS_Face&                  theFace,
 663                                 const Handle(BRepAdaptor_HSurface)& theGFace,
 664                                 const Handle(Geom2d_Curve)&         theC2d,
 665                                 const Standard_Real                 theDefEdge,
 666                                 const Standard_Real                 theFirst,
 667                                 const Standard_Real                 theLast)
 668 {
 669   const TopAbs_Orientation orEdge = theEdge.Orientation();
 670   if (orEdge == TopAbs_EXTERNAL) return;
 671
 672   const Standard_Boolean isEdgeBound = myEdges.IsBound(theEdge);
 673
 674   if (!isEdgeBound)
 675   {
 676     if (Update(theEdge, theFace, theC2d, theDefEdge, theFirst, theLast))
 677     {
 678       return;
 679     }
 680   }
 681
 682   TopoDS_Vertex pBegin, pEnd;
 683   TopExp::Vertices(theEdge, pBegin, pEnd);
 684   if (pBegin.IsNull() || pEnd.IsNull())
 685   {
 686     return;
 687   }
 688
 689   Standard_Real wFirst, wLast;
 690   BRep_Tool::Range(theEdge, theFace, wFirst, wLast);
 691
 692   gp_Pnt2d uvFirst, uvLast;
 693   BRep_Tool::UVPoints(theEdge, theFace, uvFirst, uvLast);
 694
 695   const Standard_Boolean sameUV = uvFirst.IsEqual(uvLast, Precision::PConfusion());
 696
 697   //Control vertexes tolerances
 698   gp_Pnt pFirst = theGFace->Value(uvFirst.X(), uvFirst.Y());
 699   gp_Pnt pLast  = theGFace->Value(uvLast.X(), uvLast.Y());
 700
 701   Standard_Real mindist = 10. * Max(pFirst.Distance(BRep_Tool::Pnt(pBegin)),
 702                                     pLast.Distance(BRep_Tool::Pnt(pEnd)));
 703
 704   if(mindist < BRep_Tool::Tolerance(pBegin) ||
 705      mindist < BRep_Tool::Tolerance(pEnd) ) mindist = theDefEdge;
 706
 707   // control of degenerated non-coded edges.
 708
 709   Standard_Boolean degener = BRep_Tool::Degenerated(theEdge);
 710
 711   if (!degener)
 712   {
 713     if (pBegin.IsSame(pEnd))
 714     {
 715       // calculation of the length of the edge in 3D
 716       Standard_Real longueur = 0.0;
 717       Standard_Real du = (wLast-wFirst)/20;
 718       gp_Pnt P1, P2;
 719       BRepAdaptor_Curve BC(theEdge);
 720       BC.D0(wFirst, P1);
 721       Standard_Real tolV = BRep_Tool::Tolerance(pBegin);
 722       Standard_Real tolV2 = 1.2*tolV;
 723       for (Standard_Integer l = 1; l <= 20; l++) {
 724         BC.D0(wFirst + l*du, P2);
 725         longueur += P1.Distance(P2);
 726         if (longueur > tolV2) break;
 727         P1 = P2;
 728       }
 729
 730       if (longueur < tolV2)
 731       {
 732         degener = Standard_True;
 733       }
 734     }
 735   }
 736
 737   // Correct UV points
 738   if (sameUV)
 739   {
 740     // 1. is it really sameUV without being degenerated
 741     gp_Pnt2d uvF, uvL;
 742     theC2d->D0(theFirst, uvF);
 743     theC2d->D0(theLast, uvL);
 744     if (!uvFirst.IsEqual(uvF, Precision::PConfusion()))
 745     {
 746       uvFirst = uvF;
 747     }
 748     if (!uvLast.IsEqual(uvL, Precision::PConfusion()))
 749     {
 750       uvLast = uvL;
 751     }
 752   }
 753
 754   gp_XY theUV;
 755
 756   // Process first vertex
 757   Standard_Integer ipf;
 758   if (myVertices.IsBound(pBegin))
 759   {
 760     ipf = myVertices.Find(pBegin);
 761   }
 762   else
 763   {
 764     if (sameUV && myVertices.IsBound(pEnd))
 765     {
 766       ipf = myVertices.Find(pEnd);
 767     }
 768     else
 769     {
 770       myNbLocat++;
 771       ipf = myNbLocat;
 772       myLocation3d.Bind(ipf, BRep_Tool::Pnt(pBegin));
 773     }
 774     myVertices.Bind(pBegin, ipf);
 775   }
 776   theUV = BRepMesh_FastDiscretFace::FindUV(pBegin, uvFirst, ipf, theGFace, mindist, myLocation2d);
 777   BRepMesh_Vertex vf(theUV, ipf, BRepMesh_Frontier);
 778   Standard_Integer ivf = myStructure->AddNode(vf);
 779
 780   // Process last vertex
 781   Standard_Integer ipl;
 782   if (pEnd.IsSame(pBegin))
 783   {
 784     ipl = ipf;
 785   }
 786   else
 787   {
 788     if (myVertices.IsBound(pEnd))
 789     {
 790       ipl = myVertices.Find(pEnd);
 791     }
 792     else
 793     {
 794       if (sameUV)
 795       {
 796         ipl = ipf;
 797       }
 798       else
 799       {
 800         myNbLocat++;
 801         ipl = myNbLocat;
 802         myLocation3d.Bind(ipl, BRep_Tool::Pnt(pEnd));
 803       }
 804       myVertices.Bind(pEnd,ipl);
 805     }
 806   }
 807   theUV = BRepMesh_FastDiscretFace::FindUV(pEnd, uvLast, ipl, theGFace, mindist, myLocation2d);
 808   BRepMesh_Vertex vl(theUV, ipl, BRepMesh_Frontier);
 809   Standard_Integer ivl= myStructure->AddNode(vl);
 810
 811   Standard_Integer isvf = myVemap.FindIndex(ivf);
 812   if (isvf == 0) isvf = myVemap.Add(ivf);
 813   Standard_Integer isvl = myVemap.FindIndex(ivl);
 814   if (isvl == 0) isvl = myVemap.Add(ivl);
 815
 816   Standard_Real otherdefedge = 0.5*theDefEdge;
 817   gp_Pnt2d uv;
 818   BRepMesh_Vertex v2;
 819   gp_Pnt   P3d;
 820
 821   Handle(Poly_PolygonOnTriangulation) P1;
 822
 823   if (!isEdgeBound)
 824   {
 825     Handle(Poly_PolygonOnTriangulation) P2;
 826
 827     if (degener)
 828     {
 829       // creation anew:
 830       TColStd_Array1OfInteger Nodes(1, 2), NodInStruct(1, 2);
 831       TColStd_Array1OfReal Param(1, 2);
 832
 833       NodInStruct(1) = ipf;
 834       Nodes(1) = isvf;
 835       Param(1) = wFirst;
 836
 837       NodInStruct(2) = ipl;
 838       Nodes(2) = isvl;
 839       Param(2) = wLast;
 840
 841       P1 = new Poly_PolygonOnTriangulation(Nodes, Param);
 842       P2 = new Poly_PolygonOnTriangulation(NodInStruct, Param);
 843     }
 844     else
 845     {
 846       if (orEdge == TopAbs_INTERNAL) otherdefedge *= 0.5;
 847
 848       BRepAdaptor_Curve cons;
 849       if (BRep_Tool::SameParameter(theEdge))
 850       {
 851         cons.Initialize(theEdge);
 852       }
 853       else
 854       {
 855         cons.Initialize(theEdge, theFace);
 856       }
 857
 858       TopLoc_Location L;
 859       Standard_Integer nbpmin = 2;
 860       if (cons.GetType() == GeomAbs_Circle) nbpmin = 4; //OCC287
 861       BRepMesh_GeomTool GT(cons, wFirst, wLast, 0.5*myAngle, otherdefedge, nbpmin);
 862
 863       // PTv, chl/922/G9, Take into account internal vertices
 864       // it is necessary for internal edges, which do not split other edges, by their vertex
 865       TopoDS_Iterator exV(theEdge);
 866       for ( ; exV.More(); exV.Next() )
 867       {
 868         TopoDS_Vertex aIntV = TopoDS::Vertex(exV.Value());
 869         if ( aIntV.Orientation() == TopAbs_INTERNAL )
 870          GT.AddPoint(BRep_Tool::Pnt(aIntV),
 871                      BRep_Tool::Parameter(aIntV, theEdge),
 872                      Standard_True);
 873       }
 874
 875       // Creation des polygones sur triangulation:
 876       Standard_Real puv;
 877       Standard_Integer i;
 878       Standard_Real aEdgeLen = 0., a2dEdgeLen = 0.;
 879       gp_Pnt P3dPrev;
 880       gp_Pnt2d uvPrev;
 881       GT.Value(cons, theGFace, 1, puv, P3dPrev, uvPrev);
 882       for (i = 2; i <= GT.NbPoints(); i++)
 883       {
 884         // Record 3d point
 885               GT.Value(cons, theGFace, i, puv, P3d, uv);
 886         aEdgeLen += P3d.SquareDistance(P3dPrev);
 887         a2dEdgeLen += uv.SquareDistance(uvPrev);
 888         P3dPrev = P3d;
 889         uvPrev = uv;
 890       }
 891
 892       Standard_Integer nbnodes = GT.NbPoints();
 893       Standard_Real aMinToler = Min(theDefEdge, myDeflection);
 894       if(aEdgeLen < aMinToler*aMinToler)
 895       {
 896         //check 2D resolution
 897         Standard_Real ddu = theGFace->UResolution(aMinToler);
 898         Standard_Real ddv = theGFace->VResolution(aMinToler);
 899         Standard_Real aMin = Min(ddu, ddv);
 900
 901         if(a2dEdgeLen < aMin*aMin)
 902           nbnodes = 2;
 903       }
 904       TColStd_Array1OfInteger Nodes(1, nbnodes);
 905       TColStd_Array1OfInteger NodInStruct(1, nbnodes);
 906       TColStd_Array1OfReal Param(1, nbnodes);
 907
 908       // processing of the 1st point:
 909       Nodes(1) = isvf;
 910       NodInStruct(1) = ipf;
 911       Param(1) = wFirst;
 912
 913       // last point:
 914       Nodes(nbnodes) = isvl;
 915       NodInStruct(nbnodes) = ipl;
 916       Param(nbnodes) = wLast;
 917
 918       if(nbnodes > 2)
 919       {
 920         Standard_Integer iv2;
 921         for (i = 2; i < GT.NbPoints(); i++)
 922         {
 923           // Record 3d point
 924           GT.Value(cons, theGFace, i, puv, P3d, uv);
 925           myNbLocat++;
 926           myLocation3d.Bind(myNbLocat, P3d);
 927           NodInStruct(i) = myNbLocat;
 928           // Record 2d point
 929           v2.Initialize(uv.Coord(), myNbLocat, BRepMesh_OnCurve);
 930           iv2=myStructure->AddNode(v2);
 931
 932           Standard_Integer isv = myVemap.FindIndex(iv2);
 933           if (isv == 0) isv = myVemap.Add(iv2);
 934           Nodes(i) = isv;
 935           NodInStruct(i) = myNbLocat;
 936           Param(i) = puv;
 937
 938           if (orEdge == TopAbs_FORWARD)
 939             myStructure->AddLink(BRepMesh_Edge(ivf, iv2, BRepMesh_Frontier));
 940           else if (orEdge == TopAbs_REVERSED)
 941             myStructure->AddLink(BRepMesh_Edge(iv2, ivf, BRepMesh_Frontier));
 942           else if (orEdge == TopAbs_INTERNAL)
 943             myStructure->AddLink(BRepMesh_Edge(ivf, iv2, BRepMesh_Fixed));
 944           ivf = iv2;
 945         }
 946       }
 947
 948       P1 = new Poly_PolygonOnTriangulation(Nodes, Param);
 949       P2 = new Poly_PolygonOnTriangulation(NodInStruct, Param);
 950     }
 951
 952     P2->Deflection(otherdefedge);
 953     BRepMesh_PairOfPolygon pair;
 954     pair.Append(P2);
 955     myEdges.Bind(theEdge, pair);
 956
 957     if (ivf != ivl) {
 958       if (orEdge == TopAbs_FORWARD)
 959         myStructure->AddLink(BRepMesh_Edge(ivf, ivl, BRepMesh_Frontier));
 960       else if (orEdge == TopAbs_REVERSED)
 961         myStructure->AddLink(BRepMesh_Edge(ivl, ivf, BRepMesh_Frontier));
 962       else if (orEdge == TopAbs_INTERNAL)
 963         myStructure->AddLink(BRepMesh_Edge(ivf, ivl, BRepMesh_Fixed));
 964     }
 965
 966
 967   }
 968   // If this Edge has been already checked and it is not degenerated,
 969   // the points of the polygon calculated at the first check are retrieved :
 970   else
 971   {
 972     if (degener)
 973     {
 974       // Create 2d polygon for degenerated edge
 975       TColStd_Array1OfInteger Nodes(1, 2);
 976       TColStd_Array1OfReal PPar(1, 2);
 977
 978       Nodes(1) = isvf;
 979       PPar(1) = wFirst;
 980
 981       Nodes(2) = isvl;
 982       PPar(2) = wLast;
 983
 984       P1 = new Poly_PolygonOnTriangulation(Nodes, PPar);
 985     }
 986     else
 987     {
 988       // retrieve the polygone:
 989       const BRepMesh_PairOfPolygon& pair = myEdges.Find(theEdge);
 990       const Handle(Poly_PolygonOnTriangulation)& P = pair.First();
 991       const TColStd_Array1OfInteger& NOD = P->Nodes();
 992       Handle(TColStd_HArray1OfReal) Par = P->Parameters();
 993
 994       // creation anew:
 995       const Standard_Integer nbnodes = NOD.Length();
 996       TColStd_Array1OfInteger Nodes(1, nbnodes);
 997       TColStd_Array1OfReal PPar(1, nbnodes);
 998       Standard_Integer iv2;
 999
1000       Nodes(1) = isvf;
1001       PPar(1) = wFirst;
1002
1003       Nodes(nbnodes) = isvl;
1004       PPar(nbnodes) = wLast;
1005
1006       if (nbnodes > 2)
1007       {
1008         Standard_Integer i;
1009         if (BRep_Tool::SameParameter(theEdge))
1010         {
1011           for (i = 2; i < nbnodes; i++)
1012           {
1013             const Standard_Real puv = Par->Value(i);
1014             theC2d->D0(puv, uv);
1015             v2.Initialize(uv.Coord(), NOD(i), BRepMesh_OnCurve);
1016             iv2 = myStructure->AddNode(v2);
1017
1018             Standard_Integer isv = myVemap.FindIndex(iv2);
1019             if (isv == 0) isv = myVemap.Add(iv2);
1020             Nodes(i) = isv;
1021             PPar(i) = puv;
1022
1023             if (orEdge==TopAbs_FORWARD)
1024               myStructure->AddLink(BRepMesh_Edge(ivf, iv2, BRepMesh_Frontier));
1025             else if (orEdge == TopAbs_REVERSED)
1026               myStructure->AddLink(BRepMesh_Edge(iv2, ivf, BRepMesh_Frontier));
1027             else if (orEdge == TopAbs_INTERNAL)
1028               myStructure->AddLink(BRepMesh_Edge(ivf, iv2, BRepMesh_Fixed));
1029
1030             ivf = iv2;
1031           }
1032         }
1033         else
1034         {
1035           const Standard_Real wFold = Par->Value(Par->Lower());
1036           const Standard_Real wLold = Par->Value(Par->Upper());
1037
1038           Standard_Real wKoef = 1.;
1039           if ((wFold != wFirst || wLold != wLast) && wLold != wFold)
1040           {
1041             wKoef = (wLast - wFirst) / (wLold - wFold);
1042           }
1043
1044           BRepAdaptor_Curve cons(theEdge, theFace);
1045           Extrema_LocateExtPC pcos;
1046           pcos.Initialize(cons, cons.FirstParameter(),
1047               cons.LastParameter(), Precision::PConfusion());
1048
1049           Standard_Real wPrev;
1050           Standard_Real wCur      = wFirst;
1051           Standard_Real wCurFound = wFirst;
1052           for (i = 2; i < nbnodes; i++)
1053           {
1054             P3d = myLocation3d(NOD(i));
1055             // Record 2d point
1056             wPrev = wCur;
1057             wCur  = wFirst + wKoef*(Par->Value(i) - wFold);
1058                   wCurFound += (wCur - wPrev);
1059             pcos.Perform(P3d, wCurFound);
1060             if (pcos.IsDone()) wCurFound = pcos.Point().Parameter();
1061             theC2d->D0(wCurFound, uv);
1062             v2.Initialize(uv.Coord(), NOD(i), BRepMesh_OnCurve);
1063             iv2 = myStructure->AddNode(v2);
1064
1065             Standard_Integer isv = myVemap.FindIndex(iv2);
1066             if (isv == 0) isv = myVemap.Add(iv2);
1067                   Nodes(i) = isv;
1068             PPar(i) = wCurFound;
1069
1070             if (orEdge==TopAbs_FORWARD)
1071               myStructure->AddLink(BRepMesh_Edge(ivf, iv2, BRepMesh_Frontier));
1072             else if (orEdge == TopAbs_REVERSED)
1073               myStructure->AddLink(BRepMesh_Edge(iv2, ivf, BRepMesh_Frontier));
1074             else if (orEdge == TopAbs_INTERNAL)
1075               myStructure->AddLink(BRepMesh_Edge(ivf, iv2, BRepMesh_Fixed));
1076
1077             ivf = iv2;
1078           }
1079         }
1080       }
1081
1082     P1 = new Poly_PolygonOnTriangulation(Nodes, PPar);
1083
1084     if (ivf != ivl) {
1085       if (orEdge == TopAbs_FORWARD)
1086         myStructure->AddLink(BRepMesh_Edge(ivf, ivl, BRepMesh_Frontier));
1087       else if (orEdge == TopAbs_REVERSED)
1088         myStructure->AddLink(BRepMesh_Edge(ivl, ivf, BRepMesh_Frontier));
1089       else if (orEdge == TopAbs_INTERNAL)
1090         myStructure->AddLink(BRepMesh_Edge(ivf, ivl, BRepMesh_Fixed));
1091       }
1092     }
1093   }
1094
1095   P1->Deflection(theDefEdge);
1096   if (myInternaledges.IsBound(theEdge))
1097   {
1098     BRepMesh_PairOfPolygon& pair = myInternaledges.ChangeFind(theEdge);
1099     if (orEdge == TopAbs_REVERSED)
1100       pair.Append(P1);
1101     else
1102       pair.Prepend(P1);
1103   }
1104   else
1105   {
1106     BRepMesh_PairOfPolygon pair1;
1107     pair1.Append(P1);
1108     myInternaledges.Bind(theEdge, pair1);
1109   }
1110 }
1111
1112
1113 //=======================================================================
1114 //function : Update(edge)
1115 //purpose  :
1116 //=======================================================================
1117 Standard_Boolean BRepMesh_FastDiscret::Update(const TopoDS_Edge&          theEdge,
1118                                               const TopoDS_Face&          theFace,
1119                                               const Handle(Geom2d_Curve)& theC2d,
1120                                               const Standard_Real         theDefEdge,
1121                                               const Standard_Real         theFirst,
1122                                               const Standard_Real         theLast)
1123 {
1124   TopLoc_Location Loc;
1125   Handle(Poly_Triangulation) T, TNull;
1126   Handle(Poly_PolygonOnTriangulation) Poly, NullPoly;
1127
1128   Standard_Integer i = 1;
1129   Standard_Boolean found = Standard_False;
1130   do
1131   {
1132     BRep_Tool::PolygonOnTriangulation(theEdge,Poly,T,Loc,i);
1133     i++;
1134     if (!found && !T.IsNull() && T->HasUVNodes() &&
1135         !Poly.IsNull() && Poly->HasParameters())
1136     {
1137       if (Poly->Deflection() <= 1.1*theDefEdge)
1138       {
1139         // 2d vertex indices
1140         TopAbs_Orientation orEdge = theEdge.Orientation();
1141         Standard_Integer iv1, iv2, ivl;
1142         Standard_Integer isv1, isv, isvl;
1143
1144         // Get range on 2d curve
1145         Standard_Real wFirst, wLast;
1146         BRep_Tool::Range(theEdge, theFace, wFirst, wLast);
1147
1148         // Get end points on 2d curve
1149         gp_Pnt2d uvFirst, uvLast;
1150         BRep_Tool::UVPoints(theEdge, theFace, uvFirst, uvLast);
1151
1152         // Get vertices
1153         TopoDS_Vertex pBegin, pEnd;
1154         TopExp::Vertices(theEdge,pBegin,pEnd);
1155
1156         const Standard_Boolean sameUV =
1157           uvFirst.IsEqual(uvLast, Precision::PConfusion());
1158
1159         //Controle vertice tolerances
1160         BRepAdaptor_Surface  BS(theFace, Standard_False);
1161         Handle(BRepAdaptor_HSurface) gFace = new BRepAdaptor_HSurface(BS);
1162
1163
1164         gp_Pnt pFirst = gFace->Value(uvFirst.X(), uvFirst.Y());
1165         gp_Pnt pLast  = gFace->Value(uvLast.X(), uvLast.Y());
1166
1167         Standard_Real mindist = 10. * Max(pFirst.Distance(BRep_Tool::Pnt(pBegin)),
1168                                           pLast.Distance(BRep_Tool::Pnt(pEnd)));
1169
1170         if (mindist < BRep_Tool::Tolerance(pBegin) ||
1171             mindist < BRep_Tool::Tolerance(pEnd) ) mindist = theDefEdge;
1172
1173         if (sameUV)
1174         {
1175           // 1. is it really sameUV without being degenerated
1176           gp_Pnt2d uvF, uvL;
1177           theC2d->D0(theFirst, uvF);
1178           theC2d->D0(theLast, uvL);
1179           if (!uvFirst.IsEqual(uvF, Precision::PConfusion())) {
1180             uvFirst = uvF;
1181           }
1182           if (!uvLast.IsEqual(uvL, Precision::PConfusion())) {
1183             uvLast = uvL;
1184           }
1185         }
1186
1187         const TColgp_Array1OfPnt&      Nodes   = T->Nodes();
1188         const TColStd_Array1OfInteger& Indices = Poly->Nodes();
1189         Handle(TColStd_HArray1OfReal)  Param   = Poly->Parameters();
1190
1191         const Standard_Integer nbnodes = Indices.Length();
1192         TColStd_Array1OfInteger NewNodes(1, nbnodes);
1193         TColStd_Array1OfInteger NewNodInStruct(1, nbnodes);
1194
1195         gp_Pnt P3d;
1196         gp_XY theUV;
1197
1198         // Process first vertex
1199         Standard_Integer ipf;
1200         if (myVertices.IsBound(pBegin))
1201         {
1202           ipf = myVertices.Find(pBegin);
1203         }
1204         else
1205         {
1206           if (sameUV && myVertices.IsBound(pEnd))
1207           {
1208               ipf = myVertices.Find(pEnd);
1209           }
1210           else
1211           {
1212             P3d = Nodes(Indices(1));
1213             if (!Loc.IsIdentity())
1214               P3d.Transform(Loc.Transformation());
1215             myNbLocat++;
1216             myLocation3d.Bind(myNbLocat,P3d);
1217             ipf = myNbLocat;
1218           }
1219           myVertices.Bind(pBegin,ipf);
1220         }
1221         NewNodInStruct(1) = ipf;
1222         theUV = BRepMesh_FastDiscretFace::FindUV(pBegin, uvFirst, ipf, gFace, mindist, myLocation2d);
1223         BRepMesh_Vertex vf(theUV,ipf,BRepMesh_Frontier);
1224         iv1 = myStructure->AddNode(vf);
1225         isv1 = myVemap.FindIndex(iv1);
1226         if (isv1 == 0) isv1 = myVemap.Add(iv1);
1227         NewNodes(1) = isv1;
1228
1229         // Process last vertex
1230         Standard_Integer ipl;
1231         if (pEnd.IsSame(pBegin))
1232         {
1233           ipl = ipf;
1234         }
1235         else
1236         {
1237           if (myVertices.IsBound(pEnd))
1238           {
1239             ipl = myVertices.Find(pEnd);
1240           }
1241           else
1242           {
1243             if (sameUV)
1244             {
1245               ipl = ipf;
1246               ivl = iv1;
1247               isv1 = isv1;
1248             }
1249             else
1250             {
1251               myNbLocat++;
1252               myLocation3d.Bind(myNbLocat,Nodes(Indices(nbnodes)).Transformed(Loc.Transformation()));
1253               ipl = myNbLocat;
1254             }
1255             myVertices.Bind(pEnd,ipl);
1256           }
1257         }
1258         NewNodInStruct(nbnodes) = ipl;
1259         theUV = BRepMesh_FastDiscretFace::FindUV(pEnd, uvLast, ipl, gFace, mindist, myLocation2d);
1260         BRepMesh_Vertex vl(theUV,ipl,BRepMesh_Frontier);
1261
1262         ivl = myStructure->AddNode(vl);
1263         isvl = myVemap.FindIndex(ivl);
1264         if (isvl == 0) isvl = myVemap.Add(ivl);
1265
1266         NewNodes(nbnodes) = isvl;
1267
1268         gp_Pnt2d uv;
1269         BRepMesh_Vertex v;
1270
1271         if (BRep_Tool::SameParameter(theEdge))
1272         {
1273           for (i = 2; i < Indices.Length(); i++)
1274           {
1275             // Record 3d point
1276             P3d = Nodes(Indices(i));
1277             if (!Loc.IsIdentity())
1278               P3d.Transform(Loc.Transformation());
1279             myNbLocat++;
1280             myLocation3d.Bind(myNbLocat, P3d);
1281             NewNodInStruct(i) = myNbLocat;
1282             // Record 2d point
1283             uv = theC2d->Value(Param->Value(i));
1284             v.Initialize(uv.Coord(), myNbLocat, BRepMesh_Frontier);
1285             iv2 = myStructure->AddNode(v);
1286             isv = myVemap.FindIndex(iv2);
1287             if (isv == 0) isv = myVemap.Add(iv2);
1288             NewNodes(i) = isv;
1289
1290             //add links
1291             if (orEdge == TopAbs_FORWARD)
1292               myStructure->AddLink(BRepMesh_Edge(iv1,iv2,BRepMesh_Frontier));
1293             else if (orEdge == TopAbs_REVERSED)
1294               myStructure->AddLink(BRepMesh_Edge(iv2,iv1,BRepMesh_Frontier));
1295             else if (orEdge == TopAbs_INTERNAL)
1296               myStructure->AddLink(BRepMesh_Edge(iv1,iv2,BRepMesh_Fixed));
1297             iv1 = iv2;
1298           }
1299
1300           // last point
1301           if (iv1 != ivl) {
1302             if (orEdge == TopAbs_FORWARD)
1303               myStructure->AddLink(BRepMesh_Edge(iv1,ivl,BRepMesh_Frontier));
1304             else if (orEdge == TopAbs_REVERSED)
1305               myStructure->AddLink(BRepMesh_Edge(ivl,iv1,BRepMesh_Frontier));
1306             else if (orEdge == TopAbs_INTERNAL)
1307               myStructure->AddLink(BRepMesh_Edge(iv1,ivl,BRepMesh_Fixed));
1308           }
1309
1310
1311         }
1312         else
1313         {
1314           const Standard_Real wFold = Param->Value(Param->Lower());
1315           const Standard_Real wLold = Param->Value(Param->Upper());
1316
1317           Standard_Real wKoef = 1.;
1318           if ((wFold != wFirst || wLold != wLast) && wLold != wFold)
1319           {
1320             wKoef = (wLast - wFirst) / (wLold - wFold);
1321           }
1322
1323           BRepAdaptor_Curve cons(theEdge, theFace);
1324           Extrema_LocateExtPC pcos;
1325           pcos.Initialize(cons, cons.FirstParameter(),
1326                           cons.LastParameter(), Precision::PConfusion());
1327
1328           Standard_Real wPrev;
1329           Standard_Real wCur      = wFirst;
1330           Standard_Real wCurFound = wFirst;
1331           for (i = 2; i < Indices.Length(); i++)
1332           {
1333             // Record 3d point
1334             P3d = Nodes(Indices(i));
1335             if (!Loc.IsIdentity())
1336               P3d.Transform(Loc.Transformation());
1337             myNbLocat++;
1338             myLocation3d.Bind(myNbLocat, P3d);
1339             NewNodInStruct(i) = myNbLocat;
1340             // Record 2d point
1341             wPrev = wCur;
1342             wCur  = wFirst + wKoef*(Param->Value(i) - wFold);
1343             wCurFound += (wCur - wPrev);
1344             pcos.Perform(P3d, wCurFound);
1345             if (pcos.IsDone()) wCurFound = pcos.Point().Parameter();
1346             theC2d->D0(wCurFound, uv);
1347             v.Initialize(uv.Coord(), myNbLocat, BRepMesh_Frontier);
1348             iv2 = myStructure->AddNode(v);
1349             isv = myVemap.FindIndex(iv2);
1350             if (isv == 0) isv = myVemap.Add(iv2);
1351             NewNodes(i) = isv;
1352
1353
1354             //add links
1355             if (orEdge == TopAbs_FORWARD)
1356               myStructure->AddLink(BRepMesh_Edge(iv1,iv2,BRepMesh_Frontier));
1357             else if (orEdge == TopAbs_REVERSED)
1358               myStructure->AddLink(BRepMesh_Edge(iv2,iv1,BRepMesh_Frontier));
1359             else if (orEdge == TopAbs_INTERNAL)
1360               myStructure->AddLink(BRepMesh_Edge(iv1,iv2,BRepMesh_Fixed));
1361             iv1 = iv2;
1362           }
1363
1364           // last point
1365           if (iv1 != ivl) {
1366             if (orEdge == TopAbs_FORWARD)
1367               myStructure->AddLink(BRepMesh_Edge(iv1,ivl,BRepMesh_Frontier));
1368             else if (orEdge == TopAbs_REVERSED)
1369               myStructure->AddLink(BRepMesh_Edge(ivl,iv1,BRepMesh_Frontier));
1370             else if (orEdge == TopAbs_INTERNAL)
1371               myStructure->AddLink(BRepMesh_Edge(iv1,ivl,BRepMesh_Fixed));
1372           }
1373         }
1374
1375         Handle(Poly_PolygonOnTriangulation) P1 =
1376           new Poly_PolygonOnTriangulation(NewNodes, Param->Array1());
1377         P1->Deflection(theDefEdge);
1378         if (myInternaledges.IsBound(theEdge))
1379         {
1380           BRepMesh_PairOfPolygon& pair = myInternaledges.ChangeFind(theEdge);
1381           if (theEdge.Orientation() == TopAbs_REVERSED)
1382             pair.Append(P1);
1383           else
1384             pair.Prepend(P1);
1385         }
1386         else
1387         {
1388           BRepMesh_PairOfPolygon pair1;
1389           pair1.Append(P1);
1390           myInternaledges.Bind(theEdge, pair1);
1391         }
1392
1393         Handle(Poly_PolygonOnTriangulation) P2 =
1394           new Poly_PolygonOnTriangulation(NewNodInStruct, Param->Array1());
1395         P2->Deflection(theDefEdge);
1396         BRepMesh_PairOfPolygon pair;
1397         pair.Append(P2);
1398         myEdges.Bind(theEdge, pair);
1399
1400         found = Standard_True;
1401       }
1402       else
1403       {
1404         BRep_Builder B;
1405         B.UpdateEdge(theEdge,NullPoly,T,Loc);
1406         B.UpdateFace(theFace,TNull);
1407       }
1408     }
1409     else if (!T.IsNull() && !T->HasUVNodes())
1410     {
1411       BRep_Builder B;
1412       B.UpdateEdge(theEdge,NullPoly,T,Loc);
1413       B.UpdateFace(theFace,TNull);
1414     }
1415   }
1416   while (!Poly.IsNull());
1417
1418   return found;
1419 }
1420
1421 //=======================================================================
1422 //function : output
1423 //purpose  :
1424 //=======================================================================
1425 Standard_Integer BRepMesh_FastDiscret::NbTriangles() const
1426 {
1427   return myStructure->NbElements();
1428 }
1429
1430 //=======================================================================
1431 //function : Triangle
1432 //purpose  :
1433 //=======================================================================
1434
1435 const BRepMesh_Triangle& BRepMesh_FastDiscret::Triangle
1436   (const Standard_Integer Index) const
1437 {
1438   return myStructure->GetElement(Index);
1439 }
1440
1441 //=======================================================================
1442 //function : NbEdges
1443 //purpose  :
1444 //=======================================================================
1445
1446 Standard_Integer BRepMesh_FastDiscret::NbEdges() const
1447 {
1448   return myStructure->NbLinks();
1449 }
1450
1451 //=======================================================================
1452 //function : Edge
1453 //purpose  :
1454 //=======================================================================
1455
1456 const BRepMesh_Edge& BRepMesh_FastDiscret::Edge(const Standard_Integer Index) const
1457 {
1458   return myStructure->GetLink(Index);
1459 }
1460
1461 //=======================================================================
1462 //function : NbVertices
1463 //purpose  :
1464 //=======================================================================
1465
1466 Standard_Integer BRepMesh_FastDiscret::NbVertices() const
1467 {
1468   return myStructure->NbNodes();
1469 }
1470
1471 //=======================================================================
1472 //function : Vertex
1473 //purpose  :
1474 //=======================================================================
1475
1476 const BRepMesh_Vertex& BRepMesh_FastDiscret::Vertex
1477   (const Standard_Integer Index) const
1478 {
1479   return myStructure->GetNode(Index);
1480 }
1481
1482 //=======================================================================
1483 //function : Pnt
1484 //purpose  :
1485 //=======================================================================
1486
1487 const gp_Pnt& BRepMesh_FastDiscret::Pnt(const Standard_Integer Index) const
1488 {
1489   return myLocation3d(myStructure->GetNode(Index).Location3d());
1490 }
1491
1492 //=======================================================================
1493 //function : VerticesOfDomain
1494 //purpose  :
1495 //=======================================================================
1496
1497 void BRepMesh_FastDiscret::VerticesOfDomain(BRepMesh_MapOfInteger&  Indices) const
1498 {
1499   Indices.Clear();
1500
1501   // recuperate from the map of edges.
1502   const BRepMesh_MapOfInteger& edmap = myStructure->LinkOfDomain();
1503
1504   // iterator on edges.
1505   BRepMesh_MapOfInteger::Iterator iter(edmap);
1506
1507   Standard_Integer ind_edge;
1508   for (iter.Reset(); iter.More(); iter.Next()) {
1509     ind_edge = iter.Key();
1510     const BRepMesh_Edge& Ed = Edge(ind_edge);
1511     Indices.Add(Ed.FirstNode());
1512     Indices.Add(Ed.LastNode());
1513   }
1514 }
1515
1516 BRepMesh_Status BRepMesh_FastDiscret::CurrentFaceStatus() const
1517 {
1518   return myFacestate;
1519 }
1520
1521 //=======================================================================
1522 //function : GetFaceAttribute
1523 //purpose  :
1524 //=======================================================================
1525
1526 Standard_Boolean BRepMesh_FastDiscret::GetFaceAttribute(const TopoDS_Face&              theFace,
1527                                                         Handle(BRepMesh_FaceAttribute)& theFattrib) const
1528 {
1529   if(myMapattrib.IsBound(theFace))
1530   {
1531     theFattrib = myMapattrib(theFace);
1532     return Standard_True;
1533   }
1534   return Standard_False;
1535 }
1536
1537 //=======================================================================
1538 //function : RemoveFaceAttribute
1539 //purpose  :
1540 //=======================================================================
1541
1542 void BRepMesh_FastDiscret::RemoveFaceAttribute(const TopoDS_Face& theFace)
1543 {
1544   if(myMapattrib.IsBound(theFace))
1545     myMapattrib.UnBind(theFace);
1546 }