b70f724ee8d5dd45194543388130e843d80e0407
[occt.git] / src / BRepMesh / BRepMesh_FastDiscret.cxx
1 // Created on: 1996-02-27
2 // Created by: Ekaterina SMIRNOVA
3 // Copyright (c) 1996-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 #include <BRepMesh_FastDiscret.hxx>
18
19 #include <BRepMesh_WireChecker.hxx>
20 #include <BRepMesh_FastDiscretFace.hxx>
21 #include <BRepMesh_FaceAttribute.hxx>
22 #include <BRepMesh_DataStructureOfDelaun.hxx>
23 #include <BRepMesh_GeomTool.hxx>
24 #include <BRepMesh_PairOfPolygon.hxx>
25 #include <BRepMesh_Classifier.hxx>
26 #include <BRepMesh_EdgeParameterProvider.hxx>
27 #include <BRepMesh_IEdgeTool.hxx>
28 #include <BRepMesh_EdgeTessellator.hxx>
29 #include <BRepMesh_EdgeTessellationExtractor.hxx>
30
31 #include <BRepAdaptor_Curve.hxx>
32 #include <BRepAdaptor_Surface.hxx>
33 #include <BRepAdaptor_HSurface.hxx>
34
35 #include <Bnd_Box.hxx>
36 #include <BRepTools.hxx>
37 #include <BRepBndLib.hxx>
38 #include <BndLib_Add3dCurve.hxx>
39 #include <Poly_Triangulation.hxx>
40 #include <Poly_PolygonOnTriangulation.hxx>
41
42 #include <Precision.hxx>
43 #include <Geom2d_Curve.hxx>
44 #include <Geom_Surface.hxx>
45 #include <Geom_Plane.hxx>
46 #include <GeomAbs_SurfaceType.hxx>
47 #include <Extrema_LocateExtPC.hxx>
48
49 #include <TColStd_Array1OfInteger.hxx>
50 #include <TColStd_HArray1OfReal.hxx>
51 #include <TColgp_Array1OfPnt2d.hxx>
52 #include <TColGeom2d_SequenceOfCurve.hxx>
53 #include <SortTools_ShellSortOfReal.hxx>
54 #include <TCollection_CompareOfReal.hxx>
55
56 #include <TopTools_SequenceOfShape.hxx>
57 #include <TopTools_ListIteratorOfListOfShape.hxx>
58
59 #include <TopAbs.hxx>
60 #include <TopoDS.hxx>
61 #include <TopoDS_Vertex.hxx>
62 #include <TopExp.hxx>
63 #include <TopExp_Explorer.hxx>
64
65 #include <Standard_ErrorHandler.hxx>
66 #include <Standard_Failure.hxx>
67 #include <NCollection_IncAllocator.hxx>
68
69 #include <BRep_ListIteratorOfListOfPointRepresentation.hxx>
70 #include <BRep_PointRepresentation.hxx>
71
72 #include <vector>
73
74 #ifdef HAVE_TBB
75   // paralleling using Intel TBB
76   #include <tbb/parallel_for_each.h>
77 #endif
78
79 #define UVDEFLECTION 1.e-05
80
81 IMPLEMENT_STANDARD_HANDLE (BRepMesh_FastDiscret, Standard_Transient)
82 IMPLEMENT_STANDARD_RTTIEXT(BRepMesh_FastDiscret, Standard_Transient)
83
84 //=======================================================================
85 //function : BRepMesh_FastDiscret
86 //purpose  : 
87 //=======================================================================
88 BRepMesh_FastDiscret::BRepMesh_FastDiscret(
89   const Standard_Real                              theDefle,
90   const Standard_Real                              theAngl,
91   const Bnd_Box&                                   theBox,
92   const Standard_Boolean                           theWithShare,
93   const Standard_Boolean                           theInshape,
94   const Standard_Boolean                           theRelative,
95   const Standard_Boolean                           theShapetrigu,
96   const Standard_Boolean                           isInParallel)
97 : myAngle (theAngl),
98   myDeflection (theDefle),
99   myWithShare (theWithShare),
100   myInParallel (isInParallel),
101   myRelative (theRelative),
102   myShapetrigu (theShapetrigu), 
103   myInshape (theInshape),
104   myBoundaryVertices(new BRepMesh::DMapOfVertexInteger),
105   myBoundaryPoints(new BRepMesh::DMapOfIntegerPnt)
106 {
107   if ( myRelative )
108     BRepMesh_ShapeTool::BoxMaxDimension(theBox, myDtotale);
109 }
110
111 //=======================================================================
112 //function : BRepMesh_FastDiscret
113 //purpose  : 
114 //=======================================================================
115 BRepMesh_FastDiscret::BRepMesh_FastDiscret(const TopoDS_Shape&    theShape,
116                                            const Standard_Real    theDefle,
117                                            const Standard_Real    theAngl,
118                                            const Bnd_Box&         theBox,
119                                            const Standard_Boolean theWithShare,
120                                            const Standard_Boolean theInshape,
121                                            const Standard_Boolean theRelative,
122                                            const Standard_Boolean theShapetrigu,
123                                            const Standard_Boolean isInParallel)
124 : myAngle (theAngl),
125   myDeflection (theDefle),
126   myWithShare (theWithShare),
127   myInParallel (isInParallel),
128   myRelative (theRelative),
129   myShapetrigu (theShapetrigu),
130   myInshape (theInshape),
131   myBoundaryVertices(new BRepMesh::DMapOfVertexInteger),
132   myBoundaryPoints(new BRepMesh::DMapOfIntegerPnt)
133 {
134   if ( myRelative )
135     BRepMesh_ShapeTool::BoxMaxDimension(theBox, myDtotale);
136
137   Perform(theShape);
138 }
139
140 //=======================================================================
141 //function : InitSharedFaces
142 //purpose  : 
143 //=======================================================================
144 void BRepMesh_FastDiscret::InitSharedFaces(const TopoDS_Shape& theShape)
145 {
146   TopExp::MapShapesAndAncestors(theShape, TopAbs_EDGE, TopAbs_FACE, mySharedFaces);
147 }
148
149 //=======================================================================
150 //function : Perform(shape)
151 //purpose  : 
152 //=======================================================================
153 void BRepMesh_FastDiscret::Perform(const TopoDS_Shape& theShape)
154 {
155   InitSharedFaces(theShape);
156
157   std::vector<TopoDS_Face> aFaces;
158   TopExp_Explorer anExplorer(theShape, TopAbs_FACE);
159   for (; anExplorer.More(); anExplorer.Next())
160   {
161     const TopoDS_Face& aFace = TopoDS::Face(anExplorer.Current());
162     Add(aFace);
163     aFaces.push_back(aFace);
164   }
165
166 #ifdef HAVE_TBB
167   if ( myInParallel )
168   {
169     tbb::parallel_for_each(aFaces.begin(), aFaces.end(), *this);
170   }
171   else
172   {
173 #endif
174     std::vector<TopoDS_Face>::const_iterator anIt(aFaces.begin());
175     for (; anIt != aFaces.end(); anIt++)
176       Process(*anIt);
177 #ifdef HAVE_TBB
178   }
179 #endif
180 }
181
182
183 //=======================================================================
184 //function : Process
185 //purpose  : 
186 //=======================================================================
187 void BRepMesh_FastDiscret::Process(const TopoDS_Face& theFace) const
188 {
189   Handle(BRepMesh_FaceAttribute) anAttribute;
190   if (GetFaceAttribute(theFace, anAttribute))
191   {
192     try
193     {
194       OCC_CATCH_SIGNALS
195
196       BRepMesh_FastDiscretFace aTool(GetAngle(), WithShare());
197       aTool.Add(anAttribute);
198     }
199     catch (Standard_Failure)
200     {
201       anAttribute->SetStatus(BRepMesh_Failure);
202     }
203   }
204 }
205
206 //=======================================================================
207 //function : Add(face)
208 //purpose  : 
209 //=======================================================================
210 Standard_Integer BRepMesh_FastDiscret::Add(const TopoDS_Face& theFace)
211 {
212   try
213   {
214     OCC_CATCH_SIGNALS
215
216     // Initialize face attributes
217     myAttribute.Nullify();
218     GetFaceAttribute(theFace, myAttribute);
219     if (myAttribute.IsNull())
220     {
221       myAttribute = new BRepMesh_FaceAttribute(theFace,
222         myBoundaryVertices, myBoundaryPoints);
223
224       myAttributes.Bind(theFace, myAttribute);
225     }
226
227     myStructure     = myAttribute->ResetStructure();
228     myVertexEdgeMap = myAttribute->ChangeVertexEdgeMap();
229     myInternalEdges = myAttribute->ChangeInternalEdges();
230
231     if (!myWithShare)
232     {
233       myEdges.Clear();
234       myBoundaryVertices->Clear();
235       myBoundaryPoints->Clear();
236     }
237
238     Standard_Real defedge;
239     Standard_Integer nbEdge = 0;
240     Standard_Real savangle = myAngle;
241     Standard_Real cdef;
242     Standard_Real maxdef = 2.* BRepMesh_ShapeTool::MaxFaceTolerance(theFace);
243
244     Standard_Real defface = 0.;
245     if (!myRelative)
246       defface = Max(myDeflection, maxdef);
247
248     NCollection_Sequence<EdgePCurve>  aPCurves;
249     NCollection_Sequence<TopoDS_Edge> aFaceEdges;
250
251     const TopoDS_Face&                  aFace = myAttribute->Face();
252     const Handle(BRepAdaptor_HSurface)& gFace = myAttribute->Surface();
253     TopExp_Explorer aWireIt(aFace, TopAbs_WIRE);
254     for (; aWireIt.More(); aWireIt.Next())
255     {
256       TopExp_Explorer aEdgeIt(aWireIt.Current(), TopAbs_EDGE);
257       for (; aEdgeIt.More(); aEdgeIt.Next(), ++nbEdge)
258       {
259         const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
260         if (!myMapdefle.IsBound(aEdge))
261         {
262           if (myRelative)
263           {
264             if (myEdges.IsBound(aEdge))
265             {
266               const BRepMesh_PairOfPolygon& aPair = myEdges.Find(aEdge);
267               const Handle(Poly_PolygonOnTriangulation)& aPolygon = aPair.First();
268               defedge = aPolygon->Deflection();
269             }
270             else
271             {
272               defedge = BRepMesh_ShapeTool::RelativeEdgeDeflection(
273                 aEdge, myDeflection, myDtotale, cdef);
274
275               myAngle = savangle * cdef;
276             }
277
278             defface += defedge;
279             defface = Max(maxdef, defface);
280           }
281           else
282           {
283             defedge = myDeflection;
284           }
285
286           defedge = Max(maxdef, defedge);
287           defedge = Max(UVDEFLECTION, defedge);
288           myMapdefle.Bind(aEdge, defedge);
289         }
290         else
291         {
292           defedge = myMapdefle(aEdge);
293           if ( myRelative )
294           {
295             defface += defedge;
296             defface = Max(maxdef, defface);
297           }
298         }
299
300         Standard_Real aFirstParam, aLastParam;
301         Handle(Geom2d_Curve) aCurve2d = 
302           BRep_Tool::CurveOnSurface(aEdge, aFace, aFirstParam, aLastParam);
303
304         if (aCurve2d.IsNull())
305           continue;
306
307         EdgePCurve aPCurve = { aCurve2d, aFirstParam, aLastParam };
308         aPCurves.Append(aPCurve);
309         aFaceEdges.Append(aEdge);
310
311         add(aEdge, aPCurve, defedge);
312         myAngle = savangle;
313       }
314     }
315
316     if ( nbEdge == 0 || myVertexEdgeMap->Extent() < 3 )
317     {
318       myAttribute->SetStatus(BRepMesh_Failure);
319       return myAttribute->GetStatus();
320     }
321
322     if ( myRelative )
323     {
324       defface = defface / nbEdge;
325     }
326     else
327     {
328       defface = myDeflection;
329     }
330
331     if ( myWithShare )
332       defface = Max(maxdef, defface);
333
334     TopLoc_Location aLoc;
335     Handle(Poly_Triangulation) aTriangulation = BRep_Tool::Triangulation(aFace, aLoc);
336
337     if (!myShapetrigu || aTriangulation.IsNull())
338     {
339       Standard_Real xCur, yCur;
340       Standard_Real maxX, minX, maxY, minY;
341
342       minX = minY = 1.e100;
343       maxX = maxY =-1.e100;
344
345       Standard_Integer ipn = 0;
346       Standard_Integer i1 = 1;
347       for ( i1 = 1; i1 <= myVertexEdgeMap->Extent(); ++i1 )
348       {
349         const BRepMesh_Vertex& aVertex = myStructure->GetNode(myVertexEdgeMap->FindKey(i1));
350
351         ++ipn;
352
353         xCur = aVertex.Coord().X();
354         yCur = aVertex.Coord().Y();
355
356         minX = Min(xCur, minX);
357         maxX = Max(xCur, maxX);
358         minY = Min(yCur, minY);
359         maxY = Max(yCur, maxY);
360       }
361
362       Standard_Real myumin = minX;
363       Standard_Real myumax = maxX;
364       Standard_Real myvmin = minY;
365       Standard_Real myvmax = maxY;
366
367       const Standard_Real umin = gFace->FirstUParameter();
368       const Standard_Real umax = gFace->LastUParameter();
369       const Standard_Real vmin = gFace->FirstVParameter();
370       const Standard_Real vmax = gFace->LastVParameter();
371
372       if (myumin < umin || myumax > umax)
373       {
374         if (gFace->IsUPeriodic())
375         {
376           if ((myumax - myumin) > (umax - umin))
377             myumax = myumin + (umax - umin);
378         }
379         else
380         {
381           if (umin > myumin)
382             myumin = umin;
383
384           if (umax < myumax)
385             myumax = umax;
386         }
387       }
388
389       if (myvmin < vmin || myvmax > vmax)
390       {
391         if (gFace->IsVPeriodic())
392         {
393           if ((myvmax - myvmin) > (vmax - vmin))
394             myvmax = myvmin + (vmax - vmin);
395         }
396         else
397         {
398           if ( vmin > myvmin )
399             myvmin = vmin;
400
401           if (vmax < myvmax)
402             myvmax = vmax;
403         }
404       }
405
406       GeomAbs_SurfaceType aSurfType = gFace->GetType();
407       // Fast verification of the validity of calculated limits.
408       // If wrong, sure a problem of pcurve.
409       if (aSurfType == GeomAbs_BezierSurface &&
410          (myumin < -0.5 || myumax > 1.5 || myvmin < -0.5 || myvmax > 1.5) )
411       {
412         myAttribute->SetStatus(BRepMesh_Failure);
413         return myAttribute->GetStatus();
414       }
415
416       //define parameters for correct parametrics
417       Standard_Real deltaX = 1.0;
418       Standard_Real deltaY = 1.0;
419
420       {
421         BRepMesh::HClassifier& aClassifier = myAttribute->ChangeClassifier();
422         BRepMesh_WireChecker aDFaceChecker(aFace, Precision::PConfusion(),
423           myInternalEdges, myVertexEdgeMap, myStructure,
424           myumin, myumax, myvmin, myvmax, myInParallel );
425
426         aDFaceChecker.ReCompute(aClassifier);
427         BRepMesh_Status aCheckStatus = aDFaceChecker.Status();
428
429         if (aCheckStatus == BRepMesh_SelfIntersectingWire)
430         {
431           Standard_Integer nbmaill = 0;
432           Standard_Real eps = Precision::Confusion();
433           while (nbmaill < 5 && aCheckStatus != BRepMesh_ReMesh)
434           {
435             ++nbmaill;
436
437             // Clear the structure of links
438             myStructure = myAttribute->ResetStructure();
439
440             
441             for (Standard_Integer j = 1; j <= aFaceEdges.Length(); ++j)
442             {
443               const TopoDS_Edge& anEdge = aFaceEdges(j);
444               if (myEdges.IsBound(anEdge))
445                 myEdges.UnBind(anEdge);
446
447               defedge = Max(myMapdefle(anEdge) / 3.0, eps);
448               myMapdefle.Bind(anEdge, defedge);
449
450               add(anEdge, aPCurves(j), defedge);
451             }
452
453             aDFaceChecker.ReCompute(aClassifier);
454             if (aDFaceChecker.Status() == BRepMesh_NoError)
455               aCheckStatus = BRepMesh_ReMesh;
456           }
457         }
458
459         myAttribute->SetStatus(aCheckStatus);
460         if (!myAttribute->IsValid())
461           //RemoveFaceAttribute(theFace);
462           return myAttribute->GetStatus();
463       }
464
465       // try to find the real length:
466       // akm (bug OCC16) : We must calculate these measures in non-singular
467       //     parts of face. Let's try to compute average value of three
468       //     (umin, (umin+umax)/2, umax), and respectively for v.
469       //                 vvvvv
470       Standard_Real longu = 0.0, longv = 0.0; //, last , first;
471       gp_Pnt P11, P12, P21, P22, P31, P32;
472
473       Standard_Real du = 0.05 * ( myumax - myumin );
474       Standard_Real dv = 0.05 * ( myvmax - myvmin );
475       Standard_Real dfuave = 0.5 * ( myumin + myumax );
476       Standard_Real dfvave = 0.5 * ( myvmin + myvmax );
477       Standard_Real dfucur, dfvcur;
478
479       // U loop
480       gFace->D0(myumin, myvmin, P11);
481       gFace->D0(myumin, dfvave, P21);
482       gFace->D0(myumin, myvmax, P31);
483       for (i1=1, dfucur=myumin+du; i1 <= 20; i1++, dfucur+=du)
484       {
485         gFace->D0(dfucur, myvmin, P12);
486         gFace->D0(dfucur, dfvave, P22);
487         gFace->D0(dfucur, myvmax, P32);
488         longu += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
489         P11 = P12;
490         P21 = P22;
491         P31 = P32;
492       }
493
494       // V loop
495       gFace->D0(myumin, myvmin, P11);
496       gFace->D0(dfuave, myvmin, P21);
497       gFace->D0(myumax, myvmin, P31);
498       for (i1=1, dfvcur=myvmin+dv; i1 <= 20; i1++, dfvcur+=dv)
499       {
500         gFace->D0(myumin, dfvcur, P12);
501         gFace->D0(dfuave, dfvcur, P22);
502         gFace->D0(myumax, dfvcur, P32);
503         longv += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
504         P11 = P12;
505         P21 = P22;
506         P31 = P32;
507       }
508
509       longu /= 3.;
510       longv /= 3.;
511       // akm (bug OCC16) ^^^^^
512
513       if (longu <= 1.e-16 || longv <= 1.e-16)
514       {
515         //yes, it is seen!!
516         myAttribute->SetStatus(BRepMesh_Failure);
517         return myAttribute->GetStatus();
518       }
519
520
521       if (aSurfType == GeomAbs_Torus)
522       {
523         gp_Torus Tor = gFace->Torus();
524         Standard_Real r = Tor.MinorRadius(), R = Tor.MajorRadius();
525         Standard_Real Du, Dv;//, pasu, pasv;
526
527         Dv = Max(1.0e0 - (defface/r),0.0e0) ;
528         Standard_Real oldDv = 2.0 * ACos (Dv);
529         oldDv = Min(oldDv, myAngle);
530         Dv  =  0.9*oldDv; //TWOTHIRD * oldDv;
531         Dv = oldDv;
532
533         Standard_Integer nbV = Max((Standard_Integer)((myvmax-myvmin)/Dv), 2);
534         Dv = (myvmax-myvmin)/(nbV+1);
535
536         Standard_Real ru = R + r;
537         if ( ru > 1.e-16 )
538         {
539           Du = Max(1.0e0 - (defface/ru),0.0e0);
540           Du  = (2.0 * ACos (Du));
541           Du = Min(Du, myAngle);
542           Standard_Real aa = sqrt(Du*Du + oldDv*oldDv);
543
544           if (aa < gp::Resolution())
545             return myAttribute->GetStatus();
546
547           Du = Du * Min(oldDv, Du) / aa;
548         }
549         else
550         {
551           Du = Dv;
552         }
553
554         Standard_Integer nbU = Max((Standard_Integer)((myumax-myumin)/Du), 2);
555         nbU = Max(nbU, (Standard_Integer)(nbV*(myumax-myumin)*R/((myvmax-myvmin)*r)/5.));
556       
557         Du = (myumax-myumin)/(nbU+1);
558         //-- DeltaX and DeltaY are chosen so that to avoid "jumping" 
559         //-- of points on the grid
560         deltaX = Du;
561         deltaY = Dv;
562       }
563       else if (aSurfType == GeomAbs_Cylinder)
564       {
565         gp_Cylinder Cyl = gFace->Cylinder();
566         Standard_Real R = Cyl.Radius();
567
568         // Calculate parameters for iteration in U direction
569         Standard_Real Du = 1.0 - (defface/R);
570         if (Du < 0.0)
571           Du = 0.0;
572
573         Du = 2.0 * ACos (Du);
574         if (Du > GetAngle())
575           Du = GetAngle();
576
577         deltaX = Du / longv;
578         deltaY = 1.;
579       }
580       else
581       {
582         deltaX = (myumax-myumin)/longu;
583         deltaY = (myvmax-myvmin)/longv;
584       }
585
586       // Restore face attribute
587       myAttribute->SetDefFace(defface);
588       myAttribute->SetUMax(myumax);
589       myAttribute->SetVMax(myvmax);
590       myAttribute->SetUMin(myumin);
591       myAttribute->SetVMin(myvmin);
592       myAttribute->SetDeltaX(deltaX);
593       myAttribute->SetDeltaY(deltaY);
594     }
595   }
596   catch(Standard_Failure)
597   {
598     myAttribute->SetStatus(BRepMesh_Failure);
599   }
600
601   return myAttribute->GetStatus();
602 }
603
604 //=======================================================================
605 //function : addLinkToMesh
606 //purpose  :
607 //=======================================================================
608 void BRepMesh_FastDiscret::addLinkToMesh(
609   const Standard_Integer   theFirstNodeId,
610   const Standard_Integer   theLastNodeId,
611   const TopAbs_Orientation theOrientation)
612 {
613   if (theOrientation == TopAbs_FORWARD)
614     myStructure->AddLink(BRepMesh_Edge(theFirstNodeId, theLastNodeId, BRepMesh_Frontier));
615   else if (theOrientation == TopAbs_REVERSED)
616     myStructure->AddLink(BRepMesh_Edge(theLastNodeId, theFirstNodeId, BRepMesh_Frontier));
617   else if (theOrientation == TopAbs_INTERNAL)
618     myStructure->AddLink(BRepMesh_Edge(theFirstNodeId, theLastNodeId, BRepMesh_Fixed));
619 }
620
621 //=======================================================================
622 //function : getEdgeAttributes
623 //purpose  :
624 //=======================================================================
625 Standard_Boolean BRepMesh_FastDiscret::getEdgeAttributes(
626   const TopoDS_Edge&                      theEdge,
627   const BRepMesh_FastDiscret::EdgePCurve& thePCurve,
628   const Standard_Real                     theDefEdge,
629   BRepMesh_FastDiscret::EdgeAttributes&   theAttributes) const
630 {
631   EdgeAttributes& aEAttr = theAttributes;
632
633   // Get vertices
634   TopExp::Vertices(theEdge, aEAttr.FirstVertex, aEAttr.LastVertex);
635   if (aEAttr.FirstVertex.IsNull() || aEAttr.LastVertex.IsNull())
636     return Standard_False;
637
638   // Get range on 2d curve
639   const TopoDS_Face& aFace = myAttribute->Face();
640   BRep_Tool::Range(theEdge, aFace, aEAttr.FirstParam, aEAttr.LastParam);
641
642   // Get end points on 2d curve
643   BRep_Tool::UVPoints(theEdge, aFace, aEAttr.FirstUV, aEAttr.LastUV);
644
645   aEAttr.IsSameUV =
646     aEAttr.FirstUV.IsEqual(aEAttr.LastUV, Precision::PConfusion());
647
648   //Control tolerance of vertices
649   const Handle(BRepAdaptor_HSurface)& gFace = myAttribute->Surface();
650   gp_Pnt pFirst = gFace->Value(aEAttr.FirstUV.X(), aEAttr.FirstUV.Y());
651   gp_Pnt pLast  = gFace->Value(aEAttr.LastUV.X(),  aEAttr.LastUV.Y());
652
653   aEAttr.MinDist = 10. * Max(pFirst.Distance(BRep_Tool::Pnt(aEAttr.FirstVertex)),
654                              pLast .Distance(BRep_Tool::Pnt(aEAttr.LastVertex)));
655
656   if (aEAttr.MinDist < BRep_Tool::Tolerance(aEAttr.FirstVertex) ||
657       aEAttr.MinDist < BRep_Tool::Tolerance(aEAttr.LastVertex))
658   {
659     aEAttr.MinDist = theDefEdge;
660   }
661
662   if (aEAttr.IsSameUV)
663   {
664     // 1. is it really sameUV without being degenerated
665     gp_Pnt2d uvF, uvL;
666     thePCurve.Curve2d->D0(thePCurve.FirstParam, uvF);
667     thePCurve.Curve2d->D0(thePCurve.LastParam,  uvL);
668
669     if (!aEAttr.FirstUV.IsEqual(uvF, Precision::PConfusion()))
670       aEAttr.FirstUV = uvF;
671
672     if (!aEAttr.LastUV.IsEqual(uvL, Precision::PConfusion()))
673       aEAttr.LastUV = uvL;
674   }
675
676   return Standard_True;
677 }
678
679 //=======================================================================
680 //function : registerEdgeVertices
681 //purpose  : 
682 //=======================================================================
683 void BRepMesh_FastDiscret::registerEdgeVertices(
684   BRepMesh_FastDiscret::EdgeAttributes& theAttributes,
685   Standard_Integer&                     ipf,
686   Standard_Integer&                     ivf,
687   Standard_Integer&                     isvf,
688   Standard_Integer&                     ipl,
689   Standard_Integer&                     ivl,
690   Standard_Integer&                     isvl)
691 {
692   EdgeAttributes& aEAttr = theAttributes;
693   if (aEAttr.FirstVExtractor.IsNull())
694   {
695     // Use edge geometry to produce tesselation.
696     aEAttr.FirstVExtractor = 
697       new TopoDSVExplorer(aEAttr.FirstVertex, aEAttr.IsSameUV, aEAttr.LastVertex);
698   }
699
700   if (aEAttr.LastVExtractor.IsNull())
701   {
702     // Use edge geometry to produce tesselation.
703     aEAttr.LastVExtractor = 
704       new TopoDSVExplorer(aEAttr.LastVertex, aEAttr.IsSameUV, aEAttr.FirstVertex);
705   }
706
707   gp_XY aTmpUV;
708   // Process first vertex
709   ipf = myAttribute->GetVertexIndex(aEAttr.FirstVExtractor, Standard_True);
710   aTmpUV = BRepMesh_ShapeTool::FindUV(ipf, aEAttr.FirstUV, aEAttr.FirstVertex, 
711     aEAttr.MinDist, myAttribute);
712
713   myAttribute->AddNode(ipf, aTmpUV, BRepMesh_Frontier, ivf, isvf);
714
715   // Process last vertex
716   ipl = aEAttr.LastVertex.IsSame(aEAttr.FirstVertex) ? ipf :
717     myAttribute->GetVertexIndex(aEAttr.LastVExtractor, Standard_True);
718   aTmpUV = BRepMesh_ShapeTool::FindUV(ipl, aEAttr.LastUV, aEAttr.LastVertex, 
719     aEAttr.MinDist, myAttribute);
720
721   myAttribute->AddNode(ipl, aTmpUV, BRepMesh_Frontier, ivl, isvl);
722 }
723
724 //=======================================================================
725 //function : add
726 //purpose  : 
727 //=======================================================================
728 void BRepMesh_FastDiscret::add(
729   const TopoDS_Edge&                      theEdge,
730   const BRepMesh_FastDiscret::EdgePCurve& thePCurve,
731   const Standard_Real                     theDefEdge)
732 {
733   const TopAbs_Orientation orEdge = theEdge.Orientation();
734   if (orEdge == TopAbs_EXTERNAL)
735     return;
736
737   EdgeAttributes aEAttr;
738   if (!getEdgeAttributes(theEdge, thePCurve, theDefEdge, aEAttr))
739     return;
740
741   if (!myEdges.IsBound(theEdge))
742   {
743     update(theEdge, thePCurve.Curve2d, theDefEdge, aEAttr);
744     return;
745   }
746
747   Standard_Integer ipf, ivf, isvf, ipl, ivl, isvl;
748   registerEdgeVertices(aEAttr, ipf, ivf, isvf, ipl, ivl, isvl);
749
750   // If this Edge has been already checked and it is not degenerated, 
751   // the points of the polygon calculated at the first check are retrieved :
752
753   // retrieve the polygone:
754   const BRepMesh_PairOfPolygon&              aPair    = myEdges.Find(theEdge);
755   const Handle(Poly_PolygonOnTriangulation)& aPolygon = aPair.First();
756   const TColStd_Array1OfInteger&             aNodes   = aPolygon->Nodes();
757   Handle(TColStd_HArray1OfReal)              aParams  = aPolygon->Parameters();
758
759   // creation anew:
760   const Standard_Integer  aNodesNb = aNodes.Length();
761   TColStd_Array1OfInteger aNewNodes (1, aNodesNb);
762   TColStd_Array1OfReal    aNewParams(1, aNodesNb);
763
764   aNewNodes (1) = isvf;
765   aNewParams(1) = aEAttr.FirstParam;
766
767   aNewNodes (aNodesNb) = isvl;
768   aNewParams(aNodesNb) = aEAttr.LastParam;
769
770   const TopoDS_Face& aFace = myAttribute->Face();
771   if (!BRepMesh_ShapeTool::IsDegenerated(theEdge, aFace))
772   {
773     BRepMesh_EdgeParameterProvider aProvider(theEdge, aFace, aParams);
774     for (Standard_Integer i = 2; i < aNodesNb; ++i)
775     {
776       const Standard_Integer aPointId = aNodes(i);
777       const gp_Pnt& aPnt = myBoundaryPoints->Find(aPointId);
778
779       const Standard_Real aParam = aProvider.Parameter(i, aPnt);
780       gp_Pnt2d aUV = thePCurve.Curve2d->Value(aParam);
781
782       Standard_Integer iv2, isv;
783       myAttribute->AddNode(aPointId, aUV.Coord(), BRepMesh_OnCurve, iv2, isv);
784
785       aNewNodes (i) = isv;
786       aNewParams(i) = aParam;
787
788       addLinkToMesh(ivf, iv2, orEdge);
789       ivf = iv2;
790     }
791
792     // last point
793     if (ivf != ivl)
794       addLinkToMesh(ivf, ivl, orEdge);
795   }
796
797   Handle(Poly_PolygonOnTriangulation) P1 = 
798     new Poly_PolygonOnTriangulation(aNewNodes, aNewParams);
799
800   storePolygon(theEdge, P1, theDefEdge);
801 }
802
803 //=======================================================================
804 //function : update(edge)
805 //purpose  :
806 //=======================================================================
807 void BRepMesh_FastDiscret::update(
808   const TopoDS_Edge&                                theEdge,
809   const Handle(Geom2d_Curve)&                       theC2d,
810   const Standard_Real                               theDefEdge,
811   BRepMesh_FastDiscret::EdgeAttributes&             theAttributes)
812 {
813   EdgeAttributes& aEAttr = theAttributes;
814
815   const TopoDS_Face& aFace = myAttribute->Face();
816   Handle(BRepMesh_IEdgeTool) aEdgeTool;
817   // Try to find existing tessellation.
818   for (Standard_Integer i = 1; aEdgeTool.IsNull(); ++i)
819   {
820     TopLoc_Location aLoc;
821     Handle(Poly_Triangulation) aTriangulation;
822     Handle(Poly_PolygonOnTriangulation) aPolygon;
823     BRep_Tool::PolygonOnTriangulation(theEdge, aPolygon, aTriangulation, aLoc, i);
824
825     if (aPolygon.IsNull())
826       break;
827
828     if (aTriangulation.IsNull() || !aPolygon->HasParameters())
829       continue;
830
831     if (aPolygon->Deflection() > 1.1 * theDefEdge)
832       continue;
833
834     const TColgp_Array1OfPnt&      aNodes   = aTriangulation->Nodes();
835     const TColStd_Array1OfInteger& aIndices = aPolygon->Nodes();
836     Handle(TColStd_HArray1OfReal)  aParams  = aPolygon->Parameters();
837
838     aEAttr.FirstVExtractor = new PolyVExplorer(aEAttr.FirstVertex, 
839       aEAttr.IsSameUV, aEAttr.LastVertex, aIndices(1), aNodes, aLoc);
840
841     aEAttr.LastVExtractor = new PolyVExplorer(aEAttr.LastVertex, 
842       aEAttr.IsSameUV, aEAttr.FirstVertex, aIndices(aIndices.Length()), aNodes, aLoc);
843
844     aEdgeTool = new BRepMesh_EdgeTessellationExtractor(theEdge, theC2d, 
845       aFace, aTriangulation, aPolygon, aLoc);
846   }
847
848   if (aEdgeTool.IsNull())
849   {
850     aEdgeTool = new BRepMesh_EdgeTessellator(theEdge, myAttribute, 
851       mySharedFaces, theDefEdge, myAngle);
852   }
853
854   Standard_Integer ipf, ivf, isvf, ipl, ivl, isvl;
855   registerEdgeVertices(aEAttr, ipf, ivf, isvf, ipl, ivl, isvl);
856
857   TopAbs_Orientation orEdge = theEdge.Orientation();
858   Handle(Poly_PolygonOnTriangulation) P1, P2;
859   if (BRepMesh_ShapeTool::IsDegenerated(theEdge, aFace))
860   {
861     const Standard_Integer  aNodesNb = 2;
862     TColStd_Array1OfInteger aNewNodes      (1, aNodesNb);
863     TColStd_Array1OfInteger aNewNodInStruct(1, aNodesNb);
864     TColStd_Array1OfReal    aNewParams     (1, aNodesNb);
865
866     aNewNodInStruct(1) = ipf;
867     aNewNodes      (1) = isvf;
868     aNewParams     (1) = aEAttr.FirstParam;
869
870     aNewNodInStruct(aNodesNb) = ipl;
871     aNewNodes      (aNodesNb) = isvl;
872     aNewParams     (aNodesNb) = aEAttr.LastParam;
873
874     P1 = new Poly_PolygonOnTriangulation(aNewNodes,       aNewParams);
875     P2 = new Poly_PolygonOnTriangulation(aNewNodInStruct, aNewParams);
876   }
877   else
878   {
879     const Standard_Integer  aNodesNb = aEdgeTool->NbPoints();
880     TColStd_Array1OfInteger aNewNodes      (1, aNodesNb);
881     TColStd_Array1OfInteger aNewNodInStruct(1, aNodesNb);
882     TColStd_Array1OfReal    aNewParams     (1, aNodesNb);
883
884     aNewNodInStruct(1) = ipf;
885     aNewNodes      (1) = isvf;
886     aNewParams     (1) = aEAttr.FirstParam;
887
888     aNewNodInStruct(aNodesNb) = ipl;
889     aNewNodes      (aNodesNb) = isvl;
890     aNewParams     (aNodesNb) = aEAttr.LastParam;
891
892     Standard_Integer aLastPointId = myAttribute->LastPointId();
893     for (Standard_Integer i = 2; i < aNodesNb; ++i)
894     {
895       gp_Pnt        aPnt;
896       gp_Pnt2d      aUV;
897       Standard_Real aParam;
898       aEdgeTool->Value(i, aParam, aPnt, aUV);
899       myBoundaryPoints->Bind(++aLastPointId, aPnt);
900
901       Standard_Integer iv2, isv;
902       myAttribute->AddNode(aLastPointId, aUV.Coord(), BRepMesh_Frontier, iv2, isv);
903
904       aNewNodInStruct(i) = aLastPointId;
905       aNewNodes      (i) = isv;
906       aNewParams     (i) = aParam;
907
908       addLinkToMesh(ivf, iv2, orEdge);
909       ivf = iv2;
910     }
911
912     P1 = new Poly_PolygonOnTriangulation(aNewNodes,       aNewParams);
913     P2 = new Poly_PolygonOnTriangulation(aNewNodInStruct, aNewParams);
914   }
915
916   // last point
917   if (ivf != ivl)
918     addLinkToMesh(ivf, ivl, orEdge);
919
920   storePolygon(theEdge, P1, theDefEdge);
921   storePolygonSharedData(theEdge, P2, theDefEdge);
922 }
923
924 //=======================================================================
925 //function : storeInternalPolygon
926 //purpose  : 
927 //=======================================================================
928 void BRepMesh_FastDiscret::storePolygon(
929   const TopoDS_Edge&                         theEdge,
930   Handle(Poly_PolygonOnTriangulation)&       thePolygon,
931   const Standard_Real                        theDeflection)
932 {
933   thePolygon->Deflection(theDeflection);
934   if (myInternalEdges->IsBound(theEdge))
935   {
936     BRepMesh_PairOfPolygon& aPair = myInternalEdges->ChangeFind(theEdge);
937     if (theEdge.Orientation() == TopAbs_REVERSED)
938       aPair.Append(thePolygon);
939     else
940       aPair.Prepend(thePolygon);
941
942     return;
943   }
944
945   BRepMesh_PairOfPolygon aPair;
946   aPair.Append(thePolygon);
947   myInternalEdges->Bind(theEdge, aPair);
948 }
949
950 //=======================================================================
951 //function : storePolygonSharedData
952 //purpose  : 
953 //=======================================================================
954 void BRepMesh_FastDiscret::storePolygonSharedData(
955   const TopoDS_Edge&                         theEdge,
956   Handle(Poly_PolygonOnTriangulation)&       thePolygon,
957   const Standard_Real                        theDeflection)
958 {
959   thePolygon->Deflection(theDeflection);
960   BRepMesh_PairOfPolygon aPair;
961   aPair.Append(thePolygon);
962   myEdges.Bind(theEdge, aPair);
963 }
964
965 //=======================================================================
966 //function : GetFaceAttribute
967 //purpose  : 
968 //=======================================================================
969 Standard_Boolean BRepMesh_FastDiscret::GetFaceAttribute(
970   const TopoDS_Face&              theFace,
971   Handle(BRepMesh_FaceAttribute)& theAttribute ) const
972 {
973   if (myAttributes.IsBound(theFace))
974   {
975     theAttribute = myAttributes(theFace);
976     return Standard_True;
977   }
978
979   return Standard_False;
980 }
981
982 //=======================================================================
983 //function : RemoveFaceAttribute
984 //purpose  : 
985 //=======================================================================
986 void BRepMesh_FastDiscret::RemoveFaceAttribute(const TopoDS_Face& theFace)
987 {
988   if (myAttributes.IsBound(theFace))
989     myAttributes.UnBind(theFace);
990 }