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