0025310: Regressions in visualization
[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.Perform(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     myVertexEdgeMap = myAttribute->ChangeVertexEdgeMap();
228     myInternalEdges = myAttribute->ChangeInternalEdges();
229     Handle(BRepMesh_DataStructureOfDelaun)& aStructure =
230       myAttribute->ResetStructure();
231
232     if (!myWithShare)
233     {
234       myEdges.Clear();
235       myBoundaryVertices->Clear();
236       myBoundaryPoints->Clear();
237     }
238
239     Standard_Real defedge;
240     Standard_Integer nbEdge = 0;
241     Standard_Real savangle = myAngle;
242     Standard_Real cdef;
243     Standard_Real maxdef = 2.* BRepMesh_ShapeTool::MaxFaceTolerance(theFace);
244
245     Standard_Real defface = 0.;
246     if (!myRelative)
247       defface = Max(myDeflection, maxdef);
248
249     NCollection_Sequence<EdgePCurve>  aPCurves;
250     NCollection_Sequence<TopoDS_Edge> aFaceEdges;
251
252     const TopoDS_Face&                  aFace = myAttribute->Face();
253     const Handle(BRepAdaptor_HSurface)& gFace = myAttribute->Surface();
254     TopExp_Explorer aWireIt(aFace, TopAbs_WIRE);
255     for (; aWireIt.More(); aWireIt.Next())
256     {
257       TopExp_Explorer aEdgeIt(aWireIt.Current(), TopAbs_EDGE);
258       for (; aEdgeIt.More(); aEdgeIt.Next(), ++nbEdge)
259       {
260         const TopoDS_Edge& aEdge = TopoDS::Edge(aEdgeIt.Current());
261         if (!myMapdefle.IsBound(aEdge))
262         {
263           if (myRelative)
264           {
265             if (myEdges.IsBound(aEdge))
266             {
267               const BRepMesh_PairOfPolygon& aPair = myEdges.Find(aEdge);
268               const Handle(Poly_PolygonOnTriangulation)& aPolygon = aPair.First();
269               defedge = aPolygon->Deflection();
270             }
271             else
272             {
273               defedge = BRepMesh_ShapeTool::RelativeEdgeDeflection(
274                 aEdge, myDeflection, myDtotale, cdef);
275
276               myAngle = savangle * cdef;
277             }
278
279             defface += defedge;
280             defface = Max(maxdef, defface);
281           }
282           else
283           {
284             defedge = myDeflection;
285           }
286
287           defedge = Max(maxdef, defedge);
288           defedge = Max(UVDEFLECTION, defedge);
289           myMapdefle.Bind(aEdge, defedge);
290         }
291         else
292         {
293           defedge = myMapdefle(aEdge);
294           if ( myRelative )
295           {
296             defface += defedge;
297             defface = Max(maxdef, defface);
298           }
299         }
300
301         Standard_Real aFirstParam, aLastParam;
302         Handle(Geom2d_Curve) aCurve2d = 
303           BRep_Tool::CurveOnSurface(aEdge, aFace, aFirstParam, aLastParam);
304
305         if (aCurve2d.IsNull())
306           continue;
307
308         EdgePCurve aPCurve = { aCurve2d, aFirstParam, aLastParam };
309         aPCurves.Append(aPCurve);
310         aFaceEdges.Append(aEdge);
311
312         add(aEdge, aPCurve, defedge);
313         myAngle = savangle;
314       }
315     }
316
317     if ( nbEdge == 0 || myVertexEdgeMap->Extent() < 3 )
318     {
319       myAttribute->SetStatus(BRepMesh_Failure);
320       return myAttribute->GetStatus();
321     }
322
323     if ( myRelative )
324     {
325       defface = defface / nbEdge;
326     }
327     else
328     {
329       defface = myDeflection;
330     }
331
332     if ( myWithShare )
333       defface = Max(maxdef, defface);
334
335     TopLoc_Location aLoc;
336     Handle(Poly_Triangulation) aTriangulation = BRep_Tool::Triangulation(aFace, aLoc);
337
338     if (!myShapetrigu || aTriangulation.IsNull())
339     {
340       Standard_Real xCur, yCur;
341       Standard_Real maxX, minX, maxY, minY;
342
343       minX = minY = 1.e100;
344       maxX = maxY =-1.e100;
345
346       Standard_Integer ipn = 0;
347       Standard_Integer i1 = 1;
348       for ( i1 = 1; i1 <= myVertexEdgeMap->Extent(); ++i1 )
349       {
350         const BRepMesh_Vertex& aVertex = aStructure->GetNode(myVertexEdgeMap->FindKey(i1));
351
352         ++ipn;
353
354         xCur = aVertex.Coord().X();
355         yCur = aVertex.Coord().Y();
356
357         minX = Min(xCur, minX);
358         maxX = Max(xCur, maxX);
359         minY = Min(yCur, minY);
360         maxY = Max(yCur, maxY);
361       }
362
363       Standard_Real myumin = minX;
364       Standard_Real myumax = maxX;
365       Standard_Real myvmin = minY;
366       Standard_Real myvmax = maxY;
367
368       const Standard_Real umin = gFace->FirstUParameter();
369       const Standard_Real umax = gFace->LastUParameter();
370       const Standard_Real vmin = gFace->FirstVParameter();
371       const Standard_Real vmax = gFace->LastVParameter();
372
373       if (myumin < umin || myumax > umax)
374       {
375         if (gFace->IsUPeriodic())
376         {
377           if ((myumax - myumin) > (umax - umin))
378             myumax = myumin + (umax - umin);
379         }
380         else
381         {
382           if (umin > myumin)
383             myumin = umin;
384
385           if (umax < myumax)
386             myumax = umax;
387         }
388       }
389
390       if (myvmin < vmin || myvmax > vmax)
391       {
392         if (gFace->IsVPeriodic())
393         {
394           if ((myvmax - myvmin) > (vmax - vmin))
395             myvmax = myvmin + (vmax - vmin);
396         }
397         else
398         {
399           if ( vmin > myvmin )
400             myvmin = vmin;
401
402           if (vmax < myvmax)
403             myvmax = vmax;
404         }
405       }
406
407       GeomAbs_SurfaceType aSurfType = gFace->GetType();
408       // Fast verification of the validity of calculated limits.
409       // If wrong, sure a problem of pcurve.
410       if (aSurfType == GeomAbs_BezierSurface &&
411          (myumin < -0.5 || myumax > 1.5 || myvmin < -0.5 || myvmax > 1.5) )
412       {
413         myAttribute->SetStatus(BRepMesh_Failure);
414         return myAttribute->GetStatus();
415       }
416
417       //define parameters for correct parametrics
418       Standard_Real deltaX = 1.0;
419       Standard_Real deltaY = 1.0;
420
421       {
422         BRepMesh::HClassifier& aClassifier = myAttribute->ChangeClassifier();
423         BRepMesh_WireChecker aDFaceChecker(aFace, Precision::PConfusion(),
424           myInternalEdges, myVertexEdgeMap, aStructure,
425           myumin, myumax, myvmin, myvmax, myInParallel );
426
427         aDFaceChecker.ReCompute(aClassifier);
428         BRepMesh_Status aCheckStatus = aDFaceChecker.Status();
429
430         if (aCheckStatus == BRepMesh_SelfIntersectingWire)
431         {
432           Standard_Integer nbmaill = 0;
433           Standard_Real eps = Precision::Confusion();
434           while (nbmaill < 5 && aCheckStatus != BRepMesh_ReMesh)
435           {
436             ++nbmaill;
437
438             // Clear the structure of links
439             aStructure = myAttribute->ResetStructure();
440
441             
442             for (Standard_Integer j = 1; j <= aFaceEdges.Length(); ++j)
443             {
444               const TopoDS_Edge& anEdge = aFaceEdges(j);
445               if (myEdges.IsBound(anEdge))
446                 myEdges.UnBind(anEdge);
447
448               defedge = Max(myMapdefle(anEdge) / 3.0, eps);
449               myMapdefle.Bind(anEdge, defedge);
450
451               add(anEdge, aPCurves(j), defedge);
452             }
453
454             aDFaceChecker.ReCompute(aClassifier);
455             if (aDFaceChecker.Status() == BRepMesh_NoError)
456               aCheckStatus = BRepMesh_ReMesh;
457           }
458         }
459
460         myAttribute->SetStatus(aCheckStatus);
461         if (!myAttribute->IsValid())
462           //RemoveFaceAttribute(theFace);
463           return myAttribute->GetStatus();
464       }
465
466       // try to find the real length:
467       // akm (bug OCC16) : We must calculate these measures in non-singular
468       //     parts of face. Let's try to compute average value of three
469       //     (umin, (umin+umax)/2, umax), and respectively for v.
470       //                 vvvvv
471       Standard_Real longu = 0.0, longv = 0.0; //, last , first;
472       gp_Pnt P11, P12, P21, P22, P31, P32;
473
474       Standard_Real du = 0.05 * ( myumax - myumin );
475       Standard_Real dv = 0.05 * ( myvmax - myvmin );
476       Standard_Real dfuave = 0.5 * ( myumin + myumax );
477       Standard_Real dfvave = 0.5 * ( myvmin + myvmax );
478       Standard_Real dfucur, dfvcur;
479
480       // U loop
481       gFace->D0(myumin, myvmin, P11);
482       gFace->D0(myumin, dfvave, P21);
483       gFace->D0(myumin, myvmax, P31);
484       for (i1=1, dfucur=myumin+du; i1 <= 20; i1++, dfucur+=du)
485       {
486         gFace->D0(dfucur, myvmin, P12);
487         gFace->D0(dfucur, dfvave, P22);
488         gFace->D0(dfucur, myvmax, P32);
489         longu += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
490         P11 = P12;
491         P21 = P22;
492         P31 = P32;
493       }
494
495       // V loop
496       gFace->D0(myumin, myvmin, P11);
497       gFace->D0(dfuave, myvmin, P21);
498       gFace->D0(myumax, myvmin, P31);
499       for (i1=1, dfvcur=myvmin+dv; i1 <= 20; i1++, dfvcur+=dv)
500       {
501         gFace->D0(myumin, dfvcur, P12);
502         gFace->D0(dfuave, dfvcur, P22);
503         gFace->D0(myumax, dfvcur, P32);
504         longv += ( P11.Distance(P12) + P21.Distance(P22) + P31.Distance(P32) );
505         P11 = P12;
506         P21 = P22;
507         P31 = P32;
508       }
509
510       longu /= 3.;
511       longv /= 3.;
512       // akm (bug OCC16) ^^^^^
513
514       if (longu <= 1.e-16 || longv <= 1.e-16)
515       {
516         //yes, it is seen!!
517         myAttribute->SetStatus(BRepMesh_Failure);
518         return myAttribute->GetStatus();
519       }
520
521
522       if (aSurfType == GeomAbs_Torus)
523       {
524         gp_Torus Tor = gFace->Torus();
525         Standard_Real r = Tor.MinorRadius(), R = Tor.MajorRadius();
526         Standard_Real Du, Dv;//, pasu, pasv;
527
528         Dv = Max(1.0e0 - (defface/r),0.0e0) ;
529         Standard_Real oldDv = 2.0 * ACos (Dv);
530         oldDv = Min(oldDv, myAngle);
531         Dv  =  0.9*oldDv; //TWOTHIRD * oldDv;
532         Dv = oldDv;
533
534         Standard_Integer nbV = Max((Standard_Integer)((myvmax-myvmin)/Dv), 2);
535         Dv = (myvmax-myvmin)/(nbV+1);
536
537         Standard_Real ru = R + r;
538         if ( ru > 1.e-16 )
539         {
540           Du = Max(1.0e0 - (defface/ru),0.0e0);
541           Du  = (2.0 * ACos (Du));
542           Du = Min(Du, myAngle);
543           Standard_Real aa = sqrt(Du*Du + oldDv*oldDv);
544
545           if (aa < gp::Resolution())
546             return myAttribute->GetStatus();
547
548           Du = Du * Min(oldDv, Du) / aa;
549         }
550         else
551         {
552           Du = Dv;
553         }
554
555         Standard_Integer nbU = Max((Standard_Integer)((myumax-myumin)/Du), 2);
556         nbU = Max(nbU, (Standard_Integer)(nbV*(myumax-myumin)*R/((myvmax-myvmin)*r)/5.));
557       
558         Du = (myumax-myumin)/(nbU+1);
559         //-- DeltaX and DeltaY are chosen so that to avoid "jumping" 
560         //-- of points on the grid
561         deltaX = Du;
562         deltaY = Dv;
563       }
564       else if (aSurfType == GeomAbs_Cylinder)
565       {
566         gp_Cylinder Cyl = gFace->Cylinder();
567         Standard_Real R = Cyl.Radius();
568
569         // Calculate parameters for iteration in U direction
570         Standard_Real Du = 1.0 - (defface/R);
571         if (Du < 0.0)
572           Du = 0.0;
573
574         Du = 2.0 * ACos (Du);
575         if (Du > GetAngle())
576           Du = GetAngle();
577
578         deltaX = Du / longv;
579         deltaY = 1.;
580       }
581       else
582       {
583         deltaX = (myumax-myumin)/longu;
584         deltaY = (myvmax-myvmin)/longv;
585       }
586
587       // Restore face attribute
588       myAttribute->SetDefFace(defface);
589       myAttribute->SetUMax(myumax);
590       myAttribute->SetVMax(myvmax);
591       myAttribute->SetUMin(myumin);
592       myAttribute->SetVMin(myvmin);
593       myAttribute->SetDeltaX(deltaX);
594       myAttribute->SetDeltaY(deltaY);
595     }
596   }
597   catch(Standard_Failure)
598   {
599     myAttribute->SetStatus(BRepMesh_Failure);
600   }
601
602   return myAttribute->GetStatus();
603 }
604
605 //=======================================================================
606 //function : addLinkToMesh
607 //purpose  :
608 //=======================================================================
609 void BRepMesh_FastDiscret::addLinkToMesh(
610   const Standard_Integer   theFirstNodeId,
611   const Standard_Integer   theLastNodeId,
612   const TopAbs_Orientation theOrientation)
613 {
614   Handle(BRepMesh_DataStructureOfDelaun)& aStructure =
615     myAttribute->ChangeStructure();
616
617   if (theOrientation == TopAbs_FORWARD)
618     aStructure->AddLink(BRepMesh_Edge(theFirstNodeId, theLastNodeId, BRepMesh_Frontier));
619   else if (theOrientation == TopAbs_REVERSED)
620     aStructure->AddLink(BRepMesh_Edge(theLastNodeId, theFirstNodeId, BRepMesh_Frontier));
621   else if (theOrientation == TopAbs_INTERNAL)
622     aStructure->AddLink(BRepMesh_Edge(theFirstNodeId, theLastNodeId, BRepMesh_Fixed));
623 }
624
625 //=======================================================================
626 //function : getEdgeAttributes
627 //purpose  :
628 //=======================================================================
629 Standard_Boolean BRepMesh_FastDiscret::getEdgeAttributes(
630   const TopoDS_Edge&                      theEdge,
631   const BRepMesh_FastDiscret::EdgePCurve& thePCurve,
632   const Standard_Real                     theDefEdge,
633   BRepMesh_FastDiscret::EdgeAttributes&   theAttributes) const
634 {
635   EdgeAttributes& aEAttr = theAttributes;
636
637   // Get vertices
638   TopExp::Vertices(theEdge, aEAttr.FirstVertex, aEAttr.LastVertex);
639   if (aEAttr.FirstVertex.IsNull() || aEAttr.LastVertex.IsNull())
640     return Standard_False;
641
642   // Get range on 2d curve
643   const TopoDS_Face& aFace = myAttribute->Face();
644   BRep_Tool::Range(theEdge, aFace, aEAttr.FirstParam, aEAttr.LastParam);
645
646   // Get end points on 2d curve
647   BRep_Tool::UVPoints(theEdge, aFace, aEAttr.FirstUV, aEAttr.LastUV);
648
649   aEAttr.IsSameUV =
650     aEAttr.FirstUV.IsEqual(aEAttr.LastUV, Precision::PConfusion());
651
652   //Control tolerance of vertices
653   const Handle(BRepAdaptor_HSurface)& gFace = myAttribute->Surface();
654   gp_Pnt pFirst = gFace->Value(aEAttr.FirstUV.X(), aEAttr.FirstUV.Y());
655   gp_Pnt pLast  = gFace->Value(aEAttr.LastUV.X(),  aEAttr.LastUV.Y());
656
657   aEAttr.MinDist = 10. * Max(pFirst.Distance(BRep_Tool::Pnt(aEAttr.FirstVertex)),
658                              pLast .Distance(BRep_Tool::Pnt(aEAttr.LastVertex)));
659
660   if (aEAttr.MinDist < BRep_Tool::Tolerance(aEAttr.FirstVertex) ||
661       aEAttr.MinDist < BRep_Tool::Tolerance(aEAttr.LastVertex))
662   {
663     aEAttr.MinDist = theDefEdge;
664   }
665
666   if (aEAttr.IsSameUV)
667   {
668     // 1. is it really sameUV without being degenerated
669     gp_Pnt2d uvF, uvL;
670     thePCurve.Curve2d->D0(thePCurve.FirstParam, uvF);
671     thePCurve.Curve2d->D0(thePCurve.LastParam,  uvL);
672
673     if (!aEAttr.FirstUV.IsEqual(uvF, Precision::PConfusion()))
674       aEAttr.FirstUV = uvF;
675
676     if (!aEAttr.LastUV.IsEqual(uvL, Precision::PConfusion()))
677       aEAttr.LastUV = uvL;
678   }
679
680   return Standard_True;
681 }
682
683 //=======================================================================
684 //function : registerEdgeVertices
685 //purpose  : 
686 //=======================================================================
687 void BRepMesh_FastDiscret::registerEdgeVertices(
688   BRepMesh_FastDiscret::EdgeAttributes& theAttributes,
689   Standard_Integer&                     ipf,
690   Standard_Integer&                     ivf,
691   Standard_Integer&                     isvf,
692   Standard_Integer&                     ipl,
693   Standard_Integer&                     ivl,
694   Standard_Integer&                     isvl)
695 {
696   EdgeAttributes& aEAttr = theAttributes;
697   if (aEAttr.FirstVExtractor.IsNull())
698   {
699     // Use edge geometry to produce tesselation.
700     aEAttr.FirstVExtractor = 
701       new TopoDSVExplorer(aEAttr.FirstVertex, aEAttr.IsSameUV, aEAttr.LastVertex);
702   }
703
704   if (aEAttr.LastVExtractor.IsNull())
705   {
706     // Use edge geometry to produce tesselation.
707     aEAttr.LastVExtractor = 
708       new TopoDSVExplorer(aEAttr.LastVertex, aEAttr.IsSameUV, aEAttr.FirstVertex);
709   }
710
711   gp_XY aTmpUV;
712   // Process first vertex
713   ipf = myAttribute->GetVertexIndex(aEAttr.FirstVExtractor, Standard_True);
714   aTmpUV = BRepMesh_ShapeTool::FindUV(ipf, aEAttr.FirstUV, aEAttr.FirstVertex, 
715     aEAttr.MinDist, myAttribute);
716
717   myAttribute->AddNode(ipf, aTmpUV, BRepMesh_Frontier, ivf, isvf);
718
719   // Process last vertex
720   ipl = aEAttr.LastVertex.IsSame(aEAttr.FirstVertex) ? ipf :
721     myAttribute->GetVertexIndex(aEAttr.LastVExtractor, Standard_True);
722   aTmpUV = BRepMesh_ShapeTool::FindUV(ipl, aEAttr.LastUV, aEAttr.LastVertex, 
723     aEAttr.MinDist, myAttribute);
724
725   myAttribute->AddNode(ipl, aTmpUV, BRepMesh_Frontier, ivl, isvl);
726 }
727
728 //=======================================================================
729 //function : add
730 //purpose  : 
731 //=======================================================================
732 void BRepMesh_FastDiscret::add(
733   const TopoDS_Edge&                      theEdge,
734   const BRepMesh_FastDiscret::EdgePCurve& thePCurve,
735   const Standard_Real                     theDefEdge)
736 {
737   const TopAbs_Orientation orEdge = theEdge.Orientation();
738   if (orEdge == TopAbs_EXTERNAL)
739     return;
740
741   EdgeAttributes aEAttr;
742   if (!getEdgeAttributes(theEdge, thePCurve, theDefEdge, aEAttr))
743     return;
744
745   if (!myEdges.IsBound(theEdge))
746   {
747     update(theEdge, thePCurve.Curve2d, theDefEdge, aEAttr);
748     return;
749   }
750
751   Standard_Integer ipf, ivf, isvf, ipl, ivl, isvl;
752   registerEdgeVertices(aEAttr, ipf, ivf, isvf, ipl, ivl, isvl);
753
754   // If this Edge has been already checked and it is not degenerated, 
755   // the points of the polygon calculated at the first check are retrieved :
756
757   // retrieve the polygone:
758   const BRepMesh_PairOfPolygon&              aPair    = myEdges.Find(theEdge);
759   const Handle(Poly_PolygonOnTriangulation)& aPolygon = aPair.First();
760   const TColStd_Array1OfInteger&             aNodes   = aPolygon->Nodes();
761   Handle(TColStd_HArray1OfReal)              aParams  = aPolygon->Parameters();
762
763   // creation anew:
764   const Standard_Integer  aNodesNb = aNodes.Length();
765   TColStd_Array1OfInteger aNewNodes (1, aNodesNb);
766   TColStd_Array1OfReal    aNewParams(1, aNodesNb);
767
768   aNewNodes (1) = isvf;
769   aNewParams(1) = aEAttr.FirstParam;
770
771   aNewNodes (aNodesNb) = isvl;
772   aNewParams(aNodesNb) = aEAttr.LastParam;
773
774   const TopoDS_Face& aFace = myAttribute->Face();
775   if (!BRepMesh_ShapeTool::IsDegenerated(theEdge, aFace))
776   {
777     BRepMesh_EdgeParameterProvider aProvider(theEdge, aFace, aParams);
778     for (Standard_Integer i = 2; i < aNodesNb; ++i)
779     {
780       const Standard_Integer aPointId = aNodes(i);
781       const gp_Pnt& aPnt = myBoundaryPoints->Find(aPointId);
782
783       const Standard_Real aParam = aProvider.Parameter(i, aPnt);
784       gp_Pnt2d aUV = thePCurve.Curve2d->Value(aParam);
785
786       Standard_Integer iv2, isv;
787       myAttribute->AddNode(aPointId, aUV.Coord(), BRepMesh_OnCurve, iv2, isv);
788
789       aNewNodes (i) = isv;
790       aNewParams(i) = aParam;
791
792       addLinkToMesh(ivf, iv2, orEdge);
793       ivf = iv2;
794     }
795
796     // last point
797     if (ivf != ivl)
798       addLinkToMesh(ivf, ivl, orEdge);
799   }
800
801   Handle(Poly_PolygonOnTriangulation) P1 = 
802     new Poly_PolygonOnTriangulation(aNewNodes, aNewParams);
803
804   storePolygon(theEdge, P1, theDefEdge);
805 }
806
807 //=======================================================================
808 //function : update(edge)
809 //purpose  :
810 //=======================================================================
811 void BRepMesh_FastDiscret::update(
812   const TopoDS_Edge&                                theEdge,
813   const Handle(Geom2d_Curve)&                       theC2d,
814   const Standard_Real                               theDefEdge,
815   BRepMesh_FastDiscret::EdgeAttributes&             theAttributes)
816 {
817   EdgeAttributes& aEAttr = theAttributes;
818
819   const TopoDS_Face& aFace = myAttribute->Face();
820   Handle(BRepMesh_IEdgeTool) aEdgeTool;
821   // Try to find existing tessellation.
822   for (Standard_Integer i = 1; aEdgeTool.IsNull(); ++i)
823   {
824     TopLoc_Location aLoc;
825     Handle(Poly_Triangulation) aTriangulation;
826     Handle(Poly_PolygonOnTriangulation) aPolygon;
827     BRep_Tool::PolygonOnTriangulation(theEdge, aPolygon, aTriangulation, aLoc, i);
828
829     if (aPolygon.IsNull())
830       break;
831
832     if (aTriangulation.IsNull() || !aPolygon->HasParameters())
833       continue;
834
835     if (aPolygon->Deflection() > 1.1 * theDefEdge)
836       continue;
837
838     const TColgp_Array1OfPnt&      aNodes   = aTriangulation->Nodes();
839     const TColStd_Array1OfInteger& aIndices = aPolygon->Nodes();
840     Handle(TColStd_HArray1OfReal)  aParams  = aPolygon->Parameters();
841
842     aEAttr.FirstVExtractor = new PolyVExplorer(aEAttr.FirstVertex, 
843       aEAttr.IsSameUV, aEAttr.LastVertex, aIndices(1), aNodes, aLoc);
844
845     aEAttr.LastVExtractor = new PolyVExplorer(aEAttr.LastVertex, 
846       aEAttr.IsSameUV, aEAttr.FirstVertex, aIndices(aIndices.Length()), aNodes, aLoc);
847
848     aEdgeTool = new BRepMesh_EdgeTessellationExtractor(theEdge, theC2d, 
849       aFace, aTriangulation, aPolygon, aLoc);
850   }
851
852   if (aEdgeTool.IsNull())
853   {
854     aEdgeTool = new BRepMesh_EdgeTessellator(theEdge, myAttribute, 
855       mySharedFaces, theDefEdge, myAngle);
856   }
857
858   Standard_Integer ipf, ivf, isvf, ipl, ivl, isvl;
859   registerEdgeVertices(aEAttr, ipf, ivf, isvf, ipl, ivl, isvl);
860
861   TopAbs_Orientation orEdge = theEdge.Orientation();
862   Handle(Poly_PolygonOnTriangulation) P1, P2;
863   if (BRepMesh_ShapeTool::IsDegenerated(theEdge, aFace))
864   {
865     const Standard_Integer  aNodesNb = 2;
866     TColStd_Array1OfInteger aNewNodes      (1, aNodesNb);
867     TColStd_Array1OfInteger aNewNodInStruct(1, aNodesNb);
868     TColStd_Array1OfReal    aNewParams     (1, aNodesNb);
869
870     aNewNodInStruct(1) = ipf;
871     aNewNodes      (1) = isvf;
872     aNewParams     (1) = aEAttr.FirstParam;
873
874     aNewNodInStruct(aNodesNb) = ipl;
875     aNewNodes      (aNodesNb) = isvl;
876     aNewParams     (aNodesNb) = aEAttr.LastParam;
877
878     P1 = new Poly_PolygonOnTriangulation(aNewNodes,       aNewParams);
879     P2 = new Poly_PolygonOnTriangulation(aNewNodInStruct, aNewParams);
880   }
881   else
882   {
883     const Standard_Integer  aNodesNb = aEdgeTool->NbPoints();
884     TColStd_Array1OfInteger aNewNodes      (1, aNodesNb);
885     TColStd_Array1OfInteger aNewNodInStruct(1, aNodesNb);
886     TColStd_Array1OfReal    aNewParams     (1, aNodesNb);
887
888     aNewNodInStruct(1) = ipf;
889     aNewNodes      (1) = isvf;
890     aNewParams     (1) = aEAttr.FirstParam;
891
892     aNewNodInStruct(aNodesNb) = ipl;
893     aNewNodes      (aNodesNb) = isvl;
894     aNewParams     (aNodesNb) = aEAttr.LastParam;
895
896     Standard_Integer aLastPointId = myAttribute->LastPointId();
897     for (Standard_Integer i = 2; i < aNodesNb; ++i)
898     {
899       gp_Pnt        aPnt;
900       gp_Pnt2d      aUV;
901       Standard_Real aParam;
902       aEdgeTool->Value(i, aParam, aPnt, aUV);
903       myBoundaryPoints->Bind(++aLastPointId, aPnt);
904
905       Standard_Integer iv2, isv;
906       myAttribute->AddNode(aLastPointId, aUV.Coord(), BRepMesh_Frontier, iv2, isv);
907
908       aNewNodInStruct(i) = aLastPointId;
909       aNewNodes      (i) = isv;
910       aNewParams     (i) = aParam;
911
912       addLinkToMesh(ivf, iv2, orEdge);
913       ivf = iv2;
914     }
915
916     P1 = new Poly_PolygonOnTriangulation(aNewNodes,       aNewParams);
917     P2 = new Poly_PolygonOnTriangulation(aNewNodInStruct, aNewParams);
918   }
919
920   // last point
921   if (ivf != ivl)
922     addLinkToMesh(ivf, ivl, orEdge);
923
924   storePolygon(theEdge, P1, theDefEdge);
925   storePolygonSharedData(theEdge, P2, theDefEdge);
926 }
927
928 //=======================================================================
929 //function : storeInternalPolygon
930 //purpose  : 
931 //=======================================================================
932 void BRepMesh_FastDiscret::storePolygon(
933   const TopoDS_Edge&                         theEdge,
934   Handle(Poly_PolygonOnTriangulation)&       thePolygon,
935   const Standard_Real                        theDeflection)
936 {
937   thePolygon->Deflection(theDeflection);
938   if (myInternalEdges->IsBound(theEdge))
939   {
940     BRepMesh_PairOfPolygon& aPair = myInternalEdges->ChangeFind(theEdge);
941     if (theEdge.Orientation() == TopAbs_REVERSED)
942       aPair.Append(thePolygon);
943     else
944       aPair.Prepend(thePolygon);
945
946     return;
947   }
948
949   BRepMesh_PairOfPolygon aPair;
950   aPair.Append(thePolygon);
951   myInternalEdges->Bind(theEdge, aPair);
952 }
953
954 //=======================================================================
955 //function : storePolygonSharedData
956 //purpose  : 
957 //=======================================================================
958 void BRepMesh_FastDiscret::storePolygonSharedData(
959   const TopoDS_Edge&                         theEdge,
960   Handle(Poly_PolygonOnTriangulation)&       thePolygon,
961   const Standard_Real                        theDeflection)
962 {
963   thePolygon->Deflection(theDeflection);
964   BRepMesh_PairOfPolygon aPair;
965   aPair.Append(thePolygon);
966   myEdges.Bind(theEdge, aPair);
967 }
968
969 //=======================================================================
970 //function : GetFaceAttribute
971 //purpose  : 
972 //=======================================================================
973 Standard_Boolean BRepMesh_FastDiscret::GetFaceAttribute(
974   const TopoDS_Face&              theFace,
975   Handle(BRepMesh_FaceAttribute)& theAttribute ) const
976 {
977   if (myAttributes.IsBound(theFace))
978   {
979     theAttribute = myAttributes(theFace);
980     return Standard_True;
981   }
982
983   return Standard_False;
984 }
985
986 //=======================================================================
987 //function : RemoveFaceAttribute
988 //purpose  : 
989 //=======================================================================
990 void BRepMesh_FastDiscret::RemoveFaceAttribute(const TopoDS_Face& theFace)
991 {
992   if (myAttributes.IsBound(theFace))
993     myAttributes.UnBind(theFace);
994 }